# 6.1. 距离度量
距离是大多数经典机器学习背后的一个基本概念。K 近邻按距离给候选点排序。DBSCAN 通过把距离与阈值比较来生长簇。轮廓系数对距离取平均。k-means 最小化的是距离的平方。
RustyML 把这一切都定义在一个小模块 [`crate::math::distance`](https://docs.rs/rustyml/latest/rustyml/math/distance/index.html) 里。这个模块是“两点之间有多远”的唯一定义之处。每个支持度量选择的估计器都共用同一个调度器。本页记录它的公开接口：有什么、没有什么，以及数值上的捷径在哪里。
这个模块分两层。底层是 3 个自由函数。它们是不分配内存的内核，每次处理一对向量。顶层是 [`DistanceCalculationMetric`](https://docs.rs/rustyml/latest/rustyml/math/enum.DistanceCalculationMetric.html)，一个小枚举。这个枚举给度量命名，并调度到对应内核。
估计器存的是这个枚举，而不是函数指针，因为枚举是 `Copy` 的，支持 `serde` 序列化，`match` 起来开销也很小。要搭建自己的最近邻逻辑，就直接用内核。要获得和库内部一致的度量抽象，就用枚举。
## 6.1.1. 3 个逐行内核
这 3 个内核都从 `rustyml::math` 重新导出。它们的名字很重要：没有名为 `euclidean_distance_row` 的函数。欧几里得内核名叫 `squared_euclidean_distance_row`。它返回平方差之和，从不开方。
这不是疏忽，而是整个设计的核心。只关心排序的调用方——比如找最近点、判断是否落在半径内、找最近质心——根本用不到开方。给每一对点都算一次 `sqrt` 纯属浪费。真要拿到真正的欧几里得距离，就自己开方，或者走调度器。
```rust,ignore
pub fn squared_euclidean_distance_row<S1, S2>(x1: &ArrayBase<S1, Ix1>, x2: &ArrayBase<S2, Ix1>) -> f64;
pub fn manhattan_distance_row<S1, S2>(x1: &ArrayBase<S1, Ix1>, x2: &ArrayBase<S2, Ix1>) -> f64;
pub fn minkowski_distance_row<S1, S2>(x1: &ArrayBase<S1, Ix1>, x2: &ArrayBase<S2, Ix1>, p: f64) -> f64;
// where S1: Data<Elem = f64>, S2: Data<Elem = f64>
```
输入类型同时接受视图和切片。每个函数都接收一个一维 `ndarray` 数组的引用。每个函数都通过 `S: Data<Elem = f64>` 对存储方式泛型。自有的 `Array1<f64>`、借来的 `ArrayView1<f64>`，以及矩阵的一行（比如 `&data.row(i)`），全都能原样传入。
不必先把行拷进 `Vec<f64>`。元素类型固定为 `f64`，没有 `f32` 路径。`S1` 和 `S2` 是相互独立的类型参数，所以两个参数可以用不同的存储类型。拿一个自有的查询向量去和矩阵的某一行比较，完全没问题。
这 3 个函数本身都不会因长度不匹配而 panic。`ndarray` 的 `Zip` 要求两边等长，你若违反这条规则，panic 就发生在那里。请把维度相等当作一条由你自己维护的前置条件。
```rust
use ndarray::array;
use rustyml::math::{
manhattan_distance_row, minkowski_distance_row, squared_euclidean_distance_row,
};
fn main() {
let a = array![1.0, 2.0, 3.0];
let b = array![4.0, 6.0, 8.0];
// 平方 L2，不开方。要度量距离请自己开方。
let sq = squared_euclidean_distance_row(&a, &b);
let euclidean = sq.sqrt();
let l1 = manhattan_distance_row(&a, &b);
let l3 = minkowski_distance_row(&a, &b, 3.0);
// 闵可夫斯基是超集：p = 1 退化为曼哈顿，p = 2 退化为欧几里得。
let mink1 = minkowski_distance_row(&a, &b, 1.0);
let mink2 = minkowski_distance_row(&a, &b, 2.0);
assert!((mink1 - l1).abs() < 1e-12);
assert!((mink2 - euclidean).abs() < 1e-12);
println!("sq={sq} l2={euclidean} l1={l1} l3={l3}");
}
```
`minkowski_distance_row` 是通用形式。它对每个坐标累加 `|a_i - b_i|^p`，再把总和取 `1/p` 次方。它是这 3 个函数里唯一可能 panic 的一个。当 `p` 小于 1.0，或者 `p` 为 `NaN` 时，它就会 panic。panic 消息的末尾就是你传进去的那个值：
```text
invalid parameter `p`: Minkowski order must be at least 1.0, got 0.5
```
阶数小于 1.0 会被拒绝，是因为它们根本构不成一个度量。三角不等式对这些阶数不成立。6.1.5 里讲到的 kd 树剪枝依赖三角不等式。任何依赖它的索引，在这些阶数下都会返回错误的答案，而不只是奇怪的答案。
裸内核并不拒绝 `p = f64::INFINITY`。无穷大不小于 1.0，也不是 `NaN`，所以检查会通过。函数于是会算出一个退化的 `powf(inf)` 表达式，而不是切比雪夫（L-infinity）极限。别指望传一个无穷阶数就能得到那个极限。6.1.4 会说明，估计器的构建器拒绝这种情况，而裸内核并不拒绝。
## 6.1.2. `DistanceCalculationMetric` 调度器
`DistanceCalculationMetric` 是可配置度量那一层。它有 3 个变体，`Euclidean` 是 `Default`：
| `Euclidean` | L2 范数（默认） | `squared_euclidean_distance_row(...).sqrt()` |
| `Manhattan` | L1 范数 | `manhattan_distance_row(...)` |
| `Minkowski(f64)` | 通用 p 范数，`p` 内联携带 | `minkowski_distance_row(..., p)` |
变体本身就是全部配置。`Minkowski` 把 `p` 值作为自己的载荷带在身上。因此一个度量就是一个自洽的值，没有另外的参数需要保持同步。
这个枚举派生了 `Clone`、`Copy`、`PartialEq` 和 `Default`。在 `machine_learning` 或 `utils` feature 下，它还派生了 `Serialize` 和 `Deserialize`。这让它很容易存进结构体字段。这也意味着它能挺过模型持久化（见 [7.2. 深入模型持久化](../Chapter-07/7.2._深入模型持久化.md)）。
`DistanceCalculationMetric` 上有两个公开方法。第一个是 `distance(&self, a: ArrayView1<f64>, b: ArrayView1<f64>) -> f64`。它是度量调度的唯一权威来源。每个支持度量选择的估计器都调它，而不是各自写一遍 `match`。它按值接收 `ArrayView1<f64>`，不是按引用。`ArrayView1` 是 `Copy` 的，所以你可以直接传 `v.view()` 或矩阵的一行，还能跨多次调用复用同一个视图而无需克隆。
第二个公开方法是 `within(&self, a, b, threshold) -> bool`。它回答的是 `distance(a, b) <= threshold` 是否成立，而且不必先算出真实距离。它转而在度量的免开方空间里比较，比如对 `Euclidean` 就是 `sq_dist <= threshold * threshold`。这个映射在非负值上单调，所以结果始终和朴素比较一致，却省掉了 `sqrt`。正因如此，半径查询应该优先用 `within`，而不是 `distance(...) <= r`。
```rust
use ndarray::array;
use rustyml::math::DistanceCalculationMetric;
fn main() {
let a = array![0.0, 0.0];
let b = array![3.0, 4.0];
let euclidean = DistanceCalculationMetric::Euclidean;
let manhattan = DistanceCalculationMetric::Manhattan;
let minkowski = DistanceCalculationMetric::Minkowski(3.0);
// ArrayView1<f64> 是 Copy 的，所以同一个视图能跨多次调用复用。
assert_eq!(euclidean.distance(a.view(), b.view()), 5.0); // sqrt(9 + 16)
assert_eq!(manhattan.distance(a.view(), b.view()), 7.0); // 3 + 4
// `within` 在免开方空间里比较：5^2 <= 5^2 为真，5^2 <= 4.9^2 为假。
assert!(euclidean.within(a.view(), b.view(), 5.0));
assert!(!euclidean.within(a.view(), b.view(), 4.9));
let _ = minkowski.distance(a.view(), b.view());
}
```
你可以从 2 个等价的位置导入这个调度器。它的老家是 `rustyml::math::DistanceCalculationMetric`。给 ML 用户的重新导出是 `rustyml::machine_learning::DistanceCalculationMetric`。两个名字指向同一个类型。用哪个路径，取决于你已经在从哪个模块导入。
## 6.1.3. 度量的性质与闵可夫斯基阶数
这 3 个度量共享几条性质。每一个都非负且对称：`d(a, b) == d(b, a)`。每一个都只在两个向量相同时为零。每一个都满足三角不等式，前提是库允许的那些阶数。这些性质让 6.1.5 里的 kd 树剪枝得以成立。估计器依赖着它们。
闵可夫斯基阶数 `p` 在几个有名的度量之间移动。它控制单个大坐标差能主导结果到什么程度。当 `p = 1` 时，得到的是曼哈顿距离。此时每根轴贡献自己的原始绝对差。斜着走一步，代价是两条直角边之和。
当 `p = 2` 时，得到的是欧几里得距离，也就是普通的直线距离。当 `p` 涨过 2，最大的单轴差会越来越主导总和。每个差值都被提升到 `p` 次方，所以更大的 `p` 会更偏袒那个最大的差距。度量的行为就变得越来越像“只看最大坐标差”。这种行为就是切比雪夫极限，也叫 L-infinity 极限。
RustyML 不把这个极限做成一个可用的度量。没有 `Chebyshev` 这个变体。`Minkowski(f64::INFINITY)` 对估计器来说不是合法配置（见 6.1.4）。想要接近“最大坐标差”那种行为，就挑一个大的有限 `p`。把这个结果当作一种近似，而不是真正的极限。
`(1, 2)` 之间的分数阶，比如 `Minkowski(1.5)`，是合法的度量。它们落在城区距离和直线几何之间。用它们来缓和欧几里得对离群点的敏感度，同时不必彻底走到曼哈顿距离。
## 6.1.4. 哪些估计器接受哪些度量
有 2 个估计器让你选择度量。两者用的是同一套模式：一个返回 `Result` 的 `with_metric` 构建器。它返回 `Result`，是因为它在你设置度量的那一刻就校验闵可夫斯基阶数。
| [`KNN`](../Chapter-02/2.3._K近邻.md) | `.with_metric(...)?` 构建器 | 欧几里得、曼哈顿、闵可夫斯基（p >= 1，有限） |
| [`DBSCAN`](../Chapter-02/2.8._DBSCAN.md) | `.with_metric(...)?` 构建器 | 欧几里得、曼哈顿、闵可夫斯基（p >= 1，有限） |
| [`silhouette_score`](../Chapter-05/5.3._聚类指标.md) | `metric` 函数参数 | 欧几里得、曼哈顿、闵可夫斯基（p >= 1） |
`with_metric` 比裸内核更严格。当 `p < 1.0`，或者 `p` 不是有限值时，它会拒绝 `Minkowski(p)`。这种情况下，它返回 `Error::InvalidParameter`（见 [1.6. 错误处理](../Chapter-01/1.6._错误处理.md)）。它不会把失败拖到 fit 时才以 panic 的形式暴露。这正是 `with_metric` 返回 `Result` 的原因：默认构造器绝不会在度量上失败，但覆盖它可能会失败。失败会立刻出现，就在构建器调用的那一刻。
两个估计器都默认使用 `Euclidean`。只有想要别的度量时，才需要调用 `with_metric`。
```rust
use ndarray::array;
use rustyml::machine_learning::neighbors::{KNN, WeightingStrategy};
use rustyml::math::DistanceCalculationMetric;
fn main() {
let x_train = array![[0.0, 0.0], [10.0, 0.0], [0.0, 10.0]];
let y_train = array![0_i32, 1, 1];
let mut knn = KNN::<i32>::new(1)
.unwrap()
.with_weighting_strategy(WeightingStrategy::Uniform)
.with_metric(DistanceCalculationMetric::Manhattan)
.unwrap();
knn.fit(&x_train, &y_train).unwrap();
let x_test = array![[0.5, 0.0], [9.5, 0.0]];
let preds = knn.predict(&x_test).unwrap();
println!("{preds:?}");
// 阶数小于 1 不是一个度量，构建器会在做任何事之前就拒绝它。
let bad = KNN::<i32>::new(1)
.unwrap()
.with_metric(DistanceCalculationMetric::Minkowski(0.5));
assert!(bad.is_err());
}
```
[`KMeans`](../Chapter-02/2.7._KMeans聚类.md) 和 [`MeanShift`](../Chapter-02/2.9._MeanShift.md) 都不接收度量参数。两者都直接调用 `squared_euclidean_distance_row`，所以从构造上就只能用欧几里得。k-means 的定义就是最小化簇内平方 L2 距离。换掉度量会破坏质心更新的数学，所以没有可以切换的选项。要做非欧几里得聚类，该用 DBSCAN。
给 `silhouette_score` 传一个度量，能让你在构建聚类时所用的同一套几何下评估它。举例来说，给一个用了曼哈顿距离的 DBSCAN 结果打分时，就用 `DistanceCalculationMetric::Manhattan`。这样能让评估和聚类保持一致。
```rust
use ndarray::array;
use rustyml::math::DistanceCalculationMetric;
use rustyml::metrics::silhouette_score;
fn main() {
// 两团分得很开的点。
let x = array![
[0.0, 0.0], [0.2, 0.1], [0.1, -0.2],
[10.0, 10.0], [10.1, 9.8], [9.9, 10.2],
];
let labels = array![0_isize, 0, 0, 1, 1, 1];
let s_euclidean = silhouette_score(&x, &labels, DistanceCalculationMetric::Euclidean);
let s_manhattan = silhouette_score(&x, &labels, DistanceCalculationMetric::Manhattan);
println!("euclidean={s_euclidean} manhattan={s_manhattan}");
}
```
## 6.1.5. 平方距离与可比空间优化
`squared_euclidean_distance_row` 把平方距离这条捷径以一个公开函数的形式暴露出来。库内部也在用同一条捷径，通过一个私有的想法：可比空间。每个度量都有一个单调、免开方的形式：欧几里得取平方，闵可夫斯基取 `p` 次方，曼哈顿则是恒等变换。这个变换在非负输入上是单调的。
有些判断只依赖排序。比如哪个点更近、某点是否落在半径内、哪个点是第 k 近的点。任何这样的判断都能在可比空间里完成，而且永远不用为开方买单。
内部的 kd 树做的正是这件事。KNN 和 DBSCAN 在低维时会自动使用它。它把每个候选距离都存在可比空间里。它用同一空间里的逐轴下界来剪枝。它只对真正要返回的那几个结果，才把可比空间的值换算回真实距离。`within`（见 6.1.2）就是这个想法露出水面的公开一角。
这条实用的经验同样适用于你自己的代码。当你是在排序或设阈值，而不是把距离报给人看时，就待在平方空间里。比较 `squared_euclidean_distance_row` 的值，对判断“哪个点更近”是正确的。而且它严格地比比较平方根更便宜。只在真实距离要离开你的循环那一刻，才调用 `.sqrt()`。
## 6.1.6. 实例：成对距离矩阵
要为你自己的最近邻逻辑建一整张成对距离矩阵，光靠这些内核就够了。这里的每个度量都保证 2 个结构性事实：矩阵是对称的，对角线是零。把每个无序对只算一次，再把值镜像到对角线另一侧，对角线就留在零。这样能把距离计算的次数减半。在这个热点双重循环里，待在平方空间中，每个元素只开一次方。如果下游只需要排序，就干脆跳过开方。
```rust
use ndarray::{Array2, array};
use rustyml::math::squared_euclidean_distance_row;
fn main() {
let data = array![[0.0, 0.0], [1.0, 0.0], [0.0, 1.0], [1.0, 1.0]];
let n = data.nrows();
// 对称且对角线为零：只填上三角，再镜像。
let mut dist = Array2::<f64>::zeros((n, n));
for i in 0..n {
for j in (i + 1)..n {
// 行按引用传入，不拷贝，每个元素只开一次方。
let d = squared_euclidean_distance_row(&data.row(i), &data.row(j)).sqrt();
dist[[i, j]] = d;
dist[[j, i]] = d;
}
}
// 对单个查询，跳过矩阵，直接扫一遍：
let query = data.row(0);
let nearest = (1..n)
.min_by(|&a, &b| {
// 在平方空间里比较，选最小值不需要开方。
let da = squared_euclidean_distance_row(&query, &data.row(a));
let db = squared_euclidean_distance_row(&query, &data.row(b));
da.total_cmp(&db)
})
.unwrap();
println!("matrix=\n{dist:?}\nnearest to row 0: {nearest}");
}
```
这个例子里真正的重点在 `min_by` 那一半。只查几个点时，一整张 `O(n^2)` 矩阵是选错了工具。做一次最近邻查找，只需在 `O(n)` 里扫一遍，从不碰开方。只有当下游算法要吃掉整张矩阵时，比如层次聚类或者 MDS 嵌入，才值得建出完整矩阵。不要为了找一个邻居就去建它。
## 6.1.7. 性能、SIMD 与并行
每个内核都是单趟运行，没有中间分配。`squared_euclidean_distance_row` 和 `manhattan_distance_row` 各自在两个输入上折叠一次 `ndarray::Zip`。`minkowski_distance_row` 做的是同样的事，只是每个元素多一次 `powf` 调用，最后再加一次 `powf(1.0 / p)` 调用。这 3 个函数都带有 `#[inline]` 属性。
每次调用的开销和维度 `d` 呈线性关系。欧几里得和曼哈顿每个元素只需一次减法，加一次乘法或一次取绝对值。两者都很便宜。闵可夫斯基每个元素要付一次超越函数 `powf` 调用，这让它明显更慢。能用 `Euclidean` 或 `Manhattan` 时就优先用它们。避免使用 `Minkowski(2.0)` 或 `Minkowski(1.0)`，它们只是用更慢的路径算出同样的数字。
这些内核里没有手写的 SIMD 代码，也没有 `f32` 路径。`Zip` 循环紧凑、无分支，闵可夫斯基除外。这类代码的形态正是优化编译器能自动向量化的那种。但源码里没有任何东西强制向量化，所以不要假设某一套具体的指令集。
单次距离调用完全是串行的，内核内部没有任何 rayon 调用。这是对的选择：一行的工作量太小，不值得为它承担线程调度的开销。并行发生在上一层，也就是调用方。`silhouette_score` 会在元素数超过一个可调阈值时，把成对扫描铺到 rayon 线程池上。KNN 提供了 `predict_parallel` 方法，DBSCAN 则会并行化它的邻域查询。
如果瓶颈出在你自己的成对矩阵循环上，就自己用 rayon 把按行的外层循环并行化。这些内核都是纯函数，且是 `Send`-safe 的，所以这样接起来很干净。关于并行何时划算、以及那些阈值怎么调的更全面讨论，见 [7.3. 性能调优与并行](../Chapter-07/7.3._性能调优与并行.md)。这个模块随附的兄弟数值原语，见 [6.2. 矩阵乘法](./6.2._矩阵乘法.md) 和 [6.3. 并行归约](./6.3._并行归约.md)。