宋 薇 張曉民 郭東恩

（南陽理工學(xué)院軟件學(xué)院 南陽 473000）

基于前綴路徑圖的頻繁閉項(xiàng)集挖掘算法?

宋 薇 張曉民 郭東恩

（南陽理工學(xué)院軟件學(xué)院 南陽 473000）

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的重要方法之一，它主要用來揭示數(shù)據(jù)庫中項(xiàng)或?qū)傩灾g的相關(guān)性。頻繁項(xiàng)集是產(chǎn)生關(guān)聯(lián)的基礎(chǔ)和核心。頻繁閉項(xiàng)集項(xiàng)集數(shù)量遠(yuǎn)遠(yuǎn)小于頻繁項(xiàng)集，而且包含了頻繁項(xiàng)集的全部信息。為了有效壓縮事務(wù)數(shù)據(jù)庫信息，論文提出了前綴路徑圖結(jié)構(gòu)，該結(jié)構(gòu)可以存儲挖掘所需的全部項(xiàng)集信息，減少掃描數(shù)據(jù)庫次數(shù)。并且提出了一種基于前綴路徑圖的頻繁閉項(xiàng)集挖掘算法PGraph-FCIMiner。論文的實(shí)驗(yàn)均采用Java語言編寫，實(shí)驗(yàn)結(jié)果證明算法具有較好的執(zhí)行效率和可擴(kuò)展性。

數(shù)據(jù)挖掘；頻繁閉項(xiàng)集；前綴路徑圖

1 引言

挖掘頻繁項(xiàng)集是產(chǎn)生關(guān)聯(lián)的核心和基礎(chǔ)，因此目前對關(guān)聯(lián)規(guī)則算法的研究上主要集中在如何高效的生成頻繁項(xiàng)集上。為了減少掃描數(shù)據(jù)庫的次數(shù)，提出了壓縮結(jié)構(gòu)，將挖掘頻繁項(xiàng)集所需相關(guān)信息存儲在這些結(jié)構(gòu)上，然后基于這些結(jié)構(gòu)挖掘出頻繁項(xiàng)集。常見的結(jié)構(gòu)有樹結(jié)構(gòu)、位表以及圖結(jié)構(gòu)。

CATS Tree［1］是一棵動態(tài)構(gòu)建的前綴樹，在挖掘的過程中可以動態(tài)指定最小支持度且不需要重新構(gòu)建。但樹構(gòu)建的過程以及挖掘的過程都很復(fù)雜，為了解決這個問題提出了 SC Tree［2］。SC Tree通過提前對數(shù)據(jù)庫排序?qū)崿F(xiàn)靜態(tài)構(gòu)建，在挖掘過程中也沒有最小支持度的限制。CanTree［3］用于增量式頻繁模式挖掘，數(shù)據(jù)庫更新時，樹記錄事務(wù)數(shù)據(jù)庫的內(nèi)容。CP-tree［4］是像FP-tree的壓縮的支持度降序的樹結(jié)構(gòu)，通過掃描一次數(shù)據(jù)庫構(gòu)建，構(gòu)建過程包含插入階段和重建階段。IFP-growth［5］是基于address-table和FP-tree+的算法。挖掘FP-tree+是通過自頂向下遍歷頭表中的每個項(xiàng)，所以FP-tree+可以在原始的FP-tree上構(gòu)建，減少內(nèi)存需要。

BitTable［6］是一些整數(shù)的集合，每一位代表一個項(xiàng)，用來壓縮候選項(xiàng)集和數(shù)據(jù)庫。BitTableFI在水平和垂直方向使用BitTable壓縮數(shù)據(jù)庫快速產(chǎn)生候選集和支持度，但是候選集的產(chǎn)生及檢測影響算法的效率，為了解決這個問題提出了Index-Bit-TableFI［7］。Index-BitTableFI在水平和垂直方向使用BitTable，在水平方向上運(yùn)用索引數(shù)組以及相應(yīng)的計算方法，通過深度優(yōu)先策略快速得到頻繁模式。BTFIM［8］是基于BitTable的頻繁模式挖掘算法，算法中首先將數(shù)據(jù)庫信息壓縮到BitTable中，而且算法中使用垂直方向BitTable用來快速計算支持度。

