基于二部分圖網(wǎng)絡(luò)結(jié)構(gòu)推薦的改進(jìn)算法

, ,

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

基于二部分圖網(wǎng)絡(luò)結(jié)構(gòu)推薦的改進(jìn)算法

鄧 松,邱靜,陳軍華*

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海200234)

介紹了一種基于網(wǎng)絡(luò)結(jié)構(gòu)推薦的改進(jìn)算法.在標(biāo)準(zhǔn)物質(zhì)擴(kuò)散算法的基礎(chǔ)上,考慮到用戶的評分對推薦商品的影響,對推薦算法中初始資源分配矢量和資源轉(zhuǎn)移矩陣進(jìn)行了改進(jìn),增加了調(diào)節(jié)因子.使用來源于GroupLens網(wǎng)站上的訓(xùn)練集數(shù)來評價這個推薦算法的性能,從而進(jìn)行了一系列的實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明,該算法比傳統(tǒng)的協(xié)同過濾系統(tǒng)、基于網(wǎng)絡(luò)結(jié)構(gòu)的推薦系統(tǒng)和帶有權(quán)重的基于網(wǎng)絡(luò)結(jié)構(gòu)的推薦系統(tǒng)具有更好的推薦精度和更高的命中率,解決了標(biāo)準(zhǔn)物質(zhì)擴(kuò)散算法當(dāng)中的冷啟動問題和可擴(kuò)展性問題,使得推薦結(jié)果具有多樣性.

推薦算法; 物質(zhì)擴(kuò)散算法; 冷啟動問題; 可擴(kuò)展性問題; 推薦多樣性

0 緒 論

隨著互聯(lián)網(wǎng)技術(shù)日新月異的革新,全世界的網(wǎng)頁服務(wù)器總數(shù)不斷增加,網(wǎng)頁的數(shù)量也因此呈現(xiàn)爆炸性的增長趨勢[1].互聯(lián)網(wǎng)上出現(xiàn)越來越多的暗信息,但是對人們有作用的信息,也越來越難以被發(fā)現(xiàn).由此,諸如Google、百度和bing等搜索引擎[2]應(yīng)運(yùn)而生.但是搜索引擎需要用戶能夠明確自己的需求,輸入關(guān)鍵字,所以反饋的信息都限制在用戶已知的信息范圍中,而不能幫助用戶找到其不知道但有價值或感興趣的內(nèi)容.

推薦系統(tǒng)能夠從一定程度上彌補(bǔ)搜索引擎的缺陷[3],相較于傳統(tǒng)的搜索引擎,推薦系統(tǒng)分析用戶的歷史操作,建立了用戶偏好模型,依靠算法計算預(yù)測用戶對未知商品的偏好權(quán)重,并根據(jù)權(quán)重對商品排序,向用戶推送一個可能令其感興趣的商品推薦列表[4].推薦系統(tǒng)所采用的算法技術(shù)可以被分為兩大主類:基于內(nèi)容的推薦算法[5-6]和協(xié)同過濾算法[7-8].迄今為止,協(xié)同過濾算法是推薦系統(tǒng)中使用最成功、最廣泛的算法[8].

基于網(wǎng)絡(luò)結(jié)構(gòu)的推薦算法[9-14]不考慮用戶和產(chǎn)品的內(nèi)容特征,而僅僅把它們看成抽象的節(jié)點(diǎn),所有算法利用的信息都藏在用戶和產(chǎn)品的選擇關(guān)系之中.這些算法效果明顯好于經(jīng)典的協(xié)同過濾算法.但目前這些推薦系統(tǒng)還存在下列問題:

1) 缺乏個性化的推薦.因?yàn)橥扑]系統(tǒng)的不夠完善,算法不精確,導(dǎo)致很多信息被籠統(tǒng)粗放地推薦給用戶,缺乏個性化,致使用戶得到的并不是其感興趣的產(chǎn)品;

2) 推薦的自動化程度低.用戶進(jìn)行人機(jī)交互時,告知系統(tǒng)自己的信息和感興趣的產(chǎn)品,但是由于系統(tǒng)更新不及時或延時效應(yīng)等原因,產(chǎn)生了推薦效果不佳的情況;

3) 推薦的持久性程度低.由于大部分系統(tǒng)不能有效地利用用戶的歷史查找數(shù)據(jù),只依賴當(dāng)前的推薦信息,這樣勢必導(dǎo)致推薦持久力的下降;

