夏博飛，范玉順，黃科滿

（清華大學(xué) 自動化系，北京 100084）

1 問題的提出

隨著Web 服務(wù)技術(shù)和面向服務(wù)架構(gòu)（Service Oriented Architecture，SOA）標(biāo)準(zhǔn)的成熟，一方面互聯(lián)網(wǎng)上的Web服務(wù)種類和數(shù)量都急劇增加；另一方面，Web服務(wù)個體以動態(tài)集成的方式形成服務(wù)組合，進而滿足用戶大規(guī)模、個性化、復(fù)雜多變的業(yè)務(wù)需求。由此，大量異質(zhì)的、具有復(fù)雜關(guān)聯(lián)關(guān)系的Web服務(wù)在相互競爭、協(xié)作的過程中，形成了Web服務(wù)生態(tài)系統(tǒng)［1］。例如，為了適應(yīng)未來面向服務(wù)的網(wǎng)絡(luò)制造需要［2-3］，越來越多的制造業(yè)企業(yè)將各自的資源封裝成Web 服務(wù)（如應(yīng)用程序接口（Application Programming Interface，API）的形式），以便不同資源間的協(xié)同合作，逐漸形成了云制造中的Web服務(wù)生態(tài)系統(tǒng)。但隨著時間的推移，Web服務(wù)生態(tài)系中滿足相同功能需求的服務(wù)個體越來越多，這些功能上相似的服務(wù)個體之間產(chǎn)生了競爭關(guān)系。由于競爭淘汰作用，一些服務(wù)個體將從服務(wù)生態(tài)系統(tǒng)中消亡，使得調(diào)用這些服務(wù)個體的服務(wù)組合失效，并對服務(wù)使用者產(chǎn)生影響。

圖1 所示為選自ProgrammableWeb 中 Web API生態(tài)系統(tǒng)中的一個實例。在該服務(wù)生態(tài)系統(tǒng)中，服務(wù)使用者調(diào)用發(fā)布在網(wǎng)站上的服務(wù)個體（API），以Mashup的形式進行服務(wù)組合，完成特定的功能。圖1中的服務(wù)組合ebay in MSN Messenger調(diào)用三個服務(wù)個體ebay，Microsoft Bing Maps和MSN Messenger，完成一個基于地理位置的在線購物聊天的功能；服務(wù)組合Amazon.com Shopping Together調(diào)用兩個服務(wù)個體Amazon Product Advertising和MSN Messenger，完成一個具有網(wǎng)購功能的聊天工具。隨著時間的推移，服務(wù)個體MSN Messenger無法繼續(xù)提供聊天功能的服務(wù)，因此服務(wù)組合ebay in MSN Messenger和Amazon.com Shopping Together均失效，無法完成其原有功能。這種現(xiàn)象正是由服務(wù)生態(tài)系統(tǒng)中服務(wù)個體的消亡引起的。面對復(fù)雜隨機的網(wǎng)絡(luò)環(huán)境和日益涌現(xiàn)的海量Web服務(wù)，服務(wù)使用者在選擇服務(wù)個體時不僅要滿足功能上的需求，還要考慮服務(wù)個體的可靠性，從而保證形成的服務(wù)組合具有持久可用性。然而，僅針對某一個服務(wù)個體很難判斷其可靠性。因此，需要把多個服務(wù)個體看成一個整體，從服務(wù)生態(tài)系統(tǒng)的角度研究服務(wù)個體的消亡問題。由此，本文的工作主要圍繞兩方面進行：①識別并提取Web服務(wù)生態(tài)系統(tǒng)中消亡服務(wù)個體的特征；②利用消亡服務(wù)個體的特征預(yù)測潛在的消亡服務(wù)個體，最終為服務(wù)使用者提供決策意見。

服務(wù)標(biāo)簽（tag）作為Web 2.0時代流行的資源識別和管理方法［4］，具有門檻低、易用、操作靈活和互動性強等優(yōu)點，在互聯(lián)網(wǎng)上被各行各業(yè)廣泛應(yīng)用，如圖片分享網(wǎng)站Flickr（www.flickr.com）、網(wǎng)頁分享網(wǎng)站Delicious（www.delicous.com）、大眾點評網(wǎng)（www.dianping.com）和視頻網(wǎng)站youku（www.youku.com）等。近年來，一些Web服務(wù)注冊機構(gòu)，如Seekda.com，ProgrammableWeb.com 開始對Web服務(wù)標(biāo)注功能描述性的服務(wù)標(biāo)簽。相比一些傳統(tǒng)Web服務(wù)描述方法，如語義Web服務(wù)描述語言（Web Services Description Language-Semantic，WSDL-S）［5］、Web 服務(wù)描 述語言注釋（Semantic Annotation for Web Service Description Language，SAWSDL）［6］、Web 服務(wù)建 模本體（Web Service Modeing Ontology，WSMO）、Web服務(wù)本體描述語言（Web Ontology Language for Service，OWLS）［7］，服務(wù)標(biāo)簽雖然在規(guī)范性和完備性上不如服務(wù)描述文件，但是可以集中概括Web服務(wù)所屬范疇和涵蓋的功能類型。用戶通過搜索被標(biāo)注特定標(biāo)簽的服務(wù)或者利用標(biāo)簽云等方式，可以高效地在大量服務(wù)中迅速篩選需要的Web服務(wù)。因此含有相同標(biāo)簽的服務(wù)在滿足特定業(yè)務(wù)需求時存在競爭關(guān)系。每一個服務(wù)個體標(biāo)注了若干服務(wù)標(biāo)簽，由此產(chǎn)生了復(fù)雜的競爭關(guān)系網(wǎng)絡(luò)。本文利用Web服務(wù)標(biāo)簽信息，建立服務(wù)相似度網(wǎng)絡(luò)（Service Similarity Network，SSN），采用網(wǎng)絡(luò)分析法研究服務(wù)競爭關(guān)系；首次提出服務(wù)特征百分比（Feature Percentage Ranking，F(xiàn)PR），進而構(gòu)建基于FPR 的Logistic回歸模型的服務(wù)個體消亡概率預(yù)測算法。經(jīng)過ProgrammableWeb上OpenAPI服務(wù)生態(tài)系統(tǒng)的實證分析，表明該方法能夠有效地篩選消亡服務(wù)，提高服務(wù)組合的持久可用性。同時，實驗表明具有個性化功能的服務(wù)具備更高的存活率，因此服務(wù)提供者應(yīng)著力于提供具有個性化功能的服務(wù)。

