基于Spark的并行信任進化算法

黃冬平 周夏冰 劉冠峰

1(蘇州大學計算機科學與技術學院 江蘇 蘇州 215006)

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

0 引 言

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

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

RDD默認的分區函數為HashPartitioner，該函數根據key的哈希值對節點個數求余的結果進行分區，當某個key數量較多時，很容易將大量具有相同key的數據分布到同一個分區里。這種情況稱為數據傾斜，而RDD的執行時間為所有分區計算時間的最大值[3]，數據傾斜的存在不僅僅會影響運行效率，嚴重情況下會導致task運行失敗[4]。

針對上述問題，本文提出基于Spark的主從式并行MET算法——SparkMET。采用主從式架構，由主節點進行變異、交叉、選擇過程，從節點計算適應度值。并提出一種新的數據分區策略——LBP算法，在SparkMET計算適應度值之前對數據進行重分區，解決數據傾斜問題，能最大限度提高MET算法的運算效率。

1 MET算法

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

圖1 信任進化過程

1.1 適應度函數

(1)

RBi,Sj=mean(rBi,Sj)

(2)

(3)

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

1.2 變 異

MET算法變異過程如式(4)所示，利用當前信任網絡中隨機選擇的個體之間的差分向量進行變異操作，生成變異向量，每一個信任網絡為獨立個體，信任網絡里的advisors為個體的基因，F為縮放因子。

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

(4)

1.3 交 叉

MET算法交叉過程如下：

(5)

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

圖2 MET算法交叉過程

1.4 選 擇

MET算法選擇過程采用“貪婪”策略，即比較候選信任網絡TBi,g+1與當前信任網絡TBi,g的適應度值，適應度值更優的將被保留，進入下一代種群。

(6)

2 基于Spark的并行MET算法

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

2.1 信任矩陣

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

表1 信任矩陣

2.2 評分矩陣

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

表2 評分矩陣

2.3 評分矩陣填充

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

2.3.1熟悉度計算

本文用Salton指標來衡量兩個買家的熟悉度，定義如下：

(7)

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

2.3.2缺失值填充

用類似基于用戶協同過濾的思想，計算公式如下：

(8)

有時候信任網絡里的所有advisors都沒有對Sj進行過評分，此時使用Sj和Bi的評分均值進行填充：

(9)

2.4 LBP算法

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

LBP算法首先對各個分區進行采樣，這樣只運行少量的數據，不會影響程序的性能，然后根據采樣結果確定合適的分區標簽，在并行化階段，利用Spark的PartitionBy算子對數據重新劃分，相同分區標簽的數據會分布到一個RDD分區里。通過自定義分區標簽的方式，使得RDD中每個分區的信任網絡數量雖然不同，但是每個分區的advisors數量大致相同。分區標簽li的計算方法如下：

(10)

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

算法1LBP算法

輸入:待分區數據rdd；分區數P；分區買家數量Pn。

輸出:分區標簽。

1.functionLBP(rdd,P,Pn)

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

5. 根據式(10) & 樣本生成標簽

6.returnlabel

//分區標簽構成的列表

7.endfunction

8.functionMP(rdd,label)

//重分區函數

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

經LBP算法重分區后，數據傾斜問題得以解決，開始計算適應度值。此過程在計算節點進行，由于適應度值計算需利用位于主節點中的評價數據，所以主節點會把評價數據發送到計算節點供各個task使用。當task數量較多時，大量的數據傳輸不僅會浪費網絡帶寬也會增加程序的運行時間，而廣播變量(broadcast)的使用能有效解決這一問題。SparkMET算法廣播評價數據到各個計算節點，task從各自所屬節點中獲取評價數據，減少了跨節點的數據傳輸，能有效提高程序的執行速度。

適應度值計算完畢后，主節點負責收集計算結果并進行選擇過程，適應度值更小的信任網絡將被保留，進入下一輪進化過程。重復上述步驟，達到最大迭代次數時退出循環，此時的信任網絡為最優結果，與初代信任網絡相比，被排除出信任網絡的買家即為attackers。綜上所述，SparkMET算法流程如圖3所示，偽代碼如算法2所示。

圖3 SparkMET算法流程圖

算法2SparkMET算法

輸入:初代信任網絡TBi,g；信任數據Trusts；評分數據rates。

輸出:最優的信任網絡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為迭代次數

8.forBi∈TBi,gdo

9. 變異&交叉生成候選網絡TBi,g+1

10.endfor

11. bc=SC.broadcast(Rates)

//廣播

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

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

//分區標簽L1

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

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

//分區標簽L2

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

//初代信任網絡適應度值

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

//候選信任網絡適應度值

24. result=selection(fit1, fit2)

//選擇

25.TBi,g=result

//進化結果進入下次循環

26.endfor

27.returnTBi,G

28.endfunction

3 實 驗

3.1 實驗數據集及實驗環境

本文所用數據為推薦領域常用的Epinions數據集[14]，包含了49 290個買家之間的信任關系，同時還有49 290個買家對139 738個賣家的評價數據，稀疏度非常高。MET算法中的縮放因子F=0.5，交叉概率CR=0.5。本文所用實驗環境為4臺虛機搭建的Spark集群，集群配置如表3，所有程序利用Python 3.7實現。

表3 實驗集群配置

3.2 實驗及結果

3.2.1算法運行時間對比

MET算法與SparkMET算法性能對比如圖4所示，四條曲線分別表示在不同節點數下算法運行時間的變化趨勢。可以看出，隨著節點個數增加，SparkMET算法執行速度越快，且隨著迭代次數增加，加速效果趨于穩定。這是因為最耗時的適應度值計算工作是由多臺機器共同完成的，大大降低了單機運行時算法的運行時間，證明了本文算法的有效性。但是當節點數增大到4時，未達到預期的加速效果。這是因為隨著節點數增加，主節點在收集適應度值過程中，跨節點的數據傳輸消耗的時間也在增加，導致可加速部分所占比例變小。這也證明了在分布式計算中，節點數并不是越多越好，節點多了不僅會浪費資源，反而有時會適得其反，達不到預期的加速效果。

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

自動分區與LBP算法性能對比如圖5所示，兩條曲線分別表示自動分區和LBP重分區時算法單次運行時間的變化趨勢。可以看出，經LBP策略重分區后，算法運行時間低于自動分區時的運行時間。這是因為重分區后，RDD的每個分區計算時間十分接近，數據傾斜問題得到解決。

圖5 自動分區和LBP算法分區性能對比

3.2.2加速比實驗

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

Sup=T1/Tn

(11)

式中：T1為MET算法的運行時間；Tn為SparkMET算法在節點數為n時的運行時間。

圖6所示為SparkMET算法加速比，三條曲線分別表示在不同節點數時算法的加速比變化趨勢。可以看出，隨著節點個數的增加，加速效果逐漸提升，且隨著迭代次數增加，加速比趨于穩定。在節點個數大于2時，算法效率提升得更為明顯，這是因為在少量節點時，節點不僅要承擔計算任務，還要分擔一部分的資源調度任務，影響節點的計算性能。

4 結 語

為了解決MET算法運算效率低下的問題，本文提出了SparkMET算法，該算法采用主從式的工作方式，僅在最為耗時的適應度值計算過程進行并行計算。針對數據傾斜問題，本文提出了LBP算法，該算法根據各個分區的采樣結果確定分區標簽，將RDD自動分區后的數據重新分區。實驗結果表明，結合LBP分區策略的SparkMET算法能有效提高MET算法的時效性。未來將在更大規模的數據集上進行實驗，降低LBP算法重分區時shuffle過程的時間開銷，進一步提升算法的運行效率。