回顾传统 kNN 算法以及优化方法。

kNN 的基本思路，给定一个训练数据集，对新的输入 instance，在训练数据集中找到与之最邻近的 k 个 instance，然后看这 k 个 instance 的大多数属于哪个类，那么这个类就是输入 instance 的最终类别。

特征归一化

这算是常识性的知识啦，不过每次都会提醒一下。对于数值型的特征，我们一般都会进行归一化，如将数值范围处理到 0 到 1 之间，以此来保证每个特征是同等重要的。

来看看下面的例子，如果不归一化，那么，第一列(数字差值最大)的属性对计算结果的影响最大(代入相似度距离计算公式)，然而我们不希望这样。

40920	8.326976	0.953952	largeDoses
14488	7.153469	1.673904	smallDoses
26052	1.441871	0.805124	didntLike
75136	13.147394	0.428964	didntLike
38344	1.669788	0.134296	didntLike
72993	10.141740	1.032955	didntLike
35948	6.830792	1.213192	largeDoses
42666	13.276369	0.543880	largeDoses
......

最简单的归一化做法 newValue=(oldValue-min)/(max-min)

代码

def autoNorm(dataSet):
    minVals = dataSet.min(0)  # select min value from columns
    maxVals = dataSet.max(0) # select max value from columns
    ranges = maxVals - minVals # max-min
    m = dataSet.shape[0]
    normDataSet = zeros(shape(dataSet))
    normDataSet = dataSet - tile(minVals, (m, 1)) # oldValue-min
    normDataSet = normDataSet / tile(ranges, (m, 1)) # division
    return normDataSet, ranges, minVals

当然，要记住在做分类的时候，也要先对特征进行归一化。

相似度距离计算

怎么来判断邻近？如何来度量两个点之间的距离？距离选择很大程度上影响 kNN 的效果，因此它必须能足够的体现出样本间的相似和不同的程度，最常用的是欧式距离。

$$d(x,y):=\sqrt {(x_1-y_1)^2+(x_2-y_2)^2+…+(x_n-y_n)^2}=\sqrt {\sum^n_{i=1}(x_i-y_i)^2}$$

保存前 K 个点，可以用 最大堆(Max Heap) 实现。

根据具体的问题，距离也可以采用 余弦距离、海明距离、编辑距离 等等。

k 值选取

k 的选取是很重要的，看上面一个例子，蓝色和红色分别代表两个不同的类 B 和 R，绿色是输入 instance，我们要对其进行分类，可以发现，k 取 3 和 5 得到的分类结果是完全不同的。

k=3，新的 instance 属于 R 类别，因为离它最近的 3 个 instance 是有 2 个属于 R，1 个属于 B。
k=5，新的 instance 属于 R 类别，因为离它最近的 5 个 instance 是有 2 个属于 R，3 个属于 B。

所以，k 怎么选？

事实上，通常来说，我们在一开始会选取一个较小的 k 值(k=1)，然后采取交叉验证(cross-validation)的方法，直到 k=n，取使交叉验证得到最好的结果的那个 k，经验上，k 小于数据集大小的平方根。

k 值太小 or k 值太大
k 值太小容易产生过拟合，因为它很容易学到噪声，比如说 k=1，那么就只用看和输入 instance 最邻近的一个 instance，举个例子吧

而另一方面，k 值太大，那么意味着你的模型变得更加的简单，比如说 k=N(N为训练样本的个数)，那么无论输入的 instance 是什么类别，都会归到训练集中 instance 最多的那个类，也就是说，根本没有进行训练，只是简单的 count 而已，并没有利用训练集的其他大量的有用信息。

评价

KNN 是一种 instance-based method，对于未知和非正态分布的数据可以取得较高的分类准确率，优缺点如下：

优点：

