pierrelai

档案

作者存档

数据分析站点导航[转]

2011/06/27 pierrelai 留下评论

中文互联网数据资料来源
平台机构	易观国际	互联网信息中心	淘宝数据平台	百度数据研究中心
	艾瑞咨询	电子商务研究中心	IDC中国	百度数据中心
	计世资讯	互联网数据中心	智库数据	梅花网
	CNZZ数据中心	缔元信互联网数据	第一财经	中国经济网数据中心
	投资界	赛迪顾问
				>>>待补充

分析论坛	人大经济论坛	中国商业智能网	中国统计网	SAS爱好者
	市场调研论坛	数据挖掘研究院	数据挖掘论坛	SAS中文论坛
	沃顿知识在线	中国数据分析网	数据仓库之路	SPSS论坛
	统计家园	BI Think商业智能网	统计之都	中文自然语言处理
	智能中国网	EXCEL HOME技术论坛	百岛潮论坛	经济学家
				>>>待补充

其他	月光博客	互联网的那点事	中文互联网数据资讯中心
	36氪	游戏大观	洪波的偏见	亿邦电商
	草根网	互联网的一些事	游戏邦	关于营销的那点事
	派代网	IT 商业新闻网	业网内	网络推广方案
	中国网站排名
				>>>待补充
中文博客站点
数据挖掘与分析	小蚊子乐园	数据挖掘与数据分析	数据挖掘者	未来趋势—车品觉
	数据化管理	沈浩老师	数据文化	数据挖掘营销应用
	郑来轶	ExcelPro的图表博客	数据元素	庖丁的小刀
	让数据说话	Flystarhj的博客	数据小兵	SAS数据挖掘
	数据&分析	统计软件学习	图说企业文化	Keep On Fighting
	数据之路	数据分析与研究	诸葛小川	小象的博客
	杜牛牛	SAS博客列表
				>>>待补充

网站分析	网站数据分析	网站分析在中国	MAR’S 观点	上海WA非官方组织
	网站分析	Tenly的互联网哲学	在线广告分析	邮件营销在中国
	香港网站分析	蓝鲸的网站分析笔记	搜索引擎营销	So Marketing博客
	SOYAN天空	网站分析与电子商务	搜索营销智库	数据营销宝典
	芒果运营	Keven网站分析博客	像风一样自由	IWOM研究
	CIC网络口碑	互联网营销博客
				>>>待补充

用户研究	腾讯用户研究	UCD中国用户研究	淘宝用户研究	阿里用户研究
	当当用户研究	支付宝用户研究	搜狐用户研究	顺网用户研究
	网易用户研究	百度泛用户体验	口碑用户研究	5173用户研究
	19楼用户研究
				>>>待补充

来自于：http://blog.sina.com.cn/s/blog_4ecd024b0100sjuv.html

可关注于：http://www.itongji.cn/data/

分类：数据分析标签：网站导航, 常用网站, 数据分析

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

2011/04/29 pierrelai 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包的做图功能绘制相应的网络图。

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()函数，更多细节及其他算法可以查看帮助文档。

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

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()函数能够简单地计算网络中各个节点的中间度。

## png("betweenness.png", width = 500, height = 500)

plot(betweenness(gg, directed = FALSE))

## dev.off()

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

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个节点，基本上都有比较合理的解释，其中有三个人是“高中校友”兼“大学校友”，而另外两个则沟通了“网络好友”与“大学好友”。

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

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

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春季实习生招聘正式启动

2011/04/17 pierrelai 留下评论

Q&A：支付宝招聘新浪微博

分类：互联网的那些事标签：2011, 实习生, 招聘, 支付宝

分析是一种状态

2011/04/16 pierrelai 留下评论

之前听了前易观分析师曹飞的一个分享，整理下

先说说自己的感想：分析师一种状态，一语点破，对于一个分析师来说，不光要通晓数据分析的方法，更重要的是要了解业务，而业务的熟悉不是一本书之类的能够完成完成，更重要的是对业务在生活中的点点积累，因此也可以说这是一种状态，多思考，多积累。

