基于QoS感知的Web服務(wù)推薦算法綜述

高文斌　董晨辰　王 睿　胡谷雨

摘? 要： 隨著Web服務(wù)數(shù)量的迅速增長(zhǎng)，服務(wù)過載的問題逐步顯現(xiàn)。為了解決服務(wù)過載的問題，基于服務(wù)質(zhì)量（Quality of Service，QoS）感知的服務(wù)推薦成為了服務(wù)計(jì)算領(lǐng)域的研究熱點(diǎn)。從起初的基于協(xié)同過濾算法到目前基于深度學(xué)習(xí)的服務(wù)推薦算法，這些算法從各個(gè)角度提升著服務(wù)推薦的精度。文章以算法的改進(jìn)過程為主線，對(duì)主要的服務(wù)推薦算法及其存在的弊端進(jìn)行了分析與總結(jié)，并對(duì)未來服務(wù)推薦算法的發(fā)展進(jìn)行了展望。

關(guān)鍵詞： 服務(wù)質(zhì)量; 服務(wù)過載; 服務(wù)推薦算法; 分析

中圖分類號(hào)：TP393? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：1006-8228（2022）03-01-04

Abstract： With the rapid growth of the number of Web Services， the problem of service overload has gradually emerged. To relieve service overload， the QoS-aware service recommendation has become a hot research topic in the field of service computing. Whether the original collaborative filtering algorithm or the current service recommendation algorithms based on deep learning， these algorithms applied in the field of service recommendation have been improving the accuracy of service recommendation from all angles. Taking the improvement process of the algorithm as the main line， this paper analyzes and summarizes the main algorithms of service recommendation and their disadvantages， and prospects the development of service recommendation algorithm in the future.

Key words： Quality of Service; service overload; service recommendation algorithm; analysis

0 引言

隨著服務(wù)化理念的推廣和面向服務(wù)的計(jì)算模式（SOC）的廣泛應(yīng)用，越來越多的企業(yè)選擇為用戶提供服務(wù)化的產(chǎn)品。作為面向服務(wù)的架構(gòu)（SOA）最主流的實(shí)現(xiàn)方式，Web服務(wù)（Web Service，ws）的數(shù)量成指數(shù)級(jí)增長(zhǎng)。Web服務(wù)模型中包含三個(gè)實(shí)體：服務(wù)提供者、服務(wù)注冊(cè)中心、服務(wù)消費(fèi)者。

圖1顯示了傳統(tǒng)Web服務(wù)模型的基本結(jié)構(gòu)。服務(wù)提供者將其提供的服務(wù)信息注冊(cè)到服務(wù)注冊(cè)中心，這一過程稱為服務(wù)發(fā)布。服務(wù)發(fā)現(xiàn)指服務(wù)消費(fèi)者向服務(wù)注冊(cè)中心發(fā)送攜帶服務(wù)功能性需求的服務(wù)調(diào)用需求，服務(wù)注冊(cè)中心通過檢索服務(wù)數(shù)據(jù)庫(kù)，為服務(wù)消費(fèi)者匹配滿足功能性需求的服務(wù)的過程。服務(wù)消費(fèi)者從服務(wù)注冊(cè)中心獲取到服務(wù)的注冊(cè)信息后，直接訪問服務(wù)提供者提供的服務(wù)，無需再經(jīng)過注冊(cè)中心，這一過程稱為服務(wù)綁定。

然而截至2021年6月29日，僅programableweb上發(fā)布的Web服務(wù)數(shù)量已經(jīng)達(dá)到22200個(gè)。服務(wù)發(fā)現(xiàn)效率越來越低下，服務(wù)過載逐步顯現(xiàn)。服務(wù)過載，意為通過常規(guī)的服務(wù)發(fā)現(xiàn)手段已經(jīng)難以實(shí)現(xiàn)對(duì)服務(wù)有效的處理和利用。如何解決服務(wù)過載問題，幫助用戶快速定位高質(zhì)量（Qualityofservice，QoS）服務(wù)成為目前服務(wù)計(jì)算領(lǐng)域一個(gè)研究熱點(diǎn)。推薦系統(tǒng)在電商、電影等易產(chǎn)生信息過載領(lǐng)域的成功，為服務(wù)計(jì)算領(lǐng)域的專家學(xué)者提供了解決服務(wù)過載的新思路。以服務(wù)推薦的方式替代服務(wù)發(fā)現(xiàn)過程，不僅可以解決服務(wù)過載的問題，更是一個(gè)由用戶被動(dòng)搜索轉(zhuǎn)向用戶定向主動(dòng)推薦的過程。目前已經(jīng)有一些學(xué)者對(duì)于服務(wù)推薦做過綜述性研究，張等人[1]從服務(wù)推薦要解決的問題、面臨的挑戰(zhàn)、未來的發(fā)展等角度對(duì)服務(wù)推薦領(lǐng)域的研究成果做了綜述;閆[2]等人對(duì)基于協(xié)同過濾的推薦算法做了綜述。隨著推薦算法的不斷推陳出新，服務(wù)推薦算法也不再局限于協(xié)同過濾。本文將從推薦算法發(fā)展的角度對(duì)近十年的服務(wù)推薦算法作一個(gè)綜述。

