Archive

Posts Tagged ‘推荐系统’

社会网络分析:探索人人网好友推荐系统

2011/04/29 3 条评论

作者:陈逸波. 社会网络分析:探索人人网好友推荐系统. 统计之都, 2011.04. URL: http://cos.name/2011/04/exploring-renren-social-network/.

最近四五年间,互联网行业似乎总是绕不开社交网络这个概念。无论是旗舰级别的传说中的facebook、LinkedIn,还是如雨后春笋般冒出来的各种团购和微博网站,全都或多或少地体现着SNS(社会网络服务)的特色。这些五花八门的产品,在丰富我们业余生活的同时,也为研究者提供了大量珍贵的数据。以往只能依靠有限的调研或模拟才能进行的社会网络分析(SNA),现在具备了大规模开展和实施的条件。国内著名而典型的SNS网站“人人网”,最近依靠上市新闻重新赢得了大家的关注。本文基于人人网的好友关系数据,应用统计分析软件R做了社会网络分析的一些尝试。

注:网络边界的确定,是社会网络分析的关键而困难的步骤。由于数据获取的限制,本文分析的对象限制于我的好友。也就是说,本文分析的网络是我自己的好友圈子,读者看了这些分析结果或许会觉得索然无味,感兴趣的同学可以分析一下自己的社交网络,看看是否会有类似的结果。

一、读取数据

之所以选择人人网作为分析的对象,很重要的一点原因在于其数据获取较为便利。本文读取数据的过程借助了一款命令行浏览器cURL,这个浏览器在R中可以用RCurl包实现,简要的中文介绍建议参考medo的《R不务正业之RCurl》。通过RCurl的简单编程,我们可以在R中实现登录人人网、发布状态以及读取页面数据等功能。

人人网好友列表页面的url为http://friend.renren.com/GetFriendList.do?curpage=0&id=****,其中curpage为页码参数,id为相应的用户。通过对id与curpage做简单的循环,我读取了自己(陈逸波)的所有好友以及好友的好友。如果需要分析更大范围的网络,可以做进一步的循环迭代。(读取数据的R代码见文末附件。)

用上述代码读取到的数据集记为net.1,该数据有如下的格式:

1
2
set.seed(13)
net.1[sample(1:nrow(net.1), 10), ]
                u0        id0     u1       id1
68282          沈叶  229657865 邢凤婷 238382560
19358        吴昊宸  115975869   吴玥 250106135
18406   叶敏佳MO小沫  222288430 官兴华  32503437
7782           李彬   54598688 鱼化石 323984442
57464          牛智 1411553595   谢諹 221389295
1833         马天云   23157153   张立 227738255
222150       刘雯欢  227317115   李嫣 334590411
278125       陈长虹  236145500 李利文 249059215
135239         高涛  248013976 宋阳阳 247196544
18214        蒋鸿章   35702214 华明明 226037245

其中,第一行数据表示“沈叶”与“邢凤婷”是好友关系,id0与id1为相应的用户id。需要注意的是人人网中不可避免地会出现同名用户的情况,因此id才是用户的唯一标识。

二、绘制简单的好友关系网络图

本文分析的焦点集中于我的好友之间形成的网络,因此考虑做网络图来直观地展示网络的结构。

首先,从上述读取到的数据集中筛选出希望分析的子集。这个子集包含了两个条件:

(1)网络中没有我自己(否则会呈现以我为中心的分布,失去了分析的意义);
(2)网络中的用户都是我自己的好友。

1
2
net.1.1 = net.1[net.1[, 1] != "陈逸波", ]
net.1.2 = net.1.1[net.1.1[, 4] %in% net.1.1[, 2], ]

因为我的好友中不存在同名的现象,可以直接使用用户名,否则需要对同名用户做一定标记或者直接用id来做后续的分析。

1
ff = net.1.2[, c(1, 3)]

然后就是直接利用igraph包的做图功能绘制相应的网络图。

1
2
3
4
5
6
7
8
library(igraph)
gg = graph.data.frame(d = ff, directed = F)
## png("net.png", width = 500, height = 500)
par(mar = c(0, 0, 0, 0))
set.seed(14)
plot(gg, layout = layout.fruchterman.reingold, vertex.size = 5, vertex.label = NA,
    edge.color = grey(0.5), edge.arrow.mode = "-")
## dev.off()

从图中可以直观地看出,我的好友网络存在一定的人群分割,可以尝试对这个网络进行一些分析以提取出其中相对独立的子群(或者称为社群)。

三、子群分割

信息的分类和过滤是社会网络服务的一项特征,例如人人网对好友关系有一套自己的分类方式,用户可以自行对好友进行分组,从而对信息的收发做分组的管理。但是作为用户却未必能够养成并保持这种分组的习惯(例如我自己就从来没有对好友做过分组)。与此同时我们揣测,作为真实关系的线上反映,人人网的好友网络是能够自动呈现出一定的人群分割的,而在社会网络分析中,对网络成分的分析也确实是一项重点。通过分析网络的结构,提取出其中的子群,能够让我们更好地理解这个网络的组成方式,从而更好地管理和利用信息流。

寻找子群的算法有很多,igraph包提供了若干函数以实现对网络子群的搜索,本文采用了其中的walktrap.community()函数,更多细节及其他算法可以查看帮助文档。

为了在网络图中展示这些子群,我们采用不同的颜色来标记他们。

