聚类算法研究综述

1、电脑知识与技术本栏目责任编辑:闻翔军数据库及信息管理1引言数据挖掘是指从从大量无序的数据中提取隐含的、有效的、可理解的、对决策有潜在价值的知识和规则,为用户提供问题求解层次的决策支持能力。数据挖掘主要的算法有分类模式、关联规则、决策树、序列模式、聚类模式分析、神经网络算法等等。聚类算法是一种有效的非监督机器学习算法,是数据挖掘中的一个非常重要的研究课题。当人们使用数据挖掘工具对数据中的模型和关系进行辨识的时候,通常第一个步骤就是聚类,其目的就是将集中的数据人为地划分成若干类,使簇内相似度尽可能大、簇间相似度尽可能小,以揭示这些数据分布的真实情况。但任何聚类算法都对数据集本身有一定的预先假设,根

2、据文献1的理论,如果数据集本身的分布并不符合预先的假设,则算法的结果将毫无意义。因此,面对特定的应用问题,如何选择合适的聚类算法是聚类分析研究中的一个重要课题。本文比较了数据挖掘中现有聚类算法的性能,分析了它们各自的优缺点,并指出了其今后的发展趋势。2聚类算法分类研究聚类的目的是把大量数据点的集合分成若干类,使得每个类中的数据之间最大程度地相似,而不同类中的数据最大程度地不同。通常聚类算法可以分为层次聚类、分割聚类、密度型聚类、网格型聚类和其他聚类等几种。2.1层次聚类层次聚类算法通过将数据组织成若干组并形成一个相应的树状图来进行聚类,它又可以分为两类,即自底向上的聚合层次聚类和自顶向下的分裂

3、层次聚类。聚结型算法采用自底向上的策略,首先把每个对象单独作为一个聚类,然后根据一定的规则合并成为越来越大的聚类,直到最后所有的对象都归入到一个聚类中。大多数层次聚类算法都属于聚结型算法,它们之间的区别在于类间相似度的定义不同。与聚结型算法相反,分裂型算法采用自顶向下的方法,它先将所有的对象都看成一个聚类,然后将其不断分解直至每个对象都独自归入一个聚类。一般情况下不使用分裂型方法,因为在较高的层次很难进行正确的拆分。纯粹的层次聚类算法的缺点在于一旦进行合并或分裂之后,就无法再进行调整。现在的一些研究侧重于层次聚类算法与循环的重新分配方法的结合。主要的层次聚类算法有BIRCH ,CURE ,RO

4、CK ,CHAMELEON ,AMOEBA ,COBWEB ,Clustering with Random Walks 算法等。CURE 算法2不用单个中心或对象来代表一个聚类,而是选择数据空间中固定数目的、具有代表性的一些点共同来代表相应的类,这样就可以识别具有复杂形状和不同大小的聚类,从而能很好地过滤孤立点。ROCK 算法3是对CURE 的改进,除了具有CURE 算法的一些优良特性之外,它还适用于类别属性的数据。CHAMELEON 算法4是Karypis 等人于1999年提出来的,它在聚合聚类的过程中利用了动态建模的技术。2.2分割聚类分割聚类算法是另外一种重要的聚类方法。它先将数据点集分

