物质扩散模型

引言

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

物质扩散(Probabilistic 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. 矩阵W^{P}每列的和都是1,i.e. \sum_{j=1}^{n}w_{j\ell}^{P}=1对于所有的1\leq \ell \leq n都成立。

证明. \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. \frac{w_{j\ell}^{P}}{k(O_{j})}=\frac{w_{\ell j}^{P}}{k(O_{\ell})}对于所有的1\leq j,\ell\leq n都成立。换言之,矩阵W^{P}不一定是对称矩阵,只有在所有物品的度都完全一致的情况下才是对称矩阵。

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

性质3. 矩阵W^{P}对角线上的元素是该列的最大值。i.e. w_{jj}^{P}\geq w_{\ell j}^{P}对于所有的1\leq j,\ell\leq n都成立。

证明. 根据矩阵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. 能量守恒定律:\sum_{j=1}^{n}c_{j}^{'}=\sum_{\ell=1}^{n}c_{\ell}.

证明. 根据前面的性质,已经知道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. 如果物品O_{j}的用户都是物品O_{\ell}的用户,换句话说,如果a_{ij}=1, 则有a_{i\ell}=1.那么w_{jj}^{P}=w_{\ell j}^{P}对于所有的1\leq \ell \leq n都成立。反之,如果w_{jj}^{P}=w_{\ell j}^{P},那么物品O_{j}的用户都是物品O_{\ell}的用户。

证明. 根据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. 1\leq I_{j}\leq n对于所有的1\leq j\leq n都是成立的。

证明. 根据以上性质可以得到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}

对于物质扩散的算法,可以用以下简单方法进行推广。增加参数d>0,定义用户U_{\alpha}和用户U_{\beta}的相似度S_{\alpha \beta}^{P}(d)如下:

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

d>1时,减弱了热门物品对用户相似度的影响;当d\in (0,1)时,增加了热门物品对用户相似度的影响。某篇论文显示基于某些数据,d=1.9是最佳的参数。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s