崔曉靖，陳興蜀，曾雪梅

（四川大學(xué) 計(jì)算機(jī)學(xué)院，四川 成都610065）

0 引 言

Web使用挖掘［1－3］是Web挖掘的一個(gè)分支，是通過(guò)挖掘用戶的訪問(wèn)日志，從中發(fā)現(xiàn)用戶的訪問(wèn)模式的過(guò)程。只有使用準(zhǔn)確描述用戶瀏覽行為的數(shù)據(jù)進(jìn)行挖掘才能發(fā)現(xiàn)正確的模式和規(guī)則。因此，作為知識(shí)提取的輸入數(shù)據(jù)，數(shù)據(jù)預(yù)處理后的數(shù)據(jù)必須具有較高的準(zhǔn)確性。用戶訪問(wèn)記錄的缺失影響了Web使用挖掘的準(zhǔn)確性。例如，文獻(xiàn)［4］中對(duì)Web日志挖掘中路徑補(bǔ)充的影響進(jìn)行評(píng)估，說(shuō)明了路徑補(bǔ)充提升了規(guī)則抽取的數(shù)量以及抽取規(guī)則的支持度和置信度。所以，在Web日志挖掘中路徑補(bǔ)全是很有必要的。

為了提高數(shù)據(jù)與處理后數(shù)據(jù)的質(zhì)量，學(xué)者們提出了多種路徑補(bǔ)充方案［5－7］。文獻(xiàn)［5］使用典型的“后退”方式對(duì)缺失路徑進(jìn)行補(bǔ)充。文獻(xiàn)［6］提出一種新的基于“多窗口”方式的路徑補(bǔ)充算法，解決了用戶使用多個(gè)窗口進(jìn)行瀏覽時(shí)的路徑補(bǔ)充問(wèn)題，是對(duì) “后退”方式的補(bǔ)充。文獻(xiàn)［7］提出一種個(gè)性化推薦模式下的路徑補(bǔ)充機(jī)制，利用網(wǎng)站的靜態(tài)結(jié)構(gòu)和動(dòng)態(tài)信息結(jié)合不同的頁(yè)面類型進(jìn)行有效地路徑補(bǔ)充。這些方法大多是將兩個(gè)頁(yè)面間的最近訪問(wèn)路徑或最短路徑補(bǔ)充到原始路徑中。在網(wǎng)頁(yè)結(jié)構(gòu)復(fù)雜的情況下，兩個(gè)網(wǎng)頁(yè)之間的鏈接相對(duì)復(fù)雜，多數(shù)情況下用戶并不是沿著最短路或最近訪問(wèn)過(guò)的路徑進(jìn)行瀏覽，而且用戶可能是在同一窗口打開(kāi)一系列頁(yè)面，也可能是在不同窗口打開(kāi)多個(gè)頁(yè)面。這種情況下，僅僅基于 “后退”或者“多窗口”的路徑補(bǔ)全算法并不能完整地還原用戶的行為趨勢(shì)。本文在現(xiàn)有的路徑補(bǔ)全算法的基礎(chǔ)上提出一種基于站點(diǎn)結(jié)構(gòu)和用戶瀏覽時(shí)間的路徑補(bǔ)充算法來(lái)解決這些問(wèn)題。實(shí)驗(yàn)證明，在上述的幾種訪問(wèn)模式下，本文的路徑補(bǔ)全算法都能夠有效地補(bǔ)充丟失的路徑。

1 Web日志預(yù)處理簡(jiǎn)介

本文的數(shù)據(jù)預(yù)處理模型如圖1所示。數(shù)據(jù)預(yù)處理過(guò)程主要包括數(shù)據(jù)清洗、用戶識(shí)別、會(huì)話識(shí)別和路徑補(bǔ)全4個(gè)過(guò)程。圖中網(wǎng)站結(jié)構(gòu)通過(guò)爬蟲(chóng)獲取。

圖1 數(shù)據(jù)預(yù)處理過(guò)程

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

數(shù)據(jù)清理是數(shù)據(jù)預(yù)處理的第一階段。Web日志中存在大量的干擾性數(shù)據(jù)，這些數(shù)據(jù)與用戶訪問(wèn)行為無(wú)關(guān)，嚴(yán)重影響了Web日志挖掘結(jié)果的準(zhǔn)確性。數(shù)據(jù)清理階段主要清理一些無(wú)關(guān)數(shù)據(jù)。其規(guī)則如下參見(jiàn)文獻(xiàn)［8］。

1.2 用戶識(shí)別

