基于用戶和服務(wù)區(qū)域信息的個(gè)性化Web服務(wù)質(zhì)量預(yù)測(cè)

魯城華，寇紀(jì)淞

1 天津大學(xué) 管理與經(jīng)濟(jì)學(xué)部，天津 300072 2 天津財(cái)經(jīng)大學(xué) 珠江學(xué)院，天津 301811

引言

隨著面向服務(wù)計(jì)算的普及，涌現(xiàn)大量Web服務(wù)，基于服務(wù)質(zhì)量(quality of service, QoS)的研究成為熱點(diǎn)[1-2]，如服務(wù)選擇[3]、服務(wù)推薦[4]和服務(wù)組合等[5]。因此，提供準(zhǔn)確的QoS信息是所有基于QoS研究工作的前提。

QoS信息包括兩種類型，第1種獨(dú)立于用戶，其值由服務(wù)提供者統(tǒng)一提供，如服務(wù)價(jià)格[6]。第2種QoS信息與用戶和服務(wù)的環(huán)境相關(guān)，如響應(yīng)時(shí)間[7]，其值容易受到異步的用戶端網(wǎng)絡(luò)環(huán)境、拓?fù)浣Y(jié)構(gòu)以及服務(wù)器端設(shè)備水平和傳輸效率的影響，測(cè)量QoS信息需要用戶對(duì)服務(wù)調(diào)用之后才能得到。

面對(duì)QoS信息的千變?nèi)f化，獲得準(zhǔn)確并具有個(gè)性化的QoS信息非常重要[8]。然而，要求每個(gè)用戶調(diào)用所有服務(wù)并返回準(zhǔn)確的QoS信息是不現(xiàn)實(shí)的。一方面，Web服務(wù)數(shù)量龐大，這項(xiàng)工作耗時(shí)巨大；另一方面，用戶并非專家，難以保證用戶評(píng)估QoS信息的準(zhǔn)確性。因此，有必要找到一種有效的QoS預(yù)測(cè)方法而無需進(jìn)行繁瑣的服務(wù)調(diào)用[9]。

已有研究采用協(xié)同過濾方法對(duì)歷史QoS信息進(jìn)行分析并實(shí)現(xiàn)預(yù)測(cè)[10]，其核心是使用相似用戶或服務(wù)的QoS信息預(yù)測(cè)未知QoS信息，已經(jīng)被證實(shí)具有良好的預(yù)測(cè)效果[11]。傳統(tǒng)的協(xié)同過濾方法僅使用已有的QoS信息，忽略了一些客觀因素的影響，如用戶和服務(wù)所在國(guó)家、省市地區(qū)等區(qū)域因素。同一地區(qū)的用戶和服務(wù)具有相似的經(jīng)濟(jì)水平，使其具有相似的硬件環(huán)境。因此，在同一區(qū)域的用戶調(diào)用相同的服務(wù)通常產(chǎn)生相似的QoS信息。為了提高QoS預(yù)測(cè)的準(zhǔn)確性，本研究將全局QoS信息與用戶和服務(wù)區(qū)域信息相結(jié)合，提出一種基于用戶和服務(wù)區(qū)域信息的QoS預(yù)測(cè)方法。

1 相關(guān)研究評(píng)述

近年來，互聯(lián)網(wǎng)上涌現(xiàn)出越來越多具有相同或者相似功能的Web服務(wù)[12]，因此，QoS屬性成為大眾關(guān)注的熱點(diǎn)[13]。同時(shí)，很多基于QoS的研究工作逐漸發(fā)展起來，如服務(wù)選擇[14-15]、服務(wù)推薦[16]、服務(wù)組合[17-18]和服務(wù)信任[19]等。因此，為這些研究工作提供準(zhǔn)確的QoS信息是極其重要的。

目前對(duì)QoS預(yù)測(cè)的研究還處于起步階段[20]。最簡(jiǎn)單的預(yù)測(cè)方法是平均值方法，該方法包括用戶平均值方法和服務(wù)平均值方法，前者是以計(jì)算該用戶使用的其他服務(wù)的QoS信息平均值作為該用戶對(duì)當(dāng)前未使用服務(wù)的QoS信息；后者是以計(jì)算所有使用過該服務(wù)的用戶的QoS信息平均值作為當(dāng)前用戶使用該服務(wù)的QoS信息。平均值方法較為簡(jiǎn)單，只是計(jì)算QoS信息的平均值，這種方法不能準(zhǔn)確地反映出不同用戶QoS之間的個(gè)性化差異[21]。本研究將對(duì)未知QoS進(jìn)行個(gè)性化的預(yù)測(cè)，以提高預(yù)測(cè)的準(zhǔn)確性。

受用戶協(xié)作思想的啟發(fā)，協(xié)同過濾方法被應(yīng)用到QoS的預(yù)測(cè)中[22]。協(xié)同過濾方法對(duì)領(lǐng)域知識(shí)沒有要求[23]，因此被廣泛應(yīng)用于不同的領(lǐng)域。通常將協(xié)同過濾方法分為基于記憶[24]和基于模型兩種類型[25]。

