馬建威，陳洪輝， STEPHAN Reiff-Marganiec(.國防科學(xué)技術(shù)大學(xué) 信息系統(tǒng)工程重點實驗室，湖南 長沙，4007；2.第三軍醫(yī)大學(xué)衛(wèi)勤教研室，重慶，40008；.萊斯特大學(xué) 計算機(jī)科學(xué)與技術(shù)系，英國 萊斯特)

?

基于混合推薦和隱馬爾科夫模型的服務(wù)推薦方法

馬建威1,2，陳洪輝1， STEPHAN Reiff-Marganiec3
(1.國防科學(xué)技術(shù)大學(xué) 信息系統(tǒng)工程重點實驗室，湖南 長沙，410073；2.第三軍醫(yī)大學(xué)衛(wèi)勤教研室，重慶，400038；3.萊斯特大學(xué) 計算機(jī)科學(xué)與技術(shù)系，英國 萊斯特)

摘要：針對現(xiàn)階段越來越多的服務(wù)開始部署于云環(huán)境，服務(wù)數(shù)量呈幾何級增長，必須獲取并推薦最優(yōu)服務(wù)，而傳統(tǒng)的基于內(nèi)容的過濾或協(xié)同過濾方法缺乏對新用戶和冗余服務(wù)的有效處理方法，提出一種在云環(huán)境下對最優(yōu)服務(wù)進(jìn)行有效推薦的方法。首先，分析2種協(xié)同過濾方法的優(yōu)缺點，并提出改進(jìn)的混合推薦算法；其次，針對常常被忽略的新用戶學(xué)習(xí)策略，提出新用戶偏好的確定方法；針對服務(wù)的動態(tài)變化情況，基于隱馬爾科夫模型(hidden Markov model)提出一種冗余服務(wù)消解策略。最后，基于真實數(shù)據(jù)集和通過公開API獲取的公共服務(wù)集進(jìn)行實驗。研究結(jié)果表明：所提出的算法與其他方法相比具有更高的準(zhǔn)確度和更好的服務(wù)質(zhì)量，能更有效地提高系統(tǒng)性能。

關(guān)鍵詞：協(xié)同過濾；服務(wù)選擇；新用戶學(xué)習(xí)；隱馬爾科夫模型；冗余檢測

近年來，大量的分布式系統(tǒng)部署環(huán)境不斷向云環(huán)境遷移，越來越多的服務(wù)開始以云服務(wù)的形式展現(xiàn)，服務(wù)的用戶也呈現(xiàn)出幾何量級式快速增長，并且這種趨勢仍在加劇。然而，隨著大量云服務(wù)的出現(xiàn)，諸如服務(wù)提供者的虛假惡意行為、服務(wù)使用高峰時所出現(xiàn)的瓶頸以及云環(huán)境的動態(tài)性等都會造成信息質(zhì)量發(fā)生動態(tài)變化，甚至對用戶變得不可知，當(dāng)前擺在面向服務(wù)應(yīng)用面前的最大挑戰(zhàn)已經(jīng)轉(zhuǎn)變?yōu)槿绾巫畲蠡乩梅?wù)資源，并且充分保證用戶的滿意度。對服務(wù)質(zhì)量進(jìn)行預(yù)測并推薦適當(dāng)?shù)姆?wù)成為解決問題的關(guān)鍵。推薦系統(tǒng)在解決以上問題方面正發(fā)揮著越來越重要的作用[1]。協(xié)同過濾方法(collaborative filtering)是推薦系統(tǒng)的一種信息推薦方法，在學(xué)習(xí)用戶偏好以及預(yù)測用戶興趣等方面得到廣泛應(yīng)用，并且取得了非常好的應(yīng)用效果。然而，傳統(tǒng)的協(xié)同過濾方法通常通過記錄用戶交易歷史的方法計算用戶之間的相似性，從而進(jìn)行過濾推薦，卻無法有效地對新用戶進(jìn)行推薦，這就出現(xiàn)所謂的“冷啟動”(cold start)問題。冷啟動問題在云環(huán)境條件下更加容易發(fā)生，原因在于每天都有數(shù)以百萬級的新用戶在開始使用互聯(lián)網(wǎng)尋找合適的服務(wù)資源。此外，由于拷貝與轉(zhuǎn)載操作簡單，因此，互聯(lián)網(wǎng)上經(jīng)常會出現(xiàn)大量的冗余服務(wù)資源，而傳統(tǒng)的協(xié)同過濾方法無法有效區(qū)分冗余資源，這也使得用戶常常受限于大量冗余的資源列表，而無法從中找出合適的資源，進(jìn)而極大地降低了用戶的使用滿意度。為此，本文作者提出一種基于混合推薦算法和隱馬爾科夫模型的信息推薦方法。首先提出一種混合協(xié)同過濾方法，利用隨機(jī)行走(random walk)策略進(jìn)行云環(huán)境下的信息推薦；然后，基于受歡迎度和信息熵的方法提出新用戶興趣判定的方法；最后，基于隱馬爾科夫模型(hidden Markov model)提出服務(wù)冗余的判定方法，并進(jìn)行實驗驗證。