1
2
3
4
5
6
7
8
9
10
11
com = walktrap.community(gg)
sg = data.frame(name = com$labels, sg = com$mem)
member = com$mem
mcolor = rainbow(max(member) + 1)[member + 1]
## png("walktrap.community_1.png", width = 500, height = 500)
par(mar = c(0, 0, 0, 0))
set.seed(14)
plot(gg, layout = layout.fruchterman.reingold, vertex.size = 5,
    vertex.color = mcolor, vertex.label = NA, edge.color = grey(0.5),
    edge.arrow.mode = "-")
## dev.off()

从图中可以直观地看出好友网络已经被划分为若干相对独立的子群。这也与我们对人人网(尤其是其前身校内网)的直观理解相符合——人人网的好友关系基本都是真实线下关系的反映,很自然地可以划分为初中同学、高中同学、大学同学,等等(例如左下角的五个节点,那是统计之都的同学们)。

具体地看一下划分得到的子群,就能够更好地理解子群的含义。我挑出了比较典型的几个子群,其中包括:

“实验室同学”(子群1)

1
sg[sg[, 2] == 1, ]
141      周莉  1
194    杨志昌  1
234      潘伟  1
261    卢进文  1
300 冯婷janet  1
307      胡刚  1

“校内论坛上某版版友”(子群6)

1
sg[sg[,2] == 6, ]
18        曲文君  6
23        翟传鑫  6
104         梁玮  6
196       单广宇  6
230 花木马leeear  6
247         王昉  6
268         李典  6
279         陈侃  6
296       王祎萍  6
312         牛智  6
323         郗旺  6

“初中同学”(子群9)

1
sg[sg[,2] == 9, ]
14          蒋鸿章  9
20            唐健  9
28            朱铭  9
109           周乙  9
119         周云鸽  9
133         王莉萍  9
184           姚佳  9
202           孙倩  9
216           袁慧  9
227           沈叶  9
237         熊翊君  9
239           巴锦  9
259         周贤莉  9
269         高君娴  9
297           蒋健  9
298         马秋莲  9
303 郑<U+2764>小佳  9
304           金华  9

“高中学弟学妹”(子群10)

1
sg[sg[,2] == 10, ]
205      邹舒怡 10
236      封启云 10
253        何非 10
258      朱亚希 10
260        陈平 10
265      洪怡君 10
266        程功 10
281      李常然 10
291 朱燕^^Jue 10
302    周飏 Ivy 10

“统计之都”(子群7)

1
sg[sg[,2] == 7, ]
35    魏太云  7
150   邓一硕  7
224   吴云崇  7
278     高涛  7
322 统计之都  7

其他子群还包括“大学同学(数学系)”、“大学同学(非数学系)”等等,不一而足。因此可以认为上述算法得到的子群划分是合理且有意义的。

四、起到中介作用的那些好友

在社会网络分析中,对节点的中介作用有一个经典的刻画叫做“中间度”。中间度衡量了节点作为中介的程度,当网络中某个个体的中间度较大时,我们认为它在很大程度上起到了中介和沟通的作用。常用的中间度的定义是\sum(g_{ivj} / g_{ij}, i \neq j,i \neq v, j \neq v),其中g_{ij}表示联通i与j两个节点的捷径的条数,g_{ivj}则表示联通i与j两个节点且经过v的捷径的条数(所谓捷径,就是两个节点之间的最短路径)。在igraph包中,betweenness()函数能够简单地计算网络中各个节点的中间度。

1
2
3
## png("betweenness.png", width = 500, height = 500)
plot(betweenness(gg, directed = FALSE))
## dev.off()

根据得到的中间度散点图,我们人为地选择了3000作为分界点,选取中间度高于3000的节点并在图形中利用节点的大小展示出来。

1
2
3
4
5
6
7
8
9
10
bet = which(betweenness(gg, directed = F) > 3000)
size = rep(5, nrow(sg))
size[bet] = 15
## png("walktrap.community_2.png", width = 500, height = 500)
par(mar = c(0, 0, 0, 0))
set.seed(14)
plot(gg, layout = layout.fruchterman.reingold, vertex.size = size,
    vertex.color = mcolor, vertex.label = NA, edge.color = grey(0.5),
    edge.arrow.mode = "-")
## dev.off()

从图中也可以直观地看出,中间度最高的5个节点,确实位于中介的地位。

具体看这5个节点(注意此处的节点是从0开始编号的):

1
V(gg)[bet - 1]
Vertex sequence:
[1] "邱元杰" "娄谦之" "王子涵" "刘波"   "顾鑫"

对这5个节点,基本上都有比较合理的解释,其中有三个人是“高中校友”兼“大学校友”,而另外两个则沟通了“网络好友”与“大学好友”。

五、基于好友关系的一种简单的推荐

最后,我们也做了基于好友关系的好友推荐,推荐的逻辑与人人网自身的推荐逻辑相同:根据共同好友的数量来进行推荐。在具体实现的时候,仍然需要考虑用户同名的情况。

1
2
3
4
5
6
net.1.3 = net.1[!(net.1[, 4] %in% net.1.1[, 2]), ]
listall = sort(table(net.1.3[, 4]), dec = T)
top = names(listall[1:20])
tmp = net.1.3[net.1.3[, 4] %in% top, 3]
top20 = sort(table(tmp), dec = T)
top20
周科  邹碧筠Phoebe       査小狮       韩晶磊       陆丽娜
55           49           42           41           41
焦丽萍       蔡锡真         高晨       鲁锦彪         张洁
40           39           39           38           38
张明珠       范莉悦       钱咏邠   薛俊波悟空         周迪
38           37           37           37           37
陈素         蒋莹         唐甜         费逸       王丽涵
36           36           36           35           35

