一種用于服務質(zhì)量預測的混合協(xié)同過濾方法

蘇 凱，馬良荔，劉 霞，郭曉明

(1.海軍工程大學裝備經(jīng)濟管理系，湖北武漢430033;2.海軍工程大學計算機工程系，湖北武漢430033;3.海軍工程大學 訓練部，湖北 武漢430033)

在Web服務組合流程構(gòu)建過程中，需要為流程中的各個功能結(jié)點選擇相應的實體Web服務。隨著面向服務計算技術的發(fā)展，網(wǎng)絡上出現(xiàn)了大量功能相似但服務質(zhì)量(QoS)各異的服務，QoS逐漸成為Web服務的主要評價指標和服務選擇的重要依據(jù)［1－3］。在 QoS感知的服務選擇中，用戶可能對大部分候選服務都未使用過，無法掌握其QoS，而對其進行逐一調(diào)用以獲取其QoS又將耗費大量資源，因而需要采取某種策略對未使用過服務的QoS進行預測。若服務組合流程選擇了QoS較低但被高估的Web服務進行綁定，可能導致組合流程不滿足用戶需求甚至運行失敗;而QoS較高但被低估的Web服務則可能在服務選擇中被忽略，從而導致服務流程的整體質(zhì)量下降。因此，在服務選擇前對候選服務的QoS進行準確的預測是獲取高質(zhì)量服務組合流程的基礎。

QoS屬性可分為獨立于用戶和依賴于用戶兩類。獨立于用戶的QoS屬性(如費用)值不依賴于特定的用戶，不同的用戶獲取的QoS值相同;而依賴于用戶的QoS屬性(如響應時間、可靠性和吞吐量等)則可能因不同用戶的網(wǎng)絡狀況、異構(gòu)環(huán)境和地理位置等差異導致值變化較大［4］。傳統(tǒng)的統(tǒng)計平均預測方法為不同用戶提供相同的預測值，該預測值通過對服務的歷史QoS數(shù)據(jù)進行算術平均得到［5－6］，未考慮不同用戶的QoS感受差異性，導致預測結(jié)果準確率較低。SHAO等借鑒電子商務領域的協(xié)同過濾推薦技術，提出了一種基于協(xié)同過濾的QoS預測方法［7］，其基本假設是對某些服務擁有相似QoS感受的用戶，對其他服務的感受也會比較接近。該方法采用相似用戶的QoS歷史信息對用戶未使用過服務的QoS進行預測，在一定程度上考慮了用戶的個性化差異，預測結(jié)果較統(tǒng)計平均法更為準確。ZHENG等提出了一種混合協(xié)同過濾方法WSRec［8］，其在對QoS進行預測時綜合了基于用戶和基于服務的協(xié)同過濾結(jié)果，使得QoS信息矩陣中的數(shù)據(jù)得到更充分的利用。實際上，大部分用戶只使用過少量服務，因此QoS信息矩陣是極度稀疏的。

上述方法都未考慮到當QoS信息矩陣極度稀疏時，采用傳統(tǒng)的協(xié)同過濾方法得到的預測結(jié)果可能并不準確的問題。針對該問題，筆者提出一種混合協(xié)同過濾方法，該方法可有效提高QoS預測準確度。

1 問題描述

QoS是描述服務質(zhì)量的一系列非功能屬性的集合，主要包括服務的價格、響應時間、吞吐量、可靠性和可用性等信息。由于傳統(tǒng)的UDDI架構(gòu)不支持服務的QoS屬性信息的注冊和存儲，ZHOU等提出了一種可擴展的UDDI系統(tǒng)UX［9］，以提供對服務QoS信息的注冊功能。為保證不失一般性，筆者以響應時間和吞吐量為例，討論QoS的預測問題。

表1給出了存儲在擴展的UDDI系統(tǒng)中的QoS數(shù)據(jù)，其中S表示服務，U表示用戶，表格中的數(shù)據(jù)項表示用戶調(diào)用服務感受到的響應時間和吞吐量QoS值。當數(shù)據(jù)項為φ時，以表1中U5對應S2的數(shù)據(jù)項為例，則表示用戶U5未使用過服務S2，因此用戶U5在調(diào)用服務 S2前需對其QoS進行預測。

