基于用戶與服務協同聚類的Web服務發現研究

摘 要:如何從大規模服務集合中快速而準確地發現目標服務是應用Web服務技術的關鍵。針對現有研究方法主要集中在基于語義的Web服務發現上，其實施難度大且適用性不強，提出一種基于服務日志挖掘的服務發現方法。該方法通過對用戶與服務進行協同聚類，縮小查詢空間，從而提高發現效率。仿真實驗表明，其在召回率與準確率上比基于關鍵字的匹配算法都有不同程度的改善，且該方法能極大地滿足服務執行時動態綁定的特性。

關鍵詞:服務匹配; 服務發現; 協同聚類; 服務挖掘

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2010)03-0986-03

doi:10.3969/j.issn.10013695.2010.03.048

Research of services discovery based on coclustering user and services

ZHU Hong-kang 1，2， YU Xue-li1

(1.School of Computer Science Software Engineering， Taiyuan University of Technology， Taiyuan 030024， China; 2.School of Mathematics  Computer Science， Shanxi Normal University， Linfen Shanxi 041000， China)

Abstract:How to discovery services for user efficiently is the key for application of the Web service technology. The current semanticbased service discovery methods are of great inconvenience and of little flexibility to be used. This paper proposed a novel service discovery method based on service log mining. The method used coclustering between user and services， reduced search space and improved discovery efficiency much. A serial of experiments illustrate the method not only enhances the recall rate and precision as discovery methods based on keyword， but also satisfy greatly the character of Web service execute time dynamic binding.

Key words:service matching; service discovery; coclustering; service mining

Web服務是一種基于網絡環境的自包含、自描述、模塊化的應用程序，通過采用一系列基于XML的標準和協議，很好地解決了跨組織、異構平臺上應用的相互連接和集成問題。近年來，隨著Web服務相關標準的持續完善和支持Web服務軟件開發平臺的不斷成熟，Web服務已成為互聯網上最為重要的一種計算資源和軟件資產。隨著Web服務數量的迅速增長，如何在Web上自動、快速、準確地找到滿足用戶目標的Web服務成為實現面向服務計算(serviceoriented computing，SOC)的關鍵問題，吸引了國內外研究者的廣泛關注。

傳統的基于UDDI的服務注冊與發現機制存在兩方面的缺陷:a)在UDDI中服務通過使用WSDL的方式進行注冊，而WSDL難以完全展現Web服務的能力，如表現服務的語義信息、服務的動態行為等;b)UDDI使用基于關鍵字的服務組織與發現，因此其服務發現的召回率與準確率都不高。研究者從兩個不同的側面對該問題展開了研究。

1)是為Web服務添加語義 特別是以Ontology作為構建工具，借助Ontology的描述和推演能力，實現Web服務的語義描述、匹配、發現、組合等方面的研究工作，代表性的工作有:基于OWLS的語義Web服務發現方法，如文獻[1];基于WSMO/WSML的語義Web服務發現方法，如文獻[2];基于WSDL擴展的語義Web服務發現方法，如文獻[3]。這是目前典型的研究方法。

2)隨著Web服務被大量執行 如何有效地挖掘這些執行信息將對服務的發現有很大的幫助。服務挖掘的概念隨即被提出[4]，考慮到Web挖掘的成功經驗，有理由相信Web服務挖掘將會進一步推動Web服務的成功應用。本文的研究可歸屬于這類研究方法。

社區服務發現通過運用社區發現技術查找部署在同一社區中具有相似或相近功能的服務，從而提高服務發現效率。與該方法不同，本文提出的服務發現方法旨在利用以往的服務訪問信息來挖掘用戶使用模式與服務的內在關聯關系，縮小查找空間，提高發現效率。

通過對服務日志的分析，筆者發現一類用戶在一段時間內總是傾向于使用某一類服務。本文首先從服務日志文件中挖掘出用戶群與頻繁使用服務類的關聯關系;基于該關聯關系提出兩種Web服務發現的實現途徑;初步實驗表明，該方法在服務發現的效率及準確率上均有一定的改善。

1 用戶與使用服務的協同聚類算法

1.1 服務日志格式定義

為了說明問題，本文定義服務日志具有如下的簡單格式:

定義1 服務日志servicesLog={logRecord}，logRecord=(servicesID，userID，stampTime)。其中:servicesID記錄訪問的服務， 可由 (url， portType， operation)惟一標志，這些信息可從WSDL文件中獲取;userID表示訪問該服務的用戶，可由(userIP，userName，userProfile)惟一標志，userProfile表示用戶的偏好信息，可缺省;stampTime記錄訪問服務的時間。表1給出一個服務日志片段。

1.2 用戶與服務關聯關系建模

