张叶银
推荐系统
给用户推荐他可能感兴趣的东西
好友推荐，商品推荐，文档推荐，广告推荐
Amazon, Netflix, Google, Facebook, Youtube……
主流推荐算法
协同过滤
User-based, Item-based
内容过滤
属性的相关性
社会网络
图的方法
推荐系统评测
准确度
覆盖率
多样性
新颖性
Social Graph
好友推荐
关键问题
用户间的亲密度
共同好友数目
个人资料相似程度
用户互动频度
用户的兴趣
二度好友Friends of friends
People you may know
( 1, 2)
1 2
similarity user user
friendset friendset
部门 » 公司
班级 » 学校
实验室 » 班级
…
Strong ties Weak ties
Circles
好友簇
Strong ties
Community Detection
图的连通性
Clique:
例如： ' , ', ,V V V u v uv E 对于任意的u,v
圈子
应用
推荐
隐私控制
新鲜事定制
To weak ties：unsupervised
learning
flat clustering hierarchical clustering
Hierarchical agglomerative Clustering
Hierarchical agglomerative clustering
0
Monotonic
Method: Merge the nearest clusters until a
single cluster is left
Procedure HAC (N points, stop criterion)
{
(1) Initialize n points as n cluster centers;
(2) Iterate over centers until stop criterion is
satisfied:
a. Compute pair-wise similarity between
any two centers
b. Find the nearest pair of centers
c. Merge the two centers
(3) Output the hierarchical clusters.
}
( , )i jsim c c
,
, arg max ( , )i j
i j
i j sim c c
Pair-wise distances
Symmetric similarity matrix
To weak ties
相似性度量
kl
k l
similarity Rij j iv v
To weak ties
选择
特征：
用户交互：
用户关系：
k k
ij ijk A
r a n
{ | , , }argmax
o
i
o
i
o o
i i ijkc
c
r c C j k v
合并
1 1 1 1
1 1 1 1
1 1
,
( , ) ( , ) ( , ),r r r r r ri i j j k k
r r r r r r
i j i jk k
r r r
i j kU C U C U C
U U U C C C
o o o
其中，
评测
缺少标定的数据，主观评价为主
线上数据
个性化推荐
用户偏好
用户兴趣
用户成长
偏好
圈子
年龄，学校，地域，性别……
Data1 Data2 Data3 Datan
展示
偏好的度量
用户行为
访问个人主页、相册，分享，留言，评论等
k k
ij ijk A
r a n
0
0 1 2 3 4 5 6 7 8 9
量化
信息熵
年龄，学校，地域，性别
x =（， ， ， ）≈nonuniform
y =（，， ，）≈uniform
H(x)=****=
H(y)=****=
[ ] ( ) log ( )
x
H x p x p x
好友推荐
首页28个推荐位，从推荐源数据中随机选取
Ranking VS Sampling
Ranking
亲密度
影响力
Sampling
偏好
推荐人群的多样化
新颖性
采样
偏好分布密度函数P(x)未知
0
0 1 2 3 4 5 6 7 8 9
偏好
人群（年龄，性别，学校）
取舍抽样(rejection sampling)
{ ( ) / ( )( )
1 ( )
( )} qp accept dp z kq z
p z dzk
z z
用户兴趣
教育培训/科学
电脑/网络
社会民生
商业/金融理财
生活/家庭
文化/艺术
通讯数码
网络资源
医疗健康
娱乐休闲
运动体育
游戏
……
网站推荐
视频共享
音频/歌曲共享
软件共享
文档/报告共享
华语流行乐
日韩流行乐
欧美流行乐
电影
电视
动漫
华人明星
……
关键词1
关键词2
关键词3
关键词4
关键词5
……
……
……
……
……
……
……
User access
Access log
0
1
文档分类Supervised learning
Labeled
Data 分词 训练
Classifier文档 分词 文档类别
Naïve Bayes
Bayes
1 2 1 2
1 2
( | , ) ( , | ) ( )
( | ) ( | ) ( )
k k k
k k k
p C x x p x x C p C
p x C p x C p C
( | ) ( )( | )
( )
k kp x C p Cp C x p x
Conditional independent
C
X1 X2 X3
priorlikelihood
posterior
内容过滤
公共主页
相关性
cos( , ) ( ) ( ) /Ti j i ji j i jU P U P U P
用户成长
问题1
用户在什么阶段加好友最多？
爆发，还是持续增长？
问题2
用户在什么阶段内，加什么样的好友？
资料？二度好友？陌生人？
好友增长类型
前期爆发 后期爆发
中期爆发 持续增长
0
200
400
600
800
1000
1200
1 5 9 13 17 21 25 29 33 37 4
1
45 49 53 57 6
1
65 69 73 77 8
1
85 89 93 97
0
200
400
600
800
1000
1200
1 5 9 13 17 21 25 29 33 37 4
1
45 49 53 57 6
1
65 69 73 77 8
1
85 89 93 97
0
200
400
600
800
1000
1200
1 5 9 13 17 21 25 29 33 37 4
1
45 49 53 57 6
1
65 69 73 77 8
1
85 89 93 97
0
200
400
600
800
1000
1200
1 5 9 13 17 21 25 29 33 37 4
1
45 49 53 57 6
1
65 69 73 77 8
1
85 89 93 97
前期增长最终达到的好友数目较低
0
50
100
150
200
250
300
平均好友个数
227
278 276 269
前期
中期
后期
持续
不同类型增长好友数
推荐
好友，公共主页，小站，音乐，日志，视频，小组……
年龄a，好友数目n，兴趣i，活跃度d，推荐r
,
( | , , )
( , , , , )
( , , , )
( , , ) ( , , , , )
i
i r
p r a n d
p r a i n dp r a n d
p a n d p r a i n d
52
贝叶斯推理
先验知识：用户成长模型，用户兴趣，用户偏好
年龄
a
兴趣
i
好友
数目
n
推荐
r 活跃度d
1 1
1 2
( | )
( | )
p n a
p n a
1( ) a
1 1
1 2
( | )
( | )
p i a
p i a
1 1 1
1 1 2
1 2 1
1 2 2
( | , )
( | , )
( | , )
( | , )
p r i n
p r i n
p r i n
p r i n
1 1
1 2
( | )
( | )
p d n
p d n
Factorization
( , , , , )
( ) ( | ) ( | ) ( | ) ( | ) ( | )
p a i n r d
p a p i a p n a p r i p r n p d n
谢谢！
