閆紅丹， 楊懷洲

(西安石油大學(xué) 計(jì)算機(jī)學(xué)院， 西安 710065)

0 引 言

近年來(lái)，Internet的迅猛發(fā)展使其成為全球信息傳遞與共享的巨大資源庫(kù)。越來(lái)越多的網(wǎng)絡(luò)環(huán)境下的Web應(yīng)用系統(tǒng)被建立起來(lái)，Web服務(wù)也日益豐富。根據(jù)近幾年數(shù)字統(tǒng)計(jì)顯示，網(wǎng)絡(luò)上有由7 739個(gè)提供者提供有28 606個(gè)可用的Web服務(wù)[1]。那么如何從海量的Web服務(wù)中快速有效地幫用戶推薦一個(gè)優(yōu)質(zhì)的服務(wù)，就非常重要了。

Web服務(wù)作為獨(dú)立的，自描述的模塊化應(yīng)用程序，是一種松散耦合的軟件系統(tǒng)。旨在支持網(wǎng)絡(luò)上機(jī)器到機(jī)器的自動(dòng)交互，已經(jīng)普遍部署并且可以在Web上使用。這讓使用者查找、選擇和調(diào)用性能較好的Web服務(wù)變得很難。QoS通常被用于描述Web服務(wù)的非功能特性[2]，QoS的服務(wù)特性有性能(執(zhí)行時(shí)間、響應(yīng)時(shí)間、吞吐量等)、可信度(可用性、可靠性、準(zhǔn)確性、穩(wěn)定性、完整性等)和用戶滿意度等。QoS是動(dòng)態(tài)發(fā)現(xiàn)、查詢、選擇和主動(dòng)推薦服務(wù)的基礎(chǔ)[3]。但是獲取真實(shí)有效的與用戶相關(guān)的QoS屬性的值是一項(xiàng)具有挑戰(zhàn)性的任務(wù)，這就需要對(duì)QoS進(jìn)行預(yù)測(cè)。

預(yù)測(cè)較為準(zhǔn)確的QoS，就可以向用戶推薦一些水平較好且功能相同的服務(wù)。因此，如何將用戶偏好和QoS預(yù)測(cè)相結(jié)合并準(zhǔn)確地向用戶推薦優(yōu)質(zhì)的服務(wù)，是Web服務(wù)研究的熱點(diǎn)和難點(diǎn)，不僅具有重要的理論意義，還具有重大的實(shí)用價(jià)值。

1 Web服務(wù)QoS預(yù)測(cè)方法

為了更好地給用戶推薦一個(gè)優(yōu)質(zhì)的Web服務(wù)，協(xié)同過(guò)濾(collaboration filtering，CF)算法[4]作為用于Web服務(wù)QoS預(yù)測(cè)與主動(dòng)服務(wù)推薦的一個(gè)重要方法，國(guó)內(nèi)外學(xué)者都對(duì)其進(jìn)行了研究。協(xié)同過(guò)濾最先由Goldberg在1992年提出[6]，CF是通過(guò)收集其它類似用戶或Web服務(wù)的歷史QoS信息來(lái)預(yù)測(cè)當(dāng)前用戶的QoS值的方法。眾所周知協(xié)同過(guò)濾算法根據(jù)實(shí)現(xiàn)算法的推薦策略不同分為基于鄰域(Memory-based)的CF方法和基于模型(Model-based)的CF方法。接下來(lái)介紹幾種具有研究?jī)r(jià)值的協(xié)同過(guò)濾算法。

1.1 基于鄰域(Memory-based)的協(xié)同過(guò)濾算法

基于鄰域的協(xié)同過(guò)濾算法依據(jù)系統(tǒng)中已有的用戶QoS信息，在內(nèi)存中通過(guò)一定的啟發(fā)式策略實(shí)現(xiàn)活動(dòng)用戶對(duì)目標(biāo)項(xiàng)目的QoS信息預(yù)測(cè)，并通過(guò)相似度較高的一部分鄰居用戶或者Web服務(wù)來(lái)幫助預(yù)測(cè)QoS值并發(fā)布建議。Memory-based CF 分為User-based CF和Item-based CF。

