段秋實(shí) 胡志剛

(中南大學(xué)軟件學(xué)院 湖南 長(zhǎng)沙 410075)

基于云模型的Web服務(wù)QoS預(yù)測(cè)

段秋實(shí) 胡志剛

(中南大學(xué)軟件學(xué)院 湖南 長(zhǎng)沙 410075)

隨著近年來(lái)Web服務(wù)數(shù)量的快速增長(zhǎng)，用戶-服務(wù)QoS(Quality of Service)記錄矩陣變得日益稀疏。為了解決傳統(tǒng)協(xié)同過(guò)濾算法在稀疏數(shù)據(jù)集上預(yù)測(cè)精確性不高的問題，利用歐幾里得距離對(duì)數(shù)值敏感的特點(diǎn)，將云模型特征向量的歐幾里得距離轉(zhuǎn)換成云模型的相似度。對(duì)基于云模型的協(xié)同過(guò)濾算法改進(jìn)，并將改進(jìn)算法用于Web服務(wù)QoS的動(dòng)態(tài)預(yù)測(cè)。考慮用戶調(diào)用同一服務(wù)提供商的不同服務(wù)有相似體驗(yàn)，再結(jié)合云模型的相似度對(duì)QoS記錄矩陣進(jìn)行填充，在預(yù)測(cè)用戶調(diào)用某服務(wù)的QoS時(shí)使用填充后的QoS記錄矩陣進(jìn)行計(jì)算，從而有利于解決稀疏矩陣下預(yù)測(cè)準(zhǔn)確度難以提高的問題。實(shí)驗(yàn)表明，使用該算法的預(yù)測(cè)結(jié)果相較于傳統(tǒng)的協(xié)同過(guò)濾算法有更低的平均絕對(duì)誤差(MAE)，能獲得更高的推薦質(zhì)量。

Web服務(wù) QoS預(yù)測(cè) 協(xié)同過(guò)濾 云模型 相似度計(jì)算

0 引 言

因特網(wǎng)上Web服務(wù)數(shù)量的快速增加，導(dǎo)致眾多具有相似功能的Web服務(wù)的出現(xiàn)，傳統(tǒng)的Web服務(wù)發(fā)現(xiàn)只能為用戶發(fā)現(xiàn)滿足需求的服務(wù)，而不能在相似功能的服務(wù)中為用戶提供性能最優(yōu)的服務(wù)。為在相似的服務(wù)中找到最優(yōu)的服務(wù)，Web服務(wù)的服務(wù)質(zhì)量(QoS)屬性成為研究者關(guān)注的重點(diǎn)?；趨f(xié)同過(guò)濾的Web服務(wù)推薦技術(shù)的普遍思想是通過(guò)用戶的QoS記錄找到相似用戶并根據(jù)相似用戶的QoS記錄預(yù)測(cè)用戶的QoS。

Shao等提出一種基于協(xié)同過(guò)濾法的QoS預(yù)測(cè)方法，該預(yù)測(cè)方法使用皮爾遜相似度PCC(Pearson Correlation coefficient)計(jì)算任意兩個(gè)用戶之間的相似度，使用具有較高相似度用戶的QoS記錄對(duì)未知的QoS記錄進(jìn)行預(yù)測(cè)[1]?；赑CC的協(xié)同過(guò)濾算法包括兩種：使用PCC的用戶方法UPCC(user-based approach using PCC)和使用PCC的項(xiàng)目方法IPCC(item-based approach using PCC)。若兩個(gè)用戶沒有同一Web服務(wù)的調(diào)用記錄，UPCC會(huì)因?yàn)闊o(wú)法計(jì)算用戶之間的相似度導(dǎo)致預(yù)測(cè)失敗，Zheng等對(duì)Shao的QoS預(yù)測(cè)方法進(jìn)行了改進(jìn)。首先根據(jù)共同的QoS記錄數(shù)量對(duì)PCC方法得出的相似度添加權(quán)重，再分別通過(guò)UPCC和IPCC預(yù)測(cè)用戶user調(diào)用項(xiàng)目service的QoS值，最后將得到的預(yù)測(cè)結(jié)果進(jìn)行綜合并得出最終的預(yù)測(cè)結(jié)果[2]。此外Zheng等在文獻(xiàn)[3]中設(shè)計(jì)了一種通過(guò)矩陣分解預(yù)測(cè)QoS的方法。Yin等在文獻(xiàn)[4]提出，使用一種基于位置的協(xié)同正則化框架來(lái)實(shí)現(xiàn)個(gè)性化的QoS預(yù)測(cè)，該框架利用用戶的地理位置信息和歷史QoS信息識(shí)別“鄰居”，通過(guò)矩陣分解和融合獲得預(yù)測(cè)結(jié)果。但是在面對(duì)大量用戶QoS信息時(shí)難以獲得較好的矩陣分解效率。

