一、聚类到底是什么

1.1 从顾客分群开始

假设你经营一家商场，有一万名顾客的数据，每人记录两项特征：年龄和月消费额。把每个人画成二维坐标系中的一个点，横轴表示年龄，纵轴表示月消费额。

你可能观察到三个比较明显的点群：

• 第一群顾客年龄较小、月消费额较低；
• 第二群顾客年龄较小、月消费额较高；
• 第三群顾客年龄较大、月消费额较高。

这些分组并没有预先写在数据里，却可能自然地出现在数据分布中。我们可以利用它们设计不同的促销活动、理解购买行为，或者发现某些不同寻常的顾客。

聚类（Clustering）就是根据样本之间的相似程度，把样本自动归入若干个“类”或“簇”（Cluster），从而发现数据的内部结构。

直觉上的目标是：

尽量让同一个簇里的样本彼此相似，让不同簇里的样本彼此不同。

这里的“类”是算法发现的群体，不一定是现实世界已经命名好的类别。算法可能输出“簇0、簇1、簇2”，但不知道它们的业务含义。解释这些簇仍然需要分析者理解数据背景。

1.2 为什么聚类是无监督学习

监督学习中的训练数据带有已知答案。例如，用已经标注“猫”或“狗”的照片训练分类器。算法的目标是学会根据照片预测这些标签。

无监督学习中的训练数据没有这样的目标标签。聚类算法只接收照片的特征，尝试发现哪些照片彼此相似。它也许能自动形成“体形相近的一群”“毛色相近的一群”，但不会天然知道这些簇应该叫什么名字。

比较项	监督学习	聚类等无监督学习
训练时是否有目标标签	通常有	没有
核心任务	学习输入与已知答案的关系	发现数据的结构或规律
典型输出	类别预测、数值预测	簇的分配、簇的中心或结构
一个例子	判断新水果是不是苹果	自动把水果分成几组

真实数据可能同时包含特征和已知标签，例如带品种名称的花朵数据。如果希望模拟真正的无监督聚类，品种名称不能参与聚类算法的输入；它最多在完成聚类后用于辅助理解结果。

1.3 聚类有什么用

• 客户分群： 根据消费习惯、偏好和活动频率识别不同顾客群体。
• 数据挖掘： 从大量没有标签的记录中发现隐藏模式。
• 模式识别： 组织外观、声音、文本或行为相似的样本。
• 数据探索： 在建模前了解数据大概有几类、哪些区域密集。
• 异常发现： 识别与正常群体明显不同的点，例如异常交易或传感器读数。
• 数据组织与压缩： 用少量典型中心概括大量数据，帮助后续处理。

1.4 聚类没有唯一正确答案

同一批点，不同算法可能得出不同的簇；甚至同一算法更换初始条件，也可能得出不同结果。原因包括：

1. 选用了不同特征或不同特征权重；
2. 使用了不同的距离或相似度；
3. 采用了不同的聚类规则；
4. 预设的簇数或密度阈值不同；
5. 算法随机初始化不同；
6. 数据中存在噪声、离群点或多个合理的划分尺度。

例如，两条互相交错的月牙形点群，按“距哪个中心最近”划分和按“哪些点构成连续的密集区域”划分，会得到很不一样的答案。聚类结果是否有意义，最终还要与分析目的结合判断。

二、聚类的起点：如何衡量样本之间的相似程度

2.1 先用向量描述一个样本

假设一名学生有三个特征：身高、体重、数学成绩，那么他可以表示为向量

\[x=(170,65,90)^T.\]

如果总共有 $n$ 个学生，每名学生有 $m$ 个特征，则样本集合为

\[X=\{x_1,x_2,\ldots,x_n\},\qquad x_i\in\mathbb R^m.\]

可以把它们排成一个矩阵：每列一个样本时，矩阵尺寸为 $m\times n$；每行一个样本时，矩阵尺寸为 $n\times m$。两种约定都可以，只要整篇分析前后一致。

现在的问题是：给定两个向量 $x_i,x_j$，怎样用数字表示它们的差异？

2.2 闵可夫斯基距离：一类距离的总公式

闵可夫斯基距离（Minkowski Distance）定义为：

\[\boxed{d_p(x_i,x_j)=\left(\sum_{r=1}^{m}|x_{ri}-x_{rj}|^p\right)^{1/p}},\quad p\geq1.\]

它的计算思路是：分别观察两个样本在每个特征上的差，再把这些差汇总成一个距离。改变参数 $p$，就能得到不同的距离。

以两个二维点为例：

\[A=(1,1),\qquad B=(4,5).\]

两个坐标方向上的差分别为 $3$ 和 $4$。

曼哈顿距离：$p=1$

\[\boxed{d_1(x,y)=\sum_{r=1}^{m}|x_r-y_r|}.\]

对上面两个点：

\[d_1(A,B)=3+4=7.\]

这像在只能横着或竖着走的棋盘式街道里赶路：横向走3格、纵向走4格，共走7格。

欧氏距离：$p=2$

\[\boxed{d_2(x,y)=\sqrt{\sum_{r=1}^{m}(x_r-y_r)^2}}.\]

对这两个点：

\[d_2(A,B)=\sqrt{3^2+4^2}=5.\]

它就是熟悉的直线距离，也是很多聚类方法最常使用的距离。

切比雪夫距离：$p\to\infty$

\[\boxed{d_\infty(x,y)=\max_r|x_r-y_r|}.\]

对这两个点：

\[d_\infty(A,B)=\max(3,4)=4.\]

它只看差异最大的那个坐标。你可以理解为：如果所有维度的工作能同时进行，总完成时间可能由最慢的一项决定。

距离	计算结果	看待差异的方式
曼哈顿距离	7	各维差异的绝对值相加
欧氏距离	5	两点的直线距离
切比雪夫距离	4	取最大的单维差异

2.3 马哈拉诺比斯距离：考虑数据的分布与相关性

普通欧氏距离忽略了两个现实问题：

• 特征的波动范围可能完全不同；
• 特征之间可能存在相关性。

例如，身高和体重通常相关。对于身高190 cm的人，体重85 kg不一定奇怪；对于身高150 cm的人，同样的体重在样本群体中可能较少见。我们需要判断一个差异相对于整个数据分布是否异常，而不仅仅计算原始数值差了多少。

马哈拉诺比斯距离（Mahalanobis Distance）定义为：

\[\boxed{d_M(x,y)=\sqrt{(x-y)^TS^{-1}(x-y)}},\]

其中 $S$ 是特征的协方差矩阵，尺寸为 $m\times m$，假设它可逆。

通俗地说：

• 某个特征本来波动很大，同样大小的差异可能没那么异常；
• 某个特征本来非常稳定，一点变化可能就值得注意；
• 两个特征经常同步变化时，距离计算要考虑它们之间的共同规律。

当 $S=I$（单位矩阵）时，马哈拉诺比斯距离就退化为欧氏距离。若协方差矩阵不可逆，直接求 $S^{-1}$ 会出问题，实践中需要特征筛选、正则化或其他适当处理。

2.4 相关系数：比较变化趋势

设两名顾客连续三个月的消费分别为：

• 顾客A：100、200、300；
• 顾客B：1000、2000、3000。

两个人的绝对消费额差异很大，但变化趋势完全一致。若关注趋势而不是金额大小，相关系数可能更有意义。

皮尔逊相关系数定义为：

