閆紅丹， 楊懷洲

(西安石油大學 計算機學院， 西安 710065)

0 引 言

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

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

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

1 Web服務QoS預測方法

為了更好地給用戶推薦一個優(yōu)質的Web服務，協同過濾(collaboration filtering，CF)算法[4]作為用于Web服務QoS預測與主動服務推薦的一個重要方法，國內外學者都對其進行了研究。協同過濾最先由Goldberg在1992年提出[6]，CF是通過收集其它類似用戶或Web服務的歷史QoS信息來預測當前用戶的QoS值的方法。眾所周知協同過濾算法根據實現算法的推薦策略不同分為基于鄰域(Memory-based)的CF方法和基于模型(Model-based)的CF方法。接下來介紹幾種具有研究價值的協同過濾算法。

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

基于鄰域的協同過濾算法依據系統中已有的用戶QoS信息，在內存中通過一定的啟發(fā)式策略實現活動用戶對目標項目的QoS信息預測，并通過相似度較高的一部分鄰居用戶或者Web服務來幫助預測QoS值并發(fā)布建議。Memory-based CF 分為User-based CF和Item-based CF。

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

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

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

(1)余弦相似性(Cosine)。余弦相似性度量方法是通過計算向量間的余弦夾角來度量用戶間的相似性。其實現簡單、計算速度塊，但未能體現出用戶QoS信息的特征。

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

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

1.1.2 基于服務項(Item-based)的協同過濾算法

基于服務項的(Item-based)協同過濾是先通過計算item的相似性，然后根據item相似值尋找某一用戶下最接近預測item的top-k個items進行預測。Item-based協同過濾算法的關鍵步驟仍然是計算項目之間的相似性，并選出最相似的服務項，這一點與User-based協同過濾類似。

眾多學者對基于協同過濾的QoS預測方法進行了大量的研究?；谟脩艉头盏膮f同過濾算法在很大程度上依賴于歷史Web服務的調用信息，每個用戶每次會從眾多的候選對象中調用一個或者多個Web服務，導致可用QoS數據矩陣高度稀疏的，而且一些歷史值沒有實時更新，甚至過時。因此，在稀疏和冷啟動的場景下得到的預測結果不理想。同時，協同過濾算法往往會考慮top-k個相似用戶或服務，在Web服務非常多時，往往會使得參與計算的樣本集太小，導致結果不全面。但是如果擴大樣本集，即K值設定較大，那么算法的效率就會受到影響。此外，因為QoS的特性較多，上述方法也不支持多維度的QoS預測。

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

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

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

為了避免Memory-based中QoS矩陣稀疏性和在處理大量數據時的時效性等問題，提出了基于模型的協同過濾技術。該方法是利用歷史數據得到一個模型，模型的建立可以使用各種機器學習的方法，再用此模型進行預測?；谀Ｐ偷膮f同過濾算法是一種線下學習，然后進行線上預測。這里主要介紹了基于聚類的CF[7-11]和基于矩陣分解的方法[12-13]。

1.2.1 基于聚類的協同過濾算法

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

1.2.2 基于矩陣分解的QoS預測算法

Wei Lo等人[12]針對歷史記錄中存在許多缺失的QoS值和為了避免昂貴的Web服務調用等問題，提出了一種擴展矩陣因式分解(extended Matrix Factorization，EMF)的方法。本框架結合關系正則化進行缺失的QoS值預測，首先為了更準確地收集人群的智慧，研究者們在用戶端和服務端使用不同的相似性度量來識別鄰域，然后在鄰域內系統地設計了2個新的關系正則化項。最后，將這2個術語合并成一個統一的MF框架。

Zheng等人[13]提出了一種自適應矩陣分解(adaptive matrix factorization ，AMF)方法，其利用不同用戶觀測到的歷史QoS數據來準確估計候選服務的QoS值的QoS預測問題，同時消除了目標用戶對額外服務調用的需求。其支持及時準確的自適應決策，可以高效地預測QoS來獲得組件服務的實時QoS信息。AMF為了適應QoS隨時間的變化對候選服務進行在線QoS預測，利用數據轉換、在線學習和自適應加權等新技術，對傳統的矩陣分解模型進行了顯著的擴展。與現有方法相比，AMF不僅在準確度上得到了很大地提高，而且保證了高效率和魯棒性，對于實現最佳運行時服務適配至關重要。

基于Model-based的CF在離線階段進行數據的預處理；在運行階段，只有l(wèi)earned model才能用于預測，如果在系統中添加新的用戶項時，模型要定期的更新和重構。運用大量的技術，模型的建立和更新計算量相當大。

1.3 混合算法

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

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

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

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

2 結束語

隨著用戶對服務質量的重視和要求的提高，Web服務的QoS預測還有很多方面需要進行更深入的研究，主要體現在如下幾個方面。

(1)對于推薦系統存在冷啟動(沒有用戶行為數據)問題。

(2)項目評分矩陣存在諸多的敷衍性評分(如：用戶對不感興趣的敷衍性評分)，不可信用戶提供的不可靠數據會誤導相似度計算，影響推薦質量。

(3)現有的評分指標還不夠健全，沒有統一的用于評價眾多推薦算法優(yōu)良的指標。

(4)現有的預測算法的算法復雜度是O(mn + n2)[3-4](指改推薦系統有m個訓練用戶和n個Web服務項)，整體的計算時間復雜度與特征的個數呈線性關系,如何降低算法的復雜度，在未來非常有必要研究。

(5)由于實際環(huán)境中服務QoS值巨幅變化，因此如何使預測方法適應QoS值的動態(tài)變化是下一步研究的重點。