王 磊，瞿佳明

(南京林業(yè)大學經(jīng)濟管理學院，江蘇 南京 210037)

1 引言

面向服務(wù)的架構(gòu)SOA(Service-Oriented Architecture)是近年來新興的一種計算機軟件開發(fā)思想，它將網(wǎng)絡(luò)上的各種計算能力進行集成，從而以一種合作的方式去完成一定的計算任務(wù)，因此人們期待通過它解決長期困擾軟件工程領(lǐng)域的軟件復用和智能化軟件架構(gòu)問題。在面向服務(wù)的架構(gòu)中，“服務(wù)”是一個與平臺無關(guān)的抽象概念，在實際應(yīng)用中可通過Web服務(wù)來實現(xiàn)。企業(yè)可動態(tài)集成 Web服務(wù)，從而通過最少量的編程來滿足復雜的業(yè)務(wù)需求[1,2]。根據(jù)ProgrammableWeb.com所收集的大量公開可用的Web服務(wù)信息，目前有大量功能相同(或相似)的Web服務(wù)可供選擇，因此在服務(wù)集成(組合)過程不得不面臨服務(wù)選擇問題。

在進行服務(wù)選擇時，一般會依據(jù)多個Web服務(wù)質(zhì)量QoS(Quality of Service)參數(shù)展開，如服務(wù)可靠性、響應(yīng)時間、吞吐量、價格等。其中可靠性是在開展服務(wù)選擇過程中參考的重要指標之一。作為服務(wù)消費者，在軟件開發(fā)時選擇使用高質(zhì)量的Web服務(wù)是至關(guān)重要的，這可以提高軟件運行的穩(wěn)定性，減少后期的錯誤，甚至是重構(gòu)，從而減少時間與金錢的損失。

針對同一個Web服務(wù)而言，在不同的用戶調(diào)用所形成的通信鏈接下，其可靠性不同。為了給服務(wù)選擇提供參考，近年來有不少學者對服務(wù)的可靠性預測問題進行了研究。例如，Zheng等人[3,4]基于協(xié)同過濾和矩陣奇異值分解等方法所提出的個性化可靠性預測方法，通過部分客戶端隨機地對部分Web服務(wù)開展性能評估，進而可以預測任意客戶端在調(diào)用任意服務(wù)時的可靠性。

因為需要給服務(wù)選擇提供參考，在實際應(yīng)用中，Web服務(wù)可靠性預測結(jié)果的精度是至關(guān)重要的。在服務(wù)組合系統(tǒng)中，如果調(diào)用了可靠性低的服務(wù)，服務(wù)組合系統(tǒng)將不能穩(wěn)定地運行，服務(wù)提供商甚至會因為不能滿足服務(wù)等級協(xié)議SLA(Service Level Agreement)而面臨違約。為了保證Web服務(wù)可靠性預測結(jié)果的精度，本文對已有的Web服務(wù)可靠性預測方法進行適當改進，分別基于協(xié)同過濾方法和Slope One算法提出兩種不同的預測方法。實驗結(jié)果驗證了本文預測方法的有效性。

2 預備知識

2.1 Web服務(wù)可靠性

Web服務(wù)作為一種新興的技術(shù)，其可靠性研究借鑒了傳統(tǒng)的軟件可靠性研究的成果。Musa等人[5]對于軟件可靠性的定義是：“在一段時間或特定的自然單元內(nèi)軟件無失效運行的概率”。而IEEE Standard對此的定義是：“軟件可靠性是在特定的條件和特定的時段內(nèi)系統(tǒng)能夠持續(xù)運行的概率”。雖然表述有別，但可以看出，可靠性就是指軟件可以無故障運行的概率[4,6]。

