Ｗｅｂ使用挖掘技術的分析與研究

摘要：首先給出Web使用挖掘的定義和完整模型框架；然后對Web使用挖掘中主要步驟的最新研究進展狀況作了詳細的闡述和分析，其中包括數據采集、數據預處理、模式發現和模式分析；最后對未來的研究重點進行了展望。

關鍵詞：Web挖掘; Web使用挖掘;數據預處理; 模式發現; 模式分析

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2008)01－0029－04

Web上的數據正以每天新增一百萬個頁面的速度增長，頁面數目已超過10億[1]。如何從這些位于分布式環境中的海量數據挖掘和抽取潛在的、用戶感興趣的有用模式和隱藏的知識成為一個重要而非常有意義的課題。Web挖掘技術正是以此為目標應運而生的。Web挖掘技術將傳統的數據挖掘技術與Web技術結合起來[2~4]，并綜合運用了統計學、計算機網絡、數據庫與數據倉庫、可視化等眾多領域的技術。

定義1Web挖掘是指從大量Web文檔結構和使用的集合C 中發現隱含的模式p。如果將C看做輸入，p看做輸出，那么Web挖掘的過程就是從輸入到輸出的一個映射： ξ: C → p。

一般地，Web挖掘分為三類[5]：Web內容挖掘、Web結構挖掘和Web使用挖掘。目前國際上對Web使用挖掘的研究比較多。WUM[6~8]是指能夠從服務器、瀏覽器端的日志記錄和用戶的個人信息中自動發現和預測隱藏在數據中的模式信息——用戶群體的共同行為、興趣以及個人用戶的檢索偏好、習慣等。

1Web使用挖掘的基本框架

圖1給出了一個WUM比較完善的系統框架模型圖。從圖中可以看出它包含了數據采集、數據預處理、模式發現和模式分析四個主要的階段。

1．1數據采集

在WUM中，由于HTTP的無狀態連接特性而很難得到準確的用戶瀏覽信息。Jaideep Srivastava等人[9]和Cyrus Shahabi等人[10]提出從Web的結構出發，多層次地進行Web 站點信息采集。

在WUM中，使用數據的采集主要可以分為以下幾種形式：

a）服務器端的數據采集。主要包括從Web 服務器日志中收集和從網絡監視器中收集。Web服務器日志文件是執行WUM的重要數據來源。該日志文件記錄了用戶訪問站點的數據。每當站點上的網頁被訪問一次，Web服務器就在日志文件中增加一條相應的記錄。如圖2 所示的就是一條典型的 ECLF[11](extended common log file，擴展日志格式)的記錄和提取出的相關信息。當然，Web服務器日志文件還可以以其他的格式存儲，如CLF（common log file，通用日志格式) 或其他日志格式有NCSA、CERN、APACHE[12]。這些記錄數據反映了多個用戶(可能同時)對Web站點(單站點)的(存取)訪問行為。由于Web環境中存在多級別的緩存（如用戶的本地緩存和代理服務器緩存）和防火墻， 用戶瀏覽緩存的頁面不在服務器端日志上記錄， 防火墻使得不同的用戶請求在Web服務器的日志中記錄的均是防火墻的IP地址， 所以日志中的網站使用數據并不完全可靠(未采集到所有訪問頁面、采集時間不夠準確、瀏覽用戶的確定不夠準確)。用服務器端日志數據進行WUM是不完全可靠的，還必須依靠其他使用數據收集方法。

221.202.41.83\"[25/Dec/2003:05:00:00 +0800]\"

\"GET http://news.tom.com/piclib/419_11.html\"20015763\"http://news.tom.com/pic/\" \"Mozilla/4.0(compatible，MSIE 5.0; Windows 98; DigExt)\"

IP地址221.202.41.83

訪問時間25/Dec/2003:05:00:00

訪問頁面http://news.tom.com/piclib/419_11.html

Web服務器對于該請求返回的狀態信息200

返回給客戶端的內容大小15 763 Byte

該請求的引用地址http://news.tom.com/pic/

用戶客戶端類型Mozilla/4.0(compatible；MSIE 5.0;Windows 98;DigExt)

圖2Web服務器ECLF記錄格式及提取的信息