1　問題描述

由于網(wǎng)絡(luò)服務(wù)數(shù)據(jù)急劇上升，海量的資源使得用戶無法去嘗試使用每一個服務(wù)，因此，對服務(wù)質(zhì)量進(jìn)行預(yù)測并推薦服務(wù)資源成為了一個急需解決的關(guān)鍵問題。近年來，人們對服務(wù)選擇和服務(wù)推薦的研究較多，如自適應(yīng)資源管理[2]、 歷史信息分析[3]以及各種統(tǒng)計方法[4]已在服務(wù)選擇領(lǐng)域得到廣泛應(yīng)用并取得了較好的研究成果。用戶一般服務(wù)矩陣見表1。

這里所提出的服務(wù)質(zhì)量預(yù)測和推薦方法主要是基于對服務(wù)使用者與服務(wù)提供者和服務(wù)推薦者之間進(jìn)行相似度計算的思想提出的。原因在于：在QoS信息相對穩(wěn)定的前提下，服務(wù)的歷史數(shù)據(jù)統(tǒng)計能夠?qū)Ψ?wù)的選擇和推薦產(chǎn)生巨大而有意義的影響。在當(dāng)前研究中，有很多關(guān)于用戶相似度計算的技術(shù)如基于內(nèi)容的過濾[5]和協(xié)同過濾[6?8]。但對云環(huán)境下的超大規(guī)模用戶數(shù)量而言，基于內(nèi)容的過濾方法將面臨巨大的計算復(fù)雜度問題，無法有效地建立用戶配置文件，因此，基于協(xié)同過濾的思想是該種情況下服務(wù)推薦的有效手段。協(xié)同過濾主要有2類：基于用戶的協(xié)同過濾(user-basedCollaborative filtering)和基于項目的協(xié)同過濾(item-basedCollaborative filtering)。

表1　用戶?服務(wù)矩陣Table1　User?service matrix

1)基于用戶的協(xié)同過濾(user-basedCollaborative filtering)的基本思想是計算用戶與用戶之間的相似度Sim(a,u)，典型的方法包括最近 K 鄰居算法(K-nearest neighbor algorithm)以及皮爾森相關(guān)系數(shù)算法(PearsonCorrelationCoefficient algorithm)[9]。

2)基于項目的協(xié)同過濾(item-basedCollaborative filtering)與基于用戶的方法不同，其主要集中于服務(wù)集，通過計算服務(wù)之間的相似度來完成預(yù)測和推薦。由于服務(wù)之間的關(guān)系相對來說較固定，因此，該方法可以進(jìn)行預(yù)計算(pre-computing)，從而可以有效地緩解大規(guī)模數(shù)據(jù)條件下的計算復(fù)雜度問題[11]，但仍缺乏滿足新用戶需求的有效手段。任意2個服務(wù)i與服務(wù)j之間的相似度(Sim(i,j))可以通過下式進(jìn)行計算：

2 基于受歡迎度和互信息熵理論的信息推薦方法

2.1混合協(xié)同過濾方法(hybridCollaborative filtering method)

其中：ω為可信(confidence)權(quán)重，ω∈ [0,1]，通常在數(shù)據(jù)規(guī)模較小時設(shè)置為較大值，當(dāng)數(shù)據(jù)規(guī)模很大時設(shè)置為較小值，主要用于調(diào)節(jié)這 2種方法在混合推薦中所占的權(quán)重，從而充分發(fā)揮這 2種推薦方法各自的優(yōu)勢。

Algorithm1: Greedy search for Top-N services

Input: Service set R

Output: Top-N similarity services set X

1.for j→1to m

2.for i→1to m.

3.Calculate Sim(i,j)

4.x←Sim(i,j)

5.if x≠among the top-n largest values

6.x←0

7.else

8.add x to X

9.end if

10.end for

11.end for

12.Return X

在通常情況下，使用Top-N推薦算法確定與目標(biāo)用戶最相似的N個用戶，并將這N個用戶的相關(guān)服務(wù)推薦給目標(biāo)用戶。算法1給出了Top-N算法的貪婪搜索思想，當(dāng)數(shù)據(jù)規(guī)模較小時，該種算法具有較好性能。

