基于決策樹分類的智能緩存模型研究

范新燦

(深圳職業(yè)技術(shù)學(xué)院 電信學(xué)院，廣東 深圳518055)

1 Web緩存技術(shù)

互聯(lián)網(wǎng)已經(jīng)滲透進(jìn)人們生活的方方面面，Web成為獲取、發(fā)布、加工和處理信息的重要平臺。Web用戶的快速增長，導(dǎo)致Web流量的爆炸性增長，Internet帶寬產(chǎn)生擁擠，出現(xiàn)訪問延遲、通信錯誤增多、服務(wù)器過載等一系列問題，網(wǎng)絡(luò)帶寬的提高已經(jīng)跟不上用戶數(shù)量增長的速度，單純利用增加帶寬來解決速度遲緩問題不具有伸縮性，費用也相當(dāng)昂貴。

獲取一個Web文檔的代價取決于該文檔的字節(jié)數(shù)、傳輸中鏈接可獲得的帶寬以及中間經(jīng)過的網(wǎng)段個數(shù)，若能將文檔的復(fù)本從原始服務(wù)器緩存到離用戶較近的機(jī)器中，顯然可以大大縮短訪問的距離，不僅可以減少檢索延遲，還可以減少網(wǎng)絡(luò)負(fù)載。Web緩存技術(shù)是一種避免Web服務(wù)瓶頸、縮減信息流量、提高可伸縮性的手段，是最常用、經(jīng)濟(jì)的解決網(wǎng)絡(luò)擁塞和服務(wù)器過載的方法。利用Cache技術(shù)，復(fù)制用戶經(jīng)常訪問的內(nèi)容，將其保存在緩存服務(wù)器中，降低了主干網(wǎng)絡(luò)冗余帶寬流量和原始服務(wù)器的負(fù)載壓力，減少文件在網(wǎng)絡(luò)上的重復(fù)傳輸，可降低網(wǎng)絡(luò)帶寬的浪費，減輕Web服務(wù)器的負(fù)載，最終降低用戶的等待時間。

經(jīng)常被訪問的文件被緩存到了臨近的代理中，從而避免了從遠(yuǎn)端的服務(wù)器上傳輸數(shù)據(jù)，使傳輸時間最小化。由于網(wǎng)絡(luò)流量的縮減，沒有緩存的文件會相對更快地在網(wǎng)絡(luò)中傳輸，因而服務(wù)器響應(yīng)的速度也得到了提高，這些工作負(fù)荷被整個互聯(lián)網(wǎng)上的緩存代理分擔(dān)了，有效地縮減了對網(wǎng)絡(luò)帶寬的消耗，從而降低了網(wǎng)絡(luò)的流量，緩解了網(wǎng)絡(luò)擁塞。Web緩存技術(shù)成為互聯(lián)網(wǎng)建構(gòu)中廣泛應(yīng)用的技術(shù)。

2 決策樹

決策樹(decision tree)一般都是自上而下生成的。每個決策或事件（即自然狀態(tài)）都可能引出兩個或多個事件，導(dǎo)致不同的結(jié)果，把這種決策分支畫成圖形很像一棵樹的枝干，故稱決策樹。 決策樹的構(gòu)成有四個要素：決策節(jié)點、方案枝、狀態(tài)節(jié)點和概率枝。

決策樹法的決策程序如下：

(1)繪制樹狀圖，根據(jù)已知條件排列出各個方案和每一方案的各種自然狀態(tài)；

(2)將各狀態(tài)概率及損益值標(biāo)于概率枝上；

(3)計算各個方案期望值并將其標(biāo)于該方案對應(yīng)的狀態(tài)節(jié)點上；

(4)進(jìn)行剪枝，比較各個方案的期望值，并標(biāo)于方案枝上，將期望值小的(即劣等方案剪掉)所剩的最后方案為最佳方案。

決策樹算法是一種逼近離散函數(shù)值的方法。決策樹算法具有分類精度高、形成的模式簡單、對噪聲數(shù)據(jù)有很好的健壯性等優(yōu)點，因而是目前應(yīng)用最為廣泛的歸納推理算法之一，在數(shù)據(jù)挖掘中受到研究者的廣泛關(guān)注。

