基于隨機(jī)森林與用戶興趣概念格的Web服務(wù)質(zhì)量預(yù)測

孫海瑞，朵 琳

（昆明理工大學(xué) 信息工程與自動化學(xué)院，云南 昆明 650504）

0 引 言

隨著網(wǎng)絡(luò)的快速發(fā)展，Web服務(wù)變得越來越豐富，但同時也給用戶帶來了信息過載的麻煩。面對大量功能相似的Web服務(wù)時，如何為用戶推薦最優(yōu)服務(wù)成為一個亟待解決的問題[1]。由于Web服務(wù)的服務(wù)質(zhì)量（Quality of Service，QoS）能夠很好地區(qū)分Web服務(wù)的性能，因此成為用戶選擇Web服務(wù)的一個重要的非功能指標(biāo)[2]。

協(xié) 同 過 濾(Collaborative Filtering，CF)[3]運 用于QoS預(yù)測時，常用皮爾遜相關(guān)系數(shù)計算相似度。SHAO等人[4]利用基于用戶的CF，計算用戶之間的相似度，從而預(yù)測QoS。ZHENG等人[5]進(jìn)一步計算了服務(wù)之間的相似度，利用混合CF預(yù)測QoS。申利民等人[6]挖掘了QoS數(shù)據(jù)間的隱藏關(guān)系，添加比率參數(shù)改進(jìn)混合CF對QoS的預(yù)測。任等人[7]利用內(nèi)在特征建立貝葉斯分類模型，并將分類概率作為權(quán)重因子運用于QoS預(yù)測中。任等人[7]將用戶的IP地址、經(jīng)緯度、所在國家等內(nèi)在屬性作為特征構(gòu)建貝葉斯分類器，并將分類概率作為權(quán)重因子進(jìn)行服務(wù)質(zhì)量的預(yù)測。YANG等人[8]利用位置信息和QoS歷史數(shù)據(jù)對用戶和服務(wù)進(jìn)行聚類，并根據(jù)聚類結(jié)果對用戶進(jìn)行個性化的服務(wù)推薦。

為了進(jìn)一步解決QoS預(yù)測中數(shù)據(jù)稀疏以及噪聲數(shù)據(jù)問題，提出一種基于隨機(jī)森林與用戶興趣概念格的Web服務(wù)QoS預(yù)測方法（Prediction of QoS for Web service based on random forest and user interest concept lattice，RF-UICL）。針對噪聲數(shù)據(jù)，根據(jù)用戶與服務(wù)的均值、方差、經(jīng)度、緯度特征構(gòu)建隨機(jī)森林分類模型，然后基于同一分類結(jié)果選擇相似鄰居，從而實現(xiàn)噪聲過濾的目的。引入用戶興趣概念格的思想，將相似鄰居劃分為直接相似鄰居和間接相似鄰居，并改進(jìn)相似度的計算方法，分別計算其相似度。除此之外，提出一種改進(jìn)的預(yù)測公式，使用混合協(xié)同過濾方法計算請求用戶調(diào)用目標(biāo)服務(wù)的QoS值。

1 隨機(jī)森林與用戶興趣概念格

1.1 構(gòu)建隨機(jī)森林分類模型

1.1.1 特征提取與分類標(biāo)簽處理

根據(jù)歷史QoS數(shù)據(jù)計算用戶與服務(wù)的均值與方差，并結(jié)合經(jīng)緯度特征構(gòu)建特征向量[User-mean,User-var,Service-mean,Service-var,User-la,User-lo,Service-la,Service-lo]。對于每一個用戶對或服務(wù)對，都擁有唯一的特征向量。對數(shù)據(jù)集中響應(yīng)時間為0～20 s的連續(xù)型數(shù)據(jù)，將其向下取整得到離散型整數(shù)分類標(biāo)簽[0,1,…,19]。將[2,3,…,19]歸為一類，意為服務(wù)質(zhì)量較差，[0]意為服務(wù)質(zhì)量較優(yōu)，[1]意為服務(wù)質(zhì)量一般。

1.1.2 特征選擇

