基于協同過濾的推薦算法研究

毛勇

摘 要： 推薦算法是目前互聯網環境下廣泛使用的技術之一。其中協同過濾推薦算法是目前應用最廣泛最成熟的推薦技術。文章介紹了協同過濾推薦算法的基本概念和原理，對協同過濾推薦算法的相似度計算公式和評價指標進行了歸納整理，總結分析協同過濾推薦算法存在的問題，以及目前眾多學者對這些問題的解決方案，最后介紹了協同過濾推薦算法的發展方向。

關鍵詞： 推薦算法； 協同過濾； 個性化推薦； 預測推薦

中圖分類號：TP399 文獻標志碼：A 文章編號：1006-8228（2018）07-28-04

Abstract： Recommendation algorithm is one of the most widely used technologies in the Internet environment. Among them， collaborative filtering recommendation algorithm is currently the most widely used and the most matured recommendation technology. This paper mainly introduces the basic concepts and principles of collaborative filtering recommendation algorithm， summarizes the similarity calculation formula and evaluation index of collaborative filtering recommendation algorithm， summarizes and analyzes the existing problems of collaborative filtering recommendation algorithm， as well as the solutions to these problems of many scholars at present， and finally， the development direction of collaborative filtering recommendation algorithm is introduced.

Key words： recommendation algorithm； collaborative filtering； personalized recommendation； prediction recommendation

0 引言

隨著互聯網和信息技術的迅猛發展，用戶往往很難從海量的數據中獲取到自己所需要的信息，傳統的搜索引擎和信息過濾技術只能被動的為用戶提供信息服務，當用戶的信息需求不明確時，這些技術很難有效地幫助用戶。因此，如何更高效更精準地為用戶提供信息服務，成為制約互聯網信息服務發展的一個主要問題。在解決這個問題方面，推薦系統相對于傳統的推薦引擎和信息過濾技術有著明顯的優勢。推薦系統能根據用戶的歷史訪問記錄信息，來為用戶進行精準高效的個性化推薦服務。推薦算法主要分為：基于內容的推薦算法、協同過濾推薦算法和混合推薦算法。其中協同過濾推薦算法是當前應用較為廣泛和成功的推薦算法。

1 基于協同過濾的推薦算法

1992年Goldberg、Nicols、Oki和Terry首次提出協同過濾的概念[1]。協同過濾算法是一種典型的利用集群智慧的方法，它的核心思想為：對于具有相同或相似興趣愛好的用戶A和B，當用戶A喜歡某一個物品時，用戶B可能對這個物品也有著相似的興趣度。協同過濾算法一般采用最近鄰技術，利用用戶對項目的歷史評分數據，通過相似度計算產生目標用戶的最近鄰集合。

經過多年發展，協同過濾算法主要分為兩類：基于內存（Memory-based）的協同過濾推薦算法和基于模型（Model-based）的協同過濾推薦算法[2]。而基于內存的協同過濾推薦算法又可以分為：基于用戶的協同過濾算法（User Based Collaborative Filtering，UBCF）和基于項目的協同過濾推薦算法（Item-Based Collaborative Filtering，IBCF）。

1.1 基于內存的協同過濾算法：

在一部分中文文獻中，基于內存的協同過濾算法也被翻譯為“基于記憶”的協同過濾算法，基于內存的協同過濾推薦算法主要分為三步。

⑴ 收集用戶信息

收集可以代表用戶興趣的信息集合，構建用戶-項目評分矩陣如下：

⑵ 相似性計算

相似度計算是基于內存的協同過濾推薦算法的基礎步驟，通過相似度計算可以獲得用戶之間興趣偏好的相似程度或兩個項目的相似程度。

以下是兩種常用的相似度計算方法。

方法一 夾角余弦相似度（Cosine Similarity）

夾角余弦相似度將每個用戶評分數據看做n維向量，兩個向量之間的夾角余弦值表示這兩個用戶之間的相似程度，夾角余弦值越小表示這兩個用戶之間的相似度越高，具有相似的興趣偏好。夾角余弦相似度公式為：

皮爾森相關系數（Pearson Correlation Coefficient PCC）[3]：是余弦相似度在維度缺失情況下的一種改進，在兩個用戶共有的評分項目上進行相似度計算，皮爾森相關系數公式如下：

其中，Iuv表示用戶u和用戶v共有的評分項目，rui和rvi分別表示用戶u和用戶v對項目i的評分，，分別表示用戶u和用戶v各自的項目平均分。