4) 推薦策略單一.推薦系統(tǒng)在進(jìn)行推薦時,對運(yùn)用多種推薦策略缺乏考慮,不能將各種推薦算法的優(yōu)點(diǎn)進(jìn)行結(jié)合,多數(shù)情況下只是選擇某種單一的推薦策略,如基于內(nèi)容的搜索或基于分類瀏覽點(diǎn)擊的檢索,這將導(dǎo)致推薦的單一性.

1 相關(guān)技術(shù)基礎(chǔ)

根據(jù)推薦算法的不同,推薦系統(tǒng)可以分為如下幾類:協(xié)同過濾系統(tǒng),基于內(nèi)容的推薦系統(tǒng),混合推薦系統(tǒng)[13]以及最近興起的基于用戶—產(chǎn)品二部分圖網(wǎng)絡(luò)結(jié)構(gòu)的推薦系統(tǒng).

1.1協(xié)同過濾算法

協(xié)同過濾算法通過以下公式[5]計算用戶ui和用戶uj之間的相似性:

(1)

(2)

對任意用戶ui,所有aij=0的非零預(yù)測得分vij都按照降序排列,排在最前面的那些項(xiàng)目會被推薦給用戶.

1.2基于內(nèi)容的推薦算法

最初基于內(nèi)容的推薦算法是協(xié)同過濾技術(shù)的延續(xù)與發(fā)展,它不需要依據(jù)用戶對項(xiàng)目的評價意見,而是依據(jù)用戶已經(jīng)選擇的產(chǎn)品內(nèi)容信息計算用戶之間的相似性,從而進(jìn)行相應(yīng)的推薦.隨著機(jī)器學(xué)習(xí)等技術(shù)的完善,當(dāng)前的基于內(nèi)容的推薦系統(tǒng)可以分別對用戶和產(chǎn)品建立配置文件[5],通過分析已經(jīng)購買(或?yàn)g覽)過的內(nèi)容,建立或更新用戶的配置文件.系統(tǒng)可以比較用戶與產(chǎn)品配置文件的相似度,并直接向用戶推薦與其配置文件最相似的產(chǎn)品.例如,在電影推薦中,基于內(nèi)容的系統(tǒng)首先分析用戶已經(jīng)看過的打分比較高的電影共性(演員、導(dǎo)演、風(fēng)格等)[6],再推薦與這些用戶感興趣的電影內(nèi)容相似度高的其他電影.基于內(nèi)容的推薦算法的根本在于信息獲取和信息過濾.因?yàn)樵谖谋拘畔@取與過濾方面的研究較為成熟,現(xiàn)有很多基于內(nèi)容的推薦系統(tǒng)都是通過分析產(chǎn)品的文本信息進(jìn)行推薦.

1.3物質(zhì)擴(kuò)散推薦算法

物質(zhì)擴(kuò)散算法行為類似于隨機(jī)游走過程的資源分配過程[11],基于用戶—商品二部分圖,假設(shè)每個商品都具有一定數(shù)量的某種推薦能力,即用戶選擇過的商品都有某種向該用戶推薦其他商品的抽象能力,商品占有資源并把更多資源傳遞給自己更偏好的商品.

由于二部分圖本身是無權(quán)網(wǎng)絡(luò),X節(jié)點(diǎn)中的資源將平均分配到在各個Y節(jié)點(diǎn)中的鄰居,同理,Y節(jié)點(diǎn)中的資源也將平均分配到各個X節(jié)點(diǎn)中的鄰居.以圖1(a)為例,3個X節(jié)點(diǎn)的初始推薦力資源為a,b,c,資源分配過程為:首先,X節(jié)點(diǎn)中的初始化資源根據(jù)二部分圖的連接關(guān)系傳遞到Y(jié)節(jié)點(diǎn),傳遞過程類似于物質(zhì)擴(kuò)散的過程,節(jié)點(diǎn)根據(jù)自身的度(與該節(jié)點(diǎn)的連邊)大小而將資源稀釋,例如a的度數(shù)為2,則每條邊的終點(diǎn)將會得到a/2;然后Y節(jié)點(diǎn)中積累的資源,又從Y節(jié)點(diǎn)傳遞回到X節(jié)點(diǎn),分配原理與前一步相同.兩個集合通過之間的共同連接關(guān)系,實(shí)現(xiàn)了資源的再分配,節(jié)點(diǎn)的度越大,與它相關(guān)的連邊傳遞的能量越小.兩個過程的資源傳遞如圖1(b)和圖1(c)所示.

