孟桓羽 劉 真 王 芳 徐家棟 張國(guó)強(qiáng)

1(北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 北京 100044)2(北京交通大學(xué)信息中心 北京 100044)3 (南京師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 210023)

?

基于圖和改進(jìn)K近鄰模型的高效協(xié)同過(guò)濾推薦算法

孟桓羽1劉 真1王 芳2徐家棟1張國(guó)強(qiáng)3

1(北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 北京 100044)2(北京交通大學(xué)信息中心 北京 100044)3(南京師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 210023)

(huanyum@bjtu.edu.cn)

在互聯(lián)網(wǎng)高速發(fā)展的今天，推薦系統(tǒng)已成為解決信息過(guò)載的有效手段，能夠緩解用戶在篩選感興趣信息時(shí)的困擾，幫助用戶發(fā)現(xiàn)有價(jià)值的信息.推薦系統(tǒng)中的協(xié)同過(guò)濾推薦算法，因其領(lǐng)域無(wú)關(guān)性及支持用戶發(fā)現(xiàn)潛在興趣的優(yōu)點(diǎn)被廣泛應(yīng)用.由于數(shù)據(jù)的規(guī)模過(guò)大且稀疏的特點(diǎn)，當(dāng)前協(xié)同過(guò)濾在算法實(shí)時(shí)性、推薦精確度等方面仍有較大提升空間.提出了GK-CF方法，通過(guò)建立基于圖的評(píng)分?jǐn)?shù)據(jù)模型，將傳統(tǒng)的協(xié)同過(guò)濾算法與圖計(jì)算及改進(jìn)的KNN算法結(jié)合.通過(guò)圖的消息傳播及改進(jìn)的相似度計(jì)算模型對(duì)用戶先進(jìn)行篩選再做相似度計(jì)算；以用戶-項(xiàng)目二部圖的節(jié)點(diǎn)結(jié)構(gòu)為基礎(chǔ)，通過(guò)圖的最短路徑算法進(jìn)行待評(píng)分項(xiàng)目的快速定位.在此基礎(chǔ)上，進(jìn)一步通過(guò)并行圖框架對(duì)算法進(jìn)行了并行化實(shí)現(xiàn)及優(yōu)化.在物理集群環(huán)境下進(jìn)行了實(shí)驗(yàn)，結(jié)果表明，與已有的協(xié)同過(guò)濾算法相比，提出的GK-CF算法能夠很好地提高推薦的準(zhǔn)確度和評(píng)分預(yù)測(cè)的準(zhǔn)確性，并具有較好的算法可擴(kuò)展性和實(shí)時(shí)性能.

協(xié)同過(guò)濾；社會(huì)網(wǎng)絡(luò)；圖模型；K近鄰；最短路徑

隨著信息技術(shù)和互聯(lián)網(wǎng)的快速發(fā)展，大眾對(duì)社會(huì)化網(wǎng)絡(luò)的參與和關(guān)注程度也越來(lái)越高，全球最大的社交網(wǎng)站Facebook的日用戶數(shù)量在2015年第4季度已經(jīng)突破10億，國(guó)內(nèi)的社交網(wǎng)站新浪微博日活躍用戶數(shù)也達(dá)到1億.據(jù)中國(guó)電子商務(wù)研究中心監(jiān)測(cè)數(shù)據(jù)顯示，截止2015年12月，國(guó)內(nèi)著名電商網(wǎng)站年度活躍用戶數(shù)增長(zhǎng)至1.536億，同比增長(zhǎng)70%.人們逐漸從信息匱乏的時(shí)代走入了信息過(guò)載的時(shí)代，用戶在海量信息中選擇自己可能感興趣的信息的難度也逐日增加.為了緩解用戶在篩選信息時(shí)的困擾，社會(huì)網(wǎng)絡(luò)推薦系統(tǒng)應(yīng)運(yùn)而生.據(jù)世界最大電商亞馬遜的統(tǒng)計(jì)，推薦系統(tǒng)對(duì)亞馬遜銷售額貢獻(xiàn)率在20%～30%.社交網(wǎng)絡(luò)推薦主要是指通過(guò)挖掘分析用戶在社交網(wǎng)絡(luò)中的社會(huì)關(guān)系或歷史興趣，結(jié)合推薦系統(tǒng)算法，對(duì)用戶進(jìn)行各種推薦.比如，通過(guò)挖掘用戶在社交網(wǎng)絡(luò)中的好友關(guān)系從而為用戶推薦新的可能感興趣的用戶或者項(xiàng)目.

隨著20世紀(jì)90年代協(xié)同過(guò)濾算法的提出，推薦系統(tǒng)已經(jīng)成為用戶用來(lái)對(duì)過(guò)量互聯(lián)網(wǎng)信息過(guò)濾的一種重要手段[1].作為推薦系統(tǒng)最重要且應(yīng)用最廣泛的一種推薦算法，協(xié)同過(guò)濾算法的基本思想是根據(jù)用戶對(duì)項(xiàng)目或信息的偏好，發(fā)現(xiàn)項(xiàng)目或內(nèi)容本身的相關(guān)性或者是發(fā)現(xiàn)用戶的相關(guān)性.例如，用戶甲和用戶乙對(duì)某類項(xiàng)目恰巧有相同的偏好，那么，協(xié)同過(guò)濾在對(duì)用戶甲進(jìn)行推薦的時(shí)候，就會(huì)更看重那些曾經(jīng)被用戶乙選擇過(guò)而用戶甲還沒(méi)有注意到的那些項(xiàng)目.由于協(xié)同過(guò)濾算法主要利用用戶項(xiàng)目評(píng)分矩陣來(lái)計(jì)算項(xiàng)目或者用戶之間的相似度，并不要求用機(jī)器可以理解的語(yǔ)言來(lái)對(duì)項(xiàng)目進(jìn)行詳細(xì)的描述，屬于領(lǐng)域無(wú)關(guān)的，所以，學(xué)術(shù)界和工業(yè)界經(jīng)常將協(xié)同過(guò)濾算法應(yīng)用到社會(huì)網(wǎng)絡(luò)推薦中.

但是，當(dāng)前的社會(huì)網(wǎng)絡(luò)用戶-項(xiàng)目二部圖中，用戶基數(shù)大但活躍度有限，因此，用戶項(xiàng)目評(píng)分?jǐn)?shù)據(jù)集的密度很小，即稀疏度高.采用降維的矩陣分解算法，算法的計(jì)算復(fù)雜度過(guò)高，計(jì)算效率低.在采用奇異值分解(singular value decomposition, SVD)等矩陣分解的方法時(shí)，也容易導(dǎo)致過(guò)度擬合[2].此外，大多數(shù)社會(huì)網(wǎng)絡(luò)推薦算法假設(shè)推薦的項(xiàng)目之間是相互獨(dú)立的，僅著眼于用戶，使得推薦的精確度不高.

近年來(lái)，隨著分布式并行圖框架的出現(xiàn)，學(xué)術(shù)界和工業(yè)界將圖模型應(yīng)用于社會(huì)網(wǎng)絡(luò)數(shù)據(jù)關(guān)系建模，并在利用高效的分布式并行圖框架的基礎(chǔ)上運(yùn)用圖算法來(lái)支持機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘.針對(duì)當(dāng)前研究中，數(shù)據(jù)稀疏度高算法效率低，以及算法推薦精確度不高這2個(gè)問(wèn)題，本文提出一種基于圖模型和K近鄰(K-nearest neighbor,KNN)模型的GK-CF算法.為了解決社會(huì)網(wǎng)絡(luò)推薦中數(shù)據(jù)過(guò)于稀疏的問(wèn)題，本算法將原有的評(píng)分?jǐn)?shù)據(jù)使用加權(quán)無(wú)向圖的方式進(jìn)行數(shù)據(jù)建模，圖節(jié)點(diǎn)和邊表示用戶、項(xiàng)目及其之間的關(guān)系，以利用圖的拓?fù)湫再|(zhì)和基本的圖算法.同時(shí)，基于文獻(xiàn)[1]的研究發(fā)現(xiàn)用戶更容易接受來(lái)自有相似項(xiàng)目購(gòu)買(mǎi)偏好的用戶的推薦，在本文中我們采用改進(jìn)的K近鄰算法結(jié)合無(wú)向有權(quán)圖中消息的傳播，以及改進(jìn)的相似度計(jì)算模型來(lái)進(jìn)行相似用戶的篩選，使所得到的相似用戶更加精準(zhǔn).進(jìn)一步地，算法通過(guò)圖的最短路徑算法來(lái)進(jìn)行帶評(píng)分項(xiàng)目的快速定位和篩選，也降低了計(jì)算的復(fù)雜性.最后利用并行圖框架對(duì)算法進(jìn)行了優(yōu)化，使得本文提出的方法具有較好的實(shí)時(shí)性.

