基于用戶可信度的Web服務推薦方法

曹繼承，朱小柯，荊曉遠,，吳 飛

(1.南京郵電大學 計算機學院，江蘇 南京 210003；2.武漢大學 計算機學院 軟件工程國家重點實驗室，湖北 武漢 430072；3.南京郵電大學 自動化學院，江蘇 南京 210003)

0 引 言

隨著提供類似功能的Web服務越來越多，服務質量(QoS)成為選擇最佳可用服務的重要標準[1]。QoS是一些非功能屬性，例如響應時間、吞吐量、可靠性、可用性等，能夠在提供相同功能的服務中作為第二輪篩選標準[2]。

協同過濾是目前廣泛使用的一種推薦技術[3]。基于協同過濾的Web服務推薦系統通過搜集用戶的Web服務訪問記錄，利用用戶的反饋數據為用戶提供個性化的服務推薦[4]。但是大多數推薦系統都是默認用戶的數據是可信的。而現實生活中，用戶的數據會因為各種原因而變得不可信，包括設備異常或惡意評價等。如果不考慮用戶的可信度，會對最終預測結果產生嚴重的干擾。

為了解決上述問題，提出了一種基于用戶可信度的Web服務推薦方法(CRCF)。首先利用所有用戶的反饋數據計算出用戶的可信度，然后通過聚類的方式排除可信度低的用戶，從而排除含有較多干擾數據的用戶，避免其對最終預測結果的影響。最后使用協同過濾進行預測并使用平均絕對誤差和均方根誤差評判預測結果。

1 相關工作

1.1 協同過濾

協同過濾是一種廣泛使用的推薦技術，主要分為基于歷史數據的方法和基于模型的方法。基于歷史數據的方法首先搜集用戶歷史數據，然后計算用戶或者項目的相似度，最終通過相似用戶或項目產生推薦結果。基于模型的方法在訓練數據上通過數據挖掘和機器學習算法找到相應的模型，然后完成推薦。相比前者，基于歷史數據的方法因其易于理解和使用在實際中應用廣泛。文中算法屬于基于歷史數據的方法。

經典的基于歷史數據的協同過濾算法包括基于用戶的方法(UPCC)[5]和基于項目的方法(IPCC)[6]以及基于用戶和項目的方法(UIPCC)[7]。

UPCC利用式1計算用戶u和用戶v的相似度，然后找到相似度最高的k個用戶，最后通過式2進行QoS值的預測。

(1)

(2)

其中，N(u)表示用戶u和用戶v相似度最高的k個近鄰用戶。

IPCC與UPCC類似，利用式3計算服務i和服務j的相似度，然后找到相似度最高的k個服務，之后通過式4進行QoS值的預測。

(3)

(4)

UIPCC是將UPCC和IPCC的兩個結果利用式5進行加權求和，從而獲取更精確的預測，這里不再展開描述。

P(u,i)=λ×P1(u,i)+(1-λ)×P2(u,i)

(5)

1.2 用戶可信度

搜集到的用戶反饋數據中，包含很多可能干擾到最終預測結果的不可信數據，例如：(1)用戶可能會提交一些隨機的值作為其QoS反饋值；(2)用戶可能會為了某種利益故意對某些服務給予很好的QoS值，而對另外一些服務給予很差的QoS值；(3)用戶雖如實提交了其QoS數據，但是數據由于受到當時網絡環境、設備等的干擾，處于不正常的范圍內。如果不對上述的不可信數據進行處理，會對最終的預測結果產生很大的影響。

文獻[8]提出了一種通過計算用戶評價可信度來完成可信Web服務推薦的方法，但是該方法包含的參數很多，設置不當會導致很差的結果。文獻[9]提出了一種可信的Web服務推薦模型，該模型的缺點是對現有的Web體系結構并不是很適用。文獻[10]提出了一種排除含有異常數據較多的用戶的方法，該方法只考慮到了范圍異常的數據，沒有考慮范圍正常但與服務實際性能不符的惡意評價數據。文獻[11]提出了一種利用可信第三方來解決不可信用戶問題的方法，但是事實上找到可信的第三方并不容易。

通過分析所有用戶的反饋數據可知，如果某個用戶對某個服務的反饋數據與其他訪問過該服務的用戶差距很大，且很少有用戶與其相近，則這個用戶的數據是有問題的。若某個用戶有問題的數據很多，則這個用戶更有可能是有問題用戶。

在上述研究的基礎上，文中提出了一種基于用戶可信度的Web服務推薦方法，使用一種計算用戶可信度的方法，排除干擾數據的影響，并通過聚類方式排除干擾用戶，減少需要設置的參數。

2 基于用戶可信度的推薦方法

2.1 用戶可信度的計算

該算法旨在排除那些不可信的用戶，從而使預測更準確。人們更傾向于相信被大多數人認可的數據，如果某個用戶對Web服務的反饋與其他用戶差別很大，則此用戶很可能是干擾用戶。用戶t的可信度由式6求得：

