聚类算法综述

1、聚类算法综述姓名： 谢天娇 学校： 北京邮电大学 学院: 计算机学院 2014 年 5 月 30 日摘要聚类算法又称群集分析，常用于将大量数据按照一定规则分为不同类别，其与分类算法的差异在于，聚类算法可在非监督模式下处理数据，不需要人为输入数据标签。聚类算法发展至今约有六十余年，其非监督的特性在如今的大数据时代显示出更大的优势，而与之相应很多学者也致力于研究针对海量数据且精确度更高，语义更明确的聚类算法。笔者在文中从算法分类的角度简述不同种类聚类算法的基础和发展现状。然后就当前使用范围较广的层次法，划分法，密度法，谱聚类各选出一个较为代表性的算法简要分析其算法结构和性能。最后，笔者给出一种谱聚

2、类的matlab实现实例及实验结果。正文一、引言聚类分析最早起源于分类学，初时人们依靠经验一类事件的集合分为若干子集。随着科技的发展，人们将数学工具引入分类学，聚类算法便被细化归入数值分类学领域。后来，信息技术快速发展，新数据的出现呈井喷趋势，其结构的复杂性和内容的多元化尤为聚类提出了新的要求，于是多元分析技术被引入数值分析学，形成了聚类分析学。聚类分析，在英文中是Cluster analysis，又译为群集分析。其作用，简单而言即是非监督式的将大量数据以相似度为基础形成集合。非监督式，即是聚类分析与分类和回归分析的区别所在，聚类不需要人为的输入标签，尽管某些聚类算法需要设定初始划分方法或者根

3、据输入参数确定聚类集合个数，但在分析过程中，算法无须人为输入分类标准。因此，聚类分析在很多时候用于大型数据库的分类预处理，当然聚类分析也常作为独立分析数据的工具。而不同的关于相似度的判断，就形成了不同的聚类算法。聚类算法的分类有很多，从时间上可以分为传统聚类算法和现代聚类算法；从子集元素可以分为软聚类和硬聚类；从对初始状态的处理可以分为结构性聚类和分散性聚类，基于其他标准亦有其他的分类方法，在本文第二节将会给出详细介绍和分析。聚类分析具有广泛的应用领域。对于网络流量的监控和数据挖掘，可以实现舆情分析，获知前所未有的又出现的热点事件。在商业上，市场消费数据的聚类，可以使企业相关人员获知新的消费趋

4、势和市场需求。而在城市规划领域，对于地形地貌或者人口分布的聚类，可以帮助市政规划人员更好的进行城市分区和建设。不同的应用领域，需要聚类的数据差异很大，对于聚类结果也有不同的要求，选择合适的聚类算法才能得到最满意的聚类结果。二、聚类算法分类及国内外发展现状根据中国知网的搜索结果显示，可搜到的最早关于聚类的外国文献出版于1957年，中文文献则是1975年方开泰教授发表于期刊数学的实践与认识上的聚类分析系列文章 方开泰. 聚类分析J. 数学的实践与认识, 1975, （一）(01期):66-78.。聚类分析的实现步骤大致为特征选择，计算相似度，选择聚类算法，验证判定结果。每一步中选择不同的方法，便是

5、区分聚类算法的原则之一。目前的聚类算法有很多种，考虑到数据类型，相似度计算公式以计算法结构，各种算法已有很多交集。本文中，笔者参考网络文献聚类算法综述 binma85. 聚类算法综述D/OL. 2009-3-212014-5-24. /s/blog_4c2cb83f0100ct0l.html.中该作者的分类方法，将聚类算法按其发展进程大致分为传统聚类算法和现代聚类算法，在此基础上在按其技术细节细分。1. 传统聚类算法传统聚类算法多数属于硬聚类，每个元素只能属于一个集合，在元素特征模糊时聚类结果将受到影响。此外，一些传统聚类算法需要输入子集数量的初始值

6、，这使得在处理大数据时聚类效果不佳。但传统聚类是现代聚类发展的理论基础和实践先驱，因此对于传统聚类的介绍和理解具有重要意义。(1) 层次法 层次法的指导思想是对给定待聚类数据集合进行层次化分解。此算法又称为数据类算法，此算法根据一定的链接规则将数据以层次架构分裂或聚合，最终形成聚类结果。从算法的选择上看，层次聚类分为自顶而下的分裂聚类和自下而上的聚合聚类。分裂聚类初始将所有待聚类项看成同一类，然后找出其中与该类中其他项最不相似的类分裂出去形成两类。如此反复执行直到所有项自成一类。聚合聚类初始将所有待聚类项都视为独立的一类，通过联接规则，包括单链接、全连接、类间平均连接，以及采用欧氏距离作为相似

