多维数据K-means谱聚类算法改进研究

Research on Modification of K-means Spectral Clustering Algorithm of Multidimensional Data

针对传统K-means算法不能自动确定初始聚类数目k和谱聚类算法对参数敏感的问题,提出了一种基于谱聚类的K-means(PK-means)算法。该算法在对k值选取时进行了创新改进,将计算所得的高密度数据点按规律排序,选择密度点前96%的进行聚类,可以以较高的准确率取得聚类数目k,同时采用了不受参数影响且稳定性更高的基于谱聚类模糊的相似性度量方法,利用FCM算法求隶属度矩阵确定数据点间的相似性。应用PK-means算法、K均值算法与密度敏感的谱聚类算法(DSSC)进行了多维非线性数据处理的测试实验。实验结果表明,无论是对于低维数据集还是高维数据集,K-means算法的处理效率是最低的,DSSC算法稍好,而PK-means算法优势明显,其相比传统聚类算法具有更高的聚类精度和更强的鲁棒性,且维数越高,聚类性能表现越突出。

Aiming at the problem that the traditional K -means algorithm cannot determine the initial cluster number k automatically and spectral clustering algorithm is sensitive to parameter, a new K -means algorithm based on spectral clustering called PK-means is pro- posed. It makes improvement and innovation in selection of k values, sorts the calculated high density data points orderly, and then picks out the frontal 96% density point to cluster,so that the number of clusters k can be obtained with high accuracy. In the meantime,it also selects the unaffected and higher stable similarity measure method based on spectral clustering fuzziness and uses the FCM algorithm for membership degree matrix so as to determine the similarity between data points. The PK-means, K-means and DSSC have been em- ployed to deal with multi-dimensional nonlinear datasets. The experimental results show that whether the selected data source is low di- mension or high dimension,the efficiency of K -means is the lowest, followed by DSSC, and PK-means owns obvious advantages which always has the higher clustering accuracy and stronger robustness than the traditional clustering algorithm. The higher the dimension, the more prominent the clustering performance.