趙 陽(yáng)，白 凡

(江南計(jì)算技術(shù)研究所，江蘇 無(wú)錫 214083)

基于FP-tree的支持度計(jì)數(shù)優(yōu)化策略

趙 陽(yáng)，白 凡

(江南計(jì)算技術(shù)研究所，江蘇 無(wú)錫 214083)

關(guān)聯(lián)規(guī)則挖掘過(guò)程中，頻繁項(xiàng)集的挖掘是最關(guān)鍵的步驟。最大頻繁項(xiàng)集是最常用的頻繁項(xiàng)集簡(jiǎn)化表示。基于FP-tree的最大頻繁項(xiàng)集挖掘算法多數(shù)都需要自底向上地搜索FP-tree來(lái)計(jì)算項(xiàng)集的支持度。而已有的支持度計(jì)算方法在計(jì)算當(dāng)前項(xiàng)集的支持度時(shí)沒(méi)有考慮已完成的支持度計(jì)算過(guò)程所獲得的信息，因而造成了不必要的開(kāi)銷。針對(duì)該問(wèn)題，提出了基于FP-tree的支持度計(jì)數(shù)優(yōu)化策略(Support Count Optimization Method on FP-tree,SCOM)，在付出很小的額外空間代價(jià)的條件下，充分利用已完成的支持度計(jì)數(shù)過(guò)程中獲取的路徑對(duì)項(xiàng)集的支持信息和項(xiàng)集之間的關(guān)系進(jìn)行搜索剪枝，并設(shè)計(jì)實(shí)驗(yàn)將該策略應(yīng)用到DMFIA算法上。實(shí)驗(yàn)結(jié)果表明，應(yīng)用該策略的最大頻繁項(xiàng)集挖掘算法DMFIA獲得了較大的性能提升。SCOM對(duì)基于FP-tree的支持度計(jì)數(shù)進(jìn)行優(yōu)化，因此能夠應(yīng)用到所有利用FP-tree進(jìn)行支持度計(jì)數(shù)的算法之中。

關(guān)聯(lián)規(guī)則挖掘；FP-tree；最大頻繁項(xiàng)集；支持度計(jì)數(shù)；搜索剪枝

0 引 言

關(guān)聯(lián)規(guī)則的概念是由Agrawal等提出的[1-2],反映了大量數(shù)據(jù)中項(xiàng)目集之間有趣的關(guān)聯(lián)或相關(guān)關(guān)系。頻繁項(xiàng)集挖掘是關(guān)聯(lián)規(guī)則挖掘中最關(guān)鍵的一步。實(shí)踐中，由事務(wù)數(shù)據(jù)集產(chǎn)生的頻繁項(xiàng)集的數(shù)量可能非常大，因此，從中識(shí)別出可以推導(dǎo)出其他所有頻繁項(xiàng)集的、較小的、具有代表性的項(xiàng)集是有用的。由于最大頻繁項(xiàng)目集中已經(jīng)隱含了所有頻繁項(xiàng)目集,所以可把發(fā)現(xiàn)頻繁項(xiàng)目集的問(wèn)題轉(zhuǎn)化為發(fā)現(xiàn)最大頻繁項(xiàng)目集的問(wèn)題。另外,某些數(shù)據(jù)挖掘應(yīng)用僅需發(fā)現(xiàn)最大頻繁項(xiàng)目集,而不必發(fā)現(xiàn)所有的頻繁項(xiàng)目集,因而發(fā)現(xiàn)最大頻繁項(xiàng)目集對(duì)數(shù)據(jù)挖掘具有重大意義[3]。