b)應用服務器端的數據采集。這種數據采集方法可以利用應用服務器上的應用程序（如CGI程序）來記錄用戶的個人信息；同時也可以通過自定義的格式動態記錄用戶的瀏覽信息。每次用戶進行訪問時先進行身份驗證，然后由CGI程序記錄用戶全部的瀏覽過程。這種應用服務器級的采集方法與Web服務器級的數據采集方法相比，在用戶確定方面的準確性高，但是大量的應用程序會使系統的效率很低。

c）客戶端的數據采集。客戶端的瀏覽路徑采集比服務器端的采集更具優越性。因為它是建立在用戶的行為源上的，可以準確地捕捉用戶的行為。用戶的瀏覽路徑和瀏覽時間的測量可以很精確，但是它需要用戶的許可，有可能會侵犯用戶的隱私。客戶端的用戶瀏覽路徑采集包括Java Applet和Java Script以及Plug in、網頁跟蹤幀和修改瀏覽器等技術。

d)代理服務器端的數據采集。代理服務器相當于一個在客戶端瀏覽器和Web服務器之間提供了緩存功能的中介服務器，主要用于減少用戶下載網頁的時間以及服務器與客戶機之間的網絡流量[13]。從代理服務器可以得到從多個用戶到Web服務器的訪問記錄(無須用戶許可)。若代理訪問站點網頁是通過Web應用程序動態生成的， 對于用戶的每次請求， 代理需從Web服務器取得數據。該收集方法不能準確地確定瀏覽用戶， 對訪問頁面的采集不夠全面， 采集時間不準確。

Web使用挖掘數據采集技術匯總如表1所示。

1．2數據預處理

WUM中對數據進行預處理。其目標是將包含在多種數據源中的信息轉換為適合數據挖掘和模式發現所必需的數據抽象概念， 然后在事務數據庫上實施挖掘算法， 以期最終獲得有價值的規律。因為預處理的結果直接影響到挖掘算法產生的規則和模式，可以說預處理過程是WUM質量保證的關鍵。

通常WUM的預處理過程[13~15]包括數據清理、用戶識別、會話識別、路徑完善等幾個步驟，如圖3所示。



1）數據清理（data cleaning）

數據清理解決了臟數據（dirty data）的問題，消解數據中的不一致性，并將多個數據源中的數據統一成一個數據存儲。比如，將不同服務器上格式和描述都不同的原始數據規范化，去除日志文件中包含gif、jpeg、gif、map的文件名的項目。可以預先定義一個缺省的規則庫（如算法1）來幫助刪除記錄。另外，還可以預先將網站分為一般網站、圖片網站和音頻網站等，分別建立對應的規則庫；然后按照該類網站的規則庫進行數據清理。

算法1

a)選擇記錄屬性。在Web日志中，選用屬性：A={IP，r.date，r.time，request，size，referer，agent}。

b)刪除無用記錄。建立一個刪除列表：DT＝{.GIF .JPEG .JPG .gif .jpeg .jpg .map .cgi}。凡是對后綴名在刪除列表中的文件的申請記錄均應刪除。

具體過程如下:

輸入: T1.log中的所有記錄集L;

輸出: 數據清理后的關系表T2.log; //T2.log表包含A中的字段

for all li∈L //依次處理L中的每條記錄

{ifT1請求的文件后綴名不在DT中

then選取T1中所有屬于A的字段值并存入T2.log中;}

2)用戶識別（user identification）

用戶識別是從日志中識別出每個訪問網站的用戶。最常被WUM工具使用的技術就是基于日志/站點的方法，并輔助一些啟發式規則幫助識別用戶。

啟發式規則的核心思想在于:a)不同的IP地址代表著不同的用戶；b)用戶的IP地址相同，但相應的代理日志表明用戶的瀏覽器類型或操作系統發生了改變，則認為代表著不同的用戶；c)用戶的IP地址相同，用戶使用的操作系統和瀏覽器也相同的情況下，則根據網站的頁面鏈接結構對用戶進行識別(如果用戶請求的某個頁面不能從已訪問的任何頁面到達，則認為這是一個新的用戶)。