分析思路大致分为以下两类：归纳法和演绎法

归纳法：

自顶向下，演绎，预测，比如易观

容易出现认为天鹅有黑有白还有其他，没有数据，但是有很好的经验

演绎法：

自底向上、归纳、调研

样本的获取不科学容易造成错误，有大量的数据

分析师的价值与使命

描述、预测、决策

对于不同的人告知的信息不同（车品觉博客文章）

由于分析师不参与直接的商业运营，因此可以保持观点中立；

分析师眼中的商机面向整个产业，而不是商业个体（这可以是对于一个产业分析师而已）。

成功的分析师，他们拥有：

超强的商业意识：什么广告都看，注意身边的人和事

超大的信息量：公开的信息，熟知业务，企业的招聘可以看出~~~

严谨的思考：加工

精彩的表达：输出

成功的分析师，他们这样思考行业~~

定义和分类:分类是否穷尽可以看出一个人是否思考严谨

历史路径（时间轴）

产业链思维：思考要有逻辑

企业代表行业：行业脱离不了企业

假设式思维（预测和决策）：一定抛出论据

成功的分析师，他们这样研究企业~~

研习历史

研究老板

辩证式思维：研究企业哪些是好，哪些是不好

代入式思维（预测和决策）：如果你是马云你会怎么样~~

行业发展对比

拉卡拉和分众，按终端等，类似的产业链，类似的趋势

不同视角呈现能够看到不同的东西

其实就是还是要多思考

分类：数据分析标签：分析状态, 数据分析, 产业

MapReduce实现Monte Carlo特征选择的可行性概述

2011/04/04 pierrelai 留下评论

第一节：monte carlo特征选择过程

用monte carlo的思路来实现高维特征的选择，其实有点类似于随机森林的过程，但选择指标进行了改进，下面主要介绍一种自己在研究生阶段所用到的方法。

先看一张方法的框图：

方法不但考虑分类率，还考虑构成决策树各结点的基因对整体的重要性，因为当某个基因作为一棵决策树的分裂结点的属性时，如果其包含的信息量越多，那么对决策树分类率的作用也越大。因此定义某个变量（特征）的相对重要性指标为，具体定义为

从框图中可以看出，整个过程按照随机森林的思想对数据进行多次抽样分配。首先对原始数据进行c次重采样，把数据分成c组训练集和测试集；然后从特征中随机选择m个特征来构建决策树，在这过程中共随机选择了s次，而每次构建t棵决策树；最后整个过程得到cst棵决策树，计算每个特征的相对重要性指标值RI后，排序后得到重要特征。

第二节：MapReduce原理概述

用书中天气预报的例子说明下MapReduce大致原理

假设我们需要处理一批有关天气的数据，其格式如下：

按照ASCII码存储，每行一条记录
每一行字符从0开始计数，第15个到第18个字符为年
第25个到第29个字符为温度，其中第25位是符号+/-

0067011990999991950051507+0000+

0043011990999991950051512+0022+

0043011990999991950051518-0011+

0043012650999991949032412+0111+

0043012650999991949032418+0078+

0067011990999991937051507+0001+

0043011990999991937051512-0002+

0043011990999991945051518+0001+

0043012650999991945032412+0002+

0043012650999991945032418+0078+

现在需要统计出每年的最高温度。

Map-Reduce主要包括两个步骤：Map和Reduce

每一步都有key-value对作为输入和输出：

map阶段的key-value对的格式是由输入的格式所决定的，如果是默认的TextInputFormat，则每行作为一个记录进程处理，其中key为此行的开头相对于文件的起始位置，value就是此行的字符文本
map阶段的输出的key-value对的格式必须同reduce阶段的输入key-value对的格式相对应

对于上面的例子，在map过程，输入的key-value对如下：

(0, 0067011990999991950051507+0000+)

(33, 0043011990999991950051512+0022+)