\[\boxed{ r(x,y)= \frac{\sum_{j=1}^{m}(x_j-\bar x)(y_j-\bar y)} {\sqrt{\sum_{j=1}^{m}(x_j-\bar x)^2}\sqrt{\sum_{j=1}^{m}(y_j-\bar y)^2}} }.\]

它的取值通常在 $[-1,1]$ 之间：

• $r\approx1$：高度正线性相关，即一起增大、一起减小；
• $r\approx0$：没有明显的线性相关关系；
• $r\approx-1$：高度负线性相关，即一方增大时另一方减小。

要注意，$-1$ 不代表“毫无关系”，而代表方向完全相反的线性关系。如果关心同向变化，通常希望 $r$ 越接近1越好；如果只关心相关强度，有时会关注 $

r

$。常量向量的标准皮尔逊相关系数没有定义，因为分母为零。

2.5 余弦相似度：比较方向而非长度

余弦相似度（Cosine Similarity）为：

\[\boxed{\operatorname{cos}(x,y)=\frac{x^Ty}{\|x\|\|y\|}}.\]

例如，$x=(1,2)$ 与 $y=(10,20)$ 的长度不同，但方向一致，因此余弦相似度为1。

这尤其适合文本表示等场景。若两个文档在各关键词上的比例接近，但篇幅相差很大，余弦相似度仍可能很高。它反映的是方向是否相似，不等同于数值是否接近。零向量的余弦相似度需要单独处理。

2.6 距离和相似度不要混淆

指标	越相似时的典型表现
欧氏、曼哈顿、切比雪夫、马哈拉诺比斯距离	数值越小
余弦相似度	越接近1（方向越一致）
相关系数	越接近1（同向趋势越一致）

比如两支箭头朝着完全相同的方向，但一支长1米、一支长10米：它们的余弦相似度很高，欧氏距离却不小。选错指标，就可能把“方向相同”和“数值接近”混为一谈。

2.7 距离计算之前要考虑特征尺度

假设聚类使用两个特征：

• 年龄：18～80；
• 年收入：20,000～500,000。

如果不加处理，收入特征的数字远大于年龄。直接使用欧氏距离时，收入很可能主导结果，即使年龄对问题同样重要。

一种常见做法是标准化，例如将每个特征变成：

\[z=\frac{x-\mu}{\sigma},\]

其中 $\mu$ 是特征均值，$\sigma$ 是特征标准差。标准化不是永远必需的，但在基于距离的聚类中，需要主动检查量纲、异常值和特征权重。

三、簇是什么：从集合定义到簇的统计特征

3.1 硬聚类与软聚类

硬聚类（Hard Clustering）要求每个样本只能属于一个簇。若两个簇不同，则：

\[G_i\cap G_j=\varnothing,\quad i\neq j.\]

例如某人最终被归入“第2类顾客”，就不同时属于其他类。K-Means 与这里讨论的普通凝聚层次聚类都是硬聚类。

软聚类（Soft Clustering）允许一个样本以不同程度属于多个簇。例如顾客A属于高消费群体的程度为0.7，属于另一群体的程度为0.3。软聚类更适合描述边界不清晰、存在混合特征的对象。

3.2 四种定义“簇内足够接近”的方式

设 $G$ 为一个簇，其中有 $n_G$ 个样本，$d_{ij}$ 为样本 $i,j$ 的距离，$T,V>0$ 为距离阈值。以下讨论默认 $n_G\ge2$。

定义一：任意两个成员都不能太远

\[\boxed{d_{ij}\le T,\quad\forall x_i,x_j\in G}.\]

这是最容易理解、约束也最严格的条件：簇中任何两个人都必须互相够近。如果只要有两人距离超过上限，就不能满足这一条件。

定义二：每个人至少有一个近邻

\[\boxed{\forall x_i\in G,\ \exists x_j\in G,\ j\ne i:\ d_{ij}\le T}.\]

这允许链条式结构：A靠近B、B靠近C、C靠近D，即使A与D距离很远，只要每个点都有至少一个近邻，这个集合仍然满足条件。

定义三：每个人与其他成员的平均距离不超过阈值

\[\boxed{\frac1{n_G-1}\sum_{\substack{x_j\in G\\j\ne i}}d_{ij}\le T,\quad\forall x_i\in G}.\]

它不再检查每一对距离是否都短，而是要求每个成员平均而言不会离大家太远。

定义四：平均距离和最大距离同时受约束

\[\boxed{\frac1{n_G(n_G-1)}\sum_{x_i\in G}\sum_{x_j\in G}d_{ij}\le T},\]

并且要求：

\[\boxed{\max_{x_i,x_j\in G}d_{ij}\le V}.\]

第一项控制整体平均距离，第二项防止少数点相距特别远。若 $V\ge T$，定义一能够推出后面三种条件：既然每一对距离都不超过T，任何平均值也不会超过T，而且每个人都有近邻。

四种定义并不等价，它们代表了不同的“紧密程度”要求。

3.3 用什么数字描述一个簇

簇中心（Centroid）

簇内所有样本的均值：

\[\boxed{\bar x_G=\frac1{n_G}\sum_{x_i\in G}x_i}.\]

例如，簇内有 $(1,1),(2,2),(3,3)$ 三个二维点，中心就是 $(2,2)$。中心是群体的平均位置，不要求它恰好是某个真实样本。

簇直径（Diameter）

簇内距离最远的两个点之间的距离：

\[\boxed{D_G=\max_{x_i,x_j\in G}d(x_i,x_j)}.\]

直径越小，簇通常越紧凑，但它由最远的一对点决定，因此容易受到极端点影响。

样本散布矩阵（Scatter Matrix）

\[\boxed{A_G=\sum_{x_i\in G}(x_i-\bar x_G)(x_i-\bar x_G)^T}.\]

它描述簇内样本围绕中心的分散情况。不仅能刻画“散得有多厉害”，还可以反映“主要沿哪个方向散开”。

样本协方差矩阵（Covariance Matrix）

\[\boxed{S_G=\frac1{n_G-1}A_G},\qquad n_G>1.\]

它与散布矩阵的区别在于增加了按样本数进行的校正。注意分母是 簇内样本数减1，不是特征维数减1。

假设二维点云形成一条倾斜的椭圆，协方差矩阵可以反映它沿某个方向延伸较长，以及两个坐标的相关关系。若点云近似圆形，两个方向上的分散情况可能更接近。

3.4 两个簇之间的距离：连接方式（Linkage）

样本间的距离并不等同于簇间的距离。两个簇可能各自包含几十个点，怎样概括它们之间到底有多远？

设两个簇为 $G_p,G_q$，样本数分别为 $n_p,n_q$。

单连接（Single Linkage）

\[\boxed{D(G_p,G_q)=\min_{x_i\in G_p,\,x_j\in G_q}d(x_i,x_j)}.\]

只看两个簇中最近的一对点。优点是允许细长、不规则的簇，缺点是容易被一串中间点连接，出现链式效应。

完全连接（Complete Linkage）

\[\boxed{D(G_p,G_q)=\max_{x_i\in G_p,\,x_j\in G_q}d(x_i,x_j)}.\]

看最远的一对点。它倾向于生成更加紧凑的簇，但对极端点可能敏感。

中心连接（Centroid Linkage）

\[\boxed{D(G_p,G_q)=d(\bar x_p,\bar x_q)}.\]

只比较两个中心。计算直观，但即使两簇中心相近，其内部样本的形状和范围也可能很不同。

平均连接（Average Linkage）