設:WS={ws1，ws2，…，wsn}表示某段時間間隔內日志中服務的集合;U={u1，u2，…，um}表示某段時間間隔內用戶的集合;Φ={ω1，ω2，…，ωl}表示某段時間間隔內ui∈U使用服務sj∈WS的頻率。則:用戶與服務的關聯關系可以建模為如圖1所示的二部圖。

1.3 用戶與服務協同聚類算法

為了回答什么樣的用戶經常使用哪類服務，或者什么樣的服務經常被哪類用戶訪問，問題轉換為用戶與服務關聯二部圖的分割。

圖分割是NP完全的，但最近的研究發現譜圖分解能很好地解決該問題[5]，筆者采用文獻[6]中介紹的基于奇異值分解(SVD)的二部圖譜分解算法對用戶與服務進行協同聚類。算法1如下:

a)給出集合WS與U的帶權矩陣W，計算W的歸一化矩陣Wn=D1-1/2WD2-1/2。其中:D1和D2都是對角陣，Dl(i，i)=jWij，D2(j，j)=iWij。

b)對Wn進行奇異值分解，取p=[log2k]個左奇異向量u2，u3， …， up+1及右奇異向量v2，v3，…，vp+1 。

c)計算Z=[ D1-1/2U D2-1/2V]T。 其中:U=[ u2，u3， …， up+1];V=[ v2，v3，…，vp+1];

d)分別在p維數據Z上運行k均值聚類算法，從而得到k分割結果。

設由算法1得到用戶與服務的k個聚類分別為{U1，U2，…，Uk}及{S1，S2，…，Sk}，若一用戶ui∈Um，則表明ui經常使用Sm中的服務;同樣，若一服務sj∈Sm，則表明sj經常被Um中的用戶使用。

通過對用戶及服務關聯關系的協同聚類，可以從某類服務所關聯的用戶群中，進一步分析該類用戶的特征信息，如用戶的職業、偏好等(這些信息可從用戶profile獲得)，有針對性地設計或改進滿足用戶需求的服務;同樣，根據某類用戶所關聯的服務類，當同類用戶訪問服務時可以優先從該服務類中查找所需服務，從而提高服務發現的效率與準確率。

2 基于用戶與服務關聯聚類的服務發現

如前所述，本該提出的用戶與服務關聯聚類不僅可以作為服務使用模式的分析方法，而且可以嵌入到其他服務發現方法中，提高服務發現的效率與準確率。下面介紹將其嵌入到基于關鍵字服務發現中的兩種實現途徑。

2.1 基于關鍵字匹配的服務發現

給定一個服務請求q，服務匹配問題通常表現為計算某種相似度距離。

在基于關鍵字的服務發現方法中，Web服務可用VSM(vector space model)來表示，其元素從WSDL的document標志中獲得。請求q與服務s的相似度可通過計算請求向量q與服務向量s的余弦夾角:

sim(q，s)=|q#8226;s|‖q‖2#8226;‖s‖2

服務匹配時，可設定某個閾值ω，當sim(q，s)≥ω時，認為q與s匹配。

2.2 基于用戶與服務關聯聚類服務發現的實現途徑

實現途徑1:先使用基于關鍵字的服務發現算法得到初始匹配集，過濾日志文件中包含匹配集中服務的記錄，建立用戶與服務的關聯矩陣，用算法1進行k分割聚類，返回用戶所屬用戶類對應的服務集。其過程描述(算法2)如下:

輸入:用戶請求q;服務日志文件servicesLog;Web服務segistryRepository(SR)

輸出:與請求q匹配的服務集WSend

begin

1) WSmiddle=keywordMatching(q，WR)

//返回對服務庫中進行關鍵字匹配的服務集

2)LogRecordSet=filter(servicesLog， WSmiddle)

//用匹配集中的服務過濾日志文件

3)kPcoC(LogRecordSet)

//用算法1對過濾后的日志文件進行協同聚類

4)if u∈Um then WSend=Sm

//根據用戶所屬用戶類返回對應服務類中的服務

5)return(WSend)

end.

實現途徑2:先對日志文件進行協同聚類，得到用戶所屬用戶類對應的服務集，在該服務集上運用關鍵字匹配得到匹配集返回給用戶。其過程描述(算法3)如下:

輸入:用戶請求q;服務日志文件servicesLog

輸出:與請求q匹配的服務集WSend

begin

1)kPcoC(servicesLog)//對日志文件使用算法1進行協同聚類

2)if u∈Um then WSmiddle=Sm

//根據用戶所屬用戶類得到對應服務類

3)WSend=keywordMatching(q，Sm)

//在該服務類中運用關鍵字匹配得到最后的匹配集

4)return(WSend)

end.

3 仿真實驗分析

為了驗證基于用戶與服務關聯聚類服務發現方法的可行性和有效性，下面給出仿真實驗結果。

3.1 實驗數據產生

1)軟硬件環境

CPU為Intel Pentium Ⅳ 2.4 GHz，內存為1 GB，操作系統為Windows XP，語言編程采用Java實現。