(66, 0043011990999991950051518-0011+)

(99, 0043012650999991949032412+0111+)

(132, 0043012650999991949032418+0078+)

(165, 0067011990999991937051507+0001+)

(198, 0043011990999991937051512-0002+)

(231, 0043011990999991945051518+0001+)

(264, 0043012650999991945032412+0002+)

(297, 0043012650999991945032418+0078+)

在map过程中，通过对每一行字符串的解析，得到年-温度的key-value对作为输出：

(1950, 0)

(1950, 22)

(1950, -11)

(1949, 111)

(1949, 78)

(1937, 1)

(1937, -2)

(1945, 1)

(1945, 2)

(1945, 78)

在reduce过程，将map过程中的输出，按照相同的key将value放到同一个列表中作为reduce的输入

(1950, [0, 22, –11])

(1949, [111, 78])

(1937, [1, -2])

(1945, [1, 2, 78])

在reduce过程中，在列表中选择出最大的温度，将年-最大温度的key-value作为输出：

(1950, 22)

(1949, 111)

(1937, 1)

(1945, 78)

其逻辑过程可用如下图表示：

第三节：MapReduce实现monte carlo特征选择

mapreduce有两个主要特性：

MapReduce基本架构 Master-Slave 模型， Master负责任务(Task) 和数据和运算的切分，和分发，分发到集群的各节点上； Slave 在这里叫 Worker，负责执行Master分发的任务；
Map Reduce 的运算过程是先分后合。
Map 意思直译为映射，不过理解为“分治”更容易懂。就是将数据和运算进行切分，并分发到集群节点上；
Reduce (本意是减少，所以初看名称时一直不理解减少为合意), 这里应该理解为该词的另一个意思，“归并”，就是将分开执行的众多计算任务和数据进行合并，形成最终的输出结果。

而monte carlo的过程从结构上来说也是mater slave结果，如下图：

同样，它也是一个先分发计算，后合并得到结果的过程。

在这里k为每一个特征的编号，而v为每一次计算RI的值，简图如下：

在map阶段计算各个master上的特征的RI值；

shuffle过程归并每一个特征的RI值；

reduce过程计算每一个特征的总RI值，进行求和计算；

output阶段，这种背景下可以直接输出，而由于monte carlo算法的时间消耗点在map过程，因此可以使用1个reduce，然后直接将结果输出。

本人只是一个可行性分析，没有具体操作实现过，如有错误忘谅解。

by pierrelai

分类：Hadoop, 数据挖掘标签：特征选择, hadoop, map reduce, moner carlo, 数据分析, 数据挖掘

简约风格的摄影照片范例

2011/03/31 pierrelai 留下评论

今天收集分享：40张简约风格的摄影照片范例，希望有你喜欢的。

Minimalist Photography

Minimalist street lamp

Minimalist Photography

the docks

That is probably what we looked like during the flight to Europe…

Nothing Can Happen to Us

Minimalist Photography

Seeing the future in my crystal ball

Verde que te quiero verde…

分类：五彩生活标签：简约, 摄影

Google推“+1”社交搜索功能与Facebook竞争

2011/03/31 pierrelai 留下评论

北京时间3月31日凌晨消息，谷歌将于周三推出一个“+1”按钮，用户可以通过点击该按钮，向好友推荐特定搜索结果。

“+1”按钮会出现在谷歌搜索结果的旁边。目前，仅有部分用户能够使用这一功能。分析人士认为，这是谷歌为其产品增添社交网络特性，与Facebook竞争的重要举措。

Facebook一年前即已推出“赞”(Like)按钮，用户可通过点击该按钮，表达对某段内容的喜爱。这种个性化推荐系统被视为对传统搜索引擎的排名算法的挑战。

谷歌去年的营收高达290亿美元，其中很大一部分来自搜索广告。因此，对这家科技巨头而言，保持作为互联网信息主要来源的地位至关重要。

