基于位置關(guān)系模糊聚類的Web服務(wù)質(zhì)量預(yù)測

隨著面向服務(wù)計算的快速普及，Web服務(wù)的增長也變得十分迅速，因而在面對眾多可以提供相似功能的Web服務(wù)時，如何能夠讓用戶找到最佳的服務(wù)成為一個熱門問題[1]。針對這個問題，引入服務(wù)質(zhì)量(Quality of Service，QoS)的定義，QoS代表的是Web服務(wù)的非功能屬性，如可用性、可靠性、響應(yīng)時間、吞吐量、安全性和服務(wù)費用等[2]。因為這些屬性可以很好地體現(xiàn)Web服務(wù)性能的差異化，所以在為用戶進(jìn)行服務(wù)推薦時常將其作為首要且重點考慮的指標(biāo)。但在真實的情景中，用戶所調(diào)用的服務(wù)只是眾多Web服務(wù)中很少的一部分，這就導(dǎo)致了可供參考的用戶歷史QoS數(shù)據(jù)嚴(yán)重稀疏，因而根據(jù)已知的QoS歷史信息對缺失的QoS數(shù)據(jù)進(jìn)行預(yù)測成為服務(wù)推薦中的一個重要研究問題。

在Web服務(wù)質(zhì)量預(yù)測的研究中，協(xié)同過濾(Collaborative Filtering，CF)[3]是一種常用的方法。Shao等[4]根據(jù)相似用戶的已知QoS數(shù)據(jù)利用CF預(yù)測QoS。Zheng等[5]在考慮了請求用戶的相似用戶之外，還進(jìn)一步挖掘了目標(biāo)服務(wù)的相似服務(wù)，從而提出了混合CF預(yù)測QoS。以上兩者均采用皮爾遜相關(guān)系數(shù)計算相似度，在面對數(shù)據(jù)稀疏問題時，相似度準(zhǔn)確度較低。為此，申利民等[6]改進(jìn)了相似度的計算方法，并且又考慮到用戶調(diào)用服務(wù)的歷史QoS數(shù)據(jù)之間存在的比率關(guān)系，以此來提高預(yù)測精度。此外，為了發(fā)掘歷史QoS數(shù)據(jù)的潛在特征，唐瑞春等[7]基于信任度模型來尋找最佳的相似用戶，再結(jié)合CF方法預(yù)測QoS值。以上學(xué)者只針對歷史QoS數(shù)據(jù)進(jìn)行了分析，忽略了用戶與服務(wù)自身的內(nèi)在特征，因而會存在一定的噪聲數(shù)據(jù)影響QoS預(yù)測精度。因此，徐文庭等[8]針對噪聲問題構(gòu)建分類樹，并基于同一分類集合使用Slope One算法進(jìn)行預(yù)測。任迪等[9]將用戶的IP地址、經(jīng)緯度、所在國家等內(nèi)在屬性作為特征構(gòu)建貝葉斯分類器，并將分類概率作為權(quán)重因子進(jìn)行服務(wù)質(zhì)量的預(yù)測。Chen等[10]提出了一種新的基于CF的Web服務(wù)QoS預(yù)測，利用位置信息和QoS歷史數(shù)據(jù)對用戶和服務(wù)進(jìn)行聚類，并根據(jù)聚類結(jié)果對用戶進(jìn)行個性化的服務(wù)推薦。Liu等[11]提出同時利用用戶和Web服務(wù)的位置來為目標(biāo)用戶或服務(wù)選擇相似用戶，并對用戶和Web服務(wù)進(jìn)行增強(qiáng)的相似性度量。魯城華等[12]將Web服務(wù)的QoS信息與用戶和服務(wù)的內(nèi)在區(qū)域?qū)傩韵嘟Y(jié)合，采用矩陣分解法構(gòu)建預(yù)測模型。

