基于低秩張量補全的QoS數據預測技術研究
2022-05-30 09:53:10王鳳偉董慶義
電腦知識與技術 2022年28期
王鳳偉 董慶義
摘要：隨著網絡服務的發展，具有相同或相似功能的Web服務逐漸增多。基于服務質量（Quality of Service，QoS） 向用戶推薦優質的服務已成為主要標準。因此，有效預測Qos數據的缺失值為用戶推薦Web服務成為亟須解決的問題。該文針對QoS數據預測問題引入了一種基于低秩核范數張量補全方法。該方法通過構建張量來表示多元的 QoS 數據。利用核范數近似秩最小化來挖掘QoS數據之間的相關性。最后通過交替方向乘子法迭代優化得到預測結果。同時，在真實的數據集WS-Dream上進行了大量的實驗驗證。
關鍵詞：QoS 預測；Web服務；張量補全；協同過濾
中圖分類號： TP301 ? ? 文獻標識碼：A
文章編號：1009-3044（2022）28-0053-03
1 引言
近年來，Web服務的QoS數據缺失預測問題受到廣泛關注，被認為是服務選擇和服務推薦的關鍵。隨著物聯網的快速發展，Web服務數量逐漸增多，用戶對功能相似的Web服務無法分辨，面對多種服務難以抉擇。由于Web服務的QoS數據值是缺失的，是無法根據缺失的QoS值為用戶推薦高質量服務。而且，由于不同的用戶在不同的服務調用環境存在著極大的差異，使得QoS屬性值變得不穩定。所以，精確地預測Web服務的QoS數據缺失值是非常必要的，這能夠便于用戶進行服務選擇，也可以通過QoS數據向用戶推薦高質量的服務。幫助用戶在大量的服務中選擇最合適的服務。
基于 QoS 數據向用戶推薦服務直接取決于 QoS 數據的預測精度。其中，在各種 QoS 預測方法中，協同過濾方法 （Collaborative Filtering CF） 是解決QoS預測的問題有效方法。協同過濾方法分為兩類：基于鄰域的和基于模型的[1]。基于鄰域的協同過濾方法只是基于歷史相似的用戶或服務來預測 QoS 數據缺失值。然而，在真實的 Web服務平臺調用環境中，QoS 數據往往高度稀疏，難以基于歷史相似的用戶和服務進行預測。基于模型的CF方法的矩陣分解方法是通過學習潛在因子得到兩個低維目標矩陣。盡管基于矩陣分解的QoS預測方法總體上優于傳統基于鄰域的QoS預測方法，但仍存在一些不足。沒有考慮時間因素對QoS數據的影響，只是考慮了“用戶-服務”二者的關系。考慮到嚴重影響 QoS 數據的時間因素，需要引入張量數據模型來對現有 QoS 數據進行建模。
針對QoS數據缺失值預測問題，本文受到文獻[2]中對時空交通流量數據預測的啟發。首先，基于現有 QoS 數據的整體結構進行數據三階張量建模。針對此數據模型提出了基于低秩核范數張量補全的CF預測方法。因為張量秩最小化問題通常是 NP-hard [3]，所以引用核范數近似秩最小化求解。本文的主要貢獻總結如下：
（1） 為了更好地表達復雜多元的QoS數據，針對時間信息的作用，本文在先的二階“用戶-服務”的基礎上加入時間的維度構成三階張量表達Qos值，此QoS數據張量能夠很好地表達Qos數據的復雜三元關系。
（2） 提出QoS數據低秩張量補全（Low-Rank Tensor Completion，LRTC） 預測方法預測Qos數據缺失值，該方法通過核范數近似張量秩最小化求解，以此挖掘QoS數據之間的相關性提高預測精度。最后利用交替方向乘子（Alternating Direction Method of Multiplies， ADMM）法進行迭代優化。
（3） 本文提出基于低秩張量補全預測方法在公開的大規模的數據集WS-Dream上進行了實驗評估。經過實驗對比，本文提出的QoS數據預測模型的實驗結果優于其他對比基線。
2 QoS預測技術原理
2.1 QoS 數據模型
通常情況下用戶調用服務時是需要時間的積累，用戶調用的服務的 Qos 值會被記錄下來形成一系列的 Qos 數據集。基于現有的研究工作，具體構建QoS數據模型張量步驟如下[4]。
步驟一：獲取用戶所記錄的所有的 QoS 數據值集合[
步驟二：通過QoS數據記錄四元組中的[
步驟三：根據QoS數據記錄四元組中的[
步驟四：按照時間間隔將矩陣進行疊加構造張量[Y∈?U×S×T]，其中“用戶-服務”矩陣是張量的每一個切片。
2.2 低秩張量補全方法
低秩張量補全方法用于解決高維數據的缺失數據已經變得成熟。我們受到低秩矩陣數據補全[5]和張量低秩補全在交通流量數據預測的啟發，將張量低秩補全擴展應用到Web環境中QoS數據缺失值預測問題上。
針對2.1節構建的QoS數據張量模型，提出了QoS數據低秩張量補全預測方法，該方法通過張量秩近似最小化能確保QoS數據的全局一致性和局部一致性。秩最小化已被證明是利用結構數據中固有的相關性和依賴性的有力工具。具體QoS數據預測優化模型如下：
[minY：rank（Y） s.t. ： PΩ（Y）=PΩ（T）] ? ? ? ? ? ? ? ? （1）
其中[Y]表示缺失的低秩張量，[rank（Y）]表示張量[Y]的張量秩，張量秩最小化問題通常是 NP-hard，于是將QoS預測模型（1） 轉化為：
[minY：Y* s.t. ： PΩ（Y）=PΩ（T）] ? ? ? ? ? ? ? ?（2）
其中[Y*=k=13αkY（k）*]是張量的核范數，張量的核范數具體定義為沿每個張量模式展開所有矩陣的核范數之和[3]。[k]表示張量展開的第[k]模矩陣，[αk]表示張量展開的權重參數。
2.3 ADMM優化
LRTC方法采用交替方向乘數法（Alternating Direction Multiplier Method， ADMM） 進行迭代優化。ADMM算法是解決約束最小化問題的經典方法。推導出公式（2） 的增廣拉格朗日函數：
[LY（k），T（k）3k=1，λ=k=13αkY（k）*+ρ（k）2Y（k）-T（k）2F+λ，Y（k），T（k）] ? （3）
其中[ρ]是ADMM的學習率。分別依次迭代求解變量[Y]和[T]得出最終結果。
3 實驗數據與研究分析
在本節中，本文對提出的QoS數據預測算法LRTC進行了實驗評估。實驗分析張量密度對實驗結果的影響并與其他預測方法進行了比較。為了保證避免實驗的結果的偶然性，把每組實驗在同一數據集進行了10次實驗驗證。
3.1 數據集
本文采用公認的大規模數據 WS-Dream 進行實驗，數據集記錄著 142 個用戶在 64 個間隙中調用 4532 個服務產生的QoS屬性值[4]。本文主要研究QoS數據中具有代表性的響應時間（Response Time） 和吞吐量（Throughput） 兩個屬性。響應時間定義為服務用戶發送請求和接收響應之間的持續時間。吞吐量定義為每秒成功消息大小的平均速率。Qos數據的吞吐量的平均值是9.609kbps，響應時間的平均值是3.165s。 為符合真實Web環境下QoS數據稀疏的問題，本文將隨機剔除數據保證其QoS數據的稀疏性。如表1對原有數據集進行了預處理。將訓練數據集的密度設置在10% 至 30% 之間，每次遞增 5%。
3.2 參數設置
對于LRTC預測框架中的參數要進行初始化，權重參數[αk]和ADMM中學習率[ρ]，這兩個參數會直接影響整個模型預測指標的性能。對于參數的選擇采用交叉驗證確定，ADMM框架中學習[ρ]參數它決定了整個模型的收斂性。較大的數值通常會減慢收斂過程，而較小的數值則會讓模型在幾次迭代中滿足收斂。在吞吐量和響應時間的兩個Qos屬性數據集設置為[ρ=1×10-4] ，迭代次數設置為30能達到收斂。根據先驗經驗將權重參數[αk]設置為使用相同的權重遵循張量核范數進行展開。
3.3 實驗分析
在本小節中，我們對真實世界的 Qos 數據進行廣泛的實驗以評估低秩張量補全方法，數據集有兩個屬性響應時間和吞吐量。使用的評價指標為通用的平均絕對誤差（Mean Absolute Error， MAE） 和均方根誤差（Root Mean Squared Error， RMSE） [6]。通常情況下預測方法的MAE和RMSE的值越小，說明預測方法精度越高。
本文選擇與兩種個經典預測方法在數據密度缺失率不同的情況進行實驗對比。
UIPCC[7]：一種結合了UPCC和IPCC的CF預測方法。利用歷史用戶和服務的相似度進行最終預測。
PMF[8]：利用高斯假設分解用戶服務 QoS 矩陣來預測缺失值。
實驗結果表明，預測精度與QoS數據張量密度缺失有很大的關聯。從圖1可以清楚地看出，將訓練張量的密度從10%變化到30%，以5%為步長增加。圖1（a）和 1（b）為Response Time的MAE值和RMSE值結果。圖1（c）和 1（d）是Throughput的MAE值和RMSE值結果。實驗分析得出：
（1） 隨著訓練密度的增加，LRTC方法的性能增強，說明QoS數據越多，預測效果越好。此外還能看出基于鄰域的UIPCC預測方法的預測精度低于基于模型的PMF預測方法，是因為UIPCC太依賴于用戶和服務的歷史記錄值，但是通常情況下在Web環境下所記錄的QoS 數據是高度稀疏的。
（2） 另外，本文提出的LRTC方法的預測精度始終高于UIPCC和PMF方法。產生這種現象的原因是UIPCC和PMF方法兩者都只考慮了QoS數據的“用戶-服務”二階靜態關系，而沒有考慮QoS數據中“用戶-服務-時間”模型中更有用的時間信息。即實驗結果表明，構造張量模型能夠表達出QoS數據復雜的多元關系。
（3） 此外，對于利用矩陣因子模型PMF預測方法，其分解過程中沒有太關注分解所帶來的數據丟失，造成了預測精度比預想結果要差許多。LRTC方法采用了核范數低秩近似張量補全的方法，避免了數據丟失問題，并使得局部數據相關性得到提高，所以LRTC方法的預測精度優于其他對比基線。
4 結束語
在真實Web環境下為了更好地表達出 QoS 數據的結構全局性，本文針對原有 QoS 數據模型上引入了時間維度信息將傳統的“用戶-服務”二階矩陣構建成三階 QoS 數據張量“用戶-服務-時間”。 針對QoS數據張量模型，為了能提高QoS數據預測精度；通過LRTC方法預測數據的缺失值，該方法引入張量核范數低秩近似能捕獲不同用戶和不同服務之間的數據局部相關性。最后基于乘子交替方向法的框架求解各變量的最優解，從而得到預測張量來填補缺失值。同時，在公開的大規模的數據集WS-Dream上進行了實驗評估。經過實驗對比，本文提出的QoS數據預測模型的實驗結果優于其他對比基線。
參考文獻：
[1] 劉珍珍，楊懷洲.綜合時空信息的Web服務QoS預測方法研究[J].電腦知識與技術，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.
【通聯編輯：梁書】
