基于協(xié)同過濾和Slope One算法的Web服務(wù)可靠性預(yù)測

王 磊，瞿佳明

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

1 引言

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

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

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

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

2 預(yù)備知識(shí)

2.1 Web服務(wù)可靠性

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

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

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

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

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

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

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

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

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

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

3.1.1 相似性計(jì)算

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

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

(1)

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

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

Sim(a,u)=

(2)

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

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

(3)

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

3.1.2 鄰居選擇

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

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

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

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

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

(4)

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

3.1.3 預(yù)測值計(jì)算

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

(5)

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

(6)

本文提出一種基于“標(biāo)準(zhǔn)分?jǐn)?shù)”(z-score)的方法進(jìn)行預(yù)測值的計(jì)算：

/

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

(7)

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

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

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

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

3.2.1 相似性計(jì)算

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

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

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

(8)

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

Table 1 An example of service QoS matrix

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

Sim2(i,j)=

(9)

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

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

(10)

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

(11)

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

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

(12)

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

3.2.2 鄰居選擇

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

3.2.3 預(yù)測值計(jì)算

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

(13)

4 基于Slope One算法的預(yù)測方法

4.1 基本步驟

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

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

第一步：計(jì)算偏差：

(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的失效概率。

第二步：做出預(yù)測：

(15)

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

但是，結(jié)合實(shí)際情況，我們需要對公式(15)加以改進(jìn)。如果有100個(gè)用戶同時(shí)調(diào)用過服務(wù)a和服務(wù)c，但僅僅只有10個(gè)用戶同時(shí)調(diào)用過服務(wù)b和服務(wù)c。假設(shè)此時(shí)要求得目標(biāo)用戶調(diào)用服務(wù)c的失效概率，且目標(biāo)用戶也恰好調(diào)用過服務(wù)a和服務(wù)b。那么參照上述方法，應(yīng)當(dāng)分別求出服務(wù)a和服務(wù)c以及服務(wù)b和服務(wù)c的偏差，再進(jìn)行計(jì)算。但是從實(shí)際的角度來說，同時(shí)調(diào)用過服務(wù)a和服務(wù)c的100個(gè)用戶要比同時(shí)調(diào)用過服務(wù)b和服務(wù)c的10個(gè)用戶具有更高的權(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)。該公式的意義在于，如果有更多的用戶同時(shí)調(diào)用過目標(biāo)服務(wù)和某項(xiàng)服務(wù)，那么在計(jì)算這項(xiàng)服務(wù)和目標(biāo)服務(wù)的偏差時(shí)，該服務(wù)將具有更大的權(quán)重，這也更符合實(shí)際情況以及常識(shí)認(rèn)知。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)設(shè)置

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

5.2 預(yù)測結(jié)果準(zhǔn)確率評(píng)價(jià)標(biāo)準(zhǔn)

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

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

(17)

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

5.3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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