圖1 二部分圖的資源分配流程

最終分配到3個X節(jié)點(diǎn)的資源為x,y,z,式(3)表示的是最終資源和原資源的矩陣映射關(guān)系:

(3)

其中,矩陣是列歸一化的權(quán)重鄰接矩陣.假設(shè)推薦系統(tǒng)中有M個用戶和N種商品,則二部分圖有M+N個節(jié)點(diǎn),用戶集合X={x1,x2,…,xm},商品集合Y={y1,y2,…,yn},E為用戶歷史消費(fèi)記錄集合,假設(shè)用戶xi選擇過的所有產(chǎn)品,都具有某種向xi推薦其他產(chǎn)品的能力.這個抽象的能力可以看作位于相關(guān)產(chǎn)品上的某種可分的資源——擁有資源的產(chǎn)品會把更多的資源交給自己更青睞的產(chǎn)品.如果用戶xi購買、選擇或評價過商品yk,則xiyk∈E.xi的初始資源為f(xi)≥0,第一步從X集合傳遞到Y(jié)集合的推薦力資源,則商品yk的資源為式(4):

(4)

k(xi)是用戶xi的用戶度,{aik}是一個M×N的矩陣,如式(5)可以描述用戶xi和商品yk是否具有選擇關(guān)系:

(5)

即若用戶xi選擇了商品yk,則aik=1,否則aik=0.

第二步推薦力資源由Y集合傳遞回X集合,則用戶xi的資源可以表示為式(6):

(6)

通過兩步物質(zhì)擴(kuò)散,xj到xi的資源貢獻(xiàn)可以表示為:

(7)

其中

(8)

資源分配矩陣為W={wij}n×n,wij是j的初始資源傳遞到i的比例,是原集合資源的最終分配形式,可以認(rèn)為是節(jié)點(diǎn)j對于節(jié)點(diǎn)i的重要性,即商品j對于商品i的貢獻(xiàn)度,也即產(chǎn)品j愿意分配給產(chǎn)品i的資源配額.W是非對稱矩陣,對角線元素大于0.假設(shè)對于特定的用戶xi定義用戶歷史消費(fèi)記錄的n維0/1 個性化矢量f,xi選擇過的商品資源分配初始化為單位量1,其余的為 0,即f(yj)=aji,f代表了針對該用戶的初始資源分配結(jié)構(gòu),具有個性化的特點(diǎn),對于不同的用戶,初始化矢量f是不同的.最終資源分配向量為f′,f′=wf,式(9)為f′的組成元素f′(yj):

(9)

最后將用戶xi所有沒有選擇的商品yj(1≤j≤m,aji=0)進(jìn)行降序排列,推薦最終資源最多的商品.

2 考慮用戶對商品評分的改進(jìn)算法

標(biāo)準(zhǔn)物質(zhì)擴(kuò)散算法中,任意一個用戶收集的產(chǎn)品都被賦予了相同的權(quán)重.盡管算法可以得到比協(xié)同過濾算法更高的準(zhǔn)確率,但是將所有產(chǎn)品一視同仁的做法并沒有考慮用戶對產(chǎn)品的評分對推薦效果的影響.許多推薦系統(tǒng)都允許用戶對購買或者瀏覽過的項(xiàng)目進(jìn)行評分,所以推薦系統(tǒng)也可以看成是一個評分系統(tǒng)[10,14],比如Yahoo的音樂推薦系統(tǒng),允許用戶對音樂評5個星級.評分越高說明用戶越喜歡該音樂.基于網(wǎng)絡(luò)結(jié)構(gòu)的推薦算法只是判斷用戶是否選擇過項(xiàng)目,不區(qū)分高低評分對推薦結(jié)果的影響,然而用戶的評分一定程度上表示了用戶對項(xiàng)目的喜好程度,不區(qū)分高低分可能會造成信息的損失[16-18],有些推薦算法直接忽略低分,在5分的推薦系統(tǒng)中,當(dāng)且僅當(dāng)用戶對項(xiàng)目的評分大于等于3才認(rèn)為用戶選擇過項(xiàng)目.但是用戶對項(xiàng)目評分時有可能受當(dāng)時環(huán)境等因素的影響,而且低分同樣包含著一些信息,如用戶關(guān)注過該項(xiàng)目,所以不應(yīng)該直接去掉低分[11].

