第十四章 聚类方法

聚类时针对给定的样本，依据它们特征的相似度或距离，将其归并到若干个“类”或“簇”的数据分析问题。一个类是给定样本集合的一个子集。

直观上，相似的样本聚集在相同的类，不相似的样本分散在不同的类。

14.1 聚类的基本概念

包括样本之间的距离或相似度，类或簇，类与类之间的距离。

14.1.1 相似度或距离

聚类的核心概念是相似度（similarity）或距离（distance），有多种相似度或距离的定义。因为相似度直接影响聚类的结果，所以其选择是聚类的根本问题。

$$X = [ x_{ij}]_{m \times n} = \left[ \begin{matrix} x_{11}& x_{12}&...&x_{1n}\\ x_{21}& x_{22}&...&x_{2n}\\ .& .&&.\\ .& .&&.\\ .& .&&.\\ x_{m1}& x_{m2}&...&x_{mn}\\ \end{matrix} \right]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.1)$$

矩阵的第$j$列表示第$j$个样本，$j=1,2,…n$；第$i$行表示第$i$个属性，$i = 1,2,…,m$；

矩阵元素$x_{ij}$表示第$j$个样本的第$i$个属性值，$i = 1,2,…,m;j = 1,2,…,n$。

---

1. 闵可夫斯基距离

在聚类中，可将样本集合看作是向量空间中点的集合，以该空间的距离表示样本之间的相似度。常用的距离有闵可夫斯基距离，特别是欧氏距离。闵可夫斯基距离越大相似度越小，距离越小相似度越大。

定义 14.1 给定样本集合$X$，$X$是$m$维实数向量空间$R^m$中点的集合，其中$x_i,x_j \in X, x_i=(x_{1i},x_{2i},…,x_{mi})^T,x_i=(x_{1j},x_{2j},…,x_{mj})^T$，样本$x_i$与样本$x_j$的闵可夫斯基距离（Minkowski distance）定义为

$$d_{ij} = (\sum\limits_{k=1}^{m}|x_{ki} - x_{kj}|^p)^{\frac{1}{p}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.2)$$

这里$p \geq 1$。当$p=2$时称为欧氏距离（Euclidean distance），即

$$d_{ij} = (\sum\limits_{k=1}^{m}|x_{ki} - x_{kj}|^2)^{\frac{1}{2}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.3)$$

当$p = 1$时称为曼哈顿距离（Manhattan distance），即

$$d_{ij} = (\sum\limits_{k=1}^{m}|x_{ki} - x_{kj}|)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.4)$$

当$p = \infty$时称为切比雪夫距离（Chebyshev distance），取各个坐标数值差的绝对值的最大值，即

$$d_{ij} = \max\limits_{k}|x_{ki} - x_{kj}|\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.5)$$

---

1. 马哈拉诺比斯距离

马哈拉诺比斯距离（Mahalanobis distance），简称马氏距离，也是另一种常用的相似度，考虑各个分量（特征）之间的相关性并与各个分量尺度无关。马哈拉诺比斯距离越大相似度越小，距离越小相似度越大。

定义 14.2 给定一个样本集合$X,X= [x{ij}]{m \times n}$，其中协方差矩阵记作$S$。样本$x_i$与样本$x_j$之间的马哈拉诺比斯距离$d_{ij}$定义为

$$d_{ij} = [(x_i-x_j)^T S^{-1}(x_i-x_j)]^{\frac{1}{2}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.6)$$

其中

$$x_i=(x_{1i},x_{2i},...,x_{mi})^T,x_j=(x_{1j},x_{2j},...,x_{mj})^T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.7)$$

当$S$为单位矩阵时，即样本数据的各个分量互相独立且各个分量的方差为1时，由式$(14.6)$知马氏距离就是欧氏距离，所以马氏距离是欧式距离的推广。

1. 相关系数

样本之间的相似度也可以用相关系数（correlation coefficient）来表示。相关系数的绝对值越接近于1，表示样本越相似；越接近于0，表示样本越不相似。

