面向Web服務(wù)組合推薦的關(guān)聯(lián)規(guī)則研究

聶規(guī)劃，羅 跡，陳冬林

(武漢理工大學(xué)經(jīng)濟(jì)學(xué)院，湖北 武漢 430070)

隨著網(wǎng)絡(luò)經(jīng)濟(jì)的飛速發(fā)展、Web服務(wù)技術(shù)的不斷成熟，越來越多的企業(yè)為實(shí)現(xiàn)業(yè)務(wù)增值、挖掘潛在用戶，將其業(yè)務(wù)功能及流程轉(zhuǎn)換為穩(wěn)定易用的標(biāo)準(zhǔn)Web服務(wù)，并將其發(fā)布和共享在網(wǎng)絡(luò)中。單個(gè)Web元服務(wù)，如Google Amazon和 eBay等[1]的基本服務(wù)之間缺乏一定的關(guān)聯(lián)，服務(wù)功能的集成性與組合性較差，難以滿足企業(yè)和用戶的需求。在面向服務(wù)的架構(gòu)(SOA)環(huán)境下，Web服務(wù)組合應(yīng)運(yùn)而生，為服務(wù)重用、組件服務(wù)間的無縫數(shù)據(jù)交換和適用服務(wù)的集成[2-3]提供了應(yīng)用基礎(chǔ)，成為企業(yè)集成的關(guān)鍵技術(shù)。Web服務(wù)組合主要通過確定不同Web服務(wù)間的順序及交互性操作來實(shí)現(xiàn)組合服務(wù)，由服務(wù)提供者重用已有的規(guī)范Web描述語言(WSDL-S)服務(wù)構(gòu)建基于Web的應(yīng)用模塊，在總體上實(shí)現(xiàn)了潛在相關(guān)性服務(wù)的發(fā)現(xiàn)，以及對各個(gè)模塊的增值，其增值主要體現(xiàn)為提高對新需求的滿足能力，提供更高層次的可用性和服務(wù)質(zhì)量(QoS)保障[4-5]。

Web服務(wù)中基本服務(wù)之間的關(guān)聯(lián)關(guān)系是衡量服務(wù)組合質(zhì)量的重要指標(biāo)[6]，會(huì)影響服務(wù)組合的執(zhí)行效率，Web服務(wù)的有效關(guān)聯(lián)為用戶提供了服務(wù)的質(zhì)量保障。然而，傳統(tǒng)的商品營銷服務(wù)只注重對某一產(chǎn)品或服務(wù)的用戶消費(fèi)行為數(shù)據(jù)分析，由分析所得結(jié)果制定相關(guān)產(chǎn)品或服務(wù)的營銷推薦策略，這種推薦方法的考慮角度較為片面，往往忽視了Web服務(wù)中基本服務(wù)之間存在的關(guān)聯(lián)性，并沒有考慮到用戶選擇Web服務(wù)的系統(tǒng)化與最優(yōu)化過程，缺乏對用戶所需所有服務(wù)的協(xié)調(diào)與組合推薦過程，使用戶失去Web服務(wù)的最優(yōu)選擇。并且，以分類為基礎(chǔ)的服務(wù)發(fā)現(xiàn)，如UDDI在發(fā)現(xiàn)Web服務(wù)之間的關(guān)聯(lián)關(guān)系方面也明顯不足，因此需要運(yùn)用關(guān)聯(lián)規(guī)則技術(shù)來彌補(bǔ)這一缺陷。

數(shù)據(jù)挖掘(data mining)技術(shù)可以從大量數(shù)據(jù)中發(fā)現(xiàn)潛在、有用的知識(shí)[7]，并通過關(guān)聯(lián)規(guī)則挖掘出不同數(shù)據(jù)項(xiàng)之間的聯(lián)系。可通過數(shù)據(jù)挖掘技術(shù)發(fā)現(xiàn)Web服務(wù)中用戶的消費(fèi)行為，并提煉出基于用戶行為的Web服務(wù)組合關(guān)聯(lián)規(guī)則，根據(jù)這些規(guī)則對用戶行為及服務(wù)進(jìn)行分析，針對用戶需求進(jìn)行Web組合智能推薦，從而完善Web服務(wù)組合的制定。筆者通過實(shí)驗(yàn)來挖掘Web服務(wù)組合中基本服務(wù)之間的關(guān)聯(lián)規(guī)則，對服務(wù)之間關(guān)聯(lián)性強(qiáng)度進(jìn)行分析與計(jì)算，可為用戶進(jìn)行合理推薦，提高了Web服務(wù)組合執(zhí)行效率和服務(wù)質(zhì)量。

