基于MapReduce的相似矩陣并行構造

羅莉霞，蔣盛益

(1.湖南信息學院 電子信息學院，湖南 長沙 410151；2.廣東外語外貿大學 信息科學與技術學院，廣東 廣州 510006)

0 引 言

推薦系統基于用戶行為大數據，根據用戶的個性化需求提供多種多樣、有針對性的解決方案[1]。其中，基于相似矩陣構造的協同過濾算法的性能高低直接決定了推薦系統的推薦精度、響應速度等關鍵性能[2]。因此，設計高性能的協同過濾推薦算法引起了研究人員的極大關注。

現有研究往往基于傳統串行平臺展開。文獻[3]提出一種基于實值的狀態玻爾茲曼機的協同過濾算法，但受限于合理狀態轉移過程的設計。文獻[4]提出基于半監督方法的協同過濾推薦算法，但存在半監督機制全局最優解求解困難的問題。文獻[5]將差分隱私保護技術引入協同過濾中，但沒有絕對的隱私泄露保護，如何根據系統的變化升級，實現保護手段的及時跟進仍是一個需要解決的問題。推薦系統的性能不僅僅受限于協同過濾算法的設計，更受制于巨維數據下協同算法中相似矩陣的構建精度[6]。

基于上述分析，針對廣泛在推薦系統中應用的基于項目(item)的協同過濾推薦算法，提出一種MapReduce框架下的相似矩陣構造方法。主要創新點在于：

(1)所提方法由于在分散的有限資源計算節點上進行，摒棄了傳統串行構造方法性能依賴于物理硬件性能的缺點，故而在大規模數據集場景下具有更好的經濟性與擴展性。

(2)提出一種改進的局部敏感哈希(locality sensitive Hashing，LSH)算法對項目集進行快速相似性劃分，與傳統Hash算法相比，所提算法能夠使相似集合有更高的概率被歸為一類，從而提升后續輪次的計算效率。

1 總體架構與基本概念

1.1 總體架構

基于項目的協同過濾推薦算法的基本思想為：①利用數理統計的方法，首先尋找與目標項目具有相近評分的鄰居項目；②對鄰居項目進行評級打分，并依據評分結果對目標項目的評分進行預測；③推薦系統選擇評分預測結果最高的前若干項作為推薦結果發送給目標用戶[7]。因此，如圖1所示，所提基于MapReduce框架的相似矩陣構造方法總體包含如下3個部分：

圖1 所提方法總體架構

(1)項目集合分解。為提升相似矩陣計算效率，基于LSH算法將不同用戶具有相似評分的項目劃分為同一組，構成子項目集合，并將不同的項目子集分配到不同的計算節點中。此過程對應于MapReduce第一輪次計算。

(2)子項目集合內部相似度計算。基于Pearson相似性度量計算各子項目集合的相似矩陣。此過程對應于MapReduce第二輪次計算。

(3)子項目集合間相似度計算。基于Pearson相似性度量計算各子項目集合間的相似矩陣。并與第二輪次計算結果整合輸出最終的相似矩陣。此過程對應于MapReduce第三輪次計算。

為便于后續算法設計步驟介紹，本節對相關基本概念進行必要的解釋與說明。

1.2 MapReduce

MapReduce作為一種分布式并行處理平臺，底層使用Hadoop分布式文件系統(Hadoop distributed file system，HDFS)可將大型文件劃分為若干個片段，以冗余的方式存儲于分散的多臺計算節點中，提高系統可靠性[8]。而MapReduce 完整的運行過程則包含三階段：映射(Map)、混洗(Shuffle)、歸約(Reduce)[9]：

(1)在Map階段，映射函數將鍵值對(key1,value1)作為輸入，執行初步計算并輸出中間鍵值對(key2,value2)；

(2)在混洗階段，對中間鍵值對進行分組，每個計算節點都被分配了相應的數據列表(key2,value_list)；

(3)在Reduce階段，任務跟蹤器調用帶有鍵和值列表的reduce函數，每個reduce函數執行值列表的計算，并發出鍵值對(key3,value3)作為最終結果。

1.3 改進的局部敏感哈希(LSH)算法

為快速衡量兩個集合的相似度，傳統手段采用局部敏感哈希(locality sensitive Hashing，LSH)算法進行度量。其基本原理為，對于相似的若干個對象賦予更高的碰撞概率，從而具有更高的可能性將它們歸類到同一個Hash“桶”中。換言之，對于不相似的那些對象則具有更高的過濾概率從而節省計算時間以提高效率。傳統的LSH函數定義如下：

