推荐系统介绍——协同过滤，隐语义模型，随机游走
整个项目参考于：https://blog.****.net/sinat_33741547/article/category/6442592，以及对相关学习课程的实践。
项目代码：https://github.com/FairyFali/recommend。
环境依赖：Python3：Pandas,numpy,pickle
目录
基于用户的协同过滤模型
什么是基于用户的协同过滤？
协同过滤（collaborative filtering，简称CF）是利用某兴趣相投、拥有共同经验之群体的喜好来推荐用户感兴趣的信息。
具体步骤如下：
（1）收集用户购买行为和兴趣特点。通过日志文件记录的用户浏览历史，购买历史和评价历史得到用户对商品的喜好程度矩阵user-item矩阵，如图3-15所示。
（2）通过收集的矩阵可以计算用户之间的相似度，如图2所示。相似度高的用户优先作为推荐对象的相似用户。
（3）寻找邻居。选择最相近的k个邻居作为相似用户，如图3所示。
（4）个性化推荐。通过基于用户的方法的思路是，基于邻居和推荐对象的相似度为权重计算推荐对象对某一商品的喜好程度，获得所有未购买商品的预测喜好程度，选择喜好程度最高的n个商品作为推荐商品列表，如图3-17所示，同时也可以使用基于商品的个性化推荐。
（5）评估推荐结果。通过用户实际购买商品和推荐商品做对比，比较结果作为推荐质量的评判。
同理，基于商品的协同过滤则是以商品为单位计算相似度，成为基于物品的协同过滤模型。
UCF方法
基于user的协同过滤，通过不同用户对item的评分来评测用户之间的相似性，基于用户之间的相似性做出推荐。
如何预测用户1对于商品4的喜好程度，如图4所示：
（1）找到和用户1相似的用户且购买过商品4（基于购买记录）即为用户n；
（2）根据用户n对商品4的评价，以相似度为权重回填结果；
（3）针对所有用户组合，重复1~3，直到所有空格都被填满。
根据预测的用户对商品喜好程度，找到用户未购买的喜好程度最高的k个商品推荐个用户即可。
相似度计算
（1）Jaccard 系数：等于样本集交集与样本集合集的比值，即J=|A∩B|/|A∪B|
（2）余弦相似度：又称为余弦相似性。通过计算两个向量的夹角余弦值来评估他们的相似度，即。
预测得分
计算用户对商品的感兴趣程度，我们用下面的公式来求解：
其中u代表用户，i代表商品，S(u,k)包含和用户兴趣最接近的K个用户，N(i)是对物品i有过行为的用户集合，w代表用户u和用户v的相似程度，r代表用户v对物品i的兴趣。
评价方法
（1）基于预测的评估方法
一般来说，推荐系统质量采用平均绝对误差(Mean Absolute Error, MAE)来衡量，通过计算用户推荐商品与实际所购买商品之间的偏差来评估推荐质量。假设系统推荐的商品集为{p1,p2,…,pn}，而用户实际购买的商品集为{q1,q2,…,qn}，则
另外均方根误差(Root Mean Squared Error, RMSE)也是推荐系统的一个评估指标。
MAE和RMSE指标数值越小，则推荐商品和用户实际购买商品集间的差异越小，即系统推荐质量越高。
（2）基于IR的评估方法
召回率和准确率是广泛用于信息检索和统计学分类领域的两个度量值，用来评价结果的质量。其中召回率衡量的是检索系统的查全率，准确率是衡量的是检索系统的查准率。
准确率和召回率虽然没有必然的关系（从上面公式中可以看到），在实际应用中是相互制约的。要根据实际需求，找到一个平衡点，此时，就需要引入F1度量。
（此处没有列出公式计算）
程序代码
相似度程度：
def cos_sim(self, target_items, items):
'''
计算用户1和用户2的余弦相似度
e.g: x = [1 0 1 1 0], y = [0 1 1 0 1]
cosine = (x1*y1+x2*y2+...)
/ [sqrt(x1^2+x2^2+...)+sqrt(y1^2+y2^2+...)]
that means union_len(movies1, movies2)
/ sqrt(len(movies1)*len(movies2))
:param target_items:
:param items:
:return:
'''
# 交集
union_len = len(set(target_items) & set(items))
if union_len==0 : return 0
len1 = len(target_items)
len2 = len(items)
# 分母
product = len1*len2
return union_len/math.sqrt(product)
获得用户相似度前top_n的用户：
def get_top_n_user(self, target_user_id, top_n=10):
'''
获取和目标用户最相似的top_n个用户
:param target_user_id:
:param top_n:
:return:
'''
# 所有的用户id
all_user_ids = set(self.frame['UserID'])
# 其他的用户id，(set对象的^相当于取差集)
other_user_ids = all_user_ids ^ {target_user_id}
# 获取其他所有用户评分过的电影
other_user_items = []
for i in other_user_ids:
other_user_items.append(set(self.frame[self.frame['UserID'] == i]['MovieID'].values))
# 目标用户评分过的电影
target_user_items = set(self.frame[self.frame['UserID']==target_user_id]['MovieID'].values)
# 相似度列表，计算目标用户和所有用户的相似度
sim_list = []
for items in other_user_items:
sim_list.append(self.cos_sim(target_user_items, items))
# 排序（sorted函数将序列排序，zip将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。）
sim_list = sorted(zip(other_user_ids, sim_list),
key=lambda x:x[1], reverse=True)
# 返回前top_n个用户的id和相似度值
return sim_list[:top_n]
获得用户预测得分top_n的电影：
def get_top_n_items(self, target_user_id, top_n=10):
'''
获得前top_n个相似的商品
:param target_user_id:
:param top_n:
:return:
'''
# 获得相似度用户列表
sim_list = self.get_top_n_user(target_user_id)
# 计算所有的相似度总和，做归一化使用（不做也可以，主要是比较大小）
total_sim = sum([i[1] for i in sim_list])
# 相似用户的数据信息，里面存储的相似用户对应的所有的电影的评分集合
sim_user_data = []
for user in sim_list:
sim_user_data.append(
self.frame[self.frame['UserID'] == user[0]])
# 目标用户评分过的电影
target_item_ids = set(self.frame[self.frame['UserID']==
target_user_id]['MovieID'])
# 候选推荐商品，目标用户看过的电影和相似用户看过的电影做差集
candidates_item_ids = self.item_ids ^ target_item_ids
# 对候选列表的电影进行预测得分
interest_list = []
for item_id in candidates_item_ids:
# 所有相似用户对item_id的得分
tmp = []
for user_data in sim_user_data:
if item_id in user_data['MovieID'].values:
tmp.append(user_data[user_data['MovieID']
==item_id]['Rating'].values[0])
else:
# 没看过的算0分
tmp.append(0)
interest = sum([tmp[i]*sim_list[i][1]/total_sim
for i in range(0, len(sim_list))])
interest_list.append([item_id, interest])
# 排序
interest_list = sorted(interest_list, key=lambda x:x[1],
reverse=True)
# 返回top_n得分高的电影
return interest_list[:top_n]
隐语义模型
概述
LFM(latent factor model)隐语义模型，在很多系统中都有对商品进行贴标签的过程，我们可以根据用户对某些标签的喜好程度，来推荐具有这些标签的商品，但是在具体过程中贴的标签就是隐语义，为什么叫做隐语义呢？就是因为每个语义（相当于一个标签）是由计算自动得到的，不是由人去贴上的，也就是说是基于用户的行为自动聚类。
对于某个物品是否属与一个类，完全由用户的行为确定，我们假设两个物品同时被许多用户喜欢，那么这两个物品就有很大的几率属于同一个类。
以下公式便是隐语义模型计算用户u对物品i兴趣的公式：
其中，p为用户兴趣和第k个隐类的关系，q为第k个隐类和物品i的关系，F为隐类的数量，r便是用户对物品的兴趣度。
接下的问题便是如何计算这两个参数p和q了，对于这种线性模型的计算方法，这里使用的是梯度下降法。大概的思路便是使用一个数据集，包括用户喜欢的物品和不喜欢的物品，根据这个数据集来计算p和q。
下面给出公式，对于正样本，我们规定r=1，负样本r=0：
后面的lambda是为了防止过拟合的正则化项。
程序代码
语料生成
主要功能：获得所有的商品字典{userid1:{itemid1:1,itemid2:0},...}。
class Corpus:
# 数据字典位置
items_dict_path = 'data/lfm_items.dict'
@classmethod
def pre_process(cls):
'''
预处理数据，需要存在ratings.csv文件
获得所有的用户id
获得所有的商品id
获得所有的商品字典{userid1:{itemid1:1,itemid2:0},...}
:return:
'''
print('Process 语料生成')
file_path = 'data/ratings.csv'
# 文件数据
cls.frame = pd.read_csv(file_path)
# 所有的用户id
cls.user_ids = set(cls.frame['UserID'])
# 所有的商品id
cls.item_ids = set(cls.frame['MovieID'])
# 所有的商品字典，存储形式为{user_id:{item_id1:0,item_id2:1}}
cls.items_dict = {user_id: cls._get_pos_neg_item(user_id) for user_id in list(cls.user_ids)}
# 保存商品字典
cls.save()
print('Process 语料生成完毕->', cls.items_dict_path)
@classmethod
def save(cls):
'''
保存items_dict到文件
:return:
'''
f = open(cls.items_dict_path, 'wb')
pickle.dump(cls.items_dict, f)
f.close()
@classmethod
def load(cls):
'''
加载items_dict
:return:
'''
f = open(cls.items_dict_path, 'rb')
items_dict = pickle.load(f)
f.close()
return items_dict
@classmethod
def _get_pos_neg_item(cls, user_id):
'''
获得等量的用户喜欢的商品和不喜欢的商品
:param user_id:
:return:
'''
pos_items_ids = set(cls.frame[cls.frame['UserID']
== user_id]['MovieID'])
neg_items_ids = cls.item_ids ^ pos_items_ids
neg_items_ids = list(neg_items_ids)[:len(pos_items_ids)]
item_dict = {}
for i in pos_items_ids:
item_dict[i]=1
for i in neg_items_ids:
item_dict[i]=0
return item_dict
初始化模型
确定训练的参数信息。
model_path = 'data/lfm.model'
def __init__(self):
# 隐类数量
self.class_count = 5
# 迭代次数
self.iter_count = 5
# 学习率
self.lr = 0.02
# 正则项
self.lam = 0.01
# 初始化模型
self._init_model()
def _init_model(self):
'''
获得语料，初始化隐类矩阵
:return:
'''
file_path = 'data/ratings.csv'
self.frame = pd.read_csv(file_path)
self.user_ids = set(self.frame['UserID'])
self.item_ids = set(self.frame['MovieID'])
self.items_dict = Corpus.load()
# 生成正态分布带随机矩阵
array_p = np.random.randn(len(self.user_ids), self.class_count)
array_q = np.random.randn(len(self.item_ids), self.class_count)
# 带索引的隐类矩阵，行是user_id和item_id
self.p = pd.DataFrame(array_p, columns=range(self.class_count),
index=list(self.user_ids))
self.q = pd.DataFrame(array_q, columns=range(self.class_count),
index=list(self.item_ids))
训练模型
def _predict(self, user_id, item_id):
'''
计算用户对商品的兴趣
:param user_id:
:param item_id:
:return:
'''
p = np.mat(self.p.loc[user_id].values)
q = np.mat(self.q.loc[item_id].values).T
r = sum(p*q)
logit = 1/(1+math.exp(-r))
return logit
def _loss(self, user_id, item_id, y, step):
'''
实际的损失值
:param user_id:
:param item_id:
:param y: 实际的喜好
:param step: 迭代到第几步
:return:
'''
e = y - self._predict(user_id, item_id)
print('setp', step, 'user_id', user_id, 'item_id', item_id,
'实际值', y, 'loss', e)
return e
def _optimize(self, user_id, item_id, e):
'''
使用梯度下降的方法对模型进行优化
已知用户对商品的偏差值，调整模型
方法如下,调整第p行和第q行：
E = 1/2 * (y - predict)^2, predict = matrix_p * matrix_q
derivation(E, p) = -matrix_q*(y - predict),
derivation(E, q) = -matrix_p*(y - predict),
derivation（l2_square，p) = lam * p,
derivation（l2_square, q) = lam * q
delta_p = lr * (derivation(E, p) + derivation（l2_square，p))
delta_q = lr * (derivation(E, q) + derivation（l2_square, q))
:param user_id:
:param item_id:
:param e:
:return:
'''
# 梯度
gradient_p = -e * self.q.loc[item_id].values
gradient_q = -e * self.p.loc[user_id].values
# 正则项
l2_p = self.lam*self.q.loc[user_id].values
l2_q = self.lam*self.p.loc[item_id].values
# 乘以学习率
delta_p = self.lr*(gradient_p + l2_p)
delta_q = self.lr*(gradient_q + l2_q)
# 调整
self.p -= delta_p
self.q -= delta_q
def train(self):
'''
训练模型，定期完成
:return:
'''
# 迭代iter_count次
for step in range(0, self.iter_count):
# 遍历，字典中的每一key，value，
for user_id, item_dict in self.items_dict.items():
item_ids = list(item_dict.keys())
# 随机打乱
random.shuffle(item_ids)
# 遍历每一个user_id对应的item_id
for item_id in item_ids:
# 计算偏差
e = self._loss(user_id, item_id,
item_dict[item_id], step)
# 优化
self._optimize(user_id, item_id, e)
# 逐渐降低学习率，避免震荡
self.lr *= 0.9
# 将训练的模型保存下来
self.save()
预测得分
根据训练的模型计算预测得分最高的top_n个用户。
def predict(self, user_id, top_n=10):
'''
给用户推荐
:param user_id:
:param top_n:
:return:
'''
# 加载参数矩阵
self.load()
# print(self.p)
# print(self.q)
# 获得用户看过的电影
pos_items_ids = set(self.frame[self.frame['UserID']
== user_id]['MovieID'])
# 获得用户没有看过的电影
neg_items_ids = self.item_ids ^ pos_items_ids
# 兴趣得分列表
interest_list = []
for i in neg_items_ids:
interest_list.append(self._predict(user_id, i))
# 排序
candidates = sorted(zip(list(neg_items_ids), interest_list),
key=lambda x: x[1], reverse=True)
# 返回前top_n个
return candidates[:top_n]
基于随机游走的PersonRank模型
概述
基于图的推荐方法是很常见的，基本思想是将用户行为数据表示为一系列的二元组，每一个二元组(u,i)代表用户u对物品i产生过行为，这样便可以将这个数据集表示为一个二分图。
假设我们有以下的数据集，只考虑用户喜不喜欢该物品而不考虑用户对物品的喜欢程度，
PageRank简单介绍
PageRank的物理意义：对于一个网页，网络浏览者沿着网页中的超链接进行浏览时，访问到该网页的期望概率
（图片来自Wiki百科）
它的基本思想是，假设网页之前通过超链接相互连接，互联网上的所有网页便构成了一张图。用户随机的打开一个网页，并通过超链接跳转到另一个网页。每当用户到达一个网页，他都有两种选择，停留在当前网页或者通过继续访问其他网页。如果用户继续访问网页的概率为d，那么用户停留在当前网页的概率便是1-d。如果用户继续访问其他网页，则会以均匀分布的方式随机访问当前网页指向的另一网页，这是一个随机游走的过程。当用户多次访问网页后，每一个网页被访问到的概率便会收敛到某个值，而计算出来的结果便可以用于网页排名，我们用以下的公式来表示：
其中PR(i)是网页i被访问到的概率，d代表用户继续访问网页的概率，N为所有网页的数量，in(i)代表所有指向网页i的网页集合，out(j)代表网页j指向的其他网页集合。
PersonRank算法
PersonalRank算法是基于pageRank算法进行了一些变化，在pageRank算法中，计算出来的是每一个顶点相对其他顶点的相关性，代入到我们的用户物品二分图中，这显然不是我们想要的，我们需要的是所有物品相对于特定某个用户的相关性，有公式如下：
对比pageRank，不同点只在于r的值不同，u代表根节点，即我们的目标用户节点，意思便是我们每次都是从目标用户节点出发，进行随机游走，而不同于pageRank的起点是随机从所有网页中进行选择，personalRank算法得出的结果便是所有顶点相对于目标用户结点的相关性。
程序代码
存储图信息
将二分图以字典的形式存储下来，存储到本地文件（可以理解为我们常用的邻接链表）。
class Graph:
graph_path = 'data/prank.graph'
frame = pd.read_csv('data/ratings.csv')
@classmethod
def gen_user_graph(cls, user_id):
'''
获得用户的相连的节点
:param user_id:
:return:
'''
# 获得目标用户的电影列表
item_list = list(set(cls.frame[cls.frame['UserID']== user_id]['MovieID']))
# 该用户节点的链表
graph_dict = {'i'+str(i):1 for i in item_list}
return graph_dict
@classmethod
def gen_item_graph(cls, item_id):
'''
获得商品的相连的节点
:param item_id:
:return:
'''
# 目标节点的用户
user_list = list(set(cls.frame[cls.frame['MovieID']== item_id]['UserID']))
# 该商品节点的链表
graph_dict = {'u'+str(i):1 for i in user_list}
return graph_dict
@classmethod
def gen_graph(cls):
'''
获得图，图中每个节点都是用户或者商品，每一条边代表用户和商品有评分，权重设为1
:return:
'''
# 所有的用户id和商品id
user_ids = list(set(cls.frame['UserID']))
item_ids = list(set(cls.frame['MovieID']))
# 获得图的邻接链表，以字典的形式存储
G = {'u'+str(i):cls.gen_user_graph(i) for i in user_ids}
for i in item_ids:
G['i'+str(i)] = cls.gen_item_graph(i)
return G
@classmethod
def save(cls):
'''
保存图到本地文件
:return:
'''
f = open(cls.graph_path, 'wb')
pickle.dump(cls.gen_graph(), f)
f.close()
@classmethod
def load(cls):
'''
加载图信息
:return:
'''
f = open(cls.graph_path, 'rb')
G = pickle.load(f)
f.close()
return G
初始化
初始化参数，包括随机游走的概率、迭代次数、图数据、游走概率参数。
def __init__(self):
self.prank_path = 'data/prank_{}.model'
self.frame = pd.read_csv('data/ratings.csv')
# 随机游走概率
self.alpha = 0.6
# 迭代次数
self.iter_count = 20
# 图信息
self.graph = Graph.load()
# 存储节点的游走概率
self.params = {i:0 for i in self.graph.keys()}
训练模型
训练每个用户对应的电影的收敛的游走概率值。
def train(self, user_id):
'''
对于目标用户，每一轮将从该节点开始，意味着prob将为1。
节点将按如下公式更新：
对于每个节点，如果节点j的边缘在i之间：
prob_i_j=alpha*prob_j/edge_num_out_of_node_j
prob_i+=prob_i_j
alpha表示随机游走的问题。
:return:
'''
# 起点的概率为1
self.params['u'+str(user_id)] = 1
# 迭代iter_count次
for i in range(self.iter_count):
# tmp存储本次迭代后游走概率的值
tmp = {key : 0 for key in self.graph.keys()}
# 遍历图的节点和对应的边
for node, edges in self.graph.items():
for next,_ in edges.items():
# 对应于边，每个边对应的节点都增加相应的概率根据上次的params
tmp[next] += self.alpha*self.params[node]/len(edges)
# 起点值
tmp['u'+str(user_id)] += 1 - self.alpha
# 把当前的概率值赋给params
self.params = tmp
# 排序
self.params = sorted(self.params.items(), key=lambda x:x[1],
reverse=True)
# 保存到本地
self.save(user_id)
def save(self, user_id):
path = self.prank_path.format(user_id)
f = open(path, 'wb')
pickle.dump(self.params, f)
f.close()
def load(self, user_id):
path = self.prank_path.format(user_id)
f = open(path, 'rb')
self.params = pickle.load(f)
f.close()
预测推荐结果
根据随机游走值排序，获得top_n的推荐结果。
def predict(self, user_id, top_n=10):
'''
预测用户的商品
:param user_id:
:param top_n:
:return:
'''
self.load(user_id)
item_list = list(set(self.frame[self.frame['UserID']
==user_id]['MovieID']))
item_list = ['i'+str(i) for i in item_list]
candicate_list = []
for key,value in self.params:
if key not in item_list and 'u' not in key:
candicate_list.append((key, value))
return candicate_list[:top_n]
项目实战演示
具体见GitHub。
部署环境：
服务器：CentOS7.2 1核/1GB/40GB
Web服务器：Apache2.4+PHP
环境依赖：
Python3：Pandas,numpy,pickle