1 Web服務(wù)組合的推薦過程

Web服務(wù)組合主要是指當(dāng)單個(gè)Web元服務(wù)無法滿足用戶需求時(shí)，有機(jī)集成若干個(gè)Web服務(wù)，從而形成大粒度、具有內(nèi)部流程邏輯的組合服務(wù)的過程。Web服務(wù)組合解決方案涉及到服務(wù)屬性，將單個(gè)Web元服務(wù)的服務(wù)屬性進(jìn)行有效語義關(guān)聯(lián)和匹配是服務(wù)發(fā)現(xiàn)及服務(wù)組合的基礎(chǔ)和前提。通常服務(wù)屬性包括功能屬性(functional attributes)和質(zhì)量屬性(quality attributes)，前者表示W(wǎng)eb服務(wù)的功能和執(zhí)行操作，主要用來進(jìn)行服務(wù)推廣和服務(wù)發(fā)現(xiàn)，后者主要負(fù)責(zé)服務(wù)質(zhì)量評價(jià)和服務(wù)選擇。目前Web服務(wù)組合尚無統(tǒng)一的解決方案，其中基于Web服務(wù)最優(yōu)化推薦過程的方法較為典型，如圖1所示。

圖1 Web服務(wù)組合最優(yōu)化推薦過程

該方法是一個(gè)Web服務(wù)發(fā)現(xiàn)、組合集成、評估并推薦最優(yōu)Web服務(wù)組合的過程，主要過程如下:

(1)查詢提供相同服務(wù)屬性的Web元服務(wù)，將其進(jìn)行關(guān)聯(lián)、匹配，為Web服務(wù)發(fā)現(xiàn)提供基礎(chǔ)。

(2)將Web元服務(wù)進(jìn)行映射與組合，集成為所有可執(zhí)行的Web服務(wù)組合，以供其后的篩選。

(3)在所有可執(zhí)行的Web服務(wù)組合中加入約束條件，包括相關(guān)服務(wù)質(zhì)量、組合關(guān)聯(lián)規(guī)則以及相關(guān)功能屬性等約束，篩選出符合要求的可執(zhí)行服務(wù)組合。

(4)最后將這些服務(wù)組合進(jìn)行評估，分析其服務(wù)間關(guān)聯(lián)規(guī)則，做出最優(yōu)化控制，選出最優(yōu)的Web服務(wù)組合，并對用戶進(jìn)行推薦，進(jìn)而執(zhí)行最優(yōu)化Web服務(wù)組合決策。

2 Web服務(wù)組合的關(guān)聯(lián)規(guī)則

2.1 關(guān)聯(lián)規(guī)則挖掘技術(shù)

關(guān)聯(lián)規(guī)則挖掘最早由 AGRAWAL[8]等于1993年提出，是數(shù)據(jù)挖掘中最活躍的研究領(lǐng)域之一。關(guān)聯(lián)規(guī)則是描述兩個(gè)或多個(gè)變量之間某種潛在關(guān)系的特征規(guī)則，其最初研究目的是從交易數(shù)據(jù)庫中發(fā)現(xiàn)顧客購物的行為規(guī)則，即用戶購買某些商品時(shí)有多大傾向購買另外一些商品。挖掘關(guān)聯(lián)規(guī)則，對于用戶行為分析、追加銷售、商品目錄設(shè)計(jì)、倉儲(chǔ)路線規(guī)劃等方面很有價(jià)值，并且可以挖掘出Web基本服務(wù)間的關(guān)聯(lián)關(guān)系，為Web服務(wù)組合的制定提供相關(guān)規(guī)則和依據(jù)。下面給出關(guān)聯(lián)規(guī)則挖掘部分定義[9]。

