荊笑鵬　劉京菊

(電子工程學院　合肥　230037)

?

微博網(wǎng)絡中基于社區(qū)的分布式協(xié)同過濾推薦*

荊笑鵬劉京菊

(電子工程學院合肥230037)

為實現(xiàn)可以應用于微博網(wǎng)絡中大規(guī)模數(shù)據(jù)的話題推薦,提出一種基于社區(qū)的分布式協(xié)同過濾推薦算法。定義了微博中用戶對話題評分的含義,包含了常見的用戶對微博的操作類型。在社區(qū)的基礎上針對有無歷史數(shù)據(jù)提出兩種預測評分的計算方法,對不同的用戶類型采用不同的推薦策略。以社區(qū)為單位設計粗粒度的分布式結(jié)構(gòu),在具體的計算過程中,應用MapReduce架構(gòu)進行細粒度的分布式計算,在提高了算法效率的同時,增加了推薦話題的覆蓋度。實驗結(jié)果表明,該算法具有一定的實際應用價值。

社區(qū); 分布式算法; 協(xié)同過濾; 用戶相似度

Class NumberTP391

1　引言

有許多方法可以實現(xiàn)個性化推薦,這些方法可以分為：基于內(nèi)存的方法、基于協(xié)同過濾的方法和混合方法。傳統(tǒng)的基于協(xié)同過濾的方法將用戶的評價歷史作為預測用戶對項目興趣大小的基礎。然而,這種方法存在以下問題： 1) 需要其他用戶對推薦項目的評分作為參考。 2) 具有較高的復雜度,無法適應大規(guī)模的數(shù)據(jù) 3) 冷啟動問題。即難以對新用戶產(chǎn)生合適的推薦。

針對上述問題,本文提出一種基于社區(qū)的協(xié)同過濾推薦算法。與傳統(tǒng)的推薦算法不同,這種算法利用社會網(wǎng)絡中用戶的社區(qū)結(jié)構(gòu)做出推薦,社會網(wǎng)絡中用于劃分社區(qū)結(jié)構(gòu)的方法是基于相似度的社區(qū)發(fā)現(xiàn)算法。本文的主要貢獻是： 1) 引入一種以用戶的社會網(wǎng)絡和用戶-話題評分數(shù)據(jù)作為基礎計算得到的預測評分矩陣； 2) 提出一種大規(guī)模微博網(wǎng)絡數(shù)據(jù)條件下的分布式協(xié)同過濾推薦算法； 3) 使用Twitter數(shù)據(jù)集評估這種算法的效果。

2　相關(guān)工作

協(xié)同過濾推薦方法的主要思想是,利用已有用戶群過去的行為或意見預測當前用戶最可能喜歡哪些項目。通常,協(xié)同過濾方法可以分為以下三種：

1) 基于內(nèi)存的協(xié)同過濾?；趦?nèi)存的協(xié)同過濾[1]使用全部的用戶-項目數(shù)據(jù)集,用評分矩陣來存儲相應的數(shù)據(jù),根據(jù)評分矩陣產(chǎn)生相應的推薦。這種方法可以分為兩種：即基于用戶的協(xié)同過濾[2]和基于項目的協(xié)同過濾[3]。

2) 基于模型的協(xié)同過濾?；谀Ｐ偷膮f(xié)同過濾從訓練數(shù)據(jù)中識別和抽取一些用于推薦的復雜模式,然后選擇合適的模式對測試數(shù)據(jù)或是真實世界的數(shù)據(jù)執(zhí)行協(xié)同過濾推薦。基于模型的協(xié)同過濾推薦包括潛在語義模型模型[4]、馬爾科夫模型[5]和矩陣分解模型[6]等。