1 相關(guān)工作

2006年，美國(guó)著名的DVD租賃網(wǎng)絡(luò)Netflix為了推動(dòng)推薦系統(tǒng)中評(píng)分預(yù)測(cè)問(wèn)題的研究，舉行了Netflix Prize比賽，伴隨著大量研究人員的深入研究推動(dòng)了學(xué)術(shù)界對(duì)推薦系統(tǒng)的研究.近年來(lái)社會(huì)網(wǎng)絡(luò)快速興起使得推薦系統(tǒng)的發(fā)展有了新的動(dòng)力和時(shí)機(jī).社會(huì)網(wǎng)絡(luò)可以很好地模擬現(xiàn)實(shí)社會(huì)，學(xué)術(shù)界和工業(yè)界對(duì)于如何利用社會(huì)網(wǎng)絡(luò)給用戶進(jìn)行個(gè)性化推薦及對(duì)社會(huì)化推薦過(guò)程的建模方法進(jìn)行了廣泛的研究.

作為推薦算法的典型代表，協(xié)同過(guò)濾算法近年來(lái)受到工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注.協(xié)同過(guò)濾算法不需要預(yù)先獲取用戶或項(xiàng)目的特征，僅依賴于用戶的歷史興趣顯式或隱式反饋對(duì)用戶興趣建模，再根據(jù)所建模型為用戶進(jìn)行推薦.在協(xié)同過(guò)濾算法中，顯式反饋指的是用戶曾經(jīng)對(duì)項(xiàng)目有過(guò)的歷史評(píng)分或者報(bào)告，隱式反饋指的是用戶群的歷史購(gòu)買(mǎi)信息、瀏覽信息、搜索模式和鼠標(biāo)停留信息等.以基于用戶的協(xié)同過(guò)濾算法為例，其主要關(guān)注點(diǎn)是根據(jù)相似用戶曾有的對(duì)項(xiàng)目的歷史評(píng)分預(yù)測(cè)出目標(biāo)用戶u對(duì)項(xiàng)目i的興趣度.其中，用戶之間相似度的計(jì)算有很多種方法，比較常見(jiàn)和普遍使用的就是根據(jù)2個(gè)用戶對(duì)共同關(guān)注過(guò)的項(xiàng)目的歷史評(píng)分來(lái)進(jìn)行皮爾斯相似度和余弦相似度[1]的計(jì)算.

學(xué)術(shù)界在余弦函數(shù)和皮爾斯函數(shù)的基礎(chǔ)上已經(jīng)提出了大量的提高算法準(zhǔn)確度和表現(xiàn)的算法，如用戶倒排評(píng)分、實(shí)例擴(kuò)展[3]和主流加權(quán)預(yù)測(cè)[4].Park等人[5]提出了一種基于KNN圖的協(xié)同過(guò)濾算法.KNN圖的構(gòu)建基于對(duì)項(xiàng)目的貪婪過(guò)濾，從而確定與每個(gè)項(xiàng)目最相似的前K′個(gè)項(xiàng)目列表.然后從當(dāng)前用戶未評(píng)分項(xiàng)目中篩選出其K′個(gè)項(xiàng)目與目標(biāo)用戶曾經(jīng)評(píng)分項(xiàng)目集合的交集為K的項(xiàng)目，再計(jì)算目標(biāo)用戶對(duì)其的評(píng)分.在降低計(jì)算復(fù)雜度的同時(shí)保持了算法的精度.但算法的主要關(guān)注點(diǎn)放在用K近鄰圖來(lái)提高尋找相似用戶的效率上，縮小了需要計(jì)算的未評(píng)分項(xiàng)目的范圍，而且此算法不能預(yù)測(cè)目標(biāo)用戶對(duì)所有未評(píng)分項(xiàng)目的興趣度.Das等人[6]利用二叉樹(shù)剖分技術(shù)提出了一種將用戶所在區(qū)域分解后僅利用與用戶相關(guān)的特殊區(qū)域的數(shù)據(jù)為當(dāng)前用戶進(jìn)行推薦的推薦算法，從而降低了計(jì)算的復(fù)雜度.Liu等人[7]提出了一種結(jié)合了用戶評(píng)分的全局偏好信息和每對(duì)用戶共同評(píng)分的上下文信息的啟發(fā)式相似度計(jì)算模型，來(lái)提高評(píng)分預(yù)測(cè)的準(zhǔn)確性.Xiang等人[8]引入時(shí)間窗口信息區(qū)分用戶不同時(shí)間段的行為，提高評(píng)分預(yù)測(cè)的準(zhǔn)確性.Ding等人[9]根據(jù)項(xiàng)目加入系統(tǒng)的時(shí)間引入相應(yīng)的衰減因子提高推薦的準(zhǔn)確性.Koren[10]利用時(shí)序圖對(duì)用戶的長(zhǎng)期興趣和短期興趣進(jìn)行區(qū)分，旨在更準(zhǔn)確地定義用戶當(dāng)前興趣，提高推薦準(zhǔn)確性.孫光福等人[11]通過(guò)衡量用戶之間的關(guān)系尋找相似的鄰居用戶，提出了一種對(duì)用戶間的時(shí)序行為進(jìn)行建模的方法并將基于該方法發(fā)現(xiàn)的鄰居集合成功融入到基于概率矩陣分解的協(xié)同過(guò)濾推薦算法中，提升推薦精度.Matook等人[12]提出了一種結(jié)合了熟人之間的推薦和歷史評(píng)分的推薦算法.Jia等人[13]提出了一種基于雙層鄰居選取策略的協(xié)同過(guò)濾推薦算法.Qin等人[14]提出一種融合信任和用戶情感偏好的協(xié)同過(guò)濾算法.此外，為了提高推薦的準(zhǔn)確性，Alami等人[15]提出了一種結(jié)合2種啟發(fā)式方法進(jìn)行相似用戶選擇及使用矩陣分解的方法發(fā)現(xiàn)相似用戶或項(xiàng)目的潛在特征的混合協(xié)同過(guò)濾算法.Santos[16]提出一種將心理模型理論、積極心理學(xué)中的共同臨時(shí)想法與傳統(tǒng)的協(xié)同過(guò)濾算法結(jié)合的基于用戶好奇心的混合推薦算法.

在基于圖的模型中，用戶與項(xiàng)目或者用戶與用戶或者項(xiàng)目與項(xiàng)目之間的關(guān)系往往是通過(guò)有向權(quán)圖或者無(wú)向權(quán)圖的方式來(lái)表示.通常情況下，圖中的節(jié)點(diǎn)表示用戶或者項(xiàng)目，圖中的邊被賦予了權(quán)值，用來(lái)表示用戶間和項(xiàng)目間的相似度或者用戶對(duì)項(xiàng)目的評(píng)分.在這些模型中，標(biāo)準(zhǔn)的方法只是利用與用戶節(jié)點(diǎn)或者項(xiàng)目節(jié)點(diǎn)有邊相連的節(jié)點(diǎn)來(lái)預(yù)測(cè)用戶對(duì)于項(xiàng)目的評(píng)分.例如，通過(guò)統(tǒng)計(jì)用戶節(jié)點(diǎn)和項(xiàng)目節(jié)點(diǎn)之間的距離來(lái)直接估計(jì)用戶對(duì)項(xiàng)目的評(píng)分[17-18].在一些文獻(xiàn)中[19-21]，目標(biāo)項(xiàng)目節(jié)點(diǎn)或者用戶節(jié)點(diǎn)往往也通過(guò)沿著圖中的邊對(duì)其消息進(jìn)行廣播來(lái)影響那些未與其直接連接的節(jié)點(diǎn).

隨著云計(jì)算時(shí)代的到來(lái)，Zhu等人[22]提出了一種適用于云計(jì)算分布式處理環(huán)境下基于協(xié)同過(guò)濾的個(gè)性化推薦機(jī)制RAC.

不斷增長(zhǎng)的數(shù)據(jù)規(guī)模也驅(qū)動(dòng)了分布式并行圖框架系統(tǒng)的出現(xiàn)[23-24]，這些系統(tǒng)可以優(yōu)化數(shù)據(jù)在集群環(huán)境中的布局，并將復(fù)雜的迭代算法在有數(shù)百億的頂點(diǎn)和邊的圖上進(jìn)行分布執(zhí)行.在并行圖方式下的圖算法的迭代效率要比普通的數(shù)據(jù)并行系統(tǒng)下的執(zhí)行效率有數(shù)量級(jí)的提高[23].

2 評(píng)分?jǐn)?shù)據(jù)表示及系統(tǒng)建模

2.1 評(píng)分?jǐn)?shù)據(jù)描述

