KNN 算法-理论篇-如何给电影进行分类

KNN 算法-理论篇-如何给电影进行分类

KNN 算法 的全称是 K-Nearest Neighbor ，中文为 K 近邻 算法，它是基于 距离 的一种算法，简单有效。

KNN 算法 即可用于分类问题，也可用于回归问题。

假如我们统计了一些 电影数据，包括电影名称，打斗次数，接吻次数，电影类型 ，如下：

可以看到，电影分成了两类，分别是动作片和爱情片。

如果现在有一部新的电影A，它的打斗和接吻次数分别是80 和7，那如何用KNN 算法对齐进行分类呢？

我们可以将打斗次数作为 X 轴 ，接吻次数作为 Y 轴 ，将上述电影数据画在一个坐标系中，如下：

通过上图可以直观的看出，动作电影与爱情电影的分布范围是不同的。

KNN 算法 基于距离，它的原理是： 选择与待分类数据最近的K 个点，这K 个点属于哪个分类最多，那么待分类数据就属于哪个分类 。

所以，要判断电影A 属于哪一类电影，就要从已知的电影样本中，选出距离电影A 最近的K 个点：

比如，我们从样本中选出三个点（即 K 为 3），那么距离电影A 最近的三个点是《功夫》，《黑客帝国》和《战狼》，而这三部电影都是动作电影。因此，可以判断电影A 也是动作电影。

另外，我们还要处理两个问题：

关于点之间的距离判断，可以参考文章 《计算机如何理解事物的相关性》 。

至于K 值的选择，K 值较大或者较小都会对模型的训练造成负面影响，K 值较小会造成 过拟合 ，K 值较大 欠拟合 。

因此，K 值的选择，一般采用 交叉验证 的方式。

交叉验证的思路是，把样本集中的大部分样本作为训练集，剩余部分用于穗老预测，来验证分类模型的准确度。一般会把 K 值选取在较小范围内，逐一尝试K 的值，当模型准确度最高时，就是最合适的K 值。

可以总结出， KNN 算法 用于分类问题时，一般的步骤是：

如果，我们现在有一部电影B，知道该电影属于动作电影，并且知道该电影的接吻次数是 7 ，现在想预测该电影的打斗次数是多少？

这个问题就属于 回归问题 。

首先看下，根据已知数据，如何判断出距离电影B 最近的K 个点。

我们依然设置K 为3，已知数据为：

根据已知数据可以画出下图：

图中我画出了一条水平线，这条线代表所有接吻次数是7 的电影，接下来就是要找到距离 这条线 最近的三部（K 为 3）动作电影。

可以看到，距离这条水平线最近的三部动作电影是《功夫》，《黑客帝国》和《战狼》，那么这三部电影的打斗次数的平均值，就是我们预测的电影B 的打斗次数。

所以，电影B 的打斗次数是：

本篇文章主要介绍了 KNN 算法 的基本原理，它简单易懂，即可处理分类问题，又可处理回归问题。

KNN 算法 是基于 距离 的一种机器学习算法，需要计算测试点与样本点之间的距离。因此，当数据量大的时候，计算量就会非常庞大，需要大量的存储空间和计算时间。

另外，如果样本数据分类不均衡，比如有些分类的样本非常少，那么该类别的分类准确率就会很低。因此，在实际应用中，要特别注意这一点。

（本节完。）

推荐阅读：

决策树猜旁升算法-理论篇-如何计算信息纯度

决策树算法-实战篇-鸢尾花及波士顿房价预测

朴素贝叶斯分类启滑-理论篇-如何通过概率解决分类问题

朴素贝叶斯分类-实战篇-如何进行文本分类

计算机如何理解事物的相关性-文档的相似度判断

计算机如何理解事物的相关性-文档的相似度判断

生活中，我们经常会对比两个事物的 相关性 ，也可以叫做 相似度 。

人类会根据自己的经验，很容易的判断两件事物是否相似，或者相似度是多少。那如何让 计算机 也能够进行这样的判断呢？

我们都知道，计算机并没有思维，它只能理解数字。所以，如果想让计算机理解我们现实世界中的事物，必须先把现实事物转换成数字。

空间向量模型假设，任何事物都可以转换成 N 维空间中的一个点 ，这个点称为 向量 ，然后通过计算 向量之间的距离或夹角 ，来判断向量的之间相关性，进而判断事物之间的相关性。

什么是向量

向量代表了事物的特征。

向量是相对标量而言，标量只是单个数字，没有方向性。向量也叫矢量，由一组数字构成，具有方向性。

例如，用下图中的 x 表示向量，其中 n 表示向量的维度：