頻繁模式樹(shù)(Frequent Patten tree,FP-tree)是由Han等提出的對(duì)于事務(wù)數(shù)據(jù)集的一種壓縮存儲(chǔ)方式[4]?；贔P-tree的算法可以避免Apriori系列算法需要多次讀取事務(wù)數(shù)據(jù)集而造成的額外開(kāi)銷。目前，基于FP-tree的最大頻繁項(xiàng)集挖掘算法主要有FP-Max[5]，DMFIA[3]，IDMFIA[6]，F(xiàn)PMFI[7]，BDRFIA[8]，等等。FP-Max與FP-growth類似，通過(guò)遞歸構(gòu)建FP-tree的方式挖掘頻繁項(xiàng)集，用超級(jí)檢驗(yàn)的方法保證最終結(jié)果是最大頻繁項(xiàng)集。DMFIA是一種自頂向下的最大頻繁項(xiàng)集挖掘算法，與FP-Max相比，其無(wú)需遞歸生成FP-tree，對(duì)于最大頻繁項(xiàng)集維度較大的數(shù)據(jù)效果較好；IDMFIA是在DMFIA基礎(chǔ)上提出的雙向搜索算法，充分利用了低維項(xiàng)集信息進(jìn)行剪枝，擴(kuò)大了算法的適用數(shù)據(jù)范圍；FPMFIA使用基于投影的方法減少了超集檢測(cè)的時(shí)間；BDRFI則改進(jìn)FP-tree為DFP-tree(Digital Frequent Patten tree，數(shù)字頻繁模式樹(shù))，運(yùn)用多種預(yù)測(cè)剪枝策略，快速降低候選項(xiàng)集維度，減少了超級(jí)檢測(cè)的時(shí)間。調(diào)研中還發(fā)現(xiàn)各文獻(xiàn)對(duì)于“自頂向下”和“自底向上”的項(xiàng)集空間搜索的定義較為混亂[9-11]，因此文中的“自頂向下”的項(xiàng)集空間搜索特指從高維項(xiàng)集到低維項(xiàng)集的搜索。

上述基于FP-tree的最大頻繁項(xiàng)集挖掘算法中多數(shù)都需要通過(guò)遍歷FP-tree或其子樹(shù)來(lái)計(jì)算項(xiàng)集的支持?jǐn)?shù)，以避免多次掃描數(shù)據(jù)庫(kù)或遞歸生成條件FP-tree。但是在項(xiàng)集支持度計(jì)數(shù)的過(guò)程中，沒(méi)有充分利用在計(jì)算之前的項(xiàng)集支持度時(shí)所獲得的信息，因而造成了不必要的檢索開(kāi)銷。針對(duì)該問(wèn)題，提出了基于FP-tree的支持度計(jì)數(shù)優(yōu)化策略(Support Count Optimization Method on FP-tree,SCOM)。根據(jù)集合的性質(zhì)，在搜索FP-tree計(jì)算項(xiàng)集的支持度時(shí)，記錄路徑對(duì)項(xiàng)集的支持信息，以達(dá)到減少搜索路徑數(shù)的目的；并以DMFIA算法為例，應(yīng)用該策略對(duì)算法進(jìn)行改進(jìn)，并設(shè)計(jì)實(shí)驗(yàn)進(jìn)行驗(yàn)證。

1 相關(guān)知識(shí)

1.1相關(guān)定義和性質(zhì)

設(shè)I={i1,i2,…,im}是由m個(gè)項(xiàng)組成的集合，D是由一組事務(wù)組成的事務(wù)數(shù)據(jù)集且D中事務(wù)都由I中的項(xiàng)組成。給定項(xiàng)集X?I,X在D中的支持?jǐn)?shù)是指D中包含X的事務(wù)數(shù)，X在D中的支持度是指X的支持?jǐn)?shù)占D中所有事務(wù)數(shù)的百分比。

定義1：對(duì)于項(xiàng)集X?I,若X在D中的支持度sX大于等于給定的最小支持度s,則稱項(xiàng)集X為事務(wù)數(shù)據(jù)集D在最小支持度s下的頻繁項(xiàng)集；反之，則稱項(xiàng)集X為事務(wù)數(shù)據(jù)集D在最小支持度s下的非頻繁項(xiàng)集。

定義2：對(duì)于項(xiàng)集X?I,給定最小支持度s,若X的所有超集都是非頻繁項(xiàng)集，則稱項(xiàng)集X為事務(wù)數(shù)據(jù)集D在最小支持度s下的最大頻繁項(xiàng)集。

設(shè)R={n1,n2,…,nm}為由事務(wù)數(shù)據(jù)集D生成的FP-tree中的一條路徑，所有項(xiàng)集和路徑都是按照支持度降序排列的。

性質(zhì)1：對(duì)于項(xiàng)集X,若X?R,則?Y?X,Y?R且?R'?R,X?R'；若X?R,則?Y?X,Y?R且?R'?R,X?R'。

證明：根據(jù)集合的性質(zhì)容易得證。

對(duì)于項(xiàng)集X,Y?X且Y的最后一項(xiàng)為ei，R'為R的以ei結(jié)尾的前綴子路徑。

性質(zhì)2：若X?R,則必有Y?R'；若Y?R',則必有X?R。

