主題和時(shí)間特征融合下的服務(wù)消亡預(yù)測(cè)

陳曙輝，范玉順

(清華大學(xué) 自動(dòng)化系，北京 100084)

0 引言

近年來(lái)，隨著信息技術(shù)的飛速發(fā)展，電子商務(wù)[1]進(jìn)入一個(gè)迅猛發(fā)展的階段。商業(yè)服務(wù)和信息支撐技術(shù)不斷融合，軟件即服務(wù)(Software as a Service, SaaS)[2]和面向服務(wù)的體系結(jié)構(gòu)(Service-Oriented Architecture, SOA)[3]的普及，使得商業(yè)服務(wù)系統(tǒng)的開(kāi)發(fā)不再是個(gè)難題。以某一訂餐平臺(tái)為例，訂餐平臺(tái)的開(kāi)發(fā)者無(wú)需再去重復(fù)開(kāi)發(fā)地圖顯示和定位功能、餐館名稱(chēng)和菜品管理、天氣信息獲取、送餐員管理等功能模塊，而是通過(guò)調(diào)用互聯(lián)網(wǎng)上的各類(lèi)Web服務(wù)，將其組合在一起，就能輕松快捷地完成訂餐平臺(tái)所需要的各種功能。在這種環(huán)境的驅(qū)動(dòng)下，互聯(lián)網(wǎng)上Web服務(wù)的種類(lèi)和數(shù)量與日俱增。

在一個(gè)服務(wù)系統(tǒng)中，單一的服務(wù)個(gè)體(service)由于功能性單一，很難滿足用戶復(fù)雜多變的需求，更多的情況是將多個(gè)服務(wù)集成為一個(gè)服務(wù)組合(service composition)，以服務(wù)組合的形式為用戶提供服務(wù)[4]。服務(wù)組合的產(chǎn)生與使用為用戶提供了更為便利的使用方式，但也帶來(lái)一些新的問(wèn)題。Web服務(wù)的數(shù)量與日俱增，如Web服務(wù)生態(tài)系統(tǒng)[5]描述的那樣，相似功能的Web服務(wù)之間相互競(jìng)爭(zhēng)，失利的Web服務(wù)會(huì)走向消亡。在上述應(yīng)用場(chǎng)景下，消亡的Web服務(wù)會(huì)對(duì)使用它的服務(wù)組合帶來(lái)巨大損失和影響。例如上例中，構(gòu)成訂餐平臺(tái)的地圖顯示和定位、餐館管理和菜品管理、天氣信息服務(wù)中，無(wú)論哪一個(gè)出現(xiàn)問(wèn)題，都會(huì)使訂餐平臺(tái)出現(xiàn)系統(tǒng)崩潰。再以ProgrammableWeb[www.programmableWeb.com]為例，截止到2016年8月，ProgrammableWeb提供了15 368個(gè)應(yīng)用程序編程接口(,Application Programing Interface， API)和7 822個(gè)Mashup。其中：API可以為用戶提供較為單一的功能，可視為單個(gè)服務(wù)；Mashup則綜合了多個(gè)API，能夠滿足用戶較為復(fù)雜的需求，可視為服務(wù)組合。統(tǒng)計(jì)表明，平臺(tái)中282個(gè)API失效導(dǎo)致1 527個(gè)Mashup失效，給Mashup的開(kāi)發(fā)者造成了極大的損失。因此，服務(wù)組合開(kāi)發(fā)者在選擇服務(wù)時(shí)，必須考慮服務(wù)的可靠性，避免因單個(gè)服務(wù)個(gè)體失效造成整體崩潰，從根基上提高服務(wù)組合的持久可用性。

在研究Web服務(wù)可靠性的相關(guān)問(wèn)題中，Web服務(wù)失效問(wèn)題[6-9]的研究熱度更高。Web服務(wù)失效與本文研究的Web服務(wù)消亡問(wèn)題存在一定的相似性，二者都是研究因Web服務(wù)不能正常工作而對(duì)整個(gè)服務(wù)系統(tǒng)造成的影響。前者Web服務(wù)本身并沒(méi)有問(wèn)題，通常是由于網(wǎng)絡(luò)環(huán)境或者網(wǎng)絡(luò)節(jié)點(diǎn)等原因?qū)е路?wù)失效。在這類(lèi)Web服務(wù)失效中，隨著網(wǎng)絡(luò)環(huán)境的改善、受損網(wǎng)絡(luò)節(jié)點(diǎn)的修復(fù)或網(wǎng)絡(luò)節(jié)點(diǎn)的調(diào)整，很快又可以恢復(fù)使用，從長(zhǎng)遠(yuǎn)角度來(lái)說(shuō)并不對(duì)服務(wù)組合和整個(gè)服務(wù)系統(tǒng)造成太大影響。Web服務(wù)消亡是Web服務(wù)在當(dāng)前服務(wù)系統(tǒng)中永久失效。因?yàn)閃eb服務(wù)本身退出服務(wù)系統(tǒng)不再繼續(xù)提供服務(wù)，所以無(wú)法通過(guò)調(diào)整網(wǎng)絡(luò)等手段恢復(fù)，必然導(dǎo)致相關(guān)的服務(wù)組合徹底崩潰，如果大量的服務(wù)組合出現(xiàn)問(wèn)題則會(huì)威脅到整個(gè)服務(wù)系統(tǒng)的穩(wěn)定。

