基于圖游走的并行協(xié)同過濾推薦算法

顧軍華，謝志堅(jiān)，武君艷，許馨勻，張素琪

（1. 河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院，天津 300401； 2. 河北工業(yè)大學(xué) 河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，天津 300401； 3. 天津商業(yè)大學(xué) 信息工程學(xué)院，天津 300134）

近年來隨著互聯(lián)網(wǎng)科技的發(fā)展，大數(shù)據(jù)在促進(jìn)社會(huì)進(jìn)步的同時(shí)，也帶來了“信息過載”問題。如何快速從海量數(shù)據(jù)中獲取有價(jià)值的信息成為當(dāng)前大數(shù)據(jù)發(fā)展的關(guān)鍵性問題[1]。為滿足人們?cè)诖髷?shù)據(jù)中快速獲取有價(jià)值信息的需求，推薦系統(tǒng)應(yīng)運(yùn)而生。推薦系統(tǒng)的目標(biāo)是根據(jù)用戶的個(gè)性化需求將最符合用戶喜好的信息挑選出來并推薦給用戶，以減輕用戶的選擇負(fù)擔(dān)。協(xié)同過濾推薦算法是一種目前應(yīng)用最廣泛的推薦算法[2]，可以在用戶沒有明確提出自己需求的情況下，根據(jù)用戶的行為對(duì)用戶進(jìn)行推薦。但由于大數(shù)據(jù)環(huán)境下用戶和項(xiàng)目的數(shù)量不斷增長，協(xié)同過濾推薦算法面臨著嚴(yán)重的數(shù)據(jù)稀疏性和可擴(kuò)展性問題[3]。

針對(duì)稀疏性問題，許多學(xué)者從不同角度進(jìn)行了相關(guān)研究。SUN等[4]采用聚類和時(shí)間影響因子矩陣來監(jiān)測用戶興趣漂移程度，更準(zhǔn)確的預(yù)測項(xiàng)目的評(píng)分。彭宏偉等[5]提出一種基于矩陣分解的上下文感知POI推薦模型，有效地緩解稀疏性問題。WU等[6]將異構(gòu)信息網(wǎng)絡(luò)建模為張量，并提出兩種隨機(jī)梯度下降方法同時(shí)進(jìn)行分解。MA等[7]提出了一種局部概率矩陣分解的方法，降低稀疏性的同時(shí)有效地緩解了每個(gè)局部模型的過擬合問題。以上的方法均通過緩解數(shù)據(jù)稀疏性問題來提高推薦的準(zhǔn)確度。

針對(duì)協(xié)同過濾推薦算法在處理大規(guī)模數(shù)據(jù)所遇到的可擴(kuò)展性問題，許多學(xué)者在并行方法上進(jìn)行了相關(guān)研究。楊志文[8]、LU F[9]、KUPISZ[10]等將協(xié)同過濾推薦算法部署在Hadoop和Spark并行平臺(tái)上，取得了良好的執(zhí)行效率。

本文針對(duì)協(xié)同過濾推薦算法的數(shù)據(jù)稀疏性問題和可擴(kuò)展性問題進(jìn)行研究。針對(duì)稀疏性問題，在皮爾遜相關(guān)相似度的基礎(chǔ)上引入交占比系數(shù)來計(jì)算用戶的直接相似度，提出了一種基于圖游走的協(xié)同過濾推薦算法(GW_CF)，使用圖游走的方法計(jì)算用戶的間接相似度，然后根據(jù)直接相似度和間接相似度重建用戶的相似度矩陣，最后進(jìn)行推薦。在Movielens-100k數(shù)據(jù)集和IPTV數(shù)據(jù)集上實(shí)驗(yàn)，驗(yàn)證GW_CF在提高推薦準(zhǔn)確度上的有效性。針對(duì)可擴(kuò)展性問題，在Spark平臺(tái)上實(shí)現(xiàn)GW_CF算法，并使用Movielens-1M和Movielens-100k數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，驗(yàn)證GW_CF算法的可擴(kuò)展性。

1 相關(guān)工作

1.1 問題定義

基于近鄰的協(xié)同過濾問題可以描述為[11]：已知用戶集合表示為，項(xiàng)目集合表示為，用戶-項(xiàng)目評(píng)分矩陣，表示用戶對(duì)項(xiàng)目的評(píng)分。基于近鄰的協(xié)同過濾推薦算法的流程：1)根據(jù)評(píng)分矩陣R計(jì)算用戶的相似度；2)計(jì)算目標(biāo)用戶的近鄰用戶集合；3)根據(jù)近鄰用戶的評(píng)分預(yù)測目標(biāo)用戶對(duì)未評(píng)分項(xiàng)目的評(píng)分，從而生成推薦列表。

1.2 用戶相似度

用戶相似度指用戶與用戶之間行為中表現(xiàn)出的相似程度，皮爾遜相關(guān)相似度是一種常用的計(jì)算相似度的方法，反映了兩個(gè)用戶的偏好信息的線性相關(guān)程度。用戶和用戶的皮爾遜相關(guān)相似度計(jì)算公式[12-13]如下：

1.3 近鄰用戶

近鄰用戶表示與目標(biāo)用戶偏好信息最相似的一組用戶，可以通過式(1)計(jì)算用戶的相似度，然后計(jì)算目標(biāo)用戶的近鄰用戶。目標(biāo)用戶的多個(gè)近鄰用戶組成目標(biāo)用戶的近鄰用戶集合，常用的計(jì)算近鄰用戶集合的方法分為兩類：基于數(shù)量的近鄰用戶集合和基于閾值的近鄰用戶集合。

基于閾值的近鄰用戶集合包含以目標(biāo)用戶為中心，與目標(biāo)用戶的相似度大于Value的用戶?；跀?shù)量的近鄰用戶集合包含與目標(biāo)相似度最大的Top-K個(gè)近鄰用戶。

1.4 個(gè)性化推薦

首先計(jì)算目標(biāo)用戶的近鄰用戶集合，然后對(duì)目標(biāo)用戶進(jìn)行推薦。目標(biāo)用戶對(duì)未評(píng)分項(xiàng)目預(yù)測評(píng)分的計(jì)算公式[14]如式（2），最后將預(yù)測評(píng)分最大的K個(gè)項(xiàng)目推薦給目標(biāo)用戶。

2 改進(jìn)的皮爾遜相關(guān)相似度

皮爾遜相關(guān)相似度計(jì)算方法如式(1)，僅僅考慮了用戶的共同評(píng)分項(xiàng)，而忽視了共同評(píng)分項(xiàng)目與每個(gè)用戶所有評(píng)分項(xiàng)的比例關(guān)系。這會(huì)導(dǎo)致如果兩個(gè)用戶僅有極少數(shù)共同評(píng)分項(xiàng)目，并且兩個(gè)用戶對(duì)共同評(píng)分項(xiàng)目的評(píng)分極度相似，使用皮爾遜相關(guān)相似度計(jì)算得到的用戶的相似度，遠(yuǎn)遠(yuǎn)大于用戶的真實(shí)相似度，降低了推薦的準(zhǔn)確度。例如，用戶曾對(duì)200個(gè)項(xiàng)目進(jìn)行了評(píng)分，用戶對(duì)300個(gè)項(xiàng)目進(jìn)行了評(píng)分，兩個(gè)用戶僅擁有10個(gè)共同評(píng)分項(xiàng)目，且兩個(gè)用戶對(duì)每個(gè)共同評(píng)分項(xiàng)目的評(píng)分均相同。使用傳統(tǒng)皮爾遜相關(guān)相似度計(jì)算兩者的相似度為1(兩個(gè)用戶完全相似)。但實(shí)際上，除了10個(gè)共同評(píng)分項(xiàng)目以外，用戶和用戶還各自擁有大量的非共同評(píng)分項(xiàng)目，兩個(gè)用戶的喜好并不完全相同，利用皮爾遜相關(guān)相似度得到的結(jié)果遠(yuǎn)遠(yuǎn)大于兩個(gè)用戶的真實(shí)相似度。針對(duì)這個(gè)問題，本文在皮爾遜相關(guān)相似度基礎(chǔ)上，引入交占比系數(shù)來緩解共同評(píng)分項(xiàng)占比的問題，交占比反映了兩個(gè)用戶的共同評(píng)分項(xiàng)在兩個(gè)用戶評(píng)分中的占比，加入交占比系數(shù)的皮爾遜相關(guān)相似度計(jì)算公式如下：

3 基于圖游走的協(xié)同過濾推薦算法(GW_CF)

相似度計(jì)算是協(xié)同過濾推薦算法的關(guān)鍵部分，得到用戶相似度之后可以確定用戶的近鄰用戶集合。但以往計(jì)算用戶的相似度時(shí)只考慮用戶的直接相似相似度，這樣將會(huì)遺失目標(biāo)用戶的間接近鄰用戶[15-16]。例如圖1所示，、和表示3個(gè)用戶，表示用戶的評(píng)分項(xiàng)目，表示用戶的評(píng)分項(xiàng)目，表示用戶的評(píng)分項(xiàng)目。、、表示用戶、和的相似度。依據(jù)式(3)計(jì)算用戶和用戶的相似度，由于用戶和用戶沒有共同評(píng)分項(xiàng)，所以。但是用戶和擁有共同評(píng)分項(xiàng)目和，那么，同理。由于相似性具有傳遞性，因此用戶和可以通過共同的相似用戶建立間接相似度，使得。如果兩個(gè)用戶沒有共同評(píng)分項(xiàng)目，但間接相似度大于0，稱這兩個(gè)用戶為間接近鄰用戶。在數(shù)據(jù)稀疏時(shí)，為用戶尋找間接近鄰用戶能夠有效地提高推薦的準(zhǔn)確度。本文提出了基于圖游走的方法，首先根據(jù)用戶的直接相似度矩陣建立用戶網(wǎng)絡(luò)圖，其次在用戶網(wǎng)絡(luò)圖上進(jìn)行游走計(jì)算間接相似度，然后根據(jù)間接相似度和直接相似度重建用戶的相似度矩陣，最后進(jìn)行推薦。

表 1 用戶評(píng)分示例表Table 1 User rating

圖 1 間接相似度關(guān)系圖Fig. 1 Indirect similarity diagram

3.1 構(gòu)建用戶網(wǎng)絡(luò)圖

使用用戶網(wǎng)絡(luò)圖來說明用戶間的相似關(guān)系,從目標(biāo)用戶開始游走后停留在某個(gè)用戶的概率越高意味著它與目標(biāo)用戶更相似。為了建立用戶網(wǎng)絡(luò)圖，首先使用式(3)計(jì)算用戶間的直接相似度，然后根據(jù)直接相似度建立用戶近鄰矩陣。為每個(gè)用戶選擇T個(gè)直接近鄰用戶，其他非T用戶的相似度置0，得到的近鄰矩陣如式(4)所示：

3.2 基于用戶網(wǎng)絡(luò)圖游走

在用戶網(wǎng)絡(luò)圖中存在著與其他用戶的相似度都很低甚至可以忽略不計(jì)的特殊用戶節(jié)點(diǎn)。在用戶網(wǎng)絡(luò)圖中此類節(jié)點(diǎn)只有入度，沒有出度，如圖2中節(jié)點(diǎn)D，此時(shí)由于圖中D節(jié)點(diǎn)只有入度，沒有出度，用戶網(wǎng)絡(luò)圖演變?yōu)榉菑?qiáng)連通圖，以式(5)的方法游走到圖中節(jié)點(diǎn)D時(shí)將無法跳轉(zhuǎn)到其他節(jié)點(diǎn)。整個(gè)用戶網(wǎng)絡(luò)圖的游走最終停留在類似節(jié)點(diǎn)D的死節(jié)點(diǎn)，無法求得用戶的間接相似度，因此對(duì)式(5)進(jìn)行變形如下：

圖 2 非強(qiáng)連通用戶網(wǎng)絡(luò)示例圖Fig. 2 Non-strong connected user network

3.3 重建相似度矩陣

3.4 生成推薦結(jié)果

以每個(gè)用戶頂點(diǎn)為起點(diǎn)進(jìn)行游走查找其間接相似用戶，得到重建的用戶相似度矩陣，進(jìn)一步得到目標(biāo)用戶的近鄰用戶集合。然后利用式(2)對(duì)目標(biāo)用戶的未評(píng)分項(xiàng)目進(jìn)行評(píng)分預(yù)測，并將評(píng)分最高的Top-K個(gè)項(xiàng)目推薦給目標(biāo)用戶。

4 基于圖游走的并行協(xié)同過濾推薦算法

4.1 Spark介紹

Spark是基于內(nèi)存的分布式并行計(jì)算平臺(tái)[19]，它擁有Hadoop平臺(tái)和MapReduce框架的全部優(yōu)點(diǎn)，并且Spark運(yùn)算的中間結(jié)果能存儲(chǔ)在內(nèi)存中，提高了并行計(jì)算的速度，因此Spark更適合進(jìn)行數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)等需要迭代處理算法的實(shí)現(xiàn)[19-21]。Spark集群啟動(dòng)時(shí)包括一個(gè)Master節(jié)點(diǎn)和若干個(gè)Worker節(jié)點(diǎn)，其中Master節(jié)點(diǎn)主要負(fù)責(zé)集群資源的管理，Worker節(jié)點(diǎn)主要負(fù)責(zé)數(shù)據(jù)的計(jì)算。當(dāng)在Master節(jié)點(diǎn)使用spark-submit命令提交作業(yè)時(shí)，首先在本地客戶端啟動(dòng)一個(gè)Driver進(jìn)程；Driver進(jìn)程會(huì)根據(jù)設(shè)置的參數(shù)向Master節(jié)點(diǎn)申請(qǐng)相應(yīng)的集群資源，主要有Worker節(jié)點(diǎn)個(gè)數(shù)、每個(gè)Worker節(jié)點(diǎn)上Executor的內(nèi)存和CPU數(shù)量；Master節(jié)點(diǎn)與Worker節(jié)點(diǎn)進(jìn)行通信，通知Worker節(jié)點(diǎn)啟動(dòng)Executor并向Driver進(jìn)程注冊(cè)；Driver進(jìn)程與Worker節(jié)點(diǎn)連接起來，將需要執(zhí)行的任務(wù)分配給集群中的各個(gè)Worker節(jié)點(diǎn)，Worker節(jié)點(diǎn)按照任務(wù)分配從HDFS上讀取數(shù)據(jù)并緩存到內(nèi)存中，Driver進(jìn)程對(duì)各個(gè)Worker節(jié)點(diǎn)處理完的結(jié)果進(jìn)行收集和匯總。在Spark平臺(tái)實(shí)現(xiàn)基于圖游走的協(xié)同過濾算法能夠有效地提高算法的時(shí)間效率。

4.2 相似性計(jì)算的并行化

由于皮爾遜相關(guān)相似度計(jì)算公式較為復(fù)雜，全局搜索較多，因此在實(shí)現(xiàn)本文方法并行化時(shí)引入中間變量，反映了用戶在項(xiàng)目上的相似度權(quán)重，計(jì)算公式如下：

4.3 基于圖游走的協(xié)同過濾算法并行化流程

基于圖游走的協(xié)同過濾推薦算法在Spark平臺(tái)上的并行化包括3部分，分別是讀入數(shù)據(jù)創(chuàng)建RDD、計(jì)算用戶的相似度以及生成推薦列表，該算法的并行化主要體現(xiàn)在計(jì)算用戶相似度和生成推薦列表?；趫D游走的并行協(xié)同過濾推薦算法示意圖如圖3所示。

具體過程如下：

1) 讀入用戶行為數(shù)據(jù)，構(gòu)建RDD1；

2) 將 RDD1轉(zhuǎn)換成形式的 RDD2，按照用戶ID進(jìn)行聚集得到RDD3，使用flatMap算子計(jì)算每個(gè)用戶的中間變量，并按照項(xiàng)目ID進(jìn)行聚集得到RDD4；

3) 根據(jù) RDD4計(jì)算用戶和用戶的，得到形如的RDD5,其中的1和toNum是為了便于計(jì)算交占比系數(shù)而設(shè)置的；

4) 將3)的RDD5使用ReduceByKey算子統(tǒng)計(jì)其共同評(píng)分項(xiàng)，計(jì)算結(jié)合交占比系數(shù)的相似度，得到形如的 RDD6；

5) 利用4)的相似度RDD6，構(gòu)造用戶相似度矩陣userMatrixRDD，使用Spark中的線性代數(shù)庫Breeze，調(diào)用其庫函數(shù) inv()計(jì)算userMatrixRDD的逆矩陣invMatrixRDD，進(jìn)一步通過式(7)和(8)求得得間接相似度，重建相似度矩陣得到RDD7；

6) 根據(jù)RDD7按用戶劃分得到RDD8，并進(jìn)一步得到目標(biāo)用戶的近鄰用戶集合RDD9，最后進(jìn)行推薦。

5 實(shí)驗(yàn)與評(píng)價(jià)

實(shí)驗(yàn)使用Movielens數(shù)據(jù)集和IPTV數(shù)據(jù)集[20]進(jìn)行實(shí)驗(yàn)。Movielens是一個(gè)基于Web的研究型推薦系統(tǒng)，用于接收用戶對(duì)電影的評(píng)分并提供電影的推薦列表，Movielens數(shù)據(jù)集在協(xié)同過濾研究領(lǐng)域得到了廣泛研究，也是使用最多的數(shù)據(jù)集之一。IPTV數(shù)據(jù)集來源于天津市IPTV電視用戶的收視日志數(shù)據(jù)，經(jīng)過對(duì)日志數(shù)據(jù)進(jìn)行預(yù)處理和隱式評(píng)分處理，形成IPTV數(shù)據(jù)集。相比于Movielens數(shù)據(jù)集，IPTV數(shù)據(jù)集應(yīng)用性更高。Movielens-100k數(shù)據(jù)集包含943用戶，1 682項(xiàng)目，共10萬條評(píng)分記錄；Movielens-1M數(shù)據(jù)集包含6 040個(gè)用戶和3 952個(gè)項(xiàng)目， 共計(jì)100萬條評(píng)分記錄。IPTV數(shù)據(jù)集選取193用戶，8 200項(xiàng)目，共計(jì)43 175條評(píng)分記錄。

以加速比作為可擴(kuò)展性的實(shí)驗(yàn)指標(biāo)，加速比為

5.1 相似度交占比系數(shù)的有效性驗(yàn)證實(shí)驗(yàn)

在原始的皮爾遜相關(guān)相似度的基礎(chǔ)上，為了比較加入交占比(YPCC)和未加入交占比(PCC)對(duì)預(yù)測評(píng)分誤差的影響進(jìn)行本次實(shí)驗(yàn)。此次實(shí)驗(yàn)使用Movielens-100k數(shù)據(jù)集，共943用戶，1 682個(gè)項(xiàng)目，共10萬條評(píng)分記錄，稀疏度為94.12%，訓(xùn)練集和測試集按8：2分割。實(shí)驗(yàn)結(jié)果如圖4。

圖 4 交占比系數(shù)有效性驗(yàn)證實(shí)驗(yàn)Fig. 4 Trial ratio validity validation experiment

從圖4中可以看出，協(xié)同過濾推薦算法的預(yù)測評(píng)分誤差受到近鄰用戶個(gè)數(shù)Top-K的影響。隨著近鄰用戶個(gè)數(shù)Top-K的增加，PCC和YPCC曲線均呈現(xiàn)下降趨勢(shì)并最終趨于穩(wěn)定，但是YP-CC曲線明顯低于PCC曲線，尤其Top-K在[40,60]時(shí)差距最明顯。實(shí)驗(yàn)結(jié)果表明，無論近鄰用戶個(gè)數(shù)如何選取，在皮爾遜相關(guān)相似度上加入交占比系數(shù)均可以有效地減小評(píng)分預(yù)測誤差。

5.2 基于圖游走方法的有效性驗(yàn)證實(shí)驗(yàn)

5.2.1 Movielens數(shù)據(jù)集實(shí)驗(yàn)

為了驗(yàn)證基于圖游走方法在降低評(píng)分預(yù)測誤差和提高推薦準(zhǔn)確率上的有效性，本次實(shí)驗(yàn)使用Movielens-100k數(shù)據(jù)集，訓(xùn)練集和測試集按8：2分割。先通過實(shí)驗(yàn)確定用戶直接近鄰個(gè)數(shù)T的最優(yōu)取值，然后比較在不同的推薦近鄰個(gè)數(shù)Top-K下，本文方法和基于用戶的協(xié)同過濾推薦算法(BSCF)與基于聚類的協(xié)同過濾推薦算法(kmeans_CF)的和。

圖5為選取不同直接近鄰個(gè)數(shù)時(shí)的評(píng)分預(yù)測誤差曲線，T表示直接近鄰用戶選取的個(gè)數(shù)。圖5表明，當(dāng)T＞60時(shí)，趨于穩(wěn)定。

圖 5 參數(shù)T測試圖Fig. 5 Parameter T test chart

圖6 的實(shí)驗(yàn)中T=60。推薦時(shí)近鄰用戶個(gè)數(shù)Top-K作為單一變量，對(duì)基于圖游走的協(xié)同過濾推薦算法(GW_CF)、基于用戶的協(xié)同過濾推薦算法(BSCF)、基于聚類的協(xié)同過濾推薦算法(kmeans_CF)進(jìn)行對(duì)比實(shí)驗(yàn)。圖6Top-K表示推薦時(shí)近鄰用戶選取的個(gè)數(shù)，表示評(píng)分預(yù)測的平均絕對(duì)誤差。從圖中可以看出，隨著近鄰用戶個(gè)數(shù)Top-K的增加，3條曲線均呈下降趨勢(shì)，BSCF曲線和k-means_CF曲線比較接近，GW_CF曲線明顯低于另兩條曲線，當(dāng)Top-K大于80時(shí)更加明顯。實(shí)驗(yàn)結(jié)果表明：GW_CF算法在降低評(píng)分預(yù)測誤差方面是有效的。

圖7中虛線反映了使用GW_CF推薦的準(zhǔn)確度，實(shí)線反映了使用BSCF推薦的準(zhǔn)確度。生成推薦列表時(shí)推薦項(xiàng)目數(shù)為10，從圖中可以看出，隨著近鄰用戶個(gè)數(shù)Top-K的增加，兩條曲線呈上升趨勢(shì)，GW_CF準(zhǔn)確率曲線高于BSCF曲線。實(shí)驗(yàn)結(jié)果表明，基于圖游走的協(xié)同過濾推薦算法GW_CF可以有效地提高推薦準(zhǔn)確率。

圖 6 圖游走效果圖Fig. 6 Random walk effect graph

圖 7 準(zhǔn)確率對(duì)比圖Fig. 7 Accuracy comparison chart

5.2.2 IPTV隱式評(píng)分?jǐn)?shù)據(jù)集實(shí)驗(yàn)

為了驗(yàn)證基于圖游走方法在降低評(píng)分預(yù)測誤差和提高推薦準(zhǔn)確率上的有效性，本次實(shí)驗(yàn)使用IPTV數(shù)據(jù)集，訓(xùn)練集和測試集按8：2分割。先通過實(shí)驗(yàn)確定用戶直接近鄰個(gè)數(shù)T的最優(yōu)取值，然后比較在不同的推薦近鄰個(gè)數(shù)Top-K下，基于圖游走的協(xié)同過濾推薦算法(GW_CF)和基于用戶的協(xié)同過濾推薦算法(BSCF)的和。

圖8為選取不同直接近鄰個(gè)數(shù)時(shí)的評(píng)分預(yù)測誤差曲線。 圖8表明，當(dāng)T＞20時(shí)，趨于穩(wěn)定。

圖 8 參數(shù)T測試圖Fig. 8 Parameter T test chart

圖9 的實(shí)驗(yàn)中T=20，推薦近鄰用戶Top-K作為單一變量，對(duì)基于圖游走的協(xié)同過濾推薦算法(GW_CF)和基于用戶的協(xié)同過濾推薦算法(BSCF)進(jìn)行對(duì)比實(shí)驗(yàn)。從圖9 中可以看出，隨著近鄰用戶個(gè)數(shù)Top-K的增加，兩條曲線均呈下降趨勢(shì)，GW_CF曲線明顯低于BSCF曲線。實(shí)驗(yàn)結(jié)果表明：GW_CF算法在降低評(píng)分預(yù)測誤差方面是有效的。

圖 9 圖游走效果圖Fig. 9 Random Walk Effect Graph

圖10 中生成推薦列表時(shí)推薦項(xiàng)目數(shù)為10，隨著近鄰用戶個(gè)數(shù)Top-K的增加，兩條曲線呈上升趨勢(shì)，GW_CF準(zhǔn)確率曲線趨勢(shì)更明顯并且高于BSCF曲線。實(shí)驗(yàn)結(jié)果表明，在一般情況下，GW_CF比BSCF擁有更高的推薦準(zhǔn)確率。

圖 10 準(zhǔn)確率對(duì)比圖Fig. 10 Accuracy comparison chart

5.3 基于圖游走的并行協(xié)同過濾推薦算法可擴(kuò)展性實(shí)驗(yàn)

為了驗(yàn)證基于圖游走的并行協(xié)同過濾推薦算法的可擴(kuò)展性，使用Movielens-1M和Movielens-100k數(shù)據(jù)集在Spark平臺(tái)進(jìn)行實(shí)驗(yàn)。其中1M數(shù)據(jù)集包含6 040個(gè)用戶和3 952個(gè)項(xiàng)目，共計(jì)100萬條評(píng)分記錄；100k數(shù)據(jù)集包含943用戶，1 682項(xiàng)目，共10萬條評(píng)分記錄。實(shí)驗(yàn)在Spark集群上實(shí)現(xiàn)，集群環(huán)境包括6個(gè)節(jié)點(diǎn)，一個(gè)Master節(jié)點(diǎn)，5個(gè)worker節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的配置相同，且處在同一個(gè)局域網(wǎng)內(nèi)，操作系統(tǒng)為CentOs6.5，CPU為E5-2620 v4，核心頻率2.10 GHz，節(jié)點(diǎn)內(nèi)存32 GB。加速比結(jié)果如圖11。

圖 11 加速比示意圖Fig. 11 Speed-up ratio graph

從圖11中可以看出，隨著節(jié)點(diǎn)個(gè)數(shù)的增加，加速比呈現(xiàn)上升趨勢(shì)，100萬數(shù)據(jù)集更逼近線性加速比。實(shí)驗(yàn)結(jié)果表明，并行協(xié)同過濾推薦算法在大規(guī)模數(shù)據(jù)集的情況下有較好的可擴(kuò)展性。

6 結(jié)束語

本文針對(duì)協(xié)同過濾推薦算法中的數(shù)據(jù)稀疏性問題和可擴(kuò)展性問題進(jìn)行研究。針對(duì)稀疏性問題，在基于用戶的協(xié)同過濾推薦算法的基礎(chǔ)上，首先為傳統(tǒng)的皮爾遜相關(guān)相似度引入交占比系數(shù)來計(jì)算用戶的直接相似度，其次提出一種基于圖游走方法來計(jì)算用戶間接相似度，并重建相似度矩陣和進(jìn)行推薦。針對(duì)可擴(kuò)展性問題，在Spark平臺(tái)上實(shí)現(xiàn)本文方法的并行化。通過在Movielens數(shù)據(jù)集和IPTV數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，先后驗(yàn)證了加入交占比系數(shù)和基于圖游走的方法在提高推薦準(zhǔn)確度上的有效性，以及本文方法的可擴(kuò)展性。實(shí)驗(yàn)結(jié)果表明，本文的方法在提高推薦準(zhǔn)確度上是有效的，并且在大規(guī)模數(shù)據(jù)上擁有較好的可擴(kuò)展性。