定义 14.3 样本$x_i$与样本$x_j$之间的相关系数定义为

$$r_{ij} = \frac{\sum\limits_{k=1}^{m}(x_{ki} - \overline x_i)(x_{kj} - \overline x_j)}{[\sum\limits_{k=1}^{m}(x_{ki} - \overline x_i)^2 \sum\limits_{k=1}^{m}(x_{kj} - \overline x_j)^2]^{\frac{1}{2}}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.8)$$

---

其中

$$\overline x_i = \frac{1}{m}\sum\limits_{k=1}^{m}x_{ki}, \ \ \overline x_j = \frac{1}{m}\sum\limits_{k=1}^{m}x_{kj}$$

1. 夹角余弦

样本之间的相似度也可以用夹角余弦（cosine）来表示。夹角余弦越接近于1，表示样本越相似；越接近于0，表示样本越不相似。

定义 14.4 样本$x_i$与样本$x_j$之间的夹角余弦定义为

$$s_{ij} = \frac{\sum\limits_{k=1}^{m}x_{ki}x_{kj}}{[\sum\limits_{k=1}^{m}x_{ki}^2\sum\limits_{k=1}^{m}x_{kj} ^2]^{\frac{1}{2}}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.9)$$

用距离度量相似度时，距离越小样本越相似；用相关系数时，相关系数越大样本越相似。注意不同相似度度量得到的结果并不一定一致。

14.1.2 类或簇

通过聚类得到的类或簇，本质是样本的子集。如果一个聚类方法假定一个样本只能属于一个类，或类的交集为空集，那么该方法称为硬聚类（hard clustering）方法。否则，如果一个样本可以属于多个类，或者类的交集不为空集，那么该方法称为软聚类（soft clustering）方法。

用$G$表示类或簇（cluster），用$x_i,x_j$表示类中的样本，用$n_G$表示$G$中样本的个数，用$d_{ij}$表示样本$x_i$与样本$x_j$之间的距离。

---

定义 14.5 设$T$为给定的正数，若集合$G$中任意两个样本$x_i,x_j$，有

$$d_{ij} \leq T$$

则称$G$为一个类或簇。

---

定义 14.6 设$T$为给定的正数，若对集合$G$的任意样本$x_i$，一定存在$G$中的另一个样本$x_j$，使得

$$d_{ij} \leq T$$

则称$G$为一个类或簇。

---

定义 14.7 设$T$为给定的正数，若对集合$G$的任意一个样本$x_i$，$G$中的另一个样本$x_j$满足

$$\frac{1}{n_G-1} \sum\limits_{x_j \in G} d_{ij} \leq T$$

其中$n_G$为$G$中样本的个数，则称$G$为一个类或簇。

---

定义 14.8 设$T$和$V$为给定的两个正数，如果集合$G$中任意两个样本$x_i,x_j$的距离$d_{ij}$满足

$$\frac{1}{n_G(n_G-1)} \sum\limits_{x_i \in G}\sum\limits_{x_j \in G} d_{ij} \leq T$$ $$d_{ij} \leq V$$

则称$G$为一个类或簇。

---

类的特征可以通过不同角度来刻画，常用的特征有下面三种：

（1）类的均值$\overline x_G$，又称为类的中心

$$\overline x_G =\frac{1}{n_G} \sum\limits_{a = 1}^{n_G} x_a\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.10)$$

（2）类的直径（diameter）$D_G$

类的直径$D_G$是类中任意两个样本之间的最大距离，即

$$D_G = \max\limits_{x_i,x_j \in G}d_{ij}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.11)$$

（3）类的样本散布矩阵（scatter matrix）$A_G$与样本协方差矩阵（covariance matrix）$S_G$

类样本散布矩阵$A_G$为

$$A_G =\sum\limits_{i = 1}^{n_G}(x_i-\bar{x}_G)(x_i-\bar{x}_G)^T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.12)$$

样本协方差矩阵$S_G$为