用u表示用戶，p表示項(xiàng)目.用戶歷史評(píng)分記錄中的用戶集合用U={u1,u2,…,un}表示，項(xiàng)目集合用P={p1,p2,…,pm}表示，則用戶歷史評(píng)分記錄可以用一個(gè)n×m的矩陣R表示，矩陣中的每一個(gè)元素rij表示用戶ui對(duì)項(xiàng)目pj的已有評(píng)價(jià)分?jǐn)?shù)，且i∈1,2,…,n，j∈1,2,…,m.如果用戶集合中的某個(gè)用戶ui對(duì)項(xiàng)目集合中的項(xiàng)目pj尚未有過(guò)評(píng)分，則在R評(píng)分矩陣中與其對(duì)應(yīng)的矩陣元素rij為空，R評(píng)分矩陣為

其中，評(píng)分矩陣R中元素存在已知值和空值，已知值表示當(dāng)前行所代表的用戶曾經(jīng)對(duì)當(dāng)前列所代表的項(xiàng)目有過(guò)歷史評(píng)分，空值表示當(dāng)前行所代表的用戶尚未關(guān)注當(dāng)前列所代表的項(xiàng)目或者還未給項(xiàng)目做過(guò)評(píng)分.推薦算法的工作就是基于R中已有的評(píng)分值和其他相關(guān)信息對(duì)矩陣R中的空值進(jìn)行預(yù)測(cè).

2.2 基于無(wú)向有權(quán)圖的數(shù)據(jù)表示及系統(tǒng)建模

本文中，我們引入圖結(jié)構(gòu)來(lái)對(duì)用戶項(xiàng)目歷史評(píng)分?jǐn)?shù)據(jù)進(jìn)行建模，基于并行化圖模型的推薦系統(tǒng)框架如圖1所示：

Fig. 1 Recommendation system architecture based on parallel graph framework圖1 基于并行圖模型的推薦系統(tǒng)架構(gòu)

圖1中，最底層是支持大規(guī)模數(shù)據(jù)處理的并行集群環(huán)境，通過(guò)分布式處理引擎支持流式計(jì)算和分布式存儲(chǔ).用戶在參與社會(huì)化網(wǎng)絡(luò)活動(dòng)中形成的各種數(shù)據(jù)，通過(guò)圖的生成、圖的分割加載到底層的集群環(huán)境中，通過(guò)圖的消息傳播和匯聚及基于圖的計(jì)算，可以對(duì)基于圖的用戶數(shù)據(jù)做進(jìn)一步處理，包括用戶過(guò)濾、用戶相似度計(jì)算、確定候選項(xiàng)目以及對(duì)項(xiàng)目進(jìn)行評(píng)分.最終將用戶可能感興趣的結(jié)果推薦給用戶.

本文中，我們用無(wú)向有權(quán)圖的方式對(duì)原始的評(píng)分矩陣進(jìn)行建模，假設(shè)用圖G表示用戶評(píng)分的歷史記錄.G=(V,E).其中，V={v1,v2,…,vn,vn+1,vn+2,…,vn+m}，對(duì)應(yīng)上文所提用戶列表U和項(xiàng)目列表P的并集.其中v1～vn代表用戶列表U中的用戶u1～un;vn+1～vn+m代表項(xiàng)目列表P中的項(xiàng)目p1～pm.E代表圖中邊的集合，〈vi,vj〉∈E(i=1,2,…,n;j=n+1,n+2,…,n+m)代表用戶vi曾經(jīng)對(duì)vj有過(guò)歷史評(píng)分，歷史評(píng)分用來(lái)表示邊的權(quán)值.圖G如圖2所示.則給用戶ui推薦項(xiàng)目的問(wèn)題可以定義為：在當(dāng)前的無(wú)向有權(quán)圖中，預(yù)測(cè)從用戶頂點(diǎn)vi到與之沒(méi)有邊相連的某一項(xiàng)目頂點(diǎn)vj之間在圖上的相關(guān)性.

Fig. 2 The undigraph with weight based on the users- items historical ratings圖2 用戶-項(xiàng)目歷史評(píng)分無(wú)向有權(quán)圖

在這里給出基于圖的評(píng)分?jǐn)?shù)據(jù)模型的幾個(gè)定義：

定義1. 目標(biāo)頂點(diǎn)的2-度關(guān)聯(lián)頂點(diǎn).目標(biāo)頂點(diǎn)vi的2-度關(guān)系頂點(diǎn)可以表示為集合：

{vj|〈vi,vj〉?E∧(?k)〈vi,vk〉∈E∧〈vk,vj〉∈E}，

即從圖中該目標(biāo)頂點(diǎn)vi出發(fā)，若存在1個(gè)中間節(jié)點(diǎn)vk，經(jīng)過(guò)2條不重復(fù)邊〈vi,vk〉以及〈vk,vj〉能夠到達(dá)的頂點(diǎn)vj為目標(biāo)頂點(diǎn)vi的2-度關(guān)聯(lián)頂點(diǎn).

定理1. 若以用戶頂點(diǎn)為目標(biāo)頂點(diǎn)，則其2-度關(guān)聯(lián)頂點(diǎn)一定是用戶頂點(diǎn).因?yàn)楸疚尼槍?duì)的用戶-項(xiàng)目歷史評(píng)分是二部圖結(jié)構(gòu)，所有的邊都代表某用戶對(duì)某項(xiàng)目的評(píng)分，用戶之間或項(xiàng)目之間不存在邊.

證明略.

定義2. 用戶的n-度關(guān)聯(lián)項(xiàng)目.若從圖中某一用戶頂點(diǎn)vi出發(fā)，沿圖中的邊能夠到達(dá)的項(xiàng)目頂點(diǎn)，稱其為用戶vi的關(guān)聯(lián)項(xiàng)目，n表示從vi到達(dá)關(guān)聯(lián)項(xiàng)目經(jīng)過(guò)的邊數(shù).

定義3. 用戶與關(guān)聯(lián)項(xiàng)目的最短路徑.若e1,e2,…,en∈E,其中，ei是關(guān)聯(lián)于節(jié)點(diǎn)vi-1，vi的邊，交替序列v0e1v1e2…envn稱為聯(lián)接v0到vn的路.邊的數(shù)目n稱作路的長(zhǎng)度.若一條路中所有的節(jié)點(diǎn)v0,v1,…,vn均不相同，稱作通路.從圖中某一用戶頂點(diǎn)vi出發(fā)到其關(guān)聯(lián)項(xiàng)目vj存在多條通路，則從節(jié)點(diǎn)vi到節(jié)點(diǎn)vj路徑中邊數(shù)之和稱為vi到vj的路徑長(zhǎng)度，長(zhǎng)度最小的路徑稱為vi到vj的最短路徑.

3 基于圖和改進(jìn)KNN的協(xié)同過(guò)濾算法GK-CF

在傳統(tǒng)K近鄰算法中，對(duì)每個(gè)目標(biāo)用戶uactive進(jìn)行相似度計(jì)算時(shí)，都是對(duì)其計(jì)算與系統(tǒng)中所有剩余用戶的相似度，使得計(jì)算量較大且復(fù)雜度高，或者由于相似用戶的過(guò)濾過(guò)于隨機(jī)使得推薦的精確度不高.

為了選出K個(gè)相似用戶，傳統(tǒng)的用戶近鄰模型直接通過(guò)皮爾斯公式和余弦公式來(lái)計(jì)算2個(gè)用戶之間的臨近程度.

本文對(duì)上述方法進(jìn)行了改進(jìn)，主要解決2個(gè)問(wèn)題：

1)K個(gè)相似用戶的選取問(wèn)題；

2) 相似好友用戶與目標(biāo)用戶uactive之間的相似度計(jì)算問(wèn)題.

3.1 基于圖的相似用戶選取

文獻(xiàn)[1]指出相比傳統(tǒng)的基于評(píng)分的推薦，用戶更容易接受來(lái)自有相似項(xiàng)目購(gòu)買(mǎi)偏好的用戶的推薦，因此本文在傳統(tǒng)協(xié)同過(guò)濾算法的基礎(chǔ)上，結(jié)合共同評(píng)分的上下文信息，在計(jì)算用戶相似度之前，先進(jìn)行目標(biāo)用戶uactive的相似用戶篩選，僅考慮那些曾經(jīng)與目標(biāo)用戶uactive有過(guò)共同選擇和評(píng)分的用戶，將其看作目標(biāo)用戶uactive的相似用戶組，然后在目標(biāo)用戶uactive與其相似用戶組間計(jì)算相似度.

按照2.2節(jié)前述基于圖模型的定義1，與目標(biāo)用戶uactive有共同選擇和評(píng)分的用戶即為2-度關(guān)聯(lián)用戶，因此，篩選相似用戶問(wèn)題可以描述為求目標(biāo)頂點(diǎn)的2-度關(guān)聯(lián)頂點(diǎn)問(wèn)題.

