《推薦系統實踐》讀書筆記

1. 推薦系統

1.1. 什么是推薦系統

（1）推薦系統的定義
推薦系統（Recommendation System, RS）是一種自動聯系用戶和物品的工具，它能夠幫助用戶在資訊過載的環境中發現令他們感興趣的資訊，它通常由前臺的展示頁面、后臺的日志系統、推薦演算法系統三個部分組成，

（2）為什么需要推薦系統
隨著互聯網上的資料越來越多，各大應用及平臺坐擁海量資訊，但用戶卻難以找到真正對自己有用的資訊，用戶面對龐大的資料變得毫無頭緒，

目前有三大方法可以解決資訊超載的問題：分類目錄、搜索引擎和推薦系統：

• 分類目錄
  分類目錄是將資訊分門別類，從而方便用戶根據類別進行查找，例如：優設導航 、百度更多 等門戶網站，但分類目錄只適合用在內容少而精的網站上，大多數分類目錄網站只能涵蓋少數熱門資訊，應用場景有限，
• 搜索引擎
  用戶通過在搜索引擎上輸入關鍵字，查找自己需要的資訊，例如：搜狗、Bing 等搜索引擎，但是，用戶必須主動提供準確的關鍵詞，才可能找到需要的資訊，
• 推薦系統
  推薦系統通過分析用戶的歷史行為，對用戶的興趣進行建模，從而主動給用戶推薦可能滿足他們需求的資訊，該方法能夠很好的發掘長尾資訊，

我們可以看到，推薦系統相對于分類目錄和搜索引擎，在某些方面有著不可替代的優勢，通常認為，當一個系統滿足以下兩個條件時，就可以考慮應用推薦系統：

1. 存在資訊過載（用戶難以找到想要的內容）；
2. 用戶大多數時候沒有明確的需求，

1.2. 推薦系統評測

一個完整的推薦系統包括三個參與方：

• 用戶
• 網站（平臺，負責搭載推薦系統）
• 內容提供方

在評測一個推薦系統時，需要考慮上述三方的利益，一個好的推薦系統是能夠令三方共贏的系統，

1.2.1. 實驗方法

一般來說，一個新的推薦演算法最終上線，需要通過3個實驗，

• 首先，通過離線實驗證明它在很多離線指標上優于現有的演算法；
• 其次，通過用戶調查確定用戶滿意度不低于現有的演算法；
• 最后，通過在線AB測驗確定它在特定的指標上優于現有的演算法；

（1）離線實驗 Offline Experiment
離線實驗的方法的步驟如下：

• 通過日志系統獲得用戶行為資料，并生成一個標準資料集；
• 將資料集分成訓練集和測驗集；
• 在訓練集上訓練用戶興趣模型，在測驗集上進行預測；
• 通過事先定義的離線指標，評測演算法在測驗集上的預測結果，

從以上步驟看出，離線實驗的都是在標準資料集上完成的，這意味著，它不需要一個實際的系統作為支撐，只需要有一個模擬環境即可，

離線實驗的優缺點：

優點	缺點
不需要有對實際系統的控制權	無法計算商業上關心的指標
不需要用戶參與實驗	離線實驗的指標和商業指標存在差距
速度快，可以測驗大量演算法

（2）用戶調查 User Study
用戶調查由真實的用戶在需要測驗的推薦系統上完成某些任務，在他們完成這些任務時，觀察和記錄他們的行為，并讓他們回答一些問題，最后通過分析他們的行為和答案，了解推薦系統的性能，

用戶調查的優缺點：

優點	缺點
可以獲得用戶主觀感受的指標	招募測驗用戶代價較大
風險低，出錯后容易彌補	無法組織大規模的測驗用戶，統計意義不足
	雙盲實驗設計困難，導致收集的測驗指標無法在真實環境下重現

（3）在線實驗 Online Experiment
在線實驗是指將系統上線做AB測驗，把它和舊演算法進行比較，AB測驗通過一定的規則將用戶隨機分成幾組，對不同組的用戶采用不同的演算法，然后通過統計不同組的評測指標，比較不同演算法的好壞，

AB測驗的優缺點：

優點	缺點
可以準確地獲得不同演算法的實際性能指標和商業上關注的指標	周期較長，必須進行長期的實驗才能得到可靠的結果

大型網站做AB測驗，可能會因為不同團隊同時進行各種測驗對結果造成干擾，所以切分流量是AB測驗中的關鍵，不同的測驗層以及控制這些層的團隊，需要從一個統一的流量入口獲得自己AB測驗的流量，而不同層之間的流量應該是正交的，關于分層實驗和流量正交的知識可以參考這篇博客：黃一能：什么是科學的AB測驗？談談分層實驗和流量正交

1.2.2. 評判指標

評測指標用于評測推薦系統的性能，有些可以定量計算，如預測準確度、覆寫率、多樣性、實時性；有些只能定性描述，如用戶滿意度、新穎性、驚喜度、信任度、健壯性和商業目標，

有了這些指標，就可以根據需要對推薦系統進行優化，通常的優化目標是在給定覆寫率、多樣性、新穎性等限制條件下，盡量提高預測準確度，

	離線實驗	問卷調查	在線實驗
用戶滿意度	×	√	√
預測準確度	√	√	×
覆寫率	√	√	√
多樣性	√	√	√
新穎性	√	√	√
驚喜度	×	√	×

下面我們分別介紹一下這幾種評測指標，

(1) 用戶滿意度
用戶滿意度是評測推薦系統的重要指標，無法離線計算，只能通過用戶調查或者在線實驗獲得，

• 調查問卷的設計需要考慮周全，用戶才能針對特定問題給出準確的回答；
• 在線系統中用戶的滿意度通過統計用戶行為得到，一般情況，可以用用戶點擊率、停留時間、轉化率等指標度量用戶的滿意度，

(2) 預測準確度

預測準確度是度量一個推薦系統或其中推薦演算法預測用戶行為的能力， 是推薦系統最重要的離線評測指標，大致可從“評分預測”和“Top-N推薦”兩個方面進行評測，

評分預測
預測評分的準確度，衡量的是演算法預測的評分與用戶的實際評分的貼近程度，一般通過以下指標度量：

設測驗集 T T T 中有用戶 u u u 和物品 i i i，用 r u i r_{ui} rui? 表示用戶 u u u 對物品 i i i 的實際評分； r ^ u i \hat{r}_{ui} r^ui? 表示推薦演算法給出的預測評分，則

