Spark框架下基于對比散度的網(wǎng)絡服務TLRBM推薦算法

那 勇

(吉林省遠程教育技術科技創(chuàng)新中心 吉林 長春 130022) (吉林廣播電視大學遠程教育技術中心 吉林 長春 130022)

0 引 言

Web服務是可通過網(wǎng)絡互通信的計算機應用程序，由服務提供商根據(jù)用戶需求開發(fā)，隨著互聯(lián)網(wǎng)用戶需求的不斷增加，Web服務利潤增長潛力巨大。許多服務提供商傾向于結合業(yè)務和營銷計劃進行Web服務開發(fā)，這會導致多個提供商可提供功能相似的服務。同時，Web服務推薦過程中，服務質(zhì)量取決于多種因素，如網(wǎng)絡傳輸帶寬、實現(xiàn)機制和硬件等[1-2]。因此，用戶希望從服務提供商獲得理想QoS的Web服務，例如延遲、可用性和可靠性等。然而，目前幾乎所有的服務提供商都關注利潤，每個服務的QoS屬性都由服務提供商預先確定，但在其推廣過程中，服務提供商常常對Web服務QoS進行夸大以吸引更多的用戶。因此，QoS合理評價是面向應用的Web服務推薦的重要應用之一。

協(xié)同過濾推薦是Web服務推薦的主要方法，主要分為兩類[3]：模型協(xié)同過濾和內(nèi)存協(xié)同過濾，其中內(nèi)存協(xié)同過濾采用的是Web服務評分矩陣方式進行項目的推薦和預測，常用到聚類分析算法，但是在每次計算中都需要對這個評分矩陣進行計算，算法的通用性不強；而模型協(xié)同過濾算法則是根據(jù)Web服務評分矩陣進行評價模型的演化，在后續(xù)的Web服務推薦過程中采用的就是模型預測方式取代原有評分矩陣方式，有助于提高算法計算普適性和精度。評分矩陣的模型構建方式很多，例如貝葉斯方法、馬爾可夫方法、受限玻爾茲曼機RBM(Restricted Boltzmann Machine)方法等[4]。相對而言，近年來RBM方法得到了學者們更多的研究，其采用無向圖方式進行模型構建，因此可得到魯棒性更強的評價模型，其采用可見層和隱藏層兩層模型形式。已有很多文獻研究了RBM方法應用于推薦系統(tǒng)的實現(xiàn)方式，例如文獻[5]提出一種基于RBM方法的推薦問題求解策略，利用隱藏層權重共享實現(xiàn)算法性能的提升。文獻[6]同樣基于RBM方法設計了一種推薦問題求解策略，其將實值推薦問題表示為多維0-1向量表示問題，對RBM方法進行了模型擴維，雖然提高了推薦算法的精度，但降低了算法的執(zhí)行效率。通過分析已有文獻，雖然都針對某些方面進行了改進和實現(xiàn)提高了算法的性能，但是在互聯(lián)網(wǎng)大數(shù)據(jù)時代，傳統(tǒng)的Web推薦方法在實現(xiàn)過程中存在兩個方面的問題：(1) 算法的自學習更新問題。現(xiàn)有算法模型多是固定式模型，其對于特定的Web服務推薦形式有效，但是通用效果不佳，實際應用效果不理想。Web服務推薦某些應該根據(jù)時間和需求等因素的變化具備自學習的能力，這樣才能提高算法的適應性和應用價值。(2) 具有學習能力的算法，比如神經(jīng)網(wǎng)絡算法等，雖然具備一定的學習性能，但是算法的計算過程非常復雜，算法的時效性無法得到有效滿足。對大數(shù)據(jù)的處理，如何采用并行計算方式進行模型效率提升問題，提高算法的執(zhí)行效率，是提升算法應用價值的另一個重要因素。這兩個問題是制約RBM方法在Web服務推薦過程中的應用成功與否的關鍵。

