【RustyML入门】2.3. K近邻(KNN)

2.3. K近邻2.3.1. 惰性学习开销落在哪里KNN 是这个 crate 里最纯粹的惰性学习器。它的fit方法几乎不做任何学习校验输入拷贝训练特征矩阵把标签编码成紧凑的usize索引让投票变成一次廉价的整数运算。和逻辑回归或决策树不同KNN 不会把训练数据压进权重或一棵划分树里。真正的工作全部由predict完成。这种推迟是有实打实代价的。既然没有训练好的模型可查给一个查询点分类就得量它到每一个训练样本的距离留下最小的 k 个。走暴力路径时对n_test个查询、n_train行、d维的训练数据距离阶段的开销是O(n_train * n_test * d)。每个查询还需要一次O(n_train)的部分选择把最近的 k 个值挑出来。这一步用的是通过select_nth_unstable做的 Quickselect而不是整整O(n_train log n_train)的排序。内存开销是O(n_train * d)因为整个训练集在模型的整个生命周期里都留在内存中。训练集就是模型本身。你接受这个代价换来的是一个没有训练阶段、对决策边界形状不作任何假设的非参数分类器。由此直接引出两个后果。其一预测延迟随训练集规模增长几千行时飞快的 KNN到了几十万行就可能成为瓶颈。其二准确率在查询时完全由几何关系决定这也是本页后文要讲的距离度量和特征缩放在这里比在几乎任何其他模型里都更要紧的原因。2.3.2. 构造一个分类器构造函数只接收一个k。其余所有配置都有默认值通过链式的 builder 方法来设置// 核心接口来自 src/machine_learning/neighbors/knn.rspubfnnew(k:usize)-ResultSelf,Error;// k 0 时返回 Errpubfnwith_weighting_strategy(self,s:WeightingStrategy)-Self;pubfnwith_metric(self,m:DistanceCalculationMetric)-ResultSelf,Error;// 校验闵可夫斯基的 ppubfnfitS1,S2(mutself,x:ArrayBaseS1,Ix2,y:ArrayBaseS2,Ix1)-ResultmutSelf,Error;pubfnpredictS(self,x:ArrayBaseS,Ix2)-ResultArray1T,Error;pubfnpredict_parallelS(self,x:ArrayBaseS,Ix2)-ResultArray1T,Error;// T: Sync Sendpubfnfit_predictS1,S2(mutself,x:...,y:...)-ResultArray1T,Error;k 0时new返回Error::InvalidParameter。这是构造过程中唯一一个所有调用者都可能碰到的失败点。with_metric也可能失败因为它要校验闵可夫斯基阶下一节会讲到。with_weighting_strategy不会失败直接返回Self。因此一条写全的 builder 链最终会落在 metric 调用的?或.unwrap()上这也和整个测试套件采用的顺序一致。给模型定参数的两个枚举参数类型变体默认值加权方式WeightingStrategyUniform、DistanceUniform距离度量DistanceCalculationMetricEuclidean、Manhattan、Minkowski(f64)EuclideanKNN::T::default()给你k 5、Uniform加权和Euclidean距离这和调用new(5)之后什么都不改得到的默认值完全一样。想读回已保存的配置用get_k、get_weighting_strategy、get_metric和get_x_train。get_x_train返回OptionArray2f64在你调用fit之前是None。标签类型T是完全泛型的。任何满足Clone Hash Eq的类型都可以用整数类别码、String标签或者你自己的枚举都行。fit按首次出现的顺序把见到的标签编码成索引并存下反向映射。predict再把索引解码回原始的T。喂进去Array1String出来的也是Array1String。KNN 只是一个分类器crate 里没有 KNN 回归器。如果需要按邻居取平均的回归得自己在第 6.1 节的距离原语之上搭一个。下面是一个完整的例子顺序和并行两个入口都用上usendarray::array;userustyml::machine_learning::{DistanceCalculationMetric,KNN,WeightingStrategy};fnmain(){letx_trainarray![[1.0,2.0],[2.0,3.0],[3.0,4.0],[6.0,6.0],[7.0,7.0],[8.0,8.0],];lety_trainarray![0,0,0,1,1,1];letmutknnKNN::new(3).unwrap().with_weighting_strategy(WeightingStrategy::Uniform).with_metric(DistanceCalculationMetric::Euclidean).unwrap();knn.fit(x_train,y_train).unwrap();letx_testarray![[1.5,2.5],[7.5,7.0]];letseqknn.predict(x_test).unwrap();letparknn.predict_parallel(x_test).unwrap();assert_eq!(seq,par);// 确定性的两条路径结果完全一致println!(k {},knn.get_k());println!(predictions: {:?},seq);}fit会拦下那些原本会在预测时以 panic 形式冒出来的错误。零行的x返回Error::EmptyInput。x里含 NaN 或无穷时返回Error::NonFinite。y.len()和x.nrows()不一致时返回Error::DimensionMismatch。训练样本数少于k时返回Error::InvalidInput比如你没法从 3 个点里要 5 个邻居。predict和predict_parallel在fit之前被调用时返回Error::NotFitted此外还会返回EmptyInput、特征数不对时的DimensionMismatch以及查询矩阵里有 NaN 或无穷值时的NonFinite。完整的Error枚举见错误处理。fit_predict先 fit再在同一份训练矩阵上 predict。k 1时它会原样返回训练标签因为每个点的最近邻就是它自己距离为零。这让fit_predict适合用作完整性检查但不适合用来估计准确率。想要真正的泛化能力估计用训练集与测试集划分留出一部分数据再用分类指标打分。2.3.3. 距离度量与闵可夫斯基阶距离度量决定了什么才算“最近”。RustyML 用一个贯穿全库共用的枚举暴露了 3 种度量。EuclideanL2是走直线的默认选项。ManhattanL1把各坐标差的绝对值加总。当特征是量纲各异的独立轴或者你想对某个离群坐标保持稳健时就用Manhattan。Minkowski(p)把两者一并推广p 1精确退化为 Manhattanp 2精确退化为 Euclidean。测试套件在同一份数据上断言了这两个等式。介于其间或更大的p则对单位球的形状做内插和外推。with_metric会校验闵可夫斯基阶p 1或p非有限时返回Error::InvalidParameter。这是一个实打实的约束不是风格上的洁癖。阶小于 1 会破坏三角不等式结果就不再是一个合法的度量。这样的阶还会让本页后文提到的 kd-tree 索引的剪枝逻辑失效。裸的距离函数minkowski_distance_row在p 1时会直接 panic。走with_metric这条路能把这个 panic 转成一个你可以处理的、可恢复的Err。Minkowski(2.0)合法数值上和Euclidean完全相同。想要 L2 时优先用Euclidean变体。Euclidean能走一条矩阵乘法的快速路径2.3.7 节会讲通用的闵可夫斯基代码没有这条路。usendarray::array;userustyml::machine_learning::{DistanceCalculationMetric,KNN,WeightingStrategy};fnmain(){letx_trainarray![[3.0,0.0],[0.0,4.0]];lety_trainarray![0,1];letmutknnKNN::new(1).unwrap().with_weighting_strategy(WeightingStrategy::Uniform).with_metric(DistanceCalculationMetric::Minkowski(3.0)).unwrap();knn.fit(x_train,y_train).unwrap();// L3 下dist((0,3),(3,0)) 54^(1/3) ~ 3.78 dist((0,3),(0,4)) 1letx_testarray![[0.0,3.0]];println!({:?},knn.predict(x_test).unwrap());// 最近的是 (0,4) - class 1}第 6.1 节 距离度量更深入地讲解了这套度量抽象包括让空间索引省掉最后一步开方的“可比距离”技巧。2.3.4. 加权策略与平局打破KNN 找到 k 个邻居之后WeightingStrategy决定它们的标签如何汇成一个预测。Uniform是朴素的多数投票k 个邻居每人给自己的类别投一票票数最多的类别胜出。Distance给每个邻居按1.0 / distance加权于是距离近一半的邻居分量重一倍。当k大到邻居集会伸进真正不相似的点里时就该用距离加权远处的点仍然投票但影响力会衰减。距离加权还能降低结果对k具体取值的敏感度。距离加权有一个实现里显式处理的边界情况查询点正好和某个训练点重合时距离为零而1.0 / 0.0是无穷。为了避免这一点代码会先检查有没有精确匹配。只要 k 个邻居里有任何一个距离恰为0.0就只让这些精确匹配的邻居按票数投票KNN 会忽略其余的邻居。这让一次精确命中表现得像一次查表而这几乎总是你想要的结果。usendarray::array;userustyml::machine_learning::{DistanceCalculationMetric,KNN,WeightingStrategy};fnmain(){letx_trainarray![[0.0,0.0],[10.0,0.0]];lety_trainarray![0,1];letmutknnKNN::new(2).unwrap().with_weighting_strategy(WeightingStrategy::Distance).with_metric(DistanceCalculationMetric::Euclidean).unwrap();knn.fit(x_train,y_train).unwrap();// 两个点始终都在 k2 的邻居集里更近的那个赢下加权投票。letx_testarray![[1.0,0.0],[9.0,0.0]];println!(weighted: {:?},knn.predict(x_test).unwrap());// [0, 1]// 精确匹配短路了 1/0 的问题按票数投票而非权重。letx_exactarray![[0.0,0.0]];println!(exact: {:?},knn.predict(x_exact).unwrap());// [0]}RustyML 用一条有意为之、写进文档的规则来打破平局而不是随便挑一个。当Uniform下两个类别票数相等或者Distance下两个类别的加权和相等时就出现了平局。胜出的是编码索引最小的那个类别。这个索引不是最小的标签值而是fit第一次见到每个标签时的顺序。举例来说如果你的训练目标里标签7先于标签3出现那么7编码为索引 0平局时会压过3。平局的打破是确定且可复现的但具体结果取决于训练行的顺序重排你的数据有可能翻转一个平局的预测。也正是这份确定性让predict和predict_parallel能保证结果完全一致。2.3.5. 如何选 kk是最能左右行为的那个设置它就是一个直接的偏差-方差旋钮。k小往极端了说是k 1会给出低偏差、高方差的分类器决策边界紧贴数据把每一道褶皱都跟出来包括标错的点和噪声。k大则在更宽的邻域上取平均这会降低方差、抬高偏差。把k推得足够大模型就会漂向永远预测全局最常见的类别进而开始抹平那些小而真实的少数类区域。常见的起点是取接近训练集规模平方根的k再对着一份验证划分去调。没有什么能替代实测。“二分类用奇数k”这条经典建议说的就是平局问题。RustyML 的平局打破是确定性的所以偶数k永远不会报错五五开的情况按首次出现的顺序裁决但这种裁决可能显得随意还取决于你数据的顺序。奇数k能让二分类的投票根本落不到平局上。距离加权也在一定程度上缓解了这个问题因为实数权重的加权和恰好相等的情况很少见。另外别忘了 2.3.2 节那条硬性下限fit会拒绝任何大于训练样本数的k。下面这个例子把方差讲实往 class-0 区域里放一个标错的点再把一个查询点放到它紧挨着的位置。k 1时噪声胜出k 3和k 5时周围真正的 class-0 点会把它的票数压过去usendarray::array;userustyml::machine_learning::{DistanceCalculationMetric,KNN,WeightingStrategy};fnmain(){// 两个干净的簇外加一个标错的点在 (2.5, 0)它落在// class-0 区域内却带着 class-1 的标签。letx_trainarray![[0.0,0.0],[1.0,0.0],[2.0,0.0],[3.0,0.0],// class 0[10.0,0.0],[11.0,0.0],[12.0,0.0],[13.0,0.0],// class 1[2.5,0.0],// 噪声class 1];lety_trainarray![0,0,0,0,1,1,1,1,1];letx_testarray![[2.4,0.0]];// 紧挨着那个噪声点forkin[1usize,3,5]{letmutknnKNN::new(k).unwrap().with_weighting_strategy(WeightingStrategy::Uniform).with_metric(DistanceCalculationMetric::Euclidean).unwrap();knn.fit(x_train,y_train).unwrap();letpredknn.predict(x_test).unwrap();println!(k {k}: prediction {},pred[0]);}}随着k增大预测从噪声标签翻转到正确标签k 1: prediction 1 k 3: prediction 0 k 5: prediction 0k 1时对单个点的这种敏感正是高方差的失效模式。增大k就是拿它换一条更平滑、偏差更高的边界。2.3.6. 特征缩放不是可选项这个错误造成的问题比其他任何错误都多所以单独开一节来讲。KNN 按原始距离给邻居排序而这里的每一种度量都是把各坐标的差累加起来。假设一个特征取值在千级、另一个在[0, 1]之间大量程的特征就会主导距离小量程的特征则形同隐身不管真正携带标签信息的是哪一个。线性模型还能给大尺度特征学一个小系数来补偿KNN 却没有任何系数可用。你必须在调用fit之前自己把特征缩放好。下面的例子把标签完全编码在一个小量程的列里一个大量程的列则毫无信息量。用原始特征时大量程的列决定了最近邻预测是错的。用训练集逐列的均值和标准差做标准化后同时应用到训练集和查询点有信息量的那一列终于站上了同一起跑线预测就对了usendarray::{array,Axis};userustyml::machine_learning::KNN;fnmain(){// 第 0 列取值在千级没有信息量第 1 列取值在 {0, 10}携带标签。letx_trainarray![[1000.0,0.0],// class 0[3000.0,0.0],// class 0[1050.0,10.0],// class 1[3050.0,10.0],// class 1];lety_trainarray![0,0,1,1];// 第 1 列 9.0 指向 class 1第 0 列 1010.0 最接近某个 class-0 的行。letx_testarray![[1010.0,9.0]];letmutrawKNN::new(1).unwrap();raw.fit(x_train,y_train).unwrap();letraw_predraw.predict(x_test).unwrap();// 用在训练集上算出的统计量做标准化训练集和查询点都用它。letmeanx_train.mean_axis(Axis(0)).unwrap();letstdx_train.std_axis(Axis(0),0.0);letx_train_s(x_train-mean)/std;letx_test_s(x_test-mean)/std;letmutscaledKNN::new(1).unwrap();scaled.fit(x_train_s,y_train).unwrap();letscaled_predscaled.predict(x_test_s).unwrap();println!(raw features: {:?},raw_pred);// 被第 0 列主导 - [0]println!(standardized: {:?},scaled_pred);// 尊重第 1 列 - [1]}这个例子手写缩放是为了保持自成一体但统计上做法是对的均值和标准差只来自训练数据再应用到查询点上代码从不在测试集上重新估计它们。在真实的流水线里请用 crate 的standardize辅助函数或normalize而不是自己手写。在训练集上拟合出变换再把同一个变换应用到新数据上。在测试集上重新拟合会泄露信息。缩放到零均值、单位方差是常规选择当你需要把特征约束到一个固定区间时min-max 归一化是另一个选项。2.3.7. 顺序预测与并行预测、kd-tree以及 Euclidean 快速路径RustyML 给了你 2 个预测入口。predict是顺序执行的对任何标签类型都可用。predict_parallel把逐查询的工作摊到一个 Rayon 线程池上大批量查询时该用它代价是要求T: Sync Send。两者都会在查询开始之前单线程地一次性把要共享的索引建好predict_parallel之后再按测试行并行。平局的打破是确定性的所以两条路径返回的标签数组逐位相同。测试套件在Uniform、Distance和大k的各种配置下都检验了这一点。你可以先用predict来开发为了吞吐量再切到predict_parallel结果不会有任何变化。底层的搜索会走 2 条路径之一。在低维情况下最多 8 个特征predict会在首次使用时对训练数据建一棵 kd-tree 并缓存下来。kd-tree 能给出平均情况下胜过逐行扫描的邻居查找。超过 8 个特征这棵树就没法有效剪枝了这就是维度灾难几乎每个点和其他任何点都大致等距。超过这个界限代码就会退回到暴力扫描2.3.1 节那个完整的O(n_train * n_test * d)开销就会压上来。这个 8 特征的天花板来自对单一数据形态的标定不是什么普适定律。数据成簇的程度和数据集大小都会挪动实际的交叉点。它仍然是当前实现所采用的那个固定阈值。暴力路径下的 Euclidean 情形有一项专门的优化。欧几里得距离的平方展开成||x||^2 ||t||^2 - 2 * x . t剩下唯一需要逐对计算的项就是点积x . t而这是一次矩阵乘法。RustyML 一次性预算好训练行的平方范数在所有查询间共享再通过 gemmkit 矩阵乘法后端算出交叉项。这个后端会对计算分块让大训练集也能保持缓存常驻。它还会依据训练矩阵是否还装得进共享的 L3 缓存在“逐行 GEMV 群”和“分块 GEMM”之间切换。Manhattan 和 Minkowski 没有这种代数捷径只能退回到朴素的逐对度量扫描这也是想要 L2 时优先选Euclidean变体的又一个理由。kd-tree 是惰性重建的每次你再调用fit时 KNN 都会把它丢弃。因此一个重新拟合过的模型绝不会给出过期的邻居。关于并行触发门槛和调优的更多内容见性能调优与并行。2.3.8. 持久化当T满足Serialize Deserialize时i32和String都满足KNNT就能用save_to_path和load_from_path序列化。不管你选什么文件扩展名持久化写出的都是紧凑的 postcard 二进制格式存的正是定义这个模型的那些东西k、加权策略、度量、训练矩阵以及标签编码。kd-tree 不会被序列化它标了#[serde(skip)]在加载后的模型第一次调用predict时惰性重建。因此重新加载的分类器不需要你额外做什么就能给出和原模型完全一致的预测。usendarray::array;userustyml::machine_learning::{DistanceCalculationMetric,KNN};fnmain(){letx_trainarray![[0.0,0.0],[1.0,0.0],[2.0,0.0],[10.0,0.0],[11.0,0.0],[12.0,0.0],];lety_trainarray![0,0,0,1,1,1];letmutknnKNN::new(3).unwrap().with_metric(DistanceCalculationMetric::Manhattan).unwrap();knn.fit(x_train,y_train).unwrap();letpathknn_model.bin;knn.save_to_path(path).unwrap();// 首次 predict 时惰性重建 kd-treek、度量和标签都已恢复。letloadedKNN::i32::load_from_path(path).unwrap();letx_testarray![[0.5,0.0],[11.5,0.0]];assert_eq!(knn.predict(x_test).unwrap(),loaded.predict(x_test).unwrap());println!(round-trip predictions match);std::fs::remove_file(path).unwrap();}因为 KNN 模型带着它的整个训练集序列化文件会随n_train * d增长。这里的持久化存的是你的数据加上一点元数据而不是几个学出来的参数。如果模型体积对你很重要光这一点就足以让你考虑换一个参数化分类器。深入模型持久化讲解了这个格式及其保证。KNNT还实现了 crate 里共享的Fit和Predicttrait。这两个 trait 从machine_learning重导出定义在crate::traits里。Fit以(x, y)元组的形式接收训练数据。本页通篇展示的固有方法fit、predict、predict_parallel才是你平时会调用的。这两个 trait 存在的意义是让泛型代码能用同样的方式对待每一种估计器。