3.2　几种常用的聚类方法

一、系统聚类法

系统聚类法也称为分层聚类法，是目前在实际问题中应用最多的一类方法，是将类由多变少的一种方法。

1. 系统聚类的基本思想

设有n个样品，m个变量，设第i个样品，第j个变量的观测值为x_ij（i＝1，2，...，n；j＝1，2，...，m），构成的n×m阶矩阵为

，n个m元样品记为X_(i)（i＝1，2，...，n）。

设有n个样品，每个样品测得m项指标，系统聚类的基本思想是：首先定义样品间的距离（或相似系数）和类与类之间的距离。开始将n个样品看成n类，即每个样品看成一类，这时类之间的距离和样品之间的距离是等价的；然后将距离最近的两类合并成一个新的类，并计算该类和其他各类之间的距离，再按照“最小距离”原则合并类，这样每次缩小一类，直到所有的样品都合成一类为止（或变量间的）。

2. 系统聚类的基本步骤

第一步：数据变换。变换后的数据更方便比较和计算。选择合适的样品间的距离定义（如选择欧氏距离）及度量类之间的距离定义；

第二步：计算n个样品两两间的距离，得到样品间的距离矩阵D₀；

第三步：初始n个样品各自构成一类，类的个数k＝n，第i类G_i＝{X_（i）}（i＝1，2，...，n），此时类之间的距离就是样品之间的距离D₁＝D₀；

第四步：对得到的距离矩阵D₁，合并类间距离最小的两类为一个新类D₂，这时类的个数n减少一类；

第五步：计算新类和其他类之间的距离，得到新的距离矩阵；

第六步：不断重复上述过程。直到所有的数据都合并到一类为止；

第七步：画出谱系聚类图；

第八步：决定分类的个数及各类成员。

上面定义了几种距离的公式，按照每种距离的公式都可以得到一种系统聚类法。

例3.1　根据教育部网站公布的数据显示，截至2017年底，北京、天津、上海、福建、广东、西藏和青海几个省份的普通高校数量（包括本科院校和高职高专两类）分别为92所、57所、64所、89所、151所、7所和12所。根据高校数量对以上7个地区进行分类。

解：样品间的距离取平方欧氏距离，即两个地区高校数量差的绝对值。取该类中元素之间距离的最小值作为类之间的距离，根据系统聚类的步骤得：

（1）计算7个省市地区的普通高等学校数量差，由两两距离得到表3-2，由于对称性，只给出上三角的数据，以下步骤中也均按此样式给出。

对应的初始矩阵为D₀，距离矩阵D₀中各元素数值的大小就反映了7个省份间普通高等学校数量的差。

在开始的7类中，将普通高校数量差最小的北京和福建合并成一个新类，此时重新计算北京／福建这个新类和其他类的普通高校数量差，见表3-3。

由此得到距离矩阵D，。

由距离矩阵可知，青海和西藏两省的普通高校数量差为5，在当前各类中是最小的。将青海和西藏两省合并成一类，并重新计算新类中各地区的距离，得到表3-4。

由此得到矩阵距离矩阵D₂，。

由距离矩阵可知，天津和上海地区的普通高校数量差为7，在新的各类中是最小的。将天津和上海两类合并成一类，并重新计算新类中各地区的距离，得到表3-5。

由此得到距离矩阵D，。

由距离矩阵可知，北京／福建与天津／上海地区的普通高校数量差为25，在新的各类中是最小的。将北京／福建与天津／上海地区两类合并成一类，并重新计算新类中各地区的距离，得到表3-6。

由此得到矩阵距离矩阵D₄，。

由距离矩阵可知，西藏／青海与北京／福建／上海／天津地区的普通高校数量差为45，在新的各类中是最小的。将西藏／青海与北京／福建／上海／天津地区两类合并成一类，并重新计算新类中各地区的距离，得到表3-7。

由此得到矩阵距离矩阵D₅，，最后一步把所有的地区合并成一个类。

由上述合并过程得到的谱系聚类图如图3-1所示。其中1～7分别对应的是北京、天津、上海、福建、广东、西藏和青海各省份。

根据谱系图进行分类：

分成2类：G₁＝{北京，福建、天津、上海、西藏和青海}，G₂＝{广东}；

分成3类：G₁＝{北京，福建、天津、上海}，G₂＝{西藏、青海}；G₃＝{广东}；

分成4类：G₁＝{北京，福建}，G₂＝{天津、上海}；G₃＝{西藏和青海}，G₄＝{广东}；

