2.2 聚类分析

聚类分析［1］划分对象的依据是“物以类聚”，即考察个体或数据对象间的相似性，满足相似性条件的个体或数据对象划分在一组内，不满足相似性条件的个体或数据对象划分在不同的组。聚类产生的每一个组称为一个类（cluster）。因为对象类划分的数量与类型在数据挖掘之前均是未知的，数据挖掘是一种典型的无监督分类，所以，在数据挖掘后对数据挖掘结果的合理分析与解释是很重要的。

根据聚类的原理，聚类分析方法主要分为五类，即分割聚类方法、层次聚类方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法（model-based clustering）［33，34］。下面分别介绍这几种聚类方法。

1.分割聚类方法

分割聚类方法（partitioning clustering method）也叫划分聚类方法，是一类经典聚类分析方法，是一种基于某种原型（prototype）的聚类方法。该方法根据某种规则初始划分所有对象，然后采用迭代的重定位技术，使数据对象在划分之间来回移动，实现最优划分，其划分标准是相似度或者差异度大小，使同一个类中的对象是“相似的”，不同类中的对象是“不同的”。

根据采用的原型的不同，分割聚类方法主要包括k-means［1］和k-medoid［3］两大类方法。

1967年，Mac Queen首次提出了k均值聚类方法（k-means方法），它是一种经典的基于划分的聚类方法，也是EM方法［35］的特例。

设对象个数为n，聚类个数为k，x_i（i=1，2，…，n）∈D，C_j（j=1，2，…，k）∈D，最常用的目标函数为

其中，在k-means方法中，z_j为C_j的中心；而在k-medoid方法中，z_j为C_j中离中心最近的一个对象。

1）k-means方法

该方法是以平均值（mean）作为类的“中心”的一种划分聚类方法。假设有n个对象需要分成k类，其中k为聚类的个数，其值需事先设定。该方法的步骤如下。

步骤1：任意选择k个数据对象分别作为k个类的初始原型或“中心”。关于初始对象的选择方法有很多，常用的如经验选择法、随机选择法、抽样法等。

步骤2：根据差异度最小的原则，找出与各个对象最为相似的类，并把各个对象分配到其相应的类中。

步骤3：重新计算所得每一个类的所有对象的平均值，并将该平均值替代原类的“中心”，成为其新的“中心”。

步骤4：再次根据差异度最小的原则，重新聚类。

步骤5：重复步骤3和步骤4，直到所有的聚类不再发生变化为止。

k-means方法能对大型数据集进行高效分类，其计算复杂度为O（tKmn），其中，t为迭代次数；K为聚类数；m为特征属性数；n为待分类的对象数；通常K、m、。但是该方法也具有不足之处，如通常会在获得一个局部最优值时该方法自行终止、仅适合对数值型数据的聚类，且该方法局限于聚类结果为凸形（即类为凸形）的数据集，等等。

2）k-medoid方法

k-medoid方法中各个类的原型或“中心”是“medoids”，同样，根据差异度最小的原则进行迭代聚类。

事实上，k-means方法中的“中心”是虚拟的，并不是某个确实存在的数据对象。因此，k-medoid方法与k-means方法的区别就在于类的原型的选择，也就是说，如何确定聚类的初始“中心”。假设有n个对象需要分成k类，而这k个类的近似中心就是上面提到的medoids，并且按照差异度最小的原则使聚类的质量达到最好的k个对象。

比较著名的k-medoid方法有PAM（partitioning around medoids）方法、CLARANS（clustering large applications based on randomized search）方法［37］和CLA（clustering large applications）方法［36］。

划分聚类方法有一定的局限性，如聚类的形状、大小和密度以及聚类数目等。同时，样本尺寸大小、数据集的规模和数据集中数据点分布的复杂形状，都会对聚类质量产生影响。

2.层次聚类方法

层次聚类方法（hierarchical clustering method）是对给定数据对象集合进行层次分解的方法。该方法是通过某种搜索模式，在不同的层次上对对象进行分组，形成一种树形的聚类结构。