7、度计算的算法，将相似度最高的两个类合并成一个类。如此反复执行直到所有项并入同一个类。BIRCH算法 Zhang, Tian, Raghu Ramakrishnan, and Miron Livny. BIRCH: an efficient data clustering method for very large databases.JACM SIGMOD Record. Vol. 25. No. 2. ACM, 1996.是层次算法中的典型代表算法，其核心是CF（Cluster Feature）和CF树。CF是一个存储了聚类信息的三元组，其中包含了N（待聚类项个数），LS（N个数据点的线性和

8、），SS（N个数据点的平方和）。LS和SS分别反映了聚类的质心和聚类的直径大小。CF树有两个参数：分支因子和阈值T。分支因子包括非叶节点CF条目的最大个数和叶节点CF条目的最大个数。这里叶节点看作聚合而成的一个簇。阈值T限定了所有条目的最大半径或直径。BIRCH算法主要有四个阶段。第一阶段扫描待聚类的所有数据项，根据初始阈值T初始化一颗CF树。第二阶段采用聚合思路，通过增加阈值T重建CF树，使其聚合度上升。第三、四阶段，对已有的CF树实行全局聚类以得到更好的聚类效果。然而BIRCH算法并未给出详细的设定初始阈值T的方法，只是简单地赋值T=0，在第二阶段中，BIRCH算法也并未给出增加T值的规则

9、。这也正是近年来学者对于改进BIRCH算法的一个方向。蒋盛益教授在他的一种改进的BIRCH聚类算法 蒋盛益, 李霞. 一种改进的BIRCH聚类算法 J. 计算机应用, 2009, 29(1):293-296.中说明，基于T的定义可知，其值与组内平均距离和组件平均距离，及数据的分布有关。因此，初始阈值T，可以采用如下公式计算得出。在数据集中随机选取N对数据，计算每对数据间的距离di，计算N对数据间距离的数学期望Ex和方差Dx。初始化CF树的T值为，T=P*（Ex+0.25*Dx）。P为事先设定的百分比。在算法第二阶段，T的提升规则这是增大公式中的P值。这一算法的改进提升了原本算法的平均聚类精度和

10、聚类效率，改进了BIRCH算法的性能。(2) 划分法划分法属于硬聚类，指导思想是将给定的数据集初始分裂为K个簇，每个簇至少包含一条数据记录，然后通过反复迭代至每个簇不再改变即得出聚类结果。划分聚类在初始的一步中即将数据分成给定个数个簇。在算法过程中还需使用准则函数对划分结果进行判断，易产生最有聚类结果。K-Means算法 Hamerly G, Elkan C. Alternatives to the k-means algorithm that find better clusteringsJ. ACM, 2002(11):600-607，中文译为K均值算法。这种算法通过迭代不断移动个聚簇中心

11、和簇类成员，直到得到理想的结果。通过K均值算法得到的聚簇结果，簇内项相似度很高，簇间项相似度很低，具有较好的局部最优特性，但并非是全局最优解。此外，K均值只能定义在数值类属性值上，无法处理其他类型的数据。针对于无法产生全局最优解问题，算法的研究者们一部分倾向于通过优化初始簇的选择算法和均值计算改善算法性能，另一部分则允许簇分裂与合并，来调整簇间关系。K-Harmonic Means（K调和均值）算法 Zhang, B., “Generalized K-Harmonic Means Dynamic Weighting of Data in Unsupervised Learning,”, the

12、 First SIAM International Conference on Data Mining (SDM2001), Chicago, USA, April 57, (2001)是建立在中心基础上的迭代算法。其评价函数为所有点到所有中心的均方距离的调和平均值函数。P个数，a1,a2,ap的调和平均值定义为HA=P/(i=1P1ai)。这样的评价函数，通过对于项的分布给不同项赋值不同权重，可以将过于集中的中心点移到数据附近没有中心点的区域上。这种算法降低了对初始点选取的依赖，提高了算法的鲁棒性。在数据挖掘中集中划分聚类算法的比较及改进 彭丽. 数据挖掘中集中划分聚类算法的比较及改进D.

