基于最長前綴頻繁子路徑樹的Web日志挖掘算法

翁 偉，林開標(biāo)，朱順痣，王震岳

(廈門理工學(xué)院計算機(jī)與信息工程學(xué)院，福建廈門 361024)

基于最長前綴頻繁子路徑樹的Web日志挖掘算法

翁 偉，林開標(biāo)，朱順痣，王震岳

(廈門理工學(xué)院計算機(jī)與信息工程學(xué)院，福建廈門 361024)

現(xiàn)有的Web日志頻繁訪問路徑挖掘算法往往不能在追求時間效率的同時準(zhǔn)確挖掘出符合用戶瀏覽順序的頻繁路徑.提出了有效挖掘Web日志中頻繁訪問路徑的算法，將事務(wù)數(shù)據(jù)庫轉(zhuǎn)換為Web訪問路徑樹，根據(jù)支持度進(jìn)行剪枝構(gòu)造最長前綴頻繁子路徑樹，然后進(jìn)行頻繁路徑挖掘，實(shí)驗(yàn)證實(shí)了此方法的有效性，并分析了支持度設(shè)置對頻繁路徑生成的影響.

Web日志挖掘;頻繁訪問路徑;訪問路徑樹

0 引言

Web日志挖掘近年來逐漸成為數(shù)據(jù)挖掘領(lǐng)域的熱點(diǎn).Web站點(diǎn)日志存儲了用戶訪問網(wǎng)站的蹤跡.目前常見的Web日志數(shù)據(jù)格式有NCSA、擴(kuò)展W3C和IRCache等［1］，記錄的數(shù)據(jù)主要包括用戶的IP地址、訪問時間、訪問頁面、訪問方式、引用頁面等.Web日志頻繁路徑挖掘通過分析Web日志記錄發(fā)現(xiàn)用戶的訪問規(guī)律，分析和掌握用戶訪問Web站點(diǎn)的行為，對重構(gòu)網(wǎng)站、個性化推薦、廣告投放等方面有重要的參考價值［2］.目前，Web日志挖掘研究主要集中在2個方面，一是認(rèn)為用戶的瀏覽頻度就反映了用戶的訪問興趣［3-6］，二是泛化興趣度的計算方法［7-9］.興趣度定義本質(zhì)上在于從不同角度來約簡頻繁路徑，減少問題規(guī)模，如何快速準(zhǔn)確地挖掘出日志中隱含的頻繁訪問路徑是各類算法追求的共性目標(biāo).本研究在訪問路徑樹性質(zhì)的研究基礎(chǔ)上，給出了一種高效的基于最長前綴頻繁子路徑樹的Web日志挖掘算法.

1 相關(guān)概念

Web日志數(shù)據(jù)經(jīng)過數(shù)據(jù)清洗、用戶識別、會話識別等預(yù)處理步驟后，將訪問信息轉(zhuǎn)換為訪問事務(wù)數(shù)據(jù)庫，該數(shù)據(jù)庫的記錄為用戶的會話，由按訪問順序的頁面所構(gòu)成.這些記錄集是頻繁訪問路徑挖掘的對象.

定義1 設(shè)U是網(wǎng)站中所有頁面的集合，記U={p1，p2，…，pn}，會話S表示用戶對網(wǎng)站的一次完整訪問，記作S=〈pi，pi+1，…，pi+m〉，其中pi，pi+1，…，pi+m∈U，也就是說，會話是由有順序的頁面標(biāo)記所構(gòu)成的字符串，亦即訪問路徑序列，pi是用戶訪問的第一個頁面，pi+m是用戶訪問的最后一個頁面，但這些頁面可以重復(fù)，S的子串稱為訪問路徑，簡稱路徑.

定義2 Web訪問事務(wù)數(shù)據(jù)庫由某一時間區(qū)間的會話集合構(gòu)成，每一條會話為該數(shù)據(jù)庫中的一條記錄，也稱事務(wù)，事務(wù)由項(xiàng)目構(gòu)成.

定義3 如果一條訪問路徑，p=〈pj，pj+1，…，pj+m〉，滿足以下條件，

則稱路徑p為頻繁訪問路徑.其中0?N?1是預(yù)先定義好的最小支持度.

