本系列文章会从最简单的推荐系统到目前主流的推荐系统解决方案做总结。
1. 基于邻域的算法
基于邻域的算法是推荐系统中最基本的算法，在业界得到了广泛应用。基于邻域的算法分为两大类，一类是基于用户的协同过滤算法，另一类是基于物品的协同过滤算法。
1.1 基于用户的协同过滤算法（UserCF）
定义：
在一个在线个性化推荐系统中，当一个用户A需要个性化推荐时，可以先找到和他有相似兴趣的其他用户，然后把那些用户喜欢的、而用户A没有听说过的物品推荐给A。
步骤：
- 找到和目标用户兴趣相似的用户集合。
- 找到这个集合中的用户喜欢的，且目标用户没有听说过的物品推荐给目标用户。
设用户u和用户v ，N(u)表示用户u曾经有过正反馈的物品集合，N(v)表示用户v曾经有过正反馈的物品集合。可以通过下面几种方法计算用户的兴趣相似度。
- Jaccard公式简单地计算u和v的兴趣相似度：
- 或者通过余弦相似度计算：
举例：
用户A对物品{a, b, d}有过行为，用户B对物品{a, c}有过行为，利用余弦相似度公式计算用户A和用户B的兴趣相似度为：
同理，可以计算出用户A和用户C、 D的相似度：
分析：
以上例子对两两用户通过利用余弦相似度计算相似度。这种方法的时间复杂度是O(|U|*|U|)，这在用户数很大时非常耗时。解决办法是建立“物品—用户”的倒排表。可以扫描倒排表中每个物品对应的用户列表，令稀疏矩阵C[u][v]= | N(u)∩N (v) |，将用户列表中的两两用户对应的C[u][v]加1，最终就可以得到所有用户之间不为0的C[u][v]，具体如下图所示：
这里的W是余弦相似度中的分子部分，然后将W除以分母可以得到最终的用户兴趣相似度。
得到用户之间的兴趣相似度后， UserCF算法会给用户u推荐和他兴趣最相似的K个用户喜欢的物品。如下的公式度量了UserCF算法中用户u对物品 i 的感兴趣程度：
其中， S(u, K)包含和用户u兴趣最接近的K个用户， N(i)是对物品 i 有过行为的用户集合，即用户v的集合， wuv是用户u和用户v的兴趣相似度， rvi代表用户v对物品i的兴趣。
举例：
以上图为例，对用户A进行推荐。选取K=3，用户A对物品c、 e没有过行为，因此可以把这两个物品推荐给用户A。根据UserCF算法，用户A对物品c、 e的兴趣是：
分析：
使用MovieLens数据集上的离线实验来评测基础算法的性能。 UserCF只有一个重要的参数K，即为每个用户选出K个和他兴趣最相似的用户，然后推荐那K个用户感兴趣的物品：
可以发现参数K是UserCF的一个重要参数，它的调整对推荐算法的各种指标都会产生一定的影响。
准确率和召回率：
可以看到，推荐系统的精度指标（准确率和召回率）并不和参数K成线性关系。在MovieLens数据集中，选择K=80左右会获得比较高的准确率和召回率。因此选择合适的K对于获得高的推荐系统精度比较重要。当然，推荐结果的精度对K也不是特别敏感，只要选在一定的区域内，就可以获得不错的精度。
流行度：
可以看到，在3个数据集上K越大则UserCF推荐结果就越热门。这是因为K决定了UserCF在给你做推荐时参考多少和你兴趣相似的其他用户的兴趣，那么如果K越大，参考的人越多，结果就越来越趋近于全局热门的物品。
覆盖率：
可以看到，在3个数据集上， K越大则UserCF推荐结果的覆盖率越低。覆盖率的降低是因为流行度的增加，随着流行度增加， UserCF越来越倾向于推荐热门的物品，从而对长尾物品的推荐越来越少，因此造成了覆盖率的降低。
用户相似度计算的改进
余弦相似度计算用户兴趣过于粗糙。
改进思路：两个用户对冷门物品采取过同样的行为更能说明他们兴趣的相似度。
通过1/log(1 |N(i)|)惩罚了用户u和用户v共同兴趣列表中热门物品对他们相似度的影响。这种算法叫做User-IIF算法。
同样地，对UserCF-IIF的推荐性能，并将其和UserCF进行对比：
可以看到，UserCF-IIF在各项性能上略优于UserCF。这说明在计算用户兴趣相似度时考虑物品的流行度对提升推荐结果的质量确实有帮助。
基于用户的协同过滤总结
- 随着着网站的用户数目越来越大，计算用户兴趣相似度矩阵将越来越困难，其运算时间复杂度和空间复杂度的增长和用户数的增长近似于平方关系。
- 很难对推荐结果作出解释。
1.2 基于物品的协同过滤算法（ItemCF）
基于物品的协同过滤算法是目前业界应用最多的算法。
定义：
给用户推荐那些和他们之前喜欢的物品相似的物品。
步骤：
- 计算物品之间的相似度。
- 根据物品的相似度和用户的历史行为给用户生成推荐列表。
物品的相似度：
其中分母 |N(i)| 是喜欢物品 i 的用户数，而分子 |N(i) ∩N(j)| 是同时喜欢物品 i 和物品 j 的用户数。上述公式可以理解为喜欢物品 i 的用户中有多少比例的用户也喜欢物品 j 。
分析：
但上述公式存在一个问题，即如果物品 j 很热门，很多人都喜欢，那么Wij就会很大，接近1。即会造成任何物品都会和热门的物品有很大的相似度，导致出现长尾效应。
物品相似度计算的改进
通过惩罚物品j的权重，从而减轻了热门物品会和很多物品相似的可能性。
用ItemCF算法计算物品相似度时也可以首先建立用户—物品倒排表（即对每个用户建立一个包含他喜欢的物品的列表），然后对于每个用户，将他物品列表中的物品两两在共现矩阵C中加1。
上图左边是输入的用户行为记录，每一行代表一个用户感兴趣的物品集合。右边矩阵C中的 C[i][j] 记录了同时喜欢物品 i 和物品 j 的用户数。最后，将C矩阵归一化可以得到物品之间的余弦相似度矩阵W。
在得到物品之间的相似度后， ItemCF通过如下公式计算用户u对一个物品 j 的兴趣：
这里N(u)是用户喜欢的物品的集合， S(j,K)是和物品 j 最相似的K个物品的集合， wji是物品j和i的相似度， rui是用户u对物品 i 的兴趣度。（对于隐反馈数据集，如果用户u对物品 i 有过行为，那么rui=1）
该公式的含义是，和用户历史上感兴趣的物品越相似的物品，越有可能在用户的推荐列表中获得比较高的排名。
例子：
用户喜欢《C Primer中文版》和《编程之美》两本书。然后ItemCF会为这两本书分别找出和它们最相似的3本书，并根据公式的定义计算用户对每本书的感兴趣程度。
可以看到， ItemCF的一个优势就是可以提供推荐解释，即利用用户历史上喜欢的物品为现在的推荐结果进行解释。
分析：
ItemCF算法离线实验的各项性能指标的评测结果：
精度（准确率和召回率）
可以看到ItemCF推荐结果的精度也是不和K成正相关或者负相关的，因此选择合适的K对获得最高精度非常重要。
流行度
和UserCF不同，参数K对ItemCF推荐结果流行度的影响也不是完全正相关的。随着K的增加，结果流行度会逐渐提高，但当K增加到一定程度，流行度就不会再有明显变化。
覆盖率
K增加会降低系统的覆盖率。
物品相似度计算的改进
两个物品产生相似度是因为它们共同出现在很多用户的兴趣列表中。换句话说，每个用户的兴趣列表都对物品的相似度产生贡献。那么，是不是每个用户的贡献都相同呢？
未必。有些用户虽然活跃，但是买这些书并非都是出于自身的兴趣，而且这些书覆盖了当当网图书的很多领域，所以这个用户对于他所购买书的两两相似度的贡献应该远远小于一个只买了十几本自己喜欢的书的文学青年。即：活跃用户对物品相似度的贡献应该小于不活跃的用户。
ItemCF-IUF算法
上式增加用户活跃度对数的倒数这个参数来修正物品相似度的计算公式。
ItemCF-Norm 算法
研究中发现如果将ItemCF的相似度矩阵按最大值归一化，可以提高推荐的准确率。因此，如果已经得到了物品相似度矩阵w，那么可以用如下公式得到归一化之后的相似度矩阵w'：
归一化的好处不仅仅在于增加推荐的准确度，它还可以提高推荐的覆盖率和多样性。
可以看到，归一化确实能提高ItemCF的性能，其中各项指标都有了比较明显的提高。
1.3 UserCF和ItemCF的综合比较
UserCF给用户推荐那些和他有共同兴趣爱好的用户喜欢的物品。
ItemCF给用户推荐那些和他之前喜欢的物品类似的物品。.
所以，UserCF的推荐结果着重于反映和用户兴趣相似的小群体的热点，既社会化。而ItemCF的推荐结果着重于维系用户的历史兴趣，即个性化。
因此，在新闻推荐中使用UserCF，原因有三：
- 用户的兴趣不是特别细化，绝大多数用户都喜欢看热门的新闻。
- 物品的更新速度远远快于新用户的加入速度，而且对于新用户，完全可以给他推荐最热门的新闻。
- 这类网站用户数相对较稳定，维护用户相似度矩阵代价较小。
在图书、电子商务和电影网站中使用ItemCF，原因有三：
- 在这些网站中，用户的兴趣是比较固定和持久的，即对物品热门程度并不是那么敏感。
- 这些网站的物品更新速度不会特别快，一天一次更新物品相似度矩阵对它们来说不会造成太大的损失，是可以接受的。
- 这类网站物品数相对较稳定，维护物品相似度矩阵代价较小。
总结
1.4 哈利波特问题
在设计ItemCF算法之初发现ItemCF算法计算出的图书相关表存在一个问题，就是很多书都和《哈利波特》相关。也就是说，购买任何一本书的人似乎都会购买《哈利波特》。后来他们研究发现，主要是因为《哈利波特》太热门了，确实是购买任何一本书的人几乎都会购买它。
但实际上，这些书与《哈利波特》并不同属同一类型。换句话说，哈利波特问题描述的是两个不同领域的最热门物品之间往往具有比较高的相似度。
解决办法：
其中一个办法是可以在分母上加大对热门物品的惩罚，比如采用如下公式：
其中α∈[0.5 ,1] 。通过提高α，就可以惩罚热门的物品 j 。而更好的方法是依靠引入物品的内容数据解决这个问题，比如对不同领域的物品降低权重等。
