吳 倩，羅健旭

（華東理工大學(xué) 信息學(xué)院，上海200237）

0 引 言

通過(guò)算法輸出頻繁項(xiàng)集是關(guān)聯(lián)規(guī)則挖掘的核心步驟［1］。頻繁項(xiàng)集挖掘大致可以分為兩類：一類是基于候選項(xiàng)集產(chǎn)生－檢驗(yàn)的Apriori類算法，如IAA［2］，RAAT［3］，IApriori［4］，這類算法從經(jīng)典算法Apriori上演變而來(lái)，算法流程簡(jiǎn)單且易于理解，在候選項(xiàng)集得到約減時(shí)，算法效率會(huì)得到很大提高，但是算法需要多次掃描數(shù)據(jù)庫(kù)以統(tǒng)計(jì)項(xiàng)集支持度，在數(shù)據(jù)庫(kù)較大時(shí)，處理效率很低，在I／O 上消耗時(shí)間很多［5］；另一類算法是基于樹(shù)形結(jié)構(gòu)的模式增長(zhǎng)類算法，如FP－Growth［6］、COFI－Tree［7］、CT－PRO［8］等，它們?cè)谕诰蜻^(guò)程中無(wú)候選頻繁項(xiàng)集產(chǎn)生，且均基于分而治之的策略，對(duì)基于主樹(shù)建立的子樹(shù)進(jìn)行挖掘，這類算法在數(shù)據(jù)庫(kù)巨大時(shí)有效壓縮了數(shù)據(jù)中的重要信息，使得搜索效率較Apriori類算法得到很大提高［9］。

本文結(jié)合兩類算法的優(yōu)點(diǎn)，采用模式增長(zhǎng)類算法緊湊的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，第一步，遍歷原始數(shù)據(jù)庫(kù)，找到滿足最小支持?jǐn)?shù)的所有頻繁1項(xiàng)集，構(gòu)建壓縮頻繁模式樹(shù) （CFPTree）；第二步，基于分而治之的策略，分別建立了局部壓縮頻繁模式樹(shù)LocalCFP－Tree；第三步，利用Apriori算法的產(chǎn)生候選項(xiàng)集，自底向上遍歷LocalCFP－Tree來(lái)統(tǒng)計(jì)其支持?jǐn)?shù)，從而得到全部頻繁模式。改進(jìn)算法解決了Apriori算法因多次掃描數(shù)據(jù)庫(kù)而耗時(shí)長(zhǎng)的問(wèn)題，也避免了模式增長(zhǎng)類算法因大量遞歸調(diào)用出現(xiàn)內(nèi)存費(fèi)用大的現(xiàn)象。在數(shù)據(jù)集T10I4D100K、Mushroom 和Accidents上進(jìn)行測(cè)試，測(cè)試結(jié)果表明，該MCFP－Tree算法頻繁項(xiàng)集的挖掘效率明顯優(yōu)于Apriori算法和FP－Growth算法。

1 頻繁項(xiàng)集的概念及相關(guān)理論

設(shè)I＝｛i1，i2，…，in｝是n個(gè)項(xiàng)目的全集，D 是事務(wù)數(shù)據(jù)庫(kù)，事務(wù)T是I的子集，如：T＝｛i1，i2，…，im｝，此時(shí)T為m項(xiàng)集。每個(gè)事務(wù)T 都對(duì)應(yīng)唯一的事務(wù)標(biāo)識(shí)符TID。設(shè)有事務(wù)X，Y，有XI，YI，且X ∩Y ＝，則形如XY 的蘊(yùn)含式就是一條關(guān)聯(lián)規(guī)則，其中X，Y 分別為規(guī)則的前項(xiàng)集和后項(xiàng)集。如果D 中有a%的事務(wù)既包含X 又包含Y，那么則稱規(guī)則的支持度為 a%， 對(duì)應(yīng)的計(jì)算表達(dá)式為Support（XY）＝P（X ∪Y），即XY 同時(shí)出現(xiàn)的概率。

定義1 項(xiàng)集的支持度［10］為項(xiàng)集在數(shù)據(jù)庫(kù)中出現(xiàn)概率，一般由人為設(shè)定，本文中支持度取值范圍1%～90%。項(xiàng)集的支持?jǐn)?shù)為項(xiàng)集在數(shù)據(jù)庫(kù)中出現(xiàn)次數(shù)

