基于用戶的優化協同過濾推薦算法*

衛 澤 周登文

(華北電力大學控制與計算機工程學院 北京 102206)

基于用戶的優化協同過濾推薦算法*

衛 澤 周登文

(華北電力大學控制與計算機工程學院 北京 102206)

針對傳統的協同過濾推薦算法存在的用戶鄰居集選擇不準確問題,論文提出了一種優化的協同過濾推薦算法,選擇用戶的共同評分數據計算用戶的相似性,同時考慮共同評分數據中用戶對項目評分的一致性,構造評分一致矩陣,將用戶評分一致次數與評分項目數之比作為懲罰函數引入到相似度的計算中,緩解相似度計算值與實際值出現的偏差。實驗表明,提出的優化算法顯著提高了預測的準確性,從而提高了推薦質量。

鄰居集; 協同過濾; 一致矩陣; 相似度

1 引言

隨著信息技術和互聯網的發展,人們逐漸從信息匱乏的時代進入到信息過載的時代。在這個時代,無論是信息消費者還是信息生產者都遇到了極大的挑戰:作為消費者,如何從大量信息中找到自己感興趣的信息是一件非常困難的事;而作為生產者,如何讓自己的信息脫穎而出,受到廣大用戶的關注,同樣是一件困難的事。推薦系統就是為解決這一問題而提出的智能代理系統,能從大量信息中推薦符合用戶興趣偏好的資源[1]。推薦系統就是聯系用戶和信息,一方面幫助用戶發現對自己有價值的信息,另一方面讓信息展示在對其感興趣的用戶面前,從而達到消費者和生產者的雙贏。電子商務是推薦系統的一大應用領域,著名的亞馬遜是個性化推薦系統的積極應用者和推廣者。電子商務推薦系統可以基于銷售排行和用戶對商品的評分等來進行推薦[2]。評分直接反映了用戶對商品的喜好程度。協同過濾算法正是利用戶對商品的評分數據來進行推薦。至今為止,協同過濾算法仍是電子商務推薦系統中應用最成功的推薦技術之一[1～3]。

現有的協同過濾推薦算法可以分為三個子類: 1) 基于用戶的推薦(User-based Recommendation)算法[4],該算法根據所有用戶對物品的偏好,發現與當前用戶偏好相似的“鄰居”用戶群,為當前用戶產生推薦,它的基本假設是:喜歡類似物品的用戶可能有相同或者相似的偏好; 2) 基于項目的推薦(Item-based Recommendation)算法[5～7],使用所有用戶對物品的偏好發現物品之間的相似度,然后根據用戶歷史偏好信息,將類似物品推薦給用戶; 3) 基于模型的推薦(Model-based Recommendati-on)算法[8～9],利用樣本的用戶喜好信息,訓練一個推薦模型,然后進行預測,計算推薦。已有研究指出,基于近鄰算法能獲得更好地推薦準確率,但是無法解決由數據量激增帶來的可伸縮性問題[2];基于模型的算法有更好的伸縮性,但是由于模型不能表現用戶興趣多樣性,因此在推薦質量方面不如基于近鄰的算法[10]。

2 傳統的協同過濾推薦算法

基于用戶的協同過濾一般需經過:收集用戶偏好、找到相似的鄰居用戶、計算推薦三個步驟,如何收集用戶的偏好信息成為系統推薦效果最基礎的決定因素[10]。用戶有很多方式向系統提供自己的偏好信息,主要分為顯式(如評分)或隱式(如購買),顯式反饋能明確表示用戶對物品喜好的程度。要對目標用戶產生推薦,首先需要找到和目標用戶相似的用戶集合,找到這個集合中用戶喜歡的,而目標用戶沒有聽說過的物品推薦給目標用戶,由此可見,算法的核心就在于如何尋找相似用戶,一般通過用戶之間的相似度來度量。選擇合適的相似度計算方法可以明顯提高推薦系統的精度。

在協同過濾推薦算法中,用戶評分數據包含m個用戶的集U={u1,u2,…,um}和n個項目的集合I={i1,i2,…,in},用戶對項目的評分數據可表示為矩陣R(m,n),如表1所示。

表1 用戶-項目評分矩陣R(m,n)

其中,Rui、Rvi分別表示用戶u、v對項目i的評分,用戶u和v的相似度記為sim(u,v),用戶u,v在項目集合I上的共同評分集表示為Iuv={i∈I|Rui≠0∩Rvi≠0}(I為全部項目集)。Rmn表示用戶m對項目n的評分。評分表示用戶對項目的感興趣程度,評分越高,表示用戶越感興趣。為了獲得更高的推薦效率,更準確的推薦結果,最重要的一步是獲得目標用戶的相似用戶集。相似用戶集合的準確性直接影響對目標用戶最終預測的準確性。傳統的相似性計算方法分為:余弦相似度、修正的余弦相似度和Pearson相關系數[3]。目前,最常用的相似度計算方法是Pearson相關系數計算方法。

