当前位置：首页 > news >正文

KNN（k 近邻）算法详解：距离度量、k 值选择、决策边界与 C++ 实现一文搞懂（机器学习入门）

news 2026/6/13 8:53:42

KNN（k-Nearest Neighbors，k 近邻）是机器学习里最朴素、也最好懂的有监督分类算法。它有一个很特别的标签——懒惰学习（lazy learning）：它没有"训练"过程，不拟合任何模型，只是把训练数据原样存下来，等来了一个新点，才现场开算。一句话原理：看你周围最近的 k 个邻居是什么类，你就是什么类。（我不慌-----成长杂货铺：https://wobuhuang.com）

一、距离度量：欧氏距离与曼哈顿距离

要找"最近"的邻居，先得定义"近"。最常用的是欧氏距离（两点直线距离）：在二维下就是sqrt((x1-x2)^2 + (y1-y2)^2)。另一种是曼哈顿距离（各坐标差的绝对值之和），像在棋盘格里只能横竖走。

这里有个工程上的坑：量纲不同要先归一化。如果一个特征是"年龄"（0~100），另一个是"年收入"（几万到几十万），不归一化的话，距离会被大尺度特征完全主导，小尺度特征形同虚设。

二、投票分类：四步流程

算距离：算新点到每一个已知训练点的距离。
排序取 k：按距离从近到远排序，挑出最近的 k 个邻居。
投票：这 k 个邻居里，数一数哪个类别票最多。
定类：把新点归为票最多的那一类。

在码路星球的动画里，灰色新点会向第 1 近、第 2 近……一直到第 k 个邻居逐条连线，连到哪个颜色多，新点就染成哪个色，非常直观。

三、k 值与过拟合 / 欠拟合

k 是 KNN 唯一的关键超参数：

k 太小（如 k=1）：容易被一个噪声点带偏，决策边界很"毛糙"，是典型的过拟合。
k 太大：把远处不相关的点也算进来，边界变模糊，甚至被多数类淹没，倾向欠拟合。

实战中常用交叉验证在一个范围里挑最优 k；二分类时记得取奇数，避免出现票数相同的平票。

四、决策边界

把平面上每个位置都用 KNN 跑一遍，相邻预测类别的交界就是决策边界。k 越小边界越曲折破碎（对噪声敏感），k 越大边界越平滑。理解了边界，就理解了 k 为什么是在"拟合训练点"和"抵抗噪声"之间权衡。

五、完整 C++ 实现（带注释）

intknn_classify(Point q,vector<Point>&train,intk){for(auto&p:train)// ① 算距离p.dist=distance(q,p);sort(train,by_dist);// ② 按距离排序map<int,int>votes;// ③ 取前 k 个投票for(inti=0;i<k;i++)votes[train[i].label]++;returnargmax(votes);// ④ 票最多的类}

代码骨架就这四步：算距离、排序、对前 k 个邻居投票、返回票最多的类（argmax）。距离函数可按需替换为欧氏或曼哈顿。

六、复杂度：训练 O(1)，预测 O(n)，KD-Tree 加速

KNN 的复杂度特征很鲜明：训练 O(1)（只存数据），单次预测 O(n·d)（要和全部 n 个训练点比，d 是维度），空间 O(n·d)（存全部训练点）。数据量大时预测很慢，工程上用KD-Tree / 球树（ball tree）来加速近邻查找，把平均查询从 O(n) 降下来。另外要注意维度灾难：维度很高时，所有点的距离趋于接近，距离失去区分度，KNN 会失效。