基于Web日志挖掘的路徑補(bǔ)充算法改進(jìn)

邵天會

【摘要】 由于進(jìn)行數(shù)據(jù)挖掘的Web日志來源不同，進(jìn)行數(shù)據(jù)預(yù)處理時(shí)比較復(fù)雜，為了提高數(shù)據(jù)處理效率，結(jié)合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對用戶訪問路徑進(jìn)行二叉樹的轉(zhuǎn)換，提出PFS（Path For Session）算法---消息路徑優(yōu)化。研究表明該算法解決了Web日志用戶訪問路徑的補(bǔ)充問題，提高了數(shù)據(jù)預(yù)處理效率。

【關(guān)鍵詞】 訪問路徑 PFS 消息路徑優(yōu)化

Web日志挖掘主要是針對用戶瀏覽信息進(jìn)行分析，因此用戶會話的提取是首要任務(wù)。所謂的用戶會話就是某個(gè)用戶在某個(gè)時(shí)間段內(nèi)請求頁面的集合[1]。在識別用戶會話過程中存在的一個(gè)問題是確定訪問日志中是否有重要的請求沒有被記錄。路徑補(bǔ)充保證了用戶訪問日志的完整性，從而保證Web日子挖掘的現(xiàn)實(shí)意義。

一、 路徑補(bǔ)充原理

路徑補(bǔ)充就是將由于本地或代理服務(wù)器緩存的影響而沒有產(chǎn)生日志記錄的請求頁增加到用戶會話中[2]。

得到用戶會話之后，要根據(jù)用戶會話得到訪問路徑。路徑補(bǔ)充涉及定義如下：

定義：用戶會話的路徑集合 PS=…> ，其中，1≦k≦n，Resident 表示用戶在該頁面的停留時(shí)間[3]。算法輸入為 RS，RS 中的記錄是按 Rid 值分組按時(shí)間順序排列的，輸出為 PS，得到路徑 PS 后，根據(jù)引用信息進(jìn)行路徑補(bǔ)充，如果一條記錄的ReferUrl 不是上一條記錄的 Url，則認(rèn)為該用戶是點(diǎn)擊“后退”按鈕訪問了緩存中的頁面，需要進(jìn)行路徑補(bǔ)充。

PS 中的記錄是按 Rid 值分組順序排列的；輸出為：PS。

二、消息路徑優(yōu)化算法

2.1 消息路徑優(yōu)化算法原理

結(jié)合本文的研究目的和Web日志數(shù)據(jù)源針對路徑補(bǔ)充的問題提出利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)從用戶訪問序列獲得用戶訪問事務(wù)數(shù)據(jù)的算法PFS（Path For Session）算法---消息路徑優(yōu)化，PFS算法是首先把網(wǎng)站的樹形拓?fù)浣Y(jié)構(gòu)轉(zhuǎn)換為二叉樹的結(jié)構(gòu)，然后在二叉樹結(jié)構(gòu)上根據(jù)用戶的會話序列得到用戶訪問事務(wù)序列，PFS算法認(rèn)為當(dāng)前用戶的訪問序列中出現(xiàn)不連續(xù)的節(jié)點(diǎn)時(shí)，則用戶可能點(diǎn)擊了瀏覽器上的Back按鈕或重復(fù)點(diǎn)擊一個(gè)鏈接，當(dāng)出現(xiàn)這種情況時(shí)，表明用戶在點(diǎn)擊Back按鈕或重復(fù)點(diǎn)擊鏈接時(shí)就結(jié)束了上次會話，重新開始了新一輪的會話。

2.2 消息路徑優(yōu)化算法的實(shí)現(xiàn)

當(dāng)前會話頁面分別為：A，C，D，I，對應(yīng)的請求頁面分別為F，H，C，J。

這次會話的序列是：A--F--C--H--D--C--I--J使用路徑補(bǔ)充技術(shù)：A--B--F--B--A--C--H--C--A--D--A--I--D--J再利用最大向前引用路徑算法得出用戶的訪問事務(wù)為A--B--F，A--C--H，A--D--I--J，三個(gè)事務(wù)。在此過程中，必須對用戶的訪問序列進(jìn)行補(bǔ)充得到完整的路徑后再應(yīng)用最大向前應(yīng)用路徑才能得到訪問事務(wù)。利用PFS算法轉(zhuǎn)換為二叉樹。

由此，不再需要對訪問序列補(bǔ)充路徑便可由用戶訪問序列直接獲得用戶的訪問事務(wù)A--B--F，A--C--H，A--D--I--J。

三、算法改進(jìn)對比

用戶訪問會話使用路徑補(bǔ)充和PFS算法得到用戶訪問事務(wù)的時(shí)間進(jìn)行對比，此對比是假設(shè)網(wǎng)站的結(jié)點(diǎn)鏈接已經(jīng)由圖結(jié)構(gòu)轉(zhuǎn)換為樹形結(jié)構(gòu)，且樹形結(jié)構(gòu)的擁有25個(gè)葉結(jié)點(diǎn)，樹的深度為分別為3，4，5，6時(shí)進(jìn)行的。

實(shí)驗(yàn)證明該算法在相同的路徑深度前提下，減少了Web日志數(shù)據(jù)預(yù)處理的時(shí)間，提高了效率。

四、結(jié)論

PFS算法改進(jìn)了數(shù)據(jù)預(yù)處理階段的路徑補(bǔ)充步驟，從整體上提高了數(shù)據(jù)挖掘效率，但是算法基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，隨著網(wǎng)站的頁面大量增加，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)也隨之復(fù)雜，算法的復(fù)雜度同時(shí)增大，所以PFS算法對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜的網(wǎng)站需要更多的研究，以適應(yīng)復(fù)雜的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

參 考 文 獻(xiàn)

[1] 何坤鵬，郭海波.Web 日志挖掘技術(shù)及其應(yīng)用研究[J]，中國科技信息，2007-08-15：236-237.

[2] 劉明吉，王秀峰，黃亞樓.數(shù)據(jù)挖掘中的數(shù)據(jù)預(yù)處理[J]計(jì)算機(jī)科學(xué)，2000-04-15：3-9.

[3] E.F.Codd，S.B.Codd and C.T.Salley.Providing OLAP to User-Analysts：An IT Mandate.IBM Research Lab，Techni cal Report，1993.

[4] J.Qay，S.Chaudhuri，A.Bosworth，A.Layman，D.Reichart，M.Venkatrao，E Pellow，and H.Pirahesh.Data cube：A relational aggregation operatorgeneralizing group-by，cross-tab and sub-totals.Data Mining and Knowledge Discovery，1：29-54，1997.