Web服務(wù)消亡最直觀的原因是因Web服務(wù)在同類(lèi)服務(wù)激烈的競(jìng)爭(zhēng)中處于劣勢(shì)，Web服務(wù)的開(kāi)發(fā)者從戰(zhàn)略的角度停止了對(duì)Web服務(wù)的繼續(xù)支持。在相關(guān)研究中，夏博飛等[10]使用服務(wù)標(biāo)簽標(biāo)注同類(lèi)服務(wù)，利用加權(quán)服務(wù)網(wǎng)絡(luò)分析法分析競(jìng)爭(zhēng)失利的Web服務(wù)，從而為服務(wù)組合開(kāi)發(fā)者提供有效的參考。這類(lèi)方法存在的問(wèn)題是標(biāo)簽的準(zhǔn)確性問(wèn)題，大多數(shù)服務(wù)系統(tǒng)中的標(biāo)簽由開(kāi)發(fā)者填寫(xiě)，出于競(jìng)爭(zhēng)和宣傳的原因可能不會(huì)如實(shí)填寫(xiě)，影響了分類(lèi)的準(zhǔn)確性；另外，標(biāo)簽為手工標(biāo)注，存在標(biāo)簽種類(lèi)太多、標(biāo)簽格式不統(tǒng)一、維護(hù)困難等問(wèn)題。Web服務(wù)消亡另外一個(gè)容易理解的動(dòng)機(jī)是，實(shí)力欠缺的供應(yīng)商在Web服務(wù)處于競(jìng)爭(zhēng)劣勢(shì)時(shí)更容易放棄堅(jiān)持，相反實(shí)力強(qiáng)勁的供應(yīng)商則因?yàn)槠放坪托抛u(yù)等原因堅(jiān)持得更長(zhǎng)久。Xia等[11]引入Web服務(wù)供應(yīng)商的信息，并依此建立了服務(wù)特征融合建模(,Service Comprehensive Feature Modeling, SCFM)算法，得到了很好的預(yù)測(cè)效果，但是供應(yīng)商信息等個(gè)性化數(shù)據(jù)受限于服務(wù)系統(tǒng)，甚至受限于當(dāng)前服務(wù)系統(tǒng)的版本更新。

近年來(lái)，隨著機(jī)器學(xué)習(xí)的興起，用機(jī)器學(xué)習(xí)方法提取文本特征的方法[12-17]得到了廣泛應(yīng)用，從Web服務(wù)的描述、用戶的反饋文本中提取Web服務(wù)的主題特征成為可能。而在這些主題中，隨著社會(huì)流行趨勢(shì)的變化，有一些主題隨著時(shí)間的發(fā)展必然整體走向沒(méi)落，以這些主題特征為主要功能點(diǎn)開(kāi)發(fā)的Web服務(wù)退出服務(wù)系統(tǒng)的原理機(jī)制其實(shí)與Web服務(wù)之間的競(jìng)爭(zhēng)因素并不相同。另外，從實(shí)驗(yàn)數(shù)據(jù)中可以觀察到，一個(gè)新的服務(wù)，如果在產(chǎn)生的若干時(shí)間段內(nèi)未能及時(shí)得到調(diào)用和認(rèn)可，就很容易淹沒(méi)在新生的Web服務(wù)大潮中，從而使被調(diào)用的幾率大大降低，實(shí)驗(yàn)表明長(zhǎng)時(shí)間未被調(diào)用的服務(wù)出現(xiàn)服務(wù)消亡的幾率大為增加。本文從主題消亡的角度，結(jié)合時(shí)間敏感的因素，對(duì)Web服務(wù)消亡進(jìn)行了預(yù)測(cè)。在ProgrammableWeb數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證表明，該方法能有效地從服務(wù)系統(tǒng)中篩選出消亡的服務(wù)，從而為服務(wù)的使用者提供有效的參考。

1 問(wèn)題提出

本文工作是在服務(wù)系統(tǒng)環(huán)境下進(jìn)行服務(wù)失效研究。對(duì)服務(wù)系統(tǒng)的描述如圖1所示，一個(gè)服務(wù)系統(tǒng)包括服務(wù)和服務(wù)組合兩種類(lèi)型，服務(wù)提供商開(kāi)發(fā)單一功能的服務(wù)，服務(wù)組合開(kāi)發(fā)者則利用這些服務(wù)組合出功能豐富多彩的服務(wù)組合，用戶更傾向于使用滿足復(fù)雜需求的服務(wù)組合而非功能單一的服務(wù)個(gè)體。從這個(gè)角度給出研究環(huán)境和研究問(wèn)題的定義如下：

定義2服務(wù)消亡預(yù)測(cè)。在服務(wù)系統(tǒng)G中，定義服務(wù)消亡向量P=[p1,p2,…,pj]，其中pj∈[0,1]為第j個(gè)服務(wù)出現(xiàn)服務(wù)消亡的概率值。pj值越大，其服務(wù)退出的可能性越大。

通過(guò)上述定義將較為抽象的服務(wù)消亡現(xiàn)象轉(zhuǎn)化為以概率值度量出現(xiàn)服務(wù)消亡可能性的研究方法，在進(jìn)行特征分析、建立模型并解決問(wèn)題前，首先介紹使用到的一些數(shù)學(xué)模型。

1.1 泊松分解

