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

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

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

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

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

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

1.1 位置關系模糊C均值聚類算法

1.1.1 特征提取

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

表1 用戶的位置信息

表2 服務的位置信息

1.1.2 計算(用戶-服務)的位置關系

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

(1)

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

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

表3 (用戶-服務)距離關系 km

1.1.3 模糊C均值聚類原理

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

(2)

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

(3)

(4)

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

(5)

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

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

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

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

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

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

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

輸出：隸屬度矩陣U

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

表4 用戶的隸屬度矩陣Ud

表5 服務的隸屬度矩陣Us

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

1.2.1 位置關系的相似度計算

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

(6)

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

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

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

(7)

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

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

(8)

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

1.2.3 融合相似度

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

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

(9)

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

(10)

1.2.4 預測QoS

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

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

(11)

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

(12)

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

(13)

(14)

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

(15)

(16)

引入權(quán)重因子后，就來預測請求用戶u調(diào)用預測服務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服務的QoS值[15-16]，包括響應時間和吞吐量兩個屬性，其中響應時間范圍為0～20 s，吞吐量范圍為0～1000 kbps。本文針對響應時間數(shù)據(jù)進行實驗分析，并在進行實驗前需要刪除服務中響應時間為-1，代表訪問超時的服務。

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

2.2 評價指標

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

(18)

(19)

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

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

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

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

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

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

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

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

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

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

圖5 不同λ對MAE的影響

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

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

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

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

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

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

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

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

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

根據(jù)實驗結(jié)果中評價指標MAE與NMAE的值進行對比可以看出，本文所提方法在QoS預測精度上相較于其他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方法依舊有著更加良好的預測精度。

3 總結(jié)與展望

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