推荐系统实践学习笔记
1 好的推荐系统 1.1 什么是推荐系统
推荐系统和搜索引擎都是为了帮助用户从大量信息中找到自己感兴趣的信息。区别是搜索引擎由用户主动提供关键词来查找信息，推荐系统则不需要，而通过分析用户的历史行为给用户的兴趣建模，主动给用户推荐他们可能感兴趣的信息。
从物品的角度出发，推荐系统可以更好地发掘物品的长尾。长尾商品往往代表了一小部分用户的个性化需求，发掘这类信息正是推荐系统的长项。
1.2 个性化推荐系统的应用
推荐系统广泛存在于各类网站中，作为一个应用为用户提供个性化推荐。它需要依赖用户的行为数据，因此一般都由后台日志系统、推荐算法系统和前台展示页面3部分构成。 应用推荐系统的领域包括：
电子商务 - 亚马逊：基于物品、好友的个性化推荐，相关推荐，20~30%
电影视频 - Netflix：基于物品的推荐，60%；YouTube、Hulu 音乐 - Pandora：专家标记；Last.fm：用户行为 社交网络 - Facebook、Twitter 阅读 - Google Reader 基于位置的服务 - Foursquare 个性化邮件 - Tapestry 广告 - Facebook 1.3 推荐系统评测
主要有3种评测推荐效果的实验方法：
离线实验：划分训练集和测试集，在训练集训练用户兴趣模型，在测试集预测 优点：快速方便
缺点：无法用真实的商业指标来衡量 用户调查：用抽样的方法找部分用户试验效果 优点：指标比较真实
缺点：规模受限，统计意义不够 在线实验：AB测试 优点：指标真实
缺点：测试时间长，设计复杂
实际中，这三种方法在推荐算法上线前都要完成。 评测指标较多，一些重要的如下：
用户满意度：调查问卷，线上的用户行为统计、其他的指标转化得到
预测准确度：可通过离线实验计算
评分预测，通过均方根误差和平均绝对误差计算，前者更为苛刻。设 rui 为用户 u 对物品 i 的实际评分， r?ui 为预测评分
RMSE=∑u,i∈T(rui?r?ui)2|T|????????????????MAE=∑u,i∈T|rui?r?ui||T|
TopN推荐，通过准确率或召回率衡量。设 R(u) 为根据训练建立的模型在测试集上的推荐， T(u) 为测试集上用户的选择
Precision=∑u∈U|R(u)∩T(u)|∑u∈U|R(u)| Recall=∑u∈U|R(u)∩T(u)|∑u∈U|T(u)|
覆盖率：表示对物品长尾的发掘能力（推荐系统希望消除马太效应）
Coverage=|∪u∈UR(u)||I|
上面的公式无法区分不同的分布，可以用熵或基尼系数来更准确地表述覆盖率
H=?∑i=1np(i)logp(i)
p(i) 为物品 i 的流行度的比例。 G=1n?1∑j=1n(2j?n?1)p(j)
p(j) 为按流行度由小到大排序的物品列表中的第 j 个物品的流行度的比例。
多样性：推荐需要满足用户的广泛的兴趣，表示推荐列表中物品两两之间的不相似性。设 s(i,j) 表示物品 i和 j 之间的相似度
Diversity(R(u))=1?∑i,j∈R(u),i≠js(i,j)12|R(u)|(|R(u)|?1) Diversity=1|U|∑u∈UDiversity(R(u))
新颖性：指给用户推荐他们不知道的物品，可以用平均流行度做粗算，或者更精确地通过做用户调查。
惊喜度：推荐和用户的历史兴趣不相似，却使用户满意的物品。
信任度：只能通过问卷调查来评价，可以通过增加推荐系统的透明度和利用好友信息推荐来提高信任度。
实时性：保持物品的时效性，主要涉及推荐系统实时更新和对新物品的处理。 健壮性：开发健壮性高的算法，清理脏数据，使用代价较高的用户行为设计推荐系统。 商业目标：推荐系统对于网站的价值。
作者认为，离线实验的优化目标是在给定覆盖率、多样性、新颖性等限制条件下，最大化预测准确度。
对推荐系统还需要从多维度来评测，如用户维度、物品维度和时间维度，这样可以更全面地了解推荐系统的性能。
2 利用用户行为数据
2.1 用户行为
用户行为数据一般从日志中获得，可以按反馈的明确性把用户行为分为显性反馈和隐性反馈。
用户行为数据很多满足长尾分布（Zipf定律）
f(x)=αxk
另外，用户活跃度高，倾向于看冷门的物品。
基于用户行为分析的推荐算法一般称为协同过滤算法，包括基于邻域的方法、隐语义模型、基于图的随机游走算法等，应用最广的是基于邻域的方法。
2.2 基于邻域的算法
基于邻域的算法可以分为基于用户的协同过滤算法（UserCF）和基于物品的协同过滤算法（ItemCF）。
2.2.1 基于用户的协同过滤算法
UserCF算法主要有两步：
找到和目标用户兴趣相似的用户集合
找到这个集合中的用户喜欢的，且目标用户没有听说过的物品，推荐给目标用户 设 N(u) 为用户 u 有过正反馈的物品集合， N(v) 为用户 v 有过正反馈的物品集合， u 和 v 的兴趣相似度可以用Jaccard公式或余弦相似度计算
wuv=|N(u)∩N(v)||N(u)∪N(v)|
wuv=|N(u)∩N(v)||N(u)||N(v)|??????????√
以余弦相似度为例：
def calcUserSimilarity1(t):
w = defaultdict(dict) # 相似度矩阵 for u in t: for v in t: if u != v:
w[u][v] = len(t[u] & t[v]) / math.sqrt(len(t[u]) * len(t[v]))
可以利用稀疏矩阵的性质优化上面的算法：
def calcUserSimilarity2(t):
itemUsers = defaultdict(set) # 物品-用户倒排表 n = defaultdict(int) # 用户喜欢的物品数 w = defaultdict(dict) # 相似度矩阵 # 建立倒排表
for u, items in t.iteritems(): for i in items:
itemUsers[i].add(u) # 计算相似度
for i, users in itemUsers.iteritems(): for u in users: n[u] += 1