推薦系統(1)-概述

為了使推薦結果符合用戶口味，我們需要對用戶有深入的了解。用戶留下的文字和行為可以解釋。

2. 基于用戶行為數據的最典型應用是各種列表。這些列表是基于簡單的用戶行為統計數據，個性化的推薦算法是通過深入分析用戶行為來帶來更好的體驗。

3. 用戶行為不是隨機的，包含了許多模式。例如，通過對用戶購物車的分析，電子商務平臺發現了 購買A用戶購買商品B同時，在用戶瀏覽商品的同時A商品直接展示購買A 用戶購買的其他商品最著名的例子是啤酒和尿布的故事。

當當網在用戶瀏覽《數據挖掘導論》時，向用戶推薦購買本產品的客戶 還買了的書

4. 基于用戶行為分析的推薦算法稱為協同過濾算法。顧名思義，協同過濾是指用戶可以通過不斷與網站互動，不斷過濾自己不感興趣的物品，從而越來越滿足自己的需求。

5. 網站上用戶行為數據最簡單的存在形式是日志。網站在運行過程中產生了大量的原始日志 (raw log)，并將其存儲在文件系統中。許多互聯網業務根據用戶行為將各種原始日志匯總成會話日志(session log)，每次會話都表示用戶行為和相應的服務。這些日志記錄了用戶的各種行為。

6. 個性化推薦系統中的用戶行為一般分為兩種-顯性反饋行為(explicit feedback)和隱性反饋 行為(implicit feedback)。顯性反饋包括用戶明確表達對項目偏好的行為。

提供給用戶打分或贊/踩的功能，收集用戶喜好

7. 一個有趣的例子：YouTube最早是用5分評分系統 收集顯性反饋的，但后來他們的研究人員統計了不同評分的評分數1，結果發現，用戶最常用的評分是5分，其次是1分，其他的分數很少有用戶打。YouTube用戶主要關注視頻，所以他們只有在特別不滿意或特別滿意時才會得分，所以二級評分系統就足夠了。但如果它是一個評論網站，用戶主要關注評論，那么多級評分系統是必要的。

8. 與顯性反饋相對應的是隱性反饋。隱性反饋是指無法明確反映用戶偏好的行為。最具代表性的隱性反饋行為是頁面瀏覽行為。

網站顯性反饋數據和隱性反饋數據的例子

互聯網上有許多用戶行為，如瀏覽網頁、購買商品、評論、評分等。很難用一種統一的 來表達所有這些行為。下表給出了一種表達方式，將用戶行為表達為六部分，即用戶和行為對象、行為類型、上下文、內容和權重。

統一表達用戶行為

9. 一般來說，不同的數據集包含不同的行為：

無上下文信息的隱性反饋數據集 每個行為記錄僅包括用戶ID和物品ID。顯性反饋數據集 每個記錄包含用戶ID、物品ID以及用戶對項目的評分。每個記錄都包括用戶對上下文信息的隱藏反饋數據集 ID、物品ID時間戳用戶對物品的行為。上下文信息的顯性反饋數據集 ID、物品ID、用戶對物品進行評分和評分的時間戳。

10. 用戶活動和商品流行的分布

互聯網上的許多數據分布都被稱為Power Law在互聯網領域，這種分布也被稱為長尾分布。

橫坐標是物品的流行程度K，縱坐標很受歡迎K的物品的總數。

11. 用戶活動與商品流行的關系

新用戶傾向于瀏覽熱門物品，因為他們不熟悉網站，只能點擊主頁上的熱門物品，而老用戶會逐漸開始瀏覽熱門物品。

圖中曲線呈明顯下降趨勢，表明用戶越活躍，越傾向于瀏覽不受歡迎的物品。

12. 基于用戶行為數據設計的推薦算法通常被稱為協同過濾算法。學術界深入研究了協同過濾算法 ，并提出了許多方法，如基于鄰域的方法(neighborhood-based)、隱語義模型 (latent factor model)、基于圖的隨機游走算法(random walk on graph)等等。在這些方法中，最著名、最廣泛應用于行業的算法是基于鄰域的方法。

