基于序列前綴技術的XML頻繁路徑挖掘算法①

張 潔,毛國君

(中央財經(jīng)大學 信息學院,北京 100081)

XML是可擴展標記語言(eXtensible Markup Language)的簡稱,已經(jīng)成為許多領域中數(shù)據(jù)交換、數(shù)據(jù)表示、數(shù)據(jù)存儲的事實標準.面對海量且不斷產生的XML文檔,人們迫切需要從中發(fā)現(xiàn)有價值的信息和知識,研究人員正在探索尋找合適的技術來解決與XML文檔存儲和分析相關的問題.

XML數(shù)據(jù)挖掘可分為XML文檔結構挖掘和XML文檔內容挖掘.結構挖掘的主要目標是挖掘XML模式,可以分為結構內挖掘(挖掘一篇XML文檔內的結構)和結構間挖掘(挖掘多篇XML文檔之間的結構).挖掘出的頻繁模式,可在XML分類、XML聚類、XML索引、XML數(shù)據(jù)存儲、XML數(shù)據(jù)壓縮、XML查詢、XML數(shù)據(jù)預測等多個XML相關領域獲得應用.例如:通過用戶訪問模式挖掘改善網(wǎng)站架構;將頻繁查詢作為結果緩存加快XML查詢效率;通過挖掘XML格式的訂單數(shù)據(jù)進行消費者行為分析;使用頻繁路徑作為特征向量來估量XML文檔相似性從而用于XML文檔分類、聚類.XML文檔的結構信息可以通過解析表示在標簽序列中,因此,我們可以將XML文檔樹序列化,借鑒序列挖掘算法對XML文檔進行相應的頻繁模式挖掘.

由于XML特殊的結構特點和表達含義,對XML數(shù)據(jù)的挖掘具有更多的挑戰(zhàn)性和創(chuàng)新性.首先,XML本質上是基于樹結構的,傳統(tǒng)的關系型數(shù)據(jù)庫的數(shù)據(jù)挖掘方法不能直接被利用;其次,XML的結構和文本內容一體化,現(xiàn)有的方法還是以單獨挖掘結構或者文本內容信息為主,缺乏一體化的解決方案;最后,隨著大數(shù)據(jù)時代的到來,從因特網(wǎng)上獲取XML文檔成為主流應用,因此找到代價(如內存資源)和精度平衡的解決方法成為重要任務之一.本文提出一種XML文檔序列的頻繁路徑挖掘算法PXFP(PrefixSpan-based mining for XML Frequent Paths).它通過對XML文檔的序列化來形成基于前綴技術的序列模式挖掘工作,期望獲得更高的時間和空間效率.

1 相關工作

序列模式挖掘問題是最初由Agarwal等人[1]開創(chuàng)性提出,Agarwal等人借鑒頻繁項目挖掘算法提出了AprioriAll算法,該算法基于先產生后測試的策略,依據(jù)的原理是所有頻繁序列的子序列也都是頻繁的.1996 年,Srikant 和 Agrawal 又提出了 AprioriAll 算法的擴展算法 GSP 算法[2],它考慮了時間約束、滑動時間窗口和分類層次技術,從而大大地減少了產生的候選序列的數(shù)量,減少了時間和空間開銷.然而由于類Apriori 算法自身存在的局限性,學者們紛紛開始尋找更高效的方法.2000 年,Han 等人提出了基于模式增長的 FP-growth 算法,該算法不產生候選集,而是通過FP-tree 的樹狀結構壓縮數(shù)據(jù)庫,然后再利用 FP-tree 從下向上挖掘頻繁序列,加快了挖掘過程[3].其后,學者們又研究并提出了一系列基于前綴思想的算法,包括 Han和 Pei 于 2000 年提出的 FreeSpan 算法[4]和 2001 年提出的PrefixSpan算法[5],其基本思想是:遞歸地將當前挖掘的頻繁序列作為前綴,計算每一前綴的后綴,生成投影數(shù)據(jù)庫,在每個投影數(shù)據(jù)庫上進行子序列的增長.這一過程將每一次的檢驗范圍縮小到更小的投影數(shù)據(jù)庫中,降低了搜索代價.這些都是經(jīng)典的序列挖掘算法.

