基于MapReduce的相似矩陣并行構(gòu)造

羅莉霞，蔣盛益

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

0 引 言

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

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

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

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

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

1 總體架構(gòu)與基本概念

1.1 總體架構(gòu)

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

圖1 所提方法總體架構(gòu)

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

(2)子項目集合內(nèi)部相似度計算?；赑earson相似性度量計算各子項目集合的相似矩陣。此過程對應(yīng)于MapReduce第二輪次計算。

(3)子項目集合間相似度計算?；赑earson相似性度量計算各子項目集合間的相似矩陣。并與第二輪次計算結(jié)果整合輸出最終的相似矩陣。此過程對應(yīng)于MapReduce第三輪次計算。

為便于后續(xù)算法設(shè)計步驟介紹，本節(jié)對相關(guān)基本概念進行必要的解釋與說明。

1.2 MapReduce

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

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

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

(3)在Reduce階段，任務(wù)跟蹤器調(diào)用帶有鍵和值列表的reduce函數(shù)，每個reduce函數(shù)執(zhí)行值列表的計算，并發(fā)出鍵值對(key3,value3)作為最終結(jié)果。

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

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

定義1 LSH函數(shù)：給定某一依賴于度量空間Q的Hash函數(shù)組H={h∶P→U}， 其表征了點域P到某整數(shù)域W的一組映射函數(shù)。對于任意一個查詢點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)內(nèi)的正常數(shù)且滿足0

選用基于P-穩(wěn)態(tài)分布的LSH函數(shù)，首先給出P-穩(wěn)態(tài)分布的定義：

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

根據(jù)上述定義，選擇P-穩(wěn)態(tài)分布的LSH函數(shù)為

(1)

(2)

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

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

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

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

1.4 Pearson相似性度量

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

圖2 用戶-項目評分列表

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

(3)

2 相似矩陣并行構(gòu)造方案

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

2.1 項目集劃分

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

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

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

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

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

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

參數(shù)含義：

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

ri,j: 對itemj的評分列表

Begin

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

End

Functionitem_set_partition.reduce (itemj,LSH)

參數(shù)含義：

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 內(nèi)部相似度計算

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

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

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

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

算法2： 子項目集合內(nèi)部相似度計算偽代碼

Funtioninternal_sim_calculation.map(key,LSH)

參數(shù)含義：

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)

參數(shù)含義：

i: 用戶id;

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

Begin

(1)Emit (i,LSH)

End

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

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

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

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

Funtionexternal_sim.map.setup()

Begin

1.LSH_table=get_LSH(LSH)

2.PEARSON_TABLE=get_statistics(PEARSON)

End

Funtionexternal_sim.map(i,Ri)

參數(shù)含義：

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)

參數(shù)含義：

Begin

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

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

End

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

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

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

3 算例驗證與結(jié)果討論

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

表1 相似性矩陣構(gòu)造算法

3.1 軟、硬件實驗參數(shù)

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

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

3.2 實驗結(jié)果

3.2.1 LSH函數(shù)執(zhí)行次數(shù)對推薦算法執(zhí)行效率的影響

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

圖3 推薦算法執(zhí)行時間隨LSH算法運行次數(shù)的變化關(guān)系

3.2.2 數(shù)據(jù)集大小對推薦算法執(zhí)行效率的影響

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

圖4 推薦算法執(zhí)行時間隨數(shù)據(jù)集規(guī)模的變化關(guān)系

3.2.3 計算節(jié)點數(shù)量對推薦算法執(zhí)行效率的影響

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

圖5 推薦算法執(zhí)行時間隨計算節(jié)點數(shù)量的變化關(guān)系

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

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

(4)

(5)

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

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

4 結(jié)束語

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