基于記憶的協(xié)同過濾方法主要包括基于用戶的計(jì)算、基于項(xiàng)目的計(jì)算以及兩者的混合[26]?；谟洃浀腝oS預(yù)測(cè)方法是根據(jù)用戶使用Web服務(wù)之后所反饋的QoS信息計(jì)算兩個(gè)用戶(或服務(wù))之間的相似度，進(jìn)而選擇相似度比較高的一組用戶(或服務(wù))的QoS信息預(yù)測(cè)未知的QoS值。SHAO et al.[27]提出使用基于用戶的協(xié)同過濾方法進(jìn)行個(gè)性化的QoS預(yù)測(cè)，以用戶的歷史使用經(jīng)驗(yàn)(即使用服務(wù)之后反饋的QoS信息)為基礎(chǔ)，采用皮爾遜相關(guān)系數(shù)的相似性度量方法計(jì)算兩個(gè)用戶之間的相似性，然后根據(jù)當(dāng)前用戶的鄰居用戶集合對(duì)其未使用服務(wù)的QoS信息進(jìn)行預(yù)測(cè)；DING et al.[28]提出一種基于服務(wù)相似性計(jì)算的QoS預(yù)測(cè)方法，然后將QoS屬性值的預(yù)測(cè)與用戶滿意度相結(jié)合，評(píng)價(jià)服務(wù)的可信度。該研究改進(jìn)了傳統(tǒng)的皮爾遜相關(guān)系數(shù)的相似性度量方法，降低了消極QoS屬性對(duì)預(yù)測(cè)結(jié)果的影響，提高了QoS預(yù)測(cè)的準(zhǔn)確性。ZHENG et al.[11]提出一種混合的基于用戶和服務(wù)的協(xié)同過濾方法預(yù)測(cè)未知的QoS信息，該方法獲得了較好的預(yù)測(cè)效果；SILIC et al.[29]也提出一種混合的協(xié)同過濾方法預(yù)測(cè)服務(wù)的可靠性，主要根據(jù)用戶的地理位置和服務(wù)的地理位置(根據(jù)IP地址區(qū)分)、服務(wù)負(fù)載和服務(wù)級(jí)別(根據(jù)服務(wù)的計(jì)算消耗區(qū)分)4個(gè)方面的內(nèi)容。用這4個(gè)方面的線性組合預(yù)測(cè)服務(wù)可靠性，一方面，服務(wù)提供者可能不愿意分享服務(wù)的負(fù)載和計(jì)算消耗值；另一方面，該方法只考慮了局部影響而忽略了用戶間和服務(wù)間的全局關(guān)系?；谟洃浀膮f(xié)同預(yù)測(cè)方法僅從用戶或者服務(wù)角度采用已有的QoS信息進(jìn)行預(yù)測(cè)，忽略了位置信息等一些客觀因素，且當(dāng)計(jì)算規(guī)模增大時(shí)，該方法的計(jì)算效率有所降低。本研究結(jié)合用戶和服務(wù)的位置信息，從全局和局部?jī)蓚€(gè)角度對(duì)未知QoS進(jìn)行高效的個(gè)性化預(yù)測(cè)。

隨著Web服務(wù)規(guī)模的不斷擴(kuò)大，大部分研究人員開始采用一種更高效的預(yù)測(cè)方法，即基于模型的預(yù)測(cè)。最具有代表性的模型方法是矩陣因子分解法[30]，該方法已經(jīng)被證明能夠有效、準(zhǔn)確地處理大規(guī)模的服務(wù)數(shù)據(jù)集。該方法將用戶和服務(wù)分別映射到一個(gè)低維的特征空間，用兩者的乘積代表原來的QoS矩陣。將每一個(gè)用戶和服務(wù)表示成一個(gè)低維潛在的特征向量(或者叫潛在因子向量)[31]，將特征向量里的每一個(gè)特征視為關(guān)于服務(wù)或者用戶興趣偏好的任何一個(gè)方面或者其他隱含的特征。當(dāng)矩陣被分解完成之后，根據(jù)得到的兩個(gè)低維矩陣乘積與原QoS矩陣的擬合得到一個(gè)最小化的目標(biāo)函數(shù)，該函數(shù)的目標(biāo)就是使預(yù)測(cè)的QoS值盡量接近真實(shí)已知的QoS值[32]。經(jīng)過函數(shù)的優(yōu)化學(xué)習(xí)，最終得到準(zhǔn)確性比較高的QoS預(yù)測(cè)矩陣。ZHENG et al.[25]采用矩陣因子分解的方法，將用戶和服務(wù)的QoS矩陣分解為兩個(gè)低維的用戶特征矩陣和服務(wù)特征矩陣，然后結(jié)合當(dāng)前用戶的鄰居用戶集合的QoS信息預(yù)測(cè)未知的QoS信息，該方法能夠處理較大的QoS數(shù)據(jù)集，且具有較高的計(jì)算效率；YIN et al.[33]在矩陣因子分解模型中引入用戶的位置信息作為正則項(xiàng)，根據(jù)位置信息對(duì)用戶進(jìn)行篩選，計(jì)算滿足一定距離區(qū)間內(nèi)的用戶之間的相似程度，根據(jù)相似性排序得到當(dāng)前用戶的鄰居用戶集合，對(duì)建立的函數(shù)模型進(jìn)行優(yōu)化學(xué)習(xí)，得到QoS預(yù)測(cè)矩陣。該方法提高了QoS預(yù)測(cè)的效率和準(zhǔn)確率，但沒有考慮服務(wù)的位置信息。

雖然傳統(tǒng)的協(xié)同過濾方法得到了較好的QoS預(yù)測(cè)結(jié)果，但仍存在一定弊端。大部分研究?jī)H采用已有的QoS信息進(jìn)行預(yù)測(cè)，忽略了用戶和服務(wù)的位置信息等一些客觀因素的影響。即使一小部分研究考慮了位置信息，但它們沒有將全局的QoS信息影響與局部的區(qū)域影響相結(jié)合。相比之下，本研究將全局的QoS信息與用戶服務(wù)的局部區(qū)域信息相結(jié)合進(jìn)行預(yù)測(cè)，采用綜合的服務(wù)數(shù)據(jù)集，證明本研究方法具有有效性。

2 問題描述

本研究的目的是將歷史QoS信息與用戶和服務(wù)的區(qū)域信息相結(jié)合，進(jìn)行個(gè)性化的QoS信息預(yù)測(cè)。在實(shí)際應(yīng)用中，可能存在大量的用戶和服務(wù)。假設(shè)用戶數(shù)量為M，服務(wù)數(shù)量為N，用戶使用服務(wù)的QoS信息可以表示為M×N的矩陣R，矩陣中每個(gè)元素ri,j為ui用戶調(diào)用sj服務(wù)的QoS信息，i為用戶的序號(hào)值，i=1,2,…,f,…,M，j為服務(wù)的序號(hào)值，j=1,2,…,k,…,N。未被用戶使用的服務(wù)的QoS信息為空，即要預(yù)測(cè)的未知值。本研究的目標(biāo)是創(chuàng)建一個(gè)預(yù)測(cè)模型,有效而準(zhǔn)確地填充這些未知值。