近年來,在經(jīng)典序列挖掘算法的基礎上,學者們相繼提出了優(yōu)化的序列挖掘算法.2007年,張坤等人針對PrefixSpan算法存在大量重復投影數(shù)據(jù)庫的問題,提出一種名為SPMDS的算法[6]運用哈希值判斷投影數(shù)據(jù)庫是否重復,通過建立索引加快了檢索速度,進而提高了算法的性能.2009年,張利軍等提出一種基于位置信息的序列模式挖掘算法PVS[7],在PrefixSpan算法的基礎上,通過記錄每個已產生的投影數(shù)據(jù)庫的位置信息降低投影數(shù)據(jù)庫的冗余,提高了算法效率.2012年,劉棟等提出了基于Map Reduce的序列挖掘模式,采用Hadoop分布式平臺,將PrefixSpan算法擴展到大數(shù)據(jù)集[8].2013年,吳信東等設計了一種帶有通配符的模式挖掘算法,通配符的加入使模式的形式更加靈活[9];2015年,劉端陽等首次在頻繁序列模式挖掘算法中引入邏輯的思想,提出了一種基于邏輯的頻繁序列挖掘算法LFSPM,通過邏輯規(guī)則對中間結果進行過濾,該算法較好地解決了支持度閥值的設定問題,并提高了挖掘結果的可理解性[10].2015年,Kaustubh Beedkar等提出了用于挖掘具有層次結構的頻繁序列的并行算法[11],并將其設計為可以擴展到大數(shù)據(jù)集.

XML頻繁模式挖掘作為XML數(shù)據(jù)挖掘的重要研究方向之一,也獲得了許多學者的關注.2005年,Leung Ho-pong等人提出的PBClustering算法將頻繁路徑作為特征向量來計算XML文檔的相似度[12],從而進行聚類.其中頻繁路徑挖掘的具體方法是將每個XML文檔樹表示為Xpath路徑集合,然后利用AprioriAll序列挖掘算法來挖掘XML文檔集的頻繁路徑.2008年,貝毅君提出了基于等價類的頻繁標簽序列挖掘算法XSM[13],該算法將XML序列構建成垂直數(shù)據(jù)庫,通過應用概念格理論、以不同前綴為基礎將標簽序列分成互不相交的前綴等價類,通過合并等價類產生頻繁標簽序列,遞歸地從等價類中挖掘頻繁標簽序列,該算法在實驗數(shù)據(jù)集中取得了較好的時間性能.2012年,雷向欣等提出了數(shù)據(jù)流分頁頻繁子樹挖掘模型Tmlist[14],對XML數(shù)據(jù)流進行分頁,管理跨頁節(jié)點及頻繁候選子樹的跨頁增長,逐頁挖掘頻繁子樹,在可控誤差范圍內降低了空間消耗,提高了挖掘效率.2013年,李巍等提出了一種根據(jù)XML數(shù)據(jù)變化過程挖掘XML空間頻繁變化結構SFCS的方法和發(fā)現(xiàn)SFCS的數(shù)據(jù)模型SC-DOM[15],實驗證明了算法的有效性和可擴展性.

2 相關的定義

定義1.XML樹模型.一個XML文檔的結構使用樹XT(r,V,E,L,f)來表示.其中,r是樹的根節(jié)點;V是樹的節(jié)點集合;E是樹的邊集合,每條邊(v1,v2)∈E表示節(jié)點v1是節(jié)點v2的父節(jié)點;L表示標簽集合;f是從節(jié)點集合到標簽集合的一個函數(shù)映射f:V-＞L.