定義2 給定最小支持?jǐn)?shù)閾值MinSup，如果項(xiàng)集的支持?jǐn)?shù)不小于該閾值，則該項(xiàng)集為頻繁項(xiàng)集。如果頻繁項(xiàng)集含有k個(gè)元素，則稱為頻繁k項(xiàng)集。

定理1 （頻繁項(xiàng)集的反單調(diào)性［11］）如果一個(gè)項(xiàng)集的支持度小于最小支持度，則其是一個(gè)非頻繁的項(xiàng)集，那么它的任何超集均為非頻繁項(xiàng)集。反之，如果一個(gè)項(xiàng)集是頻繁的，那么它的任意非空子集均為頻繁項(xiàng)集。

Apriori算法核心：Apriori算法可分為兩步：連接和剪枝。任取兩個(gè)頻繁k 項(xiàng)集，將其中各項(xiàng)按字典順序排列，如p＝｛ti1，ti2，…，tik｝，q＝｛tj1，tj2，…，tjk｝，當(dāng)滿足ti1＝tj1，ti2＝tj2…，tik－1＝tjk－1，且tik≠tjk時(shí)，連接p，q產(chǎn)生的候選k＋1項(xiàng)候選項(xiàng)集為｛ti1，ti2，…，tik，tjk｝。剪枝則是利用了頻繁項(xiàng)集的反單調(diào)性 （定理2），設(shè)有候選k＋1項(xiàng)集包含任意非頻繁項(xiàng)或項(xiàng)集，則可直接判定其為非頻繁項(xiàng)集，否則需要對(duì)數(shù)據(jù)庫(kù)遍歷進(jìn)行支持?jǐn)?shù)的統(tǒng)計(jì)，進(jìn)一步驗(yàn)證其是否頻繁。

CFP－Tree的構(gòu)建：在CFP－Tree樹(shù)中，每個(gè)節(jié)點(diǎn)由4部分組成：節(jié)點(diǎn)序號(hào)node－id、節(jié)點(diǎn)名字node－name、節(jié)點(diǎn)鏈node－sibling、計(jì)數(shù)數(shù)組［11］。其中計(jì)數(shù)數(shù)組中每個(gè)元素值均對(duì)應(yīng)表示某一個(gè)項(xiàng)集的出現(xiàn)次數(shù)，例如C ＝｛c1，c2，…，ck｝是某個(gè)節(jié)點(diǎn)對(duì)應(yīng)的計(jì)數(shù)數(shù)組，ci則表示全局頻繁項(xiàng)目頭表 （GlobalItemTable）中第i項(xiàng)到當(dāng)前節(jié)點(diǎn)序號(hào)項(xiàng)的項(xiàng)集出現(xiàn)的次數(shù)。若當(dāng)前節(jié)點(diǎn)序號(hào)為3，其計(jì)數(shù)數(shù)組C 為 ｛2，1，0｝，C 中第1項(xiàng)表示序號(hào)為1的節(jié)點(diǎn)到序號(hào)為3的節(jié)點(diǎn)的項(xiàng)集 ｛1，2，3｝在數(shù)據(jù)庫(kù)中出現(xiàn)的次數(shù)為2次，C 中第2項(xiàng)表示項(xiàng)集 ｛2，3｝的出現(xiàn)次數(shù)為1次，C 中第3項(xiàng)表示項(xiàng)集｛3｝出現(xiàn)的次數(shù)為0次。

GlobalItemTable也由4部分組成：節(jié)點(diǎn)名字、節(jié)點(diǎn)序號(hào)、節(jié)點(diǎn)數(shù)目和節(jié)點(diǎn)指針。節(jié)點(diǎn)序號(hào)為從1 開(kāi)始的整數(shù)，相當(dāng)于GlobalItemTable中各節(jié)點(diǎn)名字的事務(wù)標(biāo)志符；節(jié)點(diǎn)指針是從GlobalItemTable中每一項(xiàng)分別指向GlobalCFPTree中對(duì)應(yīng)的同序號(hào)節(jié)點(diǎn)，該節(jié)點(diǎn)通過(guò)節(jié)點(diǎn)鏈指向下一個(gè)具有相同節(jié)點(diǎn)序號(hào)的節(jié)點(diǎn)。CFP－Tree 的構(gòu)造算法ConstructCFP－Tree如下：

