5.1.3 聚类算法分类
随着人们对数据挖掘的深入研究和了解，各种聚类算法的改进算法也相继提出，很多新算法在前人提出的算法中做了某些方面的提高和改进，且很多算法是有针对性地为特定的领域而设计的。我们必须清楚地了解各种算法的优缺点和应用范围，根据实际问题选择合适的算法，聚类算法按照其原理可以分为以下九种。
（1）基于层次的聚类算法。
基于层次的聚类算法根据对给定数据对象进行层次上的分解，可分为凝聚算法和分裂算法。自底向上的凝聚聚类方法是以数据对象作为原子类，然后将这些原子类进行聚合，逐步聚合成越来越大的类，直到满足终止条件。凝聚算法的过程为：在初始时，每一个成员都组成一个单独的簇，在以后的迭代过程中，再把那些相互邻近的簇合并成一个簇，直到所有的成员组成一个簇为止。其时间和空间复杂度均为o（n2）。通过凝聚式的方法将两簇合并后，无法再将其分离到之前的状态。在凝聚聚类时，选择合适的类的个数和画出原始数据的图像很重要。
自顶向下的分裂聚类方法与凝聚聚类方法相反，该法先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件。其主要思想是将那些成员之间不是非常紧密的簇进行分裂。与凝聚聚类方法的方向相反，分裂聚类方法从一个簇出发，一步一步细化。它的优点在于研究者可以把注意力集中在数据的结构上面。一般情况下不使用分裂聚类方法，因为在较高的层很难进行正确的拆分。
（2）基于密度的聚类算法。
很多算法都使用距离来描述数据之间的相似性，但对于非凸数据集，只用距离来描述是不够的。此时可用密度来取代距离描述相似性，即基于密度的聚类算法。它不是基于各种各样的距离，所以能克服基于距离的算法只能发现“类圆形”的聚类的缺点。其指导思想是：只要一个区域中的点的密度（对象或数据点的数目）大过某个阈值，就把它加到与之相近的聚类中去。该法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可发现任意形状的簇，并可用来过滤“噪声”数据。常见算法有DBSCAN、DENCLUE等。
（3）基于划分的聚类算法。
给定一个N个对象的元组或数据库，根据给定要创建的划分的数目k，将数据划分为k个组，每个组表示一个簇类（k≤N）时满足如下两点：首先每个组至少包含一个对象；其次每个对象必须属于且只属于一个组。算法先随机创建一个初始划分，然后采用一种迭代的重定位技术，通过将对象根据簇类之间的差异从一个划分移到另一个划分来提高簇类中数据之间的相似程度。一种好的划分的一般准则是：在同一个类中的对象尽可能“接近”或相似，而不同类中的对象尽可能“远离”或不同。为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。典型的划分包括K-Means、PAM、EM等。划分法收敛速度快，在对中小规模的数据库中发现球状簇很有作用。其缺点是倾向于识别凸形分布大小相近、密度相近的聚类，不能发现分布形状比较复杂的聚类，它要求类别数目k能合理地估计，且初始中心的选择和噪声会对聚类结果产生很大影响。还要求用户预先指定聚类个数。
（4）基于网格的聚类算法。
首先将数据空间量化为有限个单元的网格结构，然后以量化后的单个的单元为对象进行聚类。典型的算法有STING、CLIQUE等。网格聚类法处理速度快，处理时间与数据对象的数目无关，一般由网格单元的数目决定。其缺点是只能发现边界是水平或垂直的聚类，不能检测到斜边界。该类算法也不适用于高维情况，因为网格单元的数目随着维数的增加而呈指数增长。另外还有以下问题：一是如何选择合适的单元大小和数目；二是怎样对每个单元中对象的信息进行汇总；三是存在量化尺度的问题。
（5）基于模型的聚类算法。
基于模型的聚类方法是给每一个聚簇假定了一个模型，然后去寻找能够很好满足这个模型的数据集。这个模型可能是数据点在空间中的密度分布函数，它由一系列的概率分布决定；也有可能通过基于标准的统计数字自动决定聚类的数目。它的一个潜在假定是：目标数据集是由一系列的概率分布所决定的。基于模型的聚类一般有两种解决方向：统计的方案和神经网络的方案。COBWEB是一种流行的简单增量概念聚类算法，以一个分类树的形式来创建层次聚类，它的输入对象用分类属性-值对来描述。COBWEB的优点是，可以自动修正划分中类的数目；不需要用户提供输入参数；缺点是，基于这样一个假设，即在每个属性上的概率分布是彼此独立的，但这个假设并不总是成立，且对于偏斜的输入数据不是高度平衡的，它可能导致时间和空间复杂度的剧烈变化，不适用于聚类大型数据库的数据。
（6）模糊聚类算法。
现实中很多对象没有严格的属性，其类别和形态存在着中介性，适合软划分。恰好模糊聚类具有描述样本类别中介性的优点，因此成为当今聚类分析研究的主流。常用的模糊聚类有动态直接聚类法、最大树法、FCM等。假设有N个要分析的样本，每个样本有M个可量化的指标，一般步骤为：①标准化数据，常用的数据标准化方法有小数定标规范化、最大最小值规范化、标准差规范化等；②建立模糊相似矩阵，标定相似系数；③计算相似矩阵，计算整体相似关系矩阵，常用计算方法有传递闭包法、动态直接聚类法、最大树法等；④给定一个聚类水平，计算绝对相似矩阵，按行列调整绝对相似矩阵，每个分块即为一个分类。(https://www.daowen.com)
（7）基于群的聚类方法。
该算法是进化计算的一个分支，模拟了生物界中蚁群、鱼群等在觅食或避敌时的行为，可分为蚁群算法ACO和PSO。蚁群聚类算法有许多特性，如灵活性、健壮性、分布性和自组织性等，非常适合本质上是分布、动态及又要交错的问题求解中，能解决无人监督的聚类问题，具有广阔的应用前景。PSO模拟了鱼群或鸟群的行为。在优化领域，PSO可以与遗传算法相媲美，并在预测精度和运行速度方面占优势。对ACO或PSO在数据挖掘中应用的研究仍处于早期阶段，要将这些方法用到实际的大规模数据挖掘的聚类分析中还需要做大量的研究工作。
（8）基于粒度的聚类方法。
从粒度的角度来看，我们会发现聚类和分类有很大的相通之处：聚类操作实际上是在一个统一粒度下进行计算的；分类操作是在不同粒度下进行的。所以说在粒度原理下，聚类和分类是相通的，很多分类的方法也可以用在聚类方法中。作为一个新的研究方向，虽然目前粒度计算还不成熟，尤其是对粒度计算语义的研究还相当少，但随着粒度理论的不断发展，今后几年它必将在聚类算法及其相关领域得到广泛的应用。
（9）谱聚类方法。
谱聚类方法建立在谱图理论基础之上，并利用数据的相似矩阵的特征向量进行聚类，是一种基于两点间相似关系的方法，这使得该方法适用于非测度空间。它与数据点的维数无关，而仅与数据点的个数有关，可以避免由特征向量的过高维数所造成的奇异性问题。它又是一个判别式算法，不用对数据的全局结构作假设，而是首先收集局部信息来表示两点属于同一类的可能性；然后根据某一聚类判据作全局决策，将所有数据点划分到不同的数据集合中。通常这样的判据可以在一个嵌入空间中得到解释，该嵌入空间是由数据矩阵的某几个特征向量组成的。谱聚类算法成功的原因在于：通过特征分解，可以获得聚类判据在连续域中的全局最优解。与其他算法相比，它不仅思想简单、易于实现、不易陷入局部最优解，而且具有识别非凸分布的聚类能力，非常适合于许多实际问题。目前，该算法已应用于语音识别、VLSI设计、文本挖掘等领域。
实际应用的复杂性和数据的多样性往往使得单一的算法无能为力。因此，很多人对多种算法的融合进行了广泛研究并取得了一些成果。多种算法的融合大致可分为以下几类：①基于传统聚类方法的融合，如CLIQUE、CUBN等；②模糊理论与其他聚类法的融合，如遗传算法+模糊C2均值混合聚类算法等；③遗传算法与机器学习的融合；④传统聚类方法与其他学科理论的融合，如谱算法等。总之，很多新算法是以上几类方法中两种或两种以上方法有机结合而得的，它们取长补短，优势明显，这也是数据挖掘研究人员要努力的研究方向之一。
聚类算法的研究具有广泛的应用前景，其今后的发展也会面临着越来越多的挑战。首先是聚类算法的选择，建议使用者根据实际情况（如发现聚类的形状、数据输入顺序是否敏感、适用数据库的大小或者算法效率）来选择合适的聚类算法。其次，对于特征数据本身所具备的高维性、复杂性、动态性以及容易达到大规模的特性，聚类算法的设计还应该更多地考虑融合不同的聚类思想形成新的聚类算法，从而综合利用不同聚类算法的优点。由以上可知，没有一种算法是十全十美的。在选择算法时，要根据具体情况而定，也可以结合多种算法使用。例如，通过发现聚类的形状、数据输入顺序是否敏感、适用数据库的大小或者算法效率，来选择聚类算法。
一般情况下有以下结论：
（1）目标数据库如果比较大，建议使用综合性的聚类算法，如BIRCH、CURE、DBSCAN和STING等，以提高算法效率。
（2）如果聚类的形状是球形或者凸形，BIRCH和CLARANS比较适合。
（3）一般而言，聚类算法对数据输入顺序都比较敏感。如果对数据输入顺序不敏感，可以选用基于网格的STING算法。
（4）将不同类型的聚类算法相互融合（如BIRCH算法和aURE算法融合），综合各自的优点，以满足不同的聚类要求，是今后聚类算法的一个重要发展方向。
总之，聚类分析是数据挖掘中一种非常有用的技术，它可作为特征和分类算法的预处理步骤，也可将聚类结果用于进一步关联分析，还可以作为一个独立的工具来获得数据分布的情况。