, ,

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

基于二部分圖網絡結構推薦的改進算法

鄧 松,邱靜,陳軍華*

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

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

推薦算法; 物質擴散算法; 冷啟動問題; 可擴展性問題; 推薦多樣性

0 緒 論

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

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

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

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

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

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

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

1 相關技術基礎

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

1.1協(xié)同過濾算法

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

(1)

(2)

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

1.2基于內容的推薦算法

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

1.3物質擴散推薦算法

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

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

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

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

(3)

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

(4)

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

(5)

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

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

(6)

通過兩步物質擴散,xj到xi的資源貢獻可以表示為:

(7)

其中

(8)

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

(9)

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

2 考慮用戶對商品評分的改進算法

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

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

(10)

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

(11)

通過物質擴散算法的資源轉移過程,可以得到最終商品獲得的推薦資源矢量為:

(12)

3 實驗評價

3.1算法評價標準

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

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

3.2實驗結果

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

采用數據集的訓練集和測試集,經過了5次的交叉驗證.最終得到用戶1的推薦列表如表2所示.

根據本算法和其他基于二部分圖網絡結構的算法的比較結果如表3所示.

表1 電影1的評分表

表2 用戶1的推薦列表

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

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

4 結 論

實驗結果證明,所提出的算法能提高算法預測精度.關于平均預測精度,本算法分別比協(xié)同過濾算法、基于內容的推薦算法和標準的物質擴散算法增長了0.8%,0.6%和0.2%.

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

[2] 許海玲,吳瀟,李曉東,等.互聯網推薦系統(tǒng)比較研究 [J].軟件學報,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].自然科學進展,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.

(責任編輯：包震宇)

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

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

TP301.6

:A

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

*