聚类是针对给定的样本，依据它们特征的相似度或距离，将其归并到若干个“类”或“簇”的数据分析问题。一个类是样本的一个子集。直观上，相似的样本聚集在相同的类，不相似的样本分散在不同的类。这里，样本之间的相似度或距离起着重要作用。

聚类的目的是通过得到的类或簇来发现数据的特点或对数据进行处理，在数据挖掘、模式识别等领域有着广泛的应用。聚类属于无监督学习，因为只是根据样本的相似度或距离将其进行归类，而类或簇事先并不知道。

聚类算法很多，本章介绍两种最常用的聚类算法：层次聚类（hierarchical clustering）和k均值聚类（k-means clustering）。层次聚类又有聚合（自下而上）和分裂（自上而下）两种方法。聚合法开始将每个样本各自分到一个类；之后将相距最近的两类合并，建立一个新的类，重复此操作直到满足停止条件；得到层次化的类别。分裂法开始将所有样本分到一个类；之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件；得到层次化的类别。k均值聚类是基于中心的聚类方法，通过迭代，将样本分到k个类中，使得每个样本与其所属类的中心或均值最近；得到k个“平坦的”、非层次化的类别，构成对空间的划分。k均值聚类的算法1967年由MacQueen提出。

聚类的基本概念

相似度或距离

聚类的对象是观测数据，或样本集合。假设有n个样本，每个样本由m个属性的特征向量组成。样本集合可以用矩阵X表示。

聚类的核心概念是相似度（similarity）或距离（distance），有多种相似度或距离的定义。因为相似度直接影响聚类的结果，所以其选择是聚类的根本问题。具体哪种相似度更合适取决于应用问题的特性。

  1. 闵可夫斯基距离（Minkowski distance）

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

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

\[d_{ij} = (\sum_{k=1}^m \mid x_{ki} - x_{kj} \mid^p)^{\frac{1}{p}}\]

这里\(P \geq 1\)。当\(p=2\)时称为欧式距离（Euclidean distance），即

\[d_{ij} = (\sum_{k=1}^m \mid x_{ki} - x_{kj} \mid^2)^{\frac{1}{2}}\]

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

\[d_{ij} = \sum_{k=1}^m \mid x_{ki} - x_{kj} \mid\]

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

\[d_{ij} = \max_k \mid x_{ki} - x_{kj} \mid\]
  1. 马哈拉诺比斯距离

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

给定一个样本集合\(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}}

其中

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

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

  1. 相关系数

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

样本\(x_i\)与样本\(x_j\)之间的相关系数定义为

\[r_{ij} = \frac{\sum_{k=1}{m}(x_{ki} - \bar{x}_i)(x_{kj}- \bar{x}_j)}{[\sum_{k=1}{m}(x_{ki} - \bar{x}_i)^2\sum_{k=1}{m}(x_{kj} - \bar{x}_j)^2]^{\frac{1}{2}}}\]

其中

\[\bar{x}_i = \frac{1}{m} \sum_{k=1}^{m} x_{ki}, \bar{x}_j = \frac{1}{m} \sum_{k=1}^{m} x_{kj}\]
  1. 夹角余弦

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

样本\(x_i\)与样本\(x_j\)之间的夹角余弦定义为

\[s_{ij} = \frac{\sum_{k=1}^{m} x_{ki} x_{kj}}{[\sum_{k=1}^m x_{ki}^2 \sum_{k=1}^m x_{kj}^2]^{\frac{1}{2}}}\]

注意不同相似度度量得到的结果并不一定一致。进行聚类时，选择适合的距离或相似度非常重要。

类或簇

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

用G表示类或簇（cluster），用\(x_i, x_j\)表示类中的样本，用\(n_G\)表示G中样本的个数，用\(d_{ij}\)表示样本\(x_i\)与样本\(x_j\)之间的距离。类或簇有多种定义，下面给出几个常见的定义。

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

\[d_{ij} \leq T\]

则称G为一个类或簇

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

\[d_{ij} \leq T\]

则称G为一个类或簇。

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

\[\frac{1}{n_G-1} \sum_{x_j \in G} d_{ij} \leq T\]

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

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

\[\frac{1}{n_G-1} \sum_{x_j \in G} d_{ij} \leq T\] \[d_{ij} \leq V\]

则称G为一个类或簇。

以上四个定义，第一个定义最为常用，并且由它可以推出其他三个定义。

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

(1) 类的均值\(\bar{x}_G\)，又称为类的中心

\[\bar{x}_G = \frac{1}{n_G}\sum_{i=1}^{n_G} x_i\]

(2) 类的直径(diameter) \(D_G\)

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

\[D_G = \max_{x_i, x_j \in G} d_{ij}\]

(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\]

样本协方差矩阵\(S_G\)为

\[S_G = \frac{1}{m-1}A_G = \frac{1}{m-1} \sum_{i=1}^{n_G}(x_i - \bar{x}_G)(x_i-\bar{x}_G)^T\]

其中m为样本的维数（样本属性的个数）。

类与类之间的距离

下面考虑类\(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} \mid x_i \in G_p, x_j \in G_q}\]

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

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