\[\boxed{D(G_p,G_q)=\frac1{n_pn_q}\sum_{x_i\in G_p}\sum_{x_j\in G_q}d(x_i,x_j)}.\]

把所有跨簇样本对的距离求平均，综合考虑两个簇的全部成员。

Ward 连接

Ward 方法不直接取最近、最远或平均的点对距离，而是询问：合并这两个簇，会让内部平方误差增加多少？

在平方欧氏距离下，合并代价可以写成：

\[\boxed{\Delta(A,B)=\frac{n_An_B}{n_A+n_B}\|\bar x_A-\bar x_B\|^2}.\]

Ward 方法优先合并使这一增量最小的两个簇，因此常产生内部较紧凑的分组。

连接方式	决策依据	直观特征
Single	最近的一对点	容易连接链状结构
Complete	最远的一对点	倾向紧凑的簇
Centroid	两个簇中心的距离	强调平均位置
Average	所有跨簇点对的平均距离	综合考虑多个点
Ward	合并导致的平方误差增量	倾向内部紧凑、差异较小的簇

四、层次聚类：让样本形成一棵树

4.1 核心思想

想象学校组织社团。最开始每个学生都是一个独立的小组，之后兴趣接近的学生合并为小组，相关的小组合并为大组，最后形成更大的组织。这个过程不仅得到最后的分类，还保留了“小组属于哪个大组”的层次关系。

层次聚类（Hierarchical Clustering）就试图发现这种结构。

它与 K-Means 的重要区别是：层次聚类的结果包含层层合并或分裂的关系；K-Means 通常只给出某个层次上的平坦分组。

4.2 两种基本方向

凝聚型（Agglomerative / Bottom-up）从下往上：

1. 每个样本先独立形成一个簇；
2. 找到当前距离最近的两个簇；
3. 合并为新簇；
4. 更新相关距离；
5. 重复，直到满足停止条件。

分裂型（Divisive / Top-down）从上往下：

1. 所有样本起初属于一个大簇；
2. 找到需要拆分的簇；
3. 按照某种规则分成两个子簇；
4. 不断继续拆分，直到满足停止条件。

两种方法方向相反，但不意味着它们一定得出完全相同的树。

4.3 凝聚层次聚类的完整流程

在真正运行前，要回答三个问题：

1. 怎样度量相似？ 例如欧氏距离或适合问题的其他距离。
2. 怎样计算簇间距离？ 例如 Single、Complete、Average、Ward。
3. 什么时候停止？ 例如只剩下指定数量的簇；或者下一次合并距离太大；或者合并后簇直径将超过上限。

如果一直合并到只剩一个簇，就能得到完整的层次结构；如果提前停止，则得到指定粒度的分组。

4.4 一个五样本的完整手算例子

假设有5个样本 $x_1,\ldots,x_5$，已经计算出距离矩阵：

\[D=\begin{bmatrix} 0&7&2&9&3\\ 7&0&5&4&6\\ 2&5&0&8&1\\ 9&4&8&0&5\\ 3&6&1&5&0 \end{bmatrix}.\]

例如 $d(x_1,x_2)=7$，$d(x_3,x_5)=1$。矩阵对称，主对角线为0。

现在使用单连接做凝聚聚类。

第一步： 每个样本独立成簇：

\[\{1\},\{2\},\{3\},\{4\},\{5\}.\]

第二步： 全局最小的非零距离是 $d(3,5)=1$，因此把样本3和5合并：

\[G_6=\{3,5\}.\]

第三步： 更新新簇与其他簇的距离。例如：

\[D(G_6,\{1\})=\min\{d(3,1),d(5,1)\}=\min(2,3)=2.\]

这是当前最小距离，所以样本1并入：

\[G_7=\{1,3,5\}.\]

第四步： 剩下 ${1,3,5},{2},{4}$。因为 $d(2,4)=4$ 是当前最小的簇间距离，合并为：

\[G_8=\{2,4\}.\]

第五步： 最后两个簇 ${1,3,5}$ 和 ${2,4}$ 的单连接距离为5，继续合并得到所有样本组成的大簇。

次序	合并高度	新形成的簇	剩余簇数
初始	—	5个单点簇	5
1	1	${3,5}$	4
2	2	${1,3,5}$	3
3	4	${2,4}$	2
4	5	${1,2,3,4,5}$	1

这个过程体现了层次聚类最重要的逻辑：每次找当前最近的两个簇，合并，再更新距离。

4.5 树状图（Dendrogram）怎么读

树状图用分叉结构表现合并过程：

• 底部的叶子代表原始样本；
• 两个分支连接的位置表示发生了一次合并；
• 纵轴表示合并高度，对应所采用连接准则的距离或高度；
• 合并高度低的簇通常更早合并。

如果在某个纵向高度画一条水平截断线，观察它穿过多少个尚未并在一起的分支，就能得到该高度下的簇数。

在前面的五样本例子中：

• 截断高度在2和4之间，可得到3个簇；
• 截断高度在4和5之间，可得到2个簇；
• 截断高度高于5，则所有样本属于1个簇。

另一个例子中，六个样本 A、B、C、D、E、F 可依次发生 ${E,F}$、${A,B}$、${D,E,F}$、${C,D,E,F}$ 等合并，最终并成大簇。树状图比单独的簇标签提供了更多信息：它告诉我们这些群体是怎样一步步形成的。

4.6 层次聚类的复杂度和局限

一个直接、没有优化的实现如果反复搜索所有簇间距离并计算或更新距离，计算成本可能较高。以每次直接重新计算距离的朴素方式估计，时间复杂度可以达到 $O(n^3m)$ 的量级；不同连接规则和专门优化实现可能更高效。

主要优点：

• 能产生完整层次结构；
• 最终簇数可以在生成树之后通过截断确定；
• 适合展示较小数据集中的分组关系；
• 可以通过不同连接方式改变对簇形状的偏好。

主要局限：

• 对大规模样本可能耗时、占用较多内存；
• 普通凝聚方法一旦合并通常不会撤销；
• 距离和连接方式会显著改变结果；
• Single 容易出现链式效应，异常点可能影响合并顺序。

五、K-Means：通过反复移动中心来分组

5.1 一个快递站选址的直觉

假设一座城市有大量客户，要建立3个快递服务站。希望每位客户去最近的服务站，并且每个服务站尽量位于其负责客户的中心位置。

一种直观方案是：

1. 先选3个临时服务站位置；
2. 每位客户去最近的站点；
3. 计算各站点所服务客户的平均位置；
4. 把站点移到新的平均位置；
5. 让客户重新选择最近的站点；
6. 反复执行，直到分配基本不再变化。

这就是 K-Means（K均值聚类）的核心机制：分配样本、更新均值中心、重复迭代。

5.2 K 是什么，为什么要提前指定

K 表示希望得到的簇数量。例如 K=3 就表示把样本划分为3个簇。它是算法运行前确定的超参数，不是在标准 K-Means 迭代过程中自动学习出来的簇数。

不要和 KNN（K近邻）混淆：K-Means 的 K 是簇数，KNN 的 K 是进行邻居投票时考虑的邻居数。K-Means 是无监督聚类；常见的 KNN 分类属于监督学习。

5.3 K-Means 的数学模型

给定样本集合 $X={x_1,\ldots,x_n}$，希望将其划分为 $K$ 个非空簇 $G_1,\ldots,G_K$，要求：

\[G_i\cap G_j=\varnothing\ (i\ne j),\qquad \bigcup_{l=1}^{K}G_l=X.\]

定义 $C(i)$ 表示第 $i$ 个样本所属的簇编号：