定義1設(shè)I={i1，i2，…，im}為由 m 個(gè)不同的項(xiàng)目(item)組成的集合。給定一個(gè)事務(wù)數(shù)據(jù)庫D為交易T的集合，其中交易T為項(xiàng)目的集合，并且T?I。每一個(gè)交易有對應(yīng)的唯一標(biāo)識(shí)，如事務(wù)標(biāo)識(shí)(tid)。一個(gè)關(guān)聯(lián)規(guī)則是形如X→Y的蘊(yùn)含式，這里，X?I，Y?I并且 X∩Y=?。X 為規(guī)則的前提，Y為規(guī)則的結(jié)果。

定義2支持度(support):項(xiàng)集X在事務(wù)數(shù)據(jù)庫D中的支持度是指D中包含X的交易個(gè)數(shù)與D中總交易個(gè)數(shù)之比，即

定義3置信度(confidence):對形如X→Y的關(guān)聯(lián)規(guī)則，定義規(guī)則的置信度為事務(wù)數(shù)據(jù)庫D中既包含X也包含Y的事務(wù)個(gè)數(shù)與D中包含X的事務(wù)個(gè)數(shù)之比，或者說是項(xiàng)集X∪Y的支持度與X的支持度之比，即Confidence(X→Y)=Support(X∪Y)/Support(X)。

AGRAWAL等提出的經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法Apriori[10]分為兩步:①通過用戶指定的最小支持度和最小置信度，挖掘出所有的頻繁項(xiàng)集，其中頻繁項(xiàng)集指支持度不小于用戶定義的最小支持度的項(xiàng)集。②根據(jù)挖掘得到的頻繁項(xiàng)集產(chǎn)生代表用戶行為的關(guān)聯(lián)規(guī)則。因此，挖掘關(guān)聯(lián)規(guī)則的問題等價(jià)于產(chǎn)生支持度和可信度分別大于用戶給定的最小支持度和最小可信度的關(guān)聯(lián)規(guī)則。

2.2 關(guān)聯(lián)規(guī)則挖掘?qū)嶒?yàn)

筆者以旅游服務(wù)行業(yè)為例，進(jìn)行服務(wù)間關(guān)聯(lián)規(guī)則的挖掘?qū)嶒?yàn)。首先對2010年旅游行業(yè)的用戶在線預(yù)訂情況進(jìn)行信息統(tǒng)計(jì)與分析，統(tǒng)計(jì)出在線預(yù)訂旅游服務(wù)的用戶人數(shù)的分布，統(tǒng)計(jì)結(jié)果中預(yù)訂機(jī)票1 160.5萬人，預(yù)訂酒店1 273.3萬人，預(yù)訂景點(diǎn)門票112.8萬人，預(yù)訂旅行社118.2萬人，預(yù)訂旅游團(tuán)購85.3萬人。并且發(fā)現(xiàn)經(jīng)常被用戶一起預(yù)訂的服務(wù)項(xiàng)目的組合情況，建立樣本數(shù)據(jù)Dsample如表1所示，其中 Dsample的全集 I={機(jī)票，酒店，景點(diǎn)，旅行社，旅游團(tuán)購}。

采用Matlab軟件作為關(guān)聯(lián)挖掘工具，利用經(jīng)典關(guān)聯(lián)規(guī)則挖掘算法Apriori為基本原理，將全集中的項(xiàng)目按照表1的格式，每個(gè)事務(wù)以在線預(yù)訂人數(shù)作為數(shù)據(jù)輸入，將用戶最小支持度和最小置信度分別設(shè)置為10%和60%，經(jīng)過0.438 5 s后，挖掘得到9條關(guān)聯(lián)規(guī)則。

表1 樣本數(shù)據(jù)Dsample

3 實(shí)驗(yàn)結(jié)果分析

3.1 關(guān)聯(lián)規(guī)則的評價(jià)與排序

置信度和支持度是衡量關(guān)聯(lián)規(guī)則的兩個(gè)常用的客觀評價(jià)指標(biāo)，這兩個(gè)指標(biāo)分別反映出規(guī)則的實(shí)用性和有效性。Apriori算法的目的是找出滿足最小可信度閾值和最小置信度閾值的強(qiáng)關(guān)聯(lián)規(guī)則[11]。如圖2所示，關(guān)聯(lián)規(guī)則挖掘結(jié)果界面圖分為兩部分，左半部分是挖掘得到的所有關(guān)聯(lián)規(guī)則和規(guī)則前項(xiàng)或后項(xiàng)出現(xiàn)次數(shù)統(tǒng)計(jì)，右半部分是本次挖掘相關(guān)評價(jià)指標(biāo)，包括最小支持度(Min Support)、最小置信度(Min confidence)、挖掘時(shí)間(Mining Time)和事務(wù)數(shù)量(File Size)等。