3) 混合協(xié)同過濾?；旌贤扑]模型[7]通常將協(xié)同過濾推薦和其他推薦方法組合使用,目的在于克服協(xié)同過濾推薦的問題,提高預測和推薦的可擴展性和質(zhì)量?；旌蠀f(xié)同過濾通常分為兩部分：第一部分對數(shù)據(jù)進行預處理；第二部分設計不同推薦方法的組合規(guī)則。

3　微博網(wǎng)絡中基于社區(qū)的分布式協(xié)

同過濾推薦算法

3.1基于相似度的社區(qū)發(fā)現(xiàn)算法

本文所使用的基于相似度的社區(qū)發(fā)現(xiàn)算法是基于局部模塊度進行優(yōu)化,與使用全局模塊度相比,大大減小了時間復雜度,能夠花費較少的時間,有效地計算出大規(guī)模社會網(wǎng)絡的社區(qū)結(jié)構(gòu)。模塊度表示的是社區(qū)結(jié)構(gòu)是隨機產(chǎn)生的可能性,模塊度越大,說明社區(qū)的聚合度越高,社區(qū)結(jié)構(gòu)越明顯。

3.2相關(guān)定義

在微博網(wǎng)絡中,沒有用戶對話題、事件的評分功能,用戶能夠進行的操作是發(fā)布一個狀態(tài)或者一個話題,或者對好友發(fā)布的狀態(tài)或者是話題進行評論或者轉(zhuǎn)發(fā)。Carmagnola等[8]提出用戶關(guān)注的話題或采取的操作,能夠體現(xiàn)出社區(qū)結(jié)構(gòu)對當前用戶節(jié)點的影響,而吸引用戶的話題和事件能夠增加用戶之間的交流次數(shù)。用戶在微博網(wǎng)絡中的操作類型和操作次數(shù)代表了用戶的個性和關(guān)注的熱點。因而,通過對用戶的操作類型和操作次數(shù)的量化分析,可以得到與用戶-項目評分矩陣類似的評價矩陣。在此基礎上,應用協(xié)同過濾的推薦算法,能夠獲得用戶最關(guān)心的話題或者事件。

(1)

其中,Operation(u,m)表示u對m所做的操作類型,N(ou,m)表示操作類型ou,m的次數(shù)。

3.3基于社區(qū)的協(xié)同過濾推薦策略

1) 兩種預測評分的計算方法

對于新用戶,由于沒有足夠的信息支撐傳統(tǒng)的協(xié)同過濾推薦算法,因此會產(chǎn)生冷啟動問題[9]。這種情況下,如果用戶有社會網(wǎng)絡的信息,就可以通過抽取用戶的社區(qū)結(jié)構(gòu)信息幫助實現(xiàn)推薦。例如,對于金融圈中新加入的一個人而言,如果這個人經(jīng)?；钴S于微博網(wǎng)絡,那么就可以利用其微博的社會網(wǎng)絡信息產(chǎn)生一些關(guān)于金融的話題推薦。我們認為一個人的喜好和他的朋友是相似的,或者容易受到他的朋友的影響。使用基于相似度的社區(qū)發(fā)現(xiàn)算法劃分圖G的社區(qū)結(jié)構(gòu),得到{C1,C2,…,Ck}表示得到k個社區(qū)。下一步將根據(jù)式(1)計算得到的用戶-話題評分數(shù)據(jù)按照社區(qū)進行劃分,如果一個用戶屬于社區(qū)Ci,那么這個用戶對話題的所有評分都被劃分到社區(qū)Ci中。然后,針對不同的用戶使用不同的方法計算預測評分矩陣。

(2)

另一個預測評分矩陣使用基于用戶的協(xié)同過濾算法,社區(qū)Ci中,用戶a和b的相似度可以用式(3)來表示。

(3)

(4)

其中,sim(d,c,Ci)表示社區(qū)Ci中用戶c和d的相似度。

2) 面向新用戶的推薦策略

