基于序列挖掘的Ｗｅｂ服務推薦研究

摘 要：提出了一種全新的服務發(fā)現(xiàn)方法。其核心思想是通過從以往服務組合序列中發(fā)現(xiàn)高頻率出現(xiàn)的組合序列集， 然后利用該序列集進行服務推薦。給出了服務推薦系統(tǒng)框架；對序列模式算法進行了改進，以適應連續(xù)序列挖掘的需求， 并描述了服務推薦的匹配算法；最后通過在一個原型系統(tǒng)的性能測試證明服務推薦方法是可行和有效的。

關鍵詞：Web服務； 服務發(fā)現(xiàn)； 服務推薦; 序列挖掘

中圖分類號：TP311文獻標志碼：A

文章編號：1001-3695(2007)06-0075-04

0 引言

Web服務采用一系列基于XML 的標準和協(xié)議，很好地解決了跨組織、異構平臺上應用的相互連接和集成問題。越來越多的應用以Web服務方式出現(xiàn)在網絡中。軟件集成從面向組件緊密連接系統(tǒng)逐步過渡到面向服務松耦合系統(tǒng)。松耦合主要表現(xiàn)為服務可以動態(tài)發(fā)現(xiàn)、綁定和執(zhí)行。動態(tài)發(fā)現(xiàn)服務是實現(xiàn)動態(tài)綁定、執(zhí)行的前提，服務發(fā)現(xiàn)的效果直接關系組合服務的質量；因為是在執(zhí)行時發(fā)現(xiàn)服務，在保證找到滿足需求的服務的基礎上，查詢效率顯得尤為關鍵。面對數(shù)量眾多的服務群，如何快速準確地動態(tài)發(fā)現(xiàn)滿足需求的服務是一個值得研究的問題。

服務發(fā)現(xiàn)的關鍵問題是如何描述、發(fā)布服務和如何發(fā)現(xiàn)合適的服務。動態(tài)發(fā)現(xiàn)的服務要滿足組合服務對服務的功能、服務間制約關系的需求。目前Web 服務發(fā)布、發(fā)現(xiàn)機制的工業(yè)界標準是UDDI和WSDL。UDDI提供了基于分類法的服務注冊中心，服務提供者通過服務注冊中心發(fā)布服務，服務請求者通過服務注冊中心發(fā)現(xiàn)服務；WSDL描述了技術層面的服務功能性信息，如服務操作的名稱、接口、協(xié)議等。服務查找主要是通過語法層面上的關鍵字匹配實現(xiàn)的。由于缺少語義支持，UDDI和WSDL在描述術語選擇上沒有相應標準，存在很大的隨意性和不確定性，容易出現(xiàn)一義多詞和一詞多義的情況，難以保證查準率。

針對現(xiàn)有工業(yè)界標準的不足，學術界將語義Web技術與Web服務相結合，采用本體論標志語言（如DAMLS及后續(xù)版本OWLS［1］）對服務進行描述。通過本體語言的復雜邏輯推理能力計算概念語義相似度，提高了服務發(fā)現(xiàn)的查準率，但同時也影響了查詢效率。現(xiàn)有研究主要是在服務的功能和靜態(tài)行為屬性描述上，在服務動態(tài)行為即服務間復雜交互和制約關系的描述上不夠充分，不足以保證服務發(fā)現(xiàn)的效果。 

在找到滿足功能需求的服務列表后，需要綜合考慮服務的QoS質量指標，從中選取最佳的服務。服務QoS包括執(zhí)行時間、費用、可靠性、可信度、安全性等方面的因素［2］。影響服務質量因素眾多，并且其中有些指標要通過訪問第三方或服務本身才能得到，進一步影響了查詢效率。因此，服務的發(fā)現(xiàn)效果不佳是影響服務組合效果的瓶頸問題，不能滿足動態(tài)服務發(fā)現(xiàn)的需求。

針對上述問題，本文提出一種服務推薦方法——基于序列挖掘的服務推薦（Recommendation of Services Based on Sequence Mining，RSBSM）。該方法利用數(shù)據(jù)挖掘技術從以往服務組合記錄中發(fā)現(xiàn)高頻率出現(xiàn)的服務組合序列；在動態(tài)綁定服務時，根據(jù)發(fā)現(xiàn)的高頻服務組合序列來進行服務推薦。一組服務能夠組合在一起，說明這些服務之間有著某種內在的依賴或關聯(lián)關系，服務之間在靜態(tài)屬性和動態(tài)行為上是匹配的；一組服務高頻率組合在一起，說明組合中的服務組合方式被大多數(shù)流程定義者所認可，能夠反映普遍性的規(guī)律，因此推薦的服務具有較高的服務組合質量。在服務推薦時，RSBSM方法并不需要復雜的服務在功能、行為、QoS上查詢匹配過程，而是通過與高頻服務組合序列比對查找來實現(xiàn)服務推薦。因此RSBSM方法在保證服務發(fā)現(xiàn)質量的前提下，提高了服務發(fā)現(xiàn)效率，達到了準確快速發(fā)現(xiàn)服務的目的。

1 相關工作

服務發(fā)現(xiàn)是當前Web服務研究的熱點之一。為了解決動態(tài)服務發(fā)現(xiàn)問題，研究人員提出了各自不同的解決方案。文獻[3]提出將描述邏輯應用到本體領域，將DAML+OIL本體轉換為SHIQ描述邏輯語言，實現(xiàn)對DAML+OIL本體的推理。文獻[4]描述了基于OWLS語義的服務請求和服務發(fā)布描述之間的匹配算法；匹配過程中通過本體推理引擎對與輸入輸出參數(shù)相對應的本體概念進行邏輯推理，得到語義匹配度，并對返回的匹配度進行排序，得到最優(yōu)的服務匹配。

文獻[5]將服務分為基本服務（Elementary Service）、組合服務(Composite Service)和社區(qū)服務（Service Community）三種。其中社區(qū)服務是功能、接口相同的服務集合，服務要能夠在服務社區(qū)中被使用，就必須向社區(qū)進行注冊。在服務建模時可將某一服務設為抽象的社區(qū)服務；在運行時當社區(qū)接收到要執(zhí)行操作的請求后，從當前的社區(qū)成員中選取綁定服務。文獻[6]按領域本體將服務分為不同的服務社區(qū)，用來支持服務在語義層的注冊和查詢。

文獻[7]采用分布式的P2P語義存儲和注冊機制來解決服務查詢的問題。文獻[8]采用多代理系統(tǒng)來進行服務查詢匹配。文獻[2]給出了全面的服務質量QoS模型定義和計算公式，以便更好地從匹配的服務組中篩選服務。文獻[9]提出了服務發(fā)現(xiàn)不能只考慮在服務的功能、靜態(tài)屬性層面的匹配，還要在動態(tài)行為制約關系上相一致。

這些研究從不同角度對服務發(fā)現(xiàn)機制和匹配算法問題進行了探討。與上述的研究不同，RSBSM方法并不是從單個服務的需求描述與服務發(fā)布描述之間匹配關系的角度來發(fā)現(xiàn)服務，而是把服務所在組合序列作為一個整體，通過與以往高頻率出現(xiàn)的服務組合序列進行匹配，以此來發(fā)現(xiàn)服務。

2 RSBSM體系結構

RSBSM體系結構如圖1所示。

圖1 RSBSM體系結構圖

系統(tǒng)由以下兩個階段組成：

（1）高頻服務序列產生階段。流程定義文件中包含有以往服務組合信息，首先通過流程解析器對流程定義文件進行解析，得到服務組合序列集，再利用序列挖掘器從服務組合序列中發(fā)現(xiàn)高頻服務序列集。

（2）動態(tài)服務推薦階段。在流程執(zhí)行時通過服務推薦器將執(zhí)行引擎中流程執(zhí)行序列片段與高頻序列進行對比查找，將匹配高頻序列中相應服務推薦給執(zhí)行引擎來綁定服務，達到準確快速發(fā)現(xiàn)調用服務的目的。