用戶識(shí)別就是識(shí)別每個(gè)訪問(wèn)網(wǎng)站的用戶的過(guò)程。本文用戶識(shí)別采用以下策略：

（1）IP不同，表示不同用戶；

（2）IP相同，使用不同的代理服務(wù)器表示不同的用戶；

（3）IP和代理服務(wù)器相同，不同的瀏覽其代表不同的用戶［11］；

（4）IP、代理服務(wù)器以及瀏覽其都相同，引用頁(yè)面不在前面的記錄中表示不同的用戶［12］。

否則，就表示相同的用戶。

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

會(huì)話是指用戶進(jìn)入網(wǎng)站到離開(kāi)網(wǎng)站的一系列頁(yè)面請(qǐng)求。一個(gè)用戶可能多次訪問(wèn)同一網(wǎng)站，這就需要對(duì)用戶進(jìn)行會(huì)話識(shí)別以區(qū)分用戶的每次訪問(wèn)過(guò)程。本文采用文獻(xiàn)［8］中時(shí)間窗口模型的會(huì)話識(shí)別算法進(jìn)行用戶會(huì)話識(shí)別。

1.4 路徑補(bǔ)全

由于本地代理和緩存服務(wù)器的存在，用戶訪問(wèn)緩存中已經(jīng)訪問(wèn)過(guò)的頁(yè)面時(shí)，日志中并不再記錄該次訪問(wèn)，這樣就會(huì)遺漏很多頁(yè)面。本文提出一種基于網(wǎng)站拓?fù)浣Y(jié)構(gòu)和訪問(wèn)時(shí)間相結(jié)合的路徑補(bǔ)全算法。該算法主要是利用日志的動(dòng)態(tài)結(jié)構(gòu)和訪問(wèn)時(shí)間對(duì)缺失頁(yè)面進(jìn)行補(bǔ)全。算法基本思想是利用會(huì)話中的日志記錄構(gòu)建動(dòng)態(tài)站點(diǎn)結(jié)構(gòu)，并根據(jù)動(dòng)態(tài)結(jié)構(gòu)找到可能補(bǔ)充的多條路徑選擇合適的路徑補(bǔ)充到日志記錄中。具體補(bǔ)充算法將在后文中做詳細(xì)介紹。

2 路徑補(bǔ)全算法

2.1 概念描述

定義1 用戶訪問(wèn)記錄（R）。R＝＜id，time，url，refer＞。其中id 表示當(dāng)前會(huì)話中記錄R 的序號(hào)，time表示請(qǐng)求時(shí)間，url表示請(qǐng)求頁(yè)面的鏈接地址，refer表示用戶瀏覽的上一頁(yè)面，即引用站點(diǎn)URL。

定義2 用戶會(huì)話集合Session。Session＝＜Session＿ID，（R（1），R（2），…，R（n））＞，其中Session＿ID 表示會(huì)話的序號(hào)，R（i）表示會(huì)話中的第i個(gè)用戶訪問(wèn)記錄，且i，j如果i＜j，則有R（i）.id＜R（j）.id 且R（i）.time≤R（j）.time。

根據(jù)第2節(jié)中的用戶識(shí)別策略可知，對(duì)于同一個(gè)會(huì)話集合中的Session，他們擁有相同的IP。

定義3 用戶集合（U）。U ＝＜UID，＜Session（1），Session（2），…，Session（n）＞＞。其中UID 表示用戶標(biāo)識(shí)，Session（i）表示會(huì)話集合。

定義4 用戶相鄰日志記錄時(shí)間間隔（ΔT）。表示同一會(huì)話中兩條相鄰日志記錄之間的時(shí)間間隔值。

定義5 頁(yè)面瀏覽時(shí)間（vis＿time）。頁(yè)面瀏覽時(shí)間表示用戶瀏覽某一頁(yè)面所花費(fèi)的時(shí)間，也就是說(shuō)，在會(huì)話中用戶瀏覽R（i）.url花費(fèi)的時(shí)間

對(duì)于連續(xù)的兩條日志記錄R（i）和R（i＋1），即R（i＋1）.refer＝R（i），R（i）.url頁(yè)面瀏覽時(shí)間為相鄰日志記錄時(shí)間間隔ΔT；當(dāng)R（i＋1）.refer≠R（i）時(shí)，說(shuō)明兩條日志記錄不連續(xù)或者日志記錄為該會(huì)話的最后一條日志記錄，此時(shí)的ΔT（i）并不能準(zhǔn)確反映頁(yè)面的瀏覽時(shí)間，此時(shí)記R（i）.url的頁(yè)面瀏覽時(shí)間為∞。

