各种聚类算法及改进算法的研究

1、.各种聚类算法及改进算法的研究作者：王安志李明东李超时间：2009-3-3 10:59:00来源：论文天下论文网论文关键词：数据挖掘；聚类算法；聚类分析 论文摘要：该文详细阐述了数据挖掘领域的常用聚类算法及改进算法，并比较分析了其优缺点，提出了数据挖掘对聚类的典型要求，指出各自的特点，以便于人们更快、更容易地选择一种聚类算法解决特定问题和对聚类算法作进一步的研究。并给出了相应的算法评价标准、改进建议和聚类分析研究的热点、难点。上述工作将为聚类分析和数据挖掘等研究提供有益的参考。 1 引言 随着经济社会和科学技术的高速发展，各行各业积累的数据量急剧增长，如何从海量的数据中提取有用的信息成为当务之

2、急。聚类是将数据划分成群组的过程，即把数据对象分成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。它对未知数据的划分和分析起着非常有效的作用。通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。为了找到效率高、通用性强的聚类方法人们从不同角度提出了许多种聚类算法，一般可分为基于层次的，基于划分的，基于密度的，基于网格的和基于模型的五大类。 2 数据挖掘对聚类算法的要求 (1)可兼容性：要求聚类算法能够适应并处理属性不同类型的数据。(2)可伸缩性：要求聚类算法对大型数据集和小数据集都适用。(3)对用户专业知识要求最小化。(4)对数据

3、类别簇的包容性：即聚类算法不仅能在用基本几何形式表达的数据上运行得很好，还要在以其他更高维度形式表现的数据上同样也能实现。(5)能有效识别并处理数据库的大量数据中普遍包含的异常值，空缺值或错误的不符合现实的数据。(6)聚类结果既要满足特定约束条件，又要具有良好聚类特性，且不丢失数据的真实信息。(7)可读性和可视性：能利用各种属性如颜色等以直观形式向用户显示数据挖掘的结果。(8)处理噪声数据的能力。(9)算法能否与输入顺序无关。 3 各种聚类算法介绍 随着人们对数据挖掘的深入研究和了解，各种聚类算法的改进算法也相继提出，很多新算法在前人提出的算法中做了某些方面的提高和改进，且很多算法是有针对性地

4、为特定的领域而设计。某些算法可能对某类数据在可行性、效率、精度或简单性上具有一定的优越性，但对其它类型的数据或在其他领域应用中则不一定还有优势。所以，我们必须清楚地了解各种算法的优缺点和应用范围，根据实际问题选择合适的算法。 3.1 基于层次的聚类算法 基于层次的聚类算法对给定数据对象进行层次上的分解，可分为凝聚算法和分裂算法。 (1)自底向上的凝聚聚类方法。这种策略是以数据对象作为原子类，然后将这些原子类进行聚合。逐步聚合成越来越大的类，直到满足终止条件。凝聚算法的过程为：在初始时，每一个成员都组成一个单独的簇，在以后的迭代过程中，再把那些相互邻近的簇合并成一个簇，直到所有的成员组成一个簇为

5、止。其时间和空间复杂性均为O(n2)。通过凝聚式的方法将两簇合并后，无法再将其分离到之前的状态。在凝聚聚类时，选择合适的类的个数和画出原始数据的图像很重要。 (2)自顶向下分裂聚类方法。与凝聚法相反，该法先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件。其主要思想是将那些成员之间不是非常紧密的簇进行分裂。跟凝聚式方法的方向相反，从一个簇出发，一步一步细化。它的优点在于研究者可以把注意力集中在数据的结构上面。一般情况下不使用分裂型方法，因为在较高的层很难进行正确的拆分。 3.2 基于密度的聚类算法 很多算法都使用距离来描述数据之间的相似性，但对于

6、非凸数据集，只用距离来描述是不够的。此时可用密度来取代距离描述相似性，即基于密度的聚类算法。它不是基于各种各样的距离，所以能克服基于距离的算法只能发现“类圆形”的聚类的缺点。其指导思想是：只要一个区域中的点的密度（对象或数据点的数目）大过某个阈值，就把它加到与之相近的聚类中去。该法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可发现任意形状的簇，并可用来过滤“噪声”数据。常见算法有DBSCAN，DENCLUE等。3.3 基于划分的聚类算法 给定一个N个对象的元组或数据库，根据给定要创建的划分的数目k，将数据划分为k个组，每个组表示一个簇类（<=N）时满足如下两点：(1)每个组

7、至少包含一个对象；(2)每个对象必须属于且只属于一个组。算法先随机创建一个初始划分，然后采用一种迭代的重定位技术，通过将对象根据簇类之间的差异从一个划分移到另一个划分来提高簇类内数据之间的相似程度。一种好的划分的一般准则是：在同一个类中的对象尽可能“接近”或相似，而不同类中的对象尽可能“远离”或不同。为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。典型的划包括：K-means，PAM，EM等。划分法收敛速度快，在对中小规模的数据库中发现球状簇很适用。缺点是它倾向于识别凸形分布大小相近、密度相近的聚类，不能发现分布形状比较复杂的聚类，它要求类别数目k可以合理地估计，且初始中心的选择和噪