為了便于理解，圖1給出一個(gè)現(xiàn)實(shí)世界中Web服務(wù)調(diào)用場(chǎng)景，該場(chǎng)景能夠充分說明考慮用戶和服務(wù)區(qū)域信息的必要性。假設(shè)ua用戶分別調(diào)用來自兩個(gè)不同國(guó)家的兩個(gè)功能相同的Web服務(wù)s2和s3，由于這兩個(gè)國(guó)家的經(jīng)濟(jì)發(fā)展水平存在很大的差異，導(dǎo)致其服務(wù)器端的設(shè)備水平和網(wǎng)絡(luò)傳輸效率差異很大。因此，ua用戶使用這兩個(gè)服務(wù)的QoS感知也差異很大，s2服務(wù)的響應(yīng)時(shí)間為0.010s，s3服務(wù)的響應(yīng)時(shí)間為1s，相差100倍。同樣地，對(duì)于同一個(gè)服務(wù)s1，如果同時(shí)被來自兩個(gè)不同國(guó)家的ub用戶和uc用戶調(diào)用，由于受其國(guó)家發(fā)展水平不同的影響，ub用戶的IT設(shè)施和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)比uc用戶的高端，導(dǎo)致其感知服務(wù)的QoS水平不同。ub用戶接收s1服務(wù)的響應(yīng)時(shí)間為0.020s，uc用戶接收s1服務(wù)的響應(yīng)時(shí)間為0.400s，相差20倍。因此，考慮用戶和服務(wù)所在區(qū)域(國(guó)家或者省市地區(qū))的影響對(duì)于提高QoS預(yù)測(cè)的準(zhǔn)確性具有重要意義。

圖1 Web服務(wù)調(diào)用場(chǎng)景Figure 1 Scenario of Web Service Invocation

3 用戶相似度和服務(wù)相似度的計(jì)算

由于本研究考慮了區(qū)域信息，因此，有必要計(jì)算區(qū)域內(nèi)用戶或服務(wù)之間的相似度，即根據(jù)QoS歷史信息計(jì)算用戶或服務(wù)之間的相似度。相似用戶主要是指兩個(gè)用戶在同一組服務(wù)上具有比較相似的QoS歷史信息，相似服務(wù)主要是指兩個(gè)服務(wù)被同一組用戶使用時(shí)具有比較相似的QoS歷史信息[34]。對(duì)于新用戶和新服務(wù)，由于缺少Q(mào)oS信息，本研究采用區(qū)域內(nèi)平均值的方法計(jì)算其相應(yīng)的QoS信息。該方法選取同一區(qū)域內(nèi)的所有其他用戶和服務(wù)的QoS信息均值作為新用戶和新服務(wù)的QoS信息，從而能夠有效地處理QoS預(yù)測(cè)中面臨的冷啟動(dòng)問題。

不同的QoS屬性，其數(shù)據(jù)類型可能不同，如響應(yīng)時(shí)間和成本屬于數(shù)值型QoS，可靠性和可用性屬于比率型QoS。對(duì)于比率型的QoS信息，其變化范圍是有限的，如變化范圍為[0,100%]。然而，對(duì)于數(shù)值型的QoS信息，其可能存在不同的數(shù)值范圍，比較典型的數(shù)值型屬性是響應(yīng)時(shí)間，比如一個(gè)用戶使用服務(wù)的響應(yīng)時(shí)間變化范圍是[0s, 1s]，而另一個(gè)用戶的響應(yīng)時(shí)間變化范圍是[10s, 20s]。

QoS信息取值范圍的不同可能影響相似度的計(jì)算，因此，本研究采用高斯法[15]對(duì)QoS信息進(jìn)行規(guī)范化處理，將QoS信息映射到[0,1]之間。計(jì)算公式為

(1)

對(duì)QoS信息進(jìn)行規(guī)范化處理之后，本研究采用皮爾遜相關(guān)系數(shù)的相似性度量方法[35]計(jì)算用戶相似度和服務(wù)相似度，其取值范圍為[0,1]，該值越大，說明兩個(gè)用戶或服務(wù)之間的相似度越大。計(jì)算公式為

(2)

4 基于用戶和服務(wù)區(qū)域信息的QoS預(yù)測(cè)過程

在已有研究中，只采用已有的QoS信息進(jìn)行預(yù)測(cè)，忽略了一些客觀因素影響，如用戶和服務(wù)的位置信息。為了提高QoS預(yù)測(cè)的準(zhǔn)確性，本研究將全局QoS信息與用戶和服務(wù)區(qū)域信息相結(jié)合，提出一種基于用戶和服務(wù)區(qū)域信息的QoS預(yù)測(cè)方法QPRIUS(QoS prediction based on region information of users and services)。首先，結(jié)合全局QoS信息與局部區(qū)域信息構(gòu)建預(yù)測(cè)模型，然后采用隨機(jī)梯度下降法對(duì)模型優(yōu)化學(xué)習(xí)，最終得到預(yù)測(cè)結(jié)果。考慮用戶和服務(wù)區(qū)域因素有助于提高QoS預(yù)測(cè)的準(zhǔn)確性，采用區(qū)域內(nèi)平均值方法計(jì)算新用戶和新服務(wù)的QoS信息，這樣能夠有效解決冷啟動(dòng)問題。以下將給出QPRIUS方法的詳細(xì)過程。

4.1 QoS預(yù)測(cè)框架

圖2給出QPRIUS方法的框架。用戶相似度和服務(wù)相似度的計(jì)算是QoS預(yù)測(cè)的前期準(zhǔn)備工作，見圖2中虛線框所示，以區(qū)域?yàn)閱挝环謩e計(jì)算同一區(qū)域內(nèi)的用戶相似度和服務(wù)相似度，得到兩個(gè)相似度矩陣SimU和SimS，這兩個(gè)矩陣是構(gòu)造QoS預(yù)測(cè)模型的基礎(chǔ)。

圖2 QPRIUS方法框架Figure 2 Architecture of QPRIUS

在QoS預(yù)測(cè)過程中，M×N的用戶-服務(wù)QoS矩陣R經(jīng)過初始的矩陣因子分解，得到低維的用戶特征矩陣U和服務(wù)特征矩陣S。分解過程為

