物质扩散与热传导

在推荐系统中，常常用二部图来表示用户和物品之间的关系：把用户（Users）看成一类，把物品（Objects）看作另一类。当某个用户购买过某个商品时，他们之间会存在一条连边。而同一类点之间不存在连边，即用户与用户之间，商品与商品之间不存在连边，类似于这样组成的网络就称为二部图。电子商务中的商品推荐，可以看做是二部图上的链路挖掘问题，而扩散过程可以用来寻找网络中两个节点之间的关联强度¹。

典型的扩散有两类：一类是物质或者能量的扩散，满足守恒律，常称作为物质扩散（Mass Diffusion）；另一类是热的扩散，一般由一个或多个恒温热源驱动，不满足守恒律，常被称作为热传导（Heat Spreading）。

举个栗子

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

假设用户已经购买过的商品的初始推荐能力为 1，未购买的为 0。

对于物质扩散过程，首先每件商品把自己的能量平均分给所有购买过它的用户。用户的能量值则是从所有商品所得到的能量值得总和，比如上图(b)中的第一个节点的能量就等于第一个商品平均分给三个用户的的平均能量$\frac{1}{3}$，再加上第四个商品平均分给两个用户的平均能量$\frac{1}{2}$，和为$\frac{5}{6}$；

接下来，每个用户再把自己的能量平局分给所有购买过的商品，商品的能量则是从所有用户收到的能量值得总和，如对于图(c)中的第一个商品，它的能量值就等于第一个用户能量值得一半为$\frac{5}{12}$，加上第二个用户能量值得$\frac{1}{4}$为$\frac{5}{24}$,再加上第三个用户能量值得一半为$\frac{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)中的结果，则在目标用户没有购买过的所有商品中，第二个商品的温度值最大，因此基于热传导算法的推荐系统则会将此商品推荐给目标用户。

与物质扩散不同的是这种算法得到的所有商品最后的能量值之和就不一定等于初始时所有商品的能量值，即不满足守恒定律，这是因为在热传到的第二步过程中，有的用户的温度可能会被多次计算，从而导致不守恒。

数学模型

假设我们有$m$个用户(User)和$n$个物品(Object)，可以构造矩阵$A_{m\times n}$，其中：

$a_{ij} = \begin{cases} 1 & \text{用户i购买了物品j} \\ 0 & \text{用户i未购买物品j} \end{cases}$

用$(c_1,\cdots,c_n)$表示物品的初始能量；用$(t_1,\cdots,t_n)$表示物品的初始温度；$k(U_{\alpha})=\sum_{j=1}^{n}a_{\alpha j}$表示用户$\alpha$的度，即该用户购买物品数量；$k(O_{j})=\sum_{i=1}^{m}a_{ij}$表示物品$j$的度，即该商品被多少个用户购买。

物质扩散³

第一步，用户从物品那里获得能量（每件商品把自己的能量平均分给所有购买过它的用户），用户$\alpha$获得的能量我们用$b_{\alpha}$表示：

$b_{\alpha} = \sum_{l=1}^{n}a_{\alpha l}(\frac{c_l}{k(O_l)}) \tag{MD.1}$

第二步，用户将能量传递给物品（每个用户把自己的能量平局分给所有购买过的商品），物品$j$更新后的能量我们用$c_{j}^{‘}$表示：