現(xiàn)有Web服務(wù)的QoS預(yù)測(cè)過(guò)程中大多使用PCC方法來(lái)計(jì)算相似性，從而進(jìn)一步進(jìn)行求解得出最終的預(yù)測(cè)值。由于皮爾遜系數(shù)主要表示各個(gè)數(shù)據(jù)的線性相關(guān)關(guān)系，且不適用于稀疏數(shù)據(jù)集。在QoS預(yù)測(cè)的環(huán)境中用戶共同調(diào)用的服務(wù)數(shù)量較少，傳統(tǒng)的相似度計(jì)算方法會(huì)高估用戶的相似性，影響預(yù)測(cè)結(jié)果。將云模型的概念引入QoS預(yù)測(cè)中，使用云模型的特征向量描述用戶的QoS記錄。通過(guò)特征向量計(jì)算用戶的相似度，能夠有效解決傳統(tǒng)協(xié)同過(guò)濾算法中共同調(diào)用服務(wù)數(shù)量不足的問題。 使用基于云模型的協(xié)同過(guò)濾算法，有望獲得較好的推薦效果并改善矩陣稀疏的問題[5]，所以將云模型使用在Web服務(wù)QoS預(yù)測(cè)具有一定研究?jī)r(jià)值。

針對(duì)傳統(tǒng)的云模型協(xié)同過(guò)濾算法，余志虎等提出一種基于云模型的矩陣填充方法。首先利用云模型的相似度對(duì)評(píng)分矩陣進(jìn)行填充，再使用填充矩陣進(jìn)行最終的預(yù)測(cè)[6]。該方法沒有考慮各個(gè)屬性特征對(duì)預(yù)測(cè)結(jié)果影響。劉發(fā)升等綜合考慮用戶屬性相似度和云模型相似度，優(yōu)化協(xié)同過(guò)濾中相似度計(jì)算方法[7]。以上兩種方法均使用余弦相似度計(jì)算云模型相似度，但是使用余弦相似度計(jì)算存在缺陷。本文利用歐幾里得距離對(duì)數(shù)值大小敏感的特點(diǎn)，將云模型特征向量的歐幾里得距離轉(zhuǎn)換成云模型的相似度，提高預(yù)測(cè)的準(zhǔn)確性。再根據(jù)相同服務(wù)提供商的不同服務(wù)有相似服務(wù)體驗(yàn)的特點(diǎn)，利用服務(wù)的URL的域名選取相同的服務(wù)提供商，結(jié)合云模型的相似度對(duì)用戶-服務(wù)QoS矩陣進(jìn)行填充，進(jìn)一步解決矩陣稀疏問題提高預(yù)測(cè)準(zhǔn)確度。

1 云模型與協(xié)同過(guò)濾

1.1 云模型概念

云模型是李德毅院士為了解決傳統(tǒng)模糊理論不徹底問題提出的一種定性概念與定量模型相互轉(zhuǎn)化的方法[8]。目前云模型已經(jīng)成功地應(yīng)用到自然語(yǔ)言處理、數(shù)據(jù)挖掘、決策分析、智能控制、圖像處理等眾多領(lǐng)域[9]。一個(gè)定性概念通過(guò)云模型可以轉(zhuǎn)化為向量v=(Ex,En,He)，該向量稱為云的特征向量，通過(guò)特征向量的數(shù)字特征描述這個(gè)定性概念。其中Ex、En、He分別是云模型的期望、熵和超熵。期望是將定性概念量化后的最典型的數(shù)值也就是最能代表定性概念的點(diǎn)。熵代表定性概念的可度量粒度，熵越大時(shí)概念越宏觀，也是定性概念不確定性的度量，由概念的隨機(jī)性和模糊性共同決定。超熵是熵的不確定性的度量，即熵的熵，由熵的隨機(jī)性和模糊性共同決定[10-11]。

在已知N個(gè)樣本的取值xi的情況下，通過(guò)逆向云發(fā)生器可以計(jì)算該組樣本的云模型特征向量v：

1.2 基于云模型的協(xié)同過(guò)濾算法

