自适应样本和特征加权的k-means算法

Adaptive sample and feature weighted k-means algorithm

针对k-means算法在处理一些同时具备样本噪声与特征噪声的数据集时表现不佳的问题,提出一种自适应样本和特征加权的k-means聚类算法(ASFW)。所提算法引入负熵和一种正则化项,在每次迭代中自适应地调整样本和特征权重,并通过一种新的距离度量函数向最优解进行退火,可以有效避免得到较差的局部最小值,同时保持经典k-means算法的简单性。在人工合成数据集的聚类结果表明,相较于同类算法,ASFW的聚类效果更好,且对噪声样本和特征赋予的权值更正确合理,说明所提算法能够有效识别噪声,降低噪声对聚类结果的影响;在6个真实数据集下的聚类结果显示,ASFW在各个数据集的聚类性能均优于对比算法,且在大多数数据集上取得了最佳的标准互信息(NMI)和调整兰德系数(ARI),充分验证了ASFW具有良好的聚类性能。

Aiming at the problem that k-means algorithm had poor performance in processing some data sets with both sample noise and feature noise,an Adaptive Sample and Feature-Weighted k-means clustering algorithm(ASFW)was proposed.The negative entropy and a regularization term were introduced into the proposed algorithm to adaptively adjust the sample and feature weights in each iteration,and anneal the optimal solution through a novel distance measure function,which effectively avoided getting a poor local minimum while maintaining the simplicity of the classical k-means algorithm.The clustering results on artificially designed synthetic data sets show that,compared with similar algorithms,ASFW has better clustering effect,and the weights given to noise samples and features are more correct and reasonable,indicating that the proposed algorithm can effectively identify noise and reduce its influence on clustering results.The clustering results under 6 real data sets show that the clustering performance of ASFW is superior to the comparison algorithms in all data sets,and the best Normalized Mutual Information(NMI)and Adjusted Rand Index(ARI)are obtained on most data sets,which fully verifies the good clustering performance of ASFW.