基于信譽感知與嵌入式學習的Web服務QoS預測研究

鄧 璇，呂晟凱

（1.湖北大學 計算機與信息工程學院，湖北 武漢 430062；2.應用數學湖北省重點實驗室，湖北 武漢 430062；3.湖北省軟件工程技術研究中心，湖北 武漢 430062）

0 引 言

協同過濾（Collaborative Filtering）是目前應用廣泛的QoS預測方法之一[3]，傳統計算用戶（或服務）相似性的方法是基于皮爾遜相關系數或余弦相似性計算相似度，實際上只挖掘了用戶之間的二階相似度，而忽略了用戶之間更高階的隱式關系[4]。

為解決以上問題，我們在考慮用戶信譽的同時引入網絡嵌入式學習（Network Embedding Learning），提出一種基于信譽感知的QoS預測方法。該方法能從歷史數據中充分挖掘用戶（或服務）間的高階隱式關系，為目標用戶找到更多潛在的可靠相似用戶，不僅考慮了不可信用戶對預測精度的影響，也在一定程度上緩解了數據稀疏性問題[5-6]。

1 研究方法

本文方法主要包括如下4部分。

（1）用戶信譽計算：利用K-means聚類對Web服務的歷史QoS值進行聚類，聚類結果用于計算用戶的信譽度，將信譽度低于閾值的用戶標記為不可信用戶，并過濾。

（2）網絡建模：將計算得到的用戶信譽度作為用戶節點屬性，構建帶屬性的用戶-服務二分網絡。

（3）網絡嵌入式學習：對帶屬性的用戶-服務二分網絡進行嵌入式學習，獲得用戶的表征向量。

（4）QoS預測：給定一個目標用戶，為其返回Top-K個相似用戶，并利用相似用戶提供的信息預測缺失的QoS值。

1.1 K-means聚類

對每一項服務，使用K-means聚類對其所有用戶標記的QoS值進行聚類。聚類后，包含元素個數最少的集群中的用戶視為不可信用戶。聚類算法中的參數K為確定要劃分的組數，表示服務j的第k個集群，其中k是集群的索引，0≤k

長陽縣水產局局長田繼橋向記者解讀該項工作的艱巨難行之處時說，整個清理取締概算需要2億元以上的資金，這相當于該縣過去30年農業投入的總和。當這個數字報到縣人大常委會時，大家都愣住了。

矩陣A是由m個用戶和n個服務組成的m×n矩陣，用來記錄用戶的不可信索引，初始化矩陣A，其每一項值均為0。如果用戶i被標識為服務j上的候選不可信用戶，則aij設置為1。重復聚類過程，對每個服務更新矩陣A，直到所有服務的QoS值均已聚類。

用戶信譽度：在對所有QoS值聚類后，使用以下公式得到用戶不可信索引集：

式中，wu表示用戶u被識別為不可信用戶的次數，wu越大，表示該用戶的信譽度越低，即ru=1?wu。

1.2 用戶-服務二分網絡學習

1.2.1 帶屬性的用戶-服務二分網絡建模

結合用戶信譽和用戶與服務的交互信息，可以構建一個帶屬性的用戶-服務二分網絡G={U,S,R,E}，其中，U={u1,u2,...,um}是用戶集合，S={s1,s2,...,sn}是服務集合，R是用戶信譽，E={eij|i=1, 2,...,m；j=1, 2,...,n}是邊集合，在邊集合中eij=QoSij，表示用戶ui對服務sj的個性化QoS值。用戶u1，u2，u3的信譽值分別為r(u1)，r(u2)，r(u3)，其用戶-服務二分網絡如圖1所示。

圖1 用戶-服務二分網絡

1.2.2 網絡嵌入學習

二分網絡嵌入（Bipartite Network Embedding）用于學習二分網絡中的節點表示[7]。它通過執行有偏和自適應的隨機游走，很好地保持了原始二分網絡中節點的長尾分布。它在學習節點表示時，同時對顯式關系（即觀察到的連接）和高階隱式關系（即未觀察到但可傳遞的連接）進行建模。通過二分網絡嵌入式學習，可以為目標用戶發掘更多可信的間接相似用戶，有效減少不可信用戶和數據稀疏性對預測精度的影響。

1.3 協同過濾

對目標用戶i，選擇與其相似度最高的前K個用戶作為其相似用戶集合。

依據相似用戶提供的信息，缺失的QoS值可以用以下公式計算：

2 實驗與結果分析

本文在公開數據集[8]WS-Dream上進行實證分析，與3種已有方法進行對比。采用常用的平均絕對誤差（Mean Absolute Error, MAE）作為測量預測方法準確性的評價指標，MAE定義為：

式中：N為所有預測值的個數；Ru,i表示實際QoS值；u,i表示預測的QoS值。

將QoS矩陣密度以1%的步長從5%增加到10%。在K-means聚類中K取值為5，選擇反饋20個相似用戶進行預測。嵌入式學習中的負采樣數為4，窗口為5，游走停止概率p為 0.15，損失權衡參數α=0.01，β=0.01，γ=4，學習率λ=0.15。表1顯示了在不同密度條件下不同方法的MAE結果，實驗結果表明：隨著矩陣密度的增加，所有方法的MAE值都呈下降趨勢。說明矩陣的密度越大，可獲得的用戶和服務交互信息越多，預測精度也就越高。在各密度條件下，本文方法與已有方法相比，MAE值更小，即預測精度更高。說明采用信譽感知的網絡嵌入式方法，能夠緩解數據稀疏性對預測精度的影響。具體而言，與TAP方法相比，本文方法的預測精度最大可提高20.93%。

表1 各方法在不同矩陣密度條件下取得的MAE結果

3 結 語

本文將網絡嵌入式方法引入QoS預測過程中，考慮用戶的實際信譽度，提出了一種基于信譽感知網絡嵌入的QoS預測方法。該方法能夠充分利用用戶-服務二分網絡信息與用戶信譽度信息，能從歷史數據中充分挖掘用戶-服務間的高階隱式關系，為目標用戶找到更多潛在的可靠相似用戶。實驗表明，本文方法不僅考慮了用戶信譽對預測精度的影響，也在一定程度上緩解了數據稀疏性問題，相比已有三種其他方法準確度更高[9-10]。