13. 推薦算法評價指標：

對用戶u推薦N物品(記為R(u))，令用戶u在測試集上喜歡的物品 ** 為T(u)，然后通過 過準確率/召回率來評估推薦算法的精度:

   召回率：

精度：

覆蓋率: (覆蓋率反映了發掘長尾的能力。覆蓋率越高，推薦算法越能向用戶推薦長尾項目。

例:一個數據庫有500個文檔，其中50個符合定義。系統檢索到75個文檔，但實際上只有45個符合定義。在500個文檔中，系統可以檢索到460個文檔。

召回率：Recall = 45/50 = 90%

精度：Precision = 45/75 = 60%

覆蓋率：Coverage = 460 / 500 = 92%

14. 基于鄰域的方法主要包括兩種算法：

基于用戶的協同過濾算法 向用戶推薦其他用戶喜歡的物品，這些物品與他的興趣相似。基于項目的協同過濾算法 向用戶推薦類似于他以前喜歡的項目的項目。

15. 基于用戶的協同過濾算法（UserCF）

當一個用戶A當你需要個性化的推薦時，你可以首先找到其他與他有類似興趣的用戶，然后找到用戶喜歡的用戶A推薦沒聽說過的物品A。

協同過濾算法主要包括兩個步驟：①找到與目標用戶興趣相似的用戶 ** 。②找到這個 ** 用戶喜歡的，目標用戶沒聽說過的推薦給目標用戶。

給定用戶u和用戶v，令N(u)表示用戶u曾經有過正反饋的物品 ** ，令N(v) 為用戶v曾經有過正反饋的物品 ** 。

通過Jaccard簡單計算公式u和v興趣相似性：

或計算余弦相似度：

案例：

例如用戶行為記錄

用戶A和用戶B的相似度為：

用戶A和用戶C相似度如下：

用戶A和用戶D相似度如下：

可見，用戶A和用戶D相似度最高。使用上述算法可以給用戶A推薦A對物品c、e沒有行為，所以你可以向用戶推薦這兩個項目A。

在獲得用戶之間的興趣相似性后，UserCF算 ** 向用戶推薦最類似他興趣的產品K 用戶喜歡的物品。測量了以下公式UserCF算法中用戶u對物品i感興趣：

   

其中，S(u,K)包含和用戶u最接近興趣的K個用戶，N(i)是對物品i有過行為的用戶 ** ， 是用戶u和用戶v 代表用戶的興趣相似性v對物品i的興趣，因為使用的是單一行為的隱反饋數 據，所以所有的 = 1。

選取K=3，用戶A對物品c、e沒有行為，所以你可以向用戶推薦這兩個項目A。根據UserCF算法，用戶A對物品c、e興趣是：

p(A,c) = = 0.7416

p(A,e) = = 0.7416

注意，參數K是UserCF其調整對推薦算法的各種指標都有一定的影響。

以MovieLens可以看出，推薦系統的精度指標(精度和召回率)與參數不符K成線性關系MovieLens數據集中，選擇K=80精度和召回率都比較高。因此，選擇合適的K對于獲得高推薦系統的精度更為重要。人氣 K越大則UserCF推薦結果越受歡迎。這是因為K決定了UserCF在向您推薦時，請參考其他與您感興趣相似的用戶的興趣。K越大，參考 的人越多，結果就越接近全球的熱門物品。在三個數據集中，可以看到覆蓋率 K越大則UserCF推薦結果的覆蓋率越低。由于流行程度的增加，覆蓋率的降低，UserCF越來越傾向于推薦熱門物品，從而對長尾物品的推薦越來越少，導致覆蓋率下降。

16. 用戶相似度計算的改進

首先，以圖書為例。如果兩個用戶都購買了新華字典，這并不意味著他們有相似的興趣，因為絕大多數中國人小時候都購買了新華字典。但是，如果兩個用戶都購買了數據挖掘導論， 可以認為他們的興趣相似，因為只有研究數據挖掘的人才會購買這本書。換句話說，兩個用戶對不受歡迎的物品采取了相同的行為，這表明了他們興趣的相似性。

因此，John S. Breese在論文1中提出 以下公式（UserCF-IIF），用戶興趣相似性按用戶行為計算：

UserCF和UserCF-IIF各種性能對比

UserCF-IIF在各項性能上略優于UserCF。這表明，在計算用戶興趣相似性時，考慮 商品的流行程度確實有助于提高推薦結果的質量。

基于用戶協同過濾算法的缺點：① 隨著網站用戶數量的增加，計算用戶興趣相似性矩陣將變得越來越困難，其計算時間復雜性和空間復雜性的增加與用戶數量的增加相似。② 基于用戶的協同過濾很難解釋推薦結果。

17. 基于物體的協同過濾算法（ItemCF）

基于對象的協同過濾(item-based collaborative filtering)算法是目前業界應用最廣泛的算法。無論是亞馬遜，還是亞馬遜，Netflix、Hulu、YouTube，其推薦算法的基礎都是該算法。基于對象的協同過濾算法可以利用用戶的歷史行為給推薦結果提供推薦解釋，Hulu推薦使用個性化視頻 ItemCF為每個推薦結果提供推薦解釋，用于解釋的視頻是用戶之前觀看或收集的視頻。

Hulu個性化視頻推薦

協同過濾算法主要分為兩個步驟：①計算物體之間的相似性。②根據物品的相似性和用戶的歷史行為，向用戶生成推薦列表。

用以下公式定義項目的相似性：

分母|N(i)|是喜歡物品i而分子 N(i) N(j) 同時喜歡物品i和物品j用戶數。因此，上述公式可以理解為喜歡的物品i有多少用戶也喜歡商品？j。

雖然上面的公式看起來很有道理，但是有一個問題。假如物品j很受歡迎，很多人喜歡，所以 會很大，接近1。因此，該公式將導致任何項目與流行項目非常相似，這顯然不是致力于挖掘長尾信息的推薦系統的好特點。

為避免推薦流行物品，可使用以下公式：

該公式懲罰了物品j因此，它減輕了流行物品與許多物品相似的可能性。在協同過濾中，這兩個項目之所以相似，是因為它們共同受到許多用戶的喜愛，也就是說，每個用戶都可以通過他們的歷史興趣列表貢獻項目的相似性。

下圖最左邊是輸入用戶行為記錄，每行代表用戶感興趣的物品 ** 。然后，對于每一件物品 ** ，我們把里面的物體加成兩兩加一，得到一個矩陣。最后，將這些矩陣加到上面C矩陣。其中C[i][j]記錄同時喜歡的物品i 和物品j用戶數將C矩陣歸一化可以獲得物體之間的余弦相似度矩陣W。

   獲得物品之間的相似性后，ItemCF用戶通過以下公式計算u對一個物品j的興趣:

這里N(u) 是用戶喜歡的物品** ，S(j,K)是和物品j最相似的K個物品的 ** ， 是物品j和i 相似性， 是用戶u對物品i對隱反饋數據集的興趣u對物品i有過行為，就可以下令了=1。)該公式的含義是，與用戶歷史上感興趣的物品越相似，在用戶推薦列表中排名越高。