(3)

矩陣因子分解為

(4)

(5)

(6)

其中，U為d×M的用戶特征矩陣，包含M個(gè)潛在的特征向量；S為d×N的服務(wù)特征矩陣，包含N個(gè)潛在的特征向量；d為維度，特征向量的長(zhǎng)度(即特征個(gè)數(shù))。U中的每一列Ui為ui用戶的特征向量，S中的每一列Sj為sj服務(wù)的特征向量。

4.2 QPRIUS方法的詳細(xì)過程

創(chuàng)建QoS預(yù)測(cè)模型，該模型結(jié)合了QoS歷史信息以及用戶和服務(wù)的區(qū)域信息，然后對(duì)模型進(jìn)行優(yōu)化。

4.2.1 創(chuàng)建QoS預(yù)測(cè)模型

本研究預(yù)測(cè)模型中采用矩陣因子分解方法，該方法基于降維技術(shù)。奇異值分解[37]是比較著名的降維技術(shù)，能夠?qū)⒃季仃囕^好地分解為相應(yīng)的低秩矩陣。

如前所述，用戶-服務(wù)矩陣R被分解為兩個(gè)矩陣U和S，即R≈UTS，U∈d×M，S∈d×N，d?min(M,N)?；诖?，本研究的QoS預(yù)測(cè)模型P建立過程如(7)式，該最小化函數(shù)的目的是使預(yù)測(cè)的QoS信息矩陣與已知的QoS信息矩陣之間的差值盡量小。

minP(R,U,S)

(7)

A(i)*={lu|Sim(i,lu)≥μ,lu∈A(i)}

A(j)*={ls|Sim(j,ls)≥μ,ls∈A(j)}

根據(jù)正則化理論[38]，4個(gè)正則項(xiàng)被加入模型中，U和S的正則項(xiàng)能夠避免過擬合問題[39]，α和β用于調(diào)節(jié)用戶和服務(wù)的區(qū)域因子在QoS預(yù)測(cè)過程中的影響程度。為了提高預(yù)測(cè)的準(zhǔn)確性，排除噪音的影響，對(duì)于同一區(qū)域內(nèi)的用戶和服務(wù)分別計(jì)算，得到其較高質(zhì)量的鄰居集合。設(shè)定一個(gè)μ值，當(dāng)兩個(gè)用戶(或服務(wù))之間的相似度超過μ時(shí)，才會(huì)對(duì)它們的特征向量差值進(jìn)行Frobenius范數(shù)處理，而不是對(duì)所有的用戶進(jìn)行處理，這樣有助于提高計(jì)算效率和準(zhǔn)確率。加入?yún)^(qū)域正則項(xiàng)的目的是使同一區(qū)域內(nèi)相似度較高的用戶(或服務(wù))之間的特征向量(QoS信息)更加接近。也就是說，當(dāng)用戶(或服務(wù))之間的相似度較大時(shí)，在優(yōu)化過程中，為了使目標(biāo)函數(shù)值盡量小，只能使特征向量差值的Frobenius范數(shù)‖Ui-Uf‖和‖Sj-Sk‖盡量小。因此，就會(huì)縮小用戶(或服務(wù))特征向量之間的距離，使其更加接近，這樣有助于提高QoS預(yù)測(cè)的準(zhǔn)確性。

4.2.2 模型的優(yōu)化

對(duì)(7)式進(jìn)行訓(xùn)練優(yōu)化，在矩陣因子分解方法中，最常用的優(yōu)化方法是隨機(jī)梯度下降法，其基本思想是讓目標(biāo)函數(shù)中的變量Ui和Sj沿著函數(shù)負(fù)梯度的方向移動(dòng)。由于矩陣因子分解的目標(biāo)函數(shù)是凸函數(shù)[33]，因此，負(fù)梯度的方向就是朝著函數(shù)值減少的方向移動(dòng)，直到移動(dòng)到函數(shù)的極小值點(diǎn)。以用戶為例，根據(jù)MA et al.[40]的研究，在計(jì)算用戶特征向量的偏導(dǎo)數(shù)過程中，用戶鄰居集合A(i)*內(nèi)的用戶彼此互為鄰居。因此，在對(duì)區(qū)域正則項(xiàng)計(jì)算偏導(dǎo)數(shù)時(shí)相當(dāng)于對(duì)特征向量Ui計(jì)算兩次；同理，服務(wù)特征向量Sj偏導(dǎo)數(shù)的計(jì)算也是如此。計(jì)算得到的偏導(dǎo)數(shù)為

(8)

其中，Ui+1為Ui經(jīng)過一次訓(xùn)練之后得到的矩陣；Sj+1為Sj經(jīng)過一次訓(xùn)練之后得到的矩陣；ηU為矩陣U的學(xué)習(xí)步長(zhǎng)，ηS為矩陣S的學(xué)習(xí)步長(zhǎng)，ηU和ηS也是學(xué)習(xí)速率，均為正值；P為(7)式的預(yù)測(cè)模型的簡(jiǎn)寫。

在訓(xùn)練過程中，由于(8)式中的負(fù)值部分可能使特征矩陣中出現(xiàn)負(fù)值，而在矩陣的更新過程中負(fù)值無法正確表示用戶和服務(wù)的特征信息，保持矩陣中每一個(gè)特征項(xiàng)的非負(fù)性具有非常重要的意義。因此，本研究將使用非負(fù)矩陣因子分解的方法預(yù)測(cè)QoS信息。以特征矩陣Ui的訓(xùn)練過程為例，具體步驟為

(9)

為了保持矩陣的非負(fù)性，將ηU調(diào)整為[41]

(10)

這個(gè)轉(zhuǎn)化過程能夠抵消(9)式中的負(fù)值部分，因此，將(10)式代入(9)式，訓(xùn)練過程轉(zhuǎn)換為

(11)

同樣地，ηS被調(diào)整為(12)式，特征矩陣Sj的訓(xùn)練過程見(13)式。

(12)

(13)