PrefixDigraph［9］由結(jié)點(diǎn)和有向邊集合構(gòu)成，用來存儲每個結(jié)點(diǎn)的前綴路徑集，用來壓縮事務(wù)數(shù)據(jù)庫信息。PDG-FIMiner算法［9］和PDG-FCIMiner算法［10］是基于該結(jié)構(gòu)提出的頻繁項(xiàng)集挖掘算法和閉項(xiàng)集頻繁算法。

為了能夠更加緊湊地壓縮事務(wù)數(shù)據(jù)庫信息，提高挖掘頻繁閉項(xiàng)集效率，本文定義了前綴路徑圖（PrefixpathGraph）結(jié)構(gòu)用來壓縮存儲事務(wù)數(shù)據(jù)庫信息。挖掘時按照支持度由低到高的順序挖掘結(jié)點(diǎn)，挖掘之后對該結(jié)點(diǎn)的前綴路徑集進(jìn)行分解。挖掘時，通過讀取結(jié)點(diǎn)及其指向結(jié)點(diǎn)和有向邊內(nèi)容，讀取該結(jié)點(diǎn)所有的前綴路徑，挖掘出該結(jié)點(diǎn)的頻繁閉項(xiàng)集。最后對所有結(jié)點(diǎn)的頻繁閉項(xiàng)集進(jìn)行閉包檢查，挖掘出所有的頻繁閉項(xiàng)集。

2 前綴路徑圖

2.1 問題定義

事務(wù)數(shù)據(jù)庫TDB是一組事務(wù)的集合，集合中的每個事務(wù)用一個二元組＜tid，X＞表示，這個二元組包含了一組項(xiàng)的集合和該事務(wù)的ID號。設(shè)I=｛i1，i2，…，in｝是出現(xiàn)在TDB中項(xiàng)的全部集合，包含k個項(xiàng)的項(xiàng)集稱為k-項(xiàng)集。在TDB中包含項(xiàng)集Y的事務(wù)的個數(shù)稱為項(xiàng)集Y的支持度，表示為sup（Y）。給定一個最小支持度min_sup，如果一個項(xiàng)集的sup（Y）＞min_sup，那么我們就稱項(xiàng)集Y是頻繁的。

如果項(xiàng)集Y不存在真超項(xiàng)集X使得X與Y在數(shù)據(jù)集中有相同的支持度計數(shù)，則稱項(xiàng)集Y在數(shù)據(jù)集中是閉合的。如果Y在數(shù)據(jù)集中是頻繁的且閉合的，則稱項(xiàng)集Y是數(shù)據(jù)集中的頻繁閉項(xiàng)集。

2.2 前綴路徑圖定義

定義1 前綴路徑圖（PrefixpathGraph）是一個圖形結(jié)構(gòu)，用來記錄事務(wù)數(shù)據(jù)庫中的事務(wù)信息且記錄每個結(jié)點(diǎn)的前綴路徑集：

1）它是由結(jié)點(diǎn)的集合和有向邊的集合組成；

2）圖中每個結(jié)點(diǎn)代表事務(wù)數(shù)據(jù)庫的一個頻繁項(xiàng)；

3）有向邊連接圖中結(jié)點(diǎn)，始終是由事務(wù)信息中支持度最低的項(xiàng)指向支持度最高的項(xiàng)，有向邊上記錄著該結(jié)點(diǎn)的前綴路徑信息，而且前綴路徑信息按照支持度由高到低的順序?qū)?xiàng)進(jìn)行排序。

2.3 前綴路徑圖構(gòu)造算法