要說明的一點是，這些僅是幫助識別用戶的啟發規則，并非使用了這些規則就能準確地識別出用戶。在用戶識別的過程中，還會產生一些問題。典型的有：

a)單IP地址/多服務器會話。Internet業務供應商(ISP)為用戶提供了許多用于上網的代理服務器，因此在同一時間段內可能有許多不同用戶通過同一代理服務器（單IP地址）存取同一網站。

b)多IP 地址/單服務器會話。一些ISP和私用工具會為來自不同用戶的每次請求隨機分配IP地址池中的某一個。在這種情況下， 一次單獨的服務器會話可能會有多個IP地址。

c)多IP 地址/單用戶。一個用戶從不同機器上網會在不同會話中使用不同地址， 這就使得追蹤同一用戶的重復訪問變得很困難。

d)多代理/單用戶。某用戶在同一機器上打開多個瀏覽器窗口，訪問Web站點的不同部分或打開不同的瀏覽器進行訪問，將產生單個用戶的多個服務器會話。

3）會話識別(session identification)在跨越時間區段較大的Web服務器日志中，用戶有可能多次訪問了該站點。會話識別的目的就是將用戶的訪問記錄分為單個會話。用戶會話S可以定義為

S＝〈UserId，{(Pid1，time1)，…，(Pidk，timek)}〉 （1）

令 RS＝{(Pid1，time1)，…，(Pidk，timek)}

S＝〈UserId， RS〉

其中：UserId是用戶標志；RS是用戶在一段時間內請求的Web頁面的集合，它包含用戶請求頁面的標志符Pid和請求時間time。

通常可以采用超時方法識別用戶會話，對于超時閾值的設定有兩種方法：a)設定整個用戶會話的超時時間，則式(1)中的用戶會話必定滿足下面的條件(其中T為預先設定的超時閾值):timek-time1≤T。b)設定相鄰請求之間的超時時間。如果兩頁間請求時間的差值超過一定的界限就認為用戶開始了一個新的會話，則式(1)中的用戶會話必定滿足下面的條件(其中T為預先設定的超時閾值): timei-timei-1≤T。其中1

超時閾值的設定直接影響Web日志數據預處理的結果輸出。設定不同的超時閾值就會產生不同的用戶會話文件，從而最終影響Web日志的挖掘結果。

4）事務識別（transaction identification）

事務識別是指將頁面訪問序列劃分為代表Web事務或用戶會話的邏輯單元。與用戶session識別不同的是，它以事務為單位，只包含與事務相關的頁面。事務識別方法中最簡單的莫過于時間窗口法，即定義一個時間長度。該時間片內用戶瀏覽的所有頁面均歸為一個事務。比較常用的則是最大向前參考法[16]。具體做法是，從用戶訪問的首頁開始，到第一個回退動作為止定義為一個事務；接下來的第一個向前動作引發下一事務，直到下個回退動作產生。周而復始，將用戶訪問頁面序列劃分為一個個事務。比如，一個用戶在一次瀏覽過程中請求了ABCBCDE 頁面，根據最大前向參考法，用戶訪問過的訪問服務器會話期間應該是ABC和BCDE。

5）路徑補充(path completion)

由于本地緩存和代理服務器緩存的存在或是通過post技術信息傳遞，使得服務器的日志會遺漏一些重要的頁面請求，這樣就會影響到模式發現的效率和精度。解決的方法類似于用戶識別中的方法，可以借助應用日志或站點拓撲結構推斷當前請求的頁面的鏈接來源，從而將遺漏的頁面請求添加到用戶的會話文件中。

1．3模式挖掘

在數據預處理完成后，Web使用數據的模式發現采用的算法如下：

a）統計分析。統計方法是從Web中提取有用信息最常用的一種技術。通過對session 文件的分析，可以對感興趣的信息進行統計。一般包括各種統計數據，如最頻繁訪問的N個頁面、每頁平均瀏覽時間和網址路徑平均訪問長度等，也可能涉及一些關于限制的錯誤分析，如統計非法IP、無效URL和未授權訪問等。

