聚类分析(一):层次聚类算法

本篇文章为讲述聚类算法的第一篇文章,其它相关文章请参见 聚类分析系列文章

聚类算法综述

聚类分析(clustering analysis)是将一组对象根据其特征分成不同的 cluster,使得同一 cluster 内的对象在某种意义上比不同的 cluster 之间的对象更为相似。

由于 “cluster” 没有一个明确的定义,因而会有基于不同的模型的聚类算法,其中被广泛运用的聚类算法有以下几类:

  • 基于连通模型(connectivity-based)的聚类算法: 即本文将要讲述的层次聚类算法,其核心思想是按照对象之间的距离来聚类,两个离的近的对象要比两个离的远的对象更有可能属于同一 cluster
  • 基于中心点模型(centroid-based)的聚类算法: 在此类算法中,每个 cluster 都维持一个中心点(centorid),该中心点不一定属于给定的数据集。当预先指定聚类数目 k 时,此类算法需要解决一个优化问题,目标函数为所有的对象距其所属的 cluster 的中心点的距离的平方和,优化变量为每个 cluster 的中心点以及每个对象属于哪个 cluster;此优化问题被证明是 NP-hard 的,但有一些迭代算法可以找到近似解,k-means 算法 即是其中的一种。
  • 基于分布模型(distribution-based)的聚类算法: 此类算法认为数据集中的数据是由一种混合概率模型所采样得到的,因而只要将可能属于同一概率分布所产生的数据归为同一 cluster 即可,最常被使用的此类算法为 高斯混合模型(GMM)聚类
  • 基于密度(density-based)的聚类算法: 在此类算法中,密度高的区域被归为一个 clustercluster 之间由密度低的区域隔开,密度低的区域中的点被认为是噪声 (noise),常用的密度聚类算法为 DBSCAN 和 OPTICS。

层次聚类综述

层次聚类算法 (hierarchical clustering) 将数据集划分为一层一层的 clusters,后面一层生成的 clusters 基于前面一层的结果。层次聚类算法一般分为两类:

  • Agglomerative 层次聚类:又称自底向上(bottom-up)的层次聚类,每一个对象最开始都是一个 cluster,每次按一定的准则将最相近的两个 cluster 合并生成一个新的 cluster,如此往复,直至最终所有的对象都属于一个 cluster。本文主要关注此类算法。
  • Divisive 层次聚类: 又称自顶向下(top-down)的层次聚类,最开始所有的对象均属于一个 cluster,每次按一定的准则将某个 cluster 划分为多个 cluster,如此往复,直至每个对象均是一个 cluster

下图直观的给出了层次聚类的思想以及以上两种聚类策略的异同。

另外,需指出的是,层次聚类算法是一种贪心算法(greedy algorithm),因其每一次合并或划分都是基于某种局部最优的选择。

树形图

树形图 (dendrogram)可以用来直观地表示层次聚类的成果。一个有 5 个点的树形图如下图所示,其中纵坐标高度表示不同的 cluster 之间的距离(“距离”的衡量准则可以多种多样,详见本文后面的定义),可以从这张图看到,$ x_1 $ 和 $ x_2 $ 的距离最近(为 1),因此将 $ x_1 $ 和 $ x_2 $ 合并为一个 cluster $ (x_1, x_2) $,所以在树形图中首先将节点 $ x_1 $ 和 $ x_2 $ 连接,使其成为一个新的节点 $ (x_1, x_2) $ 的子节点,并将这个新的节点的高度置为 1;之后再在剩下的 4cluster $ (x_1, x_2) $, $ x_3 $, $ x_4 $ 和 $ x_5 $ 中选取距离最近的两个 cluster 合并,$ x_4 $ 和 $ x_5 $ 的距离最近(为 2),因此将 $ x_4 $ 和 $ x_5 $ 合并为一个 cluster $ (x_4, x_5) $,体现在树形图上,是将节点 $ x_4 $ 和 $ x_5 $ 连接,使其成为一个新的节点 $ (x_4, x_5) $ 的子节点,并将此新节点的高度置为 2;….依此模式进行树形图的生成,直至最终只剩下一个 cluster $ ((x_1, x_2), x_3), (x_4, x_5)) $。

