数据挖掘中的聚类算法的综述

应劭霖

(江西省化学工业学校)

1 引言

随着信息技术和计算机技术的迅猛发展，人们面临着越来越多的文本、图像、视频以及音频数据，为帮助用户从这些大量数据中分析出其间所蕴涵的有价值的知识，数据挖掘(Data Mining，DM)技术应运而生。所谓数据挖掘[1]是指从大量无序的数据中提取隐含的、有效的、可解的、对决策有潜在价值的知识和规则，为用户提供问题求解层的决策支持能力。

聚类算法是一种有效的非监督的机器学习算法，是数据挖掘中的一个非常重要研究课题。聚类的定义：聚类是将数据划分成群的过程。通过确定数据之间在预先制定的属性上的相似性来完成聚类任务，这样最相似的数据就聚集成簇。聚类与分类的不同点：聚类的类别取决于数据本身；而分类的类别是由数据分析人员预先定义好的。

Everitt[5]关于聚类所下的定义为：一个类簇内的实体是相似的，不同类簇的实体是不相似的；一个类簇是测试空间中点的会聚，同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离；类簇可以描述为一个包含密度相对较高的点集的多维空间中的连通区域，它们借助包含密度相对较低的点集的区域与其他区域(类簇)相分离。

典型的聚类过程主要包括数据准备、特征选择和特征提取、接近度计算、聚类(或分组)、对聚类结果进行有效性评估等步骤[3]、[4]、[6]、[7]。

聚类过程：

(1)数据准备：包括特征标准化和降维。

(2)特征选择：从最初的特征中选择最有效的特征，并将其存储于向量中。

(3)特征提取：通过对所选择的特征进行转换形成新的突出特征。

(4)聚类(或分组)：首先选择合适特征类型的某种距离函数或构造新的距离函数进行接近程度的度量，然后执行聚类或分组。

(5)聚类结果评估：是指对聚类结果进行评估。评估主要有3种：外部有效性评估、内部有效性评估和相关性测试评估。

当人们使用数据挖掘工具对数据中的模型和关系进辨识的时候，通常第一个步骤就是聚类，其目的就是将集中的数人为地划分成若干类，使簇内相似度尽可能大、簇间相似度尽可小，以揭示这些数据分布的真实情况。但任何聚类算法都对数据本身有一定的预先假设，根据文献[1]的理论，如果数据集本身的分布并不符合预先的假设，则算法的结果将毫无意义。因此，面对定的应用问题，如何选择合适的聚类算法是聚类分析研究中的重要课题。本文比较了数据挖掘中现有聚类算法的性能，分析它们各自的优缺点，并指出了其今后的发展趋势。

2 聚类算法的分类

聚类是一种常见的数据分析工具，其目的是把大量数据点的集合分成若干类，使得每个类中的数据之间最大程度地相似，而不同的类中的数据最大程度地不同。在多媒体信息检索及数据挖掘的过程中，聚类处理对于建立高效的数据库索引、实现快速准确的信息检索具有重要的理论和现实意义。

本文以聚类算法所采用的基本思想为依据将它们分为四类，即层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法。

2.1 层次聚类算法

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

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

2.2 分割聚类算法

分割聚类算法是另外一种重要的聚类方法。它先将数据点集分为k个划分，然后从这k个初始划分开始，通过重复的控制策略使某个准则最优化以达到最终的结果。这类方法又可分为基于密度的聚类、基于网格的聚类和基于平方误差的迭代重分配聚类。

2.2.1 基于密度的聚类

基于密度的聚类算法从数据对象的分布密度出发，将密度足够大的相邻区域连接起来，从而可以发现具有任意形状的聚类，并能有效处理异常数据。它主要用于对空间数据的聚类。

DBSCAN[4]是一个典型的基于密度的聚类方法，它将聚类定义为一组密度连接的点集，然后通过不断生长足够高密度的区域来进行聚类。DENCLUE[5]则根据数据点在属性空间中的密度来进行聚类。从本质上讲，DENCLUE是基于密度的聚类算法与基于网格的预处理的结合，它受到目标数据的维度影响较小。此外，Ankerst等人提出的OPTICS，Xu等人提出的DB-CLASD和马帅等人提出的CURD算法也采用了基于密度的聚类思想，它们都针对数据在空间中呈现的不同密度分布对DB-SCAN作了相应的改进。

