13 facebook權重算法(騰訊算法高級研究員陳松堅：智能問答技術及其應用)

基于物品的協同過濾指基于物品的行為相似度（如啤酒尿布被同時購買）來進行物品推薦。該算法認為，物品A和物品B具有很大相似度是因為喜歡物品A的用戶大都也喜歡物品B。

基于物品的協同過濾算法主要分為兩步：

基于物品的協同過濾算法中計算物品相似度的方法有以下幾種：

（1）基于共同喜歡物品的用戶列表計算。

此外，John S. Breese再其論文中還提及了IUF（Inverse User Frequence，逆用戶活躍度）的參數，其認為活躍用戶對物品相似度的貢獻應該小于不活躍的用戶，應該增加IUF參數來修正物品相似度的公式：

上面的公式只是對活躍用戶做了一種軟性的懲罰， 但對于很多過于活躍的用戶， 比如某位買了當當網80%圖書的用戶， 為了避免相似度矩陣過于稠密， 我們在實際計算中一般直接忽略他的興趣列表， 而不將其納入到相似度計算的數據集中。

（2）基于余弦相似度計算。

（3）熱門物品的懲罰。

此外，Kary pis在研究中發現如果將ItemCF的相似度矩陣按最大值歸一化， 可以提高推薦的準確率。 其研究表明， 如果已經得到了物品相似度矩陣w， 那么可以用如下公式得到歸一化之后的相似度矩陣w'：

歸一化的好處不僅僅在于增加推薦的準確度，它還可以提高推薦的覆蓋率和多樣性。一般來說，物品總是屬于很多不同的類，每一類中的物品聯系比較緊密。假設物品分為兩類——A和B， A類物品之間的相似度為0.5， B類物品之間的相似度為0.6， 而A類物品和B類物品之間的相似度是0.2。 在這種情況下， 如果一個用戶喜歡了5個A類物品和5個B類物品， 用ItemCF給他進行推薦， 推薦的就都是B類物品， 因為B類物品之間的相似度大。 但如果歸一化之后， A類物品之間的相似度變成了1， B類物品之間的相似度也是1， 那么這種情況下， 用戶如果喜歡5個A類物品和5個B類物品， 那么他的推薦列表中A類物品和B類物品的數目也應該是大致相等的。 從這個例子可以看出， 相似度的歸一化可以提高推薦的多樣性。

那么，對于兩個不同的類，什么樣的類其類內物品之間的相似度高，什么樣的類其類內物品相似度低呢？一般來說，熱門的類其類內物品相似度一般比較大。如果不進行歸一化，就會推薦比較熱門的類里面的物品，而這些物品也是比較熱門的。因此，推薦的覆蓋率就比較低。相反，如果進行相似度的歸一化，則可以提高推薦系統的覆蓋率。

最后，利用物品相似度矩陣和用戶打過分的物品記錄就可以對一個用戶進行推薦評分：

基于用戶的協同算法與基于物品的協同算法原理類似，只不過基于物品的協同是用戶U購買了A物品，會計算經常有哪些物品與A一起購買（也即相似度），然后推薦給用戶U這些與A相似的物品。而基于用戶的協同則是先計算用戶的相似性（通過計算這些用戶購買過的相同的物品），然后將這些相似用戶購買過的物品推薦給用戶U。

基于用戶的協同過濾算法主要包括兩個步驟：

步驟（1）的關鍵是計算用戶的興趣相似度，主要是利用用戶的行為相似度計算用戶相似度。給定用戶 u 和 v，N(u) 表示用戶u曾經有過正反饋（譬如購買）的物品集合，N(v) 表示用戶 v 曾經有過正反饋的物品集合。那么我們可以通過如下的 Jaccard 公式簡單的計算 u 和 v 的相似度：

或通過余弦相似度：

得到用戶之間的相似度之后，UserCF算法會給用戶推薦和他興趣最相似的K個用戶喜歡的物品。如下的公式度量了UserCF算法中用戶 u 對物品 i 的感興趣程度：