可以直观地看到,如果我们想得到一个聚类结果,使任意的两个 cluster 之间的距离都不大于 $ h $,我们只要在树形图上作一条水平的直线对其进行切割,使其纵坐标等于 $ h $,即可获得对应的聚类结果。例如,在下面的树形图中,设 $ h=2.5 $,即可得到 3cluster $ (x_1, x_2) $, $ x_3 $ 和 $ (x_4, x_5) $。

树形图示例

对象之间的距离衡量

衡量两个对象之间的距离的方式有多种,对于数值类型(Numerical)的数据,常用的距离衡量准则有 Euclidean 距离、Manhattan 距离、Chebyshev 距离、Minkowski 距离等等。对于 $ d $ 维空间的两个对象 ${\bf x} =[ x_1, x_2, …, x_d]^{T} $ 和 ${\bf y} = [y_1, y_2, …, y_d]^{T}$,其在不同距离准则下的距离计算方法如下表所示:

距离准则 距离计算方法
Euclidean 距离 $ d({\bf x},{\bf y}) = [\sum_{j=1}^{d} (x_j-y_j)^{2} ]^{\frac{1}{2}} = [({\bf x} - {\bf y})^{T} ({\bf x} - {\bf y})]^{\frac{1}{2}} $
Manhattan 距离 $ d({\bf x},{\bf y}) = \sum_{j=1}^{d} \mid{x_j-y_j}\mid $
Chebyshev 距离 $ d({\bf x},{\bf y}) = \max_{1\leq{j}\leq{d}} \mid{x_j-y_j}\mid $
Minkowski 距离 $ d({\bf x},{\bf y}) = [\sum_{j=1}^{d} (x_j-y_j)^{p} ]^{\frac{1}{p}}, p\geq{1} $

Minkowski 距离就是 $ \rm{L}\it{p}$ 范数($ p\geq{1} $),而 Manhattan 距离、Euclidean 距离、Chebyshev 距离分别对应 $ p = 1, 2, \infty $ 时的情形。

另一种常用的距离是 Maholanobis 距离,其定义如下:

其中 $ \Sigma $ 为数据集的协方差矩阵,为给出协方差矩阵的定义,我们先给出数据集的一些设定,假设数据集为 $ {\bf{X}} = ({\bf x}_1, {\bf x}_2, …, {\bf x}_n) \in \Bbb{R}^{d \times n}$,$ {\bf x}_i \in \Bbb{R}^{d} $ 为第 $ i $ 个样本点,每个样本点的维度为 $ d $,样本点的总数为 $ n $ 个;再假设样本点的平均值 $ m_{\bf x} = \frac{1}{n}\sum_{i=1}^{n} {\bf x}_i $ 为 $ {\bf 0} $ 向量(若不为 $ {\bf 0} $,我们总可以将每个样本都减去数据集的平均值以得到符合要求的数据集),则协方差矩阵 $ \Sigma \in \Bbb{R}^{d \times d} $ 可被定义为

Maholanobis 距离不同于 Minkowski 距离,后者衡量的是两个对象之间的绝对距离,其值不受数据集的整体分布情况的影响;而 Maholanobis 距离则衡量的是将两个对象置于整个数据集这个大环境中的一个相异程度,两个绝对距离较大的对象在一个分布比较分散的数据集中的 Maholanobis 距离有可能会比两个绝对距离较小的对象在一个分布比较密集的数据集中的 Maholanobis 距离更小。更细致地来讲,Maholanobis 距离是这样计算得出的:先对数据进行主成分分析,提取出互不相干的特征,然后再将要计算的对象在这些特征上进行投影得到一个新的数据,再在这些新的数据之间计算一个加权的 Euclidean 距离,每个特征上的权重与该特征在数据集上的方差成反比。由这些去相干以及归一化的操作,我们可以看到,对数据进行任意的可逆变换,Maholanobis 距离都保持不变。

