物质扩散模型

引言

在推荐系统中，常常用二部图来表示用户和物品的关系：把用户（Users）看成一类点，把物品（Objects）看成另一类点。如果用户购买了某种物品，那么用户和物品之间就存在一条连线，也就是一条边。如果用户没有购买某种物品，那么用户和物品之间就没有连线。但是用户和用户之间，物品和物品之间是不存在连线的。换句话说就是同一类点之间是不存在连线的。这样的图结构就叫做二部图。电子商务中间的物品推荐，可以看成是二部图的边的挖掘问题。扩散过程可以用来寻找二部图中两个节点的关联强度。经典的扩散过程分成两类：一种叫做物质扩散（Probabilistic Spreading），它满足能量守恒定律；另一种叫做热传导（Heat Spreading），一般由一个或多个热源（物品）驱动，不一定满足能量守恒定律。

物质扩散（Probabilistic Spreading）算法流程

如图所示，用黄色的点来表示用户，用红色的点表示物品。用户有三位，物品有四个。第一个用户和第一个物品有连线表示第一个用户购买了第一个物品，而与第二个物品没有连线表示第一个用户没有购买第二个物品。根据图像(a)所示，第一个物品和第三个物品有能量1，第二个物品和第四个物品有能量0.对于物质扩散过程，第一个物品需要把自己的能量1平均分配给购买过它的用户一和用户二。第三个物品也需要把自己的能量1平均分配给购买过它的用户一和用户三。用户的能量就是所有用物品得到的能量的总和。正如图像(b)所示，第一个用户此时具有能量1，第二个和第三个用户都具有能量1/2.接下来，每个用户再把自身的能量平均分配给所有购买过的物品，物品的能量则是从所有用户得到的能量的总和。所以第一个物品的能量就是第一个用户的能量乘以0.5加上第二个用户的能量乘以1/3，所得的能量则是2/3.其他物品的能量用类似的方法计算。

物质扩散（Probabilistic Spreading）数学模型

假设有m个用户（Users）和n个物品（Objects），可以构造矩阵 $A_{m\times n},$ 如果 $a_{ij}=1$ ，那么表示用户i购买了物品j；如果 $a_{ij}=0$ , 那么表示用户i没有购买物品j。用 $(c_{1},\cdot\cdot\cdot, c_{n})$ 来表示物品1到物品n的能量。用 $k(U_{\alpha})=\sum_{j=1}^{n}a_{\alpha j}$ 表示用户 $\alpha$ 的度，也就是该用户购买的物品数量。用 $k(O_{j})=\sum_{i=1}^{m}a_{ij}$ 表示物品j的度，也就是该物品被多少个用户购买过。根据物质扩散的算法描述，第一步需要计算出用户从物品那里得到的能量，此时用户 $i$ 得到的能量用 $b_{i}$ 表示，那么

$b_{i}=\sum_{\ell=1}^{n} a_{i\ell}\cdot c_{\ell}/k(O_{\ell}) \text{ for all } 1\leq i\leq m.$