表1 QoS信息存儲范例

目前大多采用統(tǒng)計平均法，即在預測U5調(diào)用S2的QoS值時，采用S2的歷史使用信息進行統(tǒng)計平均得到，即響應時間為(0.23+0.37+0.30)/3=0.30 s，吞吐量為(17.54+10.93+17.70)/3=15.39 kb/s。統(tǒng)計平均法計算簡單，但是由于沒有考慮不同用戶處于不同的網(wǎng)絡狀況、異構(gòu)環(huán)境和地理位置下，對相同服務感受到的QoS差異性，其預測精度不高。

2 混合協(xié)同過濾預測方法

2.1 定義

便于問題分析，作如下定義:

定義 1 用戶集 U={U1，U2，…，Um}，Ui(1≤i≤m)表示用戶集中的第i個用戶。

定義2 服務集 S={S1，S2，…，Sn}，Sj(1≤j≤n)表示服務集中的第j個服務。

定義3 用戶－服務QoS矩陣為:

其中:Rij= ＜ rtij，tpij＞ (1≤i≤m，1≤j≤n);rtij為用戶Ui感受到服務Sj的響應時間;tpij為用戶Ui感受到服務Sj的吞吐量。則QoS預測的目標為利用R中已有數(shù)據(jù)對其缺失項進行預測。

2.2 數(shù)據(jù)預處理

使用協(xié)同過濾法對用戶－服務矩陣中的缺失值進行預測前，需對矩陣中的數(shù)據(jù)項進行預處理。具體方法是將用戶－服務矩陣按照QoS屬性分離為若干個矩陣，然后對分離后的QoS矩陣的缺失項逐一進行預測。將用戶－服務矩陣R分離為響應時間矩陣RT和吞吐量矩陣TP，如式(1)所示。

2.3 相似度挖掘

常用的相似度度量方法有皮爾遜相關系數(shù)法、余弦相似法、修正余弦相似法和歐氏距離法等。其中皮爾遜相關系數(shù)法因具有易于實現(xiàn)和精度高等特點，被廣泛應用于各類推薦系統(tǒng)。采用皮爾遜相關系數(shù)法計算服務a和服務b的相似度由式(2)表示。

式中:Sim(a，b)為服務a和服務 b 的相似度，取值范圍為［－1，1］，其值越大說明越相似;Uab=Ua∩Ub為使用過服務a和服務b的用戶集合;Rua為用戶u感受到服務a的QoS值;為用戶集U中用戶感受到服務a的QoS平均值。

由式(2)可知，皮爾遜相關系數(shù)法使用服務之間的共同用戶集進行相似度計算，其未考慮兩種極端情況:

(1)當兩個服務不存在共同用戶時，無法由式(2)得到相似度的有效值。

(2)式(2)中的分母為零的情況。例如令服務a和服務b的共同用戶為用戶u和用戶v，假如此時用戶u調(diào)用a和b的QoS相等，并且用戶v調(diào)用a和b的QoS也相等，則式(2)的分母將取零，此時得到的相似度則為無窮大。

針對這兩種極端情況，對式(2)進行改進，如式(3)所示。

由于QoS矩陣的稀疏性，服務的共同用戶通常較少，假如剛好少量的共同用戶對兩個服務的QoS體驗較為接近，而另外一些用戶對這兩個服務的QoS體驗差異較大，此時采用傳統(tǒng)的皮爾遜相關系數(shù)法計算出的兩個服務的相似度仍較大，這就造成了服務的相似度過量估計的問題。因此，筆者引入相似度信任因子以避免相似度的過量估計。

式中:|Ua∩Ub|為服務a和服務b的共同用戶數(shù);λ為預先設定的閾值，與系統(tǒng)中的用戶總數(shù)有關。經(jīng)上述相似度修正后，得到的服務相似度更為可靠。經(jīng)過上述相似度計算后，將與服務a相似度最高的k個服務組成一個集合T(a)，稱為服務a的top－k近鄰服務集。

2.4 缺失值預測

傳統(tǒng)的基于服務的協(xié)同過濾法使用top－k近鄰集中的數(shù)據(jù)對缺失值進行預測，如式(5)所示。

