基于用戶興趣的Web 服務(wù)組合推薦方法研究

于珊珊，陳冬林，李 偉，蘭文姍

(1.武漢理工大學(xué) 電子商務(wù)與智能服務(wù)研究中心，湖北 武漢430070;2.新奇特車業(yè)服務(wù)股份有限公司，上海201824)

隨著Web 服務(wù)技術(shù)的日益成熟與流行，功能屬性相同或相似的Web 服務(wù)數(shù)量正在日益增多，如何從大量的Web 服務(wù)中選擇出一個最適合的服務(wù)滿足用戶需求成為研究的熱點。此外，由于單一的元服務(wù)通常很難完全滿足用戶的需求，服務(wù)組合通過組合已有的Web 服務(wù)能夠低成本且高效率地滿足用戶需求。

一般的服務(wù)組合方法可分為人工組合方法、半自動組合方法和自動組合方法3 類［1］。在服務(wù)組合管理研究中，目前面向服務(wù)組合的QoS 優(yōu)化選擇方法主要有兩種［2-3］，一種是局部優(yōu)化目標(biāo)下的服務(wù)組合，另一種是全局優(yōu)化目標(biāo)下的服務(wù)組合［4］。SUN 等研究了費用約束下QoS 最優(yōu)的元服務(wù)選擇方法［5］。TSESMETZIS 等［6］借助多選擇背包問題MCKP，建立了帶寬約束條件下企業(yè)利潤最大化的QoS 感知Web 服務(wù)決策模型。蔣哲遠等通過用戶設(shè)定的全局約束和偏好，建立了Web 服務(wù)組合QoS 指標(biāo)綜合查詢優(yōu)化模型［7］。

目前許多基于QoS 的Web 服務(wù)組合方法已經(jīng)被提出，其基本思想為采用全局優(yōu)化或者局部優(yōu)化服務(wù)組合方法，在滿足QoS 約束的前提下，通過最優(yōu)化QoS 效用函數(shù)尋找Web 服務(wù)組合方案。局部優(yōu)化Web 服務(wù)組合方法適合于對組合時間要求高，但對QoS 約束值要求寬松的場合。全局優(yōu)化服務(wù)組合方法適用于對QoS 約束要求嚴(yán)格，對組合時間相對寬松的場合。

1 服務(wù)實例匹配與發(fā)現(xiàn)方法

筆者在已有的服務(wù)組合模板基礎(chǔ)上，對模板中的服務(wù)概念與服務(wù)提供商提供的服務(wù)實例之間進行匹配。一方面采用字符串匹配算法減少復(fù)合詞匹配造成的誤差，同時利用語義相似度算法來解決字符串匹配度算法中存在的一些語義區(qū)分含糊問題。

假設(shè)sim(C1，C2)表示概念C1與C2之間的概念語義相似度，那么該算法可以表示為：

式中：sim1(C1，C2)、sim2(C1，C2)和sim3(C1，C2)分別為基于字符串、WordNet 和信息理論匹配的相似度結(jié)果;w1、w2和w3分別為3 種不同概念匹配算法的權(quán)重系數(shù)，表示在概念語義相似度算法中每種概念相似度算法所占的影響程度。

2 基于興趣度與QoS 偏好的均衡服務(wù)組合推薦方法

2.1 服務(wù)質(zhì)量QoS 指標(biāo)及組合服務(wù)QoS 的計算

2.1.1 服務(wù)質(zhì)量QoS 指標(biāo)

服務(wù)質(zhì)量QoS 指一個能夠反映服務(wù)所有非功能屬性的指標(biāo)集合，它不僅與服務(wù)本身相關(guān)，還與同服務(wù)所在的網(wǎng)絡(luò)環(huán)境有著密切的聯(lián)系［8］。

基于現(xiàn)有的研究基礎(chǔ)，筆者將服務(wù)QoS 指標(biāo)體系設(shè)計為：服務(wù)價格(Price)、響應(yīng)時間(Duration)、可用性(Availability)、成功率(Successful Rate)、安全性(Security)、服務(wù)信譽(Reputation)、服務(wù)交互性(Interactivity)和售后服務(wù)(After -sale Service)8 項指標(biāo)。

服務(wù)價格是指用戶進行網(wǎng)上訂購該服務(wù)時所需支付的金額。響應(yīng)時間是指從請求到獲得服務(wù)響應(yīng)的時間間隔，即從用戶提交服務(wù)請求到最終獲得服務(wù)所花費的總時間?？捎眯允侵阜?wù)在約定時段、約定條件下被用戶成功訪問的能力。成功率以計算一個時間段內(nèi)服務(wù)成功執(zhí)行次數(shù)與服務(wù)總請求次數(shù)的比率作為標(biāo)準(zhǔn)。安全性一般以用戶的平均打分來度量。服務(wù)信譽是衡量服務(wù)供應(yīng)商可信度的一個參數(shù)，來自于服務(wù)用戶的綜合評價情況。服務(wù)交互性指網(wǎng)站是否有很好的用戶交流方式。售后服務(wù)指用戶預(yù)訂服務(wù)成功之后，服務(wù)提供商或代理商能否及時有效地處理用戶的一些請求。服務(wù)信譽、服務(wù)交互性和售后服務(wù)都可以用戶的平均打分來衡量。