張衛(wèi)光等利用云模型能夠?qū)⒍ㄐ愿拍钆c定量模型相互轉(zhuǎn)化的特性，提出一種基于云模型的相似度計(jì)算方法LICM(likeness comparing method based on cloud model)[7,11]。并將LICM算法使用在協(xié)同過(guò)濾中，提出了一種基于云模型的協(xié)同過(guò)濾算法。在該算法中期望Ex是用戶對(duì)所有項(xiàng)目的平均評(píng)分，反映了用戶的評(píng)分偏好；熵En表示用戶評(píng)分的穩(wěn)定程度；超熵He為熵的穩(wěn)定度。該基于云模型的協(xié)同過(guò)濾算法的推薦步驟如下：

1) 通過(guò)逆向云發(fā)生器將各個(gè)用戶的評(píng)分向量轉(zhuǎn)化為對(duì)應(yīng)的評(píng)分特征向量vi=(Exi,Eni,Hei)。

2) 根據(jù)式(1)計(jì)算兩用戶的相似性：

(1)

3) 根據(jù)用戶的相似度生成用戶相似度矩陣，在相似度矩陣中找到與待測(cè)用戶的相似度最高的k個(gè)用戶作為相似用戶集合simuser。

4) 用戶u對(duì)項(xiàng)目i的評(píng)分預(yù)測(cè)值通過(guò)式(2)計(jì)算：

(2)

2 基于云模型的QoS預(yù)測(cè)過(guò)程

2.1 基于歐幾里得距離的云模型相似度

使用基于云模型的協(xié)同過(guò)濾算法對(duì)用戶QoS數(shù)據(jù)進(jìn)行預(yù)測(cè)。首先根據(jù)用戶Web服務(wù)調(diào)用記錄，把用戶使用過(guò)的服務(wù)QoS記錄作為云滴，通過(guò)逆向云算法得到各個(gè)用戶QoS記錄的云模型特征向量c=(Ex,En,He)。該特征向量中數(shù)值分別表述了用戶的平均QoS數(shù)值、QoS數(shù)值的集中程度以及其穩(wěn)定程度。再根據(jù)特征向量相似度計(jì)算結(jié)果選取相似用戶，得到推薦結(jié)果。

LICM算法通過(guò)計(jì)算用戶云模型特征向量的余弦相似度得出用戶相似度矩陣。使用向量余弦夾角計(jì)算的相似度結(jié)果，主要考慮的是兩個(gè)向量維度上相對(duì)的差異。例如，兩個(gè)用戶i、j對(duì)A、B、C三個(gè)項(xiàng)目的評(píng)分分別是(2,2,1)和(4,4,2)，那么評(píng)分向量分別為ci(2,2,1)和cj(4,4,2)，兩個(gè)向量的余弦值為1，此時(shí)可以認(rèn)為這兩個(gè)用戶有相似的評(píng)分趨勢(shì)。在預(yù)測(cè)Web服務(wù)QoS的情景中，根據(jù)用戶的QoS記錄找到相似用戶，此時(shí)用余弦夾角計(jì)算相似度并不恰當(dāng)。以QoS屬性中響應(yīng)時(shí)間RT(Response Time)為例，其特征向量中Ex、En和He分別表示的是用戶所調(diào)用服務(wù)的響應(yīng)時(shí)間平均值、響應(yīng)時(shí)間的集中程度和穩(wěn)定程度，其中En和He的數(shù)值越小說(shuō)明該用戶調(diào)用Web服務(wù)時(shí)響應(yīng)時(shí)間的集中程度和穩(wěn)定程度越高。云模型的特征向量可以用來(lái)描述云模型云滴分布的圖像，Ex在圖像中表示的是云滴圖像的形心位置，En表示云滴分布的寬度，He表示云滴的厚度。使用LICM算法比較QoS特征向量為ci(1,0.2,0.01)的用戶i與特征向量分別為cj(2,0.4,0.02)、ck(1,0.3,0.01)的用戶j和k的相似度時(shí)，用戶i與用戶j的相似度要高于用戶k。由圖1卻發(fā)現(xiàn)用戶i的云滴圖與用戶k的更相似，用戶i、j的圖像不僅形心位置有較大差異，而且云模型的寬度和厚度均有差異。

圖1 用戶i、j、k的云滴圖像