定義4 如果一條訪問路徑q=〈pk，pk+1，…，pk+n〉是路徑p=〈pj，pj+1，…，pj+m〉(m?n)的子路徑，并且k=j，那么稱q為p的前綴子路徑.類似可以定義后綴子路徑，若q是頻繁的，則稱q是p的頻繁前綴子路徑，進(jìn)一步，如果p中不存在更長的頻繁前綴子路徑，則稱q是p的最長頻繁前綴子路徑.

定義5 若路徑p=〈pj，pj+1，…，pj+m〉的前綴子路徑q=〈pj，pj+1，…，pj+m-1〉是路徑r=〈pk，pk+1，…，pj+n〉的后綴子路徑，則定義路徑r與p之積r×p=〈pk，pk+1，…，pk+n，pj+m〉，否則r×p為空.一般而言，r×p不等于p×r.路徑集合PS1與路徑集合PS2之積PS1×PS2為PS1中每條路徑與PS2中每條路徑之積的結(jié)果集.

2 算法描述

本研究提出的算法如圖1所示.

圖1 頻繁訪問路徑挖掘算法示意圖

2.1 輸入事務(wù)數(shù)據(jù)庫

輸入事務(wù)數(shù)據(jù)庫主要是將Web日志數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗、用戶識別和會話識別，這樣就可將Web日志數(shù)據(jù)轉(zhuǎn)換成了事務(wù)數(shù)據(jù)庫.Web日志包含網(wǎng)頁上所有多媒體元素，比如有后綴為.ico、.gif、.jpg、.css、.wmv、.swf等文件讀取的記錄，這些內(nèi)容與頻繁路徑挖掘無關(guān)，需要清洗掉;用戶識別主要是根據(jù)用戶的IP地址、瀏覽器類型或網(wǎng)站拓?fù)浣Y(jié)構(gòu)來判斷2條記錄是否是同一用戶的訪問行為;會話是用戶對網(wǎng)站的一次連續(xù)有效的訪問，表現(xiàn)形式就是訪問路徑序列，如果同一用戶先后請求的兩個頁面在規(guī)定的時間間隔內(nèi)，則這2個頁面屬于同一會話，因此，一個用戶對應(yīng)的訪問記錄可能對應(yīng)一條或多條會話記錄.

2.2 構(gòu)建訪問路徑樹

Web日志數(shù)據(jù)經(jīng)過數(shù)據(jù)預(yù)處理后，形成事務(wù)數(shù)據(jù)庫，如表1所示.對該數(shù)據(jù)庫的記錄逐條處理生成訪問路徑樹，該路徑樹每條從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑由一條或多條記錄構(gòu)成，如圖2所示.

表1 一個Web訪問事務(wù)數(shù)據(jù)庫

圖2 Web訪問路徑樹

Web訪問路徑樹除root節(jié)點(diǎn)外，其余各節(jié)點(diǎn)均代表頁面及該頁面出現(xiàn)的次數(shù)，分別用page和num表示.由Web訪問事務(wù)數(shù)據(jù)庫構(gòu)建Web訪問路徑樹采用孩子兄弟法存儲.

算法1 構(gòu)建Web訪問路徑樹.

2.3 生成最長前綴頻繁子路徑樹

路徑樹上節(jié)點(diǎn)的num值反映了該節(jié)點(diǎn)訪問的頻繁度，例如圖2中最左側(cè)分支中的節(jié)點(diǎn)p1的num值為3，反映了前綴為p2p1p3p1的訪問路徑有6條.若|事務(wù)數(shù)據(jù)庫 D|*N=3，那么由p2p1p3p1生成的P2P1、P1P3、P2P1P3、P3P1、P1P3P1 和 P2P1P3P1 均是頻繁路徑.根據(jù)這個思路，只要找到路徑樹上每條從根到葉子的路徑中的最長頻繁子路徑，就可以根據(jù)這些最長頻繁子路徑生成頻繁路徑.

