移動(dòng)云環(huán)境下基于預(yù)測(cè)圖的動(dòng)態(tài)協(xié)調(diào)過程推薦

侯小毛 張福泉 劉 定

(1.湖南信息學(xué)院 電子信息學(xué)院,湖南 長(zhǎng)沙 410105;2.北京理工大學(xué) 軟件學(xué)院,北京 100081)

0 引言

在互聯(lián)網(wǎng)高速發(fā)展時(shí)代，每天都有海量的內(nèi)容被生產(chǎn)，我們并不缺少優(yōu)質(zhì)的內(nèi)容，也不缺乏生產(chǎn)優(yōu)質(zhì)內(nèi)容的能力，而是優(yōu)質(zhì)內(nèi)容并沒有觸及其核心用戶，無法實(shí)現(xiàn)內(nèi)容與用戶的精準(zhǔn)匹配.移動(dòng)云計(jì)算作為移動(dòng)互聯(lián)網(wǎng)高速發(fā)展的新興服務(wù)模式，有著廣闊的市場(chǎng)應(yīng)用前景.云端多樣化的服務(wù)內(nèi)容如何高效地傳送至云端用戶，并給用戶提供最需要的數(shù)據(jù)是當(dāng)前移動(dòng)云計(jì)算需要解決的關(guān)鍵問題，這歸根結(jié)底就是一個(gè)個(gè)性化推薦的問題[1].當(dāng)前比較大型的互聯(lián)網(wǎng)公司都在做個(gè)性化推薦服務(wù)，通過綜合并利用用戶的興趣偏好、屬性，主題的屬性、內(nèi)容、分類，以及用戶之間的社交關(guān)系等等，挖掘用戶的喜好和需求[2,3]，主動(dòng)向用戶推薦其感興趣或者需要的內(nèi)容，實(shí)現(xiàn)內(nèi)容的精準(zhǔn)化推送.作為移動(dòng)云計(jì)算環(huán)境，這種個(gè)性化推薦服務(wù)的環(huán)境和要求更高，服務(wù)需要更精準(zhǔn)，響應(yīng)需要更迅速，能耗需要盡可能降低，目的是為了更適合移動(dòng)端的輕量級(jí)低能耗負(fù)載訪問.

1 預(yù)測(cè)圖

圖結(jié)構(gòu)作為數(shù)據(jù)存儲(chǔ)的一種結(jié)構(gòu)方式，常用作于復(fù)雜數(shù)據(jù)的多樣分析，云端用戶數(shù)據(jù)種類豐富，數(shù)據(jù)量龐大，對(duì)于單個(gè)用戶來說，數(shù)據(jù)屬性的多樣化及異構(gòu)性，在分析的時(shí)候采用圖結(jié)構(gòu)來定義說明更加方便.

圖結(jié)構(gòu)的分析核心主要是圖的鄰接矩陣分析[4]，從鄰接矩陣中將單個(gè)的節(jié)點(diǎn)通過網(wǎng)狀圖連接起來，構(gòu)成一張有價(jià)值的數(shù)據(jù)網(wǎng)圖，下面將對(duì)圖鄰接矩陣進(jìn)行定義.

假設(shè)S(ui)={ui,k|k=1,2,…,Ki}和S(uj)={uj,k|k=1,2,…,Kj}分別為兩個(gè)云計(jì)算用戶ui和uj的近鄰組集合，若ui和uj有部分鄰居關(guān)系，則定義：

若(ui?uj)：S(uj)∩S(uj)≠?，則表示ui和uj兩個(gè)集合有對(duì)等關(guān)系.

若(uiuj)：S(ui)?S(uj)，表示uj和ui是包含與被包含關(guān)系.包含等級(jí)低.

若(ui|uj)：S(ui)?S(uj)，表示uj和ui是包含與被包含關(guān)系.包含等級(jí)中.

若(uiuj)：S(ui)?S(uj)且有Sim(ui,ui,k)≤Sim(uj,uj,k)，表示uj和ui是包含與被包含關(guān)系.包含等級(jí)高.