式中:Rua為用戶u對服務a的QoS預測值;為目標服務a對于用戶集U中用戶的QoS平均值;為近鄰服務b對于用戶集U中用戶的QoS平均值。

隨著網(wǎng)絡上Web服務數(shù)的激增，大部分用戶只使用過少量服務，導致QoS數(shù)據(jù)極度稀疏。因此服務的top－k近鄰集中的QoS值大部分為空，即式(5)中的Rub以高概率等于零，此時仍然采用式(5)得到的預測值并不準確。因此，筆者對傳統(tǒng)的基于服務的協(xié)同過濾公式進行改進，以提高數(shù)據(jù)稀疏條件下的預測準確度，如式(6)所示。

此外，經(jīng)式(6)計算得到的預測值，存在部分值為負值的現(xiàn)象，而QoS屬性(如響應時間、吞吐量和可靠性等)值通常為非負。筆者采用服務的QoS統(tǒng)計平均值代替該部分負值。

3 實驗結(jié)果及討論

由于QoS是用戶在服務選擇過程中的重要指標，因此QoS預測的準確性直接影響了用戶服務選擇方案的質(zhì)量，進而影響最終服務組合流程的可靠性。因此采用網(wǎng)絡上真實的Web服務的QoS數(shù)據(jù)集WSDREAM對筆者所述方法的QoS預測準確性進行驗證，并與現(xiàn)有文獻的其他3種算法進行對比。WSDREAM使用分布在30多個不同國家的339個用戶對分布在73個國家的5 825個Web服務進行調(diào)用，通過對執(zhí)行過程進行監(jiān)控得到服務的QoS。為便于分析，對數(shù)據(jù)集進行處理，分別獲取了150×100的響應時間和吞吐量用戶－服務QoS矩陣。

筆者采用歸一化平均絕對誤差(NMAE)對算法的QoS預測準確度進行度量，式(7)給出了NMAE的定義。

將數(shù)據(jù)集中的150個用戶的QoS數(shù)據(jù)等分為10份，將其中9份輪流作為訓練集，另外1份作為測試集，對預測結(jié)果進行十折交叉驗證。由于現(xiàn)實中的Web服務QoS信息較為稀疏，因此在實驗中，采用隨機方式將訓練集中的若干數(shù)據(jù)項移除，以提高數(shù)據(jù)集的稀疏度。對于測試集，每次驗證時隨機選擇一個目標用戶，只保留其部分數(shù)據(jù)項，然后對移除的缺失項進行預測，并采用移除項的原有值對預測結(jié)果的準確度進行評估。為更好地對算法的準確性進行估計，取10次十折交叉驗證結(jié)果的均值。

3.1 不同矩陣密度下的算法準確度對比

圖1和圖2對比研究了筆者所提方法和其他3種算法在不同矩陣密度下的響應時間和吞吐量的預測結(jié)果。矩陣密度反映了預測系統(tǒng)所掌握的QoS歷史信息的豐富程度。在該實驗中，訓練集的矩陣密度以0.01為步長從0.09遞增到0.18，以研究在不同矩陣密度下的算法預測準確度。UPCC為基于用戶的協(xié)同過濾法，IPCC為基于服務的協(xié)同過濾法，WSRec為文獻［9］提出的混合協(xié)同過濾算法，EFMCF為筆者所提出的混合協(xié)同過濾算法。在該實驗中，目標用戶保留的數(shù)據(jù)項為20個，UPCC、IPCC和EFMCF的參數(shù)top－k統(tǒng)一取10，WSRec的參數(shù)top－k和λ分別取10和0.20，EFMCF 的參數(shù) λ 取20。

圖1 不同矩陣密度下的響應時間預測結(jié)果對比

圖2 不同矩陣密度下的吞吐量預測結(jié)果對比

由圖1和圖2可知，在不同的矩陣密度下，EFMCF的NMAE值均低于其他3種方法，表明EFMCF對響應時間和吞吐量的預測準確度更高。而IPCC的QoS預測準確度高于UPCC，因此可以認為服務之間的相似性比用戶之間的相似性更為穩(wěn)定。WSRec由于混合利用了QoS矩陣中的服務近鄰信息和用戶近鄰信息，準確度得到了一定提升，但其未考慮近鄰集中的大量零值問題，導致準確度提升有限。EFMCF采用基于用戶的協(xié)同過濾算法對服務近鄰集中的零值進行填充，進而采用基于服務的協(xié)同過濾算法得到預測值，使QoS預測的準確度得到較大提升。