Cluster 之间的距离衡量

除了需要衡量对象之间的距离之外,层次聚类算法还需要衡量 cluster 之间的距离,常见的 cluster 之间的衡量方法有 Single-link 方法、Complete-link 方法、UPGMA(Unweighted Pair Group Method using arithmetic Averages)方法、WPGMA(Weighted Pair Group Method using arithmetic Averages)方法、Centroid 方法(又称 UPGMC,Unweighted Pair Group Method using Centroids)、Median 方法(又称 WPGMC,weighted Pair Group Method using Centroids)、Ward 方法。前面四种方法是基于图的,因为在这些方法里面,cluster 是由样本点或一些子 cluster (这些样本点或子 cluster 之间的距离关系被记录下来,可认为是图的连通边)所表示的;后三种方法是基于几何方法的(因而其对象间的距离计算方式一般选用 Euclidean 距离),因为它们都是用一个中心点来代表一个 cluster 。假设 $ C_i $ 和 $ C_j $ 为两个 cluster,则前四种方法定义的 $ C_i $ 和 $ C_j $ 之间的距离如下表所示:

方法 定义
Single-link $ D(C_i, C_j) = \min_{ {\bf x} \in C_i, {\bf y} \in C_j } d({\bf x}, {\bf y}) $
Complete-link $ D(C_i, C_j) = \max_{ {\bf x} \in C_i, {\bf y} \in C_j} d({\bf x}, {\bf y}) $
UPGMA $ D(C_i, C_j) = \frac{1}{\mid C_i \mid \mid C_j \mid} \sum_ { {\bf x} \in C_i, {\bf y} \in C_j} d({\bf x}, {\bf y}) $
WPGMA omitting

其中 Single-link 定义两个 cluster 之间的距离为两个 cluster 之间距离最近的两个对象间的距离,这样在聚类的过程中就可能出现链式效应,即有可能聚出长条形状的 cluster;而 Complete-link 则定义两个 cluster 之间的距离为两个 cluster 之间距离最远的两个对象间的距离,这样虽然避免了链式效应,但其对异常样本点(不符合数据集的整体分布的噪声点)却非常敏感,容易产生不合理的聚类;UPGMA 正好是 Single-link 和 Complete-link 的一个折中,其定义两个 cluster 之间的距离为两个 cluster 之间两个对象间的距离的平均值;而 WPGMA 则计算的是两个 cluster 之间两个对象之间的距离的加权平均值,加权的目的是为了使两个 cluster 对距离的计算的影响在同一层次上,而不受 cluster 大小的影响(其计算方法这里没有给出,因为在运行层次聚类算法时,我们并不会直接通过样本点之间的距离之间计算两个 cluster 之间的距离,而是通过已有的 cluster 之间的距离来计算合并后的新的 cluster 和剩余 cluster 之间的距离,这种计算方法将由下一部分中的 Lance-Williams 方法给出)。

Centroid/UPGMC 方法给每一个 cluster 计算一个质心,两个 cluster 之间的距离即为对应的两个质心之间的距离,一般计算方法如下:

当上式中的 $ d(.,.) $ 为平方 Euclidean 距离时,$ D_{\rm{UPGMC}}(C_i, C_j) $ 为 $ C_i $ 和 $ C_j $ 的中心点(每个 cluster 内所有样本点之间的平均值)之间的平方 Euclidean 距离。

Median/WPGMC 方法为每个 cluster 计算质心时,引入了权重。

Ward 方法提出的动机是最小化每次合并时的信息损失,具体地,其对每一个 cluster 定义了一个 ESS (Error Sum of Squares)量作为衡量信息损失的准则,cluster $ C $ 的 $ {\rm ESS} $ 定义如下:

其中 $ m_{\bf x} $ 为 $ C $ 中样本点的均值。可以看到 $ {\rm ESS} $ 衡量的是一个 cluster 内的样本点的聚合程度,样本点越聚合,$ {\rm ESS} $ 的值越小。Ward 方法则是希望找到一种合并方式,使得合并后产生的新的一系列的 cluster 的 $ {\rm ESS} $ 之和相对于合并前的 cluster 的 $ {\rm ESS} $ 之和的增长最小。


Agglomerative 层次聚类算法

这里总结有关 Agglomerative 层次聚类算法的内容,包括最简单的算法以及用于迭代计算两个 cluster 之间的距离的 Lance-Williams 方法。

Lance-Williams 方法

在 Agglomerative 层次聚类算法中,一个迭代过程通常包含将两个 cluster 合并为一个新的 cluster,然后再计算这个新的 cluster 与其他当前未被合并的 cluster 之间的距离,而 Lance-Williams 方法提供了一个通项公式,使得其对不同的 cluster 距离衡量方法都适用。具体地,对于三个 cluster $ C_k $,$ C_i $ 和 $ C_j $, Lance-Williams 给出的 $ C_k $ 与 $ C_i $ 和 $ C_j $ 合并后的新 cluster 之间的距离的计算方法如下式所示:

其中,$ \alpha_i $,$ \alpha_j $,$ \beta $,$ \gamma $ 均为参数,随 cluster 之间的距离计算方法的不同而不同,具体总结为下表(注:$ n_i $ 为 cluster $ C_i $ 中的样本点的个数):

方法 参数 $ \alpha_i $ 参数 $ \alpha_j $ 参数 $ \beta $ 参数 $ \gamma $
Single-link $ 1/2 $ $ 1/2 $ $ 0 $ $ -1/2 $
Complete-link $ 1/2 $ $ 1/2 $ $ 0 $ $ 1/2 $
UPGMA $ n_i/(n_i + n_j) $ $ n_j/(n_i + n_j) $ $ 0 $ $ 0 $
WPGMA $ 1/2 $ $ 1/2 $ $ 0 $ $ 0 $
UPGMC $ n_i/(n_i + n_j) $ $ n_j/(n_i + n_j) $ $ n_{i}n_{j}/(n_i + n_j)^{2} $ $ 0 $
WPGMC $ 1/2 $ $ 1/2 $ $ 1/4 $ $ 0 $
Ward $ (n_k + n_i)/(n_i + n_j + n_k) $ $ (n_k + n_j)/(n_i + n_j + n_k) $ $ n_k/(n_i + n_j + n_k) $ $ 0 $

其中 Ward 方法的参数仅适用于当样本点之间的距离衡量准则为平方 Euclidean 距离时,其他方法的参数适用范围则没有限制。

Naive 算法

给定数据集 $ {\bf{X}} = ({\bf x}_1, {\bf x}_2, …, {\bf x}_n) $,Agglomerative 层次聚类最简单的实现方法分为以下几步:

  1. 初始时每个样本为一个 cluster,计算距离矩阵 $ \bf D $,其中元素 $ D_{ij} $ 为样本点 $ {\bf x}_i $ 和 $ {\bf x}_j $ 之间的距离;
  2. 遍历距离矩阵 $ \bf D $,找出其中的最小距离(对角线上的除外),并由此得到拥有最小距离的两个 cluster 的编号,将这两个 cluster 合并为一个新的 cluster 并依据 Lance-Williams 方法更新距离矩阵 $ \bf D $ (删除这两个 cluster 对应的行和列,并把由新 cluster 所算出来的距离向量插入 $ \bf D $ 中),存储本次合并的相关信息;
  3. 重复 2 的过程,直至最终只剩下一个 cluster

当然,其中的一些细节这里都没有给出,比如,我们需要设计一些合适的数据结构来存储层次聚类的过程,以便于我们可以根据距离阈值或期待的聚类个数得到对应的聚类结果。

可以看到,该 Naive 算法的时间复杂度为 $ O(n^3) $ (由于每次合并两个 cluster 时都要遍历大小为 $ O(n^2) $ 的距离矩阵来搜索最小距离,而这样的操作需要进行 $ n - 1 $ 次),空间复杂度为 $ O(n^2) $ (由于要存储距离矩阵)。