但在云環(huán)境下當(dāng)服務(wù)規(guī)模及數(shù)量巨大時，上述方法的計算復(fù)雜度較大。因此，在這種情況下首先使用概率的潛在語義索引PLSI(probabilistic latent semantic indexing)對用戶進(jìn)行社團(tuán)劃分，而后使用最小優(yōu)先獨立排列哈希MinHash(minwise independent permutation hashing)[10]建立用戶索引，從而保證可擴(kuò)展性的需要，見圖1。然后，使用隨機(jī)行走策略(算法2)在社團(tuán)中隨機(jī)行走，從而避免遍歷所有的服務(wù)集，大大降低計算復(fù)雜度，見圖2。

圖1　聚類分析Fig.1　ClusterClassification

圖2類間的隨機(jī)行走策略Fig.2Random walk strategy inClusters

2.2新用戶推薦策略

對于新用戶，推薦系統(tǒng)中并不具備任何關(guān)于目標(biāo)用戶的信息，因此，傳統(tǒng)的協(xié)同過濾算法無法有效地為新用戶進(jìn)行服務(wù)推薦，即出現(xiàn)“冷啟動”(cold start)問題。為了有效地解決此類問題，推薦系統(tǒng)必須設(shè)法獲得用戶的一些信息，最有效的辦法就是直接向用戶提問題，并提供服務(wù)給用戶進(jìn)行評價[12]。但在現(xiàn)實生活中應(yīng)用這種方法存在著較大局限性：若向用戶提出太多的問題，則會極大地降低系統(tǒng)的可用性，導(dǎo)致用戶難以忍受復(fù)雜的使用流程；而若缺乏足夠的問題，則又無法有效地獲得用戶信息。

Algorithm 2: Service set selection algorithm

Input: Available services in theCloud,services number limit N

Output: Service set R

1.R={ }

2.Pick a random service with required functionality on theCloud,add it to R

3.While(n≤N)

4.Pick a random service on theCloud similar to selected service

5.n++

6.add it to R

7.Return R

基于歡迎度進(jìn)行推薦的方法是一種對新用戶推薦較有效的方法，但該方法存在的主要問題是：若僅僅基于該策略進(jìn)行信息推薦，則將使得推薦系統(tǒng)無法實現(xiàn)個性化推薦，因為最受歡迎的信息往往也會受到大家的歡迎，而這根本無法體現(xiàn)出個性之間的差異；另外，基于信息熵的推薦方法能夠從每次評價值中獲取大量的信息，從而能夠?qū)π掠脩敉扑]起到積極作用[13]，但在海量數(shù)據(jù)規(guī)模下，被評價的信息數(shù)量所占的比例很低，常常出現(xiàn)數(shù)據(jù)稀疏性問題(sparsity problem)，單獨使用基于信息熵的方法將導(dǎo)致沒有信息熵可以利用，從而無法進(jìn)行推薦?？筛鶕?jù)以下步驟解決這些問題：

1)將服務(wù)集 R 中的所有備選服務(wù)按照受歡迎度的降序排列。

2)基于文獻(xiàn)[14]提出的關(guān)系劃分方法將用戶按照不同關(guān)系劃分成若干社區(qū)。

3)當(dāng)有新的待推薦用戶時，判斷該用戶是否與現(xiàn)有用戶存在關(guān)系。若存在關(guān)系，則進(jìn)行用戶相似度計算；若不存在關(guān)系，則從服務(wù)集R中隨機(jī)抽選不同受歡迎度的服務(wù)提供給用戶進(jìn)行評價。

采用前面提出的混合推薦方法進(jìn)行新用戶推薦。

2.3基于隱馬爾科夫模型的冗余信息消解策略

前面討論了靜態(tài)條件下的信息推薦。然而，在實際生活中，服務(wù)的QoS數(shù)據(jù)隨時可能因環(huán)境的變化而發(fā)生改變；此外，服務(wù)的提供商也很可能對其他服務(wù)提供商所提供的服務(wù)進(jìn)行簡單復(fù)制、 粘貼就發(fā)布出來，這導(dǎo)致大量的冗余服務(wù)出現(xiàn)，而這些冗余服務(wù)的質(zhì)量無法得到保障，且可能存在大量的惡意行為。用戶被大量的冗余信息所掩蓋，無法區(qū)分到底哪一個才是真正需要的服務(wù)，隱藏在迷霧之后的就是用戶對系統(tǒng)的極大不信任。為了解決這些問題，提出一種在動態(tài)環(huán)境下預(yù)測和獲取服務(wù)真實QoS值的方法。該方法主要從冗余檢測(redundancy detection)和 QoS 控制(QoSControl)進(jìn)行研究。文獻(xiàn)[15]討論了QoS控制問題，為此，這里研究冗余檢測的解決方法。