\[D_{pq} = \max{d_{ij} \mid x_i \in G_p, x_j \in G_q}\]

(3) 中心距离

定义类\(G_p\)和类\(G_q\)的中心\(\bar{x}_p\)与\(\bar{x}_q\)之间的距离为两类之间的距离

\[D_{pq} = d_{\bar{x}_p \bar{x}_q}\]

(4) 平均距离

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

\[D_{pq} = \frac{1}{n_p n_q} \sum_{x_i \in G_p} \sum_{x_j \in G_q} d_{ij}\]

层次聚类

层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中。层次聚类又有聚合（agglomerative）或自下而上（bottom-up）聚类、分类（divisive）或自上而下（top-down）聚类两种方法。因为每个样本只属于一个类，所以层次聚类属于硬聚类。

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

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

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

(1) 距离或相似度；

(2) 合并规则；

(3) 停止条件。

根据这些要素的不同组合，就可以构成不同的聚类方法。距离或相似度可以是闵可夫斯基距离、马哈拉诺比斯距离、相关系数、夹角余弦。合并规则一般是类间距离最小，类间距离可以是最短距离、最长距离、中心距离、平均距离。停止条件可以是类的个数达到阈值（极端情况类的个数是1）、类的直径超过阈值。

如果采用欧式距离为样本之间距离；类间距离最小为合并规则，其中最短距离为类间距离；类的个数是1，即所有样本聚为一类，为停止条件，那么聚合聚类的算法如下。

聚合聚类算法

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

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

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

(2) 构造n个类，每个类只包含一个样本。

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

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

可以看出聚合层次聚类算法的复杂度是\(O(n^3m)\)，其中m是样本的维数，n是样本个数。

k均值聚类

k均值聚类是基于样本集合划分的聚类方法。k均值聚类将样本集合划分为k个子集，构成k个类，将n个样本分到k个类中，每个样本到其所属类的中心的距离最小。每个样本只能属于一个类，所以k均值聚类是硬聚类。下面分别介绍k均值聚类的模型、策略、算法，讨论算法的特性及相关问题。

模型

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

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

策略

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

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

\[d(x_i, x_j) = \sum_{k=1}^m (x_{ki} - x_{kj})^2 = \| x_i - x_j \|^2\]

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

\[W(C) = \sum_{l=1}^k \sum_{C(i)=l} \| x_i - \bar{x}_l \|^2\]

式中\(\bar{x}_l = (\bar{x}_{1l}, \bar{x}_{2l},..., \bar{x}_{ml})^T\)是第l个类的均值或中心，\(n_l = \sum_{i=1}^n I(C(i)=l)，I(C(i)=l)\)是指示函数，取值为1或0。函数W(C)也称为能量，表示相同类中的样本四盎司的程度。

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

\[\begin{align} C^* &= arg \min_C W(C) \\ &= arg \min_C \sum_{l=1}^k \sum_{C(i)=l} \| x_i - \bar{x}_l \|^2 \\ \end{align}\]

相似的样本被聚到同类时，损失函数值最小，这个目标函数的最优化能达到聚类的目的。但是，这是一个组合优化问题，n个样本分到k个类，所有可能分法的数目是：

\[S(n,k) = \frac{1}{k!} \sum_{l=1}^k (-1)^{k-l} \begin{matrix} k \\ l \end{matrix}\quad k^n\]

这个数字是指数级的。事实上，k均值聚类的最优解求解问题是NP困难问题。现实中采用迭代的方法求解。

算法

k均值聚类的算法是一个迭代的过程，每次迭代包括两个步骤。首先选择k个类别的中心，将样本逐个指派到与其最近的中心的类中，得到一个聚类结果；然后更新每个类的样本的均值，作为类的新的中心；重复以上步骤，直到收敛为止。具体过程如下。

首先，对于给定的中心值\((m_1, m_2, ..., m_k)\)，求一个划分C，使得目标函数极小化：

\[\min_C \sum_{l=1}^k \sum_{C(i)=l} \| x_i - m_l \|^2\]

就是说在类中心确定的情况下，将每个样本分到一个类中，使样本和其所属类的中心之间的距离总和最小。求解结果，将每个样本指派到与其最近的中心\(m_l\)的类\(G_l\)中。

然后，对给定的划分C，再求各个类的中心\((m_1, m_2,...,m_k)\)，使得目标函数极小化：

\[\min_{m_1,...,m_k} \sum_{l=1}^k \sum_{C(i)=l} \| x_i - m_l \|^2\]

就是说在划分确定的情况下，使样本和其所属类的中心之间的距离总和最小。求解结果，对于每个包含\(n_l\)个样本的类\(G_l\)，更新其均值\(m_l\)：

\[m_l = \frac{1}{n_l} \sum_{C(i)=l} x_i, l=1,...,k\]

重复以上两个步骤，直到划分不再改变，得到聚类结果。现将k均值聚类算法叙述如下。

k均值聚类算法

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

输出：样本集合的聚类\(C^*\)。

(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_l\)的中心，计算每个样本到类中心的距离，将每个样本指派到与其最近的中心的类中，构成聚类结果\(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)。