在QoS預(yù)測(cè)模型的優(yōu)化過程中，變量的偏導(dǎo)數(shù)是梯度最陡的方向，也就是說，函數(shù)模型在朝著目標(biāo)值下降最快的方向運(yùn)行。隨機(jī)梯度下降算法的迭代終止條件比較多，常見的主要有3種情況：

(1)設(shè)置固定的迭代次數(shù)；

(2)給目標(biāo)函數(shù)設(shè)定一個(gè)固定的閾值，當(dāng)目標(biāo)函數(shù)的值小于閾值時(shí)，停止迭代過程；

(3)給目標(biāo)函數(shù)值的變化范圍設(shè)定一個(gè)閾值，當(dāng)前后兩次目標(biāo)函數(shù)值變化的絕對(duì)值小于閾值時(shí)，停止迭代過程。

本研究采用第(1)種設(shè)置方法，根據(jù)實(shí)驗(yàn)效果設(shè)置一定的迭代次數(shù)。

經(jīng)過(11)式和(13)式的迭代優(yōu)化過程，最終可以得到新的用戶特征矩陣U′和服務(wù)特征矩陣S′，從而計(jì)算得到QoS信息的預(yù)測(cè)矩陣R′≈U′TS′。

4.3 復(fù)雜性分析

以用戶特征矩陣U的更新過程為例，根據(jù)(11)式，矩陣U的每個(gè)列向量Ui乘上分式

通常情況下，用戶和服務(wù)的鄰居個(gè)數(shù)遠(yuǎn)小于用戶和服務(wù)本身的個(gè)數(shù)，并且存在M?MD，N?MD，因此，迭代一次時(shí)整個(gè)過程的復(fù)雜度可以用O(MD·d)表示。d值越大，在模型訓(xùn)練過程中需要更多的時(shí)間成本，不利于實(shí)際應(yīng)用。因此，本研究將d統(tǒng)一設(shè)為10?？梢园l(fā)現(xiàn)，在d值一定的條件下，QPRIUS方法的計(jì)算復(fù)雜度與矩陣密度線性相關(guān)。因此，本研究使用的方法具有較高的計(jì)算效率，并且能夠處理較大規(guī)模的數(shù)據(jù)集。

5 實(shí)驗(yàn)和分析

本研究通過實(shí)驗(yàn)驗(yàn)證QoS預(yù)測(cè)方法QPRIUS，實(shí)驗(yàn)使用Matlab R2010b編寫程序，運(yùn)行環(huán)境為Windows XP，雙核CPU2.4GHz，2G內(nèi)存。

實(shí)驗(yàn)主要分為兩部分內(nèi)容：第1部分對(duì)方法中所含的參數(shù)進(jìn)行實(shí)驗(yàn)分析，第2部分將本研究的QoS預(yù)測(cè)方法與其他研究進(jìn)行對(duì)比和分析。參數(shù)實(shí)驗(yàn)分析主要包括QoS預(yù)測(cè)模型中的特征矩陣權(quán)重系數(shù)λ1和λ2、用戶區(qū)域權(quán)重系數(shù)α、服務(wù)區(qū)域權(quán)重系數(shù)β、矩陣密度MD和相似度閾值μ。通常情況下取λ1=λ2，因此，在以下實(shí)驗(yàn)中統(tǒng)稱為λ。通過參數(shù)實(shí)驗(yàn)，可以分析預(yù)測(cè)模型中不同的參數(shù)取值對(duì)QoS預(yù)測(cè)效果的影響，同時(shí)發(fā)現(xiàn)較優(yōu)的參數(shù)值。在QoS預(yù)測(cè)方法的對(duì)比實(shí)驗(yàn)中，將QPRIUS方法與其他方法進(jìn)行對(duì)比分析。

5.1 實(shí)驗(yàn)設(shè)計(jì)

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

本研究使用的實(shí)驗(yàn)數(shù)據(jù)為WSDream-QoSDataset2[42]，見表1。由表1可知，該數(shù)據(jù)包含1 974 675條339個(gè)用戶對(duì)5 825個(gè)Web服務(wù)調(diào)用之后反饋的QoS信息，包括響應(yīng)時(shí)間和吞吐量?jī)蓚€(gè)屬性。此外，每個(gè)用戶和服務(wù)都有一個(gè)區(qū)域信息，即所在國(guó)家名稱。

表1 WSDream-QoSDataset2數(shù)據(jù)集Table 1 Data Set of WSDream-QoSDataset2

在實(shí)驗(yàn)中，本研究在QoS矩陣中隨機(jī)去掉一部分?jǐn)?shù)據(jù)，從而生成不同密度的矩陣進(jìn)行實(shí)驗(yàn)。例如，當(dāng)MD的取值為20%時(shí)，也就是說保留原始QoS矩陣中20%的值作為訓(xùn)練數(shù)據(jù)，其余80%的數(shù)據(jù)作為測(cè)試數(shù)據(jù)，即作為判斷預(yù)測(cè)準(zhǔn)確性的期望值。本實(shí)驗(yàn)僅對(duì)響應(yīng)時(shí)間和吞吐量?jī)蓚€(gè)屬性進(jìn)行研究，對(duì)于其他的QoS屬性本方法同樣適用。

5.1.2 評(píng)價(jià)指標(biāo)

本研究采用兩個(gè)常用的評(píng)價(jià)指標(biāo)測(cè)量QoS預(yù)測(cè)方法的準(zhǔn)確性，分別是平均絕對(duì)誤差(MAE)和均方根誤差(RMSE)[43]，計(jì)算公式為

(14)

5.2 參數(shù)分析實(shí)驗(yàn)

本研究對(duì)QoS預(yù)測(cè)方法中涉及的5個(gè)參數(shù)進(jìn)行實(shí)驗(yàn)分析，包括λ、α、β、MD和μ。以下實(shí)驗(yàn)以響應(yīng)時(shí)間數(shù)據(jù)為例，分別對(duì)這些參數(shù)的影響進(jìn)行分析，并選取恰當(dāng)?shù)闹?。?duì)于其他的QoS屬性，可采用同樣的方法進(jìn)行分析。

5.2.1 參數(shù)λ的影響分析

