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

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

14.1 聚类的基本概念

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

14.1.1 相似度或距离

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

X = [x_{i j}]_{m \times n} = [\begin{matrix} x_{11} & x_{12} & . . . & x_{1 n} \\ x_{21} & x_{22} & . . . & x_{2 n} \\ . & . & . \\ . & . & . \\ . & . & . \\ x_{m 1} & x_{m 2} & . . . & x_{m n} \end{matrix}] (14.1)

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

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

闵可夫斯基距离

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

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

d_{i j} = (\sum_{k = 1}^{m} | x_{k i} - x_{k j} |^{p})^{\frac{1}{p}} (14.2)

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

d_{i j} = (\sum_{k = 1}^{m} | x_{k i} - x_{k j} |^{2})^{\frac{1}{2}} (14.3)

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

d_{i j} = (\sum_{k = 1}^{m} | x_{k i} - x_{k j} |) (14.4)

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

d_{i j} = max_{k} | x_{k i} - x_{k j} | (14.5)

马哈拉诺比斯距离

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

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

d_{i j} = [(x_{i} - x_{j})^{T} S^{- 1} (x_{i} - x_{j})]^{\frac{1}{2}} (14.6)

其中

x_{i} = (x_{1 i}, x_{2 i}, . . ., x_{m i})^{T}, x_{j} = (x_{1 j}, x_{2 j}, . . ., x_{m j})^{T} (14.7)

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

相关系数

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

定义 14.3 样本 $x_{i}$ 与样本 $x_{j}$ 之间的相关系数定义为

r_{i j} = \frac{\sum_{k = 1}^{m} (x_{k i} - {\overset{―}{x}}_{i}) (x_{k j} - {\overset{―}{x}}_{j})}{[\sum_{k = 1}^{m} (x_{k i} - {\overset{―}{x}}_{i})^{2} \sum_{k = 1}^{m} (x_{k j} - {\overset{―}{x}}_{j})^{2}]^{\frac{1}{2}}} (14.8)

其中

{\overset{―}{x}}_{i} = \frac{1}{m} \sum_{k = 1}^{m} x_{k i}, {\overset{―}{x}}_{j} = \frac{1}{m} \sum_{k = 1}^{m} x_{k j}

夹角余弦

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

定义 14.4 样本 $x_{i}$ 与样本 $x_{j}$ 之间的夹角余弦定义为

s_{i j} = \frac{\sum_{k = 1}^{m} x_{k i} x_{k j}}{[\sum_{k = 1}^{m} x_{k i}^{2} \sum_{k = 1}^{m} x_{k j}^{2}]^{\frac{1}{2}}} (14.9)

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

14.1.2 类或簇

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

用 $G$ 表示类或簇（cluster），用 $x_{i}, x_{j}$ 表示类中的样本，用 $n_{G}$ 表示 $G$ 中样本的个数，用 $d_{i j}$ 表示样本 $x_{i}$ 与样本 $x_{j}$ 之间的距离。

定义 14.5 设 $T$ 为给定的正数，若集合 $G$ 中任意两个样本 $x_{i}, x_{j}$ ，有

d_{i j} \leq T

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

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

d_{i j} \leq T

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

定义 14.7 设 $T$ 为给定的正数，若对集合 $G$ 的任意一个样本 $x_{i}$ ， $G$ 中的另一个样本 $x_{j}$ 满足

\frac{1}{n_{G} - 1} \sum_{x_{j} \in G} d_{i j} \leq T

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

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

\frac{1}{n_{G} (n_{G} - 1)} \sum_{x_{i} \in G} \sum_{x_{j} \in G} d_{i j} \leq T

d_{i j} \leq V

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

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

（1）类的均值 ${\overset{―}{x}}_{G}$ ，又称为类的中心

{\overset{―}{x}}_{G} = \frac{1}{n_{G}} \sum_{a = 1}^{n_{G}} x_{a} (14.10)

（2）类的直径（diameter） $D_{G}$

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

