聚类算法研究
ＩＳＳＮ１０００?９８２５。ＣＯＤＥＮＲＵＸＵＥＷ
ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ，Ｖ０１．１９，Ｎｏ．１，Ｊａｎｕａｒｙ２００８，ＰＰ．４８“１
１３０Ｉ：１０．３７２４／ＳＥＪ．１００１．２００８．０００４８
ｏ２００８ｂｙＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ．Ａｌｌｒｉｇｈｔｓｒｅｓｅｒｖｅｄ．
聚类算法研究。
．．．●
孙吉贵ｕ，刘杰１，２＋’赵连宇１，２
１（吉林大学计算机科学与技术学院，吉林长春１３００１２）
２（符号计算与知识工程教育部重点实验室，吉林长春１３００１２）ＣｌｕｓｔｅｒｉｎｇＡｌｇｏｒｉｔｈｍｓＲｅｓｅａｒｃｈ
ＳＵＮＪｉ．ＧｕｉＬ２，ＬＩＵＪｉｅ协，ＺＨＡＯＬｉａｎ．Ｙｕｌ’２
Ｅ－ｍａｉｌ：ｊｏｓ＠ｉｓｃａｓ．ａｃ．ｅｎｈｎｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎＴｅｌ／Ｆａｘ－＋８６．１０－６２５６２５６３
１（ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ。ＪｉｌｉｎＵｎｉｖｅｒｓｉｔｙ。Ｃｈａｎｇｃｈｕｎ１３００１２，Ｃｈｉｎａ）
２（ＫｅｙＬａｂｏｒａｔｏｒｙｏｆＳｙｍｂｏｌｉｃＣｏｍｐｕｔａｔｉｏｎａｎｄＫｎｏｗｌｅｄｇｅＥｎｇｉｎｅｅｒｉｎｇｏｆｔｈｅＭｉｎｉｓｔｒｙｏｆＥｄｕｃａｔｉｏｎ，Ｃｈａｎｇｃｈｕｎ１３００１２，Ｃｈｉｎａ）
＋Ｃｏｒｒｅｓｐｏｎｄｉｎｇａｕｔｈｏｒ：Ｐｈｎ：＋８６－４３１?８５１６６４７８，Ｅ?ｍａｉｌ：ｌｉｎ．ｊｉｅ＠ｊｌｕ．ｅｄｕ．∞
ＳｕｎＪＧ，ＬｉｕＪ，ＺｈａｏＬＹ．Ｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓｒｅｓｅａｒｃｈ．Ｊｏｕｒｎａｌ矿Ｓｏｆｔｗａｒｅ，２００８，１９（１）：４８－６１．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ／１０００－９８２５／１９／４８．ｈｔｍ
Ａｂｓｔｒａｃｔ：Ｔｈｅｒｅｓｅａｒｃｈａｃｔｕａｌｉｔｙａｎｄｎｅｗｐｒｏｇｒｅｓｓｉｎｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｉｎｒｅｃｅｎｔｙｅａｒｓａｒｅｓｕｍｍａｒｉｚｅｄｉｎｔｈｉｓｐａｐｅｒ．Ｆｉｒｓｔ，ｔｈｅａｎａｌｙｓｉｓａｎｄｉｎｄｕｃｔｉｏｎｏｆｓｏｍｅｒｅｐｒｅｓｅｎｔａｔｉｖｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓｈａｖｅｂｅｅｎｍａｄｅｆｒｏｍｓｅｖｅｒａｌａｓｐｅｃｔｓ，ｓｕｃｈａｓｔｈｅｉｄｅａｓｏｆａｌｇｏｒｉｔｈｍ，ｋｅｙｔｅｃｈｎｏｌｏｇｙ，ａｄｖａｎｔａｇｅａｎｄｄｉｓａｄｖａｎｔａｇｅ．Ｏｎｔｈｅｏｔｈｅｒｈａｎｄ，ｓｅｖｅｒａｌｔｙｐｉｃａｌｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓａｎｄｋｎｏｗｎｄａｔａｓｅｔｓａｒｅｓｅｌｅｃｔｅｄ，ｓｉｍｕｌａｔｉｏｎｅｘｐｅｒｉｍｅｎｔｓａｒｅｉｍｐｌｅｍｅｎｔｅｄｆｒｏｍｂｏｔｈｓｉｄｅｓｏｆａｃｃｕｒａｃｙａｎｄｒｕｎｎｉｎｇｅｆｆｉｃｉｅｎｃｙ，ａｎｄｃｌｕｓｔｅｒｉｎｇｃｏｎｄｉｔｉｏｎｏｆｏｎｅａｌｇｏｒｉｔｈｍｗｉｔｈｄｉｆｆｅｒｅｎｔｄａｔａｓｅｔｓｉｓａｎａｌｙｚｅｄｂｙｃｏｍｐａｒｉｎｇｗｉｔｈｔｈｅｓａｍｅｃｌｕｓｔｅｒｉｎｇｏｆｔｈｅ
ｄａｔａｓｅｔｕｎｄｅｒｄｉｆｆｅｒｅｎｔａｌｇｏｒｉｔｈｍｓ．Ｆｉｎａｌｌｙ，ｔｈｅｒｅｓｅａｒｃｈｈｏｔｓｐｏｔ，ｄｉｆｆｉｃｕｌｔｙ，ｓｈｏｒｔａｇｅｏｆｔｈｅｄａｔａｃｌｕｓｔｅｒｉｎｇａｎｄｓｏｍｅｐｅｎｄｉｎｇｐｒｏｂｌｅｍｓａｒｅａｄｄｒｅｓｓｅｄｂｙｔｈｅｉｎｔｅｇｒａｔｉｏｎｏｆｔｈｅａｆｏｒｅｍｅｎｔｉｏｎｅｄｔｗｏａｓｐｅｃｔｓｉｎｆｏｒｍａｔｉｏｎ．ＴｈｅａｂｏｖｅｗｏｒｋＣａｌｌｇｉｖｅａｖａｌｕａｂｌｅｒｅｆｅｒｅｎｃｅｆｏｒｄａｔａｃｌｕｓｔｅｒｉｎｇａｎｄｄａｔａｍｉｎｉｎｇ．，‘
Ｋｅｙｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ；ａｌｇｏｒｉｔｈｍ；ｅｘｐｅｒｉｍｅｎｔ
摘要：对近年来聚类算法的研究现状与新进展进行归纳总结．一方面对近年来提出的较有代表性的聚类算法，从算法思想．关键技术和优缺点等方面进行分析概括；另一方面选择一些典型的聚类算法和一些知名的数据集，主要从正确率和运行效率两个方面进行模拟实验，并分别就同一种聚类算法、不同的数据集以及同一个数据集、不同的聚类算法的聚类情况进行对比分析．最后通过综合上述两方面信息给出聚类分析的研究热点、难点、不足和有待解决的一些问题．上述工作将为聚类分析和数据挖掘等研究提供有益的参考．
关键词：聚类：算法：实验
中图法分类号：ＴＰｌ８文献标识码：Ａ
聚类分析研究有很长的历史，几十年来，其重要性及与其他研究方向的交叉特性得到人们的肯定．聚类是数?ＳｕｐｐｏｒｔｅｄｂｙｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａ
ｕｎｄｅｒＧｒａｎｔＮｏｓ．６０４７３００３，６０５７３０７３（国家自然科学基金）；ｔｈｅＭａｊｏｒＲｅｓｅａｒｃｈＰｒｏｇｒａｍｏｆＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．６０４９６３２１（国家自然科学基金重大项目）Ｒｅｃｅｉｖｅｄ２００％０４－２４；Ａｃｃｅｐｔｅｄ２００７—０８．．０３
孙吉贵等：聚类算法研究４９
据挖掘、模式识别等研究方向的重要研究内容之一，在识别数据的内在结构方面具有极其重要的作用．聚类主要应用于模式识别中的语音识别、字符识别等，机器学习中的聚类算法应用于图像分割和机器视觉，图像处理中聚类用于数据压缩和信息检索．聚类的另一个主要应用是数据挖掘（多关系数据挖掘）、时空数据库应用（ｃｉｓ等）、序列和异类数据分析等．此外，聚类还应用于统计科学．值得一提的是，聚类分析对生物学、心理学、考古学、地质学、地理学以及市场营销等研究也都有重要作用［１－３１．
本文一方面从算法思想、关键技术和优缺点等方面对近年提出的较有代表性的聚类算法进行了分析、介绍；另一方面又选用多个知名数据集对一些典型算法进行了测试．而后综合这两方面信息得出一些相应的结论．本文第１节简单介绍聚类概念、聚类过程与聚类算法的类别．第２节重点阐述１７个较有代表性的算法．第３节描述８种聚类算法的模拟实验结果，并结合文献［４】进行分析．第４节给出本文的一些结论．
１聚类与聚类算法类别
１．１聚类概念与聚类过程
迄今为止，聚类还没有一个学术界公认的定义．这里给出Ｅｖｅｒｉｔｔ［５】在１９７４年关于聚类所下的定义：一个类簇内的实体是相似的，不同类簇的实体是不相似的；一个类簇是测试空间中点的会聚，同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离：类簇可以描述为一个包含密度相对较高的点集的多维空间中的连通区域，它们借助包含密度相对较低的点集的区域与其他区域（类簇）相分离．
事实上。聚类是一个无监督的分类，它没有任何先验知识可用．聚类的形式描述如下：
令泸｛Ｐｌ，ｐ２…．炉。｝表示一个模式（实体）集合∥ｆ表示第ｉ个模式ｆ＿｛１，２…．，一｝；Ｃ，ｃ＿Ｕ，ｆ＝ｌ，２…．，七，
Ｃ＝｛巩，ｐｆ２，．．．，ｐ０）＂，ｐｒｏｘｉｍｉｔｙ（ｐｒｏｓ，Ｐｉｔ），其中，第１个下标表示模式所属的类，第２个下标表示某类中某一模式，函数ｐｒｏｘｉｍｉ钞用来刻画模式的相似性距离．若诸类ｃｌ为聚类之结果，则诸Ｇ需满足如下条件：＋ｊ１）Ｕ暑ｅ＝Ｕ．
２）对于ＶＧ，Ｃ是以Ｇ≠Ｃ，有Ｃ二ｎＣ户０（仅限于刚性聚类）；
ＭＩＮｖ，．；ｃ－，‰。ｃ，ｖ‘，ｃｃ【，＆厶ｔｃ，（ｐｒｏｘｉｍｉｔｙ（ｐ。，Ｂ，））＞ＭＡＸｖｐｗａ，＾。。厶，ｖ岛ｃｕ（ｐｒｏｘｉｍｉｔｙ（ｐ。，ｊ■））．典型的聚类过程主要包括数据（或称之为样本或模式）准备、特征选择和特征提取、接近度计算、聚类（或分组）、对聚类结果进行有效性评估等步骤‘３ｔ６～．
聚类过程：
１）数据准备：包括特征标准化和降维．’
２）特征选择：从最初的特征中选择最有效的特征，并将其存储于向量中．
３）特征提取：通过对所选择的特征进行转换形成新的突出特征．‘
４）聚类（或分组）：首先选择合适特征类型的某种距离函数（或构造新的距离函数）进行接近程度的度量；
而后执行聚类或分组．
５）聚类结果评估：是指对聚类结果进行评估．评估主要有３种：外部有效性评估、内部有效性评估和相关性测试评估．
１．２聚类算法的类别
没有任何一种聚类技术（聚类算法）可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构【７１．根据数据在聚类中的积聚规则以及应用这些规则的方法，有多种聚类算法．聚类算法有多种分类方法，本文将聚类算法大致分成层次化聚类算法、划分式聚类算法、基于密度和网格的聚类算法和其他聚类算法，如图ｌ所示的４个类别．
ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．１９，Ｎｏ．１，Ｊａｎｕａｒｙ２００８
２聚类算法Ｆｉｇ．１Ｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎｃｈａｒｔｏｆｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓ图１聚类算法分类图
２．１层次聚类算法
层次聚类算法又称为树聚类算法【８．，ｊ，它使用数据的联接规则，透过一种层次架构方式，反复将数据进行分裂或聚合，以形成一个层次序列的聚类问题解．本文仅以层次聚类算法中的层次聚合算法为例进行介绍．层次聚合算法的计算复杂性为Ｏ（ｎ２），适合于小型数据集的分类．
２．１．１层次聚合算法
该算法由树状结构的底部开始逐层向上进行聚合，假定样本集始｛Ｄｌ，０２，．．．，Ｏ。｝共有ｎ个样本．
ＨＡｌ［初始化】．置每个样本０ｉ为一个类；／．共形成／＇／个类：Ｄ１，０２，．．．，０。?／
ＨＡ２［找最近的两个类】．ｄｉｓｔａｎｃｅ（ｏ，，吼）＝ｍｉＩｌ饥。～。ｓ＾。～ｄｉｓｔａｎｃｅ（ｏ．，ｏｖ）；
／．从现有的所有类中找出距离最近（相似度最大）的两个类０，和ＤＩ?／
ＦＬＡ３［合并Ｄ，和钥．将类Ｄｒ和啦合并成一个新类ｐ石／＋现有的类数将减１．／
ＨＡ４．若所有的样本都属于同一个类，则终止本算法；否则，返回步骤ＨＡ２．
２．１．２传统聚合规则
两个类之间距离的度量方法是传统层次聚合算法的重要组成部分，它主要包括两个重要参数相似性度量方法和联接规则．这里采用欧式距离作为相似性度量方法，联接规则主要包括单联接规则、完全联接规则、类间平均联接规则、类内平均联接规则和沃德法．这几种联接规则可定义如下【叼（其中，含Ｉｋ叫｜Ｉ是欧几里德范数，嘞和ｎｋ分别指类Ｄ，和ｑ中的样本个数，Ｃ（ｎｚ斗ｎｂ２）表示从ｎｉ＋ｒｉｌ个元素中抽出两个元素的不同组合的方法总数）：单联接聚合规则：ｄ（ｏｔ，ｏｋ）＝ｒａｉｎ。ｅｏｊ．ｙ。吧０ｘ－ｙ０；
全联接聚合规则：ｄ（ｏｔ，Ｏｋ）＝ｍａｘ，‰ｙ。矗Ｉ｜ｘ－ｙ｜Ｉ；
类间平均联接聚合规则：ｄ（ｏｉ，ｏＤ＝（１／吩像）∑。哪Ｉ∑，吨。工一Ｙ吣；
孙吉贵等：聚类算法研究５１
类内平均联接聚合规则：ｄ（ｑ，吼）＝（１／Ｃ（ｎｔ－Ｉ－ｎｋ，２））∑”啪㈦｜ｌｘ－Ｙｌｌ；
沃德法：ｄ（Ｄｌ，吼）＝（１／（嘎－Ｉ－ｎｋ））∑，甙研．。。）ＩＩｘ－矗１１２，其中，ｋ是融合聚类的中心．
２．Ｉ．３新层次聚合算法
（１）Ｂｉｎａｒｙ—Ｐｏｓｉｔｉｖｅ方法
２００７年，Ｇｅｌｂａｒｄ等人【４】提出了一种新的层次聚合算法，被称为正二进制（ｂｉｎａｒｙ．ｐｏｓｉｔｉｖｅ）方法．该方法把待分类数据以正的二进制形式存储于一个二维矩阵中，其中，行表示记录（对象），列表示其属性的可能取值．记录对应的取值为１或者Ｏ，分别表示此记录有对应的属性值或者不存在对应属性值．因此，相似性距离计算只在被比较的二进制向量中的正比特位上进行，即只在取值为１的记录（对象）之间进行．有以Ｄｉｃｅ距离为代表的多种Ｂｉｎａｒｙ．Ｐｏｓｉｔｖｅ相似性测量方法【１０’１１１．
Ｇｅｌｂａｒｄ等人采用Ｗｉｎｅ，Ｉｒｉｓ，Ｅｅｏｌｉｃ和Ｐｓｙｃｈｏｌｏｇｙｂａｌａｎｃｅ这４种数据集对１１种聚类算法进行了实验，结果表明，对于此４种数据集中的任意一种数据的聚类结果，Ｂｉｎａｒｙ．Ｐｏｓｉｔｉｖｅ等４种方法在聚类结果的准确率方面，从总体上来看都是最好的．同时他们还认为，将原始数据转换成正二进制会改善聚类结果的正确率和聚类的鲁棒性。对于层次聚类算法尤其如此．
（２）连续数据的粗聚类算法（ｒｏｕｇｈｃｌｕｓｔｅｒｉｎｇｏｆｓｅｑｕｅｎｔｉａｌｄａｔａ，简称ＲＣＯＳＤ）
２００７年．Ｋｕｍａｒ等人（１２】面向连续数据提出了一种新的基于不可分辨粗聚合的层次聚类算法ＲＣＯＳＤ．在该算法中，不可分辨关系被扩展成具有不严格传递特性的容差关系．使用相似性的上近似形成初始类，使用约束相似性的上近似概念形成后续类，其中的一个相对的相似性条件被用作合并准则．ＲＣＯＳＤ的关键思想是寻找能捕捉数据序列的连续信息及内容信息的一个特征集，并把这些特征集映射到一个上近似空间，应用约束相似性上
近似技术获得粗类簇的上近似，其中一个元素可以属于多个类簇．该算法引入妒Ｍ作为Ｗｅｂ数据的相似性度量方法，妒肘既考虑了项的出现次序又考虑了集合内容．该算法每一次迭代可以合并两个或多个类，所以加快了层次聚类速度．该算法能够有效挖掘连续数据，并刻画类簇的主要特性，帮助Ｗｅｂ挖掘者描述潜在的新的Ｗｅｂ用户组的特性．
ＰｒａｄｅｅｐＫｕｍａｒ等人在本质连续的ＭＳＮＢＣＷｅｂ导航数据集上的实验结果表明，与使用序列向量编码的传统层次化聚类算法相比，ＲＣＯＳＤ聚类算法是可行的．算法给出的描述方法能够帮助Ｗｅｂ挖掘者鉴别潜在的有意义的用户组．
２．２划分式聚类算法
划分式聚类算法需要预先指定聚类数目或聚类中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数值收敛时，得到最终聚类结果．
２．２．１Ｋ均值聚类
１９６７年，ＭａｃＱｕｅｅｎ首次提出了Ｋ均值聚类算法（Ｋ－ｍｅａｎｓ算法）．迄今为止，很多聚类任务都选择该经典算法．该算法的核心思想是找出ｘ个聚类中心ｃ１，ｃ２，．．．，ｃ晒使得每一个数据点Ｘ，和与其最近的聚类中心ｃ，的平方距离和被最小化（该平方距离和被称为偏差Ｄ）．
Ｋ均值Ｃ尽ｍｅ柚ｓ）聚类算法【８】（对＾个样本进行聚类）
ＫＩ［初始化】．随机指定Ｋ个聚类中心（ｃ１，Ｃ２，．．．，ｃ０；
Ｋ２［分配ｘｉ】．对每一个样本ｊ。找到离它最近的聚类中心Ｃｖ，并将其分配到ｃｖ所标明类；
Ｋ３［修正“】．将每一个“移动到其标明的类的中心；
Ｋ４【计算偏差】．Ｄ＝∑：１【ｍｉＩｌ，－ｌ，石ｄ（而，ｃ，）２】；
Ｋ５【Ｄ收敛？】．如果Ｄ值收敛，则ｒｅｔｕｒｎ（ｃｌ，Ｃ２９．ｏ．９ｃ０并终止本算法；否则，返回步骤Ｋ２．
Ｋ－ｍｅａｎｓ算法的优点与不足‘１３】．优点：能对大型数据集进行高效分类，其计算复杂性为Ｏ（ｔＫｍｎ），其中，ｔ为迭代次数Ⅸ为聚类数，ｔｅｌ为特征属性数，ｎ为待分类的对象数，通常，Ｋ，ｍ，Ｋ嘲．在对大型数据集聚类时，Ｋ－ｍｅａｎｓ算法比层次聚类算法快得多．不足：通常会在获得一个局部最优值时终止；仅适合对数值型数据聚类；只适用于聚类
５２ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．１９，Ｎｏ．１，Ｊａｎｕａｒｙ２００８
结果为凸形（即类簇为凸形）的数据集．
以经典Ｋ－ｍｅａｎｓ算法为基础，研究者们提出了很多新的改进的Ｋ－ｍｅａｎｓ算法，下面对其中的一些算法加以介绍．
２．２．２Ｋ－ｍｏｄｅｓ算法
（１）Ｋ－ｍｏｄｅｓ．Ｈｕａｎｇ算法［１４】
在阐述Ｋ－ｍｏｄｅｓ算法之前，先对Ｍｅａｎｓ与Ｍｏｄｅｓ做简单介绍．
在Ｋ－ｍｅａｎｓ算法中，ｍｅａｎ为类簇中心或称为质心，是指一个类簇中所有对象关于属性的均值，最初可随机指定．在Ｋ－ｍｏｄｅｓ算法中，ｍｏｄｅｓ可定义如下：设ｊ每｛墨兄，．．．夕‘｝是一个数据集，Ｖ五∈石由ｍ个分类属性｛彳１４２，．．．，彳。｝来描述Ⅸ可表示成向量瓴Ｉ—ｆ１２，．．．＾。＞，又可表示成属性一值对的合取式■ｌ鼍砖１】＾…＾Ｍ。刁锄】；Ｑ是Ｘ的一个ｍｏｄｅ，Ｑ可表示成向量（９１，ｑ２，．．．，鼋。＞，也可表示成属性?值对的合取式Ｍ１＝９１】＾…＾口。＝ｇ。】，Ｑ需使∑渊…。矾（五，Ｑ）取最小值，ｄ１陇，Ｑ）表示Ⅸ与Ｑ之间的距离，Ｑ不必是ｘ的一个元素．
１９９８年，Ｈｕａｎｇ为克服Ｋ－ｍｅａｎｓ算法仅适合于数值属性数据聚类的局限性，提出了一种适合于分类属性数据聚类的Ｋ－ｍｏｄｅｓ算法．该算法对Ｋ－ｍｅａｎｓ进行了３点扩展：引入了处理分类对象的新的相异性度量方法（简单的相异性度量匹配模式），使用ｍｏｄｅｓ代替ｍｅａｎｓ，并在聚类过程中使用基于频度的方法修正ｍｏｄｅｓ，以使聚类代价函数值最小化．
这些扩展允许人们能够直接使用Ｋ－ｍｅａｎｓ范例聚类有分类属性的数据。无须对数据进行变换．Ｋ－ｍｏｄｅｓ算法的另一个优点是ｍｏｄｅｓ能给出类的特性描述，这对聚类结果的解释是非常重要的．事实上，Ｋ－ｍｏｄｅｓ算法比Ｋ－ｍｅａｎｓ算法能够更快收敛．Ｈｕａｎｇ使用众所周知的大豆疾病数据集对其算法进行了测试，结果表明，Ｋ－ｍｏｄｅｓ算法具有很好的聚类性能．进一步地，他用包含５０万条记录和３４个分类属性的健康保险数据集进行了测试，结
果证明，该算法在（聚类的）类数和记录数两个方面是真正可伸缩的．
与Ｋ－ｍｅａｎｓ算法一样，Ｋ－ｍｏｄｅｓ算法也会产生局部最优解，依赖于初始化ｍｏｄｅｓ的选择和数据集中数据对象的次序．初始化ｍｏｄｅｓ的选择策略尚需进一步研究．
１９９９年，Ｈｕａｎｇ等人（”１证明了经过有限次迭代Ｋ－ｍｏｄｅｓ算法仅能收敛于局部最小值．
（２）Ｋ．ｍｏｄｅｓ．ＣＧＣ算’法Ｉ”１
２００１年，Ｃｈａｔｕｒｖｅｄｉ等人提出一种面向分类属性数据（名义尺度数据）的非参数聚类方法，称为Ｋ－ｍｏｄｅｓ．ＣＧＣ算法，类似于面向数值数据（间隔尺度数据）的传统Ｋ－ｍｅａｎｓ算法．与现存的大多数面向分类属性数据的聚类方法不同，Ｋ－ｍｏｄｅｓ．ＣＧＣ算法显式地优化一个基于岛范数的损失函数．ｒ‘在蒙特卡罗模拟中，Ｃｈａｔｕｒｖｅｄｉ等人用Ｋ－ｍｏｄｅｓ．ＣＧＣ和潜类算法［１７】来恢复一个已知的潜在类结构，结果表明，两者具有相等的执行效率．然而，Ｋ－ｍｏｄｅｓ．ＣＧＣ算法不但在速度方面比潜类算法快一个数量级，而且更少遇到局部最优的情况尉于包含大量分类变量的数据集，潜类算法计算极其缓慢，变得不可行．尽管在一些情况下，潜类算法比Ｋ－ｍｏｄｅｓ．ＣＧＣ算法执行得更好，但Ｃｈａｔｕｒｖｅｄｉ猜测在另外一些情况下，潜类算法很可能是不可行的．因此，Ｃｈａｔｕｒｖｅｄｉ等人建议在执行聚类分析时应互补地使用这两种方法，同时给出了Ｋ－ｍｏｄｅｓ．ＣＧＣ算法和潜类算法的经验比较，结果表明前者更占优势．
２００３年，Ｈｕａｎｇ［１８１证明了Ｋ－ｍｏｄｅｓ．ＣＧＣ算法与Ｋ－ｍｏｄｅｓ．Ｈｕａｎｇ算法是等价的．
２．２．３迭代初始点集求精Ｋ－ｍｏｄｅｓ算法
２００２年，Ｓｕｎ等人㈣将Ｂｒａｄｌｅｙ等人的迭代初始点集求精算法【２０１应用于Ｋ－ｍｏｄｅｓ算法（Ｈｕａｎｇ，１９９８）．尽管Ｈｕａｎｇ的Ｋ－ｍｏｄｅｓ算法能够聚类分类数据，但它需要预先决定或随机选择类（簇）的初始ｍｏｄｅｓ，并且初始ｍｏｄｅｓ的差异常常会导致截然不同的聚类结果．文中，Ｓｕｎ等人给出了一个关于应用Ｂｒａｄｌｅｙ等人的迭代初始点求精算法于Ｋ－ｍｏｄｅｓ聚类的实验研究．
Ｓｕｎ等人用知名大豆疾病［２ｌ】数据集进行测试。大豆疾病数据包含４７个记录，每个记录由３５个特征描述．每个记录都被标记为以下４种疾病中的一种：ＤｉａｐｏｒｔｈｅＳｔｅｍＣａｎｋｅｒ，ＣｈａｒｃｏａｌＲｏｔ，ＲｉｈｉｚｏｃｔｏｎｉａＲｏｏｔＲｏｔ以及ＰｈｙｔｏｐｈｔｈｏｒａＲｏｔ，除了ＰｈｙｔｏｐｈｔｈｏｒａＲｏｔ有１７个记录外，其他３种疾病都有１０个记录．针对Ｋ－ｍｏｄｅｓ算法，分两
孙吉贵等：聚类算法研究５３
种方案对大豆疾病数据集进行聚类实验：方案１随机选择初始点集：方案２采用迭代初始点集求精方法选择初始点集．实验结果表明，采用方案２的Ｋ－ｍｏｄｅｓ算法能够产生更高精度和更可靠的聚类结果．求精算法在给定数据集的一个小子样本集上进行，因此只需存储全部数据的内存空间的一小部分．然而，对于更大、更复杂分布的数据集，关于算法的可伸缩性和适应性方面还有许多问题需要研究．
２．２．４一致性保留Ｋ－ｍｅａｎｓ算法（Ｋ－ｍｅａｎｓ．ＣＰ）
２００４年，Ｄｉｎｇ等人【２２】提出一致性保留Ｋ－ｍｅａｎｓ算法（Ｋ－ｍｅａｎｓ．ＣＰ）．最近邻一致性是统计模式识别中的一个重要概念，他们将这个概念扩展到数据聚类，对一个类中的任意数据点，要求它的七最近邻和ｋ互最近邻都必须在该类中．他们研究了类的忌最近邻一致性的性质，提出了ｋＮＮ和ｋＭＮ一致性强制和改进算法，并提出了将类ｋ最近邻或类ｋ互最近邻一致性作为数据聚类的一种重要质量度量方法．他们选用互联网上２０个新闻组数据集进行了实验，结果表明，ｋ最近邻一致性、七互最近邻一致性以及算法聚类的正确率都得到显著改善．同时，这也表明局部一致性信息可帮助全局聚类目标函数优化．
算法Ｋ－ｍｅａｎｓ．ＣＰ．
１【初始化】．随机选择Ｋ个点作为初始类的中心（ｃｌ，Ｃ２，．．．，ｃ０；
２［分配近邻集】．分配一个近邻集砖１１＂将Ｓ分配到离其最近的类印中，Ｐ＝鹕ｍｉＩｌ词，。ｊ【∑。。ｊ（而一％）２３【更新类中心】．置ｍｖ＝∑而。ｑｘｌ／ｎｖ；／／＊更新聚类中心（即质心），ｍ，是类Ｇ的中心，刀尸Ｉ刮
４【收敛否？】．质心不再移动，则终止算法；否则返回步骤２．ＩＩ＊‘，砌＝∑，叱Ｊ∑而。Ｇ（而一ｍ，）２判断收敛２．２．５模糊聚类算法
１９６９年，Ｒｕｓｐｉｎｉ首次将模糊集理论应用到聚类分析中，提出了模糊聚类算法（ｆｕｚｚｙｃ－ｍｅａｎｓ，简称ＦＣＭ）．
ＦＣＭ算法是图像分割使用最多的方法之一，它的成功主要归功于为解决每个图像像素的隶属需要引入了模糊性．比之脆弱（ｃｒｉｓｐ）或硬分割方法，ＦＣＭ能够保留初始图像的更多信息．然而，ＦＣＭ的一个缺点是不考虑图像上下文中的任何空间信息，这使得它对噪声和其他人造图像非常敏感．人们围绕ＦＣＭ算法开展了大量研究，下面只对这方面的最新研究作简单介绍‘２３’２４１．
２００６年，李洁等人【２５】提出基于特征加权的模糊聚类新算法ＮＦＷＦＣＡ．传统模糊尽均值算法、Ｋ－ｍｏｄｅｓ算法和尽原型算法都假定样本矢量的各维特征对聚类贡献相同．但在实际应用中，由于样本矢量的各维特征来自不同传感器，存在测量精度及可靠性等差异，样本矢量的各维特征对聚类影响不尽相同．以模糊忌原型算法为基础，算法ＮＦＷＦＣＡ采用ＲｅｌｉｅｆＦ算法［２６１确定各维特征的权重，数值特征权值的计算方法为
∥：∥一丝＝丝：＋—ｄｉｆｆ＿—ｍｉｓｓ＂．
ＲＲ
属性特征权值的计算方法为
∥：Ａｃ一丝：竺＋—ｄｉｆｆ＿—ｍ细ｃ．
ＲＲ
从而修正目标函数为
Ｊ（ｗ，Ｐ）＝∑Ⅲ一一∑甩…，。嵋∑。乩．Ｊ疋Ｊ矗一办１２＋∑一一一嵋∑，。嵋神巧万。刍，ｐ二）１．当以阡∽最小时，聚类结果最优．ＮＦＷＦＣＡ还可以将模糊尽均值、Ｋ－ｍｏｄｅｓ和尽原型等算法合而为一．当∥＝０时，对应加权模糊尽均值算法；当五名０时，对应加权模糊Ｋ－ｍｏｄｅｓ算法；当脾Ｏ且五ｒ≠Ｏ时，对应加权模糊尽原型算法．
通过各种实际数据集的测试，实验结果表明，该算法的聚类结果较之传统模糊量均值算法、Ｋ－ｍｏｄｅｓ算法和忌原型算法要更准确、更高效．同时，该算法还可以分析各维特征对聚类的贡献度，有效进行特征提取和优选，这对聚类算法研究及其应用都有一定的意义．
２００７年，Ｃａｉ等人【２７】结合局部空间和灰度信息，提出快速通用ＦＣＭ聚类算法ＦＧＦＣＭ，其特点为：（１）用一个新因子岛作局部（空间和灰度）相似性度量，不仅确保图像的抗扰性，保留图像细节，而且除去了经验调节参数
ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．１９，Ｎｏ．１，Ｊａｎｕａｒｙ２００８
弼（２）分割时间只与灰度级数ｇ有关，与图像大小Ⅳ（＞＞ｇ）无关，因此，其聚类时间复杂性由Ｏ（Ｎｃｌｌ）减少到Ｏ（ｑｄ９，其中，ｃ为聚类数目＾和，２（＜＾）分别为ＦＣＭ和ＦＧＦＣＭ的迭代次数；（３）ＦＧＦＣＭ作为一个通用框架，可用于图像分割的很多其他算法，快速ＦＣＭ，ＥｎＦＣＭ，ＦＧＦＣＭ＿Ｓ１和ＦＧＦＣＭ＿Ｓ１等均可作为其特例被导出．关于合成和真实世界图像所进行的实验表明，ＦＧＦＣＭ是通用的、简单的，并且适合于有噪声和无噪声的多种类型图像；另一方面，ＦＧＦＣＭ是快速的，适合大幅灰度图像．Ｃａｉ等人指出，进一步的研究工作包括算法的聚类有效性、自适应决定聚类数量以及图像增益场评估等其他应用研究．
２．２．６图论算法
１９９９年，Ｊａｉｎ［３］指出著名的图论分裂聚类算法的主要思想是：构造一棵关于数据的最小生成树（ｍｉｎｉｍａｌ
ｓｐａｎｎｉｎｇｔｒｅｅ，简称ＭＳＴ），通过删除最小生成树的最长边来形成类．基于图论的聚类算法主要包括：ＲａｎｄｏｍＷａｌｋ，ＣＨＡＭＥＬＥＯＮ，ＡＵＴＯＣＬＵＳＴ［２８—３０１等．
２００７年，Ｌｉ【３ｌ】提出一种基于最大曰距离子树的聚类算法ＭＤＳ＿ＣＬＵＳＴＥＲ，使用阈值剪枝，剪掉最小生成树中所有长度大于阈值验０的边，从而生成最大钷离子树集，其中每个最大曰距离子树的顶点集正好形成一个类．该算法的特点是：能发现任意形状非重叠的类，只要简单说明一个参数，该参数系指每个类中最少应包含的元素个数；还能提供一个分层体系结构中几个主要的类层次，这不同于由传统层次聚合方案所生成的包括所有层次的分层体系结构．此外，该算法能将小类中的元素作为数据集中的奇异值检测出来，如果奇异值数量相对大，则将这些奇异值合并成一个新类（称为背景类）．模拟实验表明了该聚类方案的有效性．
２．３基于网格和密度的聚类算法
基于网格和密度的聚类方法是一类重要的聚类方法，它们在以空间信息处理为代表的众多领域有着广泛
应用．特别是伴随着新近处理大规模数据集、可伸缩的聚类方法的开发，其在空间数据挖掘研究子域日趋活跃．与传统聚类算法不同：基于密度的聚类算法，通过数据密度（单位区域内的实例数）来发现任意形状的类簇；基于网格的聚类算法，使用一个网格结构，围绕模式组织由矩形块划分的值空间，基于块的分布信息实现模式聚类．基于网格的聚类算法常常与其他方法相结合，特别是与基于密度的聚类方法相结合．
２００１年，Ｚｈａｏ和Ｓｏｎｇ［３２】给出网格密度等值线聚类算法ＧＤＩＬＣ．密度等值线图能够很好地描述数据样本的分布．算法ＧＤＩＬＣ的核心思想——用密度等值线图描述数据样本分布．使用基于网格方法计算每一个数据样本的密度，发现相对的密集区域——类（或称为类簇）．ＧＤＩＬＣ具有消除奇异值和发现各种形状的类的能力，它是一种非监督聚类算法．他们的实验表明，ＧＤＩＬＣ算法具有聚类准确率高和聚类速度快等特点．２００４年，Ｍａ［３３】提出一种新的基于移位网格概念的基于密度和网格的聚类算法ＳＧＣ．ＳＧＣ是一种非参数类型的算法，它不需要用户输入参数，它把数据空间的每一维分成某些间隔以形成一个数据空间的网格结构．基于滑动窗口概念，为获得一个被更多描述的密度剖面引入了整个网格结构的移位概念，因此能够提高聚类结果的精度（准确度）．与许多传统算法相比，该算法是高效的，因为类数据是基于网格单元的．该算法的主要优点可概括为：计算时间与数据集样本数无关；在处理任意形状类簇时展现了极好的性能；不需要用户输入参数；当处理大型数据集时’｛艮少遇到内存受限问题．
２００５年，Ｐｉｌｅｖａ等人【３４】提出一种用于大型，高维空间数据库的网格聚类算法ＧＣＨＬ．ＧＣＨＬ将一种新的基于密度——网格的聚类算法和并行轴划分策略相结合，以确定输入数据空间的高密度区域——类簇．该算法能够很好地工作在任意数据集的特征空间中．ＧＣＨＬ的主要特点为：（１）只对数据扫描一次；将大型数据集划分成子部分，使用有限内存缓冲区一部分接一部分地进行处理；（２）将类簇看成是由数据空间中的低密度区域划分的对象密集区域，能发现任意形状的类簇；（３）能发现奇异值，对噪声数据不敏感；（４）将数据空间量化为用于形成网格数据结构的有限数量的单元，所有的聚类操作都在网格结构上进行；聚类快速，聚类时间独立于数据对象数目和数据次序；（５）适合大型、高维数据集的聚类．
Ｐｉｌｅｖａ等人的实验结果表明，该算法所获得的聚类结果是高质量的，具有发现凹／更深、凸／更高区域的能力，对奇异值和噪声的稳健性以及极好的伸缩性，这使其能够很好地应用于医疗和地理领域．
２００６年，Ｍｉｃｒｏ等人【３５】面向移动对象轨迹数据处理领域，基于简单的轨迹间距离概念，提出了一种基于密度
孙吉贵等：聚类算法研究５５
的自适应聚类方法ＴＦＣＴＭＯ．。进一步考虑时态内在语义，给出时间聚焦方法以提高轨迹聚类效果．Ｍｉｒｅｏ等人将对象间的空间距离概念扩展到轨迹间的时空距离概念。由此将基于密度的聚类方法应用到轨迹上．Ｍｉｒｃｏ等人的关键思想是，将时态信息和空间信息相结合，使时态信息在移动对象轨迹聚类中起到了重要作用：根据所选取的时间区间的大小，轨迹间的相关程度是不同的．时间聚焦（ｔｅｍｐｇｒａｌｆｏｃｕｓｉｎｇ）方法能够发现最有意义的时间区间，提高了移动对象轨迹聚类的质量．
２００７年，Ｄｅｒｙａ等人【３６】对ＤＢＳＣＡＮ（ｄｅｎｓｉｔｙ－ｂａｓｅｄｓｐａｔｉａｌｃｌｕｓｔｅｒｉｎｇｏｆａｐｐｌｉｃａｔｉｏｎｓｗｉｔｈｎｏｉｓｅ）：进行了与辨识核对象、噪音对象和邻近类簇相关的３个边缘扩展。进而提出一种新的基于密度的聚类算法ＳＴ－ＤＢＳＣＡＮ（ｓｐａｔｉａｌ．－ｔｅｍｐｏｒａｌＤＢＳＣＡＮ）．与现有的基于密度聚类算法相比，该算法具有依据非空间值、空间值和时态值发现类簇的能力．
２．４其他聚类算法
２．４．１ＡＣＯＤＦ聚类算法
２００４年，Ｔｓａｉ等人【３７】提出一个新颖的具有不同偏好的蚁群系统（ｎｏｖｅｌＡｓ）一一Ａｃ０ＤＦ（ａｎｏｖｅｌｄａｔａｃｌｕｓｔｅｒｉｎｇａｐｐｒｏａｃｈｆｏｒｄａｔａｍｉｎｉｎｇｉｎｌａｒｇｅｄａｔａｂａｓｅｓ），用来解决数据聚类问题（当时未见用于数据聚类的ＡＣＯ（ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ）算法的报道）．设计一种不需要求解任何硬子问题（ａｎｙｈａｒｄｓｕｂ．－ｐｒｏｂｌｅｍ），但能给出近似最优解的聚类算法，是人们所期待的．ＡＣＯＤＦ能够快速获得最优解，它所包含的３个重要策略介绍如下：（１）应用不同偏好的（ｆａｖｏｒａｂｌｅ）ＡＣＯ策略．每个蚂蚁只需访问全部城市数的十分之一，并且访问城市数目逐次减少；几次循环之后，两点间相对短的路径的信息素浓度增加，两点间相对长的路径的信息素减少．因此，蚂蚁喜欢访问距离近的节点，并用自己的信息素加强此路径（由其喜欢访问的节点组成）；最后形成具有较高浓度的
路径，即聚类完成．
（２）为减少获得局部最优解所需要访问的城市数量，对蚁群采用模拟退火策略．为此设计了两个公式：
ｎｓ（ｔ＋１）＝ｎｓ（ｔ）×Ｌ
其中，珊是蚁群在％函数期间访问的节点数，ｎｓ（ｔ＋１）表示当前蚁群的访问的节点数，，ｎｓ（０表示上‘次循环蚁群访问的节点数，ｒ是一个常数（７印．９５）．
ｎ／（ｔ＋１）＝２ｘｎｓ（ｔ）／３－ｉｘｎｓ（ｔ）／（ｒｕｎｘ３），
其中，矿是蚁群在乃函数期间访问的节点数，硬件１）表示蚁群当前访问的节点数，顿力表示上一次循环蚁群访问的节点数，ｒｕｎ＝２，ｆ∈｛ｌ，２｝．
（３）使用锦标赛（ｔｏｕｒｎａｍｅｎｔ）：选择策略．与传统ＡＣＯ不同，ＡＣＯＤＦ采用锦标赛选择技术进行路径选择．即从Ⅳ条路径中随机选择ｘ条路径，再从这髟条路径中选择最短路径（悯．
Ｔｓａｉ等人分别进行了模拟和实际数据实验．模拟数据实验：首先选含５７９个数据的数据集，分别用ＡＣＯＤＦ，ＧＫＡ和ＦＳＯＭ＋Ｋ－ｍｅａｎｓ等３种算法进行非球形聚类；然后选含３００个数据的数据集，依次用上面３种算法进行球形聚类．实际数据实验：采用７３２个客户信用卡上的８维实际数据，根据客户收入和消费进行聚类．实验结果表明，大多数情况下，，ＡＣＯＤＦ的搜索速度比ＧＫＡ和ＦＳＯＭ＋Ｋ－ｍｅａｎｓ更快，且错误率比它们更小．
３实验
为了对有一定代表性的聚类算法给出进一步的分析，我们从重点介绍的１９种算法中选出８种算法，从ＵＣＩ机器学习数据集储存库中选择了人们常用的５个数据集，分别针对分类属性数据和数值型数据对这８种算法进行了对比实验．实验的计算机环境为：处理器为ＰｅｎｔｉｕｍＭ１ＡＧＨｚ，内存５１２ＭＢ，硬盘８０Ｇ操作系统为ＷｉｎｄｏｗｓＸＰ，编程语言为ＶＣ６．Ｏ．
３．１数据集
本文采用Ｉｒｉｓ，Ｗｉｎｅ，，Ｓｏｙｂｅａｎ，．Ｚｏｏ和Ｉｍａｇｅ数据集作为测试数据集，前４个数据集为常用的知名数据集，已知其聚类结果可靠、并取得一致意见，适合做聚类分析的基准数据集．本文选用Ｉｍａｇｅ数据集的主要目的是与Ｉｒｉｓ
５６ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．１９，Ｎｏ．１，Ｊａｎｕａｒｙ２００８
和Ｗｉｎｅ这两个基准数据集进行比较．
针对数值型数据，分别采用Ｉｒｉｓ，Ｗｉｎｅ和Ｉｍａｇｅ等３个数据集进行测试．
Ｉｒｉｓ包含３个类，每类各有５０个元素，每一类代表一种类型的鸢尾花，１５０个样本在３个类簇中分布均匀；其中，一类与另外两类线性可分，另外两类有部分重叠．Ｗｉｎｅ数据集具有好的聚类结构，它包含１７８个样本，１３个数值型属性，分成３个类，每类中样本数量不同．Ｉｍａｇｅ取自ＵＣＩ机器学习数据集，本文作者在众多文献中未见其被使用．该数据集是从包含７个户外图像集合的数据库中随机选取的，并采用手工进行分类．针对分类属性数据，分别采用Ｓｏｙｂｅａｎ和Ｚｏｏ数据集进行测试．
Ｓｏｙｂｅａｎ数据集共有４７个样本，具有３５个属性，分为４类，是线性可分的，其所有属性都可作为分类属性．Ｚｏｏ数据集共有１０１个记录，分为７类，是线性不可分的．在Ｚｏｏ中，由１６个属性来描述样本，其中１５个为布尔属性值｛０．１）和１个分类属性值属性（腿的数量）｛０，２，４，５，６，８）．
３．２针对分类属性数据的实验
针对分类属性数据聚类，我们对Ｋ－ｍｏｄｅｓ算法、迭代初始点集求精Ｋ－ｍｏｄｅｓ算法分别采用线性可分大豆疾病数据和线性不可分动物园数据进行２０次随机实验．
３．２．１大豆疾病数据实验
大豆疾病数据实验结果：我们采用Ｓｕｎ等人【１９】提出的计算正确率的方法．正确率计算公式为
，－＝∑‰。（ｑ／ｎ）．
ａ，是出现在第ｆ个类簇（执行算法得到的）及其对应的类（初始类）中的样本数，ｋ是类数（这里有ｋ－－４，聚类数），一是数据集中样本总数（即４７）．实验结果见表１和表２．
Ｔａｂｌｅ１Ｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔｓｏｆ２０ｒａｎｄｏｍｔｅｓｔｓｆｏｒｓｏｙｂｅａｎｄｉｓｅａｓｅｄａｔａｓｅｔｏｎ２ａｌｇｏｒｉｔｈｍｓ
表１两种算法对大豆疾病数据集２０次随机实验聚类结果
～、、＝Ａｃｃｕｒａｃ孓ｓ，＝冬Ｋ－ｍ。ｄｅｓ１‘唧ｈｗ蛳：燃ｔｓ∞缸锄眦
１ｗｏｌ—、－～）
９８５７
９４６８
８９Ｏ３
７７Ｏｌ
７０７ｌ
６８２Ｏ
Ｔａｂｌｅ２Ａｖｅｒａｇｅｒｕｎｔｉｍｅｏｆ２０ｒａｎｄｏｍｔｅｓｔｓｆｏｒｓｏｙｂｅａｎｄｉｓｅａｓｅｄａｔａｓｅｔｏｎ２ａｌｇｏｒｉｔｈｍｓ
表２两种算法对大豆疾病数据进行２０次随机实验的平均运行时间
垒！ｇ！里尘翌堑！！！壁旦坚！！！ｇ！！虫！ｆ１２
Ｋ－ｍｏｄｅｓＯ．００８１７３３ｌ
！生！丝：！垫ｉ望！！：Ｐ！ｉ坐！！！！！！塑坚坐墨：巴！皇！！！：！！！：墼箜
从大豆疾病数据集的实验结果来看，迭代初始点集求精Ｋ－ｍｏｄｅｓ算法明显好于Ｋ－ｍｏｄｅｓ算法，两者的平均正确率分别为９２．６％和８４％．从算法运行时间来看，迭代初始点集求精Ｋ－ｍｏｄｅｓ算法所需时间略长．
３．２．２动物园数据实验
下面对Ｋ－ｍｏｄｅｓ算法和迭代初始点集求精Ｋ－ｍｏｄｅｓ算法，用动物园数据ｆ２１】进行２０次随机实验，实验结果见表３．聚类正确率计算公式为ｒ＝ｌ一错分样本个数／样本总数），且以下实验均采用该正确率计算公式．
Ｔａｂｌｅ３Ｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔｓｏｆ２０ｒａｎｄｏｍｔｅｓｔｓｆｏｒＺＯＯｄａｔａｓｅｔｏｎ２ａｌｇｏｒｉｔｈｍｓ
表３两种算法对动物园数据进行２０次随机实验的聚类结果
Ａｌｇｏｒｉｔｈｍｎ肘ｕｍ！Ｄ哪ｅｌ＂Ｓｅ（粤ｍｌｃｓｔｌｕ畔ｏｅ％ｍ９ａ扒ｍｍｎａｌｏｎｌｌａ．）ａｃｃ舢ｕｒ。ａ蒜ｃｙｕ／ｏ，）觚盯ａｇｔｒｉｎ。ｅ。（斧嘲
Ｉ‘Ｊｓｌ！丝堡垡竖！！型！！：２２ｉ！望望！！！！翌塑！墨：巴！生！！ｉ！！：！ｉ垒：丝：塑！ｉ！ｉ
孙吉贵等：聚类算法研究５７
从以上实验结果可以得出，大豆集的分类效果整体好于动物园数据集，这与大豆集数据线性可分而动物园数据线性不可分是一致的．对于大豆集和动物园两个数据集，迭代初始点集求精Ｋ－ｍｏｄｅｓ算法的分类正确率都好于Ｋ－ｍｏｄｅｓ算法。这说明初始化时选择一个接近真实ｍｏｄｅｓ的初始值，通过不断迭代更容易得到正确的聚类结果．另外，从运行时间来看，迭代初始点集求精Ｋ－ｍｏｄｅｓ算法的运行时间比Ｋ－ｍｏｄｅｓ算法长一些．
３．３针对数值型数据进行实验
３．３．１层次聚合算法和Ｋ－ｍｅａｎｓ算法比较
针对数值型数据，我们分别采用层次聚合算法中的单一联接法、完全联接法、类间平均联接法、沃德法和划分式聚类算法中的Ｋ－ｍｅａｎｓ算法，用ＵＣＩ中的数据集Ｉｒｉｓ，Ｗｉｎｅ，Ｉｍａｇｅ［２９】随机进行了２０次聚类实验，对比结果见表４．．
Ｔａｂｌｅ４Ｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔｓｏｆ２０ｒａｎｄｏｍｔｅｓｔｓｆｏｒＩｒｉｓ，Ｗｉｎｅ，Ｉｍａｇｅｄａｔａｓｅｔｓｏｎｓｅｖｅｒａｌａｌｇｏｒｉｔｈｍｓ
表４几种算法对Ｉｒｉｓ，Ｗｉｎｅ，Ｉｍａｇｅ数据集２０次随机实验的聚类结果
Ａｖｅｒａｇｅａｃｃｕｒａｃｙｏｆｒｕｎｎｉｎｇ２０ｃｙｃｌｅｓ（％）Ａｖｅｒａｇｅｒｕｎｎｉｎｇｔｉｍｅ（ｓ）
Ａｌｇｏｒｉｔｈｍ
ＩｒｉｓＷｉｎｅＩｍａｇｅＩｒｉｓＷｉｎｅＩｍａｇｅＮｅａｒｅｓｔｎｅｉｇｈｂｏｒ６８．００４２．７０３０．００１．５８３１０２５３．１３４６１４５５．２４ｌ４３
Ｆｕｒｔｈｅｓｔｎｅｉｇｈｂｏｒ８４．００６７．４０３９．００１．５０４２５８５３．１４３３７４５．６７０８Ｂｅｔｗｅｅｎｇｒｏｕｐｓａｖｅｒａｇｅ７４．７０６１．２０３７．００１．５０２６５９５３．１５２５６８５５．７８５２８Ｗａｒｄｍｅｔｈｏｄ。８９．３０５５．６０６０．ｏｏ２．３７９２６５４．７７５６６２５８．９５９９５Ｋ－ｍｅａｎｓ８１．６０８７，９６５６．０００．００２５５３５２２５０．００３７６４２５０．０４５６６２８３５实验结果表明，传统层次聚合算法对聚类结构好的Ｗｉｎｅ数据集分类结果并不理想，这与传统层次聚合算法的再分配能力差相关（即若在初始阶段把一些数据分配给某个类簇，那么这些数据就不能再被分配给其他类
簇）；而对于Ｉｍａｇｅ数据集来讲，无论层次聚合算法还是Ｋ－ｍｅａｎｓ算法都基本上不能对其进行正确分类，这可能与Ｉｍａｇｅ数据集的聚类结构等有关系；Ｋ－ｍｅａｎｓ的运行效率远高于传统层次聚合算法．我们还发现，聚类结果有其不可预见性，对于不同数据集合，同一算法的聚类正确率可能会大不相同；对于同一数据集合，采用不同的聚类算法，其聚类结果和效率也会有很大差异．因此在实际应用中，应根据待聚类数据集的数据类型、聚类结构（若可得到的话）选择相应的聚类算法，以取得最佳聚类效果．
３．３．２ｋ最近邻一致性强制与保留算法Ｋ－ｍｅａｎｓ．ＣＰ关于不同足值的实验
选择Ｉｒｉｓ和Ｗｉｎｅ数值属性数据集，针对Ｋ－ｍｅａｎｓ．ＣＰ算法（采用欧式距离进行相似性计算）Ⅸ取ｌｏ，分别进行２０次随机实验．实验结果（见表５）表明，无论对数据集Ｉｒｉｓ还是数据集Ｗｉｎｅ，都是在焉，－３时达到最高正确率．对于数据集Ｉｒｉｓ，Ｋ＝３时正确率为８４．６５％：对于数据集Ｗｉｎｅ，Ｋ＝３时正确率为６４．００％．这说明Ｋ－ｍｅａｎｓ．ＣＰ算法对数据集的初始分类数具有一定的预测功能．此外，聚类结果在很大程度上依赖于所用相似性度量方式．Ｔａｂｌｅ５Ｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔｓｏｆ２０ｒａｎｄｏｍｔｅｓｔｓｆｏｒＩｒｉｓ．ＷｉｎｅｄａｔａｓｅｔｓｏｎＫ－ｍｅａｎｓ—ＣＰ
表５一致性保留Ｋ－ｍｅａｎｓ算法对Ｉｒｉｓ，Ｗｉｎｅ数据集进行２０次随机实验的聚类结果
ＩｒｉｓＷｉｎｅ
置
ＡｖｅｒａｇｅａＧｃｕｒａｃｙ（％）Ａｖｅｒａｇｅｒｕｎｎｉｎｇｔｉｍｅ（ｓ）Ａｖｅｒａｇｅａｃｃｕｒａｃｙ（％）Ａｖｅｒａｇｅｒｕｎｎｉｎｇｔｉｍｅ（ｓ）Ｋ＝Ｉ８１．０００．０１５１７９０７５５．４５０．０２３５３２９
盖．＿２８１．４００．０１２６４４３１５５６．５５０．０４３９８６１７５
Ｘ＝３８４．６５Ｏ．０１２９７９５６５６４．０００．０８９０７４９５
捌８２．５００．０１３７１７８４５０．１００．１８９２３２５
３．４Ｋ－ｍｅａＲ５算法与露最近邻一致强制和保留算法比较
为判断七最近邻一致强制和保留算法是否明显优于足均值（Ｋ－ｍｅａｎｓ）算法、ｋＮＮ一致性与聚类质量之间有何关系，本文针对Ｋ－ｍｅａｎｓ算法、１最近邻一致强制和保留算法（扛ｌ，简记为ｅｐｌ算法）和２最近邻一致强制和保留算法（ｋ＝－２，简记为ｅｐ２算法），关于Ｉｍａｇｉｎｅ，Ｉｒｉｓ，Ｗｉｎｅ，Ｇｌａｓｓ，Ｉｏｎｏｓｐｈｅｒｅ等数值型数据集进行了２０次随机聚类实验．从聚类结果的正确率和总体质量（简称质量）两个方面来评价聚类结果之优劣．总体质量（质量）可用类间差异与类内差异之比来度量．一类簇的紧凑程度可用该类簇中每个数据到该类簇质心之间距离的平方和来刻画．整
５８ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．１９，Ｎｏ．１，Ｊａｎｕａｒｙ２００８
个聚类的类簇内差、整个聚类之类簇间的差异以及总体质量则分别由下面的式（１卜式（３）来计算：
∑吨，。Ｅ矾ｄ（ｘ，瓦）２（１）
∑。；／ｄｎｄ（弓，写）２（２）
∑吲删。ｄ（ｊｉ：『，夏）２／∑同，。。∑ｘＥｃ，ｄ“瓦）２（３）其中，ｋ为聚类结果包含的类簇数，Ｃ，表示类簇’，，瓦表示Ｃ，的质心，ｉ，夏分别表示类衡和ｆ的质心，ｄ为距离函数．这里的质量只有相对意义，对相同算法不同数据集“质量值”间的相互比较没有意义．实验结果见表６．实验结果表明，从聚类正确率和总体质量来看乒最近邻一致强制和保留算法不优于Ｋ－ｍｅａｎｓ算法，ｋＮＮ一致性与聚类质量无关．
Ｔａｂｌｅ６Ｃｌｎｓｔｅｒｉｎｇｒｅｓｕｌｔｓｏｆ２０ｒａｎｄｏｍｔｅｓｔｓｆｏｒ５ｄａｔａｓｅｔｓｏｉｌＫ－ｍｅａｎｓ．ｃｐｌ＆ｃｐ２ａｌｇｏｒｉｔｈｍｓ
表６Ｋ－ｍｅａｎｓ，ｅｐｌ和ｅｐ２算法关于５个数据集的２０次随机实验聚类结果
Ｉｍａｌ：ｉｎｅＡｖｅｒａｇｅａｃｃｕｒａｃｙ（２０ｔｉｍｅｓ）Ａｖｅｒａｇｅｑｕａｌｉｔｙ（２０ｔｉｍｅｓ）
ｃｐｌ（１Ｍｎ０．６２３５７１４２８５７１４２８０．７７８０３６７５０８３９３８００
ｅｐ２（２ＮＮ）０．６０９５２３８０９５２３８０９０．７６４７５３６１７７１７６ｌｌ０
Ｋ－ｍｅａｎｓ０．６３２３８０９５２３８０９５２０．７３４０７６３５８２９Ｉ７１９Ｏ
ＩｒｉｓＡｖｅｒａｇｅａｃｃｕｒａｃｙ（２０ｔｉｍｅｓ）Ａｖｅｒａｇｅｑｕａｌｉｔｙ（２０ｔｉｍｅｓ）
０００００００００００００．２５８６２６１７２４４８１２４０
ｅｐｌ（１ＮＮｌ０．８４０
ｃｐ２（２ＮＮ）０．８９２３３３３３３３３３３３３０．３２２４８９１５７４１２０４６０
Ｋ－ｍｅｓｎ８０．８６２３３３３３３３３３３３４０．２９０２６８６９２３６４３ｌｌＯ
ＷｉｎｅＡｖｅｒａｇｅａｃｃｕｒａｃｙ（２０ｔｉｍｅｓ）Ａｖｅｒａｇｅｑｕａｌｉｔｙ（２０ｔｉｍｅｓ）
ｃｐｌ（１ＮＮ）０．８９８３１４６０６７４１５７３０．０４５４３３２３９３２４０６３６
∞２（２ＮＮ）０．９０５３３７０７８６５１６８５０．０４５１５５３６０９７６７０５９
Ｋ－ｒｅＣａｌｌＳ０．９４６９１０１１２３５９５５００．０４９０９８７３５８８００５７５
ＧｌａｓｓＡｖｅｒａｇｅａｃｃｕｒａｃｙ（２０ｔｉｍｅｓ）Ａｖｅｒａｇｅｑｕａｌｉｔｙ（２０ｔｉｍｅｓ）
ｅｐｌ（１ＮＮ）０．５１１９１５８８７８５０４６７０，４００８８１５０９６５８６７９
ｅｐ２（２Ｎｈｎ０．５３１５４２０５６０７４７６６０．４０４０６１８８６９０６００６
Ｋ－ｍｅａｎｓ０．５４２５２３３６４４８５９８ｌ０．４５３５２２０４７４３０９０５
ＩｏｎｏｓｐｈｅｒｅＡｖｅｒａｇｅａｃｃｕｒａｃｙ（２０ｔｉｍｅｓ）Ａｖｅｒａｇｅｑｕａｌｉｔｙ（２０ｔｉｍｅｓ）
ｅｐｌ（１ＮＮ）０．６９１８８０３４１８８０３４２０．００３８１２４７６８５１３４１２
ｃｐ２（２ＮＮ）０．６８２０５１２８２０５１２８２０．００３５５５３１１４６２０３４７
Ｋ－ｍｅａｎｓ０．７１０２５６４１０２５６４１００．００３７８４５９９４５０９１６ｌ
４结论
尽管聚类分析有着几十年的研究历史，众多聚类算法相继被提出、相关的应用被展开，但聚类问题仍然存在着巨大的挑战．
通过对一些比较有代表性的聚类算法的总结。可以得出如下一些结论：
大多数聚类算法都需要预先给出参数，事实上，如果没有相关知识和经验，这在多数情况下是不可行的．对于层次化聚类算法，如何找到聚合或分裂过程的有效终止条件仍然是一个开问题．由此，开展非参数聚类算法、将聚类算法与参数自动生成算法相结合、展示聚类过程等研究可能富有前景．Ｂｉｎａｒｙ．Ｐｏｓｉｔｉｖｅ方法（２００７年）的研究表明，将数据转换成正二进制会改善聚类结果的正确率和鲁棒性．粗聚类算法ＲＣＯＳＤ（２００７）能够有效挖掘连续数据，并能描述类簇的主要特性，有助于理解聚类结果．
快速找到类的合理个数和较好的初始类中心点集，使算法终止于全局最优解等是划分式聚类算法的研究热点；对于Ｋ－ｍｅａｎｓ和ＦｕｚｚｙＣ－ｍｅａｎｓ算法，还有使其适合分类属性数据集等研究课题．Ｋ－ｍｏｄｅｓ—Ｈｕａｎｇ算法适合分类属性数据，能给出类的特性描述，其对聚类数目和数据集规模都是可伸缩的，但已证明该算法经有限次迭代只能收敛于局部最优．２００２年的迭代初始点集求精Ｋ－ｍｏｄｅｓ算法较好地解决了Ｋ－ｍｏｄｅｓ．Ｈｕａｎｇ算法常因初始ｍｏｄｅｓ选择差异导致聚类结果截然不同的情况．２００４年，一致性保留算法Ｋ－ｍｅａｎｓ．ＣＰ的作者提出将筮最近邻一致性作为聚类质量的度量方法，并给出局部一致性信息能支持全局聚类目标函数优化和聚类正确率有明显改善等结果，但我们的实验结果未能支持该论文的观点和结论．２００６年，基于特征加权模糊聚类算法通过分析各维特征对聚类的贡献度，有效进行特征提取和优选。在聚类效率和准确率方面较传统模糊聚类算法都有明显提
孙吉贵等：聚类算法研究５９
高．２００７年，快速通用模糊聚类算法，一个通用框架，很多图像分割聚类算法都是其特例，它适合有噪声、无噪声多种类型图像和大幅灰度图像．
基于密度和网格聚类算法多用于时空信息处理、消除奇异值、发现各种形状的类簇，对噪声不敏感，适合大型、高维数据集等方面具有好的特性．网格密度等值线聚类算法ＧＤＩＬＣ（２００１）用密度等值线图描述样本分布，具有消除奇异值和发现各种形状类簇的能力．基于密度和网格的聚类算法ＳＧＣ（２００４）是一种非参数类型的算法；计算时间与数据集规模无关；适于任意形状类簇．网格聚类算法ＧＣＨＬ（２００５）能够发现任意形状类簇和奇异值，对噪声数据不敏感；聚类快速，聚类时间独立于数据规模和数据次序，伸缩性极好；适合大型、高维数据集．基于密度自适应聚类方法ＴＦＣＴＭＯ（２００６）结合时态信息和空间信息，时间聚焦能够提高移动对象轨迹聚类质量．基于密度聚类算法ＳＴｏＤＢＳＣＡＮ（２００７）能够综合使用非空间值、空间值和时态值实现聚类．在很多文献中，研究者们给出了各自的聚类算法评价指标，并只给出其算法的优点．我们认为，开展聚类算法（全面、客观的）评价标准、数据集特性的描述方法等研究，不仅时机成熟，而且有着重要意义．下面我们将给出关于文献【４】就１１种算法和我们就８种算法所作的实验的分析，以作为对上述总结的补充．同时给出部分代表性算法的比较（见表７）．
Ｔａｂｌｅ７Ｃｏｍｐａｒａｔｉｖｅｒｅｓｕｌｔｓｏｆｐａｒｔｔｙｐｉｃａｌｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓ
表７部分代表性聚类算法比较
尽ｍｄｃｓ．Ｈ啪ｇ１９９８Ｐａｒｔｉｔｉｏｎｃａｔｃｇｏｒｙ８皿１ｌ姐ｔｙ１ｓ咄ｉｔｉｖｃｓｐｈｅ佗Ｌａｒｇｅ，Ｄｅｓｍｂｅ．，１璐ｔｃｒ。ｍｃａｓｔｅ
‘ｃａｔｅｇｏｒｖｗｅｌｌ
竺！！兰竺：竺竺：竺竺量燮！璺当监』竺墨二．盏墨芝
Ｆ晒ｅａｔｍ＇ｅｃｌｕｗｓｔｅｒｅｉｇｈ咄ｔｅｄｃＥａｔｃｕｌｉｇｄ。ｅｒｙａｎｓｄｉｍｉｓｔｉａｌ撕ｎｃｔｙｅ，ｓ
∞
１
ｓ
１
１
“
－
２
０
０
６Ｐａｒｔｉｔｉｏｎ１ｉｖｅＳｐｈ唧ｓｍｌＩ，ｍｉ】【Ｆｅａｔ眦ｗｃｉｇｈｔｅｄ
。，．．ｃ砒ｃｇｏｒｙｓｉｍｉｌａｒｉｔｙ。。ｈｅｆｅＳｍａｌＩ，ｍｉ】【ＦｅａｔＩｌ∞ｗｃ
ｔｕ五万ｃｎｌｓｔｅＩ】ｎｇ
口ｍｅ。ａｓＩｌｒｅ
。Ｓ∞ｓｌｔｌＶｅ
５。竺哗。ｄａ诅２００７ＨｉｅｍｒｃｈｙＳ３Ｍ２一Ｓｅｑｕ姐ｃｃｄａｔａｈｇｅ．ｓｃａｌｅＤ掣ｃｔ。ｌｕｓｔｃｒｒｏｕ朗ｃＬ邺ｔｅｎｎｇ’。ｆｅａｔｕｒｅ
ｓｏｃ：。∞…哆Ｄ胁ｉｓｔａｎｉ∞ｃｅＮ叫ｓ盅，。Ａ妻≯茹ｇｈ－ａｎｄＭｏｓｔｓｐａｔｉｌｙｕｓｎｅｄｆｏｒ
‘（１ｌｍｃａｓｔｏｎ‘ＧＣＨＬ２００５ＧｒｉｄＥ～ｕｌｉｄｅａｎ２。Ｉｎ：．二－
唑１仃ａｒｙｏ竺ｉ∞ｊｉｇｈＩｎｆｏｍａｔｉｏｎ
ＡＣＯＤＦ２００４ＯｔｈｃｒｓＥ～ｕｌｉｄｅａｎ１一．．型璺８罂ｎ，ｈｉｇｈ‘Ｇｅｔｏｐ！掣Ⅷｕｃ
！！！竺！！：坚：型！坚！：！！！！！！！！！！罂！
文献【４】对１１种算法采用４个知名数据集进行实验．其中，４个数据集由２个类属性数据集和２个数值型数据集组成，由于对Ｋ－ｍｅａｎｓ和传统层次化算法采用了欧式距离作为相似性度量函数，所以针对２个类属性数据集所得到的测试结果不宜作为分析的依据．实验结果：对所选的２个数值型数据集，非层次化算法的分类结果优于层次化算法；对相同数据集，不同聚类算法产生了不同的聚类结果；对同～种算法、不同的数据集，其聚类的正确率不同．
本文对８种算法从ＵＣＩ中选择４个知名聚类分析基准数据集和１个不常用数据集分别进行２０次随机实验，并采用聚类正确率和运行时间作为衡量指标分别对数值型和类属性数据集进行实验；对Ｋ－ｍｅａｎｓ．ＣＰ算法，
６０ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．１９，Ｎｏ．１，Ｊａｎｕａｒｙ２００８
选数值型数据集Ⅸ取不同值进行实验；对Ｋ－ｍｅａｎｓ．ＣＰ算法，选择相同数据集，用不同相似性度量方式进行测试．实验结果：对不同数据集、同一算法，其聚类正确率不相同；对同一数据集、不同聚类算法，其聚类正确率和效率会有很大差异；将Ｋ－ｍｅａｎｓ算法与Ｋ－ｍｅａｎｓ．ＣＰ算法使用不同数值型数据集进行了比较实验，结果表明。Ｋ－ｍｅａｎｓ．ＣＰ算法丝毫也不优于Ｋ－ｍｅａｎｓ算法，ｋ最近邻一致性与聚类正确率无关，用ｋ最近邻一致性刻画聚类质量是不合适的；对同一算法和同一数据集，不同的相似性度量方式，其聚类结果也不相同．综合文献【４】和本文的实验得出的主要结论是：聚类算法的聚类结果有一定的不可预见性，在实际应用中应根据数据类型选择合适的聚类算法（和可恰当的相似性度量方式），以取得最佳的聚类效果．针对不同数据集，进一步开展聚类算法预测分类数的能力研究．一
致谢感谢刘大有教授对本文提纲和一些重点内容所给予的有益建议，感谢金弟同学对Ｋ－ｍｅａｎｓ－ＣＰ算法所做的编程和实验．
Ｒｅｆｅｒｅｎｃｅｓ：
【ｌ】ＪａｉｎＡＫ，ＦｌｙｎｎＰ１．Ｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎｕｓｉｎｇｃｌｕｓｔｅｒｉｎｇ．Ｉｎ：ＡｈｕｊａＮ，ＢｏｗｙｃｒＩ【’ｅｄｓ．ＡｄｖａｎｃｅｓｉｎＩｍａｇｅＵｎｄｅｒｓｔａｎｄｉｎｇ：ＡＦｅｓｔｃｈｒｉｆｉｆｏｒＡｚｒｉｅｌＲｏｓｅｎｆｅｌｄ．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥＰｒｅｓｓ，１９９６．６５—８３．
【２】ＣａｄｅｓＩ，ＳｍｙｔｈＰ，ＭａｎｎｉｌａＨ．Ｐｒｏｂａｂｉｌｉｓｔｉｃｍｏｄｅｌｉｎｇｏｆｔｒａｎｓａｃｔｉｏｎａｌｄａｔａｗｉｔｈａｐｐｌｉｃａｔｉｏｎｓｔｏｐｒｏｆｉｌｉｎｇ，ｖｉｓｕａｌｉｚａｔｉｏｎａｎｄｐｒｃｄｉｃｔｉ衄，ｓｉｇｍｏｄ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅ７ｔｈＡＣＭＳＩＧＫＤＤ．ＳａｎＦｒａｎｃｉｓｃｏ：ＡＣＭＰｒｅｓｓ，２００１．３７．４６．ｈｔｔｐ：／／ｗｗｗ．ｓｉｇｋｄｄ．ｏｒｇ／ｋｄｄ２００１／【３】ＪａｉｎＡｌ（’ＭｕｒｔｙＭＮ，ＦｌｙｎｎＰＪ．Ｄａｔａｃｌｕｓｔｅｒｉｎｇ：Ａｒｅｖｉｅｗ．ＡＣＭＣｏｍｐｕｔｉｎｇＳｕｒｖｅｙｓ，１９９９，３１（３）：２６４－３２３．。
【４】ＧｅｌｂａｒｄＲ，ＧｏｌｄｍａｎＯ，ＳｐｉｅｇｌｃｒＩ．Ｉｎｖｅｓｔｉｇａｔｉｎｇｄｉｖｅｒｓｉｔｙｏｆｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｓ：Ａｎｅｍｐｉｒｉｃａｌｃｏｍｐａｒｉｓｏｎ．Ｄａｔａ＆ＫｎｏｗｌｅｄｇｅＥｎｇｉｎｅｅｒｉｎｇ，２００７，６３（１）：１５５－１６６．
［５１ＪａｉｎＡＫＤｕｂｅｓＲＣ．ＡｌｇｏｒｉｔｈｍｓｆｏｒＣｌｕｓｔｅｒｉｎｇＤａｔａ．Ｐｒｅｎｔｉｃｅ—ＨａｌｌＡｄｖａｎｃｅｄＲｅｆｅｒｅｎｃｅＳｅｒｉｅｓ。１９８８．１－３３４．
【６】ＪａｉｎＡＫ，ＤｕｉｎＲＰＷ，ＭａｏＪＣ．Ｓｔａｔｉｓｔｉｃａｌｐａｔｔｅｒｎｒｅｃｏｇｎｉｔｉｏｎ：Ａｒｅｄｅｗ．ＩＥＥＥＴｒａｎｓ．ｏｎＰａｔｔｅｒｎＡｎａｌｙｓｉｓａｎｄＭａｃｈｉｎｅＩｎｔｅｌｌｉｇｅｎｃｅ，２０００，２２（１）：４－３７．
【７】ＳａｍｂａｓｉｖａｍＳ，ＴｈｅｏｄｏｓｏｐｏｕｌｏｓＮ．Ａｄｖａｎｃｅｄｄａｔａｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｓｏｆｍｉｎｉｎｇｗｃｂｄｏｃｕｍｅｎｔｓ．ＩＳＳＵＥＳｉｎＩｎｆｏｒｍｉｎｇＳｃｉｅｎｃｅａｎｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ，２００６，（３）：５６３—５７９．
【８】ＭａｒｑｕｅｓＪＰ，Ｗｒｉｔｔｅｎ；ＷｕＹＦ，Ｔｒａｎｓ．ＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎＣｏｎｃｅｐｔｓ，ＭｅｔｈｏｄｓａｎｄＡｐｐｌｉｃａｔｉｏｎｓ．２ｎｄｅｄ．，Ｂｅｉｊｉｎｇ：ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ，２００２．５１－７４（ｉｎＣｈｉｎｅｓｅ）．
【９】ＦｒｅｄＡＬＮ，ＬｅｉｔａｏＹＭＮ．ＰａｒｔｉｔｉｏｎａｌＶＳｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇｕｓｉｎｇａｍｉｎｉｍｕｍｇｒａｍｍａｒｃｏｍｐｌｅｘｉｔｙａｐｐｒｏａｃｈ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＳＳＰＲ＆ＳＰＲ２０００．ＬＮＣＳ１８７６．２０００．１９３－２０２．ｈｔｔｐ：／／ｗｗｗ．ｓｉｇｍｏｄ．ｏｒｇ／ｄｂｌｐ／ｄｂ／ｃｏｎｆ／ｓｓｐｒ／ｓｓｐｒ２０００．ｈｔｍｌ
【１０】ＧｅｌｂａｒｄＲ，ＳｐｉｅｇｌｅｒＩ．Ｈｅｍｐｅｌ’Ｓｒａｖｅｎｐａｒａｄｏｘ：Ａｐｏｓｉｔｉｖｅａｐｐｒｏａｃｈｔｏｃｌｕｓｔｅｒａｎａｌｙｓｉｓ．ＣｏｍｐｕｔｅｒｓａｎｄＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ，２０００，２７（４）：３０５—３２０．
【ｌｌ】ＺｈａｎｇＢ，ＳｒｉｈａｒｉＳＮ．Ｐｒｏｐｅｒｔｉｅｓｏｆｂｉｎａｒｙｖｅｃｔｏｒｄｉｓｓｉｍｉｌａｒｉｔｙｍｅａｓｕｒｅｓ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＪＣＩＳＣＶＰＲＩＰ２００３．２００３．２６－３０．ｈｔｔｐ：／／ｗｗｗ．ｅｅ．ｄｕｋｅ．ｅｄｕ／ＪＣＩＳ／
【１２】ＫｕｍａｒＰ，ＫｒｉｓｈｎａＰＲ，ＢａｐｉＲＳ，ＤｅＳＫ．Ｒｏｕｇｈｃｌｕｓｔｅｒｉｎｇｏｆｓｅｑｕｅｎｔｉａｌｄａｔａ．Ｄａｔａ＆ＫｎｏｗｌｅｄｇｅＥｎｇｉｎｅｅｒｉｎｇ，２００７，３（２）：１８３－１９９．【１３】ＨｕａｎｇＺ．Ａｆａｓｔｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｔｏｃｌｕｓｔｅｒｖｅｒｙｌａｒｇｅｃａｔｅｇｏｒｉｃａｌｄａｔａｓｅｔｓｉｎｄａｔａｍｉｎｉｎｇ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＳＩＧＭＯＤＷｏｒｋｓｈｏｐ
ｏｎＲｅｓｅａｒｃｈＩｓｓｕｅｓｏｎＤａｔａＭｉｎｉｎｇａｎｄＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙ．Ｔｕｃｓｏｎ，１９９７．１４６－１５１．ｈｔｔｐ：／／ｗｗｗ．ｉｎｆｏｒｍａｔｉｋ．ｕｎｉ—ｔｒｉｅｒ．ｄｅ／一ｌｅｙ／ｄｂ／ｃｏｎｆ／ｓｉｇｍｏｄ／ｓｉｇｍｏｄ９７．ｈｔｍｌ
［１４１Ｈｕａｎｇｚ．Ｅｘｔｅｎｓｉｏｎｓｔｏｔｈｅｋ－ｍｅｅｎｓａｌｇｏｒｉｔｈｍｆｏｒｃｌｕｓｔｅｒｉｎｇｌａｒｇｅｄａｔａｓｅｔｓｗｉｔｈｃａｔｅｇｏｒｉｃａｌｖａｌｕｅｓ．ＤａｔａＭｉｎｉｎｇａｎｄＫｎｏｗｌｅｄｇｅ，ＤｉｓｃｏｖｅｒｙＩＩ，１９９８，（２）：２８３－３０４．
【１５】ＨｕａｎｇＺ，ＮｇＭＡ．Ｆｕｚｚｙｋ－ｍｏｄｅｓａｌｇｏｒｉｔｈｍｆｏｒｃｌｕｓｔｅｒｉｎｇｃａｔｅｇｏｒｉｃａｌｄａｔａ．［ＥＥＥＴｒａｎｓ．ｏｎＦｕｚｚｙＳｙｓｔｅｍｓ，１９９９，７（４）：４４６－４５２．．［１６１ＣｈａｔｕｒｖｃｄｉＡＤ，ＧｒｅｅｎＰＥ，ＣａｒｒｏｌｌＪＤ．Ｋ－ｍｏｄｅｓｃｌｕｓｔｅｒｉｎｇ．ＪｏｕｒｎａｌｏｆＣｌａｓｓｉｆｉｃａｔｉｏｎ，２００１，１８（１）：３５—５６．
【１７】ＧｏｏｄｍａｎＬＡ．Ｅｘｐｌｏｒａｔｏｒｙｌａｔｅｎｔｓｔｒｕｃｔｕｒｅａｎａｌｙｓｉｓｕｓｉｎｇｂｏｔｈｉｄｅｎｔｉｆｉａｂｌｅａｎｄｕｎｉｄｅｎｔｉｆｉａｂｌｅｍｏｄｅｌｓ．Ｂｉｏｍｅｔｒｉｋａ，１９７４，６１（２）：。２１５－２３１．
【１８】ＨｕｚｎｇＺＸ，ＭｉｃｈａｅｌＫ．ＡｎｏｔｅｏｎＫ－ｍｏｄｅｓｃｌｕｓｔｅｒｉｎｇ．ＪｏｕｒｎａｌｏｆＣｌａｓｓｉｆｉｃａｔｉｏｎ，２００３，２０（２）：２５７－２６．
【１９】ＳｕｎＹ，ＺｈｕＱＭ，Ｃｈｅｎｚｘ．Ａｎｉｔｅｒａｔｉｖｅｉｎｉｔｉａｌ—ｐｏｉｎｔｓｒｅｆｉｎｅｍｅｎｔａｌｇｏｒｉｔｈｍｆｏｒｃａｔｅｇｏｒｉｃａｌｄａｔａｃｌｕｓｔｅｒｉｎｇ．ＰａＲｅｒｎＲｅｃｏｇｎｉｔｉｏｎＬｅｔｔｅｒｓ，２００２，２３（７）：８７５—８８４．
【２０】ＢｒａｄｌｅｙＰＳ，ＦａｙｙａｄＵＭ．Ｒｅｆｉｎｉｎｇｉｎｉｔｉａｌｐｏｉｎｔｓｆｏｒｋ－ｍｅａｎｓｃｌｕｓｔｅｒｉｎｇ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅ１５ｔｈＩｎｔｅｒｎｅｔＣｏｎｆ．ｏｎＭａｃｈｉｎｅＬｅａｒｎｉｎｇ．ＳａｎＦｒａｎｃｉｓｃｏ：ＭｏｒｇａｎＫａｕｆｍａｎｎＰｕｂｌｉｓｈｅｒｓ。１９９８．９１－９９．ｈｔｔｐ：／／ｗｗｗ．ｃｓ．ｗｉｓｅ．ｅｄｕ／ｉｃｍｌ９８／
孙吉贵等：聚类算法研究
【２１】
［２２１
【２３１
【２４】
【２５】
【２６】
【２７】
【２８】
［２９】
【３０】
【３１】
【３２】
【３３】
【３４】
【３５】
【３６】
【３７】６ｌ
ｈｔｔｐ：／／ｗｗｗ．ｉｃｓ．ｕｃｉ．ｅｄ“‘忸ｌｅａｒ州ｄａｔａｂａｓｃｓ／
ＤｉｎｇＣ，ＨｅＸ．Ｋ－Ｎｅａｒｅｓｔ－Ｎｅｉ【ｇｈｂｏｒｉｎｄａｔａｃｌｕｓｔｅｒｉｎｇ：Ｉｎｃｏｒｐｏｒａｔｉｎｇｌｏｃａｌｉｎｆｏｒｍａｔｉｏｎｉｎｔｏｇｌｏｂａｌｏｐｔｉｍｉｚａｔｉｏｎ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＡＣＭＳｙｍｐ．ｏｎＡｐｐｌｉｅｄＣｏｍｐｕｔｉｎｇ．Ｎｉｃｏｓｉａ：ＡＣＭＰｒｅｓｓ．２００４．５８４—５８９．ｈｔｔｐ：ｌｌｗｗｗ．ａ锄．ｏｒｓ／ｃｏｎｆｅｒｅｎｃｅｓ／ｓａｃ／ｓａｃ２００４／
ＬｙｅｒＮＳ，ＫａｎｄｅｌＡ，ＳｃｈｎｅｉｄｅｒＭ．Ｆｅａｔｕｒｅ－Ｂａｓｅｄｆｕｚｚｙｃｌａｓｓｉｆｉｃａｔｉｏｎｆｏｒｉｎｔｅｒｐｒｃｔａｔｉｏｎｏｆｍａｍｍｏｇｒａｍｓ．ＦｕｚｚｙＳｅｔｓＳｙｓｔｅｍ，２０００，１１４（２）：２７１－２８０．
ＹａｎｇＭＳ。ＨｕＹＪ。ＬｉｎＫＣＲ’ＬｉｎＣＣＬ．ＳｅｇｍｅｎｔｔａｔｉｏｎｔｅｃｈｎｉｑｕｅｓｆｏｒｔｉｓｓｕｅｄｉｆｆｅｒｅｎｔｉａｔｉｏｎｉｎＭＲＩｏｆｏｐｈｔｈａｌｍｏｌｏｇｙｕｓｉｎｇｆｕｚｚｙｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ．ＪｏｕｒｎａｌｏｆＭａｇｎｅｔｉｃＲｅｓｏｎａｎｃｅＩｍａｇｉｎｇ，２００２，（２０）：１７３—１７９．
ＬｉＪ，ＧａｏＸＢ，ＪｉａｏＬＣ．Ａｎｅｗｆｅａｔｕｒｅｗｅｉｇｈｔｅｄｆｕｚｚｙｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ．ＡＣＴＡＥｌｅｃｔｒｏｎｉｃａＳｉｎｉｃａ，２００６，３４（１）：４１２－４２０（ｉｎＣｈｉｎｅｓｅｗｉｔｈＥｎｇｌｉｓｈａｂｓｔｒａｃｔ）．
Ｋｏｎｏｎｅｎｋｏ
Ｉ．Ｅｓｔｉｍａｔｉｎｇａｔｔｒｉｂｕｔｅｓ：Ａｎａｌｙｓｉｓａｎｄｅｘｔｅｎｓｉｏｎｓｏｆｒｅｌｉｅｆ．Ｉｎ：Ｐｒｏｃ，ｏｆｔｈｅ１７ｔｈＥｕｒｏｐｅａｎＣｏｎｆ．ＯｎＭａｃｈｉｎｅＬｅａｒｎｉｎｇ．ＬＮＣＳ７８４。１９９４．１７１－１８２．
ＣａｉＷＬ，ＣｈｅｎＳＣ，ＺｈａｎｇＤＱ．Ｆａｓｔａｎｄｒｏｂｕｓｔｆｕｚｚｙｃ?ｍｅａｌ坞ｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｓｉｎｃｏｒｐｏｒａｔｉｎｇｌｏｃａｌｉｎｆｏｒｍａｔｉｏｎｆｏｒｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎ．ＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ，２００７，４０（３）：８２５—８３３．
ＨａｒｅｌＤ。ＫｏｒｅｎＹ．Ｃｌｕｓｔｅｒｉｎｇｓｐａｔｉａｌｄａｔａｕｓｉｎｇｒａｎｄｏｍｗａｌｋｓ．ｈａ：Ｐｒｏｃ．ｏｆｔｈｅ７ｔｈＡＣＭＳＩＧＫＤＤＩｎｔ’１Ｃｏｎｆ．ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙａｎｄＤａｔａＭｉｎｉｎｇ．ＮｅｗＹｏｒｋ：ＡＣＭＰｒｅｓｓ，２００１．２８１－２８６．ｈｔｔｐ：／／ｗｗｗ．ｓｉｇｋｄｄ．ｏｒｇ／ｋｄｄ２００１／
ＫａｒｙｐｉｓＧ，ＨａｎＥＨ，ＫｕｍａｒＶ．ＣＨＡＮＥＬＥＯＮ：Ａｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｕｓｉｎｇｄｙｎａｍｉｃｍｏｄｅｌｉｎｇ．ＩＥＥＥＣｏｍｐｕｔｅｒ，１９９９，２（８）：６８—７５．
Ｅｓｔｉｖｉｌｌ－ＣａｓｔｒｏＶ，ＬｅｅＩ．ＡＵＴＯＣＬＵＳＴ：Ａｕｔｏｍａｔｉｃｃｌｕｓｔｅｒｉｎｇｖｉａｂｏｕｎ血ｒｙｅｘｔｒａｃｔｉｏｎｆｏｒｍｉｎｉｎｇｍａｓｓｉｖｅｐｏｉｎｔ－ｄａｔａｓｅｔｓ．Ｉｎ：ＡｂｒａｈａｒｔＪ，ＣａｒｌｉｓｌｅＢＨ。ｅｄｓ．Ｐｒｏｃ．ｏｆｔｈｅ５ｔｈＩｎｔ’ｌＣｏｎｆ．ｏｎＧｅｏｃｏｍｐｕｔａｔｉｏｎ．２０００．２３－２５．ｈｔｔｐ：／／ｗｗｗ．ｇｅｏｃｏｍｐｕｔａｔｉｏｎ．ｏｒｓ／２０００／ｉｎｄｅｘ．ｈｔｍｌ
“Ⅵ．Ａｃｌｕｓｔｅｒｉｎｇ
ａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｍａｘｉｍａｌＯ－ｄｉｓｔａｎｔｓｕｂｔｒｅｅｓ．ＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ，２００７，４０（５）：１４２５—１４３１．ＺｈａｏＹＣ，ＳｏｎｇＪ．ＧＤＩＬＣ：Ａｇｒｉｄ－ｂａｓｅｄｄｅｎｓｉｔｙｉｓｏｌｉｎｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ．ｈａ：ＺｈｏｎｇＹ）（’ＣｕｉＳ，ＹａｎｇＹ，ｅｄｓ．Ｐｒｏｃ．ｏｆｔｈｅＩｎｔｅｍｅｔＣｏｎ￡ｏｎＩｎｆｏ－Ｎｃｔ．Ｂｅｉｊｉｎｇ：ＩＥＥＥＰｒｅｓｓ，２００１．１４０－１４５．ｈｔｔｐ：Ｈｉｅｅｅｘｐｌｏｒｅ．ｉｅｅｅ．ｏｒｇ／ｉｅｌ５／７７１９／２１１６Ｉ／００９８２７０９．ｐｄｆ?
ＭａｗＭ，ＣｈｏｗＥ，ＴｏｍｍｙＷＳ．Ａｎｅｗｓｈｉｆｔｉｎｇｇｒｉｄｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ．ＰａＵｅｍＲｅｃｏｇｎｉｔｉｏｎ，２００４，３７（３）：５０３－５１４．
ＰｉｌｅｖａｒＡＨ，ＳｕｋｕｍａｒＭ．ＧＣＨＬ：Ａｇｒｉｄ－ｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｆｏｒｈｉｇｈ?ｄｉｍｅｎｓｉｏｎａｌｖｅｒｙｌａｒｇｅｓｐａｔｉａｌｄａｔａｂａｓｅｓ．ＰａｔｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎＬｅｔｔｅｒｓ，２００５，２６（７）：９９９—１０１０．
ＮａｎｎｉＭ，ＰｅｄｒｅｓｃｈｉＤ．Ｔｉｍｅ－Ｆｏｃｕｓｅｄｃｌｕｓｔｅｒｉｎｇｏｆｔｒａｊｅｃｔｏｒｉｅｓｏｆｍｏｖｉｎｇｏｂｊｅｃｔｓ．ＪｏｕｒｎａｌｏｆＩｎｔｅｌｌｉｇｅｎｔＩｎｆｏｒｍａｔｉｏｎＳｙｓｔｅｍｓ，２００６，２７（３）：２６７—２８９．
ＢｉｒａｎｔＤ，ＫｕｔＡ．ＳＴ?ＤＢＳＣＡＮ：Ａｎａｌｇｏｒｉｔｈｍｆｏｒｃｌｕｓｔｅｒｉｎｇｓｐａｔｉａｌ－ｔｅｍｐｏｒａｌｄａｔａ．Ｄａｔａ＆ＫｎｏｗｌｅｄｇｅＥｎｇｉｎｅｅｒｉｎｇ，２００７，６０（１）：２０８—２２１．
ＴｓａｉＣＦ，ＴｓａｉＣＷ，ＷｕＨＣ，ＹａｎｇＴ．ＡＣＯＤＦ：Ａｎｏｖｅｌｄａｔａｃｌｕｓｔｅｒｉｎｇａｐｐｒｏａｃｈｆｏｒｄａｔａｍｉｎｉｎｇｉｎｌａｒｇｅｄａｔａｂａｓｅｓ．ＪｏｕｒｎａｌｏｆＳｙｓｔｅｍｓａｎｄＳｏｆｔｗａｒｅ，２００４，７３（１）：１３３—１４５．
附中文参考文献：
【８】ＭａｒｑｕｅｓＪＰ，著；吴逸飞，译．模式识别——原理、方法及应用．ｊＢ京：清华大学出版社。２００２．５１—７４
【２５】李洁，高新波，焦李成．基于特征加权的模糊聚类新算法．电子学报，２００６，３４（１）：４１２－４２０．
孙吉贵（１９６２一），男，辽宁庄河人，博士，教授，博士生导师，ＣＣＦ高级会员。主要研究领域为人工智能，约束规划，决策支持系统．
刘杰（１９７３一），女，博士生，讲师，主要研究领域为数据挖掘。模式识别．糌ｊｅ（１９８４－－），男，硕士生，主要研究领域
为数据挖掘．