若(ui?uj)：S(ui)∩S(uj)=?，則表示ui和uj兩個(gè)集合無直接關(guān)系.

這樣，所有云計(jì)算用戶都可以用上述關(guān)系來描述，這種關(guān)系運(yùn)用圖結(jié)構(gòu)來表示，根據(jù)對(duì)等和包含關(guān)系，可生成一個(gè)帶環(huán)有向結(jié)構(gòu)圖，這里我們定義為預(yù)測(cè)圖，如此，云計(jì)算用戶數(shù)據(jù)就可以基于預(yù)測(cè)圖來分析.

在預(yù)測(cè)分析中，分別對(duì)用戶和資源進(jìn)行相似計(jì)算，從而對(duì)用戶圖結(jié)構(gòu)和資源圖結(jié)構(gòu)進(jìn)行整理與分類處理，計(jì)算集合相似方法較多，本文采用皮爾遜相關(guān)系數(shù)法來計(jì)算相似度[5]，根據(jù)用戶對(duì)某種或者某類資源的感興趣程度，可將用戶進(jìn)行相似度計(jì)算.計(jì)算公式如(1)所示.

(1)

下面對(duì)資源進(jìn)行相似度計(jì)算，云計(jì)算服務(wù)種類多，資源豐富，在對(duì)資源進(jìn)行分類時(shí)，也可以按照公式(1)的方法進(jìn)行相似計(jì)算，目的是在動(dòng)態(tài)推薦時(shí)，可以為用戶提供更全面的相似服務(wù).

(2)

N(si)={sj|σ(Sim(si,sj)(k))>ε,1≤k≤K},

(3)

N(ui)={uj|σ(Sim(ui,uj)(k))>ε,1≤k≤K}.

(4)

因此，資源和用戶可以根據(jù)公式(3)和(4)組建近鄰矩陣.

2 動(dòng)態(tài)協(xié)調(diào)推薦

平臺(tái)推薦一般分為靜態(tài)和動(dòng)態(tài)兩種模式[7]，靜態(tài)推薦取一段時(shí)間內(nèi)根據(jù)用戶喜好和屬性進(jìn)行內(nèi)容推薦，而動(dòng)態(tài)推薦是則分為實(shí)時(shí)推薦和非實(shí)時(shí)推薦，也是根據(jù)用戶特點(diǎn)進(jìn)行針對(duì)性推薦，相比于靜態(tài)模式，推薦內(nèi)容更精準(zhǔn)，特別是實(shí)時(shí)推薦，更是有效地跟蹤用戶需求，提高推薦內(nèi)容準(zhǔn)確度，但動(dòng)態(tài)推薦服務(wù)端成本高，能耗高，綜合靜態(tài)模式和動(dòng)態(tài)模式優(yōu)缺點(diǎn)，本文選擇基于協(xié)調(diào)過程的動(dòng)態(tài)推薦方法.下面將對(duì)動(dòng)態(tài)協(xié)調(diào)過程推薦模型的建立進(jìn)行描述.

(5)

其中，用戶和云計(jì)算環(huán)境數(shù)據(jù)資源關(guān)系圖用矩陣A表示，用戶和云計(jì)算環(huán)境數(shù)據(jù)資源的矩陣用B表示.

公式(1)描述了預(yù)測(cè)數(shù)據(jù)集合計(jì)算方法，該方法在計(jì)算過程中，矩陣A和B的抽象建模過程會(huì)有損失[9]，在此定義目標(biāo)函數(shù)F來對(duì)此損失進(jìn)行評(píng)價(jià)，設(shè)用戶集合為U，數(shù)據(jù)資源集合為S，計(jì)算方法如.

(6)

其中，aij、bi和qij分別表示用戶與資源近似值，資源索引和用戶離線損失值.動(dòng)態(tài)推薦的精準(zhǔn)正是因?yàn)槊恳淮瓮扑]都是將用戶跟蹤數(shù)據(jù)和云計(jì)算資源匹配的結(jié)果.這種匹配隨時(shí)間變化，而且無規(guī)律，在此，將用戶、資源和匹配數(shù)量三者進(jìn)行隨機(jī)變換，方法如公式(7)、(8)、(9)所示.

