第28卷第l1期
2011年11月
计算机应用研究
ApplicationResearchofComputers
V o1.28No.11
NOV.2011
一
种有效的K-means聚类中心初始化方法术
熊忠阳，陈若田，张玉芳
(重庆大学计算机学院，重庆400044)
摘要：传统K—means算法由于随机选取初始聚类中心，使得聚类结果波动性大；已有的最大最小距离法选取
初始聚类中心过于稠密，容易造成聚类冲突现象.针对以上问题，对最大最小距离法进行了改进，提出了最大距
离积法.该方法在基于密度概念的基础上，选取到所有已初始化聚类中心距离乘积最大的高密度点作为当前聚
类中心.理论分析与对比实验结果表明，此方法相对于传统K—means算法和最大最小距离法有更快的收敛速
度，更高的准确率和更强的稳定性.
关键词:K一均值算法；基于密度；初始聚类中心；最大最小距离；最大距离积
中图分类号:TP311.13文献标志码:A文章编号:1001—3695(2011)11—4188.03 doi:10.3969/j.issn.1001.3695.2011.11.050 Effectivemethodforclustercenters'initializationinK—meansclustering XIONGZhong—yang,CHENRuo—tian,ZHANGYu—fang (CollegeofComputerScience,ChongqingUniversity,Chongqing400044,China) Abstract:Initializingclust
meansalgorithmleadstogreatfluctuationsintheclusteringre—
suhs.Theexistingmax—raindistancealgorithm,indeed,hasratherdenseclustercenters,whichmayeasilybringabout cluste—
ringconflicts.Tosolvetheseproblems,thispaperregardedtheexistingmax—mindistancealgorithmasthethinkingfoundation andproposedthemaximumdistancesproductalgorithm.Basedonthetheoryofdensity—basedclustering,themaximumdis—tancesproductalgorithmselectedeachpointwhichhadmaximumproductofdistancesbetwe enitselfandallotherinitialized
clusteringcenters.Theoryanalysisandexperimentalresultsshowthatcomparedwithtraditi onalK—meansalgorithmandmax—
mindistancealgorithm,themaximumdistancesproductalgorithmcanresultinfasterconver gencespeed,higheraccuracy,
greaterstability.
Keywords:K—meansalgorithm;density—basedclustering;initialclusteringcenters;max —mindistance;maximumdistances
product
数据挖掘就是从大量的，有噪声的，模糊的数据中，提取隐
含的，事先不为人知的，但又潜在有用的信息和知识的过程.
maxstep主要的数据挖掘方法有分类，聚类，关联分析，回归分析等.其
中运用比较广泛的聚类分析就是将数据对象分组成为多个类 或簇，使得同一个簇中的对象之问具有较高的相似度，而不同
簇中的对象差别较大….作为基于划分的聚类方法,K—means
算法具有算法简单，收敛速度快，能有效地处理大数据集等多
方面的优点，但传统的K—means算法对初始聚类中心敏感，选
择不同的初始聚类中心会产生不同的聚类结果且有不同的准
确率.
为了消除初始聚类中心选取的盲目性，人们采用基于密
度'的最大最小距离法替代了传统K—means随机初始化聚
类中心的方法，在收敛速度，准确率方面都有了较大的提
高.本文为了进一步优化初始聚类中心的选择，提出了最
大距离积法，并给出了密度参数的计算方法.实验表明，此算
法优于已有的最大最小距离法和传统K—means算法.
传统K—means算法…的基本思想：首先从Ⅳ个数据对象
中随机选择个对象作为初始聚类中心；对于剩下的其他对
象，则根据它们与这些聚类中心的相似度(距离)，分别将其分
配给与其最相似的聚类；然后再计算每个聚类新的聚类中心
(该聚类中所有对象的均值)；不断重复这一过程直到标准测
度函数开始收敛为止.一般都采用方差(簇内误差平方总和)
作为标准测度函数J，其定义为
——
E=∑∑IX—X}(1)
i=1XeCi.
其中：为簇的总数，置为簇c的平均值.
传统K-means算法描述如下:
输入：迭代终止条件，最大迭代次数maxStep，簇的总数
目和包含Ⅳ个记录的样本集.
输出：满足迭代终止条件的个簇和迭代次数.
a)随机初始化个簇中心;
b)对于每个数据对象，计算该对象与个簇中心的距离,
选择距离最小(相似度最大)的簇将该对象分入该簇;
C)重新计算个簇的中心，中心为该簇内所有点的算术
平均值，用式(1)计算出此时的准则函数值.
d)如果达到最大迭代次数或满足:
IE，一E1I<(2)
收稿日期:2011—04—01；修回日期:2011.05-03基金项目：重庆市科委基金资助项
目(2008BB2191)
作者简介：熊忠阳(1962一)，男，教授，博导，主要研究方向为数据挖掘，并行处理等(***************.en)；陈若田(1988-)，男，硕士研究生;
张玉芳(1965一)，女，教授.
第11期熊忠阳，等：一种有效的K—means聚类中心初始化方法?4189?
其中:s是一个极小数;E和E：分别代表前后两次迭代的准则
函数值.式(2)表示簇内误差平方总和已经收敛，即簇成员不
再发生变化，那么结束聚类，否则，返回b).
2最大最小距离法
传统K—means算法对初始聚类中心敏感，为了得到更好的
聚类结果，也为了得到更高效的聚类过程，该最大最小距离
法对初始聚类中心的选取进行了优化，替代传统K—means算
法过程中的步骤a).其基本思想如下:
通过预先设定好的密度参数(包括MinPts和s)，就可
以发现处于高密度区域的数据对象(满足邻域范围内的数
据对象数最少为MinPts的数据对象)，从而得到一个高密度点
集合D.在D中取处于最高密度区域的数据对象作为第1个
聚类中心Z.；取距离z_最远的一个高密度点作为第2个聚类
中心Z:，计算D中数据对象Xi到Z,Z2的距离d(X,Z)和d
(X,Z2);Z3为满足
max(min(d(,Z1)),rain(d(X;,Z2)))
的数据对象；为满足式子
max(min(d(X,Z1)),
min(d(X,Z2)),…,min(d(X,Z—1)))
的数据对象,XD.依此可得到个初始聚类中心.
3最大距离积法
最大最小距离法与随机初始化聚类中心相比，降低了对初
始聚类中心的敏感性，在收敛速度，准确率方面都有了较大的
进步.但由于它选取聚类中心遵从最小距离的思想，可能造成
初始聚类中心选取过于稠密，出现聚类冲突现象，使得原本属于同一个簇的对象被分到了两个不同的簇中，从而降低了聚类结果的质量.为了克服初始聚类中心选取过于稠密的现象，本文提出了最大距离积法，尽可能地稀疏初始聚类中心的分布. 其基本思想如下:
按照与最大最小距离法同样的思路，根据密度参数到高
密度点集合D和初始的两个聚类中心Z和，再计算D中其
余每个数据对象到z,z的距离d(,Z.)和d(X,Z2);
为满足
max(d(X,Z1))×d(X,Z2))
的数据对象；为满足
max(d(X,Z1)×(x,z2)×…×d(X,Zk一1))
的数据对象.]i|,XD.依此可得到个初始聚类中心.
其基本步骤描述如下:
a)计算任意两个数据对象间的距离(相似度)d(X,).
b)通过密度参数MinPts和，把处于低密度区域的点删
除，得到处于高密度区域的数据对象的集合D.
e)把处于最高密度区域的数据对象作为第1个聚类中心
z，加入集合Z(已初始化聚类中心)中，同时从集合D中删
除；再在集合D中到距离z1最远的点作为第2个聚类对象z，将其加入集合Z中，并从集合D中删除.
d)在集合D中搜索到集合z中的每个点距离乘积最大的
点，将其作为当前所要的聚类中心，并加入集合z.
e)重复步骤d)，直到集合z中的样本个数达到K个.
f)聚类中心初始化完成.
根据该方法基本思想和步骤可以看出，它选取到所有已初
始化聚类中心距离乘积最大的高密度点作为当前聚类中心，从而稀疏了初始聚类中心的分布.
在该方法中需要输入密度参数MinPts和8，对于没有经验
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议