由于用戶與服務(wù)所在區(qū)域的不同，它們之間的網(wǎng)絡(luò)情況也會存在差距，而網(wǎng)絡(luò)因素對QoS的影響是客觀存在的，但傳統(tǒng)協(xié)同過濾只是單純的考慮歷史數(shù)據(jù)的相似性，并沒有考慮用戶與服務(wù)的位置相關(guān)性，因而會出現(xiàn)相似度計算不準(zhǔn)確的問題。為進(jìn)一步充分利用用戶與服務(wù)的位置信息，并考慮到硬聚類算法的局限性(若聚類簇數(shù)過小，則聚類后同一簇之中簇的上界與下界會存在一定差距；若聚類簇數(shù)過大，則同一聚類簇中可用數(shù)據(jù)就會變少)，本文提出一種基于位置關(guān)系模糊聚類的Web服務(wù)質(zhì)量預(yù)測方法：

(1)考慮到用戶與服務(wù)之間因地理位置因素不同所造成網(wǎng)絡(luò)環(huán)境的影響，本文根據(jù)用戶與服務(wù)的內(nèi)在經(jīng)緯度特征數(shù)據(jù)，利用距離關(guān)系數(shù)據(jù)建立模糊C均值聚類模型，并根據(jù)得到的隸屬度矩陣采用新的相似度計算方法計算位置關(guān)系上的相似度。

(2)針對傳統(tǒng)相似度計算方法在數(shù)據(jù)高稀疏度的情況下精度較低這一問題，本文利用用戶的歷史QoS數(shù)據(jù)，采用一種改進(jìn)的相似度計算方法計算用戶或服務(wù)之間的相似度，并使用權(quán)值將用戶或服務(wù)位置關(guān)系上的相似度與歷史QoS相似度相融合，進(jìn)而進(jìn)行QoS的預(yù)測。

1 基于位置關(guān)系模糊聚類的協(xié)同預(yù)測方法

1.1 位置關(guān)系模糊C均值聚類算法

1.1.1 特征提取

本文所需要的特征，均由真實的數(shù)據(jù)集提供，其中用戶與服務(wù)的內(nèi)在信息包括：ID、IP地址、國家、大陸、緯度、經(jīng)度等[9]，其中服務(wù)的經(jīng)緯度特征為服務(wù)提供商所在的具體位置。在構(gòu)建模糊C均值聚類模型前需要提取每個用戶和服務(wù)的經(jīng)緯度信息，以此來計算兩者之間的距離。數(shù)據(jù)集提供的經(jīng)緯度信息采用WGS84格式，其中北緯為正，南緯為負(fù)，東經(jīng)為正，西經(jīng)為負(fù)，具體見表1、表2。

表1 用戶的位置信息

表2 服務(wù)的位置信息

1.1.2 計算(用戶-服務(wù))的位置關(guān)系

本文在計算用戶與服務(wù)之間的位置關(guān)系時，根據(jù)數(shù)據(jù)集中提取的經(jīng)緯度特征采用半正矢(Haversine)[13]距離公式計算用戶到服務(wù)之間的距離，從而得到一個(用戶-服務(wù))的距離矩陣。半正矢公式為

(1)

其中r代表地球的半徑，(la1，lo1)與(la2，lo2)分別代表需要計算距離的兩個不同樣本的(緯度，經(jīng)度)。

根據(jù)得到的(用戶-服務(wù))之間的距離關(guān)系，生成可用于模糊聚類的數(shù)據(jù)集合L，具體見表3。

表3 (用戶-服務(wù))距離關(guān)系 km

1.1.3 模糊C均值聚類原理

算法原理：若將所給的n個樣本數(shù)據(jù)集合x={x1，x2，…，xn}，聚類到k個不同的簇之中，需要將目標(biāo)函數(shù)Jm不斷進(jìn)行迭代，從而使其最小化。目標(biāo)函數(shù)Jm為

(2)

根據(jù)目標(biāo)函數(shù)Jm，進(jìn)行最優(yōu)化求解，可得聚類簇中心cj與隸屬度uij的表達(dá)公式：

(3)

(4)

在聚類過程中需要引入一個閾值ε，并將其設(shè)置為聚類停止迭代的條件。具體迭代停止條件為

(5)

1.1.4 構(gòu)建聚類模型，獲取隸屬度

通過1.1.1與1.1.2，我們已經(jīng)將用戶與服務(wù)的內(nèi)在經(jīng)緯度特征提取出來，并根據(jù)半正矢距離計算公式得到了(用戶-服務(wù))距離關(guān)系的數(shù)據(jù)集合L，因而可進(jìn)行模糊C均值聚類算法模型的構(gòu)建：

