林 丽,薛 芳
(1.集美大学计算机学院,福建 厦门 361021;2.集美大学信息化中心,福建 厦门 361021)
聚类分析在数据挖掘、文本摘要、图像识别领域有广泛应用,它是一种非常重要的机器学习算法。聚类算法能自动把数据对象划分成不同类别,每个类别中数据具有相似特征。通过聚类算法,可以在茫茫数据中挖出数据的规律。K-means算法是一种基于划分的硬聚类算法,其运算速度快,尤其适用于高维数据、大规模及文本数据的聚类,是目前比较常用的一种聚类算法。
K-means算法的做法是随机选择K个聚类中心,通过欧式距离计算各个样本和聚类中心的相似度。将样本分配给距离最近的类。K-means算法存在2个问题:1)聚类结果不稳定;2)用欧式距离计算样本相似度。所有特征参与欧式距离计算且贡献度都一样,这往往带有大小不等的随机波动。针对问题1),文献[1-3]提出K-means++算法,其采用概率来选择初始聚类中心,极大改善了传统K-means算法随机选择聚类中心的不确定性,提高聚类准确率。但是K-means++算法只考虑优化聚类中心,并没有考虑特征的不同贡献。关于问题2)存在如下例子:如有二维样本(身高,体重),其中身高数值范围是150~190,体重数值范围是50~60,现有三个样本:a(180,50),b(190,50),c(180,60)。按照欧式距离计算样本相似度,Dist(a,b)=Dist(a,c),那么身高10 cm真的等价于体重10 kg么?显然不是。而根据不同特征贡献加权的欧式距离去计算,样本的相似度才更准确。关于特征加权,文献[4-5]提出通过特征的总方差、均值来表示特征权重,但是方差并不能准确表示特征的差异情况。……