示例：

下圖是一個基于項目推薦的簡單例子。用戶喜歡這個例子《C Primer中文版和編程之美。ItemCF將為這兩本書找出最相似的三本書，然后根據公式的定義計算用戶對每本書的興趣。ItemCF因為這本書和《C Primer中文版相似，相似度為0.4，而且這本書和《編程之美》差不多，相似性是0.5。考慮到用戶是對的《C Primer中文版的興趣是1.3，對編程之美的興趣是0.9，那么用戶對算法導論的興趣就是1.3 × 0.4 0.9×0.5 = 0.97。

從這個例子可以看出，ItemCF一個優點是可以提供推薦解釋，即用戶歷史上喜歡的 項目來解釋當前的推薦結果。

MovieLens數據集中ItemCF結果精度(精度和召回率) ItemCF推薦結果的精度也不和諧K正相關或負相關，所以選擇合適的K獲得最高精度是非常重要的。 流行度 和UserCF不同，參數K對ItemCF推薦結果流行度的影響也不是完全正相關的。 隨著K的增加，結果流行度會逐漸提高，但當K增加到一定程度，流行度就不會再有明顯變化。覆蓋率 K增加會降低系統的覆蓋率。

18. 用戶活躍度對物品相似度的影響

在協同過濾中兩個物品產生相似度是因為它們共同出現在很多用戶 的興趣列表中。換句話說，每個用戶的興趣列表都對物品的相似度產生貢獻。