證明：若X?R,由于所有項(xiàng)集和路徑都是按照支持度降序排列的，則對(duì)于X的以ei為結(jié)尾的前綴子集X',必有X'?R'，而Y?X'，故Y?R',同理可證若Y?R',則必有X?R,證畢。

1.2FP-tree與DMFIA

FP-tree是一種輸入數(shù)據(jù)的壓縮表示法，它通過(guò)逐個(gè)讀入事務(wù)，并把每個(gè)事物映射到FP-tree中的一條路徑來(lái)構(gòu)造。由于不同的事物可能會(huì)有若干個(gè)相同的項(xiàng)，因此它們的路徑可能部分重疊。路徑相互重疊越多，使用FP樹(shù)結(jié)構(gòu)獲得的壓縮效果越好。如果FP-tree足夠小，能夠存放在內(nèi)存之中，就可以直接從這個(gè)內(nèi)存中的結(jié)構(gòu)提取頻繁項(xiàng)集，而不必重復(fù)掃描存放在硬盤上的數(shù)據(jù)。

在FP-tree中，每個(gè)節(jié)點(diǎn)由4個(gè)域組成[12]:節(jié)點(diǎn)名稱item-name、節(jié)點(diǎn)計(jì)數(shù)item-count、節(jié)點(diǎn)鏈item-link(用于指向樹(shù)中具有相同item-name的下一個(gè)節(jié)點(diǎn))，及父節(jié)點(diǎn)指針item-parent。同時(shí)為方便樹(shù)的遍歷，F(xiàn)P-tree還包含一個(gè)頻繁項(xiàng)頭表Htable，它由兩個(gè)域組成:項(xiàng)目名稱item-name和指向FP-tree中具有相同item-name的首節(jié)點(diǎn)指針head of node-link。

為了獲得較好的壓縮效果，通常需要將事務(wù)中的項(xiàng)按照支持度降序排列，盡管這樣得到的FP-tree并不一定是最小的[13]。通過(guò)兩次掃描數(shù)據(jù)集來(lái)構(gòu)造FP-tree：

(1)第一次掃描數(shù)據(jù)集，確定每個(gè)項(xiàng)的支持度計(jì)數(shù)，丟棄非頻繁項(xiàng)；按照支持度降序構(gòu)建頻繁項(xiàng)頭表Headers，創(chuàng)建FP-tree的根節(jié)點(diǎn)，標(biāo)記為“null”；

(2)第二次掃描數(shù)據(jù)集，對(duì)于每個(gè)事務(wù)Trans，根據(jù)項(xiàng)的支持度降序排列。令當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)，順序遍歷Trans中的項(xiàng)，若當(dāng)前節(jié)點(diǎn)包含與該項(xiàng)同名的子節(jié)點(diǎn)，則該子節(jié)點(diǎn)計(jì)數(shù)加1，當(dāng)前節(jié)點(diǎn)變?yōu)樵撟庸?jié)點(diǎn)；否則，創(chuàng)建當(dāng)前節(jié)點(diǎn)的新的子節(jié)點(diǎn)，item-name=當(dāng)前項(xiàng)的名稱，item-count=1，item-parent指向當(dāng)前節(jié)點(diǎn)，Headers中同名鏈表的尾節(jié)點(diǎn)的item-link指向該子節(jié)點(diǎn)。直到遍歷完數(shù)據(jù)集中所有的事務(wù)，F(xiàn)P-tree構(gòu)建完成。

文獻(xiàn)[9]提出了FP-tree的一種改進(jìn)—數(shù)字頻繁模式樹(shù)(DFP-tree)，用頻繁項(xiàng)降序排列后的序號(hào)代替名稱，有利于提高超集檢測(cè)的效率。

DMFIA采用FP-tree的存儲(chǔ)結(jié)構(gòu)和自頂向下的搜索策略。它采用雙重循環(huán)的方式挖掘最大頻繁項(xiàng)集，外層循環(huán)是在MFCS非空狀態(tài)下進(jìn)行，內(nèi)層循環(huán)以自底向上的方式進(jìn)行處理，若MFCS中項(xiàng)集的支持度大于等于最小支持度閾值，則將該項(xiàng)集加入到最大頻繁項(xiàng)集(Maximum Frequent Sets，MFS)中;對(duì)非頻繁項(xiàng)集，通過(guò)循環(huán)每次刪除該項(xiàng)集中的一個(gè)項(xiàng)來(lái)產(chǎn)生新的候選項(xiàng)集，對(duì)于新的候選項(xiàng)集需要判斷在MFS和MFCS中是否存在超集，若不存在則將其加入MFCS中，否則將其刪除。