本研究在預(yù)測(cè)模型中引入用戶和服務(wù)特征矩陣正則項(xiàng)，一方面可以防止模型的過度擬合，另一方面從全局QoS角度對(duì)模型優(yōu)化進(jìn)行調(diào)節(jié)。本實(shí)驗(yàn)討論模型中權(quán)重系數(shù)λ對(duì)實(shí)驗(yàn)結(jié)果的影響，先不考慮用戶和服務(wù)的局部區(qū)域信息，即α和β取值為0，MD=50%，d=10，μ=0.400。本實(shí)驗(yàn)將λ的取值分別設(shè)定為1E-5、1E-4、1E-3、1E-2、1E-1和1E0，進(jìn)行300次迭代優(yōu)化過程，計(jì)算MAE值和RMSE值，取10次結(jié)果的平均值，實(shí)驗(yàn)結(jié)果見圖3。

由圖3可知，隨著λ增大，MAE和RMSE的變化趨勢(shì)基本一致。當(dāng)λ=1E-3時(shí)，MAE值為0.361，RMSE值為1.019，均為最低值，此時(shí)的預(yù)測(cè)效果最優(yōu)。實(shí)驗(yàn)結(jié)果表明，λ取值大小對(duì)模型的預(yù)測(cè)效果具有一定影響。如果取值過小，正則項(xiàng)因子的范數(shù)在模型優(yōu)化過程中獲得較大值，使對(duì)已知數(shù)據(jù)的逼近誤差越來越小，容易形成過度擬合，增大了對(duì)預(yù)測(cè)數(shù)據(jù)的逼近誤差。也就是說，當(dāng)λ取值過小時(shí)，正則項(xiàng)因子的加入失去了調(diào)節(jié)作用；如果λ取值過大，導(dǎo)致正則項(xiàng)因子的范數(shù)越來越低，增大了對(duì)已知數(shù)據(jù)的逼近誤差，最終影響未知數(shù)據(jù)的預(yù)測(cè)結(jié)果。對(duì)本研究來說，當(dāng)λ取1E-3時(shí)，實(shí)驗(yàn)效果最優(yōu)，在后面的實(shí)驗(yàn)中將使用此值。

圖3 不同λ取值下的實(shí)驗(yàn)結(jié)果Figure 3 Experimental Results under Various λ

5.2.2 參數(shù)α的影響分析

參數(shù)α決定用戶區(qū)域因素在QoS預(yù)測(cè)中所占的權(quán)重，如果α特別小，在QoS預(yù)測(cè)中使用用戶-服務(wù)QoS矩陣；如果α特別大，用戶的區(qū)域信息控制整個(gè)預(yù)測(cè)過程，影響預(yù)測(cè)準(zhǔn)確性。本實(shí)驗(yàn)討論α的取值對(duì)預(yù)測(cè)結(jié)果的影響，將α的取值分別設(shè)為1E-5、1E-4、1E-3、1E-2、1E-1和1E0，λ=1E-3，β=0，MD=50%，d=10，μ=0.400，計(jì)算10次結(jié)果的MAE和RMSE平均值，計(jì)算結(jié)果見圖4。

由圖4可知，當(dāng)α=1E-5時(shí)，MAE值為0.358，RMSE值為1.012，比圖3中λ=1E-3時(shí)的最優(yōu)MAE值和RMSE值小。說明加入用戶區(qū)域信息后，模型的預(yù)測(cè)效果有所提高。當(dāng)α=1E-2時(shí)，MAE值為0.350，RMSE值為0.997，均為最小值，此時(shí)的預(yù)測(cè)準(zhǔn)確性最佳。實(shí)驗(yàn)結(jié)果表明，加入用戶局部區(qū)域因素有助于提升QoS預(yù)測(cè)效果。若用戶區(qū)域因素在預(yù)測(cè)模型中的權(quán)重過大，會(huì)過度陷入局部因素，忽略全局影響，降低預(yù)測(cè)準(zhǔn)確性。α取1E-2時(shí)預(yù)測(cè)效果最優(yōu)，后面的實(shí)驗(yàn)將采用此值。

5.2.3 參數(shù)β的影響分析

與參數(shù)α類似，β決定服務(wù)區(qū)域因素在QoS預(yù)測(cè)中所占的權(quán)重。本實(shí)驗(yàn)討論β取值變化對(duì)QoS預(yù)測(cè)效果的影響，將β值分別設(shè)為1E-5、1E-4、1E-3、1E-2、1E-1和1E0，λ=1E-3，α=0，MD=50%，d=10，μ=0.400，實(shí)驗(yàn)運(yùn)行10次取平均值，計(jì)算結(jié)果見圖5。

圖5 不同β取值下的實(shí)驗(yàn)結(jié)果Figure 5 Experimental Results under Various β

由圖5可知，β=1E-5時(shí)，MAE值為0.351，RMSE值為0.995，優(yōu)于圖3中MAE和RMSE的最小值，說明考慮服務(wù)的區(qū)域因素有助于提高QoS預(yù)測(cè)效果。當(dāng)β=1E-1時(shí)，MAE值為0.329，RMSE值為0.944，均為最小值。實(shí)驗(yàn)結(jié)果表明，加入服務(wù)區(qū)域信息有助于提升QoS預(yù)測(cè)效果，但是當(dāng)β取值過大時(shí)，預(yù)測(cè)模型同樣會(huì)陷入局部影響。當(dāng)β=1E-1時(shí)預(yù)測(cè)效果最佳，后面的實(shí)驗(yàn)將采用此值。

與5.2.2的實(shí)驗(yàn)結(jié)果對(duì)比可以發(fā)現(xiàn)，在同樣的權(quán)值下，相對(duì)于用戶的局部區(qū)域信息，服務(wù)的局部區(qū)域信息對(duì)QoS預(yù)測(cè)的影響更大。通常情況下，當(dāng)用戶向Web服務(wù)注冊(cè)中心提交服務(wù)請(qǐng)求后，注冊(cè)中心根據(jù)用戶請(qǐng)求查找滿足其需求的服務(wù)并提供相應(yīng)的綁定信息。用戶直接與服務(wù)提供者進(jìn)行交互并調(diào)用服務(wù)，服務(wù)在提供者的服務(wù)器端運(yùn)行并提供用戶需要的信息，用戶通過電腦接收服務(wù)結(jié)果。服務(wù)器在整個(gè)服務(wù)運(yùn)行中起主導(dǎo)作用，而用戶端只負(fù)責(zé)接收運(yùn)行結(jié)果。因此，服務(wù)所在的區(qū)域發(fā)展水平對(duì)其QoS信息具有較大的影響，實(shí)驗(yàn)結(jié)果充分說明了這一點(diǎn)。