算法简单直观，易于实现
免训练，参数少
不需要产生额外的数据来描述规则，它的规则就是训练数据（样本）本身，并不是要求数据的一致性问题，即可以存在噪音
虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本数量的不平衡问题，当然，在 k 值很大而样本又极度不平衡的情况下，结果就不妙了
最直接地利用了样本之间的关系，减少了类别特征选择不当对分类结果造成的不利影响，可以最大程度地减少分类过程中的误差项。对于一些类别特征不明显的类别而言，KNN法更能体现出其分类规则独立性的优势，使得分类自学习的实现成为可能

缺点：

时空复杂度高，分类速度慢
需要将所有训练样本首先存储起来，进行分类时实时进行计算处理，需要计算待分样本与训练样本库中每一个样本的相似度，才能求得与其最近的K个样本
对于高维样本或样本集规模较大的情况，其时间和空间复杂度较高，时间代价为O(mn)，其中 m 为向量空间模型空间特征维数，n 为训练样本集大小
样本库容量依赖性较强
有不少类别无法提供足够的训练样本，产生分类误差
特征作用相同
传统 KNN 认为每个属性的作用都是相同的(赋予相同权重)，而实际情况下，有些特征与分类是强相关的，有些特征与分类是弱相关的，还有一些特征(可能是大部分)与分类不相关。
K值的确定 KNN 算法必须指定 K 值，K 值选择不当则分类精度不能保证。

优化

加快分类速度

解决思路： 一是减少样本量，二是加快搜索 k 近邻。

减少样本量

当训练样本集中样本数量太大时，可以从原始训练样本集中选择最优的子集进行 KNN 的寻找，这类方法主要包括 Condensing算法、WilSon 的 Editing 算法和 Devijver 的 MultiEdit 算法，Kuncheva 使用 遗传算法 在这方面也进行了一些研究。

加快搜索 k 近邻

主要通过快速的搜索算法来实现，采用一定的方法加快搜索速度或减小搜索范围，如可以构造交叉索引表，利用匹配成功与否的历史来修改样本库的结构，使用样本和概念来构造层次或网络来组织训练样本。

常用的方法是先建立数据索引，然后再进行快速匹配。因为实际数据一般都会呈现出簇状的聚类形态，通过设计有效的索引结构可以大大加快检索的速度。索引树属于这一类，其基本思想就是对搜索空间进行层次划分。根据划分的空间是否有混叠可以分为 Clipping 和 Overlapping 两种。前者划分空间没有重叠，其代表就是 k-d 树；后者划分空间相互有交叠，其代表为 R 树。(这里只介绍k-d树)

KD Tree

构建 k-d tree

1.If Data-set为空，则返回空的k-d tree
2.调用节点生成程序：
    - 确定split域
    对于所有描述子数据（特征矢量），统计它们在每个维上的数据方差。以SURF特征为例，描述子为64维，可计算64个方差。挑选出最大值，对应的维就是split域的值。数据方差大表明沿该坐标轴方向上的数据分散得比较开，在这个方向上进行数据分割有较好的分辨率
    - 确定Node-data域
    数据点集Data-set按其第split域的值排序。位于正中间的那个数据点被选为Node-data。此时新的Data-set' = Data-set\Node-data（除去其中Node-data这一点）。
