机器学习-13：MachineLN之kNN
你要的答案或许都在这里：小鹏的博客目录
我想说
其实训练模型是个力气活，有人说训练模型很简单，把数据塞进去，然后跑完就好了，哦，这样的话谁都会，关键的也就在这里，同样的数据同样的模型，有些人训练的模型在测试集上99%，有些人的则只有95%，甚至90%，其实学习最关键的也在这里，大家同时学一个知识，也都学了，但是理解的程度会大相径庭，注意trick不可不学，并且坑不得不踩。唉，前几天训练好的一个模型，再让自己复现感觉也很难搞定了，天时地利人和！！！今天开始搞传统机器学习的理论和实践，突然发现这是自己的短板，其实也不是啦：李航老师统计学看了4遍，周志华老师机器学习看了一遍，模式分类那本大厚书粗略看了一遍，经典的数据挖掘看了一遍，还看了一本机器学习的忘记名字了，吴恩达的课看了一遍，还看了一些英文资料，机器学习实践照着敲了一遍，在就是一些零零碎碎的.....，虽然做过一些实践，但是缺乏工程上的磨练。
1. kNN介绍
kNN（K Nearest Neighbor）：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征相似数据（最近邻）的分类标签，一般来说我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中的k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
看一下下图：x是未知类别的，计算与w1，w2，w3相似度（距离），下图是取5个（k个）最相似的数据，然后从5个中选择出现次数最多的类别，作为x的类别。
其实，k值的选择至关重要，看下图，不宜太小不宜太大：
2. kNN中相似度量方法：
上面提到的相似度（还有推荐中的相似度），很多时候都是用距离来衡量，计算距离的方法有：
- 闵氏距离 两观测点x和y间的闵氏距离是指两观测点p个变量值绝对差k次方总和的k次方根：
- 欧式距离 两观测点x和y间的欧式距离是指两观测点p个变量值绝对差平方总和的平方根：
可以看出，欧式距离是闵氏距离在k=2时的特例。
- 绝对(曼哈顿)距离 两观测点x和y间的绝对(曼哈顿)距离是指两观测点p个变量值绝对之差的总和：
可以看出，绝对(曼哈顿)距离是闵氏距离在k=1时的特例。
- 切比雪夫距离 两观测点x和y间的切比雪夫距离是指两观测点p个变量值绝对之差的最大值：
可以看出，切比雪夫距离是闵氏距离在k=无穷大时的特例
- 夹角余弦距离
可以看出夹角余弦距离是从两观测的变量整体结构相似性角度测度其距离的。夹角余弦值越大，其结构相似度越高。
当然除了以上的相似度量方法还有很多，马氏距离、交叉熵、KL变换等，都是可以衡量相似度的方法，但是要注意在什么情境用什么方法；
3. 注意的问题：
实际应用中，p个维度（特征）之间可能存在数量级的差异（这里也体现了数据归一化的重要性），数量级较大的维度对距离大小的影响会大于数量级小的变量。为了消除这种影响，统计学中常见的方法有标准分数法和极差法(有的称为极大-极小值法)。
- 标准分数法：
- 极差(极大-极小值法)法：
另外，很多时候是这么做的，例如在DL中我们用CNN提取的特征作为kNN的样本；或者更传统一点，可以通过PCA降维后的结果作为kNN的样本；可以减少维度灾难；鄙人缺少此方便实战经验，写起来比较晦涩；
4. kNN的优缺点
KNN的优缺点：
- 优点： 1、思想简单，理论成熟，既可以用来做分类也可以用来做回归； 2、可用于非线性分类； 3、训练（计算时间）时间复杂度为O(n)； 4、准确度高，对数据没有假设，对outlier不敏感；
- 缺点： 1、计算量大（样本量大）； 2、样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）； 3、需要大量的内存；
5. 一些思考：
- 一个是机器学习，算法基本上都比较简单，最难的是数学建模，把那些业务中的特性抽象成向量的过程，另一个是选取适合模型的数据样本。这两个事都不是简单的事。算法反而是比较简单的事。
- 对于KNN算法中找到离自己最近的K个点，是一个很经典的算法面试题，需要使用到的数据结构是“较大堆——Max Heap”，一种二叉树。你可以看看相关的算法。
下一遍： kNN实践 python代码+详细注释
推荐阅读：