一種多markov鏈預(yù)測(cè)模型的web緩存替換算法

一種多markov鏈預(yù)測(cè)模型的web緩存替換算法

1多模型優(yōu)化算法由于用戶數(shù)量的急劇增加和當(dāng)前網(wǎng)絡(luò)速度的雙重限制，人們?cè)诮邮站W(wǎng)絡(luò)信息時(shí)往往害怕長(zhǎng)期等待。web緩存技術(shù)允許用戶訪問(wèn)的對(duì)象減少網(wǎng)絡(luò)連接量，改善響應(yīng)時(shí)間，這是一個(gè)簡(jiǎn)單有效的解決方案。緩存的性能很大程度上依賴于緩存替換算法,雖然經(jīng)典算法使Web緩存的性能得到了一定程度的提高,但由于缺乏預(yù)測(cè)機(jī)制緩存的性能作用有限.文獻(xiàn)中通過(guò)研究社交網(wǎng)站(SNS)中用戶的訪問(wèn)行為模型,提出了具有預(yù)測(cè)機(jī)制、面向SNS用戶的緩存替換算法,但是算法只面向SNS用戶無(wú)法適應(yīng)通用的網(wǎng)絡(luò)環(huán)境中.文獻(xiàn)中利用PPM預(yù)測(cè)模型根據(jù)上下文關(guān)系和序列匹配得到預(yù)測(cè)對(duì)象集,該模型在預(yù)測(cè)精度與空間復(fù)雜度間難以達(dá)到平衡.文獻(xiàn)中將預(yù)處理后會(huì)話得到的序列構(gòu)建訪問(wèn)模式樹(shù),并根據(jù)最小支持度進(jìn)一步建立頻繁訪問(wèn)模式樹(shù),該方法沒(méi)有考慮各個(gè)用戶瀏覽過(guò)程中的差異性.目前還沒(méi)有一種可以適應(yīng)任意網(wǎng)絡(luò)環(huán)境表現(xiàn)出較好性能的替換算法.替換算法的優(yōu)劣衡量通過(guò)多個(gè)性能標(biāo)準(zhǔn)綜合評(píng)估,好的算法需要在多個(gè)性能標(biāo)準(zhǔn)間取得平衡.文獻(xiàn)中使用Markov鏈模型描述Web中用戶的瀏覽特征,進(jìn)而對(duì)用戶的訪問(wèn)進(jìn)行預(yù)測(cè),該類方法取得了較高的預(yù)測(cè)準(zhǔn)確率.針對(duì)已有算法的缺陷,本文充分考慮Web中各個(gè)用戶瀏覽過(guò)程的差異性,將具有相同或相近瀏覽特征的用戶用同一個(gè)模型描述,建立多Markov鏈模型,利用該模型對(duì)用戶的訪問(wèn)對(duì)象進(jìn)行預(yù)測(cè),使替換算法保留將要訪問(wèn)的對(duì)象.在GDSF算法的基礎(chǔ)上引入平均間隔時(shí)間,避免緩存保留大量不再具有存儲(chǔ)價(jià)值的對(duì)象,并將新算法命名為PGDSF-AI(PredictionGreedyDualSizeFrequency-AverageInterval)算法.通過(guò)軌跡實(shí)驗(yàn)表明,PGDSF-AI算法的多個(gè)性能指標(biāo)取得了較好的效果.2存儲(chǔ)的狀態(tài)序列緩存替換問(wèn)題可以描述如下:假設(shè)O是有限Web訪問(wèn)對(duì)象數(shù)據(jù)集,對(duì)任意請(qǐng)求對(duì)象d∈O,有相應(yīng)的對(duì)象大小為sd和取回代價(jià)cd.假定緩存總?cè)萘繛镃,當(dāng)前請(qǐng)求序列R=(R1,R2,…,Rn)導(dǎo)致緩存的一個(gè)狀態(tài)序列(S1,S2,…,Sn),已使用的緩存容量為Cused,對(duì)任意的Sk(k=1,2,…,n)有式中,Ek是移除緩存的對(duì)象的集合,且,緩存的所有狀態(tài)的遷移均滿足式(1).緩存替換算法就是在所有滿足上式的狀態(tài)序列中,找出一個(gè)狀態(tài)序列使目標(biāo)函數(shù)的數(shù)值最小.通常情況下使用一個(gè)目標(biāo)函數(shù)衡量緩存中對(duì)象的價(jià)值,選擇價(jià)值最小的對(duì)象從緩存中替換出去.3多因素鏈預(yù)測(cè)模型3.1u3000sqp的生成多Markov鏈模型根據(jù)Web中各個(gè)用戶瀏覽過(guò)程表現(xiàn)的差異性和相似性,將Web上所有的用戶分為多個(gè)類別,用四元組表示為:<X,K,P(C),MC>.其中,X={x1,x2,…,xn}是一個(gè)離散隨機(jī)變量,每個(gè)xi為一個(gè)網(wǎng)頁(yè),稱為模型的一個(gè)狀態(tài);K表示用戶類別的數(shù)目;C={c1,c2,…,ck}表示用戶的類別,其分布函數(shù)P(C)表示不同類別用戶的概率分布;MC={mc1,mc2,…,mck}為類Markov鏈的集合,mck是描述類別為ck的用戶瀏覽特征的Markov鏈,稱為類Markov鏈,其概率轉(zhuǎn)移矩陣Ak和初始狀態(tài)分布Bk分別表示為式中,pku3000ij表示從狀態(tài)Xi到狀態(tài)Xj的轉(zhuǎn)移概率,即屬于ck類別的用戶訪問(wèn)頁(yè)面xi后接下來(lái)訪問(wèn)頁(yè)面xj的概率;pki表示狀態(tài)Xi的初始狀態(tài)概率.3.2概率轉(zhuǎn)移矩陣ak將用戶的訪問(wèn)歷史頁(yè)面以時(shí)間順序排列,獲得該用戶的瀏覽序列.設(shè)有學(xué)習(xí)數(shù)據(jù)D={d1,d2,…,dm}是m個(gè)用戶的瀏覽序列,第k類用戶有mk個(gè)瀏覽序列.利用最大似然估計(jì)計(jì)算用戶的類別C的概率分布P(C=ck)=mk/m.將初始狀態(tài)看成特殊的聚類結(jié)果,將每個(gè)用戶的瀏覽序列看成一個(gè)類,為每一類別用戶建立類Markov鏈,并使用式(4)和(5)計(jì)算概率轉(zhuǎn)移矩陣Ak中的每一項(xiàng)pkij和初始狀態(tài)分布Bk中的每一維pki的值,從而得到m個(gè)類Markov鏈.式中,Skij表示在第k類所有用戶瀏覽序列中,狀態(tài)對(duì)(xi,xj)出現(xiàn)的次數(shù);αkij是超級(jí)參數(shù),取值為β/n2,β為問(wèn)題域空間的大小.同理,計(jì)算任意兩個(gè)類Markov鏈mck和mcl合并后的類Markov鏈mc(k+l)為式(6)和(7)中的所有參數(shù)與式(4)和(5)的參數(shù)相同.任意兩個(gè)概率轉(zhuǎn)移矩陣Ak和Al的相似度定義為矩陣中行的交叉熵的平均值:式中,pkij、plu3000ij分別表示概率轉(zhuǎn)移矩陣Ak和Al中從狀態(tài)Xi到狀態(tài)Xj的轉(zhuǎn)移概率;n是概率轉(zhuǎn)移矩陣的行數(shù).類Markov鏈的動(dòng)態(tài)特征由其轉(zhuǎn)移矩陣描述,兩個(gè)類Markov鏈mck和mcl的相似度由它們的概率轉(zhuǎn)移矩陣的相似度定義:M為Bayes網(wǎng)絡(luò)模型,使用模型M的似然函數(shù)P(D/M)為準(zhǔn)則函數(shù)評(píng)價(jià)聚類結(jié)果.不斷嘗試合并具有較大相似度的類Markov鏈,找到使得準(zhǔn)則函數(shù)取極值的聚類結(jié)果,即為最好的聚類結(jié)果.至此,多Markov鏈模型完成了建立的整個(gè)過(guò)程.3.3系統(tǒng)結(jié)果預(yù)測(cè)多Markov鏈模型建立后,根據(jù)當(dāng)前用戶的瀏覽過(guò)程對(duì)該用戶的接下來(lái)的訪問(wèn)進(jìn)行預(yù)測(cè).假設(shè)已知Web中用戶的瀏覽序列X=(x1,x2,…,xl),為了預(yù)測(cè)用戶將要訪問(wèn)的對(duì)象,需要先判定該用戶所屬的用戶類別,再利用當(dāng)前的瀏覽序列預(yù)測(cè)用戶可能處于的狀態(tài).其預(yù)測(cè)過(guò)程分為以下兩步:(1)bk和概率轉(zhuǎn)移矩陣ak在任意類別ck中,瀏覽序列(x1,x2,…,xl)出現(xiàn)的概率為式中,pki和pk(i-1)i分別是初始狀態(tài)分布Bk和概率轉(zhuǎn)移矩陣Ak中的項(xiàng).利用式(11)計(jì)算當(dāng)前用戶屬于某一類別ck的概率:式中,P(x1,x2,…,xl)表示序列(x1,x2,…,xl)的邊際概率;P(C=ck)表示類別ck用戶的概率分布.如果用戶滿足式(12),則將用戶所屬的類別判定為類別ck.(2)用戶狀態(tài)轉(zhuǎn)移矩陣假設(shè)用戶在t時(shí)刻的狀態(tài)向量為H(t)=(0,0,…,1,0,…,0),對(duì)應(yīng)的狀態(tài)為Xi,即t時(shí)刻訪問(wèn)了頁(yè)面對(duì)象xi,則狀態(tài)向量的第i維值記為1,其余各維值記為0.當(dāng)前用戶在t時(shí)刻的狀態(tài)用一個(gè)狀態(tài)概率向量V(t)=(P(Xt=x1),P(Xt=x2),…,P(Xt=xl))表示,V(t)中的每一維的值就是在t時(shí)刻用戶處于不同狀態(tài)的概率.若經(jīng)過(guò)判定后用戶所屬類別為ck,已知t-1時(shí)刻的狀態(tài)向量H(t-1),則t時(shí)刻用戶處于不同狀態(tài)的概率為式中,Ak表示類Markov鏈mck的狀態(tài)轉(zhuǎn)移矩陣;H(t-1)表示t-1時(shí)刻的狀態(tài)向量.4基于預(yù)測(cè)的延遲治理方法pgssf-ai4.1確定總體存儲(chǔ)價(jià)值的調(diào)節(jié)參數(shù)對(duì)于最近很少訪問(wèn)或者以后也幾乎不會(huì)被訪問(wèn)的對(duì)象,則認(rèn)為該類對(duì)象不再具有存儲(chǔ)價(jià)值,若一直存在緩存中則會(huì)降低緩存的命中率.為了解決這個(gè)缺陷,本文使用平均訪問(wèn)間隔時(shí)間評(píng)估對(duì)象接下來(lái)的訪問(wèn)變化,避免緩存保留大量不再具有存儲(chǔ)價(jià)值的對(duì)象.假設(shè)對(duì)象在第k-1次訪問(wèn)后經(jīng)過(guò)tk的時(shí)間被第k次訪問(wèn),且第k-1次訪問(wèn)后已知平均訪問(wèn)間隔時(shí)間為Tk-1,則第k次訪問(wèn)后得到的平均間隔時(shí)間Tk為式中,λ為調(diào)節(jié)參數(shù),取介于0.5和1之間的值;t為當(dāng)前時(shí)間與對(duì)像第一次訪問(wèn)的間隔時(shí)間.平均間隔時(shí)間Tk根據(jù)歷史訪問(wèn)的平均間隔時(shí)間,考慮對(duì)象過(guò)去的訪問(wèn)頻繁程度,同時(shí),通過(guò)計(jì)算最近一次訪問(wèn)后的時(shí)間流逝,充分考慮Web對(duì)象訪問(wèn)的時(shí)間局部性.剛被訪問(wèn)過(guò)的對(duì)象以及經(jīng)常被訪問(wèn)的對(duì)象,對(duì)應(yīng)的平均間隔時(shí)間也越小;對(duì)于長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)的對(duì)象,由于其流逝時(shí)間tk很大,則其平均間隔時(shí)間也較大.4.2類馬來(lái)安排p并進(jìn)行網(wǎng)絡(luò)營(yíng)銷本文提出的PGDSF-AI算法通過(guò)訓(xùn)練建立多Markov鏈預(yù)測(cè)模型,采用GDSF算法作為原型計(jì)算對(duì)象的鍵值大小,使用鍵值函數(shù)作為緩存替換問(wèn)題描述中的目標(biāo)函數(shù)用來(lái)衡量緩存中對(duì)象的價(jià)值,充分考慮對(duì)象的流行度、大小、取回代價(jià)等因素對(duì)緩存性能的影響,引入平均間隔時(shí)間評(píng)估對(duì)象訪問(wèn)的變化,使用式(15)計(jì)算緩存中對(duì)象的鍵值大小.式中,M表示膨脹因子;fd表示對(duì)象d的流行度;Td表示對(duì)象d訪問(wèn)fd次后的平均間隔時(shí)間;cd表示取回對(duì)象d所花費(fèi)的代價(jià);sd表示對(duì)象d的大小.當(dāng)用戶的請(qǐng)求到來(lái)時(shí),如果緩存中不存在請(qǐng)求的對(duì)象且沒(méi)有足夠空間保存該對(duì)象,PGDSF-AI算法將緩存中所有對(duì)象按鍵值大小進(jìn)行排序.利用多Markov鏈預(yù)測(cè)模型根據(jù)當(dāng)前用戶的請(qǐng)求序列給用戶分為類別ck,用描述該類別用戶瀏覽特征的類Markov鏈對(duì)用戶可能處于的狀態(tài)進(jìn)行預(yù)測(cè).為了控制預(yù)測(cè)的對(duì)象的數(shù)目和準(zhǔn)確性,設(shè)定概率閾值θ,獲取大于該概率閾值的狀態(tài)對(duì)象,將其組成用戶極有可能訪問(wèn)的預(yù)測(cè)對(duì)象集PSet.如果鍵值最小的對(duì)象出現(xiàn)在PSet中,則認(rèn)為該對(duì)象接下來(lái)會(huì)被訪問(wèn),選擇下一個(gè)對(duì)象替換出緩存直到緩存有足夠空間存放請(qǐng)求對(duì)象.PGDSF-AI算法描述如算法1所示.算法1:PGDSF-AI緩存替換算法輸入:學(xué)習(xí)數(shù)據(jù)D;當(dāng)前請(qǐng)求對(duì)象d;概率閾值θ;輸出:緩存對(duì)象;步驟1:初始狀態(tài)時(shí)將D中每個(gè)用戶的瀏覽序列看成一個(gè)類,利用式(4)和(5)計(jì)算概率轉(zhuǎn)移矩陣Ak和初始狀態(tài)分布Bk,為每一類用戶建立類Markov鏈;步驟2:用式(8)和(9)計(jì)算任意兩個(gè)類Markov鏈之間的相似度,并按相似度大小排成隊(duì)列Q;步驟3:利用似然函數(shù)P(D/M)計(jì)算準(zhǔn)則函數(shù)值P,利用式(6)和(7)合并Q中的兩個(gè)類Markov,直到不存在使P增大的合并;步驟4:If(d在緩存中時(shí))更新緩存中d的Td和fd;Else利用式(13)計(jì)算緩存中所有對(duì)象的鍵值,并按鍵值從小到大排成H;步驟5:利用式(10)~(12)判定當(dāng)前用戶的類別ck,用式(13)對(duì)用戶訪問(wèn)進(jìn)行預(yù)測(cè),得到狀態(tài)概率向量V(t);If(H[k]對(duì)應(yīng)的對(duì)象不屬于PSet)break;5模擬實(shí)驗(yàn)與分析5.1存儲(chǔ)的sdna實(shí)驗(yàn)使用軌跡驅(qū)動(dòng)的方法對(duì)算法性能比較和評(píng)估,數(shù)據(jù)集使用DEC和NLANR兩個(gè)數(shù)據(jù)集,DEC數(shù)據(jù)集記錄了Squid代理服務(wù)器處理的從1996.9.1到1996.9.22的3543968個(gè)請(qǐng)求,NLANR包含了NLANR中四個(gè)主要的代理服務(wù)器于1997.12.22為期一天的1766409個(gè)請(qǐng)求,實(shí)驗(yàn)前先對(duì)數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行預(yù)處理.為了驗(yàn)證本文提出的緩存替換算法的性能,實(shí)驗(yàn)在Linux系統(tǒng)平臺(tái)下使用C語(yǔ)言編寫(xiě)的緩存模擬器對(duì)替換算法仿真.引入的平均間隔時(shí)間中λ參數(shù)設(shè)為0.6,即充分考慮對(duì)象訪問(wèn)的時(shí)間局部性,對(duì)最近一次訪問(wèn)后的流逝時(shí)間賦予更大的權(quán)重,同時(shí)考慮過(guò)去的平均間隔時(shí)間.選取數(shù)據(jù)集的3/4作為訓(xùn)練集建立多Markov鏈預(yù)測(cè)模型,其余1/4數(shù)據(jù)集對(duì)用戶狀態(tài)對(duì)象預(yù)測(cè).設(shè)定概率閾值θ=0.3的條件下,緩存模擬器分別按照緩存容量占總訪問(wèn)規(guī)模的0.05%~20%變化范圍運(yùn)行.5.2不同存儲(chǔ)容量的緩沖系統(tǒng)的數(shù)據(jù)集為了驗(yàn)證算法的性能,本文主要從命中率(HitRate,HR)和字節(jié)命中率(ByteHitRate,BHR)兩個(gè)性能指標(biāo)上將提出的算法分別與LRU、SIZE、GD-Size、GDSF和LH-MLRU算法的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比,實(shí)驗(yàn)結(jié)果分別如圖1~4所示.從圖1~圖4可以看出,在命中率(HR)方面PGDSF-AI算法始終優(yōu)于其他所有算法,當(dāng)緩存大小占總訪問(wèn)對(duì)象總大小的0.05%、0.5%和5%時(shí),與LH-MLRU算法相比,在DEC數(shù)據(jù)集上能提高4%~5%左右,在NLANR數(shù)據(jù)集上提高約2%~4%.當(dāng)緩存大小占總訪問(wèn)對(duì)象總大小的10%和20%時(shí),與其他算法相比有所減少.這種現(xiàn)象產(chǎn)生的原因有兩點(diǎn):一是PGDSF-AI算法利用多Markov預(yù)測(cè)模型對(duì)用戶的瀏覽進(jìn)行預(yù)測(cè)產(chǎn)生了預(yù)測(cè)對(duì)象集,在當(dāng)緩存容量不足需要替換緩存中對(duì)象時(shí),需要先判斷該對(duì)象是否在預(yù)測(cè)對(duì)象集中,因此接下來(lái)可能被訪問(wèn)的對(duì)象可以保留在緩存中而不被替換出去;二是緩存保護(hù)平均間隔時(shí)間小的對(duì)象,使其獲得較高的鍵值,避免緩存過(guò)多保留流行度大且長(zhǎng)時(shí)間不被訪問(wèn)的對(duì)象.但當(dāng)緩存容量不斷增大時(shí),緩存有足夠的容量保存新的對(duì)象,算法的優(yōu)勢(shì)也在減弱.在字節(jié)命中率(BHR)方面,PGDSF-AI算法在數(shù)據(jù)集DEC和NLANR上均優(yōu)于其他算法,在數(shù)據(jù)集DEC上與LH-MLRU算法相比能提高1%~4%左右,在數(shù)據(jù)集NLANR上略占優(yōu)勢(shì).LH-ML-RU算法在兩個(gè)數(shù)據(jù)集上均略微優(yōu)于LRU、SIZE、GD-Size和GDSF算法,SIZE算法的性能表現(xiàn)最不理想.這是因?yàn)镻GDSF-AI算法綜合考慮了對(duì)象的各個(gè)因素,并保護(hù)平均間隔時(shí)間小的對(duì)象,使得經(jīng)常被訪問(wèn)的對(duì)象盡量保留在緩存中.LH-MLRU算法由于靈活的設(shè)置參數(shù)使算法在多個(gè)性能上達(dá)到最優(yōu),而SIZE算法每次替換占用空間最大的對(duì)象,導(dǎo)致小的對(duì)象長(zhǎng)時(shí)間保存在緩存中.6本構(gòu)模型的改進(jìn)本文基于多Markov鏈模型使用不同的類Markov鏈描述Web中具有不同瀏覽特征的用戶,并對(duì)用戶的訪問(wèn)對(duì)象進(jìn)行預(yù)測(cè),提出了具有預(yù)測(cè)機(jī)制的Web緩存替換算法PGDS