【有书共读07】《算法图解》第10章 K最近邻算法笔记

第10章  K-最近邻算法

这学期学python的时候，有幸python老师也给我们讲解了一下这个k-最近邻算法，只能说了解了下吧，现在做点小小了解的笔记。

在机器学习中经常要用到分类算法，在很多的分类算法中有一种算法就是是k-最近邻算法，也称为kNN算法。

一、K-最近邻算法的工作原理

官方解释：存在一个样本数据集，也称作训练样本集，并且样本中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系，输入没有标签的新数据后，将新数据的每个特征与样本集中的数据对应的特征进行比较，然后算法提取样本集中特征最相似的数据（最近邻）的分类标签。一般来说，我们只选择样本集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数，最后，选择k个最相似的数据中出现次数最多的分类，作为新数据的分类。

我的理解：k-近邻算法就是根据“新数据的分类取决于它的邻居”进行的，比如邻居中大多数都是退伍军人，那么这个人也极有可能是退伍军人。而算法的目的就是先找出它的邻居，然后分析这几位邻居大多数的分类，极有可能就是它本省的分类。

二、适用情况

优点：精度高，对异常数据不敏感（你的类别是由邻居中的大多数决定的，一个异常邻居并不能影响太大），无数据输入假定；

缺点：计算发杂度高（需要计算新的数据点与样本集中每个数据的“距离”，以判断是否是前k个邻居），空间复杂度高（巨大的矩阵）；

适用数据范围：数值型（目标变量可以从无限的数值集合中取值）和标称型（目标变量只有在有限目标集中取值）。

三、算法实例及讲解

距离计算

基于向量空间的欧几里得距离的计算。（L2距离）

特别情况下可采用Lp距离（明氏距离） L1距离。

简单点来说就是 在一个具有大量样本集中，每一个实例都具有3个或以上的特征属性，其中有一个属性必然是分类属性，其余属性为数值型属性（即使是标称型属性，也可以通过 某些方法转变过来），每一个实例都是由属性特征值组成的一个向量，一个样本集就是多个向量组成。

例如下面这个例子

“”性别“”可以看成是一个分类属性，然后其他看特征属性 ，组成一个实例向量就为 [170,140,22]和[160,100,21]

算法步骤：
1、计算已知类别数据集中的点与当前点之间的距离；
2、按照距离递增次序排序；
3、选取与当前点距离最小的k个点；
4、确定k个点所在类别的出现频率；

（K用于选择最近邻的数目，K的选择非常敏感。K值越小意味着模型复杂度越高，从而容易产生过拟合；K值越大则 意味着整体的模型变得简单，学习的近似误差会增大，在实际的应用中，一般采用一个比较小的K值，用交叉验证的 方法，选取一个最优的K值。）
5、返回前k个点出现频率最高的类别作为当前点的预测分类

橙子还是柚子

请看下边的水果，是橙子还是柚子呢？我知道，柚子通常比橙子更大、更红。

我的思维过程类似于这样：我脑子里有个图表。

一般而言，柚子更大、更红。这个水果又大又红，因此很可能是柚子。但下面这样的水果呢？

如果判断这个水果是橙子还是柚子呢？一种办法是看它的邻居。来看看离它最近的三个邻居。

在这三个邻居中，橙子比柚子多，因此这个水果很可能是橙子。祝贺你，你刚才就是使用K最近邻（k-nearestneighbours，KNN）算法进行了分类！这个算法非常简单。

KNN算法虽然简单却很有用！要对东西进行分类时，可首先尝试这种算法。下面来看一个更真实的例子。

创建推荐系统

假设你是Netflix，要为用户创建一个电影推荐系统。从本质上说，这类似于前面的水果问题！

你可以将所有用户都放入一个图表中。

这些用户在图表中的位置取决于其喜好，因此喜好相似的用户距离较近。假设你要向Priyanka推荐电影，可以找出五位与他最接近的用户。

假设在对电影的喜好方面，Justin、JC、Joey、Lance和Chris都与Priyanka差不多，因此他们喜欢的电影很可能Priyanka也喜欢！

有了这样的图表以后，创建推荐系统就将易如反掌：只要是Justin喜欢的电影，就将其推荐给Priyanka。

特征抽取

在前面的水果示例中，你根据个头和颜色来比较水果，换言之，你比较的特征是个头和颜色。现在假设有三个水果，你可抽取它们的特征。

再根据这些特征绘图。

从上图可知，水果A和B比较像。下面来度量它们有多像。要计算两点的距离，可使用毕达哥拉斯公式。

例如，A和B的距离如下。

A和B的距离为1。你还可计算其他水果之间的距离。

这个距离公式印证了你的直觉：A和B很像。

假设你要比较的是Netflix用户，就需要以某种方式将他们放到图表中。因此，你需要将每位用户都转换为一组坐标，就像前面对水果所做的那样。

在能够将用户放入图表后，你就可以计算他们之间的距离了。

下面是一种将用户转换为一组数字的方式。用户注册时，要求他们指出对各种电影的喜欢程度。这样，对于每位用户，都将获得一组数字！

Priyanka和Justin都喜欢爱情片且都讨厌恐怖片。Morpheus喜欢动作片，但讨厌爱情片（他讨厌好好的动作电影毁于浪漫的桥段）。前面判断水果是橙子还是柚子时，每种水果都用2个数字表示，你还记得吗？在这里，每位用户都用5个数字表示。

在数学家看来，这里计算的是五维（而不是二维）空间中的距离，但计算公式不变。

这个公式包含5个而不是2个数字。

这个距离公式很灵活，即便涉及很多个数字，依然可以使用它来计算距离。你可能会问，涉及5个数字时，距离意味着什么呢？这种距离指出了两组数字之间的相似程度。

这是Priyanka和Justin的距离。

余弦相似度

前面计算两位用户的距离时，使用的都是距离公式。还有更合适的公式吗？在实际工作中，经常使用余弦相似度（cosine similarity）。假设有两位品味类似的用户，但其中一位打分时更保守。他们都很喜欢Manmohan Desai的电影Amar Akbar Anthony，但Paul给了5星，而Rowan只给4星。如果你使用距离公式，这两位用户可能不是邻居，虽然他们的品味非常接近。余弦相似度不计算两个矢量的距离，而比较它们的角度，因此更适合处理前面所说的情况。本书不讨论余弦相似度，但如果你要使用KNN，就一定要研究研究它！

四、机器学习简介

1. OCR 
   OCR指的是光学字符识别（optical character recognition），这意味着你可拍摄印刷页面的照片， 
   计算机将自动识别出其中的文字。
2. 朴素贝叶斯分类器（Naive Bayes classifier）2 
   按识别数字为例， 
   KNN：①浏览大量的数字图像，将这些数字的特征提取出来。 
   ②遇到新图像时，你提取该图像的特征，再找出它最近的邻居都是谁！ 
   OCR的第一步是查看大量的数字图像并提取特征，这被称为训练（training）。大多数机器学习算法都包含训练的步骤：要让计算机完成任务，必须先训练它。 
   OCR算法提取线段、点和曲线等特征。