这个推荐的结果与人人网的推荐基本一致(因为逻辑相同嘛),以下是人人网的一些推荐截图:

上述推荐的机制较为简单,但是在拥有大量真实关系的网络中,推荐的效率还是比较高的。当然,我们也可以开展对文本与行为的挖掘,以得到超越真实线下关系的推荐,但本文尚未做这方面的尝试。

推荐引擎初探

2011/04/01 发表评论

本文我们将讲讲推荐引擎到底是怎么工作的。推荐引擎利用特殊的信息过滤技术,将不同的物品或内容推荐给可能对它们感兴趣的用户。

图 1. 推荐引擎工作原理图
图 1. 推荐引擎工作原理图

图 1 给出了推荐引擎的工作原理图,这里先将推荐引擎看作黑盒,它接受的输入是推荐的数据源,一般情况下,推荐引擎所需要的数据源包括:

  • 要推荐物品或内容的元数据,例如关键字,基因描述等;
  • 系统用户的基本信息,例如性别,年龄等
  • 用户对物品或者信息的偏好,根据应用本身的不同,可能包括用户对物品的评分,用户查看物品的记录,用户的购买记录等。其实这些用户的偏好信息可以分为两类:
  • 显式的用户反馈:这类是用户在网站上自然浏览或者使用网站以外,显式的提供反馈信息,例如用户对物品的评分,或者对物品的评论。
  • 隐式的用户反馈:这类是用户在使用网站是产生的数据,隐式的反应了用户对物品的喜好,例如用户购买了某物品,用户查看了某物品的信息等等。

显式的用户反馈能准确的反应用户对物品的真实喜好,但需要用户付出额外的代价,而隐式的用户行为,通过一些分析和处理,也能反映用户的喜好,只是数据不是很精确,有些行为的分析存在较大的噪音。但只要选择正确的行为特征,隐式的用户反馈也能得到很好的效果,只是行为特征的选择可能在不同的应用中有很大的不同,例如在电子商务的网站上,购买行为其实就是一个能很好表现用户喜好的隐式反馈。

推荐引擎根据不同的推荐机制可能用到数据源中的一部分,然后根据这些数据,分析出一定的规则或者直接对用户对其他物品的喜好进行预测计算。这样推荐引擎可以在用户进入的时候给他推荐他可能感兴趣的物品。

推荐引擎的分类

推荐引擎的分类可以根据很多指标,下面我们一一介绍一下:

  1. 推荐引擎是不是为不同的用户推荐不同的数据根据这个指标,推荐引擎可以分为基于大众行为的推荐引擎和个性化推荐引擎
    • 根据大众行为的推荐引擎,对每个用户都给出同样的推荐,这些推荐可以是静态的由系统管理员人工设定的,或者基于系统所有用户的反馈统计计算出的当下比较流行的物品。
    • 个性化推荐引擎,对不同的用户,根据他们的口味和喜好给出更加精确的推荐,这时,系统需要了解需推荐内容和用户的特质,或者基于社会化网络,通过找到与当前用户相同喜好的用户,实现推荐。

    这是一个最基本的推荐引擎分类,其实大部分人们讨论的推荐引擎都是将个性化的推荐引擎,因为从根本上说,只有个性化的推荐引擎才是更加智能的信息发现过程。

  2. 根据推荐引擎的数据源其实这里讲的是如何发现数据的相关性,因为大部分推荐引擎的工作原理还是基于物品或者用户的相似集进行推荐。那么参考图 1 给出的推荐系统原理图,根据不同的数据源发现数据相关性的方法可以分为以下几种:
    • 根据系统用户的基本信息发现用户的相关程度,这种被称为基于人口统计学的推荐(Demographic-based Recommendation)
    • 根据推荐物品或内容的元数据,发现物品或者内容的相关性,这种被称为基于内容的推荐(Content-based Recommendation)
    • 根据用户对物品或者信息的偏好,发现物品或者内容本身的相关性,或者是发现用户的相关性,这种被称为基于协同过滤的推荐(Collaborative Filtering-based Recommendation)。
  3. 根据推荐模型的建立方式可以想象在海量物品和用户的系统中,推荐引擎的计算量是相当大的,要实现实时的推荐务必需要建立一个推荐模型,关于推荐模型的建立方式可以分为以下几种:
    • 基于物品和用户本身的,这种推荐引擎将每个用户和每个物品都当作独立的实体,预测每个用户对于每个物品的喜好程度,这些信息往往是用一个二维矩阵描述的。由于用户感兴趣的物品远远小于总物品的数目,这样的模型导致大量的数据空置,即我们得到的二维矩阵往往是一个很大的稀疏矩阵。同时为了减小计算量,我们可以对物品和用户进行聚类, 然后记录和计算一类用户对一类物品的喜好程度,但这样的模型又会在推荐的准确性上有损失。
    • 基于关联规则的推荐(Rule-based Recommendation):关联规则的挖掘已经是数据挖掘中的一个经典的问题,主要是挖掘一些数据的依赖关系,典型的场景就是“购物篮问题”,通过关联规则的挖掘,我们可以找到哪些物品经常被同时购买,或者用户购买了一些物品后通常会购买哪些其他的物品,当我们挖掘出这些关联规则之后,我们可以基于这些规则给用户进行推荐。
    • 基于模型的推荐(Model-based Recommendation):这是一个典型的机器学习的问题,可以将已有的用户喜好信息作为训练样本,训练出一个预测用户喜好的模型,这样以后用户在进入系统,可以基于此模型计算推荐。这种方法的问题在于如何将用户实时或者近期的喜好信息反馈给训练好的模型,从而提高推荐的准确度。