定義6 頁(yè)面平均瀏覽時(shí)間（avg＿time）。頁(yè)面平均瀏覽時(shí)間表示用戶集合中某一頁(yè)面的平均瀏覽時(shí)間

式中：num（url）——用戶集合U 中有效url（vis＿time（R（i）.url）≠∞）個(gè)數(shù)。

頁(yè)面平均瀏覽時(shí)間是對(duì)用戶瀏覽某一頁(yè)面瀏覽時(shí)間的一個(gè)估計(jì)。由于不同用戶的訪問(wèn)習(xí)慣、閱讀速度等具有個(gè)性化特征，因此定義6中的頁(yè)面平均瀏覽時(shí)間是針對(duì)不同用戶的，即不同用戶對(duì)同一個(gè)頁(yè)面的平均瀏覽時(shí)間可能不相等。由于vis＿time（R（i）.url）＝∞時(shí)，vis＿time（R（i）.url）不能有效反映用戶瀏覽該url的時(shí)間因而在估計(jì)url 的平均瀏覽時(shí)間時(shí)應(yīng)被舍棄。

定義7 用戶瀏覽路徑時(shí)長(zhǎng)（Tpath）。設(shè)path＝＜url1，url2，…，urlk＞其中url1，url2，...，urlk為訪問(wèn)路徑的url序列，且path－urli表示從path 的url序列中去掉urli頁(yè)面則

定義8 網(wǎng)頁(yè)動(dòng)態(tài)結(jié)構(gòu)。網(wǎng)頁(yè)動(dòng)態(tài)結(jié)構(gòu)也是用圖結(jié)構(gòu)存儲(chǔ)，動(dòng)態(tài)站點(diǎn)結(jié)構(gòu)圖G＝（V，E），V 表示會(huì)話中的頁(yè)面url，即圖G 中的頂點(diǎn)，頂點(diǎn)順序依次為url1，url2，…，urln，E 為當(dāng)前記錄前已經(jīng)遍歷的站點(diǎn)頁(yè)面間的鏈接，即圖G 中的頂點(diǎn)間的有向鏈接，G 的鄰接矩陣B 是n 階方陣，如果R（i）.url＝urli且R（j）.url＝urlj則有

定義9 待補(bǔ)充路徑和實(shí)際路徑的偏離程度σ。σ用于選取待補(bǔ)充路徑中最接近真實(shí)路徑的路徑。

為了選擇最合適的路徑，定義相鄰url的路徑時(shí)間間隔，它是為了衡量路徑補(bǔ)全算法中產(chǎn)生多個(gè)路徑的一個(gè)參數(shù)，而定義5中的頁(yè)面瀏覽時(shí)間是為了估算頁(yè)面平均瀏覽時(shí)間。

2.2 路徑補(bǔ)全基本流程

文獻(xiàn)［8］進(jìn)行會(huì)話識(shí)別后R（i＋1）.refer為空或者屬于站點(diǎn)URl集合。遍歷會(huì)話中的記錄，路徑補(bǔ)充按照以下流程進(jìn)行：

（1）如果會(huì)話中，R（1）.refer為本站點(diǎn)的網(wǎng)頁(yè)，則補(bǔ)充R（1）.refer到會(huì)話中，并繼續(xù)遍歷會(huì)話中的日志記錄，轉(zhuǎn)到（2）。

（2）如果會(huì)話中，R（i＋1）.refer≠R（i）.url且會(huì)話未結(jié)束，補(bǔ)充規(guī)則如下：①令待選路徑集合Path＿Set＝＜path－1，path0＞其中path0＝＜R（i）.url，R（i＋1）.refer＞，path－1＝＜R（i）.url＞。②根據(jù)用戶訪問(wèn)站點(diǎn)動(dòng)態(tài)結(jié)構(gòu)圖求出R（i＋1）.refer和R（i）.url之間的所有路徑path1，path2，…，pathn，并將這些路徑添加到Path＿Set里。

（3）計(jì)算Path＿Set中路徑集合時(shí)長(zhǎng)偏離ΔT（i）的程度σ－1，σ0，…，σn。

（4）找出min｛σ－1，σ0，…，σn｝所對(duì)應(yīng)的路徑pathk并將pathk－R（i）.url中的url 頁(yè)面轉(zhuǎn)換成記錄的形式補(bǔ)充到＜R（i）.url，R（i＋1）.url＞中。若存在p，q 滿足min｛σ－1，σ0，…，σn｝＝σp＝σq使得，則取pathp和pathq中里當(dāng)前記錄最近的一條路徑補(bǔ)充＜R（i）.url，R（i＋1）.url＞之間。

