張繼榮，王向陽

(西安郵電大學 通信與信息工程學院，西安 710061)

?

基于XML數(shù)據挖掘的Apriori算法的研究與改進

張繼榮，王向陽

(西安郵電大學 通信與信息工程學院，西安 710061)

XML以其諸多優(yōu)點，迅速成為不同領域間信息表示與交換的標準;大量XML數(shù)據的出現(xiàn)給數(shù)據挖掘帶來了新的挑戰(zhàn);挖掘XML數(shù)據關聯(lián)規(guī)則的大部分工作都是基于Apriori算法的研究;對Apriori算法的基本方法與效率進行了分析，指出其不足，并提出了改進的XApriori算法，該算法基于新的數(shù)據結構，利用Hash表的存儲技術以及對Apriori算法的優(yōu)化來提高查找頻繁項集的效率;對Apriori算法和XApriori算法進行了比較，實驗結果表明改進的XApriori算法優(yōu)于Apriori算法。

XML；數(shù)據挖掘；關聯(lián)規(guī)則；頻繁項集；Apriori

0 引言

XML(eXtensible Markup Language，可擴展標記語言)[1]是一種描述數(shù)據內容和結構的語言，其具有標準的文本格式，可以在不同平臺間，進行數(shù)據的表示、存儲和交換，XML的飛速發(fā)展產生了大量的XML數(shù)據，所以，對其進行挖掘[2]已經變得非常重要。對XML數(shù)據關聯(lián)規(guī)則[3-4]的挖掘概括有以下3種不同的方法：1)Wan 等人提出的XML 挖掘算法是直接使用 XQuery 語言來實現(xiàn)Apriori 算法的，無需預先處理 XML 文檔[5]。2)Daniele Braga 等人提出的方法是通過預處理數(shù)據、抽取關聯(lián)規(guī)則和后期處理關聯(lián)規(guī)則3個主要步驟來實現(xiàn) Apriori 算法[6]。3)Ling Feng 等人提出一種不基于 Apriori 算法并且將不同的事務和項的概念映射到 XML 文檔樹型結構的方法[7]。本文基于XML 文檔并通過改進的Apriori 算法[4]來進行關聯(lián)規(guī)則的挖掘。XML挖掘包括對其結構和內容的挖掘，本文是基于XML文檔的內容來進行關聯(lián)規(guī)則的挖掘，通過DOM技術解析、提取出XML文檔的內容[8]，由于XML文檔的內容等價于元素的值，而被解析提取之后的XML元素值的集合與文本基本等價。所以，對XML文檔內容的挖掘就轉變成對一般文本文檔的挖掘。

1 關聯(lián)規(guī)則的基本概念

設所有的項目集合記為I={i1,i2,…,im}，數(shù)據集記為D(事物數(shù)據庫),D={T1,T2,…,Tn},其中Ti(i=1,2,…,n)稱為事務且Ti?I，包含k個項的項集稱為k-項集[9]。在XML數(shù)據中，將提取出的每一個元素記為一個事務，每個事務都有自己的ID，元素的值記為項，各個項都有自己的編號Ik(k=1,2,…,n)，把XML數(shù)據提取出的事務集合記為D，項的集合記為I。以某食品店部分交易記錄信息的XML文檔的數(shù)據表示為例來說明。記錄信息的部分XML文檔如下：

……

該文檔內容經過解析、提取之后，可以表示成表1和表2的形式。

關聯(lián)規(guī)則[10]是形如R：X→Y的邏輯蘊含式，其中X?I ，Y?I且X∩Y=Φ。在數(shù)據庫D中，存在關聯(lián)規(guī)則X→Y的支持度記為Support(X→Y)或Support(X∪Y)，表示同時出現(xiàn)項集X和Y的比例。若有Support(X)，則存在關聯(lián)規(guī)則X→Y的置信度，記為Confidence(X→Y)= Support(X∪Y)/Support(X)，表示包含X的事務下同時也包含Y的事務的比例。

表1 事務數(shù)據

表2 項目數(shù)據

關聯(lián)規(guī)則的產生，給定最小支持度minsup，首先找出所有的其支持度不小于minsup的頻繁項集，再由頻繁項集計算出關聯(lián)規(guī)則。如何高效地查找頻繁項集是整個算法的重點，也是本文后續(xù)工作研究的重點。

