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

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

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