协同过滤算法笔记
基于邻域的算法是推荐系统中最基本的算法，该算法不仅在学术界得到了深入研究，而且在业界得到了广泛应用，主要是协同过滤算法（collaborative filtering）。协同过滤算法分为两大类，一类是基于用户的协同过滤算法，另一类是基于物品的协同过滤算法，首先来介绍第一种协同过滤的算法——基于用户的协同过滤（user-based collaborative filtering）。
基于用户的协同过滤算法主要包括两个步骤： (1) 找到和目标用户兴趣相似的用户集合。 (2) 找到这个集合中的用户喜欢的，且目标用户没有听说过的物品推荐给目标用户。
步骤(1)的关键就是计算两个用户的兴趣相似度。这里，协同过滤算法主要利用行为的相似度计算兴趣的相似度。给定用户u和用户v，令N(u)表示用户u曾经有过正反馈的物品集合，令N(v)为用户v曾经有过正反馈的物品集合。那么，我们可以通过如下的Jaccard公式简单地计算u和v的兴趣相似度：
或者通过余弦相似度计算：
首先建立物品到用户的倒排表，对于每个物品都保存对该物品产生过行为的用户列表。令稀疏矩阵。那么，假设用户u和用户v同时属于倒排表中K个物品对应的用户列表，就有C[u][v]=K。从而，可以扫描倒排表中每个物品对应的用户列表，将用户列表中的两两用户对应的C[u][v]加1，最终就可以得到所有用户之间不为0的C[u][v]。下面的代码实现了上面提到的算法：
得到用户之间的兴趣相似度后，UserCF算法会给用户推荐和他兴趣最相似的K个用户喜欢的物品。如下的公式度量了UserCF算法中用户u对物品i的感兴趣程度：
其中，S(u, K)包含和用户u兴趣最接近的K个用户，N(i)是对物品i有过行为的用户集合，wuv是用户u和用户v的兴趣相似度，rvi代表用户v对物品i的兴趣，因为使用的是单一行为的隐反馈数据，所以所有的rvi=1。 如下代码实现了上面的UserCF推荐算法：
用户相似度计算的改进
原因：以图书为例，如果两个用户都曾经买过《新华字典》，这丝毫不能说明他们兴趣相似，因为绝大多数中国人小时候都买过《新华字典》。但如果两个用户都买过《数据挖掘导论》，那可以认为他们的兴趣比较相似，因为只有研究数据挖掘的人才会买这本书。换句话说，两个用户对冷门物品采取过同样的行为更能说明他们兴趣的相似度。
因此，引入了对热门物品的惩罚，改进后的根据用户行为计算用户的兴趣相似度：
接下来介绍第二种协同过滤的算法——基于物品的协同过滤（item-based collaborative filtering）。基于物品的协同过滤算法是目前业界应用最多的算法。无论是亚马逊网，还是Netflix、Hulu、YouTube，其推荐算法的基础都是该算法。之所以会比基于用户的协同过滤更加受欢迎的原因是，当一个网站的用户数较大时，基于用户的协同过滤算法需要构造一个user-user的相似度计算矩阵，而此时网站的物品数目可能比用户数少得多，计算用户兴趣相似度矩阵将越来越困难，其运算时间复杂度和空间复杂度的增长和用户数的增长近似于平方关系。
基于物品的协同过滤算法并不利用物品的内容属性计算物品之间的相似度，它主要通过分析用户的行为记录计算物品之间的相似度，因此，保存和计算的就不是user-user的相似度计算矩阵，而是item-item的相似度计算矩阵。
基于物品的协同过滤算法主要分为两个步骤： (1) 计算物品之间的相似度。 (2) 根据物品的相似度和用户的历史行为给用户生成推荐列表。
计算公式如下：
为了避免热门物品受大多数用户喜爱而和其他所有物品的相似度高，改进后的公式为：
这个公式惩罚了物品j的权重，因此减轻了热门物品会和很多物品相似的可能性。其中，|N(i)|是喜欢物品i的用户数，|N(j)|是喜欢物品j的用户数。
和UserCF算法类似，用ItemCF算法计算物品相似度时也可以首先建立用户—物品倒排表（即对每个用户建立一个包含他喜欢的物品的列表），然后对于每个用户，将他物品列表中的物品两两在共现矩阵C中加1。详细代码如下所示：
在得到物品之间的相似度后，ItemCF通过如下公式计算用户u对一个物品j的兴趣：
这里N(u)是用户喜欢的物品的集合，S(j,K)是和物品j最相似的K个物品的集合，wji是物品j和i的相似度，rui是用户u对物品i的兴趣。（对于隐反馈数据集，如果用户u对物品i有过行为，即可令rui=1。）该公式的含义是，和用户历史上感兴趣的物品越相似的物品，越有可能在用户的推荐列表中获得比较高的排名。该公式的实现代码如下所示。
用一个图来形式化这个过程：
第一步计算物品之间的相似性，如C++Primer中文版和算法导论之间的相似性为0.4……
第二步为了计算用户u对算法导论的兴趣得分，中的i对应图中的C++Primer中文版和编程之美，将这两本书的wr计算并相加，如C++Primer中文版的wr计算为：C++Primer中文版和算法导论的相似度wji = 0.4，用户u对C++Primer中文版兴趣度rui = 1.3，所以wji * rui = 0.4 * 1.3
物品相似度计算的改进
改进1
原因：假设有这么一个用户，他是开书店的，并且买了当当网上80%的书准备用来自己卖。那么，他的购物车里包含当当网80%的书。假设当当网有100万本书，也就是说他买了80万本。从前面对ItemCF的讨论可以看到，这意味着因为存在这么一个用户，有80万本书两两之间就产生了相似度，也就是说，内存里即将诞生一个80万乘80万的稠密矩阵。因此，需要我们应该认为活跃用户对物品相似度的贡献应该小于不活跃的用户，需要对活跃用户进行惩罚。
因此，引入了对活跃用户的惩罚，改进后的根据用户行为计算物品的相似度：
改进2：
将ItemCF的相似度矩阵按最大值归一化，可以提高推荐的准确率。其研究表明，如果已经得到了物品相似度矩阵w，那么可以用如下公式得到归一化之后的相似度矩阵w'：
UserCF和ItemCF优缺点的对比：
参考资料：《推荐系统实战》 项亮著