U|t+r=H1(|U|t|pt),

(7)

S|t+r=H2(|S|t|qt),

(8)

L|t+r=H3(|L|t|ht),

(9)

H1、H2和H3分別為隨機(jī)變換函數(shù).這個(gè)隨機(jī)變換過程描述了t+r時(shí)刻的變換情況.時(shí)間間隔為r.在動(dòng)態(tài)推薦過程中，對(duì)隨機(jī)變換函數(shù)進(jìn)行相似模擬[10]，方法如

(10)

在相似模擬過程中，為了方便量化，采用σ(x)函數(shù)進(jìn)行歸一化處理.引入隨機(jī)變換之后，公式(6)可以變?yōu)榛跁r(shí)間t的函數(shù)如

(11)

3 實(shí)例仿真

為了驗(yàn)證本文推薦算法的性能，本文通過Spring+Mybatis來完成數(shù)據(jù)模型建立，通過Matlab進(jìn)行數(shù)據(jù)統(tǒng)計(jì)分析，在實(shí)例仿真過程中，將分別從相似度變化指數(shù)、近鄰動(dòng)態(tài)變化指數(shù)和準(zhǔn)確度指數(shù)三個(gè)方面來驗(yàn)證算法性能.前兩者驗(yàn)證動(dòng)態(tài)推薦的功能性，是否能夠在有限時(shí)間內(nèi)找出與某用戶具有一定相似關(guān)系的用戶和資源，后者驗(yàn)證該模型相較于其他推薦模型的優(yōu)勢(shì).

3.1 實(shí)驗(yàn)環(huán)境設(shè)置及參數(shù)配置

在本文仿真中，預(yù)測(cè)圖建立，矩陣計(jì)算等操作均在Spring+Mybatis完成，實(shí)驗(yàn)仿真數(shù)據(jù)均來自于文獻(xiàn)WS-DREAD，其中，云計(jì)算用戶個(gè)數(shù)為339個(gè)，云計(jì)算資源服務(wù)共計(jì)5 825項(xiàng)[11].

考慮到動(dòng)態(tài)協(xié)調(diào)過程的適應(yīng)性，必須考慮用戶和資源在模型構(gòu)造時(shí)的動(dòng)態(tài)變化情況，這也是精準(zhǔn)推薦實(shí)現(xiàn)的基礎(chǔ)，在預(yù)測(cè)圖鄰接矩陣變換后，要進(jìn)行相似度和準(zhǔn)確度計(jì)算評(píng)價(jià)，而動(dòng)態(tài)協(xié)調(diào)建模過程對(duì)服務(wù)質(zhì)量QoS的影響是評(píng)估該動(dòng)態(tài)協(xié)調(diào)過程的關(guān)鍵.下面將對(duì)QoS中兩個(gè)關(guān)鍵因素即響應(yīng)時(shí)間(RT)和吞吐量(TP)在建模過程中的變化進(jìn)行仿真.

3.2 相似度變化指數(shù)

考慮到用戶和資源在動(dòng)態(tài)協(xié)調(diào)過程中的變化情況，在鄰接矩陣變換及相似計(jì)算過程中，相似度變化指數(shù)衡量動(dòng)態(tài)協(xié)調(diào)過程達(dá)到穩(wěn)定狀態(tài)的效率.其計(jì)算方法如

(12)

其中τ為動(dòng)態(tài)協(xié)調(diào)過程計(jì)算變化狀態(tài)的最小時(shí)間間隔，Sim(ui,uj)(t)為t時(shí)刻用戶或者資源ui和uj的相似度.L為用戶或者資源總數(shù).

對(duì)此過程進(jìn)行Matlab仿真，分別對(duì)339個(gè)用戶和5 825條云資源服務(wù)項(xiàng)在RT和TP兩個(gè)服務(wù)質(zhì)量下的ΔSV隨時(shí)間變化情況.如圖1和2所示.