例子1.圖1給出了一個XML文檔對應的樹結構,其中:它的根節(jié)點r=n1;樹的節(jié)點集合V={n1,n2,n3,n4,n5,n6,n7,n8,n9};邊集合E={(n1,n2),(n2,n3),(n2,n4),(n2,n5),(n3,n6),(n4,n7),(n5,n8),(n5,n9)};樹的標簽集合L={a,b,c,d,e,f,g};節(jié)點集合到標簽集合的一個函數(shù)映射 f:{n1-＞ a,n2-＞ b,n3-＞ c,n4-＞ e,n5-＞ e,n6-＞ d,n7-＞ f,n8-＞ f,n9-＞ g}.

圖1 XML文檔樹模型示例

定義2.XML樹的標簽序列表示.對XML文檔樹進行廣度優(yōu)先遍歷,即按層序從左到右輸出XML樹的每個節(jié)點的標簽,得到XML樹的標簽序列被稱為該XML樹的標簽序列表示.

例子2.圖1中XML樹的標簽序列表示為＜a,b,(c,e,e),(d,f,f,g)＞.注:同層如果有多個標簽用括號括起來,如果只有一個標簽,括號可以省略.

定義3.XML樹的標簽路徑.XML樹的一個標簽序列被表示為A=＜a1,a2,...,an＞.假如在A中ai均是ai+1的父節(jié)點(0＜i＜n),則稱序列A為該XML樹的一條標簽路徑.

例子 3.對應圖 1 中 XML 樹,＜a,b,c,d＞,＜a,b,e,f＞和＜a,b,e,g＞都是它的標簽路徑.

定義 4.前綴路徑.對于路徑 A=＜a1,a2,...an＞和序列 B=＜b1,b2,...bm＞,n≤m,滿足 a1b1,a2b2,...,anbn,則稱A是B的一個前綴路徑,簡稱前綴.

例子4.對于標簽序列數(shù)據(jù)B=＜a,b,(c,e,e),(d,f,f,g)＞.依據(jù)定義 4 可知:路徑 A=＜a,b,c,d＞是 B 的前綴,但是C=＜a,c,d＞不是B的前綴.當然B的前綴不止一個,比如＜a＞,＜a b＞,＜a b c＞,＜a b e＞,＜a b e f＞,＜a b e g＞也都是B的前綴.

定義5.直接后綴.路徑A={a1,a2,...an}是序列B={b1,b2,...bm}的前綴,當n＜m時,bn+1中an的子節(jié)點的集合被稱為A在B上的直接后綴;當n=m時,A在B上的直接后綴為空.

例子 5.在圖 1 中,令 A=＜a,b,c＞,B= ＜a,b,(c,e,e),(d,f,f,g)＞,則 A 在 B 上的直接后綴為＜d＞.這是因為在圖1中,＜(d,f,f,g)＞中只有d是c的子節(jié)點.

定義6.位置信息.一個路徑A={a1,a2,...an}在一個XML樹中的位置信息用一個3元組來表示,記為(s,v,m),其中s表示XML標簽序列數(shù)據(jù)庫S中包含該路徑的序列的序號;v表示對應的序列中該路徑的結束位置為XML樹的第幾層;m表示該路徑的結束位置在XML樹該層的第幾個.當一個路徑在數(shù)據(jù)庫中多次出現(xiàn)時,這個路徑的位置信息表示為向量((s1,v1,m1),(s2,v2,m2),…,(sk,vk,mk)).

例子6.對于圖1(假設數(shù)據(jù)庫中只有圖1所示一篇XML文檔),路徑A=＜a,b,c＞的位置信息可以表示為(1,3,1);路徑B=＜a,b,e,f＞的位置信息可分別表示為(1,4,2),(1,4,3).

3 PXFP算法

3.1 從XML文檔集中挖掘頻繁路徑的基本步驟

XML文檔是半結構化數(shù)據(jù),對其進行頻繁路徑挖掘可以分為兩步:XML文檔序列化和序列挖掘,基于此將從XML文檔集中挖掘頻繁路徑的過程劃分為五個階段,如圖2所示.

圖2 從XML文檔集中挖掘頻繁路徑的基本步驟

