这篇笔记讲的是拿到数据之后、下结论之前要做的事：先把变量整理成可以比较的形式，再定义“像”和“不像”，然后用聚类与降维从数据本身找出结构，最后判断这个结构能信到什么程度。
没有标签的时候，数据不会告诉我们“该分成几类”“哪些方向重要”。我们读出来的结构，一部分来自数据，一部分来自方法自己的假设。全篇围绕的就是这个问题：怎样区分这两部分。
每个方法都可以拆成三个部分：
方法之间的差别主要在第 2 部分，方法失效，也多半是因为数据不满足它的结构假设。最后一章用一张表把所有方法放在一起对照。
本章的问题： 后面的距离和方差都依赖变量的分布形状与尺度。数据直接拿来算会有什么问题？偏态和方差随均数变化、量纲不一致、缺失，每一种对应一类处理（变换、缩放、填补或删除）。每一种处理都在改变数据，所以要知道它改变了什么、依赖什么前提。
| 症状 | 后果 | 处理 |
|---|---|---|
| 偏态，方差随均数变化 | 正态性、方差齐性的前提不成立 | 数据变换 |
| 量纲不一致，尺度差异大 | 距离、方差被大尺度的变量主导 | 归一化与特征缩放 |
| 有缺失 | 样本代表性受损，部分方法无法运行 | 删除、填充或不填充 |
参数统计方法（ \(t\) 检验、方差分析、回归）要求数据大致正态、各组方差相等。数据不满足时，常见的办法是先做一个单调变换，再对变换后的数据分析。
对数变换：对原始数据 \(X\) 取对数，以 \(X' = \lg X\) 作为新的分析数据。当 \(X \le 0\) 时对数没有定义，所以有零或负值时可以取 \(X' = \lg(X + k)\)，常取 \(k = 1\)。数据左偏时可以先反射，取 \(X' = \lg(k - X)\)，其中 \(k\) 大于 \(X\) 的最大值。
对数变换常用于：
平方根变换：取 \(X' = \sqrt{X}\)。原始数据有小值或零值时，可以取 \(X' = \sqrt{X + 0.5}\)。常用于：
倒数变换：取 \(X' = 1/X\)。常用于数据两端波动较大的资料，可以减小极端值的影响。倒数变换会反转数据的次序，数据中不能有 0。
平方根反正弦变换：率或比例 \(p\) 服从二项分布时，取 \(X' = \arcsin\sqrt{p}\)，可以使方差稳定，总体率偏离 50% 较远时更需要。
这几种变换是同一个想法。若标准差 \(\sigma\) 随均数 \(\mu\) 变化，选择变换 \(g\) 使 \(g'(\mu) \propto 1/\sigma(\mu)\)，变换后方差就近似为常数（delta 方法）：
| 变换 | 形式 | 标准差与均数的关系 | 典型场合 |
|---|---|---|---|
| 对数 | \(\lg X\) | \(\sigma \propto \mu\) | 右偏、跨量级、对数正态 |
| 平方根 | \(\sqrt{X}\) | \(\sigma \propto \sqrt{\mu}\)（方差与均数成比例） | 泊松型计数 |
| 倒数 | \(1/X\) | \(\sigma \propto \mu^2\) | 两端波动大、极端值主导 |
| 平方根反正弦 | \(\arcsin\sqrt{p}\) | 二项率的方差 \(p(1-p)/n\) | 率、比例 |
| Box-Cox | \((X^{\lambda} - 1)/\lambda\)， \(\lambda = 0\) 时为 \(\ln X\) | 由数据估计 \(\lambda\) | 不确定用哪种时 |
Box-Cox 变换（Box & Cox, 1964）把前面的几种放进同一个参数族： \(\lambda = 0\) 是对数， \(\lambda = 1/2\) 与 \(\lambda = -1\) 分别与平方根、倒数相差一个线性变换， \(\lambda = 1\) 是不变换。 \(\lambda\) 通过极大似然由数据估计，目的是让数据尽量接近正态，并不保证正态；它要求 \(X > 0\)，含零或负值时可以用 Yeo-Johnson 变换。
使用时需要注意：
这两个词在中文里常被混用，先分开。归一化（normalization）泛指把数据调整到某个共同基准上的各种做法，在统计里还包括分位数归一化（把不同样本的分布对齐）和把分布整体调整到正态这类更重的处理。特征缩放（feature scaling）是其中最常见的一类，只调整位置和尺度。另外要注意，中文里“归一化”常特指 min-max 缩放，“标准化”特指 z 分数。
本笔记关心特征缩放，因为它决定了距离类方法（聚类、kNN、t-SNE、UMAP）算出来的“远近”有没有意义。设一个变量的样本为 \(x_1, \dots, x_n\)， \(\bar{x}\) 为均值， \(s\) 为标准差：
| 做法 | 公式 | 结果 | 说明 |
|---|---|---|---|
| 中心化 | \(x - \bar{x}\) | 均值为 0 | 只平移，不改尺度；PCA 的第一步 |
| min-max 缩放 | \(\frac{x - \min(x)}{\max(x) - \min(x)}\) | 落在 \([0, 1]\) | 对极端值敏感：一个离群点就能把其余点压成一团 |
| 极差归一化 | \(\frac{x - \bar{x}}{\max(x) - \min(x)}\) | 大致落在 \([-1, 1]\) | 中心化后再除以极差 |
| 标准化（z 分数） | \(\frac{x - \bar{x}}{s}\) | 均值 0、标准差 1 | 最常用；量纲不同、尺度差异大时先做这一步 |
| 稳健标准化 | \(\frac{x - \operatorname{med}(x)}{\operatorname{IQR}(x)}\) | 无 | 用中位数与四分位距，抗离群点 |
| 缩放到单位长度 | \(\frac{x}{\lVert x \rVert}\) | 向量长度为 1 | 按样本（行）缩放，不是按变量（列） |
标准差有两种定义：除以 \(n\)（总体标准差）或除以 \(n-1\)（样本标准差）。不同的软件各取一种，大样本下差别可以忽略，小样本对比结果时要留意。
什么时候用哪一种：
归一化更宽的用法（分位数归一化、把分布对齐到正态）属于前面数据变换的问题，Box-Cox 是其中的代表。分位数归一化在生信里常用来对齐不同样本的表达量分布。
处理缺失值，先要判断它为什么缺失，再选方法。机制判断错了，后面填得再精细，也只是把一种偏倚换成另一种。
| 机制 | 含义 | 例子 | 直接删除的后果 |
|---|---|---|---|
| 完全随机缺失 MCAR | 缺失与任何变量（包括它自己）都无关 | 仪器偶发故障、样本管打碎 | 不引入偏倚，只损失信息 |
| 随机缺失 MAR | 缺失只依赖其它已观测的变量 | 收入缺失与学历有关，与收入本身无关 | 一般有偏；可以利用已观测的变量估计缺失值 |
| 非随机缺失 MNAR | 缺失依赖该变量自身的取值 | 高收入者更不愿填收入 | 有偏，也没有通用的补救办法 |
这里的“随机”指的是缺失机制，不是缺失值本身。MAR 下如果分析模型已经包含了决定缺失的那些变量，直接删除记录（完全病例分析）在一定条件下也可以无偏，但通常会损失信息。MNAR 没有通用的解法，只能把假设写清楚，做敏感性分析，或者用选择模型、模式混合模型去建模。
缺失本身有时就是信息，这一点在决策上比机制分类更有用：
所以填什么，取决于缺失在这份数据里意味着什么，而不是哪种算法更精巧。
分三类：删除、填充、不填充。
把含缺失的记录（或整列）删掉，得到完整的数据表。方法简单，在 MCAR 下无偏，缺失比例很小、样本量充足时很有效；类别标签缺失时通常也只能这样做。代价是样本减少、信息丢失：样本本来不多时，删掉几个对象就可能改变结论；缺失比例大、尤其是非随机缺失时，删除会使结论产生偏离。
用估计值把缺失处补上。常用的有：
| 方法 | 做法 | 代价与适用 |
|---|---|---|
| 人工填写 | 由领域专家逐条判断 | 偏差最小，但最费时，只在数据量小且缺失项关键时可行 |
| 均值/众数填充 | 数值变量填均值，分类变量填众数 | 会低估方差、稀释变量间的相关性；快，但不宜作为最终分析的做法 |
| 条件均值填充 | 只在同类的对象里取均值（例如按决策属性分组） | 比无条件均值合理，分组变量怎么选仍然主观 |
| 回归填充 | 用其它变量建立回归方程预测缺失项 | 变量间不是线性关系时估计有偏；不加随机误差项时同样低估方差 |
| 热卡填充 / kNN | 找一个最相似的完整对象，把它的值搬过来 | 利用了数据间的关系，概念直接；“相似”的定义主观，是它的主要问题 |
| EM | 在参数与缺失值之间交替迭代：E 步求条件期望，M 步极大化对数似然 | 需要分布假设，可能收敛到局部极值，计算量大 |
| 多重填补 MI | 为每个缺失值生成 \(m\) 套填补，各自完整分析，最后按 Rubin 规则合并 | 能把填补带来的不确定性计入方差，在这几种里统计上最合理；计算复杂，且依赖填补模型正确 |
Rubin 规则：设第 \(i\) 个填补数据集得到估计 \(\hat{Q}_i\) 及其方差 \(U_i\)，则合并后的估计为 \(\bar{Q} = \frac{1}{m}\sum_i \hat{Q}_i\)，总方差为
$$T = \bar{U} + \left(1 + \frac{1}{m}\right)B, \qquad \bar{U} = \frac{1}{m}\sum_i U_i, \quad B = \frac{1}{m-1}\sum_i (\hat{Q}_i - \bar{Q})^2$$
即填补数据集内部的方差，加上数据集之间的方差。
还有几种较少用的做法：把空值当作一个特殊取值（如统一填 unknown，容易造成严重偏离，一般不推荐）；用所有可能的取值逐一尝试（组合完整化），数据量大时代价极高；利用属性之间的相关性找一个“代理属性”来推（C4.5 的做法），只能处理基数很小的名义变量。
几点取舍：均值填充不要单独使用，它同时改变分布形状和变量间的相关性；有监督学习中训练集里的缺失记录可以删，但预测时遇到含缺失的样本不能一删了之；缺失比例高时，任何单一填补都不如多重填补可信。另外可以给缺失的变量加一个“是否缺失”的指示变量，保留缺失本身的信息，这在预测中常用，用于推断时则会引入偏差。
许多方法本身就能处理缺失，或者不需要把缺失消掉：
没有哪种填充方法适用于所有问题，这一点应该写在分析报告里。可以按下面的顺序处理：
留下的问题： 数据整理好之后，“像”还没有定义。下一章给出相似度与距离。
本章的问题： 聚类和降维处理的都不是原始数据，而是一张“谁离谁近”的表。这张表怎么来，取决于变量的类型（数值、二元、分类、有序、混合）和用途，同一份数据换一个度量，结论可能完全不同。所以要先定义相似度或距离，并清楚每种定义的适用场合与前提。
相似系数衡量两个对象有多像，取值越大越像。常用的两种：
相似系数的好处是不受（各分量同向缩放的）线性变换影响，而且容易改造成距离；代价是计算量比直接算距离大，维数很高时尤其明显。
注意余弦距离 \(d = 1 - \cos\theta\) 不是严格意义上的距离，它不满足三角不等式。例如三个二维向量 \(u = (-0.591, 0.027)\)、 \(v = (-1.517, -1.363)\)、 \(w = (1.178, -0.934)\)，有 \(d(u, v) + d(v, w) = 1.455\)，而 \(d(u, w) = 1.811\)，绕一下反而更近。需要真正的距离时改用弦距离 \(\sqrt{2(1 - \cos\theta)} = \lVert \hat{\mathbf{x}} - \hat{\mathbf{y}} \rVert\)（ \(\hat{\mathbf{x}}\) 为单位向量），它满足度量的四条公理。
核函数 \(K(\mathbf{x}, \mathbf{y})\) 是定义在 \(\mathbb{R}^d \times \mathbb{R}^d\) 上的二元函数，可以理解成某个高维特征空间里的内积： \(K(\mathbf{x}, \mathbf{y}) = \langle \phi(\mathbf{x}), \phi(\mathbf{y}) \rangle\)。它的用处是不必显式算出 \(\phi(\mathbf{x})\) 就能用到高维特征（核技巧），例如高斯核 \(K(\mathbf{x}, \mathbf{y}) = \exp(-\gamma\lVert \mathbf{x} - \mathbf{y} \rVert^2)\) 对应的是无穷维特征空间。核与距离是一体两面：由 \(\lVert \phi(\mathbf{x}) - \phi(\mathbf{y}) \rVert^2 = K(\mathbf{x}, \mathbf{x}) - 2K(\mathbf{x}, \mathbf{y}) + K(\mathbf{y}, \mathbf{y})\) 就能把核换算成距离。
DTW（dynamic time warping，动态时间规整）用来比较两个长度可以不同的序列：它允许在时间轴上弯折对齐，再累加配对点的距离，常用于时间序列（语音、动作、曲线）。代价是计算量为两个序列长度的乘积，且需要限制弯折幅度，否则会退化。
一个函数 \(d(\cdot, \cdot)\) 要被称为距离（度量），需要满足四条：
只满足前三条的只能叫“不相似度”（dissimilarity）。这个区分是有用的：三角不等式保证基于索引的近邻查询可以安全剪枝（kd-tree、ball-tree 的“近邻的近邻还是近邻”）；没有它，kNN、DBSCAN 仍能定义，只是退化为全局扫描。上面余弦距离的反例就说明了这一点。
对两个向量 \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^p\)，Minkowski 距离是 \(L_p\) 范数：
$$d(\mathbf{x}, \mathbf{y}) = \left( \sum_{i=1}^{p} \lvert x_i - y_i \rvert^q \right)^{1/q}$$
三个常见特例：
| \(q\) | 名称 | 形式 | 特点 |
|---|---|---|---|
| \(1\) | 曼哈顿距离（ \(L_1\)） | \(\sum_i \lvert x_i - y_i \rvert\) | 对单个方向的差异不放大，抗离群点 |
| \(2\) | 欧氏距离（ \(L_2\)） | \(\sqrt{\sum_i (x_i - y_i)^2}\) | 默认选择；平方后便于求导 |
| \(q \to \infty\) | 切比雪夫距离（ \(L_\infty\)） | \(\max_i \lvert x_i - y_i \rvert\) | 只看最大的那个差异 |
\(q\) 越小，各维度的差异越被同等对待； \(q\) 越大，距离越由个别大的差异决定。注意欧氏距离对变量的尺度非常敏感，所以前面反复强调要先标准化。
马氏距离（Mahalanobis）解决的是“变量之间相关”的情形：它先用协方差矩阵 \(S\) 把数据白化（去相关并归一尺度），再算欧氏距离，
$$d(\mathbf{x}, \mathbf{y}) = \sqrt{(\mathbf{x} - \mathbf{y})^{\mathrm{T}} S^{-1} (\mathbf{x} - \mathbf{y})}$$
这一步的几何含义（旋转到主轴、再按各轴标准差缩放）见线代笔记“数据与统计视角”一节。注意它和加权 Minkowski 距离 \(d = \left( \sum_i \omega_i \lvert x_i - y_i \rvert^q \right)^{1/q}\) 不是一回事：后者只是给每个变量指定权重，不考虑变量之间的相关性。
两个对象各由若干“有/无”的属性描述时，把每种组合数出来：
| \(y = 1\) | \(y = 0\) | |
|---|---|---|
| \(x = 1\) | \(a\)（同有） | \(b\) |
| \(x = 0\) | \(c\) | \(d\)（同无） |
Jaccard 距离只数不一致的那些，且不计“同无”：
$$d(\mathbf{x}, \mathbf{y}) = \frac{b + c}{a + b + c}$$
为什么分母里没有 \(d\)？因为“两者都没有”这种属性可以被无限列举（没有一百种病、没有一千种商品），把它算进来会让距离被大量的共同缺失稀释，两个毫不相干的人也会显得很像。这个约定来自 Jaccard，所以叫 Jaccard 距离。
取值有次序但间距没有意义的变量（低/中/高），按秩处理：
这样做等于把“次序”当成了等距的尺度，比名义变量多用了信息；但如果等级之间的真实间距很不均匀，这个假设也会带偏结果。
数值变量与分类变量混在一起时，可以用 Gower 距离：对每个变量分别算一个 \([0, 1]\) 上的相异度（数值变量取差的绝对值除以全距，分类变量取匹配与否），再对各变量取（加权）平均。
高维下距离失效可以直接模拟出来：
1 高维下距离失去分辨力。每个维度取 100 个单位超立方体内的均匀随机点，从第一个点到其余 99 个点的最大距离与最小距离之差，相对于最小距离，随维度升高迅速趋于 0：所有点都“差不多远”。
| 数据类型 | 常用度量 | 要点 |
|---|---|---|
| 数值，量纲一致、变量不相关 | 欧氏距离 | 默认选择，先标准化 |
| 数值，变量相关 | 马氏距离 | 等价于先白化再算欧氏距离 |
| 数值，有离群点 | 曼哈顿距离 | 对大的差异不放大 |
| 看方向不看大小（文本、表达谱） | 余弦、相关系数 | 余弦距离不满足三角不等式 |
| 二元（有 / 无） | Jaccard 距离 | 不计两者都没有的情形 |
| 名义变量 | 简单匹配 | 多分类变量先二值化，注意权重 |
| 有序变量 | 秩标准化后用 Minkowski | 假定等级之间等距 |
| 数值与分类混合 | Gower 距离 | 逐变量算相异度再取平均 |
| 时间序列 | DTW | 长度可以不同，要限制弯折幅度 |
| 概率分布 | KL 散度、Hellinger、Wasserstein | KL 不对称，不是距离 |
留下的问题： 有了这张“谁离谁近”的表，怎样把对象分成组？下一章讲聚类。
本章的问题： 没有标签时，怎样把对象分成组？每个聚类算法都隐含了对“簇”的定义：到质心近、由合并规则决定、高密度的连通区域、来自同一个分布。数据的簇符合这个定义，算法就有效，不符合就失效。分完之后又没有标准答案，需要评价指标，也要知道指标自己的偏好。相似度与距离的定义见上一章。
聚类要在没有标签的前提下把对象分组，使组内尽量像、组间尽量不像。“像”由上一节的度量定义，“分成几组、怎么分”由算法决定。按分组方式，常见的方法分五族。
| 族 | 思路 | 代表 | 要预先定什么 | 适合 |
|---|---|---|---|---|
| 划分式 | 先定簇数，反复“分配—更新”直到稳定 | k-means 及其变体 | 簇数 \(K\) | 凸的、中等规模的数值数据 |
| 层次式 | 自底向上合并（或自顶向下切分），用树状图记录全过程 | 系统聚类、BIRCH、ROCK、Chameleon | 在树的哪里切 | 想要层次结构、簇数不确定 |
| 密度式 | 高密度区域连成簇，低密度处是边界与噪声 | DBSCAN、OPTICS | 半径与最少点数 | 形状不规则、含噪声 |
| 网格式 | 把空间划成网格，按单元密度判断稠密并合并 | STING、CLIQUE | 网格粒度与密度阈值 | 大规模空间数据 |
| 模型式 | 假定数据来自若干概率分布（或由网络生成） | 高斯混合模型、SOM | 分布个数与形式 | 需要“软”归属与概率解释 |
五族算法对“簇”的定义不同，选算法其实是在选对簇形状的假设。下面用两个弯月形的簇做一个对比：k-means 的簇是“到质心近”，只能切出凸的块；DBSCAN 的簇是密度连通的区域，不要求凸。
2 两个弯月形的簇，用三种方式着色。左：真实分组；中：k-means（K = 2）；右：DBSCAN（eps = 0.2，minPts = 5，灰色为噪声）。k-means 沿一条直线把两个弯月各切一半，DBSCAN 恢复了两个弯月。标题里的 ARI 是与真实分组比较得到的调整兰德系数。
图上 k-means 把两个弯月各切一半，DBSCAN 把它们分开了。反过来，簇是球形、密度均匀时，k-means 更快，也更稳。
k-means 优化的是簇内平方和（SSE，scikit-learn 里叫 inertia）：
$$\text{SSE} = \sum_{k=1}^{K} \sum_{\mathbf{x} \in C_k} \lVert \mathbf{x} - \boldsymbol{\mu}_k \rVert^2, \qquad \boldsymbol{\mu}_k = \frac{1}{\lvert C_k \rvert} \sum_{\mathbf{x} \in C_k} \mathbf{x}$$
“类内的点都足够近”这句直觉，写下来就是它： \(K\) 个簇各自的方差之和。
两步都使 SSE 单调不增。分配一步固定质心，每个点选最近的质心正是让 \(\lVert \mathbf{x} - \boldsymbol{\mu}_k \rVert^2\) 最小；更新一步固定分配，对 \(\boldsymbol{\mu}_k\) 求导令其为零，得到的最优值就是簇内均值。SSE 有下界（ \(\ge 0\)）且每步不增，所以一定会收敛（Lloyd, 1982）。
收敛不等于找到了全局最优：迭代只会停在局部极小。另外可能出现空簇（某个质心没有分到任何点，需要重新指派），也就是迭代中途簇数减少。实践中多次随机重启，取 SSE 最小的那次。
k-means 隐含假设簇是各向同性的球形。目标是欧氏距离的平方，它把“离质心远”一律当成不好，所以长条形、弯曲形、密度不均的簇会被切错。针对这一点有一系列变体，每个都在补一个前提：
| 补的前提 | 变体 | 做法 |
|---|---|---|
| 初值不该乱选 | k-means++、intelligent k-means、genetic k-means | 让初始质心彼此尽量远 |
| 均值不抗离群点 | k-medoids、k-medians | 用实际样本点（或中位数）当代表，且允许任意距离 |
| 只能处理数值变量 | k-modes | 用众数当中心，用“不相同的属性个数”当距离 |
| 簇不是凸的 | kernel k-means | 先映射到高维再划分 |
| 数据规模大 | 抽样或 MiniBatch 版本 | 大数据集更容易陷入局部极小，抽样是常用对策 |
另外两点： \(K\) 必须事先给定，而它往往正是想问的问题（见“聚类结果的评价”一节的内部指标）；聚类前要先标准化，否则 SSE 由量纲最大的变量主导。
层次式不预设簇数，而是把“合并”或“分裂”的全过程记下来，分两个方向：自底向上（agglomerative，每个对象先各自成类，再不断合并最近的类）与自顶向下（divisive，全体先是一类，再不断分裂）。合并的历史可以画成一棵树状图（dendrogram），于是簇数变成了“在哪里切”的问题：可以按高度差最大处切，也可以按需要的簇数切。
自底向上的步骤：
关键在于第 3 步：两个类合并成一个之后，它和别的类“有多远”有多种定义方式，这就是 linkage：
| linkage | 类间距离取 | 倾向 | 单调性 |
|---|---|---|---|
| 最短距离（single） | 两类中最近的一对点 | 容易拉出长链，能分出非凸的簇 | 有 |
| 最长距离（complete） | 两类中最远的一对点 | 倾向紧致的球状簇，怕离群点 | 有 |
| 类平均（average） | 两类所有点对的平均距离 | 折中，最常用 | 有 |
| 质心法（centroid） | 两个质心的距离 | 可能出现“倒置”（合并后距离反而变小） | 无 |
| Ward 法 | 合并后 SSE 的增量 | 倾向大小相近的紧致簇 | 有 |
“单调性”指合并距离随层次单调不减，没有它，树状图会出现交叉，切树得到的划分也就不再嵌套。类平均与 Ward 法常被当作默认选择，一是单调，二是空间扩张／浓缩的程度适中（Ward, 1963）。
层次式最初是为小数据设计的（邻近度矩阵是 \(O(n^2)\) 的），面向更大规模数据的有几个代表：BIRCH（先建一棵聚类特征树做压缩，适合大规模数值数据）、ROCK（面向分类变量，用“共同邻居数”定义相似度）、Chameleon（先用 kNN 图建图，再按图的连通性合并，效果常被称道但复杂度高）。
密度式解决的是 k-means 解决不了的形状问题：把“足够密”的区域连成簇，稀疏处当作边界或噪声。以 DBSCAN（Ester 等, 1996）为例，先给定半径 \(\varepsilon\) 与最少点数 minPts，定义三个概念：
算法就是：任取一个尚未访问的核心点，把它的 \(\varepsilon\) 邻域收进同一簇，再对新进来的核心点重复这一扩张，直到不能再扩；然后换下一个未访问的核心点。落在同一片高密度区域里的簇会自然合并。
它有三个好处：簇可以是任意形状（因为只看连通性）、不需要预先指定簇数、噪声被显式地标出来而不是硬塞进某个簇。代价是两个参数都要选，而结果对它们相当敏感： \(\varepsilon\) 大一点就把两个簇粘成一片，小一点就把一个簇碎成若干片；密度差别大的数据尤其难办，一组参数不可能同时适合稠密区和稀疏区。参数可以借助 k-距离图来定（把每个点到其第 minPts 近邻的距离排序画出来，拐点处常作为 \(\varepsilon\) 的参考）。OPTICS 就是为这个问题提出的：它不直接给出一组参数，而是按密度可达性给点排序，生成一条可以按任意密度阈值去切的“可达性图”，相当于把多个 \(\varepsilon\) 的结果一次算完。
把数据空间划成网格单元，统计每个单元里的点数，按阈值判定稠密单元，再把相邻的稠密单元连成簇。优点是复杂度只与网格数有关、与点数基本无关，因此适合大规模空间数据；缺点是簇的边界被网格对齐（粒度选粗了，相邻但分属两簇的点会被并在一起），而且高维时网格数随维度指数增长，这与“距离在高维失效”是同一个原因。
模型式把聚类写成生成过程：假定同一簇的数据来自同一种概率分布，聚类于是变成估计混合分布的参数。最典型的是高斯混合模型（GMM）：数据被看作若干个高斯分布的混合，每个簇对应一个分量，用 EM 算法迭代估计权重、均值与协方差。它的好处是归属以概率给出（一个点可以 70% 属于 A、30% 属于 B），每个簇还能用参数描述形状；代价是执行效率低（尤其分量多而数据少时）、需要假定分布形式，而且协方差矩阵的形态决定了它同样偏好椭球状的簇。分量个数可以用 BIC 之类的信息准则来选。基于神经网络的一支以自组织映射（SOM，Kohonen）为代表：用低维网格上的竞争学习把高维数据投影到网格上，保留拓扑关系，用法更接近可视化而非严格的概率模型。
聚类没有唯一正确答案，“好不好”必须先说清楚是相对于什么而言：
两者都只回答“这个划分在某个指标下如何”，不回答“这个聚类有没有意义”，后者是领域问题，指标给不了。
每个簇取其中占比最大的那个真实类别，把命中数加起来除以总数：
$$P = \sum_k \frac{\max_j \lvert C_k \cap L_j \rvert}{n}$$
纯度与准确率形似但不一样，容易混淆：纯度随簇数单调不减，把每个点各自设为一簇时纯度恒为 1。所以它不能用来比较簇数不同的结果，只能在同一簇数下比较，报告时要写明簇数。
把所有点对分成“同簇”与“不同簇”，再看两套划分（聚类结果与真实分类）在这些点对上是否一致。记：
$$RI = \frac{TP + TN}{TP + TN + FP + FN}$$
RI 的问题是基准偏高：随机划分也有相当比例的点对“碰巧一致”，因为簇数多时大多数点对在两边都不同簇（TN 占多数）。随机划分的期望是 \(E[RI]=1-2/K+2/K^2\) ： \(K=2\) 时只有 0.5， \(K=3\) 时 0.556， \(K=10\) 时 0.82， \(K=20\) 时 0.905——簇数越多基准越接近 1，看不出好坏。调整兰德系数（ARI）修正的就是这一点（Hubert & Arabie, 1985）：它把随机划分下的期望值减掉再归一化，
$$ARI = \frac{\sum_i\sum_j \tbinom{n_{ij}}{2} - \left[ \sum_i \tbinom{a_i}{2} \sum_j \tbinom{b_j}{2} \right] \bigg/ \tbinom{n}{2}} {\frac{1}{2}\left[ \sum_i \tbinom{a_i}{2} + \sum_j \tbinom{b_j}{2} \right] - \left[ \sum_i \tbinom{a_i}{2} \sum_j \tbinom{b_j}{2} \right] \bigg/ \tbinom{n}{2}}$$
其中 \(n_{ij}\) 是“真实类 \(i\) 且聚类 \(j\)”的样本数， \(a_i\)、 \(b_j\) 分别是类 \(i\)、簇 \(j\) 的规模， \(n\) 为总数。ARI 取值在 1（完全一致）与 0（与随机划分的期望相当）之间，也可能为负（比随机还差）。
用一个小例子（三个真实类 \(A, B, C\) 在三个簇中的数量分别为 \(5, 1, 2\)； \(1, 4, 0\)； \(0, 1, 3\)）：
$$\sum_i\sum_j \tbinom{n_{ij}}{2} = \tbinom{5}{2} + \tbinom{2}{2} + \tbinom{4}{2} + \tbinom{3}{2} = 20$$
$$\sum_i \tbinom{a_i}{2} = \tbinom{8}{2} + \tbinom{5}{2} + \tbinom{4}{2} = 44, \qquad \sum_j \tbinom{b_j}{2} = \tbinom{6}{2} + \tbinom{6}{2} + \tbinom{5}{2} = 40$$
$$ARI = \frac{20 - 44 \times 40 / 136}{0.5 \times (44 + 40) - 44 \times 40 / 136} = \frac{7.06}{29.06} = 0.24$$
这三个是“把聚类当成分类”来算的指标，与 RI 不是一回事：RI 数的是点对，它们数的是点。
$$Precision = \frac{TP}{TP + FP}, \qquad Recall = \frac{TP}{TP + FN}$$
$$F_\beta = \frac{(1 + \beta^2)\,P\,R}{\beta^2 P + R}, \qquad F_1 = \frac{2PR}{P + R}$$
\(P\) 与 \(R\) 的取值范围是 \([0, 1]\)， \(F_\beta\) 也是； \(\beta > 1\) 时召回更重要， \(\beta < 1\) 时精确更重要，常用的 \(F_1\) 取 \(\beta = 1\)，是两者的调和平均。
这里的 TP 等四项与 RI 一节的同名项含义不同：聚类结果没有“类别名”，必须先决定哪个簇对应哪个真实类（常用最大重叠或匈牙利算法配对），才能统计 TP/FP/FN，所以这组指标对配对方式敏感，汇报时要说明配对规则。
内部指标几乎都是“簇内距离”与“簇间距离”的某种比值，区别只在两个距离怎么定义。
对每个样本点 \(i\)（Silhouette, Rousseeuw, 1987）：
$$s(i) = \frac{b(i) - a(i)}{\max\{a(i), b(i)\}}, \qquad s = \frac{1}{n}\sum_{i=1}^{n} s(i)$$
\(s(i) \in [-1, 1]\)：接近 1 说明点在自己的簇里很安稳，接近 \(-1\) 说明它其实离邻居簇更近（可能被分错了），接近 0 说明它在两簇边界上。整体的 \(s\) 取平均。注意 \(b(i)\) 取的是“到某个簇的平均距离”，不是“到某个簇中心的距离”，两者含义不同，对簇形状的稳健性也不同。
把总平方和拆成簇内与簇间两部分（Caliński & Harabasz, 1974）：
$$W = \sum_{k=1}^{K}\sum_{\mathbf{x} \in C_k} \lVert \mathbf{x} - \mathbf{c}_k \rVert^2, \qquad B = \sum_{k=1}^{K} n_k \lVert \mathbf{c}_k - \mathbf{c} \rVert^2$$
其中 \(\mathbf{c}_k\) 为簇 \(k\) 的中心， \(\mathbf{c}\) 为全体样本的中心， \(n_k\) 为簇 \(k\) 的样本数。指标是两者按自由度调整后的比值：
$$CH = \frac{B / (K - 1)}{W / (n - K)}$$
越大越好。它就是方差分析（ANOVA）里的 \(F\) 统计量： \(B/(K-1)\) 与 \(W/(n-K)\) 分别是组间与组内均方，衡量的是“簇间差异相对于簇内波动有多大”。放在方差分析的框架下看，它同样带着正态性与方差齐性的前提；另外簇本身是由数据算出来的，它并不服从 \(F\) 分布，不能拿去查 \(p\) 值，实践中只把它当作相对比较的指标。
对每个簇 \(i\)，定义它以“簇内平均半径” \(s_i\)（簇内所有点到簇中心的平均距离）与“簇间中心距离” \(d_{ij}\) 构成的比值
$$R_{ij} = \frac{s_i + s_j}{d_{ij}}$$
再对每个簇取最像的那个对手，最后求平均（Davies & Bouldin, 1979）：
$$DB = \frac{1}{K} \sum_{i=1}^{K} \max_{j \neq i} R_{ij}$$
取值在 \([0, +\infty)\)，越小越好。（注意是“先对每个 \(i\) 取最大、再平均”，不是对所有 \((i, j)\) 求和。）三个内部指标里它的计算量与 CH 相当（都只需到簇中心的距离，另加簇间距离），比轮廓系数的 \(O(n^2)\) 省；代价是同样偏好球状簇。
\(K\) 没有现成的答案，常用的参考有：SSE 随 \(K\) 变化曲线的肘部、轮廓系数最大处、CH 指数最大处；模型式聚类可以用 BIC；gap 统计量则把 SSE 与随机参考分布下的期望值比较。这些指标给出的结论经常不一致，可以几个一起看，再结合可解释性与稳定性来定。
| 指标 | 要标签吗 | 衡量什么 | 取值与方向 | 注意 |
|---|---|---|---|---|
| 纯度 | 要 | 每个簇里占比最大的类 | 0 到 1，越大越好 | 随簇数增大而增大，不能比较不同簇数 |
| RI / ARI | 要 | 点对划分的一致性 | ARI 为 1 最好，0 相当于随机，可为负 | RI 的基准偏高，优先用 ARI |
| Precision / Recall / F | 要 | 点对是否被正确放在一起 | 0 到 1，越大越好 | 依赖簇与类的配对方式 |
| 轮廓系数 | 不要 | 紧致程度与分离程度 | \(-1\) 到 1，越大越好 | 偏好球状、大小相近的簇 |
| CH 指数 | 不要 | 簇间与簇内方差之比 | 越大越好 | 就是方差分析的 \(F\)，偏好球状簇 |
| DB 指数 | 不要 | 簇内离散与簇间距离之比 | 不小于 0，越小越好 | 偏好球状簇，计算量小 |
留下的问题： 聚类要在原空间做，但高维数据看不见。把它压到二维或三维来看，怎么压、压完怎么读，是下一章。
本章的问题： 把高维数据压到二维或三维来看，压的时候要保留什么？保留方差（PCA）、距离（MDS）、测地距离（ISOMAP），还是邻域关系（t-SNE、UMAP）？保留的量不同，图上能读出来的东西也不同，错读图是降维里最常见的错误。
降维把高维数据压到低维，用来可视化、去噪，或者作为聚类和建模的预处理。线性方法（PCA、MDS）保留全局的方差或距离，非线性方法（t-SNE、UMAP 等）保留邻域关系。
在聚类或建模之前先把数据“变小”，是常见的一步，有三条路：变换、降维、抽样。它们不是必须的，但规模大或维度高时，先简化往往比直接上算法有效，BIRCH 用聚类特征树做压缩才能处理大规模数据，就是一个例子。三条路也可以组合使用，和前面五族算法搭配。
谱聚类是降维与聚类的结合，单独提一下：先把数据写成相似度矩阵，转成图的拉普拉斯矩阵，对它做特征分解，取最小的几个非零特征值对应的特征向量作为新坐标（这一步就是 Laplacian eigenmaps 降维，用到的是线代笔记里的谱分解），最后在新坐标上跑 k-means。它不需要假定簇是凸的，效果常好于直接在原空间跑 k-means，代价是要做特征分解。
主成分分析（principal component analysis）在本笔记的流程里有三个角色：把相关的变量换成不相关的、降维以便可视化、用前几个主成分去噪。它的数学（协方差矩阵的谱分解、用 SVD 直接算、保留的方差比例，以及“不要先算 \(X^{\mathrm{T}}X\)”这条数值上的建议）在线代笔记“数据与统计视角”一节已经推导过，这里只写结论和用法。
做法：把中心化后的数据 \(X\)（ \(n \times p\)）投影到方差最大的方向上。第 \(j\) 个主方向是协方差矩阵 \(S = X^{\mathrm{T}}X / (n-1)\) 的第 \(j\) 个特征向量，主成分得分 \(X\mathbf{q}_j\) 就是样本在该方向上的坐标，取前 \(k\) 个主方向即把数据压到 \(k\) 维。保留的方差比例是前 \(k\) 个特征值之和与全部特征值之和的比，这个比例也可以反过来当判据用：碎石图看特征值的拐点，或者累计比例到某个阈值。
几点使用上的判断：
MDS（multidimensional scaling，多维标度）与 PCA 的出发点相反：它不要求有数据矩阵，只要求有距离矩阵。给定样本两两之间的距离（或不相似度） \(d_{ij}\)，找一组低维坐标 \(\mathbf{x}_i\)，让它们的距离尽量接近给定的 \(d_{ij}\)。于是它能处理“只有距离、没有坐标”的数据（例如主观相似度评分、地图上的城市距离），也能用非欧氏的距离。
按对距离的使用方式分两类：度量 MDS 要求低维距离直接接近 \(d_{ij}\)；非度量 MDS 只要求次序一致（该近的还近、该远的还远），适合只有排序信息的数据。
PCoA（principal coordinates analysis，主坐标分析）是 MDS 用于数值数据时的标准做法，也叫经典 MDS：
Torgerson 法（有解析解）：把平方后的距离矩阵双中心化，再对结果做特征分解。双中心化就是
$$B = -\frac{1}{2} C D^{2} C, \qquad C = I - \frac{1}{n} J_n$$
其中 \(D^2 = [d_{ij}^2]\)， \(J_n\) 为全 1 矩阵。取 \(B\) 的最大的几个特征值对应的坐标即得解。当 \(d_{ij}\) 是欧氏距离时， \(B\) 恰好是中心化数据矩阵的 Gram 矩阵 \(XX^{\mathrm{T}}\)，所以此时 PCoA 与 PCA 是同一件事：PCA 从数据矩阵出发，PCoA 从距离矩阵出发。MDS 并不是 PCA 的扩展，两者在欧氏距离下等价，MDS 还可以用别的距离。
迭代法：不要求欧氏距离，直接最小化距离的残差（stress），
$$Stress_D(\mathbf{x}_1, \dots, \mathbf{x}_N) = \left( \sum_{i \neq j} \left( d_{ij} - \lVert \mathbf{x}_i - \mathbf{x}_j \rVert \right)^{2} \right)^{1/2}$$
适用范围更广，但需要初值，可能落入局部极小。
PCA 与 MDS 优化的是全局的量：方差、距离。它们隐含一个假设：数据在原始空间里大致是平的。如果数据其实在一个弯曲的低维曲面上（瑞士卷、球面、环面），任何线性投影都会把卷的不同层叠在一起，把本来很远的点画到一起。下面两个方法换了一个目标：只保留邻域，也就是谁和谁是近邻要保住，其余的距离可以不管。
高维观测往往由少数潜在变量生成，数据因此落在一个低维流形附近，这叫流形假设。手写数字图片有 784 个像素，但“写的是什么数字、倾斜多少”才是真正的自由度；单细胞表达谱有上万个基因，细胞状态却只有几个。如果只关心“哪些样本相似”，保住邻域关系就足够做可视化和后续分析，全局距离保不住也不可惜（在高维空间里它本来就不太可靠）。
代价是，这些图上的距离与面积不能再按比例去读。后面“怎么读这些图”一节会具体说。
在 t-SNE 与 UMAP 之前，流形学习已经有一批做法，共同套路是：先用 kNN 把数据连成一张图，再对这张图做谱分解，取特征向量当新坐标。
t-SNE 与 UMAP 可以看作这条路线上的两个“概率化／工程化”版本：同样从 kNN 出发，但不再解特征分解，而是直接优化一个把“邻域关系”写成概率的目标函数，因此能处理更大的数据，也更依赖随机优化。
t-SNE（t-distributed stochastic neighbor embedding，van der Maaten & Hinton, 2008）在高维端把“距离”变成“条件概率”，在低维端换成一个重尾核，再让两边的概率分布尽量一致。
对每个点 \(\mathbf{x}_i\)，把它到其余各点的距离经高斯核变成条件概率
$$p_{j \mid i} = \frac{\exp\!\left(-\lVert \mathbf{x}_i - \mathbf{x}_j \rVert^{2} / 2\sigma_i^{2}\right)}{\sum_{k \neq i} \exp\!\left(-\lVert \mathbf{x}_i - \mathbf{x}_k \rVert^{2} / 2\sigma_i^{2}\right)}$$
其中 \(\sigma_i\) 由二分搜索确定，使得这个条件分布的熵等于 \(\log(\text{困惑度})\)，即
$$H(P_i) = -\sum_j p_{j \mid i} \log p_{j \mid i} = \log(\text{perplexity})$$
困惑度因此可以读作“每个点的有效邻居数”：取 30，就是让每个点大致关心 30 个邻居。它比 \(\sigma\) 直观得多，也是最主要的参数。数据有多尺度结构（局部很密、整体很疏）时，要把不同困惑度下的结果都看一看。
每个点各自定标之后，条件概率再对称化并整体归一化：
$$p_{ij} = \frac{p_{j \mid i} + p_{i \mid j}}{2n}$$
（每行条件概率之和为 1，所以这样定义的 \(p_{ij}\) 全体之和恰为 1。）
低维坐标 \(\mathbf{y}_i\) 之间的相似度不用高斯核，而用自由度为 1 的 t 分布（柯西核）：
$$q_{ij} = \frac{\left(1 + \lVert \mathbf{y}_i - \mathbf{y}_j \rVert^{2}\right)^{-1}}{\sum_{k \neq l} \left(1 + \lVert \mathbf{y}_k - \mathbf{y}_l \rVert^{2}\right)^{-1}}$$
为什么两边不一样？因为低维空间装不下高维的邻居结构：高维里一个点周围的“中等距离”邻居，到二维就没有地方放了（ \(d\) 维球体积按 \(r^d\) 增长，二维的“容量”远远不够）。这就是所谓的拥挤问题（crowding problem）。重尾核的尾巴衰减得慢，使得“不相似的点”在低维也会被推得很开，从而给中等距离腾出位置。反过来，如果用高斯核，这些点会被挤在原点附近，簇黏成一团。
两个分布之间的差异用 KL 散度衡量，优化目标是最小化
$$C = KL(P \,\Vert\, Q) = \sum_{i \neq j} p_{ij} \log \frac{p_{ij}}{q_{ij}}$$
对低维坐标求导（ \(P\) 已对称化）得到
$$\frac{\partial C}{\partial \mathbf{y}_i} = 4 \sum_{j \neq i} \left(p_{ij} - q_{ij}\right)\left(1 + \lVert \mathbf{y}_i - \mathbf{y}_j \rVert^{2}\right)^{-1}\left(\mathbf{y}_i - \mathbf{y}_j\right)$$
这个式子可以这样读： \(p_{ij} > q_{ij}\)（本该更近）的点对相吸， \(p_{ij} < q_{ij}\)（不该这么近）的点对相斥，力的大小还乘上了核的权重。整个算法就是在这两种力之间找平衡：引力来自高维端定义的邻域，斥力主要由低维的重尾核提供。
KL 散度是不对称的，这决定了 t-SNE 的特点： \(p\) 大而 \(q\) 小会被重罚（该近的必须近）， \(p\) 小而 \(q\) 大罚得轻（不该近的稍微近一点可以接受）。所以 t-SNE 偏保局部结构，簇内的邻域很可靠，簇间的排布就不那么可靠。
perplexity、R 的 Rtsne 都是 30）。数据大、结构多尺度时，单靠一个困惑度会顾此失彼；Kobak & Berens（2019）的做法是多尺度：把困惑度 30 与 \(n/100\) 两个核组合起来用，学习率取 \(n/12\)。Rtsne 的 stop_lying_iter = 250 就是控制这一点（前 250 次迭代保持夸张）。Rtsne 的 pca = TRUE 只是先用 PCA 把输入数据降到 initial_dims（默认 50）维，嵌入本身默认仍是随机初始化，要用 PCA 初始化需要自己通过 Y_init 传入。Rtsne 的 theta = 0.5 就是这个近似的精度参数（取 0 即精确计算）。FIt-SNE 再用插值加 FFT 把排斥力降到 \(O(n)\)（Linderman 等, 2019），是百万级数据的常用实现。3 同一组瑞士卷数据（800 个点）的四种画法。颜色是点在流形上的内在坐标（卷展开后的位置）。PCA 把卷的不同层压在同一片区域，颜色交错；t-SNE 与 UMAP 按邻域关系重排后，同一层的点回到彼此附近，颜色沿一条带子渐变。图题里的百分比是 10 近邻的 Jaccard 重叠率。能读出来的只有邻域，颜色带连贯并不代表图上的距离能按比例读回原空间。
图上标注的 kNN 百分比是渲染时算出来的：10 近邻的 Jaccard 重叠率。t-SNE 与 UMAP 都明显高于 PCA，这就是“保邻域”的量化说法。图中的 t-SNE 用的是 Rtsne 默认的随机初始化，UMAP 用的是谱初始化。
UMAP（uniform manifold approximation and projection，McInnes 等, 2018）与 t-SNE 的骨架很像：也是先从 kNN 图出发、也在低维用重尾核、也是“引力 + 斥力”的优化。差别在于每一步都换成了集合论/图论的语言。
建图：对每个点取 \(k\) 个近邻（默认 15）。距离不直接使用，而是先做局部度量归一化：记 \(\rho_i\) 为点 \(i\) 到最近邻的距离，再用二分搜索找一个 \(\sigma_i\)，使得
$$\sum_{j} \exp\!\left(-\frac{d_{ij} - \rho_i}{\sigma_i}\right) = \log_2 k$$
减掉 \(\rho_i\) 保证了“最近邻的隶属度为 1”（局部连通性）， \(\sigma_i\) 则把每个点的邻域尺度拉齐，稠密区和稀疏区因此得到同等对待。
算隶属度： \(\mu_{j \mid i} = \exp\!\left(-\left(d_{ij} - \rho_i\right) / \sigma_i\right)\)，再按模糊集的 t-余模把两个方向合并成无向的 \(\mu_{ij} = \mu_{i \mid j} + \mu_{j \mid i} - \mu_{i \mid j}\mu_{j \mid i}\)。得到的是一张加权图：边权是“这两点算不算邻居”的连续隶属度，而不是硬性的“近/不近”。
低维里把边权建模成
$$w_{ij} = \left(1 + a \lVert \mathbf{y}_i - \mathbf{y}_j \rVert^{2b}\right)^{-1}$$
\(a\) 与 \(b\) 不是手调的，而是由 min_dist 拟合出来的：先按 min_dist 画出一条“小于它时权重保持 1、之后再指数衰减”的目标曲线，再最小二乘拟合出 \(a, b\)。于是 min_dist 的含义很明确，即嵌入里两点之间允许的最小距离：取小值，点靠得更紧，簇更紧凑；取大值，点分布得更开。umap-learn 文档给的经验是 0 用于聚类、0.1–0.3 用于可视化。
目标函数是两张图之间的交叉熵，拆成两项：对每条边（高维认为该近的点对）用 \(-\mu_{ij}\log w_{ij}\) 做吸引，对随机抽出的非边点对用 \(-(1-\mu_{ij})\log(1 - w_{ij})\) 做排斥。排斥项不遍历所有点对，而是负采样：每条边随机抽若干个反例（默认 5 个），用随机梯度下降迭代。这也是它比 t-SNE 快的原因之一：斥力用采样代替了精确计算。
以两个实现为准（默认值取自各自的文档，注意它们并不完全一致）：
| 参数 | uwot（R） | umap-learn（Python） | 作用 |
|---|---|---|---|
n_neighbors | 15 | 15 | 邻域大小，相当于 t-SNE 的困惑度；调大更看全局，调小更看局部 |
min_dist | 0.01 | 0.1 | 嵌入中点与点的最小距离；小则紧凑，大则分散 |
n_components | 2 | 2 | 嵌入维度 |
metric | "euclidean" | "euclidean" | 建图用的距离；高维数据常换成 "cosine" |
negative_sample_rate | 5 | 5 | 每条边抽多少个反例 |
init | "spectral" | "spectral" | 初始化；谱初始化（即前一小节的谱方法）比随机好 |
两个方法常被放在一起比较，UMAP 的论文摘要里也确实写着它“与 t-SNE 的可视化质量相当，并且可以说保留了更多全局结构，运行时间更优”（原文用的是 arguably）。这句话要分开来看：
速度是真的：负采样 + 随机梯度下降让 UMAP 在较大数据上明显更快，这是实现层面的优势。
“更多全局结构”这一点要打折扣。UMAP 的理论建立在“数据在流形上均匀分布”的假设上，而实际数据几乎不会满足这个假设；Chari & Pachter（2023）系统检查了这类嵌入，给出的定量结果并不乐观：二维嵌入里近邻的 Jaccard 不相似度平均高于 0.7；细胞类型的邻居排序与原空间的相关不超过 0.4；最大／最小距离之比被放大 4–200 倍，而且只要调一调 n_neighbors 或困惑度，就能让“某个群体只在一组样本里出现”这种结论翻转。
两边的可用补救是一样的：用有信息的初始化（PCA/谱）而不是随机初始化，全局结构会明显更稳（Kobak & Linderman, 2021）。
所以 t-SNE 和 UMAP 都只能当作“邻域关系的可视化”来用，不要从图上读距离、簇的大小和簇的个数。
下面几条都有出处，也都能用上面的瑞士卷图自己验证：改一改困惑度或 n_neighbors，图就会变。
降维就是在选一个要保留的量。选了什么，决定了图上哪些东西能读：
| 方法 | 保留什么 | 复杂度 | 主要参数 | 图上距离可读吗 |
|---|---|---|---|---|
| PCA | 方差（全局、线性） | \(O(\min(np^2, n^2p))\) 量级 | 主成分个数 | 可读：它本身就是线性投影 |
| PCoA / MDS | 距离（全局） | 以特征分解为主 | 距离的定义 | 可读：欧氏距离下与 PCA 一致 |
| ISOMAP | 测地距离（邻域图上的最短路） | 最短路加稠密特征分解，成本高 | 近邻数 \(k\) | 大致可读：沿流形的距离 |
| Laplacian eigenmaps / LLE | 邻域关系（图上的平滑性、局部线性重构） | 稀疏特征分解 | 近邻数 \(k\) | 不可读 |
| t-SNE | 邻域（局部） | \(O(n^2)\)；Barnes-Hut \(O(n\log n)\) | 困惑度、初始化、随机种子 | 不可读 |
| UMAP | 邻域（局部） | 负采样 + 随机梯度下降，比 t-SNE 快 | n_neighbors、min_dist、随机种子 | 不可读 |
降维和聚类是两件事，放在一起时最容易犯的错是“在二维图上用眼睛数簇，然后宣布有 K 个簇”。正确的顺序是：
谱聚类是最典型的、把两步合起来的做法（见“数据简化”一节）：它先降维、再在低维上跑 k-means，因此低维坐标是聚类过程的一部分，而不是事后画出来的图。
留下的问题： 每个方法都有自己的假设和失效情形。怎样在它们之间选，又怎样判断一个结构是不是真的？这是最后一章的内容。
本章的问题： 前面按“数据准备 → 相似度 → 聚类 → 降维”把方法过了一遍。现在退一步看：这些方法各自假设了什么、什么时候失效，怎样在它们之间选择，以及它们背后有没有共同的结构？
下表把聚类与降维的方法放在一起，对照它们假设的结构、优化的目标和失效的情形。选方法时，先看数据满不满足它的假设：
| 方法 | 假设的结构 | 优化的目标 | 前提与失效情形 |
|---|---|---|---|
| k-means | 各向同性的球形簇 | 簇内平方和 \(W\) | 要先标准化；非凸的簇、大小或密度悬殊的簇、离群点都会出错 |
| 层次聚类（Ward） | 紧致的簇 | 每步使 \(W\) 的增量最小 | 数据大时慢；合并之后不能撤销 |
| 层次聚类（单链接） | 连通的簇 | 最近点对的距离 | 噪声会把簇连成链 |
| DBSCAN | 密度连通的簇 | 没有整体目标，由 \(\varepsilon\) 与 minPts 定义 | 密度差异大时一组参数不够；高维下 \(\varepsilon\) 难选 |
| 高斯混合模型 | 若干个高斯分布的混合 | 似然 | 偏好椭球形；分量多、数据少时不稳 |
| PCA | 线性的低维结构 | 保留方差 | 非线性结构；对离群点敏感 |
| MDS / PCoA | 距离可以嵌入低维 | stress，或双中心化后的特征分解 | 欧氏距离下与 PCA 等价 |
| t-SNE | 邻域结构 | \(\mathrm{KL}(P \parallel Q)\) | 距离和簇的大小不可读；依赖困惑度与初始化 |
| UMAP | 邻域结构（模糊图） | 交叉熵 | 同上；参数与初始化敏感 |
先问三个问题：
流程大致是：
数据 → 查缺失与离群 → 变换（若需要）→ 标准化 →（可选）降维 → 聚类 → 评价 → 解释
设样本 \(\mathbf{x}_1, \dots, \mathbf{x}_n\) 被分成 \(K\) 个簇，总平方和 \(T\) 可以拆成簇内平方和 \(W\) 与簇间平方和 \(B\)：
$$T = W + B, \qquad T = \sum_{i} \lVert \mathbf{x}_i - \bar{\mathbf{x}} \rVert^2$$
这就是方差分析里 \(SS_{\text{total}} = SS_{\text{within group}} + SS_{\text{between group}}\) 的分解（概率统计笔记里把它读成勾股定理）。 \(T\) 由数据决定，与怎么分无关，所以：
此外还有更直接的联系：k-means 的目标可以松弛成一个特征值问题，解落在 PCA 前 \(K-1\) 个主方向张成的子空间里（Ding & He, 2004），这也是先用 PCA 降维再聚类常常有效的原因之一。
谱聚类、Laplacian eigenmaps、t-SNE 和 UMAP 的共同起点，都是先用 kNN 把数据连成一张图，区别在于图之后怎么做。谱方法对图的拉普拉斯矩阵做特征分解，取特征向量作为新坐标（谱聚类再在这些坐标上跑 k-means）；t-SNE 和 UMAP 把邻域关系写成概率或模糊集合，直接优化一个“引力加斥力”的目标。前者有解析解、结果确定，后者能处理更大的数据，但依赖随机优化，结果会随参数和随机种子变化。
没有标签时，评价指标只能说“这个划分在某个指标下如何”，说不出“这个结构是不是真的”。一个常用的补充是看稳定性：对数据重采样（有放回抽样，或随机去掉一部分），重复聚类或降维，用 ARI 比较各次划分之间的一致性。结构在重采样、换算法、换参数下都能重现，才可信；只在一个设置下出现的，更像是方法自己的产物。这和概率统计笔记里用 Bootstrap 估计统计量的抽样分布是同一个想法：把“数据的随机性”显式地模拟出来。