在大量的關聯(lián)規(guī)則算法中，基于 Apriori算法[11]挖掘效率的研究成為了重點。在1993年，Agrawal等人提出了Apriori算法。該算法的基本思想：按包含項目數(shù)自小至大的、逐層搜索迭代的方法來尋找頻繁項集。即用頻繁k-項集產生(k+1)-項集。具體過程是：第一次對數(shù)據庫進行掃描，找出所有的頻繁1-項集，記為L1；對L1自連接產生C2，對C2修剪后，第二次掃描數(shù)據庫，找出所有的頻繁2-項集，記為L2，如此循環(huán)，直到沒有頻繁項集為止。從過程中可看到Apriori算法的不足：在面對較大數(shù)據時，需要花費較大的開銷產生數(shù)目巨大的候選項集，Ck中的項集的數(shù)目將會呈現(xiàn)出指數(shù)般的增長；另外需要k次掃描數(shù)據庫，k為最大頻繁項集中子項集的項目數(shù)。從而帶來了很大的I/O交互負載并且非常耗費時間。

2 Apriori改進算法的設計

2.1 數(shù)據結構的設計及事務數(shù)據的Hash表表示

分析Apriori算法的不足可知， Apriori算法效率的提高關鍵在于：1)減少掃描事務數(shù)據庫的次數(shù)；2)減少候選項集的數(shù)目。對此，本文設計了新的數(shù)據結構，并利用Hash表來表示和存儲數(shù)據。該方法的基本思想是：對于Apriori算法來說，其依賴的數(shù)據結構是水平的，本文對其轉變成項目事務垂直對應的關系數(shù)據結構。對XML解析提取出的數(shù)據事務和項用Hash表來記錄[12]，每個項構建一個Hash表，Hash表中的元素為各個事務在對應的項中出現(xiàn)的事務編碼，為了方便后續(xù)計算項集出現(xiàn)的次數(shù)，本文以二進制編碼形式來表示事務元素[13]，各事務在對應的項中出現(xiàn)，則相應的表示為1，否則為0。將表1和表2可以表示成Hash表的形式，如表3所示。

表3 事務數(shù)據Hash表

表3產生頻繁項集的方法：給定最小支持度計數(shù)(minsup)，如果項目的二進制代碼中1的個數(shù)不小于minsup，其相應的項集即為頻繁1-項集。有2-項集{Ii，Ij}，只需在Hash表中提取第i項和第j項的二進制代碼，對其作按位邏輯與運算，得到的二進制代碼中1的個數(shù)不少于minsup的2-項集{Ii，Ij}即為頻繁2-項集。頻繁k-項集以相同的方法得到。該方法不會產生大量的候選項集，不但節(jié)省了內存空間，而且在計算支持度時，只需提取出部分的二進制代碼，不需對Hash表進行整體掃描，從而降低了I/O交互負載并且節(jié)省了時間，最終使得Apriori算法的效率得到了大幅度的提高。

2.2 連接步的改進方法

分析Apriori算法的計算過程中發(fā)現(xiàn)Apriori算法需要重復多次的對兩個k-項集進行判斷：1)判斷其前k-1項是否相同；2)判斷最后一項是否不同。對k-項集的判斷運算將影響著Apriori算法效率的高低。于是本文對其進行了必要的改進。該方法的基本思想：Lk-1自連接生成Ck前，判斷任意的兩個項集的前k-2項是否相同，如果不同，則不進行兩個項集的連接運算，因為產生的項集是重復的、非頻繁的[14]。設項集按升序排列的Lk-1中，任意項集X和Y作連接時，若Xk-2≠Yk-2，則放棄對X和Y的進行連接運算，從而減少了運算量。

