推薦算法綜述（二）

【編者按】推薦系統在各種系統中廣泛使用，推薦算法則是其中最核心的技術點，InfoQ接下來將會策劃系列文章來為讀者深入介紹。推薦算法綜述分文五個部分，本文作為第一篇，將會簡要介紹推薦系統算法的主要種類。其中包括算法的簡要描述、典型的輸入、不同的細分類型以及其優點和缺點。在第二和第三篇中，我們將會詳細介紹這些算法的區別，讓你能夠深入理解他們的工作原理。

注：本文翻譯自 Building Recommenders ，InfoQ中文站在獲得作者授權的基礎上對文章進行了翻譯。

本文是推薦算法綜述的第二部分。在第一篇文章中，我們簡要介紹了推薦算法主要種類及其特點。在本文中，我們將會詳細介紹協同過濾推薦算法以及其優點和缺點，這樣大家就能深入理解其運行原理。

協同過濾（CF）推薦算法通過在用戶活動中尋找特定模式來為用戶產生有效推薦。它依賴于系統中用戶的慣用數據，例如通過用戶對其閱讀過書籍的評價可以推斷出用戶的閱讀偏好。這種算法的核心思想就是：如果兩個用戶對于一些項的評分相似程度較高，那么一個用戶對于一個新項的評分很有可能類似于另一個用戶。值得注意的是，他們推薦的時候不依賴于項的任何附加信息（例如描述、元數據等等）或者用戶的任何附加信息（例如喜好、人口統計相關數據等等）。CF的方法大體可分為兩類：分別為鄰域和基于模型的方法。鄰域方法（即基于內存的CF）是使用用戶對已有項的評分直接預測該用戶對新項的評分。與之相反，基于模型的方法是使用歷史評分數據，基于學習出的預測模型，預測對新項的評分。通常的方式是使用機器學習算法，找出用戶與項的相互作用模型，從而找出數據中的特定模式。

基于鄰域的CF方法意在找出項與項之間的聯系（基于項的CF），或者用戶與用戶之間的聯系（基于用戶的CF）。

• 基于用戶的CF通過找出對項的偏好與你相似的用戶從而基于他們對于新項的喜好來為你進行推薦。
• 基于項的CF會向用戶推薦與用戶喜歡的項相似的項，這種相似是基于項的共同出現幾率（例如用戶買了X，通時也買了Y）。

首先，在做基于項的協同過濾之前，我們先通過例子來看一下基于用戶的協同過濾。

假設我們有一組用戶，他們表現出了對一組圖書的喜好。用戶對一本圖書的喜好程度越高，就會給其更高的評分，范圍是從1到5。我們來通過一個矩陣來展示它，行代表用戶，列代表圖書（圖1）。

圖1：用戶對圖書的評分。所有的評分范圍從1到5，5代表喜歡程度最高。第一個用戶（行1）對第一個圖書（列1）的評分是4。空的單元格代表用戶未給圖書評價。

使用基于用戶的協同過濾方法，我們首先要做的是基于用戶給圖書作出的評價計算出用戶之間的相似度。讓我們從一個單一用戶的角度考慮這個問題，看圖1中的第一行。要做到這一點，常見的做法是將使用包含了用戶喜好項的向量（或數組）代表每一個用戶。相較于使用多樣化的相似度量這種做法非常直接。在這個例子中，我們將使用余弦相似性。當我們把第一個用戶和其他五個用戶進行比較時，就能直觀地看到他和其他用戶的相似程度（圖2）。對于大多數相似度量，向量之間相似度越高，代表彼此更相似。本例中，第一個用戶與兩位其他用戶非常相似，有兩本共同書籍，與另兩位用戶的相似度低一些，只有一本共同書籍，而與最后一名用戶完全不相似，沒有一本共同書籍。

圖2：第一個用于與其他用戶的相似度。可以使用余弦相似性在一個單一維度繪制用戶之間的相似度。

更一般地，我們可以計算出每個用戶的相似性，并且在相似矩陣中表示它們（圖3）。這是一個對稱矩陣，這意味著對它進行數學計算會有一些有用的特性。單元格的背景顏色表明用戶相似度的高低，更深的紅色表示他們之間更相似。

圖3：用戶間的相似矩陣。用戶之間的相似度基于用戶對所讀圖書的評價數據的相似度

現在我們使用基于用戶的協同過濾方法準備好了為用戶生成推薦。在一般情況下，對于一個給定的用戶，這意味著找到最相似的用戶，并推薦這些類似的用戶欣賞的項，并根據用戶相似度對其進行加權。我們先來看第一個用戶，為他們生成一些推薦。首先，我們找到了與第一個用戶最相似的另一用戶，刪除用戶已經評價過的書籍，給最相似用戶正在閱讀的書籍加權，然后計算出總和。在這種情況下，我們計算出n=2，表示為了產生推薦，需要找出與目標用戶最相似的兩個用戶。這兩個用戶分別是2和3（圖4）。然后，第一個用戶已經評價了5和1，所產生的推薦書是3（4.5分）和4（3分）。

圖4：為一個用戶進行推薦。我們將選取最相似的兩個用戶所評價的書，進行加權，然后推薦加權分數最高且目標用戶未評價過的圖書。

