邱奕飛，馬 力

（西安郵電大學(xué) 計算機(jī)學(xué)院，陜西 西安 710061）

了解用戶的訪問行為，挖掘用戶偏愛的瀏覽模式，對于改善網(wǎng)站的系統(tǒng)設(shè)計，進(jìn)行合理的市場決策都具有十分重要的意義[1]。瀏覽模式，即某一個用戶于瀏覽器頻繁地對一系列地址的連續(xù)依次瀏覽所留下的軌跡。這種軌跡在很大程度上能夠反映該用戶本人對特定的“事物”、“活動”以及“人為對象”所產(chǎn)生的帶有傾向性、選擇性的態(tài)度、情緒和想法，即興趣。進(jìn)一步地，對用戶瀏覽軌跡的長期觀察，可以獲得用戶興趣的變化。一方面，從而過濾出該用戶固有的、長期的興趣點。另一方面，從而跟蹤用戶興趣的遷移軌跡，以研究、預(yù)判用戶的興趣遷移方向。

關(guān)聯(lián)規(guī)則領(lǐng)域的最經(jīng)典算法就是Apriori算法，是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。其核心是基于兩階段頻集思想的遞推算法，但是該算法在實際應(yīng)用時，存在著很多缺陷，比如需要多次掃描事務(wù)數(shù)據(jù)庫，需要很大的I/O負(fù)載，而且可能產(chǎn)生龐大的候選集[2]。GSP（Generalized Sequential Patterns，廣義序列模式）[3]算法是 Srikant和 Agrawal于1996年開發(fā)的一種序列模式挖掘算法。它是Apriori算法的原創(chuàng)性頻繁項集挖掘算法的擴(kuò)展。GSP采用多次掃描的候選產(chǎn)生-測試的方法生成序列模式。PNT（Preferred Navigation Tree，瀏覽偏愛樹）[4]是一種用來存儲用戶瀏覽信息的樹結(jié)構(gòu)。相比用戶會話期數(shù)據(jù)庫，該結(jié)構(gòu)占用較小的空間。但是這種結(jié)構(gòu)的挖掘往往會遺留那些不是由根節(jié)點出發(fā)的 “散落”的偏愛路徑，而無法全面地得到所有的偏愛瀏覽模式。

1 頻繁鏈表—存取樹的基本邏輯結(jié)構(gòu)

頻繁鏈表—存取樹結(jié)構(gòu)（Frequent Link and Access Tree，F(xiàn)LaAT）[5]，是wu等人提出的一種頻繁鏈表結(jié)合存取樹的結(jié)構(gòu)。為了完備地找到所有偏愛路徑，F(xiàn)LaAT采用類似PNT的樹結(jié)構(gòu)，外加一個頻繁鏈表。而頻繁鏈表配合next鏈（見下文）很好地捕捉了PNT所遺漏的偏愛模式。整個FLaAT總體上由一棵存取樹和一張頻繁鏈表組成。本文將用于存儲用戶訪問路徑的FLaAT結(jié)構(gòu)進(jìn)行了變形，變形后的用戶興趣FLaAT結(jié)構(gòu)如圖1所示。

圖1 用戶興趣FLaAT結(jié)構(gòu)圖Fig.1 User interest FLaAT structure

1.1 存取樹的基本結(jié)構(gòu)

存取樹事實上一種基于鏈表的結(jié)構(gòu)，換言之，整棵樹相當(dāng)于一個根節(jié)點本身。節(jié)點用于表示用戶瀏覽軌跡中所包含（途經(jīng)）的興趣點。每個節(jié)點包含6個屬性（此處僅介紹邏輯結(jié)構(gòu)）：interest、support、preference、child、younger以及 next。 其中：Interest即“興趣”，是指該節(jié)點所表示的興趣本身，即預(yù)定義的主題分類中的一個。support即“支持度”，是指截至當(dāng)前所統(tǒng)計到的，經(jīng)過該節(jié)點的瀏覽軌跡的總數(shù)。child即“孩子”，指向該節(jié)點的孩子節(jié)點。younger即“兄弟”，指向該節(jié)點的下一個兄弟節(jié)點。