特征向量數(shù)值上的差異越小，對(duì)應(yīng)的云滴圖像越相似。歐幾里得距離表示的是兩個(gè)點(diǎn)在空間中的距離。歐幾里得距離越小的點(diǎn)，其對(duì)應(yīng)坐標(biāo)值的差異也越小，故使用歐幾里得距離來(lái)計(jì)算云模型相似度時(shí)更加側(cè)重特征向量數(shù)值大小方面的差異。張龍昌等在文獻(xiàn)[12]中提出了一種利用歐幾里得距離比較云模型相似度的方法。已知兩個(gè)云模型的特征向量分別為v1=(Ex1,En1,He1)和v2=(Ex2,En2,He2)，云模型特征向量的距離：

圖1中用戶i與用戶j的距離d(i,j)=1.002，大于用戶k的距離d(i,k)=0.1，距離更小的k用戶的云模型更相似。經(jīng)過(guò)實(shí)驗(yàn)證明，歐幾里得距離越小的云模型之間的相似度也會(huì)越高。因此在使用云模型進(jìn)行協(xié)同預(yù)測(cè)的情況下，使用歐幾里得距離的方式來(lái)計(jì)算相似度會(huì)更加合理。但該距離度量公式只能通過(guò)數(shù)值大小判斷哪些云模型更相似，而無(wú)法像余弦算法或是PCC算法一樣計(jì)算出兩者之間的相似程度，因此也無(wú)法直接應(yīng)用在協(xié)同過(guò)濾算法中。

為了將歐幾里得距離應(yīng)用在相似度計(jì)算的過(guò)程中，提高基于云模型的協(xié)同過(guò)濾算法的準(zhǔn)確性，本文提出一種基于歐幾里得距離的云模型相似度計(jì)算方法(EuLICM)。假設(shè)兩個(gè)用戶i和j的特征向量分別為vi=(Exi,Eni,Hei)和vj=(Exj,Enj,Hej)，那么用戶i和j的歐幾里得相似度eusim(i,j)為：

(3)

通過(guò)對(duì)云模型的歐幾里得距離做歸一化處理，將不同的距離對(duì)應(yīng)到區(qū)間[0，1)上。當(dāng)兩個(gè)特征向量完全一致時(shí)，歐幾里得距離為0相似度為1，說(shuō)明這兩個(gè)用戶完全相似；當(dāng)兩個(gè)特征向量差距明顯時(shí)，歐幾里得距離也會(huì)變大，隨著距離的增加，式(3)的值會(huì)趨近0，說(shuō)明兩個(gè)用戶的相似度越低。

用戶的QoS記錄特征向量根據(jù)用戶已調(diào)用的服務(wù)數(shù)據(jù)計(jì)算，用戶之間調(diào)用的項(xiàng)目不會(huì)完全一致。為了消除在計(jì)算相似度的過(guò)程中，項(xiàng)目不一致帶來(lái)的影響，考慮引入一個(gè)影響因子η，將兩個(gè)用戶共同調(diào)用的服務(wù)數(shù)量考慮在內(nèi)。用戶i和用戶j的相似度影響因子ηi,j與兩個(gè)用戶共同調(diào)用的服務(wù)數(shù)量有關(guān)，影響因子計(jì)算方式如下：

(4)

其中:Ii∩Ij代表的是用戶i和用戶j共同調(diào)用過(guò)的服務(wù)數(shù)量，Ii和Ij分別代表的是用戶調(diào)用的服務(wù)數(shù)量。

綜合歐幾里得距離相似度和影響因子，最終用戶i和j的相似度sim(i,j)表示為：

sim(i,j)=ηi,j×eusim(i,j)

(5)

根據(jù)歐幾里得距離計(jì)算云模型相似度的步驟如算法1所示。

算法1基于歐幾里得距離的云模型相似度計(jì)算

輸入：用戶i的QoS記錄向量ci、用戶j的QoS記錄向量cj

輸出：用戶i與用戶j的相似度sim(i,j)

1) 根據(jù)ci計(jì)算i的特征向量vi=(Exi,Eni,Hei)；

2) 根據(jù)cj計(jì)算j的特征向量vj=(Exj,Enj,Hej)；

3) 利用式(3)計(jì)算用戶i和用戶j的歐幾里得相似度eusim(i,j)；

4) 分別統(tǒng)計(jì)用戶i和j調(diào)用的服務(wù)數(shù)量Ii和Ij；

5) 統(tǒng)計(jì)用戶i和j的共同調(diào)用數(shù)量Ii∩Ij；

6) 利用式(4)計(jì)算影響因子ηi,j；

7) 結(jié)合eusim(i,j)和ηi,j，通過(guò)式(5)計(jì)算用戶i和j的相似度sim(i,j)。

2.2 結(jié)合云模型和服務(wù)特征的QoS預(yù)測(cè)

