K近邻算法实战——电影分类算法

一、k最近邻算法的原理

简单来说，kNN可以看成：
有那么一堆你已经知道分类的数据，当一个新数据进入的时候，就开始跟训练数据里的每个点求距离，然后挑离这个训练数据最近的k个点看看这几个点属于什么类型，最后用少数服从多数的原则，给新数据归类。

kNN算法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

kNN算法的核心思想 ：如果一个数据在特征空间中最相邻的k个数据中的大多数属于某一个类别，则该样本也属于这个类别（类似投票），并具有这个类别上样本的特性。通俗地说，对于给定的测试样本和基于某种度量距离的方式，通过最靠近的k个训练样本来预测当前样本的分类结果。

kNN算法就是根据距离待分类样本A最近的k个样本数据的分类来预测A可能属于的类别，基本的计算步骤如下：

1. 存在一个样本数据集合，也称为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。
2. 计算待分类数据与训练集中每一个样本之间的距离。
3. 找出与待分类样本距离最近的k个样本。
4. 观测这k个样本的分类情况。
5. 把出现次数最多的类别作为待分类数据的类别

二、k最近邻算法过程详解

举个简单的例子，我们可以使用k最近邻算法分类一个电影是爱情片还是动作片。我们以接吻次数和打斗次数来区分是爱情电影还是动作电影。我们已有的数据集，这个数据集有两个特征，即打斗镜头数和接吻镜头数。除此之外，我们也知道每个电影的所属类型，即分类标签，现在要预测电影5是属于哪个类型的电影（爱情片或动作片），如表3-1所示。

用经验法则粗略地观察：接吻镜头多的是爱情片；而打斗镜头多的是动作片。如果现在给我一部电影，你告诉我这个电影打斗镜头数和接吻镜头数，不告诉我这个电影类型，我可以根据你给我的信息，按经验法则来判断这个电影是属于爱情片还是动作片。而k最近邻算法也可以像我们人一样做到这一点，但k最邻近算法是靠已有的数据来预测的。比如，你告诉我这个电影打斗镜头数为101，接吻镜头数为20，k最近邻算法会提取样本集中特征最相似数据（最邻近）的分类标签，得到的结果取决于数据集的大小以及最近邻的判断标准因素。

我们可以从散点图大致推断，这个坐标为（101, 20）的圆点标记的电影可能属于动作片，因为距离已知的那两个动作片的圆点更近。

k最近邻算法的步骤描述如下：

1. 计算已知类别数据集中的点与当前测试点之间的距离。
2. 按照距离递增次序排序。
3. 选取与当前测试点距离最小的k个点。
4. 确定前k个点所在类别的出现频率。
5. 返回前k个点所出现频率最高的类别作为当前测试点的预测分类。

关于这里的距离度量，这个电影分类的例子有2个特征，也就是2维的，可以使用我们高中学过的两点距离公式（两点距离公式其实就是欧氏距离在二维空间上的公式，也就是欧氏距离n的值为2的情况，欧氏距离也称为欧几里德距离）来计算距离，如图3-3所示。

这样我们得到了样本集中所有电影与未知电影的距离，按照距离递增排序，可以找到k个距离最近的电影。假定k=3，则三个最靠近的电影分别是动作片电影3（108,5）、动作片电影4（115,8）、爱情片电影2（5,89）。在这三个点中，动作片出现的频率为三分之二，爱情片出现的频率为三分之一，所以坐标为（101, 20）的圆点标记的电影类型为动作片。这个判别过程就是k最近邻算法。

三、kNN算法的注意事项

1. k值的选取

• 如果当k的取值过小时，一旦有噪声的成分存在，将会对预测产生比较大的影响，例如取k值为1时，一旦最近的一个点是噪声，那么就会出现偏差，k值的减小就意味着整体模型变得复杂，容易发生过拟合（在训练集上准确率非常高，而在测试集上准确率低），而忽略了数据真实的分布。
• 如果k的值取得过大时，就相当于用较大邻域中的训练实例进行预测，学习的近似误差会增大，这时与输入目标点较远的实例也会对预测起作用，使预测发生错误。k值的增大就意味着整体的模型变得简单，比如如果k=N（N为训练样本的个数），那么无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类。这时相当于你压根就没有训练模型，直接拿训练数据统计了一下各个数据的类别，再找最大的类别而已！
• 所以说k值既不能过大，也不能过小（也就是说，选取k值的关键是实验调参）。k的取值尽量要取奇数，以保证在计算结果最后会产生一个较多的类别，如果取偶数则可能会产生相等的情况，不利于预测。

2. 距离的度量

（1）欧氏距离

欧式距离其实就是应用勾股定理计算两个点的直线距离。二维空间的公式，如图3-4所示，P为点(x2,y2)与点(x1,y1)之间的欧氏距离，|x|为点(x2,y2)到原点的欧式距离。

同理，N维空间的公式，如图3-5所示。

（2）曼哈顿距离

曼哈顿距离就是表示两个点在标准坐标系上的绝对轴距之和。如图3-6所示，折线A代表曼哈顿距离，线段C代表欧氏距离，也就是直线距离，而折现B和折现D代表等价的曼哈顿距离。曼哈顿距离就是两个点在南北方向上的距离加上在东西方向上的距离，即$d(i,j)=|x_i$