圖2 旅游服務(wù)關(guān)聯(lián)規(guī)則挖掘結(jié)果界面圖

圖2中的左上部分，顯示了每一條規(guī)則的內(nèi)容及其支持度和置信度，例如規(guī)則1:85.3→1 273.3 Sup=4 Conf=80。其中，85.3為旅游團(tuán)購服務(wù)，1 273.3為預(yù)定酒店服務(wù)，其支持度為40%，置信度為80%，整條規(guī)則表示參加了旅游團(tuán)購服務(wù)的用戶極有可能參與預(yù)定酒店服務(wù)。該條規(guī)則將旅游行業(yè)中的旅游團(tuán)購服務(wù)與預(yù)定酒店服務(wù)進(jìn)行了緊密關(guān)聯(lián)。將圖2中的規(guī)則用項(xiàng)目的形式表示如表2所示。

表2 旅游服務(wù)關(guān)聯(lián)規(guī)則挖掘結(jié)果表

在圖2左下部分顯示了規(guī)則前項(xiàng)或后項(xiàng)的出現(xiàn)次數(shù)，例如第一條:“1 273.3”→Count:7，表示酒店在整個(gè)規(guī)則的前項(xiàng)或后項(xiàng)中共出現(xiàn)了7次，即酒店是在整個(gè)關(guān)聯(lián)規(guī)則中出現(xiàn)頻率最高的規(guī)則前項(xiàng)或后項(xiàng)，表示預(yù)定酒店服務(wù)在整個(gè)Web服務(wù)中所占權(quán)重最大，與其他基本服務(wù)之間的關(guān)聯(lián)性最強(qiáng)。

本次關(guān)聯(lián)規(guī)則是按照支持度和置信度兩者的綜合指標(biāo)由高到低進(jìn)行的排序，支持度和置信度均較大的規(guī)則排列的更加靠前。當(dāng)然，關(guān)聯(lián)規(guī)則也可以采用其他指標(biāo)進(jìn)行排序[12]，如根據(jù)規(guī)則的長度、提升度、規(guī)則前項(xiàng)或后項(xiàng)的優(yōu)先級(jí)進(jìn)行排序，在排序后可以刪除對分類結(jié)果沒有影響的規(guī)則。

3.2 Web服務(wù)間關(guān)聯(lián)度的計(jì)算

為了具體量化基本W(wǎng)eb服務(wù)之間的關(guān)聯(lián)關(guān)系，通過所得關(guān)聯(lián)規(guī)則列表，可以用式(1)來計(jì)算兩個(gè)基本W(wǎng)eb服務(wù)間的統(tǒng)計(jì)關(guān)聯(lián)度:

式中:QoSStR為兩個(gè)基本服務(wù)間的統(tǒng)計(jì)關(guān)聯(lián)度;WSi和WSj為兩個(gè)基本服務(wù);r為服務(wù) WSi和WSj在挖掘?qū)嶒?yàn)中綁定執(zhí)行的次數(shù)，r的值與QoSStR的值成正比。例如預(yù)訂景點(diǎn)與預(yù)訂酒店這兩個(gè)基本服務(wù)，在挖掘得到規(guī)則的前項(xiàng)或后項(xiàng)中共綁定出現(xiàn)了4次，那么QoSStR(景點(diǎn)，酒店)=2/(1+e-4)=1.96。又如，預(yù)訂旅游團(tuán)購與預(yù)訂酒店的服務(wù)，在所有規(guī)則的前后項(xiàng)中綁定出現(xiàn)了3次，那么QoSStR(旅游團(tuán)購，酒店)=2/(1+e-3)=1.91，可以看出預(yù)訂景點(diǎn)和酒店的關(guān)聯(lián)度相較于后者更高。

