一種基于聚類的服務QoS值協(xié)同過濾預測方法

任麗芳,陳三麗

(1.山西財經(jīng)大學 信息學院,山西 太原 030006;2.太原師范學院 計算機科學與技術系,山西 晉中 030619)

0 引言

互聯(lián)網(wǎng)技術的飛速發(fā)展促進了計算模式的不斷演變,軟件、數(shù)據(jù)、存儲、計算力等都被打包成服務的形式交付用戶使用,服務的種類和數(shù)量急劇增長,出現(xiàn)了許多具有相同功能而不同QoS的服務[1-2]。而且現(xiàn)有研究已經(jīng)表明服務QoS是個性化的,即不同的用戶使用相同服務時其QoS值是不同的[3]。因此,如果能對用戶使用服務的QoS進行預測,不僅有助于用戶在相同功能的服務中選擇QoS更優(yōu)的服務,而且能主動地為用戶推薦QoS最優(yōu)的服務。服務QoS值預測正受到學術界和工業(yè)界越來越多的關注[4]。

現(xiàn)有的服務質(zhì)量預測方法通常是基于協(xié)同過濾的,包括基于內(nèi)存的方法和基于模型的方法。其中基于內(nèi)存的方法在本質(zhì)上是基于近鄰的方法,根據(jù)歷史數(shù)據(jù)挖掘用戶或服務之間的相似模式,然后基于K個最相似用戶或相似服務對目標用戶使用未知服務的QoS做出預測。這類方法在理論上可解釋性強,引起了國內(nèi)外學者的廣泛關注[5-14]。

基于相似用戶的方法將與目標用戶偏好相似的用戶的歷史記錄中QoS好的或者評價高的服務推薦給目標用戶。如Shao等人在文獻[5]考慮用戶間在相同服務上的相似的QoS體驗,提出了基于用戶的協(xié)同過濾個性化QoS 預測方法。在文獻[6]中Zheng和Lyu提出了一種基于用戶的面向服務的系統(tǒng)的可靠性預測方法,并指出可靠性可以擴展到其他QoS 屬性。他們用Pearson相關系數(shù)來度量用戶之間的相似性,利用相似用戶的數(shù)據(jù)來預測組件服務對于目標用戶的失敗率?；谙嗨品盏姆椒▽⑴c目標用戶的歷史記錄中QoS高或者評價好的相似服務推薦給用戶,常常與基于相似用戶的方法聯(lián)合使用。如Zheng 等人在文獻[7]和[8]提出了集成用戶相似的方法與服務相似的服務推薦方法,通過將基于用戶的QoS值與基于服務的QoS值加權(quán)平均來計算未知QoS值,提高了服務QoS 預測的準確率,為服務推薦提供了依據(jù)。Jiang等人在文獻[9]提出了一個協(xié)同過濾方法,該方法集成了基于相似用戶的協(xié)同過濾與基于相似服務的協(xié)同過濾,他們在度量用戶或者服務的相似性時通過考慮共同服務或者用戶的標準差改進了相似度計算方法,提出了集成相似用戶與相似服務的Top-N服務推薦方法,進一步提高了個性化QoS預測的準確率。Chen等[10]提出了基于特征聚類的潛在因子模型CFLFM來預測QoS。Min等[11]根據(jù)用戶的相似性設計了魯棒的服務QoS預測方法,阻止先令攻擊。Ren和Wang在文獻[12]利用SVM預測服務QoS是否能被目標用戶偏好,進而實現(xiàn)服務推薦。Hwang等[13]將服務的QoS值表示為具有概率函數(shù)的離散隨機變量,為服務選擇預測QoS值。Ma等[14]根據(jù)高度相似的相似不變性,用回歸的方法進行服務QoS預測。

這類基于近鄰的方法中K值的確定需要通過實驗進行參數(shù)調(diào)節(jié),不具有通用性。而且對于不同的目標用戶,使用相同的K值。然而實際中,有的用戶相似用戶較多,而有的用戶相似用戶較少。小K值使相似用戶較多的用戶失去部分相似用戶提供的信息,大K值又使相似用戶較少的用戶參考了許多本來不相似的用戶的信息,導致QoS預測的準確度不高。因此,本文提出一種基于聚類的服務QoS預測方法,該方法能根據(jù)數(shù)據(jù)本身疏密程度自然地個性化地確定相似用戶的個數(shù)。

1 問題描述

服務QoS是服務的推薦與服務選擇中的關鍵因素。然而,不同的用戶使用相同的服務其QoS值是不同的,因此,對于用戶尚未使用過的服務其QoS值是未知的,本文解決的問題正是對未知QoS值的預測。

定義1:目標用戶是指要為其使用服務能獲得的QoS值進行預測的用戶。

定義2:未知服務是指目標用戶尚未使用過的服務,對于該用戶而言他使用該服務能獲得的QoS值事先是未知的。