首先掃描數(shù)據(jù)庫，統(tǒng)計事務(wù)中出現(xiàn)的項(xiàng)及其支持度，得到頻繁1-項(xiàng)集。再次掃描數(shù)據(jù)庫，對于每個事務(wù)刪除不頻繁項(xiàng)。對刪除不頻繁項(xiàng)之后長度大于1的事務(wù)按照支持度由高到低對事務(wù)中的頻繁項(xiàng)進(jìn)行排序，當(dāng)項(xiàng)的支持度相同時，按照詞典順序排序。在第二次掃描數(shù)據(jù)庫過程中構(gòu)造前綴路徑圖，在前綴路徑圖中保存每個預(yù)處理后的事務(wù)。為每個排序后事務(wù)中最后一項(xiàng)即當(dāng)前事務(wù)支持度最低的項(xiàng)創(chuàng)建結(jié)點(diǎn)，排序后事務(wù)第一項(xiàng)即當(dāng)前事務(wù)支持度最高的項(xiàng)為該結(jié)點(diǎn)的連接結(jié)點(diǎn)，創(chuàng)建有向邊由當(dāng)前事務(wù)中支持度最低的項(xiàng)指向支持度最高的項(xiàng)，有向邊記錄當(dāng)前事務(wù)的其他頻繁項(xiàng)信息，且有向邊的內(nèi)容也是由支持度高到低的順序排序，當(dāng)有向邊只包含支持度時，內(nèi)容為“：”。創(chuàng)建結(jié)點(diǎn)時，判斷圖中是否存在對應(yīng)的結(jié)點(diǎn)，若無，則創(chuàng)建并更新nodelist。若存在，則判斷當(dāng)前連接結(jié)點(diǎn)是否存在，若無，則創(chuàng)建。若當(dāng)前連接結(jié)點(diǎn)存在，則判斷當(dāng)前結(jié)點(diǎn)和連接結(jié)點(diǎn)是否已存在有向邊，若不存在，新增有向邊并記錄當(dāng)前事務(wù)其他頻繁項(xiàng)信息。若存在有向邊，則判斷需要記錄的當(dāng)前事務(wù)項(xiàng)集信息是否存在，若不存在則在有向邊上新增當(dāng)前事務(wù)項(xiàng)集信息。若存在，更新其支持度。

算法1 前綴路徑圖的構(gòu)造算法C-PrefixpathGraph

輸入：事務(wù)數(shù)據(jù)庫TDB，最小支持度ε；

輸出：前綴路徑圖PrefixpathGraph，頻繁1-項(xiàng)集allI-tem，node-list。

begin

掃描TDB并統(tǒng)計頻繁項(xiàng)及其支持度，將頻繁項(xiàng)按照支持度由高到低順序排序，并記錄為allItem；

for（TDB中的每個事務(wù)）｛

事務(wù)的頻繁項(xiàng)按照支持度由高到低排序，若支持度相同，按照詞典順序排序，排序后的事務(wù)記為sortedTran

if（sortedTran長度＞1）｛

if（sortedTran長度=2）｛

name=sortedTran最后一項(xiàng)；

link=sortedTran第一項(xiàng)；

edge=”：”；

｝else｛

name=sortedTran最后一項(xiàng)；

link=sortedTran第一項(xiàng)；

edge=sortedTran其他項(xiàng)；

｝

if（！graph.contains（name））｛

graphNode=new Node（）；

graphNode.setName（name）；

graphNode.setLink（link）；

graphNode.setEdge（edge）；

nodeList.add（name）；

｝else｛

graphNode=graph.get（name）；

if（！graphNode.getLink（）。contains（link））｛

graphNode.addLink（link）；

graphNode.addEdge（edge）；

｝else｛

i=graphNode.getLink（）.indexOf（link）；

if（！graphNode.getEdge（i）.contains（edge））

graphNode.addEdge（edge，i）；

else

graphNode.updateEdge（edge，i）；

｝

｝

graph.put（name，graphNode）；

｝

end；

例1 表1是一個事務(wù)數(shù)據(jù)庫，最小支持度為2。

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

