Ｗｅｂ日志挖掘中的數據預處理研究

摘要：Web日志信息的預處理是Web日志挖掘任務中的重要階段，是整個Web日志挖掘過程的基礎和實施有效挖掘算法的前提，在Web日志挖掘中起著重要的作用，也是工作量較大的一部分。數據預處理的基本技術，包括數據清理、數據集成和轉換、數據歸約等。本文介紹了數據預處理中涉及到的數據清理、用戶識別、會話識別、路徑補充、事務識別等過程，并提出了一種路徑補充算法。

關鍵詞：Web日志；數據預處理；用戶會話；路徑補充；事務識別

中圖分類號：TP311文獻標志碼：A 文章編號：1009-3044(2008)14-20789-03

1 引言

存在不完整、含噪聲的和不一致的數據是大型的、現實世界數據庫或者數據倉庫的共同特點。不完整的數據的出現可能有多種原因，如收集不全，或者感興趣的數據很難得到等。數據含有噪聲（具有不正確的屬性值）可能由于收集數據的設備出現故障，或者是數據傳輸中出現錯誤。在含有噪聲的數據上進行數據挖掘可能得到錯誤的結果。因而在進行數據挖掘之前我們必須對數據進行預處理，以消除數據的不完整性、噪聲和不一致性。數據預處理的過程見圖1。

2 數據預處理步驟

2.1 數據清理

數據清理過程中試圖填充空缺的值，識別孤立點、清除噪聲，并糾正數據中的不一致性。由于Web服務器紀錄了很多用戶不關心的信息。數據清理階段就是要刪除Web日志中與挖掘目的不相關的數據和記錄，為后面的用戶會話識別和事務識別做好準備工作。

由于Web日志挖掘主要是對Web用戶使用行為的研究，所以只有利用準確描述用戶瀏覽行為的數據進行挖掘，才能發現正確的規則和模式。因為用戶在發出html的請求時，會發出對包含在頁面中的圖片及音樂等次要元素的請求，而Web服務器都會為此做記錄，所以數據清理階段通過檢查URL的后綴刪除不相關的數據，把后綴名為GIF、JPEG、JPG、JPEG、JPG、SWF、CSS、JS和MAP的請求項刪除。值得注意的是，當服務器對用戶發出的請求響應失敗時，Web日志同樣會記錄這種情況，但這對Web日志挖掘沒有意義，可以采取在數據清理過程中通過檢測日志中的狀態碼來刪除服務器對請求失敗的記錄。

2.2 用戶識別

用戶識別的目的是要分辨出每個訪問網站的用戶，但由于本地緩存、防火墻還有代理服務器的存在使得過程變得復雜。解決的辦法可以通過對用戶行為進行跟蹤，一般最常使用的技術是基于日志/站點的方法，并輔助一些啟發式規則來識別用戶，概括起來就是：若沒有證據表明是不同的用戶，就認為是同一用戶。最常用的一個規則是：若訪問用戶的IP地址相同，但是相應的代理日志中如果顯示訪問用戶的操作系統不同或者是瀏覽器類型不同，則認為他們來自不同的用戶。另一個規則是：將用戶的訪問日志、引用日志和站點的拓撲結構結合起來，構建出用戶的瀏覽路徑，如果當前的請求頁面同用戶已瀏覽的頁面之間沒有超鏈接關系，那么就認為存在相同IP地址的不同用戶。

2.3 會話識別

一個會話是指用戶對服務器進行訪問時一串順序的頁面請求，即用戶連續訪問的具有一定目的性的頁面序列。用戶會話識別就是將用戶的多條訪問日志記錄分為單個的會話。

目前用戶會話的表示方法主要有兩種方法：一種是將會話簡單地表示成訪問頁面的集合[1，2]，其優點是算法思想簡單、直觀。另一種方法在集合表示的基礎上，加上了用戶訪問的時間信息，將用戶會話看成是訪問頁面所形成的一個頁面序列[3，4]。

定義1 用戶會話S是一個二元組，其中userid是用戶標識，RS是用戶在一段時間內請求的Web頁面的集合。