為了確定目標(biāo)用戶uactive的2-度關(guān)聯(lián)用戶，本文提出圖的消息傳播和聚合方法GraPA.

在GraPA方法中，圖中的頂點(diǎn)有3種狀態(tài)：1)未激活狀態(tài)，記為S0；2)被消息激活對(duì)消息進(jìn)行廣播的狀態(tài)，記為S1；3)收到消息后對(duì)消息進(jìn)行合并的狀態(tài)，記為S2.圖中每一個(gè)頂點(diǎn)vi維護(hù)的消息可表示為vList=(vidi，Li)，其中vidi表示頂點(diǎn)vi的ID，Li表示在傳播過(guò)程中到達(dá)頂點(diǎn)vi的其他頂點(diǎn)ID的集合，初始化為L(zhǎng)i=(vidi).全圖頂點(diǎn)按照離散的等間隔時(shí)間序列在3個(gè)狀態(tài)間進(jìn)行狀態(tài)轉(zhuǎn)換，完成消息的傳播和聚合.圖的信息傳播和聚合的方法GraPA流程如算法1所示：

算法1. 基于時(shí)間步序列的圖信息傳播和聚合方法GraPA.

輸入: 無(wú)向圖G=(V,E)；

輸出: 無(wú)向圖G中所有頂點(diǎn)的消息列表List[(vid,Li)].

① 初始時(shí)刻，將圖中的所有頂點(diǎn)的狀態(tài)初始化為S0.

② 在時(shí)間步T=2n-1，所有頂點(diǎn)均作為發(fā)布消息的源節(jié)點(diǎn)，沿著以當(dāng)前廣播消息頂點(diǎn)vi為源頂點(diǎn)的邊e〈vi，vj〉廣播vi頂點(diǎn)的Li至頂點(diǎn)vj，這是圖的消息傳播.

③ 在時(shí)間步T=2n，所有頂點(diǎn)將時(shí)間步T=2n-1時(shí)收到的不同源頂點(diǎn)廣播來(lái)的頂點(diǎn)，如Lj,Lp,…,Lk合并起來(lái)，同時(shí)將合并后的集合L=Lj∪Lp∪…∪Lk作為頂點(diǎn)vi的更新后的Li.這是圖的消息聚合.

從圖的初始時(shí)刻開(kāi)始，在經(jīng)過(guò)1輪2個(gè)時(shí)間步后，每個(gè)用戶頂點(diǎn)所維護(hù)的Li即為該用戶的2-度關(guān)系用戶.

3.2 用戶相似度計(jì)算

在篩選出用戶的2-度關(guān)聯(lián)用戶后，接著計(jì)算2-度關(guān)聯(lián)用戶與目標(biāo)用戶uactive之間的相似度.

如果用I來(lái)表示2用戶u和v曾經(jīng)共同給過(guò)評(píng)分的項(xiàng)目集合，則傳統(tǒng)的皮爾斯公式計(jì)算用戶之間的相似度為

(1)

傳統(tǒng)的皮爾斯公式僅考慮2用戶曾經(jīng)有過(guò)共同評(píng)分的項(xiàng)目，對(duì)于一方用戶曾經(jīng)做過(guò)評(píng)分而另一方用戶尚未關(guān)注的項(xiàng)目不加考慮.但是這種擁有共同評(píng)分的項(xiàng)目數(shù)較少，使得用于計(jì)算2用戶之間相似度的數(shù)據(jù)過(guò)少，在一定程度上降低了用于推薦預(yù)測(cè)的信息量.因此，在本文中，我們考慮2用戶間一方有評(píng)分而另一方尚未評(píng)分的項(xiàng)目，假設(shè)用Iuv=Iu-Iv表示用戶u曾經(jīng)有過(guò)評(píng)分而用戶v尚未評(píng)分的項(xiàng)目，并將用戶v對(duì)這一部分項(xiàng)目的評(píng)分統(tǒng)一賦值為常量C.同理用Ivu=Iv-Iu表示用戶v曾經(jīng)有過(guò)評(píng)分而用戶u尚未評(píng)分的項(xiàng)目，同時(shí)將用戶u對(duì)這一部分項(xiàng)目的評(píng)分也統(tǒng)一賦值為常量C.將Iuv和Ivu這2個(gè)集合中的項(xiàng)目評(píng)分加入計(jì)算，則式(1)中，計(jì)算用戶評(píng)分與此用戶的評(píng)分均值的偏離度的平方和擴(kuò)展為

(2)

式(1)中，除了計(jì)算I中項(xiàng)目涉及到的2個(gè)用戶評(píng)分與對(duì)應(yīng)用戶的評(píng)分均值偏離度的乘積和

(3)

還將考慮Iuv和Ivu這2個(gè)集合中的項(xiàng)目，將式(3)擴(kuò)展為

(4)

從而保證2用戶有足夠的評(píng)分項(xiàng)目信息量用于計(jì)算用戶之間的相似度.

(5)

(6)

綜上，本文提出用戶相似度的計(jì)算方法：

(7)

3.3 基于圖最短路徑的可推薦項(xiàng)目數(shù)計(jì)算

對(duì)于無(wú)向圖G=(V,E)中的一條路徑是指1個(gè)頂點(diǎn)序列P=v1v2…vk,其中每一對(duì)相鄰的頂點(diǎn)vi和vi+1之間都有1條邊,P也稱為從v1到vk的一條路徑.按照2.2節(jié)定義2和定義3，在一個(gè)無(wú)向圖中的節(jié)點(diǎn)vi到節(jié)點(diǎn)vi+1的最短路徑指的是從節(jié)點(diǎn)vi到節(jié)點(diǎn)vi+1路徑長(zhǎng)度之和最小的路徑.

通過(guò)最短路徑尋找符合條件的項(xiàng)目的過(guò)程我們通過(guò)圖的消息傳播方式實(shí)現(xiàn)，此算法歸結(jié)為在無(wú)向圖G的拓?fù)涔?jié)點(diǎn)中迭代執(zhí)行特定的算法，shortPA算法流程如算法2所示：

算法2. 基于圖消息傳播的ShortPA算法.

輸入: 無(wú)向圖G=(V,E)、目標(biāo)頂點(diǎn)的ID:TargetID；

輸出: 無(wú)向圖G中所有非目標(biāo)頂點(diǎn)的頂點(diǎn)ID-屬性列表List[(VID,Vattribute)].

① forV-*初始化*-

② ifVid==TargetIDthen

changeVattr(Vid,0);

③ elsechangeVattr(Vid,∞);

④ end if

⑤ end for -*初始化各頂點(diǎn)的屬性為到目標(biāo)頂點(diǎn)的距離，也即定義各非目標(biāo)頂點(diǎn)到目標(biāo)頂點(diǎn)的距離為無(wú)窮大，目標(biāo)頂點(diǎn)到自身的距離為0*-

⑥ repeat；

⑦ begin Phase 1：并行化； -*圖中每條邊上的源節(jié)點(diǎn)沿著與其相連的邊向其目標(biāo)頂點(diǎn)發(fā)送消息，當(dāng)源頂點(diǎn)自身的距離屬性值加1小于目標(biāo)頂點(diǎn)的屬性值時(shí)，設(shè)定源頂點(diǎn)的屬性值加1為當(dāng)前要發(fā)送的消息，否則，設(shè)定要發(fā)送的消息值為空*-

⑧ ifsrcVattr+1

⑨ elsesentMessage(dstID,positiveInfitility)；

⑩ end if

由于評(píng)分?jǐn)?shù)據(jù)圖的規(guī)模性，評(píng)分?jǐn)?shù)據(jù)圖會(huì)進(jìn)行分割得到評(píng)分?jǐn)?shù)據(jù)子圖，為了保證對(duì)數(shù)據(jù)的并行處理，在算法2中，階段1、階段2及階段3均為可并行對(duì)各評(píng)分?jǐn)?shù)據(jù)子圖進(jìn)行分別處理的設(shè)計(jì).

基于用戶的協(xié)同過(guò)濾推薦中用戶u對(duì)項(xiàng)目i的興趣度評(píng)分是通過(guò)綜合用戶u的其他相似用戶對(duì)項(xiàng)目i的評(píng)分而得到的：

ru,i=aggrsu∈Srsu,i，

(8)

其中，S表示用戶u的相似用戶中曾經(jīng)給項(xiàng)目i做過(guò)評(píng)分的用戶的集合.為提高預(yù)測(cè)評(píng)分的精確度，在具體的算法[1]中，用戶u對(duì)項(xiàng)目i的評(píng)分ru,i通過(guò)式(9)進(jìn)行計(jì)算：

(9)

其中，k是正則化因子，通常通過(guò)

求得，其中Isu代表用戶su曾經(jīng)給過(guò)評(píng)分的項(xiàng)目的集合.

3.4 GK-CF算法及其并行化設(shè)計(jì)

