机器学习课程-温州大学-06机器学习-KNN算法

• 语言: 中文（简体）
• 格式: .pdf
• 来源: github.com/fengdu78

摘要

文档主要介绍了KNN（k-Nearest Neighbor）算法的基本原理及其应用。KNN算法是一种简单而成熟的机器学习算法，适用于分类和回归问题。其核心思路是通过计算新样本与训练集中样本的距离，选择最近的k个邻居，并根据邻居的类别或标签值进行预测。算法的三要素包括k值选择、距离度量和决策规则。此外，文档还介绍了KD树作为一种高效的空间划分方法，用于加速KNN算法的搜索过程，特别适用于高维数据的最近邻搜索。通过构建KD树，可以快速定位目标点的叶子节点，并在超球体内寻找最近邻点。

AI总结

# 《机器学习课程-温州大学-06机器学习-KNN算法》总结

## 核心观点

K近邻法（k-Nearest Neighbor, kNN）是一种简单而成熟的机器学习算法，适用于基本的分类与回归任务。其主要思路是：根据新样本在特征空间中与k个最近邻训练样本的类别或标签值，通过多数表决或均值计算等方法进行预测。

## 关键信息

1. **KNN算法三要素**：
- **k值选择**：k值的选择对模型性能有显著影响，需根据具体问题和数据集进行调整。
- **距离度量**：常用的距离度量方法包括欧氏距离和余弦相似度。
- **决策规则**：
- **分类问题**：通过多数表决方式确定新样本的类别。
- **回归问题**：以k个最近邻标签值的均值作为预测值。

2. **算法流程**：
- 计算测试对象到训练集中每个对象的距离。
- 按照距离远近排序。
- 选取与测试对象最近的k个训练对象作为邻居。
- 统计邻居的类别频次或计算标签值的均值。
- 根据频次或均值确定测试对象的类别或预测值。

3. **距离度量**：
- **欧氏距离**：计算两个样本各特征维度差的平方和开平方。
- **余弦相似度**：计算两个样本特征向量的夹角余弦值。

4. **KD树**：
- **KD树划分**：通过交替选择特征维度进行空间划分，构建树状结构，提高搜索效率。
- **KD树搜索**：通过树状结构快速定位目标点所在的叶子节点，并在超球体内寻找最近邻点。

5. **案例分析**：
- 以二维数据集为例，构建KD树并搜索目标点（4,4）的最近邻时，通过中位数切分和深度优先遍历，忽略不相关的子树区域，最终找到最近邻点。

---

**总结**：KNN算法是一种基于局部样本分布的懒惰学习算法，通过k个最近邻的类别或标签值进行预测。其核心在于选择合适的k值、距离度量方法以及高效的搜索策略（如KD树）。该算法简单易懂，但在处理大规模数据时效率较低，因此KD树的引入显著提升了其在高维空间中的搜索效率。