宋 薇 張曉民 郭東恩

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

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

宋 薇 張曉民 郭東恩

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

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的重要方法之一，它主要用來(lái)揭示數(shù)據(jù)庫(kù)中項(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ù)庫(kù)信息，論文提出了前綴路徑圖結(jié)構(gòu)，該結(jié)構(gòu)可以存儲(chǔ)挖掘所需的全部項(xiàng)集信息，減少掃描數(shù)據(jù)庫(kù)次數(shù)。并且提出了一種基于前綴路徑圖的頻繁閉項(xiàng)集挖掘算法PGraph-FCIMiner。論文的實(shí)驗(yàn)均采用Java語(yǔ)言編寫(xiě)，實(shí)驗(yàn)結(jié)果證明算法具有較好的執(zhí)行效率和可擴(kuò)展性。

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

1 引言

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

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

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

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

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

2 前綴路徑圖

2.1 問(wèn)題定義

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

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

2.2 前綴路徑圖定義

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

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

2）圖中每個(gè)結(jié)點(diǎn)代表事務(wù)數(shù)據(jù)庫(kù)的一個(gè)頻繁項(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ù)庫(kù)，統(tǒng)計(jì)事務(wù)中出現(xiàn)的項(xiàng)及其支持度，得到頻繁1-項(xiàng)集。再次掃描數(shù)據(jù)庫(kù)，對(duì)于每個(gè)事務(wù)刪除不頻繁項(xiàng)。對(duì)刪除不頻繁項(xiàng)之后長(zhǎng)度大于1的事務(wù)按照支持度由高到低對(duì)事務(wù)中的頻繁項(xiàng)進(jìn)行排序，當(dāng)項(xiàng)的支持度相同時(shí)，按照詞典順序排序。在第二次掃描數(shù)據(jù)庫(kù)過(guò)程中構(gòu)造前綴路徑圖，在前綴路徑圖中保存每個(gè)預(yù)處理后的事務(wù)。為每個(gè)排序后事務(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)有向邊只包含支持度時(shí)，內(nèi)容為“：”。創(chuàng)建結(jié)點(diǎn)時(shí)，判斷圖中是否存在對(duì)應(yīng)的結(jié)點(diǎn)，若無(wú)，則創(chuàng)建并更新nodelist。若存在，則判斷當(dāng)前連接結(jié)點(diǎn)是否存在，若無(wú)，則創(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ù)庫(kù)TDB，最小支持度ε；

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

begin

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

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

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

if（sortedTran長(zhǎng)度＞1）｛

if（sortedTran長(zhǎng)度=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是一個(gè)事務(wù)數(shù)據(jù)庫(kù)，最小支持度為2。

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

掃描數(shù)據(jù)庫(kù)一次，事務(wù)數(shù)據(jù)庫(kù)的項(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ù)庫(kù)，事務(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，此時(shí)前綴路徑圖見(jiàn)圖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，此時(shí)前綴路徑圖見(jiàn)圖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)容為空，不讀取。最終前綴路徑圖見(jiàn)圖1（c）。

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

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

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

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

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

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

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

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

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

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

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

獲取該項(xiàng)對(duì)應(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)個(gè)數(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；

分解前綴路徑即更新圖，類(lèi)似之前操作；

｝

｝

｝

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

｝

end；

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

結(jié)點(diǎn)b無(wú)前綴路徑集，因此將b：7加入FCI。支持度從低到高進(jìn)行考察，第一個(gè)考察的是結(jié)點(diǎn)e，前綴路徑大于1，因此通過(guò)求交集等方法得到其頻繁前綴是ba：2連接結(jié)點(diǎn)加入FCI，與e支持度相同，因此e不是頻繁閉項(xiàng)集，分解e結(jié)點(diǎn)的前綴路徑ba和bac，刪除e結(jié)點(diǎn)，更新圖結(jié)果見(jiàn)圖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é)果見(jiàn)圖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é)果見(jiàn)圖2（c）；考察結(jié)點(diǎn)a，只有一個(gè)前綴路徑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 挖掘過(guò)程中分解圖

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

實(shí)驗(yàn)中算法是采用Java語(yǔ)言編寫(xiě)，機(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挖掘時(shí)間低于PDG-FCIMiner，特別是當(dāng)支持度低時(shí)，算法效率相比更高。而且由實(shí)驗(yàn)結(jié)果可知，當(dāng)數(shù)據(jù)量不變時(shí)隨著最小支持度遞減，運(yùn)行時(shí)間呈線性增長(zhǎng)。

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

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

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

5 結(jié)語(yǔ)

本文定義了一種存儲(chǔ)事務(wù)數(shù)據(jù)庫(kù)信息的新結(jié)構(gòu)前綴路徑圖，用來(lái)更加緊湊地壓縮事務(wù)信息。圖中的每個(gè)結(jié)點(diǎn)代表事務(wù)數(shù)據(jù)庫(kù)中一個(gè)頻繁項(xiàng)，有向邊上記錄著指向結(jié)點(diǎn)的前綴路徑集信息而且是由支持度高的項(xiàng)指向支持度較低的項(xiàng)，這樣保證更多的相同的前綴路徑信息合并。每個(gè)項(xiàng)只占用一個(gè)結(jié)點(diǎn)而且信息存儲(chǔ)的過(guò)程中如果指向結(jié)點(diǎn)、有向邊、前綴信息均存在，只需更新前綴信息的支持度。本文提出了一種基于前綴路徑圖的頻繁閉模式挖掘算法PGraph-FCIMiner，該算法只需將前綴路徑圖中每個(gè)結(jié)點(diǎn)連接指向該結(jié)點(diǎn)的結(jié)點(diǎn)和有向邊上的前綴路徑構(gòu)成該結(jié)點(diǎn)的前綴路徑集，通過(guò)挖掘前綴路徑集的頻繁閉合項(xiàng)集信息，將結(jié)點(diǎn)代表的項(xiàng)連接得到各結(jié)點(diǎn)的頻繁閉合項(xiàng)集。通過(guò)對(duì)各結(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］宋薇.基于二叉樹(shù)和有向圖的頻繁閉項(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日

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

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