数模系列（5）：k近邻算法（k-Nearest Neighbors

1. 引子：近朱者赤,近墨者黑

1.1. 先来瞎扯扯

有一阵子没有更新《数模系列》了，自从上次的更新之后，我一直在看一些机器学习方向的专业书和视频。（书主要以周志华的西瓜书和Peter Harrington 的 Machine Learning in Action《机器学习实战》为主，视频主要以林轩田和NG的课程为主。）

由于以前参加过几次数模的比赛，自己的专业方向叫做计算数学，所以看一些算法理论的知识速度上相对比较快，这方面倒还好点。时不时的会在书里面看到以前认识的一些“老朋友”，和他们再一起坐下来聊聊天不费力。但是算法的实现这一块就比较麻烦且繁琐了，大部分写过代码的人都应该有体会，有个段子就是某个程序员说道“这个破算法看着很简单啊，我明天就能实现”，但实际上实现的时间总是要往后再推。

机器学习现在之所以这么火，正是因为它的的确确能应用到生活当中，而并不是因为它的理论，因此算法实现的地位还是相当重要的。《机器学习实战》一书中以Python 用到了很多例子，且写得通俗易懂。以后的《数模系列》除了自己以前的一些笔记之外，还会穿插这本书里面的算法及其实现。

我用的开发环境是Windows 10 + Anaconda 3 + Pycharm，因为该书的代码使用的是Python2，和Python3 还是有些区别的，我将代码实现的所有文件全都放到了我的GitHub 上：

https://github.com/lizhimushui/Machine-learning-in-action

这一期的主角是一个非常简单的算法——k近邻（k-Nearest Neighbors, 简称kNN），其代码链接如下：

https://github.com/lizhimushui/Machine-learning-in-action/blob/master/knn/kNN.py

1.2. 红与黑

“近朱者赤，近墨者黑”的意思很明白，其实也就是物以类聚，人以群分。

图1：你是红还是黑？

掌握了这句话，其实也就掌握了k近邻算法的核心思想。比方说把这个世界上的人分成了“朱子”和“墨子”两大类，现在我想看看自己属于哪一类，我拿了一个叫做“k近邻”的算法过来，看到它的使用说明如下：

1. 挑选一个数字k；

2. 按顺序列出你身边和你走的最近的k个人；

3. 依次数数着这k个人都是哪一种人，其中人数最多的一类就是答案。

假如你身边的k个人中，“朱子”和“墨子”的人数一样，那就看你自己的偏好吧，可以再在算法中进一步的细化。同理，如果你想给跟你走得更近的人的权重更大，也可以再对这个原始的算法进行改进。

2. k近邻步骤详解（结合相亲网站实例）

k近邻算法是一个解决分类问题的简单机器学习方法。它甚至都没有训练模型的过程，是惰性学习（lazy learning）的典型代表。

现在来看一个实例，某个“大龄剩斗士”每天逛着相亲网站，浏览了很多相亲对象的简历，会标记上“不感兴趣”，“可能感兴趣”和“很感兴趣”。现在相亲网站本着“红娘”的热心要给这个“大龄剩斗士”推荐他还没有标记的其他人，希望能尽可能的符合其口味。

2.1. 数据预处理：无量纲化

m个特征的单位不一，大小范围也很有可能不一致，如果不事先对这些特征数据进行预处理，这对后面计算距离矩阵会造成极大的困扰。标准化的办法也有很多，一般较为常用的分为正态标准化和极差标准化。

在相亲网站的实例中，包含3个特征，分别为“每年获取的飞行常客里程数”，“玩视频游戏所耗时间百分比”和“每周消费的冰激凌公升数”。 这个“单身人士”标记了1000个样本，为“不感兴趣”，“可能感兴趣”和“很感兴趣”。

既然只有3个特征，将原始数据经过极差标准化之后，我们将其可视化一下。画出三维图如下：

（图是利用Python的matplotlib库画的，其中中文和负号的显示问题的解决，我写在了知乎的文章中：

https://zhuanlan.zhihu.com/p/32981102

有需要的话， 可以去设置下“一劳永逸”的解决办法。）

图2：相亲网站三维散点图

旋转之后，发现三维图 好像从上往下看分类效果不错，我们再贴个二维图如下：

（ 其实到底选哪些特征好呢，虽然只有3个维度，但也可以考虑这个数模系列的第2期更新的主成分分析法PCA试试，或者可以采用方差分析的方法看看这些指标对于结果的贡献程度。）

图3：相亲网站二维散点图

2.2. 计算与样本矩阵的距离

在相亲网站的实例中，还未被标记标签的某个人的简历如下。其原始数据为每年获取的飞行常客里程数为10000 km，玩视频游戏所耗时间百分比为10%，每周消费的冰激凌公升数为0.5公升。经过极差标准化后的数值分别为0.10956，0.478，0.2944。 其与1000个样本集的欧氏距离按上述公式计算好即可，由于计算得出的结果向量有1000 维，此处就不贴结果了。

(在我的Pycharm上，版本是Pycharm社区版2017.3.2，控制台使用input() 函数键入数据竟然不行，在知乎上和Pycharm社区都提了问，具体问题描述如下：

https://www.zhihu.com/question/265683209

最后在Pycharm社区得到了回答，结果居然是这个社区版的bug，控制台的input() 函数只能暂时不用了，如果需要用再装别的版本，这里分享下，如果可以帮助到其他有此问题的人那就再好不过了。)

2.3. 对距离进行排序，取距离最近的前k个样本

将结果向量d按照升序进行排列，得到向量dsort。取出dsort的前k 个值所对应的样本。

在实例中，我们取k的值为3，dsort的前3个值对应的样本依次是707号样本，765 号样本，288 号样本。

2.4. 统计k个样本的分类情况，返回最多的分类情况

对前k个样本对应的标签种类进行统计，也就是这k个样本对结果进行投票，最后返回统计后最多的标签作为结果。

在我们的例子中，707号样本对应的是“可能感兴趣”，765号样本对应的也是“可能感兴趣”，288号样本是“很感兴趣”，所以2 票胜出1 票，返回对于这个人的标签预测结果是“可能感兴趣”。

3. 无关内容

这期的最后，把王国维的读书三境界贴上来分享下。王国维在《人间词话》说：“古今之成大事业、大学问者，必经过三种之境界：‘昨夜西风凋碧树，独上高楼，望尽天涯路’。此第一境也。‘衣带渐宽终不悔，为伊消得人憔悴。’此第二境也。‘众里寻他千百度，蓦然回首，那人却在灯火阑珊处’。此第三境也。”

虽然这里面说的是成大学问者，但是其实读书也是一样的。第一层境界是我找到了我想要看的神书，打开目录，对我即将要看的内容有个大概了解，甚至给自己一些不知从哪来的盲目的自信心。第二层境界细细啃读书里面的内容，甚至有些因此而自愿的“废寝忘食”。第三层境界是看完书后，合上书本，或者自己静思，或者外人外物的不经意间的提示，你把脑门一拍，会心一笑。

下期更新的主角就是方差分析吧！