声明：部分转载 http://www.cnblogs.com/pinard/p/6061661.html
最近在整理之前学过的一些机器学习算法，首先简单的knn算法，个人对knn用中国古代的一句话总结就是近朱者赤，近墨者黑。
1.KNN的原理
- 假设有一个带有标签的样本数据集（训练样本集），其中包含每条数据与所属分类的对应关系。
- 输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。
- 计算新数据与样本数据集中每条数据的距离。
- 对求得的所有距离进行排序（从小到大，越小表示越相似）。
- 取前 k 个样本数据对应的分类标签。
- 分类决策规则。
首先针对于第二点的第一条，计算距离。我们常用的计算计算距离的公式有以下几个：
（1）欧式距离，即对于两个n维向量x和y，两者的欧式距离定义为：
大多数情况下，欧式距离可以满足我们的需求，我们不需要再去操心距离的度量。
（2）曼哈顿距离，定义为：
（3）切比雪夫距离，定义为：
其中欧式距离是闵可夫斯基距离距离在p=2时的特例，而曼哈顿距离是p=1时的特例。
其次针对第三点，如何选择k。对于k值的选择，没有一个固定的经验，一般根据样本的分布，选择一个较小的值，可以通过交叉验证选择一个合适的k值。
选择较小的k值，就相当于用较小的领域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是泛化误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
选择较大的k值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
一个极端是k等于样本数m，则完全没有分类，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单。
这里我们可以用交叉验证法来寻找最佳的k值。
针对第四点，分类决策规则，一般都是使用前面提到的多数表决法。所以我们重点是关注与k值的选择和距离的度量方式。
2.KNN的优化
因为简单的KNN使用的是蛮力搜索，当特征数较少的时候效果还是比较好的，当特征数达到上千以上，样本量有几十万以上，就显得有些浪费时间了。所以我们提出的解决思路是：一是减少样本量，二是加快搜索 k 近邻。
2.1 减少样本量
当训练样本集中样本数量太大时，可以从原始训练样本集中选择最优的子集进行 KNN 的寻找，这类方法主要包括 Condensing算法、WilSon 的 Editing 算法和 Devijver 的 MultiEdit 算法，Kuncheva 使用 遗传算法 在这方面也进行了一些研究。
2.2 加快搜索KNN
主要通过快速的搜索算法来实现，采用一定的方法加快搜索速度或减小搜索范围，如可以构造交叉索引表，利用匹配成功与否的历史来修改样本库的结构，使用样本和概念来构造层次或网络来组织训练样本。
常用的方法是先建立数据索引，然后再进行快速匹配。因为实际数据一般都会呈现出簇状的聚类形态，通过设计有效的索引结构可以大大加快检索的速度。索引树属于这一类，其基本思想就是对搜索空间进行层次划分。有两个优化算法，一个是KD树实现，一个是球树实现。
2.3 KD树
KD树算法没有一开始就尝试对测试样本分类，而是先对训练集建模，建立的模型就是KD树，建好了模型再对测试集做预测。所谓的KD树就是K个特征维度的树，注意这里的K和KNN中的K的意思不同。KNN中的K代表最近的K个样本，KD树中的K代表样本特征的维数。为了防止混淆，后面我们称特征维数为n。
KD树算法包括三步，第一步是建树，第二部是搜索最近邻，最后一步是预测。
2.3.1 KD树的建立
kd 树的结构
kd树是一个二叉树结构，它的每一个节点记载了【特征坐标，切分轴，指向左枝的指针，指向右枝的指针】。
其中，特征坐标是线性空间 Rn 中的一个点 (x1,x2,…,xn)切分轴由一个整数 r 表示，这里 1≤r≤n，是我们在 n 维空间中沿第 rr维进行一次分割。节点的左枝和右枝分别都是 kd 树，并且满足：如果 y 是左枝的一个特征坐标，那么 yr≤xr（左分支结点）；并且如果 z 是右枝的一个特征坐标，那么 zr≥xr（右分支结点）。
给定一个数据样本集 S⊆Rn 和切分轴 r，以下递归算法将构建一个基于该数据集的 kd 树，每一次循环制作一个节点：
−− 如果 |S|=1，记录 S 中唯一的一个点为当前节点的特征数据，并且不设左枝和右枝。（|S| 指集合 S 中元素的数量）
−− 如果 |S|>1
- 将 S 内所有点按照第 r 个坐标的大小进行排序；
- 选出该排列后的中位元素（如果一共有偶数个元素，则选择中位左边或右边的元素，左随便哪一个都无所谓），作为当前节点的特征坐标，并且记录切分轴 r；
- 将 SL设为在 S 中所有排列在中位元素之前的元素； SR 设为在 S 中所有排列在中位元素后的元素；
-
当前节点的左枝设为以 SL 为数据集并且 r 为切分轴制作出的 kd 树；当前节点的右枝设为以 SR 为数据集并且 r为切分轴制作出的 kd 树。再设 r←(r+1)modn。（这里，我们想轮流沿着每一个维度进行分割；modn 是因为一共有 n 个维度，在沿着最后一个维度进行分割之后再重新回到第一个维度。）
给定一个二维空间的数据集：
T = {（2,3），（5,4），（9,6）,（4,7），（8,1），（7,2）}， 构造一个平衡kd树。
为了方便，我这里进行编号A(2，3)、B（5,4）、C（9,6）、D（4,7）、E（8,1）、F（7,2）
初始值r=0，对应x轴。
可视化数据点如下：
首先先沿 x 坐标进行切分，我们选出 x 坐标的中位点，获取最根部节点的坐标，对数据点x坐标进行排序得：
A(2，3)、D（4,7）、B（5,4）、F（7,2）、E（8,1）、C（9,6）
则我们得到中位点为B或者F，我这里选择F作为我们的根结点，并作出切分（并得到左右子树），如图：
对应的树结构如下：
根据算法，此时r=r+1=1，对应y轴，此时对应算法|S|>1，则我们分别递归的在F对应的左子树与右子树按y轴进行分类，得到中位节点分别为B，C点，如图所示：
对应树结构为：
而到此时，B的左孩子为A，右孩子为D，C的左孩子为E,均满足|S|==1，此时r = (r+1)mod2 = 0,又满足x轴排序，对x轴划分！则如图所示：
对应树结构如下：
恩恩，到这里为止，给定的kd树构造完成啦，所有的数据点都能在树上的每个结点找到！而我们根据上面构造树的过程，也能很容易的知道，来了一个新的数据点的时候，对应该层的指定维数，通过比较大小，我就能知道往左（预测点对应维度数据小于该结点对对应维度数据）走还是往右（预测点对应维度数据大于该结点对应维度数据）走，那么好的情况下，我们就能省掉一半的数据点啦~（不好的情况，哈哈，没有节省，后面会说到，这也是kd树的致命缺点~）
恩，好啦，到这里为止，我们一步一步给出了kd树的构造过程。这也是李航博士书籍上例子中kd树构造的详细过程！他的图片如下：
对应kd树为:
2.3.2 KD树的搜索
- kd树搜索
我这里和统计学习方法例子一样，以最近邻为例加以叙述，同样的方法可以应用到k近邻。
为了让大家更好的理解，我这里直接用上面例子给大家一步一步给出过程！
首先我们来看用kd树的最近邻搜索算法流程：
输入：已构造的kd树；目标点x；
输出：x的最近邻.
（1）在kd树中找出包含目标点x的叶结点：从根结点出发，递归地向下访问kd树，若目标点x当前维的坐标小于切分点的坐标,则移动到左子节点，否则移动到右子结点.直到子结点为叶结点位置.
（2）以此叶结点为“当前最近点”
（3）递归地向上回退，在每个结点进行以下操作：
（a）如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”.
（b）当前最近点一定存在于该结点一个子结点对应的区域.检查该子结点的父结点的另一个子结点对应的区域是否有更近的点.具体地，检查另一子结点对应的区域是否以目标点为球心、以目标点与“当前最近点”间为半径的超球体相交。
如果不相交，向上回退.
（4）当回退到根结点时，搜索结束。最后的“当前最近点”即为最近邻点.
看到这里是不是有点晕了，哈哈，不要怕，下面通过例子，一步一步走一遍上面所描述的算法过程，化抽象为具体！
kd树最近邻搜索例题：
给定一个二维空间的数据集：
T = {（2,3），（5,4），（9,6）,（4,7），（8,1），（7,2）}，输入目标实例为K(8.5,1),求K的最近邻。
首先我们由上面可以给出，T的kd树对应如下：
我们此时的K（8.5,1），根据算法第一步得：第一层的x轴K点为8大于F点的7，所以进入F（7,2）的右子树，进入下面红色线条区域：
到了第二层，分割平面坐标为y轴，K点y轴坐标为1，小于C点y轴坐标6，则继续向右走，在下图红色线条区域内：
则此时算法对应第（1）部分完成，我们找到了叶子节点E（8,1）。
我们进行算法第（2）步，把E（8,1）作为最近邻点。此时我们算一下KE之间的距离为0.5（便于后面步骤用到）.
然后进行算法第（3）步，递归的往上回退，每个结点进行相同步骤，好，我现在从E点回退到C点，对应图片如下；
此时对C点进行第（3）步的（a）操作，判断一下KC距离与保存的最近邻距离（这时是KE）比较，KC距离为点K（8.5,1）与点C（9,6）之间的距离>最近邻0.5，于是不更新最近邻点。
然后对C点进行第（3）步的（b）操作，判断一下当前最近邻的距离画一个圆是否与C点切割面相交，如图所示：
我们很容易看到与C点切割面并没有相交，于是执行由C点回退到它的父结点F点。如图：
对F点进行（a），（b）操作！
进行（a）步骤，判断FK的距离是否小于当前保存的最小值，FK=>0.5，所以不改变最小距离
下面我们进行（b）步骤，为了判断F点的另一半区域是否有更小的点，判断一下当前最近邻的距离画一个圆是否与F点切割面相交，如图所示：
发现与任何分割线都没有交点，那么执行算法最后一步，此时F点已经是根结点，无法进行回退，那么我们可以得到我们保留的当前最短距离点E点就是我们要找的最近邻点！任务完成，
并且根据算法流程，我们并没有遍历所有数据点，而是F点的左孩子根本没有遍历，节省了时间，但是并不是所有的kd树都能到达这样的效果。
2.3.3 KD树的预测
有了KD树搜索最近邻的办法，KD树的预测就很简单了，在KD树搜索最近邻的基础上，我们选择到了第一个最近邻样本，就把它置为已选。在第二轮中，我们忽略置为已选的样本，重新选择最近邻，这样跑k次，就得到了目标的K个最近邻，然后根据多数表决法，如果是KNN分类，预测为K个最近邻里面有最多类别数的类别。如果是KNN回归，用K个最近邻样本输出的平均值作为回归预测值。
2.4. KNN算法之球树实现原理
KD树算法虽然提高了KNN搜索的效率，但是在某些时候效率并不高，比如当处理不均匀分布的数据集时,不管是近似方形，还是矩形，甚至正方形，都不是最好的使用形状，因为他们都有角。一个例子如下图：
如果黑色的实例点离目标点星点再远一点，那么虚线圆会如红线所示那样扩大，导致与左上方矩形的右下角相交，既然相 交了，那么就要检查这个左上方矩形，而实际上，最近的点离星点的距离很近，检查左上方矩形区域已是多余。于此我们看见，KD树把二维平面划分成一个一个矩形，但矩形区域的角却是个难以处理的问题。
为了优化超矩形体导致的搜索效率的问题，牛人们引入了球树，这种结构可以优化上面的这种问题。
我们现在来看看球树建树和搜索最近邻的算法。
2.4.1 球树的建立
球树，顾名思义，就是每个分割块都是超球体，而不是KD树里面的超矩形体。
我们看看具体的建树流程：
1) 先构建一个超球体，这个超球体是可以包含所有样本的最小球体。
2) 从球中选择一个离球的中心最远的点，然后选择第二个点离第一个点最远，将球中所有的点分配到离这两个聚类中心最近的一个上，然后计算每个聚类的中心，以及聚类能够包含它所有数据点所需的最小半径。这样我们得到了两个子超球体，和KD树里面的左右子树对应。
3)对于这两个子超球体，递归执行步骤2). 最终得到了一个球树。
可以看出KD树和球树类似，主要区别在于球树得到的是节点样本组成的最小超球体，而KD得到的是节点样本组成的超矩形体，这个超球体要与对应的KD树的超矩形体小，这样在做最近邻搜索的时候，可以避免一些无谓的搜索。
2.4.2 球树搜索最近邻
使用球树找出给定目标点的最近邻方法是首先自上而下贯穿整棵树找出包含目标点所在的叶子，并在这个球里找出与目标点最邻近的点，这将确定出目标点距离它的最近邻点的一个上限值，然后跟KD树查找一样，检查兄弟结点，如果目标点到兄弟结点中心的距离超过兄弟结点的半径与当前的上限值之和，那么兄弟结点里不可能存在一个更近的点；否则的话，必须进一步检查位于兄弟结点以下的子树。
检查完兄弟节点后，我们向父节点回溯，继续搜索最小邻近值。当回溯到根节点时，此时的最小邻近值就是最终的搜索结果。
从上面的描述可以看出，KD树在搜索路径优化时使用的是两点之间的距离来判断，而球树使用的是两边之和大于第三边来判断，相对来说球树的判断更加复杂，但是却避免了更多的搜索，这是一个权衡。
2.5 KNN算法的扩展
这里我们再讨论下KNN算法的扩展，限定半径最近邻算法。
有时候我们会遇到这样的问题，即样本中某系类别的样本非常的少，甚至少于K，这导致稀有类别样本在找K个最近邻的时候，会把距离其实较远的其他样本考虑进来，而导致预测不准确。为了解决这个问题，我们限定最近邻的一个最大距离，也就是说，我们只在一个距离范围内搜索所有的最近邻，这避免了上述问题。这个距离我们一般称为限定半径。
接着我们再讨论下另一种扩展，最近质心算法。这个算法比KNN还简单。它首先把样本按输出类别归类。对于第 L类的ClCl个样本。它会对这ClCl个样本的n维特征中每一维特征求平均值，最终该类别所有维度的n个平均值形成所谓的质心点。对于样本中的所有出现的类别，每个类别会最终得到一个质心点。当我们做预测时，仅仅需要比较预测样本和这些质心的距离，最小的距离对于的质心类别即为预测的类别。这个算法通常用在文本分类处理上。
3. KNN算法小结
KNN算法是很基本的机器学习算法了，它非常容易学习，在维度很高的时候也有很好的分类效率，因此运用也很广泛，这里总结下KNN的优缺点。
KNN的主要优点有：
1） 理论成熟，思想简单，既可以用来做分类也可以用来做回归
2） 可用于非线性分类
3） 训练时间复杂度比支持向量机之类的算法低，仅为O(n)
4） 和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感
5） 由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合
6）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分
KNN的主要缺点有：
1）计算量大，尤其是特征数非常多的时候
2）样本不平衡的时候，对稀有类别的预测准确率低
3）KD树，球树之类的模型建立需要大量的内存
4）使用懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢
5）相比决策树模型，KNN模型可解释性不强
