Chapter 7: 聚类

欢迎来到"第二座山"！

前六章我们一直有"标签"这个拐杖（监督学习）。但现实中，大部分数据是没有标签的。没人告诉你这张图是猫还是狗，也没人告诉你这封邮件是不是垃圾邮件。

当没人告诉你答案时，你能发现数据中的结构吗？这就是无监督学习。

本章我们将探索无监督学习的第一站——聚类 (Clustering)。唯一的指导原则就是：物以类聚，人以群分。

聚类算法流派

我们将聚类算法划分为三大流派：

划分式 (Partitional)

划分式的代表就是我们之前讲过的K-means。

划分式聚类算法的逻辑有点像切蛋糕。给你一个$K$，你必须要把数据切成$K$块。这是一锤子买卖，或者是一个不断迭代优化的过程，但总之结果就是$K$个互不重叠的集合。

划分式问题往往都很简单。但是问题在于你需要预先知道$K$。
层次式 (Hierarchical)

它的代表是聚合层次聚类 (Hierarchical Agglomerative Clustering, HAC)。

层次是的产出不是给你$K个分类，而是还给你一整个结构。一般我们会使用两个方式来整合结构：

自底向上 (Agglomerative) 的逻辑是在算法开始时，每个人都是一个独立的部落，部落之间会不断合并，直到全天下统一。
自顶向下 (Divisive) 正好和自底向上反过来。开始时是一个大国，然后不断分裂成小的诸侯国。

层次是的特点不需要我们预先指定$K$，而我们得到的结构往往是一个树状图 (Dendrogram)。
贝叶斯式 (Bayesian)

学院派。他认为数据是由某种概率分布生成的，例如混合高斯模型GMM。他给出的答案不是“你属于A类”，而是“你属于A类的概率是80%”。

聚合层次聚类

HAC的逻辑非常符合人类的直觉，有点像是一个不断消消乐的过程。

算法经过如下步骤；

初始化：把$n$个数据点看作$n$个独立的蔟，也就是Cluster。
循环：只要蔟的数量大于一，那么我们就重复以下步骤：
- 找到最小距离对：在所有现存的蔟两两之间，我们要找到距离最近的那一对$(C_a, C_b)$：
$$(C_a, C_b) = arg min_{A, B}d(A,B)$$
- 合并：将这两个蔟合并成为一个新的大蔟。

这个算法极其简单，但是我们该如何计算AB之间的距离 $d(A,B)$？

距离度量

我们有多种方式计算两个蔟之间的距离，不同的计算方式直接决定了结果的形状。

在下面的例子中，我们都定数据点为$x = {1, 2, 4, 5, 7.25}$。每个元素都是一个蔟。

单链接 (Single-Linkage)

通过计算两个蔟之间最近的两个点的距离，即可找出单链接的值：

$$ d(A, B) = \min_{x \in A, y \in B} d(x, y) $$

流程：

在第一轮我们计算所有点对距离：
- $d(1,2)=1$, $d(4,5)=1$。这两对是最近的。
- 接下来合并${1,2} \to C_1$, ${4,5} \to C_2$。剩下 ${7.25}$。
第二轮计算现有三个簇 $C_1, C_2, {7.25}$。
- $d(C_1, C_2)$ 是多少？$C_1$ 里最右是 2，$C_2$ 里最左是 4。距离是 $4-2=2$。
- $d(C_2, {7.25})$ 是多少？$C_2$ 里最右是 5。距离是 $7.25-5=2.25$。
  由于$2 < 2.25$。因此我们将 $C_1$ 和 $C_2$ 合并。
总结最后结果为： ${1, 2, 4, 5}$ 先合并，最后才带上 $7.25$。

单链接容易产生 Chaining Effect (链式效应)。它倾向于形成细长的、蜿蜒的聚类。

全链接 (Complete-Linkage)

全链接寻找的是两个簇之间最远的两个点的距离：

$$ d(A, B) = \max_{x \in A, y \in B} d(x, y) $$

只有当你们两个帮派里相距最远的人也离得不够远时，我才承认你们近。这要求簇极其紧凑。

第一轮与之前一样，最近的点先合并。${1,2} \to C_1$, ${4,5} \to C_2$。
在第二轮：
- 为了算出 $d(C_1, C_2)$ 是多少，我们找最远的两个元素。$C_1$ 最左是 1，$C_2$ 最右是 5。距离 = $5-1 = 4$。
- 同理，对$d(C_2, {7.25})$来说，$C_2$ 最左是 4。距离 = $7.25-4 = 3.25$。
  由于$3.25 < 4$，这一次，$C_2$ 抛弃了 $C_1$，转而和 ${7.25}$ 合并。
最后我们得到${4, 5, 7.25}$ 先合并，最后再和 ${1, 2}$ 合并。

全链接倾向于产生紧凑、直径较小的球状聚类。但由于异常值和极值会拉大Max距离，因此全链接对异常值比较敏感。

平均链接 (Average-Linkage)