2 相關(guān)工作

Web 服務(wù)領(lǐng)域近年來得到了大量學(xué)者的關(guān)注［8-11］。隨著各方面技術(shù)標(biāo)準(zhǔn)的不斷成熟，服務(wù)個體與服務(wù)提供者、服務(wù)使用者和服務(wù)組合的關(guān)系呈現(xiàn)出類生態(tài)特性，被稱為Web服務(wù)生態(tài)系統(tǒng)［1］。隨著時間的推移，不斷有新的服務(wù)個體加入系統(tǒng)，具有相似功能的服務(wù)個體之間產(chǎn)生競爭關(guān)系，部分服務(wù)在激烈的競爭中退出系統(tǒng)。這些退出系統(tǒng)的服務(wù)個體將使調(diào)用這些服務(wù)的服務(wù)組合失效，影響了服務(wù)組合的長期可用性。該問題是Web服務(wù)生態(tài)系統(tǒng)發(fā)展到一定階段帶來的，并且對系統(tǒng)的發(fā)展產(chǎn)生了很大的影響。以全球最大的OpenAPI服務(wù)生態(tài)系統(tǒng)ProgrammableWeb為例：2005年6月到2013年6月，該服務(wù)生態(tài)系統(tǒng)中消亡的服務(wù)個體約占服務(wù)個體總數(shù)的19%，這些消亡的服務(wù)個體使20.5%的服務(wù)組合失效，即影響了20.5%的服務(wù)使用者［12］。因此分析服務(wù)生態(tài)系統(tǒng)中服務(wù)消亡的機制，預(yù)測服務(wù)個體的消亡概率，提高服務(wù)組合的長期可用性，對促進服務(wù)生態(tài)系統(tǒng)的良性發(fā)展具有重要的意義，然而這方面的研究卻十分缺乏。

近年來，許多學(xué)者針對Web服務(wù)標(biāo)簽做了大量工作。為了解決Web服務(wù)的語義描述效率問題，文獻［13］提出一種基于多維度標(biāo)簽的Web服務(wù)語義描述策略；文獻［14］為了解決人工為Web服務(wù)標(biāo)注標(biāo)簽的繁瑣工作，提出一種基于Web服務(wù)描述語言（Web Service Distribut Language，WSDL）的自動標(biāo)注標(biāo)簽方法，并實現(xiàn)了原型系統(tǒng)。在服務(wù)發(fā)現(xiàn)方面，文獻［15］給出利用標(biāo)簽和服務(wù)描述文本的系統(tǒng)算法，提高了Web服務(wù)發(fā)現(xiàn)效率的算法，使用戶能夠清晰高效地描述服務(wù)功能需求，從而提高了搜索返回服務(wù)的質(zhì)量。上述這些研究大都從服務(wù)標(biāo)簽本身出發(fā)，研究內(nèi)容包括如何為Web服務(wù)標(biāo)注標(biāo)簽以及利用服務(wù)標(biāo)簽提高服務(wù)發(fā)現(xiàn)、功能描述等。

復(fù)雜網(wǎng)絡(luò)分析作為一種研究手段，在Web服務(wù)研究領(lǐng)域得到了廣泛應(yīng)用。通過解析Web服務(wù)文件接口，文獻［7］給出了Web服務(wù)網(wǎng)絡(luò)的模型，從復(fù)雜網(wǎng)絡(luò)的角度分析了服務(wù)網(wǎng)絡(luò)的性質(zhì)；文獻［16］利用復(fù)雜網(wǎng)絡(luò)工具對Web服務(wù)領(lǐng)域中的科學(xué)工作流網(wǎng)絡(luò)進行了建模分析，得到了科學(xué)工作流中不同服務(wù)節(jié)點的性質(zhì)，給出了提高重用率的建議；文獻［17］將復(fù)雜網(wǎng)絡(luò)分析作為主要工具，分析了ProgrammableWeb上Mashup服務(wù)生態(tài)系統(tǒng)的靜態(tài)特性以及動態(tài)演化機制，挖掘了服務(wù)生態(tài)系統(tǒng)演化的規(guī)律，為進一步的Web服務(wù)推薦提供了基礎(chǔ)。