首先回顧一下UserCF算法和ItemCF算法的推薦原理：UserCF給用戶推薦那些和他有共同興趣愛好的用戶喜歡的物品， 而ItemCF給用戶推薦那些和他之前喜歡的物品具有類似行為的物品。

（1）從推薦場景考慮

首先從場景來看，如果用戶數量遠遠超過物品數量，如購物網站淘寶，那么可以考慮ItemCF，因為維護一個非常大的用戶關系網是不容易的。其次，物品數據一般較為穩定，因此物品相似度矩陣不必頻繁更新，維護代價較小。

UserCF的推薦結果著重于反應和用戶興趣相似的小群體的熱點，而ItemCF的推薦結果著重于維系用戶的歷史興趣。換句話說，UserCF的推薦更社會化，反應了用戶所在小型興趣群體中物品的熱門程度，而ItemCF的推薦更加個性化，反應了用戶自己的個性傳承。因此UserCF更適合新聞、微博或微內容的推薦，而且新聞內容更新頻率非常高，想要維護這樣一個非常大而且更新頻繁的表無疑是非常難的。

在新聞類網站中，用戶的興趣愛好往往比較粗粒度，很少會有用戶說只看某個話題的新聞，而且往往某個話題也不是每天都會有新聞。 個性化新聞推薦更強調新聞熱點，熱門程度和時效性是個性化新聞推薦的重點，個性化是補充，所以 UserCF 給用戶推薦和他有相同興趣愛好的人關注的新聞，這樣在保證了熱點和時效性的同時，兼顧了個性化。

（2）從系統多樣性（也稱覆蓋率，指一個推薦系統能否給用戶提供多種選擇）方面來看，ItemCF的多樣性要遠遠好于UserCF，因為UserCF更傾向于推薦熱門物品。而ItemCF具有較好的新穎性，能夠發現長尾物品。所以大多數情況下，ItemCF在精度上較小于UserCF，但其在覆蓋率和新穎性上面卻比UserCF要好很多。

在介紹本節基于矩陣分解的隱語義模型之前，讓我們先來回顧一下傳統的矩陣分解方法SVD在推薦系統的應用吧。

基于SVD矩陣分解在推薦中的應用可分為如下幾步：

SVD在計算前會先把評分矩陣 A 缺失值補全，補全之后稀疏矩陣 A 表示成稠密矩陣，然后將分解成 A' = U∑V T 。但是這種方法有兩個缺點：（1）補成稠密矩陣后需要耗費巨大的儲存空間，對這樣巨大的稠密矩陣進行儲存是不現實的；（2）SVD的計算復雜度很高，對這樣大的稠密矩陣中進行計算式不現實的。因此，隱語義模型就被發明了出來。

更詳細的SVD在推薦系統的應用可參考 奇異值分解SVD簡介及其在推薦系統中的簡單應用 。

隱語義模型（Latent Factor Model）最早在文本挖掘領域被提出，用于找到文本的隱含語義。相關的算法有LSI，pLSA，LDA和Topic Model。本節將對隱語義模型在Top-N推薦中的應用進行詳細介紹，并通過實際的數據評測該模型。

隱語義模型的核心思想是通過隱含特征聯系用戶興趣和物品。讓我們通過一個例子來理解一下這個模型。

現有兩個用戶，用戶A的興趣涉及偵探小說、科普圖書以及一些計算機技術書，而用戶B的興趣比較集中在數學和機器學習方面。那么如何給A和B推薦圖書呢？

我們可以對書和物品的興趣進行分類。對于某個用戶，首先得到他的興趣分類，然后從分類中挑選他可能喜歡的物品。簡言之，這個基于興趣分類的方法大概需要解決3個問題：

對于第一個問題的簡單解決方案是找相關專業人員給物品分類。以圖書為例，每本書出版時，編輯都會給出一個分類。但是，即使有很系統的分類體系，編輯給出的分類仍然具有以下缺點：（1）編輯的意見不能代表各種用戶的意見；（2）編輯很難控制分類的細粒度；（3）編輯很難給一個物品多個分類；（4）編輯很難給一個物品多個分類；（5）編輯很難給出多個維度的分類；（6）編輯很難決定一個物品在某一個類別中的權重。