在用于推薦的機(jī)器學(xué)習(xí)算法中，使用文本主題特征提取的有很多，常見(jiàn)的有隱狄利克雷分布—主題模型(Latent Dirichlet Allocation, LDA)[12-13]、泊松分解[14-15]和深度學(xué)習(xí)[16-17]等。LDA通過(guò)模擬人們的寫(xiě)作過(guò)程，從語(yǔ)料庫(kù)中挑選詞匯構(gòu)成文本來(lái)訓(xùn)練模型，但是LDA認(rèn)為文本中的詞匯是從詞袋中隨機(jī)挑選而得，忽視了一篇文章中詞匯間存在的內(nèi)在關(guān)系，并不完全符合實(shí)際情況；深度學(xué)習(xí)通過(guò)構(gòu)建多層神經(jīng)網(wǎng)絡(luò)，抽象出較為準(zhǔn)確的主題特征，然而深度學(xué)習(xí)在學(xué)習(xí)代價(jià)上，特別是學(xué)習(xí)矩陣維數(shù)較大、中間層設(shè)置較多的情況下，需要較大的計(jì)算量;泊松分解認(rèn)為文檔的詞匯使用情況滿足某一特定參數(shù)下的泊松分布模型，通過(guò)EM算法不斷調(diào)整參數(shù)，使預(yù)設(shè)模型逐漸逼近文檔的真實(shí)模型，其缺點(diǎn)是對(duì)模型參數(shù)要求較高，但對(duì)于稀疏矩陣，通過(guò)使用獨(dú)特的訓(xùn)練方法，可以大大降低模型的訓(xùn)練成本。與前兩種算法相比泊松分解有極大的優(yōu)勢(shì)，而服務(wù)系統(tǒng)中的服務(wù)主題特征提取恰好滿足這種情況。

泊松分解在2013年由Prem Gopalan提出[14]，作為機(jī)器學(xué)習(xí)中比較新的研究成果，泊松分解屬于產(chǎn)生式概率模型，如圖2所示。泊松分解本質(zhì)上仍然是一種非負(fù)的矩陣分解算法，與傳統(tǒng)的非負(fù)矩陣分解(Nonnegative Matrix Factorization, NMF)[18]不同的是，對(duì)于一個(gè)滿足泊松分布的系數(shù)矩陣，泊松分解在非負(fù)矩陣分解的基礎(chǔ)上，通過(guò)調(diào)整系數(shù)使分解后得到的兩個(gè)矩陣都滿足Gamma分布，即

ηu～Gamma(λua,λub);

θi～Gamma(λia,λib);

(1)

式中(λ·a,λ·b)表示Gamma分布的形狀參數(shù)和尺度參數(shù)。

ηu,k～Gamma(λua,k,λub,k);

θi,k～Gamma(λia,k,λib,k);

(2)

式(2)的聯(lián)合概率公式可以表示為

(3)

使用變分推斷的前提假設(shè)是各個(gè)Gamma分布之間相互獨(dú)立。對(duì)于式(3)中的每個(gè)ηu,k(?k∈K)，從中抽取與其相關(guān)的部分，得到

p(ηu,k|yui,k,λua,k,λub,k)

(4)

由此得到迭代公式

(5)

=exp(Eq[log(ηu,kθi,k)])∝log(ηu,k)+log(θi,k)。

(6)

式中Eq(·)表示在分布q下的期望。因?yàn)閘og(ηu,k)=Ψ(λua,k)-log(λub,k)，所以φui,k的迭代公式為

φui,k←exp{Ψ(λua,k)-log(λub,k)+Ψ(λia,k)-

log(λib,k)}。

(7)

(8)

可以看出，當(dāng)yui=0時(shí)無(wú)需計(jì)算φui,k，對(duì)于稀疏矩陣而言，泊松分解的這個(gè)特性可以節(jié)省很大一部分計(jì)算量?，F(xiàn)實(shí)生活的大多數(shù)服務(wù)系統(tǒng)在海量的Web服務(wù)隊(duì)列中，其服務(wù)組合調(diào)用的往往只有其中少數(shù)幾個(gè)，因此對(duì)于服務(wù)系統(tǒng)的特征提取，使用泊松分解構(gòu)建模型是非常適宜的一種方法。

1.2 極限學(xué)習(xí)機(jī)ELM

預(yù)測(cè)服務(wù)消亡與否在本質(zhì)上屬于分類(lèi)問(wèn)題，目前常見(jiàn)的可用于分類(lèi)的算法有Logistic回歸、支持向量機(jī)(Support Vector Machine, SVM)、極限學(xué)習(xí)機(jī)(Extreme Learning Machine, ELM)。依據(jù)摩爾—彭羅斯廣義逆理論提出的ELM[19]算法，在保證較優(yōu)的訓(xùn)練結(jié)果的前提下，具有更快的訓(xùn)練速度。

ELM在結(jié)構(gòu)上是一種單隱層神經(jīng)網(wǎng)絡(luò)，通過(guò)一步計(jì)算就可以求出網(wǎng)絡(luò)的輸出權(quán)值，其模型結(jié)構(gòu)如圖3所示。對(duì)于一個(gè)有N個(gè)樣本點(diǎn)的數(shù)據(jù)集(Xi,Ti),i=1,…,N，其中Xi=[xi1,xi2,…,xin]T∈Rn，Ti=[ti1,ti2,…,tim]T∈Rm。設(shè)置一個(gè)有L個(gè)隱層節(jié)點(diǎn)的單隱層神經(jīng)網(wǎng)絡(luò)，公式為

(9)

式中：g(x)為激活函數(shù)，對(duì)于第j個(gè)隱層節(jié)點(diǎn)，Wj=[w1j,w2j,…,wnj]T為輸入權(quán)重，βj=[βj1,βj2,…,βjm]T為輸出權(quán)重，bj為偏置量。

ELM的訓(xùn)練目標(biāo)是使輸入Xi通過(guò)網(wǎng)絡(luò)訓(xùn)練后與輸出Ti之間的誤差最小,即

(10)

將式(9)代入后得到

(11)

H(W1,…,WL,b1,…bL,X1,…,XN)=

則

(12)

2 特征分析

2.1 主題特征分析