為了克服上述缺點，本文提出一種基于Spark框架下的基于兩層受限玻爾茲曼機的Web服務質(zhì)量預測模型，并基于用戶之間的直接信任關系，提出了一種基于受限玻爾茲曼機的Web服務質(zhì)量預測模型。同時為提高算法處理Web服務大數(shù)據(jù)的并行化執(zhí)行能力，采用了對比散度算法來提高收斂速度，并考慮了大數(shù)據(jù)情形采用Spark框架實現(xiàn)TLRBM模型的快速執(zhí)行算法，大幅度提升了Web服務推薦算法的計算速度。

1 理論介紹

1.1 受限玻爾茲曼機

受限玻爾茲曼機模型結構的無向二部圖如圖1所示，具有m個可見單元V=(v1,v2,…,vm)，以及n個隱藏單元H=(h1,h2,…,hn)。其中：V表示可觀測數(shù)據(jù)，H是觀測變量之間的相關性。與傳統(tǒng)玻爾茲曼機相比，RBM模型結構中同層節(jié)點之間沒有關聯(lián)性，其可見層和隱藏層的聯(lián)合構型(V,H)具有能量函數(shù)：

式中：vi和hj分別是可見單位i和隱單元j的二進制狀態(tài)；bi表示第i個可見節(jié)點的偏差，cj表示第j個可見節(jié)點的偏差；wij是單元vi和hj之間的邊緣相關聯(lián)的實值權重。

(a) 玻爾茲曼機

(b) 受限制玻爾茲曼機圖1 受限制玻爾茲曼機與傳統(tǒng)玻爾茲曼機對比

該模型下的聯(lián)合概率分布是通過Gibbs分布p(v,h)=1/Ze-E(v,h)求出所有可能的可見和隱藏向量對，其中Z=∑v,he-E(v,h)。因為隱藏單元之間沒有直接聯(lián)系，所以可簡單的獲得無偏樣本數(shù)據(jù)〈vihj〉data的條件概率如下：

類似地，可見單元之間沒有直接聯(lián)系，可獲得無偏樣本〈vihj〉model的條件概率如下：

式中:sig(x)=1/(1+e-x)是Logistic函數(shù)。為了處理數(shù)據(jù)，可通過調(diào)整權重和偏差來提高節(jié)點的概率，以降低該節(jié)點的能量并提高其他節(jié)點的能量，特別是在低能量情況下。因此，它對分割函數(shù)有很大的貢獻。具有權重的訓練向量的對數(shù)概率的導數(shù)為：

(4)

式中:〈…〉是Gibbs分布的期望。

式(3)可以反復計算直到樣本向量均位于可見層上，隱藏層是條件獨立的，并且來自〈…〉的無偏樣本，使用對比散度(CD)學習會使結果快速收斂。

1.2 用戶信任度計算

Web服務推薦過程中需要使用到用戶的評價問題，一般采用信任網(wǎng)絡模型進行表示，該網(wǎng)絡模型采用有向圖G=(U,E)表示，其中模型參數(shù)U表示信任網(wǎng)絡模型節(jié)點集，Web服務在網(wǎng)絡中以節(jié)點形式進行表示；E表示信任網(wǎng)絡模型的邊集，信任值在網(wǎng)絡中以節(jié)點之間的邊值wi形式進行表達，具體如圖2所示(以6個Web服務信任網(wǎng)絡模型為例)。

圖2 信任網(wǎng)絡模型(6個Web服務)

圖2所示信任網(wǎng)絡模型中節(jié)點之間的信任值一般采用[0,1]區(qū)間內(nèi)的實數(shù)進行表示，其可表征節(jié)點之間的信任關系。其中0表示節(jié)點之間不存在信任關系，1表示節(jié)點之間具有完全信任關系。實際的Web服務推薦過程中，節(jié)點表示的Web服務是真實存在的，但Web服務之間的關系屬性值卻不容易獲得。

