基于Kmeans的聚类数的求解问题研究针对经典k-means聚类算法的弊端进行一定程度上的改进,提出一种新的基于距离相等函数决定最佳聚类值的改进方法。实验采用两大类标准数据集来测试该算法,并和k-means算法的结果进行了比较,证实了该改进算法的有效性,解决了聚类数目k值的难确定性问题。南昌高专学报2101年第2期(第9总3期)21年4月出版01JunlfacagClgoraoNnhnoeelN.Sm9)Ar01o(3p.12u2基于Kma的最佳聚类数的—esn求解问题研究付淇(西科技师范学院，西南昌301)江江303摘要：对经典kmen针-sB聚类算法的弊端进行一定程度上的改进。出一种新的基于距离相等函数决定提最佳聚类值的改进方法。验采用两大类标准数据集来测试该算法，和kmen实并-as算法的结果进行了比较，实证了该改进算法的有效性，决了聚类数目k值的难确定性问题。解关键词：据挖掘；类分析；—as距离相等函数数聚kmen;中图分类号：P0.T316文献标识码：A文章编号：0875{010—18010-3421)205—20引言到优化，即符合经验规则：≤、。k/定理1证明如下：d样本与其聚类中心的平均的令为kmas-en算法是解决空间聚类的一种经典算法，这种算法简单、快速。在kmas法中”是事先给定的。-en算却但很多时候。们事先并不知道数据集应该分成多少个类我距离，=/;为聚类中心的平均距离，=,空间聚dDnZZ当类具有分形几何特征时.即每个聚类内部的空问结构与整个聚类空间结构在形态上是相似的，时应有：此别才合适，而确定最佳聚类数的问题最终还是归属于聚类有效性问题。目前也提出了一些检验聚类有效性的函数Ⅱ3】,人们使用上述聚类有效性函数计算合适的聚类数，即本文采用多数学者使用的经验规则刚：≤≤J}一上：LD,一1最佳聚类数|i}。但是，际空间聚类不一定具备分形几何特征，虑实考、,文献[】6在理论上，证明了该经验准则的/且5和【】都合理性。据此本人提出距离相等函数的概念和相应的数学模型.行最佳值的确定方法的研究。进1kmas法改进的基本原理-en算问题的一般性，间聚类应遵循紧致和分离性要求，一空即个好的空间聚类应该使各聚类中心的间距尽可能地大.而样本与其中心间距尽可能地小。此时应有：定义1令K,l空间聚类的聚类空间，中，=R为其=,…,,设，个空间对象被聚类为.个簇，{勋，假J1j}定义类际距离为所有聚类中心(内样本的均值)全域中簇到心(体样本的均值)全的距离之和：I__247;_gt;’}D()、‘1当LD,Lk==d,合上述(-)(-)=即=lDn时联13和14两个方程，易得到：2n即k、,正是被很多学者容k_lt;,≤/这￣所接受但又难以证明的经验规则。2基于距离相等函数的空间聚类最佳值确定算法I广mmIj-J(一)11定理1为最佳空间聚类数的求解指出了一个途径。即首先可以先求出最优解的上界。这样便大大缩小了最式中￡为类际距离；为全部样本的均值；簇c所mm是f=含样本的均值；七为所要聚类的个数。定义2令=,为空间聚类的聚类空间，中，埘其=幻，2…,,设，个空间对象被聚类为k个簇，{_,假1定优解的范围，其次找到LD,=或者l-最小的k值。构工DI造距离相等函数：义类内距离为所有聚类簇内部距离的总和(中，其每个簇的内部距离为该簇内所有样本到其中心的距离之和):IIIlml磊肌J)l…荟J/IItml(由式(—)知，离相等函数Fk实际上是由两21可距()D∑∑Il=j,-i-Jp‘C‘(21)—部分组成的，中，为类际距离，关于k的增函数，其是而D为类内距离，关于k的减函数。()变化取决于两是Fk的者的距离，个先单调递减，到极小值后，单调递增是达再的函数。利用距离相等函数Fk的单调性，进一步减()来少计算开销。低计算的复杂度。文据此设计了一个空减本式中，D为类内距离；P为任一空间对象，即样本；、mic、义与式(一)同。Ik含11相定理1令K=_,1IR为空间聚类的聚类空间，中，其_,:新，…,)%,假设n个空间对象被聚类为k个簇，为类际距离。D为类内距离，LD时，间聚类数k达当=空间聚类最佳值确定算法。最佳屉值确定算法过程描述：算法：kmes法基础上，在—a算n通过距离相等函数优收稿日期：00-9221--90作者简介：付g(98)女，17-,江西临川人，师，士，讲硕主要研究方向：数据挖掘。