学习自《图解算法》

K最近邻算法（k-nearest neighbours，KNN）

• 学习使用K最近邻算法创建分类系统。
• 学习特征抽取。
• 学习回归，即预测数值，如明天的股价或用户对某部电影的喜欢程度。

K最近邻算法

使用K最近邻算法创建分类系统。

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

1. 我们已知某些实物的分类
2. 将未知的神秘的水果按照对应的颜色和个头绘制进去
3. 然后找邻居（这里暂且为3，邻居是距离它最近的几个），在这三个邻居中，橙子比柚子多，因此这个水果很可能是橙子，所以标注为橙子

特征抽取

在前面的图表中，相似的水果相距较近，但如何确定两个水果的相似程度呢，我们抽取特征，在前面的水果示例中，你根据个头和颜色来比较水果

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

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

按照上面的道理我们建造一个电影推荐系统

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

因为上面的水果案例只比较两个特征，所以可以建造二维图，而这里有五个，我们处于三维空间，最多可以直观理解三维，所以这里画出五维不太好画，但是我们同样使用距离公式就可以看出谁和谁更相似

Priyanka和Justin的距离 ：2
Priyanka和Morpheus的距离：24

只要是Justin喜欢的电影，就将其推荐给Priyanka，反之亦然。你这就创建了一个电影推荐系统

回归，即预测数值

如明天的股价或用户对某部电影的喜欢程度

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

你求这些人打的分的平均值，结果为4.2。这就是回归 （regression）

回归很有用。假设你在伯克利开个小小的面包店，每天都做新鲜面包，需要根据如下一组特征预测当天该烤多少条面包你还有一些历史数据，记录了在各种不同的日子里售出的面包数量。

预测你今天能售出多少条面包呢？？我们来使用KNN算法，其中的K为4。首先，找出与今天最接近的4个邻居。距离如下，因此最近的邻居为A、B、D和E。

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

你将使用KNN来做两项基本工作——分类和回归：
分类就是编组；
回归就是预测结果（如一个数字）

机器学习

KNN算法真的是很有用，堪称你进入神奇的机器学习领域的领路人！机器学习旨在让计算机更聪明
大多数机器学习算法都包含训练的步骤：要让计算机完成任务，必须先训练它，基于已知取判断未知

OCR

OCR指的是光学字符识别 （optical character recognition），这意味着你可拍摄印刷页面的照片，计算机将自动识别出其中的文字。【QQ的提取图片文字】

训练

OCR的第一步是查看大量的数字图像并提取特征，这被称为训练（training）
浏览大量的数字图像，将这些数字的特征提取出来。
这与前面判断水果是橙子还是柚子时一样。一般而言，OCR算法提取线段、点和曲线等特征

判断

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

垃圾邮件过滤器

垃圾邮件过滤器使用一种简单算法——朴素贝叶斯分类器 （Naive Bayes classifier），

训练

判断

假设你收到一封主题为“collect your million dollars now!”的邮件，这是垃
圾邮件吗？

例如，使用这个非常简单的模型时，发现只有单词
million在垃圾邮件中出现过。朴素贝叶斯分类器能计算出邮件为垃圾邮
件的概率，其应用领域与KNN相似。