当然,还有一些更高效的算法,它们用到了特殊设计的数据结构或者一些图论算法,是的时间复杂度降低到 $ O(n^2 ) $ 或更低,例如 SLINK 算法(Single-link 方法),CLINK 算法(Complete-link 方法),BIRCH 算法(适用于 Euclidean 距离准则)等等。


利用 Scipy 实现层次聚类

在这里我们将利用 SciPy(python 中的一个用于数值分析和科学计算的第三方包,功能强大,NumPy+SciPy+matplotlib 基本等同于 Matlab)中的层次聚类模块来做一些相关的实验。

生成实验样本集

首先,我们需要导入相关的模块,代码如下所示:

1
2
3
4
5
# python 3.6
>>> import numpy as np
>>> from scipy.cluster.hierarchy import linkage, dendrogram, fcluster
>>> from sklearn.datasets.samples_generator import make_blobs
>>> import matplotlib.pyplot as plt

其中 make_blobs 函数是 python 中的一个第三方机器学习库 scikit-learn 所提供的一个生成指定个数的高斯 cluster 的函数,非常适合用于聚类算法的简单实验,我们用该函数生成实验样本集,生成的样本集 X 的维度为 n*d

1
2
3
4
5
6
7
>>> centers = [[1, 1], [-1, -1], [1, -1]] # 定义 3 个中心点
# 生成 n=750 个样本,每个样本的特征个数为 d=2,并返回每个样本的真实类别
>>> X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4, random_state=0
>>> plt.figure(figsize=(10, 8))
>>> plt.scatter(X[:, 0], X[:, 1], c='b')
>>> plt.title('The dataset')
>>> plt.show()

样本的分布如下图所示。

数据集分布图

进行 Agglomerative 层次聚类

SciPy 里面进行层次聚类非常简单,直接调用 linkage 函数,一行代码即可搞定。

1
>>> Z = linkage(X, method='ward', metric='euclidean')

以上即进行了一次 cluster 间距离衡量方法为 Ward、样本间距离衡量准则为 Euclidean 距离的 Agglomerative 层次聚类;其中 method 参数可以为 'single''complete''average''weighted''centroid''median''ward' 中的一种,分别对应我们前面讲到的 Single-link、Complete-link、UPGMA、WPGMA、UPGMC、WPGMC、Ward 方法;而样本间的距离衡量准则也可以由 metric 参数调整。

linkage 函数的返回值 Z 为一个维度 (n-1)*4 的矩阵, 记录的是层次聚类每一次的合并信息,里面的 4 个值分别对应合并的两个 cluster 的序号、两个 cluster 之间的距离以及本次合并后产生的新的 cluster 所包含的样本点的个数;具体地,对于第 i 次迭代(对应 Z 的第 i 行),序号为 Z[i, 0] 和序号为 Z[i, 1]cluster 合并产生新的 cluster n + i, Z[i, 2] 为序号为 Z[i, 0] 和序号为 Z[i, 1]cluster 之间的距离,合并后的 cluster 包含 Z[i, 3] 个样本点。

例如本次实验中 Z 记录到的前 25 次合并的信息如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
>>> print(Z.shape)
(749, 4)
>>> print(Z[: 25])
[[253. 491. 0.00185 2. ]
[452. 696. 0.00283 2. ]
[ 70. 334. 0.00374 2. ]
[237. 709. 0.00378 2. ]
[244. 589. 0.00423 2. ]
[141. 550. 0.00424 2. ]
[195. 672. 0.00431 2. ]
[ 71. 102. 0.00496 2. ]
[307. 476. 0.00536 2. ]
[351. 552. 0.00571 2. ]
[ 62. 715. 0.00607 2. ]
[ 98. 433. 0.0065 2. ]
[255. 572. 0.00671 2. ]
[437. 699. 0.00685 2. ]
[ 55. 498. 0.00765 2. ]
[143. 734. 0.00823 2. ]
[182. 646. 0.00843 2. ]
[ 45. 250. 0.0087 2. ]
[298. 728. 0.00954 2. ]
[580. 619. 0.01033 2. ]
[179. 183. 0.01062 2. ]
[101. 668. 0.01079 2. ]
[131. 544. 0.01125 2. ]
[655. 726. 0.01141 2. ]
[503. 756. 0.01265 3. ]]