(1)序列化階段:依據(jù)XML文檔的樹形結構和定義2得到XML標簽序列.此外為了不遺漏XML文檔樹的結構信息,將每個節(jié)點表示為“節(jié)點:父節(jié)點”的形式(根節(jié)點除外),最終實現(xiàn)XML文檔的序列化,作為數(shù)據(jù)挖掘的格式化數(shù)據(jù)來用于分析.

(2)頻繁節(jié)點階段:找出支持度不小于閥值的頻繁節(jié)點,構造Hash映射表,將頻繁節(jié)點標簽與數(shù)字一一對應.

(3)轉化階段:將頻繁節(jié)點根據(jù)Hash表映射為數(shù)字同時去掉不頻繁的節(jié)點,得到轉化后的序列數(shù)據(jù)庫作為頻繁路徑挖掘階段算法的輸入.

(4)頻繁路徑挖掘階段:本文將設計PXFP算法來完成這一工作.算法的整體思想是:首先掃描數(shù)據(jù)庫來獲取1階頻繁序列L1,假設L1={1,2,3,4},然后依次以L1中的元素為前綴遞歸挖據(jù)頻繁序列…深度優(yōu)先直到不再有更長的前綴產生時,再以2為前綴…以此類推,直到遍歷過L1中所有元素后停止.規(guī)范化的算法描述見4.2節(jié).

(5)最大頻繁路徑階段:去除頻繁路徑中包含于其他頻繁路徑中的子路徑,得到最大頻繁路徑.

下面以一個實例來介紹XML頻繁路徑的挖掘過程.給定3個待挖掘的XML文檔樹,如圖3所示,令支持度閥值為0.5.

圖3 待挖掘的XML文檔樹

(1)序列化階段

對各個XML文檔樹進行層序遍歷,即按照廣度優(yōu)先的策略按層序從左到右輸出XML樹的每個節(jié)點.如圖3中的XML樹(1),order(第一層)(person,item)(第二層)(name,address,book)(第三層).得到的XML標簽序列集合如表1所示,該集合表示出了XML樹的層級關系.

表1 XML文檔的序列化表示

此外,為了不遺漏XML文檔樹的結構信息,需要將XML文檔樹的邊,即父子節(jié)點間的對應關系表示在序列中.由于每一個節(jié)點都有且只有一個父節(jié)點(根節(jié)點除外),因此把每個節(jié)點表示為“節(jié)點:父節(jié)點”的形式(根節(jié)點除外).例如:對于XML樹(1),其標簽序列表示為＜order,(person,item),(name,address,book)＞,序列化的結果為 ＜order,(person:order,item:order),(name:person,address:person,book:item)＞.可以用同樣的方式處理另外兩個XML文檔樹,表1給出了序列化的結果.

(2)頻繁節(jié)點階段

很顯然,一個頻繁路徑中的所有節(jié)點必須頻繁,所以發(fā)現(xiàn)頻繁節(jié)點是挖掘頻繁路徑的基礎性工作.這個階段相對比較簡單,只需要找出所有支持度不小于50%的節(jié)點即可.這里的支持度是指出現(xiàn)該路徑的文檔數(shù)與總文檔數(shù)的比值.實際操作中,將頻繁節(jié)點映射成連續(xù)的整數(shù),結果如表2所示,這樣的映射純粹是為了處理的方便和高效,減少內存空間的占用.

表2 支持度不小于50%的頻繁節(jié)點

(3)轉換階段

根據(jù)前一階段得到的頻繁節(jié)點集,構造Hash映射表,將頻繁節(jié)點的標簽與數(shù)字一一對應,將頻繁節(jié)點根據(jù)Hash表映射為數(shù)字同時去掉不頻繁的節(jié)點得到轉換后的序列,如表3所示.這樣做可以減少XML文檔標簽序列集的表示空間,并加快后面的挖掘速度.

表3 轉換后的序列數(shù)據(jù)庫

(4)頻繁路徑挖掘階段