分成5类：G₁＝{北京，福建}，G₂＝{天津}、G₃＝{上海}；G₄＝{西藏、青海}，G₅＝{广东}；

分成6类：G₁＝{北京，福建}，G₂＝{天津}；G₃＝{上海}；G₄＝{西藏}，G₅＝{青海}，G₆＝{广东}。

由该题目的含义可以得出，本题按照普通高校数量分成3类或4类比较合适。

在例3.1中，标度类与类之间距离的方法也称为最短距离法。采用最短距离法对样品进行分类时，类与类之间的距离是采用了所有元素中距离最短的作为类之间的距离，由于该种分类法对数据有链接聚合的趋势，因此在聚类中并不是普遍使用的方法。如果类与类之间距离采用最长距离法或其他度量距离的方法进行分类，结果与上述结果不一定相同。类与类之间常用的距离定义方法有以下几种：

3. 类与类之间距离的定义方法

用d_ij表示样品X_（i）和X_（j）的距离，样品的亲疏关系用相似系数C_ij表示，用D_ij表示类G_i和G_j之间的距离。

（1）最长距离法

类与类之间的距离定义为两类中相距最远的样品之间的距离：

在合并过程中，当类G_i和G_j合并成G_r以后，按照最长距离法计算新类G_r与其他类之间的距离。类似地可以定义，称为最短距离法。

（2）中间距离法

当某步骤类G_p和G_q合并成G_r以后，按照取中间距离的方法计算新类G_r与其他类之间的距离，递推公式：

常取。由几何知识可知，D_rk是以D_qk，D_pk，D_pq为边的三角形中D_pq边上的中线。

（3）重心法

上述三种定义距离的方法没有考虑每一类中包含样品的个数。将两类间的距离定义为两类重心间距离的方法称为重心法。实际上，每一类样品的重心就是该类样品的均值。

当某步骤类G_p和G_q合并成G_r以后，它们包含的样品数分别为n_p，n_q，n_r（n_r＝n_p＋n_q），各类的重心分别为，，，显然：

设某一类G_k（k≠p，q）的重心为，则它与新类G_r的距离为：。

如果样品间的距离取欧氏距离，代入后有：

如果样品间的距离不是取欧氏距离，则重心法可以导出不同的公式。

（4）类平均法

重心法虽然有很好的代表性，但并没有很充分地利用各样品的信息，因此又有人定义了两类样品两两之间平方距离的平均作为类之间的距离：

类平均法也是目前使用比较广泛、聚类效果比较好的一种聚类方法。当某步骤将类G_p和G_q合并成G_r以后，G_r＝{G_p，G_q}，且n_r＝n_p＋n_q，此时G_r和其他类G_k距离平方的递推公式为

此外，为了充分考虑两个类之间的距离及在新类中所占的比例，还有可变类平均法和可变法等聚类分析的方法。

（5）离差平方和法

离差平方和法是Ward于1936年提出来的，因此也称Ward法。Ward法是实际问题中应用比较广泛、分类效果较好的一类方法。它是基于方差分析的基本思想，认为合理的分类应该满足：同类样品之间的离差平方和应该比较小，不同类样品之间的离差平方和应该比较大。

基本思想是：先将n个样品每个样品分成一类，此时W＝0；然后每次将其中的某两类合并成一类，因为每缩小一类离差平方和就要增加，每次选择使W增加最小的两类合并，直到合并成一类为止。

假定已经将n个样品分成k类，记为G₁，G₂，...，G_k.令n_r表示G_t类的样品个数，表示G_t类第i个样品的重心，表示G_t类的第i个样品。此时G_t中样品的离差平方和为

其中，为m维向量，w_t为一数值t＝1，2，...，k。

k个类的总离差平方和为

当k固定时，要选择使W达到极小的分类。

样品间采用欧氏距离，当类G_p和G_q合并成G_r以后，G_r和其他类G_k之间的递推公式为：。

4. 系统聚类几种计算距离方法的统一

上述几种聚类方法的步骤完全相同，Lance和Williams给出了统一的公式：

上述不同的系统聚类方法就是参数α_p，α_q，β，γ取不同的值得到的。统一公式的给出，为计算机编程解决聚类问题提供了很大的方便。

例如，在最短距离中就是，，β＝0，；在离差平方和距离测算中就是，，，γ＝0。

5. 系统聚类分类数目的确定

