机器学习-K近邻算法（KNN）
一.基本思想
K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分类到这个类中。如下面的图：
通俗一点来说，就是找最“邻近”的伙伴，通过这些伙伴的类别来看自己的类别。比如以性格和做过的事情为判断特征，和你最邻近的10个人中（这里暂且设k=10），有8个是医生，有2个是强盗。那么你是医生的可能性更加大，就把你划到医生的类别里面去，这就算是K近邻的思想。
KNN做回归和分类的主要区别在于最后做预测时候的决策方式不同。KNN做分类预测时，一般是选择多数表决法，即训练集里和预测的样本特征最近的K个样本，预测为里面有最多类别数的类别
1. K值选择,距离度量,分类决策规则是K近邻法的三个基本要素.
KNN算法我们主要要考虑三个重要的要素，对于固定的训练集，只要这三点确定了，算法的预测方式也就决定了。这三个最终的要素是k值的选取，距离度量的方式和分类决策规则。
对于分类决策规则，一般都是使用前面提到的多数表决法。所以我们重点是关注与k值的选择和距离的度量方式。
对于k值的选择，没有一个固定的经验，一般根据样本的分布，选择一个较小的值，可以通过交叉验证选择一个合适的k值。
选择较小的k值，就相当于用较小的领域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是泛化误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
选择较大的k值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
一个极端是k等于样本数m，则完全没有分类，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单。
对于距离的度量，我们有很多的距离度量方式，但是最常用的是欧式距离，即对于两个n维向量x和y，两者的欧式距离定义为：
大多数情况下，欧式距离可以满足我们的需求，我们不需要再去操心距离的度量。
当然我们也可以用他的距离度量方式。比如曼哈顿距离，定义为：
更加通用点，比如闵可夫斯基距离(Minkowski Distance)，定义为：
可以看出，欧式距离是闵可夫斯基距离距离在p=2时的特例，而曼哈顿距离是p=1时的特例。
KNN的主要优点有：
1） 理论成熟，思想简单，既可以用来做分类也可以用来做回归
2） 可用于非线性分类
3） 训练时间复杂度比支持向量机之类的算法低，仅为O(n)
4） 和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感
KNN的主要缺点有：
1）计算量大，尤其是特征数非常多的时候
2）样本不平衡的时候，对稀有类别的预测准确率低
3）KD树，球树之类的模型建立需要大量的内存
4）使用懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢
从K近邻的思想可以知道，K近邻算法是离不开对于特征之间“距离”的表征的，至于一些常见的距离
一.明可夫斯基距离(Minkowski Distance)
有两个n维的点，他们之间的明可夫斯基距离的定义为：
你会发现这个式子和p-范数的形式很像。比如对于一个向量x，他的p-范数为：
所以，要是在一些论文里面明可夫斯基距离写成下面的式子，也别感到奇怪：
注意：
说可夫斯基距离是一个距离，还不如说他是一类距离的定义，因为p值是可以变的，因为p值的不同，可以得到欧氏距离，曼哈顿距离，和切比雪夫距离等等。
Ⅰ.曼哈顿距离
p=1的时候，就称之为曼哈顿距离
Ⅱ.欧氏距离
欧式距离用的是不是最多不知道，但是绝对是最熟悉的一种距离表示形式。从小就开始接触的形式。 p=1的时候，就称之为曼哈顿距离
Ⅲ.切比雪夫距离
p→∞的时候，就称之为曼哈顿距离
总结：
闵可夫斯基距离比较直观，但是它与数据的分布无关，具有一定的局限性，如果 x 方向的幅值远远大于 y 方向的值，这个距离公式就会过度放大 x 维度的作用。
二.余弦距离
在几何中，夹角余弦能够衡量两个方向之间的差异，那么这种差异也能够用在机器学习里面。
夹角余弦取值范围为[-1,1]。夹角余弦越大表示两个向量的夹角越小，夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1，当两个向量的方向完全相反夹角余弦取最小值-1