有些專家和學者同時指出，Web服務(wù)的可靠性并不能簡單地定義為Web服務(wù)不失效的概率，因為除了不失效以外，Web服務(wù)的可靠性還包括是否滿足用戶需求等衡量標準[7,8]。例如,某一Web服務(wù)，其調(diào)用的返回本身并沒有錯誤，但是服務(wù)消費者并不能在SLA所規(guī)定的響應(yīng)時間內(nèi)接收到響應(yīng)，那么在這種情況下這一Web服務(wù)就不能被認為是可靠的。因此，Web服務(wù)可靠性不僅包括了Web服務(wù)正確性，還包括了Web服務(wù)可用性、響應(yīng)時間。Wang等人[9]提出一種性能敏感的Web服務(wù)可靠性定義，這一方法給每個Web服務(wù)設(shè)定一個響應(yīng)時間的約束，通過多次客戶端的調(diào)用測試，考察Web服務(wù)在不違反響應(yīng)時間約束下的正確的響應(yīng)的概率來描述Web服務(wù)的可靠性。

2.2 Web服務(wù)可靠性預測

由于網(wǎng)絡(luò)等環(huán)境因素、服務(wù)自身運行狀態(tài)等內(nèi)部因素，不同的用戶調(diào)用同一個服務(wù)的可靠性可能大相徑庭[3]，所以調(diào)用Web服務(wù)的失效概率不僅和Web服務(wù)本身有關(guān)，也和調(diào)用它的用戶相關(guān)。

Zheng等人[4]認為，Web服務(wù)可靠性預測就是基于過往的失效數(shù)據(jù)對未來的可靠性做出推測。數(shù)據(jù)的來源主要有以下兩個途徑：其一，服務(wù)提供者會提供一定的數(shù)據(jù)作為服務(wù)屬性的一部分供服務(wù)消費者在選擇服務(wù)時參考，但數(shù)據(jù)的客觀和真實與否需要服務(wù)消費者自行甄別。其二，服務(wù)注冊中心可以作為第三方對數(shù)據(jù)進行收集，相對于服務(wù)提供者，第三方數(shù)據(jù)往往更值得信賴。此外，用戶(即服務(wù)消費者)也能上傳調(diào)用服務(wù)的反饋信息[4]。

因此，對目標用戶調(diào)用目標服務(wù)的可靠性預測問題轉(zhuǎn)化為基于一個包含不同用戶調(diào)用不同服務(wù)的失效概率的矩陣數(shù)據(jù)集，通過對數(shù)據(jù)集中的數(shù)據(jù)進行運算，從而得出目標用戶調(diào)用目標服務(wù)的失效概率的預測結(jié)果。

假設(shè)已經(jīng)收集了一定的用戶調(diào)用服務(wù)的失效概率數(shù)據(jù)，即構(gòu)成了一個m行n列的矩陣,其中，m表示用戶的數(shù)量，n表示服務(wù)的數(shù)量。矩陣中每個元素pa,i的值表示用戶a調(diào)用服務(wù)i的失效概率，如果用戶a沒有調(diào)用過服務(wù)i，該元素為空值?，F(xiàn)在的問題就轉(zhuǎn)化為：如何通過矩陣中的已知值pa,i求解未知值pu,i。協(xié)同過濾算法[10]被廣泛應(yīng)用于求解這一問題。如基于相似用戶的預測方法，即根據(jù)目標用戶和其他用戶的相似性選擇一定用戶成為鄰居，然后基于鄰居對于目標服務(wù)的可靠性評估結(jié)果形成預測。

3 協(xié)同過濾服務(wù)可靠性預測的改進

3.1 基于用戶的協(xié)同過濾算法

基于用戶的協(xié)同過濾(User-based collaborative filtering)是利用鄰居的信息對目標用戶的空缺值進行預測的一種算法。其步驟大體上可分為以下幾步：相似性計算、鄰居選擇、預測值計算。

3.1.1 相似性計算

相似性計算通常是該算法的第一步，目的在于計算目標用戶和其他用戶之間的相似性，為下一步鄰居的選擇做準備。相似性計算主要有以下方法：

(1)余弦相似性。借鑒幾何學中余弦的概念，通過將矩陣中的值看作向量來衡量兩者之間的相似性，且計算用戶和服務(wù)相似性時向量分別為行向量和列向量。兩個向量夾角的余弦值就代表兩者的相似性。

(1)

