基于一种有效性函数的k—means算法

孙秀娟

摘 要：传统的K-means算法要求事先给出聚类数k值，从而导致聚类质量的下降。本文提出一种基于聚类有效性函数IG的K-means算法，該函数定义为数据特征轴总长度的平方与最小类间距的比值，当比值达到最小时对应的值为最佳聚类数k。而且，与其它有效性函数比较，IG能高效处理簇密度不同的数据集。实验证明，改进算法提高了聚类质量。

关键词：K-means；聚类；IG

K-means算法是一种最广泛使用的聚类划分方法。传统的K-means算法需要预先指定聚类数k，如果初始k选取得不合适，会使聚类结果产生较大的偏差。多数情况下，聚类数k事先无法确定，因此需要对最佳聚类数k进行搜索。搜索最佳k值的有效方法是构造聚类有效性函数。因此，本文提出一种基于几何结构的新聚类有效性函数，该函数被定义为数据特征轴总长度的平方与最小类间距的比值，最优聚类数为比值达到最小时对应的k值。

1 改进的k-means算法

1.1 IG函数

一般来说，聚类有效性函数的构造主要是从反映类内紧致性和类间分离度入手，其关键在于构造一个能使两个指标有机结合的数学表达式。本文提出一种新聚类有效性函数，该函数可使以上两个指标有机结合。聚类有效函数定义如下：

其中λjm是类Cm中数据协方差矩阵的特征值，假设Mm为类Cm中数据对象的平均值， ，Vm是类Cm的中心， 是两个类中心Vm、Vn的欧氏距离。

1.2 基于IG函数的k-means算法

2 实验

下面本文使用两种数据集对聚类有效性函数IG、CH和I进行测试比较。CH函数计算簇间距离和簇内距离的比例，CH值越大，代表聚类效果越好；有效性函数I（k）最大时对应的k值就是最优的簇个数。对每个有效性函数，将其对应的算法（IG对应文中的算法2，将算法2中的IG函数改为CH、I后的算法就是CH、I分别对应的算法）分别运行30次。我们将比较每个有效性函数达到最优时对应的k值。

3 结论

本文提出了一种确定与数据实际分布相符合的簇数目k的有效性函数，该函数定义为计算聚类中数据特征轴总长度的平方与最小类间距之比，当该比值达到最小时，聚类结果是最优的，此时对应的聚类数也是最佳的。实验表明IG函数与其它有效性函数相比，该函数对类（簇）密度不同的数据集有较好的聚类效果，能正确发现簇的个数。

[参考文献]

[1]孙士保，秦克云.改进的k-平均聚类算法研究[J].计算机工程，2007，33（13）：200-201.