D_{G} = max_{x_{i}, x_{j} \in G} d_{i j} (14.11)

（3）类的样本散布矩阵（scatter matrix） $A_{G}$ 与样本协方差矩阵（covariance matrix） $S_{G}$

类样本散布矩阵 $A_{G}$ 为

A_{G} = \sum_{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_{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_{p q} = min {d_{i j} | x_{i} \in G_{p}, x_{j} \in G_{q}} (14.14)

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

定义类 $G_{p}$ 的样本与类 $G_{q}$ 的样本之间的最长距离为两类之间的距离

D_{p q} = max {d_{i j} | x_{i} \in G_{p}, x_{j} \in G_{q}} (14.15)

（3）中心距离

定义类 $G_{p}$ 与类 $G_{q}$ 的中心之间的距离为两类之间的距离

D_{p q} = d_{{\overset{―}{x}}_{p} {\overset{―}{x}}_{q}} (14.16)

（4）平均距离

定义类 $G_{p}$ 与类 $G_{q}$ 任意两个样本之间距离的平均值为两类之间的距离

D_{p q} = \frac{1}{n_{p} n_{q}} \sum_{x_{i} \in G_{p}} \sum_{x_{j} \in G_{q}} d_{i j} (14.17)

14.2 层次聚类

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

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

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

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

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

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

算法 14.1（聚合聚类算法）

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

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

（1）计算 $n$ 个样本两两之间的欧式距离 ${d_{i j}}$ ，记作矩阵 $D = [d_{i j}]_{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}, \dots, x_{n}}$ ，每个样本由一个特征向量表示，特征向量的维数是 $m$ 。 $k$ 均值聚类的目标是将 $n$ 个样本分到 $k$ 个不同的类或簇中，这里假设 $k < n$ 。 $k$ 个类 $G_{1}, G_{2}, \dots, G_{k}$ 形成对样本集合 $X$ 的划分，其中 $G_{i} ⋂ G_{j} = \emptyset, ⋃_{i = 1}^{k} G_{i} = X$ 。用 $C$ 表示划分，一个划分对应着一个聚类结果。

划分 $C$ 是一个多对一的函数。如果把每个样本用一个正数 $i \in {1, 2, \dots, n}$ 表示，每个类也用一个正数 $l \in {1, 2, \dots, 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_{k = 1}^{m} (x_{k i} - x_{k j})^{2} (14.18)

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

W (C) = \sum_{l = 1}^{k} \sum_{C (i) = l} | | x_{i} - {\bar{x}}_{l} | |^{2} (14.19)

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

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

C^{*} = \arg min_{C} W (C)

= \arg min_{C} \sum_{l = 1}^{k} \sum_{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)}, \dots, m_{k}^{(0)})$ 。

（2）对样本进行聚类。对固定的类中心 $m^{(t)} = (m_{1}^{(t)}, . ., m_{l}^{(t)}, \dots, m_{k}^{(t)})$ ，其中 $m_{l}^{(t)}$ 为类 $G_{t}$ 的中心，计算每个样本到类中心的距离，将每个样本指派到与其最近的中心的类中，构成聚类结果 $C^{(t)}$ 。

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

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

14.3.4 算法特性

总体特点

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

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

收敛性

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

初始类的选择

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

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

类别数 $k$ 的选择

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

Blog

第十四章聚类方法

14.1 聚类的基本概念

14.1.1 相似度或距离

14.1.2 类或簇

14.1.3 类与类之间的距离

14.2 层次聚类

14.3 $k$ 均值聚类

14.3.1 模型

14.3.2 策略

14.3.3 算法

14.3.4 算法特性

14.1 聚类的基本概念

14.1.1 相似度或距离

14.1.2 类或簇

14.1.3 类与类之间的距离

14.2 层次聚类

14.3 k均值聚类

14.3.1 模型

14.3.2 策略

14.3.3 算法

14.3.4 算法特性

14.3 $k$ 均值聚类