其实在现在的推荐系统中,很少有只使用了一个推荐策略的推荐引擎,一般都是在不同的场景下使用不同的推荐策略从而达到最好的推荐效果,例如 Amazon 的推荐,它将基于用户本身历史购买数据的推荐,和基于用户当前浏览的物品的推荐,以及基于大众喜好的当下比较流行的物品都在不同的区域推荐给用户,让用户可以从全方位的推荐中找到自己真正感兴趣的物品。

深入推荐机制

这一章的篇幅,将详细介绍各个推荐机制的工作原理,它们的优缺点以及应用场景。

基于人口统计学的推荐

基于人口统计学的推荐机制(Demographic-based Recommendation)是一种最易于实现的推荐方法,它只是简单的根据系统用户的基本信息发现用户的相关程度,然后将相似用户喜爱的其他物品推荐给当前用户,图 2 给出了这种推荐的工作原理。
图 2. 基于人口统计学的推荐机制的工作原理
图 2. 基于人口统计学的推荐机制的工作原理

从图中可以很清楚的看到,首先,系统对每个用户都有一个用户 Profile 的建模,其中包括用户的基本信息,例如用户的年龄,性别等等;然后,系统会根据用户的 Profile 计算用户的相似度,可以看到用户 A 的 Profile 和用户 C 一样,那么系统会认为用户 A 和 C 是相似用户,在推荐引擎中,可以称他们是“邻居”;最后,基于“邻居”用户群的喜好推荐给当前用户一些物品,图中将用户 A 喜欢的物品 A 推荐给用户 C。

这种基于人口统计学的推荐机制的好处在于:

  1. 因为不使用当前用户对物品的喜好历史数据,所以对于新用户来讲没有“冷启动(Cold Start)”的问题。
  2. 这个方法不依赖于物品本身的数据,所以这个方法在不同物品的领域都可以使用,它是领域独立的(domain-independent)。

那么这个方法的缺点和问题是什么呢?这种基于用户的基本信息对用户进行分类的方法过于粗糙,尤其是对品味要求较高的领域,比如图书,电影和音乐等领域,无法得到很好的推荐效果。可能在一些电子商务的网站中,这个方法可以给出一些简单的推荐。另外一个局限是,这个方法可能涉及到一些与信息发现问题本身无关却比较敏感的信息,比如用户的年龄等,这些用户信息不是很好获取。

基于内容的推荐

基于内容的推荐是在推荐引擎出现之初应用最为广泛的推荐机制,它的核心思想是根据推荐物品或内容的元数据,发现物品或者内容的相关性,然后基于用户以往的喜好记录,推荐给用户相似的物品。图 3 给出了基于内容推荐的基本原理。
图 3. 基于内容推荐机制的基本原理
图 3. 基于内容推荐机制的基本原理

图 3 中给出了基于内容推荐的一个典型的例子,电影推荐系统,首先我们需要对电影的元数据有一个建模,这里只简单的描述了一下电影的类型;然后通过电影的元数据发现电影间的相似度,因为类型都是“爱情,浪漫”电影 A 和 C 被认为是相似的电影(当然,只根据类型是不够的,要得到更好的推荐,我们还可以考虑电影的导演,演员等等);最后实现推荐,对于用户 A,他喜欢看电影 A,那么系统就可以给他推荐类似的电影 C。

这种基于内容的推荐机制的好处在于它能很好的建模用户的口味,能提供更加精确的推荐。但它也存在以下几个问题:

  1. 需要对物品进行分析和建模,推荐的质量依赖于对物品模型的完整和全面程度。在现在的应用中我们可以观察到关键词和标签(Tag)被认为是描述物品元数据的一种简单有效的方法。
  2. 物品相似度的分析仅仅依赖于物品本身的特征,这里没有考虑人对物品的态度。
  3. 因为需要基于用户以往的喜好历史做出推荐,所以对于新用户有“冷启动”的问题。

虽然这个方法有很多不足和问题,但他还是成功的应用在一些电影,音乐,图书的社交站点,有些站点还请专业的人员对物品进行基因编码,比如潘多拉,在一份报告中说道,在潘多拉的推荐引擎中,每首歌有超过 100 个元数据特征,包括歌曲的风格,年份,演唱者等等。

基于协同过滤的推荐

随着 Web2.0 的发展,Web 站点更加提倡用户参与和用户贡献,因此基于协同过滤的推荐机制因运而生。它的原理很简单,就是根据用户对物品或者信息的偏好,发现物品或者内容本身的相关性,或者是发现用户的相关性,然后再基于这些关联性进行推荐。基于协同过滤的推荐可以分为三个子类:基于用户的推荐(User-based Recommendation),基于项目的推荐(Item-based Recommendation)和基于模型的推荐(Model-based Recommendation)。下面我们一个一个详细的介绍着三种协同过滤的推荐机制。

基于用户的协同过滤推荐