$c_{j}^{'} = \sum_{\alpha=1}^{m}a_{\alpha j}(\frac{b_{\alpha}}{k(U_{\alpha})}) \tag{MD.2}$

将$\color{red}{(MD.1)}$带入$\color{red}{(MD.2)}$：

$\begin{align*} c_{j}^{'} & = \sum_{\alpha=1}^{m}a_{\alpha j}(\frac{b_{\alpha}}{k(U_{\alpha})})\\ & = \sum_{\alpha=1}^{m}a_{\alpha j}(\frac{\sum_{l=1}^{n}a_{\alpha l}(\frac{c_l}{k(O_l)})}{k(U_{\alpha})})\\ & = \sum_{l=1}^{n} c_l \frac{1}{k(O_l)} \sum_{\alpha=1}^{m}\frac{a_{\alpha j}a_{\alpha l}}{k(U_{\alpha})}\\ & = \sum_{l=1}^{n} w_{jl}^Pc_l \end{align*}$

其中，

$\color{red}{w_{jl}^P = \frac{1}{k(O_l)} \sum_{\alpha=1}^{m}\frac{a_{\alpha j}a_{\alpha l}}{k(U_{\alpha})} \tag{MD.3}}$

采用向量化的表示方法：

$C^{'} = W^PC \tag{MD.4}$

其中，$W^P = (w_{jl}^P), C = (c_1,\cdots,c_n)^T,$

热传导

第一步，用户的温度等于所有他购买过的商品的温度的平均值，用户$\alpha$的温度我们用$b_{\alpha}$表示：

$b_{\alpha} = \sum_{l=1}^{n} \frac{a_{\alpha l}c_l}{k(U_{\alpha})} \tag{HS.1}$

第二步，每件商品的温度等于所有购买过他的用户的温度的平均值，物品$j$更新后的温度我们用$t_{j}^{‘}$表示：

$t_{j}^{'} = \sum_{\alpha=1}^{m} \frac{a_{\alpha j}b_{\alpha}}{k(O_{j})} \tag{HS.2}$

将$\color{red}{(HS.1)}$带入$\color{red}{(HS.2)}$：

$\begin{align*} t_{j}^{'} & = \sum_{\alpha=1}^{m} \frac{a_{\alpha j}b_{\alpha}}{k(O_{j})}\\ & = \sum_{\alpha=1}^{m} \frac{a_{\alpha j}\sum_{l=1}^{n} \frac{a_{\alpha l}c_l}{k(U_{\alpha})}}{k(O_{j})}\\ & = \sum_{l=1}^{n}c_l \frac{1}{k(O_{j})}\sum_{\alpha=1}^{m} \frac{a_{\alpha j}a_{\alpha l}}{k(U_{\alpha})}\\ & = \sum_{l=1}^{n}w_{jl}^Hc_l \end{align*}$

其中，

$\color{red}{w_{jl}^H = \frac{1}{k(O_{j})}\sum_{\alpha=1}^{m} \frac{a_{\alpha j}a_{\alpha l}}{k(U_{\alpha})}} \tag{HS.3}$

采用向量化的表示方法：

$T^{'} = W^HT \tag{HS.4}$

其中，$W^H = (w_{jl}^H), T = (t_1,\cdots,t_n)^T,$

物质扩散 vs 热传导⁴

基于物质扩散和基于热传导的推荐算法的区别在于：基于物质扩散的方法在进行个性化推荐时，系统的总能量是保持不变即守恒的；而热传导在推荐过程中，目标用户（即被推荐用户）的收藏品将被视作恒温热源，源源不断的给系统提供能量，所以系统的总能量随着传递步骤的增加是在不断增加的。换而言之，对于物质扩散，相当于有固定的初始能量在系统中传递，最后的系统稳态结果是和节点度（即物品被收藏数目）成正比的，所以它倾向于推荐那些度较大（较流行）的物品，相当于一个凸透镜，将用户的视野汇聚在那些较流行的节点上，从而也就不难理解这种方法会对提高推荐的精确性有很大帮助。

而对于热传导，因为热源存在的缘故，从而保证系统中有足够的能量可以传递到那些“冷点”上。也正是这个热源的存在，导致系统的最终稳态结果是所有节点温度相同，所以相对于物质扩散来说，热传导倾向于推荐那些度较小（较不流行）的节点，相当于一个凹透镜，把用户的视野发散到了那些较不流行的物品上，从而提高了推荐的多样性。

Hybrid Method

我们可以混合这两种模型，同时兼顾精确性和多样性：

$w_{jl}^{H+P}=\frac{1}{k(O_{j})^{1-\lambda}k(O_l)^{\lambda}}\sum_{\alpha=1}^{m} \frac{a_{\alpha j}a_{\alpha l}}{k(U_{\alpha})}$

举个栗子

数学模型

物质扩散3

热传导

物质扩散 vs 热传导4

Hybrid Method

物质扩散³

物质扩散 vs 热传导⁴