2.1.2 組合服務(wù)的QoS 計算

在組合服務(wù)的QoS 屬性計算中，除了要對組合方案中每一個單獨的服務(wù)提供商的QoS 屬性進行計算，在綜合計算時還需要基于整個組合方案進行整體QoS 計算，所采取的計算方法除了與采取的服務(wù)選擇策略有關(guān)，還與組合方案的服務(wù)組成結(jié)構(gòu)有關(guān)。

筆者采用全局最優(yōu)策略，不僅考慮當(dāng)前任務(wù)的QoS 計算，還考慮各任務(wù)節(jié)點聚合后的綜合QoS 評價值，從而使組合方案整體的QoS 能滿足限制條件。

在選擇結(jié)構(gòu)中，加入用戶興趣度這一指標(biāo)。不同組合結(jié)構(gòu)下的組合服務(wù)QoS 計算方法如表1所示，其中：N為任務(wù)數(shù)量;pi為選擇結(jié)構(gòu)中服務(wù)Si的執(zhí)行概率，且滿足∑N i=1pi=1;IDi為用戶對服務(wù)實例Si所屬的服務(wù)概念SCi的興趣度;n為循環(huán)次數(shù)。

表1 不同組合結(jié)構(gòu)下的組合QoS 計算方法

2.2 興趣度與QoS 偏好的服務(wù)組合均衡推薦

筆者采用文獻［9］中的組合服務(wù)優(yōu)化算法，并在此基礎(chǔ)上引入用戶興趣度，建立QoS 感知的組合服務(wù)選取的數(shù)學(xué)模型。該模型主要考慮如何在既定成本的約束下，使總服務(wù)組合方案QoS 最優(yōu)?？偡?wù)成本將作為服務(wù)組合過程中的約束條件，因此服務(wù)價格不參與組合服務(wù)QoS 的計算。

對于一些質(zhì)量屬性，如成功率、可用性等，其值越大則其質(zhì)量越好，屬于增量型指標(biāo)。而對于響應(yīng)時間，其值越大則其質(zhì)量越差，屬于減量型指標(biāo)。為了消除組合服務(wù)質(zhì)量中各屬性變化的不一致性，采用文獻［10］中提到的歸一化標(biāo)準(zhǔn)計算增量型和減量型屬性指標(biāo)。

每個服務(wù)提供商可通過式(2)得到其綜合質(zhì)量得分：

式中，Wk為每個質(zhì)量屬性所對應(yīng)的權(quán)重，Wk∈［0，1］，且

在現(xiàn)實情況中，用戶對服務(wù)概念的興趣度會對服務(wù)選擇造成一定的影響，考慮到該因素，筆者在綜合質(zhì)量得分的基礎(chǔ)上，加入用戶興趣度，通過式(3)得到最終服務(wù)實例得分：

式中，IDi為用戶對服務(wù)概念的興趣度。

假設(shè)一個服務(wù)組合由n個任務(wù)組成，對于每一個任務(wù)Si(i=1，2，…，n)都有一系列的服務(wù)提供商Sij(j=1，2，…，m)可執(zhí)行該任務(wù)。其中任務(wù)Si(i=1，2，…，u)順序執(zhí)行，任務(wù)Si(i=u+1，u+2，…，v)并發(fā)執(zhí)行，任務(wù)Si(i=v+1，v+2，…，n)選擇執(zhí)行，且有1 ＜u＜v＜n。因為循環(huán)結(jié)構(gòu)可視作順序結(jié)構(gòu)的重復(fù)，故不再單獨討論。

引入二進制變量yij，當(dāng)服務(wù)提供商Sij被選擇來執(zhí)行服務(wù)時，yij為1，否則為0。qijk為Sij關(guān)于第k個QoS 屬性的取值。

順序結(jié)構(gòu)的組合QoS 可表示為：

并行結(jié)構(gòu)中，只有QoS 屬性中響應(yīng)時間的組合計算方法與順序結(jié)構(gòu)不同，其余QoS 屬性的組合計算方法與順序結(jié)構(gòu)相同。并行結(jié)構(gòu)的組合QoS 可表示為：

選擇結(jié)構(gòu)的組合QoS 可表示為：

式中，pi為選擇結(jié)構(gòu)中任務(wù)Si被選擇的概率，pi∈［0，1］，且

組合服務(wù)的總QoS 值即目標(biāo)函數(shù)可表示為：

約束條件可表示為：

式中，Qpr為服務(wù)價格，是已知量;Wk和pi均為已知數(shù)據(jù)，Wk∈［0，1］且[0，1]且

3 實驗及結(jié)果分析

