推薦系統中用到的熱傳導演算法和物質擴散是怎麼用的？

01-23

在鵝廠實習，發現這個演算法在推薦系統裡面用的非常廣，組裡面也在用，於是調研了下，寫了篇總結，直接粘過來了。

總結過程中參考了網上的很多文章，我自己的工作主要在數學模型部分。

在推薦系統中，常常用二部圖來表示用戶和物品之間的關係：把用戶（Users）看成一類，把物品（Objects）看作另一類。當某個用戶購買過某個商品時，他們之間會存在一條連邊。而同一類點之間不存在連邊，即用戶與用戶之間，商品與商品之間不存在連邊，類似於這樣組成的網路就稱為二部圖。電子商務中的商品推薦，可以看做是二部圖上的鏈路挖掘問題，而擴散過程可以用來尋找網路中兩個節點之間的關聯強度。

典型的擴散有兩類：一類是物質或者能量的擴散，滿足守恆律，常稱作為物質擴散（Mass Diffusion）；另一類是熱的擴散，一般由一個或多個恆溫熱源驅動，不滿足守恆律，常被稱作為熱傳導（Heat Spreading）。

一、舉個栗子

下圖展示了兩種典型的擴散過程。考慮為標有星號（即用戶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)中的結果，則在目標用戶沒有購買過的所有商品中，第二個商品的溫度值最大，因此基於熱傳導演算法的推薦系統則會將此商品推薦給目標用戶。

與物質擴散不同的是這種演算法得到的所有商品最後的能量值之和就不一定等於初始時所有商品的能量值，即不滿足守恆定律，這是因為在熱傳到的第二步過程中，有的用戶的溫度可能會被多次計算，從而導致不守恆。

二、數學模型

假設我們有m個用戶(User)和n個物品(Object)，可以構造矩陣 $A_{m imes n}$ ，其中：

$a_{ij} = egin{cases} 1 ext{user i buy Object j} \ 0 ext{user i not buy Object 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的度，即該商品被多少個用戶購買。

2.1 物質擴散

- 第一步，用戶從物品那裡獲得能量（每件商品把自己的能量平均分給所有購買過它的用戶），用戶 $alpha$ 獲得的能量我們用 $b_{alpha}$ 表示：
$b_{alpha} = sum_{l=1}^{n}a_{alpha l}(frac{c_l}{k(O_l)})$
- 第二步，用戶將能量傳遞給物品（每個用戶再把自己的能量平局分給所有購買過的商品），物品j更新後的能量我們用 $c_{j}^{$ 表示：
$c_{j}^{$
整理一下：
$egin{align*} c_{j}^{$
其中，
$w_{jl}^P = frac{1}{k(O_l)} sum_{alpha=1}^{m}frac{a_{alpha j}a_{alpha l}}{k(U_{alpha})}$
採用向量化的表示方法：

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

---

2.2 熱傳導

- 第一步，用戶的溫度等於所有他購買過的商品的溫度的**平均值**，用戶 $alpha$ 的溫度我們用 $b_{alpha}$ 表示：
$b_{alpha} = sum_{l=1}^{n} frac{a_{alpha l}c_l}{k(U_{alpha})}$
- 第二步，每件商品的溫度等於所有購買過他的用戶的溫度的平均值，物品j更新後的溫度我們用 $t_{j}^{$ 表示：
$t_{j}^{$
整理一下：

$egin{align*} t_{j}^{$
其中，
$w_{jl}^H = frac{1}{k(O_{j})}sum_{alpha=1}^{m} frac{a_{alpha j}a_{alpha l}}{k(U_{alpha})}$
---
採用向量化的表示方法：
$T^{$
其中， $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})}$

Reference

[1]:http://www.ccast.ac.cn/workshop/network-2010/wenzhang/zt.pdf

[2]:物質擴散模型

[3]:科學網—淺談物理學方法在推薦系統中應用價值和意義

[4]:推薦演算法整理 -- 擴散演算法

先佔地，這個可以聊聊。

其實整個推薦系統的問題，有極大一部分是對關係網路的計算。這個網路包括但不限於：

1. 商品和商品的相似性關係

2. 用戶-商品的喜好關係

等等，這些關係一般可以用一些非常大的稀疏矩陣來表示，等價於比較大的圖（網路）。這些圖可能是有向的，也可能是無向的。

而其實對於非常大的、在現實中可能存在的圖（網路）的研究，有一門科學就叫作網路科學（Network Science），這門科學...基本上是物理學。有非常多的物理學的方法可以應用到這個領域。熱力學方法只是其中一種。甚至還有利用量子力學把網路節點當作磁矩最小化哈密爾頓量來求最優圖分割的等等。

熱力學方法其實就是把網路的每個節點當作一個粒子，然後粒子間的熱運動（或者其他的什麼物理性質）可以通過網路的邊來傳導，這種傳導由於容易進行並行計算，有可能得到一些很好的性質。

使用物理學的好處是，物理學方法背後有物理圖景，有可能給演算法一個很強有力的解釋性出來。

當然實際中這塊的研究其實從上個世紀90年代才剛剛入門，現在很多方法都是經驗性的。機器學習尤其是推薦系統是一個非常結果導向商業性的東西，所以真正好的方法都並沒有什麼物理學圖景而且也還沒有找到好的解釋，當然這更可能是因為我們人類對這裡的理解還太淺了。

這是簡單的計算進行步奏，希望給你幫助哦

沒人回答？那我就自己把這幾天的研究貼出來，其實就是找到了一個帖子：

http://www.360doc.com/content/10/0601/21/11586_30745105.shtml

看了之後還是不甚明白怎麼運用到實際推薦中。