K近邻算法

1、基本思想

K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

2、如何选择距离

与该实例最近邻的k个实例，这个最近邻的定义是通过不同距离函数来定义，我们最常用的是欧式距离。

3、k值该如何选择？

我们一般选取一个较小的数值，通常采取 交叉验证法来选取最优的k值

4、特征归一化

归一化的目的就是取消不同特征值的“权重”问题，使得不同的特征值是等价的

5、小总结—KNN算法过程

1. 计算测试样本和训练样本中每个样本点的距离（常见的距离度量有欧式距离，马氏距离等）；
2. 对上面所有的距离值进行排序；
3. 选前 k 个最小距离的样本；
4. 根据这 k 个样本的标签进行投票，得到最后的分类类别；

   6、kd树

   Kd-树是K-dimension tree的缩写，是对数据点在k维空间（如二维(x，y)，三维(x，y，z)，k维(x1，y，z..)）中划分的一种数据结构，主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。本质上说，Kd-树就是一种平衡二叉树。

kd树示例

kd树上的KNN算法