从上面的信息可以看到,在第 6 次合并中,样本点 141 与样本点 550 进行了合并,生成新 cluster 756;在第 25 次合并中,样本点 503cluster 756 进行了合并,生成新的 cluster 770。我们可以将样本点 141550503 的特征信息打印出来,来看看它们是否确实很接近。

1
2
3
4
>>> print(X[[141, 550, 503]])
[[ 1.27098 -0.97927]
[ 1.27515 -0.98006]
[ 1.37274 1.13599]]

看数字,这三个样本点确实很接近,从而也表明了层次聚类算法的核心思想:每次合并的都是当前 cluster 中相隔最近的。

画出树形图

SciPy 中给出了根据层次聚类的结果 Z 绘制树形图的函数 dendrogram,我们由此画出本次实验中的最后 20 次的合并过程。

1
2
3
4
5
6
>>> plt.figure(figsize=(10, 8))
>>> dendrogram(Z, truncate_mode='lastp', p=20, show_leaf_counts=False, leaf_rotation=90, leaf_font_size=15, show_contracted=True)
>>> plt.title('Dendrogram for the Agglomerative Clustering')
>>> plt.xlabel('sample index')
>>> plt.ylabel('distance')
>>> plt.show()

得到的树形图如下所示。

程序绘制出的树形图

可以看到,该树形图的最后两次合并相比之前合并过程的合并距离要大得多,由此可以说明最后两次合并是不合理的;因而对于本数据集,该算法可以很好地区分出 3cluster(和实际相符),分别在上图中由三种颜色所表示。

获取聚类结果

在得到了层次聚类的过程信息 Z 后,我们可以使用 fcluster 函数来获取聚类结果。可以从两个维度来得到距离的结果,一个是指定临界距离 d,得到在该距离以下的未合并的所有 cluster 作为聚类结果;另一个是指定 cluster 的数量 k,函数会返回最后的 kcluster 作为聚类结果。使用哪个维度由参数 criterion 决定,对应的临界距离或聚类的数量则由参数 t 所记录。fcluster 函数的结果为一个一维数组,记录每个样本的类别信息。

对应的代码与返回结果如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 根据临界距离返回聚类结果
>>> d = 15
>>> labels_1 = fcluster(Z, t=d, criterion='distance')
>>> print(labels_1[: 100]) # 打印聚类结果
[2 1 2 3 2 1 1 3 2 2 1 1 1 3 1 2 1 1 3 3 3 3 3 3 1 1 3 2 2 3 2 1 1 2 1 2 3
2 2 3 3 1 1 1 1 1 2 3 2 1 3 3 1 1 3 3 1 2 3 1 3 3 3 3 3 2 3 3 2 2 2 3 2 2
3 1 2 1 2 3 1 1 2 2 2 2 1 3 1 3 3 2 1 2 1 2 1 1 2 2]
>>> print(len(set(labels_1))) # 看看在该临界距离下有几个 cluster
3
# 根据聚类数目返回聚类结果
>>> k = 3
>>> labels_2 = fcluster(Z, t=k, criterion='maxclust')
>>> print(labels_2[: 100])
[2 1 2 3 2 1 1 3 2 2 1 1 1 3 1 2 1 1 3 3 3 3 3 3 1 1 3 2 2 3 2 1 1 2 1 2 3
2 2 3 3 1 1 1 1 1 2 3 2 1 3 3 1 1 3 3 1 2 3 1 3 3 3 3 3 2 3 3 2 2 2 3 2 2
3 1 2 1 2 3 1 1 2 2 2 2 1 3 1 3 3 2 1 2 1 2 1 1 2 2]
>>> list(labels_1) == list(labels_2) # 看看两种不同维度下得到的聚类结果是否一致
True

