基于序列挖掘的Ｗｅｂ服務推薦研究
2007-01-01 00:00:00夏海江吳健鄧水光
計算機應用研究 2007年6期
摘 要：提出了一種全新的服務發現方法。其核心思想是通過從以往服務組合序列中發現高頻率出現的組合序列集， 然后利用該序列集進行服務推薦。給出了服務推薦系統框架；對序列模式算法進行了改進，以適應連續序列挖掘的需求， 并描述了服務推薦的匹配算法；最后通過在一個原型系統的性能測試證明服務推薦方法是可行和有效的。
關鍵詞：Web服務； 服務發現； 服務推薦; 序列挖掘
中圖分類號：TP311文獻標志碼：A
文章編號：1001-3695(2007)06-0075-04
0 引言
Web服務采用一系列基于XML 的標準和協議，很好地解決了跨組織、異構平臺上應用的相互連接和集成問題。越來越多的應用以Web服務方式出現在網絡中。軟件集成從面向組件緊密連接系統逐步過渡到面向服務松耦合系統。松耦合主要表現為服務可以動態發現、綁定和執行。動態發現服務是實現動態綁定、執行的前提，服務發現的效果直接關系組合服務的質量；因為是在執行時發現服務，在保證找到滿足需求的服務的基礎上，查詢效率顯得尤為關鍵。面對數量眾多的服務群，如何快速準確地動態發現滿足需求的服務是一個值得研究的問題。
服務發現的關鍵問題是如何描述、發布服務和如何發現合適的服務。動態發現的服務要滿足組合服務對服務的功能、服務間制約關系的需求。目前Web 服務發布、發現機制的工業界標準是UDDI和WSDL。UDDI提供了基于分類法的服務注冊中心，服務提供者通過服務注冊中心發布服務，服務請求者通過服務注冊中心發現服務；WSDL描述了技術層面的服務功能性信息，如服務操作的名稱、接口、協議等。服務查找主要是通過語法層面上的關鍵字匹配實現的。由于缺少語義支持，UDDI和WSDL在描述術語選擇上沒有相應標準，存在很大的隨意性和不確定性，容易出現一義多詞和一詞多義的情況，難以保證查準率。
針對現有工業界標準的不足，學術界將語義Web技術與Web服務相結合，采用本體論標志語言（如DAMLS及后續版本OWLS［1］）對服務進行描述。通過本體語言的復雜邏輯推理能力計算概念語義相似度，提高了服務發現的查準率，但同時也影響了查詢效率。現有研究主要是在服務的功能和靜態行為屬性描述上，在服務動態行為即服務間復雜交互和制約關系的描述上不夠充分，不足以保證服務發現的效果。
在找到滿足功能需求的服務列表后，需要綜合考慮服務的QoS質量指標，從中選取最佳的服務。服務QoS包括執行時間、費用、可靠性、可信度、安全性等方面的因素［2］。影響服務質量因素眾多，并且其中有些指標要通過訪問第三方或服務本身才能得到，進一步影響了查詢效率。因此，服務的發現效果不佳是影響服務組合效果的瓶頸問題，不能滿足動態服務發現的需求。
針對上述問題，本文提出一種服務推薦方法——基于序列挖掘的服務推薦（Recommendation of Services Based on Sequence Mining，RSBSM）。該方法利用數據挖掘技術從以往服務組合記錄中發現高頻率出現的服務組合序列；在動態綁定服務時，根據發現的高頻服務組合序列來進行服務推薦。一組服務能夠組合在一起，說明這些服務之間有著某種內在的依賴或關聯關系，服務之間在靜態屬性和動態行為上是匹配的；一組服務高頻率組合在一起，說明組合中的服務組合方式被大多數流程定義者所認可，能夠反映普遍性的規律，因此推薦的服務具有較高的服務組合質量。在服務推薦時，RSBSM方法并不需要復雜的服務在功能、行為、QoS上查詢匹配過程，而是通過與高頻服務組合序列比對查找來實現服務推薦。因此RSBSM方法在保證服務發現質量的前提下，提高了服務發現效率，達到了準確快速發現服務的目的。
1 相關工作
服務發現是當前Web服務研究的熱點之一。為了解決動態服務發現問題，研究人員提出了各自不同的解決方案。文獻[3]提出將描述邏輯應用到本體領域，將DAML+OIL本體轉換為SHIQ描述邏輯語言，實現對DAML+OIL本體的推理。文獻[4]描述了基于OWLS語義的服務請求和服務發布描述之間的匹配算法；匹配過程中通過本體推理引擎對與輸入輸出參數相對應的本體概念進行邏輯推理，得到語義匹配度，并對返回的匹配度進行排序，得到最優的服務匹配。
文獻[5]將服務分為基本服務（Elementary Service）、組合服務(Composite Service)和社區服務（Service Community）三種。其中社區服務是功能、接口相同的服務集合，服務要能夠在服務社區中被使用，就必須向社區進行注冊。在服務建模時可將某一服務設為抽象的社區服務；在運行時當社區接收到要執行操作的請求后，從當前的社區成員中選取綁定服務。文獻[6]按領域本體將服務分為不同的服務社區，用來支持服務在語義層的注冊和查詢。
文獻[7]采用分布式的P2P語義存儲和注冊機制來解決服務查詢的問題。文獻[8]采用多代理系統來進行服務查詢匹配。文獻[2]給出了全面的服務質量QoS模型定義和計算公式，以便更好地從匹配的服務組中篩選服務。文獻[9]提出了服務發現不能只考慮在服務的功能、靜態屬性層面的匹配，還要在動態行為制約關系上相一致。
這些研究從不同角度對服務發現機制和匹配算法問題進行了探討。與上述的研究不同，RSBSM方法并不是從單個服務的需求描述與服務發布描述之間匹配關系的角度來發現服務，而是把服務所在組合序列作為一個整體，通過與以往高頻率出現的服務組合序列進行匹配，以此來發現服務。
2 RSBSM體系結構
RSBSM體系結構如圖1所示。
圖1 RSBSM體系結構圖
系統由以下兩個階段組成：
（1）高頻服務序列產生階段。流程定義文件中包含有以往服務組合信息，首先通過流程解析器對流程定義文件進行解析，得到服務組合序列集，再利用序列挖掘器從服務組合序列中發現高頻服務序列集。
（2）動態服務推薦階段。在流程執行時通過服務推薦器將執行引擎中流程執行序列片段與高頻序列進行對比查找，將匹配高頻序列中相應服務推薦給執行引擎來綁定服務，達到準確快速發現調用服務的目的。
3 高頻服務序列
3．1 服務組合序列
目前服務組合大多基于工作流方式（如BPEL）的組裝，按照服務間依賴關系用流程控制方式將服務拼裝成業務流程，通過對流程定義文件的解析可以獲取服務組合序列。本文所謂的服務組合序列是指由一組順序執行服務組成的序列片段。在解析流程文件時，對于分支結構，將分支分別處理為多組序列片段；而對于循環或并發結構，可以在控制節點處直接截斷，接下來流程處理為另一序列片段。若得到的序列片段中存在抽象服務，則在抽象服務將序列片段分為兩組。為了避免得到過長序列，可設序列最大長度閾值。若序列長度超過閾值時，將序列分為兩段。組合序列中的服務綁定信息可從相應的WSDL文件獲取。
3．2 服務組合序列挖掘
序列挖掘是指相對時間或其他順序出現的序列的高頻率序列發現［10］。但序列模式挖掘主要是針對離散型的序列，即只關心項目的前后位置關系；服務組合序列挖掘主要是分析連續序列。本文采用序列模式挖掘的ApriorAll算法［11］，對算法中序列的包含定義及序列連接運算算法作了相應修改以適用于連續序列挖掘的要求。
定義2 包含。
服務序列挖掘過程與ApriorAll算法基本相同，主要區別在于包含的定義和連接算法。算法中包含(Contain)是指包含的序列必須是連續序列;而連接運算必須是連續序列的連接。
4 動態服務推薦
服務組合方式可分為靜態組合和動態組合方式。靜態組合方式在執行前綁定具體服務；動態組合方式在設計時以抽象服務代替具體服務，在執行時綁定具體服務。由于Web服務體系結構是一個松耦合集成系統，即便是事先綁定的服務也有可能在執行時變得不可用，靜態和動態組合的執行都需要動態發現綁定服務。動態綁定服務時，本文采用RSBSM方法來推薦服務，以達到在保證較好服務選取效果的前提下，快速發現服務的目的。
要動態綁定序列S中占位服務sp，用得到的高頻序列集（見第3章）與序列S進行對比匹配，將匹配的高頻序列中具體服務與sp進行綁定。因為長度大的高頻序列具有較好的服務間依賴關系，所以高頻序列集事先按長度、支持度降序排列，先比對長度較長的序列。一般來說，支持度高的序列更能反映普遍性規律，當長度一樣時，先比對支持度高的高頻序列。匹配算法基本思路是將高頻序列作為滑動窗口在序列S中移動匹配，比對時讓sp處于滑動窗口中間，以保證有較好的服務上下文的依賴關系。為了提高匹配效率，設置了最多推薦服務個數的閾値MaxNum。當查詢到服務個數超過MaxNum，直接返回，避免算法執行過深，影響算法執行效率。執行引擎在得到推薦服務集后，綁定調用第一個推薦服務，若調用時發現服務不可用，則選下一個推薦服務，依此類推。
5 原型系統DartFlow
DartFlow［12］是筆者所在課題組共同開發的一個語義服務組合的原型系統。系統主要功能是在領域本體支持下，對注冊服務信息進行語義標志，在流程執行時對流程中抽象服務動態綁定，從而實現高效動態的服務組合。本文在DartFlow基礎上對系統進行擴展，增加了RSBSM功能。擴展后系統結構（圖2）主要包括以下組成部分：
(1)服務注冊接口(SRP)，提供給用戶進行服務注冊的接口。在服務注冊時，用戶根據本體庫(OR)中領域本體對服務進行語義標志，并存儲于服務庫（SR）中。
(2)流程定義工具(FD)，提供流程定義者進行服務組合的圖形化流程定義工具。在定義流程時，用戶從SR中獲取具體服務，根據OR中領域本體進行抽象服務的定義，并將產生的流程定義文件存儲于流程庫(FR)。
(3)高頻序列產生器(FSG)。從FR中讀取流程定義并進行解析歸納，將產生的高頻服務序列存儲于高頻服務序列庫(FSR)。
(4)執行引擎(FEE)，負責流程的執行，是系統核心部件。為了以下性能測試的需要，系統對服務推薦功能作了開關設置：當需要動態綁定服務時，如果推薦功能開關設置為Enable，根據FSR中高頻服務序列進行服務推薦；否則根據OR中領域本體從SR中發現服務。
圖2 Dartflow系統結構圖
6 性能測試
為了檢驗本文提出的RSBSM的可行性和有效性，在DartFlow上分別對RSBSM方法和語義服務發現方法進行了性能對比測試。為了敘述方便，本文將后者稱為SWSD（Semantic Web Services Discovery）方法。SWSD方法服務匹配算法參見文獻[13]。
（1）測試數據。DartFlow系統中已注冊有旅游行業143個服務，采用這些服務作為測試數據集。
（2）硬件系統。CPU為Intel Pentium 2.00 GHz，內存為1 GB，操作系統為Windows XP。
（3）測試結果。首先通過對上述服務進行充分組合，定義了45個業務流程；在支持度為0.75%，最大推薦服務數為5，最長序列長度為7情況下，得到671個推薦服務集。然后定義了序列平均長度為7的30個組合序列片段，隨機將序列中某個服務設為抽象服務；采用RSBSM和SWSD方法對該抽象服務動態發現具體服務的時間進行記錄。測試結果如圖3所示。
圖3 測試結果
通過對測試結果分析可知，SWSD方法的服務發現平均時間為735 ms；RSBSM方法的服務發現平均時間為412 ms。說明RSBSM方法在服務發現效率上有了很大提高。但RSBSM方法在流程17和26中服務發現時間反而增大了，這是因為RSBSM方法對兩個流程中的抽象服務并沒有找到推薦服務，引擎還需用SWSD方法發現服務，反而增加了時間。這說明推薦系統對于個別不常見組合的流程片段支持不好。由于目前還沒有標準的測試平臺和服務測試用例，只能對一個領域內的服務充分組合來進行測試。通過測試初步證明RSBSM方法的有效性。
7 結束語
本文提出一種全新的服務發現方法，該方法從流程文件發現高頻序列集，利用高頻序列集來指導服務流程執行時動態發現選取服務，這不僅能夠保證服務在功能、接口上的匹配，而且能滿足服務間依賴約束關系。在保證發現服務質量前提下，提高了服務查找效率，滿足了服務流程執行時動態綁定服務準確高效的需求。本文提出的服務推薦方法為服務發現的研究提供了一個不同于現有服務發現機制的新方向。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