其中，i是用戶a和用戶u共同調(diào)用過的服務(wù)，pa,i和pu,i的值分別表示用戶a和用戶u調(diào)用服務(wù)的失效概率。易知，兩者相似性越高，夾角就越小，相應(yīng)地余弦值越大，反之亦然。該計算的結(jié)果和相似性成正比，值越大表示相似性越大。

(2)皮爾遜相關(guān)系數(shù)。皮爾遜相關(guān)系數(shù)是常用來衡量多維向量相關(guān)性的一種方法，它是一個處于-1～1的值，-1表示兩者完全負相關(guān)，0表示兩者完全無關(guān)，1表示兩者完全正相關(guān)。該系數(shù)的計算公式如下：

Sim(a,u)=

(2)

(3)本文所采用的相似度計算方法。余弦相似度更多的是從方向上對矩陣中的行列向量進行區(qū)分，但是對矩陣中的數(shù)值(向量值)沒有足夠的敏感性。皮爾遜相關(guān)系數(shù)則是應(yīng)用最為廣泛的一種相似性計算方法，并且在“分數(shù)膨脹”(指個人的數(shù)據(jù)較為集中，然而和他人數(shù)據(jù)差異較大，這也符合用戶調(diào)用Web服務(wù)失效概率的特點)的情況下有良好的表現(xiàn)。結(jié)合實際情況，本文將選取皮爾遜相關(guān)系數(shù)作為相似性計算方法。

在協(xié)同過濾算法中，相似性計算通常是第一步，但也被認為是最重要的一步。因為相似性計算的合理性直接影響了能否有效地進行鄰居選擇，從而進一步影響預測效果。皮爾遜相關(guān)系數(shù)雖然在該算法中已經(jīng)得到了廣泛的應(yīng)用和認可，但是通過其計算公式我們不難發(fā)現(xiàn)，這一方法在某些應(yīng)用場景下并不能很好地衡量相似性的大小。例如,我們假設(shè)兩個用戶共同調(diào)用過的服務(wù)只有一項，但是通過相關(guān)系數(shù)計算之后，兩者的相似性卻比共同調(diào)用過很多服務(wù)的兩個用戶要高；在鄰居選擇時，和目標用戶僅僅共同調(diào)用過一項服務(wù)的用戶會被認為是更相似的鄰居，這是不合常理的。若要使得相關(guān)系數(shù)的值能有效地反映用戶的相關(guān)性，那么兩者共同調(diào)用過的服務(wù)也應(yīng)當作為衡量因素之一。在共同調(diào)用服務(wù)達到一定數(shù)量時，相關(guān)系數(shù)的值才具有參考價值。因此，本文提出一種對用戶相似性計算進行修正的方法，即：

(3)

其中，首先設(shè)置一個閾值β，該值衡量的是兩個用戶共同調(diào)用過的服務(wù)數(shù)量，如果兩個用戶共同調(diào)用過的服務(wù)數(shù)量大于或等于該閾值，則說明相似性具有足夠的參考價值，不需要修正;否則，需要通過除以一個懲罰因子γ來進行修正。

3.1.2 鄰居選擇

在完成了計算目標用戶和其他用戶的相似性之后，所有的數(shù)據(jù)形成了一個相似性數(shù)據(jù)集。因此，下一步就是從相似性數(shù)據(jù)集中選擇目標用戶的鄰居，即決定哪些用戶的數(shù)據(jù)可以被用來進行預測。通常我們認為，相似性越高的用戶是目標用戶更近的鄰居，從而具有更高的參考價值。鄰居的選擇主要有以下兩種方法：

(1)設(shè)置閾值進行選擇。該方法的主要思想是，為相似用戶的數(shù)據(jù)集設(shè)置一個最低相似性閾值α，一旦相似性小于該閾值，則不能作為目標用戶的鄰居，大于或等于該閾值則可以作為鄰居，從而參與后面的運算。該方法保證了符合要求的每個鄰居都有足夠的參考價值且都能參與運算，并且簡單易行、便于理解。但是，該方法的缺點在于，如果閾值設(shè)置過大，則覆蓋面過小，意味著只有很少的幾個用戶能夠作為鄰居；相反，如果閾值設(shè)置過小，則會有過多的用戶作為鄰居，很多無關(guān)用戶也會參與預測，計算結(jié)果同樣會受到影響。因此，閾值需要經(jīng)過多次實驗之后才能取得。

