推荐算法之用户协同过滤
一、概念
用户协同过滤一般是在海量的用户中发掘出一小部分和目标用户品位比较类似的，然后根据他们喜欢的其他东西组织成一个排序的目录作为推荐给目标用户。
可以抽象为user->user->item, 推荐与其相同兴趣的用户喜欢的item，简称user-based
这其中涉及到三个关键点
1、如何收集用户偏好
用户的偏好可以从用户行为中得到。用户行为日志通常存储在分布式数据仓库中,如支持离线分析的Hadoop Hive和支持在线分析的Google Dremel。
用户行为又可以分为显性反馈行为(explicit feedback)和隐性反馈行为(implicit feedback)
为什么显性反馈行为不能完全代表用户偏好
（1）用户大多具有懒惰性，不愿意对物品进行评级：例如大部分人对购买的物品不愿意给出评价，这体现了一种用户懒惰行为
（2）用户可能撒谎或者只给出部分信息：如果某人克服了懒惰性，真的对物品进行评分，该用户也可能撒谎
（3）用户不会更新其评价结果：例如考虑一个大学生Mary,他喜欢评级，十年前他还是个小孩，它给她喜欢的唱片打了5星。基于最新的评价结果，它成了另一名大学生的近邻，但是如果将他小时候听的儿歌推荐给该大学生，将会感觉很奇怪。
举例：视频平台的显示评级和隐式评级的收集场景
早期的推荐系统的关注点在于显式的反馈学习，例如 Netflix 比赛中，需要预测的是用户对物品的显式评分。随着互联网的快速发展，其实大部分的场景下我们能得到的都是隐式反馈，例如新闻的点击，电影的观看，商品的购买等。而用户购买过了一件商品并不代表用户喜欢它，所以很多时候会出现差评的现象；而用户没有购买过的商品，也不代表用户不喜欢它。
2、如何找到相似的用户
当已经对用户行为进行分析得到用户喜好后，可以根据用户喜好计算相似用户。
（1）相似度的计算
参见相似度算法
（2）找到"邻居"
有两种找到邻居的方法：固定数量的邻居（K-neighbors ）或基于相似度门槛的邻居（Threshold-based neighbors）
3、如何给出推荐
基于用户对物品的偏好找到相邻邻居用户，然后将邻居用户喜欢的推荐给当前用户。
二、使用k-最近邻模式的用户协同过滤
所谓最近邻，就是找到距离最近或最相似的用户。而这里，k-最近邻（K Nearest Neighbor）的意思就是，找出最近或最相似的k个用户，将他们的评分（相似度权重求和）最高的几个物品进行推荐。
1、执行步骤
step 1：建立物品-用户倒排表
由于用户之间的交互是稀疏的，可以做一个物品-用户倒排表，从而得到所有交互不为0的用户。
ABCD等是用户，abc等是对应用户喜欢的物品
step 2：建立用户相似度矩阵
利用物品-用户倒排表，构建用户相似度矩阵，其中的值，如 matrix[A][B]表示用户A和用户B共同喜欢的电影的数量
step 3：计算用户相似度
遍历用户相似度矩阵中所有的两两用户，根据两两用户共同喜欢的电影的数量，计算用户相似度.
计算用户相似度的公式如下：
W(uv)表示用户u与v的相似度，作为matrix[u][v]的值
N(u)表示用户u增有过正反馈的物品集合，N(u)表示用户u增有过正反馈的物品集合
改进的用户相似度计算公式：
该公式惩罚了用户u和v共同喜欢的物品中热门物品对他们相似度的影响，以图书为例，如果两个用户都曾经买过《新华字典》，这丝毫不能说明他们的兴趣相似，因为绝大多数中国人小时候都买过《新华字典》。但如果两个用户都买过《数据挖掘导论》，那可以认为他们的兴趣比较相似，因为只有研究数据挖掘的人才会买这本书。换句话说，两个用户对冷门物品采取过同样的行为更能说明他们兴趣的相似度。
i表示用户u和用户v都有过正反馈的物品集合，N(i)表示对物品i有过正反馈的用户数
step 4：针对目标用户u，找到其最相似的K个用户，产生N个推荐
首先，对用户u，在用户相似度中找到与其相似度最高的K个用户
然后，得到相似度最高的K个用户所喜欢而用户u没有接触过的商品i，利用如下的公式计算用户u对物品i的感兴趣程度p(u, i)
W(uv)表示用户u与v的相似度，R(vi)表示用户v对i的兴趣
最后，根据感兴趣程度由高到低确定N个推荐给用户u的物品。
2、代码实现
采用GroupLens提供的MovieLens数据集 ，包含6000多用户对4000多部电影的100万条评分。该数据集是一个评分数据集，用户可以给电影评1-5分5个不同的等级。
本文着重研究隐反馈数据集中TopN推荐问题，因此忽略了数据集中的评分记录。也就是说，TopN推荐的任务是预测用户会不会对某电影评分，而不是预测用户在准备对某部电影评分的前提下会给电影评多少分。
# coding=utf-8
'''
用户协同过滤推荐
'''
import random
import math
from operator import itemgetter
#========================================================
# 核心算法
#========================================================
class UserBasedCF():
def __init__(self):
'''
初始化相关参数
'''
# 找到与目标用户兴趣相似的20个用户，为其推荐10部电影
self.n_sim_user = 20
self.n_rec_item = 10
# 训练用的数据集
self.dataSet = {}
# 用户相似度矩阵
self.user_sim_matrix = {} # 使用典中典模拟矩阵
self.item_count = 0
print('配置:邻居用户数 = %d' % self.n_sim_user)
print('配置:推荐数 = %d' % self.n_rec_item)
def load_file(self, filename):
'''
读文件，返回文件的每一行
INPUT -> 文件名
'''
with open(filename, 'r') as f:
for i, line in enumerate(f):
if i == 0: # 去掉文件第一行的title
continue
yield line.strip('\r\n')
print('Load %s success!' % filename)
def get_dataset(self, filename):
'''
读文件得到评分数据
INPUT -> 文件名
'''
dataSet_len = 0
for line in self.load_file(filename):
user, item, rating, timestamp = line.split('::')
self.dataSet.setdefault(user, {})
# 键中键：形如{'1': {'1287': '2.0', '1953': '4.0', '2105': '4.0'}, '2': {'10': '4.0', '62': '3.0'}}
# 用户1看了id为1287的电影，打分2.0
self.dataSet[user][item] = rating
dataSet_len += 1
print('样本量 = %s' % dataSet_len)
def userSimilarity(self):
'''
计算用户间相似度
'''
print("STEP1:构建item-user表...")
item_user = {}
for user, items in self.dataSet.items():
for item in items:
if item not in item_user:
item_user[item] = set()
item_user[item].add(user)
self.item_count = len(item_user)
print("item-user表构建完成! 总物品数:%d" % self.item_count)
print('STEP2:利用倒排表构建用户间相似度矩阵...')
for item, users in item_user.items():
for u in users:
for v in users:
if u == v:
continue
self.user_sim_matrix.setdefault(u, {})
self.user_sim_matrix[u].setdefault(v, 0) # 默认相似度为0
weight = 1
# 根据热门程度加权
# weight = 1 / math.log2(1+len(users))
self.user_sim_matrix[u][v] += weight
print('用户间相似度矩阵构建完成!')
print('STEP3:计算用户间相似度 ...')
for u, related_users in self.user_sim_matrix.items():
for v, count in related_users.items(): # count表示用户u和v都看过电影数
# 计算用户相似度
self.user_sim_matrix[u][v] = count / math.sqrt(len(self.dataSet[u]) * len(self.dataSet[v]))
print('用户间相似度计算完成!')
def recommend(self, user):
'''
针对目标用户，找到其最相似的K个用户，产生N个推荐
INPUT -> 待推荐用户
'''
K = self.n_sim_user
N = self.n_rec_item
rank = {}
watched_items = self.dataSet[user]
for v, sim in sorted(self.user_sim_matrix[user].items(), key=itemgetter(1), reverse=True)[0:K]: # 按维度1(用户相似度)降序排列，取前K个
for item, interest in self.dataSet[v].items(): # 遍历邻居v看过的电影及对该电影的兴趣程度
if item in watched_items: # 如果user已看过这部电影，跳过
continue
rank.setdefault(item, 0)
rank[item] += float(sim) * float(interest) # 计算user对电影item的感兴趣程度
return sorted(rank.items(), key=itemgetter(1), reverse=True)[0:N] # 返回user感兴趣程度最高的N部电影
#========================================================
# 主程序
#========================================================
if __name__ == '__main__':
rating_file = 'ratings2.csv'
# 初始化
userCF = UserBasedCF()
# 读取评分文件
userCF.get_dataset(rating_file)
# 构建用户相似度矩阵
userCF.userSimilarity()
