【机器学习基础】机器学习入门核心算法：K-近邻算法（K-Nearest Neighbors, KNN）

机器学习入门核心算法：K-近邻算法（K-Nearest Neighbors, KNN）

• 一、算法逻辑
• • • 1.1 基本概念
    • 1.2 关键要素
    • • 距离度量
      • K值选择
• 二、算法原理与数学推导
• • • 2.1 分类任务
    • 2.2 回归任务
    • 2.3 时间复杂度分析
• 三、模型评估
• • • 3.1 评估指标
    • 3.2 交叉验证调参
• 四、应用案例
• • • 4.1 手写数字识别
    • 4.2 推荐系统
• 五、经典面试题
• • • 问题1：KNN的主要优缺点？
    • 问题2：如何处理高维数据？
    • 问题3：KNN与K-Means的区别？
• 六、高级优化技术
• • • 6.1 数据结构优化
    • 6.2 近似最近邻（ANN）
• 七、最佳实践指南
• • • 7.1 参数调优建议
    • 7.2 特征处理要点
• 总结与展望

一、算法逻辑

1.1 基本概念

K-近邻算法（KNN）是一种基于实例的监督学习算法，其核心思想是**“物以类聚”**。算法特点包括：

• 懒惰学习（Lazy Learning）：没有显式的训练过程，直接存储全部训练数据
• 非参数化：不假设数据分布形式
• 局部近似：仅依赖邻近样本进行预测

工作原理： 给定新样本时，在训练集中查找距离最近的K个样本，通过这K个邻居的标签进行多数表决（分类）或均值计算（回归）。

1.2 关键要素

距离度量

常用距离计算公式：

K值选择

• K=1：最近邻算法，决策边界不规则，容易过拟合
• K过大：决策边界平滑，可能欠拟合

二、算法原理与数学推导

2.1 分类任务

多数表决规则：

y

^

=

arg

⁡

max

⁡

c

∑

x

i

∈

N

k

(

x

)

I

(

y

i

=

c

)

\\hat{y} = \\arg\\max_{c} \\sum_{\\boldsymbol{x}_i \\in N_k(\\boldsymbol{x})} I(y_i = c)

y^​=argcmax​xi​∈Nk​(x)∑​I(yi​=c) 其中：

• $N_k(\mathbf{x})$
• $I(\cdot )$

加权投票改进：

y

^

=

arg

⁡

max

⁡

c

∑

x

i

∈

N

k

(

x

)

w

i

I

(

y

i

=

c

)

\\hat{y} = \\arg\\max_{c} \\sum_{\\boldsymbol{x}_i \\in N_k(\\boldsymbol{x})} w_i I(y_i = c)

y^​=argcmax​xi​∈Nk​(x)∑​wi​I(yi​=c) 权重计算：

w

i

=

1

d

(

x

,

x

i

)

+

ϵ

w_i = \\frac{1}{d(\\boldsymbol{x}, \\boldsymbol{x}_i) + \\epsilon}

wi​=d(x,xi​)+ϵ1​ （

ϵ

\\epsilon

ϵ为防止除零的小常数）

2.2 回归任务

均值预测：

y

^

=

1

k

∑

x

i

∈

N

k

(

x

)

y

i

\\hat{y} = \\frac{1}{k} \\sum_{\\boldsymbol{x}_i \\in N_k(\\boldsymbol{x})} y_i

y^​=k1​xi​∈Nk​(x)∑​yi​

加权回归：

y

^

=

∑

x

i

∈

N

k

(

x

)

w

i

y

i

∑

w

i

\\hat{y} = \\frac{\\sum_{\\boldsymbol{x}_i \\in N_k(\\boldsymbol{x})} w_i y_i}{\\sum w_i}

y^​=∑wi​∑xi​∈Nk​(x)​wi​yi​​

2.3 时间复杂度分析

三、模型评估

3.1 评估指标

3.2 交叉验证调参

K值选择方法：

代码示例：

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import GridSearchCV

params = {'n_neighbors': [3,5,7,9],
'weights': ['uniform', 'distance']}
grid = GridSearchCV(KNeighborsClassifier(), params, cv=5)
grid.fit(X_train, y_train)

四、应用案例

4.1 手写数字识别

数据集：MNIST（60,000张28×28灰度图） 关键步骤：

性能表现：

• 测试集准确率：97.1%
• 推理速度：200样本/秒（使用KD树加速）

4.2 推荐系统

应用场景：电影推荐 特征工程：

• 用户评分矩阵
• 电影类型标签（One-Hot编码）
• 用户行为时序特征

相似度计算：

Similarity

(

u

,

v

)

=

∑

i

∈

I

u

v

(

r

u

i

−

r

ˉ

u

)

(

r

v

i

−

r

ˉ

v

)

∑

i

∈

I

u

v

(

r

u

i

−

r

ˉ

u

)

2

∑

i

∈

I

u

v

(

r

v

i

−

r

ˉ

v

)

2

\\text{Similarity}(u,v) = \\frac{\\sum_{i \\in I_{uv}}(r_{ui} – \\bar{r}_u)(r_{vi} – \\bar{r}_v)}{\\sqrt{\\sum_{i \\in I_{uv}}(r_{ui} – \\bar{r}_u)^2} \\sqrt{\\sum_{i \\in I_{uv}}(r_{vi} – \\bar{r}_v)^2}}

Similarity(u,v)=∑i∈Iuv​​(rui​−rˉu​)2

​∑i∈Iuv​​(rvi​−rˉv​)2

​∑i∈Iuv​​(rui​−rˉu​)(rvi​−rˉv​)​

推荐流程：

五、经典面试题

问题1：KNN的主要优缺点？

优点分析：

• 原理直观，实现简单
• 无需训练阶段，适合动态数据集
• 天然支持多分类任务

缺点分析：

• 计算复杂度高（预测阶段需全量计算）
• 对高维数据敏感（维度灾难）
• 需要特征标准化处理

问题2：如何处理高维数据？

解决方案：

问题3：KNN与K-Means的区别？

本质区别对比：

六、高级优化技术

6.1 数据结构优化

KD树构建：

球树（Ball Tree）：

• 将数据点组织成嵌套超球体
• 适合高维数据，比KD树更高效

6.2 近似最近邻（ANN）

大规模数据加速方法：

七、最佳实践指南

7.1 参数调优建议

7.2 特征处理要点

• 标准化：必须对数值特征进行标准化
• 类别特征：使用嵌入（Embedding）代替One-Hot
• 缺失值：使用KNNImputer进行填充

总结与展望

KNN算法凭借其简单直观的特性，在模式识别、推荐系统等领域持续发挥重要作用。未来发展方向包括：