摘要：當今電子商務網站日益增多，網站所提供的功能和服務也越來越豐富，然而也存在不足。比如，提供的服務或信息分布不合理，未能充分考慮到用戶的需求；信息的訪問路徑未能考慮到信息的重要性和普遍關注性等等。本文研究將集中在基于圖結構的用戶訪問模式挖掘及其在電子商務中的應用上，通過對基于Web拓撲結構(圖結構)挖掘用戶訪問模式的數據挖掘，可對已存在的Web站點的結構及站點內的頁面進行調整和改善，方便地向瀏覽模式相似的用戶組推薦其感興趣的主題相似的頁面，使各類信息和服務以更有效的方式提供給用戶。

關鍵詞：數據挖掘 Web日志挖掘 用戶訪問模式 Web拓撲結構

一、引言

近幾年因特網已經成為一個巨大的、分布廣泛的和全球性的信息服務中心，逐漸滲透到人們的日常工作、生活及其它領域，它為用戶提供了各種信息。然而，用戶面對一堆雜亂無章的信息往往花費了大量的精力卻無法找到理想的結果。如何有效得分析用戶的需求，幫助用戶從因特網的信息海洋中發現他們感興趣的信息和資源，已經成為一項迫切而重要的課題。解決這些問題的一個途徑，就是將傳統的數據挖掘技術與Web結合起來，進行Web數據挖掘。其中的Web日志挖掘可以掌握用戶在瀏覽站點時的行為，并且將挖掘出的用戶訪問模式應用于網站上，在改善Web站點的結構以及頁面間的超鏈接結構，提高站點的服務質量等方面有重要的意義。

二、Web數據挖掘概述

(一)Web數據挖掘的定義及分類

Web數據挖掘我們這里采用一個更一般的定義：Web數據挖掘是指從與WWW相關的資源和行為中抽取感興趣的、有用的模式和隱含信息。

Web信息的多樣性決定了Web挖掘任務的多樣性，Web數據挖掘總的來說分為內容挖掘、結構挖掘和日志挖掘三類，如圖l所示：

(二)Web日志挖掘

Web日志挖掘也稱Web使用挖掘，是指從Web使用數據中抽取用戶訪問模式的過程。

一般Web日志挖掘的過程分為以下三步：

1．數據準備：對Web日志內容進行預處理，刪除無用數據，識別用戶會話，完善訪問路徑。

2．模式識別：采用相應的數據挖掘算法，對預處理之后的數據進行挖掘，生成模式。

3．模式分析：排除模式識別中沒有價值的規則或模式，將有價值的模式提取出來。

三、基于圖結構的Web日志挖掘

(一)數據準備

1．數據源

目前的Web日志挖掘的數據源主要是Web服務器日志文件，它記錄了用戶訪問站點的數據，每當站點上的頁面被訪問一次，Web服務器就在日志中增加一條相應的記錄。服務器上的日志不僅詳細記錄了站點訪問者的瀏覽行為，而且匯集了訪問同一站點的多個訪問者的行為。

2．數據預處理

在Web日志挖掘中，主要分析的數據源是服務器日志，但是由于服務器日志記錄的數據并不完整，直接在其上進行挖掘非常困難。因此要對日志數據進行預處理主要包括以下步驟：

數據轉換：將原始日志文件導入數據庫中。

數據清理：刪除與日志分析目的無關的記錄。

用戶識別：將用戶和請求的頁面相關聯。

會話識別：將用戶在一段時間內的請求頁面分解成能反映實際瀏覽習慣的用戶會話。

路徑補充：將本地或者代理服務器中緩存而沒有被日志記錄的請求頁面增加到會話中。

(二)基于圖結構的用戶訪問模式挖掘

本文中的算法在現有的挖掘關聯規則算法的基礎上上進行延伸，并且在支持度計算，候選路徑的產生和剪除階段時考慮網站的圖結構。這樣，在候選集的生成和剪除過程中減少了候選集的數量，可提高發現模式的精確性和效率，并且避免了“交易變質”的問題。首先，分析站點結構，并給出“圖”的相關定義和定理。其次，對現有的Web日志挖掘方法進行簡單的介紹和分析。接著，給出基于圖結構的用戶訪問模式挖掘算法。

1．站點結構的分析

每個Web網站并不是平面結構，而是有自己的特定結構。我們可將Web結構看作是一個多層的模型，每個層面包含很多頁面，這些頁面上有很多文本、圖片、音樂等頁面元素組成，它們可以鏈接本層面或其他層面的頁面元素。

Web可以用一個有向圖來表示，G=(V，E)，V是頁面的集合，E是頁面之間的超鏈接集合。頁面抽象為圖中的頂點，而頁面之間的超鏈接抽象為圖中的有向邊。頂點v的入邊表示對v的引用，出邊表示v引用了其它的頁面。 所以Web頁面之間的超鏈接揭示了Web結構。通過對Web結構的分析可對Web數據挖掘有很大的幫助，如圖4，某站點拓撲結構示例圖。

2．基于圖結構的用戶訪問模式挖掘算法

Web用戶訪問模式的挖掘過程可描述為：把用戶會話序列看成是對圖的遍歷，結合數據庫和Web圖結構確定訪問的最大向前路徑。從中找出支持度大于閾值的所有子路徑即頻繁遍歷路徑，最后確定最大頻繁遍歷路徑。基于圖結構的用戶訪問模式的挖掘和現有方法最大的不同是，訪問模式也被認為是圖遍歷，而不是二叉樹訪問順序，即用戶會話序列是圖中的路徑。