本文提出的基于圖模型和改進(jìn)K近鄰的協(xié)同過(guò)濾算法GK-CF，算法偽代碼描述如算法3所示：

算法3. 基于圖模型和改進(jìn)K近鄰的協(xié)同過(guò)濾GK-CF算法.

輸入: 用戶-項(xiàng)目歷史評(píng)分?jǐn)?shù)據(jù)ru,i；

輸出: 推薦項(xiàng)目列表List[Iid].

① 初始化:G:(V,E)←graphBuild(ru,i)；

-*G為無(wú)向有權(quán)圖，V={v1,v2,…,vn,vn+1,vn+2,…,vn+m},對(duì)應(yīng)上文所提用戶列表U和項(xiàng)目列表P的并集.其中的v1～vn代表用戶列表U中的用戶u1～un.vn+1～vn+m代表項(xiàng)目列表P中的項(xiàng)目p1～pm.E代表圖中邊的集合.E〈vi,vj〉∈E代表vi所代表的用戶ui曾經(jīng)對(duì)vj所代表的項(xiàng)目pj有過(guò)歷史評(píng)分*-

②U1={v1,vi,…,vn}←GraPA(G)； -*篩選出目標(biāo)用戶uactive的2-度關(guān)系用戶*-

③unSortPearson={(v1,Pv1),(vi，Pvi),…,(vn，Pvn)}←improvedPearson(U1)； -*計(jì)算用戶集U1與目標(biāo)用戶uactive之間的相似度*-

④U1′←SortByPearsonValueAndTakeTopK(unSortPearson,K)； -*根據(jù)其與目標(biāo)用戶uactive之間的相似度進(jìn)行排序后選出其前K個(gè)用戶作為目標(biāo)用戶uactive的相似用戶集U1′*-

⑤I′={vm+1,vm+k,…,vm+n+1}←ShortPA(G,TargetID)； -*根據(jù)ShortPA算法篩選出符合條件的項(xiàng)目集*-

⑥unSortItemAttractive={(vm+1，Avm+1)，(vm+k，Avm+k+1),…,(vm+n+1，Avm+n+1)}←formulation(I′)； -*根據(jù)式(9)計(jì)算出目標(biāo)用戶uactive對(duì)可推薦項(xiàng)目集I′={vm+1,vm+k,…,vm+n+1}中項(xiàng)目的興趣度*-

⑦List[Iid]={vm+1，vm+p,…,vm+n-2}←SortByAttractiveValueAndTakeTopN(unSortItemAttractive，K)； -*選擇預(yù)測(cè)值前top-N的項(xiàng)目作為推薦項(xiàng)目推薦給用戶*-

⑧ returnList[Iid].

GK-CF算法的輸入為根據(jù)用戶-項(xiàng)目歷史評(píng)分文件生成的基于并行計(jì)算框架Spark的彈性分布式數(shù)據(jù)集(resilient distributed dataset, RDD).RDD是不可變的帶分區(qū)的記錄集合，也是Spark中的編程模型，與并行計(jì)算框架Hadoop的MapReduce 2階段提交任務(wù)，任務(wù)間相互等待高時(shí)延不同，Spark提供了RDD上的2類操作：RDD本身的轉(zhuǎn)換(trans-formation)以及對(duì)RDD的動(dòng)作(action).在Spark中，一段程序?qū)嶋H上就構(gòu)造了一個(gè)由相互依賴的多個(gè)RDD組成的有向無(wú)環(huán)圖(directed acyclic graph， DAG)，將這個(gè)有向無(wú)環(huán)圖作為一個(gè)任務(wù)提交給Spark執(zhí)行將完成在RDD上的各種操作.因此Spark任務(wù)之間不需要互相等待，對(duì)于迭代式數(shù)據(jù)處理性能好.并且Spark每次迭代的數(shù)據(jù)保存在內(nèi)存中，使得Spark的性能相比Hadoop有很大的提升[23,25].

GK-CF算法中的每一步都進(jìn)行了并行化設(shè)計(jì)，使得全圖數(shù)據(jù)得以并行化處理.其中，算法3中的步驟②和步驟⑤分別對(duì)應(yīng)算法1和算法2,算法3中的步驟③(計(jì)算用戶集U1與目標(biāo)用戶uactive之間的相似度)和步驟⑥(根據(jù)式(9)計(jì)算出目標(biāo)用戶uactive對(duì)可推薦項(xiàng)目集I′={vm+1,vm+k,…,vm+n+1}中項(xiàng)目的興趣度)是另外2個(gè)重要步驟，對(duì)其并行化設(shè)計(jì)說(shuō)明如下：

步驟③中，為了并行計(jì)算目標(biāo)用戶uactive和其2-度關(guān)系用戶U1間的相似度，將計(jì)算相似度任務(wù)劃分為4個(gè)不同的子任務(wù)：

2) 通過(guò)對(duì)用戶-項(xiàng)目歷史評(píng)分RDD及用戶平均評(píng)分RDD進(jìn)行連接(join)，map操作求出目標(biāo)用戶uactive和其2-度關(guān)系用戶集U1={v1,v2,…,vn}中每個(gè)用戶vu的評(píng)分均值偏離度RDD及其評(píng)分均值偏離度平方和RDD；

3) 再通過(guò)map操作將評(píng)分均值偏離度RDD做鍵值對(duì)中的key-value值交換后通過(guò)join操作將與目標(biāo)用戶uactive相關(guān)的評(píng)分偏離度RDD和與其2-度關(guān)系用戶集U1中用戶相關(guān)的評(píng)分偏離度RDD的笛卡兒積求出后，通過(guò)map操作求出目標(biāo)用戶uactive與其對(duì)應(yīng)的2-度關(guān)系用戶的評(píng)分均值偏離度的乘積RDD；

4) 通過(guò)對(duì)評(píng)分均值偏離度的乘積RDD及評(píng)分偏離度平方和的一系列join及map操作后獲取目標(biāo)用戶uactive及其2-度關(guān)系用戶間的相似度RDD.

同理，步驟⑥中的任務(wù)也可以分為2個(gè)子任務(wù)：

1) 通過(guò)求和(sum)和map操作計(jì)算出式(9)中的正則化因子k；

2) 基于算法步驟③中計(jì)算出的目標(biāo)用戶uactive與其2-度關(guān)系用戶間的評(píng)分偏離度RDD、相似度RDD、目標(biāo)用戶平均評(píng)分RDD以及步驟⑥中計(jì)算出的正則化因子k通過(guò)join、過(guò)濾(filter)、map等一系列操作完成用戶u對(duì)項(xiàng)目i的評(píng)分ru,i.

3.5 算法復(fù)雜度分析

由于推薦算法涉及對(duì)海量數(shù)據(jù)的處理，除了推薦結(jié)果的準(zhǔn)確性之外，算法本身的復(fù)雜度也是需要討論的.本文提出的GK-CF算法通過(guò)建立圖數(shù)據(jù)模型及子圖分割，實(shí)現(xiàn)了對(duì)原始海量數(shù)據(jù)的分布式并行處理，對(duì)其時(shí)間復(fù)雜度Ttime和空間復(fù)雜度Tspace分析如下：根據(jù)算法3的描述，算法3的主要步驟是計(jì)算目標(biāo)用戶uactive的2-度好友集合(步驟②)、計(jì)算目標(biāo)用戶uactive與其2-度好友間的相似度(步驟③)、基于圖的最短路徑計(jì)算可推薦項(xiàng)目(步驟⑤)及計(jì)算目標(biāo)用戶uactive對(duì)可推薦項(xiàng)目的興趣度(步驟⑥).

1) 在計(jì)算目標(biāo)用戶uactive的2-度好友集合過(guò)程中，根據(jù)算法1中圖的消息傳播和聚合算法GraPA，每個(gè)頂點(diǎn)均需向其鄰居頂點(diǎn)發(fā)送1次消息，假設(shè)圖中的頂點(diǎn)個(gè)數(shù)為N(N為用戶-項(xiàng)目評(píng)分文件中用戶U和項(xiàng)目數(shù)P之和)，邊的條數(shù)為E，則按鄰接表方式存儲(chǔ)圖的空間復(fù)雜度為O(N+E).1次消息傳播和聚合的時(shí)間復(fù)雜度為O(N)，2-度好友通過(guò)前后2次的消息傳播和聚合，時(shí)間復(fù)雜度仍然為O(N).眾所周知，用戶評(píng)分?jǐn)?shù)據(jù)具有高稀疏性，通過(guò)無(wú)向有權(quán)圖對(duì)其建模后得到稀疏圖，不失一般性，1個(gè)稀疏圖其邊數(shù)和圖中節(jié)點(diǎn)數(shù)的關(guān)系表現(xiàn)為E≤(Nlog·N)-2.由于在此步驟中圖中的每一個(gè)頂點(diǎn)都要沿著它的鄰邊向它的鄰居頂點(diǎn)進(jìn)行1次消息傳播，并在鄰居頂點(diǎn)進(jìn)行存儲(chǔ)以完成聚合操作，因此需要在每個(gè)頂點(diǎn)開(kāi)辟的額外存儲(chǔ)空間為2E≤Nlog·N.因此，此步驟中的空間復(fù)雜度為O(Nlog·N).

