K 近邻算法（K-Nearest Neighbors, KNN）详解及案例
K近邻算法（K-Nearest Neighbors, KNN）详解及案例
一、基本原理
K近邻算法是一种监督学习算法，核心思想是“物以类聚，人以群分”：对于一个新样本，通过计算它与训练集中所有样本的“距离”，找出距离最近的K个样本（即“近邻”），再根据这K个近邻的标签（分类问题）或数值（回归问题）推断新样本的结果。
KNN属于“惰性学习（Lazy Learning）”，它没有显式的“训练过程”，不会提前构建模型，而是在预测时直接依赖训练数据进行计算，因此也被称为“实例-based学习”。
二、核心要素与关键步骤
1. 距离度量
距离用于衡量样本间的相似性，距离越小，样本越相似。常用的距离度量包括：
-
欧氏距离（最常用）：适用于连续特征，计算n维空间中两个点的直线距离。
公式：对于样本x=(x1,x2,...,xn)x=(x_1,x_2,...,x_n)x=(x1,x2,...,xn)和y=(y1,y2,...,yn)y=(y_1,y_2,...,y_n)y=(y1,y2,...,yn)，欧氏距离为：
d(x,y)=∑i=1n(xi−yi)2d(x,y)=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2}d(x,y)=i=1∑n(xi−yi)2 -
曼哈顿距离：适用于高维数据，计算坐标轴上的“城市街区距离”。
公式：d(x,y)=∑i=1n∣xi−yi∣d(x,y)=\sum_{i=1}^{n}|x_i-y_i|d(x,y)=∑i=1n∣xi−yi∣ -
余弦相似度：适用于高维稀疏数据（如文本），衡量向量方向的相似性（与模长无关）。
公式：cosθ=x⋅y∣∣x∣∣⋅∣∣y∣∣=∑i=1nxiyi∑i=1nxi2⋅∑i=1nyi2\cos\theta=\frac{x\cdot y}{||x||\cdot||y||}=\frac{\sum_{i=1}^{n}x_i y_i}{\sqrt{\sum_{i=1}^{n}x_i^2}\cdot\sqrt{\sum_{i=1}^{n}y_i^2}}cosθ=∣∣x∣∣⋅∣∣y∣∣x⋅y=∑i=1nxi2⋅∑i=1nyi2∑i=1nxiyi
2. K值选择
K值是KNN的核心超参数，直接影响预测结果：
- K值过小：近邻数量少，易受噪声样本影响，导致“过拟合”（模型对训练数据太敏感）。
- K值过大：近邻包含过多无关样本，导致“欠拟合”（模型忽略局部特征，偏向全局平均）。
- 常见选择：通常取奇数（避免投票平局），如3、5、7等；实际应用中通过交叉验证（如5折交叉验证）选择最优K值。
3. 决策规则
- 分类问题：对K个近邻的标签进行“多数投票”（少数服从多数），得票最多的标签即为新样本的预测类别。
- 回归问题：对K个近邻的数值取“平均值”（或加权平均值），作为新样本的预测值。
4. 核心步骤
- 确定距离度量方式（如欧氏距离）和K值；
- 计算新样本与训练集中所有样本的距离；
- 按距离从小到大排序，选取前K个样本作为“近邻”；
- 根据K个近邻的标签（分类）或数值（回归），得到新样本的预测结果。
三、优缺点
优点
- 简单直观：无需复杂的模型训练，原理易懂，实现难度低；
- 适应性强：可处理非线性数据，对特征分布无严格假设；
- 扩展性好：可通过优化距离计算（如KD树、球树）提升效率。
缺点
- 计算成本高：预测时需与所有训练样本计算距离，样本量过大时速度慢；
- 对不平衡数据敏感：若某类样本占比极高，K近邻易被其主导；
- 对噪声和异常值敏感：离群点可能被误判为“近邻”，影响预测结果；
- 依赖距离度量：高维数据中“距离”的意义会弱化（维度灾难）。
四、案例详情（分类问题：电影类型预测）
问题描述
已知4部电影的特征（搞笑镜头数、打斗镜头数）和标签（喜剧片/动作片），预测一部新电影的类型。
训练数据
| 电影ID | 搞笑镜头数（特征1） | 打斗镜头数（特征2） | 标签 |
|---|---|---|---|
| A | 30 | 10 | 喜剧片 |
| B | 20 | 5 | 喜剧片 |
| C | 5 | 40 | 动作片 |
| D | 10 | 30 | 动作片 |
新样本
待预测电影E：搞笑镜头数=25，打斗镜头数=20，需预测其类型。
预测步骤
步骤1：确定参数
选择欧氏距离作为度量方式，K=3（奇数，避免平局）。
步骤2：计算新样本与训练样本的距离
电影E（25,20）与A、B、C、D的欧氏距离：
- 与A（30,10）的距离：(25−30)2+(20−10)2=(−5)2+102=25+100=125≈11.18\sqrt{(25-30)^2+(20-10)^2}=\sqrt{(-5)^2+10^2}=\sqrt{25+100}=\sqrt{125}\approx11.18(25−30)2+(20−10)2=(−5)2+102=25+100=125≈11.18
- 与B（20,5）的距离：(25−20)2+(20−5)2=52+152=25+225=250≈15.81\sqrt{(25-20)^2+(20-5)^2}=\sqrt{5^2+15^2}=\sqrt{25+225}=\sqrt{250}\approx15.81(25−20)2+(20−5)2=52+152=25+225=250≈15.81
- 与C（5,40）的距离：(25−5)2+(20−40)2=202+(−20)2=400+400=800≈28.28\sqrt{(25-5)^2+(20-40)^2}=\sqrt{20^2+(-20)^2}=\sqrt{400+400}=\sqrt{800}\approx28.28(25−5)2+(20−40)2=202+(−20)2=400+400=800≈28.28
- 与D（10,30）的距离：(25−10)2+(20−30)2=152+(−10)2=225+100=325≈18.03\sqrt{(25-10)^2+(20-30)^2}=\sqrt{15^2+(-10)^2}=\sqrt{225+100}=\sqrt{325}\approx18.03(25−10)2+(20−30)2=152+(−10)2=225+100=325≈18.03
步骤3：排序并选K=3个近邻
距离从小到大排序：
A（11.18）→ B（15.81）→ D（18.03）→ C（28.28）
前3个近邻为：A、B、D。
步骤4：多数投票
- 近邻A的标签：喜剧片；
- 近邻B的标签：喜剧片；
- 近邻D的标签：动作片；
- 投票结果：喜剧片（2票）＞动作片（1票）。
预测结果
电影E被预测为喜剧片。
五、总结
KNN是一种基于“相似性”的简单算法，核心依赖距离度量和K值选择。尽管存在计算成本高的问题，但因其直观性和适应性，在推荐系统、图像识别、文本分类等领域仍被广泛应用（如推荐系统中“相似用户喜欢的商品”推荐）。实际使用时需注意优化样本量和距离计算，以提升效率。