8、声会对聚类结果产生很大影响。还要求用户预先指定聚类个数。 3.4 基于网格的聚类算法 首先将数据空间量化为有限个单元的网格结构，然后对量化后的单个的单元为对象进行聚类。典型的算法有STING，CLIQUE等。网格聚类法处理速度快，处理时间与数据对象的数目无关，一般由网格单元的数目决定。缺点是只能发现边界是水平或垂直的聚类，不能检测到斜边界。该类算法也不适用于高维情况，因为网格单元的数目随着维数的增加而呈指数增长。另外还有下列问题： 一是如何选择合适的单元大小和数目，二是怎样对每个单元中对象的信息进行汇总，三是存在量化尺度的问题。 3.5 基于模型的聚类算法 基于模型的方法给每一个聚簇假定了一个

9、模型，然后去寻找能够很好满足这个模型的数据集。这个模型可能是数据点在空间中的密度分布函数，它由一系列的概率分布决定，也可能通过基于标准的统计数字自动决定聚类的数目。它的一个潜在假定是：目标数据集是由一系列的概率分布所决定的。一般有2种尝试方向：统计的方案和神经网络的方案。COBWEB是一种流行的简单增量概念聚类算法，以一个分类树的形式来创建层次聚类，它的输入对象用分类属性-值对来描述。COBWEB的优点为：可以自动修正划分中类的数目；不需要用户提供输入参数。缺点为：COBWEB基于这样一个假设：在每个属性上的概率分布是彼此独立的。但这个假设并不总是成立。且对于偏斜的输入数据不是高度平衡的，它可

10、能导致时间和空间复杂性的剧烈变化，不适用于聚类大型数据库的数据。 3.6 模糊聚类算法 现实中很多对象没有严格的属性，其类属和形态存在着中介性，适合软划分。恰好模糊聚类具有描述样本类属中间性的优点，因此成为当今聚类分析研究的主流。常用的模糊聚类有动态直接聚类法、最大树法、FCM等。基本原理为：假设有N个要分析的样本，每个样本有M个可量化的指标，一般步骤为：(1)标准化数据：常用的数据标准化方法有：小数定标规范化，最大最小值规范化，标准差规范化等。(2)建立模糊相似矩阵，标定相似系数。(3)计算多极相似矩阵，计算整体相似关系矩阵，有传递闭包法，动态直接聚类法，最大树法等。(4)给定一个聚类水平，

11、计算绝对相似矩阵。按行列调整绝对相似矩阵，每个分块即为一个分类。 3.6.1 模糊C-均值聚类算法 FCM算法用隶属度确定每个样本属于某个聚类的程度。它与K平均算法和中心点算法等相比，计算量可大大减少，因为它省去了多重迭代的反复计算过程，效率将大大提高。同时，模糊聚类分析可根据数据库中的相关数据计算形成模糊相似矩阵，形成相似矩阵之后，直接对相似矩阵进行处理即可，无须多次反复扫描数据库。根据实验要求动态设定m值，以满足不同类型数据挖掘任务的需要，适于高维度的数据的处理，具有较好的伸缩性，便于找出异常点。但m值根据经验或者实验得来，具有不确定性，可能影响实验结果。并且，由于梯度法的搜索方向总是沿着

12、能量减小的方向，使得算法存在易陷入局部极小值和对初始化敏感的缺点。为克服上述缺点，可在FCM算法中引入全局寻优法来摆脱FCM聚类运算时可能陷入的局部极小点，优化聚类效果。 3.6.2 免疫进化算法 该算法借鉴生命科学中的免疫概念和理论在保留原算法优良特性的前提下，力图有选择、有目的地利用待求问题中的一些特征或知识来抑制其优化过程中出现的退化现象。免疫算法的核心在于免疫算子的构造，通过接种疫苗或免疫选择两个步骤来完成。免疫进化算法能提高个体的适应度和防止群体的退化，从而达到减轻原有进化算法后期的波动现象和提高收敛速度。例如IFCM、IFCL算法。它们既较大地提高了获取全局最优的概率，又减轻了基于

13、遗传聚类算法在遗传后期的波动现象。进一步的工作是参数的适当选取和减小运行时间等。人对于客观事物的识别往往只通过一些模糊信息的综合，便可以获得足够精确的定论。3.7 其它聚类算法 3.7.1 基于群的聚类方法 该法是进化计算的一个分支，模拟了生物界中蚁群、鱼群等在觅食或避敌时的行为。可分为蚁群算法ACO和PSO。蚁群聚类算法的许多特性，如灵活性、健壮性、分布性和自组织性等，使其非常适合本质上是分布、动态及又要交错的问题求解中，能解决无人监督的聚类问题，具有广阔的前景。PSO模拟了鱼群或鸟群的行为。在优化领域，PSO可以与遗传算法相媲美，并在预测精度和运行速度方面占优势。对ACO或PSO在数据挖掘

