基于Spark的并行信任進(jìn)化算法

黃冬平 周夏冰 劉冠峰

1(蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 江蘇 蘇州 215006)

2(上交所技術(shù)有限責(zé)任公司 上海 200120)

0 引 言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，電子商務(wù)平臺(tái)在人們的生活中扮演著越來越重要的角色，在以信任為導(dǎo)向的電子商務(wù)平臺(tái)中，如亞馬遜、Epinions等，買家在完成一筆交易后，可以根據(jù)自己的購買體驗(yàn)寫下相應(yīng)的評價(jià)，這些評價(jià)對所有人都是可見的，買家也可以根據(jù)自己的購買體驗(yàn)對已有的評價(jià)進(jìn)行評分：有幫助、無幫助等[1]。大多數(shù)潛在買家在購買之前都會(huì)參考這些買家(advisors)的評價(jià)，根據(jù)賣家聲譽(yù)的好壞決定是否進(jìn)行購買。然而，有些不誠實(shí)的買家(attackers)會(huì)提供虛假評價(jià)，造成錯(cuò)誤推薦。Jiang等[2]提出的信任進(jìn)化(MET)算法對于鑒別attackers有著非常好的效果，但是當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，MET算法的運(yùn)算效率很低。而并行計(jì)算框架的出現(xiàn)，成為解決這一問題的重要途徑。

現(xiàn)今主流的并行計(jì)算框架有MapReduce、Spark等。相比于MapReduce，Spark是基于內(nèi)存的編程框架，中間結(jié)果可存儲(chǔ)在內(nèi)存中，降低了數(shù)據(jù)交換的訪問延遲，因而Spark運(yùn)算速度要高于MapReduce。Spark的操作都是基于彈性分布式數(shù)據(jù)集(RDD)進(jìn)行的，且自帶豐富的算子，如map、reduce、filter、collect等，只需用很少的代碼就可以實(shí)現(xiàn)復(fù)雜的并行操作，相比于MapReduce來說，Spark的運(yùn)算效率更高、代碼更靈活。

RDD默認(rèn)的分區(qū)函數(shù)為HashPartitioner，該函數(shù)根據(jù)key的哈希值對節(jié)點(diǎn)個(gè)數(shù)求余的結(jié)果進(jìn)行分區(qū)，當(dāng)某個(gè)key數(shù)量較多時(shí)，很容易將大量具有相同key的數(shù)據(jù)分布到同一個(gè)分區(qū)里。這種情況稱為數(shù)據(jù)傾斜，而RDD的執(zhí)行時(shí)間為所有分區(qū)計(jì)算時(shí)間的最大值[3]，數(shù)據(jù)傾斜的存在不僅僅會(huì)影響運(yùn)行效率，嚴(yán)重情況下會(huì)導(dǎo)致task運(yùn)行失敗[4]。

針對上述問題，本文提出基于Spark的主從式并行MET算法——SparkMET。采用主從式架構(gòu)，由主節(jié)點(diǎn)進(jìn)行變異、交叉、選擇過程，從節(jié)點(diǎn)計(jì)算適應(yīng)度值。并提出一種新的數(shù)據(jù)分區(qū)策略——LBP算法，在SparkMET計(jì)算適應(yīng)度值之前對數(shù)據(jù)進(jìn)行重分區(qū)，解決數(shù)據(jù)傾斜問題，能最大限度提高M(jìn)ET算法的運(yùn)算效率。

1 MET算法

MET算法吸收傳統(tǒng)差分進(jìn)化(DE)算法的原理，其工作方式與DE算法類似[5]。圖1為信任進(jìn)化過程原理圖，一開始買家B2信任B3，但是B2發(fā)現(xiàn)自己的購買體驗(yàn)與B3對賣家S1的評價(jià)相差較大，卻與B1的評價(jià)相似，于是B2開始信任B1，不信任B3。此過程為B2的信任進(jìn)化過程[6]。

圖1 信任進(jìn)化過程

1.1 適應(yīng)度函數(shù)

(1)

RBi,Sj=mean(rBi,Sj)

(2)

(3)

式中：rBi,Sj∈[1,5]表示買家Bi對賣家Sj的評價(jià)；rAk,Sj∈[1,5]表示advisorAk對Sj的評價(jià)。

1.2 變 異