• 平均絕對誤差（MAE） M A E = ∑ ( u , i ) ∈ T ∣ r u i ? r u i ′ ∣ ∣ T ∣ MAE=\frac{\sum_{(u,i)\in T}|r_{ui}-r_{ui}'|}{|T|} MAE=∣T∣∑(u,i)∈T?∣rui??rui′?∣?
• 均方根誤差（RMSE） R M S E = ∑ ( u , i ) ∈ T ( r u i ? r ^ u i ) 2 ∣ T ∣ RMSE=\sqrt{\frac{\sum_{(u,i)\in T}(r_{ui}-\hat{r}_{ui})^2}{|T|}} RMSE=∣T∣∑(u,i)∈T?(rui??r^ui?)2? ?一般而言，RMSE的誤差會比MAE小

Top-N推薦
如果推薦服務會給用戶提供個性化的推薦串列，那么這種推薦就叫做Top-N推薦，

Top-N推薦的預測準確率，一般通過2個指標度量：

設 R ( u ) R(u) R(u) 是根據用戶在訓練集上的行為提供給用戶的推薦串列， T ( u ) T(u) T(u) 是用戶在測驗集上的實際行為串列，

• 準確率（Precision） P r e c i s i o n = ∑ u ∈ U ∣ R ( u ) ∩ T ( u ) ∣ ∑ u ∈ U ∣ R ( u ) ∣ Precision=\frac{\sum_{u\in U}|R(u)\cap T(u)|}{\sum_{u\in U}|R(u)|} Precision=∑u∈U?∣R(u)∣∑u∈U?∣R(u)∩T(u)∣?
• 召回率（Recall） R e c a l l = ∑ u ∈ U ∣ R ( u ) ∩ T ( u ) ∣ ∑ u ∈ U ∣ T ( u ) ∣ Recall=\frac{\sum_{u\in U}|R(u)\cap T(u)|}{\sum_{u\in U}|T(u)|} Recall=∑u∈U?∣T(u)∣∑u∈U?∣R(u)∩T(u)∣?

Top-N推薦由于其個性化特性突出，因此相對于評分預測更符合實際的應用需求，

(3) 覆寫率
覆寫率(Coverage)是描述一個推薦系統對物品長尾的發掘能力，覆寫率最簡單的定義是：推薦系統能夠推薦出來的物品占總物品集合的比例，

假設系統的用戶集合為 U U U，總物品集合為 I I I，推薦系統給每個用戶推薦一個長度為 N N N 的物品推薦串列 R ( u ) R(u) R(u)，覆寫率公式表達為： C o v e r a g e = ? u ∈ U R ( u ) ∣ I ∣ Coverage=\frac{\bigcup_{u\in U}R(u)}{|I|} Coverage=∣I∣?u∈U?R(u)?

覆寫率是內容提供者關心的指標，覆寫率為100%的推薦系統可以將每個物品都至少推薦給一個用戶，

除了利用推薦物品的占比來定義覆寫率，還可以通過研究物品在推薦串列中出現的次數分布來描述推薦系統的挖掘長尾的能力，如果分布比較平，說明推薦系統的覆寫率很高；如果分布陡峭，說明分布系統的覆寫率較低，

資訊論和經濟學中有兩個著名指標，可以定義覆寫率：

• 資訊熵 H = ? ∑ i = 1 n p ( i ) log ? p ( i ) H=-\sum_{i=1}^{n}p(i)\log p(i) H=?i=1∑n?p(i)logp(i)其中 p ( i ) p(i) p(i)是物品 i i i的流行度除以所有物品流行度之和；
• 基尼系數（Gini Index） G = 1 n ? 1 ∑ j = 1 n ( 2 j ? n ? 1 ) p ( i j ) G=\frac{1}{n-1}\sum_{j=1}^{n}(2j-n-1)p(i_j) G=n?11?j=1∑n?(2j?n?1)p(ij?)其中， i j i_j ij? 是按照物品流行度 p p p 從小到大排序的物品串列中第 j j j 個物品，

基尼系數的計算原理：首先，我們將物品按照熱門程度從低到高排列，那么下圖中的黑色曲線表示最不熱門的 x % x\% x% 物品的總流行度占系統的比例 y % y\% y% ，這條曲線肯定是在 y = x y=x y=x 曲線之下的，而且和 y = x y=x y=x 曲線相交在(0,0)和(1,1)，

令 S A S_A SA? 為 A A A 的面積， S B S_B SB? 為 B B B 的面積，那么基尼系數的形象定義就是 S A / ( S A + S B ) S_A/(S_A+S_B) SA?/(SA?+SB?)，從定義可知，基尼系數屬于區間 [ 0 , 1 ] [0,1] [0,1]，
如果系統的流行度很平均，那么 S A S_A SA? 就會很小，從而基尼系數很小，如果系統物品流行度分配很不均勻，那么 S A S_A SA? 就會很大，從而基尼系數也會很大，

(4) 多樣性
為了滿足用戶廣泛的興趣，推薦串列需要能夠覆寫用戶不同的興趣領域，即需要具有多樣性，

多樣性描述了推薦串列中物品之間的不相似性，假設 s ( i , j ) ∈ [ 0 , 1 ] s(i,j)\in [0,1] s(i,j)∈[0,1] 定義了物品 i i i 和 j j j 之間的相似度，那么用戶 u u u的推薦串列 R ( u ) R(u) R(u) 的多樣性定義如下： D i v e r s i t y = 1 ? ∑ i , j ∈ R ( u ) , i ≠ j s ( i , j ) 1 2 ∣ R ( u ) ∣ ( ∣ R ( u ) ∣ ? 1 ) Diversity=1-\frac{\sum_{i,j\in R(u),i\neq j}s(i,j)}{\frac{1}{2}|R(u)|(|R(u)|-1)} Diversity=1?21?∣R(u)∣(∣R(u)∣?1)∑i,j∈R(u),i?=j?s(i,j)?

推薦系統整體多樣性可以定義為所有用戶推薦串列多樣性的均值： D i v e r s i t y = 1 ∣ U ∣ ∑ u ∈ U D i v e r s i t y ( R ( u ) ) Diversity=\frac{1}{|U|}\sum_{u\in U}Diversity(R(u)) Diversity=∣U∣1?u∈U∑?Diversity(R(u))

(5) 新穎性
新穎性也是影響用戶體驗的重要指標之一，它指的是向用戶推薦非熱門非流行物品的能力，評測新穎度最簡單的方法是利用推薦結果的平均流行度，因為越不熱門的物品，越可能讓用戶覺得新穎，

但是這種計算方法比較粗糙，因為不同用戶不知道的東西是不同的，需要配合用戶調查準確統計新穎度，

(6) 驚喜度
驚喜度與新穎度相關，它是指推薦結果和用戶的歷史興趣不相似，但卻讓用戶滿意的程度，

(7) 信任度
信任度用于衡量用戶對推薦系統的信任程度，這個指標的意義在于，如果用戶信任推薦系統就會增多用戶和推薦系統的互動，信任度目前只能通過問卷調查的方式來度量，

提高信任度的方式主要有兩種：

• 增加系統透明度
  即提供推薦解釋，讓用戶了解推薦系統的運行機制，
• 利用社交網路資訊
  即利用用戶的好友給用戶做推薦，

(8) 實時性
許多物品具有很強的時效性，例如新聞、微博等，需要在時效期內推薦給用戶，否則物品的價值就可能大打折扣，推薦系統的實時性包括兩方面：

• 實時更新推薦串列滿足用戶新的行為變化；
• 將新加入系統的物品推薦給用戶；

前者可以通過推薦串列的更新速率來控制和測評，后者可以通過計算推薦串列中有多大比例的物品是新加入物品來測評，

(9) 健壯性
任何能帶來利益的演算法系統都會被攻擊，最典型的案例就是搜索引擎的作弊與反作弊斗爭，推薦系統也不例外，健壯性衡量了推薦系統抗擊作弊的能力，

2011年的推薦系統大會專門有一個推薦系統健壯性的教程，作者總結了很多作弊方法，最著名的是行為注入攻擊（Profile Injection Attack），就是注冊很多賬號，用這些賬號同時購買某件商品A和自己的商品，此方法針對一種購物網站的推薦方法：“購買商品A的用戶也經常購買的其他商品”，

一般會利用模擬攻擊來評測演算法的健壯性：

• 給定一個資料集和演算法，用演算法給資料集中的用戶生成推薦串列；
• 用常用的攻擊方法向資料集中注入噪聲資料；
• 利用演算法在有噪聲的資料集上再次生成推薦串列；
• 通過比較攻擊前后推薦串列的相似度評測演算法的健壯性，

提高推薦系統健壯性的方法：

• 選擇健壯性高的演算法；
• 選擇代價較高的用戶行為，例如收費的用戶行為（購物等）、限制用戶權限（給用戶分級）；
• 在使用資料前進行攻擊檢測，從而對資料進行清理，

(10) 商業目標
設計推薦系統時，需要考慮最終的商業目標，不同網站具有不同的商業目標，它與網站的盈利模式息息相關，

比如電子商務網站的目標可能是銷售額，基于展示廣告盈利的網站其商業目標可能是廣告展示總數，基于點擊廣告盈利的網站其商業目標可能是廣告點擊總數，因此，設計推薦系統時需要考慮最終的商業目標，也就是說網站使用推薦系統的目的除了滿足用戶發現內容的需求，同時也需要利用推薦系統加快實作商業上的指標，

1.2.3. 評判維度

增加評測維度的目的，就是知道一個演算法在什么情況下性能最好，這樣可以為融合不同推薦演算法取得最好的整體性能帶來參考，

一般評測維度分3種：

• 用戶維度：主要包括用戶的人口統計學資訊、活躍度以及是不是新用戶等；
• 物品維度：包括物品的屬性資訊、流行度、平均分以及是不是新加入的物品等；
• 時間維度：包括季節，是作業榷訓是周末，白天還是晚上等；

如果推薦系統的評測報告中包含了不同維度下的系統評測結果，就能幫我們全面了解系統性能，甚至找到一個看上去比較弱的演算法的優勢，或者發現一個看上去比較強的演算法的缺點，

2. 資料來源

2.1. 用戶行為資料

基于用戶行為資料獲取資料也就是通過用戶曾經進行過的行為來了解用戶興趣和需求，

用戶行為資料一般存于網站的日志中，網站在運行程序中都產生大量原始日志(Raw Log)，多種原始日志可以按照用戶行為匯總成會話日志(Session Log)，其中每個會話表示一次用戶行為及其對應的服務，

下面給出一種用戶行為的統一表示，可以作為資料庫設計的參考：

欄位	含義
user id	產生行為的用戶的唯一標識
item id	產生行為的物件的唯一標識
behavior type	行為的種類（比如是購買還是瀏覽）
context	產生行為的背景關系，包括時間和地點等
behavior weight	行為的權重（如果是觀看視頻的行為，那么這個權重可以是觀看時長；如果是打分行為，這個權重可以是分數）
behavior content	行為的內容（如果是評論行為，那么就是評論的文本；如果是打標簽的行為，就是標簽）

用戶行為在個性化推薦系統中一般分兩種：

• 顯性反饋行為（Explicit Feedback）
  顯性反饋行為包括用戶明確表示對物品喜好的行為，例如用戶評分、點贊之類的用戶表態；
• 隱性反饋行為（Implicit Feedback）
  隱性反饋行為指的是那些不能明確反應用戶喜好的行為，最具代表性的隱性反饋行為就是頁面瀏覽行為，用戶進行瀏覽既可能是對該頁面的內容感興趣，也可能是誤操作，

我們從幾個不同方面來比較顯性反饋資料和隱性反饋資料：

	顯性反饋資料	隱性反饋資料
用戶興趣	明確	不明確
數量	較少	龐大
存盤	資料庫	分布式檔案系統
實時讀取	實時	有延遲
正負反饋	都有	只有正反饋

下標列舉了在各個領域的網站中這顯性反饋資料和隱性反饋資料的例子：

	顯性反饋資料	隱性反饋資料
視頻網站	用戶對視頻的評分	用戶觀看視頻的日志、瀏覽視頻頁面的日志
電子商務網站	用戶對商品的評分	購買日志、瀏覽日志
門戶網站	用戶對新聞的評分	閱讀新聞的日志
音樂網站	用戶對音樂/歌手/專輯的評分	聽歌的日志

在很多時候我們并不使用統一結構表示所有行為，因為使用統一的結構會造成很大的空間浪費，一般來說，會用不同的資料集包含不同的行為，目前比較有代表性的資料集有下面幾個：

• 無背景關系資訊的隱性反饋資料集
  每一條行為記錄僅僅包含用戶ID和物品ID，Book-Crossing 就是這種型別的資料集；
• 無背景關系資訊的顯性反饋資料集
  每一條記錄包含用戶ID、物品ID和用戶對物品的評分；
• 有背景關系資訊的隱性反饋資料集
  每一條記錄包含用戶ID、物品ID和用戶對物品產生行為的時間戳，Lastfm資料集 就是這種型別的資料集；
• 有背景關系資訊的顯性反饋資料集
  每一條記錄包含用戶ID、物品ID、用戶對物品的評分和評分行為發生的時間戳，Netflix Prize 提供的就是這種型別的資料集，

2.2. 用戶標簽資料

標簽是一種重要的特征表現方式，用戶用標簽來描述對物品的看法，可以說標簽是聯系用戶和物品的紐帶，也是反應用戶興趣的重要資料源，

根據給物品打標簽的人的不同，標簽應用一般分為兩種：一種是讓作者或者專家給物品打標簽；另一種是讓普通用戶給物品打標簽，也就是UGC(User Generated Content，用戶生成的內容)的標簽應用，

標簽系統中的推薦問題主要有以下兩個：

• 如何利用用戶打標簽的行為為其推薦物品（基于標簽的推薦）
• 如何在用戶給物品打標簽時為其推薦適合該物品的標簽（推薦標簽）

為了研究上面的兩個問題，我們首先需要理解下面三個問題：

• 用戶為什么要打標簽
  用戶標注的動機一是便于上傳者組織自己的資訊，同時幫助其他用戶找到資訊；二是可以更好地組織內容，方便用戶將來的查找，同時可以傳達某些資訊，比如照片的拍攝時間和地點等；
• 用戶是如何打標簽的
  用戶打標簽的行為也具有長尾分布的特點，即只使用少數常用標簽、只給少數熱門物品打標簽；
• 用戶打什么樣的標簽
  不同的系統有不同的標簽系統，通常需要專家去定義一些標簽給用戶使用，否則用戶很可能會給物品打上各種各樣奇奇怪怪的標簽，Delicious上的一種經典標簽系統可以表示如下：
  1. 表明物品是什么，比如是一只鳥，就會有“鳥”這個詞的標簽；是豆瓣的首頁，就有一個標簽叫“豆瓣”；是喬布斯的首頁，就會有個標簽叫“喬布斯”，
  2. 表明物品的種類，比如表示一個網頁類別的標簽包括 article（文章）、blog（博客）、book（圖書）等，
  3. 表明誰擁有物品，比如很多博客的標簽中會包括博客的作者等資訊，
  4. 表達用戶的觀點，比如用戶認為網頁很有趣，就會打上標簽funny（有趣），認為很無聊，就會打上標簽boring（無聊），
  5. 用戶相關的標簽，比如 my favorite（我最喜歡的）、my comment（我的評論）等，
  6. 用戶的任務，比如 to read（即將閱讀）、job search（找作業）等，

2.3. 背景關系資訊

背景關系資訊是指用戶訪問推薦系統的時間、地點、心情等，對于提高推薦系統的推薦準確度是非常重要的，比如，一個賣衣服的推薦系統在冬天和夏天應該給用戶推薦不同種類的服裝，推薦系統不能因為用戶在夏天喜歡過某件T恤，就在冬天也給該用戶推薦類似的T恤，因此，準確了解用戶的背景關系資訊，并將該資訊應用于推薦演算法是設計好的推薦系統的關鍵，

總的來說，一般在推薦系統中我們會主要利用用戶的時間背景關系資訊和位置背景關系資訊，

2.3.1. 時間背景關系資訊

一般認為，時間資訊對用戶興趣的影響表現在以下幾個方面：

• 用戶興趣變化
  用戶興趣變化是因為用戶自身原因發生的變化，比如隨著時間的推移，用戶半年前喜歡看番劇，現在喜歡看文藝片，要準確預測用戶現在的興趣，就應該關注用戶最近的行為，因為用戶最近的行為最能體現他現在的興趣，當然，考慮用戶最近的興趣只能針對漸變的用戶興趣，而對突變的用戶興趣很難起作用；
• 物品生命周期
  當我們決定在某個時刻給某個用戶推薦某個物品時，需要考慮該物品在該時刻是否已經過時了，典型的短生命周期物品有新聞、直播等；
• 季節效應
  季節效應主要反映了時間本身對用戶興趣的影響，比如人們夏天吃冰淇淋，冬天吃火鍋，夏天穿T恤，冬天穿棉衣，以及不同節假日的商品規律等等，

在給定時間資訊后，推薦系統從一個靜態系統變成了一個時變的系統，而用戶行為資料也變成了時間序列，包含時間資訊的用戶行為資料集由一系列三元組構成，其中每個三元組 ( u , i , t ) (u,i,t) (u,i,t) 代表了用戶 u u u 在時刻 t t t 對物品 i i i 產生過行為，在給定資料集后，通過統計如下資訊研究系統的時間特性：

• 資料集每天獨立用戶數的增長情況
  有些網站處于快速增長期，它們每天的獨立用戶數都在線性（甚至呈指數級）增加，而有些網站處于平穩期，每天的獨立用戶數都比較平穩，還有一些網站處于衰落期，每天的用戶都在流失，在3種不同的系統中用戶行為是不一樣的；
• 系統的物品變化情況
  比如新聞網站，每天都會出現大量新的新聞，而每條熱門的新聞其時間周期都不會太長，今天熱門的新聞也許明天就被人忘記了；
• 用戶訪問情況
  有些網站用戶來一次就永遠不來了，有些網站用戶每周來一次，而有些網站用戶每天都來，為了度量這些特性，我們可以統計用戶的平均活躍天數，同時也可以統計相隔 T T T天來系統的用戶的重合度，

2.3.2. 地點背景關系資訊

除了時間，地點作為一種重要的空間特征，也是一種重要的背景關系資訊，不同地區的用戶興趣有所不同，用戶到了不同的地方，興趣也會有所不同，

用戶興趣和地點相關的特征主要有兩個：

• 興趣本地化
  不同地方的用戶興趣存在著很大的差別，不同國家和地區用戶的興趣存在著一定的差異，
• 活動本地化
  一個用戶在一段時間內往往只能在附近的地區活動，因此，在基于位置的推薦中我們需要考慮推薦地點和用戶當前地點的距離，不能給用戶推薦太遠的地方，

2.4. 社交網路資料

社交網路可以很好地模擬現實社會，在社交網路中的用戶通常相互認識，這大大提高了推薦的信任度，同時也緩解了推薦系統冷啟動的問題，

不過，社會化推薦有一些明顯的缺點，其中最主要的就是很多時候并不一定能提高推薦演算法的離線精度（準確率和召回率），特別是在基于社交圖譜資料的推薦系統中，因為用戶的好友關系不是基于共同興趣產生的，所以用戶好友的興趣往往和用戶的興趣并不一致，比如，我們和自己父母的興趣往往就差別很大，

現在互聯網上充斥著各種各樣帶有社交性質的網站，那么，從什么方面可以獲得社交網路資料呢？一般來說，有如下渠道：

• 電子郵件
  電子郵件其實也是一個社交網路，可以通過分析用戶的聯系人串列了解用戶的好友資訊，進一步通過研究兩個用戶之間的郵件往來頻繁程度度量兩個用戶的熟悉程度，
• 用戶注冊資訊
  在注冊時引導用戶填寫一些諸如公司、學校等資訊，就樣就可以知道哪些用戶曾經在同一家公司作業過，哪些用戶曾經在同一個學校學習過，
• 用戶的位置資料
  位置資訊也是一種反映用戶社交關系的資料，在同一地點的用戶更容易有相似的興趣，甚至這些用戶相互之間就認識，
• 論壇和討論組
  每個群聊或小組都包含一些有相同興趣的人，如果兩個用戶同時加入了很多相同的小組，我們可以認為這兩個用戶很可能互相了解或者具有相似的興趣，如果兩個用戶在討論組中曾經就某一個帖子共同進行過討論，那就更加說明他們之間的熟悉程度或興趣相似度很高，
• 即時聊天工具
  和電子郵件系統一樣，用戶在即時聊天工具上也會有一個聯系人串列，而且往往還會給聯系人進行分組，通過這個串列和分組資訊，我們就可以知道用戶的社交網路關系，而通過統計用戶之間聊天的頻繁程度，可以度量出用戶之間的熟悉程度，
• 社交網站
  社交網站是研究用戶關系的絕佳地點，例如Facebook中的絕大多數用戶聯系基于社交圖譜：由人們之間的親屬關系、作業關系而形成；Twitter中的絕大多數用戶聯系基于興趣圖譜：通過人們之間的共同興趣和信念形成，

社交網路定義了用戶之間的聯系，我們通常用圖描述社交網路，一般來說，有3種不同的社交網路資料：

• 雙向確認的社交網路資料
  以Facebook和人人網為代表，用戶之間形成好友關系需要通過雙方的確認；
• 單向關注的社交網路資料
  以Twitter和新浪微博為代表，用戶A可以關注用戶B，而不用得到用戶B的允許；
• 基于社區的社交網路資料
  用戶之間并沒有明確的關系，但同在一個社區，比如豆瓣小組，屬于同一個小組可能代表了用戶興趣的相似性；

3. 通用推薦模型

3.1. 協同過濾推薦

3.1.1. 基于鄰域的模型

基于鄰域的演算法分為兩大類，一類是基于用戶的協同過濾演算法，另一類是基于物品的協同過濾演算法，

（1）基于用戶的協同過濾演算法 UserCF

在一個在線個性化推薦系統中，當一個用戶A需要個性化推薦時，可以先找到和A有相似興趣的其他用戶，然后把那些用戶喜歡的、而用戶A沒有關注過的物品推薦給A，這種方法稱為基于用戶的協同過濾演算法（UserCF），

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

• 找到和目標用戶興趣相似的用戶集合
• 找到這個集合中的用戶喜歡的，且目標用戶沒有聽說過的物品，推薦給目標用戶

演算法的關鍵是計算兩個用戶的興趣相似度，協同過濾演算法主要利用用戶興趣串列的相似度計算用戶興趣的相似度，給定用戶 u u u、 v v v，令 N ( u ) N(u) N(u) 表示用戶 u u u 曾經有過興趣的物品集合， N ( v ) N(v) N(v) 表示用戶 v v v 曾經有過興趣的物品集合，

計算用戶興趣相似度的方法有3種：

• Jaccard公式 w u v = ∣ N ( u ) ∩ N ( v ) ∣ ∣ N ( u ) ∪ N ( v ) ∣ w_{uv}=\frac{|N(u)\cap N(v)|}{|N(u)\cup N(v)|} wuv?=∣N(u)∪N(v)∣∣N(u)∩N(v)∣?
• 余弦相似性 w u v = ∣ N ( u ) ∩ N ( v ) ∣ ∣ N ( u ) ∣ ∣ N ( v ) ∣ w_{uv}=\frac{|N(u)\cap N(v)|}{\sqrt{|N(u)||N(v)|}} wuv?=∣N(u)∣∣N(v)∣ ?∣N(u)∩N(v)∣?
• 改進的余弦相似性 w u v = ∑ i ∈ N ( u ) ∩ N ( v ) 1 log ? ( 1 + ∣ N ( i ) ∣ ) ∣ N ( u ) ∣ ∣ N ( v ) ∣ w_{uv}=\frac{\sum_{i\in N(u)\cap N(v)}\frac{1}{\log(1+|N(i)|)}}{\sqrt{|N(u)||N(v)|}} wuv?=∣N(u)∣∣N(v)∣ ?∑i∈N(u)∩N(v)?log(1+∣N(i)∣)1??其中 1 log ? ( 1 + ∣ N ( i ) ∣ ) \frac{1}{\log(1+|N(i)|)} log(1+∣N(i)∣)1?降低了用戶 u u u和用戶 v v v的共同興趣串列中熱門物品對用戶相似度的影響

得到了用戶之間的興趣相似度之后，就要將用戶興趣串列轉換為“物品-用戶”倒排表，即對每個物品建立一個喜歡它的用戶的串列，以此來給用戶推薦與他興趣最相似的 K K K個用戶喜歡的物品，如下的公式度量了UserCF演算法中用戶 u u u對物品 i i i的感興趣程度： p ( u , i ) = ∑ v ∈ S ( u , K ) ∩ N ( i ) w u v r v i p(u,i)=\sum_{v\in S(u,K)\cap N(i)}w_{uv}r_{vi} p(u,i)=v∈S(u,K)∩N(i)∑?wuv?rvi?其中 S ( u , K ) S(u,K) S(u,K)包含和用戶 u u u興趣最接近的 K K K個用戶， N ( i ) N(i) N(i)是對物品 i i i有過行為的用戶集合， w u v w_{uv} wuv?是用戶 u u u和用戶 v v v的興趣相似度， r v i r_{vi} rvi?代表用戶 v v v對物品 i i i的興趣，一般情況下，如果使用的是單一行為的隱反饋資料，那所有的 r v i = 1 r_{vi}=1 rvi?=1，

例如用戶 A A A、 B B B、 C C C、 D D D和物品 a a a、 b b b、 c c c、 d d d、 e e e有如下用戶興趣串列：

用戶	興趣物品串列
A A A	a a a、 b b b、 d d d
B B B	a a a、 c c c
C C C	b b b、 e e e
D D D	c c c、 d d d、 e e e

用余弦相似度計算用戶興趣相似度：
w A B = ∣ { a , b , d } ∩ { a , c } ∣ ∣ { a , b , d } ∣ ∣ { a , c } ∣ = 1 6 w_{AB}=\frac{|\{a,b,d\}\cap \{a,c\}|}{\sqrt{|\{a,b,d\}||\{a,c\}|}}=\frac{1}{\sqrt{6}} wAB?=∣{a,b,d}∣∣{a,c}∣ ?∣{a,b,d}∩{a,c}∣?=6 ?1?

w A C = ∣ { a , b , d } ∩ { b , e } ∣ ∣ { a , b , d } ∣ ∣ { b , e } ∣ = 1 6 w_{AC}=\frac{|\{a,b,d\}\cap \{b,e\}|}{\sqrt{|\{a,b,d\}||\{b,e\}|}}=\frac{1}{\sqrt{6}} wAC?=∣{a,b,d}∣∣{b,e}∣ ?∣{a,b,d}∩{b,e}∣?=6 ?1?

w A D = ∣ { a , b , d } ∩ { c , d , e } ∣ ∣ { a , b , d } ∣ ∣ { c , d , e } ∣ = 1 3 w_{AD}=\frac{|\{a,b,d\}\cap \{c,d,e\}|}{\sqrt{|\{a,b,d\}||\{c,d,e\}|}}=\frac{1}{3} wAD?=∣{a,b,d}∣∣{c,d,e}∣ ?∣{a,b,d}∩{c,d,e}∣?=31?

通過比較我們可以知道用戶 A A A與用戶 D D D的興趣相似度最高，所以我們從用戶 D D D的興趣串列中選取物品推薦給用戶 A A A，此時我們需要計算用戶 A A A與用戶 D D D興趣串列中的物品的感興趣程度，首先建立“物品-用戶”倒排表：

物品	喜歡該物品的用戶
a a a	A A A、 B B B
b b b	A A A、 C C C
b b b	B B B、 D D D
d d d	A A A、 D D D
e e e	C C C、 D D D

從倒排表我們可以看出，用戶 A A A的興趣物品 a a a、 b b b、 d d d 在用戶 B B B、 C C C、 D D D 中分別有分布，所以可以計算用戶 A A A 與用戶 B B B、 C C C、 D D D 的興趣串列中物品的感興趣程度，所以這里取 K = 3 K=3 K=3： p ( A , c ) = w A B + w A D = 0.7416 p(A,c)=w_{AB}+w_{AD}=0.7416 p(A,c)=wAB?+wAD?=0.7416

p ( A , e ) = w A C + w A D = 0.7416 p(A,e)=w_{AC}+w_{AD}=0.7416 p(A,e)=wAC?+wAD?=0.7416

根據計算結果，我們可以知道用戶 A A A 對物品 c c c、 e e e 的興趣一致，因此我們可以任意推薦他們其中一個，或者一起推薦給用戶 A A A，需要注意的是我們沒有計算 p ( A , a ) p(A,a) p(A,a)、 p ( A , b ) p(A,b) p(A,b)、 p ( A , d ) p(A,d) p(A,d)，這是因為物品 a a a、 b b b、 d d d 已經在用戶 A A A 的興趣串列中了，所以沒必要再推薦，

（2）基于物品的協同過濾演算法 ItemCF

基于物品的協同過濾演算法用于給用戶推薦那些與他們之前喜歡的物品相似的物品，

ItemCF演算法主要通過分析用戶的行為記錄來計算物品之間的相似度，該演算法認為，物品A和物品B具有很大的相似度是因為喜歡物品A的用戶大都也喜歡物品B，

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

1. 計算物品之間的相似度；
2. 根據物品的相似度和用戶的歷史行為給用戶生成推薦串列，

我們給定物品 i i i、 j j j，設 N ( i ) N(i) N(i)為喜歡物品 i i i的用戶數， N ( j ) N(j) N(j)為喜歡物品 j j j的用戶數，則物品 i i i、 j j j的相似度可以表達為：

• Jaccard公式 w i j = ∣ N ( i ) ∩ N ( j ) ∣ ∣ N ( i ) ∣ w_{ij}=\frac{|N(i)\cap N(j)|}{|N(i)|} wij?=∣N(i)∣∣N(i)∩N(j)∣?上述公式可以理解為喜歡物品 i i i 的用戶中有多少比例的用戶也喜歡物品 j j j
• 余弦相似性 w i j = ∣ N ( i ) ∩ N ( j ) ∣ ∣ N ( i ) ∣ ∣ N ( j ) ∣ w_{ij}=\frac{|N(i)\cap N(j)|}{\sqrt{|N(i)||N(j)|}} wij?=∣N(i)∣∣N(j)∣ ?∣N(i)∩N(j)∣?該公式降低了熱門物品會和很多物品相似的可能性，可以避免推薦出熱門的物品，
• 改進的余弦相似性 w i j = ∑ u ∈ N ( i ) ∩ N ( j ) 1 log ? ( 1 + ∣ N ( u ) ∣ ) ∣ N ( i ) ∣ ∣ N ( j ) ∣ w_{ij}=\frac{\sum_{u\in N(i)\cap N(j)}\frac{1}{\log(1+|N(u)|)}}{\sqrt{|N(i)||N(j)|}} wij?=∣N(i)∣∣N(j)∣ ?∑u∈N(i)∩N(j)?log(1+∣N(u)∣)1??其中 1 log ? ( 1 + ∣ N ( i ) ∣ ) \frac{1}{\log(1+|N(i)|)} log(1+∣N(i)∣)1?對余弦相似性進行了修正，使得活躍用戶對物品相似度的貢獻大于不活躍的用戶，

提一句，如果將ItemCF的相似度矩陣 w w w 按最大值歸一化，可以提高推薦的準確率，歸一化公式如下： w i j ′ = w i j max ? j w i j w_{ij}'=\frac{w_{ij}}{\max_{j}w_{ij}} wij′?=maxj?wij?wij??

在ItemCF中，兩個物品之所以產生相似度是因為它們共同被很多用戶喜歡，即每個用戶都可以通過他們的歷史興趣串列給物品“貢獻”相似度，也就是說，在得到物品之間的相似度后，我們可以建立一個“用戶-物品”倒排表，即對每個用戶建立一個包含他喜歡的物品的串列，

然后通過如下公式計算用戶 u u u對一個物品 j j j的興趣度： p u j = ∑ i ∈ N ( u ) ∩ S ( j , K ) w j i r u i p_{uj}=\sum_{i\in N(u)\cap S(j,K)}w_{ji}r_{ui} puj?=i∈N(u)∩S(j,K)∑?wji?rui?

這里 N ( u ) N(u) N(u)是用戶喜歡的物品的集合， S ( j , K ) S(j,K) S(j,K)是和物品 j j j最相似的 K K K個物品的集合， w j i w_{ji} wji?是物品 j j j和 i i i的相似度， r u i r_{ui} rui?是用戶 u u u對物品i的興趣（如果用戶 u u u對物品 i i i有過行為，即可令 r u i = 1 r_{ui}=1 rui?=1），該公式的含義是，與用戶歷史上感興趣的物品越相似的物品，越有可能是用戶感興趣的物品，

ItemCF的推薦程序可以用如下例子來表示：
假設已知用戶對兩個物品 A 1 A_1 A1?、 A 2 A_2 A2?的興趣度分別為1.3、0.9，現有5個用戶未曾見過的新物品，它們與物品 A 1 A_1 A1?、 A 2 A_2 A2?的相似度可以表示為：

物品	與物品 A 1 A_1 A1?的相似度	與物品 A 2 A_2 A2?的相似度
B 1 B_1 B1?	0.7	0
B 2 B_2 B2?	0.4	0.5
B 3 B_3 B3?	0	0.5
B 4 B_4 B4?	0.6	0
B 5 B_5 B5?	0	0.6

可得，用戶對 B 1 B_1 B1?、 B 2 B_2 B2?、 B 3 B_3 B3?、 B 4 B_4 B4?、 B 5 B_5 B5?的興趣度分別為：
p u B 1 = 1.3 ? 0.7 = 0.91 p_{uB_1}=1.3*0.7=0.91 puB1??=1.3?0.7=0.91

p u B 2 = 1.3 ? 0.4 + 0.9 ? 0.5 = 0.97 p_{uB_2}=1.3*0.4+0.9*0.5=0.97 puB2??=1.3?0.4+0.9?0.5=0.97

p u B 3 = 0.9 ? 0.5 = 0.45 p_{uB_3}=0.9*0.5=0.45 puB3??=0.9?0.5=0.45

p u B 4 = 1.3 ? 0.6 = 0.78 p_{uB_4}=1.3*0.6=0.78 puB4??=1.3?0.6=0.78

p u B 5 = 0.9 ? 0.6 = 0.54 p_{uB_5}=0.9*0.6=0.54 puB5??=0.9?0.6=0.54

由此我們可知，用戶可能對物品 B 2 B_2 B2?的興趣度最高，應該向用戶推薦物品 B 2 B_2 B2?

（3）UserCF 與 ItemCF 的區別

特性	UserCF	ItemCF
性能	適用于用戶數少于物品數的場合，如果用戶很多，計算用戶相似度矩陣代價很大	適用于物品數少于用戶數的場合，如果物品很多，計算物品相似度矩陣代價很大
領域	適用于時效性較強，用戶個性化興趣不太明顯的領域	適用于長尾物品豐富，用戶個性化需求強烈的領域
實時性	用戶有新行為，不一定造成推薦結果的立即變化	用戶有新行為，一定會導致推薦結果的實時變化
冷啟動	無法給新用戶和物品進行準確推薦	新用戶只要對一個物品產生行為，就可以給他推薦和該物品相關的其他物品
推薦解釋	很難提供令用戶信服的推薦解釋	可以利用用戶的歷史行為給用戶做推薦解釋

3.1.2. 隱語意模型

LFM（Latent Factor Model）隱語意模型的核心思想是通過隱含特征(Latent Factor)聯系用戶興趣和物品，它采取基于用戶行為統計的自動聚類，讓用戶和物品的分類自動化，

LFM通過如下公式計算用戶u對物品i的興趣： P r e f e r e n c e ( u , i ) = r u i = p u T q i = ∑ f = 1 F p u , k q i , k Preference(u,i)=r_{ui}=p_u^Tq_i=\sum_{f=1}^{F}p_{u,k}q_{i,k} Preference(u,i)=rui?=puT?qi?=f=1∑F?pu,k?qi,k?

其中 , p u , k p_{u,k} pu,k?度量了用戶 u u u的興趣和第 k k k個隱類的關系，而 q i , k q_{i,k} qi,k?度量了物品 i i i和第 k k k個隱類之間的關系，

推薦系統的用戶行為樣本分為正樣本（用戶喜歡什么物品）和負樣本（用戶對什么物品不感興趣），經過對正負樣本的采樣，可以得到一個用戶—物品集 K = { ( u , i ) } K=\{(u,i)\} K={(u,i)}，其中如果 ( u , i ) (u,i) (u,i)是正樣本，則有 r u i = 1 r_{ui}=1 rui?=1，否則 r u i = 0 r_{ui}=0 rui?=0，然后，通過隨機梯度下降法優化如下的損失函式來找到最合適的引數 p p p 和 q q q： C = ∑ ( u , i ) ∈ K ( r u i ? r ^ u i ) = ∑ ( u , i ) ∈ K ( r u i ? ∑ k = 1 K p u , k q i , k ) + λ ∥ p u ∥ 2 + λ ∥ q i ∥ 2 C=\sum_{(u,i)\in K}(r_{ui}-\hat{r}_{ui})=\sum_{(u,i)\in K}\Bigl(r_{ui}-\sum_{k=1}^{K}p_{u,k}q_{i,k}\Bigr)+\lambda\Vert p_u\Vert^2+\lambda\Vert q_i\Vert^2 C=(u,i)∈K∑?(rui??r^ui?)=(u,i)∈K∑?(rui??k=1∑K?pu,k?qi,k?)+λ∥pu?∥2+λ∥qi?∥2其中， λ ∥ p u ∥ 2 + λ ∥ q i ∥ 2 \lambda\Vert p_u\Vert^2+\lambda\Vert q_i\Vert^2 λ∥pu?∥2+λ∥qi?∥2是用來防止過擬合的正則化項， λ \lambda λ可以通過實驗獲得，

隨機梯度下降法需要首先對引數 p u , k p_{u,k} pu,k? 和 q i , k q_{i,k} qi,k? 分別求偏導數：
? C ? p u , k = ? 2 q i , k + 2 λ p u , k \frac{\partial C}{\partial p_{u,k}}=-2q_{i,k}+2\lambda p_{u,k} ?pu,k??C?=?2qi,k?+2λpu,k?

? C ? q i , k = ? 2 p u , k + 2 λ q i , k \frac{\partial C}{\partial q_{i,k}}=-2p_{u,k}+2\lambda q_{i,k} ?qi,k??C?=?2pu,k?+2λqi,k?

然后這兩個引數沿著方向導數前進，得到如下遞推公式：
p u , k = p u , k + α ( q i , k ? λ p u , k ) p_{u,k}=p_{u,k}+\alpha(q_{i,k}-\lambda p_{u,k}) pu,k?=pu,k?+α(qi,k??λpu,k?)

q i , k = q i , k + α ( p u , k ? λ q i , k ) q_{i,k}=q_{i,k}+\alpha(p_{u,k}-\lambda q_{i,k}) qi,k?=qi,k?+α(pu,k??λqi,k?)其中， α \alpha α指學習速率（Learning Rate），是一個可調引數，

LFM和基于領域的方法區別大致如下：

特性	LFM	基于鄰域
理論基礎	基于機器學習，理論基礎好，可以優化引數建立最優模型	基于統計的方法，沒有學習程序
離線計算的空間復雜度	O ( F ? ( M + N ) ) O(F*(M+N)) O(F?(M+N))，其中 F F F指隱類的個數， M M M指用戶數， N N N指物品數	UserCF: O ( M ? M ) O(M*M) O(M?M)，ItemCF: O ( N ? N ) O(N*N) O(N?N)，其中 M M M指用戶數， N N N指物品數
離線計算的時間復雜度	O ( K ? F ? S ) O(K*F*S) O(K?F?S)，其中 F F F指隱類的個數， S S S指迭代次數	UserCF: O ( N ? ( K / N ) 2 ) O(N*(K/N)^2) O(N?(K/N)2)，ItemCF: O ( M ? ( K / M ) 2 ) O(M*(K/M)^2) O(M?(K/M)2)，其中 M M M指用戶數， N N N指物品數， K K K指用戶對物品行為記錄的總數
在線實時推薦	不能實時推薦，不適用于物品數量龐大的系統	可以實時推薦
推薦解釋	解釋性不強	解釋性好

3.1.3. 基于圖的模型

用戶對物品的行為很容易用二分圖表示，已知用戶行為資料是由一系列二元組組成的，其中每個二元組 ( u , i ) (u, i) (u,i)表示用戶 u u u對物品 i i i產生過行為，這樣的資料可以用二分圖 G ( V , E ) G(V,E) G(V,E)表示，其中 V = V U ∪ V I V=V_U\cup V_I V=VU?∪VI? 由用戶頂點集合 V U V_U VU?和物品頂點集合 V I V_I VI?組成，

對于資料集中的每一個二元組 ( u , i ) (u,i) (u,i)，都有一套對應的邊 e ( v u , v i ) e(v_u,v_i) e(vu?,vi?)，其中 v u ∈ V U v_u\in V_U vu?∈VU?是用戶 u u u對應的頂點， v i ∈ V I v_i\in V_I vi?∈VI?是物品 i i i對應的頂點，如下表和圖所示：

用戶	興趣物品串列
A A A	a a a、 b b b、 d d d
B B B	a a a、 c c c
C C C	b b b、 e e e
D D D	c c c、 d d d、 e e e

表示為二分圖：

可以看到在上圖中，圓形結點為一個分割，矩形結點為另一個分割，

要將個性化推薦演算法放到二分圖模型上，那么給用戶 u u u推薦物品的任務就可以轉化為度量用戶頂點 v u v_u vu?與 v u v_u vu?沒有邊直接相連的物品節點在圖上的相關性，相關性越高的物品在推薦串列中的權重就越高，

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

• 兩個頂點之間有很多路徑相連；
• 鏈接兩個頂點之間的路徑長度都比較短；
• 鏈接兩個頂點之間的路徑不會經過出度比較大的頂點，

基于上面3個主要因素，研究人員設計了很多計算圖中頂點之間相關性的方法，這里講解基于隨機游走的PageRank和PersonalRank演算法，

（1）PageRank演算法

PageRank是用來衡量特定網頁相對于搜索引擎中其他網頁的重要性的演算法，其計算結果作為Google搜索結果中網頁排名的重要指標，

網頁之間通過超鏈接相互連接，互聯網上不計其數的網頁就構成了一張超大的圖，PageRank假設用戶從所有網頁中隨機選擇一個網頁進行瀏覽，然后通過超鏈接在網頁直接不斷跳轉，到達每個網頁后，用戶有兩種選擇：到此結束或者繼續選擇一個鏈接瀏覽，

設用戶繼續瀏覽的概率為 α \alpha α，用戶以相等的概率在當前頁面的所有超鏈接中隨機選擇一個繼續瀏覽，當經過很多次這樣的隨機游走之后，每個網頁被訪問用戶訪問到的概率就會收斂到一個穩定值，

演算法迭代關系式如下所示： P R ( v ) = 1 ? α N + α ∑ v ′ ∈ i n ( v ) P R ( v ′ ) ∣ o u t ( v ′ ) ∣ PR(v)=\frac{1-\alpha}{N}+\alpha\sum_{v'\in in(v)}\frac{PR(v')}{|out(v')|} PR(v)=N1?α?+αv′∈in(v)∑?∣out(v′)∣PR(v′)?

其中 P R ( v ) PR(v) PR(v)是網頁 v v v被訪問的概率（也就是重要性程度）， α \alpha α是用戶繼續訪問網頁的概率， N N N是網頁總數， i n ( v ) in(v) in(v)表示指向網頁 v v v的網頁集合（入度）， o u t ( v ′ ) out(v') out(v′)表示網頁 v ′ v' v′指向的網頁集合（出度），

將網頁替換為其他物品同理，

（2）PersonalRank演算法

PersonalRank跟PageRank的區別只在于每一步概率的取值不一樣，PersonalRank用 r v r_v rv?替換了 1 / N 1/N 1/N，也就是說PersonalRank走到任意的下一個節點的概率服從均勻分布，

公式表達為： P R ( v ) = ( 1 ? α ) r v + α ∑ v ′ ∈ i n ( v ) P R ( v ′ ) ∣ o u t ( v ′ ) ∣ PR(v)=(1-\alpha)r_v+\alpha\sum_{v'\in in(v)}\frac{PR(v')}{|out(v')|} PR(v)=(1?α)rv?+αv′∈in(v)∑?∣out(v′)∣PR(v′)?其中 r v = { 1 , v = v u 0 , v ≠ v u r_v = \begin{cases} 1, & v=v_u \\ 0, & v\neq v_u \end{cases} rv?={1,0,?v=vu?v?=vu??， v u v_u vu?是指用戶 u u u對應的節點

為了PersonalRank的時間復雜度，可以從矩陣論出發重新設計演算法，

令 M M M為用戶物品二分圖的轉移概率矩陣，即： M ( v , v ′ ) = 1 ∣ o u t ( v ) ∣ M(v,v')=\frac{1}{|out(v)|} M(v,v′)=∣out(v)∣1?那么，迭代公式可以轉化為： r = ( 1 ? α ) r v + α M T r = ( 1 ? α ) ( 1 ? α M T ) ? 1 r v \begin{aligned} r & = (1-\alpha)r_v+\alpha M^Tr \\ & = (1-\alpha)(1-\alpha M^T)^{-1}r_v \\ \end{aligned} r?=(1?α)rv?+αMTr=(1?α)(1?αMT)?1rv??

用PersonalRank演算法對上面的示例中的用戶 A A A進行推薦，可得如下結果：

用戶 A A A 和物品 c c c、 e e e 沒有邊相連，但是用戶 A A A 和物品 c c c 有三條長度為 3 3 3 的路徑相連，用戶 A A A 和物品 e e e 有兩條長度為 3 3 3 的路徑相連，那么，頂點 A A A 與 e e e 之間的相關性就要高于頂點 A A A 與 c c c，因而物品 e e e 在用戶 A A A 的推薦串列中應該排在物品 c c c 之前，最終得出的推薦串列為 { c , e } \{c,e\} {c,e}

用戶 A A A與物品 c c c的路徑：

用戶 A A A與物品 e e e的路徑：