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

張繼榮，王向陽(yáng)

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

?

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

張繼榮，王向陽(yáng)

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

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

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

0 引言

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

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

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

……

該文檔內(nèi)容經(jīng)過解析、提取之后，可以表示成表1和表2的形式。

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

表1 事務(wù)數(shù)據(jù)

表2 項(xiàng)目數(shù)據(jù)

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

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

2 Apriori改進(jìn)算法的設(shè)計(jì)

2.1 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)及事務(wù)數(shù)據(jù)的Hash表表示

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

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

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

2.2 連接步的改進(jìn)方法

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

例如在數(shù)據(jù)庫(kù)中D中，按升序排列的項(xiàng)集L2={{I5、I1}，{I5、I8}，{I4、I3}，{I4、I1}，{I3、I8}，{I1、I6}}。按改進(jìn)的連接方法生成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}}，相比可知減少了冗余項(xiàng)集的產(chǎn)生，兩者對(duì)數(shù)據(jù)庫(kù)的掃描分別需要2次和27次?？梢姡B接步的改進(jìn)可以減少運(yùn)算量和掃描次數(shù)。

2.3 剪枝步的改進(jìn)方法

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

性質(zhì)1：設(shè)一項(xiàng)集為Xk，Xk中存在的任意子集記為Yk，如果Xk是頻繁項(xiàng)集，那么Yk也是頻繁項(xiàng)集。

性質(zhì)2：設(shè)一事務(wù)為Tk，Ck-1中的任何項(xiàng)集記為Ik-1，如果Ik-1?Tk，則刪除事務(wù)Tk，不會(huì)影響Lk的產(chǎn)生。

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

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

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

舉例說明：設(shè)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中包含項(xiàng)目I4，I5，I6，I7的頻繁項(xiàng)集得到l3={{I1、I2、I3}}，得新的c4為空集，顯然L4也為空集。顯然改進(jìn)的Apriori算法只需掃描一次數(shù)據(jù)庫(kù)，可以提前刪除不可能包含于頻繁項(xiàng)集的項(xiàng)，從而大幅度的減少匹配候選頻繁項(xiàng)集的時(shí)間開銷?？梢娸^之Apriori算法的效率有了很大的提升。

2.4 算法描述

第一步：對(duì)XML文檔進(jìn)行解析、提取出事務(wù)和相應(yīng)的項(xiàng)，并且以新的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)在Hash表中，構(gòu)成事務(wù)集合數(shù)據(jù)庫(kù)D；

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

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

第四步：剪枝步，計(jì)算Lk-1中所有項(xiàng)目的頻度，通過改進(jìn)的剪枝步的設(shè)計(jì)思想來產(chǎn)生一個(gè)新的更小的k-1項(xiàng)頻繁項(xiàng)集的集合lk-1，再通過自連接生成Ck；

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

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

2.5 對(duì)算法進(jìn)行實(shí)例數(shù)據(jù)的演示

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

表4 XApriori算法實(shí)例運(yùn)算過程

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 算法分析與測(cè)試

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

2)XApriori算法的數(shù)據(jù)結(jié)構(gòu)比較簡(jiǎn)單，設(shè)計(jì)了項(xiàng)目事務(wù)垂直對(duì)應(yīng)的關(guān)系數(shù)據(jù)結(jié)構(gòu)，對(duì)每一個(gè)項(xiàng)目進(jìn)行了二進(jìn)制編碼，存儲(chǔ)在Hash表中。在后續(xù)計(jì)算中使用了集合，使得計(jì)算比較節(jié)省時(shí)間。

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

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

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

圖1 時(shí)間和支持度關(guān)系圖

4 結(jié)束語(yǔ)

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

經(jīng)過實(shí)驗(yàn)證明，XApriori算法有效地提高了Apriori算法的運(yùn)行效率。

[1]源艷芬,梁慎青.簡(jiǎn)單介紹可擴(kuò)展標(biāo)記語(yǔ)言XML[A]. 電腦知識(shí)與技術(shù)，2010，20(6)：5523-5526.

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

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

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

[5] 蘇 勇，王 燕. 基于XQuery的XML文檔的關(guān)聯(lián)規(guī)則挖掘[J]. 計(jì)算機(jī)工程與科學(xué)，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解析與應(yīng)用[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2007，17(4)：86-89.

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

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

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

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

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

[14] 崔貫勛,李 梁,王柯柯,等.關(guān)聯(lián)規(guī)則中Apriori算法的研究與改進(jìn)[J].計(jì)算機(jī)應(yīng)用，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-)，女，遼寧沈陽(yáng)人，博士，教授，碩士生導(dǎo)師，主要從事現(xiàn)代通信網(wǎng)方向的研究。

1671-4598(2016)06-0178-03

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

TP311.13

A