協同過濾推薦算法比較研究

周泓宇，梁剛，楊進（.四川大學計算機學院，成都　60065；.樂山師范學院計算機科學學院，樂山　64000）

協同過濾推薦算法比較研究

周泓宇1，梁剛1，楊進2
（1.四川大學計算機學院，成都610065；2.樂山師范學院計算機科學學院，樂山614000）

0　引言

隨著信息技術的發展，網絡數據規模急劇擴大，大數據滿足用戶對信息需求的同時，帶來了信息過載的問題——用戶難以從海量數據中快速找到有用的信息[1]。推薦系統從用戶的角度出發，根據用戶的需求偏好、行為記錄等，挖掘出用戶可能感興趣的信息，并主動推薦給用戶。

協同過濾是推薦系統中采用的最為廣泛最為重要的技術之一[2]，其基本思想是具有相似行為的用戶對項目的需求也是相似的[3]。協同過濾算法只關注用戶的歷史行為，不受項目具體屬性的限制；并且能夠與社會網絡相結合，具有較好的推薦精度。其主要類型分為基于內存的協同過濾、基于模型的協同過濾以及組合協同過濾。本文首先介紹三種類型的協同過濾算法，以其中基于用戶（項目）的協同過濾算法、基于矩陣分解的協同過濾算法以及基于線性回歸的集成策略為例進行詳細闡述，然后給出對比實驗結果和分析，最后是全文總結。

1　基于用戶（項目）的協同過濾算法

基于內存的協同過濾算法包括基于用戶的方法和基于項目的方法，大致分為三個步驟：①基于用戶-項目評分矩陣，計算用戶（項目）之間的相似性；②通過相似度的逆序，選取最相似的前K個用戶（項目）作為鄰居；③根據鄰居的評分，對目標用戶（項目）未評分的項進行預測。下面以基于用戶的協同過濾算法為例進行詳細說明。

定義一個給定的用戶集U和項目集S，用戶對項目的評分表示為一個m×n的矩陣R，如表1所示。R（i，j）表示用戶i對項目j的評分，代表用戶對項目的偏好。如MovieLens數據集中用1~5分表示用戶的喜愛程度；若R（i，j）=0則表示用戶i未對項目j打分。

表1　用戶-項目m×n階評分矩陣R

首先基于用戶-項目評分矩陣計算用戶之間的相似度，常用的相似度算法包括余弦相似度算法、修正的余弦相似度算法和Pearson相關相似度算法。本文采用余弦相似度算法，把用戶的評分看作一個n維的評分向量，第k維的值表示對項目k的評分，設用戶u與用戶v的評分向量分別表示為向量u和v，則用戶u和用戶v之間的相似度為：

選取與用戶u相似度最大的k個用戶作為鄰居G （u），依據這k個鄰居對目標項目j的評分，加權預測用戶u對項目j的評分Pu，j，如公式（2）所示。其中，表示用戶i評分的均值，Ri，j表示用戶i對項目j的評分。

基于項目的方法與基于用戶的方法相似，通過計算兩兩項目的相似性得到目標項目的鄰居，并通過項目鄰居的評分預測用戶對目標項目的評分。兩種基于內存的協同過濾算法適用于不同的推薦環境，例如在電子商務中，項目的個數遠小于用戶的個數，且項目內容相比用戶變動更少，因此基于項目的推薦方法有更優的時間復雜度和實時性；而在微博、新聞等方面的推薦則與之相反，使用基于用戶的方法更好一些。

2　基于矩陣分解的協同過濾算法

基于模型的協同過濾算法通過對數據集的訓練完成對系統復雜模式的識別，并基于學習模型對協同過濾任務做出智能預測，包括基于概率的算法、樸素貝葉斯算法、聚類算法和基于矩陣分解的算法等，其中基于矩陣分解的算法常用于對基于評分的推薦環境[4]。基于矩陣分解的推薦算法是將原本高維度的評分矩陣RM×N分解成兩個低維度矩陣PM×D與QD×N的乘積，可將PM×D、QD×N分別看作用戶和項目的隱含特征矩陣，其中D表示隱含特征個數[5]。通過多次迭代訓練，使得PM×DQD×N不斷地逼近評分矩陣RM×N，最后得到最終的P、Q矩陣（P× Q≈R），以此來對未評分的項進行預測。下面以基礎的矩陣分解推薦算法為例進行說明。

為使得P×Q≈R，需求P×Q到R的最近距離，即使整個模型的損失最小，如式（3）所示，其中K為所有已評分項。

其中，t為迭代次數，α為迭代步長。通過多次迭代得到最終的P、Q矩陣，具體算法如下：

基于矩陣分解的推薦算法關注整個評分矩陣的損失程度，更注重全局性，且空間復雜度較低。

3　基于線性回歸的集成策略

基于線性回歸的集成策略是將多個弱學習器通過某種線性組合，獲得比單個弱學習器效果更好的強學習器的過程，線性系數由回歸分析確定。將上述基于用戶的方法、基于項目的方法和基于矩陣分解的方法看作三個弱學習器，分別表示為hu（X）、hs（X）和hv（X），強學習器Hw（X）如式（6）所示。