(1)生成最大向前路徑

Web用戶訪問模式的挖掘過程的第一步是把用戶會話序列看成是對圖的遍歷，結合數據庫和Web圖結構確定訪問的最大向前路徑。所謂最大向前路徑(MFP)是指從起始頁開始到回溯發生前，用戶連續訪問的最大頁面序列。

假設 代表一個用戶會話， 代表一個含有潛在MFP的字符串，初值為空，f1ag表明當前的遍歷方向是前進還是后退，數據庫D存儲MFP序列。算法依次對每一個用戶會話進行如下操作：

①依次讀取頁面xi(1≤i≤m)。

②若Xi不存在于{y1，…，y-1}中，即xi是沒有訪問過的頁面，則將xi作為yj加入當前可能的MFP中，f1ag標記為前進，轉(1)。

③否則若xi=yk(1≤k

如果f1ag標明前進遍歷，則將{y1，…，y-1}作為一個M F P輸出到最大前向路徑集合F中，然后從中刪除{yk 1，…，yj-1}，并設標志f1ag為向后移動，轉(1)。

如果flag標明為回退，刪除{yk i，…，yj-1}后轉(1)。

④當處理到用戶會話中的最后一頁時，如果f1ag標志仍-標明向前，則此時的{y1，…，yj 1}是該會話中的最后一個MFP。 此算法的形式化描述如下：

for aU Sn∈S //依次處理繪畫文件中的每個會話Sn1

y1=x1；j=2；i=2 f1ag=YES； ////初始化頁面序列，將遍歷方向設置為前進；

while(i≤m)//循環處理用戶會話Sn中每個頁面；

{

if(xi==yk)for some 1≤k (2)挖掘頻繁遍歷路徑

頻繁遍歷路徑是指MFP中滿足一定支持度的子路徑序列(不是連續頁面序列)。頻繁遍歷路徑的確定能用像Aprior算法中的逐層搜索算法實現。在算法的每步中，都要掃描數據庫，并計算所有的候選集的支持度。每步中的所有候選集都有相同的長度。在每個過程的結束，生成候選集Ck，然后計算Ck中每個候選項的支持度并剪除小于支持度閾值的候選項，以減少下一循環的掃描時間，由此頻繁遍歷路徑集合Lk被確定，并用于在下個步中候選集的計算。算法的一般結構如下。支持度的最小值記為minSupport，Ck表示所有長度為k的候選集，Lk表示所有長度為k的頻繁遍歷路徑的集合，D表示數據庫，G表示圖。

算法4－逐層搜索確定圖G中的頻繁遍歷路徑 盡管逐層搜索算法的基本結構相似于Apriori，但是它的組成部分(i)候選集支持度計算(ii)產生下一階段的候選集，明顯不同于Apriori，因為，該算法中的候選集必須是圖中的路徑。該算法基于定理4執行Apriori剪除。對于支持度計算(第6，7步)，基于子路徑的數量。

在圖4的例子中， 是一條頻繁遍歷路徑，也是用戶會話2和4的一條子路徑，盡管在用戶會話4中，它的頂點是不連續的，但在圖5中，它是一條路徑。還有，頻繁遍歷路徑 不能再延伸，因為如圖4所示，它的終結點A只有到頂點B和C的兩條弧，并已經包含在這條路徑中。頻繁遍歷路徑 不能延伸，既不是由于已經包含在路徑中的頂點C，也不是由于頂點B，因為 不是頻繁遍歷路徑。

四、Web日志挖掘的應用

從Web使用數據中挖掘出的訪問模式可以應用到廣闊的領域，以下僅介紹在電子商務中的應用。

(一)個性化服務

根據網站用戶的訪問情況，為用戶提供個性化信息服務，這是許多互聯網應用，尤其是互聯網信息服務或電子商務(網站)所追求的目標。根據用戶的訪問行為和檔案向使用者進行動態的推薦，對許多應用都有很大的吸引力。Web日志挖掘是一個能夠出色地完成這個目標的方式。

例如141：SiteHelper可以通過分析每個用戶的網頁訪問情況，了解用戶的愛好，并從用戶瀏覽時間較長的網頁中抽取出相應關鍵字，匯總后給用戶，獲得反饋后，再向用戶推薦網站中其他類似或相關網頁。又如：WebWatcher“跟蹤”用戶瀏覽網頁過程，識別用戶可能感興趣的鏈接，WebWatcher根據用戶本人和其他類似用戶的瀏覽情況，對每個新網頁進行評估，以幫助用戶能夠及時地瀏覽自己感興趣的網頁。

(二)商業智能

有關用戶訪問網站的行為模式，對于電子商務中的市場人員來說是非常重要的，通過定義Web使用日志的超維數據立方，將Web使用數據與電子商務應用數據有機地結合在一起。這樣就可以利用數據挖掘方法與技術來為客戶關系管理中的四個重要階段(吸引顧客，保留顧客，交叉銷售，顧客離開)提供決策支持。例如：WebLogMiner可以將Web日志數據轉換為超維數據立方的形式以便能夠進行OLAP分析處理和數據挖掘工作。在WebLogMiner系統中還使用了關聯規則，分類和序列模式分析等數據挖掘方法，得到了電子商務交易行為序列、特征和交易預期的分析。

五、小結

本文運用一種基于Web拓撲結構(圖結構)挖掘用戶訪問模式的方法，區別于常用的基于樹形結構的Web路徑分析技術，提高了發現模式的精確性和效率。我們給出一個像Aprior那樣的逐層搜索算法，得到用戶的瀏覽模式。