1.1.1 基于用戶(User-based)的協(xié)同過(guò)濾算法

基于用戶的(User-based)協(xié)同過(guò)濾算法是基于這樣一個(gè)假設(shè):如果一些用戶對(duì)某一類服務(wù)項(xiàng)的QoS信息(如，響應(yīng)時(shí)間)比較接近，則對(duì)其它類似服務(wù)項(xiàng)的響應(yīng)時(shí)間也比較接近。相似用戶對(duì)某一item的QoS信息相似，即先計(jì)算用戶相似性，然后找到對(duì)item i 預(yù)測(cè)過(guò)的用戶，找到最相似top-k個(gè)用戶進(jìn)行預(yù)測(cè)。User-based協(xié)同過(guò)濾推薦算法的核心就是通過(guò)相似性度量方法計(jì)算出最近鄰居集合，并將最近鄰的QoS信息結(jié)果作為推薦預(yù)測(cè)結(jié)果返回給用戶。

目前主要有3種度量用戶間相似性的方法，分別是:余弦相似性、修正的余弦相似性以及皮爾遜相關(guān)系數(shù)(Pearson correlation coefficient，PCC)[4]。

(1)余弦相似性(Cosine)。余弦相似性度量方法是通過(guò)計(jì)算向量間的余弦?jiàn)A角來(lái)度量用戶間的相似性。其實(shí)現(xiàn)簡(jiǎn)單、計(jì)算速度塊，但未能體現(xiàn)出用戶QoS信息的特征。

(2)修正的余弦相似性 (Adjusted Cosine)。余弦相似性未考慮到用戶QoS信息(如，吞吐量)尺度問(wèn)題。修正的余弦相似性通過(guò)減去用戶對(duì)服務(wù)項(xiàng)的平均吞吐量，修正的余弦相似性度量方法改善了以上問(wèn)題，更多地體現(xiàn)了用戶的相關(guān)性而不是相似性。

(3)皮爾森(Pearson)相關(guān)系數(shù)。PCC不僅考慮了服務(wù)項(xiàng)的平均QoS信息，還可以有效地防止某用戶總是傾向給比另外一個(gè)用戶更高的QoS值，而二者的分值之差又始終保持一致，那么則認(rèn)為二者具有很好的相似性。

1.1.2 基于服務(wù)項(xiàng)(Item-based)的協(xié)同過(guò)濾算法

基于服務(wù)項(xiàng)的(Item-based)協(xié)同過(guò)濾是先通過(guò)計(jì)算item的相似性，然后根據(jù)item相似值尋找某一用戶下最接近預(yù)測(cè)item的top-k個(gè)items進(jìn)行預(yù)測(cè)。Item-based協(xié)同過(guò)濾算法的關(guān)鍵步驟仍然是計(jì)算項(xiàng)目之間的相似性，并選出最相似的服務(wù)項(xiàng)，這一點(diǎn)與User-based協(xié)同過(guò)濾類似。

眾多學(xué)者對(duì)基于協(xié)同過(guò)濾的QoS預(yù)測(cè)方法進(jìn)行了大量的研究?；谟脩艉头?wù)的協(xié)同過(guò)濾算法在很大程度上依賴于歷史Web服務(wù)的調(diào)用信息，每個(gè)用戶每次會(huì)從眾多的候選對(duì)象中調(diào)用一個(gè)或者多個(gè)Web服務(wù)，導(dǎo)致可用QoS數(shù)據(jù)矩陣高度稀疏的，而且一些歷史值沒(méi)有實(shí)時(shí)更新，甚至過(guò)時(shí)。因此，在稀疏和冷啟動(dòng)的場(chǎng)景下得到的預(yù)測(cè)結(jié)果不理想。同時(shí)，協(xié)同過(guò)濾算法往往會(huì)考慮top-k個(gè)相似用戶或服務(wù)，在Web服務(wù)非常多時(shí)，往往會(huì)使得參與計(jì)算的樣本集太小，導(dǎo)致結(jié)果不全面。但是如果擴(kuò)大樣本集，即K值設(shè)定較大，那么算法的效率就會(huì)受到影響。此外，因?yàn)镼oS的特性較多，上述方法也不支持多維度的QoS預(yù)測(cè)。