13、大连理工大学, 2008年.中，该文章作者通过使用一种新的距离度量应用于K调和均值算法中，进一步改进了该算法的聚类效果。通常而言，算法中关于距离的度量都采用欧氏距离。这篇文章中，作者介绍了新的度量函数d(x,y)=1-exp(-x-y2)，其中是一个正的常数，其值的大小决定了聚簇疏密。新的度量方式改变了K调和均值的目标函数公式和中心更新公式。通过Wine等三个聚类数据集的验证，采用新距离度量方法的K调和均值算法，从运行时间、迭代次数和结果精度方面都有所提高。(3) 基于密度的方法上文中提到的两类算法，其聚类的划分都以距离为基础，容易产生类圆形的凸聚类。而密度算法很好的克服了这一缺点。密度算法的

14、指导思想是将空间中密度大于某一阈值的点加入到一个聚类中。DBSCAN算法 荣秋生, 颜君彪, 郭国强. 基于DBSCAN聚类算法的研究与实现J. 计算机应用, 2004, 24(4):45-46.是基于密度聚类的经典算法。它将簇定义为密度相连的点的最大集合，将足够高密度的区域划分为簇。这样的算法对噪声具有健壮性，并且可以发现任意形状的聚簇。DBSCAN的基本算法流程为，从任意对象P开始根据阈值和参数通过广度优先搜索提取从P密度可达的所有对象，得到一个聚类。若P是核心对象，则可以一次标记相应对象为当前类并以此为基础进行扩展。得到一个完整的聚类后，在选择一个新的对象重复上述过程。若P是边界对象，则

15、将其标记为噪声并舍弃。尽管DBSCAN算法改进完善了上述两种算法的一些缺陷，但此算法也存在不足。如聚类的结果与参数关系较大，阈值过大容易将同一聚类分割，阈值过小容易将不同聚类合并。此外固定的阈值参数对于稀疏程度不同的数据不具适应性，密度小的区域同一聚类易被分割，密度大的区域不同聚类易被合并。针对DBSCAN算法在聚类时未考虑非空间属性，以及处理大量数据的内存消耗。文献 胡彩平, 秦小麟. 一种改进的基于密度的抽样聚类算法J. 中国图像图形学报, 2007, 12(11):2031-2036.中提出了基于密度的抽样聚类IDBSCAS算法，此算法通过核心对象和边界对象选取适当位置和数量的种子对象，

16、使算法能够有效的处理大规模空间数据库并且同时考虑了数据的非空间因素。针对DBSCAN理大量数据的内存消耗和对分布不均数据处理的不适应，文献 周水庚, 周傲英, 曹晶. 基于数据区分的DBSCAN算法J. 计算机研究与发展, 2000, 37(10):1153-1159.给出了一种解决方案。将数据在主要但分布稀疏程度不均的维度上将数据空间划分为若干区域，分别计算各个区域的聚类密度阈值，以此进行聚类合并，最后再进行全局聚类合并。(4) 基于网格的方法基于网格的方法，通过采用一个多分辨率的网格数据结构，近数据空间划分为有限个单元，之后所有的处理都是以单个单元为对象的。这样的处理使得算法处理速度很快，

17、处理工作量与数据项个数无关，而与划分的网格个数有关。STING算法 Wang W,Yang J,Muntz R.STING:A Statistical Information Grid Approach to Spatial Data MiningC In:Proceedings of the 23rd VLDB Conference.Athens,Greece:s.n.,1997:186-195.是传统的基于网格的算法，它将空间区域划分为矩形单元后处理。WaveCluster算法 Sheikholeslami G,Chatterjee S,Zhang A.WaveCluster:A Mult

18、i-Resolution ClusteringApproach forVery Large Spatial DatabasesC In:Proceedings of the 24th VLDB Conference.New York,USA:s.n.,1998:428-439.先在空间上加一多维网格结构汇总数据，然后采用小波变换变换元特征空间，在再变换后的空间中寻找密集区域。2. 现代聚类算法随着科学技术的发展以及待处理数据的多元化和数据洪流的出现。传统聚类算法尽管不断自我完善和改进，但一些基于新的思想或利润的聚类算法亦不断出现。 (1) 模糊聚类1969年，数据集模糊划分 Ruspini H