輸入：數(shù)據(jù)庫(kù)D，最小支持?jǐn)?shù)MinSup

輸出：GlobalCFP－Tree

（1）掃描數(shù)據(jù)庫(kù)D，統(tǒng)計(jì)所有項(xiàng)出現(xiàn)的次數(shù)，將其與MinSup進(jìn)行比較，將小于MinSup的項(xiàng)全部去除，剩余的頻繁一次項(xiàng)按頻次降序排列，依次對(duì)其添加序號(hào)，從1開(kāi)始遞增，形成GlobalItemTable。

（2）掃描數(shù)據(jù)庫(kù)D，將D 中不屬于GlobalItemTable的項(xiàng)去除，D 中保留下的均是頻繁一次項(xiàng)，形成的新數(shù)據(jù)庫(kù)叫D′。

（3）根據(jù)GlobalItemTable建立最左枝樹(shù)。如從GlobalItemTable的第1項(xiàng)開(kāi)始，該項(xiàng)指針指向一個(gè)新的節(jié)點(diǎn)，節(jié)點(diǎn)序號(hào)為該項(xiàng)在表中的序號(hào)1，節(jié)點(diǎn)名為該項(xiàng)在表中對(duì)應(yīng)的名字，新節(jié)點(diǎn)鏈連接為空，計(jì)數(shù)數(shù)組長(zhǎng)度為當(dāng)前序號(hào)的大小，計(jì)數(shù)數(shù)組內(nèi)元素全部置0。

（4）將D′中的數(shù)據(jù)按條讀取，設(shè)第一條事務(wù)數(shù)據(jù)為｛a，b，c｝，首先將各數(shù)據(jù)項(xiàng)變換為GlobalItemTable中對(duì)應(yīng)的序號(hào)，如 ｛1，3，2｝，再對(duì)其按大小進(jìn)行升序排列，得到一條對(duì)應(yīng)的數(shù)據(jù)項(xiàng)集 ｛1，2，3｝，叫mappedTrans，再調(diào)用第 （5）步中函數(shù)InsertToCFPTree，將mappedTrans插入CFP－Tree中。

（5）函數(shù)InsertToCFPTree。首先令FirstItem 為mappedTrans中第1 項(xiàng)，當(dāng)前起始節(jié)點(diǎn)currNode 為GlobalItemTable中第FirstItem 個(gè)的項(xiàng)指針指向的節(jié)點(diǎn)。對(duì)于mappedTrans里每個(gè)元素i，如果currNode已經(jīng)有序號(hào)為i的子節(jié)點(diǎn)，則將該節(jié)點(diǎn)計(jì)數(shù)數(shù)組的第FirstItem 項(xiàng)加1，否則創(chuàng)建一個(gè)序號(hào)為i的新節(jié)點(diǎn)，新節(jié)點(diǎn)的計(jì)數(shù)數(shù)組長(zhǎng)度等于其父節(jié)點(diǎn)的計(jì)數(shù)數(shù)組長(zhǎng)度，令該新節(jié)點(diǎn)計(jì)數(shù)數(shù)組的第FirstItem 項(xiàng)為1。

2 MCFP－Tree的提出

MCFP－Tree主要基于CFP－Tree緊湊的數(shù)據(jù)結(jié)構(gòu)，改進(jìn)了頻繁項(xiàng)集的搜索方法，打破了候選項(xiàng)集生成－檢驗(yàn)方法在含有較短頻繁模式的大數(shù)據(jù)庫(kù)下處理效率低下的劣勢(shì)，使得算法具有更全面的適用性。

輸入：數(shù)據(jù)庫(kù)D 的CFP－Tree，CFPTreeD；全局頻繁模式項(xiàng)目頭表，GlobalItemTable；最小支持?jǐn)?shù)閾值，Min－Sup；只包含頻繁一項(xiàng)集的數(shù)據(jù)庫(kù)，D’。

輸出：D 中滿足最小支持?jǐn)?shù)的所有頻繁模式FS。

中間變量：非頻繁項(xiàng)集，NFS；候選頻繁項(xiàng)集，CFS；局部頻繁項(xiàng)目頭表LocalItemTable中所有項(xiàng)對(duì)應(yīng)的序號(hào)集合，LocalIdTable。