k均值聚类算法的复杂度是\(O(mnk)\)，其中m是样本维数，n是样本个数，k是类别个数。

算法特性

  1. 总体特点

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

  1. 收敛性

k均值聚类属于启发式算法，不能保证收敛到全局最优，初始中心的选择会直接影响聚类结果。注意，类中心在聚类的过程中会发生移动，但是往往不会移动太大，因为在每一步，样本被分到与其最近的中心的类中。

  1. 初始类的选择

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

  1. 类别数k的选择

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

聚类算法总结，前沿与应用

由于类或簇没有一个明确的定义，因此存在多种聚类方法。依据聚类思想的不同，可以将聚类算法划分为以下九大类：

依据思想划分的聚类方法

Partition-based Clustering

  • 思想：将点的中心作为聚类的中心，对空间进行分割。
  • 代表算法：K-means；K-medoids；PAM；CLARA；CLARANS。(affinity propagation算法也可以看作这类方法的一种)
  • 优点：相对低的时间复杂度；相对高的计算效率。
  • 缺点：不适合非凸的数据集；对于异常值敏感；容易陷入局部最优；聚类数量需要预先设定；聚类结果对设定的聚类数量敏感。

Hierarchy-based Clustering

  • 思想：构建数据间的层次关系。分为single-link，comple-link，average-link
  • 代表算法：BIRCH；CURE；ROCK；Chameleon
  • 优点：适合任意形状的数据；适合任意类型属性的数据；聚类结果具有层次结构；相对较好的可扩展性。
  • 缺点：相对高的时间复杂度；聚类数量需要预先设定。

Fuzzy Theory-based Clustering

  • 思想：离散的类型标签{0,1}改进为连续的概率区间[0,1]
  • 代表算法：FCM；FCS；MM
  • 优点：用类型概率替换类型标签更加符合实际；相对高的聚类准确性。
  • 缺点：相对低的可扩展性；容易陷入局部最优；聚类结果对于初始参数敏感；聚类数量需要预先设定；对于基于核函数的FCS算法时间复杂度高。

Distribution-based Clustering

  • 思想：假设从同一个分布中采用的数据属于同一类，且数据集中存在多个分布采样数据。
  • 代表算法：DBCLASD；GMM
  • 优点：使用类型概率分布更加符合实际；通过改变分布类型，分布数量可获得相对高的可扩展性；具有良好的统计学理论支持；
  • 缺点：前提假设不一定完全正确；加入过多对结果具有很强影响的参数；相对高的时间复杂度。

Density-based Clustering

  • 思想：在空间中处于高密度的一系列点属于同一类
  • 代表算法：DBSCAN；OPTICS；Mean-Shift。(DENCLUE也可以看作这类方法的一种)
  • 优点：高效；适合任意形状的数据；
  • 缺点：当空间中密度不均衡时聚类结果差；空间复杂度高；基于核函数的Mean-Shift时间复杂度高；聚类结果对参数敏感；

Graph Theory-based Clustering

  • 思想：数据点被看作图中的点，数据点之间的关系被看作图中的边。
  • 代表算法：CLICK；MST-based clustering。(SM算法，NJW算法也是这类方法中的一种)
  • 优点：高效；聚类结果准确性高；
  • 缺点：时间复杂度随图复杂度高速增长。

Grid-based Clustering

  • 思想：将原始的数据空间切割为有限的小方块。
  • 代表算法：STING；CLIQUE。(Wavecluster也是这类方法中的一种)
  • 优点：低时间复杂度；高度可扩展性；适合并行与增量计算；CLIQUE算法拥有Grid-based和Density-based的优点。
  • 缺点：聚类结果对于Gird粒度敏感；高效建立在减少聚类质量和聚类准确度的基础上。

Fractal Theory-based Clustering

  • 思想：基于分形理论
  • 代表算法：FC
  • 优点：高效；时间复杂度O(n)；高度可扩展性；对异常值不敏感；适合高维数据；适合任意形状数据；
  • 缺点：前提假设并不完全正确；聚类结果对参数敏感。

Model-based Clustering

  • 思想：选择特定的模型学习聚类，statistical learning/neural network learning
  • 代表算法：
    • statistical learning：COBWEB；GMM
    • neural network learning：SOM；ART
  • 优点：每个模型针对特定场景有特定效果。
  • 缺点：高时间复杂度；前提假设不一定完全正确；聚类结果对参数敏感。

参考文献

  • Xu D, Tian Y. A comprehensive survey of clustering algorithms[J]. Annals of Data Science, 2015, 2(2): 165-193.
  • Saxena A, Prasad M, Gupta A, et al. A review of clustering techniques and developments[J]. Neurocomputing, 2017, 267: 664-681.
  • Aggarwal C C, Zhai C X. A survey of text clustering algorithms[M]//Mining text data. Springer, Boston, MA, 2012: 77-128.
  • Ben-David S. Clustering-what both theoreticians and practitioners are doing wrong[C]//Thirty-Second AAAI Conference on Artificial Intelligence. 2018.
  • 统计学习方法 第2版 李航