本文的組織結(jié)構(gòu)如下：第1節(jié)介紹服務(wù)推薦所要完成的目標(biāo)以及目前服務(wù)推薦算法的評(píng)價(jià)指標(biāo);第2節(jié)介紹基于協(xié)同過濾的服務(wù)推薦算法;第3節(jié)介紹基于矩陣分解的服務(wù)推薦算法;第4節(jié)介紹基于深度學(xué)習(xí)的服務(wù)推薦算法;第5節(jié)總結(jié)全文。

1 服務(wù)推薦目標(biāo)及算法評(píng)價(jià)指標(biāo)

表1顯示的是用戶和服務(wù)關(guān)于響應(yīng)時(shí)間的QoS矩陣，稱為“用戶-服務(wù)”矩陣，也稱為共現(xiàn)矩陣。表中的數(shù)值分別表示用戶調(diào)用對(duì)應(yīng)服務(wù)時(shí)的響應(yīng)時(shí)間數(shù)據(jù)，“-”表示用戶并未調(diào)用過該服務(wù)?；赒oS的服務(wù)推薦所要解決的問題便是預(yù)測(cè)出共現(xiàn)矩陣中“-”位置處的QoS數(shù)值，并以QoS值為排序指標(biāo)，為用戶推薦服務(wù)。

其中[fxi]表示待評(píng)估模型的預(yù)測(cè)值，[yi]表示樣本真實(shí)值，m表示樣本總數(shù)。MAE、RMSE的值越小，表示預(yù)測(cè)值與實(shí)際值之間的誤差越小，模型的推薦性能越好。

2 基于協(xié)同過濾的服務(wù)推薦算法

協(xié)同過濾算法是最早應(yīng)用在服務(wù)推薦領(lǐng)域的算法，以基于用戶的協(xié)同過濾算法為例，其計(jì)算原理為：假設(shè)相似用戶具有相似的喜好，在該假設(shè)的基礎(chǔ)上，通過計(jì)算用戶的相似群體完成推薦。用戶[i，j]的相似度[sim（i，j）]的計(jì)算常用以下兩種方法。

其中[θ]表示用戶向量[i，j]之間的夾角。余弦相似度衡量了向量夾角的大小，由式⑶可見，夾角越小，余弦相似度越大。

其中，[Ri，p]表示用戶[i]對(duì)物品[p]的評(píng)分，[Ri]代表用戶[i]對(duì)所有物品的平均評(píng)分，[P]代表物品集合。與余弦相似度相比，皮爾遜相關(guān)系數(shù)通過用戶平均分對(duì)獨(dú)立評(píng)分進(jìn)行修正，降低了用戶評(píng)分偏置的影響。