\[C(i)\in\{1,2,\ldots,K\}.\]

K-Means 的优化目标是，让样本到所属簇中心的平方欧氏距离总和尽可能小：

\[\boxed{W(C,\mu)=\sum_{l=1}^{K}\sum_{i:C(i)=l}\|x_i-\mu_l\|^2}.\]

这个值也称为 WCSS（Within-Cluster Sum of Squares）或 Inertia。它越小，说明样本相对于当前簇中心越集中，但必须注意：不同 K 的 WCSS 不能直接拿“越小越好”作为最终选 K 的唯一理由。

5.4 为什么用平方距离，为什么中心取均值

设某个簇有 $r$ 个样本，中心为 $\mu$。我们希望最小化：

\[J(\mu)=\sum_{i=1}^{r}\|x_i-\mu\|^2.\]

对 $\mu$ 求导：

\[\frac{\partial J}{\partial\mu}=2r\mu-2\sum_{i=1}^{r}x_i.\]

令导数为0，得到：

\[\boxed{\mu=\frac1r\sum_{i=1}^{r}x_i}.\]

因此，固定某个簇中的成员后，使平方误差总和最小的中心，就是这些成员的算术平均值。这解释了“K-Means”名字里的“均值”。

平方项也会更强烈地惩罚离中心较远的样本，因此 K-Means 对异常点可能敏感。

5.5 迭代算法的两个交替步骤

初始化： 选择 K 个初始中心 $\mu_1^{(0)},\ldots,\mu_K^{(0)}$。

分配步骤： 在中心固定时，把样本分配给最近的中心：

\[\boxed{C(i)=\arg\min_l\|x_i-\mu_l\|^2}.\]

更新步骤： 在分配固定时，重新计算各簇均值：

\[\boxed{\mu_l=\frac1{|G_l|}\sum_{x_i\in G_l}x_i}.\]

然后重复分配、更新，直到簇标签不再改变、中心移动足够小，或达到迭代上限。若出现等距点，需要明确平局处理规则；若某个簇变为空簇，实际实现还需要专门处理。

每个主要步骤都在固定另一组变量的情况下减少或保持 WCSS，因此 WCSS 不会因这些步骤而上升。它最终通常收敛到一个局部最优，但不保证全局最优。

5.6 五个对角线点：完整观察中心移动

假设有5个二维点：

\[(1,1),(2,2),(3,3),(4,4),(5,5).\]

选 K=2，初始中心为：

\[\mu_1=(1,1),\qquad\mu_2=(2,2).\]

第一次分配后：

\[G_1=\{(1,1)\},\quad G_2=\{(2,2),(3,3),(4,4),(5,5)\}.\]

更新中心：

\[\mu_1=(1,1),\qquad\mu_2=(3.5,3.5).\]

第二次分配时，点 $(2,2)$ 发现自己离第一个中心更近，因此改投第一个簇：

\[G_1=\{(1,1),(2,2)\},\quad G_2=\{(3,3),(4,4),(5,5)\}.\]

再次更新中心：

\[\boxed{\mu_1=(1.5,1.5),\qquad\mu_2=(4,4)}.\]

继续分配后簇不再变化，于是停止。

簇	最终成员	最终中心
1	(1,1)、(2,2)	(1.5,1.5)
2	(3,3)、(4,4)、(5,5)	(4,4)

5.7 新样本如何归入已经形成的簇

假设最终中心就是 $(1.5,1.5)$ 与 $(4,4)$：

• 新样本 $(0,0)$ 更接近第一个中心，归入簇1；
• 新样本 $(4,5)$ 更接近第二个中心，归入簇2；
• 新样本 $(2.75,2.75)$ 恰好位于两个中心的中点，与它们等距，必须使用约定的平局规则。

由此可见，K-Means 把空间划分为一块块“离哪个中心最近”的区域。这也说明为什么它在两个相互缠绕的月牙形簇上容易失败：月牙的边界未必能由最近中心合理刻画。

5.8 初始中心为何会改变最终结果

再考虑5个点：

\[\begin{aligned} x_1&=(0,2),\\ x_2&=(0,0),\\ x_3&=(1,0),\\ x_4&=(5,0),\\ x_5&=(5,2). \end{aligned}\]

取 K=2。

情况A： 以 $x_1=(0,2)$、$x_2=(0,0)$ 为初始中心。迭代后可能得到：

\[G_1=\{x_1,x_5\},\quad G_2=\{x_2,x_3,x_4\},\]

中心为 $(2.5,2)$、$(2,0)$，其 WCSS 为：

\[W_A=26.5.\]

情况B： 换成 $x_1=(0,2)$、$x_5=(5,2)$ 为初始中心，则可得到：

\[G_1=\{x_1,x_2,x_3\},\quad G_2=\{x_4,x_5\},\]

中心为 $(1/3,2/3)$、$(5,1)$，其 WCSS 为：

\[W_B=\frac{16}{3}\approx5.33.\]

同样的数据、同样的 K，$W_A$ 与 $W_B$ 相差明显。这是 K-Means 可能落入不同局部最优的直接证据。

常见改进方法包括：采用 K-Means++ 初始化、多次使用不同初始中心运行并选择 WCSS 较低的结果、固定随机种子以便重现实验。K-Means++ 也不能保证全局最优。

5.9 为什么不枚举所有划分来寻找全局最优

把 $n$ 个不同样本划分为 K 个非空、无序簇，可能的划分数量是第二类斯特林数：

\[\boxed{S(n,K)=\frac1{K!}\sum_{l=1}^{K}(-1)^{K-l}\binom Kl l^n}.\]

当 K 固定且 $n$ 增大时，数量大致按 $K^n/K!$ 增长，非常快。求解一般情况下的全局最优 K-Means 是 NP 困难问题，因此实践中采用快速迭代、初始化改进和多次尝试，而不是枚举所有划分。

5.10 复杂度、优点和局限

如果有 $n$ 个样本、每个样本 $m$ 个特征、K 个中心，则每轮通常需要 $O(nKm)$ 的距离计算。迭代 $t$ 轮，总计算量约为：

\[\boxed{O(tnKm)}.\]

优点：简单、易理解、速度通常较快，适合大量数据中大致紧凑的簇。

局限：必须指定 K；受初始中心、异常点和特征尺度影响；倾向中心式、近似球状的簇；只找到局部最优；结果通常没有层次结构。

K-Means 还有一个关键问题：真正合适的 K 常常并不知道。 下一章就围绕这个问题展开。

六、X-Means：让 K-Means 尝试自己决定簇数

6.1 K-Means 的最大难题之一：K 应该是多少

回到快递站选址的例子：如果已经决定建3个站点，K-Means 能帮助调整位置。但城市究竟需要建2个、3个、5个还是10个站点呢？这个问题本身并不由标准 K-Means 解决。

一种方法是人工尝试很多 K，然后比较结果。例如分别跑 K=2、3、4、5……，画 WCSS 曲线找“肘部”，或者对各个 K 计算轮廓系数。这确实可行，但需要人判断：肘部在哪里？不同指标冲突怎么办？到底要试到多大的 K？

X-Means 的目的，就是在保留 K-Means 基本思想的同时，让算法尝试调整簇数，并用模型选择标准判断是否值得增加新的簇。

可以把两者的区别概括为：

• K-Means：K 已经确定，我来把中心放好。
• X-Means：先放好已有的中心，再判断哪些簇值得拆成两个，逐步增加 K。

