聚类算法综述

王玉晗 罗邓三郎

摘 要：在数据挖掘中，聚类有着非常重要的地位。本文分别介绍了基于划分、基于层次、基于密度、基于网格和基于模型的聚类方法。对这五类聚类方法中的典型算法的聚类思想和特点做了相应的介绍，并分析了算法的优缺点，对聚类算法做了初步的总结。在具体问题的应用中，需多方面考虑算法的特性才能得到最佳聚类结果。

关键词：数据挖掘 聚类 密度 模型

中图分类号：G71 文献标识码：A 文章编号：1672-3791（2018）08（c）-0010-02

随着科技的发展，目前已步入大数据的时代，数据中包含的信息具有很高的价值。通过聚类分析，数据对象被划分为具有现实意义的组（集群），有助于人类分析和描述世界。聚类分析在心理学研究中、生物学研究中和模式识别以及数据挖掘等领域中都起着重要的作用。

聚类分析仅通过描述对象和其关系的数据信息，期望将对象划分为多个组，使得组内对象相似，组间对象不同。聚类的定义最早由Everitt在1974年提出，要求组内对象在空间中相对紧凑，组内任意两对象间的距离小于不同组的任意两对象间的距离。在实际应用中，聚类的定义通常不精确，最优的定义取决于聚类对象的性质和期望得到的结果。

根据聚类算法中对象间相似度的计算方式以及聚类结果中对象的关系可以将聚类算法分为划分法、层次法、基于密度的方法、基于网格的方法、基于模型的方法[1]。

1 聚类方法

1.1 基于划分的聚类方法

基于划分的聚类方法只是将数据对象集合划分为若干个无交集的子集（簇），使得每个对象仅属于一个子集。主要包括K-Means算法、K-modes算法、PAM算法和CLARA算法等。

K-Means算法是一个基于原型的划分聚类算法，通过对象间的距离评价对象间的相似度，距离越近，对象间相似度越大，反之则越小。用户需要预先指定需要划分的簇数k和每簇質心的初值，其思想如下：先选取k个数据作为k个簇的质心，计算数据集中每个对象到质心的距离，按照距离将其归类，完成后重新计算每个簇的质心，直到聚类结果不再发生变化为止。K-Means聚类算法的优点主要为算法运算快速且简单，对于数据较多的数据集有较高的聚类效率，具有可伸缩性。确定质心初值的主要方法有：（1）根据数据对象的性质和分布凭主观经验选取。（2）将数据对象随机分成k类，把每类的重心作为质心初值。（3）按密度大小选取质心初值。聚类结果对质心初值的选择敏感，选用不同质心初值可能得到不同的结果。数据集中的噪点和孤立点也会影响K-Means算法的聚类结果。

1.2 基于层次的聚类方法

层次聚类把数据对象构建成一组具有树状结构的嵌套簇，除了叶子节点的每个簇都是由其子节点（子簇）的并集构成，根节点包含所有的数据对象。根据层次分解的过程一般分为两类：（1）凝聚。从仅包含单个数据对象的簇开始，每次合并最接近的一对簇，直至簇中包含所有数据对象为止。（2）分裂。从一个包含所有数据对象的簇开始，每次对簇进行分割，直至簇中仅包含一个数据对象为止。树状图是层次聚类结果常用的表示方式。层次聚类方法主要包括单链接聚类、CURE算法、BIRCH算法和ROCK算法等。

单链接聚类基于自底向上方式对数据对象进行分类，在聚类过程的开始，每个元素都在自己的簇中。然后通过最短距离将这些簇依次组合成较大的簇，直到簇中包含所有的数据对象。CURE是针对大小相似的数据集和球形数据集的一种改进算法，其思想为一个簇由其中多个数据对象表示，每个簇对应多于一个的对象。这种策略使得CURE算法可以适应非球形的几何形状，并且能利用簇的收缩或凝聚控制孤立点的影响[2]。BIRCH是一种针对大规模数据集的聚类算法，通过聚类特征和聚类特征树，利用各个簇之间的距离，通过迭代的方法对数据集进行聚类[3]。ROCK算法是一种鲁棒的聚类算法，在确认两个数据的分类时考虑了它们邻居的数量，适用于类别型数据，如关键字、布尔值和枚举值等。