19、E. A new approach to clustering. Inf Cont., 1969, 15: 2228.的概念被Ruspini首先提出，并首次系统探究了关于模糊聚类的算法，其后的一些学者也相继提出了基于模糊关系的聚类算法。但由于当数据集较大时，基于模糊关系的聚类算法需要先建立模糊等价矩阵，计算量非常大，这类方法也就逐渐减少研究了。与此同时，借助于图论、动态规划、进化算法、马尔科夫随机场等技术，学者们提出了许多其他的模糊聚类算法，其中应用最为广泛的是基于目标函数的聚类方法。该方法设计简单，应用范围广，本质来说可归结为较为简单的优化问题。模糊C均值（FCM）算法是基于木变函数的模糊聚

20、类算法的典型代表。自Dumn于1974年发表后，便被人们不断完善发展。FCM算法最早是从硬聚类目标函数的优化中导出的，通过将项与对应簇的中心点距离用隶属平方加权，将类内误差平方和目标函数改写为类内加权误差平方和目标函数，得到了关于给予目标函数模糊聚类的一种大致描述。由于FCM算法的实用性和数据处理效果，对于此算法的研究有着蓬勃的发展，目前已经形成了庞大的体系。对于FCM的算法研究和改进大致有如下方面：基于目标函数的研究，不同数据类型的聚类，隶属度约束条件的研究、算法实现等。基于目标函数的研究中，2011年，Tsai在文献 Tsai Du-Ming, Lin Chung-Chan. Fuzzy

21、C-means based clustering for linearly and nonlinearly separable data. Pattern Recognition, 2011, 44: 17501760.提出了一种包含距离变量的新居里准则，在FCM算法和KFCM算法中尝试应用并得到了较好的效果。当数据并非球体分布式，通过核函数改造目标函数中的距离测度成为了一种解决方案。2010年，Gravest和Pedrycz提出了一种综合比较分析的模糊核聚类算法，在一定程度上解决了非球体分布数据的聚类问题。但核函数的选择构造及参数设定又是一个新的难题。(2) 量子聚类随着量子力学理论在实践方

22、面的发展，量子计算在物理方面的实现极大地推动了量子计算理论与量子算法的创新。2002年，David Home将量子机制与聚类算法结合，通过将数据映射到量子空间，构建波函数，测量势能方程来获取最终的聚类中心，提出了一种量子聚类算法 David Horn; Assaf Gottlieb. The Method of Quantum ClusteringJ, Advances in Neural Information Processing Systems,2001:769-776.。2010年曾成、徐红等人在文献 曾成,赵锡均,徐红.基于量子遗传算法的聚类方法C.Proceedings of th

23、e 29th Chinese Control Conference July 29-31,201O Beijing,China.采用量子遗传算法，将聚类问题转化为聚类中心学有问题，提出了一种基于量子遗传算法的聚类方法。(3) 谱聚类谱聚类 Jain A,Murty M,Flynn P.Data clustering:A ReviewJ. ACM Computing Surveys,1999,31(3):264-323是聚类分析中一个新兴且具有生命力的分支，是近年来国际上机器学习数据挖掘领域的一个新的研究热点。谱聚类建立在谱图理论基础上，克服了传统聚类中对于样本空间形状的局限，以及可能陷入局部最

24、优而非全局最优的问题。谱聚类算法本质上是将聚类问题转化为图的最优划分问题，属于对点聚类算法。但由于以谱图理论为基础，要实现谱聚类需要一定的图论方面的理论知识基础。其中主要包括三个方面：一、图划分准则：包括最小割集准则、规范割集准则、比例割集准则、平均割集准则、最小最大割集准则、多路规范割集准则。二、相似矩阵、度矩阵及Laplacian矩阵。 三、势函数、Fiedler向量及谱。谱聚类算法大致分为三个阶段。阶段一，构建矩阵W表示样本集。阶段二，计算W的前k个特征值和特征向量，构建特征向量空间。阶段三，利用K-means或其他经典聚类算法对向量空间中的特征向量进行聚类。不同的谱映射方法和准则函数的