采用機(jī)器學(xué)習(xí)算法從服務(wù)系統(tǒng)中提取主題特征的方法通常用于尋找服務(wù)系統(tǒng)中使用頻繁或者熱門(mén)的Web服務(wù)和服務(wù)主題，以便對(duì)服務(wù)系統(tǒng)中的熱門(mén)服務(wù)進(jìn)行分類(lèi)、聚類(lèi)、推薦等。服務(wù)消亡需要搜尋服務(wù)系統(tǒng)中容易退出系統(tǒng)的服務(wù)，這類(lèi)服務(wù)通常是不常使用或者冷門(mén)的，傳統(tǒng)算法模型并不適用。本文的主題分析側(cè)重于通過(guò)服務(wù)系統(tǒng)的主題特征分析，尋找其對(duì)服務(wù)消亡的潛在因素和影響，從而提高服務(wù)系統(tǒng)的整體穩(wěn)定性。

主題特征分析的定性分析以ProgrammableWeb為背景，本文使用LDA提取了2005～2016年間的所有Web服務(wù)在不同主題下的分布情況，其中主題數(shù)目設(shè)置為50，圖4所示為所提取的Web服務(wù)主題分布排序后的結(jié)果。分析認(rèn)為，雖然當(dāng)前時(shí)期下的Web服務(wù)主題有冷熱之分，但從長(zhǎng)遠(yuǎn)角度看，Web服務(wù)的一個(gè)主題總是經(jīng)歷從產(chǎn)生、熱門(mén)到最終冷卻沒(méi)落的過(guò)程。圖4統(tǒng)計(jì)的結(jié)果表明，在主題更替過(guò)程中圍繞這個(gè)主題而產(chǎn)生的Web服務(wù)總數(shù)相差不多，占比大致在2%上下浮動(dòng)。另外一方面，以已經(jīng)或者正在走向沒(méi)落的主題為中心開(kāi)發(fā)的Web服務(wù)必然會(huì)更多地退出服務(wù)系統(tǒng)。循此思路，本文統(tǒng)計(jì)在不同主題中已經(jīng)退出系統(tǒng)的Web服務(wù)占所有Web服務(wù)的比例，將結(jié)果從高到低排序，如圖5所示。由圖可以看出，數(shù)據(jù)呈現(xiàn)明顯的規(guī)律性特征，某些主題內(nèi)的Web服務(wù)較多產(chǎn)生了消亡現(xiàn)象。服務(wù)系統(tǒng)內(nèi)的Web服務(wù)會(huì)因?yàn)橹黝}分布的不同而呈現(xiàn)不同的服務(wù)消亡趨勢(shì)，從這個(gè)角度出發(fā)，本文將服務(wù)主題分布數(shù)據(jù)引入服務(wù)消亡預(yù)測(cè)。

2.2 時(shí)間特征分析

在研究服務(wù)組合失效問(wèn)題時(shí)，一個(gè)比較容易推斷出的結(jié)論是，那些不能得到用戶認(rèn)可的Web服務(wù)通常會(huì)最先退出服務(wù)系統(tǒng)，時(shí)間因素是檢驗(yàn)Web服務(wù)是否活躍的一個(gè)重要判別特征。本文通過(guò)服務(wù)從創(chuàng)建到第一次被調(diào)用的時(shí)間間隔來(lái)研究時(shí)間因素對(duì)服務(wù)退出的影響。

在服務(wù)數(shù)量和種類(lèi)都飛速增長(zhǎng)的今天，如果某一服務(wù)在發(fā)布后的若干時(shí)間段未能得到調(diào)用，則很容易淹沒(méi)在海量的服務(wù)中，其被調(diào)用的可能性大大降低。以ProgrammableWeb數(shù)據(jù)為例，本文抓取應(yīng)用程序接口(Application Programming Interface，API)的創(chuàng)建時(shí)間和Mashup的發(fā)布時(shí)間，以月為單位計(jì)算API的首次調(diào)用時(shí)間和創(chuàng)建時(shí)間的差值。圖6中柱狀圖為統(tǒng)計(jì)結(jié)果，曲線為擬合曲線，曲線方程為y=max(A)×e-i/10，其中A為統(tǒng)計(jì)結(jié)果向量，i為月份。從圖中可見(jiàn)，從發(fā)布后至下個(gè)月開(kāi)始前獲得調(diào)用的API有144個(gè)，在創(chuàng)建18個(gè)月內(nèi)得到首次調(diào)用的服務(wù)數(shù)目占所有被調(diào)用服務(wù)數(shù)目的50%，隨著時(shí)間的增長(zhǎng)，服務(wù)被調(diào)用的可能性降低。

服務(wù)在得到調(diào)用后，會(huì)得到一種類(lèi)似“再激活”的屬性，即重新進(jìn)入服務(wù)組合開(kāi)發(fā)者的視野，從而大大增加再次被調(diào)用的幾率。從另一個(gè)角度觀察ProgrammableWeb的數(shù)據(jù)，統(tǒng)計(jì)服務(wù)被調(diào)用的總次數(shù)。圖7所示為統(tǒng)計(jì)被調(diào)用最多的前200個(gè)服務(wù)調(diào)用次數(shù)，與圖6相比，服務(wù)被調(diào)用次數(shù)迅速下降。分析表明，服務(wù)調(diào)用次數(shù)與服務(wù)創(chuàng)建—首次調(diào)用時(shí)間差呈現(xiàn)大致的對(duì)應(yīng)關(guān)系，可能由于從眾心理，人們更容易相信已經(jīng)被別人認(rèn)可的服務(wù)，體現(xiàn)在數(shù)據(jù)上就是越是經(jīng)常被使用的服務(wù)，被調(diào)用的次數(shù)越多。相對(duì)而言，對(duì)于一個(gè)服務(wù)，“創(chuàng)建—首次調(diào)用”時(shí)間指標(biāo)越大，被調(diào)用的總次數(shù)越少。

3 模型建立