1.3 基于密度的聚类方法

基于密度的聚类方法是根基数据集密度的大小将数据集分类成簇，密度高的区域聚类成簇，密度低的区域作为噪声和孤立点处理，适用于空间中任意形状的簇，具有很强的抗噪能力。DBSCAN算法是经典的基于密度的聚类算法。其核心思想为：预先设置距离阈值和密度阈值，将数据对象都标记为核心点，任意数据对象由距离阈值确定的范围内不存在核心点，则将其视为噪声点消除。确定出每个距离阈值内的所有满足密度阈值的核心点的边界点，并把每一组连接的核心点分为一个簇，最后将边界点分配给相关核心点的簇。其优点有：可以自动确定聚类数量；对任意形状的簇都适用；对数据异常点不敏感。缺点为需要设置距离和密度阈值，处理空间分布稀疏的数据对象时难以得到满意的聚类结果，时间复杂度比K-Means算法高。

1.4 基于网格的聚类方法

基于网格的聚类方法把原数据对象空间划分成独立于输入对象分布的单元。通过构建父级子级网格单元关系形成一种多分辨率的网络数据结构，将连续空间离散化成有限数目的单元，利用所形成的网格结构进行聚类。该方法仅依赖于离散化后空间中的每一维的单元数，处理速度不受原数据大小的影响。STING是典型基于网格的聚类算法。在构建的层次结构实中，每个上层的结构单元都在下一层被划分为多个下层的结构单元。在聚类时，每个网格单元的统计信息会被预先计算和储存，相连高密度的网格单元判断为簇。STING算法基于网格结构，其算法效率高有利于增量更新和并行处理[4]，但在构建父级单元时没有考虑子级单元和相邻单元之间的联系，无法得到精确簇间边界，同时聚类精度会受到网格粒度的影响，聚类精度随粒度减小而提高，处理时间随之增加。

1.5 基于模型的聚类方法

基于模型的聚类算法需要为数据对象中的可能存在的每一簇构建一个分布模型，并假设数据对象均独立分布，通过数据对象的真实分布计算模型参数，最后利用所得模型完成聚类。基于模型的方法主要包括统计学和网络神经方法，其中统计学方法有COBWEB算法；网络神经方法有SOM算法[5]。基于模型的聚类方法通常以概率的形式对簇进行划分，易于理解，但是算法的执行效率并不高，同时假设条件不一定成立，对聚类结果也造成一定影响。

2 结语

本文介绍了基于5种聚类方法，主要介绍了其中具有代表性的算法K-Means、CURE、DBScan、STING算法和基于模型的聚类方法。分析了各类算法的特点和特性，对于不同的问题应采用不同的聚类算法。在实际应用中，需要结合算法的优缺点选择合适的算法才能获得理想的聚类效果。

参考文献

[1] 陈建娇.高维数据的K-harmonic Means聚类方法及其应用研究[D].上海大学，2012.

[2] 周迎春，骆嘉伟.基于分层的平衡迭代规约聚类分析算法研究[J].科学技术与工程，2008，8（10）：2579-2584.

[3] 陈绍彬，叶飞跃，刘佰强，等.食品HACCP分类的BIRCH算法[J].计算机工程，2008，34（23）：59-61.

[4] 杨静.分层模糊最小-最大聚类算法及其在图像聚类中的应用研究[D].合肥工业大学，2007.

[5] 冉延平，余昭平，贾利新，等.基于混合模型的聚类算法研究[J].河南科学，2005，23（3）：324-327.