本文在前人工作的基礎(chǔ)上，進一步探究了Web服務(wù)生態(tài)系統(tǒng)中消亡服務(wù)個體的問題。以Web服務(wù)標(biāo)簽信息作為切入點，挖掘服務(wù)之間的相似性，再從服務(wù)相似性推移到服務(wù)競爭關(guān)系，利用復(fù)雜網(wǎng)絡(luò)方法對Web服務(wù)生態(tài)系統(tǒng)中服務(wù)個體間的競爭關(guān)系進行建模，提出一套基于統(tǒng)計機器學(xué)習(xí)的消亡服務(wù)預(yù)測方法，可以為服務(wù)使用者提供可靠的參考建議。

3 含權(quán)服務(wù)相似度網(wǎng)絡(luò)與服務(wù)特征百分比

3.1 含權(quán)服務(wù)相似度網(wǎng)絡(luò)SSN

服務(wù)個體之間的競爭導(dǎo)致服務(wù)個體的消亡，包含相似功能的服務(wù)個體之間存在著競爭關(guān)系［7］。因此，為了挖掘消亡服務(wù)個體的特征，需要構(gòu)建一個描述服務(wù)個體功能相似度的網(wǎng)絡(luò)。在構(gòu)建SSN 時遵循如下原則：

原則1 服務(wù)標(biāo)簽是對服務(wù)個體功能的客觀描述，被標(biāo)注相同服務(wù)標(biāo)簽的服務(wù)個體之間存在競爭關(guān)系。例如，Google Maps服務(wù)和Yahoo Maps服務(wù)都標(biāo)注了mapping標(biāo)簽，則認(rèn)為這兩個服務(wù)之間存在競爭關(guān)系。

原則2 提供相同功能的服務(wù)個體越多，服務(wù)個體之間的競爭就越激烈。例如，標(biāo)簽ti在所有服務(wù)個體中出現(xiàn)了100次，標(biāo)簽tj在所有服務(wù)個體中出現(xiàn)了10 次，則認(rèn)為含有ti功能的服務(wù)個體之間的競爭更激烈。

原則3 相似功能的服務(wù)可能標(biāo)注的服務(wù)標(biāo)簽不同，需要考慮服務(wù)標(biāo)簽?zāi)：缘膯栴}。以英文服務(wù)標(biāo)簽為例：兩個服務(wù)分別標(biāo)注了photo 和picture，雖然具有不同的服務(wù)標(biāo)簽，但兩個服務(wù)顯然都提供了圖片相關(guān)的功能。

基于以上三個原則，引入復(fù)雜網(wǎng)絡(luò)方法研究服務(wù)標(biāo)簽與服務(wù)的競爭關(guān)系。如圖2所示，首先構(gòu)建“服務(wù)—標(biāo)簽”二部圖。二部圖中的節(jié)點分為服務(wù)節(jié)點和標(biāo)簽節(jié)點兩種；二部圖中的邊表示服務(wù)個體被標(biāo)注的服務(wù)標(biāo)簽。為了消除服務(wù)標(biāo)簽的語義模糊性，需要考察標(biāo)簽語義相似度，對“服務(wù)—標(biāo)簽”二部圖中語義相近的標(biāo)簽節(jié)點進行合并。WordNet是普林斯頓大學(xué)開發(fā)的一個在線語義知識關(guān)系庫（wordnet.princeton.edu），自發(fā)布以來獲得了學(xué)術(shù)界的廣泛認(rèn)可。利用WordNet可以計算兩個服務(wù)標(biāo)簽的語義相似度［18］，判斷是否可以合并標(biāo)簽節(jié)點。完成相似標(biāo)簽節(jié)點合并后，從“服務(wù)—標(biāo)簽”二部圖中抽取描述服務(wù)個體之間相似度的網(wǎng)絡(luò)，進一步考慮服務(wù)標(biāo)簽的頻率，抽取標(biāo)簽出現(xiàn)頻率關(guān)聯(lián)網(wǎng)絡(luò)。獲得含權(quán)服務(wù)的相似度網(wǎng)絡(luò)，用來刻畫服務(wù)生態(tài)系統(tǒng)中服務(wù)個體間的復(fù)雜相似關(guān)系網(wǎng)絡(luò)，最終得到含權(quán)SNN。該網(wǎng)絡(luò)中的節(jié)點表示服務(wù)個體，節(jié)點之間邊的權(quán)重表示服務(wù)個體間的相似度大小。

為了規(guī)范描述，在文獻［16-17］的基礎(chǔ)上，給出一種含權(quán)SNN 構(gòu)建算法的矩陣描述，算法流程中涉及三個矩陣，意義如下：

（1）STN=［stnij］，0≤i≤N，0≤j≤Index。STN是一個稀疏矩陣，stnij=1表示服務(wù)個體i被標(biāo)注了標(biāo)簽j，stnij=0表示沒有被標(biāo)注標(biāo)簽j，N表示服務(wù)個體數(shù)，Index表示簽數(shù)種類數(shù)。

（2）TFN=［tfnij］，0≤i，j≤Index。TFN是一個對角陣，對角線元素tfnij表示標(biāo)簽i的出現(xiàn)頻率。

（3）SSN=［ssnij］，0≤i，j≤N。SSN是一個對稱陣，ssnij表示服務(wù)個體i與服務(wù)個體j的相似度，即服務(wù)相似度網(wǎng)絡(luò)中服務(wù)節(jié)點i與服務(wù)節(jié)點j之間連邊的權(quán)值，具體如算法1所示。

