1201.机器学习-算法-KNN

一部新片过来：接吻镜头 18 次、打斗镜头 7 次。库里已有一批标好「爱情片 / 动作片」的老片，各自也有这两个计数。没有一条干净的直线能把两类彻底分开——爱情片里也会打几下，动作片里也会亲一下。

这时一个很朴素的办法是：别先学一条全局规则，先去问「最像它的几部老片」都是什么类型。这就是 K 近邻（K-Nearest Neighbors，KNN）的思路。

段末注释：KNN 用距离找邻居再投票（或取平均），属于基于实例的监督学习；训练阶段几乎只「记住样本」，预测时才算距离，因此常叫惰性学习（lazy learning）。后文沿用 KNN。

配图目录：./1201.机器学习-算法-KNN/。

1. 一句话定位

维度	一句话
学习范式	监督学习（需要带标签的训练样本）
输入 → 输出	特征 $\mathbf{x}$ → 类别（分类）或连续值（回归，邻居标签平均）
在优化什么	不显式拟合参数；假设「特征空间里相近的点，标签也相近」

出现背景：Cover & Hart（1967）给出近邻规则的经典分析（Nearest Neighbor Pattern Classification）。当时不少方法急于学一条全局决策面；KNN 用「查最近邻再表决」处理局部不规则边界，训练阶段几乎只存样本，把计算留到预测时。

比喻：像搬进新小区，想判断这里适不适合带娃——你不会先解一个全市方程，而是先问最近几户邻居的感受，再少数服从多数（或给更近的邻居更大话语权）。

图 1　找最近邻居，再投票

2. 直觉：三步流水线

图 2　算距离 → 找 k 个邻居 → 投票

算距离：新样本与训练集每个点比远近。
找邻居：取出距离最小的 $k$ 个训练点。
做决策：分类用多数票（可加权）；回归对邻居标签取平均（可加权）。

惰性体现在：第 1～3 步都发生在预测时；所谓「训练」往往只是存下数据（外加可选的索引加速）。

3. 核心链路

3.1 距离：中间量是「有多像」

对两个 $m$ 维向量 $\mathbf{x}=(x_1,\ldots,x_m)$、$\mathbf{z}=(z_1,\ldots,z_m)$，最常用的是欧氏距离：

$$
d(\mathbf{x},\mathbf{z}) = \sqrt{\sum_{j=1}^{m}(x_j-z_j)^2}
$$

距离越小，越「像」。文本等高维稀疏特征更常用余弦相似度（看夹角，不看绝对长度）；选用哪一种，应让「近」在业务上真的表示「同类可能性更大」。

3.2 量纲：距离会被大值域特征绑架

若一维是「年收入（万元级）」、另一维是「年龄（十级）」，欧氏距离几乎只听收入的。实务上先做标准化 / 归一化，再算距离。

图 3　特征尺度不齐时的距离陷阱

简单最小–最大归一化示意：

$$
x’ = \frac{x - x_{\min}}{x_{\max} - x_{\min}}
$$

3.3 从邻居到标签

设邻居标签为 $y_{(1)},\ldots,y_{(k)}$（按下标表示「第 $i$ 近」）。

多数投票：谁票多跟谁；二分类时 $k$ 常取奇数，减少平局。
距离加权投票：更近的邻居权重大，常用 $w_i = 1/d_i^2$（$d_i$ 为到该邻居的距离；实际实现需处理 $d_i=0$）。

回归时把「投票」换成对 $y_{(i)}$ 的（加权）平均即可。

3.4 「参数」从哪来

KNN 没有像 Logistic 那样的 $\beta$ 需要迭代估计。你要定的是超参数与协议：

$k$：邻居个数
距离 / 相似度定义
是否加权、是否标准化
（可选）KD-Tree / Ball Tree / ANN 等加速结构

4. 手算完整实例：电影类型

A. 问题与原始表

用「接吻镜头数、打斗镜头数」判爱情 / 动作（示意）。

影片	接吻 $x_1$	打斗 $x_2$	类型
A	20	3	爱情
B	18	2	爱情
C	5	18	动作
D	3	20	动作
E	15	8	爱情

B. 初始化

距离用欧氏；$k=3$；决策为多数投票。懒学习无参数迭代——「可部署对象」就是整张训练表 + $(k,$ 度量, 投票规则$)$。

C. 训练过程

无显式多轮训练；预测时才算距离。下面把 E 留出复核 与 新片预测 写全。

D. 可部署对象

训练集五条记录；$k=3$；欧氏距离；多数票。推理不另学一套 $\beta$。

E. 预测 / 推断

（1）训练内留出复核：查询 $E=(15,8)$，库只用 A–D（模拟「该点未入模」）。

库中影片	$d(E,\cdot)$
A	$\sqrt{(15-20)^2+(8-3)^2}=\sqrt{50}\approx7.1$
B	$\sqrt{(15-18)^2+(8-2)^2}=\sqrt{45}\approx6.7$
C	$\sqrt{(15-5)^2+(8-18)^2}=\sqrt{200}\approx14.1$
D	$\sqrt{(15-3)^2+(8-20)^2}=\sqrt{288}\approx17.0$

最近 3 个：B、A、C → 票型爱情、爱情、动作 → 爱情（与 E 真值一致）。

（2）新片 $Q=(16,6)$，库用全部 A–E：

邻居候选	$d(Q,\cdot)$
A	$\sqrt{25}=5.0$
B	$\sqrt{20}\approx4.5$
C	$\sqrt{265}\approx16.3$
D	$\sqrt{365}\approx19.1$
E	$\sqrt{5}\approx2.2$

