KNN算法原理
KNN算法又称为k最近邻分类算法。所谓的k最近邻，就是指最接近的k个邻居（数据），即每个样本都可以由它的k个邻居来表达。
KNN算法的核心思想是，在一个含未知样本的空间，可以根据离这个样本最邻近的k个样本的数据类型来确定样本的数据类型。
该算法涉及3个主要因素：分类决策规则、距离与相似的衡量、k的大小。
KNN做分类预测时，一般是选择多数表决法，即训练集里和预测的样本特征最近的k个样本，预测为里面有最多类别数的类别。而KNN做回归时，一般是选择平均法，即最近的K个样本的样本输出的平均值作为回归预测值。
对于距离的度量，我们有很多的距离度量方式，但是最常用的是欧式距离。
k值的选择，过小则容易过拟合，过大则容易欠拟合，可以使用交叉验证法选取k值。
KNN算法优缺点
优点：
- 思想简单，理论成熟，既可以用来做分类也可以用来做回归；
- 可用于非线性分类；
- 训练时间复杂度为O(n)；
- 准确度高，对数据没有假设，对离群值不敏感。
缺点：
- 计算量大；
- 样本不平衡问题（即有些类别的样本数量很多，而其他样本的数量很少）；
- 需要大量的内存。
KNN中不平衡样本问题的解决方案
KNN在分类时重要的不足在于当样本不平衡时（即一个类的样本容量很大，而其他类样本数量很小），很可能导致当输入一个未知样本时，该样本的k个邻居中大数量类的样本占多数。但是这类样本并不接近目标样本，而数量小的这类样本很靠近目标样本。这个时候，我们有理由认为该位置样本属于数量小的样本所属的一类，但是，KNN却不关心这个问题，它只关心哪类样本的数量最多，而不去把距离远近考虑在内，因此，会导致预测结果的不准确。
我们可以采用权值的方法来改进。和样本距离小的邻居权值大，和样本距离大的邻居权值则相对较小，由此，将距离远近的因素也考虑在内，避免因一个样本过大导致误判的情况。
KNN算法计算量过大的解决方案
KNN算法计算量较大，因为对每一个待分类的样本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。KNN算法的改进方法之一是分组快速搜素近邻法。其基本思想是：将样本集按近邻关系分解成组，给出每组质心的位置，以质心作为代表点，和未知样本计算距离，选出距离最近的一个或若干个组，再在组的范围内应用一般的KNN算法。由于并不是将未知样本与所有样本计算距离，故该改进算法可以减少计算量，但不能不减少存储量。
KD树的概念
kd树（k-dimension tree）是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是一种二叉树，表示对k维空间的一个划分，构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。这种空间划分就是对数据点进行分类，“挨得近”的数据点就在一个空间里面。利用kd树可以省去对大部分数据点的搜索，从而减少搜素的计算量。
kd树的构造
构造根结点，使得根结点对应于k维空间中包含所有实例点的超矩形区域；通过下面的递归的方法，不断地对k维空间进行切分，生成子结点。在超矩形区域选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分成左右两个子区域（子结点）；这时，实例被分到两个子区域（子结点）；这时，实例被分到两个子区域，这个过程直到子区域内没有实例时终止（终止时的结点为叶结点）。在此过程中，将实例保存在相应的结点上。通常，循环的选择坐标轴对空间切分，选择训练实例点在坐标轴上的中位数为切分点，这样得到的kd树是平衡的。
构造平衡kd树算法
输入：k维空间数据集$T={x_1,x_2,…,x_N}$，其中$x_i ={x_i(1),x_i(2),…,x_i(k)}，i=1,2,…,N$；
输出：kd树
（1）开始：构造根结点，根结点对应于包含T的k维空间的超矩形区域。选择x(1)为坐标轴，以T中所有实例的x(1)坐标中位数为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴x(1)垂直的超平面实现。由根结点生成深度为1的左、右子结点：左子结点对应坐标x(1)小于切分点的子区域，右子结点对应于坐标x(1)大于切分点的子区域。将落在切分超平面上的实例点保存在根结点。
（2）重复：对深度为j的结点，选择x(I)为切分的坐标轴，I =j%k+1，以该结点的区域中所有实例的x(I)坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴x(I)垂直的超平面实现。由该结点生成深度为j+1的左、右子结点：左子结点对应坐标x(I)小于切分点的子区域，右子结点对应坐标x(I)大于切分点的子区域。将落在切分超平面上的实例点保存在该结点。
搜索kd树
利用kd树可以省去对大部分数据点的搜素，从而减少搜索的计算量。
用kd树的最近邻搜索：
输入：已构造的kd树；目标点x；
输出：x的最近邻
（1）在kd树中找出包含目标点x的叶结点：从根结点出发，递归的向下访问kd树。若目标点当前维的坐标值小于切分点的坐标值，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止；
（2）以此叶结点为“当前最近点”；
（3）递归的向上回退，在每个结点进行以下操作：
- 如果该结点保存的实例点比当前最近点距目标点更近，则以该实例点为“当前最近点”；
- 当前最近点一定存在于该结点一个子结点对应的区域是否有更近的点。具体的，检查另一个子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。如果相交，可能在另一个子结点对应的区域内存在距离目标更近的点，移动到另一个子结点。接着，递归的进行最近邻搜索。如果不相交，向上回退。
（4） 当回退到根结点时，搜索结束。最后的“当前最近点”即为x的最近邻点。该方法可以修改后用于k近邻搜索，即通过维护一个包含k个最近邻结点的队列来实现。
优化kd树建立过程中切分维度的顺序
构建开始前，对比数据点在各维度的分布情况，数据点在某一维度坐标值的方差越大分布越分散，方差越小分布越集中。从方差大的维度开始切分可以取得很好的切分效果及平衡性。
kd树每一次继续切分都要计算该子区间在需切分维度上的中值，计算量很大，如何优化？
- 算法开始前，对原始数据点在所有维度进行一次排序，存储下来，然后在后续的中值选择中，无须每次都对其子集进行排序，提升了性能。
- 从原始数据点中随机选择固定数目的点，然后对其进行排序，每次从这些样本点中取中值，来作为分割超平面。
k-Means与KNN的区别
- KNN是分类算法，k-Means是聚类算法；
- KNN是监督学习，k-Means是非监督学习；
- KNN给它的数据集是带label的数据，已经是完全正确的数据，k-Means给它的数据集是无label的数据，是杂乱无章的，经过聚类后才变得有点顺序，先无序，后有序；
- KNN没有明显的前期训练过程，k-Means有明显的前期训练过程；
- k的含义
- KNN是对一个样本x给它分类，即求出它的y。就是从数据集中，在x附近找离它最近的k个数据点，这k个数据点，类别c占的个数最多，就把x的label设为c。
- k-Means中k是人工固定好的数字，假设数据集合可以分为k个簇，由于是依靠人工定好，需要一点先验知识。