將上一階段得到的轉換后的序列數(shù)據(jù)庫作為頻繁路徑挖掘階段算法的輸入,調用序列挖掘算法找出所有可能的頻繁路徑.本文將設計PXFP算法來完成這一工作.我們先通過本例來說明PXFP的基本思想,規(guī)范化的算法描述將在4.2節(jié)來完成.

頻繁路徑挖掘階段采用的算法是基于前綴的思想,首先找到長度為 1 的前綴,包括＜1＞,＜2＞,＜3＞,＜4＞,＜5＞,＜6＞,我們需要對這6個前綴分別遞歸搜索各個前綴對應的頻繁路徑.依據(jù)表3的序列數(shù)據(jù)庫,表4是長度為1的前綴對應的直接后綴.

表4 長度為1的前綴的直接后綴

這里我們以前綴＜1＞為例來說明挖掘過程,對其他前綴進行遞歸的方法和前綴＜1＞一樣.方法如下,首先統(tǒng)計＜1＞的直接后綴的出現(xiàn)次數(shù)得到{2:3,3:3}.由于此時＜2＞,＜3＞均滿足支持度閾值,因此我們得到前綴為＜1＞的 2 階頻繁路徑為＜12＞和＜13＞,并記錄下＜12＞的位置信息為(1,2,1)(2,2,1)(3,2,1),＜13＞的位置信息為(1,2,2)(2,2,2)(3,2,2).接著我們分別遞歸＜12＞和＜13＞為前綴所對應的直接后綴.首先看＜12＞前綴,由＜12＞的位置信息找到其對應的直接后綴為＜(45)＞,＜4＞,＜4＞,進行計數(shù)得到{4:3,5:1},因此得到以＜12＞為前綴的3階頻繁路徑為＜124＞,并更新＜124＞的位置信息為(1,3,1)(2,3,1)(3,3,1).由＜13＞的位置信息找到其對應的直接后綴為＜6＞,＜6＞,＜6＞,進行計數(shù)得到{6:3},因此得到以＜13＞為前綴的3階頻繁路徑為＜136＞,并記錄下＜136＞的位置信息為(1,3,3)(2,3,2)(3,3,2).繼續(xù)遞歸以＜124＞和＜136＞為前綴的頻繁路徑.由于前綴＜124＞和＜136＞對應的直接后綴為空,因此不能產生4階頻繁路徑.至此以1為前綴的頻繁路徑挖掘結束,產生的頻繁路徑為＜1＞＜12＞＜13＞＜124＞＜136＞.同樣的方法可以得到其他前綴對應的頻繁路徑.頻繁路徑挖掘結果如表5所示.

表5 頻繁路徑挖掘結果

(5)最大頻繁路徑階段

去除頻繁路徑中包含于其他頻繁路徑中的子路徑,得到最大頻繁路徑.根據(jù)Hash表找到原始的最大頻繁路徑,結果如表6所示.

表6 最大頻繁路徑

3.2 算法描述

PXFP算法是基于序列前綴的XML頻繁路徑挖掘算法,其目標是挖掘XML序列數(shù)據(jù)庫中滿足支持度閥值的頻繁路徑.下面我們對PXFP算法做一個歸納總結.

算法.PXEP 算法輸入:序列數(shù)據(jù)庫S和支持度閾值αα輸出:所有滿足支持度要求的頻繁路徑集1)掃描序列數(shù)據(jù)庫,找到所有長度為1的序列模式L1,作為初始的種子集;2)對于L1中的每一個元素,依次取出一個元素作為新候選模式的前綴,以此來劃分搜索空間;3)令前綴的長度i=1;4)對于每個長度為i且滿足支持度要求的前綴進行遞歸挖掘:a)找出前綴所對應的直接后綴,并記錄其位置信息.如果直接后綴為空,則遞歸返回.

