基于單向頻繁模式樹的頻繁項集挖掘算法

蔣東潔，李玲娟

(南京郵電大學(xué) 計算機學(xué)院，江蘇 南京 210023)

0 引 言

關(guān)聯(lián)規(guī)則挖掘[1-2]是數(shù)據(jù)挖掘中一個非常重要的研究領(lǐng)域，其要解決的問題是快速找到滿足最小支持度的頻繁項集。頻繁項集挖掘方法可以分為產(chǎn)生候選項集的方法和不產(chǎn)生候選項集的方法。前一種方法以Apriori[3]算法為代表，該算法需要多次掃描數(shù)據(jù)庫，并生成大量候選集，效率較低；后一種方法以FP-Growth[4-5]算法為代表，不需要產(chǎn)生候選項集，只需掃描兩次數(shù)據(jù)庫，節(jié)省了大量的I/O時間，因此總的效率有很大提高。

FP-Growth算法在挖掘過程中要創(chuàng)建復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，絕大部分時間主要消耗在構(gòu)造和遍歷FP-tree及條件FP-tree上。如果能夠提高這方面的效率，將有助于提高算法的總體效率。FP-Growth*[6-7]算法在創(chuàng)建條件FP-tree時創(chuàng)建一個二維數(shù)組，使用該數(shù)組存儲FP-tree中任意二個項目的出現(xiàn)次數(shù)，減少了FP-tree的遍歷時間；文獻[8]對FP-tree的構(gòu)造過程進行改進，同時用hash結(jié)構(gòu)存儲頻繁項頭表，有效減少了項搜索時間；文獻[9]提出了一種不用構(gòu)造條件FP-tree，直接利用最初FP-tree生成的被約束子樹進行挖掘的算法，因為該算法不用遞歸地構(gòu)建條件FP-tree，可以節(jié)省大量的存儲空間，同時該算法縮減了每一個節(jié)點的域的個數(shù)，只保留指向父節(jié)點的指針，與FP-Growth算法相比，所需的存儲空間減少了一倍，效率提高了一倍。

文中在文獻[9]算法(稱其為改進前算法)的基礎(chǔ)上，將被約束子樹分為指向相同端點和不同端點這兩種情況進行挖掘，設(shè)計了一種新的基于單向頻繁模式樹的頻繁項集挖掘算法(unidirectional frequent itemset mining，UFIM)。

1 有關(guān)定義

設(shè)I={i1,i2,…,im}為m個不同項目(Item)的集合，D={T1,T2,…,Tn}為包含n條事務(wù)記錄所構(gòu)成的事務(wù)數(shù)據(jù)庫，Ti(i=1,2,…,n)是其中一條記錄，由I中若干項組成。設(shè)X為由項組成的一個集合，若X∈T，則稱記錄T包含X。

定義1 支持度[10-11](support)：規(guī)則X→Y在數(shù)據(jù)庫D中的支持度是D中同時包含項集X和Y的概率，記為sup(X→Y)，即

sup(X→Y)=P{X∪Y}=|X∪Y|/|D|

定義2 置信度[10-11](confidence)：規(guī)則X→Y在D中的置信度是指在包含項集X的條件下包含項集Y的概率，記為conf(X→Y)，即

conf(X→Y)=P{Y|X}=sup(X→Y)/sup(X)

支持度和置信度這兩個閾值是描述關(guān)聯(lián)規(guī)則的兩個重要概念，支持度反映關(guān)聯(lián)規(guī)則在數(shù)據(jù)庫中的重要性，置信度衡量關(guān)聯(lián)規(guī)則的可信程度。給定一個數(shù)據(jù)集D，挖掘關(guān)聯(lián)規(guī)則問題就是產(chǎn)生支持度和置信度分別等于或大于用戶給定的最小支持度(minsup)和最小置信度(minconf)的關(guān)聯(lián)規(guī)則。

定義3 單向FP-tree(UFP-tree)：UFP-tree是一種樹結(jié)構(gòu)，該樹[12-13]由一個標(biāo)號為NULL的根節(jié)點(root)、一個項前綴子樹(item prefix subtress)集合、一個頻繁項頭表(frequent-item header table)構(gòu)成。