根据搜索模式的不同，层次聚类方法可以分为两类，即“自顶向下（top-down）”分解型层次聚类法（divisive hierarchical clustering）和“自底向上（bottom-up）”聚结型层次聚类法（agglomerative hierarchical clustering）［38］。

一般来说，分割聚类方法需要结合一种迭代控制策略进行聚类，从而优化聚类的结果。与分割聚类方法相比，找到最佳的聚类结果并不是层次聚类方法的目标。

层次聚类方法的核心思想是相似度或者差异度与阈值的大小关系，将最相似的部分合并，或者是将最不相似的两个部分分类。如果合并最相似的部分，那么，从每一个对象作为一个类开始，逐层向上进行聚结层次聚类，直到满足预先设定的终止条件为止。例如，类的数目达到预定值，或者是最近的两个类之间的距离达到设定的阈值就进行合并。若分割最不相似的两个部分，从所有对象归属在唯一的一个类中开始，逐层向下分解，直到满足一些预定的条件，这便是分解型层次聚类法。两种方法的运算过程如图2-2所示。

图2-2 聚结型层次聚类和分解型层次聚类法的比较

在层次聚类方法中，判断各个类之间相似程度的依据通常是差异度值的大小。下面介绍常用两个类之间基于距离的差异度计算。

假设C_i和C_j是聚结过程中同一层次上的两个类，n_i和n_j分别是C_i和C_j两个类中的对象数目，且p（i）为C_i中的任意一个对象，p（j）为C_j中的任意一个对象，f_i为C_i中对象的平均值，f_j为C_j中对象的平均值，则

1）平均值距离

d_mean（C_i，C_j）=d（f_i，f_j）　　　　　　（2-2）

2）平均距离

3）最大距离

4）最小距离

传统的层次聚类方法中的聚结型层次聚类方法［如AGNES（agglomerative nesting）方法］和分解型层次聚类方法［如DIANA（divisive analysis）方法］都是经典层次聚类方法。

传统的层次聚类方法易于理解，使用简单。但是各个类的大小和其中对象分布形状同样会影响聚类的结果，在对象分布形状比较特殊的情况下，甚至可能会产生错误的聚类结果。

同时，层次聚类方法的时间复杂度较高。一般来说，聚结型层次聚类方法的空间复杂度为O（n），平均时间复杂度为O（n2logn），最坏的情况下，时间复杂度可以达到O（n3）。

层次聚类方法的另一个不足是：该方法终止条件不易确定，选择合并点或分解点比较困难。同时，由于每一次类的聚结或分解都是不可逆的，即当某一步骤的合并或分解过程完成，这个处理是不能被撤销的。而在某一步骤没有合理选择好合并或分解点的话，就会导致聚类质量的降低，即该方法没有良好的可伸缩性。

为了克服层次聚类方法的不足，研究者做了大量的研究工作，提出了很多方法来提高层次聚类的结果，其代表方法主要分为两类：一类方法是综合了层次凝聚和迭代的重定位方法，首先利用凝聚层次聚类方法进行聚类，然后运用重定位方法对结果重新分类，如BIRCH（balanced iterative reducing and clustering using hierarchies）方法［39］。另一类方法则是在每层聚类结果中，考虑了子聚类之间的互连性和相似性，如CURE（clustering using representatives）方法［40］、ROCK方法［41］和Chameleon方法［42］。

CURE方法是在1998年提出的聚结型层次聚类方法，可以用于处理大规模数据集。CURE方法的思想是：采用抽样和分割策略构成了有效的预聚类方案，在不影响聚类的质量的前提下，降低了需要处理的数据量，提高了该方法的效率。该方法不受对象分布形状的限制，能够处理其分布形状大小差别比较大的类，如球形、非球形及混合型等许多复杂形状的聚类，并且能够更灵活地处理异常值。但是，该方法对参数设置敏感，设置不同的参数值得到的聚类结果差别比较大。