RS包含了用戶請求的頁面的標識符Pid和請求的時間t，用戶會話S可以表示為如下的元組。

S= (1)

其中tk表示頁面Pidk的訪問時間。通過用戶識別，可以得到關于用戶的訪問web頁面的一個序列，然后可以通過設定超時的方法識別用戶會話。這里有兩種方法[5]，一種方法是設定整個用戶會話時間間隔T，使得tk－t1≤T。另一種方法就是縮小范圍，設定相鄰請求之間的超時時間，如果兩個頁面請求時間的差值超過設定的界限值就認為用戶開始了一個新的會話。(1)式中的用戶會話要滿足下面的條件（其中T為設定的超時界限值）：

ti－ti-1≤T，1

現在常采用第二種方法來進行超時設定。基于以上的思想，可以用如下偽代碼算法過程來識別用戶會話：

輸入：經過數據清理后的日志集合Cleaned_Data，會話的超時設定值T。

輸出：經過識別得到的會話集合Recognized_Session，在算法開始時將Session集合初始化為空。

算法如下：

RecognizeProgress (DataQueue)

{Createlist();//初始化一個新隊列用來存放會話識別后的頁面序列

If (DataQueue.Isempty) return;//如果日志記錄隊列為空，則退出

else {Session.add(DataQueue.Front); DataQueue.Dequeue;}

//取得隊列中的第一個元素加入到識別后的集合中，并從隊列清除之

//尋找DataQueue隊列中剩下的元素

If userid與新隊列的當前指針所指結點的userid相同且Time與該結點的Time相差小于T

{session.Add (Data);

DataQueue.Dequeue;

} //將符合條件的頁面結點加入集合中，并刪除該節點更新隊列。

//比較完DataQueue中所有的元素后，按照頁面的訪問時間進行排序

session.sortByVisitOrder ();

If DataQueue.Isempty return;/ /如果隊列為空，則退出

else //否則遞歸訪問DataQueue隊列

RecognizeProgress(DataQueue)；

以上算法基于遞歸的思想，將經過清理后的日志記錄數據集合中符合同一用戶會話條件的頁面序列取出來放入一個新的集合中，并按照訪問頁面的時間進行排序。該算法簡單，實現起來相對容易。

2.4 路徑補充

路徑補充(path completion)是對識別出的用戶會話進行優化的步驟，使得其更適合描述用戶的瀏覽請求。由于本地緩存和代理服務器的存在，使得服務器的日志會遺漏一些重要的頁面請求。路徑補充就是將這些一路的請求補充到用戶會話中去。解決的方法往往依賴于網站的拓撲結構圖。

根據網站的拓撲結構分析，網站可以用樹形結構來表示。網站有一個主頁，用戶可以通過主頁到達任何一個一級欄目首頁、二級欄目首頁以及最終內容頁面。考慮到每個頁面所擁有的子鏈接數目不同，頁面可以采用非結構化的存儲方式。

定義每個頁面節點的結構表示為：node=<節點編號，父節點集合，子節點集合>。

node=，如果是網站首頁，則node的父節點集合為空。如果是網站的尾頁即葉節點，則node的子節點集合為空。

基于站點的拓撲結構，這里提出一種路徑搜索算法，其基本思想是若當前頁與下一頁有鏈接關系時，說明用戶可能是通過當前頁的鏈接到達下一頁。若無鏈接，則返回當前頁的引用頁。若存在兩個或兩個以上的引用頁，可根據請求時間最接近于當前頁的那個鏈接作為考慮對象，并判斷引用頁與下一頁有無鏈接關系。循環執行，最后能得到用戶的訪問路徑。

此處定義一個字符串數組path[m]存儲每個用戶的訪問路徑。首先初始化path[m]為空。算法描述：

輸入：經過數據清洗、用戶識別、會話識別后的web日志集合，網站的拓撲結構。

輸出：用戶完整的訪問路徑。

算法偽碼如下：

for(i=1;i<=n ; i++) //每位用戶具有n次會話

{{If T>2 //如果會話集合頁面數大于2頁則執行下面操作

{node1=FirstPage(); //取得用戶路徑中的第一頁

node2=SecondPage(); //取得用戶路徑中的第二頁

s=0

While (S<=Total) {

// S為頁面計數變量，Total為一次會話中用戶瀏覽的總頁面數

If (node1和node2之間有鏈接) //查找網絡拓撲物理結構存儲

{Path[i].Add(node1); //將Node1加入路徑數組中

node1=node2; node2=NextPage();//取下一頁

S++

}

else //node1和node2之間沒有鏈接

{//向前搜索獲得node1的父節點

node1=node1.parent; //取node1的父節點作為回退頁

//如果碰到多個父節點，取請求時間最接近node1的節點

path[i].Add(node1); //將node1的父節點加入路徑}

}}}

算法分析：其時間復雜度為O(m×t) ， 空間復雜度為O(m)。由于算法中采用了數組來存儲路徑補充后的頁面序列，而路徑補充后的頁面序列的長度不能預先得到，所以也可以用隊列來實現上述算法。在用戶會話識別的基礎上應用上述路徑補充算法能夠有效的完成對用戶訪問路徑的補充。

2.5 事務識別

用戶事務識別主要是根據Web日志挖掘中的模式發現的知識挖掘特性來確定與知識相對應的事務定義，因此不同的會話分析可以確定不同的事務。

事務識別最常用的是最大向前參考模型，方法如下：假設用戶訪問過程中只在改變訪問主題時才會訪問前面訪問過的頁面以跳轉到另外的頁面。那么，確定用戶訪問事務是指用戶一直前向訪問，直到向后返回訪問才算是開始一個新的訪問事務。所謂前向，指的是某頁面不在目前的訪問事務頁面集里。后向，指的是某頁面在目前的訪問事務頁面集里。最大向前路徑(MFP)是在用戶會話中第一頁到回退的前一頁組成的路徑。例如：一個用戶會話中請求的頁面順序是A－B－C－A－D－E ，對應的MFP為A－B－C和A－D－E。這種方法的基本模型是MFP中的最后一頁是內容頁，而在此之前的頁面都是導航頁。

3 結束語

Web日志數據準確性是Web日志挖掘中重要的前提和基礎。只有準確的數據才能正確地反映用戶的意圖，才能保證分析沿著正確的方向進行。高質量的Web日志挖掘必須依賴高質量的數據。有效的利用web日志可以挖掘出潛在的信息，有助于網站經營者為用戶提供個性化服務。目前，如何提高與改進Web日志挖掘預處理技術，確保輸入Web日志挖掘的數據正確高效已成為一項重要課題和研究方向。

本文作者創新點：在路徑補充階段提出了一種算法，此算法在一定程度上提高了數據預處理階段的工作效率，節省了系統開銷，為web日志挖掘的下一階段工作模式發現和模式分析做了充分的準備。

參考文獻：

[1] Pei， J.， Han， J.， et al.. Mining access patterns efficiently from Web logs[C].PAKDD’00， Kyoto， Japan2000， Liping Sun， Xiuzhen Zhang. Efficient Frequent Pattern Mining on Web Logs[C]. APWeb 2004. pp. 533–542.

[2] Liping Sun， Xiuzhen Zhang. Efficient Frequent Pattern Mining on Web Logs[C].APWeb 2004. pp. 533–542.

[3] Ezeife，Yi Lu. Mining Web Log Sequential Patterns with Position Coded Pre-Order Linked WAP-Tree [J]. Data Mining and Knowledge Discovery. 2005， 10， 5-38.

[4] Maged El-Sayed， Carolina Ruiz， Elke A. Rundensteiner: FS-Miner: efficient and incremental mining of frequent sequence patterns in web logs. WIDM 2004:128-135.

[5] Robert Cooley， Bamshad Mobasher， Jaideep Srivastava: Data Preparation for Mining World Wide Web Browsing Patterns [J]. Knowledge and Information System. 1(1): 5-32 (1999).

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