基于用户的协同过滤推荐的基本原理是,根据所有用户对物品或者信息的偏好,发现与当前用户口味和偏好相似的“邻居”用户群,在一般的应用中是采用计算“K- 邻居”的算法;然后,基于这 K 个邻居的历史偏好信息,为当前用户进行推荐。下图 4 给出了原理图。
图 4. 基于用户的协同过滤推荐机制的基本原理
图 4. 基于用户的协同过滤推荐机制的基本原理

上图示意出基于用户的协同过滤推荐机制的基本原理,假设用户 A 喜欢物品 A,物品 C,用户 B 喜欢物品 B,用户 C 喜欢物品 A ,物品 C 和物品 D;从这些用户的历史喜好信息中,我们可以发现用户 A 和用户 C 的口味和偏好是比较类似的,同时用户 C 还喜欢物品 D,那么我们可以推断用户 A 可能也喜欢物品 D,因此可以将物品 D 推荐给用户 A。

基于用户的协同过滤推荐机制和基于人口统计学的推荐机制都是计算用户的相似度,并基于“邻居”用户群计算推荐,但它们所不同的是如何计算用户的相似度,基于人口统计学的机制只考虑用户本身的特征,而基于用户的协同过滤机制可是在用户的历史偏好的数据上计算用户的相似度,它的基本假设是,喜欢类似物品的用户可能有相同或者相似的口味和偏好。

基于项目的协同过滤推荐

基于项目的协同过滤推荐的基本原理也是类似的,只是说它使用所有用户对物品或者信息的偏好,发现物品和物品之间的相似度,然后根据用户的历史偏好信息,将类似的物品推荐给用户,图 5 很好的诠释了它的基本原理。

假设用户 A 喜欢物品 A 和物品 C,用户 B 喜欢物品 A,物品 B 和物品 C,用户 C 喜欢物品 A,从这些用户的历史喜好可以分析出物品 A 和物品 C 时比较类似的,喜欢物品 A 的人都喜欢物品 C,基于这个数据可以推断用户 C 很有可能也喜欢物品 C,所以系统会将物品 C 推荐给用户 C。

与上面讲的类似,基于项目的协同过滤推荐和基于内容的推荐其实都是基于物品相似度预测推荐,只是相似度计算的方法不一样,前者是从用户历史的偏好推断,而后者是基于物品本身的属性特征信息。
图 5. 基于项目的协同过滤推荐机制的基本原理
图 5. 基于项目的协同过滤推荐机制的基本原理

同时协同过滤,在基于用户和基于项目两个策略中应该如何选择呢?其实基于项目的协同过滤推荐机制是 Amazon 在基于用户的机制上改良的一种策略,因为在大部分的 Web 站点中,物品的个数是远远小于用户的数量的,而且物品的个数和相似度相对比较稳定,同时基于项目的机制比基于用户的实时性更好一些。但也不是所有的场景都是这样的情况,可以设想一下在一些新闻推荐系统中,也许物品,也就是新闻的个数可能大于用户的个数,而且新闻的更新程度也有很快,所以它的形似度依然不稳定。所以,其实可以看出,推荐策略的选择其实和具体的应用场景有很大的关系。

基于模型的协同过滤推荐

基于模型的协同过滤推荐就是基于样本的用户喜好信息,训练一个推荐模型,然后根据实时的用户喜好的信息进行预测,计算推荐。

基于协同过滤的推荐机制是现今应用最为广泛的推荐机制,它有以下几个显著的优点:

  1. 它不需要对物品或者用户进行严格的建模,而且不要求物品的描述是机器可理解的,所以这种方法也是领域无关的。
  2. 这种方法计算出来的推荐是开放的,可以共用他人的经验,很好的支持用户发现潜在的兴趣偏好

而它也存在以下几个问题:

  1. 方法的核心是基于历史数据,所以对新物品和新用户都有“冷启动”的问题。
  2. 推荐的效果依赖于用户历史偏好数据的多少和准确性。
  3. 在大部分的实现中,用户历史偏好是用稀疏矩阵进行存储的,而稀疏矩阵上的计算有些明显的问题,包括可能少部分人的错误偏好会对推荐的准确度有很大的影响等等。
  4. 对于一些特殊品味的用户不能给予很好的推荐。
  5. 由于以历史数据为基础,抓取和建模用户的偏好后,很难修改或者根据用户的使用演变,从而导致这个方法不够灵活。

混合的推荐机制

在现行的 Web 站点上的推荐往往都不是单纯只采用了某一种推荐的机制和策略,他们往往是将多个方法混合在一起,从而达到更好的推荐效果。关于如何组合各个推荐机制,这里讲几种比较流行的组合方法。

  1. 加权的混合(Weighted Hybridization): 用线性公式(linear formula)将几种不同的推荐按照一定权重组合起来,具体权重的值需要在测试数据集上反复实验,从而达到最好的推荐效果。
  2. 切换的混合(Switching Hybridization):前面也讲到,其实对于不同的情况(数据量,系统运行状况,用户和物品的数目等),推荐策略可能有很大的不同,那么切换的混合方式,就是允许在不同的情况下,选择最为合适的推荐机制计算推荐。
  3. 分区的混合(Mixed Hybridization):采用多种推荐机制,并将不同的推荐结果分不同的区显示给用户。其实,Amazon,当当网等很多电子商务网站都是采用这样的方式,用户可以得到很全面的推荐,也更容易找到他们想要的东西。
  4. 分层的混合(Meta-Level Hybridization): 采用多种推荐机制,并将一个推荐机制的结果作为另一个的输入,从而综合各个推荐机制的优缺点,得到更加准确的推荐。