事實上，在存取樹中，一個節(jié)點的“孩子們”是以：“孩子”、“孩子的兄弟”、“孩子的兄弟的兄弟”、“孩子的兄弟的兄弟的兄弟”......（下文稱“兄弟鏈”）的形式存在的。

preference意為“偏愛度”，定義如下：

定義2.0：平均訪問度f：設(shè)x為某節(jié)點。若x沒有孩子，則x.f不存在。若x有孩子y，則統(tǒng)計y的所有兄弟節(jié)點個數(shù)n（即沿y的兄弟鏈檢索直到某節(jié)點無兄弟節(jié)點為止）。那么，x的平均訪問度

定義2.1：偏愛度[6]p：設(shè)x為某非根節(jié)點。z為x的“父親”（即x是z的孩子，或者x在z的孩子的兄弟鏈上），那么，x的偏愛度

next指向下一個 “同類”節(jié)點 （即與該節(jié)點擁有相同interest之節(jié)點），具體意義將在1.2節(jié)中指出。

1.2 頻繁鏈表的基本結(jié)構(gòu)

頻繁鏈表事實上是一張向量表，其中每一個元素被稱為一個“組”（team）。組負(fù)責(zé)監(jiān)管整棵樹中某一個興趣分類。每一個組包含3個屬性 （此處僅介紹邏輯結(jié)構(gòu)）：interest、count以及first。其中：interest即“興趣”，是指該組所監(jiān)管的興趣分類。count即“計數(shù)”，是指該興趣在全局被訪問的總次數(shù)。first即“第一個”，是指從頻繁鏈表出發(fā)的，樹中第一個（未必是時間上）包含該興趣的節(jié)點。由于用戶瀏覽軌跡的多變性，同一個興趣點，可能分布在多條路徑上，即存在多個代表相同興趣的節(jié)點。first指向第一個該興趣節(jié)點，而被指向節(jié)點的next值為全局中下一個同興趣節(jié)點，以此類推。換言之，全局隸屬于同一個興趣分類的不同節(jié)點（至少一個），由頻繁鏈表中監(jiān)管該興趣的組中的first項發(fā)起，這些節(jié)點中的next值參與，共同搭建了一條形如“first-next-next...”的鏈表（下文稱“next鏈”）。這樣，通過頻繁鏈表的每一個組，都可以便利地檢索到全局所有該興趣的節(jié)點，大大降低了挖掘難度。next鏈的整體結(jié)構(gòu)如圖2所示。

2 FLaAT的構(gòu)建與更新算法

FLaAT即一張表和一棵樹。FLaAT的主體數(shù)據(jù)結(jié)構(gòu)是鏈表，而鏈表的特性使得整體結(jié)構(gòu)面臨增、改操作時所付出的代價極小。因此，在已經(jīng)處理完一批數(shù)據(jù)（即頻繁鏈表與樹結(jié)構(gòu)已經(jīng)完全建立）的情況下，F(xiàn)LaAT對后續(xù)新數(shù)據(jù)極其歡迎，這也十分符合FLaAT被用于長期增量式跟蹤挖掘工作的任務(wù)特性。

圖2 興趣“A”的next鏈Fig.2 The next chain of interest“A”

對于一個增量式的數(shù)據(jù)結(jié)構(gòu)，如果更新一次的過程就是“n+1”的過程，那么創(chuàng)建的過程就是 “0+1”的過程。因此FLaAT的更新算法與創(chuàng)建算法本質(zhì)上是統(tǒng)一的。

表1 FLaAT的更新算法Tab.1 Update algorithm of FLaAT

所有已經(jīng)獲得的用戶瀏覽軌跡被依次添加進(jìn)FLaAT中，同時，新獲取的軌跡也及時地更新之，使得整個FLaAT完整的記錄用戶的瀏覽行為。然而要得到用戶的偏愛瀏覽模式集，還需要對FLaAT進(jìn)行挖掘。

