K近邻算法（KNN）
k近邻算法
k近邻(k-nearest neighbor,KNN)是一种基本的分类与回归算法。于1968年由Cover和Hart提出。k近邻的输入是实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。k近邻算法假设给定一个训练数据集，其中的实例类别已定，分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测。因此，k近邻法不具有显式的学习过程。简单的说，给定一个训练数据集，对新的输入实例，在训练集中找到与该实例最近邻的k个实例，这k个实例的多数属于哪个类，就把该输入实例分为这个类。这就是k近邻算法中k的出处，通常k是不大于20的整数。
k近邻算法的三个基本要素：k值的选择、距离度量、分类决策规则
k近邻算法步骤：
对未知类别属性的数据集的每个点依次执行以下操作:
（1） 计算已知类别数据集中的点与当前点之间的距离；
（2） 按照距离递增次序排序；
（3）选取与当前点距离最小的k个点；
（4）确定前k个点所在类别的出现频率；
（5）返回前k个点所出现频率最高的类别作为当前点的预测分类
k近邻算法总结
优点：
1. 简单、有效、精度高；
2. 对离群值不敏感；
3. 无数据输入假定；
4 .可用于数值型数据和离散型数据；
缺点:
1. 计算复杂度高、空间复杂度高；
2. 样本不平衡问题（即有的类别的样本数量很多，而其它类别的样本数量很少），影响分类效果；
3. 一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少 ，否则容易发生误分；
4. 最大的缺点是无法给出数据的内在含义，无法给出任何数据的基础结构信息，无法知晓平均实例样本和典型实例样本具有什么特征。
注意事项
1. K值的设定
较小的k值，学习的近似误差减小，但是估计误差会增大，意味着整体模型变得复杂，容易过拟合。
较大的k值，学习的近似误差增大，但是估计误差会减小，意味着整体模型变得简单。
在应用中k值一般取一个比较小的数值。采用交叉验证选取最优的k值。
2.优化改进
在确定最终的类别时，不是简单的使用多数表决投票，而是进行加权投票，距离越近权重越高。
k近邻法中，当训练集、距离度量、k值和分类决策规则确定后，其结果唯一确定。
k近邻法的实现需要考虑如何快速搜索k个最近邻点。kd树是一种便于对k维空间中的数据进行快速检索的数据结构。