# 2.12. t-SNE
`TSNE` 是 RustyML 对 t-distributed Stochastic Neighbor Embedding（t-SNE）的实现，是把高维数据变成一张二维或三维图的常用方法。它位于 `machine_learning::manifold`。跟 [2.10. 主成分分析](./2.10._主成分分析.md) 和 [2.11. 核主成分分析](./2.11._核主成分分析.md) 里的线性降维器不同，`TSNE` 学不到任何可复用的投影，只嵌入你交给它的那些点。
如果你熟悉 scikit-learn，这就是 `sklearn.manifold.TSNE`，API 是特意照着它设计的：暴露一个 `perplexity`、一个 `learning_rate`、一个 `n_iter`，可以在 exact 和 Barnes-Hut 两种梯度之间选择，初始化也可以在 PCA 与随机之间选。
## 2.12.1. t-SNE 适合做什么，不适合做什么
t-SNE 是一个*可视化*工具。它唯一的任务，是把高维空间里相似的点，在低维画布上摆到彼此靠近的位置，让人眼能看出数据里的簇结构。人们误用 t-SNE 的大多数情况，都是把它当成通用的降维工具来用，但它并不是。
这套设计把这条限制落到了实处。在 [估计器 trait](../Chapter-01/1.5._Prelude与模块导入.md) 里，PCA 和核 PCA 同时实现了 `Transform`（把新的、没见过的数据，经一个拟合好的模型投影过去）和 `FitTransform`。`TSNE` 只实现 `FitTransform`：没有 `transform` 方法，没有存下来的拟合状态，也没法往一个已有的嵌入里加点。嵌入坐标本身就是优化变量，而不是某个学到的函数的输出。
以后要投影新样本，用 PCA。只是想给手头的数据画图，用 t-SNE。这两个工具是互补的：一条常见的流水线，先跑 PCA，再把结果喂给 t-SNE（见 [2.12.9](#2129-开销扩展性与宽数据预处理)）。
那个固有方法接收 `&self`，返回一个全新的嵌入，所以它从不修改模型。你可以直接调用它，也可以通过 `FitTransform` trait 调用。trait 方法接收 `&mut self`，只是转手调用那个固有方法。
## 2.12.2. t-SNE 的工作原理
t-SNE 把相似度量两遍：一遍在原始空间，一遍在嵌入空间，然后不断挪动嵌入，直到两边对上。
在高维空间里，t-SNE 构建一组**两两之间的亲和度**。对每个点 `i`，它以该点为中心放一个高斯，把 `i` 到各邻居的平方距离，转成条件概率 `p_{j|i}`：近处的点概率高，远处的点概率接近零。
高斯的宽度不是固定的。RustyML *逐点*求解它：对 `sigma` 做二分搜索，让每个点的邻居分布的熵，匹配上你设定的目标。这个目标就是 **perplexity**，可以读作有效邻居数，大致是每个点应该"感受"到多少个邻居。
这个搜索最多跑 50 步二分，收敛到 `1e-5` 的容差。自距离总是映射成正好为零，所以一个点永远不会是自己的邻居。随后，条件概率被对称化成联合概率 `p_ij`，它在所有点对上求和为 1。
在嵌入空间里，t-SNE 用的是另一个尾巴更重的核。这个核是**自由度为 1 的 Student-t 分布**，`q_ij` 正比于 `(1 + ||y_i - y_j||^2)^-1`。这正是名字里那个"t"的由来，也是它解决**拥挤问题**（crowding problem）的办法。二维里的高斯，腾不出足够的空间，去安置那些在比如说 50 维里只算中等距离的邻居。
面积就是不够，于是一切都塌成一团。t 分布厚重的尾巴，让中等相似的点可以在图上离得很远，却不用付出多少概率代价，于是簇之间干净利落地分开，而不是挤作一堆。
这两个分布的匹配方式，是在嵌入坐标上做梯度下降，最小化 **Kullback-Leibler 散度** `KL(P || Q)`。KL 散度的不对称是故意的：把一对高 `p`（真正相近）的点在图上摆得很远，会受到重罚；把一对低 `p`（真正相远）的点摆得很近，几乎不受罚。正是这份不对称，让 t-SNE 忠实地保住*局部*邻域，把*全局*距离当作可以牺牲的东西，也正是它驱动了 [2.12.8](#2128-读懂-t-sne-图) 里所有读图的注意事项。
## 2.12.3. 构造模型
`TSNE::new` 接收 4 个核心超参数，一开始就校验它们，出问题时返回 [`Error::InvalidParameter`](../Chapter-01/1.6._错误处理.md)，而不是等到拟合时才失败。
```rust
use ndarray::array;
use rustyml::machine_learning::manifold::t_sne::{TSNE, TSNEMethod};
fn main() {
// 三维特征空间里两组松散的点。
let x = array![
[0.0, 0.0, 0.0],
[0.2, 0.1, -0.1],
[-0.1, 0.2, 0.1],
[0.1, -0.2, 0.0],
[5.0, 5.0, 5.0],
[5.2, 4.9, 5.1],
[4.8, 5.1, 4.9],
[5.1, 5.0, 4.8],
];
// new(n_components, perplexity, learning_rate, n_iter) -> Result<TSNE, Error>。
let tsne = TSNE::new(2, 3.0, 200.0, 300)
.unwrap()
.with_method(TSNEMethod::Exact)
.unwrap();
// fit_transform 接收 &self，返回一个 (n_samples, n_components) 数组。
let embedding = tsne.fit_transform(&x).unwrap();
assert_eq!(embedding.shape(), &[8, 2]);
println!("embedding shape: {:?}", embedding.shape());
}
```
构造函数的校验规则窄，但严：
| 参数 | 类型 | 约束 | 违规时 |
| --- | --- | --- | --- |
| `n_components` | `usize` | 大于 0（用 2，或者想要可旋转的图就用 3） | `InvalidParameter` |
| `perplexity` | `f64` | 严格为正且有限 | `InvalidParameter` |
| `learning_rate` | `f64` | 严格为正且有限 | `InvalidParameter` |
| `n_iter` | `usize` | 大于 0 | `InvalidParameter` |
`TSNE::default()` 给出的是 `new(2, 30.0, 200.0, 1000)`，配 PCA 初始化和 Barnes-Hut，对一个真实数据集（而不是玩具规模）来说是个合理的起点。其余一切都通过构建方法设置，每个都返回 `Self` 以便链式调用，唯独 `with_method` 返回 `Result`，因为 Barnes-Hut 得校验它的 angle 和维度：
| 构建方法 | 设置 | 默认值 |
| --- | --- | --- |
| `with_method(TSNEMethod)` 返回 `Result` | exact 或 Barnes-Hut 梯度 | `n_components` 为 3 或更小时用 Barnes-Hut，否则用 Exact |
| `with_init(Init)` | `Init::PCA` 或 `Init::Random` | `Init::PCA` |
| `with_random_state(u64)` | 随机初始化路径的种子 | `None` |
| `with_min_grad_norm(f64)` | 提前停止的梯度阈值 | `1e-7` |
每个存下来的字段都有对应的 getter：`get_n_components`、`get_perplexity`、`get_learning_rate`、`get_n_iter`、`get_random_state`、`get_init`、`get_method`、`get_min_grad_norm`。用它们可以检查一串构建方法调用最终解析成了什么。
## 2.12.4. Exact 与 Barnes-Hut
`TSNEMethod` 决定了开销上的取舍。RustyML 的默认值**不是** exact 方法，这跟很多人的想当然不一样。
`TSNEMethod::Exact` 构建完整的稠密 `n x n` 联合概率矩阵，每次迭代都在所有点对上算梯度，因此每一步在时间和内存上都是 `O(n^2)`。`TSNEMethod::Exact` 支持任意 `n_components`。
`TSNEMethod::BarnesHut { angle }` 让亲和度保持稀疏：每个点只跟它 `k = ceil(3 * perplexity) + 1` 个最近邻打交道，用一棵空间划分树来概括排斥力，把每次迭代压到大约 `O(n log n)`。
`angle`（theta）取值在 `[0, 1)`，用精度换速度：越大，树的单元格展开得越早，跑得更快但更粗糙。`0.5` 是标准的折中。这棵树活在嵌入空间里，所以 Barnes-Hut 只支持 `n_components` 为 3 或更小。
只要 `n_components` 为 3 或更小，`TSNE::new` 就会选 `angle = 0.5` 的 Barnes-Hut，这覆盖了所有可视化场景；否则就退回 Exact。`with_method` 强制同样的约束：`angle` 落在 `[0, 1)` 之外会被 `InvalidParameter` 拒绝，Barnes-Hut 配上超过 3 个分量，也会被同一个错误拒绝。
```rust
use ndarray::array;
use rustyml::machine_learning::{TSNE, TSNEMethod};
fn main() {
let x = array![
[0.0, 0.0], [1.0, 0.0], [0.0, 1.0], [1.0, 1.0],
[8.0, 8.0], [9.0, 8.0], [8.0, 9.0], [9.0, 9.0],
];
// n_components 为 2 时的默认值：angle 为 0.5 的 Barnes-Hut。
let bh = TSNE::new(2, 3.0, 200.0, 300).unwrap();
assert_eq!(bh.get_method(), TSNEMethod::BarnesHut { angle: 0.5 });
// 更粗、更快的树。
let coarse = TSNE::new(2, 3.0, 200.0, 300)
.unwrap()
.with_method(TSNEMethod::BarnesHut { angle: 0.8 })
.unwrap();
// Exact 的 O(n^2) 梯度；一旦 n_components > 3 就只有这一个选项。
let exact = TSNE::new(2, 3.0, 200.0, 300)
.unwrap()
.with_method(TSNEMethod::Exact)
.unwrap();
for model in [bh, coarse, exact] {
let emb = model.fit_transform(&x).unwrap();
assert_eq!(emb.ncols(), 2);
}
}
```
Barnes-Hut 的梯度经过缩放，去匹配 exact 路径（那个因子 4 已经折算进去），所以同一个 `learning_rate` 对两种方法都适用，你可以在它们之间切换而不用重新调参。两种方法都逐位可复现：树的构建是确定性的，归一化项按固定顺序累加，因此结果不依赖线程调度。
## 2.12.5. perplexity 与样本数规则
perplexity 是最能改变你图形状的那个超参数。它设定了每个点校准自己高斯时对准的有效邻居数。perplexity 低会强调局部结构，容易把数据碎成许多小岛；perplexity 高会把更大的邻域揉在一起，可能把本来分明的簇抹成一片。
5 到 50 之间的取值，几乎覆盖所有用法，而合适的值会随数据集变大而上移。
perplexity 上有两条限制，它们并不一样。第一条由 `fit_transform` 强制执行，而不是 `TSNE::new`：`perplexity` 必须严格小于样本数，否则 `fit_transform` 返回 `InvalidParameter`。
第二条限制关乎 Barnes-Hut 的稀疏性，而不是正确性。Barnes-Hut 路径给每个点保留 `k = ceil(3 * perplexity) + 1` 个邻居，上限是 `n - 1`。有些 t-SNE 实现会把高于大约 `n / 3` 的 perplexity 当成错误直接拒绝，RustyML 不会。过了这个点，邻居数的上限早已封顶在 `n - 1`，也就是每个点已经把其他所有点都列为邻居了。这时嵌入依然正确，只是 Barnes-Hut 会失去它相对 Exact 通常有的速度优势。
真正要紧的是那条强制执行的 `perplexity < n` 检查，它对两种方法都一样。这也是为什么在寥寥几个点上跑 t-SNE 收获不大：20 个样本时，强制规则已经把 perplexity 压在 20 以下，在这个上限附近跑，几乎没有真实的邻居结构可找，图上的"簇"多半是噪声。
```rust
use ndarray::array;
use rustyml::error::Error;
use rustyml::machine_learning::{TSNE, TSNEMethod};
fn main() {
let x = array![[0.0, 0.0], [1.0, 1.0], [2.0, 0.5]]; // 3 个样本
// perplexity 必须严格小于 n_samples。
// 这里 3.0 并不小于 3。
let model = TSNE::new(2, 3.0, 200.0, 100)
.unwrap()
.with_method(TSNEMethod::Exact)
.unwrap();
match model.fit_transform(&x) {
Err(Error::InvalidParameter { .. }) => {
println!("perplexity too large for this sample count");
}
other => panic!("expected InvalidParameter, got {other:?}"),
}
}
```
## 2.12.6. 初始化、设种子与可复现性
`Init` 决定优化从哪里起步，这个选择会影响可复现性。
`Init::PCA` 是默认值：它用输入的前几个主成分来初始化嵌入，并缩放到一个很小的展布。只要 PCA 成功，这个方法就是**确定性**的，无视 `random_state`——同一份数据总是给出同样的起始布局，因而也给出同样的最终嵌入。它还给优化器一个展布合理的起始布局，这就是它成为默认值的原因。
PCA 初始化可能在两种情况下失败：输入的特征数比 `n_components` 还少，或者它的首个主成分退化（展布为零）。这两种情况下，`Init::PCA` 都会退回 `Init::Random` 用的那套随机初始化。而这个退路会去看 `random_state`（或全局种子），确定性也就随之回来了。
`Init::Random` 从极小的随机噪声出发，种子取自 crate 的中央 RNG。除了上面那条退路之外，只有这条路径会去看 `random_state`。用 `with_random_state` 设个种子，这次运行就变得逐位可复现；不设它，起点就取自系统熵，于是每次运行都不一样。
```rust
use ndarray::array;
use rustyml::machine_learning::{Init, TSNE, TSNEMethod};
use rustyml::set_global_seed;
fn main() {
let x = array![
[0.0, 0.0], [1.0, 0.5], [0.5, 1.0],
[6.0, 6.0], [7.0, 6.5], [6.5, 7.0],
];
// 为单个模型显式设种子：无论有没有全局种子都可复现。
let seeded = TSNE::new(2, 2.0, 200.0, 250)
.unwrap()
.with_init(Init::Random)
.with_random_state(42)
.with_method(TSNEMethod::Exact)
.unwrap();
let e1 = seeded.fit_transform(&x).unwrap();
let e2 = seeded.fit_transform(&x).unwrap();
assert_eq!(e1, e2); // 逐位相同
// 一个没设种子、随机初始化的模型之所以能复现，只是因为
// 这段代码先设定了线程局部的全局种子。
set_global_seed(7);
let unseeded = TSNE::new(2, 2.0, 200.0, 250)
.unwrap()
.with_init(Init::Random)
.with_method(TSNEMethod::Exact)
.unwrap();
let _emb = unseeded.fit_transform(&x).unwrap();
}
```
`random_state` 字段喂给 `make_rng`，crate 里每个随机化组件都走这同一条种子解析路径。显式的 `Some(seed)` 是独立的，从不碰全局流；`None` 则听命于 [`set_global_seed`](../Chapter-07/7.1._可复现性与随机种子.md) 在当前线程上设定的值。
这带来两个实际后果。其一，在默认的 PCA 初始化下，种子并不重要——除非你也切到 `Init::Random`，否则别指望 `with_random_state` 改变什么。其二，优化器里的并行归约也是顺序稳定的，所以一份固定配置在同一台机器上逐位可复现，跟线程数无关。完整的机制，包括全局种子的线程局部特性，都在 [7.1. 可复现性与随机种子](../Chapter-07/7.1._可复现性与随机种子.md) 里。
## 2.12.7. 优化器内部
这个梯度下降循环不是普通的 SGD，它的几个阶段解释了 `n_iter` 和 `learning_rate` 大部分的作用。
前 250 次迭代运行在**早期夸张**（early exaggeration）之下（如果 `n_iter` 更小，那就是全部迭代）。这个阶段，t-SNE 把每个联合概率 `p_ij` 都乘以 12，放大吸引力，让紧致的簇在布局定型之前先聚拢起来，在各组之间腾出空地。阶段一结束，夸张系数就落回 1，图开始精调。
如果 `n_iter` 设得太低，运行可能会停在夸张阶段内部，留下一个过度收缩、还没精调的嵌入。这也是默认用 1000 次迭代的原因之一，真实运行很少会想要少于几百次迭代。
动量走同一张时间表：夸张阶段是 `0.5`，之后是 `0.8`，让精调阶段带着更多惯性穿过 KL 曲面上那些平坦的地段。每个坐标还有一个**自适应增益**（Jacobs 的 delta-bar-delta）：梯度保持符号时增益增长，步子来回震荡时增益衰减，下限钉在 `0.01`。
所以 `learning_rate` 只设定一个基准步长，每个参数的有效学习率会随运行推进而自适应。每一步之后，嵌入都会重新以原点为中心，防止漂移，这就是为什么输出的各列，均值总是接近零。
`min_grad_norm` 控制提前停止。夸张阶段结束后，循环每次迭代都检查梯度里绝对值最大的那一项，一旦它跌破阈值（默认 `1e-7`）就立刻停下，省掉图收敛之后的空转迭代。这项检查在夸张阶段被跳过，因为那时被放大的梯度根本不会触发它。把 `min_grad_norm` 设成 `0.0`，就能关掉提前停止，永远跑满 `n_iter`。
```rust,ignore
// 完整的构建方法列表，供参考。
let tsne = TSNE::new(2, 30.0, 200.0, 1000)? // n_components, perplexity, lr, n_iter
.with_init(Init::PCA) // 或 Init::Random
.with_random_state(0) // 只影响 Init::Random
.with_method(TSNEMethod::Exact)? // 或 BarnesHut { angle }
.with_min_grad_norm(0.0); // 关闭提前停止
```
启用 `show_progress` feature（见 [1.2. 安装与Feature配置](../Chapter-01/1.2._安装与Feature配置.md)），循环就会在每次迭代计算并显示实时的 KL 散度；不启用这个 feature，那一趟计算会被整个跳过，在生产构建里不花一分钱开销。
## 2.12.8. 读懂 t-SNE 图
t-SNE 优化的是局部邻域，把全局几何丢在一边。正因如此，这张图在好几件事上会误导人，读图时要记住这一点。
两个簇之间的距离什么都说明不了。画布上离得远的两团，并不比离得近的两团"更不一样"。簇间的间隙是 KL 目标和优化器随机游走的产物，不是一次测量。
簇的*大小*也是同样的道理：一个簇的点看起来铺得多开，并不是该簇真实方差的度量。为了保住局部邻域完整，稠密区域会被放大，稀疏区域会被压缩。绝不要把 t-SNE 图上的簇间距离或簇直径，当成定量结果来引用。
嵌入依赖初始化，而且优化是非凸的，所以单次运行只是一整个布局分布里抽出的 1 个样本。多跑几次：在 `Init::Random` 下换种子，或者把 perplexity 扫过 5、30、50 这样的值，只相信那些跨运行都还在的结构。一个在某个 perplexity 下出现、换一个就散掉的簇，多半是假象，而不是发现。
不要把 t-SNE 坐标当特征喂给下游模型。它们是一张图，不是可复用的表示：没有 `transform`，所以不适用于新数据；它们也会随运行变化，作为距离没有意义。想要可复用、可投影的特征，用 [PCA](./2.10._主成分分析.md)。
一个常见且合理的工作流是反过来做：先在原始空间里聚类，比如用 [KMeans](./2.7._KMeans聚类.md)，再按簇标签给 t-SNE 图上色，从视觉上核验聚类结果。
## 2.12.9. 开销、扩展性与宽数据预处理
两种方法都要在开头一次性付出 `O(n^2)` 的准备开销，用来计算两两距离、校准每个点的 sigma。Barnes-Hut 在它更便宜的 `O(n log n)` 迭代开始之前，仍要做一次 `O(n^2)` 的近邻搜索。所以两者每次迭代的开销不同：Exact 是 `O(n^2)`，Barnes-Hut 是 `O(n log n)`，但谁都躲不开准备阶段那个平方项，而且 exact 路径的内存开销是一整个 `n x n` 矩阵。
粗略地说，exact t-SNE 在几千个点这个量级还算从容；再往上，Barnes-Hut 能让你推到几万个点。让默认的方法选择替你处理这件事就好。
另一个杠杆是你数据的*宽度*。距离计算的开销是 `O(n^2 * d)`，`d` 是输入特征数，而且高维欧几里得距离本身还很嘈杂。标准的对策，是先用 PCA 把宽数据降到大约 50 维，再在那上面跑 t-SNE，这对速度和质量都有帮助。
这一步跟 `Init::PCA` 是两回事：`Init::PCA` 只用前 2 或 3 个主成分，去给*起始布局*播种；这里，PCA 压缩的是*输入本身*，在 t-SNE 运行之前就完成了。
```rust
use ndarray::array;
use rustyml::machine_learning::{PCA, TSNE, TSNEMethod};
fn main() {
// 10 个样本，8 个原始特征（真实问题里不妨想象成上百个）。
let x = array![
[0.10, 0.21, 0.05, 0.30, 0.11, 0.02, 0.22, 0.14],
[0.12, 0.19, 0.08, 0.28, 0.09, 0.05, 0.20, 0.10],
[0.09, 0.23, 0.03, 0.31, 0.13, 0.01, 0.24, 0.16],
[0.11, 0.20, 0.06, 0.29, 0.10, 0.03, 0.21, 0.12],
[0.80, 0.70, 0.90, 0.10, 0.60, 0.85, 0.15, 0.75],
[0.82, 0.68, 0.88, 0.12, 0.62, 0.83, 0.17, 0.73],
[0.78, 0.72, 0.91, 0.09, 0.58, 0.87, 0.14, 0.77],
[0.81, 0.69, 0.89, 0.11, 0.61, 0.84, 0.16, 0.74],
[0.40, 0.45, 0.42, 0.55, 0.38, 0.47, 0.52, 0.44],
[0.42, 0.43, 0.44, 0.53, 0.36, 0.49, 0.50, 0.46],
];
// 第一步：用 PCA 压缩（这里压到 4 维，宽数据用约 50 维）。
let mut pca = PCA::new(4).unwrap();
let reduced = pca.fit_transform(&x).unwrap();
// 第二步：在这份紧凑表示上跑 t-SNE。
let tsne = TSNE::new(2, 3.0, 200.0, 300)
.unwrap()
.with_method(TSNEMethod::Exact)
.unwrap();
let embedding = tsne.fit_transform(&reduced).unwrap();
assert_eq!(embedding.shape(), &[10, 2]);
}
```
一旦两两之间的计算量足够大，预计算和每次迭代的那几趟就会切换到 RustyML 的并行原语；GEMM 调用则自行并行。归约保持固定顺序，所以结果不依赖线程数。要调吞吐量，见 [7.3. 性能调优与并行](../Chapter-07/7.3._性能调优与并行.md)，那里讲了这些门限值。
## 2.12.10. fit_transform 的错误
构造时校验 4 个超参数，其余检查都在 `fit_transform` 时运行，全都返回整个 crate 通用的 [`Error`](../Chapter-01/1.6._错误处理.md) 类型：
| 情形 | 错误变体 |
| --- | --- |
| 零行 | `EmptyInput` |
| 输入里有 `NaN` 或无穷值 | `NonFinite` |
| 样本数少于 2 | `InvalidInput` |
| `perplexity` 没有严格小于样本数 | `InvalidParameter` |
每个失败都是一个带类型的 `Error`，而不是 panic。你可以对原因做模式匹配再反应：用更小的 perplexity 重试、清掉非有限的行，或者干脆停下，就像上面那个例子一样。