輸入：(用戶-服務(wù))距離關(guān)系的數(shù)據(jù)集合L

過程：(1)選擇合適的聚類簇數(shù)k及隸屬度因子m；

(2)初始化簇中心cj、隸屬度uij；

(3)通過不斷迭代計算，更新隸屬度uij與簇中心cj；

(4)當(dāng)達(dá)到指定迭代停止條件時，完成聚類。

輸出：隸屬度矩陣U

因為在對QoS進(jìn)行預(yù)測時，使用的是混合協(xié)同過濾算法，即使用一定權(quán)值融合基于用戶與基于服務(wù)的協(xié)同過濾算法，那么在對位置關(guān)系進(jìn)行相似度的計算時，也需要根據(jù)基于用戶或基于服務(wù)分別進(jìn)行位置關(guān)系上相似度的計算，以便融合混合協(xié)同過濾算法根據(jù)歷史QoS數(shù)據(jù)計算的相似度。所以在構(gòu)建模糊C均值聚類時需要分別對基于用戶與基于服務(wù)進(jìn)行模糊C均值聚類模型的建立，從而得到用戶所屬聚類簇的隸屬度矩陣Ud以及服務(wù)所屬聚類簇的隸屬度矩陣Us。Ud與Us見表4、表5(此表作為示例，設(shè)置的聚類簇數(shù)為4)。

表4 用戶的隸屬度矩陣Ud

表5 服務(wù)的隸屬度矩陣Us

1.2 協(xié)同過濾算法預(yù)測QoS

1.2.1 位置關(guān)系的相似度計算

考慮到傳統(tǒng)聚類方法使得同一聚類簇中的邊緣用戶或服務(wù)的相似度存在一定差距，從而影響最終的QoS預(yù)測結(jié)果，根據(jù)模糊C均值聚類所得的隸屬度計算，引入位置關(guān)系相似度的計算方法。由于在FCM模型中所得到的隸屬度矩陣中每個用戶都具有相同的維度，并且不存在缺失值，所以對其進(jìn)行相似度的計算就不用擔(dān)心數(shù)據(jù)稀疏性對精度所造成的影響。因而，本文提出一種改進(jìn)的相似度計算方法，通過用戶與服務(wù)的隸屬度矩陣將比值相似度的計算算法與歐式距離的計算方法相結(jié)合，從而更加準(zhǔn)確地計算用戶和服務(wù)在位置關(guān)系隸屬度上的相似度：

(6)

式中當(dāng)max(xi，yi)=0時，說明最小與最大都為0，因而分式直接賦值為1。k代表的是聚類簇數(shù)即所得隸屬度矩陣的維數(shù)。x與y分別代表請求用戶或服務(wù)與其他用戶或服務(wù)所屬聚類簇的隸屬度向量，并且根據(jù)計算不同對象的隸屬度相似度時，x與y所屬集合不同。當(dāng)計算用戶所在位置關(guān)系上的相似度時，x,y∈Ud，得到相似度SimUd。當(dāng)計算服務(wù)所在位置關(guān)系上的相似度時，x,y∈Us，得到相似度SimUs。

1.2.2 歷史QoS數(shù)據(jù)的相似度計算

由于在歷史QoS數(shù)據(jù)稀疏的情況下，傳統(tǒng)相似度的計算方法會因為共同調(diào)用服務(wù)數(shù)量過小而造成較大誤差。因而本文提出一種改進(jìn)的相似度計算方法，充分利用到已知的QoS數(shù)據(jù)計算與用戶或服務(wù)之間的相似度，并給與擁有更多共同調(diào)用服務(wù)的用戶之間的相似度更高的權(quán)值。在基于用戶的協(xié)同過濾算法中，請求用戶u與相似鄰居用戶v之間的歷史QoS數(shù)據(jù)相似度的計算為

(7)