假設(shè)存在m個(gè)Web服務(wù)，n個(gè)用戶，用戶的QoS記錄可以用一個(gè)n×m的矩陣來(lái)表示，其中一行和一列分別代表用戶或服務(wù)的QoS記錄，用戶-服務(wù)QoS記錄矩陣如圖2所示。

圖2 用戶-服務(wù)QoS記錄矩陣

隨著因特網(wǎng)中用戶和Web服務(wù)數(shù)量的膨脹，用戶-服務(wù)矩陣將會(huì)變得稀疏。在此類情況下使用PCC等方法計(jì)算相似度不僅有可能會(huì)找不到共同評(píng)分的項(xiàng)目，也會(huì)因?yàn)楣餐u(píng)分的用戶過(guò)少，在計(jì)算時(shí)只考慮有共同評(píng)分的項(xiàng)目，導(dǎo)致過(guò)高估計(jì)用戶的相似度?；谠颇Ｐ偷膮f(xié)同過(guò)濾算法將用戶的評(píng)分抽象成特征向量，通過(guò)特征向量的相似度尋找鄰居，相對(duì)于PCC等算法在計(jì)算相似度不必嚴(yán)格用戶的所有評(píng)分屬性，在一定程度上解決了矩陣稀疏的問題。

稀疏矩陣導(dǎo)致的誤差不僅僅出現(xiàn)在相似度計(jì)算階段，在預(yù)測(cè)階段也會(huì)因?yàn)樵u(píng)分的缺失導(dǎo)致預(yù)測(cè)的結(jié)果偏小。假設(shè)需要預(yù)測(cè)用戶n調(diào)用k服務(wù)的QoS記錄，已知n的相似用戶集合為(1，2，3，4，…)。根據(jù)式(2)很容易發(fā)現(xiàn)預(yù)測(cè)結(jié)果會(huì)偏小，甚至在相似用戶集合中有大量未調(diào)用該服務(wù)的情況下，QoS的預(yù)測(cè)值會(huì)變成負(fù)值導(dǎo)致預(yù)測(cè)結(jié)果偏差極大。

在真實(shí)的環(huán)境中，一個(gè)Web服務(wù)提供商往往會(huì)提供多個(gè)Web服務(wù)，而同一服務(wù)提供商的服務(wù)具有相同的網(wǎng)絡(luò)環(huán)境和處理能力，所以用戶在調(diào)用同一個(gè)提供商的不同服務(wù)時(shí)會(huì)有相似的QoS。同一服務(wù)提供商的所有服務(wù)有相同的根域名，因此通過(guò)調(diào)用服務(wù)的URL可以判斷服務(wù)是否屬于同一個(gè)提供商所提供。根據(jù)以上性質(zhì)可以作如下假設(shè)，若用戶有缺失服務(wù)的提供商的其他服務(wù)記錄，則該用戶調(diào)用此缺失服務(wù)的QoS近似于該提供商的其他服務(wù)的QoS平均值。基于以上假設(shè)，為了解決矩陣稀疏的問題，本文提出一種結(jié)合云模型和服務(wù)信息的用戶服務(wù)矩陣數(shù)據(jù)填充方法，并利用該方法對(duì)QoS進(jìn)行預(yù)測(cè)。該填充方法分為兩步填充，第一步填充是根據(jù)缺失服務(wù)的服務(wù)信息對(duì)矩陣進(jìn)行填充，若用戶有缺失服務(wù)的提供商的其他服務(wù)，則該記錄的填充值為用戶調(diào)用此提供商的QoS平均值，否則填充值為其余用戶調(diào)用該缺失服務(wù)的QoS平均值，填充方法如式(6)；第二步再利用云模型尋找相似用戶，結(jié)合第一步的填充矩陣修改填充值。

(6)

算法2介紹如何對(duì)訓(xùn)練集中QoS記錄矩陣的缺失值進(jìn)行填充，訓(xùn)練集是一個(gè)有大量QoS記錄缺失的n×m矩陣，通過(guò)算法2可以將訓(xùn)練集中的缺失QoS記錄補(bǔ)全，提供給測(cè)試集使用。

算法2結(jié)合云模型和服務(wù)信息的QoS信息填充

輸入：n×m的QoS記錄矩陣Q、最近鄰居數(shù)k

輸出：n×m的QoS記錄填充矩陣Q′

1) for(i=1;i≤n-1;i++)

for(j=i+1;j≤n;j++)

使用算法1計(jì)算用戶i，j的相似度sim(i,j)

S[i,j]=sim(i,j)