最近 3 个：E、B、A，全是爱情 → 判 $Q$ 为爱情片。

5. 适用 / 不适用

按特征 / 训练目标 / 训练数据三维对照；每行带一个具体例子。

维度	判定	要求或边界	具体例子
特征	适用	已数值化（或可算相似度）；各维量纲已标准化/归一化；维数不宜过高，或已降维；「近」在业务上真表示更可能同类	电影：`(接吻次数, 打斗次数)` 标准化后，用欧氏距离找邻居判爱情/动作片
特征	不适用	量纲悬殊却不缩放；原始超高维稀疏且硬上欧氏距离；类别型无编码就当数字减	同时丢进「年收入（万）」和「是否会员（0/1）」不算缩放，距离几乎只听收入；上万维词袋直接欧氏，点与点都差不多远
训练目标	适用	分类（天然多类）或回归（邻居标签平均）；能接受「因为这几个邻居」式解释，不强制全局线性系数	手写数字 0–9 多分类：新图找最像的 $k$ 张已标注图投票
训练目标	不适用	必须输出稳定可宣讲的全局规则；或只要校准很好的概率且邻域稀疏	风控合规要「收入>x 且负债率<y → 拒绝」这类规则，树/规则更合适；邻域里同类极少时，KNN「伪概率」很飘
训练数据	适用	有标签；样本量中等、能整库（或索引后）参与距离计算；同类在特征空间相对成团	品类约几千 SKU、每类有一批已标注样本，新商品用属性向量找近邻推荐类目
训练数据	不适用	训练库极大且预测延迟极严（每次要扫海量点且无近似近邻）；或噪声点多还设 $k=1$	亿级用户实时特征、毫秒级打分却暴力全库 KNN；标注里夹杂大量错标且 $k=1$，一次错邻就定乾坤

6. 优缺点与常见坑

优点

思路直观，实现简单，几乎无「训练」。
天然支持多分类；边界可以很弯曲。
对局部结构敏感，有时对稀有模式比强偏置线性模型更友好。

缺点

预测慢、占内存：要存样本并算距离（可用索引 / 近似近邻缓解）。
可解释性弱：解释往往是「因为这几个邻居」，不是稳定规则。
受距离定义、$k$、尺度、噪声点强烈影响。

常见坑

$k$ 太小：听单个噪声点的；$k$ 太大：邻域跨过真实边界，被多数类淹没。用交叉验证选；经验上常试奇数，并小于 $\sqrt{n}$ 量级作粗起点。
不做标准化：大值域特征抢走距离。
高维滥用欧氏距离：维数升高后点与点都「差不多远」，先降维或换度量。
把惰当免费：训练快 ≠ 上线便宜；样本量上去后要算清预测延迟。

7. 最小可运行示例

"""KNN 最小示例：输入二维特征，输出类别；先标准化再拟合。"""
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

# 输入：X (n_samples, n_features)；y 为类别标签
X = np.array([
    [20, 3], [18, 2], [5, 18], [3, 20], [15, 8],
])
y = np.array(["爱情", "爱情", "动作", "动作", "爱情"])

# 处理逻辑：标准化后找 k 个邻居多数投票；也可设 weights="distance"
clf = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier(n_neighbors=3, weights="uniform")),
])
clf.fit(X, y)

x_new = np.array([[16, 6]])
print("预测类型:", clf.predict(x_new)[0])
print("各类概率:", dict(zip(clf.classes_, clf.predict_proba(x_new)[0])))

预期：与手算中新片 $Q$ 一致，倾向「爱情」（代码含标准化，数值概率与纯欧氏手算不必逐位相同）。

重要配置参数（sklearn `KNeighborsClassifier`）

参数（库内常用名）	训练中的作用与影响	参考起点 / 常用范围	配置指导
`n_neighbors`（$k$）	$k$ 小：边界细、噪声敏感；$k$ 大：更平滑、可能抹掉局部结构	常从奇数 $k=3,5,7$ 起；可用交叉验证扫	验证波动大 → 略增大 $k$；边界过钝 → 略减小 $k$
`weights`	`uniform` 等权投票；`distance` 近邻权重大	默认 `uniform`；样本疏密不均可试 `distance`	边界样本多时 `distance` 常更稳，仍要以验证集为准
`metric` / `p`	距离定义（欧氏、曼哈顿等）；量纲不同会主导远近	标准化后常用欧氏（`minkowski` + `p=2`）	先标准化再调 $k$；类别特征勿直接欧氏硬套
`algorithm`	近邻检索实现（`auto`/`kd_tree`/`ball_tree`/`brute`）	默认 `auto` 通常足够	维数很高时树索引收益下降，关注预测耗时而非只调 $k$

8. 和近邻算法怎么挑

需求	更优先考虑
要概率 + 系数解释、近似线性可分	Logistic 回归
局部相似、弯曲边界、多分类基线	KNN
间隔最大化、可核技巧、中小样本	支持向量机（SVM）
要规则解释、特征交互多	决策树 / Boosting

9. 小结

KNN = 距离定义相似 + 取 $k$ 个邻居 + 投票或平均。
真正吃紧的是度量、缩放与 $k$，不是「训练出一堆系数」。
做局部、多分类、不规则边界时好用；高维、超大库、强解释需求时要谨慎或换模型。
最易踩的坑：特征未标准化就直接欧氏距离。

参考文献

Cover T., Hart P. Nearest Neighbor Pattern Classification. IEEE Trans. Inf. Theory 1967.
scikit-learn: Nearest Neighbors
Harrington P. Machine Learning in Action（机器学习实战）KNN 章节。