(2)最大鄰居數(shù)量選擇。該方法的思想是，在相似用戶的數(shù)據(jù)集中按照從大到小的順序，選擇一定數(shù)量的相似性最高的用戶作為鄰居。Zheng等人[4]認為，在利用Top-K思想選擇鄰居時，鄰居應(yīng)當滿足如下條件：

S(u)={a|Sim(a,u)≥

Simk,Sim(a,u)>0,a≠u}

(4)

其中，Simk表示用戶相似性數(shù)據(jù)集中按大小降序排列后的第k個值，Sim(a,u)>0保證選擇的鄰居都是正相關(guān)的。最大鄰居數(shù)量選擇是相似性選擇中使用最為廣泛的一種方法，因此本文也使用該方法進行相似用戶選擇。

3.1.3 預測值計算

在最后一步產(chǎn)生預測中，預測結(jié)果通常由兩部分構(gòu)成：一部分來自目標用戶自身，另外一部分來自目標用戶的鄰居[4]。本文采用以下方法產(chǎn)生預測值：

(5)

wa=Sim(a,u)/(∑b∈S(u)Sim(b,u))

(6)

本文提出一種基于“標準分數(shù)”(z-score)的方法進行預測值的計算：

/

∑a∈s(u)Sim(a,u)

(7)

其中，σu和σa分別表示用戶u和用戶a調(diào)用服務(wù)的失效概率的標準差。公式(7)和公式(5)相比，第一部分是相同的，都是目標用戶u曾經(jīng)調(diào)用過的所有服務(wù)的失效概率的算術(shù)平均值；第二部分結(jié)構(gòu)相同，都是考慮了用戶u的鄰居和用戶u的偏差，并且給不同的鄰居根據(jù)相似性的大小賦予了不同的權(quán)重。但是，在第二部分中，公式(7)利用用戶u和用戶a的調(diào)用服務(wù)失效概率的標準差對數(shù)據(jù)進行了標準化處理，起到了減小誤差的作用。

3.2 基于服務(wù)的協(xié)同過濾算法

從服務(wù)的角度出發(fā)，即在目標用戶調(diào)用過的其它服務(wù)中，存在著一些和目標服務(wù)相似的服務(wù)?；诜?wù)的協(xié)同過濾將從服務(wù)的角度出發(fā)，去尋找目標服務(wù)的鄰居，然后利用鄰居的數(shù)值來開展預測。

從算法的角度來說，基于服務(wù)的協(xié)同過濾和基于用戶的協(xié)同過濾一樣，同樣存在計算相似性、選擇鄰居、產(chǎn)生推薦三個步驟，并且在計算過程中其主要思想和基于用戶的協(xié)同過濾算法相同。但是，基于服務(wù)本身的特點，本文在“相似性計算”過程中使用了不同于基于用戶的協(xié)同過濾的計算方法。

3.2.1 相似性計算

服務(wù)和用戶最大的區(qū)別在于服務(wù)具有更明顯的屬性上的分類特征，因此它們更容易被區(qū)分：根據(jù)功能，Web服務(wù)有的提供地圖信息，有的提供搜索服務(wù)，有的提供支付功能等等；根據(jù)提供者，Web服務(wù)有的由知名的大公司提供，有的由個人開發(fā)者提供；根據(jù)收費，Web服務(wù)差異也很大；除此以外，Web服務(wù)自身還有很多的屬性。因此，在基于服務(wù)的協(xié)同過濾中，Web服務(wù)的屬性可以被用來計算兩者的相似性，而不是僅僅局限于通過矩陣內(nèi)數(shù)據(jù)進行計算。從Web服務(wù)自身的屬性(包括功能、服務(wù)提供者類型、是否收費等)出發(fā)去計算相似性，結(jié)果更符合現(xiàn)實的情況。比如目標服務(wù)i是微軟公司提供的地圖服務(wù)，服務(wù)j是Google公司提供的地圖服務(wù)，則兩者在Web服務(wù)提供者和Web服務(wù)功能兩點上都具有極高的相似性。如果僅僅根據(jù)用戶-服務(wù)矩陣中的數(shù)據(jù)計算，結(jié)果恰好得出服務(wù)i和服務(wù)j相似性不高而排除了服務(wù)j作為服務(wù)i的鄰居，是不符實際的。