算法1 含權(quán)服務(wù)相似度矩陣SSN的獲取算法。

輸入：服務(wù)、標(biāo)簽二元組集合｛〈si，tlisti〉，1≤i≤N｝。其中：si表示服務(wù)個體i，tlisti表示被標(biāo)注的標(biāo)簽集合，N表示服務(wù)個體總數(shù)。

輸出：含權(quán)服務(wù)相似度矩陣SSN。

算法1的基本思路如下：統(tǒng)計所有出現(xiàn)在服務(wù)個體中的標(biāo)簽，合并語義近似的服務(wù)標(biāo)簽，并為每個標(biāo)簽編號，進而將原始服務(wù)標(biāo)簽數(shù)據(jù)轉(zhuǎn)化成“服務(wù)—標(biāo)簽”稀疏矩陣STN；再對STN的列求和，構(gòu)造服務(wù)標(biāo)簽頻率矩陣TFN；最終由構(gòu)造的STN和TFN做矩陣乘法，獲得含權(quán)服務(wù)相似度矩陣SSN。

3.2 服務(wù)特征百分比FPR

在獲得含權(quán)SSN 后，基于該SSN 網(wǎng)絡(luò)中服務(wù)節(jié)點的度獲取服務(wù)的特征，預(yù)測服務(wù)個體是否消亡。由于在服務(wù)生態(tài)系統(tǒng)中，服務(wù)個體和服務(wù)標(biāo)簽的數(shù)量均隨時間動態(tài)變化，即SSN 網(wǎng)絡(luò)中節(jié)點的度也是動態(tài)變化的，僅用每個服務(wù)節(jié)點的度作為特征降低了算法的動態(tài)性能。因此，在3.1節(jié)的基礎(chǔ)上提出FPR 的概念，并給出服務(wù)FPR 的獲取算法，如算法2所示。

算法2 基于SSN矩陣的服務(wù)FPR 提取算法。

輸入：含權(quán)服務(wù)相似度矩陣SSN，N表示SSN矩陣的階數(shù)。

輸出：排序含權(quán)服務(wù)相似度矩陣SSN′。

算法2的基本思想如下：根據(jù)每個服務(wù)節(jié)點在SSN 網(wǎng)絡(luò)中的相似度之和，對服務(wù)節(jié)點重新排序編號。由3.1節(jié)可知，SSN矩陣是對SSN 網(wǎng)絡(luò)的一種矩陣描述，其中ssnij代表服務(wù)si與sj的相似度且SSN矩陣為對稱陣。因此，SSN矩陣的每一行對應(yīng)一個服務(wù)，行號i對應(yīng)一個服務(wù)si。經(jīng)過矩陣排序算法后，獲得SSN 網(wǎng)絡(luò)的另一種等價矩陣描述SSN′。SSN′也是一個對稱陣，矩陣行號對應(yīng)一個服務(wù)，且SSN′是排序后的矩陣，行號i可以作為服務(wù)節(jié)點si在SSN 網(wǎng)絡(luò)中的編號。對排名做歸一化處理后，定義

為服務(wù)si的FPR，每一個加入SSN 網(wǎng)絡(luò)中的服務(wù)節(jié)點都有一個FPR。

4 消亡服務(wù)個體的預(yù)測方法

利用第3章中獲取的服務(wù)FPR，提出一套基于統(tǒng)計機器學(xué)習(xí)的Web服務(wù)生態(tài)系統(tǒng)中消亡服務(wù)個體的預(yù)測方法。該問題是一個二值分類問題，因此首先用統(tǒng)計學(xué)的方法對兩類服務(wù)個體FPR 的差異性進行假設(shè)檢驗，在判斷FPR 差異的顯著性后，再設(shè)計回歸分類算法來預(yù)測潛在消亡服務(wù)。

4.1 兩類服務(wù)個體FPR的置換檢驗

本節(jié)通過引入置換檢驗［19］的方式，量化兩類服務(wù)個體FPR 值差異的顯著性。

服務(wù)生態(tài)系統(tǒng)中m個消亡服務(wù)個體的fpr值為x1，…，xm，均值為；n個非消亡服務(wù)個體的fpr值為y1，…，yn，均值為。設(shè)檢驗統(tǒng)計量

則檢驗為

令N=m+n，考慮數(shù)據(jù)x1，…，xm，y1，…，yn的N！種置換，計算檢驗統(tǒng)計量T，表示為T1，T2，…，TN。若原假設(shè)成立，則T取每個Tj的概率為1／N！。令Tobs表示檢驗統(tǒng)計量T的觀測值，當(dāng)T很大時拒絕原假設(shè)，則p值為

考慮實際Web服務(wù)生態(tài)系統(tǒng)中的N值較大，計算N！的任務(wù)量非常繁重，可以從置換集中隨機抽樣進而計算p的近似值，計算步驟如下：

步驟1 計算檢驗統(tǒng)計量觀測值Tobs。

步驟2 從N個fpr值中隨機抽取m個分配給消亡服務(wù)個體，剩下的n個分配給非消亡服務(wù)個體。

步驟3 用置換后的數(shù)據(jù)計算檢驗統(tǒng)計量。

步驟4 重復(fù)步驟1～步驟3K次，令T1，T2，…，TK表示每次結(jié)果。

步驟5 近似的p值為