3 高頻服務序列

3．1 服務組合序列

目前服務組合大多基于工作流方式（如BPEL）的組裝，按照服務間依賴關系用流程控制方式將服務拼裝成業(yè)務流程，通過對流程定義文件的解析可以獲取服務組合序列。本文所謂的服務組合序列是指由一組順序執(zhí)行服務組成的序列片段。在解析流程文件時，對于分支結構，將分支分別處理為多組序列片段；而對于循環(huán)或并發(fā)結構，可以在控制節(jié)點處直接截斷，接下來流程處理為另一序列片段。若得到的序列片段中存在抽象服務，則在抽象服務將序列片段分為兩組。為了避免得到過長序列，可設序列最大長度閾值。若序列長度超過閾值時，將序列分為兩段。組合序列中的服務綁定信息可從相應的WSDL文件獲取。

3．2 服務組合序列挖掘

序列挖掘是指相對時間或其他順序出現(xiàn)的序列的高頻率序列發(fā)現(xiàn)［10］。但序列模式挖掘主要是針對離散型的序列，即只關心項目的前后位置關系；服務組合序列挖掘主要是分析連續(xù)序列。本文采用序列模式挖掘的ApriorAll算法［11］，對算法中序列的包含定義及序列連接運算算法作了相應修改以適用于連續(xù)序列挖掘的要求。

定義2 包含。

服務序列挖掘過程與ApriorAll算法基本相同，主要區(qū)別在于包含的定義和連接算法。算法中包含(Contain)是指包含的序列必須是連續(xù)序列;而連接運算必須是連續(xù)序列的連接。

4 動態(tài)服務推薦

服務組合方式可分為靜態(tài)組合和動態(tài)組合方式。靜態(tài)組合方式在執(zhí)行前綁定具體服務；動態(tài)組合方式在設計時以抽象服務代替具體服務，在執(zhí)行時綁定具體服務。由于Web服務體系結構是一個松耦合集成系統(tǒng)，即便是事先綁定的服務也有可能在執(zhí)行時變得不可用，靜態(tài)和動態(tài)組合的執(zhí)行都需要動態(tài)發(fā)現(xiàn)綁定服務。動態(tài)綁定服務時，本文采用RSBSM方法來推薦服務，以達到在保證較好服務選取效果的前提下，快速發(fā)現(xiàn)服務的目的。

要動態(tài)綁定序列S中占位服務sp，用得到的高頻序列集（見第3章）與序列S進行對比匹配，將匹配的高頻序列中具體服務與sp進行綁定。因為長度大的高頻序列具有較好的服務間依賴關系，所以高頻序列集事先按長度、支持度降序排列，先比對長度較長的序列。一般來說，支持度高的序列更能反映普遍性規(guī)律，當長度一樣時，先比對支持度高的高頻序列。匹配算法基本思路是將高頻序列作為滑動窗口在序列S中移動匹配，比對時讓sp處于滑動窗口中間，以保證有較好的服務上下文的依賴關系。為了提高匹配效率，設置了最多推薦服務個數(shù)的閾値MaxNum。當查詢到服務個數(shù)超過MaxNum，直接返回，避免算法執(zhí)行過深，影響算法執(zhí)行效率。執(zhí)行引擎在得到推薦服務集后，綁定調用第一個推薦服務，若調用時發(fā)現(xiàn)服務不可用，則選下一個推薦服務，依此類推。

5 原型系統(tǒng)DartFlow

DartFlow［12］是筆者所在課題組共同開發(fā)的一個語義服務組合的原型系統(tǒng)。系統(tǒng)主要功能是在領域本體支持下，對注冊服務信息進行語義標志，在流程執(zhí)行時對流程中抽象服務動態(tài)綁定，從而實現(xiàn)高效動態(tài)的服務組合。本文在DartFlow基礎上對系統(tǒng)進行擴展，增加了RSBSM功能。擴展后系統(tǒng)結構（圖2）主要包括以下組成部分：

