机器学习读书笔记 — KNN

1.KNN
kNN是一种分类的算法，这个算法的思路非常简单。对于给定的训练数据集，对于新输入的实例，在训练数据集中找打与该实例最临近的k个实例，在这k个实例里面，多数属于某一类的话，就把这个实例归于某一类。

如果k=3 ，那么从所有的点里面找到离新输入的实例最近的三个点。如下图所示。那么在这三个点里面，多数的点属于三角类。那么就认为新输入的点属于三角类。

image.png

如果k=5，那么从所有的点里面找到离新输入的实例最近的五个点。如下图所示，那么在这三个点里面，多数的点属于圆圈类。那么就认为新输入的点属于圆圈类。

image.png

KNN的算法本身是比较简单的，对于上面的例子，选择k=3还是k=5是一个完全不同的结果。KNN算法的核心在于选择合适的k值。

2. kd树
   knn在计算的时候，需要计算待分类的样本点到所有样本的距离之后，才能找到最近的前k个点。最简单的办法就是线性扫描，这样做的缺点是计算开销比较大。解决的办法就是使用kd树（k-dimensional树的简称）的方法。

• 构建kd树

• 搜索kd树

---

参考文献

1. 李航《统计学习方法》