步驟6 由p值判斷兩類服務(wù)FPR 差異的顯著性水平。

4.2 Logistic回歸模型

Logistic回歸是一種經(jīng)典的二值分類算法，其基本思想是：使用Logit變換作為連接函數(shù)，將響應(yīng)變量的期望與線性自變量相聯(lián)系［20］。在本文研究中，自變量為SSN 網(wǎng)絡(luò)中服務(wù)個體的FPR 值，響應(yīng)變量服從Bernoulli分布（規(guī)定1 表示潛在消亡服務(wù)，0表示非潛在消亡服務(wù)）。通過現(xiàn)有SSN 網(wǎng)絡(luò)中的服務(wù)個體訓(xùn)練Logistic回歸模型的參數(shù)，并計算新加入SSN 網(wǎng)絡(luò)的服務(wù)個體的FPR 值，進而通過模型預(yù)測新加入服務(wù)生態(tài)系統(tǒng)的服務(wù)個體是否會潛在消亡。

構(gòu)建Logistic回歸模型如下：定義πi為服務(wù)個體si潛消亡的概率，

構(gòu)建Logistic回歸方程，其中β0 和β1 為待估參數(shù)，

通過回歸方程求出πi，

利用現(xiàn)有SSN 網(wǎng)絡(luò)訓(xùn)練參數(shù)β0 和β1。SSN 網(wǎng)絡(luò)提供的信息包括服務(wù)節(jié)點si（值為1表示為消亡服務(wù)，為0表示為非消亡服務(wù)）及其fpri。令N表示訓(xùn)練集構(gòu)成的SSN 網(wǎng)絡(luò)中服務(wù)節(jié)點的個數(shù)，采用最大似然估計（Maximum Likelihood Estimation，MLE）方法估計參數(shù)β0 和β1。列出似然函數(shù)表達式如下：

對似然函數(shù)取log對數(shù)，可得

分別對β0 和β1 求偏導(dǎo)數(shù)，使其為0，可得方程組

利用Newton-Raphson 數(shù)值解法，求出參數(shù)的最大似然估計和，完成回歸預(yù)測模型。給定一個新加入系統(tǒng)的服務(wù)個體S，可以求出其特征百分比fpr，進而得到該服務(wù)個體潛在消亡的概率π，

4.3 消亡服務(wù)個體的預(yù)測算法

在4.1節(jié)和4.2節(jié)基礎(chǔ)上給出完整的潛在消亡服務(wù)個體的預(yù)測算法，如算法3所示。

算法3 消亡服務(wù)個體預(yù)測算法。

輸入：TagIndex〈tag，index〉（標(biāo)簽編號列表）；STN矩陣（行數(shù)為N，列數(shù)為Index）；TFN矩陣（階數(shù)為Index）；〈s，tlist〉（待預(yù)測服務(wù)的服務(wù)—標(biāo)簽二元組）；（訓(xùn)練數(shù)據(jù)集得到的Logistic模型參數(shù)）。

輸出：0-1變量（1表示消亡服務(wù)，0表示非消亡服務(wù)）。

5 算法驗證分析

5.1 實驗數(shù)據(jù)集

本文所用數(shù)據(jù)集獲取自ProgrammableWeb（www.programmableweb.com）——迄今為止最大的在線OpenAPI服務(wù)生態(tài)系統(tǒng)。在ProgrammableWeb中，服務(wù)個體以API的形式被服務(wù)提供商發(fā)布到網(wǎng)上，使用者調(diào)用這些API，并以Mashup的形式將這些API 組合成新的應(yīng)用。Programma-bleWeb上注冊的每個API包括服務(wù)提供商信息、在哪些Mashup中出現(xiàn)過，以及服務(wù)注冊時間和服務(wù)消亡時間，并且API都被標(biāo)注了服務(wù)標(biāo)簽。為了研究消亡服務(wù)個體對服務(wù)組合的影響，對ProgrammableWeb上2005年6月到2012年12月的數(shù)據(jù)進行整理，清洗掉沒有出現(xiàn)在Mashup中的API，篩選出1 176個API，最終得到的數(shù)據(jù)如表1所示。

表1 ProgrammableWeb數(shù)據(jù)集

因為預(yù)測算法是有監(jiān)督學(xué)習(xí)的算法，所以需要按照時間間隔，將ProgrammableWeb 上的數(shù)據(jù)分為訓(xùn)練集和測試集，如表2所示。

表2 訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)

訓(xùn)練組與測試組的數(shù)據(jù)包括服務(wù)個體、服務(wù)標(biāo)簽和服務(wù)個體是否消亡的信息。本文利用訓(xùn)練組的數(shù)據(jù)訓(xùn)練回歸模型的參數(shù)，預(yù)測測試組中的服務(wù)個體是否為潛在消亡個體，并與實際數(shù)據(jù)比對，進而評估預(yù)測算法。

5.2 評價指標(biāo)

利用幾個指標(biāo)檢驗預(yù)測算法的效果。召回率（Recall）和準(zhǔn)確率（Precision）［21］是兩個最重要的二值分類算法驗證指標(biāo)：在本文中，召回率的意義為算法能夠識別全部消亡服務(wù)的百分比；準(zhǔn)確率的意義為算法能夠識別出的消亡服務(wù)中有多大比例是真正消亡的服務(wù)。二者計算公式如下：

其中TP，F(xiàn)P，TN和FN表示二值分類的四種結(jié)果，意義如表3所示。