3.dataleft = {d属于Data-set' && d[split] ≤ Node-data[split]}
  Left_Range = {Range && dataleft}
  dataright = {d属于Data-set' && d[split] > Node-data[split]}
  Right_Range = {Range && dataright}
4.left = 由（dataleft，Left_Range）建立的k-d tree，即递归调用 createKDTree（dataleft，Left_Range）并设置 left 的 parent 域为 Kd；
  right = 由（dataright，Right_Range）建立的k-d tree，即调用createKDTree（dataleft，Left_Range）并设置 right 的 parent 域为 Kd。

如上图的 2 维数据，构建 KD Tree 过程：

确定 split 域的首先该取的值。分别计算 x，y 方向上数据的方差得知x方向上的方差最大，所以 split 域值首先取0，也就是 x 轴方向；
确定 Node-data 的域值。根据 x 轴方向的值 2,4,5,7,8,9 排序选出中值为7，所以 Node-data = (7,2)。这样，该节点的分割超平面就是通过(7,2)并垂直于 split = 0(x轴)的直线x = 7；
确定左子空间和右子空间。分割超平面x = 7将整个空间分为两部分，如图2所示。x < = 7的部分为左子空间，包含3个节点{(2,3)，(5,4)，(4,7)}；另一部分为右子空间，包含2个节点{(9,6)，(8,1)}。

最后生成的 k-d 树。

k-d tree 寻找

星号表示要查询的点(2.1,3.1)。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点(2,3)。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行’回溯’操作：算法沿搜索路径反向查找是否有距离查询点更近的数据点。此例中先从(7,2)点开始进行二叉查找，然后到达(5,4)，最后到达(2,3)，此时搜索路径中的节点为<(7,2)，(5,4)，(2,3)>，首先以(2,3)作为当前最近邻点，计算其到查询点(2.1,3.1)的距离为0.1414，然后回溯到其父节点(5,4)，并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以(2.1,3.1)为圆心，以0.1414为半径画圆，如图4所示。发现该圆并不和超平面y = 4交割，因此不用进入(5,4)节点右子空间中去搜索。

再回溯到(7,2)，以(2.1,3.1)为圆心，以0.1414为半径的圆更不会与x = 7超平面交割，因此不用进入(7,2)右子空间进行查找。至此，搜索路径中的节点已经全部回溯完，结束整个搜索，返回最近邻点(2,3)，最近距离为0.1414。

一个复杂点的例子如查找点为(2，4.5)。同样先进行二叉查找，先从(7,2)查找到(5,4)节点，在进行查找时是由y = 4为分割超平面的，由于查找点为y值为4.5，因此进入右子空间查找到(4,7)，形成搜索路径<(7,2)，(5,4)，(4,7)>，取(4,7)为当前最近邻点，计算其与目标查找点的距离为3.202。然后回溯到(5,4)，计算其与查找点之间的距离为3.041。以(2，4.5)为圆心，以3.041为半径作圆，如图5所示。可见该圆和y = 4超平面交割，所以需要进入(5,4)左子空间进行查找。此时需将(2,3)节点加入搜索路径中得<(7,2)，(2,3)>。回溯至(2,3)叶子节点，(2,3)距离(2,4.5)比(5,4)要近，所以最近邻点更新为(2，3)，最近距离更新为1.5。回溯至(7,2)，以(2,4.5)为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如图6所示。至此，搜索路径回溯完。返回最近邻点(2,3)，最近距离1.5。k-d树查询算法的伪代码如表3所示。

上述两次实例表明，当查询点的邻域与分割超平面两侧空间交割时，需要查找另一侧子空间，导致检索过程复杂，效率下降。研究表明 N 个节点的 K 维 k-d 树搜索过程时间复杂度为：$O_{worst}=O(kN^{1-1/k})$。

关于 kd tree 的介绍来自于 k-d tree算法

训练样本的维护

对训练样本库进行维护以满足 KNN 算法的需要，包括对训练样本库中的样本进行添加或删除。对样本库的维护并不是简单的增加删除样本，而是可采用适当的办法来保证空间的大小，如符合某种条件的样本可以加入数据库中，同时可以对数据库库中已有符合某种条件的样本进行删除。从而保证训练样本库中的样本提供 KNN 算法所需要的相对均匀的特征空间。

相似度距离公式优化

为了改变传统 KNN 算法中特征作用相同的缺陷，可以对相似度的距离公式中给特征赋予不同权重，例如在欧氏距离公式中给不同特征赋予不同权重。特征的权重一般根据各个特征在分类中的作用设定，可根据特征在整个训练样本库中的所起的作用大小来确定权重，也可根据在训练样本的局部样本(靠近待测试样本的样本集合)中的分类作用确定权重。