本文構(gòu)建的隨機(jī)森林分類模型采用CART分類樹作為子樹，使用基尼（Gini）系數(shù)來衡量數(shù)據(jù)的不確定性，以衡量結(jié)果作為CART分類樹分裂節(jié)點的依據(jù)?；嵯禂?shù)越大，數(shù)據(jù)的不確定性也就越大。

設(shè)待分類的數(shù)據(jù)樣本共有K個類別，某一樣本點屬于第k類的概率為Pk，則其概率分布的基尼系數(shù)為：

對于已知的數(shù)據(jù)樣本集合D，設(shè)該數(shù)據(jù)樣本集合共有K個類別，Ck為數(shù)據(jù)集D中屬于第k類的樣本子集，|Ck|與|D|分別表示屬于第k類的樣本子集個數(shù)與數(shù)據(jù)集的樣本總個數(shù)，則D的基尼系 數(shù)為：

1.2 用戶興趣概念格劃分相似鄰居

1.2.1 概念格

形式概念分析（Formal Concept Analysis，F(xiàn)CA）理論[9-11]是一種數(shù)據(jù)分析和知識表示的方法。概念格[14]是FCA中的一個基本結(jié)構(gòu)，是數(shù)據(jù)分析與規(guī)則提取的有效工具。

對于一個形式背景K=(U,M,I)，U是對象集合，M是屬性集合，I?U×M是U和M之間的一個關(guān)系。若A?U，B?M，則：

式中：f(A)是A中所有對象共有的屬性，g(B)是B中所有屬性共有的對象。若f(A)=B，g(B)=A，則(A,B)是一個形式概念，記為C。A是形式概念C的外延，記作Ext(C)；B是形式概念C的內(nèi)涵，記作Int(C)。形式背景K的所有形式概念記作LC，由一個形式背景得出其全部概念及這些概念形成的Hasse圖稱為概念格的構(gòu)造[9]。

1.2.2 構(gòu)造用戶興趣概念格

QoS中的響應(yīng)時間矩陣如表1所示。

表1 QoS中的響應(yīng)時間矩陣（單位：s）

將響應(yīng)時間矩陣轉(zhuǎn)化為代表用戶興趣的二進(jìn)制矩陣，對響應(yīng)時間在2 s以內(nèi)的服務(wù)設(shè)置為 “1”代表用戶感興趣，其余各值設(shè)為“0”代表用 戶不感興趣，從而可將此二進(jìn)制矩陣當(dāng)作用戶形式背景。表2是從表1中提取出來的用戶興趣形式背景K=(U,S,Q)，其中U表示所有用戶集合，S表示所有服務(wù)集合，Q表示U和S之間的一個關(guān)系。

表2 用戶興趣形式背景

通過用戶興趣形式背景K可以構(gòu)造用戶興趣概念格LQoS[10]，基于表2構(gòu)造的用戶興趣概念格如圖1所示。

圖1 用戶興趣概念格

1.2.3 劃分直接相似鄰居和間接相似鄰居

根據(jù)隨機(jī)森林分類模型，判斷目標(biāo)用戶調(diào)用目標(biāo)服務(wù)的類別標(biāo)簽，并將其他已調(diào)用過該服務(wù)且與目標(biāo)用戶分類標(biāo)簽一致的用戶作為其相似鄰居Su。服務(wù)的相似鄰居Ss同樣也要根據(jù)隨機(jī)森林模型的分類結(jié)果進(jìn)行確定，從而過濾掉噪聲數(shù)據(jù)的影響。確定用戶和服務(wù)的相似鄰居Su和Ss后，通過用戶興趣概念格來查找用戶和服務(wù)的最相似鄰居MSu和MSs。在用戶興趣概念格LQoS中，從概念格的頂部到底部來搜索MSu、MSs的定義為：

式中：C表示LQoS中任意的一個形式概念，u表示請求用戶，s表示調(diào)用的服務(wù)。

同理可以得到服務(wù)s的直接相似鄰居Ssd和間接相似鄰居Ssid，其定義為：

2 協(xié)同過濾預(yù)測QoS

