推荐系统-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算法的成败
参考书籍《算法图解》第九章
转载请注明作者:小停雨的博客