聚类分析的目的就是研究对象的分类，如何选择分类的数目是一个重要问题。由于类的结构和内容很难给出一个统一的定义，因此分类的数目确定至今仍没有一个统一的标准。在实际问题中可以根据分类的阈值、样本值散点图、相关统计量的值再结合问题研究的目的和实际需要选择合适的分类数。

系统分类的分类数量没有统一的确定方法，Bemirmen于1972年提出了根据谱系图来进行分类的准则，也是目前进行分类数量确定主要准则。

准则1　任何类在临近的类中都应该是突出的，也就是各类重心之间的距离应该足够大；

准则2　各类所包含的元素个数不应该过多；

准则3　分类的数目符合实用的目的；

准则4　若采用不同的聚类方法进行处理，则在各自聚类的图上应该能够发现相同的类。

二、动态聚类法

系统聚类法一次形成类以后便不能改变，这就要求一次分类分得比较准确，对分类方法提出了较高的要求，相应的计算量也比较大。当样本容量很大时，需要占据足够大的计算机内存空间，而且在分类过程中，需要将每类样品和其他类样品之间的距离逐一加以比较，以此决定应该合并的类别。当数据量比较大时，分类需要较多的计算时间，同时要求支持计算的机器内存足够大。基于以上问题，产生了动态聚类的方法。基本步骤是：

1. 按照一定的原则选择一批凝聚点（聚核）；

2. 让样品向最近的凝聚点凝聚，这样就由点凝聚成类，得到初始分类；

3. 初始分类不一定合理，可按“最近距离”原则进行修改，直到分类合理得到最终的分类为止。

三、K-均值聚类法

K-均值聚类法也称为快速聚类法，是Macqueen于1967年提出的聚类方法，该种聚类方法中类的个数K预先给定或者在聚类过程中确定，是一种非谱系聚类的方法。该种聚类方法在解决数据量非常大的问题时，比系统聚类法有更大的优势。

K-均值聚类法的核心过程由三步组成：首先把样品粗略分成K个初始类；其次是对初始类进行修改，逐个分配样品到其最近均值的类中，重新计算接受新样品的类的均值；最后重复第二步的操作，直到各类元素均无元素进出为止。

K-均值聚类法最终聚类的结果在很大程度上依赖最初的划分。另外，如果指定了初始类的中心，系统只负责分类，不再更改初始类中心的位置，最终将每个样品数据都归类到各个初始中心。

该种归类方法因为在计算机计算过程中无须确定距离，也不需要存储数据，因此该种聚类方法的优点是占内存少、计算量小、处理速度快，特别适合大样本的聚类分析，缺点是要求用户指定分类的数目，并且只能对观测值进行聚类，不能对变量进行聚类分析。

四、有序样品的聚类

前面讨论的样品是相对独立的，分类时是彼此相等的。在实际问题中，还存在一种与顺序密切相关的问题，例如，要研究新中国成立以来的国民收入分成几个阶段的问题。阶段的划分必须以时间顺序进行。研究类似的问题，实际上是在给定的数据中找一些分点，将所有的数据分成几段，每段看成一类，这种分类的方法就是有序样品的分类。

在有序样品分类中，分点的位置不同就产生了不同的分类方法，每一种给出分点位置的方法称为一个分割。分类时希望分点位置达到最合适，这就是最优分割问题。也就是求一个分割满足：各段分割内部样品之间的差异最小，而不同段之间样品的差异明显大于内部样品的差异。

要想把n个有序样品分成k类，有序样品的分类结果要求每一类必须是相邻的元素组成，因此分类所有的可能为种，当n较大时，有序样品的分类可能性远远小于一般样品分类的总数。由此可见，有序样品的分类问题相对要简单一些。

这里介绍Fisher提出的被称为最优分割的算法。设X_（1），X_（2），...，X_（n）是n个有序样品，分成k类。最优分割的步骤：

第一步：定义类的直径：设某一类G_ij＝{X_（i），X_（i＋1），...，X_（j）}（j>i），为它们的均值，表示该类的直径。定义

用D（i，j）表示这类直径，常用的直径有：。

第二步：定义目标函数：将n个有序样品分成k类，定义该种分类的目标函数为各类的直径之和。显然当n和k固定时，目标函数的值越小，分类的方法越合理。

第三步：求出精确的最优解：对于固定的n，选择不同的k，就会得到不同的目标函数，选出目标函数最小的，就是最优解的分割方案。