TRDt=

(6)

通過式6可以得到一個保存用戶可信度的向量：T={t1,t2,…,tm}，其中含有范圍異常數據以及惡意數據的用戶的可信度會明顯小于可信用戶。圖1為香港中文大學搜集的數據集的用戶可信度的分布圖。由圖1可見，多數用戶的可信度都集中在某個區間，只有少數在此區間外。

圖1 用戶可信度分布直方圖

2.2 不可信用戶的排除

通過設置閾值并將用戶可信度與之比較來分辨用戶是否可信是一種方法，但是閾值的設置會對結果有一定的影響，增加了需要調試的參數。

文中利用K-means聚類的方法，將上述向量中的數據聚為兩類，排除可信度低的類別，利用剩下的可信用戶進行QoS預測，從而避免了閾值設置不當而產生的誤差，也避免了參數過多的問題。

2.3 算法步驟

輸入：QoS數據的訓練集TrainData，QoS數據的測試集TestData，近似鄰居數top-k，調和參數λ。

輸出：QoS預測值P(u,i)。

(1)對訓練集TrainData中的QoS數據，用式6計算出用戶的可信度，獲得用戶可信度向量T。

(2)利用K-means聚類方法對用戶可信度向量T進行聚類，其中類別數為2。排除可信度低的類別中的用戶，利用可信度高的類別中的用戶進行預測。

(3)使用式1計算出用戶的相似度。

(4)選取相似度最高的k個用戶作為此用戶的鄰居用戶N(u)。

(5)使用式2計算此用戶基于UPCC的QoS預測值。

(6)與UPCC相似，使用式3和式4計算出基于IPCC的QoS預測值。

(7)使用式5將得到的以用戶為基礎的和以項目為基礎的預測值通過調和參數λ進行加權求和，獲得最終的預測值。

(8)調節參數獲得最佳預測值。

3 實 驗

3.1 數據庫

文中使用的是香港中文大學搜集的數據集distributed reliability assessment mechanism for web services (WS-DREAM)[12-13]。該數據集描述了339個用戶在5 825個服務上的QoS評估結果。QoS項包括響應時間和吞吐量，選用響應時間來進行算法性能的驗證。

3.2 評價指標

選取平均絕對誤差(MAE)和均方根誤差(RMSE)作為最終預測結果準確率的評價指標。定義分別如下：

(7)

(8)

MAE計算預測值與真實值差的絕對值的平均值，其對所有差的權重是一樣的；RMSE在計算預測值與真實值差的和之前對其進行了平方操作，增大了對大誤差的權重。MAE和RMSE的值越小，說明預測的結果越好[14]。

3.3 實驗設置

為了更好地證明文中算法的有效性，在原有數據集的基礎上進行了人為加噪聲的操作。增加若干用戶，其QoS的值隨機生成；選取若干用戶，隨機交換其若干QoS值；選取若干用戶，隨機選定若干位置，給予該位置一個很大的QoS值。

服務的數量是巨大的，用戶只可能對其中的很少一部分進行訪問，因此用戶與其訪問過的服務的QoS矩陣是稀疏的，為了滿足現實情況，需要對數據進行稀疏操作。選取的稀疏度為5%～30%，以5%為間隔(稀疏度為5%即保留5%的數據用來訓練，剩余數據用來測試)。

在進行了5%的稀疏以及上述加噪后，各個用戶的可信度如圖2所示。

圖2 稀疏及加噪后用戶的可信度散點圖

由圖2可以看出，加噪用戶的可信度都處于可信度最低的水平(圖中圓圈所示)，可以很容易地用聚類進行排除。

3.4 實驗結果

為了降低預測結果的偶然性，進行了20次隨機試驗，使用MAE和RMSE評價預測結果的好壞，并同時選取了UPCC、IPCC、UIPCC作為對比算法[15]。最終結果以及對比算法的結果見表1和表2。

由表1和表2可以看出，在數據很稀疏的情況下，CRCF比UIPCC的預測準確率有很大的提升，也進一步說明了有噪聲數據對最終預測結果具有一定的影響。現實中數據是很稀疏的，并且干擾數據也較多，CRCF能有效提升預測準確率。

表1 不同稀疏度下MAE的對比結果

表2 不同稀疏度下RMSE的對比結果

4 結束語

文中提出了一種基于用戶可信度的Web服務推薦方法，首先計算出用戶的可信度，然后根據用戶可信度對用戶進行聚類，從而選取可信用戶使用協同過濾進行預測。該方法有效地避免了范圍異常數據及用戶惡意評價數據對最終預測結果的影響，提高了QoS預測精準度。但是該方法只考慮了用戶的可信度，并未考慮服務的可信度。下一步工作是充分挖掘不可信用戶的數據，發現可以分辨服務可信度的方法，找到一種更一般化的可信服務推薦模型。