挖掘部分主程序：

（1）Procedure Mining

（2） Clear CFS

（3） For each frequent itemi∈ reversedGlobalItemTable

（4） Clear NFS

（5） ConstructLocalItemTable（i）

（6） If the size of LocalItemTable isnot 0

（7） Retraverse CFPTreeDto record the count of each item appeared with i

（8） Construct the LocalItemTable（i）

（9） Construct LeftMostBranch （i）

（10） Construct LocalCFP－Tree（i）

（11） MineFrequentItems（i）；

（12） Print all sets in FS

（13） End if

（14） End for

（15）End

算法從GlobalItemTable表中的最不頻繁項(xiàng)集開(kāi)始逆序遍歷，在當(dāng)前項(xiàng)基礎(chǔ)上重新掃描數(shù)據(jù)庫(kù)D’，統(tǒng)計(jì)當(dāng)前項(xiàng)基礎(chǔ)上各項(xiàng)的出現(xiàn)頻次，尋找當(dāng)前項(xiàng)基礎(chǔ)上的頻繁項(xiàng)，重新給他們賦予新的序號(hào)，從1開(kāi)始，逐個(gè)遞增，形成LocalItemTable，類比GlobalCFP－Tree的構(gòu)造方法構(gòu)造Local－CFP－Tree。在LocalCFP－Tree的基礎(chǔ)上采用改進(jìn)算法進(jìn)行搜索頻繁項(xiàng)集。

（1）Procedure MineFrequentItems（i）

（2） Clear CFS

（3） iterNum＝1； ／／the number of iteration

（4） For each node j∈LocalItemTable

（5） Attach the name of i and j into FS

（6） Attach the node－id j into LocalIdTable

（7） End for

（8） Sort the LocalIdTable in ascending order

（9） Scan the LocalIdTable to create all combination of two different node－id into CFS

（10） For each itemj∈CFS

（11） SearchforCount（j）；

（12） If the count＞＝MinSup

（13） Attach j into FS

（14） Else

（15） Attach j into NFS

（16） End if

（17） End for

（18） If the size of CFS isnot 0or 1

（19） Increment the count of iterNum

（20） Combination （CFS，i，iterNum）

（21） End if

（22）End

要搜索基于序號(hào)為i的頻繁項(xiàng)的頻繁項(xiàng)集，可以挖掘基于該項(xiàng)建立的LocalCFP－Tree，這棵子樹(shù)中儲(chǔ)存了所有滿足MinSup的頻繁項(xiàng)集。LocalItemTable中是基于該項(xiàng)的所有頻繁1次項(xiàng)，若這些項(xiàng)的數(shù)目不大于1，則直接輸出這些項(xiàng)與序號(hào)為i的項(xiàng)的組合，它們?yōu)檩敵鲱l繁2次項(xiàng)；否則，采用Apriori算法候選項(xiàng)集的生成方法，按照候選項(xiàng)集的連接條件，調(diào)用Combination 函數(shù)，生成候選多項(xiàng)集，再調(diào)用SearchforCount函數(shù)計(jì)算候選項(xiàng)集的出現(xiàn)頻數(shù)。

（1） Procedure SearchforCount（j）

（2） Count＝0；

（3） FirstItem＝the first of j

（4） LastItem＝the last of j

（5） Find the node k whose id is LastItem in LocalItemTable

（6） While the sibling of K is null

（7） K is the sibling of itself

（8） If the sum of countArray is not 0

（9） Attach all the parent of k to local root into parentList

（10） End if

（11） If parentList contains j

（12） If （the size of countArray of node K ＜FirstItem）

（13） Add up the values in the countArray of K

（14） Else

（15） Add up the value from countArray ［0］to countArray［FirstItem－1］

（16） End if

（17） End if

（18） End while

（19） End

（20） Procedure Combination（CFS，i，iterNum）

（21） Create new candidate frequent itemset newCFS from CFS according to Apriori’s candidate generation rule

（22） Clear CFS

（23） For each itemj∈newCFS

（24） If j not in the NFS

（25） If j＞＝MinSup

（26） Attach j into FS

（27） Attach j into CFS

（28） Else

