今年抖音非常火爆和流行,我们在刷抖音的时候,经常会发现给我们刷到自己微信或者是抖音好友喜欢的小视频,这里很多人都就会很好奇,抖音怎么知道这些人是我的好友,甚至知道我和好友的兴趣就一样呢,这就有了基于社交网络数据的推荐算法。ps:抖音的推荐是多种算法实现的,基于社交网络数据应该只是其中的一个分支。
社会化推荐之所以受到很多网站的重视,是缘于如下优点:
1. 好友推荐可以增加推荐的信任度 好友往往是用户最信任的。用户往往不一定信任计算机的智能,但会信任好朋友的推荐。同样是给用户推荐《天龙八部》,前面提到的基于物品的协同过滤算法会说是因为用户之前看过《射雕英雄传》,而好友推荐会说是因为用户有8个好友都非常喜欢《天龙八部》。对比这两种解释,第二种解释一般能让用户更加心动,从而购买或者观看《天龙八部》。
2. 社交网络可以解决冷启动问题 当一个新用户通过微博或者抖音账号登录网站时,我们可以从社交网站中获取用户的好友列表,然后给用户推荐好友在网站上喜欢的物品。从而我们可以在没有用户行为记录时就给用户提供较高质量的推荐结果,部分解决了推荐系统的冷启动问题。
当然,社会化推荐也有一些缺点,其中最主要的就是很多时候并不一定能提高推荐算法的离线精度(准确率和召回率)。特别是在基于社交图谱数据的推荐系统中,因为用户的好友关系不是基于共同兴趣产生的,所以用户好友的兴趣往往和用户的兴趣并不一致。
-
原理
如果给定一个社交网络和一份用户行为数据集。其中社交网络算法是给用户推荐好友喜欢的物品集合。即用户
u
u
u
对物品
i
i
i
的兴趣
p
u
i
p_{ui}
p
u
i
可以通过如下公式计算:
p
u
i
=
∑
v
∈
o
u
t
(
u
)
r
v
i
{p_{ui}} = \sum\limits_{v \in out(u)} {r_{vi}}
p
u
i
=
v
∈
o
u
t
(
u
)
∑
r
v
i
其中
o
u
t
(
u
)
out(u)
o
u
t
(
u
)
是用户
u
u
u
的好友集合,如果用户
v
v
v
喜欢物品
i
i
i
,则
r
v
i
=
1
r_{vi}=1
r
v
i
=
1
,否则
r
v
i
=
0
r_{vi}=0
r
v
i
=
0
。不过,即使都是用户
u
u
u
的好友,不同的好友和用户
u
u
u
的熟悉程度和兴趣相似度也是不同的。因此,我们应该在推荐算法中考虑好友和用户的熟悉程度以及兴趣相似度:
p
u
i
=
∑
v
∈
o
u
t
(
u
)
w
u
v
r
v
i
{p_{ui}} = \sum\limits_{v \in out(u)} {w_{uv}}{r_{vi}}
p
u
i
=
v
∈
o
u
t
(
u
)
∑
w
u
v
r
v
i
这里,
u
v
w
u_{vw}
u
v
w
由两部分相似度构成,一部分是用户
u
u
u
和用户
v
v
v
的熟悉程度,另一部分是用户
u
u
u
和用户
v
v
v
的兴趣相似度,我们分别用如下公式表示:
f
a
m
i
l
i
a
r
i
t
y
(
u
,
v
)
=
∣
o
u
t
(
u
)
∩
o
u
t
(
v
)
∣
∣
o
u
t
(
u
)
∪
o
u
t
(
v
)
∣
{familiarity(u, v)} ={\frac{|out(u) \cap out(v)|}{|out(u) \cup out(v)|}}
f
a
m
i
l
i
a
r
i
t
y
(
u
,
v
)
=
∣
o
u
t
(
u
)
∪
o
u
t
(
v
)
∣
∣
o
u
t
(
u
)
∩
o
u
t
(
v
)
∣
s
i
m
i
l
i
a
r
i
t
y
(
u
,
v
)
=
∣
N
(
u
)
∩
N
(
v
)
∣
∣
N
(
u
)
∪
N
(
v
)
∣
{similiarity(u, v)} ={\frac{|N(u) \cap N(v)|}{|N(u) \cup N(v)|}}
s
i
m
i
l
i
a
r
i
t
y
(
u
,
v
)
=
∣
N
(
u
)
∪
N
(
v
)
∣
∣
N
(
u
)
∩
N
(
v
)
∣
其中
o
u
t
(
u
)
,
o
u
t
(
v
)
out(u),out(v)
o
u
t
(
u
)
,
o
u
t
(
v
)
代表用户
u
u
u
,
v
v
v
的好友集合,
N
(
u
)
,
N
(
v
)
N(u), N(v)
N
(
u
)
,
N
(
v
)
代表用户
u
u
u
,
v
v
v
的共同兴趣集合。
-
实例分析
-
数据处理
下面两个表格分别为自己编的用户好友数据与用户兴趣数据:
用户 | 好友 |
---|---|
A | B,C,D |
B | A,C |
C | A,B,D |
D | A,C,E |
E | D |
用户 | 兴趣 |
---|---|
A | 篮球,乒乓球 |
B | 羽毛球,篮球,足球 |
C | 乒乓球,桌球,足球 |
D | 足球,羽毛球,篮球 |
E | 乒乓球,桌球,篮球,棒球 |
规范数据集,具体需要什么样的数据,具体情况具体分析:
def load_data(friend_file, interest_file): # 规范数据集
fri_f = open(friend_file, "r", encoding="utf-8")
int_f = open(interest_file, "r", encoding="utf-8")
friends_data = dict()
for line in fri_f:
data = line.strip().split("\t")
friends_data[data[0]] = data[1].split(",")
interests_data = dict()
for line in int_f:
data = line.strip().split("\t")
interests_data[data[0]] = data[1].split(",")
fri_f.close()
int_f.close()
print("好友数据集: ", friends_data)
print("兴趣数据集: ", interests_data)
return friends_data, interests_data
好友数据集: {'A': ['B', 'C', 'D'], 'B': ['A', 'C'], 'C': ['A', 'B', 'D'], 'D': ['A', 'C', 'E'], 'E': ['D']}
兴趣数据集: {'A': ['篮球', '乒乓球'], 'B': ['羽毛球', '篮球', '足球'], 'C': ['乒乓球', '桌球', '足球'], 'D': ['足球', '羽毛球', '篮球'], 'E': ['乒乓球', '桌球', '篮球', '棒球']}
-
构建倒排列表
由
推荐系统实践(一)—-基于用户的协同过滤算法(UserCF)
,我们知道计算用户相似度,必须构建倒排列表,方法和前面博文相同。
def user_friend_interest(friends_data, interests_data): # 构建倒排列表
friends_dic = dict()
for user, friends in friends_data.items():
for friend in friends:
if friend not in friends_dic:
friends_dic[friend] = set()
friends_dic[friend].add(user)
interests_dic = dict()
for user, interests in interests_data.items():
for interest in interests:
if interest not in interests_dic:
interests_dic[interest] = set()
interests_dic[interest].add(user)
print("好友数据倒排列表: ", friends_dic)
print("兴趣数据倒排列表: ", interests_dic)
return friends_dic, interests_dic
获得下面倒排列表:
好友数据倒排列表: {'B': {'C', 'A'}, 'C': {'D', 'B', 'A'}, 'D': {'E', 'C', 'A'}, 'A': {'B', 'C', 'D'}, 'E': {'D'}}
兴趣数据倒排列表: {'篮球': {'D', 'E', 'B', 'A'}, '乒乓球': {'E', 'C', 'A'}, '羽毛球': {'B', 'D'}, '足球': {'B', 'C', 'D'}, '桌球': {'E', 'C'}, '棒球': {'E'}}
-
相似度计算
有了倒排列表我们就可以计算用户的好友熟悉度与用户兴趣相似度,两者计算方法相同,所以我们这里就只写一个了:
def similarity(data): # 好友熟悉度
C = dict()
N = dict()
for user, friends in data.items():
for u in friends:
N.setdefault(u, 0)
N[u] += 1 # 计算每个用户好友数量
for v in friends:
if u == v:
continue
C.setdefault(u, {})
C[u].setdefault(v, 0)
C[u][v] += 1 # 计算共同好友数量
W = dict()
for u, related_users in C.items():
for v, cuv in related_users.items():
W.setdefault(u, {})
W[u].setdefault(v, 0)
W[u][v] = cuv / math.sqrt(N[u] * N[v])
return W
最终获取到的用户熟悉度和兴趣相似度为:
用户-好友熟悉度: {'C': {'A': 0.6666666666666666, 'E': 0.5773502691896258, 'B': 0.4082482904638631, 'D': 0.3333333333333333}, 'A': {'C': 0.6666666666666666, 'B': 0.4082482904638631, 'D': 0.3333333333333333, 'E': 0.5773502691896258}, 'B': {'D': 0.8164965809277261, 'A': 0.4082482904638631, 'C': 0.4082482904638631}, 'D': {'B': 0.8164965809277261, 'A': 0.3333333333333333, 'C': 0.3333333333333333}, 'E': {'C': 0.5773502691896258, 'A': 0.5773502691896258}}
用户-兴趣相似度: {'B': {'D': 1.0, 'E': 0.2886751345948129, 'A': 0.4082482904638631, 'C': 0.3333333333333333}, 'D': {'B': 1.0, 'E': 0.2886751345948129, 'A': 0.4082482904638631, 'C': 0.3333333333333333}, 'E': {'B': 0.2886751345948129, 'D': 0.2886751345948129, 'A': 0.7071067811865475, 'C': 0.5773502691896258}, 'A': {'B': 0.4082482904638631, 'D': 0.4082482904638631, 'E': 0.7071067811865475, 'C': 0.4082482904638631}, 'C': {'E': 0.5773502691896258, 'A': 0.4082482904638631, 'B': 0.3333333333333333, 'D': 0.3333333333333333}}
-
推荐
由上面的公式,可以利用python实现如下逻辑:
def Recommend(user, familiarity, similarity, train): # 假设对每个物品的喜欢程度都为1
pw = 1
rank = dict()
interacted_items = train[user] # 获取user感兴趣的物品
rank = dict()
for fid, fw in familiarity[user].items():
for item in train[fid]:
if item in interacted_items:
continue
rank.setdefault(item, 0)
rank[item] = fw * pw
for vid, sw in similarity[user].items():
for item in train[vid]:
if item in interacted_items:
continue
rank.setdefault(item, 0)
rank[item] = sw * pw
rank = sorted(rank.items(),key = lambda x:x[1],reverse = True) # 按兴趣度排序
return rank
最终我们对用户
A
A
A
进行推荐,获得下面的排序列表:
为用户A推荐兴趣列表: [('棒球', 0.7071067811865475), ('桌球', 0.4082482904638631), ('足球', 0.4082482904638631), ('羽毛球', 0.4082482904638631)]
-
代码分析
基于邻域社会化推荐算法