古凌嵐
(廣東輕工職業(yè)技術學院 計算機工程系,廣東 廣州510300)
Web服務組合現(xiàn)已成為面向服務的計算模式下應用構造的主要方式,隨著面向服務技術的廣泛應用,功能相似性能相異的Web服務也越來越多,使得用戶需要花費大量時間搜索自己滿意的服務,因此,在匹配功能需求的前提下,如何快速有效地發(fā)現(xiàn)服務質量(quality of service,QoS)良好、適合用戶個性化需求的Web服務,已成為Web服務組合技術成功應用的關鍵和研究熱點。目前,許多研究成果對此進行了闡述,如文獻[1,2]在功能匹配的基礎上,結合用戶QoS約束和QoS屬性偏好,更好地滿足了用戶對服務質量的要求。文獻[3,4]基于聚類思想,對于功能相似而QoS不同的語義Web 服務先分類后排序,縮小了搜索范圍,在滿足功能和質量要求的同時,提高了服務發(fā)現(xiàn)的效率。文獻[5]以語義Web服務發(fā)現(xiàn)的結果為基礎,利用用戶和服務的情境信息、預定義的情境規(guī)則和規(guī)則等級,進一步篩選和排序得到適應用戶情境的Web服務,提高了用戶滿意度。通過分析發(fā)現(xiàn)已有研究存在以下不足:
(1)對用戶信息的利用不充分。Web服務資源的迅速膨脹,使得用戶的個性化需求逐漸成為服務發(fā)現(xiàn)的重要依據(jù),但目前主要從當前用戶背景和QoS屬性偏好來考慮,較少關注歷史數(shù)據(jù)(如歷史用戶評價、歷史用戶信息等)的利用,而歷史數(shù)據(jù)反映了用戶的行為習慣和服務體驗的滿意度,對于發(fā)現(xiàn)用戶個人偏好具有重要的價值。
(2)忽視了服務動態(tài)性和網(wǎng)絡特性對于QoS 的影響。已有研究中多采用服務提供者提供的原始QoS值,由于服務的動態(tài)性和網(wǎng)絡的不確定性,QoS的許多指標是動態(tài)變化的,直接影響了服務發(fā)現(xiàn)的有效性。
針對Web服務組合過程中服務發(fā)現(xiàn)的問題,本文提出一種基于情景的Web服務推薦方法,構建情境模型刻畫用戶和服務的信息,利用服務歷史執(zhí)行信息建立和更新服務緩存,采用K-MEANS算法實現(xiàn)服務情境聚類,并進行服務查找和初步QoS約束篩選;綜合用戶特征和用戶評價相似性,結合服務聚類集,進行用戶情境聚類,利用情境相似用戶的預測和使用頻率優(yōu)化初步推薦結果,從而最大限度地滿足了用戶個性化需求,同時也提高了服務發(fā)現(xiàn)的效率。
情境是用來描述任何一個實體情況的所有信息,本文總結文獻[6,7]情境的定義及分類工作,把情境分為用戶特征情境、服務情境和用戶評價情境3個部分。用戶特征情境包括用戶背景和平臺環(huán)境,其中用戶背景是指用戶的基本特征,包括姓名、性別、年齡、職業(yè)和民族。平臺環(huán)境是指用戶所在位置、硬件設備和網(wǎng)絡狀態(tài),硬件設備是指用戶所使用的設備,如PDA 或PC,網(wǎng)絡狀態(tài)包括網(wǎng)絡帶寬、延遲和安全性。服務情境包括服務描述和QoS 情境。其中服務描述包括服務名、輸入/輸出屬性、前提和結果。QoS情境是指經(jīng)過一段時間統(tǒng)計到的服務質量有關屬性,包括響應時間、服務費用、可用性和可靠性。用戶評價情境是指用戶對于服務的滿意程度,包括服務標識、用戶標識和用戶評分。
為了充分利用情境信息,需要建立統(tǒng)一的描述和表示模型,以刻畫服務、用戶特征和用戶評價信息,給出以下定義:
定義1 服務情境模型定義為SC=(SInfo,QoS,TStat),其中SInfo={Name,Inpu,Outp,Cond,Effe}表示服務描述,包括服務名、輸入屬性、輸出屬性、前提和結果集,QoS={Time,Cost,Avai,Reli}表示服務質量,包括響應時間、費用、可用性和可靠性,TStat為更新時間。
定義2 用戶特征情境模型定義為UC=(Feat,Plat)。其中Feat={Name,Gend,Age,Prof,Nati}表示用戶背景,包括姓名、性別、年齡、職業(yè)和民族,Plat={Loca,Devi,NStatu}表示平臺環(huán)境,包括用戶所在位置、硬件設備(PDA/PC)和網(wǎng)絡狀態(tài),NStatu={NBand,NDela,NSecu}表示網(wǎng)絡狀態(tài),包括網(wǎng)絡帶寬、網(wǎng)絡延遲和網(wǎng)絡安全性。
定義3 用戶評價情境模型定義為UR =(Uid,Sid,Score),其中Uid、Sid 和Score 分別表示用戶標識、服務標識和用戶評分。
本文方法的基本思路是:①構建情境模型描述用戶特征、服務和用戶評價信息;②收集服務運行時信息,建立和更新服務緩存;③對于相似情境的服務和用戶進行聚類;④基于服務情境發(fā)現(xiàn)符合功能和QoS 要求的初步結果;⑤基于用戶情境進一步推薦符合用戶偏好的候選服務,從而得到最適合用戶的推薦結果。服務推薦框架如圖1所示。
圖1 Web服務推薦框架
圖1中各部分的主要功能:
服務代理:負責解析用戶提出的服務請求,向服務推薦引擎提交其可識別的功能需求和QoS約束描述,返回服務推薦結果給用戶,并負責捕獲服務執(zhí)行信息,收集用戶的使用評價,提交給推薦引擎。
服務推薦引擎:由服務情境推薦、用戶情境推薦、服務緩存管理、服務聚類和用戶聚類模塊組成。事先服務聚類和用戶聚類模塊分別利用服務信息、用戶評價和用戶信息庫,對相似情境的服務和用戶進行聚類。用戶提出請求時,服務情境推薦模塊負責查找功能匹配服務所在類,若查找失敗,則通過UDDI注冊中心搜尋并返回功能和QoS匹配的具體服務,服務推薦結束;若查找成功,則計算其總的QoS值,按QoS降序排序,并剔除小于QoS約束最低容忍度的服務,得到初步推薦結果集。用戶情境推薦模塊負責查找用戶所在類,結合預測評價和使用頻率降序排序,得到最終推薦結果集,提交給服務代理。服務緩存管理模塊負責建立和更新服務緩存,包括QoS參數(shù)的更新。
UDDI注冊中心:負責Web服務的發(fā)布,并提供服務查詢功能。
為了提高服務查詢效率,本文引入了服務緩存機制。每當服務被調用時,服務代理主動進行監(jiān)測,收集該服務執(zhí)行時信息,包括服務標識、服務描述、響應時間、費用、可用性和可靠性,保存在服務信息庫作為服務緩存。當用戶請求服務時,服務推薦引擎先查詢服務緩存,查找成功則進入推薦的下一步工作,只有查詢不成功時,才需要通過UDDI注冊中心發(fā)現(xiàn)服務,隨著服務緩存中數(shù)據(jù)的不斷積累,服務查詢效率將會不斷提高。
由于Web服務的動態(tài)性,服務緩存中的數(shù)據(jù)需及時更新,一方面,對于長時間無人訪問的服務或是服務質量低下的服務定期進行刪除;另一方面,根據(jù)每次服務執(zhí)行情況,需重新評估QoS各參數(shù),以保證QoS的時效性。QoS數(shù)據(jù)是本文初步推薦服務的主要依據(jù),下面重點對于QoS參數(shù)評估的方法進行說明。
由于Web服務的動態(tài)性,使得QoS 值也隨之不斷變化,越近時間得到的QoS數(shù)據(jù)對于服務質量評估的貢獻越大,為此,引入時間衰減因子λ,每當服務被調用時,利用每次服務執(zhí)行時收集的QoS數(shù)據(jù),結合λ對QoS的各參數(shù)進行重新評估
式中:qijold、qij′——緩存中服務QoS參數(shù)、最新評估的服務QoS參數(shù),qij——服務執(zhí)行時QoS 參數(shù),λ——時間衰減因子,值域為[0,1],為了盡量準確地反映服務當前的狀態(tài),忽略時間跨度很近的衰減影響,取λ=0.5,而時間跨度過大的QoS 已無太大價值,取λ=1,因此,λ計算公式如下
式中:tcur、told——當前、QoS統(tǒng)計時間,T——有效時間跨度,T0——可忽略衰減的時間跨度,λ越大,則qijold的重要性越低。
由于QoS參數(shù)包括成本型和效益型兩種,成本型包括服務費用和響應時間,取值越大,質量越低;效益型包括可用性和可靠性,取值越大,質量越高。為了便于計算和比較,在計算服務總的QoS之前還需要對QoS 各參數(shù)進行歸一化處理,將其規(guī)格化到相同量綱上。本文采用的歸一化公式如下
式中:qij′、qij″——某QoS參數(shù)處理前、后的值,、——該項參數(shù)最大、最小值,式(a)用于成本型參數(shù),式(b)則應用于效益型參數(shù)。
聚類算法通過對n 個對象不斷地分類,形成若干個聚類集合,同一類中對象的相似度較高,而不同類中對象的差別較大。本文采用K-MEANS聚類算法,通過計算服務情境相似性,對于服務進行聚類。
服務相似性通過服務情境信息中服務描述屬性的語義相似度來體現(xiàn),計算公式如下。
式中:w1~w5——服務名稱、輸入/輸出、前提和結果屬性的權重,式中的本體間距離和屬性間語義相似度的計算參考文獻[6]中方法。
服務情境聚類的算法描述:
算法1:服務情境聚類
輸入:服務情境集合SC={sc1,sc2,…,scn}。
輸出:服務類的集合C={C1,C2,…,Ck}。
(1)任意選K 個相互間相似度小于閾值δ的服務,將其服務情境向量作為初始的聚類中心,記為c={c1,c2,…,ck};
(2)初始化服務類的集合C;
(3)REPEAT
協(xié)同過濾推薦算法是基于用戶評價項目相似性計算用戶相似性,來發(fā)現(xiàn)目標用戶的最近鄰,從而成功地預測用戶感興趣的項目。本文將其用戶相似度計算方法引入用戶情境聚類中,綜合用戶評價相似性和用戶特征相似性度量用戶情境相似度,考慮到實際上用戶評價服務的數(shù)量偏少所引起的數(shù)據(jù)稀疏性對于計算準確性的影響,在服務聚類基礎上,先計算各服務類內的用戶情境相似度,以減少相似用戶搜尋空間,而后據(jù)此進行類之間聚合,最終得到用戶聚類的集合。
(1)用戶評價相似性采用常用的Person 相關系數(shù)度量,該方法是基于用戶共同評分過的服務集合來計算的,為了避免共同評分服務較少時出現(xiàn)相似性度量的偶然性,總結文獻[8]工作,引入評分服務交集最小閾值η對于相似度計算進行修正
(2)對于用戶特征相似性,本文假設用戶特征的各屬性均可量化,包括數(shù)值型和區(qū)間型兩類,而數(shù)值型屬性分為成本型和效益型,為了便于計算采用式(3)進行了規(guī)范化處理。用戶特征相似度包括數(shù)值型和區(qū)間型屬性相似度計算。
數(shù)據(jù)型屬性相似度
區(qū)間型屬性相似度。
采用相對長度法計算區(qū)間型屬性的相似度,計算公式為
式中:L(ui)、L(vi)和L(ui∩vi)——u 和v 的第i 個屬性區(qū)間長度,以及兩個屬性間重疊長度。
(3)根據(jù)用戶評價相似性和用戶特征相似性的度量方法,可得到用戶情境相似性計算公式為
式中:w1,w2——權重系數(shù),w1+w2=1,且w1>w2,k是聚類數(shù)。
服務情境和用戶情境聚類無實時性要求,可采用離線方式,在服務推薦處理之前完成。算法描述如下:
算法2:基于情境的Web服務推薦算法
輸入:服務類的集合C、用戶類的集合U、用戶標識v、服務功能需求Sreq、服務QoS約束Qreq和用戶QoS偏好權重w。
教學手段和方法的創(chuàng)新 基于前述搭建的虛擬共享實訓平臺,本改革對變速箱拆裝實訓課程的教學手段和方法進行創(chuàng)新,將整個拆裝實訓課程劃分為課前、課中和課后三個階段(如圖1所示)。
輸出:滿足用戶個性化需求的服務集合RSfinal。
1.For each cluster Ci∈C do i∈{1,…,k} //在服務類的集合中查找功能匹配的服務
2.For si∈S do//對于功能匹配的服務計算QoS
If(qi>Qreq)//若大于QoS約束則結合用戶QoS偏好計算服務總的QoS
S′=S′∪scj;//將功能匹配且大于QoS約束的服務加入S′
3.RSfirst=sort(S′,Q);//按服務總的QoS 降序排序,得到初步推薦結果
4.For 1to m do
find v∈Ui;Ui∈U//查找用戶v所在的類
5.For each user uj∈Uido//計算RSfirst預測評價,統(tǒng)計使用頻率
6.If Frsi=0filter(rsi,RSfirst);//剔除頻率為0的服務
7.For each service rsi∈RSfirstdo
EFrsi=αQi+βPrsi,v+γFrsi;//計算每個服務得到的總體評價,權重α+β+γ=1
8.RSfinal=sort(RSfirst,EFrsj);//按總評價降序排序,得到最終推薦結果
下面以一實例說明本文Web服務推薦的方法。假設有50個Web服務,包括5個酒店訂房服務、10個訂票服務、10個天氣預報服務和25個景點查詢服務,這些服務均已被使用過,其中酒店訂房服務有6人使用過,包括一名學生u6。他現(xiàn)準備在酒店訂房,并希望酒店提供訂票服務。表1描述了酒店訂房服務使用情況,各服務的QoS和業(yè)務特點,假設已通過情境聚類得到了服務類的集合C 和用戶類的集合U(表2),為了減少計算復雜度,QoS僅列出響應時間和服務費用屬性量化后的值,U 僅包含使用過酒店訂房服務的用戶類,用戶情境也僅列出用戶背景的職業(yè)屬性。
表1 用戶使用酒店訂房服務的評價(平均評分/使用次數(shù))
表2 用戶類的集合和服務類的集合列表
采用本文方法推薦Web服務的過程:
(1)在服務類的集合C 中發(fā)現(xiàn)酒店訂房服務所在類C1,得到候選服務sc1,sc2,sc3,sc4,sc5;
(2)計算各服務總的QoS值,假設sc5總的QoS值小于用戶QoS約束被剔除,則得到sc1,sc2,sc3,sc4各自總的QoS值排名(3,1,1,2);
(3)按QoS 降序排序,得到初步推薦結果sc2,sc3,sc4,sc1;
(4)在用戶類的集合U 中發(fā)現(xiàn)用戶所在類U2;
(5)計算u6對服務sc2,sc3,sc4,sc1的預測評分(4.1,4.3,0,3.2);
(6)統(tǒng)計U2使用服務sc2,sc3,sc4,sc1的頻率(11,6,0,9);
(7)剔除頻率為0 的服務sc4,設α=0.5,β=0.3,γ=0.2,計算U2對sc2,sc1,sc3的總評價為(3.52,2.92,2.57);
(8)按總評價降序排序;
(9)得到最終推薦結果sc2,sc1,sc3返回給用戶u6。
用戶u6可優(yōu)先選sc2,其次sc1,通過本文的服務推薦算法,為用戶提供了功能匹配、達到QoS約束要求,且滿足用戶個性化需求的服務。
為了進一步驗證本文方法的可行性和有效性,本文設計了3組實驗。
實驗環(huán)境:2臺服務器CPU Intel Core 2Duo 2.1GHz,內存4G,操作系統(tǒng)Window Server 2003,數(shù)據(jù)庫SQL Server 2008。1臺PC 機CPU Intel Core 2 1.86GHz,內存2G,操作系統(tǒng)Window XP。服務器1、2 分別用于配置Web服務和運行本文的Web服務推薦算法,Web服務代理也配置在服務器2上。PC用于用戶提出請求。
實驗數(shù)據(jù):鑒于現(xiàn)在沒有標準的測試數(shù)據(jù)集,實驗數(shù)據(jù)均以模擬方式產生,共生成200個Web服務。服務的QoS屬性包括響應時間、費用、可用性和可靠性,在一定范圍內隨機生成。500個用戶已使用過,用戶評價在[0,5]整數(shù)范圍內隨機生成。實驗以響應時間為例進行測試,事先以隨機次數(shù)調用每個Web服務,以獲得真實響應時間參數(shù)。
實驗1:QoS動態(tài)變化對服務推薦的影響
設T0=60s,T=250s,響應時間約束Time=40s,選取9個功能相同的Web服務(sc1~sc9),且sc4~sc9均滿足QoS約束。利用程序模擬延遲1s,對于服務sc1~sc3減少響應時間,對于sc4~sc6增加響應時間,對于sc7~sc9不做改變,對9個服務的QoS值進行計算排序,得到最初推薦結果,共進行5次實驗。
分析表3數(shù)據(jù),當某次服務被調用時QoS 發(fā)現(xiàn)變化,該服務情境的QoS響應時間屬性也被重新評估,間隔越久的原有QoS數(shù)據(jù)重要性越低,當再次請求時,若重新評估后的響應時間不能滿足QoS約束最低容忍度,將被剔除,如服務sc4在第一次延遲后其響應時間大于40s,第二次請求時被剔除,實驗結果表明,利用每次服務運行時QoS數(shù)據(jù)動態(tài)更新服務QoS參數(shù),保證了提供給用戶的QoS數(shù)據(jù)的真實性、可信性。
表3 QoS變化時對服務推薦的影響
實驗2:本文方法與其它方法在準確性上的比較
初選20個服務,之后每次增加20 個服務,對于本文方法與通過功能和QoS匹配方法 (FQM)進行比較,圖2表明,由于本文方法中服務QoS參數(shù)得到了及時更新,在服務推薦過程中從歷史數(shù)據(jù)挖掘用戶偏好,發(fā)現(xiàn)的候選服務數(shù)相對較少,為用戶提供了滿意度較高的服務,并且隨著服務數(shù)量的增加,其效果更加明顯。
圖2 服務推薦的準確性比較
實驗3:本文方法與其它方法在時間開銷上的比較
初選20個服務,之后每次增加20 個服務,比較本文方法與FQM 發(fā)現(xiàn)候選服務所用的時間,圖3 表明,由于FQM 需通過服務器1查找候選服務,隨著服務數(shù)量增多服務發(fā)現(xiàn)所用的時間大幅度增加,而本文方法由于引入了緩存機制,僅在緩存查找失敗時,才需要訪問服務器1,并且事先對服務信息庫中的服務進行了聚類處理,使得服務推薦的實時性得到了明顯改善。
圖3 服務推薦的時間開銷比較
服務發(fā)現(xiàn)是Web服務組合成功應用的關鍵,為了解決服務發(fā)現(xiàn)的效率和用戶滿意度問題,本文提出了基于情境的服務推薦方法。該方法建立情境模型描述服務執(zhí)行信息和用戶相關信息,利用服務歷史執(zhí)行信息建立和更新服務緩存,采用K-MEANS算法進行相似情境服務的聚類,基于功能和QoS匹配實現(xiàn)初步服務推薦,通過綜合用戶特征和用戶評價相似性度量用戶情境相似度,先計算各服務類內的用戶相似度,而后據(jù)此進行類之間聚合,實現(xiàn)用戶情境聚類,利用用戶所在類對初步結果的預測評價和統(tǒng)計使用頻率,使得推薦結果得到了進一步精化和優(yōu)化,實例分析和實驗結果表明,本文方法能夠快速有效地發(fā)現(xiàn)質量良好、滿足用戶個性需求的服務。下一步工作重點是服務組合過程中服務發(fā)現(xiàn)的安全性問題。
[1]WANG P.QoS-aware Web services selection with intuitionistic fuzzy set under consumer’s vague perception [J].Expert System with Applications,2009,36 (3):4460-4466.
[2]FENG Jianzhou,KONG Lingfu.Research on web service composition based on fuzzy QoS and preference weight[J].Journal of Chinese Computer Systems,2012,33 (7):1517-1521 (in Chinese). [馮建周,孔令富.基于模糊QoS 和偏好權重的Web服務組合方法研究 [J].小型微型計算機系統(tǒng),2012,33(7):1517-1521.]
[3]BAI Wen,LI Shuyu,DU Xuezhi.Fuzzy C-means clustering semantic web service discovery [J].Computer Engineering and Design,2012,33 (11):4183-4186 (in Chinese).[白雯,李蜀瑜,杜學智.模糊C-均值聚類語義Web服務發(fā)現(xiàn) [J].計算機工程與設計,2012,33 (11):4183-4186.]
[4]MA Hua,LI Jianhua,CHEN Songqiao,et al.Business useroriented service discovery model based on ontology clustering[J].Computer Engineering,2007,33 (4):215-217 (in Chinese).[馬華,李建華,陳松喬,等.基于本體聚類的面向業(yè)務用戶服務發(fā)現(xiàn)模型 [J].計算機工程,2007,33 (4):215-217.]
[5]FENG Zaiwen,HE Keqing,LI Bing,et al.A method for semantic web service discovery based on context inference [J].Chinese Journal of Computers,2008,31 (8):1354-1363 (in Chinese).[馮在文,何克清,李兵,等.一種基于情境推理的語義Web服務發(fā)現(xiàn)方法 [J].計算機學報,2008,31 (8):1354-1363.]
[6]ZOU Jin’an.Exploration of semantic web service discovery based on QoS [J].Journal of Computer Applications,2009,29 (10):2844-2846 (in Chinese).[鄒金安.基于聚類的QoS語義Web服務發(fā)現(xiàn)研究 [J].計算機應用,2009,29 (10):2844-2846.]
[7]YANG Yueming,CHEN Lichao,XIE Binhong,et al.Study on approach of web services discovery based on clustering of users’context information [J].Computer Engineering and Design,2012,33 (4):1442-1446 (in Chinese).[楊岳明,陳立潮,謝斌紅,等.基于用戶情境聚類的Web服務發(fā)現(xiàn)方法研究 [J].計算機工程與設計,2012,33 (4):1442-1446.]
[8]HUANG Chuangguang,YIN Jian,WANG Jing,et al.Uncertain neighbors collaborative filtering recommendation algorithm [J].Chinese Journal of Computers,2010,33 (8):1369-1377 (in Chinese).[黃創(chuàng)光,印鑒,汪靜,等.不確定近鄰的協(xié)同過濾推薦算法[J].計算機學報,2010,33(8): 1369-1377.]
[9]ZHU Hongkang,YU Xueli.Research on recommendation of web services based on QoS execution information [J].Computer Engineering and Applications,2010,46 (18):237-239(in Chinese). [朱紅康,余雪麗.基于服務QoS執(zhí)行信息的Web服務推薦研究 [J].計算機工程與應用,2010,46 (18):237-239.]
[10]WANG Guoxia,LIU Heping.Survey of personalized recommendation system [J].Computer Engineering and Applications,2012,48 (7):66-76 (in Chinese). [王國霞,劉賀平.個性化推薦系統(tǒng)綜述 [J].計算機工程與應用,2012,48 (7):66-76.]
[11]WEN Junhao,QIN Jia,LIU Ling.Approach to web services selection under uncertain user preferences [J].Application Research of Computers,2010,27 (6):2147-2149 (in Chinese).[文俊浩,秦佳,柳玲.一種在用戶偏好不確定情況下的Web服務選擇方法 [J].計算機應用研究,2010,27 (6):2147-2149.]
[12]Blake M B,Nowlan M F.A web service recommender system using enhanced syntactical matching [C]//Salt Lake City,Utah,USA:Proceedings of International Conference on Web Services,2007:575-582.
[13]Aciar S,Zhang D,Simoff S,et al.Informed recommender:Basing recommendations on consumer product reviews [J].IEEE Intelligent Systems,2007,22 (3):39-47.
[14]Sufyan Beg MM,Nesar Ahmad.Web search enhancement by mining user actions [J].Information Science,2007,177(23):5203-5218.
[15]ZHU Zhengzhou,WU Zhongfu,WU Kaigui,et al.E-learning services discovery algorithm based on user satisfaction [J].Computer Engineering,2009,35 (3):71-73(in Chinese).[朱鄭州,吳中福,吳開貴,等.基于用戶滿意度的學習服務發(fā)現(xiàn)算法[J].計算機工程,2009,35 (3):71-73.]
[16]Laddawan Kulnarattana,Songsak Rongviriyapanish.A client perceived QoS model for web services selection [C]//6th International Conference on Electrical Engineering/Electronics,Computer,Telecommunications and Information Technology,2009:731-734.