平均链接是中庸之道。它取得是所有点对距离的平均值。
$$ d(A, B) = \frac{1}{|A| \cdot |B|} \sum_{x \in A} \sum_{y \in B} d(x, y) $$

相比前两种，它通常能产生比较稳健的聚类结果。

那么你发现一个问题啊，假如我们的数据点是0, 10, 20, 30，你发现它们的兼具一致，则HAC的下一步合并理论上来讲是未定义的。这意味着0, 10 / 10, 20 / 20 , 30中的任意一对都可以被合并。这会导致HAC出现非确定性。

因此在实际的代码库中，为了保证HAC的确定性，我们通常会加入一个潜规则：当距离相等时，优先合并索引 (Index)更小的点。因此只要你用的是同一个软件库，结果通常是固定的。这与 K-means 的“真·随机初始化”导致的随机性有本质区别。

何时停止？

HAC 最终会把所有点合并成一个巨大的簇（树根）。我们需要在哪一刀切下去，得到我们想要的 $K$ 个类？这通常通过 Dendrogram (树状图) ：

Y 轴通常表示 Merge Distance (合并时的距离)。

如果你想要 $K$ 个类，就在树上画一条水平线，切断 $K$ 根竖线。
观察法: 通常我们在树状图中寻找“最长的竖线段”（Long Vertical Gap）。这意味着在这个距离范围内，没有发生合并，说明这几个大类之间的界限非常清晰。

基于中心的聚类

虽然我们在第一章就见过K-means，这次我们要从优化目标的角度重新审视它，并把它和HAC做一个终极对比。

首先先来复习一下K-means的流程：

选点：随机选择$k$个中心。
站队：每个点找到最近的中心，归队。
更新：每个队重新计算平均值，将中心移动到这个位置。

随后重复2-3步，直到中心位置不再发生变化。

K-means的数学目标

K-means看起来像是再根据一个看起来没问题的流程跑下去，但实际上K-means在做的是最小化一个特定的Loss函数，我们通常称之为失真 (Distortion) 或 Inertia:

$$ J = \sum_{j=1}^k \sum_{x_i \in C_j} ||x_i - \mu_j||^2 $$

其中，$||x_i - \mu_j||^2$代表的是每个点到他中心的距离平方。$c_i$表示第$i$个点归谁管，而$\mu_j$决定第$j$个组的中心位置在哪里。

我们希望蔟内的点尽可能紧凑，离自己的中心$\mu_j$越近越好。

现在我们来看看K-means是如何完成收敛的：

首先固定中心，调整点的归属：
我们现在知道有$k$个点的中心点的位置被钉在地图上了，那么对于数据点$x_i$来说，它需要选择蔟$c_i$。为了让$J$变小，它只需要看看自己的那一项$||x_i - \mu_j||^2$。

只有选距离的自己最近的那个中心才能导致这一项的值最小。因此，只要大家纷纷“弃暗投明”投奔最近的中心，就一定能导致$J$变小。
然后我们固定点的归属，调整中心位置。
现在大家的分组订好了，按照规则谁也不许换组。我们现在要移动中心$\mu_j$，让这个组内所有成员的“满意程度最大化”，也就是总距离平方和最小。这是一个纯微积分问题，也就是说，我们现在要最小化的式子就是：

$$Loss(\mu_j) = \sum_{x \in C_j}(x - \mu_j)^2$$

对$\mu_j$求得导数，并令其为零，省略中间不重要的推导部分，我们得到：

$$\mu_j = \frac{1}{n_j} \sum_{x \in C_j} x$$

因此我们知道，算术平均值也就是重心，这就是能让平方误差和变得最小的那个点。因此，把重心挪到重心，误差$J$一定减少。
由于$J$单调递减，所以我们得到K-means一定会收敛。

但正如我们之前讲到的，K-means只能保证收敛到局部最优，而不一定是全局最优。这取决于我们的初始点选的好不好。

HAC vs K-means

特性	K-means	HAC (层次聚类)
输入参数	必须预先指定 $k$	不需要（通过切树决定）
运行效率	快 (线性复杂度 $O(N)$)	慢 (通常 $O(N^3)$ 或 $O(N^2)$)
结果形状	倾向于球状/凸形 (Spherical/Convex)	取决于 Linkage (Single 可以是长条形)
随机性	有随机性 (初始化不同，结果不同)	确定性 (Deterministic)
适用场景	大数据，简单形状	小数据，需要了解层次结构

理解一下这张表选择题大概就没啥问题了。

本章小结

这一章我们学习了两种截然不同的聚类思路：

K-means：简单粗暴，先定K个中心，然后不断迭代。适合大数据，但只能切出球形的类。
HAC (层次聚类)：精细优雅，像消消乐一样不断合并。能展示数据的层级结构，但计算太慢。

K-means是"找中心"，HAC是"找邻居"。

聚类帮我们发现了数据的"分组"结构。但如果数据太复杂、维度太高怎么办？比如一张图片有10000个像素（10000维），我们能不能只用50个数就概括它？

下一章，我们将学习无监督学习的另一大神器——PCA (主成分分析)。我们将学会如何在保留信息的前提下，把高维数据"拍扁"。