其中Su表示請求用戶u調(diào)用過的服務(wù)集合，Sv表示相似鄰居用戶v調(diào)用過的服務(wù)集合，|Su∩Sv|表示請求用戶u和相似鄰居用戶v共同調(diào)用過的服務(wù)個數(shù)，|Su|和|Sv|代表的是請求用戶u和相似鄰居用戶v調(diào)用過的服務(wù)個數(shù)，qu,i為請求用戶u調(diào)用服務(wù)i的QoS值，qv,j代表的是相似鄰居用戶v調(diào)用服務(wù)j的QoS值。

在基于服務(wù)的協(xié)同過濾推薦方法中，采用式(8)來計算目標(biāo)服務(wù)s與相似服務(wù)w的相似度：

(8)

其中Us表示調(diào)用過目標(biāo)服務(wù)s的用戶集合，Uw表示調(diào)用過相似鄰居服務(wù)w的用戶集合，|Us∩Uw|表示共同調(diào)用過目標(biāo)服務(wù)s和相似鄰居服務(wù)w的用戶個數(shù)，|Us|和|Uw|分別表示調(diào)用過目標(biāo)服務(wù)s和相似服務(wù)w的用戶數(shù)，qi,s表示用戶i調(diào)用服務(wù)s的QoS值，qj,w表示用戶j調(diào)用服務(wù)w的QoS值。

1.2.3 融合相似度

為了緩解因地理因素不同造成相似度計算精度的影響，通過設(shè)置權(quán)值α、β將用戶和服務(wù)的位置關(guān)系相似度與歷史QoS數(shù)據(jù)相似度相融合，用戶或服務(wù)之間的相似度融合公式為

Simcd=αSimUd+(1-α)Simd,α∈[0,1]，

(9)

Simcs=βSimUs+(1-β)Sims,β∈[0,1]。

(10)

1.2.4 預(yù)測QoS

在分別計算用戶和服務(wù)的位置關(guān)系相似度及歷史QoS數(shù)據(jù)相似度并進(jìn)行融合之后，通過混合協(xié)同過濾算法來預(yù)測請求用戶調(diào)用目標(biāo)服務(wù)的QoS值，并且在預(yù)測QoS值的過程中考慮到不同用戶之間QoS值存在一定的比例關(guān)系[6]，使用其平均值的比值作為一定約束，使QoS預(yù)測值更加準(zhǔn)確。

在基于用戶的協(xié)同過濾推薦方法中，通過請求用戶與相似鄰居的相似度來預(yù)測請求用戶u調(diào)用目標(biāo)服務(wù)s的QoS值：

(11)

在基于服務(wù)的協(xié)同過濾推薦方法中，采用式(12)來預(yù)測請求用戶u調(diào)用服務(wù)s的QoS值：

(12)

基于用戶和基于服務(wù)得到的兩個預(yù)測值具有不同的預(yù)測精度，使用兩個置信權(quán)值conu和cons來平衡這兩個預(yù)測值：

(13)

(14)

不同的數(shù)據(jù)集有其自身的數(shù)據(jù)分布特性，在使用置信權(quán)值來平衡之外，還需要加入?yún)?shù)λ(0≤λ≤1)來優(yōu)化根據(jù)基于用戶和服務(wù)得到的兩個預(yù)測值的權(quán)重。根據(jù)得到的置信權(quán)值，用ωu和ωs作為權(quán)重因子融合基于用戶和基于服務(wù)預(yù)測值，其中ωu+ωs=1，ωu和ωs的定義如下：

(15)

(16)

引入權(quán)重因子后，就來預(yù)測請求用戶u調(diào)用預(yù)測服務(wù)s的QoS值：

(17)

2 實驗結(jié)果

2.1 數(shù)據(jù)集

為了保證實驗的真實可靠性，本文選擇在真實的數(shù)據(jù)集上驗證所提方法的有效性。本文使用的數(shù)據(jù)集為WS-DREAM公開發(fā)布的數(shù)據(jù)集Dataset Dream dataset2，該數(shù)據(jù)集記錄了339名用戶調(diào)用5825個Web服務(wù)的QoS值[15-16]，包括響應(yīng)時間和吞吐量兩個屬性，其中響應(yīng)時間范圍為0～20 s，吞吐量范圍為0～1000 kbps。本文針對響應(yīng)時間數(shù)據(jù)進(jìn)行實驗分析，并在進(jìn)行實驗前需要刪除服務(wù)中響應(yīng)時間為-1，代表訪問超時的服務(wù)。