25、选择形成了不同的谱聚类算法。在文献 蔡晓妍, 戴冠中, 杨黎斌. 谱聚类算法综述J. 计算机科学, 2008, 35(7):14-18.中，作者将谱聚类按使用的划分准则分为迭代谱和多路谱两类，并给出了各类中典型算法的介绍。迭代谱聚类算法中，PF算法 Perona P,Freeman W T.A factorization approach to grouping. H.Burkardt and B.Neumann,eds.Proc.ECCV.1998:655-670于1998年由Perona和Freeman提出，算法通过用相似矩阵W的第一个特征向量x1（最大特征值对应的特征向量）进行聚类。该算

26、法以其简单易于实现的特征引起了学术界的广泛关注。2000年，美国学者Shi和Malik提出了SM算法 Shi J,Malik J.Normalized cuts and image segmentation.IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000,22(8):888-905，该算法中构造正规相似矩阵W代入分割准则计算，并且用到了前两个特征值对应的特征向量，这样的改进使得SM算法DE聚类效果明显优于PF算法。此外，迭代谱聚类算法中的典型算法还包括Scott G L.提出的SLH算法 Scott G

27、L,Longuet-Higgins H C.Feature grouping by relocalization of eigenvectors of the proximity matrix. Proc.British Machine Vision Conference.1990:103-108，2000年Kan nan提出的KVV算法 Kannan R,Vempala S,Vetta A.On clusterings-good,bad and spectral.In FOCS,2000:367-377等。早期关于谱聚类的研究者倾向于利用二路划分准则通过迭代方式聚类样本数据。但近期研究发现，

28、选择多个特征直接进行k路分割会得到更好的聚类效果。2000年，Meila提出了MS算法 Meila M,Shi J.Learning segmentation by random walks.In NIPS,2000:873-879.，此算法以将相似性解释为马尔科夫链中的随机游动为基础，对MNcut进行了概率解释，在此解释的框架下选择随机游动矩阵P的前k个特征向量构造矩阵X，在实际应用中取得了一定的效果。2002年，Ng. Jordan等人提出了NJW算法 Ng A Y,Jordan M I,Weiss Y.On spectral clustering:Analysis and an algo

29、rithm. T.G.Dietterich,S.Becker,and Ghahramani,eds.Advances in Neural Information Processing Systems,Cambridge,MA,MIT Press,2002,14:849-856，选取Laplacican矩阵的前k个特征向量，在k维空间中生成与原数据一一对应的映像，并在此空间中进行聚类。三、四种主要聚类算法的总结比较上文介绍了很多种聚类算法，各个算法基于不同的理论基础，算法流程也各不相近，但对于聚类算法的性能评价有着比较通用的标准和测试数据集。本节中笔者首先简单介绍聚类要求，然后对目前四种常见的聚

30、类算法进行总结和性能比较。1. 评价标准 百度百科. 聚类算法EB/OL. 2014-5-26. /view/69222.htm#3.(1) 可伸缩性：聚类算法在处理小数据集合和大规模数据库对象时，是否具有同样良好的性能，而不因为数据量增大导致结果偏差。(2) 多类型数据：算法在处理非数值型数据，如二元类型，分类/标称类型，序数类型等数据时的性能。(3) 任意形状性：算法度量是否适用于任意形状（而非只是球状）的数据集，能够形成任意形状的正确聚簇。(4) 参数依赖性：聚簇结果对参数的依赖程度，以及适当参数确定的难度。(5) 抗噪声性：算法对于待处理数据中

31、孤立点，缺失或者错误数据的敏感程度以及其对聚簇结果的影响程度。(6) 顺序依赖性：聚簇结果对输入数据的顺序是否具有依赖性。(7) 高维度性：算法对于待处理数据的高维度处理能力。(8) 基于约束：算法是否能处理遇到现实问题时的额外约束，并给出合理的聚簇结果。(9)解释/可用性：算法给出的聚簇结果应该具有在现实中可以理解使用的特性。2. 四种主要算法的总结比较本小节中，笔者将给出当前比较主流的四种算法Kmeans、BIRCH、DBSCAN、谱聚类中较有代表性的具体算法的总结性描述，以及基于查阅资料基础上的性能分析比较，未能通过编码及统一的数据集进行测试，得出更为客观有参考性的比较结果笔者表示很遗憾