因此,服務QoS值預測的目的就是對目標用戶使用未知服務能獲得的QoS值進行預測。我們希望通過用戶使用服務的歷史QoS數(shù)據(jù),為目標用戶找到相似用戶,然后利用相似用戶使用該服務的QoS值對該用戶使用該服務的QoS值進行預測。因此,相似用戶的判定是服務QoS預測的核心步驟。

定義3:相似用戶是指在歷史記錄中,與目標用戶有共同使用過的服務的用戶,且在這些共同用戶上獲得的QoS值與目標用戶獲得的QoS值相等或接近。由目標用戶的所有相似用戶組成的集合為相似用戶集。

定義4:相似服務是指在歷史記錄中,與目標服務被共同用戶使用過的服務,且在這些共同用戶獲得的QoS值與目標服務獲得的QoS值相等或接近。由目標服務的所有相似服務組成的集合為相似服務集。

協(xié)同過濾思想認為在以往共同使用過的服務上有相似QoS值的用戶,在未知服務上得到的QoS也可能是相似的。因此,可以借助相似用戶在目標用戶的未知服務上獲得的QoS值對目標用戶使用未知服務的QoS值進行預測。

2 方法描述

CQoSP (Cluster-based QoS Prediction)是通過聚類識別相似用戶/服務,自然地確定相似用戶/服務,然后基于相似用戶/服務進行協(xié)同過濾服務推薦。

2.1 用戶/服務空間聚類

K個初始化的質(zhì)心的位置選擇對最后的聚類結(jié)果和運行時間都有很大的影響,因此需要選擇合適的K個質(zhì)心。如果僅僅是完全隨機的選擇,有可能導致算法收斂很慢。K-Means++算法就是對K-Means隨機初始化質(zhì)心的方法的優(yōu)化,如算法1所示。

算法1 K-Means++聚類算法

在該算法中,類簇個數(shù)K是輸入?yún)?shù),K值的確定也是聚類算法的關鍵。由于在用戶空間聚類之前,我們并不知道可能的類簇個數(shù),因此,CQoSP擬使用如式(1)定義的DB指數(shù)(Davies-Bouldin Index,DBI)作為聚類性能指標。

(1)

其中,avg(Ci)是對應于類簇Ci內(nèi)樣本間的平均距離,d(μi,μj)是類簇Ci與Cj中心點μi與μj間的距離。DBI越小聚類性能越好,因此CQoSP選取使DBI取得最小值的聚類個數(shù)K為類簇的個數(shù)。

經(jīng)過聚類相似用戶自然地被分到同一類簇,記用戶u的同類用戶集為C(u)。同時,一些不可信用戶在聚類后往往呈現(xiàn)為一種離群點,可以較為容易地被識別并從模型中過濾掉。

同樣地,服務空間也可以類似地進行聚類,以一種自然的方式發(fā)現(xiàn)相似服務。

2.2 用戶間/服務間相似性計算

屬于同一類簇的用戶,他們之間的相似度也會有差異。CQoSP細致地對待同類用戶之間相似度的差異,使用式(2)所示的改進的PCC計算每對相似用戶的相似度[16]。

(2)

相同的方法,可以計算服務i和服務j之間的相似度sim′(i,j)。

2.3 綜合預測

根據(jù)式(3),可以綜合基于用戶和基于服務的相似鄰居進行QoS值預測:

(3)

因此,基于聚類的服務QoS值預測方法的主要步驟如算法2所示。

算法2 基于聚類的服務QoS值CF預測算法

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)及環(huán)境

本文使用香港中文大學鄭子彬博士等人公開的真實數(shù)據(jù)集WSDream[1]中的Dataset2數(shù)據(jù)集進行測試,該數(shù)據(jù)集描述了真實世界中來自不同國家的339個用戶調(diào)用5 825個Web服務的QoS數(shù)據(jù),其中響應時間矩陣rtMatrix(單位:秒)和吞吐量矩陣tpMatrix(單位:比特率),皆為339行×5 825列的用戶-服務矩陣。矩陣中用-1表示服務調(diào)用發(fā)生失敗。

實驗中隨機將數(shù)據(jù)集分為兩部分,分別用于訓練和測試。由于實際應用中,數(shù)據(jù)通常是非常稀疏的,而WSDream測試數(shù)據(jù)集是稠密的,因此,本文隨機刪除一定數(shù)量的值,形成不同的密度的QoS矩陣。仿真實驗在MATLAB R2014b環(huán)境運行,操作系統(tǒng)Windows10 64位,處理器為Intel Core i7,3.6 GHz,內(nèi)存8 GB。

3.2 評價指標

本文對QoS預測值準確度的評價指標是式(4)定義的平均絕對誤差(Mean Absolute Error,MAE)和式(5)定義的均方根誤差(Root Mean Square Error,RMSE)。

(4)