算法模型主要使用主題特征和時(shí)間特征預(yù)測(cè)Web服務(wù)消亡，模型的流程圖如圖8所示。流程分為線下和線上兩部分：線下部分為圖8的左半部分，對(duì)于目標(biāo)服務(wù)系統(tǒng)，算法使用泊松分解從Web服務(wù)的自然語(yǔ)言描述信息中提煉Web服務(wù)的主題分布特征和時(shí)間特征并將其融合，然后使用機(jī)器學(xué)習(xí)算法計(jì)算出服務(wù)消亡的概率模型提供給線上部分調(diào)用；當(dāng)用戶輸入希望調(diào)用的某個(gè)Web服務(wù)或者某類(lèi)型的Web服務(wù)進(jìn)行查詢時(shí)，線上部分通過(guò)在線算法則提供對(duì)應(yīng)的Web服務(wù)消亡的概率值作為建議。

算法流程中的幾個(gè)關(guān)鍵步驟分別為主題特征提取、時(shí)間信息處理、綜合兩類(lèi)特征算出概率模型和在線算法部分。下文對(duì)這幾個(gè)步驟分別進(jìn)行說(shuō)明。

3.1 特征提取

3.1.1 主題特征提取

Web服務(wù)的主題特征采用泊松分解算法從Web服務(wù)描述文本中提取，在正式處理前需要將服務(wù)系統(tǒng)內(nèi)的所有Web服務(wù)描述文本進(jìn)行預(yù)處理，包括去除分類(lèi)無(wú)關(guān)用詞、詞性轉(zhuǎn)換等工作，最終將其轉(zhuǎn)化為“服務(wù)—詞”矩陣，具體過(guò)程不再贅述。

設(shè)獲得的“服務(wù)—詞”矩陣為Y，使用泊松分解求解服務(wù)的主題分布，即

ηs～Gamma(λua,λub);

θw～Gamma(λia,λib);

(13)

后續(xù)的求解步驟如1.1節(jié)，最終獲取的參數(shù)迭代公式如表1所示。

表1 泊松分解迭代公式

依據(jù)參數(shù)迭代公式，設(shè)計(jì)主題特征提取的算法流程如下：

算法1Web服務(wù)主題特征提取算法。

輸入：“Web服務(wù)—詞”使用關(guān)系矩陣Msw、主題數(shù)目K、Web服務(wù)的Gamma分布參數(shù)(λsa,λsb)、詞的Gamma分布參數(shù)(λwa,λwb)。

輸出：Web服務(wù)的主題特征分布μs。

算法：

1.for(k=1:K){

2. 由(λsa,λsb)計(jì)算出μs,k初值；

3. 由(λwa,λwb)計(jì)算出βw,k初值；}

4.repeat{

5. 對(duì)于矩陣Msw中每一個(gè)元素msw>0，根據(jù)表1中公式，更新φsw,k；

6. for(k=1:K){msw,k=mswφsw,k}；

7. 由表1中公式，更新μs,k和βw,k；

8.}until(convergence)

因?yàn)椴此煞纸馐欠秦?fù)分解，所以很容易推斷出當(dāng)msw=0時(shí)φsw,k=0，因此在算法步驟5和6中可以忽略矩陣Msw中非零元素的各項(xiàng)計(jì)算，當(dāng)矩陣Msw為稀疏矩陣時(shí)可以節(jié)約大量計(jì)算時(shí)間，這也是泊松分解在計(jì)算速度上相對(duì)于其他機(jī)器學(xué)習(xí)算法的優(yōu)勢(shì)所在。

3.1.2 時(shí)間特征提取

Web服務(wù)的“創(chuàng)建—初次使用”與Web服務(wù)的活躍程度呈現(xiàn)一種負(fù)指數(shù)的對(duì)應(yīng)關(guān)系，對(duì)于服務(wù)消亡而言，無(wú)論創(chuàng)建—首次調(diào)用特征還是調(diào)用次數(shù)特征，消亡的服務(wù)都位于數(shù)據(jù)的長(zhǎng)尾部分，而服務(wù)系統(tǒng)中數(shù)據(jù)量龐大的長(zhǎng)尾部分使得消亡服務(wù)的特征并不十分明顯，因此對(duì)時(shí)間因素作對(duì)應(yīng)的線性化處理，突出其時(shí)間因素與服務(wù)退出的對(duì)應(yīng)關(guān)系，以提高服務(wù)消亡預(yù)測(cè)的準(zhǔn)確度?；谏鲜鲈?，在實(shí)驗(yàn)中將采集到的時(shí)間特征做如下處理：

tr=log(t1-t0)。

(14)

式中：t1為服務(wù)得到首次調(diào)用的時(shí)間，t0為服務(wù)的創(chuàng)建時(shí)間。再將處理過(guò)的tr作歸一化處理：

(15)

3.2 服務(wù)消亡概率模型

在進(jìn)行線下部分訓(xùn)練前，通過(guò)3.1節(jié)和3.2節(jié)已經(jīng)得到集合{μs,ts}，其中μs為服務(wù)的主題特征，ts為服務(wù)的時(shí)間特征。訓(xùn)練時(shí)設(shè)置

τs=[λ1μsλ2ts]。

(16)

式中λ=[λ1λ2]為系數(shù)。因?yàn)镋LM算法需要求矩陣廣義逆運(yùn)算，設(shè)置系統(tǒng)λ的目的是使合并后的矩陣元素在數(shù)量級(jí)上保持基本一致，以避免不必要的計(jì)算誤差。在此使用rs標(biāo)志采集到的服務(wù)退出信息，其中rs=1表示服務(wù)退出服務(wù)系統(tǒng)，rs=0表示服務(wù)仍在提供服務(wù)。

使用ELM算法訓(xùn)練模型，模型的輸入為ts，輸出為rs，訓(xùn)練目標(biāo)為

(17)

訓(xùn)練過(guò)程如1.2節(jié)所示。利用{τs,rs}訓(xùn)練出ELM模型的隱層參數(shù)，至此完成模型的線下訓(xùn)練。