32、。(1) K-meansAKHM算法7AKHM算法即改进的K-调和均值算法。关于K-means的基本特征上文已经给出，此处不再赘述。KHM的算法流程为根据簇均值将数据初始分为K个簇，通过目标函数和中心移动公式对簇成员和中心点进行移动，算法迭代执行至不再有点移动即停止。AKHM对于传统KHM（K调和均值算法）的改进，在于使用了新的度量函数d(x,y)=1-exp(-x-y2)。得到KHM的新的目标函数如下：AKHMX,C=i=1NKj=1K11-exp(-xi-xj2)以及由此计算出的新的中心更新公式：wj=i=1Nexp(-xi-xj2)(1-exp(-xi-xj2)2(i=1K11-exp(

33、-xi-xj2)2xii=1Nexp(-xi-xj2)(1-exp(-xi-xj2)2(i=1K11-exp(-xi-xj2)2可见式中除了参数其他都以固定，故的选择影响了算法性能。文献7的作者通过对三个数据集IRIS、Wine以及Pendisttes进行试验，通过试验结果得出了针对不同数据的最优值。对于IRIS数据集，最优=0.1。Wine最优=0.00001。Pendisttes最优=0.0001。取三种最优值是，聚类结果的的误差平均和均小于KHM，聚类精确度不同程度上的优于KHM，运行时间和平迭代次数平均也优于KHM。由此，综合KHM的基本特性，可以得出AKHM对应于评价标准的一些特性分

34、析。1 可伸缩性：原文作者在文中指出，用于测试的数据集选择了离散的较小的数据量，尽管验证表明K-means伸缩性较好，但此算法的精确度优势在应用于处理大数据的效果并不可得知。2 数据结构适应性：AKHM由于继承自K-means，且并未对样本数据结构的处理能力进行优化，故仍然主要处理数值类型数据。3 参数依赖性：AKHM继承了K-means算法对参数K的依赖，以及本身对参数的依赖。此二者在一定程度上限制了AKHM的通用性和普及性。使得算法的性能依赖于算法使用者的经验而非算法本身。4 抗噪声性：AKHM具备调和均值的特性，可以根据数据点特征赋予其不同权重，抗噪声性明显优于K-meas算法。5 顺序

35、依赖性：类属于划分法的AKHM算法对于数据的输入顺序并不敏感。6 高维度性：从实验数据结果可知对于13维的数据集Wine和16维的数据集Pendisttes，AKHM算法均能得到比较理想的聚类效果。7 可解释/可用性：同样基于实验结果精度可知此算法具有较强的可解释和可用性。(2)BIRCH一种改进的BIRCH聚类算法26BIRCH算法属于层次聚类法的代表算法。BIRCH算法以及文献26中的改进策略在上文中已有详述，此处再做回顾以便于说明算法性能。BIRCH算法主要有四个阶段。第一阶段扫描待聚类的所有数据项，根据初始阈值T初始化一颗CF树。第二阶段采用聚合思路，通过增加阈值T重建CF树，使其聚合

36、度上升。第三、四阶段，对已有的CF树实行全局聚类以得到更好的聚类效果。文献26中对于BIRCH算法有两方面改进。一是分类属性的处理，而是阈值T的设定规则。关于分类属性的处理，文中将CF结构改为SCF。SCF=（N，Summary），N是聚类中数据点的个数，Summary包含数据点的数字属性和分类属性。由此改进了BIRCH算法只能处理数值型数据的局限。结构基于T的定义可知，其值与组内平均距离和组件平均距离，及数据的分布有关。因此，初始阈值T，可以采用如下公式计算得出。在数据集中随机选取N对数据，计算每对数据间的距离di，计算N对数据间距离的数学期望Ex和方差Dx。初始化CF树的T值为，T=P*（

37、Ex+0.25*Dx）。P为事先设定的百分比。在算法第二阶段，T的提升规则这是增大公式中的P值。这一算法的改进提升了原本算法的平均聚类精度和聚类效率，改进了BIRCH算法的性能。文献26的作者通过将改进后的BIRCH算法与K-means和K-modes算法的综合算法K-prototypes进行对比，使用三个数据集Mushroom，Congressional Votes和KDDCUP99的10%数据子集（包含条记录）进行测试对比了聚类精度，在测试时调整了调整了BIRCH的参数P和B、L（叶/非叶节点的条目个数），达到的最优聚类效果的平均算法进度分别高出K-prototypes算法4%，22%，3

38、%。下边同样给出改进了的BIRCH算法对应于评价标准的一些特性分析。1 可伸缩性：从实验数据以计算法特征可知，BIRCH算法具有良好的处理大量数据的能力。2 数据结构适应性：文献26中对于CF结构的调整即使BIRCH算法的数据结构适应性增强，对于车司机中非数值型的数据也能有较好地处理。3 参数依赖性：改进的BIRCH算法依赖于因子P的设定，同时还与B、L有关，这些参数均只能通过反复测试即经验的得出，降低了算法的非监督特性。4 抗噪声性： BIRCH算法本身的第三、四阶段全局优化时，会舍弃包含过少数据点的聚簇，对噪声有一定的抵抗能力。5 顺序依赖性：由于BIRCH算法在一次扫面数据既建成初始CF

39、树，故数据的在CF的不同状态时输入可能会被插入不同的位置，此算法的顺序依赖性较严重。6 高维度性：有实验数据得知BIRCH算法对于维度高的数据聚类结果较差。7 解释/可用性：通过对三个测试集的得到平均聚类精度均高于90%的结果可知，此算法的解释/可用性很好。(3) DBSCANIDBSCAN9DBSCAN是基于密度的空间聚类算法，算法的基本流程为从任意对象P开始根据阈值和参数通过广度优先搜索提取从P密度可达的所有对象，得到一个聚类。若P是核心对象，则可以一次标记相应对象为当前类并对此类内的项进行密度可达扩展，所有密度可达的项均被标记为p所在类，重复此过程直到不再有新的项被纳入此类。然后再选择一

40、个新的对象重复上述过程。若P是边界对象，则将其标记为噪声。重复上述过程直到所有项被标记如某一类或者噪声，即得到聚类结果。文献9中，作者提出了DBSCAN的几点不足，如密集数据时选取的无意义的种子对象过多导致算法效率低内存占用率大，以及对于非空间因素考虑不全面。针对这两个问题作者提出了IDBSCAN算法。对于前者问题，作者给出的解决方案是以初始点P为圆心，密度可达距离为半径原，以P为原点做坐直角坐标系，并画出I, III和II, IV象限的角平分线与圆的交点，每个象限内选取离该象限三个边界对象最近的至多8个点作为种子对象进行扩展，这样很好地解决了冗余查询问题。对于非空间因素的问题则提出了纯度（领

41、域内相同非空间属性的对象个数与领域内所有对象的比值），以此为基础提出了纯核心对象，纯直接密度可达等概念，同时给出了直接密度可达构造的聚簇与纯密度可达构造聚簇的关系，已解决非空间因素考虑不足的问题。在算法性能验证方面，文章作者将DBSCAN算法与IDBSCAN算法用为测试密度聚类而构造的数据集进行聚类测试。测试结果现实，在空间属性接近而非空间属性不同的区域中，IDESCAN算法准确的将其聚类为两类，而DBSCAN算法则并未识别直接将其聚为一类。在执行效率方面，作者将模拟数据集的对象个数从20000渐增到，IDBSCAN算法的效率性能明显优于DBSCAN算法。从算法评价标准来看：1 可伸缩性： I

42、DBSCAN对于大量数据的处理能力优于DBSCAN，但由于基于密度的算法的自身特性，考虑到内存占用和算法效率，这类算法并不适于过大规模的数据处理。2 任意形状性：IDBSCAN对于空间属性的处理方式使其有着较好的对数据形状的适应性。但主要应用于处理球面数据。3 参数依赖性：聚簇效果依赖于参数：半径。4 抗噪声性：基于密度算法会舍弃独立点，具有良好的抗噪声性。5 顺序依赖性：根据密度聚类，对于数据的输入顺序不敏感。6 高维度性：根据实验数据得出结论，算法在处理数据方面性能略差。7 解释/可用性：改进后的IDBSCAN算法考虑了数据的非空间特征，使得聚类结果更为合理。(4) 谱聚类NJW算法24NJW算法是谱聚类算法中多路谱聚类方法的一个代表算法。它的基本算法流程为：首先将待分类数据构成一个有权无向图，图的定点为数据点，边的权重为数据点间的相似度。然后将此图转化为Laplacian矩阵。计算矩阵的前k个特征向量，构建向量空间并将其行向量变换为单位向量。此时向量空间中的特征向量与原数据存在一一对应关系。在特征向量空间中利用K-means等聚类算法进行聚类。当向量空间中第i行被划分到某一聚类中，其对应的原数据点便被标记为该类。在算法性能方面NJW算法选择了更多特征向量，并直接计