表3 二值分類算法結(jié)果

除了準(zhǔn)確率和召回率，進一步參考并引入以下幾個算法評價指標(biāo)：

（1）由于準(zhǔn)確率和召回率有時是矛盾的，引入F1M（F1-measure）來綜合考慮召回率和準(zhǔn)確率的效果，當(dāng)F1M值較大時，測試效果比較好。

（2）準(zhǔn)確率ACC（accuracy）考察了正確預(yù)測數(shù)占總預(yù)測數(shù)的比例，當(dāng)ACC值較大時，預(yù)測效果較好。

（3）平衡錯誤率BER（balanced error rate）考察了預(yù)測錯誤數(shù)占總預(yù)測數(shù)的比例，當(dāng)BER值較小時，算法錯誤率較低。

（4）馬修相關(guān)系數(shù)MCC（matthew's correlation coefficient）體現(xiàn)了預(yù)測結(jié)果與真實數(shù)據(jù)的相關(guān)性，其變化范圍為［-1，1］：-1為完全負(fù)相關(guān)，1為完全正相關(guān)。

5.3 實驗結(jié)果

實驗中，選用WordNet在Windows平臺下最新的版本W(wǎng)ordNet 2.1作為服務(wù)標(biāo)簽語義相似度判斷的詞庫，并令算法1和算法3中的語義相似度臨界值取0.9。首先利用4.1 節(jié)中的方法，對兩類服務(wù)個體FPR 的差異進行顯著性檢驗。檢驗過程中，取K=10 000，求得p值為0.000 2。即使利用α=0.005的顯著性水平，也可以拒絕原假設(shè)。檢驗結(jié)果證明消亡與非消亡服務(wù)個體間的FPR 值差異顯著性很大，F(xiàn)PR 值可以作為區(qū)分兩類服務(wù)的特征。

5.3.1 標(biāo)簽語義模糊對實驗結(jié)果的影響

首先考慮標(biāo)簽語義模糊對預(yù)測算法的影響。將預(yù)測算法應(yīng)用在測試數(shù)據(jù)集上，考察5.2節(jié)中的指標(biāo)；同時，將沒有考慮服務(wù)標(biāo)簽語義模糊的算法作為對照組。圖3所示為兩組測試結(jié)果的準(zhǔn)確率—召回率曲線及曲線的AUC［23］。

若分類算法召回率—準(zhǔn)確率曲線的AUC=0.5，則近似為隨機分類，AUC=1則分類算法達到最佳。本文算法的AUC=0.745 3，預(yù)測分類算法的綜合效果較好。與對照組消除慮服務(wù)標(biāo)簽語義模糊的算法相比，AUC高出1.1%。觀察召回率—準(zhǔn)確率曲線后發(fā)現(xiàn)，召回率由0.3增加到0.9的這一段曲線的準(zhǔn)確率保持在0.8左右；隨著召回率的增大，準(zhǔn)確率急劇降低。因此，在保證算法準(zhǔn)確率的同時，可以通過改變閾值來提升召回率，從而使算法的準(zhǔn)確率和召回率都保持在較高的水平，預(yù)測的綜合效果更好。

5.3.2 閾值對實驗結(jié)果的影響

在算法中利用WordNet消除標(biāo)簽語義模糊，再考慮分類算法的閾值對實驗結(jié)果的影響。令Logistic回歸模型中的閾值取不同的值，分別用上述評價指標(biāo)評估算法，結(jié)果如表4所示。從表4中的預(yù)測算法評價指標(biāo)中可以看出，算法召回率隨著閾值的增大不斷降低，即算法的漏報率升高，但準(zhǔn)確率有所提高，即誤報率降低。F1M考慮了召回率和準(zhǔn)確率的綜合效果，其值先隨著閾值的增加而增大，當(dāng)閾值超過一定范圍時開始下降；ACC的變化趨勢與F1M類似，隨著閾值的增加，其值先增大后降低；與ACC對應(yīng)的BER則先降低再增加；MCC的值隨著閾值的增大先上升再下降，表示預(yù)測結(jié)果與實際數(shù)據(jù)的相關(guān)性先增大后減小。由上述分析，可以根據(jù)實際中不同的指標(biāo)需求來合理選擇閾值。

表4 不同閾值下的算法評估結(jié)果

5.4 消亡服務(wù)特點分析

進一步分析服務(wù)生態(tài)系統(tǒng)中消亡和非消亡兩類服務(wù)個體的特點，利用兩類服務(wù)個體FPR 值的經(jīng)驗分布——累計經(jīng)驗分布（Cumulative Distribution Function，CDF）［19］做定性分析。定義兩類服務(wù)個體FPR 值的經(jīng)驗分布函數(shù)：

式中：IPS=｛i｜si∈SSN且si為消亡服務(wù)個體｝，表示消亡服務(wù)個體在SSN 網(wǎng)絡(luò)中的編號集合，Nips表示集合IPS中元素的個數(shù)；IUPS=｛i｜si∈SSN且si為非消亡服務(wù)個體｝，表示非消亡服務(wù)個體在SSN 網(wǎng)絡(luò)中的編號集合，Niups表示集合IUPS元素的個數(shù)。截至2012年12月，統(tǒng)計了兩類服務(wù)個體FPR 值的經(jīng)驗分布，如圖4所示。

