热传导算法 从入门到放弃

一： 理论支持

热传导和物质传播其实也是基于random walk 理论设计的，和之前提到的基于图的随机游走算法如出一辙。

稍微有点不同的是，这两者考虑了能量是否守恒这个自然定律，让传播方向和权重更具有解释性，我们这里只讨论热传导，物质传播类似，唯一的不同点是：物质传播 涉及的能量是守恒的，而热传导，是有热源的，能量源源不断。所以，热传导对长尾、冷门的商品推荐更适合，因为有热源，所以热量或多或少总会传递到冷物品上。

用一篇论文上的小例子来详细说明一下，

小圆圈代表用户，小方块代表物品，就第一个用户来说，对应的商品的初始能量如图a所示，

(1)第一步传播：从商品到用户

用户所接受的能量是和他有关的所有物品能量的平均值。对用户u1，和他相关的商品为s1、s4 ，所以，u1的能量=(1+1)/2=1

其他用户也类似，这样就完成了从商品到用户的一步传播，

(2)第二步传播：用户到商品

商品所接受的能量也是和他相关的所有用户的能量的平均值，对商品s1,和它相关的是u1 u2 u3,那么s1的能量=(1/2+1/2+1)/3 = 2/3,其他商品类似，这样就完成了用户对商品的传播，也就是用户对商品的热度、喜好程度。

那么，我们可以抽象为数据公式，（公式编辑器太麻烦，手写吧，大家凑合看，是那么个意思，先要强调一句，要关注内容，不要关注字写的咋样）

第一步传播有：

第二步传播有：

把公式1带入到公式2 的分子中，经过变换，我们就可以得到，

W其实是一个n*n的转移矩阵，怎么计算得到这个W矩阵呢，我们可以根据公式，通过矩阵乘法来得到，具体过程就不再详细说了，懂一点矩阵的兄弟应该都可以分开。

最终的结果，如下图，

K(O)代表商品的度，K(U)代表用户的度，a11 代表用户1 对商品1的度，这里可以先简单的认为，有行为为1 没有行为为0 ：

我们如果想要求某一个人对商品列表的喜好程度，就可以，用W这个转移矩阵去乘以用户-商品的1*n的初始列矩阵，最终得到一个1*n的列矩阵，就是这个用户对n个商品的喜好得分。

当然，也可以用W去乘以全量用户的n*m的初始矩阵，得到全量用户对全量商品的喜好。

二。工程实践

那么，想要从理论投入到生产，我们就涉及到了矩阵的运算。怎样通过mapreduce 来快速计算大型稀疏矩阵，建议看一下 张丹 的博客，写的挺巧妙的。

对于两个矩阵相乘，我们需要计算A的第m行所有元素和B的第n列的所有元素的对应位置上的乘积之和, 来得到结果矩阵中的第mn个元素。

所以，我们要在map 阶段将对应行列的对应元素组织起来，使得在reduce阶段得以相乘然后相加，

但是，在实际运算中发现了问题，在reduce阶段，我们要把 对应行列的两个矩阵的元素，组织到内存map中，即便是稀疏矩阵，当用户量和商品量特别庞大的时候，还是会outOfmemory.

怎么办呢。

办法有二：

1，切分数据集，按商家维度切分数据集。因为类似我们这种o2o的平台，各个商家的sku数据是不会打通的，本来也是竞争关系，所以，当按商家维度切分数据集后，矩阵的维度将大大减小，因为行为用户有限，sku数量也有限。但是，需要运行该方法N多遍，万一以后入住商家多了呢。所以不靠谱。

2，就是抛弃到矩阵乘法的逻辑，换一种思路，我们就从公式入手，求出 商品i对商品j的w分，然后当用户对某个商品s有行为时，就可以寻找和s相关的w分值最高的那一批商品了。

于是有，

第一个mapreduce循环用户行为集，获取每个用户下所有商品对的分值，第二个mapreduce 对相同的商品对的值求和，最终得到w值。

最后强调一句，要关注内容，不要关注字写的咋样