2.1 相似度的計算

1) 余弦相似性(Cosine Correlation)

用余弦相似性計算相似度,速度快,實現簡單,但是沒有考慮用戶評分尺度的問題,導致計算出的鄰居數據不夠準確。

(1)

2) 修正的余弦相似性(Adjusted Cosine Correlation)

修正余弦相似性相對余弦相似性考慮了用戶評分尺度問題,可表示為如下公式:

(2)

3) Pearson相關相似性(Pearson Correlation)可由如下公式計算得到:

(3)

根據上一步計算得到的相似度,找到目標用戶最近鄰居集合V={v1,v2,v3,…,vm}。

2.2 預測評分并產生推薦

根據目標用戶的最近鄰居集合對項目的評分信息來預測目標用戶對其未評分項目的評分,并產生TopN推薦。用戶u對未評分項目i的預測評分Pui可通過u的鄰居集合Su(即V)對i的評分得到,可通過如下公式計算:

(4)

3 優化的協同過濾推薦算法

3.1 問題描述

2.1節中傳統的相似用戶的計算只針對用戶評分的相似性計算,兩兩用戶共同購買項目的評分能夠反映用戶之間的相似度,但是,兩兩用戶對于相同項目的評分如果一致,理論上可以認為該用戶對之間的相似度更高。2.2節提到的最近鄰的選取,怎樣選取最好的鄰居,每個鄰居的評分有多重要,鄰居的權值選擇是提高協同過濾算法精度的重要組件。本文將用戶對共同項目評分一致的次數及用戶對項目評分的總次數作為懲罰函數引入傳統的相似度計算中,對共同評分項目極少情況下的相似度計算進行平滑,從而降低過度估計帶來的影響,提高相似度的準確性。Pearson相似度計算沒有考慮用戶間重疊的評分項數對相似度的影響。本文提出的算法考慮到用戶在共同評分項目上評分一致的次數,對于相似度的影響,進而構造出評分一致矩陣,用于修正用戶相似度的計算。

3.2 用戶相似性

定義二維int型數組(維度是5*5),它存儲了兩個用戶在評分上的一致性。假定用戶U與V都對10個項目進行了評分,(評分標準為1～5分)其中對6個項目的評分一致,而其余的都不同。開始這個矩陣的所有單元都被初始化為0;對于兩個用戶對同一條目的評分,在分值對應的行與列中加1。所以,如果三個一致性的評分是4分,另三個是5分,就可得到matrix[3][3]與matrix[4][4]都是3。只要把matrix矩陣對角線的元素加起來,就能得到兩個用戶評分一致的次數。

修正后的相似度計算公式如下所示:

(5)

其中,c(u,v)表示用戶u和v之間在共同評分項目上評分一致的次數,N(u)與N(v)分別表示用戶u與用戶v對所有項目的評分次數。

3.3 相似性鄰居的選取

鄰居的選擇是預測目標用戶的評分的重要一步,如果選擇的鄰居用戶和目標用戶不相似,結果會導致目標用戶的預測評分不準確。Herlocker等最早提出了用戶相似性調整參數和鄰居用戶的選取閾值,并通過實驗證明引入這些參數后提高了推薦準確度[11～12]。所以本文引入θ來限定用戶相似鄰居的選取,θ的取值決定了相似性鄰居用戶集合的個數,只有相似性鄰居和目標用戶的相似度大于θ,才將此鄰居作為目標用戶的相似性鄰居。可表示如式(6)所示:

S(u)={v|Sim′(v,u)>θ,v≠u}

(6)

其中,S(u)表示目標用戶u的相似性鄰居集合,θ表示相似性鄰居用戶選取的閾值Sim′(v,u)的計算采用式(5)來計算。

4 實驗結果及分析

4.1 數據集

本文數據集來源于公開可用的MovieLens項目的電影數據集,MovieLens項目是明尼蘇達州立大學GroupLens研究組提供的。MovieLens提供了三種不同數量級的數據集,具體參數如表2所示。

表2 三種規模數據集

4.2 評價標準

推薦系統多采用準確度來對算法的好壞來進行評價[4]。準確度是衡量推薦算法預測用戶對項目的評分與用戶實際對項目的評分的相似程度,通常采用平均絕對誤差(MAE)來度量推薦算法的準確度。MAE是一個簡單卻魯棒的用于評估推薦精度的技術,計算的是預測評分與實際評分差的絕對值。MAE越小,則推薦精度越高。用戶u的平均絕對誤差MAEu計算如式(7)所示:

(7)

4.3 仿真分析

圖1 本文算法與傳統相似性算法推薦精度比較

為了驗證本文推薦算法的準確性,對傳統的User-based協同過濾算法與本文提出的基于評分一致的優化協同過濾算法進行比較分析,相似性度量方法選用Pearson相關系數,實驗參數θ設置為0.5。計算推薦算法的MAE鄰居個數從5增加到50,間隔為5。實驗結果如圖1所示。

由圖1可看出,在鄰居數不同的條件下,本文提出的基于評分一致的優化協同過濾算法均具有最小的MAE值。

5 結語

本文在傳統的基于用戶的協同過濾算法中,對鄰居權重的選擇使用懲罰函數來緩解對于相似度過于估計所帶來的影響,從而降低相似度計算值與實際值出現的偏差,提高算法的推薦精度。

在MovieLens數據集上進行的實驗,結果表明本文提出的基于評分一致優化協同過濾算法的預測準確率相對于傳統的協同過濾算法,可以獲得更好的推薦質量。

[1] 王國霞,劉賀平.個性化推薦系統綜述[J].計算機工程與應用,2012,48(7):66-76. WANG Guoxia, LIU Heping. Survey of personalized recommendation system[J]. Computer Engineering and Application,2012,48(7):66-76.

[2] 游文,葉水生.電子商務推薦系統中的協同過濾推薦[J].計算機技術與發展,2006,16(9):70-72. YOU Wen, YE Shuisheng. A Survey of Co-llaborative Filtering Algorithm Applied in E-commerce Recommender System[J]. Computer Technology and Development,2006,16(9):70-72.

[3] 奉國和,梁曉婷.協同過濾推薦研究綜述[J].圖書情報工作,2011,55(16):126-130. FENG Guohe, LIANG Xiaoting. Review of Collaborative Filtering Recommender[J]. Libraryand Information Service,2011,55(16):126-130.

[4] Goldberg D, Nichols D, Oki B M, et al. Using collaborative filtering to weave an information Tapestry[J]. Communications of ACM,1992,35(12):61-70.

[5] Sarwar B, Karypis G, Konstan G, et al. Item-based collaborative filtering recommendation algorithms[C]//New York: Proc. of World Wide WebCon,2001:285-295.

[6] Linden G, Smith B York, J. Amazon.com.recommendations:Item-to-item collaborative filtering[J]. IEEE Internet Computing,2003,7(1):76-80.

[7] Y. peng, X.P. Cheng. Item-based Collaborative Filtering Algorithm Using Attribute Similarity[J]. Computer Engineering and Applications,2007,43(14):144-147.

[8] Liu H. A new user similarity modelto improve the accuracyof collaborative filtering[J]. Knowledge-based System,2014,15(2):156-166.

[9] Y.L. Zhuang. A Collaborative Filtering Recommendtion Algorithm Based on the Model of Items’ Features[J]. Computer Applications and Software,2009,5(26):244-246.

[10] ADOMAVICIUS G, TUZHILIN A. Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Artand Possible Extensions[J]. IEEE Trans. Knowl. Data Eng,2005,17(6):734-749.

[11] Herlocker L J, Konstan A J, Riedl T J. Empiricalanalysis of design choices in neighborhood-based collaborative filtering algorithms[J]. Information Retrieval,2002,5(4):287-310.

[12] Herlocker L J, Konstan A J, Terveen G L, et al. Evaluating collaborative filtering recommender system[J]. ACM Transaction on Information Systems,2004,22(1):50-53.

Collaborative Filtering Recommendation Optimization Based on User

WEI Ze ZHOU Dengwen

(Department of Computer Science and Technology, North China Electric Power University, Beijing 102206)

In order to improve accuracy of the traditional collaborative filtering algorithm select user neighbor set, this paper proposes an improved collaborative filtering recommendation algorithm. The algorithm selects the user common rating data to calculate the user’s similarity, also considers the consistency of the score data, constructes evaluation matrix, and alleviates the similarity calculation value and actual value deviation by user rating consistent times thanratingitem number as a penalty function is introduced into the similarity calculation. Experimental results show that the improved algorithm proposed in this paper significantly increases the prediction accuracy, so as to improve the quality of recommendation.

neighbor set, collaborative filtering, consistent matrix, similarity Class Number TP301.6

2016年10月10日,

2016年11月14日

國家自然科學基金項目(編號:61372184);北京市自然科學基金項目(編號:4162056)資助。

衛澤,男,碩士,研究方向:推薦算法,數據挖掘。周登文,男,碩士生導師,研究方向:計算機視覺,圖像處理。

TP301.6

10.3969/j.issn.1672-9722.2017.04.003