1.KNN
kNN是一种分类的算法，这个算法的思路非常简单。对于给定的训练数据集，对于新输入的实例，在训练数据集中找打与该实例最临近的k个实例，在这k个实例里面，多数属于某一类的话，就把这个实例归于某一类。
如果k=3 ，那么从所有的点里面找到离新输入的实例最近的三个点。如下图所示。那么在这三个点里面，多数的点属于三角类。那么就认为新输入的点属于三角类。
image.png
如果k=5，那么从所有的点里面找到离新输入的实例最近的五个点。如下图所示，那么在这三个点里面，多数的点属于圆圈类。那么就认为新输入的点属于圆圈类。
image.png
KNN的算法本身是比较简单的，对于上面的例子，选择k=3还是k=5是一个完全不同的结果。KNN算法的核心在于选择合适的k值。
- kd树
knn在计算的时候，需要计算待分类的样本点到所有样本的距离之后，才能找到最近的前k个点。最简单的办法就是线性扫描，这样做的缺点是计算开销比较大。解决的办法就是使用kd树（k-dimensional树的简称）的方法。
- 构建kd树
- 搜索kd树
参考文献
- 李航《统计学习方法》