5.2.4 矩陣密度的影響分析

在實(shí)際中，不可能每個(gè)用戶都調(diào)用所有服務(wù)并反饋QoS信息，因此，QoS矩陣往往存在一定的稀疏度，即矩陣密度MD。QoS信息越多，矩陣密度越大，反之則越小。本實(shí)驗(yàn)將MD分別設(shè)為10%、20%、30%、40%、50%、60%、70%、80%和90%，λ=1E-3，α=1E-2，β=1E-1，d=10，μ=0.400，實(shí)驗(yàn)運(yùn)行10次取平均值，計(jì)算結(jié)果見圖6。

圖6 不同矩陣密度下的實(shí)驗(yàn)結(jié)果Figure 6 Experimental Results under Various Matrix Density

由圖6可知，隨著矩陣密度的增加，預(yù)測(cè)效果越來越好。當(dāng)MD取值從10%增加到50%時(shí)，MAE和RMSE下降趨勢(shì)較為明顯，隨著MD增大，MAE和RMSE下降趨勢(shì)相對(duì)較緩。實(shí)驗(yàn)結(jié)果說明已知的QoS信息越多，其對(duì)未知QoS信息預(yù)測(cè)的準(zhǔn)確性幫助越大。矩陣密度在由10%逐漸增加到50%時(shí)，其對(duì)預(yù)測(cè)準(zhǔn)確性的影響比較明顯，進(jìn)一步說明鼓勵(lì)用戶盡量多地提供QoS信息反饋值非常重要。

5.2.5 相似度閾值的影響分析

為了獲取當(dāng)前用戶或服務(wù)更高質(zhì)量的鄰居集合，本研究設(shè)定一個(gè)相似度閾值對(duì)相似用戶或服務(wù)進(jìn)行過濾。本實(shí)驗(yàn)討論在不同的矩陣密度下閾值μ的不同取值對(duì)預(yù)測(cè)結(jié)果的影響，μ的取值分別設(shè)定為0、0.200、0.400、0.600和0.800，MD取值為10%、30%、50%、70%和90%，λ=1E-3，α=1E-2，β=1E-1，d=10，實(shí)驗(yàn)運(yùn)行10次取平均值，計(jì)算結(jié)果見圖7。

圖7 不同相似度閾值時(shí)的實(shí)驗(yàn)結(jié)果Figure 7 Experimental Results under Various Similarity Threshold

由圖7可知，當(dāng)μ固定時(shí)，隨著MD增加，MAE和RMSE逐漸下降，這一結(jié)果與5.2.4實(shí)驗(yàn)結(jié)果相吻合。此外，在不同的MD下，對(duì)應(yīng)不同的最優(yōu)閾值μ。例如，當(dāng)MD=10%時(shí)，μ=0.600的預(yù)測(cè)效果比較好；當(dāng)MD取值為30%和50%時(shí)，μ=0.400的預(yù)測(cè)效果比較好；當(dāng)MD取值為70%和90%時(shí)，預(yù)測(cè)效果在μ=0.200時(shí)比較好。

可以發(fā)現(xiàn)，隨著MD增大，μ越小對(duì)預(yù)測(cè)效果的準(zhǔn)確性越有利；MD越小，μ則越大越好。說明當(dāng)QoS信息比較少時(shí)，用戶或服務(wù)之間的相似度結(jié)果存在較大噪音，只有取相似度比較大的鄰居才有利于QoS信息的預(yù)測(cè)。較低的相似度并不能正確地描述和區(qū)分用戶或服務(wù)之間的關(guān)系，進(jìn)而影響預(yù)測(cè)結(jié)果。當(dāng)MD較大時(shí)，具有豐富的QoS信息，因此，用戶或服務(wù)之間的相似度計(jì)算能夠比較恰當(dāng)?shù)孛枋鲇脩艋蚍?wù)之間的關(guān)系，即使是較低的相似度也能比較準(zhǔn)確地表示其關(guān)系。綜上所述，當(dāng)MD較小時(shí)，設(shè)置較大的閾值有利于提高預(yù)測(cè)的準(zhǔn)確性；當(dāng)MD較大時(shí)，設(shè)置較小的閾值對(duì)QoS預(yù)測(cè)比較有利。當(dāng)MD=50%時(shí)，最優(yōu)閾值為0.400，該值被應(yīng)用于本研究的其他實(shí)驗(yàn)中。

5.3 與其他方法的對(duì)比分析

本研究將QoS預(yù)測(cè)方法QPRIUS與NIMF[20]方法和Colbar[25]方法進(jìn)行對(duì)比。NIMF方法主要采用矩陣因子分解的方法，結(jié)合當(dāng)前用戶的鄰居用戶QoS信息對(duì)未知的QoS信息進(jìn)行預(yù)測(cè)。Colbar方法在矩陣因子分解模型中引入用戶的位置信息作為正則項(xiàng)，根據(jù)位置信息對(duì)用戶進(jìn)行篩選，然后計(jì)算滿足一定距離內(nèi)的用戶之間的相似度，得到當(dāng)前用戶的鄰居集，再對(duì)建立的模型進(jìn)行學(xué)習(xí)，得到QoS預(yù)測(cè)矩陣。

圖8和圖9給出本研究方法與NIMF和Colbar兩種方法在不同矩陣密度下的對(duì)比。NIMF方法沒有考慮區(qū)域信息的影響，Colbar方法只考慮了用戶的位置信息而沒有考慮服務(wù)的位置信息的影響。因此，將本研究只考慮用戶區(qū)域信息的方法QPRIU(α≠0，β=0)與Colbar方法進(jìn)行對(duì)比，然后再將同時(shí)考慮用戶和服務(wù)區(qū)域因素時(shí)的方法QPRIUS與Colbar方法和NIMF方法進(jìn)行對(duì)比。

