一种快速山峰聚类算法摘要：山峰聚类既可以对数据集进行近似聚类，又可以为其他聚类方法提供聚类所需的初始聚类中心。减法聚类是山峰聚类的改进，它避免了山峰聚类中出现的计算量随样本维数增加呈指数增长的情况。但减法聚类对处理大样本集也力不从心。引入了P??tree数据结构，对高维大样本集进行分解，然后用减法聚类对子样本集进行聚类。此算法既避免了山峰聚类的维数灾难问题，也解决了减法聚类中样本数太大的问题。实验结果证明，该算法有效地减少了运算量，提高了聚类的速度。??关键词：聚类分析；山峰聚类法；减法聚类；P??tree；无监督学习??：TP391．4文献标志码：A：1001-3695(2008)07-2043-03??QuickmountainclusteringalgorithmCHENXiao??yun??1，MINYu??fang??1，ZHENGLiang??ren??1,YANGLi??2??(1.CollegeofInformationScienceEngineering,LanzhouUniversity,Lanzhou730000,China;2.Xin激angVocationalUniversity,Urumchi830011,China)??Abstract:Anewclusteringtechniqueisdescribed,whichisanimprovementonthemountainmethod(MM)ofclustering??originally??.Forhigherdimensionaldatasets,theMMapproachbecomescomputationallyunattractiveoreveninfeasible.Subtractiveclusteringmethodisanimprovementonthemountainmethod.ButforlargedatasetstheSCMcanstillbecomputatio?勃?nally??intensive.ThispaperusedP??treedatastructuretodecomposingthehigherdimensionalandlargedatasets,thenclusteredthesmalldatasetsusingSCM.Themethodnotonlyavoidsthequestionofhigherdimensional,butalsosolvestheshor?勃?tage??oflargedatasetsofSCM.??Keywords:clusteringanalysis；mountainclusteringmethod；subtractiveclusteringmethod(SCM)；P??tree；unsupervisedlearning?お?0引言??聚类分析是将特性相似的样本进行划分归类的过程。聚类分析既是从大量样本中获取知识的重要手段，也是数据挖掘中的常用方法[1，2]。根据聚类准则的不同，有多种不同的聚类算法[3]，但大多数聚类算法都存在两个问题：a)需要事先人为地给定一些参数如聚类个数、初始聚类中心等，而在没有先验知识的情况下，人为确定这些参数既是非常主观的，也是十分困难的；b)对于大样本集或高维样本集，聚类分析的时空效率难以保证。山峰聚类法是由Yager等人[4，5]提出的，是依据样本密度计算聚类中心的简捷有效的聚类方法。这种方法既可以对数据集进行近似聚类，又可以为其他聚类方法提供聚类所需的初始聚类中心。不过该方法的计算量随样本的维数增加呈指数级增长。为此，Chiu[6]对山峰聚类作了改进，提出了减法聚类（SCM），使得计算量由样本数目决定并且不会随样本维数增加呈指数增长。但是对于大样本集SCM方法同样由于计算量太大而显得力不从心。其后，Pal等人[7]对Chiu提出的减法聚类模型进行了改进，但是时间效率并没有得到很大的?┨岣摺＊???P??tree[8]（Peanocounttree）是一种空间数据基于象限的无损失的树表示。它主要用于高维空间数据的存储，为空间数据挖掘做准备。它的思想是递归地划分高维的样本集。为了降低在处理高维样本集和大样本集时的时间复杂度，本文将P??tree引进到山峰聚类算法，在聚类前先将大样本集用P??tree数据结构分解成2????n??个小样本集；然后用改进的减法聚类计算每个小样本集的聚类中心，作为整个聚类的候选聚类中心。用此算法既避免了原山峰聚类算法中随样本维数增加而呈指数增长的时间复杂度，也避免了减法聚类在面对大样本集时效率?┑拖隆＊???1山峰聚类??山峰聚类法是由Yager和Filev在1994年提出的一种大致估计聚类中心的有效的聚类方法。它的思想是将数据样本空间划分成有限的网格，并将所有网格的交叉点作为聚类中心的候选中心点，为每个交叉点构造山峰函数及计算其值；然后不断地修改山峰函数获取函数值最大的网格交叉点作为聚类中心。其算法步骤如下：??a）根据样本的密度分布，在数据样本空间构造网格。其网格的交叉点??v??j(j=1,2,…,m,m??为网格交叉点数）既是山峰函数的计算点，也是聚类中心的候选集，记为??v??j∈V。V??是由网格点构成的集合。网格划分越细...