推荐系统-K最邻近算法

Published on 2018 - 06 - 25

经常在网购的时候看到下面有猜你喜欢。
听说淘宝首页的内容,每一个人都不一样。
用小米盒子看电影的时候,会有猜你喜欢。
 
问题是,猜的还很准,为什么呢?
 
转载请注明作者:小停雨的博客

K最临近算法

目标:

  • 使用K最邻近算法创建分类系统
  • 特征抽取
  • 回归,即预测数值(如明天得股价,或用户对某部电影的喜欢程度)
  • K最邻近算法的应用案例和局限性

计算机是怎么识别东西的

计算机通过已经给定的特征值,来分析和判断到底是什么,下面的图说明了计算机是如何判断的。

橙子还是柚子

计算机如何识别橙子还是柚子呢?

Image

计算机的思维过程是这样的:

  • 抽取两个水果特征,一般而言,柚子更大,更红。橙子体积小,颜色也偏橙色
  • 当给出一种为打标签(计算机还不认识)的水果的时候,计算机会根据其特征,匹配离它最近的三个邻居。
  • 在这三个邻居中,橙子比柚子多,因此这个水果很可能是橙子。

如果你看懂了,那么祝贺你,刚刚思考的方式就是K最邻近算法(KNN),这个算法非常简单,但很有用,需要对东西进行分类时,可以首先尝试这种算法。下面再举一个非常真实的例子。

电影推荐系统

假设我是某电影网站的员工,要为用户创建一个电影推荐系统。从本质上说,这类似于前面的水果问题。我们可以将所有的用户都放入一个图标中,这些用户在图表中的位置取决于其爱好,因此喜好相似的用户距离较近。假设我们要像Priyanka推荐电影,可以找出五位与他最接近的用户。

Image

假设在对电影的喜好方面,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算法的成败

参考书籍《算法图解》第九章
转载请注明作者:小停雨的博客