定義1 LSH函數：給定某一依賴于度量空間Q的Hash函數組H={h∶P→U}， 其表征了點域P到某整數域W的一組映射函數。對于任意一個查詢點p，若滿足如下兩個條件：

(1)若q∈B(p,r)， 則Pr[h(p)=h(q)]>P1；

(2)若q?B(p,r)， 則Pr[h(p)=h(q)]>P2。

其中，B(p,r)={q|D(p,q)≤r} 表示r(>0) 為半徑、以p為中心的球； Pr[·] 為概率算子；P1和P2為(0,1)內的正常數且滿足0

選用基于P-穩態分布的LSH函數，首先給出P-穩態分布的定義：

定義2P-穩態分布： 對于包含任意N個元素的實數集合 {v1,v2,…,vN}?R和R上服從某一分布D的N個獨立同分布變量T={t1,t2,…,tN}， 若隨機變量∑l(vl·tl) 以及∑l(|tl|P)1/PT服從同一分布，則稱D是P-穩態分布的，并且可以嚴格證明， ?P∈(0,2] 均存在相應的穩態分布[10]。

根據上述定義，選擇P-穩態分布的LSH函數為

(1)

(2)

然而，根據式(1)和式(2)可知，傳統LSH算法的性能依賴于Hash函數參數的選取，故而單次使用LSH算法對集合進行相似度區分易存在較高的碰撞概率，導致本質上不相似的數據集劃分在一起，從而影響后續兩個輪次MapReduce計算的效率。因此，提出一種改進的LSH算法，其核心在于在MapReduce框架下，應用傳統LSH算法對用戶項目集合進行多次Hash處理，從而使相似集合與不相似集合相比具有更高的概率歸為一類，從而提升后續輪次相似矩陣的計算效率。主要步驟如下：

(1)以均勻分布的方式隨機選擇k個Hash函數，構成維度為k的Hash函數組，記為Hk={h∶P→Uk}， 其中h(S)=[h1(S),h2(S),…,hk(S)]；

(2)對數據集進行映射處理，從而得到數據集所對應的維度為k的Hash列表；

(3)統計k次Hash操作的Hash值(記為K)，設判定數據集相似的哈希閾值為ε。若K≥ε，則數據集是相似的；反之，若K<ε，則數據集是不相似的。

1.4 Pearson相似性度量

協同過濾推薦算法的核心在于構建“用戶-項目”相似矩陣以實現精準的推薦。如圖2所示，不妨設用戶數量與項目數量分別為m和n，Rij為用戶i(1≤i≤m)對項目j(即itemj,1≤j≤n)的評分。協同過濾推薦算法即是要構造出不同用戶在同一項目上的相似性度量矩陣，不妨記為Sim(i1,i2)，其中i1和i2為不同的用戶編號。

圖2 用戶-項目評分列表

所提算法中，采用Pearson相關性進行來自于不同用戶、對同一項目集合的相似性度量[11]。不失一般性，設用戶i1和用戶i2共同評分的項目集合為item(i1,i2)， 從而用戶i1和用戶i2之間的Pearson相似性度量值為

(3)

2 相似矩陣并行構造方案

為有效計算用戶項目的相似性矩陣，所提基于MapReduce的相似矩陣并行構造方法包含3輪次的計算過程，即：①項目集劃分；②子項目集內部相似度計算；③子項目集間相似度計算。

2.1 項目集劃分

為計算不同用戶在同一項目集合下的相似性，所提方法首先劃分用戶評分項目的評級列表。其基本思想是將類似用戶評分的項目組合在一起，以便計算第二輪中這些子項目集合的相似性，從而減少最后一輪的計算開銷。由于當項目集規模過大時對其采用傳統諸如K-means聚類的方法存在時間復雜度過高的缺點，故而采用基于1.3節所提的改進LSH算法以貪婪機制實現快速劃分。

設itemj={(i1,ri1,j),(i2,ri2,j),…,(im,rim,j)} 為m個用戶對項目j進行的評分集合。因此，當項目數量為n時，集合數量為n。其次，為了對由類似用戶評分的項目進行聚類，應用1.3節中所述的改進LSH函數，可將整體項目集合劃分為數量為n′的子項目集合，滿足n′≤n，且由1.3節可知，相似用戶評分的項目有較高的概率屬于同一組。

