Skip to content

K 最近邻分类(KNN) ​

方法速览 ​

  • 主要用途 用附近的已标注样本为一条新记录分类。
  • 必要输入 可比较的特征距离、已标注训练样本、邻居数 k。
  • 适用条件 相近样本较可能同类,训练样本覆盖需要预测的区域。
  • 典型不适用情况 训练点稀少、特征距离无法解释,或高维数据里远近差异很小。
  • 最低限度的验证方式 用训练集估计尺度,在验证集选 k,再用独立测试集衡量效果。

为什么近处的样本能投票 ​

一台设备传回两路传感器读数。现有历史记录标有“正常”或“需检查”,新读数还没有标签。KNN 保留这些历史记录,从中按距离找出最靠近新读数的 k 条,让它们投票。对二分类而言,如果 k=3 且三个邻居的标签是 0,1,1,预测关键字是类 1。正类票占 2/3,它只是指定邻域内的经验比例。若要把比例用于风险决策,还应检验校准。

两个传感器若分别以伏和毫伏记数,未处理的欧氏距离可能被数值范围较大的那列支配。一种处理是仅用训练样本估计特征均值 μj 和总体标准差 sj,再用相同参数变换训练与新样本。平方距离为

d2(x,xi)=∑j=1p(xj−xijsj)2.

同一列中的均值在两点相减时消掉,所以真正改变距离权重的是除以 sj。平方根严格单调,比较平方距离就能确定哪些点更近。

双语言实验 ​

把邻居数从 1 改为 3,观察同一个留出样本的连线、票数与预测。再关闭缩放,判断哪一列更容易主导距离。

八条训练记录与四条留出记录由人工设置。标签在边界附近交错,便于观察小 k 如何受单条训练记录影响。代码先算训练尺度,再为留出行和网格点计算距离。把网格预测涂成两种颜色,虚线连接第 2 个留出点与当时被选中的邻居。网格只给图着色,评价指标只用四条留出记录。

运行原理实现 ​

下载 Python 源码 · 下载 MATLAB 源码

  • Python 环境安装 python -m pip install numpy matplotlib 后,在下载目录运行 python mmf_knn.py。
  • MATLAB 在下载目录运行 result = mmf_knn(),建议 R2016b 或更新版本,无需工具箱。

手算同量纲的二维平方距离、排序、取三邻居并投票。前三的平方距离为 1、2、5,输出正类。

最简版依赖 Python:无第三方依赖。MATLAB:基础功能,无需额外工具箱。

在源码所在目录运行 python mmf_min_knn.py

py
import json
points = [(0, 0), (1, 0), (3, 2), (4, 2)]
labels = [0, 0, 1, 1]
query = (3, 1)
k = 3

# 平方距离与欧氏距离的排序相同。枚举索引保留标签与样本的对应关系。
distance = [(a - query[0]) ** 2 + (b - query[1]) ** 2 for a, b in points]
neighbors = sorted(range(len(points)), key=lambda index: distance[index])[:k]
votes = sum(labels[index] for index in neighbors)
label = int(votes > k / 2)
assert neighbors == [2, 3, 1] and label == 1
result = {"squared_distances": [distance[index] for index in neighbors], "votes": votes, "label": label}
print("LAB_RESULT " + json.dumps(result, ensure_ascii=False))
下载当前源码

Python 用广播生成“查询 × 训练 × 特征”的差值数组,再沿特征求和;MATLAB 构造“查询 × 训练”的平方距离矩阵,每列一次计算某训练点与所有查询点的距离。两个实现都令等距样本按训练行顺序排列。先对照 training_scale,再查 query_neighbor_rows、test_positive_votes 和 test_predictions;输出的行号从 1 开始。结果中两行分别对应 k=1,3。

用标准函数复核 ​

Python 额外安装 scikit-learn。流水线先在训练数据拟合 StandardScaler,再用均匀权重的最近邻。MATLAB 先手动按相同总体标准差变换,再调用 fitcknn,需 Statistics and Machine Learning Toolbox。留出点没有会影响预测的等距并列。扩展到等距数据时,查看库的并列距离处理与投票规则。 scikit-learn StandardScaler 参数 · MathWorks fitcknn 参数

python
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

# 两列是不同量纲的读数,labels 与训练行一一对应。
train = [[1, 7], [2, 20], [3, 25], [4, 50], [5, 62], [7, 75], [8, 90], [9, 79]]
labels = [0, 0, 0, 1, 0, 1, 1, 1]
test = [[1.5, 15], [5.1, 60], [6.4, 68], [8.5, 84]]
for k in [1, 3]:
    # 流水线仅在 fit 时估计尺度,predict 复用尺度后再查 k 个近邻。
    model = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=k))
    # 比较四条留出查询在两种 k 下得到的类别。
    print(model.fit(train, labels).predict(test))
matlab
% 每行一条记录,只拿训练表估计距离所用的尺度。
train = [1, 7; 2, 20; 3, 25; 4, 50; 5, 62; 7, 75; 8, 90; 9, 79];
labels = [0; 0; 0; 1; 0; 1; 1; 1];
test = [1.5, 15; 5.1, 60; 6.4, 68; 8.5, 84];
center = mean(train, 1);
% std 的第二个参数为 1,表示用总体标准差;第三个参数为 1,表示按列算。
scale = std(train, 1, 1);
scale(scale == 0) = 1;
for k = [1, 3]
    % 已手动标准化,库内再次缩放保持关闭。邻居投票采用同权重。
    mdl = fitcknn((train-center)./scale, labels, 'NumNeighbors', k, ...
        'Distance', 'euclidean', 'DistanceWeight', 'equal', ...
        'Standardize', false, 'BreakTies', 'smallest');
    disp(predict(mdl, (test-center)./scale).')
end

参数练习 ​

先在图中找出 (5.1,60),预测它在 k=1 和 k=3 时会被分到哪一类。然后把训练数据和留出数据的第二列都乘以 1000,重新估计训练标准差,比较四条留出预测。

参考答案

(5.1,60) 最近的训练行是第 5 行,标签是 0。k=3 加入第 4、6 行后,标签为 0,1,1,预测转为 1。四条记录的参考准确率为 3/4 和 4/4。更换第二列单位会同时将它的标准差扩大 1000 倍,所以标准化后的距离与预测不变。小留出集只展示机制。真实任务若为了选 k 多次查看这四条记录,它们应当作为验证集,再另留一份测试集。

常见误区 ​

增大 k 会让单点影响下降,但也可能磨掉少数类的小区域。特征增多后,许多不相关的列也会贡献距离,容易淹没有效信号。新记录远离所有已知样本时,KNN 仍会给出某类,可以同时监控最近邻距离,远离训练分布时交给人工复查。K-means 也用距离,但它输出没有预先类别含义的分组;KNN 用已知标签预测类别。

关联文章 ​

MathModel FAQ · 数学建模知识库