机器学习笔记之八——knn最简单的机器学习算法以及KD树原理

上一节结束了线性回归、逻辑回归，今天一节来介绍机器学习中最简单的算法：  

 K近邻（KNN，全称K-nearst Neighbor）

      概述：判断一个样本的label只需要判断该样本周围其他样本的label。简言之，朋友选啥我选啥。

      具体实现？

          对于特征为X（X可以是多个），样本为y的训练集，当我们需要预测的时候，直接将需要预测的目标样本yi拿过来，在训练集中遍历，寻找与目标样本yi的特征Xi距离相近的点（距离相近的意思可以是欧几里的距离，也可以是其他，距离的大小由我们人为规定）。

         找到我们距离相近的点（可能是多个，这个点要多少由我们认为规定。这些点被称为近邻点）之后：

         如果是分类问题，那么就对这些点的label进行投票法（就是选数量最多的那个类别）或者加权投票法（把距离的倒数作为权值，加权求和）。

         如果是回归问题，就对这些点的label求平均值，或者加权平均值作为目标样本的结果。

       调参（需要我们给定的参数）

         （1）、K值，即判断样本需要几个近邻点。过大容易欠拟合，过小容易过拟合。

        （2）、距离的度量：一般使用欧几里的距离。

        （3）、决策规则：使用投票法、平均法，还是加权投票法、加权平均法。

KD树

  按照上面的思路，在训练集中遍历寻找近邻点的方法叫做暴力搜索，显然这种暴力搜索的开销是极其巨大的，每一次预测都要遍历整个训练集，在数据集较大的时候我们采用另一种方法来寻找近邻点，那就是KD树。

  构建KD树：

      对于具有两个特征值X1和X2的样本，计算样本中两个特征的方差，对方差大的特征取中位数，将中位数作为根结点的判断条件，小于中位数的放在左子树，大于中位数的放在右子树。

      对左、右子树进行同样的操作，如：在左子树的样本中，计算两个特征的方差，对方差大的特征取中位数，将中位数作为根结点的判断条件……

    如此循环，直到样本点分完，KD树构建完成。

   以上是对于两个特征，N个特征的时候也是一样的。

  如何预测？

     第一步，在KD树中找到包含目标点的叶子节点。

     第二步，以目标点为圆心，以目标点到这个叶子节点的的距离为半径，画图，最近邻点一定在这个圆里面。（对于对于多个特征，这里就是超球体了）。

      第三步，找到这个叶子节点的父节点A，检查该父节点A的另一子树的所有结点构成的超矩形体是否和超球体有相交（就是另一子树的结点是否有结点落在这个圆、超球体里面，相交就可能有），若相交，遍历此节点下是否有更加近的近邻点，有就更新。

     第四步，若没有，就返回第三步中说的的父节点A的父节点B，对B进行第三步中的操作，检查是否有相交，是否有更近的近邻点。

  下图为一个二维特征的KD树预测过程，x，y轴分别为两个特征属性。