谷歌表示，“+1”按钮还会出现在谷歌显示广告旁边。谷歌高层周二表示，内部测试表示，加入推荐系统后，人们点击广告的几率更高。

此外，谷歌最终将允许第三方网站在自己的页面上使用“+1”按钮。

谷歌工程师马特·卡茨(Matt Cutts)表示，“+1”按钮是谷歌搜索技术演进的一部分，而不是对Facebook“赞”按钮的直接回应。

谷歌2009年推出了社交搜索。今年2月，该公司开始在一切曾被Twitter用户分享的搜索结果下方显示特殊片段。

目前，谷歌并未对排名算法做出调整，这意味着“+1”推荐尚未对搜索结果排名造成影响。某条被“+1”的搜索结果只有在本来就处于较靠前的位置时，用户才有可能看到它。

谷歌搜索“+1”按钮使用演示

卡茨表示，谷歌正在进行评估，以决定是否将“+1”推荐作为排名要素之一。

如需使用这一新的推荐系统，用户必须创建一个谷歌个人主页(Google Profile)。用户的每一个“+1”推荐都会在他们的联系人网络中公开可见，而该网络是基于谷歌产品中现有的联系人系统，如谷歌电子邮件系统Gmail等。

卡茨表示，谷歌明确告知用户，一切“+1”推荐都是公开的，希望以此消除这一新功能可能带来的任何隐私疑虑。

新功能将于当地时间本周三向少量美国用户开放，其他美国用户可在当天晚些时候注册、体验“+1”按钮。(彦飞)

来自：http://www.alibuybuy.com/posts/57569.html

分类：互联网的那些事标签：社交, facebook, google, 搜索

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

2011/03/31 pierrelai 留下评论

图灵测试大家都很熟悉，通过问答形式来区分人和机器。小时候也做过假托《镜花缘》的逻辑题，需要你通过提问区分两个怪蜀黍谁来自“真话国”谁来自“假话国”。回到现实中，绝大多数推荐系统都无法回避冷启动问题——面对素不相识的用户，需要尽快把握其好恶给出尽量靠谱推荐。这时候通过问问题套瓷观察对方的反应，就是很常见和有效的做法（跟社交场合一样）。考虑到对象是形形色色千差万别的人，如何提出恰当给力的问题，就很值得研究和琢磨了。本文就来讲讲利用决策树的做法，源自论文《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的应用完全可以快速尝试；
对于数据不充足的应用，类似的做法局限性较大。之前也跟几位同学讨论过，或许可以考虑把挖掘目标从领域内的兴趣描述（喜欢什么类型的音乐、电影），转移到对用户通用属性（如性别、年龄段）的挖掘上，带入先验知识再来做处理;

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

官方资料：http://www.resysforum.org/info.html
wangyuantao《2011推荐系统高峰论坛——参后感》（需翻墙）：http://todwang.blogspot.com/2011/03/2011.html
wentrue《2011推荐系统峰会及全民娱乐》：http://www.wentrue.net/blog/?p=1208
chen_lst《2011推荐系统论坛游记：爱的反义词不是恨》：http://www.resyschina.com/2011/03/2011_forum_restropectio.html

分类：推荐系统标签：决策树, 推荐系统

偏好分析强悍图

2011/03/29 pierrelai 留下评论

分类：数据分析标签：sns, 偏好分析, 互联网

Older Entries

Dataing 数据驱动未来

档案

数据分析站点导航[转]

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

一、读取数据

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

三、子群分割

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

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

支付宝2011春季实习生招聘正式启动

分析是一种状态

MapReduce实现Monte Carlo特征选择的可行性概述

第一节：monte carlo特征选择过程

第二节：MapReduce原理概述

第三节：MapReduce实现monte carlo特征选择

推荐引擎初探

简约风格的摄影照片范例

Google推“+1”社交搜索功能与Facebook竞争

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

偏好分析强悍图

文章分类

最新文章

标签

我关注的

我还关注

我还在

链接分享

归档

Twitter

邮件订阅

Blog Stats

功能