衛(wèi) 澤 周登文

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

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

衛(wèi) 澤 周登文

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

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

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

1 引言

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

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

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

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

在協(xié)同過(guò)濾推薦算法中,用戶評(píng)分?jǐn)?shù)據(jù)包含m個(gè)用戶的集U={u1,u2,…,um}和n個(gè)項(xiàng)目的集合I={i1,i2,…,in},用戶對(duì)項(xiàng)目的評(píng)分?jǐn)?shù)據(jù)可表示為矩陣R(m,n),如表1所示。

表1 用戶-項(xiàng)目評(píng)分矩陣R(m,n)

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

2.1 相似度的計(jì)算

1) 余弦相似性(Cosine Correlation)

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

(1)

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

修正余弦相似性相對(duì)余弦相似性考慮了用戶評(píng)分尺度問(wèn)題,可表示為如下公式:

(2)

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

(3)

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

2.2 預(yù)測(cè)評(píng)分并產(chǎn)生推薦

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

(4)

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

3.1 問(wèn)題描述

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

3.2 用戶相似性

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

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

(5)

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

3.3 相似性鄰居的選取

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

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

(6)

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

4 實(shí)驗(yàn)結(jié)果及分析

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

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

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

4.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

(7)

4.3 仿真分析

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

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

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

5 結(jié)語(yǔ)

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

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

[1] 王國(guó)霞,劉賀平.個(gè)性化推薦系統(tǒng)綜述[J].計(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é)同過(guò)濾推薦[J].計(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] 奉國(guó)和,梁曉婷.協(xié)同過(guò)濾推薦研究綜述[J].圖書(shū)情報(bào)工作,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日

國(guó)家自然科學(xué)基金項(xiàng)目(編號(hào):61372184);北京市自然科學(xué)基金項(xiàng)目(編號(hào):4162056)資助。

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

TP301.6

10.3969/j.issn.1672-9722.2017.04.003