b)計算直接后綴中各項的支持度.如果所有項的支持度小于閾值αα,則刪除其位置信息并遞歸返回.c)將滿足支持度閥值的各個單項和當前的前綴進行合并,令i=i+1,得到若干新的前綴,將其加入長度為i的序列模式Li分別遞歸執(zhí)行第4)步.5)重復2)–4),直到遍歷完L1中的所有序列.

值得注意的是,與從單個XML文檔中挖掘關鍵模式不同,在多XML文檔頻繁路徑的挖掘中,如果某節(jié)點在前綴所對應的直接后綴中多次出現(xiàn),仍然只計數(shù)一次,但位置信息都要記錄下來.

3.3 算法偽代碼

基于如上分析,PXFP算法的偽代碼描述如下.

算法.PXEP算法輸入:序列數(shù)據(jù)庫S;最小支持度min-sup輸出:S的頻繁路徑KS 1.scan S to get L1;//掃描數(shù)據(jù)庫找到所有的頻繁1-序列2.FOR m=0 TO L1.size()//依次遍歷L1中的每個序列3. FOR father_node=L1.get(m)TO longest subsequence//由1階前綴向高階擴展4. FOR n=1 TO S.size();//在各個XML文檔集標簽序列中5. child_node[]=father.getchild();//(根據(jù)位置信息)找到子節(jié)點即直接后綴6. save or update Position of subsequence;//記錄或更新位置信息7. Calculate support of every child_node occur in S;//計算子序列支持度8. IF(support ＞=min_sup)//大于等于最小支持度為頻繁模式9. subsequence=father_node+child_node;10. add subsequence to KS;11.ELSE 12. delete Position;//小于最小支持度刪除位置信息13.Retrun KS //輸出所有頻繁路徑

4 實驗與分析

本部分實驗1的數(shù)據(jù)來源于圖3,實驗2和實驗3的數(shù)據(jù)來源于INEX XML挖掘競賽(XML Document Mining Challenge)中結構挖掘部分的電影數(shù)據(jù)集[16],這是從11個網(wǎng)站得到的XML文件.

實驗的計算機采用的配置為:4 GB內存、英特爾酷睿i3,1.40 GHz處理器、Windows 7操作系統(tǒng)、Myeclipse運行環(huán)境.采用的對比算法是同樣基于前綴的PrefixSpan算法.實驗的目標主要是檢測PXFP算法的空間效率和時間效率.

實驗1.比較內存空間使用情況

由于PXFP算法不需要產生投影數(shù)據(jù)庫,而只記錄直接后綴的位置信息,因此占用更少的內存.實驗1利用PrefixSpan算法和PXFP算法對圖3中的3個XML文檔序列化后得到的序列數(shù)據(jù)進行分析,每一步的內存占用如表7所示.由于兩個算法都是基于前綴的分治思想,因此表7中先討論以1階頻繁序列為前綴的情況,最后再從總體上進行討論.

表7 PrefixSpan算法和PXFP算法的內存使用情況

從表7的實驗結果可以看出,無論利用分治的思想在每一個小范圍內討論,還是從總體上考慮最大內存使用和合計內存使用情況,PXFP算法的空間效率都要好于PrefixSpan算法.雖然PXFP算法需要記錄較多的位置信息,但由于每個位置信息僅占用3個字符的內存,相比于PrefixSpan算法投影數(shù)據(jù)庫中的子序列相比,仍然有優(yōu)勢.

圖3中XML文檔的數(shù)量少,并且每個XML文檔的節(jié)點數(shù)少,當應用于實際中的XML文檔集時,PrefixSpan算法將產生更多的投影數(shù)據(jù)庫,因而PXFP算法的空間優(yōu)勢將會更明顯.

實驗2.比較不同支持度閥值下的執(zhí)行時間

利用實驗數(shù)據(jù)集,在兩個支持度區(qū)間進行實驗,分別是:①小支持度區(qū)間(5%–30%);②大支持度區(qū)間(10%-90%),對比本文提出的 PXFP算法和PrefixSpan算法的運行時間.表8給出的是實驗數(shù)據(jù)在小支持度區(qū)間范圍內挖掘出的頻繁路徑的個數(shù),圖4對應給出在該區(qū)間內PrefixSpan算法和PXFP算法運行時間的對比;表9給出的是實驗數(shù)據(jù)在大支持度區(qū)間范圍內挖掘出的頻繁路徑的個數(shù),圖5對應給出在該區(qū)間內PrefixSpan算法和PXFP算法運行時間的對比.