表1給出一個服務(wù)屬性矩陣示例，其中S表示服務(wù)，I表示W(wǎng)eb服務(wù)自身屬性。矩陣中的“1”表示某項服務(wù)具有某種屬性，反之則用“0”表示。本文參考衡量兩個集合相似度的“杰卡德相似系數(shù)”，將兩種Web服務(wù)i和j之間的屬性相似性計算公式定義如下：

Sim1(i,j)=|Ii∩Ij|/|Ii∪Ij|

(8)

其中，|Ii∩Ij|表示W(wǎng)eb服務(wù)i和j共同的屬性個數(shù)，|Ii∪Ij|表示W(wǎng)eb服務(wù)i和j擁有的屬性個數(shù)之和，通過該公式可以計算出Web服務(wù)兩兩之間的屬性相似度。

Table 1 An example of service QoS matrix

除此以外，我們同樣可以借鑒“基于用戶的協(xié)同過濾算法”中對于用戶相似性的計算方法，即基于矩陣中的數(shù)值來計算兩個用戶之間的皮爾遜相關(guān)系數(shù)，來計算兩種Web服務(wù)之間的相關(guān)性。同樣地，兩種Web服務(wù)之間的相關(guān)性計算公式如下：

Sim2(i,j)=

(9)

在兩種相似性計算方法的基礎(chǔ)上，本文采用線性組合的形式將兩種方法的計算結(jié)果結(jié)合到一起：

Sim(i,j)=γSim1(i,j)+(1-γ)Sim2(i,j)

(10)

其中,γ是一個設(shè)定的參數(shù)，γ∈[0,1]。Sim1(i,j)是通過服務(wù)屬性計算的兩個服務(wù)的相似性，Sim2(i,j)是通過皮爾遜相關(guān)系數(shù)計算的兩個服務(wù)的相似性。然而，在傳統(tǒng)的線性組合方法中，參數(shù)γ的值多是人為定義的，這顯然會帶來一個問題：即參數(shù)γ的值受經(jīng)驗影響較大，很難直接取到最準確的值。為了避免該問題，本文將參數(shù)γ定義為：

(11)

則兩種Web服務(wù)相似性的最終計算方法為：

Sim(i,j)=γ1Sim1(i,j)+γ2Sim2(i,j)

(12)

由公式(12)不難看出，修正之后的相似性計算方法不僅使參數(shù)的取值避免了人為經(jīng)驗的影響，也使參數(shù)的取值有了相對意義。此外，當一個新的Web服務(wù)進入算法時，因為之前沒有用戶調(diào)用過該項服務(wù)，通過皮爾遜相關(guān)系數(shù)法計算出來的相似性是0，此時必須完全根據(jù)從服務(wù)自身屬性出發(fā)的方法計算相似性，避免了協(xié)同過濾中的“冷啟動(cold-start)”問題，同樣也更符合實際情況。

3.2.2 鄰居選擇

和“基于用戶的協(xié)同過濾算法”一樣，在計算出兩個Web服務(wù)的相似性之后，需要進行鄰居的選擇，為最后的預測計算做準備。同樣地，在這里我們選用“最大鄰居數(shù)量”的方法，即對相似服務(wù)根據(jù)相似性大小進行降序排列，選取前面的一定數(shù)量的服務(wù)作為鄰居參與運算[4]。

3.2.3 預測值計算

和“基于用戶的協(xié)同過濾算法”一樣，在最后一步進行預測值的計算時，同樣選用標準化處理。計算結(jié)果仍然由兩部分構(gòu)成，即目標Web服務(wù)自身以及目標Web服務(wù)鄰居的影響：

(13)

4 基于Slope One算法的預測方法

4.1 基本步驟