對于一個沒有相關(guān)話題評分的新用戶v,推薦策略分為以下三步：(1)尋找用戶v所屬的社區(qū)C。(2)在社區(qū)C中,按照式(2)計算話題的預測評分矩陣pv(C)。(3)對不同話題的評分結(jié)果進行排序,將評分結(jié)果最高的N個話題推薦給用戶v。

3) 面向歷史用戶的推薦策略

在面向歷史用戶推薦的時候,一方面,使用式(2)計算得到的話題預測評分進行推薦,推薦一些這些用戶沒有談論過的話題,提高推薦話題的覆蓋度；另一方面,使用式(4)計算得到的話題預測評分進行推薦,獲得更加精確的推薦結(jié)果。對于在社區(qū)C中的用戶u,對話題z的評分預測值按照下式計算：

p(u,z,C)=λpv(u,z,C)+(1-λ)pcu(u,z,C)

(5)

其中,0≤λ≤1,本文中,λ的取值為0.5。對按照式(5)計算出的不同話題的評分預測值進行排序,將評分結(jié)果最高的N個話題推薦給用戶u。

3.4算法過程

本文提出的分布式協(xié)同過濾推薦算法基于以下假設：每個社區(qū)之間是相互獨立的。本文的算法可以同時運行k個作業(yè),每個作業(yè)對應一個社區(qū),有不同的輸入數(shù)據(jù)。本文算法的完整計算過程如圖1所示。

圖1　基于社區(qū)的分布式協(xié)同過濾推薦算法流程

本文算法包含三個主要的計算過程： 1) 計算社區(qū)C中話題的平均評分； 2) 計算社區(qū)C中的用戶相似度； 3) 計算社區(qū)C中用戶對話題的評分。算法的分布式結(jié)構(gòu)通過MapReduce架構(gòu)實現(xiàn)。

1) 計算社區(qū)C中話題的平均評分

此過程用戶-話題評價數(shù)據(jù)用三元組〈u,x,pu,x,C〉表示,即社區(qū)C中用戶u對話題x的評分是pu,x,C,這種表示方法可以克服用戶-話題評價數(shù)據(jù)的稀疏性。話題的平均評分定義如式(6)所示。

(6)

其中,m表示社區(qū)C中,對話題有評分記錄的用戶的個數(shù),計算得到的結(jié)果可以用二元組〈x,pv(x,C)〉表示。使用MapReduce實現(xiàn)話題平均評分的過程如下：Mapavg使用用戶-話題評價數(shù)據(jù)〈u,x,pu,x,C〉作為輸入,把話題x當作key,把評分pu,x,C當作value,消除了數(shù)據(jù)中關(guān)于用戶的部分,使得相同話題的數(shù)據(jù)被重組到同一臺機器。Reduceavg使用話題和與話題對應的評價數(shù)據(jù)計算每個話題的平均評價值,輸出話題和其平均評價值〈x,pv(x,C)〉。

2) 計算社區(qū)C中的用戶相似度

此過程使用MapReduce實現(xiàn)用戶相似度計算的過程如下：Mapsim1使用用戶-話題評價數(shù)據(jù)〈u,x,pu,x,C〉作為輸入,把話題作為key,用戶和評分的二元組〈u,pu,x,C〉作為value,使得所有屬于同一話題的數(shù)據(jù)被重組到同一臺機器。Reducesim1把社區(qū)C中每個話題的〈u,pu,x,C〉作為輸入,輸出此話題的所有評分項〈u,pu,x,C〉。Mapsim2使用Reducesim1的輸出作為輸入,即〈x,list(u,pu,x,C)〉,移除話題部分,輸出時把用戶對作為key,對應的評分對序列作為value,輸出的用戶對是評價了同一話題的。將用戶對作為key使得那些同時評價了相同話題的所有用戶被重組到同一臺機器。Reducesim2的輸入將用戶對作為key,對應的評分對序列作為value。Reducesim2計算用戶之間相似度,輸出時將用戶對作為key,將用戶對的相似度作為value,即〈u1,u2,sim(u1,u2,C)〉。