從圖2可發(fā)現(xiàn)，若將所有的最長頻繁子路徑合成為一個樹，則該樹是圖2的子圖，并且該圖是原圖的上半部分.例如，若|D|*N=3，那么圖2所示的Web訪問路徑樹的所有最長頻繁子路徑合成的圖如圖3所示，不妨稱該圖為最長前綴頻繁子路徑樹.對此，先序遍歷Web訪問路徑樹，刪除num值少于|D|*N的節(jié)點(diǎn)所表示的子樹，即可生成最長前綴頻繁子路徑樹.

圖3 最長前綴頻繁子路徑樹

算法2 構(gòu)建最長前綴頻繁子路徑樹.

2.4 產(chǎn)生頻繁訪問路徑集

先考慮單支最長頻繁前綴子路徑產(chǎn)生頻繁訪問路徑集的過程，例如圖3中的路徑P2P1P3P1，表2是其挖掘過程.

表2 單支最長頻繁前綴子路徑產(chǎn)生頻繁訪問路徑的挖掘過程

頻繁訪問路徑集合frequentPS初始值為空，當(dāng)前訪問節(jié)點(diǎn)為P2，frequentPS1和frequentPS2為中間結(jié)果，初始值均為空.frequentPS1i=frequentPS2i-1∪frequentPS3i-1表示第i步的frequentPS1等于第i-1步的frequentPS2并上第i-1步的frequentPS3.當(dāng)某步驟中frequentPS2為空時程序結(jié)束.

對整棵最長前綴頻繁子路徑樹而言，可以遍歷出所有從根到葉子的路徑，再逐條路徑進(jìn)行產(chǎn)生頻繁訪問路徑，也可以根據(jù)有些路徑其前綴是相同的這一點(diǎn)設(shè)計算法，從而減少重復(fù)計算.

3 實(shí)驗(yàn)分析