基于上述劃分，在次輪的相似性計算過程中，可分別計算不同子項目集的內部相似度。與傳統將項目集合考慮為整體的相似矩陣構造方法相比，所提劃分方法顯然減小了相似性計算輪次中的計算開銷。

該輪次中，map函數將三元組 (i,itemj,ri,j) 轉變為鍵值對itemj,(i,ri,j)。 在混洗階段，由于發出的鍵值對所有映射函數按每個不同的密鑰分組，具有相同秘鑰的鍵值對(即項目itemj)被分至同一組。然后，用itemj和對應的鍵值對列表調用每個reduce函數(即1.3節所提改進LSH算法)，最終按照用戶編號i以升序方式對 (i,ri,j) 進行排序，并將項目itemj和鍵值對列表存儲在名為LSH的HDFS文件中。最終，具有相同Hash值的用戶-項目評分列表被存儲在同一文件中。算法1示出了項目集劃分的偽代碼。

算法1： 項目集劃分偽代碼

Functionitem_set_partition.map(key, (i,itemj,ri,j))

參數含義：

Key: 鍵值對， 初始為空;i: 用戶id; itemj: 項目id;

ri,j: 對itemj的評分列表

Begin

(1) emit (i,itemj,ri,j)

End

Functionitem_set_partition.reduce (itemj,LSH)

參數含義：

itemj: 項目編號;

LSH: 具有相同Hash值的用戶-評分列表

Begin

(1)InputSUM=0, LSH=∞,a=1, K=0

(2)For列表LSH中的每個(i,ri,j)

doSUM=SUM+ri,j;

(3)Fora=1∶1∶k

do

If(ha(ri,j)ε)then

LSH=ha(ri,j)

(4) Append (LSH, (itemj,sort(LSH)))

End

2.2 內部相似度計算

本輪次的目的在于計算隸屬于同一子項目集合中的內部相似度。由于在上一輪次中，將具有相同Hash值的用戶項目集合存儲在同一名稱下的HDFS文件中，因此，通過掃描存儲這些文件的目錄，可以獲得文件名列表。然后，使用Hadoop API顯式地為每個映射器分配每個文件。

用于子項目集合內相似性計算的偽代碼如算法2所示。每個map函數對應于處理由若干個 (i,ri,j) 組成的列表，即LSH。在列表LSH中，所有項目具有相同的Hash值。為了獲得每個子項目集合內部的相似性，即Pearson相關性的統計數據，首先加載每個子項目集的列表LSH。在算法實現過程中，為有效查找項目itemi的統計信息，將計算得到的Pearson統計信息編制為一個新表，記為PEARSON_TABLE，從而便于第三輪次計算不同子項目集合間的相似度。

如前所述，經過LSH算法處理后的子項目集合以按照用戶編號i以升序方式對 (i,ri,j) 進行排序，并將項目itemj和鍵值對列表存儲在名為LSH的HDFS文件中。故而，對于每一個子項目集合而言，可采用線性掃描的方式根據式(3)計算子項目集合內部的相似度，隨后將計算結果存儲在HDFS文件中。

在計算完畢所有子項目集合的相似性后，將LSH中的用戶-項目評分列表重新排列為下一輪次計算的項目-評分列表，而對于項目itemj的每個用戶-項目評分對 (i,ri,j)， 發出鍵值對 (i,(itemj,ri,j))。 而在混洗階段，具有相同秘鑰i的項目-評分對 (itemj,ri,j) 被分到同一組。因此，每個reduce函數簡單地取得由單個用戶i分級的所有項目評分對的列表。

算法2： 子項目集合內部相似度計算偽代碼

Funtioninternal_sim_calculation.map(key,LSH)

參數含義：

Key： 鍵值對， 初始為空

LSH： 具有相同Hash值的用戶-評分列表

Begin

(1)InputLSH(i,ri,j)

(2) PEARSON_TABLE=get_statistics(PEARSON)

(3)ForLSH列表中的每個 (itemj1,ri1,j1)和 (itemj2,ri2,j2)

do

SUM=0;pj1=0;pj2=0;

(4)For每個(i1,ri1,j1)∈itemj1Do

For每個(i2,ri2,j2)∈itemj2Do

If(i1=i2)then

(6) Append (S, (i1,i2,Sim(i1,i2)))

(7)ForLSH中的每個(itemj,ri,j)Do

Foritemj中的每個(i,ri,j)Do

Emit (i, (itemj,ri,j))

OutputEmit (i,LSH)

End

