基于K-means的最佳聚类数的求解问题研究

针对经典k-means聚类算法的弊端进行一定程度上的改进,提出一种新的基于距离相等函数决定最佳聚类值的改进方法。实验采用两大类标准数据集来测试该算法,并和k-means算法的结果进行了比较,证实了该改进算法的有效性,解决了聚类数目k值的难确定性问题。

南昌高专学报

21 0 1年第 2期 (第 9总 3期 ) 2 1年 4月出版 01

Junlf ac agC l g ora o N n hn o ee l

N . S m 9) A r 0 1 o ( 3 p. 1 2u 2

基于Kma的最佳聚类数的—e s n求解问题研究付淇(西科技师范学院，西南昌 3 0 1 )江江 303

摘

要：对经典 k men针 - sB聚类算法的弊端进行一定程度上的改进。出一种新的基于距离相等函数决定提

最佳聚类值的改进方法。验采用两大类标准数据集来测试该算法，和 k men实并 - as算法的结果进行了比较，实证了该改进算法的有效性，决了聚类数目 k值的难确定性问题。解 关键词：据挖掘；类分析；— a s距离相等函数数聚 k men;中图分类号：P 0 . T31 6文献标识码： A文章编号：0 8 7 5{0 10— 1 8 0 10 - 3 4 2 1 )2 0 5— 2

0引言

到优化，即符合经验规则：≤、。 k/定理 1证明如下： d样本与其聚类中心的平均的令为

k m as - en算法是解决空间聚类的一种经典算法，这种算法简单、快速。在 k m a s法中”是事先给定的。 - en算却 但很多时候。们事先并不知道数据集应该分成多少个类我

距离，=/;为聚类中心的平均距离，=,空间聚 d Dn Z Z当类具有分形几何特征时 .即每个聚类内部的空问结构与整个聚类空间结构在形态上是相似的，时应有：此

别才合适，而确定最佳聚类数的问题最终还是归属于聚类有效性问题。目前也提出了一些检验聚类有效性的函数Ⅱ3】,

人们使用上述聚类有效性函数计算合适的聚类数，即本文采用多数学者使用的经验规则刚：≤≤ J}一

上：L D

,一 1

最佳聚类数| i}。

但是，际空间聚类不一定具备分形几何特征，虑实考

、,文献[】 6在理论上，证明了该经验准则的/且 5和【】都合理性。据此本人提出距离相等函数的概念和相应的数学模型 .行最佳值的确定方法的研究。进1 k m as法改进的基本原理 - en算

问题的一般性，间聚

类应遵循紧致和分离性要求，一空即个好的空间聚类应该使各聚类中心的间距尽可能地大 .

而样本与其中心间距尽可能地小。此时应有：

定义 1令 K , l空间聚类的聚类空间，中，= R为其 =,…,,设，个空间对象被聚类为 .个簇，{勋， 假 J 1 j}定义类际距离为所有聚类中心 (内样本的均值 )全域中簇到心 (体样本的均值 )全的距离之和：I

÷> ’} D

( )、 ‘ 1

当 L D, L k== d,合上述 (- ) (- )=即= lD n时联 1 3和 1 4两

个方程，易得到：2 n即 k、,正是被很多学者容 k<,≤/这￣所接受但又难以证明的经验规则。2基于距离相等函数的空间聚类最佳值确定算法

I广 m mIj- J

(一 ) 11

定理 1为最佳空间聚类数的求解指出了一个途径。 即首先可以先求出最优解的上界。这样便大大缩小了最

式中￡为类际距离；为全部样本的均值； 簇 c所 m m是 f=含样本的均值；七为所要聚类的个数。 定义 2令=,为空间聚类的聚类空间，中， 埘其 =幻，2…,,设，个空间对象被聚类为 k个簇，{ X, 假 1定

优解的范围，其次找到 L D,=或者 l-最小的k值。构工 DI造距离相等函数：

义类内距离为所有聚类簇内部距离的总和 (中，其每个簇的内部距离为该簇内所有样本到其中心的距离之和 ):I

I Ilml磊肌J ) l…荟 J / I I tm l (由式 (— )知，离相等函数 F k实际上是由两 2 1可距 ()

D∑∑I l= j , -i- J p‘C‘

(2 1)—

部分组成的，中，为类际距离，关于 k的增函数，其 是而 D为类内距离，关于 k的减函数。 ( )变化取决于两是 Fk的者的距离，个先单调递减，到极小值后，单调递增是达再的函数。利用距离相等函数 F k的单调性，进一步减 ()来少计算开销。低计算的复杂度。文据此设计了一个空减本

式中， D为类内距离； P为任一空间对象，即样本；、 mic、义与式 (一 )同。 I

k含 11相

定理 1令 K=X, 1 I R为空间聚类的聚类空间，中，其 X,:新，…, )%,假设 n个空间对象被聚类为 k个簇， 为类际距离。 D为类内距离， L D时，间聚类数 k达当=空

间聚类最佳值确定算法。最佳屉值确定算法过程描述： 算法： k me s法基础上，在— a算 n通过距离相等函数优

收稿日期：00-92 2 1- -9 0

作者简介：付

g(9 8 )女， 17 -,江西临川人，师，士，讲硕主要研究方向：数据挖掘。

本文来源：https://www.bwwdw.com/article/0b11.html