其中，path－1和path0表示不需要補(bǔ)充的情況和只需要補(bǔ)充R（i＋1）.refer的情況。

2.3 路徑補(bǔ)全算法實(shí)現(xiàn)

（1）兩點(diǎn)間有向路徑集合Path＿Set求解算法PS［9，10］。

站點(diǎn)動(dòng)態(tài)結(jié)構(gòu)則在路徑補(bǔ)充過(guò)程中產(chǎn)生，程序每處理一條記錄G 就可能增加一條兩個(gè)節(jié)點(diǎn)間的鏈接。算法實(shí)現(xiàn)中，用G 的逆鄰接表來(lái)實(shí)現(xiàn)。其結(jié)構(gòu)如圖2所示。

adjvex為鄰接點(diǎn)域，存放與R（i）節(jié)點(diǎn)相鄰的節(jié)點(diǎn)R（j）的序號(hào)j；nextarc指向下一表結(jié)點(diǎn)；data表示存放頂點(diǎn)R（i）信息；firstarc表示R（i）鄰接表的頭指針。所有的頭結(jié)點(diǎn)順序存放在向量R＿SET 中。

圖2 逆鄰接表的結(jié)構(gòu)

求解R＿SET 的算法如下：

由G 的鄰接矩陣B求解各頂點(diǎn)的逆鄰接表。

由逆鄰接表求解urli到urlj之間的所有有向路徑集合。

初始化urli到urlj的路徑集合Path＿Set＝NULL，以及臨時(shí)路徑集合Temp＿Path＝NULL

初始化路徑向量Path＝＜urli＞

（2）路徑補(bǔ)全算法流程。

3 實(shí)驗(yàn)與結(jié)果分析

本文以四川大學(xué)網(wǎng)站2012年6月的日志數(shù)據(jù)為實(shí)驗(yàn)數(shù)據(jù)，設(shè)計(jì)4種不同的瀏覽路徑，同一種路徑包含5條路徑，共20條路徑。這4種路徑分別是：①Path1（記P1），基于“后退”方式的用戶訪問(wèn)路徑；②Path2（記P2）?；?“多窗口 “的用戶訪問(wèn)路徑；③Path3（記P3），基于個(gè)性化模式的用戶訪問(wèn)路徑；④綜合訪問(wèn)模式的訪問(wèn)路徑。在4種訪問(wèn)模式下，分別使用已有的PRM 路徑補(bǔ)全算法［9，10］、基于多窗口的路徑補(bǔ)充算法［6］、基于個(gè)性化推薦的路徑補(bǔ)充算法［7］以及本文提出的算法來(lái)實(shí)現(xiàn)路徑補(bǔ)充。統(tǒng)計(jì)路徑補(bǔ)充的正確補(bǔ)充訪問(wèn)記錄個(gè)數(shù)，錯(cuò)誤補(bǔ)充訪問(wèn)記錄個(gè)數(shù)，分別計(jì)算各種訪問(wèn)模式下路徑補(bǔ)充的正確率P及其平均正確率。其中，正確率P＝T／（T＋F）。統(tǒng)計(jì)4種算法在四中訪問(wèn)模式下的正確率見(jiàn)表1。

表1 實(shí)驗(yàn)結(jié)果

由圖3可知：

（1）傳統(tǒng)的基于 “后退”方式的路徑補(bǔ)充算法在多窗口訪問(wèn)模式和個(gè)性化訪問(wèn)模式下路徑補(bǔ)充的準(zhǔn)確率較低；

（2）基于 “多窗口”的路徑補(bǔ)充算法和基于個(gè)性化的路徑補(bǔ)充算法在其適用的訪問(wèn)模式下準(zhǔn)確率較高；

（3）本文的基于網(wǎng)站結(jié)構(gòu)和瀏覽時(shí)間的路徑補(bǔ)充算法在多種訪問(wèn)模式下進(jìn)行的路徑補(bǔ)充均有較高的準(zhǔn)確率。

圖3 各種路徑補(bǔ)全方法準(zhǔn)確率比較

4 結(jié)束語(yǔ)

本文對(duì)各種路徑補(bǔ)全算法進(jìn)行了深入研究，探究了用戶訪問(wèn)路徑的幾種方式，分析了路徑補(bǔ)全的影響因素。并針對(duì)現(xiàn)有的路徑補(bǔ)全方法的缺點(diǎn)，提出了基于站點(diǎn)結(jié)構(gòu)和頁(yè)面瀏覽時(shí)間的路徑補(bǔ)全算法。實(shí)驗(yàn)表明，與其它方法相比，此方法在各種訪問(wèn)模式下均有較高的準(zhǔn)確率。