MET算法變異過程如式(4)所示，利用當(dāng)前信任網(wǎng)絡(luò)中隨機(jī)選擇的個(gè)體之間的差分向量進(jìn)行變異操作，生成變異向量，每一個(gè)信任網(wǎng)絡(luò)為獨(dú)立個(gè)體，信任網(wǎng)絡(luò)里的advisors為個(gè)體的基因，F(xiàn)為縮放因子。

VBi,g+1=TB1,g+F·(TB2,g-TB3,g)

(4)

1.3 交 叉

MET算法交叉過程如下：

(5)

式中：rk(0,1)∈[0,1]為隨機(jī)生成的小數(shù)；CR為交叉概率；jr∈[1,NP]為隨機(jī)生成的整數(shù)；TBi,j,g+1為候選信任網(wǎng)絡(luò)中的基因；VBi,j,g+1為差分向量的基因；TBi,j,g為初代信任網(wǎng)絡(luò)的基因，即圖2中的交叉單元。

圖2 MET算法交叉過程

1.4 選 擇

MET算法選擇過程采用“貪婪”策略，即比較候選信任網(wǎng)絡(luò)TBi,g+1與當(dāng)前信任網(wǎng)絡(luò)TBi,g的適應(yīng)度值，適應(yīng)度值更優(yōu)的將被保留，進(jìn)入下一代種群。

(6)

2 基于Spark的并行MET算法

譚旭杰等[7]結(jié)合Spark框架提出了一種基于島模型[8]的并行差分進(jìn)化算法——SparkDE。該算法將初代種群分成多個(gè)島，每個(gè)島單獨(dú)進(jìn)化指定的代數(shù)后，按照環(huán)形拓?fù)浣Y(jié)構(gòu)將最優(yōu)個(gè)體遷移到其他島替換最差個(gè)體，如此循環(huán)直到達(dá)到最大迭代次數(shù)為止。雖然MET算法與DE算法在工作形式上類似，但是該島模型不適用于MET算法，因?yàn)镸ET算法在并行化過程中，需跨節(jié)點(diǎn)獲取其他個(gè)體的信息，而不是僅僅在某個(gè)島中單獨(dú)進(jìn)化，因此大量的節(jié)點(diǎn)通信反而會(huì)導(dǎo)致更多的時(shí)間開銷。凌實(shí)等[9]提出的主從式工作方式僅在適應(yīng)度值計(jì)算過程實(shí)現(xiàn)并行化，與其他并行化方式相比，不改變原算法的工作方式，在進(jìn)化過程中也無節(jié)點(diǎn)通信，既能保證原算法運(yùn)算結(jié)果的準(zhǔn)確性，又能以較小的開銷得到良好的加速效果[10]?；诖?，本文提出了主從式的并行MET算法——SparkMET。

2.1 信任矩陣

DE算法的變異和交叉過程，要求個(gè)體的基因數(shù)必須相等，MET算法也是如此，由圖2中的交叉過程可以看出，初代信任網(wǎng)絡(luò)和差分向量的基因數(shù)是相等的。然而在真實(shí)數(shù)據(jù)里，每個(gè)買家的信任網(wǎng)絡(luò)里advisors數(shù)幾乎都不一樣。為此，本文將信任數(shù)據(jù)構(gòu)造成信任矩陣，使得個(gè)體的基因數(shù)相等，如表1所示[11]。信任矩陣的維度為n×n(n為買家數(shù)量，n≥3)，每一行代表一個(gè)信任網(wǎng)絡(luò)，即DE算法里種群中的個(gè)體，每個(gè)信任網(wǎng)絡(luò)包含n個(gè)基因，每個(gè)基因的取值范圍是[0,1]。MET算法的變異和交叉過程都是基于信任矩陣的向量進(jìn)行的。

表1 信任矩陣

2.2 評分矩陣

評分矩陣類似信任矩陣，行代表買家，列代表賣家，評分?jǐn)?shù)據(jù)范圍是[1,5]，分值越大代表評價(jià)越高，1表示很不喜歡，5表示很喜歡，空值表示買家未對該賣家評價(jià)，如表2所示[12]。由于很多買家只提供了少許評價(jià)，因此該評分矩陣十分稀疏。

表2 評分矩陣

2.3 評分矩陣填充