b）關聯規則。在Web使用挖掘中， 關聯規則主要用于發現用戶之間、頁面之間以及用戶瀏覽頁面和網上行為之間存在的潛在關系。最著名的關聯規則挖掘方法是R.Agrawal提出的Apriori算法。最近也有獨立Agrawal的頻集方法的工作[17]，以避免需要大量空間存儲中間結果和需要反復掃描數據庫而帶來的算法上的缺陷。無論哪種算法，關聯規則的發現都遵循兩個步驟：(a)迭代識別所有的頻繁項目集，要求頻繁項目集的支持率不低于用戶設定的最小支持度(具體見定義2)；(b)從頻繁項目集中構造可信度不低于用戶設定的最小置信度(具體見定義3)。

定義2支持度(support)是指交易集T中包含X和Y的交易數與交易數據庫D中所有的交易數之比：

c）序列模式。序列模式與關聯模式相仿，差別在于序列模式把數據間的關聯性與時間先后順序聯系起來，即不僅需要知道事件是否發生，而且需要確定事件發生的時間先后。可以把它看成是一種增加了時間屬性的特定關聯模型。

下列規則中，(a)是序列模式，(b)是關聯規則。比較(a)和(b）便不難發現，(a)考慮了訪問的先后順序，而(b)則沒有考慮時間因素。

（a）訪問頁面Pl和P3后有35%的用戶又訪問了頁面P5。

（b）訪問頁面P1和P3的用戶中有35%的用戶也訪問了頁面P5。

d)聚類。聚類是將數據點集合分成若干類或簇(cluster)，使得每個簇中的數據點之間最大程度地相似，而不同簇中的數據點最大程度地不同，從而發現數據集中有效的、新穎的、可以理解的數據模式分布。在WUM中，聚類技術是對符合某一訪問規律特征的用戶（頁面）進行用戶（頁面）特征挖掘。通常可以將用戶瀏覽頁面的總和視為數據空間，構造一個URL_UserID關聯矩陣Mm×n，如式(2)所示。

其中：hi， j是j客戶在一段時間內訪問第i個URL 的次數; 每一行向量M[1，j]表示所有客戶對URL“1”的訪問情況; 每一列向量M[i，1]表示客戶“1”對該商務站點中所有URL的訪問情況。因此可以這樣認為: 行向量既代表了站點的結構， 又蘊涵有客戶共同的訪問模式; 而列向量既反映了客戶類型， 也勾勒出了客戶的個性化訪問子圖。再使用一些度量方法（如Hamming距離)分別度量行向量和列向量的相似性， 就可以得到兩種類型的聚類，即使用聚類(用戶聚類) 和網頁聚類。用戶聚類主要是把具有相似特性(或瀏覽模式) 的用戶聚集在一組，這類知識對電子商務和為用戶提供個性化的服務特別有用；網頁聚類可以找出具有相關內容的網頁組，這對網上搜索引擎及提供上網幫助的應用特別有用。

e)分類。在WUM中，分類技術可以預先把頁面分到不同的類中。這樣在分析以往的訪問記錄得知某用戶以前經常訪問某一類的網頁之后，便可以將該類網頁中還沒有被該用戶訪問過的頁面推薦給用戶。這樣節省了用戶搜尋所需信息的時間，同時增強了網站的個性化服務意識。最為典型的決策樹學習系統是ID3，它采用自頂向下不回溯策略，能保證找到一個簡單的樹。算法C4.5和C5.0都是ID3的擴展，它們將分類領域從類別屬性擴展到數值型屬性。

f）路徑分析。使用路徑分析技術進行WUM時，從Web站點拓撲結構圖抽象而來的有向圖中挖掘出最頻繁的路徑訪問模式或大參引訪問序列。Chen 等人從原始日志數據中導出最大向前引用序列MFR的過程， 實際上就是在構造用戶的訪問子圖。路徑分析可以用來確定網站上最頻繁的訪問路徑， 從而調整站點的結構。例如可以得到類似如下的信息:

(a)訪問網站的用戶中有25%是從頁面B開始的；

(b)有15%的用戶訪問路徑為C→M→D→E。

針對（a），可以在頁面B上直接添加一些想給用戶直接傳達的信息，或者通過鏈接指向相應的頁面，從而提高該信息的點擊率；針對(b)，可知路徑C→M→D→E為頻繁訪問路徑，可以在這幾個頁面上添加其他超鏈接或者促銷信息，從而增加其他信息的訪問頻度。