根據(jù)申利民等[20]和ZHENG et al.[25]的原有計(jì)算結(jié)果，Colbar方法中計(jì)算了MD取值為10%、20%、30%和40%的預(yù)測(cè)結(jié)果，NIMF方法中計(jì)算了MD取值為5%、10%、15%和20%的預(yù)測(cè)結(jié)果。為了方便對(duì)比，本研究將矩陣密度設(shè)定為5%、10%、15%、20%、30%和40%，計(jì)算響應(yīng)時(shí)間和吞吐量?jī)蓚€(gè)QoS屬性的MAE和RMSE值，取10次結(jié)果的平均值，并與NIMF方法和Colbar方法分別進(jìn)行對(duì)比和分析。

首先，分析當(dāng)本研究?jī)H考慮用戶區(qū)域信息時(shí)的QPRIU方法與Colbar方法的對(duì)比。由圖8和圖9可知，在同樣的矩陣密度條件下，對(duì)于響應(yīng)時(shí)間和吞吐量?jī)蓚€(gè)屬性來說，本研究的QPRIU方法計(jì)算得到的MAE和RMSE均比Colbar方法小。說明在同樣考慮用戶區(qū)域信息的情況下，本研究的計(jì)算方法比Colbar方法的預(yù)測(cè)準(zhǔn)確度更高一些。主要是因?yàn)楸狙芯磕Ｐ驮趦?yōu)化過程中保持了矩陣的非負(fù)性，并且是根據(jù)區(qū)域劃分對(duì)用戶進(jìn)行分類并計(jì)算相似度，避免了將兩個(gè)相鄰區(qū)域的用戶因?yàn)榈乩砦恢煤芙怯布O(shè)施差別很大而被認(rèn)為是互為鄰居的情況。由于Colbar方法無法正確處理這種情況，從而導(dǎo)致其計(jì)算結(jié)果存在一定誤差。

其次，當(dāng)本研究同時(shí)考慮用戶和服務(wù)區(qū)域信息時(shí)與NIMF方法和Colbar方法進(jìn)行對(duì)比。由圖8和圖9可知，在同樣的矩陣密度條件下，對(duì)于響應(yīng)時(shí)間和吞吐量?jī)蓚€(gè)屬性來說，QPRIUS方法預(yù)測(cè)結(jié)果明顯優(yōu)于NIMF方法和Colbar方法。該實(shí)驗(yàn)結(jié)果充分說明本研究方法的優(yōu)越性和QoS預(yù)測(cè)的準(zhǔn)確性，以及充分考慮用戶區(qū)域信息和服務(wù)區(qū)域信息的必要性。

圖9 4種方法對(duì)比——吞吐量Figure 9 Comparisons of Four Methods for Throughput

圖8 4種方法對(duì)比——響應(yīng)時(shí)間Figure 8 Comparisons of Four Methods for Response Time

6 結(jié)論

本研究提出一種基于用戶和服務(wù)區(qū)域信息的Web服務(wù)質(zhì)量預(yù)測(cè)方法QPRIUS。在所創(chuàng)建的QoS預(yù)測(cè)模型中，不僅考慮全局的QoS信息，而且加入用戶和服務(wù)的局部區(qū)域信息，通過模型的迭代優(yōu)化過程，最終得到準(zhǔn)確性較高的QoS預(yù)測(cè)矩陣。研究結(jié)果表明，①在QoS預(yù)測(cè)模型中加入用戶和服務(wù)的區(qū)域影響因素有助于提高QoS預(yù)測(cè)的準(zhǔn)確性。相較而言，服務(wù)所在的區(qū)域情況對(duì)QoS信息的預(yù)測(cè)效果影響較大。主要是由于當(dāng)用戶提交其服務(wù)請(qǐng)求之后，服務(wù)在提供者的服務(wù)器端運(yùn)行并提供給用戶需要的信息。因此，服務(wù)器端在服務(wù)運(yùn)行過程中起主導(dǎo)作用，其所在區(qū)域的發(fā)展水平對(duì)服務(wù)運(yùn)行的QoS信息影響很大。②已有QoS信息的密度對(duì)QoS預(yù)測(cè)效果具有一定影響，密度越大，預(yù)測(cè)準(zhǔn)確性越高，說明鼓勵(lì)用戶盡量多地提供QoS信息反饋值非常重要。③為了提高模型的優(yōu)化效率，獲取高質(zhì)量的鄰居集合，在計(jì)算區(qū)域內(nèi)用戶之間和服務(wù)之間相似度時(shí)引入相似度閾值，當(dāng)QoS信息的密度較小時(shí)，較大的μ值有利于提高預(yù)測(cè)的準(zhǔn)確性；當(dāng)QoS信息的密度較大時(shí)，較低的μ值對(duì)QoS信息的預(yù)測(cè)比較有利。

本研究方法具有較高的QoS預(yù)測(cè)準(zhǔn)確性，與其他方法對(duì)比，準(zhǔn)確性提高了25%。同時(shí)，本研究有效地解決了新用戶和新服務(wù)的冷啟動(dòng)問題。對(duì)于較稀疏的矩陣，也能夠得到較好的預(yù)測(cè)效果。研究結(jié)果對(duì)大量基于QoS的研究工作具有重要的支持作用，有利于為其提供較為準(zhǔn)確的QoS信息，為面向服務(wù)計(jì)算的發(fā)展提供一些有益的啟示。

本研究還存在一些不足可以在后續(xù)研究予以拓展。在今后的研究中可以考慮用戶對(duì)服務(wù)的滿意度和信任度等主觀因素對(duì)QoS預(yù)測(cè)的影響，這將有利于進(jìn)一步提高QoS預(yù)測(cè)的準(zhǔn)確性。此外，本研究針對(duì)靜態(tài)的QoS信息，有些QoS屬性是動(dòng)態(tài)變化的，需要對(duì)其進(jìn)行實(shí)時(shí)預(yù)測(cè)，這有待于今后的進(jìn)一步研究。