由于上述單一使用User-based或Item-based對(duì)QoS預(yù)測(cè)準(zhǔn)確度的不足，Z. Zheng等人[4]結(jié)合使用這2種算法，其不需要實(shí)際的Web服務(wù)調(diào)用，通過(guò)分析來(lái)自類似用戶的QoS信息，為用戶發(fā)現(xiàn)合適的Web服務(wù)就可以預(yù)測(cè)目標(biāo)Web服務(wù)的相關(guān)用戶的QoS信息。在此文中，Z. Zheng等人針對(duì)原有用于計(jì)算相似度的PCC存在未考慮重疊記錄項(xiàng)的數(shù)量對(duì)相似性計(jì)算的影響，設(shè)計(jì)出了一個(gè)具有顯著加權(quán)的用于避免出現(xiàn)高估相似度(即出現(xiàn)相似偶然性)的現(xiàn)象的一個(gè)自適應(yīng)的相似度計(jì)算方法。比之前的用于計(jì)算相似性的方法有很大的改善。

上述方法，沒(méi)有考慮QoS數(shù)據(jù)缺失甚至沒(méi)有的情況。Z. Zheng等人[5]針對(duì)此情況進(jìn)行了研究。通過(guò)給PCC增加一個(gè)參數(shù)，克服了計(jì)算用戶或項(xiàng)目相似性精度的下降，并提出了一種有效的缺失數(shù)據(jù)預(yù)測(cè)算法。該算法考慮了用戶信息和項(xiàng)目信息，分別為用戶和項(xiàng)目設(shè)置了相似性閾值，預(yù)測(cè)算法將決定是否預(yù)測(cè)丟失的數(shù)據(jù)。改進(jìn)了協(xié)同過(guò)濾算法，并且對(duì)數(shù)據(jù)的稀疏性具有更強(qiáng)的魯棒性。

1.2 基于模型(Model-based)的協(xié)同過(guò)濾算法

為了避免Memory-based中QoS矩陣稀疏性和在處理大量數(shù)據(jù)時(shí)的時(shí)效性等問(wèn)題，提出了基于模型的協(xié)同過(guò)濾技術(shù)。該方法是利用歷史數(shù)據(jù)得到一個(gè)模型，模型的建立可以使用各種機(jī)器學(xué)習(xí)的方法，再用此模型進(jìn)行預(yù)測(cè)。基于模型的協(xié)同過(guò)濾算法是一種線下學(xué)習(xí)，然后進(jìn)行線上預(yù)測(cè)。這里主要介紹了基于聚類的CF[7-11]和基于矩陣分解的方法[12-13]。

1.2.1 基于聚類的協(xié)同過(guò)濾算法

聚類是數(shù)據(jù)分析中常用的一種技術(shù)。聚類的主要任務(wù)是將數(shù)據(jù)聚類成不同的組，并且同一類中的數(shù)據(jù)比其它類別中的數(shù)據(jù)更相似。Z. Zheng等人[7]為了解決數(shù)據(jù)稀疏的問(wèn)題，提出了一種新的基于聚類的QoS預(yù)測(cè)方法。通過(guò)向框架中設(shè)置一組固定的地標(biāo)(計(jì)算機(jī))，地標(biāo)可以周期性地監(jiān)視可用的Web服務(wù)，以豐富QoS數(shù)據(jù)，從而更準(zhǔn)確地預(yù)測(cè)QoS。Marin Silic等人[8]利用K均值聚類算法來(lái)聚合以前可用的調(diào)用數(shù)據(jù)對(duì)QoS預(yù)測(cè)的可靠性問(wèn)題進(jìn)行了研究，提出了一個(gè)用于原子Web服務(wù)可靠性預(yù)測(cè)的CLUS模型，CLUS利用以前調(diào)用中收集的數(shù)據(jù)預(yù)測(cè)正在進(jìn)行的服務(wù)調(diào)用的可靠性。Marin Silic等人通過(guò)考慮調(diào)用內(nèi)容的用戶、服務(wù)和環(huán)境參數(shù)來(lái)提高當(dāng)前狀態(tài)預(yù)測(cè)模型的準(zhǔn)確性，以解決與調(diào)用內(nèi)容相關(guān)的計(jì)算性能的可伸縮性問(wèn)題。K-均值聚類是一種迭代算法，在簇間移動(dòng)項(xiàng)目直至達(dá)到所需的集合[10]。使用KMC減少搜索空間[11]。標(biāo)準(zhǔn)的KMC方法生成k個(gè)聚類，每個(gè)簇都由具有相似偏好的客戶組成，在該方法中，分別選擇任意k個(gè)客戶作為k簇的初始中心點(diǎn)。然后，將每個(gè)客戶分配到集群中，使客戶與集群中心之間的相似性最大化。A. Suresh Poobathy等人[9]對(duì)基于K-均值聚類算法提出了精化的K Means Clustering(KMC)算法。KMC是一種流行的基于數(shù)據(jù)劃分的聚類算法。用戶首先給出了聚類的個(gè)數(shù)及其對(duì)初始條件的敏感性，其次給出了線性可分聚類。并采用了遺傳算法，提高了聚類質(zhì)量。由此可見(jiàn)，基于聚類的協(xié)同過(guò)濾算法在處理數(shù)據(jù)稀疏和預(yù)測(cè)的可靠性方面有突出的優(yōu)勢(shì)。