2.2.2 基于网格的聚类

基于网格的聚类从对数据空间划分的角度出发，利用属性空间的多维网格数据结构，将空间划分为有限数目的单元以构成一个可以进行聚类分析的网格结构。该方法的主要特点是处理时间与数据对象的数目无关，但与每维空间所划分的单元数相关；而且，基于其间接的处理步骤：数据→网格数据→空间划分→数据划分，该方法还与数据的输入顺序无关。与基于密度的聚类只能处理数值属性的数据所不同的是，基于网格的聚类可以处理任意类型的数据，但以降低聚类的质量和准确性为代价。

STING[6]是一个基于网格多分辨率的聚类方法，它将空间划分为方形单元，不同层次的方形单元对应不同层次的分辨率。CLIQUE[8]也是一个基于网格的聚类算法，它结合了网格聚类与密度聚类的思想，对于处理大规模高维数据具有较好的效果。除这些算法以外，以信号处理思想为基础的Wave-Cluster[9]算法也属基于网格聚类的范畴。

2.2.3 基于平方误差的迭代重分配聚类

基于平方误差的重分配聚类方法的主要思想是逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获得最优解。此类方法又可进一步分为概率聚类算法、考虑了最近邻影响的最近邻聚类算法以及K-medoids算法和K-means算法。

(1)概率聚类算法的重要代表是Mitchell等人于1997年提出的期望最大化算法(ExpectationMaximization，EM)[11]。它除了能处理异构数据之外，还具有另外几个重要的特性：①能处理具有复杂结构的记录；②能够连续处理成批的数据；③具有在线处理能力；④产生的聚类结果易于解释。

(2)最近邻距离的计算在聚类过程中起着基础性的作用，这也正是导致产生最近邻聚类算法的直接因素。共享最近邻算法(Shared NearestNeighbor，SNN)[12]就是该类算法的典型代表之一，它把基于密度的方法与ROCK算法的思想结合起来，通过只保留数据点的K个最近邻居从而简化了相似矩阵，并且也保留了与每个数据点相连的最近邻居的个数，但是其时间复杂度也提高到了O(N2)(N为数据点个数)。

(3)K-means算法是目前为止应用最为广泛的一种聚类方法，其每个类别均用该类中所有数据的平均值(或加权平均)来表示，这个平均值即被称作聚类中心。该方法虽然不能用于类别属性的数据，但对于数值属性的数据，它能很好地体现聚类在几何和统计学上的意义。但是，原始K-means算法也存在如下缺陷：①聚类结果的好坏依赖于对初始聚类中心的选择；②容易陷入局部最优解；③对K值的选择没有准则可依循；④对异常数据较为敏感；⑤只能处理数值属性的数据；⑥聚类结果可能不平衡。

为克服原始K-means算法存在的不足，研究者从各自不同的角度提出了一系列K-means的变体，如Bradley和Fayyad等人从降低聚类结果对初始聚类中心的依赖程度入手对它作了改进，同时也使该算法能适用于大规模的数据集[15]；Dhillon等人则通过调整迭代过程中重新计算聚类中心的方法使其性能得到了提高[10]。

2.3 基于约束的聚类算法

真实世界中的聚类问题往往是具备多种约束条件的，然而由于在处理过程中不能准确表达相应的约束条件、不能很好地利用约束知识进行推理以及不能有效利用动态的约束条件，使得这一方法无法得到广泛的推广和应用。这里的约束可以是对个体对象的约束，也可以是对聚类参数的约束，它们均来自相关领域的经验知识。该方法的一个重要应用在于对存在障碍数据的二维空间数据进行聚类。COD(Clustering with Obstructed Distance)[11]就是处理这类问题的典型算法，其主要思想是用两点之间的障碍距离取代了一般的欧氏距离来计算其间的最小距离。更多关于这一聚类算法的总结可参考文献[12]。