掃描數(shù)據(jù)庫一次，事務(wù)數(shù)據(jù)庫的項(xiàng)集為I=｛a，b，c，d，e，f，g，h，i｝，記錄各項(xiàng)及其支持度，頻繁1-項(xiàng)集FI=｛b：7，a：6，c：6，d：2，e：2｝。再次掃描數(shù)據(jù)庫，事務(wù)信息按照支持度降序排序且刪去不頻繁項(xiàng)。讀取T1：bae，創(chuàng)建結(jié)點(diǎn)e，e指向b，創(chuàng)建結(jié)點(diǎn)b，有向邊eb內(nèi)容為a：1；讀取T2：bd，創(chuàng)建結(jié)點(diǎn)d，d 指向b，有向邊db內(nèi)容為1；讀取T3：bc，創(chuàng)建結(jié)點(diǎn)c，有向邊cb內(nèi)容為1，此時前綴路徑圖見圖1（a）；讀取T4：bad，d結(jié)點(diǎn)以及有向邊db存在，有向邊內(nèi)容增加a：1；讀取T5：ac，創(chuàng)建結(jié)點(diǎn)a，有向邊ca內(nèi)容為1；讀取T6：bc，c結(jié)點(diǎn)以及有向邊cb存在，將有向邊內(nèi)容更新為2；讀取T7：ac，c結(jié)點(diǎn)以及有向邊cb存在，將有向邊內(nèi)容更新為2，此時前綴路徑圖見圖1（b）；讀取T8：bace，e結(jié)點(diǎn)以及有向邊eb存在，有向邊內(nèi)容增加ac：1；讀取T9：bac，c結(jié)點(diǎn)和有向邊cb存在，有向邊內(nèi)容增加a：1；T10內(nèi)容為空，不讀取。最終前綴路徑圖見圖1（c）。

圖1 構(gòu)造中的前綴路徑圖

2.4 前綴路徑圖性質(zhì)

性質(zhì)1 不受事務(wù)數(shù)據(jù)量的影響，前綴路徑圖結(jié)點(diǎn)數(shù)不超過事務(wù)數(shù)據(jù)庫中頻繁項(xiàng)的數(shù)目。

由定義1可知圖中的每個結(jié)點(diǎn)代表事務(wù)數(shù)據(jù)庫中的一個頻繁項(xiàng)，因此圖中的結(jié)點(diǎn)數(shù)最多是事務(wù)數(shù)據(jù)庫中頻繁項(xiàng)的數(shù)目，事務(wù)數(shù)據(jù)量不影響前綴路徑圖中結(jié)點(diǎn)數(shù)。

性質(zhì)2 給定一個事務(wù)數(shù)據(jù)庫，最小支持度，其對應(yīng)的前綴路徑圖存儲了挖掘長度大于1的頻繁閉項(xiàng)集所需的全部信息。

根據(jù)上述構(gòu)建過程可知，事務(wù)數(shù)據(jù)庫中每個事務(wù)預(yù)處理后的頻繁項(xiàng)長度大于2的事務(wù)信息都存儲在該結(jié)構(gòu)上。事務(wù)數(shù)據(jù)庫的每條預(yù)處理事務(wù)均由某個結(jié)點(diǎn)和其連接結(jié)點(diǎn)以及有向邊上記錄的內(nèi)容進(jìn)行存儲。因此該結(jié)構(gòu)存儲了挖掘長度大于1的頻繁閉項(xiàng)集所需的全部信息。

3 基于前綴路徑圖的頻繁閉項(xiàng)集挖掘算法

第一次掃描數(shù)據(jù)庫時已經(jīng)挖掘出頻繁1項(xiàng)集，由性質(zhì)2可知，前綴路徑圖上存儲了挖掘長度大于1的頻繁閉項(xiàng)集所需的全部信息。挖掘前綴路徑圖算法中頻繁1-項(xiàng)集作為輸入，且項(xiàng)按照支持度由低到高的順序排序。按照這個順序，挖掘每個結(jié)點(diǎn)的前綴路徑，抽取出頻繁閉合的前綴項(xiàng)集與對應(yīng)結(jié)點(diǎn)連接產(chǎn)生每個結(jié)點(diǎn)的頻繁閉項(xiàng)集候選集。計算這些頻繁閉項(xiàng)集支持度最高的項(xiàng)并與結(jié)點(diǎn)項(xiàng)支持度進(jìn)行比較判斷當(dāng)前結(jié)點(diǎn)項(xiàng)是否閉合。支持度最高的項(xiàng)沒有前綴，因此將其1-項(xiàng)集放入頻繁閉項(xiàng)集候選集中。最終對各結(jié)點(diǎn)產(chǎn)生的頻繁閉項(xiàng)集采用哈希技術(shù)進(jìn)行閉包檢查，在當(dāng)前頻繁閉項(xiàng)集候選集中移除非頻繁閉項(xiàng)集，挖掘出所有的頻繁閉項(xiàng)集。

