KNN算法简介
1 课程概览
本课介绍K近邻算法（KNN）的基本思想与核心概念，讲解KNN既能做分类（投票）也能做回归（均值）的特点，并通过电影类型预测案例详细演示欧式距离的计算过程和KNN分类的完整流程。同时讨论K值选择对模型拟合的影响。
2 核心概念与定义
- KNN（K-Nearest Neighbor，K近邻算法）：找到最近的K个邻居，根据邻居类别推断未知样本类别的算法。
- 欧式距离（Euclidean Distance）：对应维度差值平方和开平方根，即勾股定理的推广。
- 超参数（Hyperparameter）：需要用户手动输入的参数，如KNN中的K值。
- 交叉验证（Cross Validation）：寻找最优超参数的方法之一。
- 网格搜索（Grid Search）：寻找最优超参数的方法之一。
3 算法与模型详解
3.1 KNN算法思想
如果一个样本在特征空间中的K个最相似样本中，大多数属于某一个类别，则该样本也属于该类别。
- 相似性判断：通过距离计算，距离越近越相似。
- 分类问题：K个邻居投票，少数服从多数。
- 回归问题：K个邻居的目标值取平均值。
3.2 KNN分类与回归对比
| 类型 | 标签特点 | 决策方式 | 说明 |
|---|---|---|---|
| 分类 | 不连续（离散） | 投票（多数表决） | K个邻居中哪个类别多就选哪个 |
| 回归 | 连续（数值） | 均值（平均值） | K个邻居的目标值取平均 |
3.3 KNN分类流程（五步）
- 计算距离：计算未知样本到训练集中每个样本的距离。
- 排序：将距离按升序排列。
- 选取K个：找到距离最近的K个样本。
- 投票：统计K个样本中各类别数量。
- 决策：票数最多的类别作为预测结果。
若票数相同，选择距离最近的类别（奥卡姆剃刀原则）。
3.4 欧式距离计算
公式：
$$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$
理解：勾股定理的推广——斜边 = 两直角边平方和开根号。
3.5 电影类型预测案例
训练数据（x_train, y_train）：
| 电影 | 搞笑镜头 | 拥抱镜头 | 打斗镜头 | 类型 |
|---|---|---|---|---|
| 功夫熊猫 | 39 | 0 | 31 | 喜剧 |
| 叶问3 | 3 | 2 | 65 | 动作 |
| 伦敦陷落 | 2 | 3 | 55 | 动作 |
| ... | ... | ... | ... | ... |
待预测（x_test）：唐人街探案（搞笑23, 拥抱3, 打斗17）
计算示例（唐人街探案 vs 功夫熊猫）：
$$d = \sqrt{(39-23)^2 + (0-3)^2 + (31-17)^2}$$ $$= \sqrt{16^2 + 3^2 + 14^2}$$ $$= \sqrt{256 + 9 + 196}$$ $$= \sqrt{461} \approx 21.47$$
K=5时的投票结果：
| 排名 | 电影 | 距离 | 类型 |
|---|---|---|---|
| 1 | 从你的全世界路过 | 18.1 | 爱情 |
| 2 | 伦敦陷落 | 20.3 | 动作 |
| 3 | 宝贝当家 | 20.4 | 喜剧 |
| 4 | 功夫熊猫 | 21.5 | 喜剧 |
| 5 | 步步惊心 | 22.1 | 喜剧 |
投票：喜剧3票，爱情1票，动作1票 → 喜剧片
3.6 K值选择与拟合关系
| K值 | 拟合情况 | 原因 |
|---|---|---|
| K值过小（如K=1） | 过拟合 | 数据量少，学到脏数据，模型复杂 |
| K值过大（如K=N） | 欠拟合 | 模型简单，投票结果永远是多数类 |
K值选择需适中，可通过交叉验证和网格搜索寻找最优K值。
3.7 四大距离度量方式
| 距离名称 | 别名 | 说明 |
|---|---|---|
| 欧式距离（Euclidean） | — | 默认使用，勾股定理推广 |
| 曼哈顿距离（Manhattan） | 城市街区距离 | — |
| 切比雪夫距离（Chebyshev） | — | — |
| 闵氏距离（Minkowski） | — | — |
4 数学原理与推导
4.1 欧式距离公式（二维）
$$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$
- $(x_1, y_1)$：样本1的坐标
- $(x_2, y_2)$：样本2的坐标
4.2 欧式距离公式（n维）
$$d = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}$$
- $x_i$：样本x的第i个特征值
- $y_i$：样本y的第i个特征值
- $n$：特征维度数
4.3 计算示例
$$d = \sqrt{(39-23)^2 + (0-3)^2 + (31-17)^2} = \sqrt{256 + 9 + 196} = \sqrt{461} \approx 21.47$$
5 代码示例
本课无完整代码，KNN代码实现将在后续课程讲解。
6 重难点与易错提醒
- ❗重点：KNN分类=投票；KNN回归=均值。
- ❗重点：K值过小→过拟合；K值过大→欠拟合。
- ⚠️易错：K值过小是过拟合（不是欠拟合）！数据量少导致学到脏数据。
- ⚠️易错：投票票数相同时，选择距离最近的类别（奥卡姆剃刀）。
- 💡深入理解：欧式距离本质是勾股定理的推广——斜边=两直角边平方和开根号。
7 课堂问答精选
Q: K值过小会发生过拟合还是欠拟合？
A: 过拟合。K值过小（如K=1）意味着数据量少，模型会学到大量脏数据，导致模型复杂，从而过拟合。
Q: K值过大会发生什么？
A: 欠拟合。K值过大（如K=N）时，模型过于简单，投票结果永远是训练集中数量最多的类别。
Q: KNN如何确定样本相似性？
A: 通过距离计算，距离越近越相似。默认使用欧式距离。
8 本课小结
- KNN = K近邻算法，找最近的K个邻居进行决策。
- 分类=投票（多数表决）；回归=均值（平均值）。
- KNN分类五步：算距离→排序→选K个→投票→决策。
- 欧式距离 = 对应维度差值平方和开平方根（勾股定理推广）。
- K值过小→过拟合；K值过大→欠拟合。
9 延伸思考与实践
- 思考：为什么K值过小会导致过拟合？
- 思考：除了欧式距离，还有哪些距离度量方式？各有何优缺点？
- 预习：交叉验证和网格搜索如何寻找最优K值？