那么，是不是每個用戶的貢獻都相同呢?

假設有這么一個用戶，他是開書店的，并且買了當當網上80%的書準備用來自己賣。那么， 他的購物車里包含當當網80%的書。假設當當網有100萬本書，也就是說他買了80萬本。從前面 對ItemCF的討論可以看到，這意味著因為存在這么一個用戶，有80萬本書兩兩之間就產生了相似 度，也就是說，內存里即將誕生一個80萬乘80萬的稠密矩陣。

另外可以看到，這個用戶雖然活躍，但是買這些書并非都是出于自身的興趣，而且這些書覆 蓋了當當網圖書的很多領域，所以這個用戶對于他所購買書的兩兩相似度的貢獻應該遠遠小于一 個只買了十幾本自己喜歡的書的文學青年。

為了解決這個問題，John S. Breese一個稱為IUF(Inverse User Frequence)，即用戶活躍度對數的倒數的參數，他認為活躍用戶對物品相似度的貢獻應該小于不活躍的用戶，他提出應該增加IUF 參數來修正物品相似度的計算公式（ItemCF-IUF）:

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

19. 物品相似度的歸一化

如果將ItemCF的相似度矩陣按最大值歸一化，可以提高推薦的準確率。

如果已經得到了物品相似度矩陣w，那么可以用如下公式得到歸一化之后的相似度矩陣w':

歸一化的好處不僅僅在于增加推薦的準確度，它還可以提高推薦的覆蓋率和多樣性。 一般來說，物品總是屬于很多不同的類，每一類中的物品聯系比較緊密。舉一個例子，假設在一個電影網站中，有兩種電影——紀錄片和動畫片。那么，ItemCF算出來的相似度一般是紀錄片和 紀錄片的相似度或者動畫片和動畫片的相似度大于紀錄片和動畫片的相似度。但是紀錄片之間的 相似度和動畫片之間的相似度卻不一定相同。假設物品分為兩類——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類物品的數目也應該是大致相等的。從這個例子可以看出，相似度的歸一化可以提高推薦的多樣性。

ItemCF算法和ItemCF-Norm算法的離線實驗性能。

20. UserCF和ItemCF的綜合比較

UserCF是推薦系統領域較為古老的算法，1992年就已經在電子郵件的個性化推薦系統 Tapestry中得到了應用，1994年被GroupLens1用來實現新聞的個性化推薦，后來被著名的文章分 享網站Digg用來給用戶推薦個性化的網絡文章。ItemCF則是相對比較新的算法，在著名的電子商 務網站亞馬遜和DVD租賃網站Netflix中得到了廣泛應用。

那么，為什么Digg使用UserCF，而亞馬遜網使用ItemCF呢?

首先回顧一下UserCF算法和ItemCF算法的推薦原理。UserCF給用戶推薦那些和他有共同興 趣愛好的用戶喜歡的物品，而ItemCF給用戶推薦那些和他之前喜歡的物品類似的物品。從這個算法的原理可以看到，UserCF的推薦結果著重于反映和用戶興趣相似的小群體的熱點，而ItemCF 的推薦結果著重于維系用戶的歷史興趣。換句話說，UserCF的推薦更社會化，反映了用戶所在的小型興趣群體中物品的熱門程度，而ItemCF的推薦更加個性化，反映了用戶自己的興趣傳承。

