K-最近邻算法

1.算法介绍

属于有监督学习，知道可能的结果。属于多分类算法。K NearestN eighbors算法又叫K - NN算法，这个算法是机器学习里面一个比较经典的算法，总体来说K - NN算法是相对比较容易理解的算法。十大机器算法之一。

来源：算法最早是由Cover和Hart提出的一种分类算法

两个样本的距离可以通过如下公式计算，又叫欧式距离 ，关于距离公式会在后面进行讨论。

K - NN针对于离散型分类目标的一种非线性多分类的，基于加权距离的最大投票方案算法，公式（应用型的公式，理解即可。）如下:

K - NN针对于连续型回归目标，预测值是所有k个最近邻域数据点到预测据点的加权平均，公式如下:

K值选择问题，李航博士的一书统计学习方法上所说：

1）选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂(指的是数值发生一点点改变，分类结果就不相同了，模型的泛化性不佳)，容易发生过拟合；
2）选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
3）K=N（N为训练样本个数），则完全不足取，因为此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单，忽略了训练实例中大量有用信息。

如果有五个A 一个O在中间四个B

A A A       A A O B B                                     B B B B

K=4的时候，分不了AB
可以用
混乱
那么我们选5，类别结果是A

如果出现了c

A A A       A A O B B  c c                                B B B B

k = 3+1不太稳妥
k = 3+2
···
现在数据量很小，数据量大的时候一般k=3就可以了完全足够了