項前綴子樹中的每個節(jié)點由4個域組成：item-order，count，node-ahead，node-next。其中：item-order指該節(jié)點所代表的項的序號，count指通過該節(jié)點的事務(wù)個數(shù)，node-ahead指向最左子女節(jié)點或父節(jié)點，node-next指向右兄弟節(jié)點或節(jié)點鏈中下一個節(jié)點。

頻繁項頭表中每個表項由3個域組成：item-order，count，node-next頭。node-next頭指向UFP-tree中具有相同item-order的第一個節(jié)點。

定義4 被約束子樹[14]：設(shè)ki<…

2 UFIM算法設(shè)計

2.1 UFIM算法總體思想與流程

(1)UFIM算法總體思想。

UFIM算法采用分而治之的思想[15]，通過掃描兩次事務(wù)數(shù)據(jù)庫，將事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)放在一棵高度壓縮的數(shù)據(jù)結(jié)構(gòu)UFP-tree中，使其可以在內(nèi)存中存放，并且可以將重復(fù)的事務(wù)壓縮為一條事務(wù)。然后對該數(shù)據(jù)結(jié)構(gòu)進行迭代，通過模式增長的方式挖掘出所有頻繁項集。

(2)UFIM算法流程。

UFIM算法包含兩個階段：UFP-tree構(gòu)造階段和UFP-tree挖掘階段。

UFP-tree構(gòu)造階段：

①掃描事務(wù)數(shù)據(jù)庫，得到頻繁1-項集，并對其降序排序，生成項-序轉(zhuǎn)換表和序-項轉(zhuǎn)換表。

②創(chuàng)建UFP-tree的根節(jié)點，對數(shù)據(jù)庫中每個事務(wù)，首先將事務(wù)中的頻繁項轉(zhuǎn)換成對應(yīng)的序號，并降序排序，然后再將排序后的每個item-order遞歸插入到UFP-tree中，最后先根遍歷UFP-tree，將ahead指針翻轉(zhuǎn)。

UFP-tree挖掘階段：

對UFP-tree進行挖掘時，采用自底向上的遞歸思想，首先根據(jù)頭節(jié)點列表中的元素所指向的節(jié)點生成被約束子樹，然后針對這棵被約束子樹端點相同和端點不同兩種情況分別以組合方式和遞歸方式挖掘出包含該元素的所有的頻繁項集。對頭節(jié)點列表中的所有元素均自底向上執(zhí)行該操作，最終挖掘出所有的頻繁項集。

UFIM算法的流程如圖1所示。

2.2 UFP-tree的創(chuàng)建

基于定義3，UFP-tree用如下過程UFPTreeC()來創(chuàng)建。

圖1 UFIM算法流程

過程UFPTreeC()

輸入：事務(wù)數(shù)據(jù)庫D，最小支持度計數(shù)min-count

輸出：單向FP-tree

步驟：

①掃描事務(wù)數(shù)據(jù)庫D，得到每個項的支持度計數(shù)，刪除支持度計數(shù)小于min-count的項

②將項按支持度計數(shù)降序排序，得到每個項的序號，并生成項-序轉(zhuǎn)換表和序-項轉(zhuǎn)換表

③創(chuàng)建UFP-tree的根節(jié)點

For數(shù)據(jù)庫中每個事務(wù)t do

{

UFP-tree中的current指針初始化，指向根節(jié)點T；

刪除itemset中支持度計數(shù)小于min-count的項，將剩下的項轉(zhuǎn)換為序號，并降序排序得到orderlist；

}

For orderlist中每一項item-order do

{

UFP-tree_insert(item-order);

}

④按先根遍歷整棵UFP-tree，把每個節(jié)點c及其父節(jié)點p作為一個隊列元素放入隊列Q中；

⑤ For 隊列Q中每一個元素q do

{

q.c.node-ahead=q.p;//翻轉(zhuǎn)父節(jié)點指針

將節(jié)點c插入到項頭表的c.item-order的項節(jié)點鏈中，作為該節(jié)點鏈中最后一個節(jié)點；

}

