搜索
推荐系统实践学习笔记1好的推荐系统1.1什么是推荐系统推荐系统和搜索引擎都是为了帮助用户从大量信息中找到自己感兴趣的信息。区别是搜索引擎由用户主动提供关键词来查找信息，推荐系统则不需要，而通过分析用户的历史行为给用户的兴趣建模，主动给用户推荐他们可能感兴趣的信息。从物品的角度出发，推荐系统可以更好地发掘物品的长尾。长尾商品往往代表了一小部分用户的个性化需求，发掘这类信息正是推荐系统的长项。1.2个性化推荐系统的应用推荐系统广泛存在于各类网站中，作为一个应用为用户提供个性化推荐。它需要依赖用户的行为数据，因此一般都由后台日志系统、推荐算法系统和前台展示页面3部分构成。应用推荐系统的领域包括：电子商务-亚马逊：基于物品、好友的个性化推荐，相关推荐，20~30%电影视频-Netflix：基于物品的推荐，60%；YouTube、Hulu音乐-Pandora：专家标记；Last.fm：用户行为社交网络-Facebook、Twitter阅读-GoogleReader基于位置的服务-Foursquare个性化邮件-Tapestry广告-Facebook1.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)|−−−−−−−−−−√以余弦相似度为例：defcalcUserSimilarity1(t):w=defaultdict(dict)#相似度矩阵foruint:forvint:ifu!=v:w[u][v]=len(t[u]&t[v])/math.sqrt(len(t[u])*len(t[v]))可以利用稀疏矩阵的性质优化上面的算法：defcalcUserSimilarity2(t):itemUsers=defaultdict(set)#物品-用户倒排表n=defaultdict(int)#用户喜欢的物品数w=defaultdict(dict)#相似度矩阵#建立倒排表foru,itemsint.iteritems():foriinitems:itemUsers[i].add(u)#计算相似度fori,usersinitemUsers.iteritems():foruinusers:n[u]+=1forvinusers:ifu!=v:w[u][v]=w[u].get(v,0)+1foruinw:forvinw[u]:w[u][v]/=math.sqrt(n[u]*n[v])returnw然后用上面的相似度矩阵来给用户推荐和他兴趣相似的用户喜欢的物品。用户u对物品i的兴趣程度可以估计为p(u,i)=∑v∈S(u,K)∩N(i)wuvrviS(u,K)为和用户u兴趣最接近的K个用户，N(i)为对物品i有正反馈的用户集合，wuv为用户u和用户v的兴趣相似度，rvi为用户v对物品i的兴趣。defrecommend(u,t,w,k):rank=defaultdict(float)#推荐结果su=sorted(w[u].items(),key=itemgetter(1),reverse=True)forv,wuvinsu[:k]:fori,rviint[v].iteritems():ifinotint[u]:#排除已经有过反馈的物品rank[i]+=wuv*rvireturnrank通过对不同K值下的测量发现：准确率和召回率并不和K成线性关系，通过多次测量可以选择合适的K值K越大，推荐的结果越热门，流行度增大K越大，推荐结果的覆盖率越低可以调整计算用户兴趣相似度的公式来改进算法。注意到用户对冷门物品采取同样的行为更能说明他们的兴趣相似度，可以改用下式计算兴趣相似度wuv=∑i∈N(u)∩N(v)1log(1+|N(i)|)|N(u)||N(v)|−−−−−−−−−−√上式用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的相似度可以计算为wij=|N(i)∩N(j)||N(i)||N(j)|−−−−−−−−−√这里面包含的假设是每个用户的兴趣都局限在某几个方面。计算物品相似度使用和计算用户兴趣相似度类似的方法：defcalcItemSimilarity(t):n=defaultdict(int)#喜欢物品的用户数w=defaultdict(dict)#相似度矩阵foru,itemsint.iteritems():foriinitems:n[i]+=1forjinitems:ifi!=j:w[i][j]=w[i].get(j,0)+1foriinw:forjinw[i]:w[i][j]/=math.sqrt(n[i]*n[j])returnw然后计算用户u对物品i的兴趣程度p(u,i)=∑j∈S(i,K)∩N(u)wijrujS(i,K)为和物品i最相似的K个物品，N(u)为用户u喜欢的物品集合，wij为物品i和物品j的相似度，ruj为用户u对物品j的兴趣。它的意思是和用户感兴趣的物品越相似的物品，越应该被推荐。defrecommend(u,t,w,k):rank=defaultdict(float)#推荐结果reason=defaultdict(dict)#推荐解释forj,rujint[u].iteritems():sj=sorted(w[j].items(),key=itemgetter(1),reverse=True)fori,wijinsj[:k]:ifinotint[u]:#排除已经喜欢的物品rank[i]+=wij*rujreason[i][j]=wij*rujreturnrankItemCF算法的一个好处是可以给出推荐解释。对不同K值的测量可以看到：准确率和召回率和K也不成线性关系K和流行度不完全正相关K增大仍会降低覆盖率活跃用户对物品相似度的贡献要小于不活跃用户，可以用和IIF类似的IUF参数来修正物品相似度的计算公式wij=∑u∈N(i)∩N(j)1log(1+|N(u)|)|N(i)||N(j)|−−−−−−−−−√将calcItemSimilarity第9行改为w[i][j]=w[i].get(j,0)+1/math.log(1+len(items))实际计算中，对于过于活跃的用户，一般直接做忽略处理。对ItemCF的另一个改进是将相似度矩阵归一化，这样可以提高推荐的准确率，以及覆盖率和多样性。wij′=wijmaxiwij2.2.3UserCF算法和ItemCF算法的比较UserCF算法的特点是：用户较少的场合，否则用户相似度矩阵计算代价很大适合时效性较强，用户个性化兴趣不太明显的领域用户有新行为，不一定造成推荐结果的立即变化对新用户不友好，对新物品友好，因为用户相似度矩阵需要离线计算很难提供令用户信服的推荐解释对应地，ItemCF算法的特点：适用于物品数明显小于用户数的场合，否则物品相似度矩阵计算代价很大适合长尾物品丰富，用户个性化需求强的领域用户有新行为，一定导致推荐结果的实时变化对新用户友好，对新物品不友好，因为物品相似度矩阵需要离线计算用用户历史行为做推荐解释，比较令用户信服和UserCF算法相比，ItemCF算法的离线实验结果要差一些，不过这是在两者优化前的结果，实际优化后性能是接近的。原始ItemCF算法的覆盖率和新颖度不高的原因可以归结为哈利波特问题，也就是热门物品和其他物品的相似度都很高，这个问题一个办法是惩罚热门物品，同时可能还需要引入物品的内容数据来修正。2.3隐语义模型隐语义模型（LFM）最近几年非常热门，核心思想是通过隐含特征联系用户兴趣和物品。简单说就是对物品的兴趣分类，对于用户，首先确定他的兴趣分类，然后从分类中选择他可能喜欢的物品。这里的对物品分类的问题，可以用隐含语义分析技术较好地解决。它基于用户行为统计做分类，和专家标记相比：能代表各种用户的看法能控制分类的粒度能给一个物品多个分类带维度属性可以确定物品在某个分类中的权重这些都