K近邻算法的基本
k近邻法(k-nearest neighbor,KNN)是一种可以做分类也可以做回归的方法。是一种比较简单的方法，给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最近的K个实例，这K个实例的多数属于某个类，就把该输入实例分到这个类。
基本过程：
输入：训练数据集T和实例特征向量x.
输出：实例x所属的类y.
过程：（1）根据给定的距离度量，在训练集T中找到与x最近的k个点，涵盖着k个点的集合记作N。
（2）在N中根据分类决策规则决定x的类别y,比如可以将N中类别最多的类别就定义为x的类别。
特殊情况：
当k = 1的情形，称为最近邻算法。对于输入的实例点x，他的分类结果就是距离他最近的训练数据中的点。
可以看出k近邻算法没有显式的学习过程。
K近邻模型的三个基本要素
三个基本要素分别是：距离度量、K值的选择、分类决策规则。
距离度量：
特征空间中两个实例点的距离是两个实例点相似程度的反应。
若有两个实例$xi$和$x_j$，这两个实例的$L_p$距离被定义为：
$L_p(x_i,x_j)=(\sum{i=1}^n|xi^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}}$
p是>=1的，当p=2时,我们称为欧式距离：
$L_p(x_i,x_j)=(\sum{i=1}^n|xi^{(l)}-x_j^{(l)}|^2)^{\frac{1}{2}}$
当p=1时，我们称为曼哈顿距离
$L_p(x_i,x_j)=(\sum{i=1}^n|x_i^{(l)}-x_j^{(l)}|)$
怎么通俗的理解曼哈顿距离和欧式距离呢
假如你现在想从宿舍去食堂吃饭，你有2种走法第一种就是两点之间线段最近，直接走一条直线，管他有没有障碍物全部都挡不住你，你是电，你是光，你是唯一的神话，这就叫欧氏距离。
还有一种走法就是你肯定得按照学校的规划道路上走，必须在路上，你不能穿墙，上天，入地。所以你可能会有好几种走法，但是都必须在路上走。这种就叫做曼哈顿距离。还有很多种距离，我只介绍这两种。
距离度量的选择可能会影响之后的结果。
K值的选择：
K值的选择会对K近邻法的结果产生重大的影响。
先了解一下什么叫近似误差和估计误差
近似误差：可以理解为对现有训练集的训练误差。
估计误差：可以理解为对测试集的测试误差。
近似误差关注训练集，如果近似误差小了会出现过拟合的现象，对现有的训练集能有很好的预测，但是对未知的测试样本将会出现较大偏差的预测。模型本身不是最接近最佳模型。
如果选择较小的k值，就相当于只有与输入实例较近（相似）的实例才会对预测结果起作用，‘学习’的近似误差会减小，估计误差会增大，如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，K值的减小意味着整体模型变的复杂，容易发生过拟合。
如果选择比较大的k值，就相当于用较多的训练实例进行预测。有点是可以减少学习的估计误差，缺点是学习的近似误差会增大。这时与输入实例较远（不相似）的训练实例也会对预测起作用，使预测发生错误。K值的增大就意味着整体的模型变得简单。
如果K = N(样本总量) ，那么无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类。这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的。
在应用中，k值一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。
分类决策规则
K近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。
KNN的优缺点
优点
1.简单，易于理解，易于实现，无需参数估计，无需训练，既可以用来做分类也可以用来做回归；
2.可用于数值型数据和离散型数据；
3.训练时间复杂度为O(n)；无数据输入假定；
4.对异常值不敏感,kNN不会受到差别特别大的样本中的特征元素的影响(对异常值不敏感)。因为采用了归一化技术。
缺点：
1.计算复杂性高；空间复杂性高；
2.可解释性差，无法告诉你哪个变量更重要，无法给出决策树那样的规则；
3.K值的选择：最大的缺点是当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进;
4.最大的缺点是无法给出数据的内在含义。
5.消极学习方法、懒惰算法。
伪代码
- 计算已知类别数据集中的点与当前点之间的距离（值域越大的变量常常会在距离计算中占据主导作用，需要进行归一化或者标准化处理）；
- 按照距离递增次序排序；
- 选择与当前距离最小的k个点；
- 确定前k个点所在类别的出现概率 ；
- 返回前k个点出现频率最高的类别作为当前点的预测分类。
