主题
K 最近邻分类(KNN)
方法速览
- 主要用途 用附近的已标注样本为一条新记录分类。
- 必要输入 可比较的特征距离、已标注训练样本、邻居数
。 - 适用条件 相近样本较可能同类,训练样本覆盖需要预测的区域。
- 典型不适用情况 训练点稀少、特征距离无法解释,或高维数据里远近差异很小。
- 最低限度的验证方式 用训练集估计尺度,在验证集选
,再用独立测试集衡量效果。
为什么近处的样本能投票
一台设备传回两路传感器读数。现有历史记录标有“正常”或“需检查”,新读数还没有标签。KNN 保留这些历史记录,从中按距离找出最靠近新读数的
两个传感器若分别以伏和毫伏记数,未处理的欧氏距离可能被数值范围较大的那列支配。一种处理是仅用训练样本估计特征均值
同一列中的均值在两点相减时消掉,所以真正改变距离权重的是除以
双语言实验
把邻居数从 1 改为 3,观察同一个留出样本的连线、票数与预测。再关闭缩放,判断哪一列更容易主导距离。
八条训练记录与四条留出记录由人工设置。标签在边界附近交错,便于观察小
运行原理实现
- 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 开始。结果中两行分别对应
用标准函数复核
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参数练习
先在图中找出
参考答案
常见误区
增大