（29） Attach j into NFS

（30） End if

（31） End if

（32） End for

（33） If the Size of CFS is not 0

（34） Increment the count of iterNum

（35） Combination （CFS，i，iterNum）

（36） End if

（37） End

SearchforCount函數(shù)的作用是計(jì)算候選項(xiàng)集j的支持?jǐn)?shù)C。首先需要明確j的首元m 和尾元n，然后找到基于當(dāng)前節(jié)點(diǎn)的LocalItemTable指向的最左枝，求得最左枝上序號(hào)為n的節(jié)點(diǎn)的計(jì)數(shù)數(shù)組中第m 項(xiàng)到n項(xiàng)的和c1。然后需要考慮節(jié)點(diǎn)n的節(jié)點(diǎn)鏈指向是否為空，如果為空則返回的C為c1；否則，該節(jié)點(diǎn)鏈指向的節(jié)點(diǎn)變?yōu)楫?dāng)前節(jié)點(diǎn)n，向上找到節(jié)點(diǎn)n的父節(jié)點(diǎn)鏈，并判斷是否包含j，如果不包含則繼續(xù)判斷當(dāng)前節(jié)點(diǎn)n的節(jié)點(diǎn)鏈指向是否為空，直到當(dāng)前節(jié)點(diǎn)鏈指向的節(jié)點(diǎn)為空再跳出SearchforCount函數(shù)；否則c1要加上當(dāng)前節(jié)點(diǎn)n父節(jié)點(diǎn)鏈中j出現(xiàn)次數(shù)c2。最后將所有的c1＋c2＋…的和返回給C，作為當(dāng)前候選項(xiàng)集的出現(xiàn)次數(shù)。

為了方便理解，當(dāng)搜索所有基于序號(hào)為i的頻繁項(xiàng)的頻繁項(xiàng)集結(jié)束后，輸出的所有頻繁項(xiàng)或項(xiàng)集均統(tǒng)一用節(jié)點(diǎn)名字或名字的組合表示。如要輸出序號(hào)為5名字為x的頻繁項(xiàng)的一個(gè)頻繁項(xiàng)集 ｛1，2，3｝，項(xiàng)集支持?jǐn)?shù)為 ｛10｝，該項(xiàng)集對(duì)應(yīng)的節(jié)點(diǎn)名字為 ｛a，c，d｝，支持?jǐn)?shù)也應(yīng)為 ｛10｝，則輸出結(jié)果應(yīng)為 ｛a，c，d，x｝，支持?jǐn)?shù)為 ｛10｝。下面我們給出一個(gè)事務(wù)數(shù)據(jù)庫(kù)例子，用本文提出的改進(jìn)算法MCFPTree進(jìn)行挖掘。

例1：設(shè)事務(wù)數(shù)據(jù)庫(kù)D 如果所示，最小支持度為40%（最小支持?jǐn)?shù)為2），圖1 為建立GlobalCFP－Tree之前的數(shù)據(jù)處理工作，數(shù)據(jù)庫(kù)D 的GlobalCFP－Tree如圖2所示。

圖1 事務(wù)數(shù)據(jù)庫(kù)處理流程

圖2 全局壓縮頻繁模式樹(shù)GlobalCFP－Tree

樣例數(shù)據(jù)庫(kù) （圖1 （a）），首先遍歷數(shù)據(jù)庫(kù)，統(tǒng)計(jì)所有項(xiàng)出現(xiàn)的次數(shù)，找到頻繁1 次項(xiàng)，將其按頻次降序排列，每一個(gè)頻繁項(xiàng)均對(duì)應(yīng)一個(gè)Id號(hào)，從1開(kāi)始，逐個(gè)加1，形成GlobalItemTable （圖1 （b）），按照函數(shù)ConstructCFPTree建造最左枝樹(shù)，根據(jù)該表重新掃描數(shù)據(jù)庫(kù)，剔除非頻繁項(xiàng) （圖1 （c）），并將所有頻繁項(xiàng)一一對(duì)應(yīng)到GlobalItemTable表中Id值，逐行升序排列 （圖1 （d）），插入到GlobalCFP－Tree中。