3) 計算社區(qū)C中用戶對話題的評分

此過程同時使用用戶-話題評價數(shù)據(jù)和上一過程得到的用戶之間的相似度數(shù)據(jù),具體計算過程如下：Mapp1把〈u,x,pu,x,C〉和〈u1,u2,sim(u1,u2,C)〉作為輸入,輸出時將用戶作為key,使得同一用戶的所有數(shù)據(jù)被重組到同一臺機器。Reducep1使用用戶和其對應的〈x,pu,x,C〉序列或者〈u2,sim(u1,u2,C)〉序列作為輸入數(shù)據(jù),輸出〈u1,x,pu,x,C,list(u2,sim(u1,u2,C))〉,這里的u2是與u1相似的用戶。Mapp2的輸出以用戶作為key,Reducep2的輸入以用戶為key,以話題、相似用戶對的所有評分和用戶之間的相似度作為value,即〈x,pu,x,C,list(u2,sim(u1,u2,C))〉。Reducep2對用戶沒有評分的話題計算評分預測值,輸出〈u,x,pcu(u,x,C)〉。

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

本文實驗使用真實的Twitter網(wǎng)絡數(shù)據(jù)集來檢驗提出的算法的效率和有效性。Twitter數(shù)據(jù)集來自于斯坦福大學公開的用于學術(shù)研究的數(shù)據(jù)集(snap.stanford.edu/data/),實驗使用這個數(shù)據(jù)集中2000個用戶和323000條Tweets,其中每條Tweets包含作者id、時間和內(nèi)容,Tweets類型包括發(fā)表、評論和轉(zhuǎn)發(fā)。實驗使用三臺配置為IntelCorei7-4770的處理器和8GB內(nèi)存的臺式計算機上,每臺機器上配置運行單核心,內(nèi)存為2G的虛擬機,運行CentOS操作系統(tǒng)。

為檢驗分布式算法的執(zhí)行性能,實驗使用加速比[10]作為評價算法并行運行性能的指標。其定義如下：

(7)

其中,Ts表示單個核心的處理器順序執(zhí)行算法所花費的時間,Tp表示p個核心的處理器并行運行算法所花費的時間。實驗結(jié)果如圖2所示,結(jié)果顯示隨著并行的節(jié)點的數(shù)量增加,加速比同時在增加,增加程度低于理想情況,主要原因在于經(jīng)過劃分得到的社區(qū)結(jié)構(gòu)不均衡。圖3顯示的是本文算法與基于用戶的協(xié)同過濾推薦算法(對比算法)的運行時間?？梢钥闯?本文算法的運行時間遠遠低于基于用戶的協(xié)同過濾推薦算法。

圖2　本文算法的加速比

圖3　基于用戶的協(xié)同過濾推薦算法(對比算法)與本文算法的運行時間

為檢驗分布式算法的推薦話題的多樣性,實驗使用覆蓋度[11]作為評價指標,其定義如下：

(8)

其中,No表示可供推薦的話題的數(shù)量,Ns表示預測推薦話題的數(shù)量。圖4顯示本文算法與基于用戶的協(xié)同過濾推薦算法(對比算法)在不同實驗次數(shù)的條件下,所產(chǎn)生的話題覆蓋度?？梢钥闯?在將微博網(wǎng)絡劃分為社區(qū)和綜合使用兩種預測方法的情況下,本文算法具有相對較高的話題覆蓋度。

圖4　基于用戶的協(xié)同過濾推薦算法(對比算法)與本文算法的話題覆蓋度

5　結(jié)語

