基于隨機森林與用戶興趣概念格的Web服務質量預測

孫海瑞，朵 琳

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

0 引 言

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

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

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

1 隨機森林與用戶興趣概念格

1.1 構建隨機森林分類模型

1.1.1 特征提取與分類標簽處理

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

1.1.2 特征選擇

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

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

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

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

1.2.1 概念格

形式概念分析（Formal Concept Analysis，FCA）理論[9-11]是一種數據分析和知識表示的方法。概念格[14]是FCA中的一個基本結構，是數據分析與規則提取的有效工具。

對于一個形式背景K=(U,M,I)，U是對象集合，M是屬性集合，I?U×M是U和M之間的一個關系。若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的內涵，記作Int(C)。形式背景K的所有形式概念記作LC，由一個形式背景得出其全部概念及這些概念形成的Hasse圖稱為概念格的構造[9]。

1.2.2 構造用戶興趣概念格

QoS中的響應時間矩陣如表1所示。

表1 QoS中的響應時間矩陣（單位：s）

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

表2 用戶興趣形式背景

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

圖1 用戶興趣概念格

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

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

式中：C表示LQoS中任意的一個形式概念，u表示請求用戶，s表示調用的服務。

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

2 協同過濾預測QoS

2.1 計算相似度

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

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

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

在基于服務的協同過濾中，目標服務s與直接相似服務w的相似度計算公式為：

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

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

2.2 預測QoS

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

在基于服務的協同過濾中，采用式（16）來預測用戶u調用目標服務s的QoS：

通過加入參數λ（0≤λ≤1）來控制基于用戶和基于服務得到的兩個預測值的權重，從而實現混合協同過濾預測請求用戶u調用目標服務s的QoS值，即：

3 實驗結果

3.1 數據集

本文在WS-DREAM公開發布的數據集Dataset2 上進行了實驗。該數據集記錄了339名用戶調用 5 825個Web服務的QoS值，包括響應時間和吞吐量兩個屬性[12-15]。

3.2 評價指標

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

式中：N表示預測的所有QoS的個數，Pu.s表示請求用戶u調用服務s的實際QoS值，Qu.s表示請求用戶u調用服務s的預測QoS值。

3.3 實驗對比

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

（1）UPCC，使用皮爾遜相關系數（Pearson correlation coefficient，PCC）計算相似度的基于用戶的協同過濾算法。

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

（3）WSRec，融合基于用戶和基于服務的混合協同過濾算法。

（4）SVD[17]，采用矩陣因子分解算法對QoS進行預測。

（5）CACF[18]，采用CART分類樹與Slope One算法對QoS進行預測。

（6）BBCF[7]，結合貝葉斯分類器采用協同過濾算法對QoS進行預測。

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

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

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

3.4 隨機森林分類模型相關參數調優

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

表4 不同稀疏度下網格搜索選擇最優超參取值

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

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

在使用混合協同過濾算法對QoS進行預測時，需要引入參數λ來控制基于用戶和基于服務得到的兩個預測值的權重，從而使得最終預測結果達到最優。為了選擇最優的λ值，分別在稀疏度為85%和95%的歷史QoS數據下選擇不同的λ值進行實驗，具體實驗結果如圖4和圖5所示。

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

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

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

4 結 論

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