KNN：K最邻近算法（K-Nearest Neighbor,KNN）

用特征空间中距离待分类对象的最近的K个样例点的类别来预测。

投票法：K 个样例的对数类别。

1. k=1:最近邻分类

2. k 通常是奇数（因为我们根据这个K数据判断类别，如果是偶数可能出现类别对半的情况）

基于实例学习：不需要训练。

K 最邻近算法步骤：

1. 计算待分类对象鱼所有样例点的距离，找出 K 个距离最近的点。（目前用欧氏距离）

2. 通过这 K 个点的投票决定待分类对象的类别。

3. 1. 等权投票

   2. 加权投票：相似度加权

如图：K =3，分类结果是三角形

          k=5，分类结果是正方形

如果我们进行了加权，即便是K=5，由于实例点离三角形特别近，分类结果也有可能为三角形

如何确定K

1. K 太小，对噪音点敏感（早点附近的点，将都被分错）

2. K太大，模型不细致（如果 K 是所有样本数，那么分类结果将是训练数据中数量最多的类别，相当于朴素贝叶斯分类器中，只用了先验概率）

3. K权限 模型复杂度和经验风险

4. 交差验证

K-D Tree(K-Dimensional Tree)

KD Tree 是一种数据结构。对 k 维空间里的点进行组织，存储为树形的数据结构。

KD Tree 为K维空间进行分割，主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。

                                              图1

如图1：空间先按红线分割，然后前后两个空间分别按绿色线分割，然后在四个空间中再按蓝色线分割

建树：

1. 对当前所有点，依次按照一个维度的中位数为切分线进行切割,将当前区域分为两个区域，小于中位数放到左边，大于中位数放到右边。

2. 重复步骤1，直到没有点可分停止。

查找方法：（查找目标为x）

1. 在KD 树中自上而下按照建树的规则，找 x 对应的叶子节点，当做最近点，计算当前最近距离。

2. 从该叶节点开始，从底向上，重复直到根节点：计算当前节点的父节点的切分面到 x 的距离；如果该距离小于当前前最优距离，则在改父节点的另一子区域查找最近点，否则忽略该子区域，直接到上一层查找。

KD 树练习：

数据（2,3）（5,4）（9,6）（4,7）（8,1）（7,2）

查找最近邻近点：（4,5）（4,6）

                                      图2                                                              图3        

注意：

1. 图2 示：分割维度是依次轮换换着的。 

2. K>1:我们需要在KD Tree中维护一个数据，只要到分割面距离或者到其他节点的距离小于数组总最大距离，就必须计算，因有可能存在节点去替换数组中的节点。

3. KD这个数组，我是在前几轮算节点距离时，给填满的。