3 FLaAT的挖掘算法

對FLaAT的挖掘，主要目的就是從整棵存取樹中找出用戶相對比較頻繁地“走過”的路徑。事實上，我們需要一對閾值，來定義何為頻繁、何為偏愛。這對閾值正是support和preference，在FLaAT中，存取樹主要負(fù)責(zé)保存所有的瀏覽路徑的信息，而頻繁鏈表則主要用于挖掘。整體的挖掘工作就是從頻繁鏈表出發(fā)的。頻繁鏈表從全局的角度，按興趣不同進(jìn)行分類，橫向地、完整地跟蹤著所有節(jié)點。設(shè)想我們已經(jīng)獲取了7條瀏覽軌跡如下表：

表2 已經(jīng)得到的某網(wǎng)絡(luò)用戶的7條瀏覽軌跡Tab.2 A web user’s seven browsing tracks

表中的字母分別代表一個興趣分類。我們利用上述信息建立一個FLaAT如下圖：

圖3 建立完整的FLaAT結(jié)構(gòu)Fig.3 A complete FLaAT Structure established

我們不妨令 support閾值為 2，preference閾值為 0.5，開始挖掘我們從頻繁鏈表出發(fā)依次遍歷每一條next鏈，即每一個興趣分類（頻繁鏈表中count值達(dá)不到support閾值的分類在樹中不可能存在有價值的待挖掘瀏覽模式，故直接跳過，即在例子中，排除分類E、F）。只要簡單地檢測每一條分支便可得到符合要求的路徑：ABD、AC。但事實上，這樣做不完備。如果單純的比較每一個節(jié)點的閾值，往往會遺漏掉如GH這樣出現(xiàn)次數(shù)多但不集中的路徑。因此我們對于每一條next鏈都先要做一件事：把整個next鏈上的所有節(jié)點聚合到first所指向的第一個節(jié)點上。具體地，我們先將next鏈上所有的節(jié)點為根，逆向翻譯成原始興趣序列，然后調(diào)用FLaAT更新算法，將這些序列逐條添加到first所指向的第一個節(jié)點上，形成一棵以該節(jié)點為根的小型存取樹（如圖4）。

完成了以上工作之后，再檢測每一條分支便可得到符合要求的路徑。將以上工作依次執(zhí)行于所有興趣分類上，所得解為完備解。該挖掘算法具體如下：

圖4 同類合并算法Fig.4 Similar merging algorithm

該算法的時間復(fù)雜度與序列中的元素個數(shù)成線性比例關(guān)系，在這一點上，與GSP算法持平。

表3 FLaAT頻繁模式挖掘算法Tab.3 Frequent pattern mining algorithms of FLaAT

4 實驗分析

本文的實驗數(shù)據(jù)集是使用Winpcap在局域網(wǎng)中捕獲用戶一個月以來所發(fā)送的數(shù)據(jù)包，然后提取出其中有效的URL，接著依據(jù)這些URL使用網(wǎng)頁爬蟲程序取得的用戶瀏覽網(wǎng)頁。通過對捕捉到的瀏覽頁面進(jìn)行URL分析匯總后得到712個瀏覽頁面，分析后取了其中的302個有用頁面進(jìn)行挖掘，分別編號為1，2，…，302。實驗條件如下：

處 理 器 ：Intel Core i7-3612QM； 內(nèi) 存 ：8.00GB；OS：windows7；平臺：Java version1.7。

將基于FLaAT結(jié)構(gòu)的序列挖掘與傳統(tǒng)的序列挖掘模式算法GSP算法進(jìn)行比較，在相同規(guī)模的數(shù)據(jù)集中分別采用兩種方法進(jìn)行序列挖掘，然后不斷擴(kuò)大數(shù)據(jù)集規(guī)模，多次進(jìn)行實驗，分別比較兩種挖掘算法的準(zhǔn)確性和耗時。比較結(jié)果如圖5，圖6所示。