后面需要通过用户的能量来更新物品的能量，假设物品 $j$ 的新能量用 $c_{j}^{'}$ 表示，那么

$c_{j}^{'}=\sum_{i=1}^{m}a_{ij}\cdot b_{i}/ k(U_{i}) \text{ for all } 1\leq j \leq n.$

把 $b_{i}$ 的公式带入上面可以得到对于 $1\leq j\leq n,$ 我们有

$c_{j}^{'}=\sum_{\ell=1}^{n}\left(\frac{1}{k(O_{\ell})}\cdot\sum_{i=1}^{m}\frac{a_{ij}a_{i\ell}}{k(U_{i})}\right)\cdot c_{\ell}=\sum_{\ell=1}^{n}w_{j\ell}^{P}\cdot c_{\ell}.$

在这里对于 $1\leq j\leq n, 1\leq \ell \leq n,$

$w_{j\ell}^{P}=\frac{1}{k(O_{\ell})}\cdot\sum_{i=1}^{m}\frac{a_{ij}a_{i\ell}}{k(U_{i})}.$

假设 $n\times n$ 矩阵 $W^{P}=(w_{j\ell}^{P}),$ 列向量 $\vec{C}=(c_{1},\cdot\cdot\cdot,c_{n})^{T}$ 和 $\vec{C^{'}}=(c_{1}^{'},\cdot\cdot\cdot,c_{n}^{'})^{T}$ ，那么 $\vec{C^{'}}=W^{P}\vec{C}.$

性质1. 矩阵每列的和都是1，i.e. 对于所有的都成立。

证明. $\sum_{j=1}^{n}w_{j\ell}^{P}=\sum_{j=1}^{n}\sum_{i=1}^{m}\frac{1}{k(O_{\ell})}\cdot\frac{a_{ij}a_{i\ell}}{k(U_{i})}=\sum_{i=1}^{m}\frac{a_{i\ell}}{k(O_{\ell})}=1.$

性质2. 对于所有的都成立。换言之，矩阵不一定是对称矩阵，只有在所有物品的度都完全一致的情况下才是对称矩阵。

证明. 根据 $w_{j\ell}^{P}$ 和 $w_{\ell j}^{P}$ 的定义可以得到结论。

性质3. 矩阵对角线上的元素是该列的最大值。i.e. 对于所有的都成立。

证明. 根据矩阵 $A$ 的定义，对于所有的 $1\leq j,\ell\leq n,$ 可以得到

$w_{jj}^{P}=\frac{1}{k(O_{j})}\cdot \sum_{i=1}^{m}\frac{a_{ij}^{2}}{k(U_{i})}\geq\frac{1}{k(O_{j})}\cdot\sum_{i=1}^{m}\frac{a_{ij}a_{i\ell}}{k(U_{i})}=w_{\ell j}^{P}.$

性质4. 能量守恒定律：

证明. 根据前面的性质，已经知道 $W^{P}$ 矩阵每一列的和都是1，i.e. $\sum_{j=1}^{n}w_{j\ell}^{P}=1.$ 可以直接计算得到： $\sum_{j=1}^{n}c_{j}^{'}=\sum_{j=1}^{n}\sum_{\ell=1}^{m}w_{j\ell}^{P}c_{\ell}=\sum_{\ell=1}^{n}c_{\ell}\cdot\sum_{j=1}^{n}w_{j\ell}^{P}=\sum_{\ell=1}^{m}c_{\ell}.$

性质5. 如果物品的用户都是物品的用户，换句话说，如果 则有那么对于所有的都成立。反之，如果那么物品的用户都是物品的用户。

证明. 根据 $w_{j\ell}^{P}$ 的定义，可以得到

$w_{jj}^{P}=\frac{1}{k(O_{j})}\cdot \sum_{i=1}^{m}\frac{a_{ij}^{2}}{k(U_{i})}=\frac{1}{k(O_{j})}\cdot \sum_{\{1\leq i\leq m, a_{ij}=1\}}\frac{1}{k(U_{i})},$

$w_{\ell j}^{P}=\frac{1}{k(O_{j})}\cdot \sum_{i=1}^{m}\frac{a_{i\ell}a_{ij}}{k(U_{i})}=\frac{1}{k(O_{j})}\cdot \sum_{1\leq i\leq m, a_{ij}=1}\frac{a_{i\ell}}{k(U_{i})}.$

根据条件，如果 $a_{ij}=1,$ 则有 $a_{i\ell}=1,$ 那么上面两个式子相等。i.e. $w_{jj}^{P}=w_{\ell j}^{P}$ 对于所有的 $1\leq \ell \leq n$ 都成立。

根据上面性质，可以定义变量

$I_{j}=\sum_{\ell=1}^{n}(w_{\ell j}^{P}/w_{jj}^{P})^{2},$

其中 $w_{\ell j}^{P}/w_{jj}^{P}$ 可以看成物品 $O_{j}$ 与物品 $O_{j}$ 的独立程度。如果 $w_{\ell j}^{P}/w_{jj}^{P}=1,$ 那么说明物品 $O_{j}$ 的用户都是物品 $O_{\ell}$ 的用户。如果 $w_{\ell j}^{P}/w_{jj}^{P}=0,$ 那么说明物品 $O_{j}$ 的用户与物品 $O_{\ell}$ 的用户则没有交集。换言之，物品 $O_{j}$ 与物品 $O_{\ell}$ 则相对独立。根据这个性质，如果 $I_{j}$ 越小，那么物品 $O_{j}$ 与其他物品就相对独立。

性质6. 对于所有的都是成立的。

证明. 根据以上性质可以得到 $w_{\ell j}^{P}\leq w_{jj}^{P}$ 对于 $1\leq \ell \leq n$ 都成立，并且 $I_{j}\geq (w_{jj}^{P}/w_{jj}^{P})^{2}=1,$ 所以上面性质成立。

基于物质扩散算法的用户相似度

回顾一下基于用户的协同过滤算法：用户 $U_{\alpha}, U_{\beta}$ 的相似度是

$S_{\alpha \beta}=(\sum_{j=1}^{n}a_{\alpha j}\cdot a_{\beta j})/\min\{k(U_{\alpha}),k(U_{\beta})\}$

或者使用余弦表达式

$S_{\alpha \beta}=(\sum_{j=1}^{n}a_{\alpha j}\cdot a_{\beta j})/\sqrt{k(U_{\alpha})\cdot k(U_{\beta})}.$

如果用户 $U_{i}$ 并没有选择物品 $O_{j},$ 那么预测分数则是

$v_{ij}=(\sum_{1\leq \ell \leq m, \ell\neq i} S_{i\ell}\cdot a_{j\ell}) / \sum_{1\leq \ell \leq m, \ell\neq i} S_{i\ell}.$

这里的求和指的把除了用户 $i$ 的其他用户做相似度的加权，看用户 $U_{\ell}$ 是否购买了物品 $O_{j}.$ 然后对于任意的用户和物品组成的对 $(i,j),$ 只要 $a_{ij}=0$ （意思是用户 $U_{i}$ 并没有购买过物品 $O_{j}$ ），根据预测分数 $v_{ij}$ 从大到小对 $1\leq j\leq n$ 排序，推荐 $v_{ij}$ 值大的物品给用户 $U_{i}$ 即可。以上就是基于用户的协同过滤算法。

下面来介绍基于物质扩散方法的算法。与上面的方法类似，第一步就是定义用户相似度 $S_{\alpha \beta}^{P}$ 如下：

$S_{\alpha \beta}^{P}=\frac{1}{k(U_{\beta})}\cdot \sum_{j=1}^{n}\frac{a_{\alpha j}\cdot a_{\beta j}}{k(O_{j})}.$

上面定义表示物品 $O_{j}$ 购买的人越多，用户的相似度 $S_{\alpha \beta}^{P}$ 就会减少。原因就是比方说像新华字典这种购买的人非常多的物品，并不能说明大多数人都是相似的，反而是购买数学分析这种物品的人相似性比较大。也就是说物品的热门程度 $k(O_{j})$ 对计算用户相似度的时候有抑制作用。此时的评分系统则是：如果用户 $U_{\alpha}$ 之前没有购买物品 $O_{i},$ 那么其预测分数则是

$v_{\alpha i}=(\sum_{1\leq \beta\leq m, \beta\neq\alpha}S_{\alpha \beta}^{P}\cdot a_{\beta i})/\sum_{1\leq \beta\leq m, \beta\neq\alpha}S_{\alpha \beta}^{P}$