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

關(guān)鍵詞：Web日志；數(shù)據(jù)預(yù)處理；用戶會(huì)話；路徑補(bǔ)充；事務(wù)識(shí)別

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1009-3044(2008)14-20789-03

1 引言

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

2 數(shù)據(jù)預(yù)處理步驟

2.1 數(shù)據(jù)清理

數(shù)據(jù)清理過程中試圖填充空缺的值，識(shí)別孤立點(diǎn)、清除噪聲，并糾正數(shù)據(jù)中的不一致性。由于Web服務(wù)器紀(jì)錄了很多用戶不關(guān)心的信息。數(shù)據(jù)清理階段就是要?jiǎng)h除Web日志中與挖掘目的不相關(guān)的數(shù)據(jù)和記錄，為后面的用戶會(huì)話識(shí)別和事務(wù)識(shí)別做好準(zhǔn)備工作。

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

2.2 用戶識(shí)別

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

2.3 會(huì)話識(shí)別

一個(gè)會(huì)話是指用戶對服務(wù)器進(jìn)行訪問時(shí)一串順序的頁面請求，即用戶連續(xù)訪問的具有一定目的性的頁面序列。用戶會(huì)話識(shí)別就是將用戶的多條訪問日志記錄分為單個(gè)的會(huì)話。

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

定義1 用戶會(huì)話S是一個(gè)二元組，其中userid是用戶標(biāo)識(shí)，RS是用戶在一段時(shí)間內(nèi)請求的Web頁面的集合。

RS包含了用戶請求的頁面的標(biāo)識(shí)符Pid和請求的時(shí)間t，用戶會(huì)話S可以表示為如下的元組。

S= (1)

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

ti－ti-1≤T，1

現(xiàn)在常采用第二種方法來進(jìn)行超時(shí)設(shè)定?；谝陨系乃枷?，可以用如下偽代碼算法過程來識(shí)別用戶會(huì)話：

輸入：經(jīng)過數(shù)據(jù)清理后的日志集合Cleaned_Data，會(huì)話的超時(shí)設(shè)定值T。

輸出：經(jīng)過識(shí)別得到的會(huì)話集合Recognized_Session，在算法開始時(shí)將Session集合初始化為空。

算法如下：

RecognizeProgress (DataQueue)

{Createlist();//初始化一個(gè)新隊(duì)列用來存放會(huì)話識(shí)別后的頁面序列

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

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

//取得隊(duì)列中的第一個(gè)元素加入到識(shí)別后的集合中，并從隊(duì)列清除之

//尋找DataQueue隊(duì)列中剩下的元素

If userid與新隊(duì)列的當(dāng)前指針?biāo)附Y(jié)點(diǎn)的userid相同且Time與該結(jié)點(diǎn)的Time相差小于T

{session.Add (Data);

DataQueue.Dequeue;

} //將符合條件的頁面結(jié)點(diǎn)加入集合中，并刪除該節(jié)點(diǎn)更新隊(duì)列。

//比較完DataQueue中所有的元素后，按照頁面的訪問時(shí)間進(jìn)行排序

session.sortByVisitOrder ();

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

else //否則遞歸訪問DataQueue隊(duì)列

RecognizeProgress(DataQueue)；

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

2.4 路徑補(bǔ)充

路徑補(bǔ)充(path completion)是對識(shí)別出的用戶會(huì)話進(jìn)行優(yōu)化的步驟，使得其更適合描述用戶的瀏覽請求。由于本地緩存和代理服務(wù)器的存在，使得服務(wù)器的日志會(huì)遺漏一些重要的頁面請求。路徑補(bǔ)充就是將這些一路的請求補(bǔ)充到用戶會(huì)話中去。解決的方法往往依賴于網(wǎng)站的拓?fù)浣Y(jié)構(gòu)圖。

根據(jù)網(wǎng)站的拓?fù)浣Y(jié)構(gòu)分析，網(wǎng)站可以用樹形結(jié)構(gòu)來表示。網(wǎng)站有一個(gè)主頁，用戶可以通過主頁到達(dá)任何一個(gè)一級欄目首頁、二級欄目首頁以及最終內(nèi)容頁面。考慮到每個(gè)頁面所擁有的子鏈接數(shù)目不同，頁面可以采用非結(jié)構(gòu)化的存儲(chǔ)方式。

定義每個(gè)頁面節(jié)點(diǎn)的結(jié)構(gòu)表示為：node=<節(jié)點(diǎn)編號(hào)，父節(jié)點(diǎn)集合，子節(jié)點(diǎn)集合>。

node=，如果是網(wǎng)站首頁，則node的父節(jié)點(diǎn)集合為空。如果是網(wǎng)站的尾頁即葉節(jié)點(diǎn)，則node的子節(jié)點(diǎn)集合為空。

基于站點(diǎn)的拓?fù)浣Y(jié)構(gòu)，這里提出一種路徑搜索算法，其基本思想是若當(dāng)前頁與下一頁有鏈接關(guān)系時(shí)，說明用戶可能是通過當(dāng)前頁的鏈接到達(dá)下一頁。若無鏈接，則返回當(dāng)前頁的引用頁。若存在兩個(gè)或兩個(gè)以上的引用頁，可根據(jù)請求時(shí)間最接近于當(dāng)前頁的那個(gè)鏈接作為考慮對象，并判斷引用頁與下一頁有無鏈接關(guān)系。循環(huán)執(zhí)行，最后能得到用戶的訪問路徑。

此處定義一個(gè)字符串?dāng)?shù)組path[m]存儲(chǔ)每個(gè)用戶的訪問路徑。首先初始化path[m]為空。算法描述：

輸入：經(jīng)過數(shù)據(jù)清洗、用戶識(shí)別、會(huì)話識(shí)別后的web日志集合，網(wǎng)站的拓?fù)浣Y(jié)構(gòu)。

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

算法偽碼如下：

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

{{If T>2 //如果會(huì)話集合頁面數(shù)大于2頁則執(zhí)行下面操作

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

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

s=0

While (S<=Total) {

// S為頁面計(jì)數(shù)變量，Total為一次會(huì)話中用戶瀏覽的總頁面數(shù)

If (node1和node2之間有鏈接) //查找網(wǎng)絡(luò)拓?fù)湮锢斫Y(jié)構(gòu)存儲(chǔ)

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

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

S++

}

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

{//向前搜索獲得node1的父節(jié)點(diǎn)

node1=node1.parent; //取node1的父節(jié)點(diǎn)作為回退頁

//如果碰到多個(gè)父節(jié)點(diǎn)，取請求時(shí)間最接近node1的節(jié)點(diǎn)

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

}}}

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

2.5 事務(wù)識(shí)別

用戶事務(wù)識(shí)別主要是根據(jù)Web日志挖掘中的模式發(fā)現(xiàn)的知識(shí)挖掘特性來確定與知識(shí)相對應(yīng)的事務(wù)定義，因此不同的會(huì)話分析可以確定不同的事務(wù)。

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

3 結(jié)束語

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

本文作者創(chuàng)新點(diǎn)：在路徑補(bǔ)充階段提出了一種算法，此算法在一定程度上提高了數(shù)據(jù)預(yù)處理階段的工作效率，節(jié)省了系統(tǒng)開銷，為web日志挖掘的下一階段工作模式發(fā)現(xiàn)和模式分析做了充分的準(zhǔn)備。

參考文獻(xiàn)：

[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).

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