机器学习面试准备（一）KNN

目录

一、简述一下KNN算法的原理?

 二、KNN算法的三要素

三、如何理解K值的选择

四、kd树是什么及其作用？

五、KNN的优缺点

---

一、简述一下KNN算法的原理?

KNN（K-Nearest Neighbor）是一种基本的分类与回归方法，给定一个训练数据集，对于新的输入实例，在数据集中找到与该实例的最邻近的K个实例，如果这K个实例的多数属于某个类，就把该输入实例归为这一类。

KNN不具备显示的学习过程，实际上是利用训练数据集对特征空间进行划分，并作为其分类的模型。

 

---

 二、KNN算法的三要素

距离度量：一般采用LP距离。（P=1，曼哈顿距离；P=2，欧氏距离；P=∞，切比雪夫距离）

K值选择：一般选取一个比较小的数，通常选择交叉验证的方法来选取最佳的K值。

分类决策规则：一般采用多数表决规则 

---

三、如何理解K值的选择

如果K值选择较小，就相当于用较小领域中的训练实例去预测，“学习”的近似误差会减小，但估计误差会增大，如果邻近的点是噪声，预测就会出错。另外，K值的减小意味着整体模型变得复杂，容易发生过拟合。

如果K值选择较大，就相当于用较大领域中的训练实例去预测，学习的估计误差会减小，近似误差会增大，此时与输入实例较远（不相似的）实例也会对预测起作用，使预测发生错误，K值增大意味着整体的模型变得简单。

在应用中，一般选取一个比较小的数，通常选择交叉验证的方法来选取最佳的K值。

---

四、kd树是什么及其作用？

KNN最简单的实现方法是线性扫描，因为要对每个实例计算距离，所以当训练集很大，训练实例维度很高，计算会非常耗时。为了提高KNN搜索的效率，可以采用kd树来存储数据

 

---

五、KNN的优缺点

 

---

参考：

《统计学习方法》

简博士的个人空间_哔哩哔哩_Bilibili 

---