2) 在計(jì)算目標(biāo)用戶uactive與其2-度好友間的相似度時(shí)，其時(shí)間復(fù)雜度主要表現(xiàn)為RDD進(jìn)行1次map操作的時(shí)間，也即對(duì)圖中代表目標(biāo)用戶uactive的2-度好友的頂點(diǎn)的屬性值進(jìn)行1次變換修改操作的時(shí)間，因此，時(shí)間復(fù)雜度為O(N).在計(jì)算過(guò)程中需要將頂點(diǎn)數(shù)據(jù)的RDD存儲(chǔ)在內(nèi)存中，RDD通常以〈目標(biāo)用戶，2-度好友用戶，相關(guān)value〉的方式存在，則此步驟的空間復(fù)雜度為O(N).

3) 在基于圖的最短路徑計(jì)算可推薦項(xiàng)目中，由于尋找最短路徑需要進(jìn)行3次消息傳播，因此此步驟的時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(Nlog·N).

① http:--grouplens.org-datasets-movielens-

4) 在計(jì)算目標(biāo)用戶uactive對(duì)可推薦項(xiàng)目的興趣度中，此計(jì)算過(guò)程同樣需要將頂點(diǎn)的RDD以〈目標(biāo)用戶，可推薦項(xiàng)目，興趣度〉形式存在內(nèi)存中，其空間復(fù)雜度為O(N).此步驟時(shí)間復(fù)雜度與計(jì)算目標(biāo)用戶uactive與其2-度好友間相似度的時(shí)間復(fù)雜度一樣為O(N).

綜合分析得出，GK-CF算法的時(shí)間復(fù)雜度為O(N),空間復(fù)雜度為O(Nlog·N+E).由于算法的每一步均為并行執(zhí)行，在給定集群環(huán)境擁有多臺(tái)處理器數(shù)目的情況下，算法能夠在更短的時(shí)空范圍內(nèi)完成計(jì)算.

通過(guò)具體的算法實(shí)現(xiàn)，對(duì)于同樣的社會(huì)網(wǎng)絡(luò)標(biāo)準(zhǔn)數(shù)據(jù)集MovieLens①，采用并行化方法設(shè)計(jì)實(shí)現(xiàn)的GK-CF算法在4.1節(jié)的實(shí)驗(yàn)環(huán)境下運(yùn)行效率為3.33·s，而串行方式下該算法的運(yùn)行效率為31.53·s.本文提出的算法在6個(gè)節(jié)點(diǎn)的并行平臺(tái)上的運(yùn)行效率較串行方式實(shí)現(xiàn)下的運(yùn)行效率高出10倍.

上述2種算法的執(zhí)行時(shí)間結(jié)果記錄如表1所示.本文同時(shí)以Wilcoxon秩和檢驗(yàn)方法檢驗(yàn)采用并行化方法設(shè)計(jì)實(shí)現(xiàn)的GK-CF算法較之串行方式的實(shí)現(xiàn)效率是否有顯著提升.

Table 1 The Descriptive Statistics of the Operation Efficiency of GK-CF and Serialized GK-CF

表1 GK-CF及其串行方式實(shí)現(xiàn)的運(yùn)行時(shí)間的描述性統(tǒng)計(jì)

從表1中可以看出，GK-CF算法通過(guò)并行化的實(shí)現(xiàn)，其運(yùn)行效率遠(yuǎn)高于串行方法.基于Wilcoxon秩和檢驗(yàn)方法對(duì)表1中數(shù)據(jù)進(jìn)行了分析.

Wilcoxon秩和檢驗(yàn)是一種非參數(shù)統(tǒng)計(jì)方法[26]，綜合了t_test和閾值誤判方法(threshold number of misclassification，TNOM)的良好特性，克服了t_test對(duì)于噪音敏感和TNOM會(huì)丟失數(shù)據(jù)中信息的缺點(diǎn)[27].Wilcoxon秩和檢驗(yàn)法在檢驗(yàn)樣本時(shí)，首先在符號(hào)檢驗(yàn)的基礎(chǔ)上計(jì)算樣本的正、負(fù)號(hào)秩及其樣本秩的總和w及樣本的統(tǒng)計(jì)量概率p.如果樣本的統(tǒng)計(jì)量z的統(tǒng)計(jì)量概率p接近于0，則2配對(duì)樣本存在著顯著性的差異.其中，樣本統(tǒng)計(jì)量z計(jì)算為

z=[w-n1(n1+n2+1)-2]-

[n1n2(n1+n2+1)-12]1-2，

(10)

其中，n1為第1個(gè)樣本集的樣本容量，n2為第2個(gè)樣本集的樣本容量，w為第1個(gè)樣本集樣本的秩和.

檢驗(yàn)結(jié)果如表2所示：

Table 2 The Wilcoxon Rank SumTest表2 Wilcoxon秩和檢驗(yàn)

該結(jié)果顯示W(wǎng)ilcoxon統(tǒng)計(jì)量w和z皆拒絕GK-CF和其串行方式的算法運(yùn)行效率相等的零假設(shè).且樣本的統(tǒng)計(jì)量z的統(tǒng)計(jì)量概率p接近于0，2配對(duì)樣本存在顯著性差異，該檢驗(yàn)表明，并行化設(shè)計(jì)實(shí)現(xiàn)的GK-CF較其串行方式的實(shí)現(xiàn)，在運(yùn)行效率上有顯著提升.

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

本節(jié)通過(guò)實(shí)驗(yàn)繼續(xù)對(duì)本文提出算法的推薦效果進(jìn)行驗(yàn)證，討論了選取不同的用戶數(shù)和項(xiàng)目數(shù)對(duì)推薦結(jié)果的影響.并將本文提出的算法GK-CF同其他算法在真實(shí)的物理集群環(huán)境下進(jìn)行了實(shí)現(xiàn)及對(duì)比.

4.1 數(shù)據(jù)集及實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境由6臺(tái)服務(wù)器組成云平臺(tái)集群，服務(wù)器運(yùn)行的是Ubuntu14.04 64位系統(tǒng)，集群管理平臺(tái)為Spark1.1.0，每臺(tái)服務(wù)器節(jié)點(diǎn)包括一個(gè)4核CPU和8·GB內(nèi)存.集群由1臺(tái)服務(wù)器作為Master節(jié)點(diǎn)，5臺(tái)作為計(jì)算節(jié)點(diǎn).實(shí)驗(yàn)中GK-CF算法與所有參與對(duì)比的算法均在Spark平臺(tái)上進(jìn)行了并行化實(shí)現(xiàn).

實(shí)驗(yàn)采用大規(guī)模社會(huì)網(wǎng)絡(luò)標(biāo)準(zhǔn)數(shù)據(jù)集MovieLens①來(lái)驗(yàn)證本文所提出的GK-CF算法能夠更好地進(jìn)行社會(huì)網(wǎng)絡(luò)應(yīng)用中對(duì)項(xiàng)目的推薦.

① http:--grouplens.org-datasets-movielens-

4.2 評(píng)價(jià)指標(biāo)和實(shí)驗(yàn)參數(shù)

為了使本文提出的算法能夠取得較好的推薦效果，我們分別對(duì)相似用戶數(shù)量和項(xiàng)目數(shù)量的選取進(jìn)行了實(shí)驗(yàn).分別考慮了預(yù)測(cè)的均方根誤差(rmse)、準(zhǔn)確率(precision)以及召回率(recall)三個(gè)評(píng)價(jià)指標(biāo).

(11)

令R(u)是根據(jù)用戶在訓(xùn)練集上的行為為用戶做出的推薦列表，而T(u)是用戶在測(cè)試集上的行為列表，則推薦結(jié)果的準(zhǔn)確率(precision)定義為

(12)

推薦結(jié)果的召回率(recall)定義為

(13)

表3對(duì)推薦的項(xiàng)目數(shù)不做限制的情況下，選取不同數(shù)量的相似用戶的實(shí)驗(yàn)結(jié)果.通過(guò)表3可以看出，在重點(diǎn)考慮rmse的前提下，當(dāng)用戶數(shù)取100時(shí)，能夠取得較好的rmse和recall，但precision略低.

Table 3 The Similar Users Number Choose Experiment表3 相似用戶數(shù)選取

Table 4 The Candidate Items Choose Experiment表4 候選項(xiàng)目數(shù)選取

1)rmse

