基于低秩張量補全的QoS數(shù)據(jù)預(yù)測技術(shù)研究

王鳳偉 董慶義

摘要：隨著網(wǎng)絡(luò)服務(wù)的發(fā)展，具有相同或相似功能的Web服務(wù)逐漸增多?；诜?wù)質(zhì)量（Quality of Service，QoS） 向用戶推薦優(yōu)質(zhì)的服務(wù)已成為主要標(biāo)準(zhǔn)。因此，有效預(yù)測Qos數(shù)據(jù)的缺失值為用戶推薦Web服務(wù)成為亟須解決的問題。該文針對QoS數(shù)據(jù)預(yù)測問題引入了一種基于低秩核范數(shù)張量補全方法。該方法通過構(gòu)建張量來表示多元的 QoS 數(shù)據(jù)。利用核范數(shù)近似秩最小化來挖掘QoS數(shù)據(jù)之間的相關(guān)性。最后通過交替方向乘子法迭代優(yōu)化得到預(yù)測結(jié)果。同時，在真實的數(shù)據(jù)集WS-Dream上進行了大量的實驗驗證。

關(guān)鍵詞：QoS 預(yù)測；Web服務(wù)；張量補全；協(xié)同過濾

中圖分類號： TP301 ? ? 文獻標(biāo)識碼：A

文章編號：1009-3044（2022）28-0053-03

1 引言

近年來，Web服務(wù)的QoS數(shù)據(jù)缺失預(yù)測問題受到廣泛關(guān)注，被認(rèn)為是服務(wù)選擇和服務(wù)推薦的關(guān)鍵。隨著物聯(lián)網(wǎng)的快速發(fā)展，Web服務(wù)數(shù)量逐漸增多，用戶對功能相似的Web服務(wù)無法分辨，面對多種服務(wù)難以抉擇。由于Web服務(wù)的QoS數(shù)據(jù)值是缺失的，是無法根據(jù)缺失的QoS值為用戶推薦高質(zhì)量服務(wù)。而且，由于不同的用戶在不同的服務(wù)調(diào)用環(huán)境存在著極大的差異，使得QoS屬性值變得不穩(wěn)定。所以，精確地預(yù)測Web服務(wù)的QoS數(shù)據(jù)缺失值是非常必要的，這能夠便于用戶進行服務(wù)選擇，也可以通過QoS數(shù)據(jù)向用戶推薦高質(zhì)量的服務(wù)。幫助用戶在大量的服務(wù)中選擇最合適的服務(wù)。

基于 QoS 數(shù)據(jù)向用戶推薦服務(wù)直接取決于 QoS 數(shù)據(jù)的預(yù)測精度。其中，在各種 QoS 預(yù)測方法中，協(xié)同過濾方法 （Collaborative Filtering CF） 是解決QoS預(yù)測的問題有效方法。協(xié)同過濾方法分為兩類：基于鄰域的和基于模型的[1]。基于鄰域的協(xié)同過濾方法只是基于歷史相似的用戶或服務(wù)來預(yù)測 QoS 數(shù)據(jù)缺失值。然而，在真實的 Web服務(wù)平臺調(diào)用環(huán)境中，QoS 數(shù)據(jù)往往高度稀疏，難以基于歷史相似的用戶和服務(wù)進行預(yù)測?；谀Ｐ偷腃F方法的矩陣分解方法是通過學(xué)習(xí)潛在因子得到兩個低維目標(biāo)矩陣。盡管基于矩陣分解的QoS預(yù)測方法總體上優(yōu)于傳統(tǒng)基于鄰域的QoS預(yù)測方法，但仍存在一些不足。沒有考慮時間因素對QoS數(shù)據(jù)的影響，只是考慮了“用戶-服務(wù)”二者的關(guān)系。考慮到嚴(yán)重影響 QoS 數(shù)據(jù)的時間因素，需要引入張量數(shù)據(jù)模型來對現(xiàn)有 QoS 數(shù)據(jù)進行建模。

針對QoS數(shù)據(jù)缺失值預(yù)測問題，本文受到文獻[2]中對時空交通流量數(shù)據(jù)預(yù)測的啟發(fā)。首先，基于現(xiàn)有 QoS 數(shù)據(jù)的整體結(jié)構(gòu)進行數(shù)據(jù)三階張量建模。針對此數(shù)據(jù)模型提出了基于低秩核范數(shù)張量補全的CF預(yù)測方法。因為張量秩最小化問題通常是 NP-hard [3]，所以引用核范數(shù)近似秩最小化求解。本文的主要貢獻總結(jié)如下：

