最小生成树聚类方法研究

由聚类所生成的簇是一组数据对象的集合,在同一个类中的对象之间具有较高的相似度,而不同类中的对象差别较大.图的最小生成树具有最优子结构性质,删除最小生成树的最大边后的两颗子树依然分别是两个子图的最小生成树,因此可由生成图的最小生成树获得聚类.此方法适用于所有欧氏空间数据的聚类.     

针对K-means初始聚类中心优化的PCA-TDKM算法

K-means算法在聚类过程中随机选取k个初始聚类中心,容易造成聚类结果不稳定。针对该问题,提出PCA-TDKM算法：使用主成分分析法对数据对象集合的属性进行降维,提取出主属性,去掉无关属性,从而加速聚类过程;基于最小生成树算法及树的剪枝方法将数据对象划分为k个初始聚类簇,然后进行剪枝生成k棵子树,计算每棵子树中所有数据对象的均值,作为初始聚类中心;利用基于密度与最大最小距离的算法思想进行聚类。将PCA-TDKM算法与K-means、KNE-KM、QMC KM、CFSFDP-KM在UCI数据集上进行聚类比较,结果表明该算法聚类结果稳定、聚类准确率高。     

乘积图生成树的Wiener数问题

研究了给定一个连通图,如何确定其Wiener数最小的生成树问题。Dobrynin等构造了超立方体的两类Wiener数“很小”的生成树,并进一步猜想这两类树都是Wiener数最小的生成树。利用归纳推理及递归关系,对更一般的且具有良好拓扑性质和较高网络模型应用价值的乘积图,如G1×G2、Kmn等,构造了相应的生成树并计算了它们的Wiener数的值,以期获得这些乘积图Wiener数最小的生成树。这些结果推广了Dobrynin关于超立方体的结果。     

基于网格和密度的数据流聚类算法

针对数据流的特点,提出了一种新的网格密度结合的GCTS算法.它采用了双层架构,在线层实现了网格密度参数的自设定,离线层以网格单元的重心为中心点,建立一个最大的子网格,使候选网格中的局部密集区域转化成了密集网格.最后使用最小生成树的算法生成进行聚类结果.提高了聚类效果.     

图结构上下文及在图聚类中的应用

图结构特征的提取以及距离度量是计算机视觉和模式识别中的重要内容.针对传统的图上下文描述子中只考虑每个柱形区域内的特征点数目而忽略特征点之间的结构信息的问题,提出一种图的结构上下文描述子及距离度量方法.首先对图的所有顶点建立图结构上下文描述子;其次,利用二次卡方(QC)距离方法实现图的距离度量;最后,采用最小生成树聚类算法实现图聚类.实验表明,该方法对于一些非刚性变换的图聚类有较好的效果.     

广义最小生成树的遗传算法研究

本文考虑到节点度的代价问题 ,提出了广义最小生成树的概念 ,并分析了最小生成树在实际应用中的局限性 .针对一般遗传算法求解该问题的不足 ,提出了自调整的变异算子和混合选择策略 .通过仿真 ,证明了广义最小生成树模型的适用性 .最后将改进前后两种算法的仿真结果进行比较 ,证明了改进后遗传算法的有效性 .     

关于生成树的计数问题

本文论证了对连通图G的生成树的计数问题可归之于计算其块图的生成树的棵数问题,从而提供了计算图G的生成树数目的一种简便的计算方法。关键词:生成树,割边,制点,块图计算连通图G中生成树的数目,是图论计数问题中一个重要而且有趣的课题。目前已经有一些计算生成树数目的方法和公式。本文拟在现有计算公式基础上对若干图类的生成树的计数问题提供简便的计算方法。     

破圈法构造最小生成树算法探讨

求解最小生成树是《数据结构》课程教学中的一个学生重点学习的图论问题,但是目前的教材中普遍讲解Prim算法和Kruskal算法,这两个算法的基本思想均是基于避圈法。而从相反的角度求解最小生成树:破圈法构造最小生成树算法,虽然该算法的时间复杂度较高(O(n3)),但从教学的角度来看,有利于训练学生深刻理解和掌握最小生成树算法。     

无向图的第二大生成树的算法

在一个有生成树的赋权图 G=(V,E)中,其最大生成树的算法是早已解决了的.但它是否还有第二大生成树呢?如果有,又如何去求它呢?关于这个问题,本文给出了解答.在一个无向图 G=(V,E)中,来规定各条边的方向.对于图 G 的每一条边 e∈E,规定一个权α(e)∈R~+(R~+是非负实数集合),树的权定义为树的各条边的权之和,对于图 G 的一棵生成树,如果它具有最大可能权,称这棵树为 G 的最大生成树.如果图 G 的生成树具有     

最小生成树的应用及拓展探讨

最小生成树的求解在很多关于最小成本的问题中具有多种应用,本文探讨了求最小生成树的拓展问题的算法,并给出了这种算法的应用.     

能力集扩展的表格方法

每个具有非对称权重的有向图均可用一个称为“扩展表”的矩阵或表格来表示 .讨论了扩展表中的“圈”和“生成表”的概念及其基本特性 ,给出了一种寻找有向图最小生成树的表格方法——最小生成表法 .研究了最小生成表算法在最优能力集扩展问题中的应用 ,给出了一个算法的具体示例 ,并分析了有关的需研究的问题和可能的拓展     

关于图的临界群的秩

图的临界群决定了其支撑树的内部结构,因而支撑树的很多性质可以通过研究图的临界群得到.作为顶点数有限的图,其临界群是一个有限生成的群.该群的生成元的数目显示了群结构的复杂性.所需要用到的生成元的最小数目即为临界群的秩.在不引起混淆的情况下,临界群的秩也被称为图的秩.秩越小,临界群的需要的生成元的数目也就越小,研究的难度也相应越小.有一部分图的秩的下界可以通过计算直接得到.     

关于Kruskal算法的一个简便实现

根据数据结构中求一个带权无向连通图的最小生成树算法的特点,文章给出了Kruskal算法的一个简便而完整的C语言实现。特别是对不连通子图的刻画,只引进了一个一维数组就解决了问题。     

赋权图的最小环路遍历路径分析与研究

文章联系实际问题,结合旅行商问题和中国邮递员问题,提出赋权连通图中最小环路遍历路径以及求解该路径的方案.该方案参考最小生成树的普里姆算法,依据狄杰斯特拉算法,通过往返最短路径逐次比较,在赋权连通图中实现寻找最小环路遍历路径.     

基于最小生成树的图论模型及其在医学中的应用

样本数据分类是医学研究中常见的工具。本文提出了一种新的数据分类思想和方法。在分析分类过程及其主要矛盾的基础上，提出了极大λ-截子图的概念。作为示范，建立了三个基于最小生成树的图论模型，并分析了其在研究营养与疾病的关系以及基因分类中的应用。最后讨论了图论在医学中的应用前景。     

Kruskal算法的一种高效实现方法

kruskal算法是一种求连通图的最小生成树的算法,无论是采用"避圈法",还是采用"破圈法",都要用到圈的判断,文章基于此,分析提出一种高效实用的判断树中是否存在圈的方法.     

贵州雷公山秃杉种群分布格局的研究

采用相邻格子样方法取样数据,应用方差/均值比的t检验法、负二项参数、格林指数、Cassie指标、扩散指数、聚集度指标、平均拥挤度、聚块性指数等方法,研究了贵州雷公山秃杉种群的空间分布格局及其动态.结果表明:秃杉种群空间格局为聚集分布;从幼苗到大树,其聚集程度和规模逐渐减小,大树呈均匀分布.