從圖1可以看出，隨著時(shí)間的增加，用戶RT和TP的相似度變化指數(shù)減小，且用戶的RT相對(duì)于TP來說，下降速度更快，當(dāng)仿真時(shí)間到達(dá)到3 s時(shí)，相似度變化指數(shù)趨近于0.

圖1 用戶的

圖2 資源的

從圖2可以看出，隨著時(shí)間的增加，資源的RT和TP的相似度變化指數(shù)減小，當(dāng)仿真時(shí)間到達(dá)到3 s時(shí)，RT的相似度變化指數(shù)趨近于0，TP的相似度變化指數(shù)趨近于0.01.

綜合圖1和圖2可以得到，用戶和資源的ΔSV隨時(shí)間的增加而降低，在3 s內(nèi)基本達(dá)到穩(wěn)態(tài)，這說明在動(dòng)態(tài)協(xié)調(diào)過程中，在用戶和資源的變化不大的情況下，相似度變化不明顯，因此根據(jù)相似度組建的近鄰矩陣也比較穩(wěn)定.

3.3 近鄰動(dòng)態(tài)指數(shù)

在對(duì)相似變化指數(shù)進(jìn)行仿真后，下面將對(duì)動(dòng)態(tài)協(xié)調(diào)過程中的近鄰動(dòng)態(tài)指數(shù)變化進(jìn)行考察.近鄰變化指數(shù)計(jì)算方法為

(13)

圖3 用戶的

圖4 資源的

從圖3可以看出，隨著時(shí)間的增加，用戶RT和TP的近鄰變化指數(shù)減小，在2 s內(nèi)，兩者的近鄰變化指數(shù)下降速度較慢，2-3 s時(shí)間段內(nèi)，下降速度明顯加快，當(dāng)仿真時(shí)間到達(dá)到3 s時(shí)，近鄰變化指數(shù)趨近于0.

從圖4可以看出，隨著時(shí)間的增加，資源RT和TP的近鄰變化指數(shù)減小，當(dāng)仿真時(shí)間到達(dá)到3 s時(shí)，近鄰變化指數(shù)趨近于0.

綜合圖3和圖4可得，隨著時(shí)間的增加，用戶和資源的近鄰變化指數(shù)均在減小，3 s達(dá)到穩(wěn)態(tài)，表明經(jīng)過3 s后，用戶和資源在RT和TP服務(wù)質(zhì)量下，近鄰趨于穩(wěn)定狀態(tài).

綜合圖1-4可得，隨著時(shí)間的增加，動(dòng)態(tài)協(xié)調(diào)過程推薦模型對(duì)于云計(jì)算環(huán)境中不論是用戶屬性還是資源屬性的某個(gè)服務(wù)質(zhì)量均會(huì)達(dá)到穩(wěn)定狀態(tài)，收斂性好.

3.4 準(zhǔn)確度

關(guān)于準(zhǔn)確度的評(píng)價(jià)標(biāo)準(zhǔn)，主要有絕對(duì)誤差(MAE)和均方誤差(RMSE)兩個(gè)指標(biāo).計(jì)算方法

(14)

(15)

下面將對(duì)典型的推薦模型和本文推薦模型在準(zhǔn)確度方面進(jìn)行比較，當(dāng)前研究中，比較常用的推薦模型主要有：UbCF、WSRec和IbCF[12].下面分別計(jì)算這三種模型及本文模型的MAE和RMSE，為了驗(yàn)證系統(tǒng)的穩(wěn)定性，分別計(jì)算了用戶數(shù)為100和200的準(zhǔn)確度，結(jié)果如表1所示.

表1不同推薦模型的MAE和RMSE比較(u=100)

評(píng)價(jià)標(biāo)準(zhǔn)模型用戶數(shù)100RTTPMAEUbCF0．43310．137WSRec0．4039．977IbCF0．47110．205本文模型0．3236．931RMSEUbCF0．86628．621WSRec0．90926．762IbCF0．87928．919本文模型0．83721．116

表2不同推薦模型的MAE和RMSE比較(u=200)