（1） 為了更好地表達復(fù)雜多元的QoS數(shù)據(jù)，針對時間信息的作用，本文在先的二階“用戶-服務(wù)”的基礎(chǔ)上加入時間的維度構(gòu)成三階張量表達Qos值，此QoS數(shù)據(jù)張量能夠很好地表達Qos數(shù)據(jù)的復(fù)雜三元關(guān)系。

（2） 提出QoS數(shù)據(jù)低秩張量補全（Low-Rank Tensor Completion，LRTC） 預(yù)測方法預(yù)測Qos數(shù)據(jù)缺失值，該方法通過核范數(shù)近似張量秩最小化求解，以此挖掘QoS數(shù)據(jù)之間的相關(guān)性提高預(yù)測精度。最后利用交替方向乘子（Alternating Direction Method of Multiplies， ADMM）法進行迭代優(yōu)化。

（3） 本文提出基于低秩張量補全預(yù)測方法在公開的大規(guī)模的數(shù)據(jù)集WS-Dream上進行了實驗評估。經(jīng)過實驗對比，本文提出的QoS數(shù)據(jù)預(yù)測模型的實驗結(jié)果優(yōu)于其他對比基線。

2 QoS預(yù)測技術(shù)原理

2.1 QoS 數(shù)據(jù)模型

通常情況下用戶調(diào)用服務(wù)時是需要時間的積累，用戶調(diào)用的服務(wù)的 Qos 值會被記錄下來形成一系列的 Qos 數(shù)據(jù)集。基于現(xiàn)有的研究工作，具體構(gòu)建QoS數(shù)據(jù)模型張量步驟如下[4]。

步驟一：獲取用戶所記錄的所有的 QoS 數(shù)據(jù)值集合[]。

步驟二：通過QoS數(shù)據(jù)記錄四元組中的[]構(gòu)造一個“用戶-服務(wù)”的矩陣[R（0）]，將在時間間隔0處的[U]個用戶作為矩陣行，[S]個服務(wù)作為矩陣列。同理，時間間隔從1到[k]構(gòu)造出[k]的矩陣。

步驟三：根據(jù)QoS數(shù)據(jù)記錄四元組中的[]填充對應(yīng)的QoS值在矩陣中。

步驟四：按照時間間隔將矩陣進行疊加構(gòu)造張量[Y∈?U×S×T]，其中“用戶-服務(wù)”矩陣是張量的每一個切片。

2.2 低秩張量補全方法

低秩張量補全方法用于解決高維數(shù)據(jù)的缺失數(shù)據(jù)已經(jīng)變得成熟。我們受到低秩矩陣數(shù)據(jù)補全[5]和張量低秩補全在交通流量數(shù)據(jù)預(yù)測的啟發(fā)，將張量低秩補全擴展應(yīng)用到Web環(huán)境中QoS數(shù)據(jù)缺失值預(yù)測問題上。

針對2.1節(jié)構(gòu)建的QoS數(shù)據(jù)張量模型，提出了QoS數(shù)據(jù)低秩張量補全預(yù)測方法，該方法通過張量秩近似最小化能確保QoS數(shù)據(jù)的全局一致性和局部一致性。秩最小化已被證明是利用結(jié)構(gòu)數(shù)據(jù)中固有的相關(guān)性和依賴性的有力工具。具體QoS數(shù)據(jù)預(yù)測優(yōu)化模型如下：

[minY：rank（Y） s.t. ： PΩ（Y）=PΩ（T）] ? ? ? ? ? ? ? ? （1）

其中[Y]表示缺失的低秩張量，[rank（Y）]表示張量[Y]的張量秩，張量秩最小化問題通常是 NP-hard，于是將QoS預(yù)測模型（1） 轉(zhuǎn)化為：

[minY：Y* s.t. ： PΩ（Y）=PΩ（T）] ? ? ? ? ? ? ? ?（2）

其中[Y*=k=13αkY（k）*]是張量的核范數(shù)，張量的核范數(shù)具體定義為沿每個張量模式展開所有矩陣的核范數(shù)之和[3]。[k]表示張量展開的第[k]模矩陣，[αk]表示張量展開的權(quán)重參數(shù)。

2.3 ADMM優(yōu)化