評(píng)分預(yù)測(cè)的預(yù)測(cè)準(zhǔn)確度一般通過(guò)rmse計(jì)算.

本文對(duì)4種算法進(jìn)行了對(duì)比實(shí)驗(yàn)，分別是：基于用戶的協(xié)同過(guò)濾算法(collaborative filtering algori-thm, CF)、基于評(píng)分?jǐn)?shù)據(jù)矩陣及本文提出的改進(jìn)KNN算法實(shí)現(xiàn)的K-CF算法、基于交替最小二乘的協(xié)同過(guò)濾算法(alternating least squares-collaborative filtering algorithm, ALS-CF)以及基于圖模型和改進(jìn)KNN的GK-CF算法.在MovieLens①不同大小的數(shù)據(jù)集上分別運(yùn)行上述算法.結(jié)果如圖3所示，GK-CF算法的rmse值遠(yuǎn)低于基準(zhǔn)CF算法、K-CF算法及ALS-CF，能夠達(dá)到0.89，比ALS-CF低8%.說(shuō)明本文提出的算法在評(píng)分預(yù)測(cè)的準(zhǔn)確度上是優(yōu)于其他3種算法的.

Fig. 3 The rmse comparison of four algorithms圖3 4種算法的rmse對(duì)比

2)precision和recall

推薦結(jié)果準(zhǔn)確率定義為推薦算法正確判定用戶對(duì)一個(gè)項(xiàng)目是否喜歡的比例.因此，當(dāng)用戶只有二元選擇時(shí)，使用precision，recall指標(biāo)來(lái)衡量推薦質(zhì)量，比rmse更直觀.

① http:--grouplens.org-datasets-movielens-

② http:--webscope.sandbox.yahoo.com-catalog.php?datatype=r&did=3

本實(shí)驗(yàn)除了前述4種算法CF，K-CF，ALS-CF，GK-CF，進(jìn)一步加入了基于圖的隨機(jī)游走的算法(實(shí)驗(yàn)中簡(jiǎn)稱RW算法)參與對(duì)比.各算法在MovieLens①數(shù)據(jù)集上運(yùn)行的precision和recall的實(shí)驗(yàn)結(jié)果分別如圖4、圖5所示.從圖4可以看到，GK-CF的precision與ALS-CF相當(dāng)，相對(duì)于其他3種方法優(yōu)勢(shì)較為明顯，比基準(zhǔn)CF算法precision提高25%.圖5中，GK-CF的recall相對(duì)于基準(zhǔn)CF算法、ALS-CF算法，分別提高25%，14%.

Fig. 4 The precision comparison of five algorithms圖4 5種算法的precision對(duì)比

Fig. 5 The recall comparison of five algorithms圖5 5種算法的recall對(duì)比

本文也通過(guò)不同的標(biāo)準(zhǔn)數(shù)據(jù)集對(duì)GK-CF算法與其他算法進(jìn)行了對(duì)比實(shí)驗(yàn).表5是GK-CF算法與ALS-CF算法在標(biāo)準(zhǔn)數(shù)據(jù)集Yahoo!Music 1·MB②上進(jìn)行的對(duì)比實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明，GK-CF算法的recall仍高于ALS-CF算法的recall，并且GK-CF算法的precision比ALS-CF算法的precision提高了3%.

3) 算法運(yùn)行效率

我們考察了在同樣節(jié)點(diǎn)規(guī)模的情況下，不同算法的運(yùn)行效率.基準(zhǔn)CF算法在前述實(shí)驗(yàn)中犧牲precision，recall，rmse的情況下，運(yùn)行效率較高.GK-CF與ALS-CF運(yùn)行效率相當(dāng)，說(shuō)明，GK-CF在取得較好的rmse，precision，recall的情況下，并未以犧牲算法效率為代價(jià).其實(shí)驗(yàn)結(jié)果如圖6所示.

Table 5 TherecallandprecisionComparisons Between GK-CF and ALS-CF

表5 GK-CF 與ALS-CF算法的召回率及準(zhǔn)確率對(duì)比 %

Fig. 6 The runtime comparison of five algorithms圖6 5種算法運(yùn)行時(shí)間對(duì)比

GK-CF與ALS-CF在Yahoo!Music 1·MB②數(shù)據(jù)集上的算法運(yùn)行效率如表6所示.GK-CF算法較ALS-CF算法運(yùn)行效率高.

Table 6 The Algorithm Runtime Comparisons Between GK-CF and ALS-CF表6 GK-CF 與ALS-CF算法的運(yùn)行時(shí)間對(duì)比 s

4) 加速比

在真實(shí)的物理集群環(huán)境下，節(jié)點(diǎn)的規(guī)模與并行算法的執(zhí)行效率是相關(guān)的，本文通過(guò)GK-CF，RW及ALS-CF算法的加速比實(shí)驗(yàn)，對(duì)算法在節(jié)點(diǎn)規(guī)模上的可擴(kuò)展性進(jìn)行了分析.如圖7在MovieLens①的1·MB規(guī)模數(shù)據(jù)集上，算法的加速效率較為明顯，當(dāng)集群規(guī)模從1個(gè)節(jié)點(diǎn)變換到5個(gè)節(jié)點(diǎn)時(shí)，本文提出的GK-CF算法效率有近3倍的提升，與ALS-CF算法相當(dāng).說(shuō)明本文提出的算法隨著節(jié)點(diǎn)規(guī)模的擴(kuò)展有良好的可擴(kuò)展性.RW算法的效率雖然比GK-CF和ALS-CF的算法效率低近15倍且當(dāng)其運(yùn)行于單個(gè)節(jié)點(diǎn)時(shí)算法效率過(guò)低，但其加速比有近7倍的提升，也說(shuō)明對(duì)于基于圖模型的算法求解，適合于通過(guò)并行平臺(tái)來(lái)加速執(zhí)行效率.

Fig. 7 The speedup experiment of three algorithms圖7 3種算法加速比實(shí)驗(yàn)

5 總 結(jié)

現(xiàn)有的個(gè)性化推薦系統(tǒng)不僅需要處理海量、實(shí)時(shí)的數(shù)據(jù)，而且還要響應(yīng)用戶多樣化的服務(wù)請(qǐng)求，如亞馬遜的個(gè)性化書(shū)籍推薦和YouTube的個(gè)性化視頻推薦.然而大多數(shù)推薦算法存在算法精確度不高、運(yùn)行效率低等問(wèn)題，導(dǎo)致推薦質(zhì)量受限.本文提出了一種基于圖模型和改進(jìn)KNN模型的GK-CF算法，并對(duì)算法進(jìn)行了并行化的實(shí)現(xiàn).通過(guò)建立圖數(shù)據(jù)模型及子圖分割，實(shí)現(xiàn)了對(duì)原始海量數(shù)據(jù)的分布式并行處理.利用圖拓?fù)浣Y(jié)構(gòu)及沿圖路徑信息傳播和聚合的方式提出了改進(jìn)的KNN算法，用于對(duì)每個(gè)目標(biāo)用戶的相似用戶篩選，并通過(guò)改進(jìn)的皮爾斯公式處理由于用戶過(guò)多帶來(lái)相似度計(jì)算誤差，再利用圖的最短路徑算法對(duì)目標(biāo)用戶的可推薦項(xiàng)目集合進(jìn)行快速定位，最后根據(jù)目標(biāo)用戶對(duì)項(xiàng)目的評(píng)分選出最終給用戶推薦的項(xiàng)目.我們?cè)谡鎸?shí)的集群環(huán)境下，利用標(biāo)準(zhǔn)數(shù)據(jù)集驗(yàn)證了基于并行圖的GK-CF推薦算法的有效性.實(shí)驗(yàn)結(jié)果表明，相對(duì)于基準(zhǔn)CF算法、基于模型的ALS-CF算法以及基于圖結(jié)構(gòu)的隨機(jī)游走RW算法，GK-CF算法有較好的rmse，precision，recall.同時(shí)并未以犧牲算法效率為代價(jià).本文也通過(guò)算法復(fù)雜度分析、GK-CF算法的串行化和并行化的算法運(yùn)行效率對(duì)比實(shí)驗(yàn)和Wilcoxon秩和檢驗(yàn)驗(yàn)證了GK-CF由于其并行化設(shè)計(jì)實(shí)現(xiàn)具有較好的高效性，在未來(lái)的可擴(kuò)展集群上也具有較好的算法可擴(kuò)展性.

[1]Adomavicius G, Tuzhilin A. Toward the next generation of the recommender systems: A survey of the state-of-the-art and possible extensions[J]. IEEE Trans on Knowledge and Data Engineering, 2005, 17(6): 734-749

[2]Koren Y. Factorzation meets the neighborhood: A multifaceted collaborative filtering model[C] --Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 426-434

[3]Breese J S, Heckerman D, Kadie C. Empirical analysis of predictive algorithms for collaborative flitering[C] --Proc of the 14th Conf on Uncertainty in Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 1998: 43-52

