【摘要】 为了解决K-means算法对初始聚类数k和初始聚类中心经验参数的依赖问题,提出了一种基于最小生成树的无参数化聚类MNC算法(MST based Non-parameterized Clustering).首先将待聚类数据集抽象成赋权完全图WCG(Weighted Complete Graph),其中的点代表向量,赋权边代表数据间的相似关系;然后将WCG转换成全连通的最小生成树M ST(M inimum Spanning Tree);接着利用k=2的经典K-means算法对M ST边集的一维权重空间进行聚类,得到剪枝的阈值;最后对M ST进行剪枝和噪声过滤,得到的连通分量即为聚类的簇.实验结果表明,相对传统聚类算法,MNC算法不仅能够识别不同形状的数据簇,而且其无参数化的特点可以大大减少聚类时间,提高聚类效率.更多还原

【Abstract】 In order to solve the dependence problem on empirical parameters,such as cluster number k and initial centroids,of K-means algorithm,a novel M inimum Spanning Tree based non-parameterized clustering algorithm,named M NC( M ST based Non-parameterized Clustering),is proposed. Firstly,the data set in server is abstracted into a Weighted Complete Graph( WCG),where the points represent the data samples and the weighted edges represent the similarity relationship between the samples. Then the WCG is converted to the fully connected M inimum Spanning Tree( M ST) and the pruning threshold is generated by the traditional k = 2 clustering of the M ST’s one-dimensional weight space. Finally the M ST is pruned and noise filtered,with the resultant connected components correspond to the output clusters. The experimental results show that when compared to traditional clustering algorithms,not only different shape of clusters can be successfully identified,but also the computational complexity can be decreased due to the non-parameterized characteristic of M NC.更多还原