下面将聚类的结果可视化,相同的类的样本点用同一种颜色表示。

1
2
3
4
>>> plt.figure(figsize=(10, 8))
>>> plt.title('The Result of the Agglomerative Clustering')
>>> plt.scatter(X[:, 0], X[:, 1], c=labels_2, cmap='prism')
>>> plt.show()

可视化结果如下图所示。

层次聚类结果

上图的聚类结果和实际的数据分布基本一致,但有几点值得注意,一是在聚类之前我们没法知道合理的聚类的数目或者最大的距离临界值,只有在得到全部的层次聚类信息并对其进行分析后我们才能预估出一个较为合理的数值;二是本次实验的数据集比较简单,所以聚类的结果较好,但对于复杂的数据集(比如非凸的、噪声点比较多的数据集),层次聚类算法有其局限性。

比较不同方法下的聚类结果

最后,我们对同一份样本集进行了 cluster 间距离衡量准则分别为 Single-link、Complete-link、UPGMA(Average)和 Ward 的 Agglomerative 层次聚类,取聚类数目为 3,程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from time import time
import numpy as np
from scipy.cluster.hierarchy import linkage, fcluster
from sklearn.datasets.samples_generator import make_blobs
from sklearn.metrics.cluster import adjusted_mutual_info_score
import matplotlib.pyplot as plt
# 生成样本点
centers = [[1, 1], [-1, -1], [1, -1]]
X, labels = make_blobs(n_samples=750, centers=centers,
cluster_std=0.4, random_state=0)
# 可视化聚类结果
def plot_clustering(X, labels, title=None):
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='prism')
if title is not None:
plt.title(title, size=17)
plt.axis('off')
plt.tight_layout()
# 进行 Agglomerative 层次聚类
linkage_method_list = ['single', 'complete', 'average', 'ward']
plt.figure(figsize=(10, 8))
ncols, nrows = 2, int(np.ceil(len(linkage_method_list) / 2))
plt.subplots(nrows=nrows, ncols=ncols)
for i, linkage_method in enumerate(linkage_method_list):
print('method %s:' % linkage_method)
start_time = time()
Z = linkage(X, method=linkage_method)
labels_pred = fcluster(Z, t=3, criterion='maxclust')
print('Adjust mutual information: %.3f' %
adjusted_mutual_info_score(labels, labels_pred))
print('time used: %.3f seconds' % (time() - start_time))
plt.subplot(nrows, ncols, i + 1)
plot_clustering(X, labels_pred, '%s linkage' % linkage_method)
plt.show()

可以得到 4 种方法下的聚类结果如下图所示。

不同方法下的聚类结果

在上面的过程中,我们还为每一种聚类产生的结果计算了一个用于评估聚类结果与样本的真实类之间的相近程度的 AMI(Adjust Mutual Information)量,该量越接近于 1 则说明聚类算法产生的类越接近于真实情况。程序的打印结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
method single:
Adjust mutual information: 0.001
time used: 0.008 seconds
method complete:
Adjust mutual information: 0.838
time used: 0.013 seconds
method average:
Adjust mutual information: 0.945
time used: 0.019 seconds
method ward:
Adjust mutual information: 0.956
time used: 0.015 seconds

从上面的图和 AMI 量的表现来看,Single-link 方法下的层次聚类结果最差,它几乎将所有的点都聚为一个 cluster,而其他两个 cluster 则都仅包含个别稍微有点偏离中心的样本点,这充分体现了 Single-link 方法下的“链式效应”,也体现了 Agglomerative 算法的一个特点,即“赢者通吃”(rich getting richer): Agglomerative 算法倾向于聚出不均匀的类,尺寸大的类倾向于变得更大,对于 Single-link 和 UPGMA(Average) 方法尤其如此。由于本次实验的样本集较为理想,因此除了 Single-link 之外的其他方法都表现地还可以,但当样本集变复杂时,上述“赢者通吃” 的特点会显现出来。