推荐引擎的应用

介绍完推荐引擎的基本原理,基本推荐机制,下面简要分析几个有代表性的推荐引擎的应用,这里选择两个领域:Amazon 作为电子商务的代表,豆瓣作为社交网络的代表。

推荐在电子商务中的应用 – Amazon

Amazon 作为推荐引擎的鼻祖,它已经将推荐的思想渗透在应用的各个角落。Amazon 推荐的核心是通过数据挖掘算法和比较用户的消费偏好于其他用户进行对比,借以预测用户可能感兴趣的商品。对应于上面介绍的各种推荐机制,Amazon 采用的是分区的混合的机制,并将不同的推荐结果分不同的区显示给用户,图 6 和图 7 展示了用户在 Amazon 上能得到的推荐。
图 6. Amazon 的推荐机制 – 首页
图 6. Amazon 的推荐机制 - 首页

图 7. Amazon 的推荐机制 – 浏览物品
图 7. Amazon 的推荐机制 - 浏览物品

Amazon 利用可以记录的所有用户在站点上的行为,根据不同数据的特点对它们进行处理,并分成不同区为用户推送推荐:

  • 今日推荐 (Today’s Recommendation For You): 通常是根据用户的近期的历史购买或者查看记录,并结合时下流行的物品给出一个折中的推荐。
  • 新产品的推荐 (New For You): 采用了基于内容的推荐机制 (Content-based Recommendation),将一些新到物品推荐给用户。在方法选择上由于新物品没有大量的用户喜好信息,所以基于内容的推荐能很好的解决这个“冷启动”的问题。
  • 捆绑销售 (Frequently Bought Together): 采用数据挖掘技术对用户的购买行为进行分析,找到经常被一起或同一个人购买的物品集,进行捆绑销售,这是一种典型的基于项目的协同过滤推荐机制。
  • 别人购买 / 浏览的商品 (Customers Who Bought/See This Item Also Bought/See): 这也是一个典型的基于项目的协同过滤推荐的应用,通过社会化机制用户能更快更方便的找到自己感兴趣的物品。

值得一提的是,Amazon 在做推荐时,设计和用户体验也做得特别独到:

Amazon 利用有它大量历史数据的优势,量化推荐原因。

  • 基于社会化的推荐,Amazon 会给你事实的数据,让用户信服,例如:购买此物品的用户百分之多少也购买了那个物品;
  • 基于物品本身的推荐,Amazon 也会列出推荐的理由,例如:因为你的购物框中有 ***,或者因为你购买过 ***,所以给你推荐类似的 ***。

另外,Amazon 很多推荐是基于用户的 profile 计算出来的,用户的 profile 中记录了用户在 Amazon 上的行为,包括看了那些物品,买了那些物品,收藏夹和 wish list 里的物品等等,当然 Amazon 里还集成了评分等其他的用户反馈的方式,它们都是 profile 的一部分,同时,Amazon 提供了让用户自主管理自己 profile 的功能,通过这种方式用户可以更明确的告诉推荐引擎他的品味和意图是什么。

推荐在社交网站中的应用 – 豆瓣

豆瓣是国内做的比较成功的社交网站,它以图书,电影,音乐和同城活动为中心,形成一个多元化的社交网络平台,自然推荐的功能是必不可少的,下面我们看看豆瓣是如何推荐的。
图 8 . 豆瓣的推荐机制 – 豆瓣电影
图 8 . 豆瓣的推荐机制 - 豆瓣电影

当你在豆瓣电影中将一些你看过的或是感兴趣的电影加入你看过和想看的列表里,并为它们做相应的评分,这时豆瓣的推荐引擎已经拿到你的一些偏好信息,那么它将给你展示如图 8 的电影推荐。
图 9 . 豆瓣的推荐机制 – 基于用户品味的推荐
图 9 . 豆瓣的推荐机制 - 基于用户品味的推荐

豆瓣的推荐是通过“豆瓣猜”,为了让用户清楚这些推荐是如何来的,豆瓣还给出了“豆瓣猜”的一个简要的介绍。

你的个人推荐是根据你的收藏和评价自动得出的,每个人的推荐清单都不同。你的收藏和评价越多,豆瓣给你的推荐会越准确和丰富。
每天推荐的内容可能会有变化。随着豆瓣的长大,给你推荐的内容也会越来越准。

这一点让我们可以清晰明了的知道,豆瓣必然是基于社会化的协同过滤的推荐,这样用户越多,用户的反馈越多,那么推荐的效果会越来越准确。

相对于 Amazon 的用户行为模型,豆瓣电影的模型更加简单,就是“看过”和“想看”,这也让他们的推荐更加专注于用户的品味,毕竟买东西和看电影的动机还是有很大不同的。

另外,豆瓣也有基于物品本身的推荐,当你查看一些电影的详细信息的时候,他会给你推荐出“喜欢这个电影的人也喜欢的电影”, 如图 10,这是一个基于协同过滤的应用。
图 10 . 豆瓣的推荐机制 – 基于电影本身的推荐
图 10 . 豆瓣的推荐机制 - 基于电影本身的推荐

总结

