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

張 潔,毛國君

(中央財(cái)經(jīng)大學(xué) 信息學(xué)院,北京 100081)

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

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

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

1 相關(guān)工作

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

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

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

2 相關(guān)的定義

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

例子1.圖1給出了一個(gè)XML文檔對(duì)應(yīng)的樹結(jié)構(gòu),其中:它的根節(jié)點(diǎn)r=n1;樹的節(jié)點(diǎn)集合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)};樹的標(biāo)簽集合L={a,b,c,d,e,f,g};節(jié)點(diǎn)集合到標(biāo)簽集合的一個(gè)函數(shù)映射 f:{n1-＞ a,n2-＞ b,n3-＞ c,n4-＞ e,n5-＞ e,n6-＞ d,n7-＞ f,n8-＞ f,n9-＞ g}.

圖1 XML文檔樹模型示例

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

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

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

例子 3.對(duì)應(yīng)圖 1 中 XML 樹,＜a,b,c,d＞,＜a,b,e,f＞和＜a,b,e,g＞都是它的標(biāo)簽路徑.

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

例子4.對(duì)于標(biāo)簽序列數(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的前綴.當(dāng)然B的前綴不止一個(gè),比如＜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}的前綴,當(dāng)n＜m時(shí),bn+1中an的子節(jié)點(diǎn)的集合被稱為A在B上的直接后綴;當(dāng)n=m時(shí),A在B上的直接后綴為空.

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

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

例子6.對(duì)于圖1(假設(shè)數(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文檔是半結(jié)構(gòu)化數(shù)據(jù),對(duì)其進(jìn)行頻繁路徑挖掘可以分為兩步:XML文檔序列化和序列挖掘,基于此將從XML文檔集中挖掘頻繁路徑的過程劃分為五個(gè)階段,如圖2所示.

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

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

(2)頻繁節(jié)點(diǎn)階段:找出支持度不小于閥值的頻繁節(jié)點(diǎn),構(gòu)造Hash映射表,將頻繁節(jié)點(diǎn)標(biāo)簽與數(shù)字一一對(duì)應(yīng).

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

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

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

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

圖3 待挖掘的XML文檔樹

(1)序列化階段

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

表1 XML文檔的序列化表示

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

(2)頻繁節(jié)點(diǎn)階段

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

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

(3)轉(zhuǎn)換階段

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

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

(4)頻繁路徑挖掘階段

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

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

表4 長(zhǎng)度為1的前綴的直接后綴

這里我們以前綴＜1＞為例來說明挖掘過程,對(duì)其他前綴進(jìn)行遞歸的方法和前綴＜1＞一樣.方法如下,首先統(tǒng)計(jì)＜1＞的直接后綴的出現(xiàn)次數(shù)得到{2:3,3:3}.由于此時(shí)＜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＞為前綴所對(duì)應(yīng)的直接后綴.首先看＜12＞前綴,由＜12＞的位置信息找到其對(duì)應(yīng)的直接后綴為＜(45)＞,＜4＞,＜4＞,進(jìn)行計(jì)數(shù)得到{4:3,5:1},因此得到以＜12＞為前綴的3階頻繁路徑為＜124＞,并更新＜124＞的位置信息為(1,3,1)(2,3,1)(3,3,1).由＜13＞的位置信息找到其對(duì)應(yīng)的直接后綴為＜6＞,＜6＞,＜6＞,進(jìn)行計(jì)數(shù)得到{6:3},因此得到以＜13＞為前綴的3階頻繁路徑為＜136＞,并記錄下＜136＞的位置信息為(1,3,3)(2,3,2)(3,3,2).繼續(xù)遞歸以＜124＞和＜136＞為前綴的頻繁路徑.由于前綴＜124＞和＜136＞對(duì)應(yīng)的直接后綴為空,因此不能產(chǎn)生4階頻繁路徑.至此以1為前綴的頻繁路徑挖掘結(jié)束,產(chǎn)生的頻繁路徑為＜1＞＜12＞＜13＞＜124＞＜136＞.同樣的方法可以得到其他前綴對(duì)應(yīng)的頻繁路徑.頻繁路徑挖掘結(jié)果如表5所示.

表5 頻繁路徑挖掘結(jié)果

(5)最大頻繁路徑階段

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

表6 最大頻繁路徑

3.2 算法描述

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

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

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

值得注意的是,與從單個(gè)XML文檔中挖掘關(guān)鍵模式不同,在多XML文檔頻繁路徑的挖掘中,如果某節(jié)點(diǎn)在前綴所對(duì)應(yīng)的直接后綴中多次出現(xiàn),仍然只計(jì)數(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中的每個(gè)序列3. FOR father_node=L1.get(m)TO longest subsequence//由1階前綴向高階擴(kuò)展4. FOR n=1 TO S.size();//在各個(gè)XML文檔集標(biāo)簽序列中5. child_node[]=father.getchild();//(根據(jù)位置信息)找到子節(jié)點(diǎn)即直接后綴6. save or update Position of subsequence;//記錄或更新位置信息7. Calculate support of every child_node occur in S;//計(jì)算子序列支持度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 實(shí)驗(yàn)與分析

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

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

實(shí)驗(yàn)1.比較內(nèi)存空間使用情況

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

表7 PrefixSpan算法和PXFP算法的內(nèi)存使用情況

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

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

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

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

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

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

圖4 小支持度區(qū)間內(nèi)算法時(shí)間效率對(duì)比

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

圖5 大支持度區(qū)間內(nèi)算法時(shí)間效率對(duì)比

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

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

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

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

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

5 總結(jié)

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

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

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

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

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

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 張坤,朱揚(yáng)勇.無重復(fù)投影數(shù)據(jù)庫掃描的序列模式挖掘算法.計(jì)算機(jī)研究與發(fā)展,2007,44(1):126–132.

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

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

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

10 劉端陽,馮建,李曉粉.一種基于邏輯的頻繁序列模式挖掘算法.計(jì)算機(jī)科學(xué),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ù)頻繁模式挖掘技術(shù)研究[博士學(xué)位論文].杭州:浙江大學(xué),2008.

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

15 李巍,李雄飛,郭建芳.XML空間頻繁變化結(jié)構(gòu)挖掘方法.計(jì)算機(jī)學(xué)報(bào),2013,36(2):317–326.

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