//S為相似度矩陣，S[i,j]為用戶i，j的相似度

2) for(u=1;u≤n;u++)

//遍歷用戶

for(i=1;i≤m;i++)

//遍歷服務(wù)

if (Q[u,i]!=0)

T[u,i]=Q[u,i]；

else

使用式(6)計(jì)算出Pu,i；

T[u,i]=Pu,i；

//T為預(yù)填充矩陣

3) for(u=1;u≤n;u++)

//遍歷用戶

找到與用戶u相似度最高的k個(gè)用戶；

計(jì)算用戶u的QoS記錄均值；

for(i=1;i≤m;i++)

//遍歷服務(wù)

if (Q[u,i]==0)

根據(jù)式(2)將缺失項(xiàng)重新補(bǔ)齊得到Q′，其中相似用戶調(diào)用i服務(wù)的QoS記錄和相似用戶QoS

通過(guò)上述算法對(duì)訓(xùn)練集中QoS矩陣填充后得到的QoS記錄矩陣Q′。在預(yù)測(cè)測(cè)試集中用戶u的QoS記錄時(shí)，用戶u相似用戶的QoS記錄從Q′中獲取。預(yù)測(cè)用戶u的QoS記錄的步驟如算法3所述。

算法3基于云模型的QoS預(yù)測(cè)

輸入：n×m的已知QoS記錄矩陣Q、n×m的QoS填充矩陣Q′、待預(yù)測(cè)用戶u的QoS記錄向量cu，最近鄰居數(shù)k

輸出：用戶u的QoS預(yù)測(cè)結(jié)果

1) 根據(jù)cu計(jì)算u的特征向量vu=(Exu,Enu,Heu)；

2) 利用算法2對(duì)QoS記錄矩陣填充，得到填充矩陣Q′；

3) for(j=1;j≤n;j++)

使用算法1計(jì)算用戶u與矩陣Q中用戶j的相似度；

4) 在訓(xùn)練集中選取和用戶u相似度最高的k個(gè)用戶作為相似用戶集合；

5) 計(jì)算用戶u的QoS記錄均值；

6) for(i=1;i≤m;i++)

//遍歷服務(wù)

if (cu[i]==0)

根據(jù)式(2)計(jì)算用戶u缺失的服務(wù)i的QoS記錄，其中相似用戶調(diào)用i服務(wù)的QoS記錄和相似用戶QoS均值由從矩陣Q′中獲得；

算法2中第一步的時(shí)間復(fù)雜度為O(n2)，與用戶數(shù)量有關(guān)，第二步和第三步的時(shí)間復(fù)雜度為O(n×m)，與用戶數(shù)量和服務(wù)數(shù)量有關(guān)。算法3的時(shí)間復(fù)雜度為O(n+m)。在真實(shí)的QoS預(yù)測(cè)過(guò)程中，填充QoS矩陣的步驟可以在離線的情況下完成，預(yù)測(cè)待測(cè)用戶數(shù)據(jù)時(shí)，可在保證預(yù)測(cè)的時(shí)間效率的基礎(chǔ)上提高預(yù)測(cè)的準(zhǔn)確性。

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

實(shí)驗(yàn)數(shù)據(jù)集使用WSDream-QoSDataSet2數(shù)據(jù)集[14]，包含339名用戶調(diào)用5 825項(xiàng)不同服務(wù)的QoS記錄。在實(shí)驗(yàn)中，隨機(jī)抽選200名用戶和1 000項(xiàng)服務(wù)的響應(yīng)時(shí)間數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，選取其中80%的用戶數(shù)據(jù)作為訓(xùn)練集，剩余作為測(cè)試集。實(shí)驗(yàn)所有算法均使用R語(yǔ)言實(shí)現(xiàn)。

在真實(shí)環(huán)境中訓(xùn)練集中的用戶也不可能有所有服務(wù)的調(diào)用記錄，故首先對(duì)所有數(shù)據(jù)做稀疏化處理，稀疏度按照5%的遞增速度依次從10%取到50%。然后使用本文中提出的基于云模型的QoS記錄填充方法對(duì)訓(xùn)練集中的用戶服務(wù)調(diào)用矩陣進(jìn)行填充。再使用基于云模型的相似度計(jì)算方法計(jì)算測(cè)試集中的用戶與訓(xùn)練集中用戶的相似度。

為了檢驗(yàn)本文提出的算法預(yù)測(cè)QoS值的準(zhǔn)確性，使用平均絕對(duì)誤差(MAE)對(duì)算法進(jìn)行檢驗(yàn)，MAE的值越小說(shuō)明預(yù)測(cè)的效果越好。