本文研究的智能緩存模型采用GATree決策樹算法，該算法是用遺傳算法優(yōu)化產(chǎn)生的決策樹算法。采用二叉樹結(jié)構(gòu)來表達(dá)決策樹，每個節(jié)點有兩個不同節(jié)點，每個節(jié)點有隨機(jī)值，選擇一個隨機(jī)的屬性，如果其是離散的，則自由選擇值；如果這個屬性是連續(xù)的，則隨機(jī)選擇最小最大值范圍之內(nèi)的一個整數(shù)值，這樣可以減少搜索空間的范圍。

算法的基本形式引入了變異和交叉操作的最小范圍，變異操作選擇的是期望生成的樹的隨機(jī)節(jié)點，替代了節(jié)點的具有隨機(jī)選擇值的測試值，當(dāng)隨機(jī)節(jié)點是葉子節(jié)點時，替代了具有新的隨機(jī)選擇類的意境設(shè)置好的類。交叉操作選擇兩個隨機(jī)節(jié)點并且交換這些節(jié)點的子樹，不會影響決策樹的連貫性。

3 緩存模型構(gòu)建

設(shè)計基于決策樹的智能緩存模型模擬器，如圖1所示，模型總體分為構(gòu)建數(shù)據(jù)建模、模擬器和緩存輸出模塊。模擬器是模型的關(guān)鍵，分為NextAccess離散化、構(gòu)造決策樹、權(quán)重分配和決策樹輸出4個模塊。

模型首先讀取Web日志中的記錄，并將其進(jìn)行數(shù)據(jù)建模。根據(jù)Web請求序列數(shù)據(jù)請求對象，將產(chǎn)生的數(shù)據(jù)存入緩存數(shù)據(jù)表中。根據(jù)數(shù)據(jù)流的輸入，構(gòu)建決策樹智能緩存策略的數(shù)據(jù)挖掘模型。首先將同一URL下次被訪問前接受的請求總數(shù)（NextAccess）作為分類的目標(biāo)，進(jìn)行離散化，構(gòu)建決策樹。權(quán)重分配模塊采用典型的替換算法LRU進(jìn)行頁面替換，當(dāng)緩存中沒有足夠的容量來容納新來的Web對象時，調(diào)用替換算法做出替換決定。根據(jù)當(dāng)前請求序列的預(yù)測結(jié)果，更新決策樹節(jié)點信息，觀察屬性集，計算預(yù)取闕值，進(jìn)行決策樹輸出。

3.1 數(shù)據(jù)建模緩存數(shù)據(jù)表

智能模型設(shè)計一個Web數(shù)據(jù)表，數(shù)據(jù)來源是代理服務(wù)器日志文件中的數(shù)據(jù)，產(chǎn)生包括預(yù)處理和編碼來實現(xiàn)數(shù)據(jù)選擇、清洗和數(shù)據(jù)轉(zhuǎn)換。設(shè)計數(shù)據(jù)表tb_cache，關(guān)鍵字段定義如下：

Ndir：URL 的目錄層

FirstDir：URL的第一層目錄

NextAccess:同一URL下次被訪問前接受的請求總數(shù)

LastAccess:同一URL上次被訪問到當(dāng)前的請求總數(shù)

FileExtension：請求的URL文件的文件名后綴的代碼標(biāo)識

Size：返回客戶端的字節(jié)

數(shù)據(jù)表的每一行數(shù)據(jù)存儲代理服務(wù)器的一個事務(wù)，但Web文檔可被緩存必須是HTTP協(xié)議、是GET請求、請求中沒有“?”和HTTP響應(yīng)碼是200，這些數(shù)據(jù)需要在模型中進(jìn)行過濾清洗，把相應(yīng)事務(wù)導(dǎo)入數(shù)據(jù)庫中。

3.2 構(gòu)建基于決策樹分類的模擬器

數(shù)據(jù)表字段NextAccess存儲的是同一URL下次被訪問前接受的請求總數(shù)，為了把決策樹作為智能緩存策略的數(shù)據(jù)挖掘模型，需要將NextAccess離散化、構(gòu)造決策樹所用的觀察屬性集和權(quán)重分配算法。下面作幾個定義：

ORCLCaches(s)：緩存大小為 s的使用 ORCL緩存策略的Web緩存系統(tǒng)；