X-Means 由 Dan Pelleg 和 Andrew Moore 在2000年提出，名称里的 X 并不是一个待求的普通变量，而是该算法的名称。

6.2 X-Means 不是完全不需要参数

常见的 X-Means 需要设定一个搜索范围：

\[\boxed{K_{\min}\le K\le K_{\max}}.\]

例如，可以从 $K_{\min}=2$ 开始，最多允许到 $K_{\max}=10$。

这与 K-Means 直接指定 $K=5$ 不同，但也不能理解为“完全不用考虑簇数”。如果真实数据需要12个簇，而上限设置为10，算法不会突破这个上限。反过来，上限设置得过高，也可能增加计算负担或放大模型选择的误差。

X-Means 通常还会使用初始中心、收敛条件和模型评分准则等设置。

6.3 核心机制：先优化位置，再尝试改变结构

X-Means 的工作分为两个反复交替的部分。

第一部分：优化参数（Improve-Parameters）

假设目前有 K 个簇，先执行普通 K-Means：

1. 把样本分给最近的中心；
2. 重新计算每个簇的均值中心；
3. 重复，直到分组相对稳定。

此时，在当前簇数 K 不变的条件下，尽量把中心位置调整合理。

第二部分：改善结构（Improve-Structure）

接下来分别检查每个簇：

这个簇真的只需要一个中心吗？还是拆成两个簇会更合理？

一种典型做法是，对某个现有簇中的数据局部运行 K=2 的 K-Means，得到两个候选子簇。此时有两个竞争方案：

• 父模型： 保持当前一个簇、一个中心；
• 子模型： 改成两个子簇、两个中心。

然后分别计算模型评分。如果评分认为两个子簇值得保留，就接受分裂；否则继续保持原来的一个簇。

接受一批分裂以后，整个数据集的簇数增加。算法可以重新运行 K-Means 调整所有中心，然后再次检查各个簇是否还值得分裂。

因此，X-Means 并不是“一开始就把数据切成很多份”。它是从相对较少的簇出发，边优化、边生长。

6.4 为什么不能只比较分裂前后的 WCSS

这里有一个关键问题。

假设某个簇用一个中心描述，其 WCSS 为100。拆成两个簇以后，WCSS 降为70。

是否一定要拆？

不能这么判断。

因为增加一个中心通常就能让 WCSS 下降。继续拆成3个、4个、10个簇，WCSS 还可能继续下降。只看 WCSS，算法很容易倾向于生成越来越多的簇，最终每个点单独成簇，失去概括数据的意义。

X-Means 因此需要一种更全面的判断：

1. 模型有没有更好地解释数据？
2. 为了得到这种改善，新增了多少模型参数？

这就是下面的 BIC。

6.5 BIC：在“拟合得好”和“模型别太复杂”之间折中

BIC 全称为 Bayesian Information Criterion，中文常称贝叶斯信息准则。

一种常见写法是：

\[\boxed{\operatorname{BIC}_{+}(M)=\log \hat L(M)-\frac{p}{2}\log N}.\]

其中：

• $M$：候选模型，例如“一个簇”或“两个子簇”；
• $\hat L(M)$：在该模型下，参数取最优估计时的数据似然；
• $p$：模型中的自由参数数量；
• $N$：用于评价的数据样本数。

这套符号下，BIC 越大越好。

公式中的两个部分，可以这样理解：

第一项：$\log\hat L(M)$ ——模型解释数据的能力。拟合得越好，这项通常越大。

第二项：$\frac p2\log N$ ——模型复杂度的惩罚。参数越多，惩罚一般越大。

它体现了一个很合理的原则：

如果增加一组中心只能让拟合略微改善，却使模型复杂很多，就不值得分裂；如果新增的中心显著改善了对数据的解释，即使有复杂度代价，也可能值得接受。

另一个同样常见的等价写法是：

\[\boxed{\operatorname{BIC}_{-}(M)=-2\log\hat L(M)+p\log N}.\]

这时越小越好。两种写法之间只是乘上了 $-2$，比较方向相反，并非两种不同的理论。阅读资料或使用软件时，务必先确认采取哪一种定义。

BIC 中的“似然”从哪里来

K-Means 本身只定义了中心和平方误差，没有直接定义概率。要计算 BIC，X-Means 通常采用与 K-Means 相配合的概率假设，例如把每个簇近似看成围绕中心分布的、球形的高斯数据群。

在这种假设下，可以根据簇的中心、散布程度、样本数量等估计数据的概率，从而计算似然以及 BIC。

这意味着：X-Means 自动选择簇数的能力并不是完全没有前提的。 如果真实数据极度不符合其模型假设，BIC 做出的分裂判断也可能不理想。

自由参数个数 $p$ 的具体表达式取决于模型实现如何处理簇中心、混合权重和方差。不同实现可能使用不同的近似或评分细节，但核心都是“拟合收益减去复杂度惩罚”。

6.6 怎样用 BIC 决定分不分裂

设 $M_1$ 表示父模型（一个簇），$M_2$ 表示子模型（两个簇）。采用上面“越大越好”的 BIC 写法时，计算：

\[\Delta\operatorname{BIC}=\operatorname{BIC}_{+}(M_2)-\operatorname{BIC}_{+}(M_1).\]

那么：

• $\Delta\operatorname{BIC}>0$：子模型评分更好，可以接受分裂；
• $\Delta\operatorname{BIC}\le0$：分裂收益不足，保留父模型。

例如，下面的数字只是用来说明比较方式：

候选方案	BIC（越大越好）	结论
当前一个簇	-180	基准
拆成两个簇	-167	-167更大，接受分裂

如果拆成两个簇后的 BIC 反而是 -195，则不应接受这次分裂。

注意，不是所有簇都必须分裂，也不是每轮都必须增加簇数。 分裂是一个通过模型选择检验的决定。

6.7 一个完整的 X-Means 直觉例子

假设一批二维点在图上大致分成三块：

• 左边偏上的密集小群；
• 左边偏下的密集小群；
• 右边的一片密集群。

现在只知道这些点可能分成2～8个簇，于是设置：

\[K_{\min}=2,\qquad K_{\max}=8.\]

第一阶段：先运行 K=2 的 K-Means。

可能得到：

• 簇A：把左边偏上和左边偏下的两个小群合成一个较大的簇；
• 簇B：右边的密集群。

第二阶段：检查簇A能否分裂。

对簇A内部运行局部 K=2 的 K-Means，尝试形成 A1、A2 两个子簇。两个小群确实相隔较远，分裂后的模型解释力有明显改善。如果 BIC 足够支持这种改进，就接受：

\[A\longrightarrow A_1+A_2.\]

第三阶段：检查簇B。

如果簇B本来就分布得比较集中，强行拆成B1、B2并没有带来足够的收益，BIC 就可能拒绝分裂。

第四阶段：重新运行 K-Means。

现在共有3个中心，让所有样本重新分配并更新中心位置。再次检查各个簇，如果再没有值得接受的分裂，就停止。

最终算法可能自己选择：

\[\boxed{K=3}.\]

这个结果并不是因为人事先指定了3，而是算法在允许的范围内，根据分裂候选与模型评分决定的。

6.8 X-Means 的完整流程

把以上步骤整理成通用流程：