基于協(xié)同過濾的服務(wù)推薦算法主要在服務(wù)推薦早期較多采用，Sarwar等人[2]提出了基于服務(wù)的協(xié)同過濾服務(wù)推薦算法IPCC，算法輸入特征為服務(wù)，以服務(wù)為中心，應(yīng)用皮爾遜相關(guān)系數(shù)計(jì)算服務(wù)的相似鄰居，并將鄰居服務(wù)推薦給用戶。Shao[4]等人提出了基于用戶的協(xié)調(diào)過濾服務(wù)推薦算法UPCC，算法的輸入特征為用戶，以用戶為中心，應(yīng)用皮爾遜相關(guān)系數(shù)計(jì)算用戶的相似鄰居，并將相似鄰居調(diào)用過的服務(wù)推薦給中心用戶。張等人[5]提出了基于混合協(xié)同過濾的Web服務(wù)推薦算法，算法中結(jié)合了基于用戶的協(xié)同過濾和基于服務(wù)的協(xié)同過濾的共同優(yōu)點(diǎn)，并設(shè)計(jì)了考慮用戶個(gè)性化的Web服務(wù)推薦框架。張[6]等人認(rèn)為用戶的評(píng)價(jià)中存在部分惡意評(píng)價(jià)，其可信度有待考量，因此，他們提出了具有穩(wěn)定性和可行評(píng)價(jià)的服務(wù)推薦算法，該方法通過“云模型”計(jì)算服務(wù)的穩(wěn)定性，計(jì)算用戶間的“反饋相似度”以剔除虛假用戶評(píng)價(jià)，最后在穩(wěn)定和可信的基礎(chǔ)上為用戶推薦服務(wù)。Adeli等人[7]認(rèn)為用戶和服務(wù)之間的依賴性和流行度對(duì)服務(wù)推薦精度有著重要的影響，因此，他們提出了基于流行度依賴的協(xié)同過濾服務(wù)推薦算法，通過引入“用戶-服務(wù)”流行度依賴關(guān)系，提高算法在應(yīng)對(duì)冷啟動(dòng)問題時(shí)的推薦精度。

3 基于矩陣分解的服務(wù)推薦算法

雖然基于協(xié)同過濾的服務(wù)推薦算法在服務(wù)推薦領(lǐng)域初期取得了優(yōu)異的成效，但其仍然存在許多問題，其中最為嚴(yán)重的問題是：推薦結(jié)果的頭部效應(yīng)十分明顯，且難以克服數(shù)據(jù)稀疏帶來的推薦精度下降問題。為了解決這一問題，矩陣分解的方法被眾多學(xué)者應(yīng)用到服務(wù)推薦中。矩陣分解引入了“隱向量”的概念，增強(qiáng)了算法應(yīng)對(duì)數(shù)據(jù)稀疏問題的能力。

矩陣分解的算法過程如圖2所示，矩陣分解算法通過“用戶隱矩陣”與“服務(wù)隱矩陣”的乘積擬合“用戶-服務(wù)”矩陣，應(yīng)用矩陣分解算法求解服務(wù)推薦問題的過程可歸納為：

對(duì)“用戶-服務(wù)”矩陣[R=rm*n]，“用戶隱矩陣”[U=um*k]，“服務(wù)隱矩陣”[V=vk*n]，通過優(yōu)化目標(biāo)函數(shù)：[minrui≠"-"（rui-uTivu）2]完成模型參數(shù)學(xué)習(xí)，而后通過訓(xùn)練好的“用戶隱矩陣”與“服務(wù)隱矩陣”的乘積得到共現(xiàn)矩陣中所有QoS預(yù)測(cè)值并完成推薦。

在矩陣分解應(yīng)用到服務(wù)推薦領(lǐng)域以后，服務(wù)推薦的精度獲得了大幅度提高，唐[8]等人提出了基于位置聚類和張量分解的Web服務(wù)推薦算法ClustTD，該方法首先應(yīng)用聚類算法，以位置信息為指標(biāo)，分別對(duì)用戶、服務(wù)聚類，而后對(duì)聚類所得用戶向量、服務(wù)向量進(jìn)行張量分解，再加權(quán)組合完成QoS值預(yù)測(cè)。Xu[9]等人提出了基于矩陣分解的上下文感知服務(wù)推薦算法LE-MF，為了解決冷啟動(dòng)的問題，LE-MF算法中引入了服務(wù)位置信息、用戶位置信息，通過位置信息先完成用戶聚類、服務(wù)聚類，通過聚類縮小“用戶-服務(wù)”矩陣的體積，再通過矩陣分解完成服務(wù)QoS預(yù)測(cè)，并完成推薦。Yin等人[10]提出了基于網(wǎng)絡(luò)位置感知鄰居選擇的Web服務(wù)推薦QoS預(yù)測(cè)方法，與Xu等人不同的是，Yin等人沒有使用用戶、服務(wù)經(jīng)緯度信息作為聚類指標(biāo)，而是通過自治系統(tǒng)（AS）來獲取用戶、服務(wù)的網(wǎng)絡(luò)位置，從而縮小求解空間，再通過矩陣分解的方法完成服務(wù)QoS預(yù)測(cè)。Qi等人[11]從服務(wù)推薦中的數(shù)據(jù)安全角度入手，他們認(rèn)為算法中引入用戶、服務(wù)的時(shí)空信息雖然可以提高推薦精度，但時(shí)空數(shù)據(jù)往往包含用戶的敏感信息，因此他們提出了一種具有隱私保護(hù)的時(shí)空數(shù)據(jù)驅(qū)動(dòng)的服務(wù)推薦，通過引入QoS數(shù)據(jù)的時(shí)空信息和位置敏感哈希技術(shù)，提高在使用時(shí)空數(shù)據(jù)時(shí)的安全性。Botangen等人[12]從矩陣分解方法的角度入手，通過改進(jìn)算法的方式提升推薦精度，在引入地理位置信息的基礎(chǔ)上，提出了一種基于概率矩陣分解的地理位置感知Web服務(wù)推薦算法。

