推荐系统-K最邻近算法
经常在网购的时候看到下面有猜你喜欢。
听说淘宝首页的内容，每一个人都不一样。
用小米盒子看电影的时候，会有猜你喜欢。
问题是，猜的还很准，为什么呢？
转载请注明作者：小停雨的博客
K最临近算法
目标：
- 使用K最邻近算法创建分类系统
- 特征抽取
- 回归，即预测数值（如明天得股价，或用户对某部电影的喜欢程度）
- K最邻近算法的应用案例和局限性
计算机是怎么识别东西的
计算机通过已经给定的特征值，来分析和判断到底是什么，下面的图说明了计算机是如何判断的。
橙子还是柚子
计算机如何识别橙子还是柚子呢？
计算机的思维过程是这样的：
- 抽取两个水果特征，一般而言，柚子更大，更红。橙子体积小，颜色也偏橙色
- 当给出一种为打标签（计算机还不认识）的水果的时候，计算机会根据其特征，匹配离它最近的三个邻居。
- 在这三个邻居中，橙子比柚子多，因此这个水果很可能是橙子。
如果你看懂了，那么祝贺你，刚刚思考的方式就是K最邻近算法（KNN），这个算法非常简单，但很有用，需要对东西进行分类时，可以首先尝试这种算法。下面再举一个非常真实的例子。
电影推荐系统
假设我是某电影网站的员工，要为用户创建一个电影推荐系统。从本质上说，这类似于前面的水果问题。我们可以将所有的用户都放入一个图标中，这些用户在图表中的位置取决于其爱好，因此喜好相似的用户距离较近。假设我们要像Priyanka推荐电影，可以找出五位与他最接近的用户。
假设在对电影的喜好方面，justin，JC，Joey，Lance和Chris都与Priyanka差不多，因此他们喜欢的电影很可能Priyanka也喜欢。
有了这张图以后创建推荐系统简直易如反掌：只要是Justin喜欢的电影，就将其推荐给Priyanka。
但还有一个重要的问题没有解决。在前面的图表中，相似的用户相距较近，但如何确定两位用户的相似程度呢？下面来说说特征抽取
特征抽取
上面我使用过水果做示例，根据个头和颜色来比较水果，换言之，比较的特征是个头和颜色，那么放在我们的电影推荐系统里面来，如何获取新注册的用户坐标呢？
在用户注册时，可以要求他们指出对各种电影的喜欢程度，比如喜欢的明星，喜欢的电影类型喜，还有对一些电影进行打分要求他们指出对各种电影的喜欢程度。这样，对于每一个用户，都将获得一组数字。
因为比较懒，下面来展示一个比较简单的特征抽取结果，我们就只按照用户喜欢的影片类型来对新用户进行分类。
| Priyanka | Justin | Morpheus | |
|---|---|---|---|
| 喜剧片 | 3 | 4 | 2 |
| 动作片 | 4 | 3 | 5 |
| 生活片 | 4 | 5 | 1 |
| 恐怖片 | 1 | 1 | 3 |
| 爱情片 | 4 | 5 | 1 |
Priyanka和Justin都喜欢爱情片且都讨厌恐怖片。Morpheus喜欢动作片，但讨厌爱情片（他讨厌好好的动作电影会与浪漫的桥段）。前面判断水果是橙子还是柚子时，每种水果都用2个数字表示，在这里每个用户都用5个数字表示。
在数学家看来，这里计算的是五维（而不是二维）空间中的距离，我们使用毕达哥拉斯公式
$$
\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}
$$
由于我们有五个数值需要计算，所以公式为：
$$
\sqrt{(a_1-a_2 )^2+(b_1-b_2 )^2+(c_1-c_2 )^2+(d_1-d_2 )^2+(e_1-e_2 )^2 }
$$
这个距离公式很灵活，即便设计很多个数字，依然可以用它来计算距离。你可能会问，涉及5个数时，距离意味着什么呢？这种距离指出了两组数之间的相似程度。
$$
\begin{align}
&\sqrt{(𝟑−𝟒)^𝟐+(𝟒−𝟑)^𝟐+(𝟒−𝟓)^𝟐+(𝟏−𝟏)^𝟐+(𝟒−𝟓)^𝟐}\
=&\sqrt{1 + 1 + 1 + 0 + 1}\
=&\sqrt{4}\
=&2\
\end{align}
$$
上面计算的事Priyanka和Justin的距离，
Priyanka和Justin很像。Priyanka和Morpheus的差别有多大呢？下面来计算一下：
$$
\begin{align}
&\sqrt{(𝟑−2)^𝟐+(𝟒−5)^𝟐+(4−1)^𝟐+(𝟏−3)^𝟐+(𝟒−1)^𝟐}\
=&\sqrt{1 + (-1) + 9 + (-4) + 9}\
=&\sqrt{24}\
=&\sqrt[2]{6}\
\end{align}
$$
现在要向Priyanka推荐电影将易如反掌，只要是Justin喜欢的电影，就将其推荐给Priyanka，反之亦然，这样你就创建了一个电影推荐系统！
回归
假设我们不仅要向Priyanka推荐电影，还要预测她将会给这部电影打多少分。为此先找出与她最近的五个人。
弱弱的说一句，我举例总是说5个人，其实并非一定要选择5个最近的邻居，也可以选择2个，10个或10000个。这个算法是K最邻近，不是5最邻近，啊哈哈。。。
好开始预测，我们可以看到，Priyanka的五个邻居给电影打了多少分：
| 姓名 | 评分 |
|---|---|
| JC | 4 |
| Joey | 4 |
| Lance | 5 |
| CHris | 3 |
| Justin | 5 |
我们来计算这些人为这部电影打分的平均值，结果为4.2。这就是回归（regression）
KNN算法常常用来做两件基本工作——分类和回归：
- 分类就是编组；
- 回归就是预测结果（如一个数字）。
回归的作用
回归很有用，假设你开了个小小的面包店，每天都做新鲜的面包，需要根据如下一组特征预测当天该烤多少个面包：
- 天气指数1~5（1表示很糟，5表示天气非常好）
- 是不是周末或节假日（周末或节假日为1，否则为0）
- 有没有优惠活动（1表示有，0表示没有）
我们还有一组数据，记录了曾经在各种不同的日子里出售的面包数量。
| 数据 | 产量 | 数据 | 产量 |
|---|---|---|---|
| A | 300个 | B | 225个 |
| C | 75个 | D | 200个 |
| E | 150个 | F | 50个 |
今天是周末，天气不错，根据这些数据，预测今天可以售出多少个面包呢？使用KNN算法，其中的K为4，首先找出与今天最接近的4个邻居。
$$
(4,1,0) = ?
$$
使用毕达哥拉斯公式计算出以往的数据距离如下：
| 邻居 | 相似值 |
|---|---|
| A | 1 |
| B | 2 |
| C | 3 |
| D | 1.41 |
| E | 1 |
| F | 2.23 |
可以看到今天距离最近的邻居为：ABDE，将这些天售出的面包数平均，结果为218.75，这就是今天需要烤的面包数。
余弦相似度
我们来考虑一个问题：在计算两位用户的距离时，使用的都是距离公式。还有更适合的公式吗？
在世纪工作中经常使用余弦相似度。假设有两位品味类似的用户，但其中一位打分时更保守。他们都很喜欢黄渤的电影《疯狂的外星人》但Paul给了5星，而Rowan只给了4星。如果你使用距离公式，这两位用户可能不是邻居，虽然他们的品味非常接近。
余弦相似度不计算两个矢量的距离，而比较它们的角度，因此更适合处理上面所说的情况，不过这篇文章主要是理解并记录K最邻近算法与为以后的人工智能铺路。所以这篇文章不会介绍余弦相似度。但是如果以后要做人工智能方向，并且需要使用到KNN，就一定要研究研究余弦相似度
关于挑选合适的特征
为推荐电影，你让用户指出他对各类电影的喜好程度。如果你是让用户给一系列小猫图片打分呢？在这种情况下，你找出的是对小猫图片的欣赏品味类似的用户。对电影推荐系统来说，这很可能是一个糟糕的推荐引擎，因为你选择的特征与电影欣赏品味没多大关系。
又假设你只让用户给《玩具总动员》《玩具总动员2》和《玩具总动员3》打分。这将难以让用户的电影欣赏品味显现出来。使用KNN时，挑选合适的特征进行比较至关重要。
所谓的合适特征就是：
- 与要推荐的电影紧密相关的特征；
- 不偏不倚的特征（例如，如果只让用户给喜剧片打分，就无法判断他们是否喜欢动作片）
那么我们再来思考一个问题：
你认为评分真的是一个很好的电影推荐指标吗？比如我给《疯狂的外星人》的评分可能比《大话西游》高，但实际上我观看《大话西游》的时间更长，该如何改进电影推荐系统呢？
我能想到的是再加上站内所有用户对电影的平均评分，与整体的播放量，来改进整体电影的最终推荐结果。也可以结合第三方评价结果来分析电影的优劣程度，比如豆瓣等
还有一个问题
上面的面包店的例子：对于面包店，你能找出两个不错和糟糕的特征吗？在报纸上打广告后，你可能需要烤制更多的面包，或者每周一需要烤制更多的面包。在挑选合适的特征方面，没有放之四海而皆准的法则，你必须要考虑各种需要考虑到的因素。
最后一个问题
回到我们的电影推荐系统，我们创建推荐系统时只考虑了5个最邻近的邻居，这是太多还是太少了呢？
实际上是太少了。如果考虑的邻居太少，结果很可能存在偏差。
一个不错的经验规则是：
如果有N位用户，应该考虑根号(N)个邻居(\sqrt(N))小结
- KNN用于分类和回归，需要考虑最近的邻居
- 分类就是编组
- 回归就是预测结果(如数字)
- 特征抽取意味着将物品(如水果或用户)转换为一系列可比较的数字
- 能否挑选合适的特征事关KNN算法的成败
参考书籍《算法图解》第九章
转载请注明作者：小停雨的博客