计算机与现代化
２００８年第３期
ＪＩＳＵＡＮＪＩＹＵＸＩＡＮＤＡＩＨＵＡ
总第１５１期
文章编号：１００６－２４７５（２００８）０３－００９５－０３
一种有效ｋ．均值聚类中心的选取方法
曹文平
（襄樊学院电气信息工程系，湖北襄樊４４１００３）
摘要：基于ｋ一均值算法的思想和关键技术，本文对于ｋ一均值算法中的初始点的选取进行了深入的研究，提出了一种高性能初始点的选取算法并用实际数据进行测试，通过与常规的随机选取方法的比较，该算法具有更好的性能和健壮性。关键词：聚类；ｋ一均值；初始化；中心中图分类号：ＴＰ３１１
文献标识码：Ａ
ＡｎＥｆｆｅｃｔｉｖｅ
Ｍｅｔｈｏｄ
ｏｆＳｅｌｅｃｔｉｎｇＩｎｉｔｉａｌＰｏｉｎｔｓｆｏｒｋ－ｍｅａｎｓＣｌｕｓｔｅｒｉｎｇ
ＣＡＯＷｅｎ－ｐｉｎｇ
（Ｄｅｐｔ．ｏｆ
Ｅｌｅｃｔｒｉｃａｌ＆ＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇｏｆＸｉａｎｇｆａｎＵｎｉｖｅｒｓｉｔｙ，Ｘｉａｎｇｆａｎ４４１００３，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒｐｒｏｖｉｄｅｓｆｉｒｓｔｌｙｔｈｅｉｄｅａａｎｄ
ｃｏｒｅ
ｔｅｃｈｎｉｑｕｅｏｆｋ－ｍｅａｕｓｃｌｕｓｔｅｒｉｎｇ，ａｎｄｔｈｅｎｆｏｃｕｓ
ｏｎ
ｓｅｌｅｃｔｉｎｇｔｈｅ
ｃｅｎｔｒｉｏｄ
ｏｆｋ－ｍｅａｎｓ
ｃｌｕｓｔｅｒｉｎｇ．Ｄｅｐｅｎｄｉｎｇ
ｏｎ
ｔｈｅｒｅｓｅａｅｈａｂｏｕｔｉｎｉｔｉａｌｉｚａｔｉｏｎｄｅｅｐｌｙ，ｉｔｐｒｅｓｅｎｔｓａ
ｌｌｉ曲ｑｕａｌｉｔｙａｐｐｒｏａｃｈｔｈａｔ
ｕｓｅｄ
ｔｏ
ｓｅｌｅｃｔ
ｔｈｅｃｅｎｔｒｉｏｄ．Ｕｓｉｎｇｔｈｅｍｅｔｈｏｄｓｔｏ
ｔｅｓｔ
ｔｈｅａｌｇｏｒｉｔｈｍａｎｄｃｏｍｐａｒｅｗｉｔｈｔｈｅｒａｎｄｏｍｍｅｔｈｏｄ，ｉｔｃｏｎｃｌｕｄｅｓｔｈａｔＯＵｌ＂ｍｅｔｈｏｄｈａｓｔｈｅ
ｈｉＳｈｑ１１ａｌｉｔｙａｎｄ
ｒｏｂｕｓｔｎｅｓｓ．
Ｋｅｙｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ；ｋ－ｍｅａｎｓ；ｉｎｉｔｉａｌｉｚａｔｉｏｎ；ｅｅｎｔｒｉｏｄ
０
引言
类，同时也必然把另外的某一个类划分到其他的类中去（如果数据集Ｐ的数据实际上就是ｋ个类）。同时聚类分析是一种重要的人类行为，目前已应用于还存在另外一个问题是ｋ值的确定，怎样才能知道数许多方面：数据挖掘和知识发现、模式识别和模式分据集中到底存在多少个类。
类、数据压缩和向量量化。对于聚类有很多种方法，这些方法包括分割与合并方法、随机化方法和神经网１现有方法
络方法。其中在欧氏空间中的ｋ一均值聚类算法是最Ｐ．Ｓ．Ｂｒａｄｌｅｙ和ＵｓａｍａＭ．Ｆａｙｙａｄ提出了一种初流行和受关注的一个聚类算法，给定一个包含ｎ个ｄ
始聚类中心的算法ＲＡ…，是目前来说比较好的方维数据点的数据集Ｐ和一个正整数ｋ，问题的关键是
法口】。ＲＡ算法的主要思想是：（１）从原始数据集中在ｄ维空间中找出ｋ个点，这些点叫作数据集Ｐ的中抽取ｔ个样本集；（２）对每个样本集分别用ｋ一均值法心，把数据集Ｐ中的所有点分配到距它最近的中心聚类，生成ｔ个初始中心集Ｃｉ（１
ｓ
ｉ曼ｔ），每个集中包
去，共得到ｋ个不相交的子集，把每个子集称为一类，含ｋ个元素；（３）分别以Ｃｉ为初始聚类中心集，对样这ｋ个中心要满足：使得ｋ个类的均方误差的和最本集用ｋ．均值法聚类，得到ｔ个聚类中心集，选取效小。ｋ一均值算法我们一般要给定ｋ的值，并且随机从果最好的作为最终初始聚类中心。该方法的优点是数据集Ｐ中选择ｋ个点作为初始的聚类中心，最后的
提出了一种自动选择初始聚类中心的方法；通过选取聚类效果和最初的ｋ的中心有关。如果选择的ｋ个
样本丽不是整个数据集上实现，降低了算法的时间复点中有些大于１个的点是属于同一个类的，那么最后杂度；利用多个样本集，通过对预初始中心聚类，可以循环的次数再多，也必定把它们所属的类划分成两个
避免“孤立点”的影响，提高了结果初始中心的代表
收稿日期：２００７－０３－２０
作者简介：曹文平（１９６８一），男，湖北钟祥人，襄樊学院电气信息工程系讲师，硕士，研究方向：数据挖掘和模式识别。
计算机与现代化２００８年第３期
性。刘立平和孟志青提出了一种改进方法∞】，这种
ｅｎｄｆｏｒ
方法实际上是ＲＡ算法的变形，多选取初始点，然后再利用层次聚类算法来合并，最终也得到ｋ个类。
ＳｉｄｄｈｅｓｗｇｒＲａｙ和ＲｏｓｅＨ．Ｔｕｆｆ在１９９９年给出了一
４．输出Ｙｌ，Ｙ２，…，Ｙｋｏ
在上面的算法中，ｋ表示类的个数，Ｙ。（１
ｓｍｓ
ｋ）表示第ｍ类的中心，步骤１输入数据集Ｐ和阈值８；步骤２是取一个数据点作为第一个类的中心，这里假设是一个数据点；步骤３计算剩余的数据点和已选取的中心的距离（这里使用的是欧氏距离），并找出
最小值来与阈值８比较，看是否增加新的聚类中心；
种确定ｋ・均值中的聚类数目ｋ的一种方法［４】，ｋ的值
从２开始，然后找到一个ｋ的最大的临界值ｋ一，根据效果来确定最终的ｋ值。笔者把这种方法应用到
彩色图像的分割，取得了一个较好的效果。Ｊ．Ｍ．Ｐｅｎａ等人根据算法的有效性和健壮性对ｋ一均值的４种初始化方法：ｒａｎｄｏｍ、Ｆｏｒｇｙ、ＭａｃＱｕｅｅｎ和Ｋａｕｆｍａｎ进行了比较＂Ｊ。对ｋ一均值算法的研究还有很多，如
ＣｈａｒｌｅｓＴａｐａｓ
步骤４是输出选取的聚类中心。从上面的算法描述
中可以看出，只要阈值８给得合适，就能得到一个较为准确的类的数量和初始聚类中心。
Ｅｌｋａｎ使用三角不等式来加速ｋ一均值【ｏＪ，
３实验结果
采用常规的ｋ一均值方法对上面提到的２０００个数
Ｋａｎｕｎｇｏ等人提出了一种关于ｋ一均值的一种局
部搜索近似算法【７】。
据点的数据集（１１个类）进行聚类，初始点的选取分
２初始点的选取
在文献［１，３，６－７］中，作者对于初始点的选取都
是基于随机方法，如果这ｋ个类中每个类中的数据量
别采用随机方法和本文的算法，测试结果表明：采用
本文的算法选取初始点明显要优于采用随机方法选
取初始点。图１为使用随机方法来选取１１个初始点
相差不大，也许可以得到一个较为满意的结果。由于
数据集中每个点被选取的机率是相同的，如果这ｋ个类之间的数据量相差较大，则用随机方法来选取初始点时，有些类可能没有数据被选中，而有些类可能被选取两个或两个以上的数据，以这样的初始点来对数据聚类，其结果肯定是不能接受的。
在现实中，虽然不知道—个数据集中到底有多少个类，但是该领域的专业人员对两个数据间是不是同类应该有—个较为清晰的认识，那就是给出—个度量两个数据不相似性阈值￡的近似值，有了８就可以确定聚类的数目和初始点的选取。为了得到一个合理的初始聚类
（使用的是Ｍａｆｌａｂ中的随机函数ｕｎｉｄｍｄ（２０００，［１１１］）生成５０个初始点，选取其中最好的一次），其中
的小圆圈为初始点，聚类（重复执行１００次）结果如
图１随机初始点选取图２随机初始点选取的聚类结果
中心和—个俞舌的聚类数目ｋ，本文提出一种自适应的
初始点选取算法，下面给出该算法描述：
算法输入：数据集ｐ（共有Ｎ个数据）和度量两个数据不相似性阈值８
算法输出：输出选取的ｋ个初始聚类中心Ｙ。，Ｙ２，…，Ｙｋ１．输入数据集ｐ（共有Ｎ个数据，标记为ｘ。．Ｘ２，…，ｘＮ）和度量两个数据不相似性阈值８。
２．从数据集Ｐ取出一个点ｘ，作为第一个类的中心：
ｋ＝１，Ｙｋ＝ｘＩ
３．ｆｏｒｉ－－２
ｔｏ
当阈值８在０．１３９和０．１７８之间时，采用本文的
算法选取的１１个初始点如图３，其中小圆圈表示初始点，聚类（重复执行１０次）结果如图４，其中的小圆
圈为聚类中心点。
Ｎ．
（１）找Ｙ．：ｄ（ｘ．，ｙＩ）＝ｍｌｎＩｓ阻ｄ（ｘｉ，Ｙｊ）
（２）ｉｆｄ（ｘｉ，Ｙ．）＞８
ｋ＝ｋ＋１，玫２ｘｉｅｌｓｅｉ＝ｉ＋１ｅｎｄｉｆ
ｔｈｅｎ
图３
８翮始撇ｍ４ｇ方劫娩筋粼聚黼
只要阈值８在０．１３９和０．１７８之间正好选取１１
个初始点，并且每个类中有且只有一个点，这正是想
要的结果。而使用随机的方法来进行初始点的选取，如果选取１５个点，在２０次的测试中，最好的一次仅
２００８年第３期
。
曾文平：一种有效ｋ．均值聚类中心的选取方法
９７
仅覆盖了９个类。如果使用类之间数据的数量差别
大的数据集，随机的方法性能更差，这种情况对本方法是没有影响的。
［３】
ｎｉｑｕｅｓ［ＤＢ／ＯＬ】．ｈｔｔｐ：／／ｗｗｗ．ｅｅ．ｕｃｒ．ｅｄｕ／一ｂａｎｌｌ／
ＥＥ２４２／ｃｌｕｓｔｅｒｉｎｇ＿ｓｕｒｖｅｙ．ｐｄｆ，２００２－０３－０１．
刘立平，孟志青．一种选取初始聚类中心的方法［Ｊ］．计算机工程与应用，２００４。４０（８）：１７９．１８０．
４结束语
本文提出了一种高效的初始点的选取方法，通过使用数据集验证了本算法的优越性，并且该算法对于
类问数据的数量差别大的数据集来说有很好的健壮性。但是该算法的性能和阈值ｇ是密切相关的，如果
［４］ＳｉｄｄｈｅｓｗａｒＲａｙ。ＲｏｓｅＨＴｕｒｉ．Ｄｅｔｅｒｍｉｎａｔｉｏｎ０ｆＮｕｍｂｅｒ０ｆ。Ｃｌｕｓｔｅｒｓｉｎｋ－ｍｅａｎｓＣｌｕｓｔｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｉｎ
Ｃｏｌｏｕｒ
Ｉｎｌ馏ｅＳｅｇｍｅｎｔａｔｉｏｎ［ＤＢ／ＯＬ］。ｈｔｔｐ：／／ｗｗｗ．ｃｓｓｅ．ｍｍｍｓｈ．
ｅｃｌｕ．ａｒｔ／一ｒｏｓｅｔ／ｐａｐｅｒｓ／ｃａｌ９９．ｐｄｆ，１９９９－０３－０１．
［５］ＪＭＰｅｎａ，ＪＡＩ．ｏｚａｎｏ，ＰＬａｎ茹ａｇａ．Ａｎｅｍｐｉｒｉｃａｌｃｏｍｐａｒ－
ｉｓｏｎｏｆｆｏｕｒｉｎｉｔｉａｌｉｚａｔｉｏｎｍｅｔｈｏｄｓｆｏｒｔｈｅｋ－ｍｅａｎｓａｌｇｏｒｉｔｈｍ
太大就得不到实际数据的类的数量（比实际的数量
ｔｂ）；如果太小也同样得不到实际数据的类的数量（比实际的数量大）。在实际应用中对阈值８的选择是宁小勿大的原则，然后可以再使用层次聚类的方法来合并其中的某些类。
参考文献：［１］Ｐ
Ｓ
Ｌ
７
［Ｊ】．Ｐａｔｔｅｒｎ
１０４０．
Ｒｅｃｏｇｎｉｔｉｏｎ
Ｉ七ｔｔｅｒｓ。１９９９，２０（１０）：１０２７－
［６］ＣｈａｒｌｅｓＥｌｋａｎ．Ｕｓｉｎｇｔｈｅｔｒｉａｎｇｌｅｉｎｅｑｕａｌｉｔｙ
ｔｏａｃｃｅｌｅｒａｔｅｋ—
ｍｅａｎ８［ｃ］∥Ｐｒ∞∞ｄｉｎｇｓ
ｏｆｔｈｅＴｗｅｎｔｉｅｔｈＩｎｔｅｒｎａｔｉｏｎａｌ
Ｃｏｎｆｅｒｅｎｃｅ∞ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ（ＩＣＭＬ－２００３），Ｗａｓｈｉｎｇ－
ｔｏｎ
ＤＣ，２００３．
Ｊ
ＴａｐａｓＫａｎｕｎｇｏ。ＤａｖｉｄＭＭｏｕｎｔ，ＮａｔｈａｎＳ
Ｎｅｔ哪ａｈｕ，ｅｔ
Ｂｒａｄｌｅｙ，ＵｓａｍａＭＦａｙｙａｄ．Ｒｅｆｉｎｉｎｉｎｇｉｎｉｔｉａｌｐｏｉｎｔｓｆｏｒ
ａ１．ＡＬｏｃａｌＳｅａｒｃｈＡｐｐｒｏｘｉｍａｔｉｏｎＡｌｇｏｒｉｔｈｍｆｏｒｋ－ｍｅａ鼬
ｋ－ｍｅｍｍｃｌｕｓｔｅｒｉｎｇ［Ｃ］／／１５ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆ．ｏｎＭａ－
ｃｈｉｎｅ
ＣｈＩ吼ｄＩｌｇ［ＤＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．Ｃ８．ｕｍｄ．ｅｄｕ／一ｍｏｕｎｔ／
Ｐａｐｅｒ∥ｋｍｌｏｃａｌ．ｐｄｆ，２００３－０３－０１．
ｌｅａｒｎｉｎｇ，１９９８．
Ｂｅｒｋｈｉｎ．ＳｕｒｖｅｙｏｆＣｌｕｓｔｅｒｉｎｇＤａｔａ
ＭｉｎｉｎｇＴｅｃｈ－
［２］Ｐａｖｅｌ
，～．，、。，１・．，１・。，～。，１・。，～。，’・。，～。，～．一１・．，、。，、。，～≯、。，、。，～。，・・。，～。，～。，～。，、。，、。，～≯、。，・・。矿、。，～。，～。，、。，～。，、。，～。，・・。，、。，、。，、。，・．。ｒ．．。，・．。，・・。，～。，～。，・・。，・．ｉ≯～。，～、
（上接第９４页）
Ｏ（ｎ２）的时间复杂度有了提高，可见引入遗传算法的
提高。
・
对于ＧＡ－ＣＬＡＲＡＮＳ算法取ｇｅｎ＝１０００，Ｐ。＝０．５和ＧＡ．ＣＬＡＲＡＮＳ算法在运行效率上比ＣＬＡＲＡＮＳ有所
ｓｉｚｅ＝５。实验结果对比见表２。
襄２实验结果对比
ＣＬＡＲＡＮＳ：
ＧＡ—ＣＬＡＲＡＮＳ算法：
用时５０毫秒记录序号
０１２３４５６７８９１０ｌｌ
４结束语
本文利用遗传算法的隐并行性对ＣＬＡＲＡＮＳ算法进行改进，提出了ＧＡ－ＣＬＡＲＡＮＳ算法，该算法利用群体进化的优势来提高搜索效率，同时也保持了ＣＬＡＲＡＮＳ算法的固有特点。实验表明ＧＡ－ＣＬＡＲＡＮＳ算法是有效且可行的。
参考文献：
用时１９１毫秒记录序号
Ｏｌ２３４５６７８９１０１ｌ
所属簇
ｌ２２３３３４４４４４４
所属簇
ｌ１ｌ２２２３３３４
［１］ＪｉａｗｅｉＨａｎ，ＭｉｃｈｅｌｉｎｅＫ咖ｂｅｒ．数据挖掘概念与技术
［Ｍ］．北京：机械工业出版社，２００１．
［２］李敏强，寇纪凇。林丹，等．遗传算法的基本理论与应用
［Ｍ］．北京：科学出版社，２００２．
［３］
ＲａｙｍｏｎｄＴ，ＪｉａｗｄＨａｒｔ．Ｅｆｆｉｃｉｅｎｔａｎｄｅｆｆｅｃｔｉｖｅｃｌｕｓｔｅ－
４４
Ｎｇ
ｒｉｎｇｍｅｔｈｏｄｓｆｏｒｓｐａｔｉａｌｄａｔａｍｉｎｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ
ｏｆ
实验表明，ＧＡ－ＣＬＡＲＡＮＳ算法利用群体搜索使搜索效率明显高于ＣＬＡＲＡＮＳ算法，同时因为变异算子
ｔｈｅ２０ｔｈ
ＶｅｒｙＬａｒｇｅＤａｔａｂａｓｅｓＣｏｎｆｅｒｅｎｃｅ（ＶＬＤＢ９４），
Ｓａｎｔｉａｇｏ，Ｃｈｉｌｅ，１９９４：１４４—１５５．
的存在使其收敛性能优于ＣＬＡＲＡＮＳ。通过大量数据
集对两种算法进行实验比较，可以发现，ＧＡ．ＣＬＡＲ．
［４】ＫａｕｆｍａｎＬ，ＲｏｕｓｓｅｅｕｗＰ．ＦｉｎｄｉｎｇＧｒｏｕｐｓｉｎＤａｔａ：ＡｎＩｎ－
ｔｍｄｕｃｔｉｏｎｔｏＣｈｓｔｅｒ＆Ｓｏｎｓ。１９９０．
Ａｎａｌｙｓｉｓ［Ｍ］．ＮｅｗＹｏｒｋ：Ｊｏｈｎｗｉｌｅｙ
ＡＮＳ的单次迭代的时间复杂度接近Ｏ（ｎｋ），其中ｎ为数据集的大小，ｋ为聚类数目，这比ＣＬＡＲＡＮＳ的接近