KNN
一句话介绍KNN
KNN是一种可用于分类和回归的方法。一般情况下用其进行分类任务。
KNN三要素
1）模型，即对特征空间的划分；
2）距离度量，欧氏距离等；
3）分裂决策规则，即多数投票方法
特点
KNN不具有显式的学习过程，实际上是利用训练集对特征空间进行划分，然后对新样本进行相邻K个最近样本的统计，并以多数类作为该样本的预测。
K值如何确定
首先需要明确：如果我们选取较小的k值，那么就会意味着我们的整体模型会变得复杂，容易发生过拟合
下面来解释上面的模型变复杂以及过拟合：
上图中，假设待分类的样本为红色五边形：
1）如果K=1，那么黑色圆形距离红色最近，则判定红色属于黑色圆形类别！
这种极端情况的结果会发现很容易模型就学习到了噪声，即模型本身变得复杂，引入了噪声，同时，K值过小后，会导致过拟合，很容易将一些噪声（如上图离五边形很近的黑色圆点）学习到模型中，而忽略了数据真实的分布。
2）如果K增大到8，那么如下图：可以发现，此时红色目标被判定为蓝色矩形类别了，这个结果就很好接受。
如果我们选取较大的k值，就相当于用较大邻域中的训练数据进行预测，这时与输入实例较远的（不相似）训练实例也会对预测起作用，使预测发生错误，k值的增大意味着整体模型变得简单。、
那么为何K值的增大能够使得模型变得简单？
我们想，如果k=N（N为训练样本的个数）,那么无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类。这时，模型是不是非常简单，这相当于你压根就没有训练模型呀！直接拿训练数据统计了一下各个数据的类别，找最大的而已！这好像下图所示：我们统计了黑色圆形是8个，长方形个数是7个，那么哈哈，如果k=N，我就得出结论了，红色五边形是属于黑色圆形的（当然这样的结果也是错误的）
上面过于简单的模型同样导致预测结果出错，那么对于K来讲，不能太小也不能太大。在李航的书中说道，一般选取一个较小的数值，通常采取 交叉验证法来选取最优的k值
KD树
k近邻法最简单的实现是线性扫描（穷举搜索），即要计算输入实例与每一个训练实例的距离。计算并存储好以后，再查找K近邻。当训练集很大时，计算非常耗时。为了提高kNN搜索的效率，可以考虑使用特殊的结构存储训练数据，以减小计算距离的次数。
KD树构建算法
1）确定切分维度
计算各个特征维度上的方差，每次选择方差最大的进行分割
2）确定分割点
确定好分割哪一维度后，将该维度特征排序，选择中位数进行此次切分
举例：
6个二维数据点{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}构建kd树的具体步骤为：
1、确定：split域=x。具体是：6个数据点在x，y维度上的数据方差分别为39，28.63，所以在x轴上方差更大，故split域值为x；
2、确定：Node-data = （7,2）。具体是：根据x维上的值将数据排序，6个数据的中值(所谓中值，即中间大小的值)为7，所以
Node-data域位数据点（7,2）。这样，该节点的分割超平面就是通过（7,2）并垂直于：split=x轴的直线x=7；
3、确定：左子空间和右子空间。具体是：分割超平面x=7将整个空间分为两部分：x<=7的部分为左子空间，包含3个节点 = {(2,3),(5,4),(4,7)}；另一部分为右子空间，包含2个节点 = {(9,6)，(8,1)}；
KD树搜索算法
我们新来一个样本，需要在KD中完成搜索，以便确定其类别
1）二分查找，递归向从根结点出发，递归的向下访问kd树。若目标点当前维的坐标值小于切分点的坐标值，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止；
2）以此节点为“最近邻点”，从该点向上回退，目的是看看其父节点的另一子节点内是否有更近的点
做法是：
向上回退，若该节点保存的实例中有更近的距离，那么更新最近邻点，此时，需要额外检查更新节点另一子空间是否有更近的点，以目标点到该点距离为半径画圆，若圆与该最近邻点的另一子空间相交，那么移动到另一子节点，递归搜索，然后再回退，直到会退到根节点位置。
KNN与Kmeans
不同点：
K-Means是无监督学习的聚类算法，没有样本输出；
而KNN是监督学习的分类算法，有对应的类别输出。
KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。
而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。
相似点：
当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。