對此這里選取Pearson系數(shù)作為信任網(wǎng)絡模型的Web服務之間的信任值，該值可對Web服務之間的關系屬性值進行直接表達：

(5)

2 基于并行計算的Web服務推薦

2.1 基于兩層受限玻爾茲曼機的Web服務質(zhì)量預測模型

基于兩層受限玻爾茲曼機的Web服務質(zhì)量預測模型TLRBM被解釋為具有對稱連接的隨機神經(jīng)網(wǎng)絡，其中圖形模型中的節(jié)點由兩層二進制變量組成。其中，隱藏層(h)表示對于不同服務用戶具有不同QoS值的隨機二進制特征，可見層(V)表示服務用戶、Web服務項和QoS值，但存在問題是如何有效地處理缺失的QoS值。可見層通過對稱加權連接與隱藏層連接。用Gibbs分布給出在可見層和隱層上的聯(lián)合概率分布。

令V表示m個可見單元v1,v2,…,vm的向量，其由m服務用戶和n個Web服務項目組成，稱為用戶項目矩陣。該矩陣ri,k中的每個條目表示服務用戶i在Web服務項k上觀察到的QoS值的向量(例如:響應時間、故障率等)。令F表示h個隱藏單元h=(h1,h2,…,hn)的數(shù)量，它可代表隨機二進制特征，這些特征對于不同的用戶具有不同的值。

每個服務用戶被認為是TLRBM的一個單獨的訓練案例，它有一個對稱地連接到一組二進制隱藏層的softmax可視層。然后，每個隱藏單元可以學習建模不同值之間的顯著依賴關系。每個TLRBM都有一個單獨的訓練案例，但是所有相應的權重和偏差都被綁定在一起，因此如果兩個用戶具有相同的值，那么它們的兩個TLRBM必須在該Web服務項和隱藏層的softmax可視層之間使用相同的權重。

根據(jù)圖3所示模型，對每個觀察可見層的列使用條件多項式分布softmax，對隱藏層用戶特征h使用條件多項式分布。因此，可將式(2)和式(3)推廣如下：

(7)

由于在一個層的變量之間具有獨立性，因此可簡單使用Gibbs采樣進行數(shù)據(jù)采集，其具有并行采樣特性。因此，Gibbs采樣可利用以下兩個步驟完成：基于p(h|v)對隱藏層的新狀態(tài)h進行采樣，以及基于p(v|h)對可見層的狀態(tài)v進行采樣。邊際分布可以通過求和可見向量V的所有可能值進行計算：

j=1,2,…,F

(9)

圖3 基于兩層受限玻爾茲曼機的Web服務質(zhì)量 預測模型(TLRBM)

2.2 模型學習過程

首先，提出在無條件TLRBM模型中的學習方法。盡管與圖1中的模型相比，TLRBM模型中的可見單元的激活功能已經(jīng)改變，但是其對于式(4)的學習過程是一致的。唯一區(qū)別是Gibbs采樣僅用于在非丟失的QoS值上重構分布。因此，可依據(jù)式(4)獲得如下形式參數(shù)更新：

其次，學習條件TLRBM模型與基本模型相似。但是在條件TLRBM模型中，有一個額外的學習參數(shù)D：

ΔDij=ε(〈hj〉data-〈hj〉T)ri

(12)

參數(shù)Δci的更新公式為：

Δci=ε(〈vi〉data-〈vi〉recon)vi

(13)

再次，為了進行推薦，通過在softmax單元上使用推理過程來預測缺失QoS值，然后對所有缺失QoS值執(zhí)行單個Gibbs采樣步驟。給定可見向量V的值，可預測查詢服務q的QoS值，其相對于隱藏層的數(shù)量具有時間線性關系：

2.3 TLRBM服務推薦模型

如上所述，CD學習算法使用了運行吉布斯的樣本分布，迭代(T步驟)直到收斂為止。使用稱為動量法的啟發(fā)式方法，其思想是在計算迭代t上的更新時考慮在迭代t-1處計算的更新，并且采取以下形式：