在實(shí)驗(yàn)分析時，本研究采用DePual大學(xué)提供的標(biāo)準(zhǔn)數(shù)據(jù)集［10］，來自 DePaul CTI Web 服務(wù)器(http://www.cs.depaul.edu)數(shù)據(jù)的采集是隨機(jī)抽取在2002年4月2個星期中訪問這個網(wǎng)站的用戶.本實(shí)驗(yàn)采用cit.tra和cti.cod這2個數(shù)據(jù)集，cit.tra中包含了13 745條訪問路徑，這些路徑均由cit.cod中的683個頁面中的一個或多個組成.將每個頁面用一個整數(shù)標(biāo)志，那么訪問路徑序列也就轉(zhuǎn)換為一系列有序整數(shù).

相對傳統(tǒng)的Apriori算法，本研究所提算法不必進(jìn)行鏈接操作來生成頻繁項(xiàng)集，而是直接用最大頻繁項(xiàng)集來生成各子頻繁項(xiàng)集;相對文獻(xiàn)［6］來說，雖然都是利用了樹結(jié)構(gòu)，但文獻(xiàn)［6］中又將訪問路徑樹轉(zhuǎn)換成鄰接表，再通過鄰接表轉(zhuǎn)換為頻繁路徑，而本研究算法直接利用二叉樹進(jìn)行剪枝，減少了運(yùn)算過程中問題規(guī)模.比較而言，本研究所提算法的時空效率顯然具有明顯的優(yōu)勢.

本實(shí)驗(yàn)主要研究支持度N與葉子節(jié)點(diǎn)數(shù)、頻繁路徑數(shù)的關(guān)系，實(shí)驗(yàn)中除去了長度為1的頻繁路徑.實(shí)驗(yàn)所生成的頻繁路徑符合實(shí)際情況(見圖4)，從實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，0≤N≤6時，隨著支持度N的增加，葉子節(jié)點(diǎn)急劇減少，但再增加N的值，葉子節(jié)點(diǎn)緩慢變小，且最長前綴頻繁子路徑樹的葉子節(jié)點(diǎn)數(shù)目的關(guān)系也有類似的現(xiàn)象，同時還發(fā)現(xiàn)，支持度N為8的時候，可以將頻繁路徑條數(shù)控制在1 000以內(nèi).

圖4 支持度N與葉子節(jié)點(diǎn)數(shù)、頻繁路徑數(shù)的關(guān)系

4 結(jié)語

目前大多數(shù)Web日志頻繁訪問路徑挖掘算法可以歸為2類:類Apriori算法和訪問路徑樹算法.類Apriori算法運(yùn)算量大，需要多次掃描數(shù)據(jù)庫，中間結(jié)果非常占內(nèi)存;頻繁樹算法一般只需掃描一次事務(wù)數(shù)據(jù)庫，但需要多次構(gòu)建樹，空間消耗大，并且存在不能挖掘出連續(xù)可重復(fù)的頻繁訪問路徑的問題.本研究提出的算法屬于訪問路徑樹算法，構(gòu)建訪問路徑樹只需掃描一次事務(wù)數(shù)據(jù)庫，從上到下遍歷此樹各節(jié)點(diǎn)，刪除下端的非頻繁節(jié)點(diǎn)，即將該樹減枝成一棵最長前綴頻繁樹，再根據(jù)從根到葉的路徑生成頻繁路徑，保證了頻繁路徑與用戶訪問路徑是一致的.實(shí)驗(yàn)分析可以看出，支持度的變化對頻繁路徑數(shù)目的影響，當(dāng)支持度大于6時頻繁路徑數(shù)目變化趨于平緩，因此可以將6設(shè)置為大型網(wǎng)站頻繁訪問路徑挖掘算法支持度的經(jīng)驗(yàn)值.

:

［1］NLANR/NSF.IRCache Users guide［EB/OL］.［2008-03-18］.http://www.ircache.net/.

［2］韓家煒，孟小峰，王靜，等.Web挖掘研究［J］.計算機(jī)研究與發(fā)展，2001，38(4):405-413.

［3］Chen M S，Park J S，Yu P S.Data mining for path traversal patterns ina Web environment［C］//Proceedings of the16th International Conference on Distributed Computing Systems.Hong Kong:IEEE Press，1996:385-392.

［4］戰(zhàn)立強(qiáng)，劉大昕.基于訪問樹路徑的Web頻繁訪問路徑挖掘算法研究［J］.計算機(jī)應(yīng)用研究，2005(1):96-98.

［5］Agrawal R，Imielinski T，Swami A.Mining association rule between sets of items in large databases［C］//Proceedings of ACM SIG-MOD Conference on Management of Data(SIGMOD＇93).Washington，USA:ACM Press，1993:207-216.

［6］曹忠升，唐曙光，楊良聰.Web-Log中連續(xù)頻繁訪問路徑的快速挖掘算法［J］.計算機(jī)應(yīng)用，2006，1(26):216-219.

［7］翁偉.Web日志頻繁訪問路徑挖掘算法［J］.信息與電腦，2012(24):76-77.

［8］邢東山，沈鈞毅，宋擒豹.從Web日志中挖掘用戶瀏覽偏愛路徑［J］.計算機(jī)學(xué)報，2003，26(11):1518-1523.

［9］王思寶，李銀勝.基于Web日志挖掘用戶的瀏覽興趣路徑［J］.計算機(jī)應(yīng)用與軟件，2012，29(1):164-167.

［10］Mobasher B.Research Interests［EB/OL］.［2013-01-01］.http://maya.cs.depaul.edu/～ classes/ect584/resource.html.

Web Logs Mining Algorithm Based on Longest Prefix Frequent Sub-path Tree

WENG Wei，LIN Kaibiao，ZHU Shunzhi，WANG Zhenyue

(College of Computer and Information Engineering，Xiamen University of Technology，Xiamen 361024，China)

The existing web logs mining algorithm for frequent access path often can not accurately meet the users＇accessing order in pursuit of time efficiency.An efficient web logs mining algorithm for frequent access path is proposed，which converts the transaction database to web access path tree and prunes the tree branches to create the longest prefix frequent sub-path tree according to support degree，and then the mining process is implemented.The experiment confirms the effectiveness of this method，and analyzes the impact of the settings of frequent support degree on frequent paths generation.

web logs mining;frequent access path;WAP-tree

TP311.1

A

1004-5422(2013)03-0285-04

2013-05-28.

廈門市科技計劃高校創(chuàng)新課題(3502Z20123037)、福建省教育廳B類課題(JB09196)資助項(xiàng)目.作者簡介:翁 偉(1979—)，男，碩士，講師，從事知識發(fā)現(xiàn)與Web數(shù)據(jù)挖掘技術(shù)研究.