2.8. DBSCANDBSCANDensity-Based Spatial Clustering of Applications with Noise把落在稠密区域的点聚成簇其余的点标记为噪声。和 KMeans 不同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 个密度参数并对它们做校验pub fn new(eps: f64, min_samples: usize) - ResultSelf, Error pub fn with_metric(self, metric: DistanceCalculationMetric) - ResultSelf, Errornew在eps非正或非有限、或者min_samples为0时返回Error::InvalidParameter。距离度量默认为欧几里得可以用with_metric改掉它这个方法同样返回Result因为它要校验闵可夫斯基阶数见 2.8.4 节。Default::default()给出eps 0.5、min_samples 5、欧几里得。这些数字只是占位符并不是适配你数据的好默认值。参数类型含义校验epsf64邻域半径单位取决于所用度量必须为正且有限min_samplesusize核心点的邻域规模含自身必须 0metricDistanceCalculationMetric距离函数闵可夫斯基p必须 1且有限构造完成后getter 会暴露存下来的状态get_epsilon、get_min_samples、get_metric。训练完成后还会暴露get_labels() - OptionArray1isize和get_core_sample_indices() - OptionArray1usize。各错误变体如何对应到真实的失败见错误处理。2.8.3. 训练并读取标签fit跑完聚类并把结果存下来。fit_predict做同样的事同时还会把标签数组返回。get_labels则用来事后读取存下的标签。标签的类型是Array1isize簇 id 按发现顺序取0, 1, 2, ...-1标记噪声。正是这个带符号的isize类型才让噪声能和簇 id 存在同一个数组里不需要额外的掩码。userustyml::machine_learning::DBSCAN;usendarray::Array2;fnmain(){// 两个紧凑的点团外加一个孤立点。letdataArray2::from_shape_vec((9,2),vec![0.0,0.0,0.1,0.0,0.0,0.1,0.1,0.1,// 原点附近的点团 A10.0,10.0,10.1,10.0,10.0,10.1,10.1,10.1,// (10, 10) 附近的点团 B5.0,5.0,// 噪声离两个点团都很远],).unwrap();letmutdbscanDBSCAN::new(0.5,2).unwrap();letlabelsdbscan.fit_predict(data).unwrap();letn_clusterslabels.iter().filter(|l|l0).map(|l|l).max().map_or(0,|m|m1);letn_noiselabels.iter().filter(|l|l-1).count();println!(labels {:?},labels);println!(clusters {},n_clusters);println!(noise pts {},n_noise);// core_sample_indices 只保存达到核心点标准的行按升序排列。letcoresdbscan.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]噪声那一行不在其列。labels [0, 0, 0, 0, 1, 1, 1, 1, -1], shape[9], strides[1], layoutCFcf (0xf), const ndim1 clusters 2 noise pts 1 core rows [0, 1, 2, 3, 4, 5, 6, 7], shape[8], strides[1], layoutCFcf (0xf), const ndim1fit在动手之前先校验输入零行矩阵会给出Error::EmptyInput数据里任何NaN或无穷值都会给出Error::NonFinite。这体现了职责的划分像非有限的eps这样糟糕的超参数在构造时就报InvalidParameter而数据里糟糕的取值则在训练时报NonFinite。2.8.4. 距离度量with_metric接受DistanceCalculationMetric的 3 个变体Euclidean默认L2、ManhattanL1和Minkowski(p)广义的 Lp 范数。Minkowski(2.0)得到的标签和Euclidean完全一样Minkowski(1.0)得到的标签和Manhattan完全一样。要用 L1 或 L2就直接用有名字的那两个变体。把Minkowski留给真正的分数阶或更高阶。userustyml::machine_learning::{DBSCAN,DistanceCalculationMetric};usendarray::array;fnmain(){letdataarray![[0.0,0.0],[0.1,0.0],[0.0,0.1],[5.0,5.0],[5.1,5.0],[5.0,5.1],];letmutdbscanDBSCAN::new(0.5,2).unwrap().with_metric(DistanceCalculationMetric::Manhattan).unwrap();letlabelsdbscan.fit_predict(data).unwrap();println!({:?},labels);// 两个簇没有噪声}构造函数会拒绝低于1包括0.5或非有限的闵可夫斯基阶数这样的阶数会破坏三角不等式进而破坏邻域判定。换一种度量改变的是eps的单位而不仅仅是它的含义。同一组点在曼哈顿距离下的跨度比欧几里得距离更大因此为某个度量调好的eps换到另一个度量就不对了。每次换度量都要重新调eps。各度量的定义及其取舍见距离度量。2.8.5. 选择 epsk 距离启发式eps是最常被调错的参数。本节给出一套具体的方法来选它而不必靠试错。对每个点量出它到第 k 近邻的距离。取k min_samples并把点自身也算上于是下标0就是距离为0的它自己。把所有这些 k 距离按升序排好再看这条曲线。稠密簇内部的点 k 距离很小噪声点的 k 距离很大。曲线在成簇的点上一直平缓走低随后在开始碰到离群点时在“拐点”处陡然上扬。拐点处的 k 距离就是个不错的eps取值大到足以连起真正的簇又小到能把离群点晾在外面。这个排序步骤和一次 KNN 查询返回的结果一致。你可以直接用公开的度量调度器把这些 k 距离算出来userustyml::machine_learning::DistanceCalculationMetric;usendarray::array;fnmain(){// 5 个点组成的密集簇外加 2 个散落的离群点。letdataarray![[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],];letmetricDistanceCalculationMetric::Euclidean;letmin_samples3usize;// k 距离图所用的 kletndata.nrows();// 每个点的 k 距离到它第 k 近邻的距离含自身。letmutk_dists:Vecf64(0..n).map(|i|{letmutd:Vecf64(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方法。它做的是一件比重新做密度分析更窄、更省的事。本节说清楚它到底做了什么userustyml::machine_learning::DBSCAN;usendarray::array;fnmain(){lettrainarray![[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],];letmutdbscanDBSCAN::new(0.5,2).unwrap();dbscan.fit(train).unwrap();// 把每个新点归到它最近核心点所属的簇前提是落在 eps 之内。letqueriesarray![[0.05,0.05],// 位于点团 A 内 - 0[10.05,10.05],// 位于点团 B 内 - 1[5.0,5.0],// 远离所有核心点 - 噪声 (-1)];letpredsdbscan.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 会把每个环当作一条连通的链走下来。userustyml::machine_learning::{DBSCAN,KMeans};usendarray::Array2;fnmain(){// 造 2 个同心环内环半径 1外环半径 4。letmutcoords:Vecf64Vec::new();letinner12usize;forkin0..inner{lettkasf64/innerasf64*std::f64::consts::TAU;coords.push(t.cos());coords.push(t.sin());}letouter28usize;forkin0..outer{lettkasf64/outerasf64*std::f64::consts::TAU;coords.push(4.0*t.cos());coords.push(4.0*t.sin());}letdataArray2::from_shape_vec((innerouter,2),coords).unwrap();// eps 覆盖得住环上相邻点的间距却覆盖不了两环之间 3 个单位的空隙。letmutdbscanDBSCAN::new(1.2,2).unwrap();letdbdbscan.fit_predict(data).unwrap();letdb_clustersdb.iter().filter(|l|l0).map(|l|l).max().map_or(0,|m|m1);letdb_noisedb.iter().filter(|l|l-1).count();// KMeansk 2固定种子以保证可复现。letmutkmKMeans::new(2,100,1e-4).unwrap().with_random_state(0);letkm_labelskm.fit_predict(data).unwrap();// km_inner0 和 km_outer0 统计 KMeans 簇 0 里内环点和外环点各有多少个。letkm_inner0(0..inner).filter(|i|km_labels[i]0).count();letkm_outer0(inner..innerouter).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 根本无法表示一个环。DBSCAN: 2 clusters, 0 noise KMeans cluster 0: 6 inner-ring 14 outer-ring points想用真实标签或内在指标给这类结果打分见聚类指标。2.8.8. 开销、索引与并行朴素的 DBSCAN 运行时间是 O(n^2)每个点都要跑一次区域查询而暴力的区域查询要扫过全部 n 个点。RustyML 用 kd 树压低这个常数。fit期间RustyML 会在数据上建一棵 kd 树把每次区域查询的平均耗时压到大约 O(log n)。这只在数据至多有 8 个特征时才成立DBSCAN_KD_TREE_MAX_DIMS。维度一旦超过 8kd 树就剪不好枝了原因是维度灾难几乎每个点看起来都离其他点“很远”。于是fit会退回暴力扫描。这条路径上聚类结果依旧正确只是更慢。在使用高维数据之前先用 PCA 或 t-SNE 做降维。这样既能给索引提速也是因为不管用什么索引欧几里得邻域在高维里都会失去意义。暴力区域查询会借助 rayon 在邻居间并行。触发条件是扫描工作量n_samples * n_features越过一道标定好的元素闸默认262_144。簇扩张那个循环本身是串行的因为它是一次洪泛填充。所以并行帮到的是单次区域扫描而不是整体的控制流。predict会在n_queries * n_core_points * n_features越过同一道闸时按查询点并行。你可以通过crate::tuning门面调节这些闸无需重新编译。怎么调见性能调优与并行闸的机制见并行归约。还有一道护栏如果某个病态数据集产出了isize::MAX个簇fit会返回Error::Computation而不是让标签计数器溢出。DBSCAN 换给你的是任意形状的簇、自动的离群点检测以及无需去猜的k。作为代价它在最坏情况下要花二次方时间。kd 树能在低维里降低这个开销却无法把它去掉。当各簇密度不同时DBSCAN 还对eps很敏感因为单一的全局eps没法同时贴合一个稠密簇和一个稀疏簇。2.8.9. 持久化训练好的DBSCAN用save_to_path和load_from_path序列化。这两个方法都使用紧凑的 postcard 二进制格式。保存下来的数据既包含超参数也包含predict需要的训练态存下的核心点及其标签。重新加载的模型无需再见到原始训练集就能给出同样的预测。userustyml::machine_learning::DBSCAN;usendarray::array;fnmain(){letdataarray![[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],];letmutdbscanDBSCAN::new(0.5,2).unwrap();dbscan.fit(data).unwrap();letpathdbscan_model.bin;dbscan.save_to_path(path).unwrap();letloadedDBSCAN::load_from_path(path).unwrap();letpredsloaded.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 其余部分交互见深入模型持久化。