5、为k 个划分,每个划分作为一个聚类,然后从这k 个初始划分开始,通过重复的控制策略,使某个准则最优化,而每个聚类由其质心来代表(k-means 算法,或者由该聚类中最靠近中心的一个对象来代表(k-medoids 算法,以达到最终的结果。分割聚类算法收敛速度快,缺点在于它倾向于识别凸形分布大小相近、密度相近的聚类,不能发现分布形状比较复杂的聚类,它要求类别数目k 可以合理地估计,并且初始中心的选择和噪声会对聚类结果产生很大影响。这类方法又可分为基于密度的聚类、基于网格的聚类等。很多算法中都使用距离来描述数据之间的相似性,但是,对于非凸数据集,只用距离来描述是不够的。对于这种情况,要用密度来取代相

6、似性,这就是基于密度的聚类算法。基于密度的算法从数据对象的分布密度出发,把密度足够大的区域连接起来,从而可以发现任意形状的类。此类算法除了可以发现任意形状的类,还能够有效去除噪声。基于网格的聚类算法,把空间量化为有限个单元(即长方体或超长方体,然后对量化后的空间进行聚类。此类算法具有很快的处理速度。缺点是只能发现边界是水平或垂直的聚类,而不能检测到斜边界。此类算法具有很快的处理速度。时间复杂度一般由网格单元的数目决定,而与数据集的大小无关。此外,聚类的精度取决于网格单元的大小。此类算法不适用于高维情况,因为网格单元的数目随着维数的增加而呈指数增长。所有基于网格的聚类算法都存在下列问题:一是如何

7、选择合适的单元大小和数目;二是怎样对每个单元中对象的信息进行汇总。主要的分割聚类算法有k -means ,EM ,k -medoids ,收稿日期:2007-06-10作者简介:项冰冰(1980-,女,安徽合肥人,安徽大学助教,工学学士,研究方向:数据挖掘,人工智能;钱光超(1982-,男,安徽安徽无为人,安徽大学计算机科学与技术学院05级研究生,工学学士。聚类算法研究综述项冰冰1,钱光超2(1.安徽大学数学与计算科学学院安徽合肥23039;2.安徽大学计算机科学与技术学院安徽合肥230039摘要:聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。阐述了聚类算法基本原理,总结了聚类算法

8、的研究现状,按照聚类算法的分类,分析比较了几种典型聚类的性能差异和各自存在的优点及问题,并结合应用需求指出了其今后的发展趋势。关键词:数据挖掘;聚类分析;聚类算法中图分类号:TP301.6文献标识码:A 文章编号:1009-3044(200712-21500-02The Research of Clustering AlgorithmsXIANG Bing-bing 1,QIAN Guang-chao 2(1.School of Mathematics and Computational Science,Anhui University,Hefei,Anhui Province 230039,

9、China ;2.School of Computer Scienceand Technology ,Anhui University,Hefei,Anhui Province 230039,ChinaAbstract :Clustering is an important technique in data mining.It s used to discover the data distribution and concealed patterns.The paper elucidate the basic principle of the clustering algorithms a

10、nd sum up the contemporary research of the clustering algorithms.It also analyze a few representative clustering algorithms and compare their differences ,advantages and disadvantages.At last ,the paper indicate the development trend of clustering integrating the application demand.Key word:Data min

11、ing ;Clustering Analysis ;Clustering Algorithms1500本栏目责任编辑:闻翔军数据库及信息管理CLARA,CLARANS等。常见的k-medoids算法有PAM算法、CLARA算法、CLARANS算法。2.3其他聚类主要有:基于约束的聚类算法、机器学习中的聚类算法、用于高维数据的聚类算法等。基于约束的聚类算法,其约束可以是对个体对象的约束,也可以是对聚类参数的约束,它们均来自相关领域的经验知识。该方法的一个重要应用在于对存在障碍数据的二维空间数据进行聚类。COD(Clustering with Obstructed Distance5就是处理这类问

12、题的典型算法,其主要思想是用两点之间的障碍距离取代了一般的欧氏距离来计算其间的最小距离。机器学习中的聚类算法是指与机器学习相关、采用了某些机器学习理论的聚类方法,它主要包括人工神经网络方法以及基于进化理论的方法。如自组织特征映射(SOM网络是利用人工神经网络进行聚类的较早尝试,它也是向量量化方法的典型代表之一。在基于进化理论的聚类方法中,模拟退火的应用较为广泛, SNICC算法6就是其中之一。遗传算法也可以用于聚类处理,它主要通过选择、交叉和变异这三种遗传算子的运算以不断优化可选方案从而得到最终的聚类结果。高维数据聚类是目前多媒体数据挖掘领域面临的重大挑战之一,除了降维这一最直接的方法之外,对

13、高维数据的聚类处理还包括子空间聚类以及联合聚类技术等。子空间聚类算法,认为在高维数据集中,聚类往往不是存在于整个空间中,而是存在于某些子空间中。它们针对高维空间数据,寻找子空间中的聚类。主要子空间聚类算法有CLIQUE,PROCLUS等。3典型聚类算法性能比较3.1CLARANS算法CLARANS通过利用多次不同抽样改进了CLARA算法,是一种k-中心点聚类方法。它首先随机选择一个点作为当前点,然后随机检查它周围不超过参数Maxeighbar个的一些邻接点。假如找到一个比它更好的邻接点,则把它移入该邻接点,否则把该点作为局部最小量。然后再随机选择一个点来寻找另一个局部最小量,直至所找到的局部最

14、小量数目达到用户要求为止。该算法要求聚类的对象必须预先调入内存,并且需多次扫描数据集,其时空复杂度都相当大,虽通过引入R*树结构对其性能进行改善,但构造和维护代价太大。该算法对脏数据和异常数据不敏感,但对数据输入顺序异常敏感,且只能处理凸形或球形边界聚类,效率较高。3.2BIRCH算法BIRCH是一个综合性的层次聚类方法,它利用层次方法的平衡迭代进行归约和聚类。其核心是用一个聚类特征三元组表示一个簇的有关信息,从而使一簇点的表示可用对应的聚类特征。它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。算法具有对象数目的线

15、性易伸缩性,及良好的聚类质量。一次扫描就可以进行较好的聚类,其计算复杂度为O(n。BIRCH算法只适用于类的分布呈凸形及球形的情况,对不可视的高维数据则是不可行的。3.3DBSCAN算法DBSCAN是基于密度的聚类算法,可以将足够高密度的区域划分为簇,并可以在带有“噪声”的空间数据库中发现任意形状的聚类。该算法利用类的密度连通性可以快速发现任意形状的类。其基本思想是:对于一个类中的每个对象,在其给定半径的领域中包含的对象不能少于某一给定的最小数目。DBSCAN算法不进行任何的预处理而直接对整个数据集进行聚类操作。当数据量非常大时,就必须有大量内存支持,I/O消耗也非常大。其时间复杂度为O(nl

16、ogn,聚类过程的大部分时间用在区域查询操作上。DBSCAN算法能够发现空间数据库中任意形状的密度连通集;在给定合适的参数条件下,能很好地处理噪声点;对用户领域知识要求较少;对数据的输入顺序不太敏感;适用于大型数据库。但DBSCAN算法要求事先指定领域和阈值,具体使用的参数依赖于应用的目的。3.4STING算法STING是一种格的多分辨率聚类技术。它将空间区域划分为矩形单元,针对不同级别的分辨率,通常存在多个级别的矩形单元,这些单元形成了一个层次结构:高层的每个单元被划分为多个低一层的单元。高层单元的统计参数可以很容易地从低层单元的计算得到。STING扫描数据库一次来计算单元的统计信息,因此产

17、生聚类的时间复杂度是O(n,其中n是对象的数目。在层次结构建立后,查询处理时间是O(g,g是最低层风格单元的数目,通常远远小于n。STING是独立于查询的,有利于并行处理和增量更新且效率较高。但由于STING采用了一个多分辨率的方法来进行聚类分析,聚类的质量取决于网格结构的最低层粒度。如果数据粒度比较细,处理的代价会明显增加。并且,STING在构建一个父单元时没有考虑子单元和其相邻单元之间的关系,因此,尽管该技术处理速度快,但可能降低簇的质量和精确性。4结论和展望聚类分析是数据挖掘中一种非常有用的技术,它可作为特征和分类算法的预处理步骤,也可将聚类结果用于进一步关联分析,还可以作为一个独立的工

18、具来获得数据分布的情况。聚类算法的研究具有广泛的应用前景,其今后的发展也面临着越来越多的挑战。首先是聚类算法的选择,建议使用者根据实际情况(例如发现聚类的形状、数据输入顺序是否敏感、适用数据库的大小或者算法效率来选择合适的聚类算法。其次,对于特征数据本身所具备的高维性、复杂性、动态性以及容易达到大规模的特性,聚类算法的设计还应该更多地考虑融合不同的聚类思想形成新的聚类算法,从而综合利用不同聚类算法的优点。参考文献:1R O Duda,P E Hart,D G Stork.Pattern Classification(2nd EditionM.New York:Wiley,2001.4542458.2Guha S,Rastogi R,Shim K.CURE:An Efficient Clus