f(TBi)通過比較Bi與advisors共同評價(jià)過的賣家的評分差值來衡量Bi的信任網(wǎng)絡(luò)質(zhì)量，但是實(shí)際數(shù)據(jù)集中，由于評分?jǐn)?shù)據(jù)非常稀疏，要找到Bi與所有advisors共同評價(jià)過的賣家非常難，為此本文利用郭蘭杰等[13]提出的填充算法對評分?jǐn)?shù)據(jù)進(jìn)行預(yù)測填充。該填充算法原理：兩個(gè)買家的信任網(wǎng)絡(luò)里共同的advisors越多，這兩個(gè)買家越熟悉，而越熟悉的買家越可能有相似的購買體驗(yàn)。

2.3.1熟悉度計(jì)算

本文用Salton指標(biāo)來衡量兩個(gè)買家的熟悉度，定義如下：

(7)

式中：STBi,Bj表示買家Bi和Bj的熟悉程度；k(Bi)和k(Bj)分別為Bi和Bj的度，即advisors數(shù)。

2.3.2缺失值填充

用類似基于用戶協(xié)同過濾的思想，計(jì)算公式如下：

(8)

有時(shí)候信任網(wǎng)絡(luò)里的所有advisors都沒有對Sj進(jìn)行過評分，此時(shí)使用Sj和Bi的評分均值進(jìn)行填充：

(9)

2.4 LBP算法

評分矩陣填充好后，開始信任進(jìn)化過程，在此之前，先將信任數(shù)據(jù)轉(zhuǎn)換成key-value格式，便于適應(yīng)度值計(jì)算，得到信任網(wǎng)絡(luò)數(shù)據(jù)：[(1，[2，3，5，6，…])，(2，[1，5，…]),…]，每個(gè)信任網(wǎng)絡(luò)為一個(gè)key-value鍵值對，key為買家id，value為advisors組成的列表。由于各個(gè)買家的advisors數(shù)量不一，甚至相差懸殊，RDD自動(dòng)分區(qū)過程中，advisors較多的買家很容易被分到同一分區(qū)，造成數(shù)據(jù)傾斜，導(dǎo)致并行化過程中RDD計(jì)算時(shí)間增加，而經(jīng)LBP算法分區(qū)后能有效解決這一問題。

LBP算法首先對各個(gè)分區(qū)進(jìn)行采樣，這樣只運(yùn)行少量的數(shù)據(jù)，不會(huì)影響程序的性能，然后根據(jù)采樣結(jié)果確定合適的分區(qū)標(biāo)簽，在并行化階段，利用Spark的PartitionBy算子對數(shù)據(jù)重新劃分，相同分區(qū)標(biāo)簽的數(shù)據(jù)會(huì)分布到一個(gè)RDD分區(qū)里。通過自定義分區(qū)標(biāo)簽的方式，使得RDD中每個(gè)分區(qū)的信任網(wǎng)絡(luò)數(shù)量雖然不同，但是每個(gè)分區(qū)的advisors數(shù)量大致相同。分區(qū)標(biāo)簽li的計(jì)算方法如下：

(10)

式中：i∈[1,P-1]，i=0時(shí)，l0=0；P表示分區(qū)個(gè)數(shù)；SPi表示采樣數(shù)據(jù)中第i個(gè)分區(qū)的Value數(shù)量；S表示采樣數(shù)據(jù)的Value數(shù)量；num表示買家數(shù)量。LBP算法偽代碼如算法1所示。

算法1LBP算法

輸入:待分區(qū)數(shù)據(jù)rdd；分區(qū)數(shù)P；分區(qū)買家數(shù)量Pn。

輸出:分區(qū)標(biāo)簽。

1.functionLBP(rdd,P,Pn)

2. Sample=rdd.sample(False,0.5)〗3. .map(lambdax:len(x[1]))〗4. .mapPartitions(sum).collect()

5. 根據(jù)式(10) & 樣本生成標(biāo)簽

6.returnlabel

//分區(qū)標(biāo)簽構(gòu)成的列表

7.endfunction

8.functionMP(rdd,label)

//重分區(qū)函數(shù)

9.ifrdd≤label[0]then

10.return0

11. …

12.elseifrdd≤label[n-2]then

13.returnn-2

14.else

15.returnn-1

16.endif

17.endfunction