因為本文需要研究在數(shù)據(jù)稀疏的情況下，所提方法對于QoS預(yù)測的精確度提升。但在原始的數(shù)據(jù)集中，已知的響應(yīng)時間數(shù)據(jù)比較密集，因而需要對數(shù)據(jù)集進(jìn)行稀疏化處理。本文將在85%、95%兩種不同稀疏度下進(jìn)行最優(yōu)化參數(shù)實驗，在80%、85%、90%、95%四種不同稀疏度下進(jìn)行實驗對比，從而驗證所提方法的有效性。

2.2 評價指標(biāo)

本文采用平均絕對誤差(mean absolute error，MAE)[17]和歸一化平均絕對誤差(normalized mean absolute error，NMAE)[18-20]來衡量預(yù)測精度的評價指標(biāo)。具體如公式(18)、(19)所示：

(18)

(19)

式中N表示預(yù)測的所有QoS的個數(shù)，Pu,s表示請求用戶u調(diào)用服務(wù)s的實際QoS值，Qu,s表示請求用戶u調(diào)用服務(wù)s的預(yù)測QoS值。

2.3 實驗過程、參數(shù)設(shè)置及對比實驗

在研究本文所提基于位置關(guān)系模糊聚類的協(xié)同預(yù)測方法(Collaborative prediction method based on fuzzy clustering of location relationship，CP-FCLR)時，需要對一些參數(shù)進(jìn)行最優(yōu)化選擇。然后再將本文所提CP-FCLR方法與以下幾種方法分別在不同稀疏度情況下進(jìn)行實驗對比：UPCC(采用基于用戶的協(xié)同過濾算法預(yù)測QoS)、IPCC(采用基于服務(wù)的協(xié)同過濾算法預(yù)測QoS)、WSRec(采用混合協(xié)同過濾算法預(yù)測QoS)[19]、SVD[20](采用矩陣因子分解算法進(jìn)行預(yù)測)、CACF[8](采用CART分類樹與Slope One算法進(jìn)行預(yù)測)、BBCF[9](結(jié)合貝葉斯分類器進(jìn)行協(xié)同預(yù)測)，前三種方法均使用皮爾遜相關(guān)系數(shù)計算用戶或服務(wù)之間的相似度。

2.3.1 融合權(quán)值α、β的最優(yōu)選擇及敏感性分析

為了研究相似度融合時，融合權(quán)值α、β對實驗結(jié)果的影響、最優(yōu)化選擇及其在不同稀疏度情況下的敏感性分析，本文使用改進(jìn)后的融合相似度計算方法分別在基于用戶與基于服務(wù)的情況下進(jìn)行實驗。選取不同的融合權(quán)值α、β，分別在稀疏度為85%、95%的數(shù)據(jù)集上進(jìn)行實驗，根據(jù)評價指標(biāo)MAE進(jìn)行對比，從而選擇最優(yōu)權(quán)值。實驗結(jié)果如圖1、圖2所示。

圖1 稀疏度85%下α與β對MAE的影響 圖2 稀疏度95%下α與β對MAE的影響

根據(jù)實驗結(jié)果可以看出融合用戶和服務(wù)的地理位置關(guān)系相似度可以在一定程度上提高相似度的準(zhǔn)確性，也緩解了噪聲數(shù)據(jù)對實驗結(jié)果的影響，從而提高QoS的預(yù)測精度。并且，在不同的稀疏度下參數(shù)α與β的最優(yōu)取值比較穩(wěn)定，都在取值為0.4或0.5時，所得到的預(yù)測結(jié)果最優(yōu)，并且在取值為0.4或0.5時得到的誤差值相差很小，因而可以看出融合權(quán)值α、β的最優(yōu)取值對于歷史QoS數(shù)據(jù)的稀疏度不敏感。因此通過綜合考慮，在本文后續(xù)的工作中將相似度的融合權(quán)值α與β設(shè)置為0.4。

2.3.2 不同Top-K對實驗精度的影響