由構(gòu)造圖的算法可知，構(gòu)造的圖包含了預(yù)處理事務(wù)的所有信息。每個預(yù)處理事務(wù)由支持度最低的項(xiàng)指向支持度最高的項(xiàng)。挖掘時先挖掘支持度最低的項(xiàng)，當(dāng)前項(xiàng)的連接結(jié)點(diǎn)和有向邊的內(nèi)容記錄著當(dāng)前項(xiàng)的全部前綴路徑信息。挖掘完該結(jié)點(diǎn)頻繁閉項(xiàng)集之后，需要對該結(jié)點(diǎn)記錄的事務(wù)信息進(jìn)行分解，分解時依舊是支持度最低的項(xiàng)指向支持度最高的項(xiàng)，因此連接結(jié)點(diǎn)不變，將有向邊內(nèi)容最后一項(xiàng)對應(yīng)的結(jié)點(diǎn)即當(dāng)前事務(wù)中除挖掘結(jié)點(diǎn)外支持度最低的結(jié)點(diǎn)指向連接結(jié)點(diǎn)，有向邊內(nèi)容為分解前有向邊內(nèi)容移除最后一項(xiàng)的信息，循環(huán)直到所有結(jié)點(diǎn)都挖掘完畢。因?yàn)樽罡呓Y(jié)點(diǎn)沒有前綴信息，因此根據(jù)按照支持度由低到高的頻繁1-項(xiàng)集allItem循環(huán)時，判斷當(dāng)前結(jié)點(diǎn)在node-list里是否存在，當(dāng)圖創(chuàng)建結(jié)點(diǎn)時會更新node-list里的值。

當(dāng)前挖掘結(jié)點(diǎn)其連接結(jié)點(diǎn)和有向邊的內(nèi)容構(gòu)成當(dāng)前結(jié)點(diǎn)的所有前綴路徑信息。因?yàn)轭A(yù)處理事務(wù)時只保留長度大于2的事務(wù)，因此當(dāng)前挖掘結(jié)點(diǎn)必包含前綴路徑信息。如果當(dāng)前挖掘結(jié)點(diǎn)的前綴路徑只有一個，且支持度大于最小支持度將其前綴路徑信息和結(jié)點(diǎn)連接加入頻繁閉項(xiàng)集候選集。將當(dāng)前前綴路徑信息支持度與結(jié)點(diǎn)支持度比較，如果小于結(jié)點(diǎn)支持度，則將該結(jié)點(diǎn)對應(yīng)的頻繁1-項(xiàng)集加入頻繁閉項(xiàng)集候選集。結(jié)點(diǎn)的前綴路徑信息包括三種情況分別是項(xiàng)的個數(shù)等于2，其中有向邊內(nèi)容為“：”；項(xiàng)的個數(shù)為2，有向邊內(nèi)容是某個項(xiàng)；項(xiàng)的個數(shù)大于2。第一種情況表示預(yù)處理后事務(wù)只包含兩項(xiàng)，不需要分解。第二種情況分解后結(jié)點(diǎn)為有向邊最后一項(xiàng)即除挖掘結(jié)點(diǎn)支持度最低的結(jié)點(diǎn)，連接結(jié)點(diǎn)不變，有向邊內(nèi)容為“：”，并且記錄其支持度。第三種情況分解后結(jié)點(diǎn)為有向邊最后一項(xiàng)即除挖掘結(jié)點(diǎn)支持度最低的結(jié)點(diǎn)，連接結(jié)點(diǎn)不變，有向邊內(nèi)容為原有向邊內(nèi)容移除最后一項(xiàng)的內(nèi)容，并記錄其支持度。分解之后，則對圖進(jìn)行更新，判斷結(jié)點(diǎn)是否存在，如果不存在，則新建結(jié)點(diǎn)并更新nodelist。若存在，則判斷當(dāng)前連接結(jié)點(diǎn)是否存在，若無，則創(chuàng)建。若當(dāng)前連接結(jié)點(diǎn)存在，則判斷當(dāng)前結(jié)點(diǎn)和連接結(jié)點(diǎn)是否已存在有向邊，若不存在，新增有向邊并記錄當(dāng)前分解后有向邊內(nèi)容及支持度。若存在有向邊，則判斷需要記錄的分解信息是否存在，若不存在則在有向邊上新增當(dāng)前分解信息。若存在，更新其支持度。最后增加新結(jié)點(diǎn)到圖并刪除挖掘結(jié)點(diǎn)圖信息。如果當(dāng)前挖掘結(jié)點(diǎn)的前綴路徑大于一個，則需要抽取前綴路徑集的頻繁閉合項(xiàng)集信息。抽取頻繁閉合的前綴路徑主要是通過該結(jié)點(diǎn)前綴路徑之間相互做交集，記錄其交集并統(tǒng)計其支持度。統(tǒng)計交集支持度是通過交集之間做交集，更新其支持集。將前綴路徑集的頻繁閉合信息和其對應(yīng)的結(jié)點(diǎn)進(jìn)行連接，產(chǎn)生各結(jié)點(diǎn)的頻繁閉項(xiàng)集候選集。將這些前綴路徑集的頻繁閉合信息中最高的支持度和其對應(yīng)的結(jié)點(diǎn)支持度進(jìn)行比較判斷，如果小于結(jié)點(diǎn)支持度，則該結(jié)點(diǎn)對應(yīng)的頻繁1-項(xiàng)集是閉項(xiàng)集。并且對每個前綴路徑進(jìn)行分解，分解步驟同上。結(jié)點(diǎn)間的頻繁閉項(xiàng)集候選集的閉包檢查是借助哈希表進(jìn)行比較判斷。所有的頻繁閉項(xiàng)集候選集都存儲在哈希表中，其中支持度相等的任意兩項(xiàng)做交集，判斷交集是否等于自身，如果等于，則說明該候選集不是閉項(xiàng)集，而是另外項(xiàng)集的子集。最終在頻繁閉項(xiàng)集候選集中移除不是閉合的候選集，得到所有的頻繁閉項(xiàng)集。