4 基于深度學(xué)習(xí)的服務(wù)推薦算法

矩陣分解的引入雖然提高了服務(wù)推薦的精度，但是就矩陣分解算法本身，參與計(jì)算的特征數(shù)量只能是兩個(gè)，對(duì)于其他上下文信息不友好，且難以克服冷啟動(dòng)帶來的推薦精度降低問題。

隨著AlexKrizhevsky于2012年提出AlexNet[13]，深度學(xué)習(xí)的大幕正式拉開，往后的時(shí)間里，其應(yīng)用迅速地從圖像領(lǐng)域擴(kuò)展到語音領(lǐng)域，再到自然語言處理領(lǐng)域以及推薦系統(tǒng)領(lǐng)域。推薦系統(tǒng)進(jìn)入深度學(xué)習(xí)時(shí)代后產(chǎn)生的大量?jī)?yōu)秀模型、算法也被眾多學(xué)者引入服務(wù)計(jì)算領(lǐng)域，基于深度學(xué)習(xí)的服務(wù)推薦算法應(yīng)運(yùn)而生。

Xiong[14]等人提出了基于混合協(xié)同過濾的Web服務(wù)推薦，首先通過“詞嵌入”方法將用戶、服務(wù)的上下文信息編碼成輸入特征向量，將多個(gè)輸入特征向量連接以后喂入全連接網(wǎng)絡(luò)，網(wǎng)絡(luò)輸出為服務(wù)的QoS預(yù)測(cè);Bai等人[15]提出了長(zhǎng)尾Web服務(wù)推薦的深度學(xué)習(xí)框架，論文中對(duì)“長(zhǎng)尾服務(wù)”的定義為自發(fā)布以來，被調(diào)用次數(shù)低于5次的服務(wù)，他們通過論證得出隨著服務(wù)數(shù)量的增長(zhǎng)，用戶越發(fā)傾向于長(zhǎng)尾服務(wù)，提高長(zhǎng)尾服務(wù)的推薦效率可以很大程度提高用戶的體驗(yàn)。他們使用堆疊自編碼器分別提取用戶、服務(wù)特征，而后通過矩陣分解的方法實(shí)現(xiàn)QoS的預(yù)測(cè)。實(shí)驗(yàn)證明，他們的方法可以有效改善傳統(tǒng)方法導(dǎo)致的頭部效應(yīng)問題。唐等人[16]從特征交叉角度入手，提出基于一階因子分解機(jī)的質(zhì)量感知Web服務(wù)推薦算法，該方法在邏輯回歸基礎(chǔ)上，加入非線性的一階特征交叉，提升了算法的學(xué)習(xí)能力。實(shí)驗(yàn)表明他們的方法比傳統(tǒng)線性特征學(xué)習(xí)的方法效果提升很多。但是由于算法復(fù)雜度限制，因子分解機(jī)難以實(shí)現(xiàn)特征的二階交叉，隨著特征數(shù)的增加，二階特征交叉會(huì)產(chǎn)生“參數(shù)爆炸”的問題。曹等人[17]考慮到基于因子分解的方法無法實(shí)現(xiàn)特征的高階交叉，將DeepFM方法引入服務(wù)推薦領(lǐng)域，該算法首先應(yīng)用SOM神經(jīng)網(wǎng)絡(luò)進(jìn)行聚類，而后對(duì)于聚類結(jié)果喂入DeepFM網(wǎng)絡(luò)，最終輸出服務(wù)QoS的預(yù)測(cè)數(shù)據(jù)。

5 總結(jié)

從起初基于協(xié)同過濾到目前基于深度學(xué)習(xí)，服務(wù)推薦算法的發(fā)展可以總結(jié)為圍繞以下兩個(gè)核心點(diǎn)進(jìn)行突破：