$$S_G =\frac{1}{n_G - 1}A_G$$ $$=\frac{1}{n_G-1}\sum\limits_{i = 1}^{n_G}(x_i-\bar{x}_G)(x_i-\bar{x}_G)^T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.13)$$

14.1.3 类与类之间的距离

类$G_p$与类$G_q$之间的距离$D(p,q)$，也称为连接（linkage）。类与类之间的距离也有多种定义。

设类$G_p$包含$n_p$个样本，$G_q$包含$n_q$个样本，分别用$\bar{x}_p$和$\bar{x}_q$表示$G_p$和$G_q$的均值，即类的中心。

---

（1）最短距离或单链接（single linkage）

定义类$G_p$的样本与类$G_q$的样本之间的最短距离为两类之间的距离

$$D_{pq} = \min\{d_{ij}|x_i \in G_p,x_j \in G_q\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.14)$$

（2）最长距离或完全连接（complete linkage）

定义类$G_p$的样本与类$G_q$的样本之间的最长距离为两类之间的距离

$$D_{pq} = \max\{d_{ij}|x_i \in G_p,x_j \in G_q\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.15)$$

（3）中心距离

定义类$G_p$与类$G_q$的中心之间的距离为两类之间的距离

$$D_{pq} = d_{\overline x_p\overline x_q}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.16)$$

（4）平均距离

定义类$G_p$与类$G_q$任意两个样本之间距离的平均值为两类之间的距离

$$D_{pq} = \frac{1}{n_p n_q}\sum\limits_{x_i \in G_p}\sum\limits_{x_j \in G_q}d_{ij}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.17)$$

14.2 层次聚类

层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中。

层次聚类又有聚合（agglomerative）或自下而上（bottom-up）聚类、分裂（divisive）或自上而下（top-down）聚类两种方法。

• 聚合聚类开始将每个样本各自分到一个类；之后将相邻距离最近的两类合并，建立一个新的类，重复此操作直到满足停止条件；得到层次化的类别。

• 分裂聚类开始将所有样本分到一个类；之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件；得到层次化的类别。

聚合聚类的具体过程如下：对于给定的样本集合，开始将每个样本分到一个类；然后按照一定规则，例如类间距离最小，将最满足规则条件的两个类进行合并；如此反复进行，每次减少一个类，直到满足停止条件，如所有样本聚为一类。

由此可知，聚合聚类需要预先确定下面三个要素：

• 距离或相似度
• 合并规则
• 停止条件

算法 14.1（聚合聚类算法）

输入：$n$个样本组成的样本集合及样本之间的距离；

输出：对样本集合的一个层次化聚类。

（1）计算$n$个样本两两之间的欧式距离$\{d_{ij}\}$，记作矩阵$D = [d_{ij}]_{n \times n}$。

（2）构造$n$个类，每个类只包含一个样本。

（3）合并类间距离最小的两个类，其中最短距离为类间距离，构建一个新类。

（4）计算新类与当前各类的距离。若类的个数为1，终止计算，否则回到步（3）。

14.3 $k$均值聚类

$k$均值聚类是基于样本集合划分的聚类算法。$k$均值聚类将样本集合划分为$k$个子集，构成$k$个类，将$n$个样本划分到$k$个类中，每个样本到其所属类的中心的距离最小。

14.3.1 模型

给定$n$个样本的集合$X = \{x_1,x_2,…,x_n\}$，每个样本由一个特征向量表示，特征向量的维数是$m$。$k$均值聚类的目标是将$n$个样本分到$k$个不同的类或簇中，这里假设$k < n$。$k$个类$G_1,G_2,…,G_k$形成对样本集合$X$的划分，其中$G_i \bigcap G_j = \emptyset,\bigcup\limits_{i=1}^{k}G_i = X$。用$C$表示划分，一个划分对应着一个聚类结果。

划分$C$是一个多对一的函数。如果把每个样本用一个正数$i\in\{1,2,…,n\}$表示，每个类也用一个正数$l \in \{1,2,…,k\}$表示，那么划分或者聚类可以用函数$l=C(i)$表示。所以$k$均值聚类的模型是一个从样本到类的函数。