在网络数据爆炸的年代,如何让用户更快的找到想要的数据,如何让用户发现自己潜在的兴趣和需求,无论是对于电子商务还是社会网络的应用都是至关重要的。推荐引擎的出现,使得这个问题越来越被大家关注。但对大多数人来讲,也许还在惊叹它为什么总是能猜到你到底想要些什么。推荐引擎的魔力在于你不清楚在这个推荐背后,引擎到底记录和推理了些什么。

通过这篇综述性的文章,你可以了解,其实推荐引擎只是默默的记录和观察你的一举一动,然后再借由所有用户产生的海量数据分析和发现其中的规律,进而慢慢的了解你,你的需求,你的习惯,并默默的无声息的帮助你快速的解决你的问题,找到你想要的东西。

其实,回头想想,很多时候,推荐引擎比你更了解你自己。

通过第一篇文章,相信大家对推荐引擎有一个清晰的第一印象,本系列的下一篇文章将深入介绍基于协同过滤的推荐策略。在现今的推荐技术和算法中,最被大家广泛认可和采用的就是基于协同过滤的推荐方法。它以其方法模型简单,数据依赖性低,数据方便采集,推荐效果较优等多个优点成为大众眼里的推荐算法“No.1”。本文将带你深入了解协同过滤的秘密,并给出基于 Apache Mahout 的协同过滤算法的高效实现。Apache Mahout 是 ASF 的一个较新的开源项目,它源于 Lucene,构建在 Hadoop 之上,关注海量数据上的机器学习经典算法的高效实现。

感谢大家对本系列的关注和支持。

声明

本人所发表的内容仅为个人观点,不代表 IBM 公司立场、战略和观点。

参考资料

学习

讨论

作者简介

赵晨婷,现就职于 IBM 中国软件开发中心 Web 2.0 开发小组,对 SOA,J2EE,Web 2.0 应用的开发有丰富的经验。主要关注点在数据处理,数据搜索,推荐算法和推荐系统设计等。

马春娥,工作在 IBM CSDL web2.0 team,开发人员,曾参与 Project Zero 和 Lotus Mashup Center 的开发。主要的关注点在 web2.0 领域的数据的建模,数据的处理,数据的可视化,Web2.0 领域的数据的语义,数据的关联等。

提问的智慧:利用决策树进行推荐系统新用户引导

2011/03/31 发表评论

图灵测试大家都很熟悉,通过问答形式来区分人和机器。小时候也做过假托《镜花缘》的逻辑题,需要你通过提问区分两个怪蜀黍谁来自“真话国”谁来自“假话国”。回到现实中,绝大多数推荐系统都无法回避冷启动问题——面对素不相识的用户,需要尽快把握其好恶给出尽量靠谱推荐。这时候通过问问题套瓷观察对方的反应,就是很常见和有效的做法(跟社交场合一样)。考虑到对象是形形色色千差万别的人,如何提出恰当给力的问题,就很值得研究和琢磨了。本文就来讲讲利用决策树的做法,源自论文《Adaptive Bootstrapping of Recommender Systems Using Decision Trees》。

背景
先说点题外话。几周前推荐系统论坛举办的相当成功。(这里感谢组织者的辛苦工作,以及淘宝同学的给力赞助。论坛官方已经放出材料和视频,几位同学的参会总结也相当给力,本文最后将一并给出链接。)

就我个人来讲,Koren博士的talk给我印象最为深刻。首先,极大的改造了我对netflix竞赛的看法。之前个人过于孤陋,觉得类似offline prediction竞赛,基于确定的数据集和目标函数,解决的不过是一个纯数学/算法问题:参赛者不用关心领域知识和用户需求(充其量看看数据的统计分布),不断的调整堆砌模型就ok了,离真正的推荐应用差之甚远。听了一圈发现,这些参赛者对于数据集其实有相当深刻的理解和思考,比如bias和temporal dynamics、用户不同反馈的理解,都很精彩且有启发性。这与实际构建推荐系统在很大程度上是契合的,首先要找到产品需求和数据中的规律,然后再加以利用。

其次,talk内容的针对性很强,不是一些形而上的抽象总结的或偏general的介绍,很多点跟实际应用的联系非常紧密。比如提到的bootstrapping a recommender,正是自己最近在琢磨的一个问题。最近构建的应用新用户比例过半,迫切需要解决对用户的judgement和profiling。由于工作没有深入到这里,之前只有一个大致的想法:人工或者机器找出一些区分度和接受度都较强的item,混合后提供给用户,通过用户的使用反馈逐渐确定其偏好;整个过程即可以是显式的用户引导(比如初始选择喜欢的item),也可以隐式的直接推荐。

结果Koren直接介绍了他们最近在这方面的工作,即《Adaptive Bootstrapping of Recommender System Using Decision Trees》这篇发表在WSDM2011的paper,提出用决策树的方法进行自适应的用户引导和判断。上周花时间找来读了一遍,写的相当清晰也很有意思。这里记下来备忘,如能帮同学们节约些时间更善。

设定
应用场景很明确,就是一个initial interview的过程,依次给出一些item要求用户进行显式的反馈,以此来构建对用户偏好的基本了解。
暂不考虑如何挑选,先来看看候选集合中的种子(即提出的问题)需要满足什么样的条件。作者认为,至少需要考虑以下几个因素:

  • 流行度(popularity)。需要尽量给出流行或用户熟悉的item,更容易让对方接受并做出选择;
  • 区分度(contenttion)。同样很好理解,好恶一边倒的item出现在候选序列中,不能提供多少信息量;
  • 覆盖度(coverage)。这里更多指item的泛化能力。如果这个item只能关联上非常少的其他item,后续真正可做的事情也会非常有限;