解決問題的關(guān)鍵就是確定冗余信息源，并且找出能夠符合用戶需求的數(shù)據(jù)信息。為此，收集可能會影響服務(wù)未來狀態(tài)的信息，并周期性地更新服務(wù)信息以獲取最新數(shù)據(jù)。

將數(shù)據(jù)源劃分為兩類：原始數(shù)據(jù)源(original data)和冗余數(shù)據(jù)源(redundant data)。

定義1：原始數(shù)據(jù)源。原始數(shù)據(jù)源指能夠自由改變和自主更新的數(shù)據(jù)源，不受其他服務(wù)的影響。

定義 2：冗余數(shù)據(jù)源。冗余數(shù)據(jù)源指從原始數(shù)據(jù)源復(fù)制信息(全部或部分)的數(shù)據(jù)源，有2種情況：一是冗余數(shù)據(jù)源從原始數(shù)據(jù)源復(fù)制信息后，自主進(jìn)行更新，變成新的原始數(shù)據(jù)源；另一種是從原始數(shù)據(jù)源復(fù)制信息后停止更新[16]，或者只在原始數(shù)據(jù)源更新信息后的部分時段進(jìn)行更新。

由于第1種情況的冗余數(shù)據(jù)源在復(fù)制原始數(shù)據(jù)后變成了1個新的原始數(shù)據(jù)源，對它的數(shù)據(jù)判別主要是基于可信度判別，傳統(tǒng)的推薦系統(tǒng)可以解決此問題；而第2種情況的冗余數(shù)據(jù)源在復(fù)制完成后依然是冗余數(shù)據(jù)，且隨時可能進(jìn)行變化和修改，傳統(tǒng)的推薦系統(tǒng)無法有效確定其冗余屬性，該結(jié)果依然會出現(xiàn)在推薦列表中，為此，這里主要研究第2種情況的冗余數(shù)據(jù)源并解決相關(guān)問題。

在通常情況下，當(dāng)2個服務(wù)之間存在很多共同的錯誤時可以斷定存在冗余數(shù)據(jù)源，而一般的解決方法是記錄服務(wù)的使用和更新信息，通過記錄服務(wù)更新的頻率來判斷冗余數(shù)據(jù)源。這種方法簡單易行，但當(dāng)冗余數(shù)據(jù)源存在惡意攻擊意圖時，它可以隨機(jī)更新，純粹依靠記錄更新頻率無法有效鑒別冗余數(shù)據(jù)源，為 此，引入隱馬爾科夫模型(hidden Markov model)[17]來解決此類問題。隱馬爾科夫模型可以解決 3類基本問題：evaluation problems,decoding problems 和 learning problems。與馬爾科夫模型不同是，隱馬爾科夫模型中的狀態(tài)對于用戶是不可見的，且每種狀態(tài)可以隨機(jī)生成1種觀察值，為此，首先給出隱馬爾科夫模型。

定義 3：隱馬爾科夫模型(HMM)。1個隱馬爾科夫模型可以定義為1個三元組 M=(A,B,π)。其中：A=(aij)為轉(zhuǎn)移概率矩陣，定義為從一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)的概率；B=(bij)為觀察值概率矩陣，定義為任意給定狀態(tài)下觀察值的概率分布；π=(πi)為初始概率分布，定義為每個狀態(tài)作為初始狀態(tài)的概率分布。設(shè) O=(O1,O2,L,On)為觀察值序列，而S=(S1,S2,L,Sn)為狀態(tài)序列。

本文中用于確定冗余服務(wù)的 HMM 模型實例如下。

隱藏狀態(tài) S=(S1,S2)。

觀察值 O=(O1,O2)。

轉(zhuǎn)移概率 aij=P(si|sj)，表示服務(wù)在t時刻從一種狀態(tài)si轉(zhuǎn)移到另一種狀態(tài)sj的概率。

觀察概率 bi=P(oj|si) ，表 示服務(wù)在狀態(tài)si觀察值發(fā)生變化的概率。

初始概率 πi=P(si)表示服務(wù)處在初始狀態(tài) si的概率。

至此得到 HMM 模型求解所需的所有必備要素。在 HMM 模型的求解過程中，由于可以得到服務(wù)的若干觀察值，如 O=(O1,O2,L,On)，這樣，實際 HMM的求解過程就可以轉(zhuǎn)化為 HMM 的經(jīng)典問題 learning problem 的求解過程，能夠通過一系列方法求解出HMM 的所有參數(shù) M=(A,B,π)，并得出能夠最佳匹配觀察值序列的π。以下簡要介紹求解該問題的步驟(算法3)，相關(guān)推導(dǎo)見文獻(xiàn)[17]。

第1步，定義前向變量 αt(i)為給定模型 M 時 t時刻以前的觀察值序列和在 t 時刻服務(wù)處在狀態(tài) si的條件概率，如下式所示：

