「埃尔法哥哥」kNN分类算法及其python实现

0引言
分类是人类时时刻刻在做的事情，比如我们收拾孩子的玩具的时候，需要辨认哪个是“玩沙子套装”的成员、哪些是图书，然后分类存放。
一些比较懒的人，希望让生活中尽量多的事情自动化。比如一个哥们，构建了一个分类装置，将两吨的乐高积木按照颜色、形状做了分类。分类装置的核心是一个训练好的神经网络。分类算法在生产和生活里的用处不止于此。
神经网络挺好的，本文介绍一下k最近邻算法（k-Nearest neighbor,kNN）。 kNN是我确信自己学明白的第一个分类算法，它非常简单。
1kNN分类算法简介
1.1kNN分类算法的思想
kNN算法认为，具体的事物之间存在一定的相似性。举个例子，假设我和一只大熊猫的相似度是s1 ，我和赵本山的相似度是s2 。除非大家抬杠，综合身高体重毛发等等特征，我和本山大叔显然更相似，即 s1
kNN算法认为，如果一个待分类样本，与类别(假设是A类)的代表性样本最像，相似程度超过了其他类别的代表性样本，那么，我们可以判定待分类样本的类别为A 。
当然，实际操作的时候，我们用“距离”的远近来表示相似程度的大小：距离越远，相似度越低；距离越近，相似度越高。
1.2kNN算法的最简单形态-NN算法
假设我们要将10000个生物分为(人类，动物)两类，如果用最近邻算法(Nearest neighbor, NN)来完成这个任务，步骤是:(1)请专家挑选1个人类(A类) ，1个动物(B类)；(2)对于第i个生物，我们计算它与那个人类的距离，以及它与那个动物的距离，然后看那个距离更小，对应的类别就是这个生物的类别;(3)重复(2)步，直到对所有生物分类完毕。
前面我们用纯语言的方式描述这个算法，对一些人比较合适，接下来用图形介绍一下，如图1-1 。分类器会计算我离赵本山更近一点，还是离大熊猫更近一点，然后以离我更近的赵本山的类别，作为我的类别。
有的人看图学得快，有的人看文字学得快，有的人看公式学得快，大家平时可以注意一下哪种是最适合的。后面我们会有公式。

本文插图
图1-1 最近邻分类器判断我是人类还是动物
1.3kNN分类算法的完整形态
1.2讲的分类器比较简单，只找了本山大叔和大熊猫作为分类依据，现在我们看完全体的kNN 。我们请专家找4个人类， 4个动物分别作为AB两类的代表性样本，如图1-2 ，这样既可以构建一个4-NN分类器。是的， kNN中的“k”是一个整数，它代表了我们选取的代表性样本的个数。
这一次，分类器需要计算我和赵本山等的平均距离，以及我和大熊猫组合的平均距离。我和前者的距离更小，因此我属于A类。

本文插图
图1-2 4NN分类器
问题来了，前面这些相似度都是捏造的，实际生产中我们应该如何计算距离呢？
1.4距离的计算
1.4.1特征工程
计算相似度，我们需要解决两个问题:（1）构造特征；（2）制定距离计算方式。
构造特征是一项高难度的任务，这里简单做。我们选择生物的(身高，体重，尾巴长度)这3个易测量的尺寸或者重量，作为特征。具体(伪造)取值情况如表1-1 。
表1-1 训练集特征取值情况

本文插图
1.4.2欧氏距离
我们用欧氏距离来的来计算样本i和样本j之间的距离: