顧軍華，謝志堅，武君艷，許馨勻，張素琪

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

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

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

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

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

1 相關(guān)工作

1.1 問題定義

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

1.2 用戶相似度

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

1.3 近鄰用戶

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

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

1.4 個性化推薦

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

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

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

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

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

表 1 用戶評分示例表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)用戶開始游走后停留在某個用戶的概率越高意味著它與目標(biāo)用戶更相似。為了建立用戶網(wǎng)絡(luò)圖，首先使用式(3)計算用戶間的直接相似度，然后根據(jù)直接相似度建立用戶近鄰矩陣。為每個用戶選擇T個直接近鄰用戶，其他非T用戶的相似度置0，得到的近鄰矩陣如式(4)所示：

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

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

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

3.3 重建相似度矩陣

3.4 生成推薦結(jié)果

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

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

4.1 Spark介紹

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

4.2 相似性計算的并行化

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

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

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

具體過程如下：

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

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

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

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

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

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

5 實驗與評價

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

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

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

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

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

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

5.2 基于圖游走方法的有效性驗證實驗

5.2.1 Movielens數(shù)據(jù)集實驗

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

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

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

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

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

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

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

5.2.2 IPTV隱式評分?jǐn)?shù)據(jù)集實驗

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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