式中：a∈[0,1]。Web服務推薦的TLRBM模型算法學習過程見算法1所示。

算法1Web服務推薦的TLRBM模型學習過程

2. 令n=0，在時間n上計算預測誤差En；

3. Repeat

4. for allS集內(nèi)樣本 do

5. for all當前樣本中的udo

6. 基于可見層計算隱藏概率貢獻累積：

8. 計算隱藏狀態(tài)的概率：

pj=p(hj=1|V,r)(參見式(14))；

9. 吉布斯抽樣：令T=0；

Repeat

在開始另一次迭代之前計算誤差；

Until(++stepT

10. endfor

11. 對比貢獻積累差異:

12. 更新權重及參數(shù)：

利用式(12)更新ΔDij；

利用式(13)更新Δci；

13. endfor

14.n++；在時間n上計算預測誤差En；

15. Until(En-1-En)>ε；

2.4 基于Spark并行化實現(xiàn)

隨著現(xiàn)代互聯(lián)網(wǎng)科技的快速發(fā)展，Web服務數(shù)量呈現(xiàn)出大幅度增長趨勢，以面向Web的運行nginx系統(tǒng)的計算機數(shù)量為例，據(jù)相關統(tǒng)計，2010年大約有不到5萬臺數(shù)量，2014年的數(shù)據(jù)大約在40萬臺左右，而到了2017年，數(shù)量則大幅度增加到140萬臺左右，增長速度呈現(xiàn)出加速增長態(tài)勢。但是，目前采用單線程處理方式進行Web服務推薦已經(jīng)無法與現(xiàn)代Web服務推薦應用實際相適應，算法的執(zhí)行效率受到很大的制約。Spark并行化模型是一種采用內(nèi)存計算方式的系統(tǒng)，其具有開源屬性便于開發(fā)利用，目的是實現(xiàn)大型數(shù)據(jù)并行化處理。Spark采用的是一種具有分布式結構的彈性數(shù)據(jù)結構，可將中間計算數(shù)據(jù)在內(nèi)存中以緩存形式進行存儲，從而省去了中間硬盤讀取環(huán)節(jié)，便于計算速度的提升。

圖4 基于Spark并行化實現(xiàn)

3 實驗分析

3.1 實驗設置

為驗證所提算法的性能，選取Epinions數(shù)據(jù)集作為實驗對象，該數(shù)據(jù)集由Massa等通過爬取技術在Epinions網(wǎng)站上獲得的Web服務數(shù)據(jù)，共含有401 593個Web服務在139 528個項目上的測評結果，參見文獻[13]。設置數(shù)據(jù)集中前80%的Web服務數(shù)據(jù)構建算法模型的訓練集，剩余的20%Web服務數(shù)據(jù)構建算法模型的測試集。對Epinions中的Web服務數(shù)據(jù)進行優(yōu)化處理，對于不存在關聯(lián)屬性的Web服務數(shù)據(jù)進行刪除，可得到具有31 932個Web服務在78 893個項目上的測評結果。

實驗過程中，設定RBM模型中隱藏單元的節(jié)點數(shù)量為160，模型訓練過程的迭代次數(shù)上限是Epochs=100或者收斂精度設置為ζ=1e-5。實驗硬件配置：CPU為i5-6400k 3.0 GHz，內(nèi)存是金士頓ddr3-1600K，系統(tǒng)為Windows 10旗艦版，仿真平臺選取MATLAB 2013a。

當前Web服務推薦系統(tǒng)中大多使用推薦精度作為算法推薦效果的評價指標，其定義為模型評價結果與用戶真實評價結果之間的誤差均值絕對值指標(MAE指標)，或是根均方誤差指標(RMSE指標)。其中，MAE指標主要評價計算推薦結果與用戶真實評價結果的誤差均值：

(16)

另一評價指標RMSE指標的具體定義如下：

3.2 結果分析

選取集群節(jié)點的數(shù)量作為評估參數(shù)，考察集群節(jié)點數(shù)量變化對于算法計算性能的影響。集群節(jié)點的數(shù)量的變化區(qū)間是[1,10]，評價指標選取算法計算時間和加速比兩項指標，實驗結果如圖5所示。

圖5 集群節(jié)點數(shù)實驗影響

根據(jù)圖5所示實驗結果，橫坐標為實驗選取的計算集群節(jié)點數(shù)量，縱坐標是算法運行時間或計算加速比。根據(jù)實驗結果可知，隨計算節(jié)點數(shù)量的增加，算法的計算時間呈現(xiàn)出單調(diào)下降趨勢，而計算加速比則呈現(xiàn)出單調(diào)加速趨勢。同時也可看出，隨著集群節(jié)點數(shù)量的增加，算法的計算時間降低幅度和加速比增加幅度逐漸趨緩，主要原因是隨著節(jié)點的增加，節(jié)點之間的通信開銷逐漸增加，導致算法的計算性能增加幅度受到制約，因此對于本文選取的實驗對象選取計算節(jié)點為4是最為合適的設置方式。

下面，對算法的推薦精度和計算效率性能進行對比實驗，對比算法選取：文獻[14]、文獻[15]以及未采用Spark并行化實現(xiàn)的受限玻爾茲曼機算法(RBM)。表1給出選取不同收斂精度情況下算法的計算效率對比情況。

表1 計算效率對比 ×10 s

根據(jù)圖5實驗結果，本文算法選取集群節(jié)點數(shù)為4，另外，這里選取的收斂精度指標并不是式(16)-式(17)所定義的MAE和RMSE指標，而是式(9)所定義的能量函數(shù)指標。

根據(jù)表1結果可知，隨著收斂精度設定參數(shù)的增加，集中算法的計算時間均呈現(xiàn)出增加趨勢，因為收斂精度越高算法收斂過程所需的迭代步數(shù)越多，因此計算時間越大。同時，在幾種算法對比中，本文算法的計算時間最少，這是因為采用了并行計算方式，實現(xiàn)了多個計算節(jié)點的并行執(zhí)行，因此本文算法更加適用于互聯(lián)網(wǎng)大量服務推薦過程，并且對于不同的數(shù)據(jù)流，可通過擴展集群節(jié)點方式進行計算性能改善，具有更高的可擴展性和更高的實際應用價值。

設置迭代次數(shù)上限是Epochs=100，文獻[14]、文獻[15]、RBM算法以及本文并行算法的MAE和RMSE指標的實驗結果如圖6和圖7所示。

圖6 MAE指標對比結果

圖7 RMSE指標對比結果

根據(jù)圖6-圖7實驗結果可知，隨著迭代次數(shù)增加，幾種算法的MAE指標和RMSE指標均呈現(xiàn)出逐漸收斂趨勢。從收斂精度和速度上看，本文算法的Web服務推薦性能要顯著優(yōu)于文獻[14]、文獻[15]以及RBM算法的推薦性能。另外，文獻[15]優(yōu)于文獻[14]和RBM算法的推薦性能。其中RBM算法的推薦性能最差，收斂速度非常緩慢，這也從側面印證了本文采用的Spark并行化實現(xiàn)方式的有效性。

4 結 語

本文提出一種Spark框架實現(xiàn)的基于兩層受限玻爾茲曼機Web服務受限玻爾茲曼機推薦模型，主要貢獻如下：(1) 引入一種新的模型，通過有效的學習和推理過程從服務提供者和客戶端可實現(xiàn)Web服務QoS的實時監(jiān)控。(2) 為了有效地處理大數(shù)據(jù)集，采用了CD學習來提高收斂時間，特別是提出采用Spark并行化實現(xiàn)算法的有效拓展。下一步研究方向，主要是基于所提TLRBM模型，完成不同業(yè)務用戶QoS值信息采集以及主動用戶QoS預測系統(tǒng)的構建。