Funtioninternal_sim_calculation.reduce (i,LSH)

參數含義：

i: 用戶id;

LSH: 具有相同Hash值的用戶-評分列表

Begin

(1)Emit (i,LSH)

End

2.3 子項目集合間相似度計算

該輪次MapReduce映射階段，每個map函數通過使用隸屬于不同子項目集合的評分rj和rj′來計算子項目集合間的相似度，記為Sim(j,j′)；而在歸約階段，通過擴充Sim(j,j′)的結果來生成最終的相似矩陣。區別于傳統串行算法以窮舉的方式計算相似矩陣，本輪次使用隸屬于不同子項目集合的評分列表{rj}和{rj′}來計算不同組件的相似性。

設用戶i對應一組項目 {itemj1,itemj2,…,itemjt}， 相應的評分列表為Ri={ri,j1,ri,j2,…,ri,jt}， 而用戶內部相似度已經在2.2節中計算給出，故而這一輪次計算中可僅使用第二輪次生成的項目-評分列表來并行計算不在同一組中的項目對的相似度。

算法3： 子項目集間相似度計算偽代碼

Funtionexternal_sim.map.setup()

Begin

1.LSH_table=get_LSH(LSH)

2.PEARSON_TABLE=get_statistics(PEARSON)

End

Funtionexternal_sim.map(i,Ri)

參數含義：

i: 用戶編號;Ri: 用戶評分列表

Begin

(1)InputRi={ri,j1,ri,j2,…,ri,jt}

(2)For對于每個用戶-評分對(i1,ri1,j1)和(i2,r2,j2)Do

(3)If

