Question

系统聚类（又称为层次聚类，系谱聚类）是一个一般的聚类算法，通过合并或分割类，生成嵌套的集群。算法的层次结构可以一棵树表示。树的根是一个唯一的类，包含了所有的样本，而树的叶子节点是单独的一个样本。通过树的叶子节点的相互合并，最终合并成为树的根节点。

1.算法原理

系统聚类的基本思想是先将样本看作各自一类，定义类间距离的计算方法，选择距离最小的一对类合并成为一个新的类。接着重新计算类间的距离，再将距离最近的两类合并，如此最终便合成一类。

图8-2和图8-3给出了一个系统聚类的例子。

图8-2 系统聚类示例原始样本

图8-3 系统聚类示例最终效果

我们首先定义样本间距离的计算方法，计算各个样本点间的距离。先将距离最近的b与c合并，此时我们都5个类：{a}，{b，c}，{d}，{e}和{f}。我们希望进一步的合并，所以我们需要计算类{a}与{b，c}间的距离。因此我们还需要定义类间距离的计算方法。按照合并距离最小的两个类的规则，我们按顺序合并{d}与{e}，{d，e}与{f}，{b，c}与{d，e，f}，{a}与{a，b，c，d，e，f}。最终我们通过类的合并得出图8-3的结果。整个过程如同生成树的过程，树的层次结构分明。表8-1给出了样本间距离的常用定义（a，b表示某个样本点），表8-2给出了类间距离的常用定义（A，B，C代表某个类）。

表8-1 距离定义1

表8-2 距离定义2

我们考虑使用系统聚类算法将数据集N中的n个样本划分成k个不相交的类。

系统聚类算法步骤如下：

1）初始化，定义样本间距离和类间距离的计算方法，将每个样本点各自设为一类，记为c₁ ，c₂ ，…，c_n 。

2）计算任意两个类间的距离d（c_i ，c_j ），将最短距离的两个类c_i 与c_j 合并成{c_i ，c_j }，并将类重新标记为c₁ ，c₂ ，…，c_n-1 。

3）如果已经聚为k类则算法停止，否则重复步骤2，继续合并类。

系统聚类算法的优点在于灵活的距离定义使得它有很广的适用性。并且我们能够通过建树的过程发现类的层次关系。但注意系统聚类算法的计算复杂度很高，一般情形为O（n³ ），所以处理大数据聚类问题时，我们不能选择此算法。

2.Python实现

使用Scikit-learn的系统聚类函数能够轻松实现，与K-Means算法实现比较，只需更改一行代码，修改分类器。

K-Means：
y_pred = sklearn.cluster. KMeans(n_clusters=2,
    random_state=random_state).fit_predict(X)

系统聚类：

y_pred= sklearn.cluster.AgglomerativeClustering(
    affinity='euclidean',linkage='ward',n_clusters=2).fit_predict(X)

系统聚类的函数是AgglomerativeClustering（），最重要的参数是这3个：n_clusters聚类数目，affinity样本距离的定义，linkage类间距离的定义（连接规则）。

通过相同的数据，我们使用系统聚类与K-Means算法效果作对比。一般而言，系统聚类使用欧几里德距离（affinity='euclidean'）和离差平方和法（linkage='ward'）效果最好。代码见代码清单8-2，实验结果见图8-4。

代码清单8-2 系统聚类实验

# -*- coding:utf-8 -*-
# 系统聚类实验
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
plt.figure(figsize=(12, 12))
# 选取样本数量
n_samples = 1500
# 选取随机因子
random_state = 170
# 获取数据集
X, y = make_blobs(n_samples=n_samples, random_state=random_state)
# 聚类数量不正确时的效果
y_pred = AgglomerativeClustering(affinity='euclidean',linkage='ward',n_clusters= 2).fit_predict(X)
# 选取欧几里德距离和离差平均和法
plt.subplot(221)
plt.scatter(X[y_pred==0][:, 0], X[y_pred==0][:, 1], marker='x',color='b')
plt.scatter(X[y_pred==1][:, 0], X[y_pred==1][:, 1], marker='+',color='r')
plt.title("Incorrect Number of Blobs")
# 聚类数量正确时的效果
y_pred = AgglomerativeClustering(
affinity='euclidean',linkage='ward',n_clusters=3).fit_predict(X)
plt.subplot(222)
plt.scatter(X[y_pred==0][:, 0], X[y_pred==0][:, 1], marker='x',color='b')
plt.scatter(X[y_pred==1][:, 0], X[y_pred==1][:, 1], marker='+',color='r')
plt.scatter(X[y_pred==2][:, 0], X[y_pred==2][:, 1], marker='1',color='m')
plt.title("Correct Number of Blobs")
# 类间的方差存在差异的效果
X_varied, y_varied = make_blobs(n_samples=n_samples,
                                    cluster_std=[1.0, 2.5, 0.5],
                                    random_state=random_state)
y_pred= AgglomerativeClustering(
affinity='euclidean',linkage='ward',n_clusters=3).fit_predict(X_varied)
plt.subplot(223)
plt.scatter(X_varied[y_pred==0][:, 0], X_varied[y_pred==0][:, 1], marker= 'x',color='b')
plt.scatter(X_varied[y_pred==1][:, 0], X_varied[y_pred==1][:, 1], marker= '+',color='r')
plt.scatter(X_varied[y_pred==2][:, 0], X_varied[y_pred==2][:, 1], marker= '1',color='m')
plt.title("Unequal Variance")
# 类的规模差异较大的效果
X_filtered = np.vstack((X[y == 0][:500], X[y == 1][:100], X[y == 2][:10]))
y_pred= AgglomerativeClustering(
affinity='euclidean',linkage='ward',n_clusters=3).fit_predict(X_filtered)
plt.subplot(224)
plt.scatter(X_filtered[y_pred==0][:, 0], X_filtered[y_pred==0][:, 1], marker='x',color='b')
plt.scatter(X_filtered[y_pred==1][:, 0], X_filtered[y_pred==1][:, 1], marker='+',color='r')
plt.scatter(X_filtered[y_pred==2][:, 0], X_filtered[y_pred==2][:, 1], marker='1',color='m')
plt.title("Unevenly Sized Blobs")
plt.show()

*代码详见：示例程序/code/8-2.py

图8-4 系统聚类实验结果