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

翁 偉，林開標，朱順痣，王震岳

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

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

翁 偉，林開標，朱順痣，王震岳

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

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

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

0 引言

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

1 相關概念

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

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

定義2 Web訪問事務數據庫由某一時間區間的會話集合構成，每一條會話為該數據庫中的一條記錄，也稱事務，事務由項目構成.

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

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

定義4 如果一條訪問路徑q=〈pk，pk+1，…，pk+n〉是路徑p=〈pj，pj+1，…，pj+m〉(m?n)的子路徑，并且k=j，那么稱q為p的前綴子路徑.類似可以定義后綴子路徑，若q是頻繁的，則稱q是p的頻繁前綴子路徑，進一步，如果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中每條路徑之積的結果集.

2 算法描述

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

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

2.1 輸入事務數據庫

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

2.2 構建訪問路徑樹

Web日志數據經過數據預處理后，形成事務數據庫，如表1所示.對該數據庫的記錄逐條處理生成訪問路徑樹，該路徑樹每條從根節點到葉子節點的路徑由一條或多條記錄構成，如圖2所示.

表1 一個Web訪問事務數據庫

圖2 Web訪問路徑樹

Web訪問路徑樹除root節點外，其余各節點均代表頁面及該頁面出現的次數，分別用page和num表示.由Web訪問事務數據庫構建Web訪問路徑樹采用孩子兄弟法存儲.

算法1 構建Web訪問路徑樹.

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

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

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

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

算法2 構建最長前綴頻繁子路徑樹.

2.4 產生頻繁訪問路徑集

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

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

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

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

3 實驗分析

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

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

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

圖4 支持度N與葉子節點數、頻繁路徑數的關系

4 結語

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

:

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

［2］韓家煒，孟小峰，王靜，等.Web挖掘研究［J］.計算機研究與發展，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］戰立強，劉大昕.基于訪問樹路徑的Web頻繁訪問路徑挖掘算法研究［J］.計算機應用研究，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中連續頻繁訪問路徑的快速挖掘算法［J］.計算機應用，2006，1(26):216-219.

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

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

［9］王思寶，李銀勝.基于Web日志挖掘用戶的瀏覽興趣路徑［J］.計算機應用與軟件，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.

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