14.3.2 策略

$k$均值聚类归结为样本集合$X$的划分，或者从样本到类的函数的选择问题。$k$均值聚类的策略是通过损失函数的最小化选取最优的划分或函数$C^*$。

首先，采用欧氏距离平方（squared Euclidean distance）作为样本之间的距离$d(x_i,x_j)$

$$d(x_i,x_j) = \sum\limits_{k=1}^{m}(x_{ki} - x_{kj})^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.18)$$

然后，定义样本与其所属类的中心之间的距离的总和为损失函数，即

$$W(C) =\sum\limits_{l=1}^{k}\sum\limits_{C(i) =l}||x_i-\bar{x}_l||^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.19)$$

函数$W(C)$也称为能量，表示相同类中的样本相似的程度。

$k$均值聚类就是求解最优化问题：

$$C^* = \arg\min\limits_{C}W(C)$$ $$=\arg\min\limits_{C}\sum\limits_{l=1}^{k}\sum\limits_{C(i) =l}||x_i-\bar{x}_l||^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (14.20)$$

相似的样本被聚到同类时，损失函数值最小，这个目标函数的优化能达到聚类的目的。

$k$均值聚类的最优解求解问题是NP困难问题。现实中采用迭代的方法求解。

14.3.3 算法

$k$均值聚类的算法是一个迭代的过程，每次迭代包括两个步骤。

• 选择$k$个类的中心，将样本逐个指派到与其最近的中心的类中，得到一个聚类结果；
• 更新每个类的样本的均值，作为类的新的中心；

重复以上步骤，直到收敛为止。

算法 14.2（$k$均值聚类算法）

输入：$n$个样本的集合$X$；

输出：样本集合的聚类$C^\cdot$。

​ （1）初始化。令$t=0$，随机选择$k$个样本点作为初始聚类中心$m^{(0)} = (m_1^{(0)},..,m_l^{(0)},…,m_k^{(0)})$。

​ （2）对样本进行聚类。对固定的类中心$m^{(t)} = (m_1^{(t)},..,m_l^{(t)},…,m_k^{(t)})$，其中$m_l^{(t)}$为类$G_t$的中心，计算每个样本到类中心的距离，将每个样本指派到与其最近的中心的类中，构成聚类结果$C^{(t)}$。

​ （3）计算新的类中心。对聚类结果$C^{(t)}$，计算当前各个类中的样本的均值，作为新的类中心$m^{(t+1)} = (m_1^{(t+1)},..,m_l^{(t+1)},…,m_k^{(t+1)})$。

​ （4）如果迭代收敛或符合停止条件，输出$C^* = C^{(t)}$。否则，令$t= t+1$，返回步（2）。

14.3.4 算法特性

1. 总体特点

$k$均值聚类有以下特点：

• 基本划分的聚类方法；
• 类别数$k$事先指定；
• 以欧式距离平方表示样本之间的距离，以中心或样本的均值表示类别；
• 以样本和其所属类的中心之间的距离的总和为最优化的目标函数；
• 得到的类别是平坦的、非层次化的；
• 算法是迭代算法，不能保证得到全局最优。

1. 收敛性

$k$均值聚类属于启发式方法，不能保证收敛到全局最优，初始中心的选择会直接影响聚类结果。

1. 初始类的选择

选择不同的初始中心，会得到不同的聚类结果。

初始中心的选择，比如可以用层次聚类对样本进行聚类，得到$k$个类时停止。然后从每个类中选取一个与中心距离最近的点。

1. 类别数$k$的选择

$k$均值聚类中的类别数$k$值需要预先指定，而在实际应用中最优的$k$值是不知道的。解决这个问题的一个方法是尝试用不同的$k$值聚类，检验各自得到聚类结果的质量，推测最优的$k$值。聚类结果的质量可以用类的平均直径来衡量。一般地，类别数变小时，平均直径会增加；类别数变大超过某个值以后，平均直径会不变；而这个值正是最优的$k$值。