ORCLAvgDSize(s)：Web緩存中的平均文檔的大小；

ORCLTertile(t,s),t{1，2，3}：緩存存儲狀態(tài)為 t*33.3%時的文檔數(shù)；

ORCLMax(s)：緩存滿時的個體數(shù)，等于 ORCLTertiles(3,s)。

3.2.1 NextAccess的離散化

在決策樹模型設(shè)計中，將NextAccess作為分類的目標(biāo)，利用決策樹作為一個分類器，預(yù)測NextAccess的值，將值離散化到幾個類別中，定義如下：

Class0：NextAccess[1，ORCLTertile(1,s)];

Class1：NextAccess[ORCLTertile(1,s)，ORCLTertile(2,s)];

Class2：NextAccess[ORCLTertile(2,s)，ORCLTertile(3,s)];

Class3：NextAccess[ORCLTertile(3,s)，ORCLMax(s)];

緩存系統(tǒng)在經(jīng)過NextAccess次請求后，可能成功緩存某一資源，這個概率依賴于緩存系統(tǒng)中的實體個數(shù)，當(dāng) NextAccess在[1，ORCLTertile(1,s)]之間時，經(jīng)過 NextAccess次請求后有66.66%～100%的可能性；當(dāng)NextAccess 在[ORCLTertile(1,s)，ORCLTertile(2,s)]之間時 ，概率下降到 33.33%～66.66%； 界于 [ORCLTertile(2,s)，ORCLMax(s)]之間，概率下降到0-33.33%，因此低類值的要給予高優(yōu)先權(quán)。

3.2.2 權(quán)重分配

替換策略的權(quán)重分配如下：

WLRU(Ei)=j，j為文檔 E的第j次訪問。

S3替換策略的權(quán)重分配如下：

Ws3(Ei)=j+a(c)*AvgDsize(s)/Ei.size;c∈{0,1,2,3};c為文檔Ei根據(jù)GATree算法所在類別。

a(3)=Max(s)；

a(c+1)=2a(c)；

Ei.size為文檔Ei的大小。

3.2.3 觀察屬性集與輸出決策樹

將 Ndir、FirstDir、LastAccess、FileExt、Hour、Size 作為GATree算法的觀察屬性。GATree輸出決策樹如下：

4 緩存模型試驗結(jié)果

實驗采用網(wǎng)站的真實訪問，獲得訪問日志數(shù)據(jù)，進(jìn)行數(shù)據(jù)預(yù)處理，建立緩存數(shù)據(jù)表，并采用本文提出的基于決策樹算法構(gòu)建模型。仿真實驗選擇傳統(tǒng)的替換算法LRU和本文所建立緩存模型進(jìn)行比較，從緩存性能的指標(biāo)命中率（HR）、字節(jié)命中率（BHR）、延遲率（LR）三個環(huán)節(jié)進(jìn)行分析。HR表示用戶從緩存中取到的對象數(shù)和所獲得的總對象數(shù)，BHR表示用戶從緩存中獲取對象的平均字節(jié)數(shù)和從網(wǎng)上獲取的全部字節(jié)數(shù)的比值，LR表示從服務(wù)器下載對象到客戶端緩存的總時間。

從如圖 2、圖 3、圖 4所示，基于決策樹的職能緩存模型比傳統(tǒng)的LRU替換算法具有較高的命中率和字節(jié)命中率，并且延遲率較小，可見本文提出的緩存優(yōu)化模型較傳統(tǒng)的算法減少了緩存文件的冗余度，提高了命中率，改善了系統(tǒng)性能。

[1]鄧?yán)冢愔緞偅S鍵，等.基于 AOP的智能 Web緩存框架[J]. 計算機(jī)工程，2008，34(22)：283-285.

[2]韓向春，田玉根.基于預(yù)測的Web緩存替換算法[J].計算機(jī)工程與設(shè)計，2010,31(1):110-113.

[3]BALAMASH A，KLUNZ M.An overview ofweb caching replacementalgorithms[J].IEEE Communications Surveys and Tutorials，2004，6(2)：44-56.

[4]Ristenpart T Back to the Future：A framework for automatic malware removal and system repair[C]//Proc.of the Annual Computer Security Applications Conference.Miami，F(xiàn)L，USA：IEEE Computer Society，2006.