例如在數(shù)據庫中D中，按升序排列的項集L2={{I5、I1}，{I5、I8}，{I4、I3}，{I4、I1}，{I3、I8}，{I1、I6}}。按改進的連接方法生成C3，C3=L2×L2={{I5、I1、I8}，{I4、I3、I6}}，如果按Apriori算法的連接方法生成C3=L2×L2={{I5、I1、I8}，{I5、I1、I4}，{I5、I8、I3}，{I5、I1、I6}，{I4、I3、I1}，{I4、I1、I6}，{I4、I3、I8}}，相比可知減少了冗余項集的產生，兩者對數(shù)據庫的掃描分別需要2次和27次?？梢?，連接步的改進可以減少運算量和掃描次數(shù)。

2.3 剪枝步的改進方法

判斷Ck中的項集是否屬于Lk中的頻繁項集前，Apriori算法對Ck進行修剪，以除去Ck中那些不可能產生頻繁項集的候選項集。將Ck中各個項集的k-1項子項集與Lk-1中的項集進行匹對，若不出現(xiàn)相同的項集，則刪除Ck中產生該子項集的項集。該方法對數(shù)據庫進行了大量的掃描，中間產生了大量的子項集，從而造成了內存空間的浪費和很大的時間開銷，導致了剪枝步的運算效率比級低。為了解決這些問題，本文結合了Apriori的一些性質，提出了剪枝步的改進方法。Apriori的一些基本性質[14]：

性質1：設一項集為Xk，Xk中存在的任意子集記為Yk，如果Xk是頻繁項集，那么Yk也是頻繁項集。

性質2：設一事務為Tk，Ck-1中的任何項集記為Ik-1，如果Ik-1?Tk，則刪除事務Tk，不會影響Lk的產生。

從性質可得：如果在I={i1，i2，…，ik}中，存在j∈I且|Lk-1(j)|

反證法證明：假設有頻繁項集Ik，由性質1知Ik中的k個非空子項集Xk-1也是頻繁項集，所以所有的子項集Xk-1都存在于Lk-1中。又由性質1知任意項集Xk-1的每一個項目i∈I在Lk-1共出現(xiàn)了至少k-1次，所以，對任何j∈I有|Lk-1(j)|≥k-1，結果明顯矛盾，故I不是頻繁項集。

由上述性質對剪枝步進行改進，方法的基本思想是：刪除集合Lk-1中所有滿足|Lk-1(j)|

舉例說明：設L3={{I1、I2、I3}，{I1、I2、I5}，{I1、I2、I4}，{I1、I2、I6}，{I1、I2、I7}，{I2、I3、I4}，{I2、I3、I5}，{I2、I3、I6}，{I2、I3、I7}}，由上述修剪方法可得|L3(1)|=5，|L3(2)|=9，|L3(3)|=5，|L3(4)|=|L3(5)|=|L3(6)|=|L3(7)|=2，故刪掉L3中包含項目I4，I5，I6，I7的頻繁項集得到l3={{I1、I2、I3}}，得新的c4為空集，顯然L4也為空集。顯然改進的Apriori算法只需掃描一次數(shù)據庫，可以提前刪除不可能包含于頻繁項集的項，從而大幅度的減少匹配候選頻繁項集的時間開銷?？梢娸^之Apriori算法的效率有了很大的提升。

2.4 算法描述

第一步：對XML文檔進行解析、提取出事務和相應的項，并且以新的數(shù)據結構存儲在Hash表中，構成事務集合數(shù)據庫D；

第二步：輸入預定的最小支持度，并掃描數(shù)據庫，在掃描過程中計算各個1-項集的支持度，通過對各個1-項集相對應的二進制代碼中1的個數(shù)的統(tǒng)計計算，刪除小于最小支持度的項集，得到集合L1；

第三步：連接步，為了產生k-項集Lk，運用改進的連接步的設計思想產生k-1項的項集Lk-1(項集中的項按在D中出現(xiàn)頻率的大小進行生序排列)；

第四步：剪枝步，計算Lk-1中所有項目的頻度，通過改進的剪枝步的設計思想來產生一個新的更小的k-1項頻繁項集的集合lk-1，再通過自連接生成Ck；

第五步：將Ck中不滿足給定最小支持度的項集刪除掉，形成Lk；

通過循環(huán)迭代計算，重復第三步到第五步，直到不產生新的頻繁項集為止，其中各個項集的支持度為生成各個項集的連接項集的二進制代碼按位與運算后代碼中1的個數(shù)。

