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

范新燦

(深圳職業技術學院 電信學院，廣東 深圳518055)

1 Web緩存技術

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

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

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

2 決策樹

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

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

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

(2)將各狀態概率及損益值標于概率枝上；

(3)計算各個方案期望值并將其標于該方案對應的狀態節點上；

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

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

本文研究的智能緩存模型采用GATree決策樹算法，該算法是用遺傳算法優化產生的決策樹算法。采用二叉樹結構來表達決策樹，每個節點有兩個不同節點，每個節點有隨機值，選擇一個隨機的屬性，如果其是離散的，則自由選擇值；如果這個屬性是連續的，則隨機選擇最小最大值范圍之內的一個整數值，這樣可以減少搜索空間的范圍。

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

3 緩存模型構建

設計基于決策樹的智能緩存模型模擬器，如圖1所示，模型總體分為構建數據建模、模擬器和緩存輸出模塊。模擬器是模型的關鍵，分為NextAccess離散化、構造決策樹、權重分配和決策樹輸出4個模塊。

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

3.1 數據建模緩存數據表

智能模型設計一個Web數據表，數據來源是代理服務器日志文件中的數據，產生包括預處理和編碼來實現數據選擇、清洗和數據轉換。設計數據表tb_cache，關鍵字段定義如下：

Ndir：URL 的目錄層

FirstDir：URL的第一層目錄

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

LastAccess:同一URL上次被訪問到當前的請求總數

FileExtension：請求的URL文件的文件名后綴的代碼標識

Size：返回客戶端的字節

數據表的每一行數據存儲代理服務器的一個事務，但Web文檔可被緩存必須是HTTP協議、是GET請求、請求中沒有“?”和HTTP響應碼是200，這些數據需要在模型中進行過濾清洗，把相應事務導入數據庫中。

3.2 構建基于決策樹分類的模擬器

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

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

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

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

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

3.2.1 NextAccess的離散化

在決策樹模型設計中，將NextAccess作為分類的目標，利用決策樹作為一個分類器，預測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)];

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

3.2.2 權重分配

替換策略的權重分配如下：

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

S3替換策略的權重分配如下：

Ws3(Ei)=j+a(c)*AvgDsize(s)/Ei.size;c∈{0,1,2,3};c為文檔Ei根據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 緩存模型試驗結果

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

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

[1]鄧磊，陳志剛，黃鍵，等.基于 AOP的智能 Web緩存框架[J]. 計算機工程，2008，34(22)：283-285.

[2]韓向春，田玉根.基于預測的Web緩存替換算法[J].計算機工程與設計，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，FL，USA：IEEE Computer Society，2006.