机器学习笔记--K-近邻算法（一）

机器学习实战这本书的例子很多也很好，问题导向型的，所以例子也是循序渐进。如果真要读懂，一遍是不够的，特别是我这种渣。其实写机器学习实战笔记的同时，我都或多或少的参考了《机器学习与R语言》这本书，相互借鉴，看看同样的问题表述，两者有什么区别。

1. K-近邻算法的概述

简单地说，K-近邻算法采用测量不同特征值之间的距离方法进行分类。–《机器学习实战》

“物以类聚，人以群分”，相似的东西很有可能具有相似的属性。
近邻分类器就是把无标记的案例归类为与它们最相似的带有标记的案例所在的类。–《机器学习与R语言》

k-近邻算法
优 点 ：精度高、对异常值不敏感、无数据输入假定。
缺点：计算复杂度高、空间复杂度高。–《机器学习实战》

kNN算法（K-Nearest Neighbor）
优点：简单有效；对数据分布没有要求；训练阶段很快。
缺点：不产生模型，理解特征与类如何相关能力有限；需要选择一个合适的K；分类阶段很慢；名义变量(特征)和缺失数据需要额外处理。–《机器学习与R语言》

单从对k-近邻的概述，我就发现《机器学习实战》走的是高端路线，对于初学者如果连概念都不熟的话，读起来还是比较费劲的。《机器学习与R语言》走的是平民化路线，通俗易懂，简单粗暴，特别是在指出缺点-选择一个合适的k值，直接点出了KNN算法的一个难点和要改进算法需要注意的地方。“物以类聚，人以群分”这句话也很赞，直接点明kNN就是一个分类器。先看《机器学习与R语言》这本书，对理解《机器学习实战》有很大的帮助，而且两者的例子很相近，也都是问题导向型的。（坏人死于话多，话太多了）

书中举了举了电影分类的例子，一句话就是一部电影接吻远比武打多就是爱情片，反之就是武打片。

2.距离的算法

距离的度量有两种算法：欧式距离( Euclidean distance)和曼哈顿距离(manhattan distance)。欧式距离：两点间的直线距离。曼哈顿距离，就是基于一个人在城市街区步行所采取的路线。
传统上，KNN算法采用的是欧式距离。

3.选择一个合适的k

未标记的案例与已标记的案例分别计算出所有n个的距离，从中选出距离最短的K个，通过采用投票的方法，即多数原则，将未标记案例进行分类。选择一个大的K会减少噪声数据对模型的影响或者减少噪声导致的模型波动，但它会使分类器产生偏差，比如它有忽略不易察觉但很重要模式的风险。

假设采取极端的情况，即K值选择等于所有训练集。由于每一个训练案列都有在最后投票表决的机会，因此不管哪个邻居是最近的选出来的都是总体的大多数。相反，假如我们选择k值为1，会使得噪声数据或者异常值过度影响案例的分类。例如假设训练案例被意外地贴错了标签，且这个错误标签恰好又是和另外一些无标记的标签是最接近的，那么它将会导致错误的分类。

一般来说，k值的选取是从等于训练集数量的平方根开始的，即大于等于训练集的平方根。另外一种方法就是基于测试集来测试多个k值，找出最适合模型的k值。有许多的KNN的实现则是选择了一种权重投票的方法，即认为较近邻的投票比远邻的投票更具权威，比重越大。

4.对特征值数据的处理

距离公式高度依赖于特征是如何被度量的。特别地，如果某特征值比其他特征值具有更大的范围值，那么距离的度量就会被这个具有较大范围的特征所支配。比如：食物的辣度是0到超过100万，而甜度、脆度只有0到10，这会使得辣度对距离函数的影响水平远远超过甜度和脆度，就会发现距离度量只能通过辣度加以区分，而甜度、脆度就显得相形见绌。

所以，很有必要对特征值进行重新调整。传统的方法时采用min-max标准化。

另外一种常见的变换为Z-分数标准化。下面的公式是减去特征X的均值后，再除以X的标准差：

5.KNN-懒惰学习
kNN是高度依赖训练实例而不是一个抽象的模型，它仅仅是一字不差地存储训练数据，固也称是基于实例的学习或者机械学习

应用的领域有：
计算机视觉应用，包括在静止图像和视频中光学字符的识别和面部识别
预测一个人是否喜欢推荐的电影和音乐
识别基因数据的模式，或许使用它们可以检测特定的蛋白质和疾病。