[4]Delgado J, Ishii N. Memory-based weighted-majority prediction for recommender systems[C] --Proc of the ACM SIGIR’99 Workshop Recommender Systems: Algorithms and Evaluation. New York: ACM, 1999

[5]Park Y, Park S, Jung W. Reversed CF: A fast collaborative filtering algorithm using aK-nearest neighbor graph[J]. Expert Systems with Applications, 2015, 42(8): 4022-4028

[6]Das J, Aman A K, Gupta P, et al. Scalable hierarchical collaborative filtering using BSP trees[C] -- Proc of the Int Conf on Computational Advancement in Communication Circuits and Systems. Berlin: Springer, 2015: 269-278

[7]Liu Haifeng, Hu Zheng, Mian Ahmad, et al. A new user similarity model to improve the accuracy of collaborative filtering[J]. Knowledge-Based Systems, 2014, 56(1): 156-166

[8]Xiang Liang, Yuan Quan, Zhao Shiwan, et al. Temporal recommendation on graphs via long-and short-term preference fushion[C] --Proc of the 16th ACM Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2010: 723-731

[9]Ding Yi, Li Xue. Time weight collaborative filtering[C] --Proc of the 14th ACM Int Conf on Information and Knowledge Management, New York: ACM, 2005: 485-492

[10]Koren Y. Collaborative filtering with temporal dynamics[J]. Communications of the ACM, 2010, 53(4): 89-97

[11]Sun Guangfu, Wu Le, Liu Hong, el al. Recommendations based on collaborative filtering by exploiting sequential behaviors[J]. Journal of Software, 2013, 24(11): 2721-2733 (in Chinese )(孫光福, 吳樂(lè), 劉洪, 等. 基于時(shí)序行為的協(xié)同過(guò)濾推薦算法[J]. 軟件學(xué)報(bào), 2013, 24(11): 2721-2733)

[12]Matook S, Brown S A, Rolf J. Forming an intention to act on recommendations given via online social networks[J]. European Journal of Information Systems, 2015, 24(1): 76-92

[13]Jia Dongyan, Zhang Fuzhi. A collaborative filtering recommendation algorithm based on double neighbor choosing strategy[J]. Journal of Computer Research and Development, 2013, 50(5): 1076-1084 (in Chinese )(賈冬艷, 張付志. 基于雙重鄰居選取策略的協(xié)同過(guò)濾推薦算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(5): 1076-1084)

[14]Qin Jiwei, Zheng Qinghua, Tian Feng. Collaborative filtering algorithms integrating trust and preference of user’s emotion[J]. Journal of Software, 2013, 24(Suppl 2): 61-72 (in Chinese)(秦繼偉, 鄭慶華, 田峰. 一種融合信任和用戶情感偏好的協(xié)同過(guò)濾算法[J]. 軟件學(xué)報(bào), 2013, 24(增刊2): 61-72)

[15]Alami Y, Nfaoui E, Beqqali O. Toward an effective hybrid collaborative filtering: A new approach based on matrix factorization and heuristic-based neighborhood[C] --Proc of the Intelligent Systems and Computer Vision(ISCV). Piscataway, NJ: IEEE, 2015: 51-58

[16]Santos A. A hybird recommendation system based on human curiosity[C] --Proc of the 9th ACM Conf on Recommender Systems. New York: ACM, 2015: 367-370

[17]Fouss F, Pirotte A, Renders J M, et al. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J]. IEEE Trans on Knowledge and Data Engineering, 2007, 19(3): 355-369

[18]Huang Zan, Chen Hsinchun, Zeng Daniel. Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering[J]. ACM Trans on Information System, 2004, 22(1): 116-142

[19]Aggarwal C C, Wolf J L, Wu Kun-Lung, et al. Horting hatches an egg: A new graph-theoretic approach to collaborative filtering[C] --Proc of the 5th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 1999: 201-212

[20]Onuma K, Tong H, Faloutsos C. TANGENT: A novel, surprise me, recommendation algorithm[C] --Proc of the 15th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2009: 657-666

[21]Xiang Liang, Yuan Quan, Zhao Shiwan, et al. Temporal recommendation on graphs via long-and short-term preference fusion[C] --Proc of the 16th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2010: 723-732

[22]Zhu Xia, Song Aibo, Dong Fang, et al. A collaborative filtering recommendation mechanism for cloud computing[J]. Journal of Computer Research and Development, 2014, 51(10): 2255-2269 (in Chinese )(朱夏, 宋愛(ài)波, 東方, 等. 云計(jì)算環(huán)境下基于協(xié)同過(guò)濾的個(gè)性化推薦機(jī)制[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(10): 2255-2269)

[23]Xin R S, Crankshaw D, Dave A, et al. GraphX unifying data-parallel and graph-parallel analytics[DB-OL]. Computer Science Databases. 2014[2016-04-29]. https:--arxiv.org-abs-1402.2394

[24]Quick L, Wilkinson P, Hardcastle D. Using pregel-like large scale graph processing frameworks for social network analysis[C] --Proc of 2012 IEEE-ACM Int Conf on Advances in Social Networks Analysis and Mining. Piscataway, NJ: IEEE, 2012: 457-463

[25]Zaharia M, Chowdhury M, Das T, et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[C] --Proc of the 9th USENIX Conf on Networked System Design and Implementation. Berkeley, CA: USENIX Association, 2012: 15-28

[26]Deng lin, Pei Jian, Ma Jinwen, et al. A rank sum test method for informative gene discovery[C] --Proc of the 10th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2004: 410-419

[27]Xie Juanying, Gao Hongchao. Statistical correlation andk-means based distinguishable gene subset selection algorithms[J]. Journal of Software, 2014, 25(9): 2050-2075 (in Chinese)(謝娟英, 高紅超. 基于統(tǒng)計(jì)相關(guān)性與K-Means的區(qū)分基因子集選擇算法[J]. 軟件學(xué)報(bào), 2014, 25(9): 2050-2075)

Meng Huanyu, born in 1990. Master. Her main research interests include recommender system, location-based social networks.

Liu Zhen, born in 1977. PhD, associate professor. Member of CCF. Her main research interests include recommender system, location-based social networks, cloud and virtualization.

Wang Fang, born in 1977. Associate professor. Member of CCF. Her main research interests include future network architecture, mobile and internet.

Xu Jiadong, born in 1991. Master. His main research interests include recommender system, location-based social networks.

Zhang Guoqiang, born in 1980. PhD, associate professor. Senior member of CCF. His main research interests include future network architecture, network science.

An Efficient Collaborative Filtering Algorithm Based on Graph Model and ImprovedKNN

Meng Huanyu1, Liu Zhen1, Wang Fang2, Xu Jiadong1, and Zhang Guoqiang3

1(SchoolofComputerandInformationTechnology,BeijingJiaotongUniversity,Beijing100044)2(InformationTechnologyCenter,BeijingJiaotongUniversity,Beijing100044)3(SchoolofComputerScienceandTechnology,NanjingNormalUniversity,Nanjing210023)

With the rapid development of Internet, recommender system has been considered as a typical method to deal with the over-loading of Internet information. The recommender system can partially alleviate user’s difficulty on information filtering and discover valuable information for the active user. Collaborative filtering algorithm has the advantages of domain independence and supports users’ potential interests. For these reasons, collaborative filtering has been widely used. Because the user item rating matrix is sparse and in large-scale, recommender system is facing big challenges of precision and performance. This paper puts forward a GK-CF algorithm. By building a graph-based rating data model, the traditional collaborative filtering, graph algorithms and improvedKNN algorithm have been integrated. Through the message propagation in the graph and the improved user similarity calculation model, candidate similar users will be selected firstly before the calculation of users similarity. Based on the topology of bipartite graph, the GK-CF algorithm ensures the quick and precise location of the candidate items through the shortest path algorithm. Under the parallel graph framework, GK-CF algorithm has been parallelized design and implement. The experiments on real world clusters show that: compared with the traditional collaborative filtering algorithm, the GK-CF algorithm can better improve recommendation precision and the rating accuracy. The GK-CF algorithm also has good scalability and real-time performance.

collaborative filtering; social network; graph model;KNN; shortest path

2016-04-26；

2016-10-20

國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFB1200100)；國(guó)家自然科學(xué)基金項(xiàng)目(61202429,61572256)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(2015JBM042)；江蘇省自然科學(xué)基金項(xiàng)目(BK20141454) This work was supported by the National Key Research and Development Program of China (2016YFB1200100), the National Natural Science Foundation of China (61202429, 61572256), the Fundamental Research Funds for the Central Universities (2015JBM042), and the Natural Science Foundation of Jiangsu Province of China (BK20141454).

劉真(zhliu@bjtu.edu.cn)

TP181