基于頻繁的Ｍａｒｋｏｖ鏈預測模型

摘 要：預取技術通過在用戶瀏覽當前網頁的時間內提前取回其將來最有可能請求的網頁來減少實際感知的獲取網頁的時間。傳統的Markov鏈模型是一種簡單而有效的預測模型，但同時存在預測準確率偏低，存儲復雜度偏高等缺點。通過提出一種算法來減小存儲空間，最后通過證明能有效減小存儲空間。

關鍵詞：預取； 馬爾可夫模型； 頻繁模式樹

中圖分類號：TP301.6文獻標志碼：A

文章編號：1001—3695(2007)03—0041—03

0 引言

隨著Internet的發展，World Wide Web以其向用戶提供網頁信息的豐富性和交互性而成為Internet上的主要應用。然而由于帶寬的不足，用戶需要忍受長期的等待，尤其是一些撥號上網的用戶。出現了WWW就是“World Wide Wait”的說法。

為了解決這些問題，人們提出了多種技術方案，其中最主要的有網絡緩存和網絡預取技術兩種。網絡緩存技術通過在本地緩存用戶最近訪問過的網頁，能夠有效地減少網絡延遲和對帶寬的要求，已經成為當前網絡結構中的一個重要組成部分。但是由于現在網頁更新的速度比較快，能從本地緩存中獲得新網頁的概率一般比較小；另外，如果用戶要訪問以前從未請求過的網頁，緩存技術便無能為力。

如果能夠預測出用戶將來可能的訪問請求，并在用戶實際請求前將這些網頁取回并放入本地緩存，就可以較好地解決網絡緩存技術存在的上述兩個問題。這種技術就是網頁預取技術區別于被動緩存，網頁預取技術通過分析用戶訪問歷史記錄，主動預測用戶可能瀏覽的頁面，預先取出并存放在緩沖區中，以備用戶訪問，從而減少用戶的訪問延時。實際應用證明，網頁預取技術配以一定的流量平滑技術，能夠大幅度減少用戶的訪問延時，從而提高了WWW服務質量，同時能夠改進服務的QoS[1]。預取需要解決三個關鍵問題：①如何盡可能多地發現用戶將來可能的訪問請求；②如何從這些請求中準確地預測用戶的實際請求；③如何讓這種預測方法在大多數情況下均能夠使用。現有的預取技術主要分為客戶端和服務器端[2]預取技術。

Markov模型是Andrei A.Markov提出來的，在目前用途十分廣泛的一個統計模型。在其基礎上，又發展了各種不同的Markov模型。Zukerman等人[3]提出的Markov鏈用戶瀏覽預測模型是一種簡單而有效的模型，它將用戶的瀏覽過程抽象為一個特殊的隨機過程——齊次離散Markov鏈，用轉移概率矩陣描述用戶的瀏覽特征，并基于此對用戶的瀏覽進行預測。之后，Boerges等人采用了多階轉移矩陣，進一步提高了模型的預測準確率。在此基礎上，Sarukkai建立了一個實驗系統。通過在EPA服務器日志文件上的實驗表明，基于Markov鏈模型對用戶的瀏覽過程進行預測，其準確率可以達到70%左右[4]。然而，該模型在以下兩方面的不足有待改進：

（1）用戶在Internet上的瀏覽過程是一個受瀏覽目的、興趣愛好、文化背景等多方面影響的較為復雜的過程。而由于用戶的這些差異，其瀏覽過程往往表現出不同的個性差異。但Markov鏈模型采取一個單一的過程描述所有的用戶，明顯過于簡單，可能會出現較大的誤差。

（2）該模型的存儲空間主要用于保存狀態轉移概率矩陣，所以其存儲空間的復雜度是網頁數目n的平方，即為O（n2）。由于n的值一般都比較大，存儲復雜率較高。同時為了提高Web預取的命中率，常常聯合多個Markov鏈模型，即用到了多階狀態轉移矩陣，使得存儲復雜率成倍提高。

現有的Markov鏈及其改進，無論是Deshpande and Karypis于2001年提出的k階Markov鏈模型，還是Cadez和Sen于2003年提出的混合Markov鏈模型，都是針對第一點不足的，所以本文擬從第二點不足進行改進。

1 Web預處理

1.1 數據清洗(Data Cleaning)

數據清洗是指刪除Web服務器日志中與挖掘算法無關的數據項。由于Web使用挖掘主要是對用戶瀏覽行為的研究，只有利用準確描述用戶瀏覽行為的數據進行挖掘，才能發現正確的規則和模式。

數據清洗有兩種類型：①不需要對站點拓撲結構進行了解。例如，清除掉狀態代碼為“4XX”的客戶端錯誤和“5XX”的服務器錯誤記錄。②數據清洗工作需要了解站點的拓撲結構。例如用戶在瀏覽頁面時，若頁面中包含有圖像、聲音等特殊元素文件，那么由于HTTP協議對與每個Web服務器文件提出的訪問請求都要建立一個單獨的連接，除了對該頁面的訪問記錄外，對這些特殊元素文件的訪問也會作為單獨的記錄添加在Web日志中。通常認為，在大多數情況下，由于這些文件并不是用戶直接訪問的，它們只是根據用戶請求訪問的頁面中的HTML標記，隨著該頁面一起自動下載并被記錄在日志中的，可以認為它們與用戶的瀏覽行為無關，需要將它們從原始日志中清除。