2.4 机器学习中的聚类算法

机器学习中的聚类算法是指与机器学习相关、采用了某些机器学习理论的聚类方法，它主要包括人工神经网络方法以及基于进化理论的方法。

自组织映射(Self-Organizing Map，SOM)[9]是利用人工神经网络进行聚类的较早尝试，它也是向量量化方法的典型代表之一。该方法具有两个主要特点：①它是一种递增的方法，即所有的数据点是逐一进行处理的；②它能将聚类中心点映射到一个二维的平面上，从而实现可视化。此外，文献[10]中提出的一种基于投影自适应谐振理论的人工神经网络聚类也具有很好的性能。

在基于进化理论的聚类方法中，模拟退火的应用较为广泛，SINICC算法[7]就是其中之一。在模拟退火中经常使用到“微扰因子”，其作用等同于把一个点从当前的聚类重新分配到一个随机选择的新类别中，这与K-means中采用的机制有些类似。遗传算法也可以用于聚类处理，它主要通过选择、交叉和变异这三种遗传算子的运算以不断优化可选方案从而得到最终的聚类结果。

3 几个典型的聚类算法

3.1 BIRCH算法

BIRCH是一个层次聚类方法，它利用层次方法的平衡迭代进行聚类。其核心是用一个聚类特征三元组表示一个簇的有关信息，从而使一簇点的表示可用对应的聚类特征。它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。算法具有对象数目的线性易伸缩性，及良好的聚类质量。一次扫描就可以进行较好的聚类，其计算复杂度为O(n)。

3.2 DBSCAN算法

DBSCAN是基于密度的聚类算法，可以将足够高密度的区域分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的类。该算法利用类的密度连通性可以快速发现任意形状的类。基本思想是：对于一个类中的每个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目。DBSCAN算法不进行任何的预处理而直接对整个数据集进行聚类操作。当数据量非常大时，就必须有大量内存支持，I/O消耗也非常大。其时间复杂度为O(nlogn)，聚类过程的大部分时间用在区域查询操作上。

DBSCAN算法能够发现空间数据库中任意形状的密度连通集；在给定合适的参数条件下，能很好地处理噪声点；对用户领域知识要求较少；对数据的输入顺序不太敏感；适用于大型数据库。但DBSCAN算法要求事先指定领域和阈值，具体使用的参数依赖于应用的目的。

3.3 CLARANS算法

CLARANS通过利用多次不同抽样改进了CLARA算法，是一种k-中心点聚类方法。它首先随机选择一个点作为当前点，然后随机检查它周围不超过参数Maxeighbar个的一些邻接点。假如找到一个比它更好的邻接点，则把它移入该邻接点，否则把该点作为局部最小量。然后再随机选择一个点来寻找另一个局部最小量，直至所找到的局部最小量数目达到用户要求为止。该算法要求聚类的对象必须预先调入内存，并且需多次扫描数据集，其时空复杂度都相当大，虽通过引入R*—树结构对其性能进行改善，但构造和维护代价太大。该算法对“脏数据”和“异常数据”不敏感，但对数据输入顺序异常敏感，且只能处理凸形或球形边界聚类，效率较高。

4 现有聚类算法的性能比较

从上面的分析介绍不难看出，这些现有的聚类算法在不同的应用领域中均表现出了不同的性能，也就是说，很少有一种算法能同时适用于若干个不同的应用背景。