(1)服務注冊接口(SRP)，提供給用戶進行服務注冊的接口。在服務注冊時，用戶根據(jù)本體庫(OR)中領域本體對服務進行語義標志，并存儲于服務庫（SR）中。

(2)流程定義工具(FD)，提供流程定義者進行服務組合的圖形化流程定義工具。在定義流程時，用戶從SR中獲取具體服務，根據(jù)OR中領域本體進行抽象服務的定義，并將產生的流程定義文件存儲于流程庫(FR)。

(3)高頻序列產生器(FSG)。從FR中讀取流程定義并進行解析歸納，將產生的高頻服務序列存儲于高頻服務序列庫(FSR)。

(4)執(zhí)行引擎(FEE)，負責流程的執(zhí)行，是系統(tǒng)核心部件。為了以下性能測試的需要，系統(tǒng)對服務推薦功能作了開關設置：當需要動態(tài)綁定服務時，如果推薦功能開關設置為Enable，根據(jù)FSR中高頻服務序列進行服務推薦；否則根據(jù)OR中領域本體從SR中發(fā)現(xiàn)服務。 

圖2 Dartflow系統(tǒng)結構圖

6 性能測試

為了檢驗本文提出的RSBSM的可行性和有效性，在DartFlow上分別對RSBSM方法和語義服務發(fā)現(xiàn)方法進行了性能對比測試。為了敘述方便，本文將后者稱為SWSD（Semantic Web Services Discovery）方法。SWSD方法服務匹配算法參見文獻[13]。

（1）測試數(shù)據(jù)。DartFlow系統(tǒng)中已注冊有旅游行業(yè)143個服務，采用這些服務作為測試數(shù)據(jù)集。

（2）硬件系統(tǒng)。CPU為Intel Pentium 2.00 GHz，內存為1 GB，操作系統(tǒng)為Windows XP。

（3）測試結果。首先通過對上述服務進行充分組合，定義了45個業(yè)務流程；在支持度為0.75%，最大推薦服務數(shù)為5，最長序列長度為7情況下，得到671個推薦服務集。然后定義了序列平均長度為7的30個組合序列片段，隨機將序列中某個服務設為抽象服務；采用RSBSM和SWSD方法對該抽象服務動態(tài)發(fā)現(xiàn)具體服務的時間進行記錄。測試結果如圖3所示。

圖3 測試結果

通過對測試結果分析可知，SWSD方法的服務發(fā)現(xiàn)平均時間為735 ms；RSBSM方法的服務發(fā)現(xiàn)平均時間為412 ms。說明RSBSM方法在服務發(fā)現(xiàn)效率上有了很大提高。但RSBSM方法在流程17和26中服務發(fā)現(xiàn)時間反而增大了，這是因為RSBSM方法對兩個流程中的抽象服務并沒有找到推薦服務，引擎還需用SWSD方法發(fā)現(xiàn)服務，反而增加了時間。這說明推薦系統(tǒng)對于個別不常見組合的流程片段支持不好。由于目前還沒有標準的測試平臺和服務測試用例，只能對一個領域內的服務充分組合來進行測試。通過測試初步證明RSBSM方法的有效性。

7 結束語

本文提出一種全新的服務發(fā)現(xiàn)方法，該方法從流程文件發(fā)現(xiàn)高頻序列集，利用高頻序列集來指導服務流程執(zhí)行時動態(tài)發(fā)現(xiàn)選取服務，這不僅能夠保證服務在功能、接口上的匹配，而且能滿足服務間依賴約束關系。在保證發(fā)現(xiàn)服務質量前提下，提高了服務查找效率，滿足了服務流程執(zhí)行時動態(tài)綁定服務準確高效的需求。本文提出的服務推薦方法為服務發(fā)現(xiàn)的研究提供了一個不同于現(xiàn)有服務發(fā)現(xiàn)機制的新方向。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。