圖5為兩種算法挖掘結(jié)果準(zhǔn)確性比較圖。在比較時，將兩種算法的支持度閾值同時設(shè)為4，由圖可以看出兩種算法在挖掘時的準(zhǔn)確性沒有很大的差距，由于GSP算法最終挖掘的序列中只保留最長模式的序列，所以有一些頻繁的子序列就會被GSP算法丟棄，隨著數(shù)據(jù)規(guī)模的增大，GSP算法的挖掘結(jié)果準(zhǔn)確性下降幅度增大。

圖5 準(zhǔn)確性比較Fig.5 Comparison of the accuracy

圖6 耗時比較Fig.6 Comparison of time-consuming

圖6 是兩種算法的耗時比較圖。由圖中可以看出，由于GSP算法在挖掘過程中需要不斷的對數(shù)據(jù)庫重復(fù)掃描，所以當(dāng)數(shù)據(jù)集規(guī)模不斷增大時，算法執(zhí)行需要的時間增長的很快，而基于FLaAT結(jié)構(gòu)的挖掘，每當(dāng)數(shù)據(jù)集規(guī)模擴(kuò)大時，只需要對FLaAT進(jìn)行更新即可，隨著數(shù)據(jù)集規(guī)模的擴(kuò)大，執(zhí)行時間的增長明顯較為緩慢。

5 結(jié) 論

文中將頻繁鏈表-存取樹結(jié)構(gòu)應(yīng)用于web瀏覽模式的挖掘領(lǐng)域，實現(xiàn)了更新與挖掘算法，并對該算法的效率和準(zhǔn)確度等性能和GSP算法進(jìn)行了比較研究。

任何時刻，我們通過挖掘所得的偏愛瀏覽模式集，只能夠反映用戶截至當(dāng)前的興趣分布狀況。后續(xù)得到的新的瀏覽軌跡包含著用戶興趣的遷移狀況。為此，以捕獲用戶瀏覽軌跡的定期性和長期性為前提，我們可以定義一個“有效時段”，即在過去的N天內(nèi)的瀏覽軌跡為有效軌跡。這樣，F(xiàn)LaAT在不斷更新的同時，須刪除N天之前的軌跡（參照更新算法），然后進(jìn)行挖掘，并更新用戶偏愛瀏覽模式集。如此，能夠常駐偏愛集的瀏覽模式即該用戶的長期固有興趣；而不斷變化的部分可作為參考以研究用戶興趣變化方向。

[1]LI Yu-xia，LI Hong-yu.Data Mining Algorithm of Browsing Pattern Based on Web Log.Knowledge Acquisition and Modeling， 2011 Fourth International Symposium [C].2011.88:307-311.

[2]劉宏強(qiáng).Apriori關(guān)聯(lián)規(guī)則挖掘算法分析與改進(jìn)[J].中國石油大學(xué)勝利學(xué)院學(xué)報，2009，23（7）:17-19 LIU Hong-qiang.Analysis and improvement of apriori association rule mining algorithm[J].Journal of Shengli College China University of Petroleum，2009，23（7）:17-19.

[3]陳卓，楊炳儒.序列模式挖掘綜述[J].計算機(jī)應(yīng)用研究，2008，25（7）:1961-1976.CHEN Zhuo，YANG Bin-ru.Summary of sequential pattern mining[J].Application Research of Computers，2008，25（7）:1961-1976.

[4]Xing D，Shen J.Efficient Data Mining for Web Navigation Pattern[J].Information and Software Technology，2004（46）:55-63.

[5]吳瑞，張秀玲.基于FLAAT的加權(quán)偏愛模式的挖掘算法[J].計算機(jī)工程與應(yīng)用，2005，41（19）:182-184.WU Rui，ZHANG Xiu-ling.Mining algorithm based on a weighted preference patterns FLAAT[J].Computer Engineering and Applications，2005，41（19）:182-184.

[6]Attwood T K，Parry-S D J mith.生物信息學(xué)概論[M].羅靜初等譯.北京:北京大學(xué)出版社.2002.