假設(shè)此時已經(jīng)構(gòu)建了一個m行n列的矩陣，其中，m表示用戶的數(shù)量，n表示服務(wù)的數(shù)量。矩陣中每個元素pa,i的值表示用戶a調(diào)用服務(wù)i的失效概率，在此算法中如果用戶沒有調(diào)用過服務(wù)，則其相應(yīng)值為0。

通過Slope One算法進行可靠性預測主要分成兩個步驟：計算目標服務(wù)i和其他服務(wù)j的失效概率偏差devi,j；預測目標用戶u調(diào)用目標服務(wù)i的失效概率pu,i。

第一步：計算偏差：

(14)

Ii∩Ij表示共同調(diào)用過服務(wù)i和服務(wù)j的用戶集合，count(Ii∩Ij)表示用戶的數(shù)量，uc表示該集合中的用戶，pc,i和pc,j分別表示集合uc中的用戶調(diào)用服務(wù)i和服務(wù)j的失效概率。

第二步：做出預測：

(15)

計算出目標服務(wù)和其他服務(wù)之間的偏差devi,j之后，如果目標用戶u曾經(jīng)調(diào)用過其中一項服務(wù)(即pu,j≠0)，則該項服務(wù)可被用來預測當前用戶u調(diào)用目標服務(wù)i的失效概率pu,i。

但是，結(jié)合實際情況，我們需要對公式(15)加以改進。如果有100個用戶同時調(diào)用過服務(wù)a和服務(wù)c，但僅僅只有10個用戶同時調(diào)用過服務(wù)b和服務(wù)c。假設(shè)此時要求得目標用戶調(diào)用服務(wù)c的失效概率，且目標用戶也恰好調(diào)用過服務(wù)a和服務(wù)b。那么參照上述方法，應(yīng)當分別求出服務(wù)a和服務(wù)c以及服務(wù)b和服務(wù)c的偏差，再進行計算。但是從實際的角度來說，同時調(diào)用過服務(wù)a和服務(wù)c的100個用戶要比同時調(diào)用過服務(wù)b和服務(wù)c的10個用戶具有更高的權(quán)重。因此，我們需要把該權(quán)重引入公式(15)，以體現(xiàn)共同用戶數(shù)量對于結(jié)果的影響：

pu,i=(∑(devi,j+pu,j)*wi,j)/∑wi,j

(16)

其中，wi,j=count(Ii∩Ij)。該公式的意義在于，如果有更多的用戶同時調(diào)用過目標服務(wù)和某項服務(wù)，那么在計算這項服務(wù)和目標服務(wù)的偏差時，該服務(wù)將具有更大的權(quán)重，這也更符合實際情況以及常識認知。

4.2 基于k-means聚類的Slope One算法

雖然Slope One算法在簡潔高效的同時，相比于傳統(tǒng)協(xié)同過濾算法也具有較高的準確性，但是Slope One算法最大的缺陷之一在于不進行相似性計算，因此忽略了用戶和用戶之間、服務(wù)和服務(wù)之間的相似性，導致了一些不相關(guān)的用戶和服務(wù)可能會對預測結(jié)果產(chǎn)生較大的影響。此外，Slope One算法在數(shù)據(jù)稠密時具有較高的推薦精度，但是當數(shù)據(jù)變得稀疏時，該算法性能將明顯下降。因此，本文對現(xiàn)有的Slope One算法進行改進，將聚類方法(k-means算法)引入Slope One算法中。改進后的Slope One算法將先對服務(wù)進行聚類分析，這一過程類似協(xié)同過濾算法中的相似性計算以及鄰居選擇的過程，其目的在于縮小參與運算的服務(wù)和用戶范圍，以提高計算結(jié)果準確性。

在該算法中，將先對服務(wù)進行聚類分析，目標服務(wù)所在簇中的其他服務(wù)作為鄰居參與運算。

算法1基于k-means的Slope One算法.

輸入：用戶-服務(wù)失效概率矩陣(m*n)，目標用戶u，目標服務(wù)i。

輸出：目標用戶u調(diào)用目標服務(wù)i的失效概率pu,i。

步驟1從樣本中隨機選擇k個中心作為初始分區(qū)，并求出總體平方誤差，同時確定最大迭代次數(shù)和收斂系數(shù)。

