衛(wèi) 澤 周登文

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

基于用戶的優(yōu)化協(xié)同過濾推薦算法*

衛(wèi) 澤 周登文

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

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

鄰居集; 協(xié)同過濾; 一致矩陣; 相似度

1 引言

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

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

2 傳統(tǒng)的協(xié)同過濾推薦算法

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

在協(xié)同過濾推薦算法中,用戶評分?jǐn)?shù)據(jù)包含m個用戶的集U={u1,u2,…,um}和n個項目的集合I={i1,i2,…,in},用戶對項目的評分?jǐn)?shù)據(jù)可表示為矩陣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的評分。評分表示用戶對項目的感興趣程度,評分越高,表示用戶越感興趣。為了獲得更高的推薦效率,更準(zhǔn)確的推薦結(jié)果,最重要的一步是獲得目標(biāo)用戶的相似用戶集。相似用戶集合的準(zhǔn)確性直接影響對目標(biāo)用戶最終預(yù)測的準(zhǔn)確性。傳統(tǒng)的相似性計算方法分為:余弦相似度、修正的余弦相似度和Pearson相關(guān)系數(shù)[3]。目前,最常用的相似度計算方法是Pearson相關(guān)系數(shù)計算方法。

2.1 相似度的計算

1) 余弦相似性(Cosine Correlation)

用余弦相似性計算相似度,速度快,實現(xiàn)簡單,但是沒有考慮用戶評分尺度的問題,導(dǎo)致計算出的鄰居數(shù)據(jù)不夠準(zhǔn)確。

(1)

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

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

(2)

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

(3)

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

2.2 預(yù)測評分并產(chǎn)生推薦

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

(4)

3 優(yōu)化的協(xié)同過濾推薦算法

3.1 問題描述

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

3.2 用戶相似性

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

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

(5)

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

3.3 相似性鄰居的選取

鄰居的選擇是預(yù)測目標(biāo)用戶的評分的重要一步,如果選擇的鄰居用戶和目標(biāo)用戶不相似,結(jié)果會導(dǎo)致目標(biāo)用戶的預(yù)測評分不準(zhǔn)確。Herlocker等最早提出了用戶相似性調(diào)整參數(shù)和鄰居用戶的選取閾值,并通過實驗證明引入這些參數(shù)后提高了推薦準(zhǔn)確度[11～12]。所以本文引入θ來限定用戶相似鄰居的選取,θ的取值決定了相似性鄰居用戶集合的個數(shù),只有相似性鄰居和目標(biāo)用戶的相似度大于θ,才將此鄰居作為目標(biāo)用戶的相似性鄰居?？杀硎救缡?6)所示:

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

(6)

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

4 實驗結(jié)果及分析

4.1 數(shù)據(jù)集

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

表2 三種規(guī)模數(shù)據(jù)集

4.2 評價標(biāo)準(zhǔn)

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

(7)

4.3 仿真分析

圖1 本文算法與傳統(tǒng)相似性算法推薦精度比較

為了驗證本文推薦算法的準(zhǔn)確性,對傳統(tǒng)的User-based協(xié)同過濾算法與本文提出的基于評分一致的優(yōu)化協(xié)同過濾算法進(jìn)行比較分析,相似性度量方法選用Pearson相關(guān)系數(shù),實驗參數(shù)θ設(shè)置為0.5。計算推薦算法的MAE鄰居個數(shù)從5增加到50,間隔為5。實驗結(jié)果如圖1所示。

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

5 結(jié)語

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

在MovieLens數(shù)據(jù)集上進(jìn)行的實驗,結(jié)果表明本文提出的基于評分一致優(yōu)化協(xié)同過濾算法的預(yù)測準(zhǔn)確率相對于傳統(tǒng)的協(xié)同過濾算法,可以獲得更好的推薦質(zhì)量。

[1] 王國霞,劉賀平.個性化推薦系統(tǒng)綜述[J].計算機(jī)工程與應(yīng)用,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] 游文,葉水生.電子商務(wù)推薦系統(tǒng)中的協(xié)同過濾推薦[J].計算機(jī)技術(shù)與發(fā)展,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] 奉國和,梁曉婷.協(xié)同過濾推薦研究綜述[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日

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

衛(wèi)澤,男,碩士,研究方向:推薦算法,數(shù)據(jù)挖掘。周登文,男,碩士生導(dǎo)師,研究方向:計算機(jī)視覺,圖像處理。

TP301.6

10.3969/j.issn.1672-9722.2017.04.003