其中函數(shù)UFP-tree_insert()的偽代碼如下：

函數(shù)UFP-tree_insert(item-order)

{

if current指針?biāo)赶虻墓?jié)點沒有子女節(jié)點

then

創(chuàng)建一個值為item-order的UFP-tree節(jié)點node，current.node-ahead=node;

修改current指針，使其指向新節(jié)點node;

Else if current指針指向節(jié)點的子女節(jié)點中有值為item-order的節(jié)點

then

該子女節(jié)點的count值增加1，并修改current指針指向它；

Else

創(chuàng)建一個值為item-order的UFP-tree節(jié)點的node；

將節(jié)點node插入到比node.item-order大的第一個節(jié)點之前，并使其count值為1；

修改current指針，使其指向新節(jié)點node；

}

以表1中前兩列數(shù)據(jù)構(gòu)成的事務(wù)數(shù)據(jù)庫D為例，若最小支持度計數(shù)min-count為3，則頻繁1-項集為f,c,a,b,m,p，它們的支持度計數(shù)分別4,4,3,3,3,3；它們的序號分別為1,2,3,4,5,6，從而得到表1第3列的有序集。

表1 示例數(shù)據(jù)

根據(jù)以上給出的UFP-tree的詳細構(gòu)建過程，基于表1生成的UFP-tree如圖2所示。

圖2 基于表1數(shù)據(jù)生成的UFP-tree

2.3 被約束子樹的創(chuàng)建

ST(ki,…,k2,k1)是單向FP-tree的一條包含根的特殊子樹?？梢杂萌齻€數(shù)組表示：指針數(shù)組branch[]，指向每條被約束子路徑的端點;整型數(shù)組base-count，記錄每個被約束子路徑的基本頻度計數(shù)；整型數(shù)組count[]，記錄被約束子樹中具有相同序號的節(jié)點的頻度計數(shù)和。

對于序號k，從k的節(jié)點鏈中的每個節(jié)點出發(fā)，自底向上搜索單向FP-tree，就可以構(gòu)造ST(k)。

2.4 頻繁項集的挖掘

在UFP-tree構(gòu)建完成后，就可以利用被約束子樹遞歸地挖掘出所有的頻繁項集。改進前算法給出了基于被約束子樹的挖掘方法，在此基礎(chǔ)上，文中將被約束子樹分為指向相同端點和不同端點這兩種情況，并對指針數(shù)組branch[]均指向同一端點的特殊的被約束子樹的頻繁項集挖掘方法進行改進。假設(shè)此時指向的端點是j，檢查數(shù)組count[j]是否滿足最小支持度計數(shù)。若滿足，則此被約束子樹的頻繁項集為除根節(jié)點外的節(jié)點的排列組合；若不滿足，則說明此被約束子樹沒有頻繁項集。用此方法挖掘出的頻繁項集與遞歸挖掘產(chǎn)生的頻繁項集相同，但可在一定程度上減少遞歸次數(shù)和存儲空間。

文中提出的UFIM算法的頻繁項集挖掘部分主要包括UFPmining過程和mine過程。UFPmining方法的主要功能是產(chǎn)生頻繁1-項集和生成包含一個約束項的被約束子樹，然后調(diào)用mine過程產(chǎn)生長度大于1的頻繁項集。算法具體描述如下：

過程UFPmining()：在UFP-tree上挖掘頻繁集

輸入：構(gòu)建好的UFP-tree和設(shè)定的最小支持度計數(shù)min-count

輸出：所有的頻繁項集及支持度

procedure UFPmining(UFP-tree)

{

Fequent_len =0; //頻繁項集長度

fori=max-order downto 1 do

{

將序號i對應(yīng)的項放入頻繁項集數(shù)組FP[]中;

輸出序號i所對應(yīng)的項和支持度count[i]/allTrans;

依據(jù)UFP-tree構(gòu)造被約束子樹ST(i)

if(ST(i)有非根節(jié)點)

mine(ST(i));

Fequent_len --;

}

}

過程mine()可以用迭代算法實現(xiàn)，為簡潔起見，下面給出它的遞歸算法

procedure mine(ST(k1,…,km))