1. 输入数据和允许的簇数范围 $[K_{\min},K_{\max}]$。
2. 初始化少量中心，通常从下限 K 开始。
3. 优化当前中心位置，执行普通 K-Means，直到分配相对稳定。
4. 逐簇提出分裂候选：对每个当前簇局部尝试 K=2 的划分。
5. 比较模型评分：计算分裂前与分裂后的 BIC，判断拆分收益能否抵消复杂度代价。
6. 接受有价值的分裂，同时遵守 $K_{\max}$ 上限；如果候选过多，可以按评分改善程度选择一部分。
7. 重新优化全部中心，使新增中心与已有中心协同调整。
8. 继续尝试分裂；当没有可接受的分裂、达到簇数上限或满足其他停止条件时结束。

最终输出的是自动估计的簇数，以及对应的样本分配和中心位置。

6.9 X-Means 与 K-Means 的关系

X-Means 继承了 K-Means 的三个基本特征：

1. 使用中心代表簇；
2. 将样本分配给附近中心；
3. 通过均值更新中心。

新增的能力，是通过模型选择决定是否增加中心。但它没有从根本上改变 K-Means 的形状偏好。

对比	K-Means	X-Means
簇数 K	预先指定一个值	在给定范围内尝试估计
中心如何更新	均值迭代	仍然使用均值迭代
是否检查局部拆分	通常不检查	会尝试把现有簇拆成两个
如何判断增加簇数	需要外部方法	使用 BIC 等模型选择准则
适合的簇	近似紧凑、球状	依然更适合类似形状
异常点处理	通常都分配到某个簇	通常也不专门把异常点剔除

6.10 X-Means 与肘部法有什么区别

肘部法通常需要人为尝试多个固定 K，并观察 WCSS 曲线出现明显拐点的位置。X-Means 则通过局部拆分和 BIC 判断，在算法内部决定是否增加中心。

两者都试图回答“几个簇合适”，但并不保证给出相同答案：

• 肘部法判断的是 WCSS 下降速度变化；
• X-Means 的 BIC 同时关注拟合改善和模型复杂度；
• 肘部法常带有人工判断，X-Means 更偏自动化；
• 如果数据的真实结构不符合中心式、球状簇的假设，两者都可能失败。

6.11 X-Means 的优点与局限

优点：

• 不要求使用者提前给出唯一固定的 K；
• 在分裂过程中动态增加中心；
• 通过 BIC 平衡拟合程度与模型复杂度；
• 相比完全枚举所有可能的簇数和所有划分，可以避免许多没有必要的候选搜索；
• 保留了 K-Means 相对直观的中心式结构。

局限：

• 仍需合理设定 $K_{\min}$ 与 $K_{\max}$；
• 依然受初始化、特征尺度、异常点与局部最优影响；
• BIC 决策依赖概率模型假设，数据不符合假设时可能错分或漏分；
• 对细长、月牙形或不同密度的复杂簇，不一定有良好表现；
• 每轮需要尝试局部划分和模型评分，通常比只运行一次固定 K 的 K-Means 更费时；
• 不保证一定找到真实簇数，也不保证一定比对多个 K 直接做模型比较更快。

X-Means 也可使用 AIC 等信息准则变体。BIC 通常对模型复杂度施加更明确的样本规模相关惩罚。无论选择哪一种评分方法，自动选 K 都是基于一套假设进行的估计，而不是自动发现唯一的自然真相。

七、如何评价聚类结果，如何选择簇数

一个聚类算法把样本分好以后，并不意味着分组一定有意义。我们需要考虑：

• 同簇样本是否足够紧凑？
• 不同簇之间是否分开？
• 有没有把一个自然群体分得过碎，或者把多个群体硬凑在一起？
• 结果对初始中心或参数是否稳定？

下面介绍几个常用的内部聚类有效性指标。所谓内部，是指主要使用样本及其聚类结果评价，不要求提前知道每个样本的真实类别。

7.1 WCSS：固定 K 时关注簇内紧凑度

WCSS（簇内平方误差和）为：

\[\boxed{WCSS=\sum_{l=1}^{K}\sum_{x_i\in G_l}\|x_i-\mu_l\|^2}.\]

你可以想象每个点与其中心之间有一根橡皮筋。WCSS 越小，表示这些点整体离各自中心越近。在同一数据、相同 K、相同特征尺度下，WCSS 较小通常说明 K-Means 的目标函数优化得更好。

但仅凭 WCSS 不能判断 K 应该取多少。因为增加簇数通常能够降低 WCSS：极端情况下，每个样本单独成为一个簇，WCSS 就等于0，却完全失去了概括数据的作用。

7.2 肘部法（Elbow Method）

肘部法的操作是：

1. 分别对 K=1、2、3、4……运行 K-Means；
2. 记录每种 K 对应的 WCSS；
3. 画出横轴为 K、纵轴为 WCSS 的曲线；
4. 寻找从“下降很快”变为“下降缓慢”的转折点。

假设得到如下示意结果：

K	WCSS（示意值）	变化趋势
1	1000	一个簇，误差很大
2	550	明显下降
3	280	继续明显下降
4	230	下降开始变缓
5	200	改善幅度较小
6	180	改善幅度进一步减小

此时 K=3 是值得考虑的选择：再多加簇仍可改善 WCSS，但改善越来越有限。

称为“肘部”，是因为曲线在拐点附近有时像弯曲的手肘。但肘部法只是经验方法，真实数据不一定有明显拐点，选择也可能受主观判断影响。

还有一种相关思路是观察簇的平均直径：

\[\overline D=\frac1K\sum_{l=1}^{K}D_{G_l}.\]

簇数过少时，每个簇可能很大；簇数增多后，簇往往变得更小、更紧凑。我们可比较不同 K 下的平均直径，但同样不能只追求“越小越好”，否则会倾向过度拆分。

7.3 轮廓系数（Silhouette Score）：同时考虑簇内与簇间

假设一个学生被分到A组。我们关心两件事：

1. 他与A组其他成员是否亲近？
2. 他与别的组是否相隔较远？

对于样本 $i$，定义：

• $a(i)$：它与同簇其他样本的平均距离；
• $b(i)$：它与每个其他簇的平均距离中，最小的那一个。

注意：$b(i)$ 不是某一个最近外部点的距离，而是比较其他簇的平均距离。

轮廓系数为：

\[\boxed{s(i)=\frac{b(i)-a(i)}{\max\{a(i),b(i)\}}}.\]

它通常在 $[-1,1]$ 范围内：

轮廓系数	直观含义
接近1	更靠近自身簇，远离其他簇
接近0	接近两个簇的分界区域
小于0	可能被分错簇，离其他簇反而更近
接近-1	当前分组可能很不合理

举个计算例子。如果 $a(i)=0.32$，$b(i)=1.04$，那么：

\[s(i)=\frac{1.04-0.32}{1.04}\approx\boxed{0.69}.\]

这个点的分组较为合理：它与自身簇的平均距离明显小于与最近其他簇的平均距离。

整个聚类结果的轮廓系数是全部样本轮廓系数的平均：

\[\boxed{S=\frac1n\sum_{i=1}^{n}s(i)}.\]

通常希望越高越好。只有一个成员的簇通常将其轮廓系数按约定记为0；整体指标按通常定义需要至少2个簇，而且簇数小于样本数。

7.4 Davies–Bouldin 指数（DB指数）

DB 指数关注：簇内有多分散，与簇间有多接近，两者相比怎样？

先给出一种使用平方距离的版本：

\[S_i=\frac1{|G_i|}\sum_{x\in G_i}\|x-z_i\|^2, \qquad d_{ij}=\|z_i-z_j\|^2,\]

