推荐算法整理 -- 扩散算法

推荐算法

定义

推荐系统中常常用二部图来表示：把用户看成一类点，把商品看成另一类点，当某个用户购买过某个商品时，则他们之间会存在一条连边，但是每一类点之间是不会存在连边，即用户与用户之间，商品与商品之间不存在连边，类似于这样所组成的网络就称作为二部图。电子商务中的商品推荐，可以看做是而部分图上的链路挖掘问题，而扩散过程可以用来寻找网络中两个节点之间的关联强度。典型的扩散有两类：一类是物质或者能量的扩散，满足守恒律，常称作为物质扩散；另一类是热的扩散，一般由一个或多个恒温热源驱动，不满足守恒律，常被称作为热传导。

算法流程

上图以用户 - 商品二部分图为例，展示了两种典型的扩散过程。考虑为标有星号（即用户1）的用户推荐商品，因为该用户已经购买过的两件商品是我们可以利用的信息，因此可以认为每一个该用户购买过的商品都具有某种推荐能力 --- 可以理解为能量，也可以理解为热量或其他。

为了便于介绍，假设这些已经购买过的商品的初始推荐能力为1，未购买的为0。对于物质扩散过程，首先每一个商品把自己的能量平均分给所有购买过它的用户用户的能量值则是从所有商品所得到的能量值得总和，比如上图(b)中的第一个节点的能量就等于第一个商品平均分给三个用户的的平均能量1/3，再加上第四个商品平均分给两个用户的平均能量1/2，和为5/6；接下来，每一个用户再把自己的能量平局分给所有购买过的商品，商品的能量则是从所有用户收到的能量值得总和，如对于图(c)中的第一个商品，它的能量值就等于第一个用户能量值得一半为5/12，加上第二个用户能量值得1/4为5/24,再加上第三个用户能量值得一半为1/6，总的能量值即为5/12 + 5/24 + 1/6 = 19/24。以上两个步骤加起来为“从商品到商品”能量扩散一步。针对大规模系统的推荐，为了保持实时性和效率，往往只需扩散一两步。如果以一步为界，基于图(c)中的结果，则在目标用户没有购买过的所有商品中，第三个商品的能量值最大，因此基于物质扩散算法的推荐系统则会将此商品推荐给目标用户。值得注意的是物质扩散这种算法得到的所有商品最后的能量值之和就等于初始时所有商品的能量值，即能量是守恒的，图(c)中所有商品的能量之和仍为2。

对于热传导的过程，首先每一个用户的温度等于所有他购买过的商品的温度的平均值，如图(d)所示，如第一个用户购买了商品1和商品4，则该用户的温度值即为(1 + 1) / 2 = 1，以此类推；接下来每一个商品的温度等于所有购买过他的用户的温度的平均值，如图(e)中的第一个用户的温度就为用户1,2,3的温度的平均值（1 + 1/2 + 1/2） / 3 = 2/3。以上两个步骤加起来为“从商品到商品”热传导一步。类似的，如果以一步为界，基于图(e)中的结果，则在目标用户没有购买过的所有商品中，第二个商品的温度值最大，因此基于热传导算法的推荐系统则会将此商品推荐给目标用户。与物质扩散不同的是这种算法得到的所有商品最后的能量值之和就不一定等于初始时所有商品的能量值，即不满足守恒定律，这是因为在热传到的第二步过程中，有的用户的温度可能会被多次计算，从而导致不守恒。

总结

由上面的推荐结果的对比分析可知，物质扩散倾向于推荐比较流行的商品（第三个商品被3个用户购买过），而热传导倾向于推荐比较冷门的商品（第二个商品只被一个商品购买过），因为在热传导中，最后的温度值要除以购买过的该商品的的用户数目，实际上是对流行的商品进行惩罚。扩散算法具有准确性高、计算速度快、可并行程度高等优点，有望成为下一代推荐系统设计的主流算法之一。

参考文献

[1]. 个性化商业的未来。苏萌 柏林森 周涛 著。
[2]. Markdown原文。