2)Web服務的產生

Web服務采用真實的數據集，它們的WSDL文件經由andreashess網站[9]獲取，其聚集了許多站點如SALCenral[10]和Xmethods[11]上的Web服務，提供了424個Web服務描述，覆蓋了25個分類。選取其中六類:Business、Communications、News、Converter、Countryinfo、Money作為實驗用Web服務。

3)日志集的產生

鑒于目前沒有相關Web服務日志的標準平臺和標準測試數據集，這里采用模擬生成日志集作為測試用例。日志集的生成方式如下:模擬100個用戶隨機訪問六類Web服務中的服務，其產生45 000條記錄日志項作為實驗用日志集。

3.2 衡量標準

本文采用服務匹配時間、準確率和召回率三個度量標準來衡量基于關鍵字的服務匹配、與本文提出的算法2及3匹配的實驗分析。準確率和召回率的定義如下:

準確率=獲得的正確的服務匹配的正確的服務匹配個數獲得的服務匹配的總個數

召回率=獲得的正確的服務匹配個數正確的服務匹配的總個數

3.3 實驗結果分析

由于本文選取了六類(即k=6)Web服務，根據算法1，取p=「log2 k=3維奇異向量進行協同聚類，驗證基于關鍵字的匹配、算法2及3對三個度量標準的影響，結果如圖2所示。

由圖可知，盡管算法2比基于關鍵字的匹配在匹配時間上稍有提高，但其在召回率變化不大的情況下，準確率有了明顯的提高。

算法3與基于關鍵字的匹配相比，在其準確率變化不大的情況下，匹配時間卻有了顯著的提高，尤其是當服務數量增加時，其效率更加明顯。

初步實驗表明，基于用戶與服務協同聚類的服務發現算法能從不同側面改善服務發現性能，更重要的是這種發現方法滿足了服務動態綁定的需求。

4 結束語

高效的Web服務發現方法是推動Web服務技術進一步發展與應用的關鍵。當前的研究主要集中在以語義描述為基礎的匹配方法上，不同于以往的思路，本文通過挖掘服務訪問日志的方式，建立用戶與服務的關聯聚類，這不僅能夠保證服務在功能、接口上的匹配，而且能在保證發現服務質量前提下，提高服務查找效率，滿足服務執行時動態綁定的需求。本文提出方法中，聚類頻率及錯誤控制對服務發現效率的影響將是下一步研究的重點，進一步的研究包括基于日志的服務組合序列挖掘、服務間依賴約束關系挖掘、服務執行流的監控與驗證等方面。

參考文獻:

[1]

PAOLUCCI M， KAWAMURA T， PAYNE T R. Semantic matching of Web services capabilities[C]// Proc of the 1st International Semantic Web Conference. London， UK:SpringerVerlag， 2002:333-347.

[2]KELLER U， LARA R， POLLERES A. WSMO Web service discovery[R]. WSML Working Group，2004.

[3]SYEDAMAHMOOD T，SHAH G，AKKIRAJU R.Searching service repositories by combining semantic and ontological matching[C]// Proc of IEEE International Conference on Web Services. Washington DC: IEEE Computer Society， 2005:13-20.

[4]LIANG A， MILLER S， CHUNG JY. Service mining for Web service composition[C]// Proc of IEEE International Conference on Information Reuse and Integration. Las Vegas: [s.n]， 2005: 470-475.

[5]CHUNG F R K. Spectral graph theory[M].USA: American Mathematical Society， 1997.

[6]DHILLON I S. Coclustering documents and words using bipartite spectral graph partitioning[C]// Proc of the 7th ACM SIGKDD’01. New York: ACM Press， 2001:269-274.

[7]鄧水光，尹建偉，李瑩，等. 基于二分圖匹配的語義Web服務發現方法[J]. 計算機學報，2008，31(8):1364-1375.

[8]張明衛，魏偉杰，張斌，等. 基于組合服務執行信息的服務選取方法研究[J]. 計算機學報，2008，31(8):1398-1411.

[9][EB/OL]. http://www.andreashess.info/projects/annotator/ws2003.html.

[10]SALCentral [EB/OL]. http://www.salcentral.com.

[11]Xmethods [EB/OL]. http://www.xmethods.com.

[12]V AALST W M P， VERBEEK H M W. Process mining in Web services:the WebSphere case[J].IEEE Data Engineering Bulletin，2008，31(3):45-48.

[13]V AALST W M P， REIJERS H A， WEIJTERS A J M M.Business process mining: an industrial application[J]. Information Systems，2007，32(5):713-732.

[14]LIANG Q A， CHUNG J-Y， MILLER S， et al. Service pattern discovery of Web service mining in Web service registryrepository[C]// Proc of IEEE International Conference on eBusiness Engineering. Washington DC: IEEE Computer Society， 2006: 286-293.