3.3 在線算法

對(duì)于線上部分，當(dāng)一個(gè)新的服務(wù)sk被用戶輸入模型時(shí)，利用特征提取訓(xùn)練完成的參數(shù)，容易算出新服務(wù)對(duì)應(yīng)的{μsk,tsk}并生成出對(duì)應(yīng)的τsk，通過(guò)τsk和訓(xùn)練好的服務(wù)退出概率模型，最終計(jì)算出rsk。rsk為一個(gè)[0,1]間的概率值，用來(lái)表示該服務(wù)退出服務(wù)系統(tǒng)的可能性，其提供給用戶作為是否使用該服務(wù)的參考建議，值越大，該服務(wù)越有可能出現(xiàn)消亡現(xiàn)象。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)

ProgrammableWeb網(wǎng)站提供API(Web服務(wù))和Mashup(服務(wù)組合)兩種在線服務(wù)功能，其中API僅提供單一功能的服務(wù)，例如Google Maps提供地圖服務(wù)，Zillow提供在線房屋估值、掛售功能。Mashup則通過(guò)調(diào)用一個(gè)多個(gè)API，提供功能眾多、能滿足用戶復(fù)雜需求的服務(wù)。例如BetterHome通過(guò)調(diào)用Zillow, Walk Score, Google Maps等多個(gè)API，根據(jù)用戶的各種喜好(如環(huán)境、位置等信息)為用戶提供個(gè)性化房屋購(gòu)買(mǎi)、租賃建議；Globebop則通過(guò)調(diào)用Google Maps, Wikipedia等API，為用戶提供旅游地點(diǎn)路線、景點(diǎn)介紹、推薦等服務(wù)。

截止2017年5月10日，ProgrammableWeb網(wǎng)站提供了17 455個(gè)API和7 877個(gè)Mashup(包括已退出的API和Mashup)。實(shí)驗(yàn)中抓取了網(wǎng)站2005～2016年間的所有API數(shù)據(jù)，放棄了從2016年12月底至今時(shí)長(zhǎng)約半年的API數(shù)據(jù)，原因是這部分API屬于新生服務(wù)，其退出服務(wù)系統(tǒng)的可能性幾乎為0，實(shí)際觀測(cè)也是如此。在實(shí)驗(yàn)數(shù)據(jù)中加入這部分?jǐn)?shù)據(jù)無(wú)疑會(huì)增加算法結(jié)果的準(zhǔn)確度(全為負(fù)樣本)，但對(duì)算法性能測(cè)試并無(wú)實(shí)際意義。

使用數(shù)據(jù)前通過(guò)服務(wù)組合的使用情況對(duì)Web服務(wù)進(jìn)行了一次過(guò)濾，剔除了從未被調(diào)用過(guò)的API。這樣的數(shù)據(jù)處理出發(fā)點(diǎn)是，被調(diào)用的Web服務(wù)退出系統(tǒng)會(huì)對(duì)整個(gè)服務(wù)系統(tǒng)的穩(wěn)定性造成更大危害，如果算法能針對(duì)這些Web服務(wù)給出可靠的消亡預(yù)測(cè)，則將更具實(shí)際應(yīng)用價(jià)值。通過(guò)上述處理后實(shí)驗(yàn)數(shù)據(jù)集如表2所示。

表2 處理后的ProgrammableWeb.com數(shù)據(jù)

4.2 評(píng)價(jià)指標(biāo)

對(duì)于一個(gè)給定的區(qū)分閾值，如果計(jì)算得到的服務(wù)消亡概率值大于這個(gè)閾值，則認(rèn)為該服務(wù)在未來(lái)一段時(shí)間內(nèi)并不穩(wěn)定；小于這個(gè)閾值，則表示該服務(wù)能在服務(wù)系統(tǒng)內(nèi)更穩(wěn)定地提供服務(wù)。因此服務(wù)消亡預(yù)測(cè)問(wèn)題本質(zhì)上還是一個(gè)二分類(lèi)問(wèn)題，閾值調(diào)整需要根據(jù)不同的服務(wù)系統(tǒng)或用戶的使用需求而定。在這種情況下，曲線下面積(Area Under Curve，AUC)指標(biāo)值是非常適合的一種評(píng)價(jià)方法。

二分類(lèi)問(wèn)題樣本的觀察結(jié)果常表示為正類(lèi)(positive)和負(fù)類(lèi)(negative)，分類(lèi)結(jié)果有正確分類(lèi)(true)和錯(cuò)誤分類(lèi)(false)兩種情況，綜合起來(lái)有TP，F(xiàn)P，TN，F(xiàn)N4種指標(biāo)，這4種指標(biāo)能更好地體現(xiàn)分類(lèi)的準(zhǔn)確性。定義真正類(lèi)率TPR和負(fù)正類(lèi)率FPR分別為：

(18)

在[0,1]間逐漸改變分類(lèi)閾值，可以得到逐漸變化的多組分類(lèi)結(jié)果，以FPR為橫坐標(biāo)，TPR為縱坐標(biāo)，繪制受試者工作特性(Receiver Operating Characteristic, ROC)曲線，曲線與X軸之間的面積即為AUC值。ROC曲線越接近(0,1)越好，曲線拱起的弧頂使視覺(jué)判斷更為直觀。在多種算法曲線相近的情況下，AUC值越接近1，分類(lèi)算法的效果越好。

4.3 參數(shù)設(shè)置

實(shí)驗(yàn)中需要設(shè)置的參數(shù)主要為泊松分解算法參數(shù)和ELM算法部分參數(shù)。泊松分解算法中，Gamma分布參數(shù)λsa=0.14，λwa=0.16，λsb和λwb并未單獨(dú)設(shè)置，而是采用文獻(xiàn)[20]介紹的方法，其中

(19)