其中，w0，w1，w2，w3為線性系數。便于標記，令h0（X）=1，h（X）=[h0（X），hu（X），hs（X），hv（X）]，W=[w0，w1，w2，w3]T，則Hw（X）=h（X）×W。定義實際評分列向量為R（X），整個訓練集上的誤差平方和如式（7）所示。

為了使誤差平方和J（W）最小，本文采用最小二乘估計法，即：

4　實驗結果與分析

4.1實驗數據與評價標準

本實驗采用MovieLens100K數據集，其中包含了943位用戶對1682個項目的100K個評分，并將該數據集的80%作為訓練集，剩下20%為測試集。采用平均絕對誤差MAE（Mean Absolute Error）作為指標，衡量推薦算法的優劣。設預測的用戶評分集合為{p1，p2，…，pC}，對應的實際用戶評分集合為{r1，r2，…，rC}，則平均絕對誤差MAE定義如式（9）所示。

4.2實驗步驟

為了說明鄰居數K對基于用戶的協同過濾算法UBCF和基于項目的協同過濾算法IBCF的影響，選取K值從5到35進行測試，如圖1所示。從圖1中可看出，基于用戶的方法和基于項目的方法分別在K取30和K取15時達到最優效果，且前者的誤差普遍大于后者。

圖1　UBCF和IBCF的MAE指標

為了說明隱含特征個數D對基于矩陣分解的協同過濾算法MFCF的影響，分別選取10個，20個，30個，50個進行測試，如圖2所示。從圖2中可看出，在當前數據集下，MAE值隨著D的增加而增加，D取10時，效果最佳。

圖2　MFCF的MAE指標

為了直觀地比較基于線性回歸的集成算法LICF與單個學習器算法的優劣，選取每個學習器的最優效果，即分別選擇UBCF（K=30）、IBCF（K=15）和MBCF （D=10）作為弱學習器，并與集成后的強學習器作比較，如圖3所示。從圖中可看出，LICF算法的效果明顯優于每個弱學習器。

圖3　四種算法MAE指標的比較情況

5　結語

本文就三類協同過濾算法，針對性地對其中基于用戶（項目）、基于矩陣分解和基于線性回歸集成的方法進行了闡述和比較，然后利用MovieLens的電影評分數據對幾種算法的推薦效果進行了驗證。實驗結果表明，基于線性回歸的集成策略比其他單一的協同過濾算法效果好一些。組合推薦的優勢明顯，然而單個推薦算法的選擇和組合策略的方式都是多樣化的，如何找到最優的方案還有待進一步解決。

[1]柯良文，王靖.基于用戶特征遷移的協同過濾推薦[J].計算機工程，2015，41（1）:37-43.

[2]王國霞，劉賀平.個性化推薦系統綜述[J].計算機工程與應用，2012，48（7）:66-76.

[3]Candillier L,Meyer F,Boulle M.Comparing State-of-the-Art Collaborative Filtering Systems[J].Machine Learning and Data Mining in Pattern Recognition，2007，11（4）：548-562.

[4]Vucetic S,Obradovic Z.Collaborative Filtering Using a Regression-Based Approach[J].Knowledge and Information Systems，2005，7 （1）:1-22.

[5]王鵬.基于矩陣分解的推薦系統算法研究[D].北京：北京交通大學.

Recommender System;Collaborative Filtering;Linear Regression;Matrix Factorization

Comparable Research on Collaborative Filtering Recommendation Algorithms

ZHOU Hong-yu1，LIANG Gang1，YANG Jin2
（1.College of Computer Science,，Sichuan University，Chengdu 610065；2.College of Computer Science,，Leshan Normal University，Leshan 614000）

1007-1423（2016）07-0016-04

10.3969/j.issn.1007-1423.2016.07.004

周泓宇（1990-），男，碩士，研究方向為機器學習

梁剛（1976-），男，博士，講師，研究方向為機器學習、智能計算、網絡安全

楊進（1980-），男，博士，教授，研究方向為機器學習

2016-01-15

2016-02-20

推薦系統被廣泛用于電子商務、視頻網站、新聞小說推薦等各個領域，旨在向用戶提供其可能感興趣的信息。協同過濾是推薦系統的主流技術，分為基于內存的協同過濾、基于模型的協同過濾以及組合協同過濾。以其中基于用戶（項目）、基于矩陣分解以及基于線性回歸集成策略的協同過濾算法為例進行說明比較，然后通過MovieLens的數據集進行實驗對比。

推薦系統；協同過濾；線性回歸；矩陣分解

四川省科技廳項目（No.2014JY0036）、四川省教育廳創新團隊基金（No.13TD0014）

Recommender system designed to provide users with information that may be of interest is widely used in E-Commerce,video websites, news and novels recommendation,etc.Collaborative filtering is the main technology of recommender system,is divided into three classes: collaborative filtering based on memory,collaborative filtering based on the model and hybrid recommendation.Compares the algorithms of user(item)based,matrix factor based and linear regression in integration strategy as an example and gets the result through experimen-tal comparison with the dataset of MovieLens system.