(5)

其中是N為需要預測的QoS的總個數(shù)。MAE與RMSE越小,表示預測的準確度越高。

3.3 實驗結(jié)果分析

為了驗證CQoSP的有效性,本文首先考察不同數(shù)據(jù)的用戶/服務的最優(yōu)聚類,然后考察權(quán)重參數(shù)的不同值時的預測準確度,最后與3個經(jīng)典的基于近鄰方法比較QoS值的預測準確度。

(1)聚類個數(shù)K的確定

為得到相似用戶/服務類簇,首先對用戶/服務空間進行聚類,為得到最合理的聚類效果,分別考察不同聚類個數(shù)的DBI值。圖1關于用戶空間的聚類情況,其中圖1(a)是密度為0.1的響應時間矩陣在不同用戶聚類個數(shù)的DBI值,圖1(b)是密度為0.1的吞吐量矩陣在不同用戶聚類個數(shù)的DBI值。

Fig.1 Different DBI values with different user clusters on the dataset of density=0.1圖1 密度為0.1的數(shù)據(jù)集上，不同類簇個數(shù)K下，用戶空間的聚類DBI值

圖1(a)與圖1(b)分別反應的是響應時間數(shù)據(jù)上和吞吐量數(shù)據(jù)上用戶類簇個數(shù)K從2變到100時,DBI的值,有些K上聚類不收斂,沒有取到相應的點。從圖中不難發(fā)現(xiàn)吞吐量的用戶聚類收斂情況較多,取點較密,而且聚類效果較好。響應時間數(shù)據(jù)的最優(yōu)聚類個數(shù)K=12,此時DBI=0.196 3;而吞吐量數(shù)據(jù)的最優(yōu)聚類個數(shù)為K=54,此時DBI=0.020 7。

圖2是關于服務空間的聚類情況,其中圖1(a)是密度為0.1的響應時間矩陣在不同服務聚類個數(shù)的DBI值,圖2(b)是密度為0.1的吞吐量矩陣在不同服務聚類個數(shù)的DBI值。

Fig.2 Different DBI values with different services clusters on the dataset of density=0.1圖2 密度為0.1的數(shù)據(jù)集上，不同類簇個數(shù)K下，服務空間的聚類DBI值

圖2(a)與圖2(b)分別反應的是響應時間數(shù)據(jù)上和吞吐量數(shù)據(jù)上不同服務類簇個數(shù)時DBI的值。實驗中K從2取到300,為了圖形的清晰,只取了最優(yōu)聚類出現(xiàn)的一段。實驗結(jié)果表明,響應時間數(shù)據(jù)的最優(yōu)聚類個數(shù)K=216,此時DBI=0.050 6;而吞吐量數(shù)據(jù)的最優(yōu)聚類個數(shù)為K=295,此時DBI=0.045 6。

表1是不同密度的響應時間數(shù)據(jù)和吞吐量數(shù)據(jù)在用戶空間和服務空間的最優(yōu)聚類個數(shù)及相應的DBI,本文后續(xù)實驗的聚類個數(shù)參照本表設置。

(2)與其他方法的比較

為驗證本文提出的CQoSP方法的有效性,與UPCC(user-based collaborative filtering method using PCC,基于用戶的PCC協(xié)同過濾)[5]、IPCC(item-based collaborative filtering method using PCC,基于項目的PCC協(xié)同過濾)[17]、UIPCC(user-based and item-based collaborative filtering method using PCC,基于用戶和項目的PCC協(xié)同過濾)[8]3種方法比較QoS預測值的準確度。

表1 不同密度下響應時間與吞吐量在用戶和服務空間的最優(yōu)聚類個數(shù)及相應的DBI

表2 準確度比較

從表2可以看出,CQoSP方法在響應時間和吞吐量數(shù)據(jù)集的不同密度上的預測準確度比其他方法都有明顯提高,說明按照數(shù)據(jù)本身的特性自然地確定相似用戶以及相似服務的個數(shù),有助于提高基于近鄰的預測方法的準確度。

4 結(jié)論

本文提出了基于聚類的服務QoS預測方法CQoSP,首先通過聚類分析出相似用戶/服務類簇,再進一步計算同一類簇的用戶/服務與目標用戶/服務的相似度,根據(jù)相似程度確定他們提供的數(shù)據(jù)的權(quán)重,最后按權(quán)重綜合基于相似用戶的預測值與基于相似服務的預測值得出最終的預測值。在真實QoS數(shù)據(jù)集WSDream上進行了實驗,在與3種經(jīng)典方法的比較中驗證了CQoSP方法對預測準確度的提升。由于Web服務中的服務和用戶都在不斷增長,且動態(tài)環(huán)境中服務的QoS具有不確定性,未來將結(jié)合貝葉斯網(wǎng)絡探索大數(shù)據(jù)情境下服務QoS值的個性化預測。