机器学习算法图解：K最近邻算法——橙子还是柚子？

K最近邻算法

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

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

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

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

在这三个邻居中，橙子比柚子多，因此这个水果很可能是橙子。

祝贺你，你刚才就是使用K最近邻算法(k-nearest neighbours,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的距离。

Priyanka和Justin很像。Priyanka和Morpheus的差别有多大呢？请计算他们之间的距离再接着往下读。

Priyanka和Morpheus的距离为"根号24",你算对了呢？上述距离表明，Priyanka的喜好更接近于Justin而不是Morpheus.

回归(预测)

假设你不仅要向Priyanka推荐电影，还要预测她将给这部电影打多少分。为此，先找出与她最近的5个人。

假设你要预测Priyanka会给电影Pitch Perfect打多少分。Justin、JC、Joey、Lance和Chris都给它打了多少分呢？

你求这些人打的分的平均值。这就是回归。你将使用KNN来做两项基本工作--分类和回归。

回归当然很有用。假设你在伯克利开个小小的面包店，每天都做新鲜面包，需要根据如下一组特征预测当天该烤多少条面包：

1. 天气指数1~5（1表示天气很不好）

2. 是不是周末或节假日（周末或节假日为1 否侧为0）

3. 有没有活动（1表示有，0表示没有）

你还有一些历史数据，记录了在各种不同的日子里售出的面包数量。

今天是周末，天气不错。根据这些数据，预测你今天能售出多少条面包呢？我们来使用KNN算法，其中的K为4。首先，找出与今天最接近的4个邻居。

距离如下，因此最近的邻居为A、B、D和E。

将这些天售出的面包数平均，结果为.这就是你今天要烤的面包数！

挑选合适的特征

为推荐电影，你让用户指出他对各类电影的喜好程度。如果你是让用户给一系列小猫片打分呢？在这种情况下，你找出的是对小猫图片的欣赏品味类似的用户。对电影推荐系统来说，这很可能是一个不好的电影推荐引擎，因为你选择的特征与电影欣赏品味没多大关系。

又假设你只让用户给《玩具总动员》《玩具总动员2》和《玩具总动员3》打分。这将难以让用户的电影欣赏品味显现出来！使用KNN时，挑选合适的特征进行比较至关重要。所谓合适的特征，就是：

1. 与要推荐的电影紧密相关特征

2. 不偏不倚的特征。

你认为评分是不错的电影推荐指标吗？

机器学习

KNN算法真的很有用，堪称你进入神奇的机器学习领域的领路人！机器学习旨在让计算机更聪明。

图片识别

OCR指的是光学字符识别，这意味着你可拍摄印刷页面的照片，计算机将自动识别出其中的文字。Google使用OCR来实现图书数字化。OCG是如何工作的呢？我们来看一个例子。请看下面的数字。

如何自动识别出这个数字是什么呢？可使用KNN。

1. 浏览大量的数字图像，将这些数字的特征提取出来

2. 遇到新图像时 你提取该图像的特征，再找出它最近的邻居都是谁

这与前面判断水果橙子还是柚子时一样。一般而言，OCR算法提取线段、点和曲线等特征

遇到新字符时，可从中提取同样的特征。这些理念也可用于语音识别和人脸识别。你将照片上传到FaceBook时，它有时候能够自动标出照片中的人物，这是机器学习发挥作用！