然后，通過使用歸納法求解 αt(i)。

1)在初始狀態(tài)下，

2)在歸納過程中，

3)終止?fàn)顟B(tài)為

第2步，定義后向變量 βt(i)為給定模型 M 和 t時刻服務(wù)處在概率 si時從 t+1時刻到終止時刻的部分觀察值序列的條件概率：

同樣，采用歸納法求解 βt(i)。

1)在初始狀態(tài)下，

2)在歸納過程中，

3)在終止?fàn)顟B(tài)下，

第3步，定義 θt(i,j)為給定觀察值序列和模型M時服務(wù)狀態(tài)從t時刻的 sj轉(zhuǎn)移為 t+1時刻的 sj的條件概率：

綜合利用式(5)～(12)，可 以得到 θt(i,j)的表達(dá)式如下：

第4步，定 義 γt(i)為給定觀察值序列和模型M時服務(wù)在 t 時刻處在狀態(tài) si的條件概率，則可以將 γt(i)與 θt(i,j)對應(yīng)起來，如下式所示：

然后，依據(jù)式(15)～(17)獲得M的各個參數(shù)值：

最后，利用 Baum-Welch 算法實現(xiàn)冗余服務(wù)的判斷。

Algorithm 3: RDM(redundancy detection method)

Input: Observable sequence O=(O1,O2,…,On)

Output: M=(A,B,π)

1.Sample the service set as theCandidate service St

2.Initial M0

3.Estimation

4.If lgP(O|M)?lgP(O|M0)＜σ

5.M=M0

6.Else

7.M0=M

8.got step 4,re-estimation

9.End if

10.Output

圖3所示為本文所提算法的系統(tǒng)實現(xiàn)模型。圖 3主要表現(xiàn)了系統(tǒng)的各個組成構(gòu)件、構(gòu)件之間的關(guān)系以及各種輸入輸出數(shù)據(jù)等。首先用 PLSI 對候選服務(wù)進(jìn)行聚類，而后采用混合推薦算法和基于 random walk策略的Top-N貪婪搜索方法獲取最符合需求的服務(wù)。為提高服務(wù)質(zhì)量，還綜合考慮新用戶推薦、QoS 控制和冗余檢測等多項工作。

圖3　服務(wù)搜索的系統(tǒng)模型框架Fig.3　System model for services search

3 實驗及性能分析

3.1實驗設(shè)計

為驗證本文所提算法的性能，設(shè)計一組實驗，實驗采用 Matlab R2009a 進(jìn)行編程，相關(guān)服務(wù)部署在Axis1.4.2上。實驗數(shù)據(jù)為MovieLens數(shù)據(jù)集[18]和通過公開 API 收集到的10 000 條 Web 服務(wù)數(shù)據(jù)。其中MovieLens數(shù)據(jù)集包含6 040個用戶和3 900部電影，以及每個用戶對電影進(jìn)行1～5星的評分，該數(shù)據(jù)集被廣泛用于驗證推薦系統(tǒng)性能。而對于實驗使用的Web服務(wù)數(shù)據(jù)，只計算其中響應(yīng)時間及可用性這2 項 QoS指標(biāo)。并且在實驗過程中，采用文獻(xiàn)[19]中描述的方法對每個服務(wù)的QoS數(shù)據(jù)進(jìn)行歸一化處理。

實驗的評價指標(biāo)是在信息推薦領(lǐng)域廣泛使用的指標(biāo)EMA，其表達(dá)式如下：

其中：ri, j為服務(wù)的實際 QoS 值；P(ru, i)為預(yù)測值。EMA越小，表示預(yù)測精度越高。

3.2實驗結(jié)果及分析

實驗的對比方法包括基于用戶的協(xié)同過濾方法(user-basedCF)、平均預(yù)測方法(average prediction)、貪婪搜索算法(greedy)和隨機(jī)預(yù)測方法(random)等。用這些方法進(jìn)行準(zhǔn)確率對比分析實驗、新用戶影響分析實驗、冗余消減策略應(yīng)用分析實驗和延遲分析實驗。

3.2.1準(zhǔn)確率對比分析

主要基于MovieLens數(shù)據(jù)集進(jìn)行實驗，以用戶鄰居數(shù)為橫坐標(biāo)，以EMA為縱坐標(biāo)驗證算法性能。實驗結(jié)果如圖4所示。

從圖4可見：1)當(dāng)服務(wù)數(shù)量增加時，可供評價的服務(wù)數(shù)量也增加，而這將同時提供混合推薦算法和基于用戶方法的推薦準(zhǔn)確性，但對平均預(yù)測方法不造成影響；2)混合推薦算法很好地平衡了基于用戶的協(xié)同過濾方法和基于項目的協(xié)同過濾方法的優(yōu)缺點，因此，對于性能的改善有積極作用。