依據(jù)已有的服務(wù)模板，從攜程網(wǎng)上抽取的候選服務(wù)集CS1包括：航空預(yù)訂服務(wù)5 個，火車票預(yù)訂5 個，高鐵預(yù)訂4 個，酒店預(yù)訂4 個，租車服務(wù)3個，歷史古跡景點4 個，自然景觀景點3 個，門票團購5 個，普通票預(yù)定3 個。

假設(shè)S1=航空預(yù)訂服務(wù)、S2=火車票預(yù)訂、S3=高鐵預(yù)訂、S4=酒店預(yù)訂、S5=租車服務(wù)、S6=歷史古跡景點、S7=自然景觀景點、S8=門票團購、S9=普通票預(yù)定，以S1為例，候選服務(wù)提供商可表示為：S1=(S11，S12，S13，S14，S15)。由于篇幅所限，僅展示S1服務(wù)提供商的QoS 屬性值，如表2 所示。

各QoS 屬性的權(quán)重分別為W={W1，W2，W3，W4，W5，W6，W7}={0.12，0.13，0.25，0.23，0.05，0.15，0.07}，并將各屬性進行歸一化。歸一化之后的數(shù)據(jù)同樣只展示S1服務(wù)提供商的QoS 屬性值，如表3 所示。

表2 旅游組合服務(wù)中S1 服務(wù)提供商質(zhì)量屬性值

表3 歸一化后的旅游組合服務(wù)中S1 服務(wù)提供商質(zhì)量屬性值

將得到的數(shù)據(jù)代入到上述服務(wù)組合模型中，化簡為整數(shù)規(guī)劃模型，并通過Lingo 軟件求解。得到結(jié)果為航空預(yù)訂選擇服務(wù)商S15;酒店預(yù)訂選擇服務(wù)商S44;租車服務(wù)選擇服務(wù)商S53;歷史古跡選擇S61，S62，S63和S64;自然景觀選擇S71，S72，S73;團購訂票選擇服務(wù)商S85，總費用為8 396 元，是一組最優(yōu)化的組合服務(wù)。

4 結(jié)論

設(shè)計了基于用戶興趣度的服務(wù)發(fā)現(xiàn)與服務(wù)組合推薦方法，該方法包含兩個階段：一是基于興趣度的服務(wù)組合模板演化計算，二是基于興趣度與QoS 偏好的均衡服務(wù)組合推薦方法。并以在線旅游服務(wù)組合為例，將候選服務(wù)的相關(guān)數(shù)據(jù)代入基于用戶興趣度與QoS 偏好的服務(wù)組合模型中，化簡為整數(shù)規(guī)劃模型，通過Lingo 軟件求解得到最優(yōu)的服務(wù)組合方案。

實驗結(jié)果表明，通過引入用戶興趣度可以增加服務(wù)選擇的準(zhǔn)確性，使服務(wù)組合推薦結(jié)果更符合用戶的個性化需求。

［1］ MAJITHIA S，WALKER D W，GRAY W A. A framework for automated service composition in service -oriented architectures［M］. The Semantic ：Research and Applications Springer Berlin Heidelberg，2004：269 -283.

［2］ 劉冬梅，邵志清，虞才珠.用戶期望質(zhì)量驅(qū)動的Web服務(wù)優(yōu)化選?。跩］. 華東理工大學(xué)學(xué)報，2009，35(3)：416 -420.

［3］ 方其慶，劉慶華，彭曉明. QoS 全局最優(yōu)的多目標(biāo)Web 服務(wù)選擇算法［J］.計算機應(yīng)用研究，2009，26(12)：4442 -4448.

［4］ 龔小勇，朱慶生，武春嶺.支持服務(wù)質(zhì)量全局最優(yōu)和動態(tài)重計劃的Web 服務(wù)組合［J］.計算機集成制造系統(tǒng)，2008，14(10)：2068 -2075.

［5］ SUN Y，HE S Y，LEU J Y.Syndicating Web services：a QoS and user-driven approach［J］. Decision Support System，2007(43)：243 -255.

［6］ TSESMETZIS D，ROUSSAKI I.Modeling and simulation of QoS-aware Web service selection for provider profit maximization［J］.Simulation，2007，83(1)：93-106.

［7］ 蔣哲遠，韓江洪，王釗. 動態(tài)的QoS 感知Web 服務(wù)選擇和組合優(yōu)化模型［J］. 計算機學(xué)報，2009，32(5)：1014 -1025.

［8］ DOYLE R P，KAMINSKY D L.Quality of service (QoS)based planning in web services aggregation：US Patent 8676974［P］.2014-03-18.

［9］ 陳冬林，呂秋云，馬明明.面向客戶視角的QoS 集成與組合服務(wù)優(yōu)化［J］.計算機工程，2012，38(3)：49-50.

［10］ 陳麗金，周婭.基于多QoS 約束的動態(tài)Web 服務(wù)選擇研究［J］.微計算機信息，2009，25(3)：209-211.