評(píng)價(jià)標(biāo)準(zhǔn)模型用戶數(shù)200RTTPMAEUbCF0．89118．112WSRec0．79617．901IbCF0．81520．127本文模型0．62312．737RMSEUbCF1．26431．621WSRec1．17328．762IbCF1．30930．919本文模型0．95222．172

從計(jì)算結(jié)果對(duì)比可得，本文模型在動(dòng)態(tài)協(xié)調(diào)過程推薦中的MAE和RMSE明顯比UbCF、WSRec和IbCF小，這表明在準(zhǔn)確度方面，本文算法有所提高，隨著用戶數(shù)量的增加，動(dòng)態(tài)推薦模型的算法的MAE和RMSE也隨之增加，增加幅度方面，UbCF、WSRec和IbCF和本文模型差距較小.

4 結(jié)語

本文將預(yù)測(cè)圖融合與動(dòng)態(tài)協(xié)調(diào)過程推薦，經(jīng)過近鄰矩陣化處理和相似度模擬，找出用戶和資源的近鄰相似關(guān)系，為動(dòng)態(tài)協(xié)調(diào)過程推薦服務(wù)提供理論基礎(chǔ)，在龐大的云計(jì)算資源庫(kù)中為不同用戶提供差異化的推薦服務(wù).相比于傳統(tǒng)推薦模型，在準(zhǔn)確度方面提升明顯，具有一定的推廣價(jià)值.

[1] 凌霄娥. 基于社會(huì)化標(biāo)簽和歷史價(jià)格曲線的網(wǎng)絡(luò)結(jié)構(gòu)個(gè)性化推薦方法[J]. 計(jì)算機(jī)工程, 2017, 43(4):212-216.

The peak e. Network structure of personalized social tag recommendation method and historical price curve based on [J]. Computer Engineering, 2017, 43 (4): 212-216.

[2] Feng X, Sharma A, Srivastava J, et al. Social network regularized Sparse Linear Model for Top-N recommendation[J]. Engineering Applications of Artificial Intelligence, 2016, 51(C):5-15.

[3] 翟鶴, 劉柏嵩. 基于用戶信任及推薦反饋機(jī)制的社會(huì)網(wǎng)絡(luò)推薦模型[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2016, 33(11):258-262.

[4] 徐仁和, 盧文博, 王海濤. 基于鄰接矩陣變型的K分網(wǎng)絡(luò)社團(tuán)算法[J]. 信息安全與技術(shù), 2016, 7(3):31-34.

[5] 柳順義, 張和平. 定向圖的斜鄰接矩陣的積和多項(xiàng)式[J]. 蘭州大學(xué)學(xué)報(bào):自然科學(xué)版, 2016, 52(5):681-685.

[6] Niusvel AcostaMendoza, Andrés GagoAlonso, Jesús Ariel CarrascoOchoa, et al. Extension of canonical adjacency matrices for frequent approximate subgraph mining on multi-graph collections[J].International Journal of Pattern Recognition & Artificial Intelligence, 2017.

[7] Guo G, Zhang J, Yorke-Smith N. A novel recommendation model regularized with user trust and item ratings[J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(7):1 607-1 620.

[8] 陳曦, 成韻姿. 一種優(yōu)化組合相似度的協(xié)同過濾推薦算法[J]. 計(jì)算機(jī)工程與科學(xué), 2017, 39(1):180-187.

[9] 張萌, 南志紅. 基于用戶偏好的信任網(wǎng)絡(luò)隨機(jī)游走推薦模型[J]. 計(jì)算機(jī)應(yīng)用, 2016, 36(12):3 363-3 368.

[10] 徐選華, 王佩, 蔡晨光. 基于云相似度的語言偏好信息多屬性大群體決策方法[J]. 控制與決策, 2017, 32(3):459-466.

[11] 萬樹平. 一種具有區(qū)間數(shù)信息的多屬性大群體決策方法[J]. 模式識(shí)別與人工智能, 2011, 24(3):340-345.

[12] 劉先紅, 李綱. 科研社交網(wǎng)絡(luò)的推薦系統(tǒng)對(duì)比分析[J]. 圖書情報(bào)工作, 2016, 60(9):116-122.