2.1 計算相似度

直接相似鄰居對調(diào)用的服務(wù)具有較高的興趣，向用戶推薦的可能性很大，在QoS值的預(yù)測過程中影響也比較明顯。

在基于用戶的協(xié)同過濾推薦方法中，計算請求用戶u和直接相似用戶v之間相似度的公式為：

式中：Su表示請求用戶u調(diào)用過的服務(wù)集合，Sv表示直接相似用戶v調(diào)用過的服務(wù)集合，|Su∩Sv|表示請求用戶u和直接相似用戶v共同調(diào)用過的服務(wù)個數(shù)，|Su|和|Sv|分別表示請求用戶u和直接相似用戶v調(diào)用過的服務(wù)個數(shù)，qu.i表示用戶u對調(diào)用服務(wù)i的QoS值，qv.j表示用戶v對調(diào)用服務(wù)j的QoS值。

在基于服務(wù)的協(xié)同過濾中，目標(biāo)服務(wù)s與直接相似服務(wù)w的相似度計算公式為：

式中：Us表示調(diào)用過目標(biāo)服務(wù)s的用戶集合，Uw表示調(diào)用過直接相似服務(wù)w的用戶集合，|Us∩Uw|表示共同調(diào)用過目標(biāo)服務(wù)s和直接相似服務(wù)w的用戶個數(shù)，|Us|和|Uw|分別表示調(diào)用過目標(biāo)服務(wù)s和直接相似服務(wù)w的用戶數(shù)，qi.s表示用戶i對調(diào)用服務(wù)s的QoS值，qj.w表示用戶j對調(diào)用服務(wù)w的QoS值。

間接相似鄰居的相似程度要小于直接相似鄰居，向請求用戶推薦的可能性偏小，對QoS預(yù)測的影響也偏弱一些。在基于用戶與基于服務(wù)的協(xié)同過濾中，間接相似用戶或服務(wù)之間的相似度為：

2.2 預(yù)測QoS

因為在相似鄰居選擇時已經(jīng)通過隨機(jī)森林分類模型進(jìn)行了篩選，所以相似鄰居的QoS值是值得信任的?；诖?，提出一種新的預(yù)測方法。在基于用戶的協(xié)同過濾推薦方法中，通過直接相似鄰居和間接相似鄰居的相似度來預(yù)測請求用戶u調(diào)用目標(biāo)服務(wù)s的QoS值，即：

在基于服務(wù)的協(xié)同過濾中，采用式（16）來預(yù)測用戶u調(diào)用目標(biāo)服務(wù)s的QoS：

通過加入?yún)?shù)λ（0≤λ≤1）來控制基于用戶和基于服務(wù)得到的兩個預(yù)測值的權(quán)重，從而實現(xiàn)混合協(xié)同過濾預(yù)測請求用戶u調(diào)用目標(biāo)服務(wù)s的QoS值，即：

3 實驗結(jié)果

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

本文在WS-DREAM公開發(fā)布的數(shù)據(jù)集Dataset2 上進(jìn)行了實驗。該數(shù)據(jù)集記錄了339名用戶調(diào)用 5 825個Web服務(wù)的QoS值，包括響應(yīng)時間和吞吐量兩個屬性[12-15]。

3.2 評價指標(biāo)

采用平均絕對誤差（Mean Absolute Error，MAE）和歸一化平均絕對誤差（Normalized Mean Absolute Error，NMAE）[16]來衡量預(yù)測精度，即：

式中：N表示預(yù)測的所有QoS的個數(shù)，Pu.s表示請求用戶u調(diào)用服務(wù)s的實際QoS值，Qu.s表示請求用戶u調(diào)用服務(wù)s的預(yù)測QoS值。

3.3 實驗對比

為了驗證本文所提RF-UICL方法的有效性，將RF-UICL方法與以下6種方法分別在不同的稀疏度情況下進(jìn)行實驗對比。

（1）UPCC，使用皮爾遜相關(guān)系數(shù)（Pearson correlation coefficient，PCC）計算相似度的基于用戶的協(xié)同過濾算法。