以上只是针对单个item,更理想的情况是考虑item间的关联和序列关系,充分利用之前答案的信息来调整后续的对话,打出一套组合拳。

应用于推荐引导的决策树
将决策树应用于推荐引导,是一个很好理解且自然的过程。从根节点开始,向用户提问,每个节点对应一个特定问题(item/电影);依据用户的不同反馈,进入相应的子节点;不断迭代上述过程,直到到达叶子节点或满足其他退出条件。用户的profilling过程,就是一条从根节点到叶子节点的访问路径。
先看看论文中给出的一棵生成树。

论文的工作都是基于Netflix数据集。如图可见,用户有三种回答,喜欢(like)、不喜欢(dislike)和不知道(unknown);rmse值是对落到该节点所有用户预测评分的均方误差,马上会讲到。

基本的构树过程比较简单:

  • 将所有的用户评分数据映射到<like, dislike, unknown>三维空间上。Netflix评分为1-5星,这里将1-3星映射为dislike ,4-5映射为like,未评分则对应unknown;
  • 从根结点开始,选择最佳的分割item,自顶向下建树;
  • 终止条件,同时考虑以下三种:
    • 设定树的最大深度;
    • 设定最佳分割item的误差阈值;
    • 设定当前节点的最少评分数量;

来看看对分割item的评价。整个决策树的优化目标是使得RMSE最小,这里为使树均衡和方便计算,在每个结点使用了和方差。

  • 对于给定用户集合t,我们都可以计算评分的和方差
    • 任选一个item i,可以计算针对该item的平方误差,R(i)是所有对item i评分的用户集合,是集合用户对item i的平均打分;
    • 和方差,即将该用户集合t所有评分item的平方误差相加;
  • 对于给定用户集合t,任选一个item i作为分割,都会将用户分成三组:评分喜欢、评分不喜欢、未评分,分别记为tL(i)、tH(i)、tU(i)。这样可以计算出三个集合的和方差之和。
  • 决策树的每个结点对应一个用户集合,即其父结点的一个特定划分。对于根结点,这个集合就是全体用户;
  • 为每个结点寻找最佳的分割item,就是找到一个item i使得三个集合和方差之和最小:

具体实现中,还有如下的一些考虑:

  • 在计算评分误差时,考虑user bias;
  • 通过将item的损失误差转化为其被选择的概率,支持一定程度上的随机树的生成;
  • 针对性的性能优化
    • tU(i)集合的用户数目是占大多数,通过公式变化转化为对结点全体用户t和tL(i)、tL(i)的运算;
    • 通过数据结构设计,将集合划分实现为对某item对应user数组的排序操作,由于是评分只有三个值,计算复杂度为O(n);

文中给出了构树的伪代码:

建树完成。当用户通过一系列选择到达某结点时,就可以使用该结点用户集合的平均评分来进行预测对各item的喜好,甚至可以基于预测评分得到一个ranked-list提供最简陋的推荐。文中作者也做了相关的讨论:

  • 首先需要考虑对于某个item该结点下用户评分数目过少的情况,这样很容易出现过拟和。因此引入层次平滑(hierarchical smoothing),将父结点对于该item的评分也纳入来考虑,实现的相当精巧;
  • 直接基于预测值排序的推荐可能过于保守,作者建议比较该结点的预测值跟全体用户的平均值,倾向取差值较大的item;

评估
最终的评估还是RMSE,计算测试集上,决策树判定节点的预测得分与用户实际打分的差异。作者对比了HELF和Entropy0(综合popularity和熵)、Var(利用item方差)等方法,如图所见,决策树的方法使用少数几个item的效果要优于其他方法使用20、30个item的结果。


同时还比较了训练集中用户评分数据的多少对效果的影响,基本上符合常识数据越多越靠谱。

评估部分相对讲的较少,有点意犹未尽。

多棵决策树
作者认为可以考虑使用多棵决策树:

  • 互为补充,防止用户对给出的item无感。通过数据分析可知,对于unknown分支上的用户,预测准确率低;
  • 用户界面考虑,更喜欢同一页面下评分多个item(这个地方存疑,不过一次多评几个也没啥坏处);
  • 决策树属于“weak learners”,使用多棵提升准确率;

多棵树的生成参见前述的随机生成,如何合并多棵树的结果,也是很有意思。一般使用均值、线性加权的做法,不是很适用——尤其是考虑对于不同用户不同树的贡献很可能是不同的。作者着重考虑了两类因素:

  • 命中的结点深度。假设反馈越多,判定应该越准;
  • 反馈类型,like、dislike、unknown分别考虑。假设置信度like > dislike >> unknown;

最后作者进行了验证,证明混合多棵树还是能有一定的效果提升。

一些感想

  • 整个思路和实现都并不复杂,简单是种大美。不需要额外的标注、不需要进行用户/item聚类,对于数据充足、缺乏较强领域知识和强悍pm的应用完全可以快速尝试;
  • 对于数据不充足的应用,类似的做法局限性较大。之前也跟几位同学讨论过,或许可以考虑把挖掘目标从领域内的兴趣描述(喜欢什么类型的音乐、电影),转移到对用户通用属性(如性别、年龄段)的挖掘上,带入先验知识再来做处理;

附:推荐系统高峰论坛的其他链接

 

分类:推荐系统 标签:,