因為數(shù)據(jù)稀疏度的不同，在選擇最近鄰時，可供選擇的近鄰數(shù)也會存在較大差別(稀疏度越大，近鄰數(shù)越少)。所以根據(jù)Top-K原則，本文在數(shù)據(jù)稀疏度為85%、95%的數(shù)據(jù)集下，分別選取不同的最近鄰數(shù)K，根據(jù)評價指標(biāo)MAE進(jìn)行分析，從而選取最優(yōu)的最近鄰數(shù)K進(jìn)行QoS預(yù)測。具體實驗結(jié)果如圖3、圖4所示。

圖3 稀疏度85%下近鄰數(shù)K對MAE的影響 圖4 稀疏度95%下近鄰數(shù)K對MAE的影響

圖5 不同λ對MAE的影響

2.3.3 不同λ值對實驗精度的影響

為了能夠更好地將基于用戶的協(xié)同過濾與基于服務(wù)的協(xié)同過濾相融合，引入?yún)?shù)λ形成權(quán)重因子融合兩種算法。為了選擇最優(yōu)的λ值，本文使用提出的CP-FCLR算法，在數(shù)據(jù)稀疏度為85%、95%的數(shù)據(jù)集下選擇不同的λ值進(jìn)行實驗。

實驗結(jié)果如圖5所示，根據(jù)評價指標(biāo)分析，在稀疏度85%、95%下，當(dāng)λ取值0.7時，MAE最小，即所得實驗結(jié)果最優(yōu)。綜合考慮，本文選擇0.7作為λ的值。

2.3.4 不同稀疏度與預(yù)測樣本數(shù)量下的預(yù)測精度與運行時間

在稀疏度為85%、95%的情況下，使用本文所提方法進(jìn)行預(yù)測，設(shè)置待預(yù)測的樣本數(shù)量分別為10、20、30、40、50，經(jīng)過多次實驗取其均值，分別得到評價指標(biāo)MAE、NMAE及運行時間Time(單位：s)，所得實驗結(jié)果見表6。根據(jù)實驗結(jié)果可以看出，隨著樣本數(shù)量的提高，評價指標(biāo)MAE、NMAE的值逐漸趨于平穩(wěn)，從而證明了本文所提方法的有效性。此外，在實驗的運行時間上，本文所提CP-FCLR方法相對于傳統(tǒng)方法有著較大的提升，從而可以證明此方法具有更好的實用性。

表6 在不同稀疏度與樣本數(shù)量下的MAE、NMAE、Time

2.3.5 不同稀疏度下各種方法的對比實驗

將本文所提方法在稀疏度為80%、85%、90%、95%的數(shù)據(jù)集上進(jìn)行多次實驗并取均值，將實驗結(jié)果與UPCC、IPCC、WSRec、SVD、CACF、BBCF六種方法進(jìn)行對比，具體見表7。

表7 不同方法在不同稀疏度下的MAE與NMAE對比

根據(jù)實驗結(jié)果中評價指標(biāo)MAE與NMAE的值進(jìn)行對比可以看出，本文所提方法在QoS預(yù)測精度上相較于其他6種方法有著一定的提升。在不同稀疏度的情況下，本文方法相對于UPCC、IPCC、WSRec、SVD、CACF、BBCF六種方法所得實驗結(jié)果的MAE分別平均降低了53%、52.1%、50.8%、39%、28.4%、27.2%；NMAE分別平均降低了55.5%、52.5%、46.5%、23.3%、10%、9.1%。同時，在數(shù)據(jù)稀疏度比較高的情況下本文所提CP-FCLR方法依舊有著更加良好的預(yù)測精度。

3 總結(jié)與展望

本文針對用戶與服務(wù)的地理位置因素以及歷史QoS數(shù)據(jù)稀疏所造成預(yù)測精度較低這一問題，提出了一種基于位置關(guān)系模糊聚類的混合協(xié)同預(yù)測方法，利用一種改進(jìn)的相似度計算方法并融合用戶或服務(wù)位置關(guān)系相似度，緩解了地理位置因素對QoS預(yù)測的影響，同時在數(shù)據(jù)稀疏的情況下有著更優(yōu)的預(yù)測精度。在之后的工作中，將會把位置關(guān)系上的模糊聚類與隨機(jī)森林相結(jié)合，將隸屬度作為特征進(jìn)行隨機(jī)森林分類，從而達(dá)到過濾噪聲的效果。