方法二 修正的余弦相似度（Adjusted Cosine Similarity）

余弦相似度更多的是從方向上區分差異，而對絕對的數值不敏感，因此無法從每個維度來衡量數值的差異。針對這種情況，就出現了修正的余弦相似度，公式如下所示：

其中，Iuv表示用戶u和用戶v共有的評分項目，rui和rvi分別表示用戶u和用戶v對項目i的評分，，分別表示用戶u和用戶v各自的項目平均分，Iu和Iv表示用戶u和用戶v各自的評分項目。

⑶ 生成推薦列表

最近鄰集合的產生方法有兩種，一種是設置相似度闕值，只有高于闕值才判定為相似用戶，另一種是指定目標用戶的最近鄰個數。

1.1.1 基于用戶的協同過濾算法

基于用戶的協同過濾推薦算法通過比較目標用戶的一系列行為或評分信息和其他用戶之間的相似程度，來計算出目標用戶的最近鄰集合，也就是和目標用戶興趣偏好類似的用戶集合，然后將最近鄰集合中的用戶最感興趣的內容或項目作為推薦內容推薦給目標用戶。

1.1.2 基于項目的協同過濾算法

隨著推薦系統的發展，會出現這樣一種現象，推薦系統數據庫中的項目數量固定或者增長緩慢，與之相反的是推薦系統的用戶快速增長，因此推薦算法計算出的項目之間的相似度矩陣更新頻率很低。基于項目的協同過濾算法認為：用戶對不同項目的評分具有相似性，因此，在為目標用戶進行推薦時，可以先計算項目之間的相似程度，當需要預測用戶對某一個項目的評分或喜愛程度時，可以參照用戶已經評價過的項目評分來進行計算。基于物品的協同過濾算法就是找到和“目標用戶”喜歡的物品相似的物品，然后把相似的物品推薦給“目標用戶”。例如我很喜歡《黑客帝國》，而《盜夢空間》和《黑客帝國》相似度很高，推薦系統就可以給我推薦《盜夢空間》，實際上我也很喜歡《盜夢空間》。

1.2 基于模型的協同過濾算法

基于內存的協同過濾推薦算法在推薦計算過程中，推薦算法通過相似度計算對用戶未訪問過的項目進行評分預測，在這個過程中，用戶的所有評分數據都在評分預測中充分發揮作用，形成一種全局推薦，因此基于內存的推薦算法一般都可以提供較為滿意的推薦質量，但是隨著用戶數量和項目數量的增加，全局推薦計算將占用大量系統內存資源，很難滿足一些在線推薦服務的實時性要求。針對這一問題，眾多學者將機器學習和數據挖掘的計算模型與協調過濾推薦算法相結合，研究出了基于模型協同過濾推薦算法。

基于內存的協同過濾推薦算法之間在用戶-項目評分矩陣上進行運算和產生推薦結果，而基于模型的協同過濾推薦算法首先對用戶-項目評分矩陣進行分析和數據挖掘，通過機器學習的算法或統計學的相關數學模型建立相符的評分預測模型，最后根據目標用戶已有的評分數據，來對目標用戶未評分的項目進行評分預測。

2 協同過濾推薦算法評價指標

⑴ 預測準確度

預測準確度是衡量一個推薦系統或者推薦算法預測用戶行為的一個重要指標，在計算預測準確度時，需要將包含用戶歷史行為記錄的數據集分割為訓練集和測試集。通過在訓練集上建立用戶的行為和興趣模型預測用戶在測試集上的行為，并計算預測的結果和測試集中數據的重合度。通常評分預測準確度通過均方根誤差（RMSE）和平均絕對誤差（MAE）來計算[4]。

⑵ 覆蓋率

覆蓋率（coverage）表示一個推薦系統對項目長尾的挖掘能力，具體指的就是推薦算法預測出來的項目占項目總數的比例，推薦算法推薦的數量越多，表示推薦算法的推薦質量越高。在信息論和經濟學中有兩個著名的指標用來定義覆蓋率。

⑶ 多樣性

多樣性指標主要考慮到用戶的興趣是多樣的，例如用戶可能同時喜歡動作電影，戰爭電影和文藝電影，當推薦列表中的項目都包含這三類電影時，才能夠滿足用戶的多樣性需求。多樣性代表著推薦列表中的項目應該是不屬于同一類目的，也就是這些項目應該是不同的，存在差異性。

3 協同過濾推薦算法存在的問題

⑴ 數據稀疏問題

