一种基于特征加权的K-Means算法研究

聚类分析是将研究对象分为相对同质的群组的统计分析技术，聚类分析的核心就是发现有用的对象簇。

数据挖掘是目前人工智能和数据库领域研究的热点问题，指从大量的数据中提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。聚类分析现在已经成为数据挖掘领域中一个非常重要的研究方向。MacQueen 提出[1]的K-means 算法是聚类分析中最常用的方法之一。它采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标[2]。K-means 算法假设样本的每个特征对最终聚类的贡献程度一样， 但在实际情况中某些特征在聚类的过程中起到很大的作用， 而某些特征的作用却很小， 甚至对聚类过程没有影响。

针对传统K-means 算法的这一问题，学者们进行了大量研究，研究表明：通过对特征赋予不同的特征权值，能够有效解决上述问题并提高聚类性能。目前，计算特征权重的算法有很多种：刘铭[3]等人提出一种结合限制数据的特征权值量化函数，该函数通过用户指定的限制数据进行特征权值量化并对不同的限制数据赋予不同的置信度，解决了限制数据分布不均匀和限制数据中可能包含不一致性的问题；Li Jie [4]等人提出将针对分类问题的ReliefF 算法应用于聚类问题， 通过ReliefF 算法计算特征权重值， 并对各维特征进行加权，提高聚类的性能；Meng Qian [5]等人提出通过梯度下降技术最小化特征评估函数FLearning (w)为每个特征分配权重并进行加权，该算法采用遗传算法和模拟退火算法的优点，减弱冗余特征的影响，解决了容易陷入局部最优解的问题。Songtao Shang [6]等人提出一种改进的基尼指数算法计算特征权重， 该算法克服了原始Gini 的缺点， 将条件概率与后验概率结合， 抑制训练集不平衡时的影响。

杨玉梅[7]利用信息论中的信息熵计算特征权重并对各位特征加权，有效的解决了特征对聚类的影响。

综上所述，为了提高传统K-means 算法的聚类精度，国内外学者对K-means 算法进行了大量改进探索研究，并取得了一些阶段性的成果。本文拟研究传统K-means 算法在聚类过程中聚类对象的每个特征对聚类结果的贡献度，使贡献程度大的特征优先利用，理论上讲可以有效提升K-means 算法聚类的准确率和精度。因此，本文提出将熵值法和ReliefF 特征选择算法有机融合，通过采用信息熵和ReliefF 特征选择算法对特征进行加权选择，修正聚类对象间的距离函数，使算法达到更准确更高效的聚类效果。实验结果表明，改进后的算法聚类结果稳定，且具有较高的准确率，达到预期目的。

2. K-means 算法 K-means 算法的核心思想是通过迭代把数据对象划分到不同的簇中，以求目标函数最小化，从而使