自从机器学习火爆以来，一直对推荐系统的工程化比较感兴趣，但是网上又缺乏这方面的干货。

这两天偶然接触到python surprise库，才意识到其实基础的推荐算法是可以高度抽象的，也并没有想像的那么难以应用。

为了掌握工具，我发现缺乏了太多理论基础，于是决定把推荐系统的基础算法–协同过滤 进行理论研究。

随着翻看相关资料，发现实现一个简单的协同过滤是件不复杂的事情，只要能把理论和逻辑脉络梳理清楚，写成一份代码是轻而易举的事情，甚至都不需要真的去动手实践。

基于上述原因，我决定写2篇协同过滤的博客，上篇是理论篇，下篇是实现篇。

在理论篇中，为了让我自己对算法理解的更加透彻，我会用情感化的、生活化的方式描述算法，并且整理出一个逻辑清单，依照清单就可以实现一个协同过滤算法。

为了提升理解，在编写过程中我避免查阅所有资料，而是凭借我对已有资料的反思，自己梳理整个流程，达到记忆加深效果。

能做什么

用于实现推荐，例如很多网站上的”猜你喜欢”。

算法最基础的输入是：用户 -> 物品 的行为日志，表示某用户对某物品感兴趣（高级算法可以引入感兴趣程度）。

算法最基础的输出是：给某用户推荐哪些物品。

这个算法是对已有用户数据的挖掘计算，只能为数据中存在的用户推荐数据中存在的物品，当然推荐的物品应该是用户此前没有购买过的。

两种方式

协同过滤分为基于用户的协同过滤（UserCF）与基于物品的协同过滤（ItemCF），它们的输入完全一样，功能完全一样，即为某用户推荐某些物品，差别在于实现角度不同。

UserCF

UserCF试图计算出用户之间的相似度，即每一对用户的相似度，假设有10个人，每个人编号1-10，那么相似度计算结果是一个10*10大小的矩阵，即表达每一对用户的相似度。

如何计算用户之间的相似度呢？简单的说，两个人感兴趣的物品交集越大，差集越小，说明两人兴趣差不多，因此更加相似。

那么有了用户相似度，怎么为某个用户推荐物品呢？也很简单，找到与该用户相似度最近的K个用户，把这K个用户的物品推荐给该用户即可。

这里引申出一个问题，这K个相似用户各自感兴趣的物品个数会很多，到底推荐哪些物品给该用户呢？这个也很简单，为了减少学习负担，到后面具体再说。

那么UserCF适用什么场景呢？从计算角度来看，相似度矩阵是主要的计算工作，而矩阵的长宽与用户数量相关，10人就是10*10，1000万用户就是1000w*1000w，这个计算量还是很可怕的。

所以，UserCF通常适用于用户少，物品多的推荐场景。

ItemCF

ItemCF试图计算出物品之间的相似度，假设有10个物品，每个物品编号1-10，那么相似度计算结果是一个10*10大小的矩阵，即表达每一对物品的相似度。

如何计算物品之间的相似度呢？简单的说，对这两个物品感兴趣的用户交集越大，差集越小，说明两个物品可能是类似的东西，或者说两个物品的受众群体差不多是一拨人，那么两个物品应该相似一些。

那么有了物品相似度，怎么为某个用户推荐物品呢？我们已知该用户喜欢哪些物品，所以可以分别为这些物品找到最相近的K个相似物品（基于物品相似矩阵），把这些相似物品推荐给该用户即可。

这里同样引申出一个问题，该用户每个感兴趣物品的K个相似物品加起来也很多，到底推荐哪些物品给用户更精准呢？这个和UserCF类似，计算原理很简单，后面再具体说。

那么ItemCF适用什么场景呢？从计算角度来看，因为相似度矩阵规模与物品数量有关，所以更加适用于物品数量少于用户数量的场景。

而电商一般是用户多（中国好几亿用户）商品少，所以通常采用ItemCF。

输入/输出

无论采用哪一种CF算法，其输入和输出都是一样的。

输入是行为日志，每一行是：用户User ID -> 物品ItemID的单一映射关系，若要表达同一个用户喜欢多个物品则需要多行数据。

输出是推荐结果，每一行是：用户User ID -> 推荐的物品Item ID列表…。

可见，该算法的推荐结果是固定的，计算完成推荐结果也就凝固了，没有什么动态性。

这种推荐效果常见于电商网站首页的各种推荐广告位，通常是你最近看了哪一类商品，就继续给你推同类的商品。

另外一种推荐效果，是当你购买CPU的时候，推荐你购买主板、内存，这种推荐更加在乎商品的关联性，而不是类似性，所以感觉不太适合协同过滤。

逻辑清单

UserCF

1）离散uid转换到连续区间

因为要在内存构建一个用户N*N矩阵，而原始用户ID（raw uid）一般是不连续的，这导致无法构建一个高效的矩阵。