3.2 不同保留項數(shù)下的算法準確度對比

圖3和圖4研究了目標用戶取不同的保留項數(shù)時算法的響應時間和吞吐量預測結(jié)果。保留項數(shù)反映了目標用戶提交給QoS預測系統(tǒng)服務的QoS信息的豐富程度。在該實驗中，訓練集矩陣密度設為0.20，保留項數(shù)以5為步長從10遞增到55。

圖3 不同保留項數(shù)下的響應時間預測結(jié)果對比

圖4 不同保留項數(shù)下的吞吐量預測結(jié)果對比

由圖3和圖4可知，目標用戶取不同的保留項數(shù)時，EFMCF對響應時間和吞吐量兩種QoS的預測準確度均高于其他3種方法。說明用戶只需向預測系統(tǒng)提供其曾經(jīng)使用過服務的QoS信息，就可獲得其未使用過服務的較準確QoS預測值。通過進一步的實驗發(fā)現(xiàn)，用戶提交的QoS信息越豐富，其獲得的預測準確度越高，在實際應用中，該機制可鼓勵用戶向預測系統(tǒng)提供其使用過服務的QoS信息。

4 結(jié)論

針對目前QoS預測方法的不足，提出了一種混合協(xié)同過濾預測方法。采用網(wǎng)絡上真實的Web服務QoS數(shù)據(jù)集進行實驗驗證，結(jié)果表明，該方法可顯著提高對Web服務QoS的預測準確度。雖然該方法只考慮響應時間和吞吐量兩個QoS屬性，但可同時用于其他QoS屬性的預測。

Web服務的QoS數(shù)據(jù)主要通過服務供應商的發(fā)布、用戶使用反饋和對服務執(zhí)行過程實時監(jiān)控3種方式收集。筆者使用的QoS數(shù)據(jù)來源于第3種渠道，因此其數(shù)據(jù)是客觀可信的。通過另外兩種渠道收集的QoS信息，可能存在QoS不可信的情況，如供應商的夸大發(fā)布和用戶的虛假反饋等。假如采用虛假的QoS信息進行服務選擇，將嚴重影響服務選擇結(jié)果的可靠性。

［1］SU K，MA L L，GUO X M，et al.An efficient discrete invasive weed optimization algorithm for Web services selection［J］.Journal of Software，2014，9(3):709－715.

［2］YU T，ZHANGY，LINK J.Efficientalgorithms forWeb services selection with end－to－end QoS constraints［J］.ACM Trans on theWeb，2007，1(1):1 －26.

［3］蘇凱，馬良荔，郭曉明，等.一種QoS感知的服務全局優(yōu)化選擇算法［J］.華中科技大學學報:自然科學版，2014，42(4):72 －76.

［4］ZHENG Z B，ZHANG Y L，LYU MR.Distributed QoS evaluation for real－ world Web services［C］∥IEEE International Conference on Web Services.［S.l.］:［s.n.］，2010:83 －90.

［5］XIAO R L.Constructing a novel QoSaggregatedmodel based on KBPP［J］.Communications in Computer and Information Science，2010，107(3):117 －126.

［6］ZENG L，BENATALLAH B.QoS－awaremiddleware forWeb services composition［J］.IEEE Trans on Software Engineering，2004，30(5):321 －322.

［7］SHAO L，ZHANG J，WEIY，et al.Personalize QoS prediction for Web service via collaborative filtering［C］∥IEEE International Conference on Web Services.［S.l.］:［s.n.］，2007:439 －446.

［8］ZHENG Z B，MA H，LYU MR，et al.WSRec:a collaborative filtering based Web service recommender system［C］∥IEEE International Conference on Web Services.［S.l.］:［s.n.］，2009:437 －444.

［9］ZHOUC，CHIA L T，SILVERAJAN B，etal.UX:an architecture providing QoS－aware and federated support for UDDI［C］∥Proc.of the Int’1 Conf on Web Services.Las Vegas:IEEE Computer Society，2003:171－176.