從GlobalItemTable中最不頻繁項(xiàng) （序號(hào)為5的項(xiàng)）開(kāi)始，該項(xiàng)由指針指向的節(jié)點(diǎn)計(jì)數(shù)數(shù)組為空，則繼續(xù)沿節(jié)點(diǎn)鏈指向下一個(gè)同序號(hào)節(jié)點(diǎn)，找到第一條以序號(hào)為5節(jié)點(diǎn)為結(jié)尾的項(xiàng)集：｛1，2，4｝，沿節(jié)點(diǎn)鏈指向下一個(gè)節(jié)點(diǎn)，找到第二個(gè)項(xiàng)集： ｛1，3，4｝，此時(shí)該節(jié)點(diǎn)無(wú)下一個(gè)同序號(hào)節(jié)點(diǎn)，則以序號(hào)為5節(jié)點(diǎn)為結(jié)尾的項(xiàng)搜索結(jié)束。將找到的數(shù)據(jù)項(xiàng)集組合作為一個(gè)新的數(shù)據(jù)庫(kù)newD，調(diào)用ConstructCFP－Tree方法建造基于序號(hào)為5 的節(jié)點(diǎn)的LocalItemTable和LocalCFP－Tree。遍歷newD，得知項(xiàng) ｛1 （4），2 （3），3 （1），4 （5）｝的支持?jǐn)?shù)數(shù)分別為 ｛2，1，1，2｝，括號(hào)內(nèi)為項(xiàng)的名字，和MinSup對(duì)比得知，只有名字為4，5的節(jié)點(diǎn)是基于序號(hào)為5節(jié)點(diǎn)的頻繁項(xiàng)集，將其按支持?jǐn)?shù)大小降序排列，并給每一項(xiàng)重新賦Id 值，形成新的LocalItemTable，根據(jù)該表重新調(diào)用函數(shù)ConstructCFP－Tree建立新的LocalCFP－Tree，如圖3 （a）所示。

搜索以序號(hào)為5 的頻繁項(xiàng)為基礎(chǔ)建立的LocalCFPTree時(shí)，已知LocalItemTable中各項(xiàng)均為在其基礎(chǔ)上的頻繁1項(xiàng)集：｛｛1｝，｛2｝｝，支持?jǐn)?shù)分別為 ｛2，2｝。則它們分別與該頻繁項(xiàng)組合而成的輸出頻繁二項(xiàng)集名字為 ｛｛7，4｝，｛7，5｝｝，支持?jǐn)?shù)為這兩個(gè)節(jié)點(diǎn)在LocalItemTable里面的數(shù)量 ｛2，2｝。由于此時(shí)頻繁1項(xiàng)集的個(gè)數(shù)大于1，可以調(diào)用Combination函數(shù)連接產(chǎn)生候選2項(xiàng)集 ｛｛1，2｝｝，調(diào)用搜索函數(shù)SearchforCount，我們可知其支持?jǐn)?shù)為 ｛2｝，大于最小支持?jǐn)?shù)閾值，所以這個(gè)候選項(xiàng)集是頻繁2 項(xiàng)集，輸出完整的頻繁3項(xiàng)集的名字為 ｛｛7，4，5｝｝，支持?jǐn)?shù)為 ｛2｝。

MCFP－Tree采用Apriori算法的候選項(xiàng)集產(chǎn)生機(jī)制，產(chǎn)生候選項(xiàng)集后直接搜索各個(gè)局部頻繁模式樹(shù)，比遍歷數(shù)據(jù)庫(kù)計(jì)數(shù)節(jié)省時(shí)間，效率得到顯著提升。與FP－Growth相比，CFP－Tree數(shù)據(jù)結(jié)構(gòu)更為緊湊，節(jié)點(diǎn)數(shù)目最多的時(shí)候可以減少為FP－Growth的一半，大大節(jié)約了系統(tǒng)內(nèi)存的占用，此外搜索過(guò)程有效的減少對(duì)樹(shù)的遍歷，可以更高效的計(jì)算出候選項(xiàng)集的出現(xiàn)頻次。

3 算法實(shí)現(xiàn)與比較

本文用java語(yǔ)言在內(nèi)存2 G，CPU 為Intel（R）Core（TM）2Duo，32位的Windows7操作系統(tǒng)上實(shí)現(xiàn)了Apriori、FP－Growth、MCFP－Tree算法，使用了1組IBM 人工數(shù)據(jù)集T10I4D100K，2組經(jīng)典測(cè)試數(shù)據(jù)集Mushroom、Accidents。