2 SCOM

2.1主要思想

SCOM策略的主要思想是：在搜索FP-tree計(jì)算候選項(xiàng)集的支持度時(shí)，記錄各個(gè)相關(guān)路徑的支持狀態(tài)；當(dāng)通過(guò)該項(xiàng)集生成新的候選項(xiàng)集時(shí)，根據(jù)性質(zhì)1、2將舊的項(xiàng)集的路徑支持信息傳遞給新的候選項(xiàng)集，這樣在計(jì)算新的候選項(xiàng)集的支持度時(shí)就可以剪除不必要的路徑與候選項(xiàng)集的匹配。SCOM策略理論上適用于所有的DMFIA同類算法。

2.2算法步驟

為了讓SCOM策略能夠較好地發(fā)揮優(yōu)勢(shì)，需要為FP-tree的每一個(gè)節(jié)點(diǎn)增加一個(gè)域item_num，用來(lái)記錄該節(jié)點(diǎn)在Headers中同名鏈表的序號(hào)，也就是在計(jì)算以該項(xiàng)結(jié)尾的候選項(xiàng)集的支持度時(shí)檢索的路徑序號(hào)；為每一個(gè)候選項(xiàng)集X增加一個(gè)二進(jìn)制向量標(biāo)記(binary vector)用以表示路徑對(duì)X的支持情況，記為X.bv。X.bv(i)表示X.bv的第i位，X.bv(i)=0表示路徑i不支持X,X.bv(i)=1表示路徑i支持X。

DMFIA同類算法計(jì)算最大頻繁項(xiàng)集的過(guò)程大致可分為如下幾個(gè)步驟：

(1)初始化候選項(xiàng)集集合；

(2)選取部分候選項(xiàng)集，計(jì)算支持度；

(3)將最大頻繁項(xiàng)集加入到結(jié)果集；

(4)通過(guò)非最大頻繁項(xiàng)集候選項(xiàng)集生成新的候選項(xiàng)集，通過(guò)“超級(jí)檢測(cè)”等策略篩選后，代替步驟(2)中候選項(xiàng)集加入到候選項(xiàng)集集合；

(5)重復(fù)步驟(2)～(4)直到候選項(xiàng)集集合為空。

SCOM策略主要體現(xiàn)在支持度計(jì)算(步驟(2))和新的候選項(xiàng)集生成(步驟(4))之中。支持度計(jì)算過(guò)程如下：

ProcedureComputeCount(FP-tree,Headers,m)

/*Headers為頻繁項(xiàng)頭表，m為待計(jì)算的最后一項(xiàng)為i的候選項(xiàng)集*/

begin

搜索項(xiàng)目頭表Htable的項(xiàng)目名稱域item-name,假設(shè)Htable[q1].item-name=i;

根據(jù)Htable[q1].head找到FP-tree中節(jié)點(diǎn)名稱為i的節(jié)點(diǎn)n1,n2,…,nh;

根據(jù)n1,n2,…,nh及其前綴節(jié)點(diǎn)的父節(jié)點(diǎn)指針域，找到包含i的所有路徑P1,P2,…,Ph;

for(j=1;j≤h;j++) do begin

ifm.bv的第j位為1 then//項(xiàng)集空間搜索方向?yàn)椤白皂斚蛳隆睍r(shí)

m支持?jǐn)?shù)增加ndj.node-count，continue;//性質(zhì)1

/*

ifm.bv的第j位為0 then//項(xiàng)集空間搜索方向?yàn)椤白缘紫蛏稀睍r(shí)

continue;//性質(zhì)2

*/

if路徑Pj包含m,then//

m的支持?jǐn)?shù)增加ndj.node-count;

m.bv的第j位置1

end

end

對(duì)每個(gè)非最大頻繁項(xiàng)集候選項(xiàng)集m,設(shè)M'是由m生成的新的候選項(xiàng)集，則應(yīng)用SCOM策略的算法如下：

begin

for allm'∈M'do begin

ifm'與m的最后一項(xiàng)相同，then

m'.bv=m.bv;

else