LRTC方法采用交替方向乘數(shù)法（Alternating Direction Multiplier Method， ADMM） 進行迭代優(yōu)化。ADMM算法是解決約束最小化問題的經(jīng)典方法。推導(dǎo)出公式（2） 的增廣拉格朗日函數(shù)：

[LY（k），T（k）3k=1，λ=k=13αkY（k）*+ρ（k）2Y（k）-T（k）2F+λ，Y（k），T（k）] ? （3）

其中[ρ]是ADMM的學(xué)習(xí)率。分別依次迭代求解變量[Y]和[T]得出最終結(jié)果。

3 實驗數(shù)據(jù)與研究分析

在本節(jié)中，本文對提出的QoS數(shù)據(jù)預(yù)測算法LRTC進行了實驗評估。實驗分析張量密度對實驗結(jié)果的影響并與其他預(yù)測方法進行了比較。為了保證避免實驗的結(jié)果的偶然性，把每組實驗在同一數(shù)據(jù)集進行了10次實驗驗證。

3.1 數(shù)據(jù)集

本文采用公認(rèn)的大規(guī)模數(shù)據(jù) WS-Dream 進行實驗，數(shù)據(jù)集記錄著 142 個用戶在 64 個間隙中調(diào)用 4532 個服務(wù)產(chǎn)生的QoS屬性值[4]。本文主要研究QoS數(shù)據(jù)中具有代表性的響應(yīng)時間（Response Time） 和吞吐量（Throughput） 兩個屬性。響應(yīng)時間定義為服務(wù)用戶發(fā)送請求和接收響應(yīng)之間的持續(xù)時間。吞吐量定義為每秒成功消息大小的平均速率。Qos數(shù)據(jù)的吞吐量的平均值是9.609kbps，響應(yīng)時間的平均值是3.165s。 為符合真實Web環(huán)境下QoS數(shù)據(jù)稀疏的問題，本文將隨機剔除數(shù)據(jù)保證其QoS數(shù)據(jù)的稀疏性。如表1對原有數(shù)據(jù)集進行了預(yù)處理。將訓(xùn)練數(shù)據(jù)集的密度設(shè)置在10% 至 30% 之間，每次遞增 5%。

3.2 參數(shù)設(shè)置

對于LRTC預(yù)測框架中的參數(shù)要進行初始化，權(quán)重參數(shù)[αk]和ADMM中學(xué)習(xí)率[ρ]，這兩個參數(shù)會直接影響整個模型預(yù)測指標(biāo)的性能。對于參數(shù)的選擇采用交叉驗證確定，ADMM框架中學(xué)習(xí)[ρ]參數(shù)它決定了整個模型的收斂性。較大的數(shù)值通常會減慢收斂過程，而較小的數(shù)值則會讓模型在幾次迭代中滿足收斂。在吞吐量和響應(yīng)時間的兩個Qos屬性數(shù)據(jù)集設(shè)置為[ρ=1×10-4] ，迭代次數(shù)設(shè)置為30能達到收斂。根據(jù)先驗經(jīng)驗將權(quán)重參數(shù)[αk]設(shè)置為使用相同的權(quán)重遵循張量核范數(shù)進行展開。

3.3 實驗分析

在本小節(jié)中，我們對真實世界的 Qos 數(shù)據(jù)進行廣泛的實驗以評估低秩張量補全方法，數(shù)據(jù)集有兩個屬性響應(yīng)時間和吞吐量。使用的評價指標(biāo)為通用的平均絕對誤差（Mean Absolute Error， MAE） 和均方根誤差（Root Mean Squared Error， RMSE） [6]。通常情況下預(yù)測方法的MAE和RMSE的值越小，說明預(yù)測方法精度越高。

本文選擇與兩種個經(jīng)典預(yù)測方法在數(shù)據(jù)密度缺失率不同的情況進行實驗對比。

UIPCC[7]：一種結(jié)合了UPCC和IPCC的CF預(yù)測方法。利用歷史用戶和服務(wù)的相似度進行最終預(yù)測。

PMF[8]：利用高斯假設(shè)分解用戶服務(wù) QoS 矩陣來預(yù)測缺失值。

實驗結(jié)果表明，預(yù)測精度與QoS數(shù)據(jù)張量密度缺失有很大的關(guān)聯(lián)。從圖1可以清楚地看出，將訓(xùn)練張量的密度從10%變化到30%，以5%為步長增加。圖1（a）和 1（b）為Response Time的MAE值和RMSE值結(jié)果。圖1（c）和 1（d）是Throughput的MAE值和RMSE值結(jié)果。實驗分析得出：