(LSH_table.lookup(itemi1)≠(LSH_table.lookup(itemi2))

then

End

Funtionexternal_sim.reduce (key, List)

參數含義：

Begin

(1)InputSUM=0,pi=0,pj=0

(3) Append (S,(i1,i2,Sim(i1,i2)))

End

其具體偽代碼如算法3所示。在調用所有映射函數之前，每個映射器的設置函數將用于計算相似性的所需統計信息，加載到PEARSON_TABLE中，并從HDFS文件PEARSON中，將每個LSH函數值分別加載到LSH中。

其次，調用map函數對不同用戶i1、i2和用戶的評分列表進性相似性計算。對于LSH中的每對項目-評分對(itemj1,ri1,j1)、(itemj2,ri2,j2)，首先檢查項目itemj1和itemj2是否屬于同一組。若屬于同一組，則已在前一輪次中已經計算得到它們的內部相似度；否則便根據式(3)計算它們的Pearson相似度，并生成鍵值對(itemj1,itemj2)。值得一提的是，由于在第一輪中利用LSH技術對類似用戶評分的項目進行聚類，故項目間的Pearson相似度較小。

在混洗階段，具有相同鍵值的鍵值對被劃分為同一組。然后，每個reduce函數使用鍵值對(itemj1,itemj2)獲取對應的用戶-評分列表，進而依據式(3)進行子項目集合間的相似度計算，最終存儲到HDFS文件中獲得最終的相似矩陣。

3 算例驗證與結果討論

為衡量所提算法的執行效率與可擴展性，選擇文獻[12]所提串行相似矩陣構造算法與文獻[13]所提兩輪次MapReduce構造算法作為對比，見表1。

表1 相似性矩陣構造算法

3.1 軟、硬件實驗參數

令所有算法在相同軟、硬件環境下運行。計算節點數量選擇為41個，包含一臺主機負責任務分配與管理以及40臺普通計算節點。主機配置為：3.5 GHz Intel Xeon E5-2697 v2 CPU, 32 GB內存以及1 T硬盤；其余計算節點配置為：3.2 GHz Intel Core i5-6500 CPU, 8 GB內存以及1 TB 硬盤。所有計算節點間通過轉發帶寬為1 Gbps的以太網交換機連接。所有計算節點均安裝Linux操作系統(Ubuntu 10.04.4版本)，底層使用Hadoop 2.0.0版本實現分布式文件管理。而所有算法則使用Javac 1.8版本進行編譯。

基準實驗中，采用常用的MovieLens公開數據集作為案例進行算法性能測試。該數據集用明尼蘇達大學Group-Lens 研究項目所開發。采用的5分制評分原則對電影從各個角度進行評分。其包含ML(100 k)、ML(1 M)、ML(10 M)和ML(20 M)這4個子數據集。對比指標選擇為不同算法在執行相同次數(設置為10次)的平均執行時間。算法的性能約束測試主要包括局部敏感哈希函數執行次數、數據集大小、計算節點數量、不同相似程度度量對執行效率的影響。

3.2 實驗結果

3.2.1 LSH函數執行次數對推薦算法執行效率的影響

首先討論LSH執行次數對項目集合分組的影響。圖3為當達到相同的相似性時，所提算法在數據集ML(20 M)上的執行時間。可以看出，隨著LSH執行次數的增加，執行時間并不嚴格隨著執行次數的增加而增加，當LSH算法執行次數從1增加到7時算法執行時間由20 163 s逐漸下降到4737 s，隨后算法執行時間將逐漸增加。這是由于當LSH算法運行足夠次數后，項目集合的相似度不再發生明顯的變化，反而會引發額外的開銷。

圖3 推薦算法執行時間隨LSH算法運行次數的變化關系

3.2.2 數據集大小對推薦算法執行效率的影響

本小節討論數據集規模對采用表1中不同相似性矩陣構造方法的推薦算法執行效率的影響。令LSH函數的執行次數為7，圖4示出了當數據集規模由ML(100 k)增加到ML(20 M)時，所有算法的執行時間均逐漸增加。由于傳統串行方法對以枚舉方式進行評分的相似度求解，因而此算法的運行時間最長，且隨著數據集規模的擴大，其運行時長也急速增大。兩輪次MapReduce方法由于缺少了LSH算法對項目進行分類，但由于采用了并行計算的方法，故而執行時間介于傳統算法與所提算法之間。此外，由圖4可以看出，所提算法與傳統算法相比，其推薦算法運行時間比文獻[12]和文獻[13]所提算法在數據集規模較大時分別縮短了34.5%和14.4%。實驗結果表明所提算法具有更高的執行效率，同時也表明所提算法對更大規模數據集場景時展現出了良好的可擴展性。

圖4 推薦算法執行時間隨數據集規模的變化關系

3.2.3 計算節點數量對推薦算法執行效率的影響

本小節討論計算節點數量對推薦算法執行效率的影響，設LSH函數的執行次數仍為7，數據集仍使用ML(20 M)。如圖5所示，由于傳統串行算法不考慮分布式計算框架，因此算法運行時間保持不變；而對于后兩者算法而言，當計算節點從11變化到51時，所有相似矩陣構造方法下的推薦算法執行時間均逐漸下降。然而，與其它相似矩陣構造方法相比，所提算法在所有的實驗設置場景下均具有最小的執行時間，且比其它兩種算法的執行時間分別節約26.4%和14.4%以上。上述實驗結果表明，所提算法對新擴充的計算節點具有更優異的擴展性，能夠使計算節點具有更短的計算時間，從而進一步驗證明所提算法具有更快的執行效率。

圖5 推薦算法執行時間隨計算節點數量的變化關系

3.2.4 不同相似性度量方法對算法執行效率的影響

此外，由于相似性度量方法除Pearson相似性外，還有余弦相似性[14]和Jaccard相似性兩種[15]，分別如式(4)和式(5)所示。因此，本小節進一步考察采用所提相似矩陣構造算法時，不同相似性度量策略下對推薦算法執行效率的影響。設LSH函數執行次數為7，數據集選用ML(20 M)

(4)

(5)

圖6示出了不同相似性度量方法下推薦算法的運行時間。可以看出，在相同實驗條件下，Pearson相似性度量比余弦相似性度量和Jaccard相似性度量的運行時間分別高1196 s和926 s。其原因在于，從式(3)-式(5)可以看出，Pearson相似性度量需要獲取用戶編號和對應的項目評分兩種統計信息，而余弦相似性度量和Jaccard相似性度量則僅需要其中的一種，因而計算效率上而言Pearson相似性度量慢于后兩者，而后兩者的計算效率則相差不大。

圖6 不同相似性度量方法下推薦算法運行時間

4 結束語

針對海量數據下推薦算法性能提升瓶頸問題，提出了基于3輪次MapReduce計算的相似矩陣并行構造方法，包含3個主要部分：項目集合劃分、子項目集內部相似性計算和子項目集間相似性計算。在首輪次項目集合劃分時，提出了利用多次LSH算法進行項目集合快速劃分的改進算法，從而提升了后續輪次計算時的運行效率。實驗結果表明，與傳統方法相比，所提算法具備良好的執行效率與可擴展性。未來工作將深入研究不同相似性度量方法下推薦系統的推薦性能提升策略。