由于實(shí)驗(yàn)?zāi)繕?biāo)網(wǎng)站為中小型網(wǎng)站，訪問(wèn)量和日志量不會(huì)過(guò)大，運(yùn)算時(shí)，因而本文使用矩陣進(jìn)行存儲(chǔ)和計(jì)算效率也比較高。對(duì)于大型網(wǎng)站而言，日志量比較大，每個(gè)用戶會(huì)話內(nèi)的日志記錄比較多的情況，則需要對(duì)算法進(jìn)行優(yōu)化以提高程序運(yùn)行的效率，及時(shí)地為日志數(shù)據(jù)挖掘提供數(shù)據(jù)基礎(chǔ)。

［1］Nithya P，Sumathi.Novel pre－processing technique for web log mining by removing global noise and web robots ［C］／／NCCCS，IEEE，2012.

［2］Li Yan，F(xiàn)eng Boqin.The construction of transactions for web usage mining ［C］／／International Conference on Computational Intelligence and Natural Computing，2009：121－124.

［3］Reddy S K，Reddy K.An effective data preprocessing method for Web Usage Mining ［C］／／ICICES，IEEE，2013.

［4］CAI Weixin，F(xiàn)ENG Zhenyu，YANG Jian.Evaluation of impact of path completion in web log mining ［J］.Computer Systems ＆ Applications，2011，20 （3）：226－229 （in Chinese）.［蔡衛(wèi)欣，馮振宇，楊劍.web日志挖掘中路徑補(bǔ)充的影響評(píng)估 ［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2011，20 （3）：226－229.］

［5］WANG Lan，ZHAI Zhengjun.The research on data preprocess and path supplement in web data mining ［J］.Microelectronics＆Computer，2006，23 （8）：113－116 （in Chinese）. ［王嵐，翟正軍.web日志挖掘的預(yù)處理及路徑補(bǔ)全算法的研究 ［J］.微電子學(xué)與計(jì)算機(jī)，2006，23 （8）：113－116.］

［6］HUANG Jinjing，ZHAO Lei，YANG Jiwen.Path supplement in session reconstruction based on multi window ［J］.Computer Applications and Software，2009，26 （7）：46－51 （in Chinese）.［黃金晶，趙雷，楊季文.web會(huì)話構(gòu)造中基于多窗口的路徑補(bǔ)充 ［J］.計(jì)算機(jī)應(yīng)用與軟件，2009，26 （7）：46－51.］

［7］XIA Xiufeng，WANG Yu.A user access path complementing algorithm based on personalized recommendation ［J］.Computer Applications and Software，2011，28 （2）：179－183 （in Chinese）.［夏秀峰，王宇.一種基于個(gè)性化推薦的用戶訪問(wèn)路徑補(bǔ)全算法 ［J］.計(jì)算機(jī)應(yīng)用與軟件，2011，28 （2）：179－183.］

［8］CAI Hao，JIAN Yubo，HUANG Chengwei，et al.Improved method for session identification in Web log mining ［J］.Computer Engineering and Design，2009，30 （6）：1321－1323 （in Chinese）.［蔡浩，賈宇波，黃成偉，等.Web日志挖掘中的會(huì)話識(shí)別算法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30 （6）：1321－1323.］

［9］LI Y，F(xiàn)ENG B，MAO Q.Research on path completion technique in web usage mining ［C］／／International Symposium on Computer Science and Computational Technology，IEEE，2008：554－559.

［10］MAO Hongmei，GAN Shengke.An algorithm for finding all paths bet ween source node and other nodes in a digraph ［J］.Microelectronics ＆ Computer，2009，26 （3）：128－130 （in Chinese）.［毛紅梅，甘晟科.求有向圖中源點(diǎn)到各結(jié)點(diǎn)所有路徑的一種實(shí)用算法 ［J］.微電子學(xué)與計(jì)算機(jī)，2009，26（3）：128－130.］

［11］Varnagar Chintan R，Madhak Nirali N，Kodinariya，et al.Web usage mining：A review on process，methods and techniques［C］／／International Conference on Information Communication and Embedded Systems，2013：40－46.

［12］XIAO Hui，WANG Lihua.User identification algorithm in web log mining ［J］.Computer Systems ＆ Applications，2011，20 （5）：223－226 （in Chinese）.［肖慧，王立華.Web日志挖掘中的用戶識(shí)別算法 ［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2011，20 （5）：223－226.］