【摘要】 针对传统的应用于基因表示的最小生成树(MST)聚类算法在时间复杂度和聚类质量上的不足,提出了一种新的应用于数据处理的改进最小生成树(IMST)的聚类算法.该算法在提高构造最小生成树的效率的同时,通过对初步划分的生成树用矩阵表示,以度最大的结点作为聚类中心,再根据中心点算法完成聚类,解决了以往最小生成树算法无法解决的多个簇用短边或长度相同的边相连无法分类的问题,从而提高了聚类速度,改善了聚类的质量.通过对多维数据进行分析,计算各个属性的差异度,得出结论:一些属性的存在对于构造最小生成树有很小的影响或没有影响,删除这些属性列也可以提高效率,达到减少计算复杂性的目的.更多还原

【Abstract】 Conventional minimal spanning tree(MST) clustering algorithm has some defects in time complexity and clustering quality when it is applied to genetic databases with great complexity.So an improved clustering algorithm is put forward for data process,which greatly raises the efficiency in constructing the MST.With this method,we first use the matrix form to express the spanning tree that are roughly divided;then we complete the clustering with medoid algorithm,where the node with maximal degree is chosen as the medoid.The new algorithm can cluster such MSTs in which several clusters are connected with short edges or edges with same length.So that it improves the efficiency and quality of clustering.Following an analysis on multi-dimensional data and the calculation of disparity of each attribute,it is found that some attributes have little or no effect on the construction of the spanning tree.On the contrary,the efficiency can be improved and complexity decreased if those attributes are neglected.更多还原