（1） 隨著訓(xùn)練密度的增加，LRTC方法的性能增強，說明QoS數(shù)據(jù)越多，預(yù)測效果越好。此外還能看出基于鄰域的UIPCC預(yù)測方法的預(yù)測精度低于基于模型的PMF預(yù)測方法，是因為UIPCC太依賴于用戶和服務(wù)的歷史記錄值，但是通常情況下在Web環(huán)境下所記錄的QoS 數(shù)據(jù)是高度稀疏的。

（2） 另外，本文提出的LRTC方法的預(yù)測精度始終高于UIPCC和PMF方法。產(chǎn)生這種現(xiàn)象的原因是UIPCC和PMF方法兩者都只考慮了QoS數(shù)據(jù)的“用戶-服務(wù)”二階靜態(tài)關(guān)系，而沒有考慮QoS數(shù)據(jù)中“用戶-服務(wù)-時間”模型中更有用的時間信息。即實驗結(jié)果表明，構(gòu)造張量模型能夠表達出QoS數(shù)據(jù)復(fù)雜的多元關(guān)系。

（3） 此外，對于利用矩陣因子模型PMF預(yù)測方法，其分解過程中沒有太關(guān)注分解所帶來的數(shù)據(jù)丟失，造成了預(yù)測精度比預(yù)想結(jié)果要差許多。LRTC方法采用了核范數(shù)低秩近似張量補全的方法，避免了數(shù)據(jù)丟失問題，并使得局部數(shù)據(jù)相關(guān)性得到提高，所以LRTC方法的預(yù)測精度優(yōu)于其他對比基線。

4 結(jié)束語

在真實Web環(huán)境下為了更好地表達出 QoS 數(shù)據(jù)的結(jié)構(gòu)全局性，本文針對原有 QoS 數(shù)據(jù)模型上引入了時間維度信息將傳統(tǒng)的“用戶-服務(wù)”二階矩陣構(gòu)建成三階 QoS 數(shù)據(jù)張量“用戶-服務(wù)-時間”。 針對QoS數(shù)據(jù)張量模型，為了能提高QoS數(shù)據(jù)預(yù)測精度；通過LRTC方法預(yù)測數(shù)據(jù)的缺失值，該方法引入張量核范數(shù)低秩近似能捕獲不同用戶和不同服務(wù)之間的數(shù)據(jù)局部相關(guān)性。最后基于乘子交替方向法的框架求解各變量的最優(yōu)解，從而得到預(yù)測張量來填補缺失值。同時，在公開的大規(guī)模的數(shù)據(jù)集WS-Dream上進行了實驗評估。經(jīng)過實驗對比，本文提出的QoS數(shù)據(jù)預(yù)測模型的實驗結(jié)果優(yōu)于其他對比基線。

參考文獻：

[1] 劉珍珍，楊懷洲.綜合時空信息的Web服務(wù)QoS預(yù)測方法研究[J].電腦知識與技術(shù)，2021，17（18）：233-235.

[2] Chen X Y，Lei M Y，Saunier N，et al.Low-rank autoregressive tensor completion for spatiotemporal traffic data imputation[J].IEEE Transactions on Intelligent Transportation Systems，2022，23（8）：12301-12310.

[3] Song Y，Li J，Chen X，et al.An efficient tensor completion method via truncated nuclear norm[J].Journal of Visual Communication and Image Representation，2020，70：102791.

[4] Chen Y P，Zhang Y Q，Xia H，et al.A hybrid tensor factorization approach for QoS prediction in time-aware mobile edge computing[J].Applied Intelligence，2022，52（7）：8056-8072.

[5] Han Z F，Leung C S，Huang L T，et al.Sparse and truncated nuclear norm based tensor completion[J].Neural Processing Letters，2017，45（3）：729-743.

[6] Haihong E，Tong J J，Song M N，et al.QoS prediction algorithm used in location-aware hybrid Web service[J].The Journal of China Universities of Posts and Telecommunications，2015，22（1）：42-49.

[7] Zheng Z B，Ma H，Lyu M R，et al.QoS-aware web service recommendation by collaborative filtering[J].IEEE Transactions on Services Computing，2011，4（2）：140-152.

[8] Mnih A， Salakhutdinov R. Probabilistic matrix factorization[C]//NIPS'07： Proceedings of the 20th International Conference on Neural Information Processing Systems. December 3-6， Vancouver Canada， 2007： 1257-1264.

【通聯(lián)編輯：梁書】