圖4不同方法的準(zhǔn)確率對比分析Fig.4AccuracyComparison of different methods

3.2.2新用戶影響分析

該實驗建立在公共服務(wù)數(shù)據(jù)集上，結(jié)果如圖 5所示。實驗結(jié)果表明：考慮了新用戶偏好的混合推薦算法性能明顯優(yōu)于未考慮新用戶偏好的算法性能。而由于新用戶沒有歷史信息，因此，基于熵的方法無法提供有效的推薦。

3.2.3冗余消減策略應(yīng)用分析

在該實驗中，使用 HMM 模型檢測冗余服務(wù)。實驗結(jié)果見圖 6。從圖6可見：使用了冗余檢測方法的算法性能明顯優(yōu)于未使用冗余檢測方法的算法性能，而當(dāng)冗余服務(wù)比例較大時該算法的性能優(yōu)勢更加突出。

圖5　新用戶影響分析Fig.5　Impact of new user

圖6　冗余消解策略應(yīng)用分析Fig.6　Impact of redundancy detection

3.2.4延遲分析

進(jìn)一步地進(jìn)行延遲分析(圖 7)以及平均 QoS 值比較，結(jié)果分別見圖7和圖 8。對比方法為貪婪搜索算法(greedy)、隨機(jī)預(yù)測方法(random)和冗余檢測算法(RDM)。由于服務(wù)數(shù)量增加，搜索最優(yōu)服務(wù)的時間必然會延長，因此，貪婪搜索算法在延遲上呈指數(shù)級增加是用戶無法接受的，而 RDM 算法的延遲僅僅稍高于Random算法的延遲，平均QoS值卻得到極大提升，這表明 RDM 對于最優(yōu)服務(wù)的選擇和推薦具有很重要的所用。而其原因在于 RDM 使用了有效的聚類方法和隨機(jī)行走策略。

圖7　不同算法的延遲分析Fig.7　DelayComparison of different algorithms

圖8　不同算法的平均QoS指標(biāo)對比分析Fig.8　Average QoSComparison of different algorithms

4 相關(guān)工作

與本文工作相關(guān)的研究主要包括：基于QoS的服務(wù)選擇(QoS-based service selection)、協(xié)同過濾推薦(collaborative filtering based recommendation)、新用戶偏好識別(learning of new user needs)和冗余檢測(redundancy detection)。

近年來，基于QoS服務(wù)選擇的研究很多[2,4,5,20?21]。BALKE 等[20]綜合利用了服務(wù)使用模式和用戶需求偏好來擴(kuò)大服務(wù)發(fā)現(xiàn)的范圍，并借此提高候選服務(wù)的質(zhì)量；文獻(xiàn)[22]提出了一種基于預(yù)測的 QoS 管理算法，通過使用在線配置文件以及抽樣方法來評估動態(tài)服務(wù)數(shù)據(jù)的代價并借此調(diào)整服務(wù)QoS，以滿足不同需求。

協(xié)同過濾推薦已被廣泛用于發(fā)現(xiàn)相似用戶或相似產(chǎn)品[6-8,22]。主要的協(xié)同過濾方法包括基于用戶的協(xié)同過濾方法和基于項目的協(xié)同過濾方法，但這 2種方法各自存在無法克服的缺點。為此，文獻(xiàn)[23]提出了一種混合推薦算法以給出準(zhǔn)確的推薦，但該方法對新用戶偏好欠考量；文獻(xiàn)[24]利用了貝葉斯網(wǎng)絡(luò)(Bayesian network inference)進(jìn)行信息推薦；而文獻(xiàn)[25]利用社會信譽(yù)度模型來進(jìn)行在線社會網(wǎng)絡(luò)中的信息推薦。

對于新用戶偏好的缺點，絕大多數(shù)的研究集中于信息的受歡迎度分析，但由于將最受歡迎的信息推薦給用戶無法有效地發(fā)現(xiàn)用戶的個性偏好，因此，這種方法并不可靠。為此，文獻(xiàn)[12]提出一種綜合利用信息熵(entropy)和受歡迎度的方法；而文獻(xiàn)[10]則利用“訪問了這件商品的用戶，又訪問了另一件商品”的模式(co-visitation)進(jìn)行了新用戶的推薦。

目前人們對信息冗余檢測的研究很少，部分相關(guān)研究包括：文獻(xiàn)[1]提出了一種通過構(gòu)建用戶相關(guān)度來過濾無關(guān)信息的方法，而文獻(xiàn)[14]則提出了一種用戶社會關(guān)系劃分的方法，并通過這種方法有效地發(fā)現(xiàn)用戶的興趣，以過濾無關(guān)信息。