两个向量所对应的两点之间的距离就是向量的距离，距离可以描述不同向量在向量空间中的差异，也就是现实事物之间的差异。

常用的计算距离的方法有四神漏种：

其中使用最多的是欧氏距离，下面一一介绍。

麦哈顿距离

麦哈祥漏顿距离 可以理解为街道距离，或者出租车距离。

可以看到下图中，从A 点到B 点，不管是走 1线路 还是 2线路 ，距离都是一样的，这个线路的距离就是麦哈顿距离。

二维空间中的两个点 A(x1, x2) 和 B(y1, y2) ，麦哈顿距离的计算公式为：

n 维空间中的两个点 A(x1...xn) 和 B(y1...yn) ，麦哈顿距离的计算公式为：

欧式距离

欧式距离 也叫欧几里得距离，比较好理解，就是直线距离。

如下图，A 点到B 点的直线距离就是欧式距离。

对于二维空间中的两个点 A(x1, x2) 和 B(y1, y2) ，欧式距离的计算公式游宴烂为：

对于 n 维空间中的两点 A(x1...xn) 和 B(y1...yn) ，欧式距离的计算公式为：

切比雪夫距离

切比雪夫距离 可以类比为在方格中走格子，怎样走的格子数最少。

如下图中，从A 格子走到B 格子，先斜线走，再直线走，最终走的 格子数 就是切比雪夫距离。

对于二维空间中的两个点 A(x1, x2) 和 B(y1, y2) ，切比雪夫距离的计算公式为：

上面公式的含义是， ∣x1 − y1∣ 和 ∣x2 − y2∣ 两者的最大者。

对于 n 维空间中的两点 A(x1...xn) 和 B(y1...yn) ，切比雪夫距离的计算公式为：

闵可夫斯基距离

闵可夫斯基距离 也叫做闵氏距离，它并不是一种单独的距离，而是上面三种距离的统一。

对于二维空间中的两个点 A(x1, x2) 和 B(y1, y2) ，闵可夫斯基距离的计算公式为：

对于 n 维空间中的两点 A(x1...xn) 和 B(y1...yn) ，闵可夫斯基距离的计算公式为：

根据 p 取值的不同，闵可夫斯基距离表示不同的距离：

向量也是有大小的，向量的大小就是向量的长度。

向量的长度也叫 向量的模 ，它是向量所对应的 点到空间原点的距离 ，通常使用 欧氏距离 来表示向量的长度。

数学中有一个概念叫做 范数 ，范数常被用来衡量向量的长度。

范数有4 种，分别对应向量的4 种距离：

向量的夹角经常用 余弦值 表示。

对于二维空间中的两个点 A(x1, x2) 和 B(y1, y2) ，余弦的计算公式为：

对于 n 维空间中的两点 A(x1...xn) 和 B(y1...yn) ，余弦的计算公式为：

夹角的余弦取值范围是 [-1, 1] ，那么：

我们可以将向量的距离与夹角展现在同一个 N 维坐标系中，如下：

向量的余弦取值范围是 [-1, 1] ，余弦值越大，表示越相似，正好与相似度成正比。

对于向量之间的距离，通常用 欧式距离 ED表示， ED 越小，表示越相似，与相似度成反比，而且 ED 的取值范围非常大。

所以通常会将欧式距离进行 1/(ED+1) 归一化 处理，用 ED' 表示。 ED' 的取值范围是 [0, 1] ，并且与相似度成正比：

应用空间向量模型的机器学习算法有 K 近邻（KNN）分类、K 均值（K-Means) 聚类 等。

为了让计算机能够判断现实事物的相似度，我们引出了 空间向量 的概念。

下面我们来看如何使用空间向量，来判断 文档相似度 。

比如，现在我们有两个中文句子，要判断这两个句子的相似度：

要想将文档转换成向量，首先需要对文档进行分词。

分词

我们可以使用 jieba 对这两个句子进行分词，结果如下：

可以得到所有词的集合：

计算每个句子的分词的词频：

从而可以得到词频向量：

上文中，我们介绍了，可以通过向量的 距离 或者 余弦夹角 来度量向量之间的相似度。这里我们使用余弦夹角来计算。我们知道 N 维空间的余弦公式为：

从而可以计算余弦夹角为：

可以看到，最终算出的余弦夹角为 0.85 ，比较接近 1 ，说明这两个句子还是很相近的。

本篇文章主要介绍了以下几点：

（本节完。）

推荐阅读：

决策树算法-理论篇-如何计算信息纯度

决策树算法-实战篇-鸢尾花及波士顿房价预测

朴素贝叶斯分类-理论篇-如何通过概率解决分类问题

朴素贝叶斯分类-实战篇-如何进行文本分类