1999年提出的ROCK方法属于聚结型层次聚类方法，被用来解决分类变量属性聚类问题。该方法的思想是：通过构筑一个稀疏图（sparse graph），采用互连度（interconnectivity）计算两个类之间的相似性。而互连度的计算则依赖于不同的类拥有的共同邻居（neighbor）的数目。

同年在ROCK方法的基础上提出了Chameleon方法。Chameleon方法采用互联度和接近度（closeness）来衡量两个类之间的相似性。该方法判断两个类之间的互联度和接近度与类的内部对象间的互联度和接近度是否高度关联。如果高度关联，则将这两个类进行合并。该方法具有处理不规则形状聚类的能力。

3.基于密度的聚类方法

基于密度的聚类方法（density-based clustering method）根据局部数据特征来识别类：只要临近区域的密度超过某个阈值，就继续执行聚类。在数据空间中，类是由低密度区域分割出来的高密度对象区域，而那些位于低密度区域中的数据点被视为噪声。

多数基于密度的聚类方法对形成的聚类形状没有限制，同时，对类中对象的分布也没有特别的要求。

基于密度的聚类方法一直以来都是研究的一个热点，取得了丰硕的研究成果，如1996年提出的经典的基于密度方法——DBSCAN（density-based spatial clustering of applications with noise）方法［43］及其相关的改进方法［44］、小波分析法——Wave Cluster方法［45］、DENCLUE（density-based clustering）方法［46］、基于网格方法——CLIQUE（clustering in quest）方法［47］和OPTICS（ordering points to identify the clustering structure）方法［48］等。事实上，小波分析法——Wave Cluster方法、DENCLUE方法和基于网格方法同时也是基于网格的聚类方法。

DBSCAN方法是经典密度聚类方法，其主要思想是：根据要求输入两个参数，即半径ε和对象的最小数目MinPts，如果一个对象在其半径为ε的邻域内包含的对象不少于MinPts个，那么在该区域内的对象都是密集的。DBSCAN方法中的类被看作一个按一定规则确定的最大密集区域。对于没有被包含在任何类中的对象，即存在于稀疏区域中的对象则被认为是噪声。DBSCAN方法具有不受聚类形状的限制、不受异常值的影响等优点。但是，该方法需要事先输入两个参数ε和MinPts，而且该方法对这两个参数非常敏感，合理设置这两个参数值往往十分困难。

OPTICS方法是在1999年提出来的，与DBSCAN方法不同的是：该方法并不明确地生成数据类，而是将对象根据密度进行排序，得到对象的内在聚类结构，通过图形显示对象的分布及内在联系。

1998年提出的DENCLUE方法运用密度分布函数通过识别密度吸因子（density attractor）方法进行聚类。密度吸因子是密度函数的局部极值点。该方法结果不受异常值的影响。

4.基于网格的聚类方法

基于网格的聚类方法（grid-based clustering method）是将数据空间划分成有限个单元（cell）的网格结构，所有的处理都是以单个的单元为对象的方法，所以，网格聚类方法也属于层次聚类方法。该方法的基本思想是：对于多维空间的网格，将每一维划分成区间，对网络进行编码并统计每个网格中的记录个数，每个网格用网格中心点作为代表点。判断每个网格中的记录是否小于异常点阈值并标记该网格为异常点。距离最远的两个非异常点网格代表两个初始类，判断其他未被分类的非异常点网格与距离最近的现有类的代表网格之间的距离是否小于聚类阈值：如果网格之间的距离小于聚类阈值，则将该网格分配到对应类中；否则将该网格标记为一新类，一直迭代至所有网格分类完毕。

经典的网格聚类方法有CLIQUE（clustering in quest）方法［53］、BANG（balanced and nested grid）方法［54］、Wave Cluster方法和STING（statistical information grid）方法［55］。

CLIQUE方法是一种适用于高维数据的聚类方法。针对高维空间数据集，该方法采用了子空间的概念来进行聚类，该方法的主要思想是：如果一个k维数据区域是密集的，那么其在（k-1）维空间上的投影也一定是密集的。所以，可以通过寻找（k-1）维空间上的密集区来确定k维空间上的候选密集区，从而大大降低了需要搜索的数据空间。CLIQUE方法适用于处理高维数据，也可应用于大数据集。另外，该方法还给出了用户易于理解的聚类结果最小表达式。

这类方法的主要优点是，处理速度快，有利于并行处理和增量更新。其缺点是，聚类结果的精确度不高，且网格聚类方法中网格划分的大小直接影响聚类质量，如网格划分太粗糙，会造成不同聚类的对象被划分到同一个单元的可能性增加；相反，划分太细致，会得到很多小的聚类，因此如何找到合适的网格大小提高聚类的质量一直都是基于网格的聚类方法的目标。

5.基于模型的聚类方法

基于模型的聚类方法给每一个聚类假定一个模型，然后在数据集中寻找能够很好地满足这个模型的对象。这个模型可能是数据点在空间中的密度分布函数，它由一系列的概率分布决定。基于模型的方法有两类，即统计学方法［56］和神经网络方法［57］。

6.聚类有效性

聚类有效性（cluster validity）通常是指对聚类方法结果进行量化评价的方法［49］。随着研究不断深入，研究者提出了一系列聚类有效性评价指数［50，51］。聚类有效性指数是以一个定量的、客观的函数值来评价聚类结果的。其主要应用包括两个方面：如果聚类的数目是事先知道的，聚类的有效性对比不同的聚类方法得到不同的聚类结果；如果聚类数目事先是不知道的，为了选取数据集最佳的聚类数目，通常需要对比不同聚类数目条件下聚类结果之间的差异。

总的来说，评价一个聚类方法的结果从计算方法上大致可以有三大类，即内部评价准则、外部准则及相对评价准则［52］。

（1）外部准则

外部准则通过分析对比聚类方法产生的结果与数据集“真实”的分类情况，评估聚类方法的有效性，即每个数据点的正确分类为已知，在已有基准参考的基础上设计聚类分析的评价函数。在这种情况下忽略聚类的期望特征，而只是关心聚类所得结果相对于已有分类标准的有效性。其主要方法包括纯净度、聚类熵和F-measure。

从20世纪70年代开始就出现了许多著名的准则，这其中包括聚类错误（Clustering Error，CE）、Wallance indices、Rand Index（RI）、Fowlkes-Mallowsindex和Jaccard index等［62］。外部评价指标还包括在分类研究中常用的F1和Recall准则。

由于这些准则通常在没有考虑类所处空间的情况下对比数据点划分的差异，因此，有效性相对低些。针对这种情况，Patrikainen［52］扩展了CE等用于比较子空间聚类的结果。

（2）内部评价准则

在处理的数据集的结构未知、不能依据外部提供的标准信息来评价的情况下，则选用内部评价准则。这时聚类结果的质量评价依赖自身的特征属性，如类内方差，即类内数据点距离误差平方和，k-means方法的局部最优度量就是基于此概念提出的。

因内部准则和外部准则都是基于统计信息的，计算的复杂度较高。

（3）相对评价准则

相对评价准则是基于不同聚类选项的，在同一数据集上以不同的聚类选项和参数多次执行一个或多个聚类方法，目的是发现这些不同的聚类选项和参数下具有最佳质量的聚类结果。相对评价准则的重要部分是有效性指数（validity index），包括SD有效性指数和Dunn指数两种。其中，Dunn指数被用来度量类距离与类直径之间的比例。

相对评价准则使用的方法主要包括聚类融合（clustering ensemble）［53］、元聚类（metaclu stering）［54］等。

一般来说，每个聚类中的目标尽量“相似”或“接近”，而不同组的目标尽可能“相异”或“远离”。所以，通常衡量一个聚类方法产生结果的好坏的指标主要有两个，即类内紧凑度（compactness）和类间分离度（separaaon）。

类内紧凑度，指每一个类中的对象成员应该尽可能地紧凑。常用的紧密性衡量方法是方差。

类间分离度，指不同的类之间应该很好地被分开。实际应用中主要有三种方法来衡量两个类之间的距离，即最近对象距离、最远对象距离以及类中心距离。