在新聞網站中，用戶的興趣不是特別細化，絕大多數用戶都喜歡看熱門的新聞。即使是個性 化，也是比較粗粒度的，比如有些用戶喜歡體育新聞，有些喜歡社會新聞，而特別細粒度的個性化一般是不存在的。比方說，很少有用戶只看某個話題的新聞，主要是因為這個話題不可能保證每天都有新的消息，而這個用戶卻是每天都要看新聞的。因此，個性化新聞推薦更加強調抓住新聞熱點，熱門程度和時效性是個性化新聞推薦的重點，而個性化相對于這兩點略顯次要。因此，UserCF可以給用戶推薦和他有相似愛好的一群其他用戶今天都在看的新聞，這樣在抓住熱點和時效性的同時，保證了一定程度的個性化。這是Digg在新聞推薦中使用UserCF的最重要原因。

UserCF適合用于新聞推薦的另一個原因是從技術角度考量的。因為作為一種物品，新聞的更 新非常快，每時每刻都有新內容出現，而ItemCF需要維護一張物品相關度的表，如果物品更新很 快，那么這張表也需要很快更新，這在技術上很難實現。絕大多數物品相關度表都只能做到一天 一次更新，這在新聞領域是不可以接受的。而UserCF只需要用戶相似性表，雖然UserCF對于新 用戶也需要更新相似度表，但在新聞網站中，物品的更新速度遠遠快于新用戶的加入速度，而且 對于新用戶，完全可以給他推薦最熱門的新聞，因此UserCF顯然是利大于弊。

但是，在圖書、電子商務和電影網站，比如亞馬遜、豆瓣、Netflix中，ItemCF則能極大地發 揮優勢。首先，在這些網站中，用戶的興趣是比較固定和持久的。一個技術人員可能都是在購買技術方面的書，而且他們對書的熱門程度并不是那么敏感，事實上越是資深的技術人員，他們看的書就越可能不熱門。此外，這些系統中的用戶大都不太需要流行度來輔助他們判斷一個物品的好壞，而是可以通過自己熟悉領域的知識自己判斷物品的質量。因此，這些網站中個性化推薦的任務是幫助用戶發現和他研究領域相關的物品。因此，ItemCF算法成為了這些網站的首選算法。此外，這些網站的物品更新速度不會特別快，一天一次更新物品相似度矩陣對它們來說不會造成太大的損失，是可以接受的。

同時，從技術上考慮，UserCF需要維護一個用戶相似度的矩陣，而ItemCF需要維護一個物品 相似度矩陣。從存儲的角度說，如果用戶很多，那么維護用戶興趣相似度矩陣需要很大的空間， 同理，如果物品很多，那么維護物品相似度矩陣代價較大。

在早期的研究中，大部分研究人員都是讓少量的用戶對大量的物品進行評價，然后研究用 戶興趣的模式。那么，對于他們來說，因為用戶很少，計算用戶興趣相似度是最快也是最簡單 的方法。但在實際的互聯網中，用戶數目往往非常龐大，而在圖書、電子商務網站中，物品的 數目則是比較少的。此外，物品的相似度相對于用戶的興趣一般比較穩定，因此使用ItemCF是 比較好的選擇。當然，新聞網站是個例外，在那兒，物品的相似度變化很快，物品數目龐大， 相反用戶興趣則相對固定(都是喜歡看熱門的)，所以新聞網站的個性化推薦使用UserCF算法的 更多。

UserCF和ItemCF優缺點的對比

21. 隱語義模型 LFM（latent factor model）

隱語義模型是最近幾年推薦系統領域最為熱門的研究話題，它的核心思想是通過隱含特征 (latent factor)聯系用戶興趣和物品。

兩個用戶在豆瓣的讀書列表

上圖展示了兩個用戶在豆瓣的讀書列表。從他們的閱讀列表可以看出，用戶A的興趣涉及偵探小說、科普圖書以及一些計算機技術書， 而用戶B的興趣比較集中在數學和機器學習方面。

那么如何給A和B推薦圖書呢?