圖4中的兩類服務(wù)個體的FPR 經(jīng)驗分布有明顯區(qū)別：以FPR 的某一個取值為分界點，兩種服務(wù)個體的FPR 在分界點的兩側(cè)近似服從均勻分布，即消亡服務(wù)個體的FPR 值偏大，非消亡服務(wù)個體的FPR 值偏小。

進一步分析SSN 網(wǎng)絡(luò)中FPR 值大的服務(wù)個體的特點。以SSN 網(wǎng)絡(luò)中的一個服務(wù)Gowalla為例，Gowalla 的服務(wù) 標(biāo)簽有l(wèi)ocation，social，mobile，mapping，places，但服務(wù)生態(tài)系統(tǒng)中提供mapping功能的服務(wù)有Google Maps，Bing Maps等，提供location功能的服務(wù)有foursquare等，提供social功能的服務(wù)有Facebook等。雖然Gowalla服務(wù)涉及多個熱門領(lǐng)域，但每個領(lǐng)域都有提供相似功能的其他服務(wù)個體與其競爭，因此Gowalla最終從服務(wù)生態(tài)系統(tǒng)中消亡。不但Gowalla服務(wù)，而且其他FPR值大的服務(wù)個體都具有這種特點：涉及服務(wù)生態(tài)系統(tǒng)中的多個熱門領(lǐng)域，具有大而全的特點，但并沒有突出的功能特點；相反，服務(wù)生態(tài)系統(tǒng)中FPR 值小的服務(wù)大多只涉及某一個熱門領(lǐng)域，服務(wù)功能小而精，因此更容易在服務(wù)生態(tài)系統(tǒng)中存活下來。

6 結(jié)束語

隨著Web技術(shù)的快速發(fā)展和SOA 架構(gòu)的廣泛應(yīng)用，大量的Web服務(wù)被發(fā)布到Internet環(huán)境中，并在長期的協(xié)同競爭過程中形成了服務(wù)生態(tài)系統(tǒng)。本文從服務(wù)生態(tài)系統(tǒng)出發(fā)，基于Web服務(wù)競爭關(guān)系研究服務(wù)消亡的機制，提出潛在消亡服務(wù)的預(yù)測算法，分析了服務(wù)生態(tài)系統(tǒng)中消亡服務(wù)個體的特點，并最終為服務(wù)使用者和服務(wù)提供商提供建議。

具備相似功能的Web服務(wù)存在競爭關(guān)系，因此本文利用服務(wù)標(biāo)簽的相似性刻畫服務(wù)個體功能的相似性，進而構(gòu)建含權(quán)服務(wù)相似度網(wǎng)絡(luò)，量化服務(wù)個體的競爭關(guān)系。通過分析含權(quán)服務(wù)相似度網(wǎng)絡(luò)中服務(wù)個體的FPR，發(fā)現(xiàn)消亡和非消亡服務(wù)個體的FPR分布呈現(xiàn)明顯的差異性：含權(quán)服務(wù)相似度網(wǎng)絡(luò)中FPR 大的服務(wù)個體所提供的功能大多具有大而全的特點，即提供多個熱門功能，但每個功能都不夠完善，因此不容易在服務(wù)生態(tài)系統(tǒng)中生存下來；FPR小的服務(wù)個體，所提供的功能大多具有小而精的特點，即只專注某一個方面的功能，并不斷完善，因此在服務(wù)生態(tài)系統(tǒng)中生存的機會更大。

進一步通過置換檢驗的方式發(fā)現(xiàn)消亡和非消亡服務(wù)個體間FPR 值的分布差異十分顯著。因此，提出基于Logistic回歸模型的潛在消亡服務(wù)預(yù)測算法，利用服務(wù)個體的FPR 值訓(xùn)練模型，預(yù)測新加入系統(tǒng)的服務(wù)個體是否會消亡?；赑rogrammableWeb上OpenAPI數(shù)據(jù)的實證分析，表明算法的召回率、準(zhǔn)確率等指標(biāo)均在較高的水平，該方法能夠有效預(yù)測消亡服務(wù)，從而給服務(wù)使用者提供可靠的建議。

本文只考慮了服務(wù)個體之間的相似度關(guān)聯(lián)對消亡服務(wù)、服務(wù)組合質(zhì)量的影響。在后續(xù)的工作中，將進一步考慮其他服務(wù)個體關(guān)聯(lián)對服務(wù)組合質(zhì)量的影響。

［1］BARROS A，DUMAS M.The rise of Web service ecosystems［J］.IT Professional，2006，8（5）：31-37.

［2］LI Bohu，ZHANG Lin，WANG Shilong，et al.Cloud manufacturing：a new service-oriented networked manufacturing model［J］.Computer Integrated Manufacturing Systems，2010，16（1）：1-7，16（in Chinese）.［李伯虎，張 霖，王時龍，等.云制造——面向服務(wù)的網(wǎng)絡(luò)化制造新模式［J］.計算機集成制造系統(tǒng)，2010，16（1）：1-7，16.］

［3］LI Bohu，ZHANG Lin，REN Lei，et al.Further discussion on cloud manufacturing［J］.Computer Integrated Manufacturing Systems，2011，17（3）：449-457（in Chinese）.［李伯虎，張霖，任 磊，等.再論云制造［J］.計算機集成制造系統(tǒng)，2011，17（3）：449-457.］