(7)

為了研究本文算法在不同矩陣密度情況下的預(yù)測(cè)情況，用EuLICM算法與基于余弦相似度的協(xié)同過(guò)濾算法、基于PCC的協(xié)同過(guò)濾算法以及基于LICM的協(xié)同過(guò)濾算法進(jìn)行對(duì)比。再將以上算法和使用本文填充算法的EuLICM預(yù)測(cè)結(jié)果進(jìn)行對(duì)比。每種算法均重復(fù)實(shí)驗(yàn)多次，取均值作為實(shí)驗(yàn)結(jié)果。圖3是使用EuLICM算法的協(xié)同過(guò)濾與使用LICM的協(xié)同過(guò)濾算法以及其他常用算法在10%到50%密度下MAE值對(duì)比。圖4是使用本文填充方法后的預(yù)測(cè)結(jié)果與常用算法的對(duì)比。圖5是使用本文填充方法的EuLICM和不使用填充的EuLICM的推薦質(zhì)量比較。

圖3 矩陣密度變化對(duì)無(wú)填充預(yù)測(cè)算法的影響

圖4 矩陣密度變化對(duì)有填充預(yù)測(cè)算法的影響

由圖3可知，使用EuLICM算法作為相似度計(jì)算方法預(yù)測(cè)Web服務(wù)QoS的結(jié)果與對(duì)比方法相比有更低的MAE值。說(shuō)明使用QoS特征向量的歐幾里得距離計(jì)算相似度確實(shí)可以提高預(yù)測(cè)的準(zhǔn)確性。根據(jù)圖4可知本文提出的QoS預(yù)測(cè)算法在精度上相對(duì)于現(xiàn)有協(xié)同過(guò)濾算法有較明顯提升。在矩陣密度為10%的情況下MAE值與對(duì)比方法相比要低0.2，但是隨著矩陣密度提高，MAE值差距在減小，在50%的矩陣密度情況下MAE值差大約為0.1。分析圖5可得，在矩陣密度較低的預(yù)測(cè)情況中采用結(jié)合云模型與服務(wù)信息的矩陣填充方法對(duì)矩陣填充，可以使預(yù)測(cè)準(zhǔn)確性獲得較大的提升。但是隨著矩陣密度的增加，訓(xùn)練集用戶的QoS記錄的空值的情況會(huì)減少，使用填充的算法和不使用的算法預(yù)測(cè)結(jié)果的MAE值差距會(huì)變小。在真實(shí)的Web服務(wù)預(yù)測(cè)情況下，通過(guò)本文的方法將QoS訓(xùn)練集補(bǔ)充完整，能夠較大程度地提高在Web服務(wù)調(diào)用稀疏的情況下的預(yù)測(cè)結(jié)果準(zhǔn)確性。

為了研究本文算法在選取不同鄰居數(shù)時(shí)的表現(xiàn)，依次設(shè)置最近鄰居數(shù)量k的值從2、4、6、8、10、12對(duì)結(jié)果進(jìn)行檢驗(yàn)。圖6為在矩陣稀疏度為25%情況下預(yù)測(cè)結(jié)果MAE的變化情況。

圖6 k值對(duì)預(yù)測(cè)準(zhǔn)確度的影響情況

圖6是在取不同的最近鄰居數(shù)時(shí)算法預(yù)測(cè)結(jié)果MAE的變化情況?？梢园l(fā)現(xiàn)，當(dāng)所取的鄰居數(shù)不斷增大時(shí)，預(yù)測(cè)結(jié)果的MAE會(huì)變低，但是當(dāng)鄰居數(shù)大于一個(gè)閾值之后預(yù)測(cè)準(zhǔn)確性會(huì)趨于穩(wěn)定。并且該閾值與訓(xùn)練集的數(shù)量有關(guān)，當(dāng)訓(xùn)練集數(shù)量增加時(shí)因?yàn)橄嗨贫容^高的用戶也會(huì)相應(yīng)的增加，只有相似度較高的用戶才會(huì)對(duì)預(yù)測(cè)結(jié)果有明顯影響。

4 結(jié) 語(yǔ)