經(jīng)LBP算法重分區(qū)后，數(shù)據(jù)傾斜問題得以解決，開始計(jì)算適應(yīng)度值。此過程在計(jì)算節(jié)點(diǎn)進(jìn)行，由于適應(yīng)度值計(jì)算需利用位于主節(jié)點(diǎn)中的評價(jià)數(shù)據(jù)，所以主節(jié)點(diǎn)會(huì)把評價(jià)數(shù)據(jù)發(fā)送到計(jì)算節(jié)點(diǎn)供各個(gè)task使用。當(dāng)task數(shù)量較多時(shí)，大量的數(shù)據(jù)傳輸不僅會(huì)浪費(fèi)網(wǎng)絡(luò)帶寬也會(huì)增加程序的運(yùn)行時(shí)間，而廣播變量(broadcast)的使用能有效解決這一問題。SparkMET算法廣播評價(jià)數(shù)據(jù)到各個(gè)計(jì)算節(jié)點(diǎn)，task從各自所屬節(jié)點(diǎn)中獲取評價(jià)數(shù)據(jù)，減少了跨節(jié)點(diǎn)的數(shù)據(jù)傳輸，能有效提高程序的執(zhí)行速度。

適應(yīng)度值計(jì)算完畢后，主節(jié)點(diǎn)負(fù)責(zé)收集計(jì)算結(jié)果并進(jìn)行選擇過程，適應(yīng)度值更小的信任網(wǎng)絡(luò)將被保留，進(jìn)入下一輪進(jìn)化過程。重復(fù)上述步驟，達(dá)到最大迭代次數(shù)時(shí)退出循環(huán)，此時(shí)的信任網(wǎng)絡(luò)為最優(yōu)結(jié)果，與初代信任網(wǎng)絡(luò)相比，被排除出信任網(wǎng)絡(luò)的買家即為attackers。綜上所述，SparkMET算法流程如圖3所示，偽代碼如算法2所示。

圖3 SparkMET算法流程圖

算法2SparkMET算法

輸入:初代信任網(wǎng)絡(luò)TBi,g；信任數(shù)據(jù)Trusts；評分?jǐn)?shù)據(jù)rates。

輸出:最優(yōu)的信任網(wǎng)絡(luò)TBi,G。

1.functionSalton(Trusts,rates)

2. 利用式(8)-式(9)更新評分

3.returnRates

4.endfunction

//填充評分矩陣

5.functionSparkMET(TBi,g,Rates,G)

6. SC=SparkContext()

7.forg∈Gdo

//G為迭代次數(shù)

8.forBi∈TBi,gdo

9. 變異&交叉生成候選網(wǎng)絡(luò)TBi,g+1

10.endfor

11. bc=SC.broadcast(Rates)

//廣播

12. rdd1=SC.Parallalize(TBi,g)

13. L1=LBP(rdd1,P,num)

//分區(qū)標(biāo)簽L1

14. rdd2=SC.Parallalize(TBi,g+1)

15. L2=LBP(rdd2,P,num)

//分區(qū)標(biāo)簽L2