［4］NING Da，HE Keqing，PENG Rong，et all.An automatic emerging approach for Web service semantics based on social tagging［J］.Chinese Journal of Computers，2011，38（12）：2414-2426（in Chinese）.［寧 達，何克清，彭 蓉，等.基于社會標(biāo)注的Web 服務(wù)語義自動浮現(xiàn)方法［J］.計算機學(xué)報，2011，38（12）：2414-2426.］

［5］NAGARAJAN M，VERMA K，SHETH A P，et al.Semantic interoperability of Web services-challenges and experiences［C］／／Proceedings of IEEE International Conference on Web Services.Washington，D.C.，USA：IEEE，2006：373-382.

［6］ZEIN O K，KERMARREC Y，GARLATTI S，et al.A metadata model for Web services applied to index and discover elearning services［C］／／Proceedings of the 2nd International Conference on Information and Communication Technologies.Washington，D.C.，USA：IEEE，2006：626-630.

［7］WANG Hui，F(xiàn)ENG Zhiyong，SUI Yang，et al.Service network：an infrastructure of Web services［C］／／Proceedings of International Conference on Intelligent Computing and Intelligent Systems.Washington，D.C.，USA：IEEE，2009：303-308.

［8］YUN Bensheng，YAN Junwei，LIU Min.Method to optimize Web service composition based on Bayes trust model［J］.Computer Integrated Manufacturing Systems，2010，16（5）：1103-1110（in Chinese）.［云本勝，嚴(yán)雋薇，劉 敏.基于Bayes信任模型的Web服務(wù)組合優(yōu)化方法［J］.計算機集成制造系統(tǒng)，2010，16（5）：1103-1110.］

［9］ZHENG Jian，JIANG Jianhui.Labeled transition system based decision method for Web service behavior mismatch type［J］.Computer Integrated Manufacturing Systems，2011，17（12）：2743-2751（in Chinese）.［鄭 劍，江建慧.基于標(biāo)簽轉(zhuǎn)換系統(tǒng)的Web服務(wù)行為失配類型的判定方法［J］.計算機集成制造系統(tǒng)，2011，17（12）：2743-2751.］

［10］ZHU Xilu，WANG Bai.Web service selection algorithm based on uncertain quality of service［J］.Computer Integrated Manufacturing Systems，2011，17（11）：2532-2539（in Chinese）.［祝希路，王 柏.基于不確定服務(wù)質(zhì)量的Web服務(wù)選擇算法［J］.計算機集成制造系統(tǒng)，2011，17（11）：2532-2539.］

［11］FENG Jianzhou，KONG Lingfu，WANG Xiaohuan.Web service automatic composition based on semantic relationship graph ［J］.Computer Integrated Manufacturing Systems，2012，18（2）：427-436（in Chinese）.［馮建周，孔令富，王曉寰.基于語義關(guān)系圖的Web服務(wù)自動組合方法［J］.計算機集成制造系統(tǒng)，2012，18（2）：427-436.］

［12］XIA Bofei，F(xiàn)AN Yushun，HUANG Keman.A method for predicting perishing services in a service ecosystem［C］／／Proceedings of the International Conference on Service Science.Washington，D.C.，USA：IEEE，2013：13-17.

［13］NING Da，HE Keqing，PENG Rong，et al.A multi-dimensional social tagging method for semantic Web services［C］／／Proceedings of International Conference on Services Computing.Washington，D.C.，USA：IEEE，2011：735-736.

［14］FANG Lu，WANG Lijie，LI Meng，et al.Towards automatic tagging for Web services［C］／／Proceedings of the 19th International Conference on Web Services.Washington，D.C.，USA：IEEE，2012：528-535.

［15］CHUKMOL U，BENHARKAT A N，AMGHAR Y.Enhancing Web service discovery by using collaborative tagging system［C］／／Proceedings of the 4th International Conference on Next Generation Web Services Practices.Washington，D.C.，USA：IEEE，2008：54-59.

［16］TAN Wei，ZHANG Jia，F(xiàn)OSTER I.Network analysis of scientific workflows：agateway to reuse［J］.Computer，2010，43（9）：54-61.

［17］HUANG Keman，F(xiàn)AN Yushun，TAN Wei.An empirical study of programmable Web：a network analysis on a servicemashup system［C］／／Proceedings of the 19th International Conference on Web Services.Washington，D.C.，USA：IEEE，2012：552-559.

［18］PEDERSEN T，PATWARDHAN S，MICHELIZZI J.WordNet∷similarity-measuring the relatedness of concepts［C］／／Boston，Mass.，USA：Association for Computational Linguistics，2004：1024-1025.

［19］WASSERMAN L A.All of statistics［M］.ZHANG Bo，LIU Zhonghua，WEI Qiuping，et al.transl.Beijing：SciencePress，2008：74-75，127-129（in Chinese）.［L·沃塞曼.統(tǒng)計學(xué)完全教程［M］.張 波，劉中華，魏秋萍，等，譯.北京：科學(xué)出版社，2008：74-75，127-129］.

［20］PETER D.Introductory statistics with R［M］.2nd ed.Berlin，Germany：Springer-Verlag，2008：227-247.

［21］SU L T.The relevance of recall and precision in user evaluation［J］.Journal of the American Society for Information Science，1994，45（3）：207-217.

［22］YANG Yiming.An evaluation of statistical approaches to text categorization［J］.Information Retrieval，1999，1／2（1）：69-90.