总体来说，分割聚类算法的应用最为广泛，其收敛速度快，且能够扩展以用于大规模的数据集；缺点在于它倾向于识别凸形分布、大小相近、密度相近的聚类，而不能发现形状比较复杂的聚类，并且初始聚类中心的选择和噪声数据会对聚类结果产生较大的影响。层次聚类方法不仅适用于任意属性和任意形状的数据集，还可以灵活控制不同层次的聚类粒度，因此具有较强的聚类能力，但它大大延长了算法的执行时间；此外，对层次聚类算法中已经形成的聚类结构不能进行回溯处理。基于约束的聚类通常只用于处理某些特定应用领域中的特定需求。机器学习中的人工神经网络和模拟退火等方法虽然能利用相应的启发式算法获得较高质量的聚类结果，但其计算复杂度往往较高，同时其聚类结果的好坏也依赖于对某些经验参数的选取。在针对高维数据的子空间聚类和联合聚类等算法中，虽然通过在聚类过程中选维、逐维聚类和降维从一定程度上减少了高维度带来的影响，但它们均不可避免地带来了原始数据信息的损失和相应的聚类准确性的降低。因此，寻求这类算法在聚类质量和算法时间复杂度之间的折中也是一个重要的问题。

总之，虽然一些算法相对其他方法在某些方面的性能有了一定程度的提高，但它不可能在任何应用背景下均具有很好的结果，各有各的优势和不足。因此对于它们的改进还有一个相当大的空间。

5 总结与展望

通过以上的分析得知，没有一种算法是十全十美的，建议使用者根据实际情况，例如发现聚类的形状、数据输入顺序是否敏感、适用数据库的大小或者算法效率，来选择聚类算法。

一般情况下有以下结论：

(1)目标数据库如果比较大，建议使用综合性的聚类算法，如：BIRCH、CURE、DBSCAN和STING等，以提高算法效率。

(2)如果聚类的形状是球形或者凸形，BIRCH和CLARANS比较适合。

(3)一般而言，聚类算法对数据输入的顺序都比较敏感。如果希望不敏感，可以选用基于网格的STING算法。

(4)将不同类型的聚类算法相互结合(例如BIRCH算法和CURE算法)，综合各自的优点，以满足不同的聚类要求。是今后聚类算法的一个重要发展方向。

聚类分析是数据挖掘中一种非常有用的技术，它可作为特征和分类算法的预处理步骤，也可将聚类结果用于进一步关联分析，还可以作为一个独立的工具来获得数据分布的情况。聚类算法的研究具有广泛的应用前景，其今后的发展也面临着越来越多的挑战。首先是聚类算法的选择，建议使用者根据实际情况(例如发现聚类的形状、数据输入顺序是否敏感、适用数据库的大小或者算法效率)来选择合适的聚类算法。其次，对于特征数据本身所具备的高维性、复杂性、动态性以及容易达到大规模的特性，聚类算法的设计还应该更多地考虑融合不同的聚类思想形成新的聚类算法，从而综合利用不同聚类算法的优点。

[1]蔡伟杰,张晓辉,朱建秋,朱扬勇.关联规则挖掘综述,2004.

[2]薛惠锋,张文宇,寇晓东.智能数据挖掘技术.西安:西北工业大学出版社,2005.

[3]王光宏,蒋平.数据挖掘综述.同济大学学报.2004年2月.

[4]Han J W,Micheline K.数据挖掘概念与技术.范明,孟晓峰译.北京：机械工业出版社,2001.

[5]夏火松,数据仓库与数据挖掘技术[M]北京:科学出版社,2004.

[6]苏新宁,杨建林,邓三鸿,等.数据挖掘理论与技术[M].北京:科学技术文献出版社.2003:53～65.

[7]陈京明著.数据仓库与数据挖掘技术.北京:电子工业出版,2004.8.

[8]Mehmed Kantardzic.数据挖掘—概念、模型、方法和算法[M].陈茵,程雁译北京:清华大学出版社.2003.

[9]Pearl J.Data Mining with Graphical Models[D].Computer Science Dept.Standford University.2000.

[10]GantiV,Gehrke J,RamakrishnaR. CACTUS-ClusteringCategorical DataUsing Summaries[C].San Diego:Proceedings of the 5th ACMSIGKDD,1999.73-83.

[11]TungAKH,Hou J,Han J.SpatialClustering in the Presence ofOb-stacles[C].Heidelberg: Proceedings of the 17th ICDE,2001.359-367.

[12]Han J,KamberM,TungA KH.SpatialClusteringMethods in Data Mining:A Survey[C]. GeographicDataMining andKnowledgeDis-covery,2001.