2.5 對算法進行實例數(shù)據的演示

這里以圖表3的XML文檔解析提取出的數(shù)據為例，每一個項目都以二進制代碼的形式表示是否出現(xiàn)在13個事務中，給定最小支持度計數(shù)為2。XApriori算法的實例計算過程如表4所示。

表4 XApriori算法實例運算過程

L1

ItemSupItemSupItemSup{I1}7{I4}4{I8}3{I2}2{I5}8{I9}4{I3}4{I7}4

C2↓

ItemSupItemSupItemSup{I2,I8}0{I8,I9}0{I4,I1}1{I2,I3}0{I8,I1}1{I4,I5}2{I2,I4}1{I8,I5}1{I7,I9}1{I2,I7}0{I3,I4}1{I7,I1}3{I2,I9}0{I3,I7}2{I7,I5}3{I2,I1}0{I3,I9}3{I9,I1}4{I2,I5}0{I3,I1}3{I9,I5}3{I8,I3}0{I3,I5}3{I1,I5}6{I8,I4}1{I4,I7}0{I8,I7}0{I4,I9}1

L2↓

ItemSupItemSupItemSup{I3,I7}2{I4,I5}2{I9,I5}3{I3,I9}3{I7,I1}3{I1,I5}6{I3,I1}3{I7,I5}3{I3,I5}3{I9,I1}4

C3↓

ItemSupItemSup{I3,I7,I9}1{I3,I9,I5}2{I3,I7,I1}1{I3,I1,I5}2{I3,I7,I5}1{I7,I1,I5}2{I3,I9,I1}3{I9,I1,I5}3

L3↓

ItemSupItemSup{I3,I9,I1}3{I9,I1,I5}3

C4 ↓ItemSup{I3,I9,I1,I5}3→L4 ↓ItemSup{I3,I9,I1,I5}3

3 算法分析與測試

對比Apriori算法，XAprior算法有以下優(yōu)點：1)XApriori算法只對XML文檔數(shù)據庫掃描一次，在后續(xù)計算只需要索引出相應項集的二進制代碼，隨著算法的運行，需要處理的事務和項集在不斷地減小，從而節(jié)省了大量的時間，也大大的降低了I/O交互負載。

2)XApriori算法的數(shù)據結構比較簡單，設計了項目事務垂直對應的關系數(shù)據結構，對每一個項目進行了二進制編碼，存儲在Hash表中。在后續(xù)計算中使用了集合，使得計算比較節(jié)省時間。

3)XApriori算法只在開始掃描數(shù)據庫時對每個事務和項目進行了處理，在后續(xù)計算只需要索引出相應項集的二進制代碼，不需對所有項集進行處理。例如支持項目A的事務的集合為TA，支持項目B的事務的集合為TB，則同時支持項目A、B的事務為兩個集合交集(交集是兩個集合的二進制代碼進行按位邏輯與運算后的二進制代碼所代表的事務集合，不再對事務中的項目進行匹配)，這就使得尋找兩個集合的交集時無需進行循環(huán)掃描。XApriori算法避免了對所有項集進行大量的模式匹配計算和循環(huán)掃描，提高了時間效率。

4)XApriori算法的連接步和剪枝步可以提前刪除不可能包含頻繁項集的候選項集，減少了冗余，使得算法的效率得到了較大的提高。

為了測試XApriori算法，用Eclipse分別實現(xiàn)了Apriori和XApriori算法，使用了XML文檔解析提取出的關系型數(shù)據，該數(shù)據的事務數(shù)中為1 000，平均每個事務擁的項集數(shù)為10。該實驗在內存為2 GB，CPU主頻為2 200 MHz，操作系統(tǒng)為Windows7的計算機上進行。實驗結果如圖1所示，可以看出，XApriori算法有了較大的提高。

圖1 時間和支持度關系圖

4 結束語