通過基于用戶的協同過濾讓我們對協同過濾有了一定的理解。接著讓我們再看一個例子，基于項的協同過濾。同樣地，我們以評價過一些書籍的一組用戶為基礎（圖1）。類似于基于用戶的協同過濾，在基于項的協同過濾中，我們要做的第一件事也是計算相似矩陣。然而，這一次，我們要看的是項，而非用戶的相似性。類似地，我們要計算出一本書和其它書的相似性，我們將使用評價過一本書的用戶向量（或數組）表示這本圖書，并比較他們的余弦相似性函數。在第一列的第一本書，最類似于第五列的第五本書，因為評價他們的用戶大致相同（圖5）。第三本書有兩個相同的評價用戶，第四和第二本書只有一個共同評價用戶，而最后一本書是不認為是相似的，因為同它有沒有共同的評價用戶。

圖5：第一個圖書和其它圖書的對比。圖書用評價過它們的用戶表示。使用相似值（0-1）表示相似度。兩本書越相似則相似值越高

為了更充分地顯示結果，我們可以顯示表示所有圖書之間相似度的相似矩陣（圖6）。同樣地，單元格背景顏色的深淺表示相似度的高低，顏色越深表明相似度越高。

圖6：書的相似矩陣

現在，我們已經知道了圖書之間的相似度，我們可以為用戶進行推薦。在基于項的方法中，我們采用被用戶評價過的項，推薦和被采取項最相似的項。在我們的例子中，第一個用戶首先將被推薦第三本書，其次是第六本書（圖7）。另外，我們只推薦和用戶已經評價過圖書最相似的前兩本書。

圖7：為用戶進行推薦。我們選取他們評價過的圖書，找出與他們最相似的前兩本書，進行加權，然后推薦給用戶加權分最高且他沒有讀過的書。

鑒于基于用戶和基于項的協同過濾的描述聽起來非常相似，有趣的是它們可以產生不同的推薦結果。即使在我們這里給出的簡易的例子中，即使使用的數據相同，這兩種方法產生對于同一用戶產生的推薦結果也不相同。當你構建推薦系統的時候，這兩種協同過濾方式都是值得考慮的。即使將這兩種方式描述給非專家聽，它們聽起來也非常相似，在實踐中，他們可以產生不同的結果，為用戶提供了不同的體驗。

鄰域方法由于其簡單性和效率具有相當的知名度，同時也是由于它們有產生準確的和個性化的推薦的能力。然而，它們也有一些可擴展性的限制，因為在用戶數量和項的數量增長的情況下，它們需要一個相似度的計算（基于用戶或項）。在最壞的情況下，這種計算的時間復雜度可能是O(m*n)，但在實踐中的情況稍微好一點O(m+n)，部分原因是由于利用了數據的稀疏度。雖然稀疏有助于可擴展性，它也對基于鄰域的方法提出了一個挑戰，因為我們的用戶僅僅對龐大數量項中的很少一部分進行了評分。例如，在Mendeley，我們有數以百萬計的文章而一個用戶可能只讀了其中幾百篇文章。兩個讀過100篇文章的用戶有一篇相同文章的概率（共5000萬篇文章）是0.0002。

基于模型的方法可以幫助克服一些基于鄰域的方法的局限性。它不像基于鄰域的方法，使用用戶項評分直接預測新的項。基于模型的方法會在使用評分去學習預測模型的基礎上，去預測新項。一般的想法是使用機器學習算法建立用戶和項的相互作用模型，從而找出數據中的模式。在一般情況下，基于模型的CF被認為是建立CF推薦系統的更先進的算法。有許多不同的算法可用于構建模型并基于這些模型進行預測，例如，貝葉斯網絡、聚類、分類、回歸、矩陣分解、受限玻爾茲曼機等等。這些技術在為了最終贏得Netflix獎的解決方案中扮演了關鍵角色。Netflix發起了一個競賽，從2006年到2009年提供一百萬美元獎金，頒發給產生的推薦比他們自己的推薦系統精確10%以上的推薦系統團隊。成功獲獎的解決方案是Netflix研發的一個集成（即混合）了超過100種算法模型，這些算法模型都采用了矩陣分解和受限玻爾茲曼機。

矩陣因子分解（如奇異值分解，奇異值分解+ +）將項和用戶都轉化成了相同的潛在空間，它所代表了用戶和項之間的潛相互作用（圖8）。矩陣分解背后的原理是潛在特征代表了用戶如何給項進行評分。給定用戶和項的潛在描述，我們可以預測用戶將會給還未評價的項多少評分。

圖8：矩陣分解表示。用戶偏好矩陣可以被分解成一個用戶主題矩陣乘以一個主題項矩陣。

在表1中，我們概述了基于鄰域和基于模型的協同過濾方法的主要優點和缺點。由于它們僅依賴于用戶的慣用數據，協同過濾方法需要最低限度專業工程的努力，以產生足夠好的結果，但是，他們也有局限性。例如，CF傾向于推薦流行的項，很難推薦給有獨特口味的人（即感興趣的項并沒有產生足夠多的慣用數據）。這被稱為流行性偏見，它通常是用基于內容的過濾方法。CF方法的一個更重要的限制是我們所稱的“冷啟動問題”，系統是不能夠給沒有（或非常少）慣用活動的用戶進行推薦，又名曰新用戶問題，或推薦新項問題。新用戶的“冷啟動問題”可以通過流行性和混合方法進行解決，而新項問題可以通過使用基于內容的過濾或multi-armed bandits（即探索利用）進行解決。我們將在下一篇文章中討論上述方法中的一些方法。

在這篇文章中，我們討論了三種基本的協同過濾的實現方法。基于項、基于用戶和基于矩陣分解之間的差異是很微妙的，很難簡單明了地解釋它們。了解它們之間的差異將有助于你選擇最適合你的推薦算法。在接下來的文章中，我們會繼續更加深入地介紹一些流行的推薦算法。

查看英文原文： Overview of Recommender Algorithms – Part 2