其中 $z_i$ 为第 $i$ 个簇中心，$S_i$ 描述该簇内部平均平方距离，$d_{ij}$ 描述两个中心的平方距离。

对每个簇，找一个最难与之区分的其他簇：

\[R_i=\max_{j\ne i}\frac{S_i+S_j}{d_{ij}}.\]

再对所有簇求平均：

\[\boxed{DB=\frac1K\sum_{i=1}^{K}R_i}.\]

如果两个簇内部都很松散、中心又靠得很近，分子大、分母小，DB 指数就会变大。因而：

\[\boxed{\text{DB 指数通常越小越好。}}\]

DB 指数在不同资料和实现中也有以平均欧氏距离而非平均平方欧氏距离定义 $S_i$ 与中心距离的形式；必须使用相同定义才能直接比较数值。若两个中心完全重合，公式中的分母还需要特殊处理。

7.5 Dunn 指数：最窄的簇间间隔与最大的簇内跨度

Dunn 指数的直觉是：两个簇之间最靠近的地方，和某个簇内部最远的跨度相比，够不够大？

先定义簇直径：

\[\Delta(G_i)=\max_{x,y\in G_i}d(x,y).\]

再定义两个簇之间的最短距离：

\[\delta(G_i,G_j)=\min_{x\in G_i,\,y\in G_j}d(x,y).\]

于是：

\[\boxed{V_D=\frac{\min_{i\ne j}\delta(G_i,G_j)}{\max_l\Delta(G_l)}}.\]

分子越大，说明不同簇至少有一段明显间隔；分母越小，说明簇内部不会延伸得太远。因此：

\[\boxed{\text{Dunn 指数通常越大越好。}}\]

它的一个问题是对极值敏感：最靠近的跨簇点对、最远的簇内点对都可能受到噪声影响。

7.6 评价指标的方向与用途

指标	核心含义	通常希望
WCSS / Inertia	到所属中心的平方距离总和	固定 K 时越小越好
肘部法	WCSS 随 K 增大，何处开始明显变缓	选择有解释意义的拐点
平均簇直径	簇内部的典型最大跨度	倾向较小，但不能无限拆分
轮廓系数	簇内紧凑与簇间分离的相对关系	越大越好，最高为1
DB指数	内部离散程度相对于簇间距离	越小越好
Dunn指数	最小簇间距离与最大簇内直径之比	越大越好
X-Means 的 BIC	拟合能力与模型复杂度的折中	取决于定义，常用版本越大越好

这些指标不会始终一致，因为它们在强调不同的事情。例如一个细长月牙簇可以在空间中与另一个月牙清楚分离，但以中心式、球状簇为偏好的指标未必最欣赏这种结构。

所以评价聚类结果时，应综合考虑指标、簇的几何形状、稳定性和实际分析目的。

八、DBSCAN：根据密度发现簇和噪声

8.1 从“附近有多少人”理解密度

假设站在地图上观察城市人口：

• 市中心有大量紧密分布的人；
• 郊区也有一个比较集中的社区；
• 两个社区之间有零星住户；
• 很远处还有孤立的一栋房屋。

如果我们关注的是“密集区域”，而不是“到哪个中心最近”，自然会采用另一种分组方法。

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）正是这样一种基于密度、能够识别噪声点的聚类算法。

它不要求簇一定围绕一个中心，也不要求提前指定 K。只要一片足够密集的区域能通过密集点连续连接，就可以形成一个簇。

8.2 两个关键参数：eps 与 min_samples

eps（$\varepsilon$）是邻域半径。以点 $x$ 为中心，考虑距离它不超过 $\varepsilon$ 的所有点：

\[\boxed{N_\varepsilon(x)=\{y\in X:d(x,y)\le\varepsilon\}}.\]

min_samples（$N$）是形成核心点所需的最少邻域样本数。

例如：$\varepsilon=0.8$、$N=5$。如果一个点在半径0.8的邻域里至少拥有5个样本，就足以成为核心点。计数包含它自己，所以这里相当于自己加上至少4个其他邻居。

8.3 三种点：核心、边界、噪声

核心点（Core Point）

如果：

\[\boxed{|N_\varepsilon(x)|\ge N},\]

这个点就是核心点。它周围足够拥挤，能形成密集区域的主体。

边界点（Border Point）

如果某个点自己周围不够密集、不是核心点，但位于至少一个核心点的 eps 邻域内，它就是边界点。

边界点能够归入某个簇，但它本身不能继续向外扩展簇。

噪声点（Noise / Outlier）

如果一个点既不是核心点，也不在任何核心点的 eps 邻域内，就把它视为噪声点。

类型	自身邻域足够密集？	位于某个核心点的邻域内？
核心点	是	不要求
边界点	否	是
噪声点	否	否

8.4 DBSCAN 如何形成一个簇

设有四个核心点 A、B、C、D，满足：

\[d(A,B)\le\varepsilon,\quad d(B,C)\le\varepsilon,\quad d(C,D)\le\varepsilon.\]

即使 A 与 D 的距离很大，它们仍然能通过核心点链条连接：

\[A\longrightarrow B\longrightarrow C\longrightarrow D.\]

这四个核心点属于同一个密度连通的簇。再把它们的边界邻居加入，簇就形成了。

算法的完整直觉过程是：

1. 选择一个尚未处理的点，查看其 eps 邻域；
2. 如果它是核心点，就以它为起点创建簇；
3. 找出与它邻接的其他核心点；
4. 从这些核心点继续扩展，沿密度连接链寻找更多核心点；
5. 把这些核心点周围的边界点也纳入簇；
6. 扩展到不能继续时，完成这个簇；
7. 再寻找其他尚未处理的密集区域；
8. 最终无法归入任何簇的点标记为噪声。

在不少实现中，噪声点用簇标签 $-1$ 表示。

有一个容易忽略的细节：如果一个边界点接近两个不同簇的核心点，它的最终归属可能受处理顺序影响；但这种边界点本身不会把两个核心点簇直接合并。

8.5 为什么 DBSCAN 能识别弯曲月牙

考虑二维平面上的两条互相交错、像月牙一样的点群。每条月牙是一片连续密集区域，但它们都不是圆形。

K-Means 会让点靠近某个中心，结果可能把一条月牙切成两块，或者把两条月牙的一部分合在一起。因为“离哪个中心最近”不等于“沿哪条月牙连续分布”。

DBSCAN 则从密集点出发，沿密度连接的路径扩展，能够更自然地追踪弯曲形状。在参数合适的情况下，两条月牙可以被识别为两个独立簇。

此外，K-Means 通常把每个点分到某个簇；DBSCAN 可以把远离密集区域的孤立点单独标为噪声。这是 DBSCAN 在异常点识别和不规则形状分析方面的突出优点。

8.6 eps 与 min_samples 的影响

参数	过小的可能结果	过大的可能结果
eps	原有密集群被拆散，噪声点增多	不同密集群可能被连接在一起
min_samples	比较稀疏的区域也容易形成核心点	很多样本无法成为核心点，噪声增加

这两个参数必须结合数据的尺度与实际密度进行选择。尤其注意：如果对特征做了标准化，eps 的距离单位也发生变化，不能照搬原始特征空间的阈值。

8.7 DBSCAN 的优点和限制

优点：

• 不需要预先指定 K；
• 能发现月牙形等非凸、不规则簇；
• 能够直接标记噪声与孤立点；
• 对某些分布，能够保留密度连接的自然结构。

局限：