在本課題研究的改進(jìn)算法中要區(qū)分高分和低分,即用戶對項(xiàng)目的喜好,首先考慮的是,對于用戶評分的平均分高的商品,說明用戶對它的喜愛程度普遍高,則在初始資源分配時,就不應(yīng)該跟其他平均評分低的商品獲得一樣的資源,故可以改進(jìn)標(biāo)準(zhǔn)物質(zhì)擴(kuò)散算法中的初始資源分配矢量為式(10):

(10)

改進(jìn)的算法中的另一個改進(jìn)點(diǎn)就是對資源轉(zhuǎn)移矩陣Wij的改進(jìn),同樣是考慮用戶對商品的評分對推薦算法的影響,改進(jìn)的資源轉(zhuǎn)移矩陣為:

(11)

通過物質(zhì)擴(kuò)散算法的資源轉(zhuǎn)移過程,可以得到最終商品獲得的推薦資源矢量為:

(12)

3 實(shí)驗(yàn)評價

3.1算法評價標(biāo)準(zhǔn)

為了評價算法的性能,采用基準(zhǔn)數(shù)據(jù)集set-MovieLens進(jìn)行測試,這個數(shù)據(jù)集被廣泛的應(yīng)用于測試推薦算法的效率.該數(shù)據(jù)集可以從Netflix網(wǎng)站上下載,它包含了1 837個用戶對3 952部電影的評分?jǐn)?shù)據(jù),數(shù)據(jù)量達(dá)到了3×105.每個用戶對電影的評分離散的分為1～5分5個等級.這個數(shù)據(jù)集被隨機(jī)分為兩個部分:其中80%的數(shù)據(jù)用于做訓(xùn)練集,20%的數(shù)據(jù)用戶做測試集.

包括協(xié)同過濾、基于內(nèi)容的推薦算法、標(biāo)準(zhǔn)的物質(zhì)擴(kuò)散算法和改進(jìn)的考慮用戶評分的二部分圖網(wǎng)絡(luò)結(jié)構(gòu)在內(nèi)的所有算法,都能夠給用戶提供一個未評分的有序的電影隊(duì)列.對于任意用戶ui,如果用戶-項(xiàng)目(ui-oi)對在測試集中,則度量計算oj在有序隊(duì)列中的位置.例如,如果用戶ui未評分的電影有1 000部,而oj排在前面第10位,oj排在前10/1 000位置,記為r(ij)=0.01.一個優(yōu)秀的推薦算法,r值越小,推薦能力越好[15].

3.2實(shí)驗(yàn)結(jié)果

電影評分表(表1)中,第一列表示用戶的ID,第二列表示用戶對電影的評分.這些評分?jǐn)?shù)據(jù)都是從原始數(shù)據(jù)集中進(jìn)行數(shù)據(jù)預(yù)處理得到的.

采用數(shù)據(jù)集的訓(xùn)練集和測試集,經(jīng)過了5次的交叉驗(yàn)證.最終得到用戶1的推薦列表如表2所示.

根據(jù)本算法和其他基于二部分圖網(wǎng)絡(luò)結(jié)構(gòu)的算法的比較結(jié)果如表3所示.

表1 電影1的評分表

表2 用戶1的推薦列表

表3 測試集中每一個入口的預(yù)測平均位置

如表3所示、根據(jù)協(xié)同過濾算法、基于內(nèi)容的推薦算法、標(biāo)準(zhǔn)物質(zhì)擴(kuò)散算法和考慮用戶對商品評分的改進(jìn)算法的位置值的平均值分別為0.126、0.124、0.121和0.118.很明顯,考慮用戶對商品評分的改進(jìn)算法具有最好的預(yù)測精度.

4 結(jié) 論

實(shí)驗(yàn)結(jié)果證明,所提出的算法能提高算法預(yù)測精度.關(guān)于平均預(yù)測精度,本算法分別比協(xié)同過濾算法、基于內(nèi)容的推薦算法和標(biāo)準(zhǔn)的物質(zhì)擴(kuò)散算法增長了0.8%,0.6%和0.2%.