ComputeBV(FP-tree,m,m');//由性質(zhì)2根據(jù)路徑的包含關(guān)系計(jì)算路徑支持信息

end

end

ProcedureComputeBV(FP-tree,Headers,m,m')

/*由性質(zhì)2根據(jù)已計(jì)算過(guò)路徑支持信息的m計(jì)算新的候選項(xiàng)集m'的路徑支持信息，I(0)表示全0的二進(jìn)制向量，|m.bv|表示m.bv的長(zhǎng)度*/

/*針對(duì)“自頂向下”的項(xiàng)集空間搜索*/

begin

m'.bv=I(0);

fori=0 to |m.bv| do begin

ifm.bv(i)=0 then continue;

由Headers找到item_name=m末項(xiàng)名稱的第i個(gè)節(jié)點(diǎn)Ni;

ifNi存在item_name=m'末項(xiàng)名稱的祖先節(jié)點(diǎn)Nj,Nj.item_num=jthen

m'.bv(j)=1;

end

/*針對(duì)“自底向上”的項(xiàng)集空間搜索*/

begin

m'.bv=I(1);

fori=0 to |m.bv| do begin

ifm.bv(i)=1 then continue;

由Headers找到item_name=m末項(xiàng)名稱的第i個(gè)節(jié)點(diǎn)Ni；

ifNi存在item_name=m'末項(xiàng)名稱的子孫節(jié)點(diǎn)Nj,Nj.item_num=jthen

m'.bv(j)=0

end

2.3算法實(shí)例

舉例說(shuō)明該策略的優(yōu)化過(guò)程。圖1為一棵數(shù)字頻繁模式樹(shù)。

圖1 數(shù)字頻繁模式樹(shù)

設(shè)X={2,3,5}為已經(jīng)計(jì)算過(guò)支持度的候選項(xiàng)集，則X.bv=(1,0)；Y1={2,5}，Y2={2,3}為“自頂向下”的項(xiàng)集空間搜索算法生成的新候選項(xiàng)集，Y3={2,3,5,6}為根據(jù)自底向上搜索算法生成的新候選項(xiàng)集，根據(jù)SCOM策略能夠快速得出Y1.bv=X.bv=(1,0)，由ComputeBV得Y2.bv=(1,0)，Y3.bv=(1,0,1)，則在計(jì)算Y1、Y2的支持度時(shí)，只需搜索item_name=6的第二條路徑，在計(jì)算Y3的支持度時(shí)，只需搜索第一條路徑與第三條路徑。

3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證SCOM策略的實(shí)際優(yōu)化效果，在8 G RAM，Intel Core i5-2430 M CPU 2.40 GHz，Windows7操作系統(tǒng)上用Java實(shí)現(xiàn)了DMFIA原算法和應(yīng)用了SCOM策略的DMFIA算法SCOM-DMFIA。實(shí)驗(yàn)采用的測(cè)試數(shù)據(jù)集為mushroom，包含有8 124條記錄，記錄平均長(zhǎng)度為23，共有115個(gè)蘑菇屬性。圖2為在不同最小支持度下(分為5%，10%，15%，20%，25%五檔)兩種算法的執(zhí)行時(shí)間對(duì)比結(jié)果。

圖2 mushroom數(shù)據(jù)集上兩種算法的執(zhí)行時(shí)間對(duì)比

從圖2可以看出，應(yīng)用了SCOM策略的DMFIA算法的整體運(yùn)行時(shí)間明顯少于原算法。為了進(jìn)一步說(shuō)明SCOM策略通過(guò)優(yōu)化支持度計(jì)數(shù)進(jìn)而提高最大頻繁項(xiàng)集挖掘算法整體性能的過(guò)程，實(shí)驗(yàn)中還監(jiān)測(cè)了兩種算法用于支持度計(jì)數(shù)的時(shí)間開(kāi)銷，如圖3所示。

圖3 mushroom數(shù)據(jù)集上兩種算法用于支持度計(jì)數(shù)的時(shí)間對(duì)比

從圖3中可以看出，SCOM明顯降低了DMFIA算法用于支持度計(jì)數(shù)的時(shí)間。

以上實(shí)驗(yàn)結(jié)果說(shuō)明，SCOM策略的確能在基于FP-tree的支持度計(jì)數(shù)過(guò)程中減少搜索路徑，降低時(shí)間開(kāi)銷，進(jìn)而提高整個(gè)最大頻繁項(xiàng)集挖掘算法的效率。

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

文中提出的基于FP-tree的支持度計(jì)數(shù)優(yōu)化策略—SCOM，通過(guò)記錄支持度計(jì)算過(guò)程中路徑對(duì)項(xiàng)集的支持情況，依據(jù)相關(guān)性質(zhì)在支持度計(jì)算中搜索FP-tree時(shí)避免不必要的搜索路徑，以達(dá)到搜索優(yōu)化的目的。實(shí)驗(yàn)結(jié)果表明，該策略有效提高了最大頻繁項(xiàng)集挖掘算法DMFIA的運(yùn)行效率，并且可以推廣應(yīng)用到DMFIA的同類算法中。下一步的工作中將進(jìn)一步探究SCOM在其他種類頻繁項(xiàng)集挖掘算法中的適用性。

[1] Agrawal R， Imielinski T，Swami A． Mining association rules between sets of items in large database[C]//Proceedings of 1993 ACM SIGMOD conference on management of data．New York:ACM，1993:207-216．

[2] Han J, Kamber M. Data mining:concepts and techniques[M].Beijing:High Education Press,2001.

[3] 宋余慶，朱玉全，孫志揮，等．基于FP-tree的最大頻繁項(xiàng)目集挖掘及更新算法[J]．軟件學(xué)報(bào)，2003，14(9):1586-1592．

[4] Han J，Pei J，Yin Y．Mining frequent patterns without candidate generation[C]//Proceedings of the 2000 ACM-SIGMOD international conference on management of data．New York:ACM，2000:1-12．

[5] Grahne G，Zhu J．High performance mining of maximal frequent itemset[EB/OL]．[2014-07-06]．http://www．docin．com/p-773109811．html．[6] 吉根林，楊 明，宋余慶，等．最大頻繁項(xiàng)目集的快速更新[J]．計(jì)算機(jī)學(xué)報(bào)，2005，28(1):128-135．

[7] 顏躍進(jìn)，李舟軍，陳火旺．基于FP-Tree有效挖掘最大頻繁項(xiàng)集[J]．軟件學(xué)報(bào)，2005，16(2)：215-222．

[8] 錢雪忠，惠 亮．關(guān)聯(lián)規(guī)則中基于降維的最大頻繁模式挖掘算法[J]．計(jì)算機(jī)應(yīng)用，2011，31(5):1339-1343．

[9] 顏躍進(jìn),李舟軍,陳火旺.一種挖掘最大頻繁項(xiàng)集的深度優(yōu)先算法[J].計(jì)算機(jī)研究與發(fā)展,2005,42(3):462-467.

[10] 陳 晨,鞠時(shí)光.基于改進(jìn)FP-tree的最大頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(24):6236-6239.

[11] 王黎明,趙 輝.基于FP樹(shù)的全局最大頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)研究與發(fā)展,2007,44(3):445-451.

[12] 付冬梅，王志強(qiáng)．基于FP-tree和約束概念格的關(guān)聯(lián)規(guī)則挖掘算法及應(yīng)用研究[J]．計(jì)算機(jī)應(yīng)用研究，2014，31(4):1013-1015．

[13] Tan Pangning．?dāng)?shù)據(jù)挖掘?qū)д摚河⑽腫M].北京：人民郵電出版社，2006.