表1中，Mushroom 是從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)（http：／／archive.ics.uci.edu／ml／datasets.html）下載，Accidents、T10I4D100K數(shù)據(jù)集從頻繁項(xiàng)集挖掘數(shù)據(jù)庫(kù)（http：／／fimi.ua.ac.be／data／）下載。

圖3 基于GlobalItemTable中頻繁項(xiàng)建立的LocalCFP－Tree

表1 數(shù)據(jù)集

由于頻繁項(xiàng)集數(shù)量在支持度范圍30%～90%之間變化很大 （數(shù)量從幾個(gè)至兩千多個(gè)），為便于分析，我們統(tǒng)一對(duì)頻繁項(xiàng)集的維數(shù)分布圖在不同支持度時(shí)分別取以10為底的對(duì)數(shù) （如圖5、圖8所示），縮小數(shù)量的變化范圍。

Mushroom 最大事務(wù)長(zhǎng)為23，所以很可能出現(xiàn)較多長(zhǎng)頻繁模式 （頻繁模式的維數(shù)大于10）。由圖4可知，MCFPTree網(wǎng)格區(qū)域所占面積遠(yuǎn)比同支持度時(shí)其它兩種算法的面積小，結(jié)合圖5，在支持度范圍內(nèi)，頻繁模式的長(zhǎng)度均較短（以長(zhǎng)度不大于5的頻繁模式為主），此時(shí)，改進(jìn)算法效率遠(yuǎn)高于兩種經(jīng)典算法。在支持度為40%時(shí)，改進(jìn)算法運(yùn)行效率較Apriori算法提高了75.2%，較FP－Growth算法提高了76.1%。明顯可以看出在處理含有較多短小頻繁項(xiàng)集時(shí)，改進(jìn)算法擁有顯著的優(yōu)越性。

圖4 Mushroom 數(shù)據(jù)集的算法性能對(duì)比

圖5 Mushroom 數(shù)據(jù)集頻繁集的數(shù)量

下面兩個(gè)數(shù)據(jù)集數(shù)據(jù)量分別為100000和340183，屬于數(shù)據(jù)量很大的數(shù)據(jù)庫(kù)，而且挖掘頻繁項(xiàng)集的耗時(shí)在支持度范圍內(nèi)跨度較 Mushroom 更大，所以我們統(tǒng)一對(duì)T10I4D100K 和Accidents的性能對(duì)比圖的縱坐標(biāo)取log以10為底的對(duì)數(shù)，壓縮時(shí)間的變化范圍，如圖6、圖7所示。對(duì)Accidents的頻繁項(xiàng)集維數(shù)分布圖的縱坐標(biāo)也取以10為底的log函數(shù)，如圖8所示。

圖6 T10I4D100K 數(shù)據(jù)集的算法性能對(duì)比

圖8 Accidents數(shù)據(jù)集頻繁項(xiàng)集的數(shù)量

T10I4D100K 是個(gè)數(shù)據(jù)量為100000的人工數(shù)據(jù)庫(kù)，但在支持度大于5%時(shí)，它的頻繁項(xiàng)集很少，所以我們?nèi)⊥诰虻姆秶鸀?%～5%。在支持度低于5%的時(shí)候，頻繁項(xiàng)集的數(shù)目增加很快，還是以短小頻繁模式為主，但是由于數(shù)據(jù)庫(kù)變大，搜索時(shí)間相應(yīng)就會(huì)變長(zhǎng)，Apriori的運(yùn)行效率顯然明顯低于其它兩種算法。當(dāng)最小支持度為3% 時(shí)，MCFP－Tree算法效率比Apriori算法提高了94%，比FPGrowth算法提高了40%，當(dāng)支持度降為1%時(shí)，涌現(xiàn)較多長(zhǎng)頻繁模式，MCFP－Tree算法所占面積略小于FP－Growth算法，效率只比FP－Growth算法提高了3.6%。