算法2 基于前綴路徑圖的閉頻繁項(xiàng)集挖掘算法PGraph-FCIMiner

輸入：前綴路徑圖PrefixpathGraph，最小支持度ε，allI-tem，node-list；

輸出：所有的頻繁閉項(xiàng)集FCI。

begin

支持度最高的頻繁項(xiàng)加入FCI；

for（支持度從低到高的allItem每個項(xiàng)）｛

if（當(dāng)前項(xiàng)在node-list里）｛

獲取該項(xiàng)對應(yīng)的結(jié)點(diǎn)的前綴路徑信息paths

if（paths.size（）==1）｛

if（paths的支持度大于等于最小支持度）｛

前綴路徑連接結(jié)點(diǎn)及其支持度存入FCI；

if（paths支持度小于結(jié)點(diǎn)支持度）結(jié)點(diǎn)及其支持度存入FCI；

｝

link=paths第一項(xiàng)；

canNode=paths最后一項(xiàng)；

if（paths項(xiàng)個數(shù)＞2）｛

newedge=paths其他項(xiàng)集信息；

flag=1；

｝else｛

if（！canNode不是“：”）｛

newedge=“：”；

flag=1；

｝

｝

if（flag=1）

添加canNode，newedge，link到圖、更新nodelist；

｝else｛

獲得prePaths的頻繁閉合信息連接結(jié)點(diǎn)存入FCI，并將支持度最大的項(xiàng)與結(jié)點(diǎn)支持度比較，若小于，將結(jié)點(diǎn)及其支持度存入FCI；

分解前綴路徑即更新圖，類似之前操作；

｝

｝

｝

結(jié)點(diǎn)間閉包檢查，移除非頻繁項(xiàng)集，得到最終FCI；

｝

end；

例2 將例1的前綴路徑圖作為輸入，挖掘過程如下。

