网站原创摘 要：传统的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函数
一般来说,聚类有效性函数的构造主要是从反映类内紧致性和类间分离度入手,其关键在于构造一个能使两个指标有机结合的数学表达式.本文提出一种新聚类有效性函数,该函数可使以上两个指标有机结合.聚类有效函数定义如下：
| 有关论文范文主题研究: | 关于函数的论文范文集 | 大学生适用: | 大学毕业论文、学术论文 |
|---|---|---|---|
| 相关参考文献下载数量: | 21 | 写作解决问题: | 怎么撰写 |
| 毕业论文开题报告: | 论文模板、论文摘要 | 职称论文适用: | 期刊发表、初级职称 |
| 所属大学生专业类别: | 怎么撰写 | 论文题目推荐度: | 经典题目 |
其中λ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.