對于UserCF，首先需要找到和他們看了同樣書的其他用戶(興趣相似的用戶)，然后給他們推薦那些用戶喜歡的其他書。 對于ItemCF，需要給他們推薦和他們已經看的書相似的書，比如作者B看了很多關于數據挖掘的書，可以給他推薦機器學習或者模式識別方面的書。

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

如何給物品進行分類如何確定用戶對哪些類的物品感興趣，以及感興趣的程度？對于一個給定的類，選擇哪些屬于這個類的物品推薦給用戶，以及如何確定這些物品在一個類中的權重？

對于第一個問題的簡單解決方案是找編輯給物品分類。以圖書為例，每本書出版時，編輯都 會給書一個分類。為了給圖書分類，出版界普遍遵循中國圖書分類法1。但是，即使有很系統的分類體系，編輯給出的分類仍然具有以下缺點：

編輯的意見不能代表各種用戶的意見。比如，對于《具體數學》應該屬于什么分類，有 人認為應該屬于數學，有些人認為應該屬于計算機。編輯很難控制分類的粒度。我們知道分類是有不同粒度的，《數據挖掘導論》在粗粒度的 分類中可能屬于計算機技術，但在細粒度的分類中可能屬于數據挖掘。對于不同的用戶， 我們可能需要不同的粒度。比如對于一位初學者，我們粗粒度地給他做推薦就可以了， 而對于一名資深研究人員，我們就需要深入到他的很細分的領域給他做個性化推薦。編輯很難給一個物品多個分類。有的書不僅屬于一個類，而是可能屬于很多的類。 編輯很難給出多維度的分類。我們知道，分類是可以有很多維度的，比如按照作者分類、 按照譯者分類、按照出版社分類。編輯很難決定一個物品在某一個分類中的權重。比如編輯可以很容易地決定《數據挖掘導論》屬于數據挖掘類圖書，但這本書在這類書中的定位是什么樣的，編輯就很難給出一個準確的數字來表示。

為了解決上面的問題，研究人員提出:為什么我們不從數據出發，自動地找到那些類，然后進行個性化推薦？于是，隱含語義分析技術(latent variable ** ysis)出現了。隱含語義分析技術 因為采取基于用戶行為統計的自動聚類，較好地解決了上面提出的5個問題：

編輯的意見不能代表各種用戶的意見，但隱含語義分析技術的分類來自對用戶行為的統 計，代表了用戶對物品分類的看法。編輯很難控制分類的粒度，但隱含語義分析技術允許我們指定最終有多少個分類，這個數字越大，分類的粒度就會越細，反正分類粒度就越粗。編輯很難給一個物品多個分類，但隱含語義分析技術會計算出物品屬于每個類的權重， 因此每個物品都不是硬性地被分到某一個類中。 編輯很難給出多維度的分類，但隱含語義分析技術給出的每個分類都不是同一個維度的，它是基于用戶的共同興趣計算出來的，如果用戶的共同興趣是某一個維度，那么LFM給出的類也是相同的維度。編輯很難決定一個物品在某一個分類中的權重，但隱含語義分析技術可以通過統計用戶行為決定物品在每個類中的權重，如果喜歡某個類的用戶都會喜歡某個物品，那么這個物品在這個類中的權重就可能比較高。

隱含語義分析技術從誕生到今天產生了很多著名的模型和方法，其中和該技術相關且耳熟能 詳的名詞有pLSA、LDA、隱含類別模型(latent class model)、隱含主題模型(latent topic model)、 矩陣分解( ** trix factorization)。

以LFM為例介紹隱含語義分析技術在推薦系統中的應用，LFM的公式如下：

這個公式中 和 是模型的參數，其中 度量了用戶u的興趣和第k個隱類的關系，而 度量了第k個隱類和物品i之間的關系。

要計算這兩個參數，需要一個訓練集，對于每個用戶u，訓練集里都包含了用戶u喜歡的物品和不感興趣的物品，通過學習這個數據集，就可以獲得上面的模型參數。

推薦系統的用戶行為分為顯性反饋和隱性反饋。LFM在顯性反饋數據(也就是評分數據)上解決評分預測問題并達到了很好的精度。在沒有負樣本的情況下，需要對用戶沒有過行為的物品進行采集，對負樣本采樣時應該遵循以下原則：