由以上分析得出，基本服務(wù)之間的關(guān)聯(lián)關(guān)系會(huì)影響服務(wù)組合的執(zhí)行效率，也是衡量服務(wù)組合質(zhì)量的重要指標(biāo)。許多用戶在服務(wù)預(yù)訂過程中往往遺漏了某些項(xiàng)目，那么此時(shí)可以根據(jù)關(guān)聯(lián)規(guī)則進(jìn)行智能化推薦。例如，按照規(guī)則2所示，可以為只預(yù)訂了景點(diǎn)門票的用戶進(jìn)行預(yù)訂酒店的服務(wù)推薦;按照規(guī)則8所示，可以為在線預(yù)定了旅游團(tuán)購、景點(diǎn)門票以及機(jī)票的用戶推薦酒店的預(yù)訂。與此同時(shí)，由于各個(gè)項(xiàng)目所占的權(quán)重不同，也可以將其考慮在Web服務(wù)組合的制定中，權(quán)重大的項(xiàng)目可以被優(yōu)先推薦。因此根據(jù)這些關(guān)聯(lián)為用戶進(jìn)行相關(guān)Web服務(wù)組合的最優(yōu)化推薦，可以為用戶提供更有保障的組合服務(wù)。

4 結(jié)論

筆者針對傳統(tǒng)的商品營銷推薦策略沒有從用戶最優(yōu)化選擇角度出發(fā)，缺乏對Web服務(wù)間的關(guān)聯(lián)性協(xié)調(diào)與組合的不足，利用數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則技術(shù)對服務(wù)間的關(guān)聯(lián)關(guān)系進(jìn)行研究。通過關(guān)聯(lián)規(guī)則算法進(jìn)行挖掘?qū)嶒?yàn)得到Web服務(wù)間關(guān)聯(lián)規(guī)則，并對其進(jìn)行分析。研究Web服務(wù)間的關(guān)聯(lián)性，提高了Web服務(wù)組合的執(zhí)行效率和服務(wù)質(zhì)量，從而優(yōu)化了Web服務(wù)組合，為用戶帶來Web服務(wù)的最優(yōu)化組合推薦。

[1] WANG P，CHAO K M，LO C C.On optimal decision for QoS-aware composite service selection[J].Expert Systems with Applications，2010(37):440-449.

[2] 鄧水光，吳朝暉.Web服務(wù)組合方法綜述[J].中國科技論文在線，2008，3(2):79-84.

[3] JEONG B，CHO H，CHOONGHYUN L.On the functional quality of service(FQoS)to discover and compose interoperable web services[J].Expert Systems with Applications，2009(36):5411-5418.

[4] JONG M K，CHANG O K，ICK H K.Quality-ofservice oriented web service composition algorithm and planning architecture[J].The Journal of Systems and Software，2008(81):2079-2090.

[5] LIU M，SHEN W M，QI H，et al.An weighted ontology-based semantic similarity algorithm for web service[J].Expert Systems with Applications，2009(36):12480-12490.

[6] 代鈕，楊雷，張斌，等.支持組合服務(wù)選取的QoS模型及優(yōu)化求解[J].計(jì)算機(jī)學(xué)報(bào)，2006，29(7):1167-1178.

[7] 馬猛.關(guān)聯(lián)挖掘的若干研究[D].合肥:安徽大學(xué)圖書館，2002.

[8] AGRAWAL R.Mining association rules between sets of items in lager databases[C]//Proc ACM SIGM OD Int'l Conf Management of Data.Washington:[s.n.]，1993:207-216.

[9] 鐵治欣，陳奇，俞瑞釗.采掘關(guān)聯(lián)規(guī)則的高效并行算法[J].計(jì)算機(jī)研究與發(fā)展，1999，36(8):948-952.

[10] 熊擁軍，陳春穎.基于關(guān)聯(lián)挖掘技術(shù)的數(shù)字圖書館個(gè)性化推送服務(wù)[J].圖書情報(bào)工作，2010，54(1):125-129.

[11] 蘇占東，游福成，楊炳儒.關(guān)聯(lián)規(guī)則的綜合評價(jià)方法研究與實(shí)例驗(yàn)證[J].計(jì)算機(jī)應(yīng)用，2004，24(10):17-20.

[12] 成桂蘭，劉旭東，陳德人.基于混合聚類的個(gè)性化推薦算法[J].武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2011，33(3):379-381.