因此需要raw uid映射到从0开始增长的内部ID（inner uid），即0、1、2、3、4…，这样用户数量为10的矩阵可以直接用 matrix[10][10]这样的连续数组表达，其访问效率和空间占用都是最佳的。

2）构建正排字典

即将原始输入的行为日志：user id -> item id，按照user id分组变成一个正排字典：

这份数据可以让我们高效的获知某个user的感兴趣物品列表，后续计算用户相似度矩阵时会用到。

3）构建倒排字典

该步骤是计算用户相似度的前置步骤。

两个用户的相似度计算需要如下2个数据：

1. 两个用户感兴趣物品的交集大小（基于倒排字典计算）。
2. 两个用户各自感兴趣物品的集合大小做乘积并开根号（基于正排字典计算）。

最终相似度等于上述2个数字做除法，即物品交集越大、差集越小，则两个用户更加相似。

所谓倒排字典，即根据原始输入日志，构建如下的结构：

至于如何计算两个用户的物品交集，继续往下看。

4）计算每对用户的物品交集

遍历倒排字典，以item id 2来说：

• 这三对用户存在交集关系（uid1, uid2）、(uid1, uid3)、(uid2, uid3)
• 这三对用户的交集集合大小应分别+1，即三对用户均拥有item id 2这个物品

在完整的遍历倒排字典后，每对用户之间的交集大小应该都可以统计出来，可以将这份统计数据临时存储在相似度矩阵里，即10个用户则为10*10矩阵。

这个矩阵matrix是一个相似度矩阵的半成品，准备进入下一个阶段最终计算。

5）计算用户相似度矩阵

遍历4）中计算的半成品相似度矩阵，对矩阵每个元素matrix[i][j]来说：

• 从正排字典获取uid i和uid j的感兴趣物品集合大小分为别a和b，计算得到c=sqrt(a * b)
• 令matrix[i][j] = matrix[i][j] / c得到最终两个用户的相似度

6）为每个用户推荐物品

遍历正排字典，我们可以获得每个用户。

对于每个用户来说，我们可以基于用户相似度矩阵，获得该用户与其他所有用户的相似度。

我们可以取相似度最高的K个相似用户，通过正排字典可以获得这K个相似用户的感兴趣物品作为推荐候选集合，这个集合会比较大，因此需要进一步挑选最可能感兴趣的物品。

因为这K个相似用户感兴趣的物品可能存在交集，那么评估每个物品优先级的方法就是把交集中的物品所属的用户相似度做加和，作为物品的打分。

假设相似用户A和B都对item 1感兴趣，那么item1的得分就是用户A的相似度+用户B的相似度。这样整个推荐候选集里的物品就都有了打分，可以取分数较高的一些物品作为推荐结果。

ItemCF

1）离散item id转换到连续区间

与UserCF类似，因为要构建物品相似度矩阵，所以需要将item id进行连续化处理。

2）构建正排字典

同UserCF，构建出user id -> [item id 1, item id 2…]的字典。

3）构建倒排字典

同UserCF，构建出item id -> [uid 1, uid 2…]的字典。

4）计算每对物品的用户交集

遍历正排字典，与UserCF相比，仅仅改为累加每对item的用户交集大小，保存到物品相似度矩阵matrix。

5）计算物品相似度矩阵

遍历4）中计算的半成品物品相似度矩阵，对矩阵每个元素matrix[i][j]来说：

• 从倒排字典获取item i和item j的用户集合大小分别为a和b，计算得到c=sqrt(a * b)
• 令matrix[i][j] = matrix[i][j] / c得到最终两个物品的相似度

6）为每个用户推荐物品

遍历正排字典，我们可以获得每个用户与他感兴趣的物品列表。

对于每个他感兴趣的物品，我们可以根据物品相似度矩阵得到相似度最高的K个其他物品，作为推荐候选集合，这个集合会比较大，需要进一步挑选最可能感兴趣的物品。

因为每个感兴趣物品的相似物品可能存在交集，所以可以将交集的相似物品的相似度做加和，作为物品的打分。

假设用户A对item1，item 2感兴趣，然后item1的相似物品有item3和item4，item2的相似物品有item4和item5，那么item3，item4，item5是推荐候选集。

对于item3来说，应该将相似度(item1,item3)作为item3的打分。

对于item4来说，应该将相似度(item1,item4)+(item2,item4)作为item4的打分。

对于item5来说，应该将相似度(item2,item5)作为item5的打分。

最后可以对item3，item4，item5进行打分排序，选靠前的作为推荐结果。

PHP实现

采用PHP实现了基于物品的系统过滤，因为理论已经讲的比较清晰，所以代码就不做二次讲解了：https://github.com/owenliang/ItemCF-php。

参考资料

• 协同过滤推荐算法的原理与实现
• 【推荐系统实战】：C++实现基于用户的协同过滤（UserCollaborativeFilter）
• 基于物品的协同过滤算法：理论说明，代码实现及应用
• Python推荐系统库——Surprise