由表8和圖4可以看出,在小支持度區(qū)間,實驗數(shù)據(jù)集產生較多的頻繁路徑,隨著支持度閥值增大,PXFP算法和PrefixSpan算法的執(zhí)行時間都在縮短,原因在于隨著支持度閥值的增加,生成的各階頻繁路徑在減少,并且在該數(shù)據(jù)集中,頻繁路徑減少的速度很快.同時也可以看出,PXFP算法處理XML文檔標簽序列的時間效率明顯高于PrefixSpan算法.

表8 小支持度區(qū)間內挖掘出頻繁路徑個數(shù)

圖4 小支持度區(qū)間內算法時間效率對比

表9 大支持度區(qū)間內挖掘出頻繁序列個數(shù)

圖5 大支持度區(qū)間內算法時間效率對比

表9和圖5從更宏觀、更全面的角度進行實驗,展現(xiàn)了最小支持度在更大范圍內變化時兩算法的執(zhí)行效率對比.實驗結果表明:隨著支持度閥值增大,PXFP算法和PrefixSpan算法的執(zhí)行時間都在下降,同時,PXFP算法在各支持度下的時間效率都要明顯高于PrefixSpan算法.其中,最小支持度在10%–30%的范圍內變化時,由于挖掘出的頻繁子路徑數(shù)量減少速度很快,因此算法執(zhí)行時間下降速度很快;最小支持度在40%–70%的范圍內,頻繁子序列數(shù)量減少速度相對較慢,因此挖掘算法的執(zhí)行時間降速放緩;然而,在70%及以上的支持度下,由于此時已經(jīng)不再有頻繁模式被挖掘出來,算法執(zhí)行時間再一次驟減,并且由于兩算法在掃描一次數(shù)據(jù)庫后基本不用再進行后面的循環(huán),因此兩算法的運行時間都趨于0,PXFP算法的優(yōu)勢也不如產生大量頻繁子路徑時明顯.

實驗3.比較不同XML文檔數(shù)下的執(zhí)行時間

創(chuàng)建XML數(shù)據(jù)集,其中存放的XML文檔數(shù)量由1000,2000,3000,逐漸遞增至10000.控制支持度閥值為20%,對該數(shù)據(jù)集進行頻繁路徑挖掘,考察隨著XML文檔數(shù)量,即標簽序列數(shù)量攀升的情況下,兩算法的執(zhí)行效率.實驗結果如圖6.

圖6 標簽序列數(shù)量增加時執(zhí)行時間的比較

圖6表明,在固定的支持度閥值下,隨著XML文檔數(shù)據(jù)集規(guī)模的增大,即標簽序列數(shù)量的增加,PXFP算法和PrefixSpan算法的執(zhí)行時間在攀升.在數(shù)據(jù)量較小的情況下,兩算法的運行時間效率相差不多,隨著數(shù)據(jù)量不斷增加,PXFP算法執(zhí)行時間上的優(yōu)勢在增大,特別地,當序列數(shù)量為10 K時,PXFP算法所需要的時間幾乎是PrefixSpan算法運行時間的60%,并且可以預見的是,當數(shù)據(jù)量更大時,PXFP算法的優(yōu)勢將更加明顯.因此可以得出結論,在任何數(shù)據(jù)量下,PXFP算法有高于PrefixSpan算法的執(zhí)行效率,并且數(shù)據(jù)量越大,PXFP算法的優(yōu)勢越明顯.

5 總結

本文中提出了基于序列前綴技術的XML頻繁路徑挖掘算法—PXFP算法.PXFP算法結合了序列前綴、位置信息等思想及XML樹形結構特征,用于從XML文檔集中挖掘出頻繁模式.PXFP算法有如下的優(yōu)點:

1)廣度優(yōu)先遍歷XML文檔樹并以“節(jié)點:父節(jié)點”形式表示每個節(jié)點,這種序列化的方式在不遺漏XML文檔樹的結構信息的同時降低了序列中的節(jié)點冗余,減小了待挖掘的序列長度;

2)較之PrefixSpan算法,不需要產生投影數(shù)據(jù)庫,大大節(jié)約了存儲空間;

3)由位置信息直接定位到序列數(shù)據(jù)庫中,不需要多次掃描數(shù)據(jù)庫及投影數(shù)據(jù)庫,減少時間開銷.

在實驗中,PXFP算法用于挖掘XML頻繁路徑在時間效率和空間效率上均優(yōu)于經(jīng)典的PrefixSpan算法,證明了算法的有效性.但是,本文中提出的XML頻繁路徑挖掘算法在應用于大型XML文檔或XML數(shù)據(jù)流還有改進和提升的空間,這是未來進一步研究的方向.

1 Agrawal R,Srikant R.Mining sequential patterns.Proceedings of the 11th International Conference on Data Engineering.Washington,DC,USA.1995.3–14.

2 Srikant R,Agrawal R.Mining sequential patterns:Generalizations and performance improvements.Proceedings of the 5th International Conference on Extending Database Technology:Advances in Database Technology.London,UK.1996.3–17.

3 Han JW,Pei J,Yin YW.Mining frequent patterns without candidate generation.Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data.New York,NY,USA.2000.1–12.

4 Han JW,Pei J,Mortazavi-Asl B,et al.FreeSpan:Frequent pattern-projected sequential pattern mining.Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,NY,USA.2000.355–359.

5 Pei J,Han J,Mortazavi-Asl B,et al.PrefixSpan:Mining sequential patterns efficiently by prefix-projected pattern growth.Proceedings of the 17th International Conference on Data Engineering.Washington,DC,USA.2001.215.

6 張坤,朱揚勇.無重復投影數(shù)據(jù)庫掃描的序列模式挖掘算法.計算機研究與發(fā)展,2007,44(1):126–132.

7 張利軍,李戰(zhàn)懷,王淼.基于位置信息的序列模式挖掘算法.計算機應用研究,2009,26(2):529–531.

8 劉棟,尉永清,薛文娟.基于Map Reduce的序列模式挖掘算法.計算機工程,2012,38(15):43–45.[doi:10.3778/j.issn.1002-8331.2012.15.010]

9 吳信東,謝飛,黃詠明,等.帶通配符和One-Off條件的序列模式挖掘.軟件學報,2013,24(8):1804–1815.

10 劉端陽,馮建,李曉粉.一種基于邏輯的頻繁序列模式挖掘算法.計算機科學,2015,42(5):260–264.[doi:10.11896/j.issn.1002-137X.2015.05.052]

11 Beedkar K,Gemulla R.LASH:Large-scale sequence mining with hierarchies.Proceedings of the 2015 ACM SIGMOD Inter-national Conference on Management of Data.New York,NY,USA.2015.491–503.

12 Leung HP,Chung FL,Chan SCF,et al.XML document clustering using common XPath.Proceedings of the International Workshop on Challenges in Web Information Retrieval and Integration.Washington,DC,USA.2005.91–96.

13 貝毅君.XML數(shù)據(jù)頻繁模式挖掘技術研究[博士學位論文].杭州:浙江大學,2008.

14 雷向欣,楊智應,黃少寅,等.XML數(shù)據(jù)流分頁頻繁子樹挖掘研究.計算機研究與發(fā)展,2012,49(9):1926–1936.

15 李巍,李雄飛,郭建芳.XML空間頻繁變化結構挖掘方法.計算機學報,2013,36(2):317–326.

16 INEX.Initiative for the evaluation of XML retrieval.http://inex.mmci.uni-saarland.de/data/documentcollection.html,2014.