本文来源：http://www.yeolar.com/note/2013/10/03/recommend-system/
放假在家看项亮的《推荐系统实践》，觉得写得不错。因为我接触推荐系统的时间也不长，这本书正好适合入门。书里面的理论篇幅不多，比较偏重综述和实验分析，让人能有个感性的认识。如果想加强一下理论背景的话，个人推荐《数据挖掘导论》和《机器学习》。写了一份笔记，书里面有一些错误和不清晰的地方，自己做了些修改，本文是前半部分。
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定律）
另外，用户活跃度高，倾向于看冷门的物品。
基于用户行为分析的推荐算法一般称为协同过滤算法，包括基于邻域的方法、隐语义模型、基于图的随机游走算法等，应用最广的是基于邻域的方法。
2.2 基于邻域的算法
基于邻域的算法可以分为基于用户的协同过滤算法（UserCF）和基于物品的协同过滤算法（ItemCF）。
2.2.1 基于用户的协同过滤算法
UserCF算法主要有两步：
- 找到和目标用户兴趣相似的用户集合
- 找到这个集合中的用户喜欢的，且目标用户没有听说过的物品，推荐给目标用户
设 N(u) 为用户 u 有过正反馈的物品集合， N(v) 为用户 v 有过正反馈的物品集合， u 和 v 的兴趣相似度可以用Jaccard公式或余弦相似度计算
以余弦相似度为例：
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
for v in users:
if u != v:
w[u][v] = w[u].get(v, 0) + 1
for u in w:
for v in w[u]:
w[u][v] /= math.sqrt(n[u] * n[v])
return w
然后用上面的相似度矩阵来给用户推荐和他兴趣相似的用户喜欢的物品。用户 u 对物品 i 的兴趣程度可以估计为
S(u,K) 为和用户 u 兴趣最接近的 K 个用户， N(i) 为对物品 i 有正反馈的用户集合， wuv 为用户 u 和用户 v 的兴趣相似度， rvi 为用户 v 对物品 i 的兴趣。
def recommend(u, t, w, k):
rank = defaultdict(float) # 推荐结果
su = sorted(w[u].items(), key=itemgetter(1), reverse=True)
for v, wuv in su[:k]:
for i, rvi in t[v].iteritems():
if i not in t[u]: # 排除已经有过反馈的物品
rank[i] += wuv * rvi
return rank
通过对不同 K 值下的测量发现：
- 准确率和召回率并不和 K 成线性关系，通过多次测量可以选择合适的 K 值
- K 越大，推荐的结果越热门，流行度增大
- K 越大，推荐结果的覆盖率越低
可以调整计算用户兴趣相似度的公式来改进算法。注意到用户对冷门物品采取同样的行为更能说明他们的兴趣相似度，可以改用下式计算兴趣相似度
上式用 1log(1+|N(i)|) （IIF参数）减小了热门物品对用户兴趣相似度的影响。将 calcUserSimilarity2 第15行改为
w[u][v] = w[u].get(v, 0) + 1 / math.log(1 + len(users))
UserCF算法用的并不多。它的问题是运算复杂度大，并且难以解释推荐的结果。
2.2.2 基于物品的协同过滤算法
ItemCF算法是目前应用最多的算法。它也主要分为两步：
- 根据用户行为计算物品之间的相似度
- 根据物品的相似度和用户的历史行为给用户生成推荐列表
设 N(i) 为喜欢物品 i 的用户数， N(j) 为喜欢物品 j 的用户数， i 和 j 的相似度可以计算为
这里面包含的假设是每个用户的兴趣都局限在某几个方面。
计算物品相似度使用和计算用户兴趣相似度类似的方法：
def calcItemSimilarity(t):
n = defaultdict(int) # 喜欢物品的用户数
w = defaultdict(dict) # 相似度矩阵
for u, items in t.iteritems():
for i in items:
n[i] += 1
for j in items:
if i != j:
w[i][j] = w[i].get(j, 0) + 1
for i in w:
for j in w[i]:
w[i][j] /= math.sqrt(n[i] * n[j])
return w
然后计算用户 u 对物品 i 的兴趣程度
S(i,K) 为和物品 i 最相似的 K 个物品， N(u) 为用户 u 喜欢的物品集合， wij 为物品 i 和物品 j 的相似度， ruj 为用户 u 对物品 j 的兴趣。它的意思是和用户感兴趣的物品越相似的物品，越应该被推荐。
def recommend(u, t, w, k):
rank = defaultdict(float) # 推荐结果
reason = defaultdict(dict) # 推荐解释
for j, ruj in t[u].iteritems():
sj = sorted(w[j].items(), key=itemgetter(1), reverse=True)
for i, wij in sj[:k]:
if i not in t[u]: # 排除已经喜欢的物品
rank[i] += wij * ruj
reason[i][j] = wij * ruj
return rank
ItemCF算法的一个好处是可以给出推荐解释。
对不同 K 值的测量可以看到：
- 准确率和召回率和 K 也不成线性关系
- K 和流行度不完全正相关
- K 增大仍会降低覆盖率
活跃用户对物品相似度的贡献要小于不活跃用户，可以用和IIF类似的IUF参数来修正物品相似度的计算公式
将 calcItemSimilarity 第9行改为
w[i][j] = w[i].get(j, 0) + 1 / math.log(1 + len(items))
实际计算中，对于过于活跃的用户，一般直接做忽略处理。
对ItemCF的另一个改进是将相似度矩阵归一化，这样可以提高推荐的准确率，以及覆盖率和多样性。
2.2.3 UserCF算法和ItemCF算法的比较
UserCF算法的特点是：
- 用户较少的场合，否则用户相似度矩阵计算代价很大
- 适合时效性较强，用户个性化兴趣不太明显的领域
- 用户有新行为，不一定造成推荐结果的立即变化
- 对新用户不友好，对新物品友好，因为用户相似度矩阵需要离线计算
- 很难提供令用户信服的推荐解释
对应地，ItemCF算法的特点：
- 适用于物品数明显小于用户数的场合，否则物品相似度矩阵计算代价很大
- 适合长尾物品丰富，用户个性化需求强的领域
- 用户有新行为，一定导致推荐结果的实时变化
- 对新用户友好，对新物品不友好，因为物品相似度矩阵需要离线计算
- 用用户历史行为做推荐解释，比较令用户信服
和UserCF算法相比，ItemCF算法的离线实验结果要差一些，不过这是在两者优化前的结果，实际优化后性能是接近的。原始ItemCF算法的覆盖率和新颖度不高的原因可以归结为哈利波特问题，也就是热门物品和其他物品的相似度都很高，这个问题一个办法是惩罚热门物品，同时可能还需要引入物品的内容数据来修正。
2.3 隐语义模型
隐语义模型（LFM）最近几年非常热门，核心思想是通过隐含特征联系用户兴趣和物品。简单说就是对物品的兴趣分类，对于用户，首先确定他的兴趣分类，然后从分类中选择他可能喜欢的物品。
这里的对物品分类的问题，可以用隐含语义分析技术较好地解决。它基于用户行为统计做分类，和专家标记相比：
- 能代表各种用户的看法
- 能控制分类的粒度
- 能给一个物品多个分类
- 带维度属性
- 可以确定物品在某个分类中的权重
这些都是专家标记不能或者很难做到的。
隐含语义分析技术其他相关的技术：pLSA、LDA、隐含类别模型、隐含主题模型、矩阵分解等
LFM如下计算用户 u 对物品 i 的兴趣
参数 pu,k 表示用户 u 的兴趣和第 k 个隐类的关系度， qi,k 表示物品 i 和第 k 个隐类的关系度。这两个参数需要通过机器学习得到，利用最优化理论，可以通过最小化下式来计算 p 和 q
λ∥pu∥2+λ∥qi∥2 是用来防止过拟合的正则化项， λ 可通过实验获得。
利用随机梯度下降法，令 eui=rui−pTuqi ，求导，得到递推关系
α 为学习速率。
对于隐性反馈数据，LFM的一个问题是如何给每个用户生成负样本。研究表明，较好的方案是：对每个用户，保证正负样本数相近（设比例为 R ）；选取那些热门但用户却没有选择的物品作为负样本（更能明确表明用户对它不感兴趣）。
下面是LFM推荐算法的一个实现：
def selectRandomSample(items, positiveItems):
n = len(items)
mp = len(positiveItems)
mn = 0
s = {} # 采样
for i in positiveItems:
s[i] = 1 # 正样本 rui = 1
for k in range(0, n * 3):
i = items[random.randint(0, n - 1)]
if i in s:
continue
s[i] = 0 # 负样本 rui = 0
mn += 1
if mn > mp: # 正负样本比例为1
break
return s
def calcLatentFactorModel(t, k, step, alpha, lamb):
p, q = initModel(t, k) # numpy.matrix
for j in range(0, step):
for u, positiveItems in t.iteritems():
sampleItems = selectRandomSample(items, positiveItems)
for i, rui in sampleItems.iteritems():
eui = rui - p[u] * q[i]
p[u] = sum(alpha * (eui * q[i] - lamb * p[u]))
q[i] = sum(alpha * (eui * p[u] - lamb * q[i]))
alpha *= 0.9
return p, q
def recommend(u, p, q):
rank = {} # 推荐结果
for i in q:
rank[i] = sum(p[u]