K最邻近算法

使用K最邻近算法创建分类系统，学习特征抽取。学习回归，即预测数值。学习K最邻近算法的应用案例和局限性。

橙子还是柚子

人是如何判断看到的一个水果到底是橙子还是柚子？看与它长得像的几个邻居中，是橙子多还是柚子多。

实际上这个思考的过程，就是使用K最近邻（k-nearest neighbours，KNN）算法进行了分类！

它的算法非常简单，如何对一个对象分类？看它邻近的几个邻居是属于什么类别，它就更有可能属于哪个类别。

创建推荐系统

假设Netflix要为用户创建一个电影推荐系统。

将用户放入一个图表中，这些用户在图表中的位置取决于其喜好，因此喜好相似的用户距离较近。如果要向A推荐，可以找出五位与他最接近的用户。

接下来的问题就是如何确定用户的相似程度。

特征抽取将每位用户转换为一组坐标，比如根据他们的喜好，定义出A（喜剧片3，动作片4，生活片4，恐怖片1，爱情片4），B（喜剧片4，动作片3，生活片5，恐怖片1，爱情片5）。

这样A与B用户的是否相近就可以直接通过毕达哥拉斯公式计算出来。

回归

假设你不仅要推荐电影，还要预测A给这部电影打多少分。

与A相似的人有k个，你求这些人打的分的平均值，结果为4.2。这就是回归（regression）。

使用KNN可以做两项基本工作——分类和回归：

分类就是编组；

回归就是预测结果（如一个数字）。

前面计算两位用户的距离时，使用的都是距离公式。在实际工作中，经常使用余弦相似度（cosine similarity）。

比如有两位品味类似的用户，但其中一位打分时更保守。如果你使用距离公式，这两位用户可能不是邻居，虽然他们的品味非常接近。

余弦相似度不计算两个矢量的距离，而比较它们的角度，因此更适合处理前面所说的情况。

机器学习

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

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

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

(2) 遇到新图像时，你提取该图像的特征，再找出它最近的邻居都是什么。

OCR的第一步是查看大量的数字图像并提取特征，这被称为训练（training）。大多数机器学习算法都包含训练的步骤：要让计算机完成任务，必须先训练它。

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

假设你收到一封主题为“collect your million dollars now!”的邮件，你可研究这个句子中的每个单词，看看它在垃圾邮件中出现的概率是多少。

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

小结

KNN用于分类和回归，需要考虑最近的邻居。

分类就是编组。

回归就是预测结果（如数字）。

特征抽取意味着将物品（如水果或用户）转换为一系列可比较的数字。

能否挑选合适的特征事关KNN算法的成败。