本文在分析了微博中的各類操作后,定義了用戶對話題評分的計算方法。為解決傳統(tǒng)協(xié)同過濾推薦算法具有冷啟動和較低的時間效率的問題,本文提出了微博網(wǎng)絡中基于社區(qū)的分布式協(xié)同過濾推薦算法。針對冷啟動問題,本文算法綜合使用兩種話題評分預測方法,在緩解冷啟動問題的同時,提高了推薦話題的覆蓋率。針對時間效率的問題,本文算法結(jié)合MapReduce的框架,提出一種分布式的協(xié)同過濾推薦算法,最后實驗表明,本文算法在實際網(wǎng)絡上運行時,在冷啟動問題和時間效率問題上表現(xiàn)出了良好的性能。

[1] 趙琴琴.基于內(nèi)存的協(xié)同過濾推薦算法研究[D].北京:中國科學院研究生院,2011.

ZHAO Qinqin. Research on memory based collaborative filtering recommendation algorithm[D]. Beijing: University of Chinese Academy of Sciences,2011.

[2] Zhao Z D, Shang M S. User-based collaborative-filtering recommendation algorithms on hadoop[C]//Knowledge Discovery and Data Mining, 2010. WKDD’10. Third International Conference on. IEEE,2010:478-481.

[3] Sarwar B, Karypis G, Konstan J, et al. Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th international conference on World Wide Web. ACM,2001:285-295.

[4] Hofmann T. Latent semantic models for collaborative filtering[J]. ACM Transactions on Information Systems (TOIS),2004,22(1):89-115.

[5] Sahoo N, Singh P V, Mukhopadhyay T. A Hidden Markov Model for Collaborative Filtering[J]. Ssrn Electronic Journal,2010,36(4):1329-1356.

[6] Pirasteh P, Hwang D, Jung J J. Exploiting matrix factorization to asymmetric user similarities in recommendation systems[J]. Knowledge-Based Systems,2015,83:51-57.

[7] Fiasconaro A, Tumminello M, Nicosia V, et al. Hybrid recommendation methods in complex networks[J]. Physical Review E,2015,92(1):012-811.

[8] Carmagnola F, Vernero F, Grillo P. SoNARS: A Social Networks-Based Algorithm for Social Recommender Systems[J]. User Modeling Adaptation & Personalization,2009,5535:223-234.

[9] Fatemi M, Tokarchuk L. A Community Based Social Recommender System for Individuals & Groups[C]//Social Computing(Social Com), 2013 International Conference on. IEEE,2013:351-356.

[10] Jiang J, Lu J, Zhang G, et al. Scaling-Up Item-Based Collaborative Filtering Recommendation Algorithm Based on Hadoop[C]//Proceedings of the 2011 IEEE World Congress on Services. IEEE Computer Society,2011:490-497.

[11] Ge M, Delgado-Battenfeld C, Jannach D. Beyond accuracy:evaluating recommender systems by coverage and serendipity[C]//Proceedings of the fourth ACM conference on Recommender systems. ACM,2010:257-260.

Community Based Distributed Collaborative Filtering Recommendation in Microblog Network

JING XiaopengLIU Jingju

(Electronic Engineering Institute, Hefei230037)

To better meet the application requirements of topics recommendation in large-scale microblog network data,this paper proposed a community based distributed collaborative filtering recommendation algorithm. The algorithm defines the meaning of the topic of user rating in the microblog,containing the common users operation type in the microblog. The algorithm proposes two calculation methods of predictions ratings for the presence or absence of historical data on the basis of the community. These allow for different types of users with different recommended strategies. The algorithm designs coarse-grained distributed architecture on the basis of communities and applies fine-grained distributed architecture of the MapReduce. It improves the efficiency of the algorithm,while increasing the coverage of recommended topics. Experimental results show that the algorithm has some practical value.

community, distributed algorithms, collaborative filtering, users similarity

2016年4月7日,

2016年5月26日

荊笑鵬，男，碩士研究生，研究方向：數(shù)據(jù)挖掘，網(wǎng)絡安全。劉京菊，女，碩士，副教授，研究方向：數(shù)據(jù)挖掘，網(wǎng)絡安全。

TP391

10.3969/j.issn.1672-9722.2016.10.025