數據稀疏問題是推薦系統中普遍存在的現象。協同過濾算法是在用戶-項目評分矩陣的基礎上進行相似度計算和預測推薦，而在正常的推薦系統中，用戶不可能對系統中的每一個項目都作出評分，因此在用戶-項目評分矩陣中存在著大量的空白項。在對用戶或者項目之間進行相似性計算時，缺乏客觀準確的評分數據，最終出現推薦結果不夠精準的問題。

針對這個問題，學術界研究了許多方法來解決這個問題：①矩陣填充。通常是對沒有評分數據的項目填入一個固定的缺省值或者填入其他用戶在這個項目上的平均值。②矩陣降維和奇異值分解（SVD）[5]。采用奇異值分解的方法去掉不重要的和用噪音，降低矩陣維度，增加矩陣數據的稠密程度。③采用預測評分對用戶-項目評分矩陣的空白評分項進行填充[6]。常用的方法有BP神經網絡、Na?ve Bayesian分類器等，通過這些方法預測用戶對項目的評分情況。

⑵ 冷啟動問題

冷啟動是數據稀疏問題的一個特殊情況，它分為新項目冷啟動問題和新用戶冷啟動問題。冷啟動出現的原因是，當一個新用戶或者一個新的項目加入到系統時，該用戶沒有對系統中的項目進行推薦或者一個新的項目加入到系統后短時間內沒有用戶對其進行評價。推薦算法在進行相似度計算時因為缺少評分數據，因此很難為新用戶或新項目匹配到相似用戶或相似項目。

⑶ 可擴展性問題

協同過濾算法的核心是通過對用戶-項目評分矩陣來進行相似度計算，而在推薦系統中，用戶和項目的數量隨著時間的變化而增加，也就意味著在進行相似度計算時，龐大的矩陣計算將會嚴重影響推薦算法的推薦效率。針對這一問題，經典的解決方法有k-means聚類、EM（Expectation-Maximization）算法、Gibbs Sampling 算法和模糊聚類算法等。

⑷ 興趣漂移問題

興趣漂移問題在現實情境中是經常存在的。因為用戶的興趣變化會隨著生活環境，年齡增長等外界原因或者自身性格變化的內部原因而改變，但是推薦系統很難根據用戶的歷史記錄來敏銳的捕捉到這點，這就導致推薦算法推薦和預測用戶可能感興趣的內容與用戶實際關注和感興趣的內容產生脫節。針對這一問題，業內專家主要采用顯式反饋和隱式反饋相結合的方法，或者將用戶的地理位置、登錄時間等因素考慮在內，進一步進行精準的推薦。

4 總結和展望

協同過濾推薦算法是目前應用最廣泛最成功的推薦算法，在電子商務、互聯網音樂視頻等領域有著不可忽視的作用。本文圍繞協同過濾推薦算法這一主題，重點介紹了協同過濾推薦算法的核心思想、算法分類、算法過程和協同過濾推薦算法所存在的問題以及相應的解決方案。綜合分析協同過濾推薦算法的發展趨勢，我們可以看出雖然協同過濾推薦算法相比之前的只針對用戶-項目評分矩陣這一顯式反饋因素進行考慮，現在的協同過濾推薦算法在算法性能和用戶興趣挖掘方面有了很大進步，同時與機器學習和深度學習的一些前沿算法相結合也有了良好的效果。但是隨著現代社會人們生活節奏的加快，其興趣需求的變化頻率也隨之加快，如何更加敏銳靈活的感知用戶的興趣變化，這些方面也是以后需要繼續研究的方向。

參考文獻（References）：

[1] Goldberg D， Nichols D， Oki B M， et al.Using collaborative filtering to weavr an information tapestry[J].Communications of the ACM.December，1992.35（12）：61-70

[2] 查大元.個性化推薦系統的研究和實現[J].計算機應用與軟件，2011.28（10）：7-8，42

[3] Tao Jun， Zhang Ning. Collaborative Filtering Algorithm Based on Interest-Class[J]. Computer System&Applications;，2011.5：55-59

[4] 任磊.推薦系統關鍵技術研究[D].華東師范大學，2012.

[5] 孫小華.協同過濾系統的稀疏性與冷啟動問題研究[D].浙江大學，2005.

[6] Shan H，Kattge J，Reich P，et al.Gap Filling in the Plant Kingdom-Trait Prediction Using Hierarchical Probabilistic Matrix Factorization[J]. arXiv preprint arXiv：1206.6439，2012.