16. fit1=rdd1〗17. .partitionBy(n,lambdax:MP(x,L1)〗18. .map(lambdax:f(x,bc.value))〗19. .collect()

//初代信任網(wǎng)絡(luò)適應(yīng)度值

20. fit2=rdd2〗21. .partitionBy(n,lambdax:MP(x,L2)〗22. .map(lambdax:f(x,bc.value))〗23. .collect()

//候選信任網(wǎng)絡(luò)適應(yīng)度值

24. result=selection(fit1, fit2)

//選擇

25.TBi,g=result

//進(jìn)化結(jié)果進(jìn)入下次循環(huán)

26.endfor

27.returnTBi,G

28.endfunction

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)集及實(shí)驗(yàn)環(huán)境

本文所用數(shù)據(jù)為推薦領(lǐng)域常用的Epinions數(shù)據(jù)集[14]，包含了49 290個(gè)買家之間的信任關(guān)系，同時(shí)還有49 290個(gè)買家對139 738個(gè)賣家的評價(jià)數(shù)據(jù)，稀疏度非常高。MET算法中的縮放因子F=0.5，交叉概率CR=0.5。本文所用實(shí)驗(yàn)環(huán)境為4臺(tái)虛機(jī)搭建的Spark集群，集群配置如表3，所有程序利用Python 3.7實(shí)現(xiàn)。

表3 實(shí)驗(yàn)集群配置

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

3.2.1算法運(yùn)行時(shí)間對比

MET算法與SparkMET算法性能對比如圖4所示，四條曲線分別表示在不同節(jié)點(diǎn)數(shù)下算法運(yùn)行時(shí)間的變化趨勢?？梢钥闯?，隨著節(jié)點(diǎn)個(gè)數(shù)增加，SparkMET算法執(zhí)行速度越快，且隨著迭代次數(shù)增加，加速效果趨于穩(wěn)定。這是因?yàn)樽詈臅r(shí)的適應(yīng)度值計(jì)算工作是由多臺(tái)機(jī)器共同完成的，大大降低了單機(jī)運(yùn)行時(shí)算法的運(yùn)行時(shí)間，證明了本文算法的有效性。但是當(dāng)節(jié)點(diǎn)數(shù)增大到4時(shí)，未達(dá)到預(yù)期的加速效果。這是因?yàn)殡S著節(jié)點(diǎn)數(shù)增加，主節(jié)點(diǎn)在收集適應(yīng)度值過程中，跨節(jié)點(diǎn)的數(shù)據(jù)傳輸消耗的時(shí)間也在增加，導(dǎo)致可加速部分所占比例變小。這也證明了在分布式計(jì)算中，節(jié)點(diǎn)數(shù)并不是越多越好，節(jié)點(diǎn)多了不僅會(huì)浪費(fèi)資源，反而有時(shí)會(huì)適得其反，達(dá)不到預(yù)期的加速效果。

圖4 MET算法和SparkMET算法性能對比

自動(dòng)分區(qū)與LBP算法性能對比如圖5所示，兩條曲線分別表示自動(dòng)分區(qū)和LBP重分區(qū)時(shí)算法單次運(yùn)行時(shí)間的變化趨勢?？梢钥闯?，經(jīng)LBP策略重分區(qū)后，算法運(yùn)行時(shí)間低于自動(dòng)分區(qū)時(shí)的運(yùn)行時(shí)間。這是因?yàn)橹胤謪^(qū)后，RDD的每個(gè)分區(qū)計(jì)算時(shí)間十分接近，數(shù)據(jù)傾斜問題得到解決。

圖5 自動(dòng)分區(qū)和LBP算法分區(qū)性能對比

3.2.2加速比實(shí)驗(yàn)

加速比(Sup)能很好地反映集群的加速效果[15]，其定義如下：

Sup=T1/Tn

(11)

式中：T1為MET算法的運(yùn)行時(shí)間；Tn為SparkMET算法在節(jié)點(diǎn)數(shù)為n時(shí)的運(yùn)行時(shí)間。

圖6所示為SparkMET算法加速比，三條曲線分別表示在不同節(jié)點(diǎn)數(shù)時(shí)算法的加速比變化趨勢?？梢钥闯?，隨著節(jié)點(diǎn)個(gè)數(shù)的增加，加速效果逐漸提升，且隨著迭代次數(shù)增加，加速比趨于穩(wěn)定。在節(jié)點(diǎn)個(gè)數(shù)大于2時(shí)，算法效率提升得更為明顯，這是因?yàn)樵谏倭抗?jié)點(diǎn)時(shí)，節(jié)點(diǎn)不僅要承擔(dān)計(jì)算任務(wù)，還要分擔(dān)一部分的資源調(diào)度任務(wù)，影響節(jié)點(diǎn)的計(jì)算性能。

4 結(jié) 語

為了解決MET算法運(yùn)算效率低下的問題，本文提出了SparkMET算法，該算法采用主從式的工作方式，僅在最為耗時(shí)的適應(yīng)度值計(jì)算過程進(jìn)行并行計(jì)算。針對數(shù)據(jù)傾斜問題，本文提出了LBP算法，該算法根據(jù)各個(gè)分區(qū)的采樣結(jié)果確定分區(qū)標(biāo)簽，將RDD自動(dòng)分區(qū)后的數(shù)據(jù)重新分區(qū)。實(shí)驗(yàn)結(jié)果表明，結(jié)合LBP分區(qū)策略的SparkMET算法能有效提高M(jìn)ET算法的時(shí)效性。未來將在更大規(guī)模的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，降低LBP算法重分區(qū)時(shí)shuffle過程的時(shí)間開銷，進(jìn)一步提升算法的運(yùn)行效率。