An improved clustering algorithm for minimum spanning trees in multidimensional data

作者：Xie Zhi Qiang^*; Yu Liang; Yang Jing

来源：Journal of Harbin Engineering University, 2008, 29(8): 851-857.

• Clustering algorithm
• Clustering quality
• Matrix
• Maximal degree
• Medoid
• Minimal-spanning-tree
• Minimum spanning trees
• MST(minimum spanning tree)
• Multi-dimensional data
• New algorithm
• Quality of clustering
• Spanning trees
• Time complexities

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 deserting 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 the medoid. The new algorithm can cluster such MSTs in which several clusters are connected with ort edges or edges with same length. So that it improves the efficiency and quality of clustering. Follow-g an analysis on multi-dimensional data and the calculation of disparity of each attribute, it is found that ';me 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.

• 出版日期2008
• 单位哈尔滨工程大学