曹繼承，朱小柯，荊曉遠(yuǎn),，吳 飛

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003；2.武漢大學(xué) 計(jì)算機(jī)學(xué)院 軟件工程國家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430072；3.南京郵電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210003)

0 引 言

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

協(xié)同過濾是目前廣泛使用的一種推薦技術(shù)[3]?；趨f(xié)同過濾的Web服務(wù)推薦系統(tǒng)通過搜集用戶的Web服務(wù)訪問記錄，利用用戶的反饋數(shù)據(jù)為用戶提供個(gè)性化的服務(wù)推薦[4]。但是大多數(shù)推薦系統(tǒng)都是默認(rèn)用戶的數(shù)據(jù)是可信的。而現(xiàn)實(shí)生活中，用戶的數(shù)據(jù)會(huì)因?yàn)楦鞣N原因而變得不可信，包括設(shè)備異常或惡意評價(jià)等。如果不考慮用戶的可信度，會(huì)對最終預(yù)測結(jié)果產(chǎn)生嚴(yán)重的干擾。

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

1 相關(guān)工作

1.1 協(xié)同過濾

協(xié)同過濾是一種廣泛使用的推薦技術(shù)，主要分為基于歷史數(shù)據(jù)的方法和基于模型的方法。基于歷史數(shù)據(jù)的方法首先搜集用戶歷史數(shù)據(jù)，然后計(jì)算用戶或者項(xiàng)目的相似度，最終通過相似用戶或項(xiàng)目產(chǎn)生推薦結(jié)果?；谀Ｐ偷姆椒ㄔ谟?xùn)練數(shù)據(jù)上通過數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)算法找到相應(yīng)的模型，然后完成推薦。相比前者，基于歷史數(shù)據(jù)的方法因其易于理解和使用在實(shí)際中應(yīng)用廣泛。文中算法屬于基于歷史數(shù)據(jù)的方法。

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

UPCC利用式1計(jì)算用戶u和用戶v的相似度，然后找到相似度最高的k個(gè)用戶，最后通過式2進(jìn)行QoS值的預(yù)測。

(1)

(2)

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

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

(3)

(4)

UIPCC是將UPCC和IPCC的兩個(gè)結(jié)果利用式5進(jìn)行加權(quán)求和，從而獲取更精確的預(yù)測，這里不再展開描述。

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

(5)

1.2 用戶可信度

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

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

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

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

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

2.1 用戶可信度的計(jì)算

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

TRDt=

(6)

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

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

2.2 不可信用戶的排除

通過設(shè)置閾值并將用戶可信度與之比較來分辨用戶是否可信是一種方法，但是閾值的設(shè)置會(huì)對結(jié)果有一定的影響，增加了需要調(diào)試的參數(shù)。

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

2.3 算法步驟

輸入：QoS數(shù)據(jù)的訓(xùn)練集TrainData，QoS數(shù)據(jù)的測試集TestData，近似鄰居數(shù)top-k，調(diào)和參數(shù)λ。

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

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

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

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

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

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

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

(7)使用式5將得到的以用戶為基礎(chǔ)的和以項(xiàng)目為基礎(chǔ)的預(yù)測值通過調(diào)和參數(shù)λ進(jìn)行加權(quán)求和，獲得最終的預(yù)測值。

(8)調(diào)節(jié)參數(shù)獲得最佳預(yù)測值。

3 實(shí) 驗(yàn)

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

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

3.2 評價(jià)指標(biāo)

選取平均絕對誤差(MAE)和均方根誤差(RMSE)作為最終預(yù)測結(jié)果準(zhǔn)確率的評價(jià)指標(biāo)。定義分別如下：

(7)

(8)

MAE計(jì)算預(yù)測值與真實(shí)值差的絕對值的平均值，其對所有差的權(quán)重是一樣的；RMSE在計(jì)算預(yù)測值與真實(shí)值差的和之前對其進(jìn)行了平方操作，增大了對大誤差的權(quán)重。MAE和RMSE的值越小，說明預(yù)測的結(jié)果越好[14]。

3.3 實(shí)驗(yàn)設(shè)置

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

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

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

圖2 稀疏及加噪后用戶的可信度散點(diǎn)圖

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

3.4 實(shí)驗(yàn)結(jié)果

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

由表1和表2可以看出，在數(shù)據(jù)很稀疏的情況下，CRCF比UIPCC的預(yù)測準(zhǔn)確率有很大的提升，也進(jìn)一步說明了有噪聲數(shù)據(jù)對最終預(yù)測結(jié)果具有一定的影響?，F(xiàn)實(shí)中數(shù)據(jù)是很稀疏的，并且干擾數(shù)據(jù)也較多，CRCF能有效提升預(yù)測準(zhǔn)確率。

表1 不同稀疏度下MAE的對比結(jié)果

表2 不同稀疏度下RMSE的對比結(jié)果

4 結(jié)束語

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