1.2 用戶識別(User Identification)

由于本地緩存和代理服務器的存在，給準確地識別用戶帶來了一定的困難。盡管如此，本文仍然能夠給出一些假設，用來幫助識別用戶。

假設1 如果訪問日志中的兩條記錄的IP地址相同，但是代理日志表明用戶所使用的操作系統或瀏覽器的類型不同，那么應該認為這兩條日志記錄是來自于不同的用戶發出的頁面訪問請求。

假設2 如果訪問日志中的兩條記錄的IP地址相同，但是用戶當前請求的頁面同用戶已瀏覽的頁面之間沒有鏈接關系，則認為這兩條日志記錄是由不同的用戶發出的請求。

1.3 會話識別(Session Identification)

會話構造是Web使用挖掘預處理工作中最重要的一個環節。它相當于數據挖掘預處理階段中的數據轉換和特征提取階段。會話構造具有一定的針對性。對于不同的數據挖掘應用，會話構造采用的策略和方法不同。

會話識別最簡單的方法是利用超時（一般可設為30 min）。如果兩個頁面請求時間的差值超過一定的界限，就認為用戶開始了一個新的會話。

1.4 路徑補充(Path Completion)

由于本地緩存和代理服務器緩存的存在，使得服務器的日志會遺漏一些重要的頁面請求。路徑完善的任務就是將這些遺漏的請求補充到用戶會話中，解決的方法類似于用戶識別中的方法。

如果當前請求的頁與用戶上一次請求的頁之間沒有超文本鏈接，那么用戶很可能使用了瀏覽器上的“BACK”按鈕調用緩存在本機中的頁面。檢查引用日志確定當前請求來自哪一頁，如果用戶的歷史訪問記錄上有多個頁面均包含與當前請求頁的鏈接，則將請求時間最接近當前請求頁的頁面作為當前請求的來源。若引用日志不完整，可以使用站點的拓撲結構代替。通過這種方法將遺漏的頁面請求添加到用戶的會話文件中。

2 Markov鏈模型簡介

Markov鏈是一個典型的無后效性隨機過程，也就是說模型在時刻t的狀態只與它的前一個時刻t-1的狀態條件相關，與以前的狀態條件獨立，即(X[t]|X[t-1]，X[t-2]，…，X[0])=P(X[t]|X[t-1])。因此，一個Markov過程可以由它的轉移矩陣和初始分布向量確定。其中轉移矩陣集中描述了該Markov鏈模型的動態特征。該模型的轉移概率矩陣用A表示，初始分布向量用B表示，則

3 改進Markov的存儲復雜度

低階的Markov模型存在預取命中率偏低的情況，而高階Markov預測模型狀態隨著階數的增長而劇烈增長。在下面的部分，本文通過利用一個樹型結構來降低Markov模型的存儲復雜度。

一個頻繁訪問模式樹的結構：root是一個標為“1”的根節點，root以下是作為根節點的孩子項目前綴子樹集合，以及項目頭表組成；樹中的每一節點包含四個域url_id、count、node_link和node_next。其中url_id為url的標記(唯一標志一個url)，count為該父節點到達該節點的路徑的數目，url_link指向樹中具有相同的url_id的下一個節點，當下一個節點不存在時，node_link為1，node_next指向樹中其子節點；項目頭表的每一表項包含三個域：url_id、count、head of node。url_id與樹中的定義相同；count為樹中所有相同url_id之和；head of node指向樹中具有相同url_id值的首節點的指針。

3.1 建立訪問樹

為了簡便起見，本文以樹中當前頁面的count值表示父節點到當前節點的狀態轉移概率。

首先需要建立訪問樹，其算法如下：

設用戶會話集為S，其中的一個會話為s_i。

算法 pattern(tree，p)，構造用戶訪問模式樹

為了便于頻繁模式樹的生成和遍歷模式樹，按照頁面訪問的次數升序創建一個項目頭表，并且每個項均有一個節點鏈指向它在樹中出現的位置。

3.2 建立頻繁訪問模式樹

算法 requent(tree，α)，通過調用此算法挖掘用戶訪問頻繁模式

3.3 利用頻繁訪問模式樹進行預取的驗證

算法 frequent(tree)，通過調用此算法驗證用戶的預取訪問

輸入:頻繁訪問模式樹tree，用戶的測試會話集，用戶會話當前訪問節點為x_i，K階Markov鏈的k值

輸出:驗證用戶的下一步輸出

4 試驗

為了驗證本方法在降低存儲復雜度的有效性，本文以數據挖掘研究院的日志作為挖掘對象，經過預處理共得到3 280個用戶會話，取其中的2120個作為用戶訓練集，1160個作為測試集。

這里精確度即為預取命中數與用戶預取總數的比值。

從表1中可以看到，用戶的Min_sup對前綴基的個數影響很大，而前綴基的個數的減少對精確度的影響很小，這是因為用戶的訓練集中很多的狀態支持度很低，可以當做噪聲處理。

5 結束語

隨著WWW技術的廣泛應用，Web日志中的內容越來越成為數據挖掘中的關注的重點。Markov鏈作為一種有效的Web預取模型，存在著存儲復雜率較高的缺點，而利用頻繁訪問模式樹存儲Markov鏈，能夠大幅減小存儲空間，改進了Markov鏈的存儲空間，通過證明是一種有效的方法。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。