主題數(shù)目K=150。ELM算法中設(shè)置λ=[10 1]。

另外，本文在實(shí)驗(yàn)中采用LDA作為泊松分解的比較算法，采用樸素貝葉斯分類(lèi)算法作為ELM的對(duì)比算法。LDA的參數(shù)設(shè)置中，主題數(shù)目同樣設(shè)置為150，迭代次數(shù)設(shè)置為2 000次；樸素貝葉斯算法中無(wú)參數(shù)設(shè)置。

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

實(shí)驗(yàn)將4種算法交叉應(yīng)用，最終的實(shí)驗(yàn)結(jié)果如圖9所示。當(dāng)主題特征提取采用泊松分解，分類(lèi)算法采用ELM時(shí)取得了最好的實(shí)驗(yàn)結(jié)果，即圖中的PF+ELM曲線，AUC面積為0.800 3;采用LDA提取主題特征、ELM分類(lèi)時(shí)的AUC面積為0.780 8，效果次之;再次的為使用PF算法提取主題特征、使用樸素貝葉斯分類(lèi)，其AUC面積為0.698;效果最差為采用LDA和樸素貝葉斯組合的算法，其AUC面積為0.652 7。綜合考慮得出結(jié)論為：對(duì)于主題特征提取，泊松分解略優(yōu)于LDA算法，而分類(lèi)算法中的ELM分類(lèi)效果明顯優(yōu)于樸素貝葉斯算法。

使用訓(xùn)練完成的PF+ELM算法對(duì)數(shù)據(jù)集中最后150個(gè)服務(wù)進(jìn)行預(yù)測(cè)，預(yù)測(cè)結(jié)果如表3所示。

表3 預(yù)測(cè)結(jié)果

在實(shí)際的服務(wù)系統(tǒng)中，產(chǎn)生服務(wù)消亡現(xiàn)象的仍然為少數(shù)服務(wù)，在本組數(shù)據(jù)中，真正失效的只有Yahoo Image Search一個(gè)服務(wù)。對(duì)于其他幾個(gè)服務(wù)，由于受Yahoo search服務(wù)消亡的影響，導(dǎo)致Google的類(lèi)似服務(wù)迅速占據(jù)了絕對(duì)領(lǐng)先地位，Yahoo Local Search和Yahoo Travel也因此處于長(zhǎng)期無(wú)人問(wèn)津的尷尬地位。預(yù)測(cè)中的第4位Wolfram Alpha是一個(gè)計(jì)算類(lèi)服務(wù)，在其介紹中有“computational knowledge engine”和“make it possible to compute whatever can be computed about anything”等，在ProgrammableWeb網(wǎng)站上計(jì)算類(lèi)服務(wù)并非熱門(mén)的類(lèi)別，過(guò)度夸張的宣傳或許會(huì)使用戶敬而遠(yuǎn)之。Wookmark是一個(gè)社交類(lèi)網(wǎng)站，用戶可以在上面發(fā)布照片和視頻以及交友等。Facebook基本涵蓋其所有功能，不能獲得用戶青睞也比較容易理解。

4.5 特征組合意義和特征選擇標(biāo)準(zhǔn)

為觀察僅使用單特征情況下的預(yù)測(cè)效果，單獨(dú)采用主題特征和時(shí)間特征分別進(jìn)行預(yù)測(cè)。從圖10可以看到，當(dāng)單獨(dú)使用主題信息進(jìn)行服務(wù)消亡預(yù)測(cè)時(shí)，AUC面積為0.703；當(dāng)單獨(dú)使用時(shí)間信息進(jìn)行預(yù)測(cè)時(shí)，AUC面積為0.732 7；而當(dāng)將二者結(jié)合使用后，預(yù)測(cè)效果則有了一個(gè)較大的提升。從算法上來(lái)說(shuō)，增加一個(gè)參數(shù)，最壞的情況仍然是保持之前的結(jié)果，即這部分參數(shù)的隱層參數(shù)全為0。相反，如果能采用更多可用的特征信息，則可以進(jìn)一步提高服務(wù)退出預(yù)測(cè)的整體精確度。

雖然更多的特征加入會(huì)提高服務(wù)消亡預(yù)測(cè)的精度，但是本文在算法中僅考慮了時(shí)間特征和主題特征兩種參數(shù)。一個(gè)服務(wù)系統(tǒng)中必然包括很多特征，有些是屬于所有服務(wù)系統(tǒng)共有的特征，而有些則是該服務(wù)系統(tǒng)特有的個(gè)性化參數(shù)。在算法的可用特征的選擇上，應(yīng)該盡可能選擇那些通用的、普適性的參數(shù)，而不僅是某個(gè)服務(wù)系統(tǒng)所獨(dú)有的屬性，否則必然降低算法在不同服務(wù)系統(tǒng)間的通用性，甚至受限于服務(wù)系統(tǒng)的更新而導(dǎo)致算法失效。例如文獻(xiàn)[11]使用的供應(yīng)商信息，由于ProgrammableWeb網(wǎng)站改版的原因，新增加的Web服務(wù)中大部分已經(jīng)不再提供該項(xiàng)數(shù)據(jù)，導(dǎo)致該算法的可用性大大降低。本文僅選擇時(shí)間特征和主題特征正是出于這方面的考慮，所選取的特征均為各類(lèi)服務(wù)系統(tǒng)具備的通用屬性。

5 相關(guān)工作