14、中应用的研究仍处于早期阶段，要将这些方法用到实际的大规模数据挖掘的聚类分析中还需要做大量的研究工作。 3.7.2 基于粒度的聚类方法 从粒度的角度看，我们会发现聚类和分类有很大的相通之处：聚类操作实际上是在一个统一粒度下进行计算的；分类操作是在不同粒度下进行的。所以说在粒度原理下，聚类和分类是相通的，很多分类的方法也可以用在聚类方法中。作为一个新的研究方向，虽然目前粒度计算还不成熟，尤其是对粒度计算语义的研究还相当少，但相信随着粒度理论的不断发展，今后几年它必将在聚类算法及其相关领域得到广泛的应用。 3.7.3 谱聚法 谱聚类方法建立在谱图理论基础之上，并利用数据的相似矩阵的特征向量进行聚类，

15、是一种基于两点间相似关系的方法，这使得该方法适用于非测度空间。它与数据点的维数无关，而仅与数据点的个数有关，可以避免由特征向量的过高维数所造成的奇异性问题。它又是一个判别式算法，不用对数据的全局结构作假设，而是首先收集局部信息来表示两点属于同一类的可能性；然后根据某一聚类判据作全局决策，将所有数据点划分到不同的数据集合中。通常这样的判据可以在一个嵌入空间中得到解释，该嵌入空间是由数据矩阵的某几个特征向量张成的。谱聚类算法成功原因在于：通过特征分解，可以获得聚类判据在放松了的连续域中的全局最优解。与其他算法相比，它不仅思想简单、易于实现、不易陷入局部最优解，而且具有识别非凸分布的聚类能力，非常适

16、合于许多实际问题。目前，该算法已应用于语音识别、VLSI设计、文本挖掘等领域。 3.7.4 多种聚类方法的融合 实际应用的复杂性和数据的多样性往往使得单一的算法无能为力。因此，很多人对多种算法的融合进行了广泛研究并取得了一些成果。大致可分为以下几类：(1)基于传统聚类方法的融合，如CLIQUE、CUBN等。(2)模糊理论与其他聚类法的融合，如遗传模糊C2均值混合聚类法等。(3)遗传算法与机器学习的融合。(4)传统聚类法与其他学科理论的融合，如谱算法等。总之，很多新算法是以上几类方法中两种或两种以上方法有机结合而得的，它们取长补短，优势明显，这也是我们数据挖掘研究人员要努力的研究方向之一。 4

17、结论 综上所述，分层聚类的突出优点是它能够生成比较规整的类集合，聚类结果不依赖元素的初始排列或输入次序，与聚类过程的先后次序无关，聚类结果比较稳定，不易导致类的重构。但计算开销较大，对异常数据比较脆弱。划分聚类的优势是运算量小，能用于处理庞大的样本数据，也为实时处理提供了一定的可能性。但要求用户必须事先给出要生成的簇的数目。网格聚类处理速度快，处理时间与数据对象的数目无关。缺点是只能发现边界是水平或垂直的聚类，而不能检测到斜边界。也不适用于高维情况，并存在量化尺度的问题。密度聚类的优点是一遍扫描，并可以在带有“噪声”的空间数据库中发现形状任意、个数不定的聚类。 通常可参考以下建议：(1)如果希

18、望聚类算法对数据输入的顺序不敏感，可选用基于网格的STING算法。(2)如果目标数据库比较大，建议使用综合性的聚类算法，如CURE等。(3)如果聚类的形状是球形或者凸形，BIRCH和CLARANS比较适合。(4)将不同类型的聚类算法相互结合以满足不同的聚类要求。 5 结束语 各种聚类算法各有优缺点，又由于实际问题的复杂性和数据的多样性，使得无论哪一种方法都只能解决某一类问题。因此，用户应该根据具体问题具体分析，选择恰当的适合自己的聚类算法。近年来，随着数据挖掘、机器学习和人工智能等领域中传统方法的不断发展以及各种新方法和新技术的涌现，聚类算法得到了长足的发展。不难发现其新趋势：(1)传统聚类方法的融合发展。(2)新方法不断涌现。(3)根据实际需要，有针对性地融合众多领域的技术。总之，聚类算法综合了数据挖掘、模式识别、数学等众多领域的研究成果。随着这些领域中相关理论的发展、完善和相互渗透，以及新技术的出现，聚类分析将得到更快的发展。 参考文献： 1 孙吉贵,刘杰,赵连宇.聚类算法研究J.软件学报,2008,19(1):9. 2 贺玲,吴玲达,蔡益朝.数据挖掘中的聚类算法综述J.计算机应用研究,20