（2）IPCC，使用PCC計算服務(wù)之間相似度的基于服務(wù)的協(xié)同過濾算法。

（3）WSRec，融合基于用戶和基于服務(wù)的混合協(xié)同過濾算法。

（4）SVD[17]，采用矩陣因子分解算法對QoS進(jìn)行預(yù)測。

（5）CACF[18]，采用CART分類樹與Slope One算法對QoS進(jìn)行預(yù)測。

（6）BBCF[7]，結(jié)合貝葉斯分類器采用協(xié)同過濾算法對QoS進(jìn)行預(yù)測。

不同稀疏度下各種方法的MAE與NMAE對比如表3所示。

表3 不同稀疏度下各種方法的MAE與NMAE對比

由表3可知，在不同的歷史QoS數(shù)據(jù)稀疏度下，RF-UICL方法在QoS預(yù)測精度上相較于其他6種方法都有著一定的提升，在數(shù)據(jù)稀疏度比較高的情況下依舊有著更加良好的預(yù)測精度，從而驗證了RF-UICL方法對噪聲數(shù)據(jù)有著一定的過濾 作用。

3.4 隨機(jī)森林分類模型相關(guān)參數(shù)調(diào)優(yōu)

為了防止隨機(jī)森林分類模型過擬合，對其內(nèi)在參數(shù)進(jìn)行最優(yōu)化選擇，從而提高模型的泛化能力。針 對 參 數(shù)n_estimators，min_samples_split，min_samples_leaf，max_depth，根據(jù)網(wǎng)格搜索選擇最優(yōu)超參取值，并通過不同稀疏度下參數(shù)的取值分析模型對參數(shù)的敏感性，具體如表4所示。

表4 不同稀疏度下網(wǎng)格搜索選擇最優(yōu)超參取值

由表4可知，在不同的稀疏度下模型對參數(shù)不敏感，因而本文將隨機(jī)森林分類模型的參數(shù)設(shè)置為n_estimators=10，min_samples_split=30，min_samples_leaf=10，max_depth=5。

3.5 不同λ值對實驗精度的影響

在使用混合協(xié)同過濾算法對QoS進(jìn)行預(yù)測時，需要引入?yún)?shù)λ來控制基于用戶和基于服務(wù)得到的兩個預(yù)測值的權(quán)重，從而使得最終預(yù)測結(jié)果達(dá)到最優(yōu)。為了選擇最優(yōu)的λ值，分別在稀疏度為85%和95%的歷史QoS數(shù)據(jù)下選擇不同的λ值進(jìn)行實驗，具體實驗結(jié)果如圖4和圖5所示。

圖4 不同稀疏度下λ值對MAE的影響

圖5 不同稀疏度下λ值對NMAE的影響

根據(jù)圖4和圖5，在稀疏度為85%的情況下，λ為0.6時的MAE值最小，λ為0.7時的NMAE值最小。在稀疏度為95%的情況下，λ為0.7時的MAE值與NMAE值都達(dá)到最小。RF-UICL方法對參數(shù)λ相對不敏感，因而將參數(shù)λ設(shè)置為0.7。

4 結(jié) 論

本文提出了一種基于隨機(jī)森林與用戶興趣概念格的Web服務(wù)QoS預(yù)測方法（RF-UICL），通過隨機(jī)森林分類模型過濾噪聲數(shù)據(jù)，考慮到相似鄰居在QoS預(yù)測過程中的影響程度不同引入了用戶興趣概念格的思想，將相似鄰居分為直接相似鄰居和間接相似鄰居，然后采用改進(jìn)的相似度計算方法分別計算其相似度，同時通過混合CF預(yù)測請求用戶調(diào)用目標(biāo)服務(wù)的QoS。在真實的Web服務(wù)QoS數(shù)據(jù)集上，驗證了RF-UICL方法能夠有效提高預(yù)測精度。在今后的工作中，將繼續(xù)研究Web服務(wù)推薦，并從提高分類準(zhǔn)確度和加快用戶興趣概念格構(gòu)造等方面入手，從而提高服務(wù)質(zhì)量的預(yù)測。