1.2.2 基于矩陣分解的QoS預(yù)測(cè)算法

Wei Lo等人[12]針對(duì)歷史記錄中存在許多缺失的QoS值和為了避免昂貴的Web服務(wù)調(diào)用等問(wèn)題，提出了一種擴(kuò)展矩陣因式分解(extended Matrix Factorization，EMF)的方法。本框架結(jié)合關(guān)系正則化進(jìn)行缺失的QoS值預(yù)測(cè)，首先為了更準(zhǔn)確地收集人群的智慧，研究者們?cè)谟脩舳撕头?wù)端使用不同的相似性度量來(lái)識(shí)別鄰域，然后在鄰域內(nèi)系統(tǒng)地設(shè)計(jì)了2個(gè)新的關(guān)系正則化項(xiàng)。最后，將這2個(gè)術(shù)語(yǔ)合并成一個(gè)統(tǒng)一的MF框架。

Zheng等人[13]提出了一種自適應(yīng)矩陣分解(adaptive matrix factorization ，AMF)方法，其利用不同用戶觀測(cè)到的歷史QoS數(shù)據(jù)來(lái)準(zhǔn)確估計(jì)候選服務(wù)的QoS值的QoS預(yù)測(cè)問(wèn)題，同時(shí)消除了目標(biāo)用戶對(duì)額外服務(wù)調(diào)用的需求。其支持及時(shí)準(zhǔn)確的自適應(yīng)決策，可以高效地預(yù)測(cè)QoS來(lái)獲得組件服務(wù)的實(shí)時(shí)QoS信息。AMF為了適應(yīng)QoS隨時(shí)間的變化對(duì)候選服務(wù)進(jìn)行在線QoS預(yù)測(cè)，利用數(shù)據(jù)轉(zhuǎn)換、在線學(xué)習(xí)和自適應(yīng)加權(quán)等新技術(shù)，對(duì)傳統(tǒng)的矩陣分解模型進(jìn)行了顯著的擴(kuò)展。與現(xiàn)有方法相比，AMF不僅在準(zhǔn)確度上得到了很大地提高，而且保證了高效率和魯棒性，對(duì)于實(shí)現(xiàn)最佳運(yùn)行時(shí)服務(wù)適配至關(guān)重要。

基于Model-based的CF在離線階段進(jìn)行數(shù)據(jù)的預(yù)處理；在運(yùn)行階段，只有l(wèi)earned model才能用于預(yù)測(cè)，如果在系統(tǒng)中添加新的用戶項(xiàng)時(shí)，模型要定期的更新和重構(gòu)。運(yùn)用大量的技術(shù)，模型的建立和更新計(jì)算量相當(dāng)大。

1.3 混合算法