1．4模式分析技術

挖掘出來的用戶行為模式(集合)，需要合適的工具和技術對其進行分析、解釋和可視化，從中篩選出有趣(有用)的模式，使之成為人們可以理解的知識；否則挖掘出來的模式將得不到很好的應用。具體包括：

a)可視化技術。與其他數據挖掘應用領域一樣，Web使用挖掘技術與可視化技術的結合還剛起步。Web使用挖掘領域內的可視化技術主要分為基于點和基于序列兩類。基于點的可視化技術適合顯示數據對象的各種統計值，如產品或頁面的訪問次數、頁面間轉移的頻率或者次數等；基于序列的可視化方法著重表現用戶行為的序列特征，用各種方法描繪用戶的訪問序列。

b)知識查詢技術。自動搜索相關的規則、模式以及其他知識，可以幫助分析用戶的目標，用智能的方式回答查詢。建立一個 MLDB(multiple layered database，多層數據庫)，用數據庫技術來管理Web的元數據(meta Web)是其中的一種方法[18]。目前研究人員已經在SQL語言的基礎上提出幾種適合在數據挖掘過程中使用的查詢語言，如DMQL；也有專門為Web挖掘而定義的WebSSQL、WebLQM 和Squeal等。

2Web使用挖掘的應用系統

1)通用系統

通用系統提供多種通用的數據挖掘功能，一般并不直接支持某種特定應用。WebMiner[14]支持多種數據挖掘功能，并提供挖掘語言。WebSIFT的主要特點是支持基于support logic的模式興趣度、自動識別和過濾出令人感興趣的模式。最有影響力的是WUM系統。它把清理后的日志數據合成聚合樹(aggregate tree)，挖掘和分析工作的主要內容是使用MINT語言查詢聚合樹。

2）商業智能

在以用戶為中心導向的電子商務中，用戶盈利能力分析、用戶群體分類分析、用戶滿意度分析、用戶的獲得與保持和交叉營銷是商業領域內很重要的工作。在Web站點可收集大量的客戶行為數據，但由于數據量很大，手工分析幾乎變成了不可能的任務。適合處理大數據量的Web使用數據挖掘技術便在此處體現出了它的商業價值。有一些商用軟件如Accure、Microstrategy和IBM的SurfAid 等均是針對這個方面的應用。

3)個性化服務

Web個性化服務是指Web站點能夠根據用戶的喜好和需求自動調整Web站點的信息組織和表示。一方面用戶能夠在它的幫助下迅速找到需要的信息，使得Web站點更具吸引力。該應用的關鍵問題是用戶建模和行為預測。ThorstenJoachzms等人建立了一個稱為Web watcher的瀏覽導航系統。它根據用戶事先聲明的瀏覽目的或興趣(以關鍵字的形式表示)預測當前頁中用戶可能點擊的鏈接，并以圖形化的方式標注出此鏈接。文獻[15]實現了一個基于聚集模型的Web推薦系統。

4）Web性能改進和設計優化

其主要目的是利用Web使用挖掘技術向網站建立者提供各種關于網站架構的信息，也提供了用戶在使用網站時的習慣。網絡管理員可以在Web 緩存、網絡結構安排、負載平衡和數據分布上進行統籌規劃。具體的研究有利用 Web日志數據設計一個數據集市、為頻繁模式挖掘提供數據源、應用于智能Web緩沖。

3未來研究重點及展望

WUM技術作為一個新興研究領域，采用了來自多個領域的技術和先驗知識。雖然它取得很多突破性的進展，但是在未來的研究當中，還有一些熱點和難點的方向值得指出。

1）數據收集與預處理

在WUM過程中，如何既不侵犯用戶的個人隱私，又能盡量收集到完整的網站訪問日志；同時能保證服務器的工作效率和服務質量。有關數據收集的專門工具和技術正在研究中。另外，目前WUM的數據源主要集中在server端的log日志，在未來的研究中如何能將server log、proxy server log及client端的cookies log中的使用數據、用戶信息綜合集成并預處理，是一個研究的熱點和難點。

2)模式挖掘