5　結(jié)論

1)為有效發(fā)現(xiàn)云環(huán)境下的最優(yōu)服務(wù)，提出了一系列信息推薦方法。首先對協(xié)同過濾方法進(jìn)行分析，并基于歷史信息提出混合推薦方法；而后通過對新用戶特點進(jìn)行分析，提出了新用戶的偏好獲取方法；由于冗余信息會對最優(yōu)服務(wù)的選擇造成巨大影響，因此，基于隱馬爾科夫模型進(jìn)一步提出冗余信息的消解方法。最后，依托真實數(shù)據(jù)集和通過公共API獲取的服務(wù)進(jìn)行實驗，實驗結(jié)果表明上述算法在推薦的準(zhǔn)確性和時效性等方面都取得了較大提升。

2)基于混合推薦的方法僅僅考慮了基于內(nèi)存的協(xié)同過濾方法(memory-basedCollaborative filtering)，還沒有考慮網(wǎng)絡(luò)的本身的結(jié)構(gòu)拓?fù)?，在下一步工作中，需綜合考慮網(wǎng)絡(luò)拓?fù)?，并預(yù)測動態(tài)服務(wù)和推薦上以準(zhǔn)確捕捉用戶偏好的動態(tài)變化。

參考文獻(xiàn)：

[1]LV Y H,MOON T,KOLARI P,et al.Learning to model relatedness for news recommendation[C]//Proceedings of the 20th InternationalConference on World Wide Web.Hyderabad,India: ACM,2011: 57?66.

[2]HUH E,WELCH L R,TJADEN B,et al.Accommodating QoS prediction in an adaptive resource management framework[C]//Parallel and Distributed Processing-15 IPDPS 2000 Workshops.Cancun,Mexico: IEEE,2000: 792?799.

[3]SMITH W,FOSTER I,TAYLOR V.Predicting application run times using historical information[J].Journal of Parallel and DistributedComputing,2004,64(9):1007?1016.

[4]BLAKE M B,NOWLAN M F.Predicting service mashupCandidates using enhanced syntactical message management[C]//2008 IEEE InternationalConference on ServicesComputing.Honolulu,USA: IEEE,2008: 229?236.

[5]MOONEY R J,ROY L.Content-based book recommendation using learning for textCategorization[C]//Proceedings of the ACM InternationalConference on Digital Libraries.Kyoto,Japan: ACM,2000:195?204.

[6]SHAO L S,ZHANG J,WEI Y,et al.Personalized QoS prediction for web services viaCollaborative filtering[C]//IEEE InternationalConference on Web Services.Salt LakeCity,USA: IEEE,2007:1?8.

[7]SU X Y,KHOSHGOFTAAR T M.A survey ofCollaborative filtering techniques[J].Advances in Artificial Intelligence Archive,2009.doi:10.1155/2009/421425.

[8]MA H,KING I,LYU M R.Effective missing data prediction forCollaborative filtering[C]//Proceedings of the 30th Annual International ACM SIGIRConference on Research and Development in Information Retrieval.Amsterdam,Netherland: ACM,2007: 39?46.

[9]RESNICK P,LAKOVOU N,SUSHAK M,et al.GroupLens: An open architecture forCollaborative filtering of net news[C]//InternationalConference onComputer SupportedCooperative Work.Chapel Hill,USA: ACM,1994:175?186.

[10]DAS A,DATAR M,GARG A.Google news personalization: scalable onlineCollaborative filtering[C]//Proceedings of the16th InternationalConference on World Wide Web.Banff,Canada: ACM,2007: 271?280.

[11]SARWAR B,KARYPIS G,KONSTAN J,et al.Item-basedCollaborativefilteringrecommendationalgorithms[C]//Proceedings of the10th InternationalConference on World Wide Web.Hong Kong: ACM,2001: 285?295.

[12]RASHID A M,ALBERT I,COSLEY D,et al.Getting to know you: Learning new user preference in recommender systems[C]//InternationalConference on Intelligent User Interfaces.San Francisco,USA: ACM,2002:127?134.

[13]KOHRS A,MERIALDO B.ImprovingCollaborative filtering for new users by smart object selection[C]//Proceedings of InternationalConference on Media Feature.Florence,Italy: IEEE,2001.

[14]TANG S J,YUAN J,MAO X F,et al.RelationshipClassificationin large scale online social networks and its impact on information propagation[C]//IEEE InternationalConference onComputerCommunications.Shanghai,China: IEEE,2011: 2291?2299.

[15]CHEN H H,MA J W,HUANGFU X P,et al.Process reservation for service oriented application[C]//6th WorldCongress on Services.Miami,USA: IEEE,2010:162?163.