上述方法對(duì)QoS預(yù)測(cè)在Memory-based方面存在的數(shù)據(jù)稀疏性和數(shù)據(jù)集過(guò)大等問(wèn)題利用Model-based方法進(jìn)行了開(kāi)創(chuàng)性的研究，但是并未考慮Memory-based方法中用戶偏好和QoS特性的多樣性問(wèn)題。Karta[14]提出了結(jié)合基于規(guī)則和內(nèi)容的協(xié)同過(guò)濾的多維度推薦方法，從而避免和彌補(bǔ)了各推薦技術(shù)的弱點(diǎn)。

為解決用戶評(píng)分?jǐn)?shù)據(jù)極端稀疏的問(wèn)題，Sarwar BM等人[15]通過(guò)奇異值分解(singular value decomposition)減少了項(xiàng)目的空間維數(shù)。但維數(shù)的降低會(huì)導(dǎo)致QoS信息損失，特別是在項(xiàng)目空間維數(shù)很高的情況下，推薦效果難以保證。張衛(wèi)光等人[16]利用云模型在定性知識(shí)表示以及定性、定量知識(shí)轉(zhuǎn)換時(shí)的橋梁作用，提出了一種基于云模型的用戶相似度比較方法，在一定程度上克服了用戶評(píng)分?jǐn)?shù)據(jù)極端稀疏的負(fù)面影響。

針對(duì)不可信用戶提供的不可靠數(shù)據(jù)對(duì)推薦質(zhì)量的影響，Massa等人[17]提出了基于信任的協(xié)同過(guò)濾技術(shù)，即根據(jù)用戶之間信任關(guān)系推薦服務(wù)：若用戶A信任用戶B，那么用戶B向其推薦的服務(wù)一定滿足A的需求。但是并未解決如何在成千上萬(wàn)的用戶中尋找可信用戶的問(wèn)題[18]。

現(xiàn)有的用于Web服務(wù)推薦的方法，在個(gè)別方面(如：敷衍性評(píng)分、評(píng)價(jià)指標(biāo)等)還不能兼顧，還不夠成熟。隨著Web服務(wù)的使用和存在，設(shè)計(jì)有效的Web服務(wù)推薦的新方法正變得越來(lái)越重要，現(xiàn)有的Web服務(wù)發(fā)現(xiàn)和推薦方法要么集中在消亡的UDDI注冊(cè)中心[19]，要么是以關(guān)鍵字為主的Web服務(wù)搜索引擎，這些方法存在推薦性能不足和對(duì)用戶輸入的依賴程度大的缺點(diǎn)。為了向用戶推薦出一個(gè)更優(yōu)質(zhì)的Web服務(wù)，還需要人們更深入的研究。

2 結(jié)束語(yǔ)

隨著用戶對(duì)服務(wù)質(zhì)量的重視和要求的提高，Web服務(wù)的QoS預(yù)測(cè)還有很多方面需要進(jìn)行更深入的研究，主要體現(xiàn)在如下幾個(gè)方面。

(1)對(duì)于推薦系統(tǒng)存在冷啟動(dòng)(沒(méi)有用戶行為數(shù)據(jù))問(wèn)題。

(2)項(xiàng)目評(píng)分矩陣存在諸多的敷衍性評(píng)分(如：用戶對(duì)不感興趣的敷衍性評(píng)分)，不可信用戶提供的不可靠數(shù)據(jù)會(huì)誤導(dǎo)相似度計(jì)算，影響推薦質(zhì)量。

(3)現(xiàn)有的評(píng)分指標(biāo)還不夠健全，沒(méi)有統(tǒng)一的用于評(píng)價(jià)眾多推薦算法優(yōu)良的指標(biāo)。

(4)現(xiàn)有的預(yù)測(cè)算法的算法復(fù)雜度是O(mn + n2)[3-4](指改推薦系統(tǒng)有m個(gè)訓(xùn)練用戶和n個(gè)Web服務(wù)項(xiàng))，整體的計(jì)算時(shí)間復(fù)雜度與特征的個(gè)數(shù)呈線性關(guān)系,如何降低算法的復(fù)雜度，在未來(lái)非常有必要研究。

(5)由于實(shí)際環(huán)境中服務(wù)QoS值巨幅變化，因此如何使預(yù)測(cè)方法適應(yīng)QoS值的動(dòng)態(tài)變化是下一步研究的重點(diǎn)。