[1] 中國互聯(lián)網(wǎng)信息中心.互聯(lián)網(wǎng)發(fā)展與動態(tài) [EB/OL].[2015-10-22],http://www.cnnic.cn/hlwfzyj/hlwfzzx/201212/t20121217_38186.htm.

[2] 許海玲,吳瀟,李曉東,等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究 [J].軟件學(xué)報,2009,20(2):1-10.

Xu H L,Wu X,Li X D,et al.Comparison Study of Internet Recommendation System [J].Journal of Software,2009,2(2):350-362.

[3] 劉建國,周濤,汪秉宏.個性化推薦系統(tǒng)的研究進(jìn)展 [J].自然科學(xué)進(jìn)展,2009,19(1):1-15.

Liu J G,Zhou T,Wang B H.Research Progress of Personalized Recommendation System [J].Progress in Natural Science,2009,19(1):1-15.

[4] Yang M H,Gu Z M.Personalized recommendation based on partial similarity of interests [C].International Conference on Advanced Data Mining and Applications,2006,4093:509-516.

[5] Park H S,Yoo J O,Cho S B.A context-aware music recommendation system using fuzzy Bayesian networks with utility theory [C].Proceedings of the Third International Conference on Fuzzy Systems and Knowledge Discovery,Xi′an:ACM,2006.

[6] Chang Y I,Shen J H,Chen T I.A data mining-based method for the incremental update of supporting personalized information filtering [J].Journal of Information Science and Engineering,2008,24(1):129-142.

[7] Chen Y L,Cheng L C.A novel collaborative filtering approach for recommending ranked items [J].Expert Systems with Applications,2008,34(4):2396-2045.

[8] Liu J G,Wang B H,Guo Q.Improved collaborative filtering algorithm via information transformation [J].International Journal of Modern Physics C,2009,20(2):285-293.

[9] Liu J G,Zhou Tao,Che H A,et al.Effects of high-order correlations on Personaliz-ed recommendations for bipartite networks [J].Physica A,2010,389:881-886.

[10] Shang M S,Lyu L Y,Zhang Y C,et al.Empirical analysis of Web-based user-object bipartite networks [J].Europhysics Letters,2009,90(4):1303-1324.

[11] Zhou Tao,Kuscsik Z,Liu J G,et al.Solving the apparent diversity-accuracy dilemma of systems [C].Proceedings of National Academy of Sciences,2010,107(10):4511-4515.

[12] Wang Q,Duan S Y.Improved recommendation algorithm based on bipartite networks [J].Application Research of Computers,2013,30(3):771-775.

[13] Li Z,Wu X D,Peng H.Nonnegative matrix factorization on orthogonal subspace [J].Pattern Recognition Letters,2010,31(9):905-911.

[14] Zhang C J,Zeng A.Behavior patterns of online users and the effect on information filtering [J].Physica A,2012,391:1822-1830.

[15] Ma S C,Guan Y F.Improved recommendation algorithm based on bipartite networks [J].China Academic Journal Electronic Publishing House,2015,09(04):196-199.

(責(zé)任編輯：包震宇)

Animprovedrecommendedalgorithmfornetworkstructurebasedontwopartialgraphs

Deng Song,QiuJing,ChenJunhua*

(The College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai200234,China)

In this thesis,we introduce an improved algorithm based on network structure.Based on the standard material diffusion algorithm,considering the influence of the user′s score on the recommendation,the adjustment factor of the initial resource allocation vector and the resource transfer matrix in the recommendation algorithm is improved.Using the practical data set from GroupLens webite to evaluate the performance of the proposed algorithm,we performed a series of experiments.The experimental results reveal that it can yield better recommendation accuracy and has higher hitting rate than collaborative filtering,network-based inference.It can solve the problem of cold start and scalability in the standard material diffusion algorithm.And it also can make the recommendation results diversified.

recommendation algorithm; standard material diffusion algorithm; the problem of cold start; the problem of capability; recommended diversity

2015-12-22

鄧 松(1991-),男,碩士研究生,主要從事推薦算法方面的研究.E-mail:994946153@qq.com

導(dǎo)師簡介: 陳軍華(1968-),男,副教授,主要從事分布式數(shù)據(jù)庫及數(shù)據(jù)挖掘方面的研究.E-mail:chenjh@shnu.edu.cn

TP301.6

:A

:1000-5137(2017)04-0535-07

*