對每個用戶，要保證正負樣本的平衡(數目相似)。對每個用戶采樣負樣本時，要選取那些很熱門，而用戶卻沒有行為的物品。一般認為，很熱門而用戶卻沒有行為更加代表用戶對這個物品不感興趣。因為對于冷門的物品，用戶可能是壓根沒在網站中發現這個物品，所以談不上是否感興趣。

由于LFM相對而言較為復雜，在這里就省略了書中的具體算法介紹，有興趣可以讀一讀《推薦系統實戰》

22. LFM和基于領域的方法對比

LFM是一種基于機器學習的方法，具有比較好的理論基礎。這個方法和基于鄰域的方法(比 如UserCF、ItemCF)相比，各有優缺點。

理論基礎 LFM具有比較好的理論基礎，它是一種學習方法，通過優化一個設定的指標建立最優的模型。基于鄰域的方法更多的是一種基于統計的方法，并沒有學習過程。 離線計算的空間復雜度 基于鄰域的方法需要維護一張離線的相關表。在離線計算相關表的過程中，如果用戶/物品數很多，將會占據很大的內存。 而LFM在建模過程中，可以很好地節省離線計算的內存。離線計算的時間復雜度 在一般情況下，LFM的時間復雜度要稍微高于UserCF和ItemCF，這主要是因為該算法需要多次迭代。但總體上，這兩種算法在時間復雜度上沒有質的差別。在線實時推薦 UserCF和ItemCF在線服務算法需要將相關表緩存在內存中，然后可以在線進行實時的預測。以ItemCF算法為例，一旦用戶喜歡了新的物品，就可以通過查詢內存中的相關表將和該物品相似的其他物品推薦給用戶。因此，一旦用戶有了新的行為， 而且該行為被實時地記錄到后臺的數據庫系統中，他的推薦列表就會發生變化。而從LFM的預測公式可以看到，LFM在給用戶生成推薦列表時，需要計算用戶對所有物品的興趣權重，然后排名，返回權重最大的N個物品。那么，在物品數很多時，這一過程的時間復雜度非常高。 LFM不能進行在線實時推薦，也就是說，當用戶有了新的行為后，他的推薦列表不會發生變化。

23. 基于圖的模型

用戶行為很容易用二分圖表示，因此很多圖的算法都可以用到推薦系統中。

本章討論的用戶行為 數據是由一系列二元組組成的，其中每個二元組(u, i)表示用戶u對物品i產生過行為。這種數據集 很容易用一個二分圖表示。

用戶物品二分圖模型：說明用戶A對物品a、b、d產生過行為

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

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

兩個頂點之間的路徑數兩個頂點之間路徑的長度兩個頂點之間的路徑經過的頂點

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

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

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

基于圖的推薦算法示例

基于上面3個主要因素，研究人員設計了很多計算圖中頂點之間相關性的方法，如 PersonalRank算法。

PersonalRank算法介紹：假設要給用戶u進行個性化推薦，可以從用戶u對應的節點 開始在用戶物品二分圖上進行隨機游走。游走到任何一個節點時，首先按照概率α決定是繼續游走，還是停止這次游走并從vu節點開始重新游走。如果決定繼續游走，那么就從當前節點指向的節點中按照均勻分布隨機選擇一個節點作為游走下次經過的節點。這樣，經過很多次隨機游走后，每個物品節點被訪問到的概率會收斂到一個數。最終的推薦列表中物品的權重就是物品節點的訪問概率。（具體的算法和代碼屬于工程范疇，不具體一一介紹，有興趣可以去看《推薦系統實踐》）

以上圖為例，用PersonalRank算法給用戶A進行推薦。

上圖給出了不同迭代次數后每個頂點的訪問概率。從圖中可以看到，每個頂點的訪問概率在9次迭代之后就基本上收斂了。在這個例子中，用戶A沒有對物品b、d有過行為。在最后的迭代結果中，d的訪問概率大于b，因此給A的推薦列表就是{d, b}。