基于最大最小距离法的多中心聚类算法第26卷第6期2006年6月计算机应用ComputerApplicationsVo1.26No.6June2006:1001—9081(2006)06—1425—03基于最大最小距离法的多中心聚类算法周涓,熊忠阳,张玉芳,任芳(重庆大学计算机学院,重庆400030)(zhouzhoucqu@126)摘要:针对k-means算法的缺陷,提出了一种新的多中心聚类算法.运用两阶段最大最小距离法搜索出最佳初始聚类中心,将原始数据集分割成小类后用合并算法形成最终类,即用多个聚类中心联合代表一个延伸状或者较大形状的簇.仿真实验表明:该算法能够智能地确定初始聚类种子个数,对不规则状数据集进行有效聚类,聚类性能显着优于k-means算法.关键词i聚类;最大最小距离法;多中心;抽样:TP311.13文献标识码:AMultiseedclusteringalgorithmbasedonmax-mindistancemeansZHOUJuan,X[ONGZhong—yang,ZHANGYu—fang,RENFang(CollegeofComputer,ChongqingUniversity,Chongqing400030,China)Abstract:Anovelmuhiseedclusteringalgorithmwasproposedaimingatshortcomingsofk-meansalgorithm.Thisalgorithmcouldfindoptimalinitialstartingpointsapplyingiterativemax—mindistancemeansandthencombinedthesmallclustersfromgivendatasetintofinalones,foranelongatedOrlargedustercouldbeconsideredastheunionofafewsmalldistincthyperspheriealclusters.Experimentalresultsdemonstratethattheimprovedalgorithmcanautomaticallyobtainthenumberofinitialclusters,beeffectiveondatasetofirregularshapesandleadtobettersolutionsthank-meansalgorithm.Keywords:clustering;max—mindistancemeans;multiseed;sampling0弓l言k—means算法属于聚类…技术巾一种基本的划分方法,具有简单,快速的优点.然而这种算法对初值的依赖性很强,初值选取的不同往往导致聚类结果相当不稳定.其次,它是基于目标函数的聚类算法,一般都采用梯度法求解极值.由于梯度法的搜索方向总是沿着能量减小的方向进行,因此当初始聚类中心选择不当时,算法极易陷入局部极小点.近几年来人们提出了多种改进和优化的方法.文献[3]考虑了类结构中的多种对称性质,提出了一种改进的基于类对称的距离量度,可以有效发现超球面以外的具有较对称形状的簇.文献[4]采用多次取样数据集两次聚类以获取最优初值的思想,有效地解决了k-means算法对初始值的选择具有较大依赖性的问题.文献[5]采用了多中心代表的思想,将多个种子点分配给一个类,用一棵最小生成树体现了非凸面形状簇的伸长方向.k-means算法的基本思想是由一些初始点或者代表点开始,每个簇均围绕着一个聚类中心分配对象.所有基于中心的聚类方法都存在着两个普遍的问题:一个是如何选择合适的初始聚类种子;另一个是这些方法只适合发现球状簇,面对延伸状的簇或者大小差别很大的簇无能为力本文提出的基于最大最小距离法的多中心聚类算法(MuhiseedClusteringAlgorithm,MCA)将主要解决这两方面的问题,其中心思想是:任何一个延伸状或者较大形状的簇都可以看成是一些独立的超球面簇的结合.因此任何一个延伸状或者较大形状的簇就可以用多个聚类中心来联合代表.该算法采用多次抽样两阶段最大最小距离法的思想,将最大最小距离法和k-means有机结合,暂时将较大的簇或延伸的簇分成若干个小类,最后通过小类合并算法形成最终类.1最大最小距离法的基本思想最大最小距离法是模式识别领域中的一种基于试探的算法,思想是取尽可能离得远的对象做为聚类中心,避免了k-means算法初值选取时可能出现的聚类种子过于邻近的情况,不仅智能地确定初始聚类种子的个数,而且提高了划分初始数据集的效率.1)有J7,r个对象,S={Z,z:,…,z}.2)任取一个对象,例如z.,把z作为第一个类的中心,从集合S中找出到z.距离最大的对象作为z.3)对S中剩余对象z,分别计算到Z.z的距离.令其中较小的那个为D4)计算maxS{.}.若maxS{.}》m×[average(I一zI)],则取z为新的聚类中心.m通常取(可1≤m《1).5)重复同样的处理,直到再找不到符合条件的新的聚类中心.设样本规模为|7\,,每次寻找新的聚类中心时,很明显式3)要进行|7\,次距离计算.若共找到个聚类中心,则算法结束时共进行的计算次数为:一.最大最小距离法的...