机器学习系列——KNN算法（上）

0. 写在前面

“百折千坎终成忆，千呼万唤始出来”，这可能就是我目前的心理写照吧（虽然这里篡改了原诗）！今天终于要迎来改名之后的第一篇正式主题文章了，想到这里，笔者都有一些小激动。正如上一篇文章中所说的那样，今天笔者将和各位大大谈谈机器学习中的KNN算法（中文也称之为K-近邻算法），这个算法应该是机器学习之中运用最为频繁的算法之一了，当然这个算法也是如今最著名的十大算法之一，笔者将通过三篇文章对KNN进行介绍。

在正式开始之前，先对本文所采用的分析环境以及数据进行介绍：

windows7操作系统

python3

sublime Text3编辑器

ipython命令行

数据请到https://github.com/TinyPrince/Machine-Learning/tree/KNN下载。

1. KNN算法简介

KNN算法是1967年由Cover T和Hart P提出的一种基本分类与回归方法。它的工作原理是：存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。如下图所示：

这里我们以电影分类为例来粗略地了解一下KNN算法的基本流程，表1中给出了一些电影的特征以及相关的电影类型分类。

表中给出了7部影片，每部影片有两个属性值以及一个分类标签，其中六部影片均有明确的分类标签，而最后一部影片仅具有属性值而没有分类标签，这里就是要以KNN算法给出最后一部影片的分类。表格中的六部影片就是我们谈及到的训练样本集，笔者就是要通过判断待分类影片与训练样本集的关系从而得出其分类。而这种关系就是计算未知电影与训练样本集中其它影片的距离，我们这里依据欧几里得距离公式求得未知电影与训练集中各样本的距离，如表2所示。

现在得到了已知电影与未知电影之间的距离，然后按照距离的大小进行升序排列，从而可以得出k个距离最近的电影。当k=1时，KNN算法也被称之为K最近邻算法，但是一般在选择时都不会令k=1，一般会选择k=log(N)，其中N为训练样本集样本数，log()为自然对数。我们这里选择k=2，因此距离未知电影最近的两部电影为He's Not Really into Dudes以及Beautiful Woman，而这两部电影的类型均为爱情片，因此我们可以判断得出未知影片亦为爱情片。这就是KNN算法的核心，首先得出未知样本与训练样本之间的距离，然后选择出前K个距离最近的样本，接着判断这K个样本中的类别占比，最后选择占比最高的类别作为未知样本的类别划分。

2. KNN算法的Python程序

上文对KNN算法进行了简要介绍，指明了KNN算法的核心逻辑以及算法过程，下面笔者将使用Python程序去构建KNN算法。这里说明一点，机器学习系列文章不将对python的使用语法进行详细介绍，所以对于Python不清楚的朋友可以参考笔者今后的Python系列文章或者可以参考Python基础教程与Python学习手册等方面的书籍。

2.1 使用Python创建训练数据

这里我们以电影分类中的数据为例来展示如何使用Python创建数据集，因为我们只有六部电影作为训练数据，因此只需要创建六项记录。代码如下：

这样我们便对六部影片进行了数字化，为了检验我们创建的数据是否正常，只需要在在创建了函数之后使用以下命令，便可以检验我们的数据集是否已经创建成功。

如果创建成功，我们会看到以下数据展示：

为了更直观有趣的观察数据，我们可以将数据进行可视化，运行下面命令：

2.2 实施KNN分类算法

一段好的程序编写离不开程序编写之前的合理规划，我们这里再一次梳理一下我们为了达到分类目标需要逐步执行的过程（切记，程序就是过程，所以编写程序之前一定要了解你的任务的处理过程）：

计算已知类别数据集中的点与未知点之间的距离；

按照距离对数据集进行递增排序；

选取距离值最小的K个点；

确定前K个点所在类别出现频率；

返回前K个点出现频率最高的类别作为未知点的预测分类。

程序清单：KNN算法Python程序

函数classfication便是笔者所编写的KNN分类函数，这个函数的运行需要四个参数：第一个参数TargetData为待分类样本向量；第二个参数RefDataSet为训练数据集的属性数据；第三个参数labels为训练数据集的分类标签，切记第三个参数labels和第二参数RefDataSet的行数一致；第四个参数k为最近邻数目。

下面我们便可以采用这个分类函数对未知样本进行预测了，这里我们输入未知电影的属性数据，来确定未知电影的分类，我们得到：

这与我们在上文中得出的结论一致，因此说明了我们的分类程序得到了很好的运行，至此，我们已经完成了KNN分类算法的设计。

3. 后记

在文章的主体中笔者已经对KNN算法进行了介绍和程序编写，这部分主要对距离计算公式进行一些说明以及对于下期文章进行介绍。

对于距离的计算，一直以来存在两种比较流行的算法，一种是欧几里得距离，另外一种就是曼哈顿距离。各位大大可能对欧几里得距离比较熟悉，而对于曼哈顿距离缺少认知，这里对这两种距离计算进行一下补充说明。

对于距离计算的更多细节可自行百度，这里不再详谈！KNN算法中使用的距离计算公式为欧几里得距离计算公式。

终于写完了这期的文章，本期文章是KNN算法的第一篇文章，后续还有两篇文章，这篇文章主要是从理论以及算法本身上进行介绍，后面两期文章将对KNN算法的一些实践运用进行说明。下期文章笔者将讲一讲KNN算法是如何用来进行约会配对的（相信各位大大对此应该比较期待吧）