羅莉霞，蔣盛益

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

0 引 言

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

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

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

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

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

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

1.1 總體架構(gòu)

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

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

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

(2)子項(xiàng)目集合內(nèi)部相似度計(jì)算。基于Pearson相似性度量計(jì)算各子項(xiàng)目集合的相似矩陣。此過程對(duì)應(yīng)于MapReduce第二輪次計(jì)算。

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

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

1.2 MapReduce

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

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

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

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

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

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

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

(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)分布： 對(duì)于包含任意N個(gè)元素的實(shí)數(shù)集合 {v1,v2,…,vN}?R和R上服從某一分布D的N個(gè)獨(dú)立同分布變量T={t1,t2,…,tN}， 若隨機(jī)變量∑l(vl·tl) 以及∑l(|tl|P)1/PT服從同一分布，則稱D是P-穩(wěn)態(tài)分布的，并且可以嚴(yán)格證明， ?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算法對(duì)集合進(jìn)行相似度區(qū)分易存在較高的碰撞概率，導(dǎo)致本質(zhì)上不相似的數(shù)據(jù)集劃分在一起，從而影響后續(xù)兩個(gè)輪次MapReduce計(jì)算的效率。因此，提出一種改進(jìn)的LSH算法，其核心在于在MapReduce框架下，應(yīng)用傳統(tǒng)LSH算法對(duì)用戶項(xiàng)目集合進(jìn)行多次Hash處理，從而使相似集合與不相似集合相比具有更高的概率歸為一類，從而提升后續(xù)輪次相似矩陣的計(jì)算效率。主要步驟如下：

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

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

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

1.4 Pearson相似性度量

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

圖2 用戶-項(xiàng)目評(píng)分列表

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

(3)

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

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

2.1 項(xiàng)目集劃分

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

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

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

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

算法1： 項(xiàng)目集劃分偽代碼

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

參數(shù)含義：

Key: 鍵值對(duì)， 初始為空;i: 用戶id; itemj: 項(xiàng)目id;

ri,j: 對(duì)itemj的評(píng)分列表

Begin

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

End

Functionitem_set_partition.reduce (itemj,LSH)

參數(shù)含義：

itemj: 項(xiàng)目編號(hào);

LSH: 具有相同Hash值的用戶-評(píng)分列表

Begin

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

(2)For列表LSH中的每個(gè)(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)部相似度計(jì)算

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

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

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

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

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

Funtioninternal_sim_calculation.map(key,LSH)

參數(shù)含義：

Key： 鍵值對(duì)， 初始為空

LSH： 具有相同Hash值的用戶-評(píng)分列表

Begin

(1)InputLSH(i,ri,j)

(2) PEARSON_TABLE=get_statistics(PEARSON)

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

do

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

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

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

If(i1=i2)then

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

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

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

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

OutputEmit (i,LSH)

End

Funtioninternal_sim_calculation.reduce (i,LSH)

參數(shù)含義：

i: 用戶id;

LSH: 具有相同Hash值的用戶-評(píng)分列表

Begin

(1)Emit (i,LSH)

End

2.3 子項(xiàng)目集合間相似度計(jì)算

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

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

算法3： 子項(xiàng)目集間相似度計(jì)算偽代碼

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: 用戶編號(hào);Ri: 用戶評(píng)分列表

Begin

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

(2)For對(duì)于每個(gè)用戶-評(píng)分對(duì)(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ù)之前，每個(gè)映射器的設(shè)置函數(shù)將用于計(jì)算相似性的所需統(tǒng)計(jì)信息，加載到PEARSON_TABLE中，并從HDFS文件PEARSON中，將每個(gè)LSH函數(shù)值分別加載到LSH中。

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

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

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

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

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

3.1 軟、硬件實(shí)驗(yàn)參數(shù)

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

(4)

(5)

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

圖6 不同相似性度量方法下推薦算法運(yùn)行時(shí)間

4 結(jié)束語

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