SupportCountOptimizationMethodBasedonFP-tree

ZHAO Yang，BAI Fan

(Jiangnan Institute of Computer Technology，Wuxi 214083，China)

In the association rules mining,mining frequent itemsets is the most critical step.Maximum frequent itemsets is the most common simplified representation of frequent itemsets.Maximum frequent itemsets mining algorithms based on FP-tree are most needed to search the FP-tree bottom-up to count the support of the itemsets,but they have not considered the information obtained by completed support counting while counting the current itemset,resulting in unnecessary overhead.To solve it,Support Count Optimization Method on FP-tree,called SCOM for short,is proposed.With a small additional space cost,it can make full use of the information that whether a path supports a itemset and the relation between the itemsets to prune the search.Experimental results show that the maximum frequent itemsets mining algorithm applied obtains a performance boost with SCOM which optimizes the support count based on FP-tree,so it can be applied to all algorithms that use FP-tree to count support.

association rules mining;FP-tree;maximum frequent itemsets;support count;search prune

TP311

A

1673-629X(2017)10-0030-04

2016-11-14

2017-03-16 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-07-11

國(guó)家科技重點(diǎn)專項(xiàng)“核高基”(2015ZX01040-201)

趙 陽(yáng)(1991-)，男，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘、文本分析及可視化；導(dǎo)師：劉鎮(zhèn)江，高級(jí)工程師，研究方向?yàn)閿?shù)據(jù)挖掘、信息處理、數(shù)據(jù)可視化。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170711.1457.090.html

10.3969/j.issn.1673-629X.2017.10.007