• 对 eps 和 min_samples 敏感；
• 很难用一组全局参数同时适应密度差异很大的多个簇；
• 高维空间的距离可能失去区分力，使密度判断困难；
• 大数据集的计算成本依赖邻域搜索方法、维数和 eps，在不利情况下可能较高；
• 边界点归属存在一定的不稳定性。

一句话记忆：K-Means 问“离哪个中心近”，DBSCAN 问“周围够不够密、能否沿密集点连通”。

九、相关方法：GMM、EM、谱聚类与协同聚类

聚类并不只有上述四种方法。理解几个相关方向，有助于知道它们各自的边界。

9.1 高斯混合模型（GMM）：用概率描述簇

K-Means 为每个点指定唯一的簇，属于硬聚类。高斯混合模型（Gaussian Mixture Model，GMM）则假设数据由若干个高斯分布混合生成，每个高斯分量可以代表一个群体。

一个高斯分量不仅有均值 $\mu_k$，还有协方差矩阵 $\Sigma_k$ 和混合权重 $\pi_k$。因此，GMM 可以表达更多不同方向、不同宽窄的椭圆形分布。

对于样本 $x_i$，它属于第 k 个高斯分量的后验责任度可以表示为：

\[\gamma_{ik}=\frac{\pi_k\,\mathcal N(x_i\mid\mu_k,\Sigma_k)} {\sum_{j=1}^{K}\pi_j\,\mathcal N(x_i\mid\mu_j,\Sigma_j)}.\]

这意味着：一个点可以有70%的责任度属于第1个分量、30%属于第2个分量。它不会被强制看成绝对属于某一个群体。

9.2 EM：交替更新概率与模型参数

GMM 常用 EM（Expectation-Maximization）算法拟合。

• E步： 根据当前的均值、协方差和混合权重，估计每个样本对各分量的责任度；
• M步： 利用这些责任度，更新均值、协方差和混合权重；
• 重复： 直到对数似然或参数变化满足停止条件。

与 K-Means 相比，GMM+EM 更具有概率解释，并允许更灵活的簇形状。代价是模型更复杂，参数更多，对初始化、协方差估计和异常点也可能敏感。GMM 通常仍需设定或选择分量数。

在所有分量具有相同、各向同性协方差，并考虑硬分配或小方差极限时，GMM 的一种简化情况与 K-Means 存在密切联系。这解释了为什么两者都有“分配样本、更新中心”的交替结构。

9.3 Normalized Cuts：从图的角度理解聚类

另一类方法先把样本构造成图：

• 每个样本是图的一个节点；
• 两个样本之间的边表示相似程度；
• 相似度越高，边的权重越大。

接下来，算法尝试把图划分成几个子图，使不同子图之间的连接相对较弱，而子图内部的连接相对较强。

Normalized Cuts（规范化割）属于这种图划分思路。它不依赖单一中心来定义簇，在某些复杂形状和结构数据上很有价值。相关的谱聚类方法还会利用图矩阵的特征向量帮助发现分组。

9.4 Co-Clustering：样本和特征一起分组

通常的聚类是在“样本”这一维度进行分组，例如把顾客分成若干类。

Co-Clustering（协同聚类、双向聚类）则尝试同时组织样本与特征。

假设有一个“用户 × 商品”的购买矩阵。普通聚类可能只把用户分组；协同聚类则可以同时发现：

• 哪几类用户表现相似；
• 哪几类商品经常被相同类型的用户购买；
• 哪些用户群体与商品群体之间存在特别强的关系。

这在推荐、文本的文档—词语矩阵分析等场景中具有意义。

十、怎样在实际问题中选择聚类算法

10.1 四种主要算法的对照

特征	层次聚类	K-Means	X-Means	DBSCAN
核心思路	合并或分裂已有簇	分配到最近中心并更新均值	K-Means 加局部分裂与选模	根据密度连通区域扩展
是否事先指定精确 K	不一定	需要	不需要，但通常设上下限	不需要
是否形成层次结构	是	否	最终通常仍是平坦分组	否
是否使用中心表示簇	取决于连接方式	是	是	不依赖全局中心
能否发现不规则形状	取决于连接方式	通常较弱	通常较弱	通常较好
是否专门标记噪声	普通形式不专门处理	否	通常不专门处理	是
主要参数或选择	距离、连接方式、截断条件	K、初始化、停止条件	K范围、初始化、BIC等	eps、min_samples
主要优势	结构直观，可读树状图	简单且通常较快	可在范围内自动估计 K	适合密度形状和异常点
主要限制	大规模数据成本较高	需给 K，受初始化与形状影响	依赖模型假设和分裂判断	对密度参数敏感

10.2 按照问题特征做选择

如果只需要一个快速、容易解释的基础方案： 可以先尝试 K-Means。前提是数据适合用中心描述，且愿意为 K 做出选择。

如果希望算法在一个范围内尝试估计 K： 可以考虑 X-Means。它适合希望保留 K-Means 的中心式结构、又不想手动确定唯一 K 的情况。

如果关心样本的层次关系： 可以考虑层次聚类。例如希望知道哪些小群体可以逐步合并成更大的群体，或者希望用树状图解释结果。

如果怀疑簇形状弯曲、不规则，且噪声明显： 可以考虑 DBSCAN。它不需要人为规定簇数，但必须认真选择密度参数。

如果每个簇看起来像椭圆形分布，且需要概率归属： 可以考虑 GMM+EM。

没有一种算法能保证适用于所有数据。算法之间的差别，实际上反映了对“一个簇到底应该是什么形状、怎样形成”的不同假设。

10.3 一个完整的实际聚类分析流程

把聚类当成一个完整的数据分析任务时，建议按如下顺序思考。

第一步：先明确目的

是希望把客户分成便于运营的几组，还是发现空间中的异常活动？是需要解释层次关系，还是只需要最终分类？不同目的会改变算法和评价标准。

第二步：选择能表达问题的特征

如果想按消费习惯分群，只使用年龄可能远远不够；但如果加入身份证号等没有实际相似性意义的数字，又可能产生虚假的距离。

特征的选择通常比一味更换聚类算法更重要。

第三步：处理量纲、缺失和异常值

检查特征是否需要标准化，异常点是否应该保留为研究对象，以及缺失数据该如何处理。基于距离的方法尤其依赖这一阶段。

第四步：选择合适的距离与聚类机制

• 数值接近很重要时，考虑欧氏等距离；
• 变化趋势很重要时，考虑相关系数；
• 方向和比例更重要时，考虑余弦相似度；
• 簇围绕中心时，考虑 K-Means/X-Means；
• 关注层次关系时，考虑层次聚类；
• 关注密集区域和噪声时，考虑 DBSCAN。

第五步：检查簇数与结果质量

对 K-Means，可以比较多个 K 下的 WCSS、轮廓系数或平均直径；对 X-Means，检查最终选出的 K、BIC 决策及上下限是否合理；对层次聚类，查看树状图的截断高度；对 DBSCAN，检查得到的簇数、噪声比例和区域形状。

可使用 DB 指数、Dunn 指数等指标辅助比较，但不要因为某个分数略高就直接认定其绝对正确。

第六步：检查稳定性

换一个随机初始化、稍微改变参数或对样本做少量扰动，结果是否大体一致？如果一点变化就造成大幅重分组，解释结论时应更加谨慎。

第七步：赋予业务含义

算法可能输出三类顾客，但只有进一步查看每类的年龄、消费频率和商品偏好，才能判断它们是否真的构成有意义的群体。簇标签只是编号，不天然具有好坏、等级或价值含义。