{

//指向相同端點的特殊被約束子樹

if(ST(k1,…,km)端點相同并且端點計數(shù)≥最小計數(shù))

被約束子樹的元素排列組合記為list;

輸出FP[]∪list的每個組合，每個組合的支持度相同且為端點的支持度count[j]/allTrans; //j為端點

Else if(ST(k1,…,km)端點相同并且端點計數(shù)<最小計數(shù))

return;//沒有頻繁項集

//被約束子樹指向不同端點

Else

{

fori=km-1 downto 1 do

{

if(count[i]>=最小計數(shù))

{

將序號i對應(yīng)的項放入頻繁項集數(shù)組FP[]中;

輸出FP[]和支持度count[i]/allTrans;

依據(jù)ST(k1,…,km)構(gòu)造被約束子樹ST(k1,…,km,i)

if (ST(k1,…,km,i)中有非根節(jié)點)

mine(ST(k1,…,km,i));

Fequent_len --;

}

}

}

}

以對ST(5)的挖掘為例，其過程如下：

首先將序號5對應(yīng)的項m放入數(shù)組FP中，輸出頻繁項集{m:0.6}(冒號后面是支持度)，構(gòu)造ST(5)，如圖3(a)所示，因為其有非根節(jié)點，所以要以ST(5)為參數(shù)調(diào)用mine()。ST(5)端點不指向同一節(jié)點，要采用遞歸的方式求頻繁項集。i的初值是4，count[4]

圖3 挖掘ST(5)過程中形成的被約束子樹

在改進前的算法中，沒有對端點相同的情況進行優(yōu)化，其在挖掘ST(5)過程中還要構(gòu)建并挖掘ST(5,3,2)、ST(5,3,1)、ST(5,3,2,1)、ST(5,2,1)?？梢?，文中的此項改進是有效的。

3 實驗與結(jié)果分析

為了測試UFIM算法的性能，與FP-Growth算法及改進前算法進行對比實驗。

算法運行環(huán)境：CPU為Intel(R)Core(TM)i5- 6200U 2.30 GHz，內(nèi)存為8G，操作系統(tǒng)為Windows 10。算法實現(xiàn)用的編程語言為Java，編程環(huán)境為eclipse。實驗數(shù)據(jù)采用mushroom數(shù)據(jù)集[15]，該數(shù)據(jù)集含有119項，8 124個事務(wù)，平均每個事務(wù)有23個項。

(1)相同事務(wù)數(shù)、不同支持度下運行時間對比。

表2列出了相同事務(wù)數(shù)、不同支持度下各算法的運行時間。可以看出，在mushroom數(shù)據(jù)集中，UFIM的運行時間均小于改進前算法的運行時間。隨著支持度減小，UFIM算法和改進前算法在運行時間上的優(yōu)勢越來越明顯。這是因為，隨著支持度減小，特殊被約束子樹數(shù)量增多，UFIM算法可以快速生成頻繁項集，避免了遞歸構(gòu)建被約束子樹和對其挖掘的時間。

表2 運行時間隨支持度變化

(2)相同支持度、不同事務(wù)數(shù)下運行時間對比。

表3列出了在支持度為10%、事務(wù)數(shù)分別為1千至5千條記錄的情況下，各算法的運行時間?？梢钥闯?，UFIM在不同大小的數(shù)據(jù)集上的運行時間都小于改進前算法的運行時間。

表3 運行時間隨事務(wù)數(shù)變化

4 結(jié)束語

FP-growth算法比Apriori算法效率高幾個數(shù)量級，但它需要產(chǎn)生大量條件FP-tree，極大影響算法效率。文中設(shè)計了一種基于單向FP-tree的頻繁項集挖掘算法UFIM，該算法在挖掘過程中采用了虛擬的樹結(jié)構(gòu)—被約束子樹，并且將被約束子樹分為指向相同端點和不同端點這兩種情況進行挖掘，對指向相同端點的被約束子樹的挖掘方法做了改進。在mushroom數(shù)據(jù)集上的實驗結(jié)果表明，UFIM算法能有效減少被約束子樹創(chuàng)建次數(shù)，提高挖掘效率。