# 2.8. DBSCAN
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）把落在稠密区域的点聚成簇，其余的点标记为噪声。和 [KMeans](./2.7._KMeans聚类.md) 不同，DBSCAN 不需要你预先给出簇的数量。它能找出任意形状的簇，而不只是圆滚滚的团块，还会明确标出离群点。作为交换，你要设置 `eps` 和 `min_samples` 这 2 个密度参数，而不是 `k`。本页讲解 RustyML 实现的密度模型、挑选 `eps` 的方法、`predict` 到底做了什么，以及 O(n^2) 算法的开销。
## 2.8.1. 密度模型：核心点、边界点与噪声点
DBSCAN 给每个训练点分配 3 种角色之一，`eps`（邻域半径）和 `min_samples`（密度阈值）这 2 个参数共同决定角色。
一个点的*邻域*，是所有落在它 `eps` 范围内的点。边界取闭区间，距离恰好等于 `eps` 的点也算邻居。RustyML 的邻域查询还会把点自身算进去，因为它到自己的距离是 0，而 0 永远 `<= eps`。这一点决定了 `min_samples` 的含义：
| 角色 | 本实现中的定义 |
|------|-----------------------------------|
| **核心点** | 邻域内至少有 `min_samples` 个点（含自身）。也就是说，至少有 `min_samples - 1` 个其他点落在 `eps` 内。 |
| **边界点** | 本身不是核心点，但落在某个核心点的 `eps` 范围内，因此加入该核心点所在的簇。 |
| **噪声点** | 既非核心点也非边界点。标记为 `-1`。 |
所以 `min_samples` 把查询点自身也算在内，这和 scikit-learn 的算法一致。如果你把“邻居”理解成只算别的点、不含自身，那就要把 `min_samples` 减去 1。当 `min_samples = 2` 时，只要 `eps` 内还有另外 1 个点，这个点就成为核心点。
簇靠密度连通形成。`fit` 从一个未访问的核心点出发，认领它，再沿着核心点的邻域做洪泛式扩散，把每个能到达的点都收进来。边界点会被收进簇里，却不会让洪泛继续蔓延，因为 `fit` 不会展开边界点的邻域。洪泛始终碰不到的点，就留在 `-1`。
由此可以得出 2 点结论。第一，`fit` 里没有任何随机数生成器，因此这里的聚类完全确定。`fit` 按行号升序处理各点，每份邻居列表也按下标排序返回，所以相同输入永远给出相同的标签和相同的簇 id。第二，当一个边界点同时落在 2 个簇的触及范围内时，哪个簇的洪泛先扩散到它，它就归哪个簇。由于 `fit` 按行号顺序处理，那就是 id 较小的那个簇。这样就以确定的方式解决了经典 DBSCAN 里的边界归属二义性，而不是把它留作未定义。
## 2.8.2. 构造与配置估计器
构造函数接收这 2 个密度参数并对它们做校验：
```rust,ignore
pub fn new(eps: f64, min_samples: usize) -> Result<Self, Error>
pub fn with_metric(self, metric: DistanceCalculationMetric) -> Result<Self, Error>
```
`new` 在 `eps` 非正或非有限、或者 `min_samples` 为 `0` 时返回 `Error::InvalidParameter`。距离度量默认为欧几里得，可以用 `with_metric` 改掉它，这个方法同样返回 `Result`，因为它要校验闵可夫斯基阶数（见 2.8.4 节）。`Default::default()` 给出 `eps = 0.5`、`min_samples = 5`、欧几里得。这些数字只是占位符，并不是适配你数据的好默认值。
| 参数 | 类型 | 含义 | 校验 |
|-----------|------|---------|------------|
| `eps` | `f64` | 邻域半径，单位取决于所用度量 | 必须为正且有限 |
| `min_samples` | `usize` | 核心点的邻域规模（含自身） | 必须 `> 0` |
| `metric` | `DistanceCalculationMetric` | 距离函数 | 闵可夫斯基 `p` 必须 `>= 1` 且有限 |
构造完成后，getter 会暴露存下来的状态：`get_epsilon`、`get_min_samples`、`get_metric`。训练完成后，还会暴露 `get_labels() -> Option<&Array1<isize>>` 和 `get_core_sample_indices() -> Option<&Array1<usize>>`。各错误变体如何对应到真实的失败，见[错误处理](../Chapter-01/1.6._错误处理.md)。
## 2.8.3. 训练并读取标签
`fit` 跑完聚类并把结果存下来。`fit_predict` 做同样的事，同时还会把标签数组返回。`get_labels` 则用来事后读取存下的标签。标签的类型是 `Array1<isize>`：簇 id 按发现顺序取 `0, 1, 2, ...`，`-1` 标记噪声。正是这个带符号的 `isize` 类型，才让噪声能和簇 id 存在同一个数组里，不需要额外的掩码。
```rust
use rustyml::machine_learning::DBSCAN;
use ndarray::Array2;
fn main() {
// 两个紧凑的点团，外加一个孤立点。
let data = Array2::from_shape_vec(
(9, 2),
vec![
0.0, 0.0, 0.1, 0.0, 0.0, 0.1, 0.1, 0.1, // 原点附近的点团 A
10.0, 10.0, 10.1, 10.0, 10.0, 10.1, 10.1, 10.1, // (10, 10) 附近的点团 B
5.0, 5.0, // 噪声：离两个点团都很远
],
)
.unwrap();
let mut dbscan = DBSCAN::new(0.5, 2).unwrap();
let labels = dbscan.fit_predict(&data).unwrap();
let n_clusters = labels.iter().filter(|&&l| l >= 0).map(|&l| l).max().map_or(0, |m| m + 1);
let n_noise = labels.iter().filter(|&&l| l == -1).count();
println!("labels = {:?}", labels);
println!("clusters = {}", n_clusters);
println!("noise pts = {}", n_noise);
// core_sample_indices 只保存达到核心点标准的行，按升序排列。
let cores = dbscan.get_core_sample_indices().unwrap();
println!("core rows = {:?}", cores);
}
```
点团 A 成为簇 `0`，因为 `fit` 最先发现它。点团 B 成为簇 `1`。孤零零落在 `(5, 5)` 的那个点留在 `-1`。`min_samples = 2`、每个点团 4 个点，因此每个点团里的点都是核心点，`core_sample_indices` 就是 `[0,1,2,3,4,5,6,7]`，噪声那一行不在其列。
```text
labels = [0, 0, 0, 0, 1, 1, 1, 1, -1], shape=[9], strides=[1], layout=CFcf (0xf), const ndim=1
clusters = 2
noise pts = 1
core rows = [0, 1, 2, 3, 4, 5, 6, 7], shape=[8], strides=[1], layout=CFcf (0xf), const ndim=1
```
`fit` 在动手之前先校验输入：零行矩阵会给出 `Error::EmptyInput`，数据里任何 `NaN` 或无穷值都会给出 `Error::NonFinite`。这体现了职责的划分：像非有限的 `eps` 这样糟糕的*超参数*，在构造时就报 `InvalidParameter`；而*数据里*糟糕的取值，则在训练时报 `NonFinite`。
## 2.8.4. 距离度量
`with_metric` 接受 `DistanceCalculationMetric` 的 3 个变体：`Euclidean`（默认，L2）、`Manhattan`（L1）和 `Minkowski(p)`（广义的 Lp 范数）。`Minkowski(2.0)` 得到的标签和 `Euclidean` 完全一样，`Minkowski(1.0)` 得到的标签和 `Manhattan` 完全一样。要用 L1 或 L2，就直接用有名字的那两个变体。把 `Minkowski` 留给真正的分数阶或更高阶。
```rust
use rustyml::machine_learning::{DBSCAN, DistanceCalculationMetric};
use ndarray::array;
fn main() {
let data = array![
[0.0, 0.0], [0.1, 0.0], [0.0, 0.1],
[5.0, 5.0], [5.1, 5.0], [5.0, 5.1],
];
let mut dbscan = DBSCAN::new(0.5, 2)
.unwrap()
.with_metric(DistanceCalculationMetric::Manhattan)
.unwrap();
let labels = dbscan.fit_predict(&data).unwrap();
println!("{:?}", labels); // 两个簇，没有噪声
}
```
构造函数会拒绝低于 `1`（包括 `0.5`）或非有限的闵可夫斯基阶数：这样的阶数会破坏三角不等式，进而破坏邻域判定。换一种度量，改变的是 `eps` 的*单位*，而不仅仅是它的含义。同一组点在曼哈顿距离下的跨度比欧几里得距离更大，因此为某个度量调好的 `eps` 换到另一个度量就不对了。每次换度量，都要重新调 `eps`。各度量的定义及其取舍见[距离度量](../Chapter-06/6.1._距离度量.md)。
## 2.8.5. 选择 eps：k 距离启发式
`eps` 是最常被调错的参数。本节给出一套具体的方法来选它，而不必靠试错。对每个点，量出它到第 k 近邻的距离。取 `k = min_samples`，并把点自身也算上，于是下标 `0` 就是距离为 `0` 的它自己。把所有这些 k 距离按升序排好，再看这条曲线。稠密簇内部的点 k 距离很小，噪声点的 k 距离很大。曲线在成簇的点上一直平缓走低，随后在开始碰到离群点时，在“拐点”处陡然上扬。拐点处的 k 距离就是个不错的 `eps` 取值：大到足以连起真正的簇，又小到能把离群点晾在外面。
这个排序步骤和一次 [KNN](./2.3._K近邻.md) 查询返回的结果一致。你可以直接用公开的度量调度器把这些 k 距离算出来：
```rust
use rustyml::machine_learning::DistanceCalculationMetric;
use ndarray::array;
fn main() {
// 5 个点组成的密集簇，外加 2 个散落的离群点。
let data = array![
[0.0, 0.0], [0.2, 0.1], [0.1, 0.2], [0.3, 0.0], [0.0, 0.3],
[4.0, 4.0], [8.0, 1.0],
];
let metric = DistanceCalculationMetric::Euclidean;
let min_samples = 3usize; // k 距离图所用的 k
let n = data.nrows();
// 每个点的 k 距离：到它第 k 近邻的距离（含自身）。
let mut k_dists: Vec<f64> = (0..n)
.map(|i| {
let mut d: Vec<f64> = (0..n)
.map(|j| metric.distance(data.row(i), data.row(j)))
.collect();
d.sort_by(|a, b| a.partial_cmp(b).unwrap());
d[min_samples - 1] // 下标 0 是自身（距离 0）
})
.collect();
k_dists.sort_by(|a, b| a.partial_cmp(b).unwrap());
// 从左到右看这条曲线，末尾陡然上扬处就是拐点。
println!("sorted k-distances: {:?}", k_dists);
}
```
打印出来的曲线里那段平缓的前缀，对应的就是成簇的点。在曲线开始上扬的地方挑 `eps`。`min_samples` 则留给密度下限：常见的起点是 `2 * n_features`。数据噪声大就调高它，因为要求的邻居越多，噪声剔除就越严格。数据干净、维度又低，就往 `n_features + 1` 调低。因为 RustyML 把点自身也算进去，`min_samples = 1` 会让*每个*点都成为核心点，于是产出 0 个噪声点，这多半不是你想要的结果。
## 2.8.6. predict 到底做了什么，以及它为何不是经典 DBSCAN
教科书里的 DBSCAN 没有面向新点的 `predict` 方法，这个缺失是根本性的，而不是疏漏。DBSCAN 里的簇归属是*直推式*（transductive）的：一个点的标签取决于整个邻域的密度。往数据里加入一个新点，可能把它变成核心点，也可能把两个原本分开的簇合并成一个，或者挪动某条边界的落点。想给新点正确地打上标签，就少不了在合并后的整个集合上重新做一次密度分析。
RustyML 依然提供了 `predict` 方法。它做的是一件比重新做密度分析更窄、更省的事。本节说清楚它到底做了什么：
```rust
use rustyml::machine_learning::DBSCAN;
use ndarray::array;
fn main() {
let train = array![
[0.0, 0.0], [0.1, 0.0], [0.0, 0.1], [0.1, 0.1],
[10.0, 10.0], [10.1, 10.0], [10.0, 10.1], [10.1, 10.1],
];
let mut dbscan = DBSCAN::new(0.5, 2).unwrap();
dbscan.fit(&train).unwrap();
// 把每个新点归到它最近核心点所属的簇，前提是落在 eps 之内。
let queries = array![
[0.05, 0.05], // 位于点团 A 内 -> 0
[10.05, 10.05], // 位于点团 B 内 -> 1
[5.0, 5.0], // 远离所有核心点 -> 噪声 (-1)
];
let preds = dbscan.predict(&queries).unwrap();
println!("{:?}", preds); // preds 依次是 [0, 1, -1]，对应每个查询点。
}
```
`predict` 会为每个查询点找到它最近的核心点。它只在 `fit` 期间存下的核心点里搜索，而不是整个训练集。如果查询点落在 `eps` 之内，就返回那个核心点的簇标签，否则返回 `-1`。`predict` 只挑最近的那一个核心点，不会去检查 `eps` 内的每一个核心点。`eps` 这道闸取闭区间。`predict` 从不创建新簇，从不把查询点提拔为核心点，也从不重新跑一遍密度洪泛。所以 `predict(x)` 的结果*并不等于*把 `x` 加进训练数据后再调用一次 `fit`。把 `predict` 当成一种快速、近似的手段，用来把留出的点分派到 `fit` 已经找到的那些簇里。如果想要真正的 DBSCAN 语义，就在扩大后的数据集上重新调用 `fit`。
在 `fit` 之前调用 `predict` 会得到 `Error::NotFitted`。特征数不匹配会得到 `Error::DimensionMismatch`。查询里出现非有限值会得到 `Error::NonFinite`。空输入则返回空数组。
## 2.8.7. KMeans 失手的双环
选 DBSCAN 而不是 KMeans，主要理由在于形状。KMeans 用直线边界围着 `k` 个质心切分空间，因此只能划出凸的、大致圆形的区域。DBSCAN 顺着密度走，能勾勒任意形状。两个同心环把这种差别体现得很清楚：两环绕着共同的圆心并非线性可分，KMeans 会一刀直接切穿两者，而 DBSCAN 会把每个环当作一条连通的链走下来。
```rust
use rustyml::machine_learning::{DBSCAN, KMeans};
use ndarray::Array2;
fn main() {
// 造 2 个同心环：内环半径 1，外环半径 4。
let mut coords: Vec<f64> = Vec::new();
let inner = 12usize;
for k in 0..inner {
let t = k as f64 / inner as f64 * std::f64::consts::TAU;
coords.push(t.cos());
coords.push(t.sin());
}
let outer = 28usize;
for k in 0..outer {
let t = k as f64 / outer as f64 * std::f64::consts::TAU;
coords.push(4.0 * t.cos());
coords.push(4.0 * t.sin());
}
let data = Array2::from_shape_vec((inner + outer, 2), coords).unwrap();
// eps 覆盖得住环上相邻点的间距，却覆盖不了两环之间 >= 3 个单位的空隙。
let mut dbscan = DBSCAN::new(1.2, 2).unwrap();
let db = dbscan.fit_predict(&data).unwrap();
let db_clusters = db.iter().filter(|&&l| l >= 0).map(|&l| l).max().map_or(0, |m| m + 1);
let db_noise = db.iter().filter(|&&l| l == -1).count();
// KMeans，k = 2（固定种子以保证可复现）。
let mut km = KMeans::new(2, 100, 1e-4).unwrap().with_random_state(0);
let km_labels = km.fit_predict(&data).unwrap();
// km_inner0 和 km_outer0 统计 KMeans 簇 0 里内环点和外环点各有多少个。
let km_inner0 = (0..inner).filter(|&i| km_labels[i] == 0).count();
let km_outer0 = (inner..inner + outer).filter(|&i| km_labels[i] == 0).count();
println!("DBSCAN: {} clusters, {} noise", db_clusters, db_noise);
println!("KMeans cluster 0: {} inner-ring + {} outer-ring points", km_inner0, km_outer0);
}
```
DBSCAN 把这 2 个环完整还原：找到 2 个簇、0 个噪声点，内环是一个标签，外环是另一个。KMeans 用一条过原点的直线把平面劈开，因此它的 2 个簇都混着内环和外环的点。KMeans 根本无法表示一个环。
```text
DBSCAN: 2 clusters, 0 noise
KMeans cluster 0: 6 inner-ring + 14 outer-ring points
```
想用真实标签或内在指标给这类结果打分，见[聚类指标](../Chapter-05/5.3._聚类指标.md)。
## 2.8.8. 开销、索引与并行
朴素的 DBSCAN 运行时间是 O(n^2)：每个点都要跑一次区域查询，而暴力的区域查询要扫过全部 n 个点。RustyML 用 kd 树压低这个常数。`fit` 期间，RustyML 会在数据上建一棵 kd 树，把每次区域查询的平均耗时压到大约 O(log n)。这只在数据至多有 8 个特征时才成立（`DBSCAN_KD_TREE_MAX_DIMS`）。维度一旦超过 8，kd 树就剪不好枝了，原因是维度灾难：几乎每个点看起来都离其他点“很远”。于是 `fit` 会退回暴力扫描。这条路径上聚类结果依旧正确，只是更慢。在使用高维数据之前，先用 [PCA](./2.10._主成分分析.md) 或 [t-SNE](./2.12._t-SNE.md) 做降维。这样既能给索引提速，也是因为不管用什么索引，欧几里得邻域在高维里都会失去意义。
暴力区域查询会借助 [rayon](https://docs.rs/rayon) 在邻居间并行。触发条件是扫描工作量（`n_samples * n_features`）越过一道标定好的元素闸（默认 `262_144`）。簇扩张那个循环本身是串行的，因为它是一次洪泛填充。所以并行帮到的是单次区域扫描，而不是整体的控制流。`predict` 会在 `n_queries * n_core_points * n_features` 越过同一道闸时按查询点并行。你可以通过 `crate::tuning` 门面调节这些闸，无需重新编译。怎么调见[性能调优与并行](../Chapter-07/7.3._性能调优与并行.md)，闸的机制见[并行归约](../Chapter-06/6.3._并行归约.md)。还有一道护栏：如果某个病态数据集产出了 `isize::MAX` 个簇，`fit` 会返回 `Error::Computation`，而不是让标签计数器溢出。
DBSCAN 换给你的是任意形状的簇、自动的离群点检测，以及无需去猜的 `k`。作为代价，它在最坏情况下要花二次方时间。kd 树能在低维里降低这个开销，却无法把它去掉。当各簇密度不同时，DBSCAN 还对 `eps` 很敏感，因为单一的全局 `eps` 没法同时贴合一个稠密簇和一个稀疏簇。
## 2.8.9. 持久化
训练好的 `DBSCAN` 用 `save_to_path` 和 `load_from_path` 序列化。这两个方法都使用紧凑的 [postcard](https://docs.rs/postcard) 二进制格式。保存下来的数据既包含超参数，也包含 `predict` 需要的训练态：存下的核心点及其标签。重新加载的模型无需再见到原始训练集，就能给出同样的预测。
```rust
use rustyml::machine_learning::DBSCAN;
use ndarray::array;
fn main() {
let data = array![
[0.0, 0.0], [0.1, 0.0], [0.0, 0.1], [0.1, 0.1],
[10.0, 10.0], [10.1, 10.0], [10.0, 10.1], [10.1, 10.1],
];
let mut dbscan = DBSCAN::new(0.5, 2).unwrap();
dbscan.fit(&data).unwrap();
let path = "dbscan_model.bin";
dbscan.save_to_path(path).unwrap();
let loaded = DBSCAN::load_from_path(path).unwrap();
let preds = loaded.predict(&array![[0.05, 0.05], [10.05, 10.05], [5.0, 5.0]]).unwrap();
println!("{:?}", preds); // preds 仍是 [0, 1, -1]，和 fit 给出的结果一致。
std::fs::remove_file(path).unwrap();
}
```
关于格式细节、版本兼容的注意事项，以及持久化如何与 crate 其余部分交互，见[深入模型持久化](../Chapter-07/7.2._深入模型持久化.md)。