為了解決上述問題，研究員提出可以從數據出發，自動找到那些分類，然后進行個性化推薦。隱語義模型由于采用基于用戶行為統計的自動聚類，較好地解決了上面提出的5個問題。

LFM將矩陣分解成2個而不是3個：

推薦系統中用戶和物品的交互數據分為顯性反饋和隱性反饋數據。隱式模型中多了一個置信參數，具體涉及到ALS（交替最小二乘法，Alternating Least Squares）中對于隱式反饋模型的處理方式——有的文章稱為“加權的正則化矩陣分解”：

一個小細節：在隱性反饋數據集中，只有正樣本（正反饋）沒有負反饋（負樣本），因此如何給用戶生成負樣本來進行訓練是一個重要的問題。Rong Pan在其文章中對此進行了探討，對比了如下幾種方法：

用戶行為很容易用二分圖表示，因此很多圖算法都可以應用到推薦系統中。基于圖的模型（graph-based model）是推薦系統中的重要內容。很多研究人員把基于領域的模型也稱為基于圖的模型，因為可以把基于領域的模型看作基于圖的模型的簡單形式。

在研究基于圖的模型之前，需要將用戶行為數據表示成圖的形式。本節的數據是由一系列用戶物品二元組 (u, i) 組成的，其中 u 表示用戶對物品 i 產生過行為。

令 G(V, E) 表示用戶物品二分圖，其中 V=V U UV I 由用戶頂點 V U 和物品節點 V I 組成。對于數據集中每一個二元組 (u, i) ，圖中都有一套對應的邊 e(v u , v i )，其中 v u ∈V U 是用戶對應的頂點，v i ∈V I 是物品i對應的頂點。如下圖是一個簡單的物品二分圖，其中圓形節點代表用戶，方形節點代表物品，用戶物品的直接連線代表用戶對物品產生過行為。比如下圖中的用戶A對物品a、b、d產生過行為。

度量圖中兩個頂點之間相關性的方法很多，但一般來說圖中頂點的相關性主要取決于下面3個因素：

而相關性高的一對頂點一般具有如下特征：

舉個例子，如下圖，用戶A和物品c、e沒有邊直連，但A可通過一條長度為3的路徑到達c，而Ae之間有兩條長度為3的路徑。那么A和e的相關性要高于頂點A和c，因而物品e在用戶A的推薦列表中應該排在物品c之前，因為Ae之間有兩條路徑。其中，（A,b,C,e）路徑經過的頂點的出度為（3，2，2，2），而 (A,d,D,e) 路徑經過了一個出度比較大的頂點D，所以 (A,d,D,e) 對頂點A與e之間相關性的貢獻要小于（A,b,C,e）。

基于上面3個主要因素，研究人員設計了很多計算圖中頂點相關性的方法，本節將介紹一種基于隨機游走的PersonalRank算法。

假設要給用戶u進行個性化推薦，可以從用戶u對應的節點 v u 開始在用戶物品二分圖上進行隨機游走。游走到任一節點時，首先按照概率α決定是繼續游走還是停止這次游走并從 v u 節點重新開始游走。若決定繼續游走，則從當前節點指向的節點中按照均勻分布隨機選擇一個節點作為游走下次經過的節點。這樣，經過很多次隨機游走后，每個物品被訪問到的概率會收斂到一個數。最終的推薦列表中物品的權重就是物品節點的訪問概率。

上述算法可以表示成下面的公式：

雖然通過隨機游走可以很好地在理論上解釋PersonalRank算法，但是該算法在時間復雜度上有明顯的缺點。因為在為每個用戶進行推薦時，都需要在整個用戶物品二分圖上進行迭代，知道所有頂點的PR值都收斂。這一過程的時間復雜度非常高，不僅無法在線進行實時推薦，離線計算也是非常耗時的。

有兩種方法可以解決上面PersonalRank時間復雜度高的問題：

（1）減少迭代次數，在收斂之前停止迭代。但是這樣會影響最終的精度。