本文基于XML文檔內容關聯(lián)規(guī)則的挖掘，針對Apriori算法的缺陷，本文設計了一種高效的基于項目事務垂直對應關系的數(shù)據結構并且利用Hash表來存儲、表示提取出的數(shù)據，并通過對Apriori算法的連接步和剪枝步進行了優(yōu)化改進，提出了一種改進的XApriori算法，該算法應用于XML文檔元素值之間關聯(lián)規(guī)則的產生。Apriori算法在運算中需要反復的掃描數(shù)據庫，造成了非常大的I/O交互負載；在產生新的候選項集時需要反復的對上一級頻繁項集進行對比與匹配，造成了運算效率的低下。而XApriori算法在整個過程中只需要掃描一次數(shù)據庫，有效地降低了I/O交互負載；在生成候選項集的過程中，利用了邏輯運算，使得連接剪枝步運算大大的簡化，邏輯運算對于計算機來說，使運算效率更高；在生成候選項集前，可以提前刪除不可能包含頻繁項集的候選項集，從而規(guī)避了冗余運算，使得算法的效率得到了較大的提高。

經過實驗證明，XApriori算法有效地提高了Apriori算法的運行效率。

[1]源艷芬,梁慎青.簡單介紹可擴展標記語言XML[A]. 電腦知識與技術，2010，20(6)：5523-5526.

[2] 李 巍. 半結構化數(shù)據挖掘若干問題研究[D]. 吉林：吉林大學，2013.

[3] 李 露,鄭 琪.數(shù)據挖掘原理與實踐[M]. 北京：電子工業(yè)出版社，2011.

[4] 熊 平. 數(shù)據挖掘算法與Clementine實踐 [M]. 北京:清華大學出版社,2011.

[5] 蘇 勇，王 燕. 基于XQuery的XML文檔的關聯(lián)規(guī)則挖掘[J]. 計算機工程與科學，2011，5(10)：91-95.

[6] Braga D, Campi A, Ceri S. Discovering interesting Information in XML Data with association rules[A]. Proceeding of the 14th International Conference[C].2003，(2454)：21-30.

[7] Feng L, Dillon T.An XML-enabled association rule framework[A]. Proceeding of the 14th International Conference[C].2003，(2736)：88-97.

[8] 蔚曉娟. 基于DOM的XML解析與應用[J]. 計算機技術與發(fā)展，2007，17(4)：86-89.

[9] J.Han，M.Kamber .數(shù)據挖掘概念與技術[M]. 范 明，孟小峰,譯. 北京：機械工業(yè)出版社，2007.

[10]周艷山.數(shù)據挖掘中關聯(lián)規(guī)則的研究與應用[D]. 哈爾濱：哈爾濱工業(yè)大學，2005.

[11] 胡吉明，鮮學豐.挖掘關聯(lián)規(guī)則中Apriori算法的研究與改進[J].計算機技術與發(fā)展，2006，16(4)：99-101.

[12] 張 婕，張 燕，李廣水. 基于Hash表的多謂詞約束下頻繁項集挖掘[J].微電子學與計算機，2011，28(10)：56-59.

[13] 黃根平,陳海勇,等. 數(shù)據集成中XML模式和關系模式映射模型研究[J]. 信息工程大學學報，2009，10(4)：529-531.

[14] 崔貫勛,李 梁,王柯柯,等.關聯(lián)規(guī)則中Apriori算法的研究與改進[J].計算機應用，2010，30(11):2952-2955.

Research and Improvement of Apriori Algorithm for XML Data Mining

Zhang Jirong，Wang Xiangyang

(School of Communication, Xi′an University of Posts and Telecommunications, Xi′an 710061，China)

Due to its many advantages, XML has rapidly become as a standard for representing and exchanging information in different fields. A large number of XML data has brought new challenges to data mining. Most of the work for mining XML data association rules is based on Apriori algorithm.The basic methods and efficiency of Apriori are analyzed, pointing out its shortcomings and propose the improved XApriori algorithm. The algorithm is based on the new data structure, the use of Hash table and the optimization of Apriori to improve the efficiency of finding frequent item sets. The experimental results show that XApriori is superior to Apriori.

XML; data mining; association rules; frequent item sets; Apriori

2015-12-03；

2016-01-05。

張繼榮(1963-)，女，遼寧沈陽人，博士，教授，碩士生導師，主要從事現(xiàn)代通信網方向的研究。

1671-4598(2016)06-0178-03

10.16526/j.cnki.11-4762/tp.2016.06.049

TP311.13

A