KNN分类算法

---

一、KNN思想

KNN分类的思想很简单，对于待分类的数据X，将其和训练集（已知样本的特征和类别）样本进行距离计算，选中距离最近的K个样本，以少数服从多数的原则，在这K个样本中去数量最多的类别作为X的类别，KNN的三个要素：K值，距离计算方式（通常使用曼哈顿距离），类别判断方式（通常使用多数打败少数的原则）

二、KNN实现方法

KNN的思想很简单，核心的计算就在于距离的计算和TOP-K样本的搜索，sklearn中提供了不同的方案以供选择：
 

1、暴力搜索

遍历训练集中所有的样本，计算其与待分类数据的距离，然后选择TOP-K个，暴力搜索的优点是简单，在训练集数据量小的情况下有绝对的优势，但是数据量增加时，性能大跌
 

2、kd-tree

2.1 kd-tree的构建

首先构造一棵kd-tree，然后在树中搜索top-k个样本，kd-tree的每一个节点都是一个样本。
kd-tree中的k和KNN中的K不是一回事，kd-tree中的k指的是样本的维度，kd-tree是利用样本每一个特征进行空间的分割和构建tree，tree的构建过程如下图所示：

构建的kd-tree如下图所示：

 

2.2 kd-tree的搜索

当判断一个新的数据的类别的时候，先在kd-tree中进行搜索，找到距离新数据最近的K个样本点，搜索kd-tree的过程是，先顺着kd-tree一层一层直到叶子节点，将叶子结点当作当前最近结点，再向父节点回溯，并检查父节点的另一子节点，随时更新当前最近距离，一级一级的向上回溯，直到回溯到根结点。搜索示例如下图所示：

首先在kd 树中找到包含点 S 的叶结点D（图中的右下区域），以点D作为近似最近邻。真正最近邻一定在以点S为中心通过点 D 的圆的内部。然后返回结点 D的父结点 B，在结点 B 的另一子结点F的区域内搜索最近邻。结点F的区域与圆不相交，不可能有最近邻点。继续返回上一级父结点 A，在结点A 的另一子结点C 的区域内搜索最近邻。结点C的区域与圆相交；该区域在圆内的实例点有点E，点E比点D更近，成为新的最近邻近似。最后得到点区E是点S的最近邻。
 

3、ball-tree

3.1 ball-tree的构建

构造一棵ball-tree，ball-tree中每一个节点都是一个ball，其中包含了多个样本，ball-tree的构建过程如下：

 

3.2 ball-tree的搜索

ball-tree的搜索过程如下：
1、找到目标点t所在的小组，也就是小圆T；
2、计算这个小圆T中距离目标点t最近的点作为当前最近邻点n；
3、以目标点t为中心，当前最近邻距离（t-n）为半径画圆O；
4、找到所有和上述圆O相交的圆，如果找到的圆有小分组，就看这些小分组是否也和圆O相交，如果没有就终止，如果都相交就继续往下找小分组，直到找到了某个点，计算距离。
 
tips：以上步骤是借鉴此链接得来，BallTree结构和答疑，截图如下：