[16]DONG X L,BERTI-ENQULLE L,SRIVASTAVA D.Truth discovery andCopying detection in a dynamic world[J].Proceedings of the Vldb Endowment,2009,2: 562?573.

[17]RABINAR L R.A tutorial on hidden markov models and selected applications in speech recognition[J].Proceedings of the IEEE,1989,77(2): 257?286.

[18]Grouplens Research.MovieLens data sets[EB/OL].2010.http://grouplens.org/datasets/movielens/

[19]LIU Y T,NGU A,ZENG L Z.QoSComputation and policing in dynamic web service selection[C]//Proceedings of the13th InternationalConference on World Wide Web.New York,USA: ACM,2004: 66?73.

[20]BALKE W,MATTHIAS W.Towards personalized selection of web services[C]//Proceedings of the12th InternationalConference on World Wide Web.Budapest,Hungary: ACM,2003: 20-24.

[21]LI M,HUAI J P,GUO H P.An adaptive web services selection method based on the QoS prediction mechanism[C]//IEEE/WIC/ACM InternationalConference on Web Intelligence and Intelligent Agent Technology Workshops.Milan,Italy: IEEE,2009: 395?402.

[22]WEI Y,PRASAD V,SANG H,et al.Prediction-based QoS management for real-time data streams[C]//Proceedings of the 27th IEEE International Real-Time Systems Symposium.Rio de Janeiro,Brazil: IEEE,2006: 344?355.

[23]ZHENG Z B,MA H,LYU M R,et al.WSRec: ACollaborative filtering based web service recommender system[C]//2009 IEEE InternationalConference on Web Services.Los Angeles,USA: IEEE,2009: 437?444.

[24]YANG X W,GUO Y,LIU Y.Bayesian-inference based recommendation in online social networks[C]//IEEE InternationalConference onComputerCommunications.Shanghai,China: IEEE,2011: 551?555.

[25]CHEN RC,LUA E K,CAI Z H.Bring order to online social networks[C]//IEEE InternationalConference onComputerCommunications.Shanghai,China: IEEE,2011: 541?545.

(編輯 陳燦華)

Recommending services via hybrid recommendation algorithms and hidden Markov model inCloud

MA Jianwei1,2,CHEN Honghui1,STEPHAN Reiff-Marganiec3
(1.Science and Technology of Information System Engineering Laboratory,National University of Defense Technology,Changsha 410073,China? 2.Department of Health Service,Third Military Medical University,Chongqing 400038,China? 3.Department ofComputer Science,University of Leicester,Leicester,UK)

Abstract:With the increase of the number of users using web services for online activities through thousands of services,proper services must be obtained? however,the existing methods such asContent-based approaches orCollaborative filtering do notConsider new users and redundant services.An effective approach was proposed to recommend the most appropriate services in aCloudComputing environment.Firstly,a hybridCollaborative filtering method was proposed to recommend services.The method greatly enhances the prediction of theCurrent QoS value which may differ from that of the service publication phase.Secondly,a strategy was proposed to obtain the preferences of the new users who are neglected in other research.Thirdly,a HMM(hidden Markov model)-based approach was proposed to identify redundant services in a dynamic situation.Finally,several experiments were set up based on real data set and publicly published web services data set.The results show that the proposed algorithm has better performance than other methods.

Key words:Collaborative filtering?service selection?new user learning?hidden Markov model?redundancy detection

中圖分類號：TP393

文獻(xiàn)標(biāo)志碼：A

文章編號：1672?7207(2016)01?0082?09

DOI:10.11817/j.issn.1672-7207.2016.01.013

收稿日期：2015?01?22；修回日期：2015?03?25

基金項目(Foundation item)：國家自然科學(xué)基金資助項目(71071160)；全軍后勤科研重點計劃項目(BWS14J032)；湖南省優(yōu)秀研究生創(chuàng)新項目(CX2011B024)；國防科技大學(xué)優(yōu)秀研究生創(chuàng)新項目(B110502)；第三軍醫(yī)大學(xué)人文社科基金資助項目(2015XRW10)(Projects(61070216,71071160)supported by the National Natural Science Foundation ofChina? Project(BWS14J032)supported by the Logistics Research Plan ofChinese PLA? Project(CX2011B024)supported by the Outstanding Graduate Student Innovation Fund of Hunan Province? Project(B110502)supported by the Outstanding Graduate Student Innovation Fund of National University of Defense Technology? Project(2015XRW10)supported by Social Science Foundation of Third Military Medical University)

通信作者：馬建威，博士，講師，從事社會網(wǎng)絡(luò)分析、服務(wù)計算技術(shù)及衛(wèi)勤信息化技術(shù)研究；E-mail: majianwei@nudt.edu.cn