為了解決傳統(tǒng)基于協(xié)同過(guò)濾算法的QoS預(yù)測(cè)算法在稀疏數(shù)據(jù)集上預(yù)測(cè)效果不好的問題，本文在現(xiàn)有的基于云模型的協(xié)同過(guò)濾算法上，先是基于歐幾里得距離對(duì)云模型相似度的計(jì)算方法進(jìn)行改進(jìn)，再提出了一種結(jié)合云模型和服務(wù)信息的QoS數(shù)據(jù)填充方法。實(shí)驗(yàn)結(jié)果顯示，本文方法能夠提高在稀疏數(shù)據(jù)集上QoS預(yù)測(cè)的準(zhǔn)確性。未來(lái)工作：在云模型相似度計(jì)算過(guò)程中再考慮特征向量各個(gè)數(shù)字的數(shù)量關(guān)系并設(shè)計(jì)一套權(quán)值機(jī)制。

[1] Shao Lingshuang,Zhang Jing,Wei Yong,et al.Personalized QoS Prediction for Web Services Via Colaborative Filtering[C]//IEEE International Conference on Web Services.Salt Lake City:IEEE,2007:439-446.

[2] Zheng Z,Ma H,Lyu M R,et al.WSRec:A Collaborative Filtering Based Web Service Recommender System[C]//Proceedings of the 2009 IEEE International Conference on Web Services (ICWS 2009),2009:437-444.

[3] Zheng Z,Ma H,Lyu M R,et al.Collaborative Web Service QoS Prediction via Neighborhood Integrated Matrix Factorization[J].IEEE Transactions on Services Computing,2013,6(3):289-299.

[4] Yin J,Wei L,Deng S,et al.Colbar:A collaborative location-based regularization framework for QoS prediction[J].Information Sciences,2014,265(5): 68-84.

[5] 徐翔,王煦法.協(xié)同過(guò)濾算法中的相似度優(yōu)化方法[J].計(jì)算機(jī)工程,2010,36(6):52-54,57.

[6] 余志虎,戚玉峰.一種基于云模型數(shù)據(jù)填充的算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2010,20(12):34-37.

[7] 劉發(fā)升,洪營(yíng).基于用戶特征屬性和云模型的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)工程與科學(xué),2014,36(6):1172-1176.

[8] 李德毅,孟海軍,史雪梅.隸屬云和隸屬云發(fā)生器[J].計(jì)算機(jī)研究與發(fā)展,1995,32(6):15-20.

[9] Wang G,Xu C,Li D,et al.Generic normal cloud model[J].Information Sciences,2014,280:1-15.

[10] 張光衛(wèi),康建初,李鶴松,等.面向場(chǎng)景的協(xié)同過(guò)濾推薦算法[J].系統(tǒng)仿真學(xué)報(bào),2006,18(s2):595-601.

[11] 張光衛(wèi),李德毅,李鵬,等.基于云模型的協(xié)同過(guò)濾推薦算法[J].軟件學(xué)報(bào),2007,18(10):2403-2411.

[12] 張龍昌,楊艷紅,趙緒輝.基于云模型的SaaS決策方法[J].電子學(xué)報(bào),2015,43(5):987-992.

[13] 劉志中,宋成,安吉宇,等.Web服務(wù)質(zhì)量動(dòng)態(tài)預(yù)測(cè)方法研究[J].計(jì)算機(jī)應(yīng)用,2014,34(5):1326-1330.

[14] WS-DREAM[EB/OL].[2014-08-29].http://www.wsdream.net/.

COLLABORATIVEWEBSERVICEQOSPREDICTIONBASEDONCLOUDMODEL

Duan Qiushi Hu Zhigang

(SchoolofSoftware,CentralSouthUniversity,Changsha410075,Hunan,China)

With the rapid growth of the number of Web services in recent years, the user-service QoS record matrix has become increasingly sparse. In order to solve the problem that the traditional collaborative filtering algorithm is not accurate enough in the sparse data sets, we improved collaborative filtering algorithm based on cloud model and applied the algorithm to predict the QoS of Web service. The similarity of cloud model was calculated by feature vector based on Euclidean distance, because that the Euclidean distance is sensitive to numerical. Considering users call the same service provider of different services have similar experience, we use cloud model similarity and services information to filling the QoS matrix. To solve the problem that sparse data set leads low prediction accuracy, we predicted the QoS of service user by using the filled QoS matrix. The experimental results show this algorithm can effectively improve the prediction accuracy of QoS compared with the traditional collaborative filtering method.

Web service QoS prediction Collaborative filtering Cloud model Similarity computation

2017-02-15。國(guó)家自然科學(xué)基金項(xiàng)目(61572525)。段秋實(shí)，碩士生，主研領(lǐng)域：服務(wù)計(jì)算。胡志剛，教授。

TP3

A

10.3969/j.issn.1000-386x.2017.11.004