結(jié)點(diǎn)b無前綴路徑集，因此將b：7加入FCI。支持度從低到高進(jìn)行考察，第一個考察的是結(jié)點(diǎn)e，前綴路徑大于1，因此通過求交集等方法得到其頻繁前綴是ba：2連接結(jié)點(diǎn)加入FCI，與e支持度相同，因此e不是頻繁閉項(xiàng)集，分解e結(jié)點(diǎn)的前綴路徑ba和bac，刪除e結(jié)點(diǎn)，更新圖結(jié)果見圖2（a）；考察結(jié)點(diǎn)d，頻繁前綴是b：2連接結(jié)點(diǎn)加入FCI，與d支持度相同，因此d不是頻繁閉項(xiàng)集，分解d結(jié)點(diǎn)前綴路徑ba，刪除d結(jié)點(diǎn)，更新圖結(jié)果見圖2（b）；考察結(jié)點(diǎn)c，頻繁前綴路徑ba：2，b：4，a：4連接結(jié)點(diǎn)加入FCI，頻繁前綴項(xiàng)集最大支持度小于結(jié)點(diǎn)支持度，因此c是頻繁閉項(xiàng)集加入FCI，分解c結(jié)點(diǎn)前綴路徑ba，刪除c結(jié)點(diǎn)，更新圖結(jié)果見圖2（c）；考察結(jié)點(diǎn)a，只有一個前綴路徑b：4連接結(jié)點(diǎn)加入FCI，且支持度小于結(jié)點(diǎn)支持度，因此a是頻繁閉項(xiàng)集，加入FCI。結(jié)點(diǎn)項(xiàng)之間采用哈希技術(shù)進(jìn)行閉包檢查，最終FCI=｛b：7，bae：2，bd：2，ac：4，bc：4，bac：2，c：6，ba：4，a：6｝。

圖2 挖掘過程中分解圖

4 實(shí)驗(yàn)

實(shí)驗(yàn)中算法是采用Java語言編寫，機(jī)器配置為CPU 為 Intel（R）Core（TM）i5-4210H CPU@2.90 GHz 2.90 GHz，內(nèi)存為4G，操作系統(tǒng)為Windows 8系統(tǒng)。實(shí)驗(yàn)使用的數(shù)據(jù)集是人工合成數(shù)據(jù)集T10I4D100K。 本 文將 PGraph-FCIMiner和PDG-FCIMiner算法執(zhí)行效率進(jìn)行比較，結(jié)果如圖3所示。由圖3可知，PGraph-FCIMiner挖掘時間低于PDG-FCIMiner，特別是當(dāng)支持度低時，算法效率相比更高。而且由實(shí)驗(yàn)結(jié)果可知，當(dāng)數(shù)據(jù)量不變時隨著最小支持度遞減，運(yùn)行時間呈線性增長。

圖3 在T10I4D100K上數(shù)據(jù)集上執(zhí)行效率比較

為了驗(yàn)證變化事務(wù)量時算法的可擴(kuò)展性，采用數(shù)據(jù)集T10I4D100K，將數(shù)據(jù)集分為五部分，每部分?jǐn)?shù)據(jù)量為20K。每次運(yùn)行各部分?jǐn)?shù)據(jù)與其之前的運(yùn)行數(shù)據(jù)的累計數(shù)據(jù)。數(shù)據(jù)量由20K逐步增為100K，每次增加20K。支持度固定為3.5%，4%和4.5%。實(shí)驗(yàn)結(jié)果見圖4。顯然支持度不變時隨著數(shù)據(jù)量增長，運(yùn)行時間呈線性增長。

圖4 數(shù)據(jù)量20K到100K的運(yùn)行時間

5 結(jié)語

本文定義了一種存儲事務(wù)數(shù)據(jù)庫信息的新結(jié)構(gòu)前綴路徑圖，用來更加緊湊地壓縮事務(wù)信息。圖中的每個結(jié)點(diǎn)代表事務(wù)數(shù)據(jù)庫中一個頻繁項(xiàng)，有向邊上記錄著指向結(jié)點(diǎn)的前綴路徑集信息而且是由支持度高的項(xiàng)指向支持度較低的項(xiàng)，這樣保證更多的相同的前綴路徑信息合并。每個項(xiàng)只占用一個結(jié)點(diǎn)而且信息存儲的過程中如果指向結(jié)點(diǎn)、有向邊、前綴信息均存在，只需更新前綴信息的支持度。本文提出了一種基于前綴路徑圖的頻繁閉模式挖掘算法PGraph-FCIMiner，該算法只需將前綴路徑圖中每個結(jié)點(diǎn)連接指向該結(jié)點(diǎn)的結(jié)點(diǎn)和有向邊上的前綴路徑構(gòu)成該結(jié)點(diǎn)的前綴路徑集，通過挖掘前綴路徑集的頻繁閉合項(xiàng)集信息，將結(jié)點(diǎn)代表的項(xiàng)連接得到各結(jié)點(diǎn)的頻繁閉合項(xiàng)集。通過對各結(jié)點(diǎn)的頻繁閉合項(xiàng)集做閉包檢查挖掘出頻繁閉合項(xiàng)集。實(shí)驗(yàn)結(jié)果表明算法具有較好的執(zhí)行效率和可擴(kuò)展性。