目前WUM的工具不多，而且功能上均有較大的局限性，所采用的算法質量也不高。如何能開發出更加智能化和高效率的模式發現工具將是一個長期的研究課題。另外，如何盡可能全面(不可能全部)地集成Web上動態、分布的數據并實施挖掘，以挖掘出更多有用信息，也是未來該領域面臨的一個挑戰。

3）模式分析

開發一個智能化模式分析工具，將不同數據源挖掘出來的模式進行集成，并提供集統計分析、可視化分析技術、過濾和解釋功能等為一體的模式分析功能，真正輔助人們理解挖掘出來的知識是一個值得不斷深入研究和探索的熱點。

參考文獻：

[1]BRIN S，MOTWANI R.What can you do with a Web in your pocket[J].Data Engineering Bulletin，1998，21（2）：37－47.

[2]FELDMAN R， DAGAN I. Knowledge discovery in textual databases (KDT)[C]//Proc of the 1st Int’l Conf on Knowledge Discovery and Data Mining.Montreal:[s.n.]，1995:112－117.

[3]CHAKRABARTI S. Data mining for hypertext: a tutorial survey [J].SIGKDD Exploration， 2000，1(2):1－11.

[4]COOLEY R， MOBASHER B， SRIVASTAVA J. Web mining:information and pattern discovery on the World Wide Web[C]//Proc of the 9th Int’l Conf on Tools with Artificial Intelligence.Washington DC:IEEE Computer Society Press，1997:558－567.

[5]MADRIA S K， BHOWMICK S. Research issue in Web data mining[C]//Proc of the 1st Int’l on Data Warehousing and Knowledge Discovery. Canada:AAAI Press，1999:303－312.

[6]PITKOW J.In search of reliable usage data on the WWW[C]//Proc of the 6th Int’l World Wide Web Conference. Santa Clara:Elsevier Science，1997:133－142.

[7]GRAHAM CUMMING J. Hits and misses:a year watching the Web [C]//Proc of the 6th Int’l World Wide Web Conference.Santa Cla ra:Elsevier Science，1997:118－123.

[8]PERKOWITZ M， ETZIONI O.Adaptive Web sites:conceptual cluster mining[C]//Proc of the 16th International Joint Conference on Artificial Intelligence. Stockholm:[s.n.]， 1999:344－349.

[9]SRIVASTAVA J， COOLEY R， DESHPANDE M. Web usage mining: discovery and applications of usage patterns from Web data [J].SIGKDD Explorations， 2000，1(2):12－23.

[10]SHAHABI C， ZARKESH A， ADIBI J， et al. Knowledge discovery from users Web page navigation[C]//Proc of IEEE RIDE Workshop.Los Alamitos:IEEE Computer Society Press，1997:204－210.



[11]LUOTONEN A. The common log file format [EB/OL].(1995－09－27).http://www.w3.org/pub/www/.

[12]FastStats log analyzer[EB/OL].(1999 06 12).http://www. mach5.com/fast/.

[13]ZAIANE O， XIN M， HAN J. Discovering Web access patterns and trends by applying OLAP and data mining technology on Web logs[C]//Proc of Advances in Digital Libraries Conference (ADL). Sante Barbara:[s.n.]，1998:19－29.

[14]BUCHNER A，MULVENNA M D. Discovering Internet marketing intelligence through online analytical Web usage mining[J].SIGMOD Record， 1998， 27(4):54－61.

[15]MDBASHER B， COOLEY R， SRIVASTAVA J. Automatic personalization based on Web usage mining[J].Communications of the ACM，2000，43(8):142－151.

[16]MOBASHER B. Grouping Web page references into transactions for mining World Wide Web browsing patterns[C]//Proc of IEEE Knowledge and Data Engineering Exchange Workshop. New York:IEEE Press， 1997:108－132.

[17]COHEN E， DATAR M， FUJIWARA S. Finding interesting associations without support pruning[J].Communications of ACM， 2002，49(8):122－131.

[18]ZAIANE O R， HAN J. Resource and knowledge discovery in global information systems:a preliminary design and experiment[C]//Proc of the 1st Int’l on Knowledge Discovery and Data Minning. Montreal:[s.n.]，1995:331－336.

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