結(jié)合表1和圖8發(fā)現(xiàn)，Accidents的平均事務(wù)長(zhǎng)度和頻繁模式的長(zhǎng)度都比Mushroom 更長(zhǎng)，且此時(shí)數(shù)據(jù)庫(kù)變得很大 （約為Mushroom 的66 倍），但是頻繁模式還是以維度在10之內(nèi)的頻繁項(xiàng)集為主，證明Accidents數(shù)據(jù)庫(kù)本身就是較為稀疏的數(shù)據(jù)庫(kù)，此時(shí)改進(jìn)算法所占面積比兩種經(jīng)典算法所占面積都小，運(yùn)行效率也更高。在支持度范圍內(nèi)，改進(jìn)算法比Apriori算法平均提高91%左右，比FP－Growth算法提高95%左右，由此可以看出MCFP－Tree更適合挖掘數(shù)據(jù)量大的稀疏數(shù)據(jù)庫(kù)。

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

本文提出的MCFP－Tree算法融合了CFP－Tree的數(shù)據(jù)結(jié)構(gòu)和Apriori算法的候選項(xiàng)集產(chǎn)生方法，可以顯著提高頻繁項(xiàng)集的挖掘效率，尤其是在含有較多較短的頻繁模式的挖掘過(guò)程中 （大部分頻繁模式的長(zhǎng)度不超過(guò)10），可以取得更好的挖掘效率。但在有較多較長(zhǎng)頻繁模式時(shí)運(yùn)行效率和FP－Growth接近，所以后續(xù)研究可以利用已經(jīng)在Apriori類算法上發(fā)展起來(lái)的雙向搜索策略分別對(duì)LocalCFP－Tree挖掘，提高算法的搜索效率，此外考慮到只挖掘GlobalCFPTree主樹(shù)內(nèi)存消耗會(huì)更少，后續(xù)可以針對(duì)主樹(shù)來(lái)設(shè)計(jì)更加靈活的搜索算法，提高挖掘效率。

［1］YANG Zeming.Association rules incremental updating method based on cloud computing ［J］.Computer Engineering and Design，2014，35 （2）：504－508 （in Chinese）. ［楊澤明.云計(jì)算模型中關(guān)聯(lián)規(guī)則增量更新方法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2014，35 （2）：504－508.］

［2］Wu H，Lu ZG，Pan L，et al.An improved apriori－based algorithm for association rules mining ［C］／／6th International Conference on Fuzzy Systems and Knowledge Discovery，2009：51－55.

［3］Yu WJ，Wang XC，Wang FY，et al.The research of improved apriori algorithm for mining association rules ［C］／／11th IEEE International Conference on Communication Technology Proceedings，2008：513－516.

［4］Li XC，Teng SH.The research on improvement of apriori algorithm based on mining frequent itemsets ［J］.Journal of Jiangxi Normal University （Natural Science Edition），2011，35 （5）：498－502.

［5］Gupta B，Garg D.FP－tree based algorithms analysis：FPGrowth，COFI－Tree and CT－PRO ［J］.International Journal on Computer Science and Engineering，2011，3 （7）：2691－2699.

［6］ZHOU Lijuan，WANG Xiang.Research on association rules algorithms based on cloud environment ［J］.Computer Engineering and Design，2014，35 （2）：499－503 （in Chinese）.［周麗娟，王翔.云環(huán)境下關(guān)聯(lián)規(guī)則算法的研究 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2014，35 （2）：499－503.］

［7］XIAO Jihai，CUI Xiaohong，CHEN Junjie.Mining N－most interesting itemsets algorithm based on COFI－Tree［J］.Computer Technology and Development，2012，22 （3）：99－102 （in Chinese）.［肖繼海，崔曉紅，陳俊杰.基于COFI－Tree的N－最有興趣項(xiàng)目集挖掘算法 ［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2012，35（2）：99－102.］

［8］Yudho GS，Raj PG.CT－PRO：A bottom－up non recursive frequent itemset mining algorithm using compressed FP－tree data structure［C］／／Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations，2004：212－223.

［9］Shen B.Research on the technology of association rules［M］.Hangzhou：Zhejiang University Press，2012：5－7.

［10］Liu B，Hsu W，Chen S，et al.Analyzing the subjective interestingness of association rules ［J］.IEEE Intelligent Systems and Their Applications，2000，15 （5）：47－55.

［11］Luo XW，Wang WQ.Improved algorithms research for association rule based on matrix ［C］／／International Conference on Intelligent Computing and Informatics，2010：415－429.