⑴ 增加及優(yōu)化輸入特征，增加算法中的先驗(yàn)知識(shí);

⑵ 實(shí)現(xiàn)特征之間的高階交叉，提升算法的學(xué)習(xí)能力。

硬件能力的不斷提升，使更多的特征可以被喂入網(wǎng)絡(luò)而不用擔(dān)心計(jì)算能力;深度學(xué)習(xí)帶來更深層的特征之間的交叉學(xué)習(xí)，使得模型的泛化能力以及特征表達(dá)能力不斷增強(qiáng)，未來的服務(wù)推薦領(lǐng)域?qū)⒗^續(xù)在這兩個(gè)方面努力。

參考文獻(xiàn)（References）：

[1] 張秀偉，何克清，王健，等.Web服務(wù)個(gè)性化推薦研究綜述[J].計(jì)算機(jī)工程與科學(xué)，2013，35（9）：132-140

[2] 閆紅丹，楊懷洲.Web服務(wù)QoS預(yù)測(cè)與主動(dòng)推薦方法綜述[J].智能計(jì)算機(jī)與應(yīng)用，2019，9（1）：199-202

[3] B. Sarwar， G. Karypis， J. Konstan， and J. Riedl， "Item-based collaborative filtering recommendation algorithms，"[C] Proc. International Conference on World Wide Web， ACM Press，2001（5）：285-295

[4] L. Shao， J. Zhang， Y. Wei， J. Zhao， B. Xie and H. Mei，"Personalized QoS prediction for Web Services via collaborative filtering，"[C] IEEE International Conference on Web Services， Salt Lake City， UT，2007.7：439-446

[5] 張雪潔，王志堅(jiān)，張偉建.基于混合協(xié)同過濾的個(gè)性化Web服務(wù)推薦[J].計(jì)算機(jī)科學(xué)與探索，2015，9（5）：565-574

[6] 張永勝，樊悅芹，鄭志華，等.考慮穩(wěn)定性與可信評(píng)價(jià)的云服務(wù)推薦網(wǎng)絡(luò)研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2018，39（1）

[7] S.Adeli， P.Moradi QoS-based Web Service Recommenda-tion using Popular-dependent Collaborative Filtering[J].Joural of AI and Data Mining，2020，8（1）：83-93

[8] 唐妮，熊慶宇，王喜賓，等.基于位置聚類和張量分解的Web服務(wù)推薦算法[J].計(jì)算機(jī)工程與應(yīng)用，2016（15）：65-72

[9] Xu Y ， Yin J ， Deng S ， et al. Context-aware QoSprediction for Web Service recommendation and selection[J]. Expert Systems with Applications，2016（53）：75-86

[10] Yuyu Yin，Song Aihua，Gao Min，et al.QoS Prediction for Web Service Recommendation with Network Location-Aware Neighbor Selection[J]. International Journal of Software Engineering and Knowledge Engineering，2016，26（4）：611-632

[11] Qi L， Zhang X， Li S， et al. Spatial-Temporal Data-driven Service Recommendation with Privacy-preservation[J]. Information Sciences，2019：515

[12] Botangen K A， Yu J， Sheng Q Z， et al. Geographic-aware Collaborative Filtering for Web Service Recommendation[J]. Expert Systems with Applications，2020，151：113347

[13] ImageNet Classification with Deep Convolutional Neural Networks[J].Advances in neural information processing systems，2012，25（2）

[14] Xiong R，? Wang J，? Zhang N， et al. Deep Hybrid?Collaborative Filtering for Web Service Recommendation[J]. Expert Systems with Applications，2018，110：191-205

[15] B. Bai， Y. Fan， W. Tan and J. Zhang， "DLTSR： A Deep Learning Framework for Recommendations of Long-Tail Web Services，"[C]IEEE Transactions on Services Computing，2020，13（1）：73-85

[16] 唐明董，張婷婷，楊亞濤，等.基于因子分解機(jī)的質(zhì)量感知Web服務(wù)推薦方法[J].計(jì)算機(jī)學(xué)報(bào)，2018，41（6）：1300-1313

[17] 曹步清，肖巧翔，張祥平，等.融合SOM功能聚類與DeepFM質(zhì)量預(yù)測(cè)的API服務(wù)推薦方法[J].計(jì)算機(jī)學(xué)報(bào)，2019（6）：1367-1383