［1］Cheung W，Zaiane O R.Incremental Mining of Frequent Patterns without Candidate Generation or Support Constraint［C］//Proceedings of the Seventh International Database Engineering and Application Symposium（IDEAS'03），Edmonton，Canada，2003：111-116.

［2］Chiou C K，Tseng J C R.Sorted Compressed Tree：an Imporve Method of Frequent Patterns Mining without Support Constraint［C］//Proceedings of 2nd International Conference on Software Engineering and Data Mining，Hsinchu，Taiwan，2010：328-333.

［3］Leung C，Khan Q，Li Z，et al.CanTree：a Canonical-order Tree for Incremental Frequent-pattern Mining［J］.Knowledge and Information Systems，2007，11（3）：287-311.

［4］Tanbeer S，Ahmed C，Jeong B，et al.CP-tree：a Tree Structure for Single-pass Frequent Pattern Mining［C］//Proceedings of the 12th Pacific-Asia Conference on Knowledge Discovery and Data Mining（PAKDD），2008：1022-1027.

［5］Lin K C，Liao I E，Chen Z S.An Imporved Frequent Pattern Growth Method for Mining Association Rules［J］.Expert Systems with Applications，2011，38（5）：5154-5161.

［6］Dong J，Han M.BitTableFI：an Efficient Mining Frequent Itemsets Algorithm［J］.Journal of Knowledge-Based Systems，2007，20（4）：329-335.

［7］Song W，Yang B，Xu ZH.Index-BitTableFI：an Improved Algorithm for Mining Frequent Itemsets［J］.Journal of Knowledge-Based Systems，2008，21（6）：507-513.

［8］He H，F(xiàn)eng S，Ren J，et al.A BitTable-based Algorithm of Mining Frequent Itemsets［J］.International Journal of Advancements in Computing Technology，2011，3（8）：198-204.

［9］Wang P，Song W，Yang X，et al.PDG-FIMiner：An Efficient Frequent Itemset Mining Approach Using Prefix-PathsDigraph［J］.Advances in Information Sciences&Service Sciences，2012，4（16）：39-46.

［10］宋薇.基于二叉樹和有向圖的頻繁閉項(xiàng)集挖掘算法研究［D］.秦皇島：燕山大學(xué)，2013.SONG Wei.Research of Frequent Closed Itemset Mining Algorithms based on Binary Tree and Directed Graph［D］.Qinghuangdao：Yanshan University，2013.

An Efficient Frequent Closed Itemset Mining Approach Based on PrefixpathGraph

SONG WeiZHANG XiaominGUO Dongen
（School of Software，Nanyang Institute of Technology，Nanyang 473000）

Association rules is one of the important methods of data mining，it is mainly used to reveal the correlation between items or attributes in the database.Frequent itemsets is the basis and core of the generation of the association.The number of frequent closed itemsets is much smaller than the frequent itemsets，and it contains all the information of frequent itemsets.A novel structure termed PrefixpathGraph is defined to store the transaction database compactly，which can store all the item set information and reduce the number of scanning database.In this paper，a PrefixpathGraph-based algorithm is proposed called PGraph-FCIMiner.The experiments in this paper are written in Java language，and the experimental results show that the algorithm has a good performance and scalability.

data mining，frequent closed itemsets，PrefixpathGraph

TP301.6

10.3969/j.issn.1672-9722.2017.11.043

Class Number TP301.6

2017年5月6日，

2017年6月27日

國家自然科學(xué)基金項(xiàng)目“軟件系統(tǒng)復(fù)雜網(wǎng)絡(luò)層次化實(shí)體挖掘方法及關(guān)鍵技術(shù)研究”（編號：61572420）資助。

宋薇，女，碩士研究生，講師，研究方向：數(shù)據(jù)挖掘。張曉民，男，碩士研究生，副教授，研究方向：軟件工程。郭東恩，男，碩士研究生，副教授，研究方向：大數(shù)據(jù)。