步驟2計算服務(wù)數(shù)據(jù)集中每一項服務(wù)和各個聚類中心的歐幾里德距離，同時進行比較，并把該項服務(wù)分配到和中心距離最小的聚類中。

步驟3再次重新計算每個聚類新的中心，以及總體平方誤差。

步驟4重復步驟2和步驟3，直到求出最優(yōu)解(即滿足以下條件之一：類的成員穩(wěn)定，樣本被分配給的類不再改變；達到定義的迭代次數(shù)；總體平方誤差達到收斂系數(shù)的要求)，否則需要回到步驟2重新計算。

步驟5聚類完成，得到包含k個類的聚類集合S。

步驟6找出目標服務(wù)i所屬的聚類集合Si。

步驟7找出用戶u調(diào)用過的所有服務(wù)，構(gòu)成集合M，并求M∩Si，記為集合O。

步驟8對于集合O中的每一項服務(wù)j，找出同時調(diào)用過該項服務(wù)j和目標服務(wù)i的用戶構(gòu)成集合U，并求出countU。

步驟9求解集合O中的每一項服務(wù)j對于目標服務(wù)i的偏差：

步驟10得出預測結(jié)果：

5 實驗與分析

5.1 實驗設(shè)置

本節(jié)通過模擬實驗對本文所提出的方法與傳統(tǒng)的協(xié)同過濾方法進行對比，以比較本文方法的有效性。實驗數(shù)據(jù)采用Movielens數(shù)據(jù)集[11]，以該數(shù)據(jù)集中的評分值(歸一化處理以后的值)來模擬Web服務(wù)的失效概率。本文隨機選取數(shù)據(jù)集中的部分數(shù)據(jù)開展實驗，即250個用戶和250個項目，其中非0元素為14 563個，0元素為47 937個，矩陣稠密度為23.3%。為了方便進行實驗，本文對空值數(shù)據(jù)進行了取0的預處理。數(shù)據(jù)集被分為訓練集(80%)和測試集(20%)兩部分。本文采用的實驗平臺是Intel(R)，CPU i-5 2.60 GHz，操作系統(tǒng)Windows7(64位)，采用Java語言(開發(fā)環(huán)境Java1.8.0，開發(fā)平臺Eclipse4.5.0)實現(xiàn)本文算法。本文所有源代碼均已發(fā)布在GitHub倉庫(http://github.com/arthur0804/codes)。

5.2 預測結(jié)果準確率評價標準

本文采用廣泛使用的平均絕對誤差MAE(Mean Absolute Error)作為預測結(jié)果的度量標準。計算公式如下：

MAE=(∑|value-prediction|)/m

(17)

其中，value是實際值，prediction是預測值，m是實際值和預測值的數(shù)量。MAE值越小，表示結(jié)果越準確，預測表現(xiàn)越好。

5.3 實驗結(jié)果

由于經(jīng)本文改進后的基于用戶的協(xié)同過濾算法中包含兩個未知變量：共同調(diào)用的服務(wù)數(shù)量閾值Ia∩Iu和懲罰因子β。假設(shè)兩個變量之間是獨立的，因此將先通過實驗1和實驗2，求得兩個變量的最佳取值，然后將變量代入改進后的算法和傳統(tǒng)的算法進行對比；再通過實驗3改變相似用戶數(shù)量，將改進后的算法和傳統(tǒng)算法進行對比。值得注意的是，由于本文改進后的基于服務(wù)的協(xié)同過濾算法中包含服務(wù)的屬性值，因此在本實驗中，我們選取數(shù)據(jù)集中物品的屬性共12個，它們分別是：Action、Adventure、Drama、Children、Documentary、Romance、Music、Science、Western、War、Thrill和Tragedy。本文將通過實驗5分析改進后的Slope One算法的預測精度。在實驗的過程中，我們對每一種算法重復執(zhí)行200次，觀察其MAE值。

實驗1取相似用戶數(shù)量為10，懲罰因子為1.5，共同調(diào)用服務(wù)的數(shù)量從10到70,每次遞增10，觀察不同情況下的MAE值。

從圖1可以看出，共同調(diào)用服務(wù)的數(shù)量取20左右的值時MAE最小，即計算結(jié)果最準確。

Figure 1 MAE values under different thresholds for common invoked services圖1 不同共同調(diào)用服務(wù)閾值下的MAE值

實驗2根據(jù)實驗1的結(jié)論取相似用戶數(shù)量為10，共同調(diào)用服務(wù)的閾值為20，從1到10,每次遞增1懲罰因子的值，觀察不同情況下的MAE值。

從圖2可以看出，懲罰因子取4左右的值時MAE最小，即計算結(jié)果最準確。綜上，基于兩個變量互相獨立的假設(shè)，本文提出的基于用戶的協(xié)同過濾在取共同調(diào)用服務(wù)閾值為20和懲罰因子為4時，針對本次實驗的數(shù)據(jù)集有最好的預測表現(xiàn)，因此將兩個變量分別取20和4開展實驗3。

Figure 2 MAE values under different penalty factor values圖2 不同懲罰因子下的MAE值

實驗3通過改變相似用戶的數(shù)量，即從10到50(步長為10)逐漸增加相似用戶的數(shù)量，觀察不同相似用戶數(shù)量下傳統(tǒng)的基于用戶的協(xié)同過濾算法UCF(User-based CF)和改進后的算法IUCF(Improved User-based CF)的MAE值。

從圖3可以看出，本文通過對傳統(tǒng)的基于用戶的協(xié)同過濾算法進行改進，顯著地降低了預測結(jié)果的MAE值，提高了預測精度。

Figure 3 MAE values under diffenent numbers of neighbors by UCF and IUCF圖3 不同鄰居數(shù)量下UCF和IUCF算法的MAE值

實驗4我們通過改變相似項目(Web服務(wù))的數(shù)量，即從10到50逐漸增加相似服務(wù)的數(shù)量(步長增量設(shè)為10)，觀察不同相似服務(wù)數(shù)量下傳統(tǒng)的基于物品的協(xié)同過濾算法ICF(Item-based CF)和經(jīng)過本文改進后的算法IICF(Improved Item-based CF)的MAE值。

從圖4可以看出，本文通過對傳統(tǒng)的基于服務(wù)的協(xié)同過濾算法進行改進，IICF方法顯著地降低了MAE值。

Figure 4 MAE values under diffenent numbers of neighbors by ICF and IICF圖4 不同鄰居數(shù)量下ICF和IICF算法的MAE值

實驗5本實驗分別采用傳統(tǒng)的Slope One算法和基于k-menans的Slope One算法開展Web服務(wù)可靠性預測，對比其MAE值，實驗結(jié)果如圖5所示。

Figure 5 MAE values of the two Slope One algorithms圖5 兩種Slope One算法的MAE值

從圖5可以看出，本文通過將k-means聚類算法加入到Slope One算法中，降低了MAE值，即提高了預測的精度和準確性。

6 結(jié)束語

本文提出了新的Web服務(wù)可靠性預測的模型和方法，并驗證了該方法的有效性。本文主要工作為：(1)對傳統(tǒng)的基于用戶的可靠性預測算法進行了改進，主要體現(xiàn)在相似性選擇和預測值計算的方法上；此外本文還提出了基于服務(wù)屬性的協(xié)同過濾算法，有效地解決了傳統(tǒng)算法中普遍存在的“冷啟動”問題。(2)將k-means聚類算法引入傳統(tǒng)的Slope One算法，并將其應(yīng)用于開展Web服務(wù)可靠性預測。最后，本文通過實驗驗證了改進后的算法的有效性。

值得注意的是，本文僅僅從單個用戶和服務(wù)角度出發(fā)，預測的是某個用戶調(diào)用一項服務(wù)的可靠性，實際上某個用戶可能調(diào)用多項服務(wù)，此時就需要預測組合服務(wù)的可靠性。針對一個組合服務(wù)而言，其組件之間可能存在著可靠性的依賴關(guān)系。在未來的工作中，我們需要對具有復雜的調(diào)用關(guān)系的組合系統(tǒng)的可靠性預測問題開展系統(tǒng)深入的研究。