近年來(lái)，隨著服務(wù)系統(tǒng)在人們?nèi)粘Ｉ钪械娜找嫫占?，?duì)服務(wù)系統(tǒng)的研究逐漸引起了學(xué)者們的重視。目前的研究問(wèn)題多數(shù)集中在從用戶使用的角度出發(fā)所作的服務(wù)推薦工作，如文獻(xiàn)[5,12-14]。但對(duì)服務(wù)系統(tǒng)來(lái)說(shuō)，Web服務(wù)消亡也是一個(gè)必然的現(xiàn)象，目前有關(guān)服務(wù)系統(tǒng)內(nèi)Web服務(wù)退出服務(wù)系統(tǒng)的機(jī)制和影響的研究還比較少。服務(wù)消亡不等同于服務(wù)失效，服務(wù)消亡和服務(wù)失效的最大區(qū)別在于，導(dǎo)致服務(wù)失效的往往是因?yàn)榫W(wǎng)絡(luò)異常等原因，在故障排除后Web服務(wù)依然能夠繼續(xù)提供服務(wù)，從長(zhǎng)遠(yuǎn)的角度看對(duì)服務(wù)系統(tǒng)的影響并不嚴(yán)重，對(duì)服務(wù)失效的研究多聚焦于研究失效的原因及處理方法[6-9]。服務(wù)消亡則是Web服務(wù)徹底退出了服務(wù)系統(tǒng)，不再提供任何服務(wù)支持，解決這類(lèi)問(wèn)題更側(cè)重于預(yù)防以及相似Web服務(wù)的備選工作。目前，有關(guān)Web服務(wù)消亡問(wèn)題的研究尚處于起步階段，文獻(xiàn)[21]研究了服務(wù)消亡的產(chǎn)生機(jī)制，依此提出一個(gè)研究框架并給出了一套度量指標(biāo)，但目前Web服務(wù)正處于蓬勃發(fā)展的上升期，對(duì)應(yīng)的框架和指標(biāo)也應(yīng)該隨著服務(wù)系統(tǒng)的日趨成熟而不斷修改和變化;文獻(xiàn)[10]使用服務(wù)標(biāo)簽對(duì)Web服務(wù)進(jìn)行分類(lèi)，使用二部圖度量同類(lèi)Web服務(wù)間的競(jìng)爭(zhēng)關(guān)系來(lái)進(jìn)行服務(wù)消亡預(yù)測(cè)，然而服務(wù)標(biāo)簽為人工生成，難免存在一些分類(lèi)誤差或者遺漏;文獻(xiàn)[11]加入供應(yīng)商信息，通過(guò)判別供應(yīng)商實(shí)力來(lái)進(jìn)行服務(wù)消亡預(yù)測(cè)，分類(lèi)算法取得了不錯(cuò)的效果，但供應(yīng)商信息受限于服務(wù)系統(tǒng)，非通用性的參數(shù)限制了算法的可移植性和通用性。本文通過(guò)使用主題信息和時(shí)間信息兩類(lèi)特征數(shù)據(jù)，有效地對(duì)Web服務(wù)消亡進(jìn)行了預(yù)測(cè)。本文采用機(jī)器學(xué)習(xí)方法減少了人工干預(yù)可能帶來(lái)的誤差，特征數(shù)據(jù)的通用性則保證了預(yù)測(cè)算法在不同服務(wù)系統(tǒng)間的可移植性。

6 結(jié)束語(yǔ)

近年來(lái)，隨著Web服務(wù)的迅猛發(fā)展，服務(wù)計(jì)算及其相關(guān)研究得到了極大關(guān)注。從軟件生命周期[22]的角度分析，Web服務(wù)必然包括產(chǎn)生、提供服務(wù)和最終消亡的過(guò)程。目前，學(xué)者們的研究往往集中在從用戶的角度解決Web服務(wù)中出現(xiàn)的各種問(wèn)題，以及面向用戶做各種類(lèi)型的服務(wù)推薦等，有關(guān)Web服務(wù)生命周期中服務(wù)消亡現(xiàn)象的研究還比較少。研究服務(wù)消亡問(wèn)題，是通過(guò)檢測(cè)服務(wù)系統(tǒng)中存在不穩(wěn)定因素的相關(guān)服務(wù)，提醒服務(wù)組合開(kāi)發(fā)者和服務(wù)系統(tǒng)開(kāi)發(fā)與研究人員加以重視，從而提高服務(wù)系統(tǒng)的穩(wěn)定性。一個(gè)健康穩(wěn)定的服務(wù)系統(tǒng)才能更好地滿足用戶的各種需求，持續(xù)吸引用戶的關(guān)注并得到更好的發(fā)展。

社會(huì)流行元素的更替必然影響Web服務(wù)主題分布，不合時(shí)宜的Web服務(wù)會(huì)逐漸退出服務(wù)系統(tǒng)，時(shí)間特征則是所有Web服務(wù)共有的因素。本文提出的Web服務(wù)消亡預(yù)測(cè)方法利用機(jī)器學(xué)習(xí)算法有效提取了服務(wù)系統(tǒng)中服務(wù)消亡個(gè)體的特點(diǎn)，基于ProgrammableWeb上的實(shí)驗(yàn)表明，該方法能有效預(yù)測(cè)服務(wù)消亡，為服務(wù)的使用者特別是服務(wù)組合開(kāi)發(fā)者提供可靠的建議。

引入更多的可用指標(biāo)必然會(huì)增加預(yù)測(cè)的準(zhǔn)確性，后續(xù)研究計(jì)劃增強(qiáng)這方面的研究和探索，以發(fā)現(xiàn)和利用更多的通用性指標(biāo)。另外，算法中有一部分需要線下計(jì)算，而服務(wù)系統(tǒng)在運(yùn)行一段時(shí)間后必然會(huì)有新服務(wù)加入或已有服務(wù)消亡，導(dǎo)致線下部分必須在模型運(yùn)行一段時(shí)間后重新計(jì)算，以保持與當(dāng)前系統(tǒng)的一致性，后續(xù)研究將致力于完成對(duì)應(yīng)的增量改進(jìn)算法，從而更好地提供在線服務(wù)。