陳冬玲,曾 文

(1.沈陽(yáng)大學(xué) 信息科學(xué)與工程學(xué)院,遼寧 沈陽(yáng) 110044;2.中國(guó)科學(xué)技術(shù)信息研究所,北京 100038)

頻繁模式挖掘中基于CFP的應(yīng)用模型

陳冬玲1,曾 文2

(1.沈陽(yáng)大學(xué) 信息科學(xué)與工程學(xué)院,遼寧 沈陽(yáng) 110044;2.中國(guó)科學(xué)技術(shù)信息研究所,北京 100038)

為進(jìn)一步提高頻繁模式挖掘效率,對(duì)CFP構(gòu)造算法做了部分改進(jìn),并提出了一些基于此結(jié)構(gòu)的應(yīng)用方法.實(shí)驗(yàn)和分析表明,改進(jìn)的CFP算法在各種不同的數(shù)據(jù)挖掘應(yīng)用中更加有效.

頻繁模式;挖掘算法;應(yīng)用方法;CFP

頻繁模式挖掘是目前一個(gè)重要的研究領(lǐng)域,并得到了廣泛的應(yīng)用.目前頻繁模式的挖掘主要有兩類(lèi)算法.一類(lèi)是基于A(yíng)priori的廣度優(yōu)先算法[1].這種方法的思想是如果一個(gè)模式不是頻繁模式,那么包含此模式的超模式也一定不是頻繁模式.采用循環(huán)的方式,通過(guò)長(zhǎng)度為L(zhǎng)-1的頻繁模式,組合成長(zhǎng)度為L(zhǎng)的候選模式,然后掃描數(shù)據(jù)庫(kù)得到長(zhǎng)度為L(zhǎng)的頻繁模式.這類(lèi)方法的思想簡(jiǎn)單,也不需要復(fù)雜的數(shù)據(jù)結(jié)構(gòu),容易實(shí)現(xiàn).但這種generation-and-test的方法需要產(chǎn)生大量的候選集,而且需要多次的掃描數(shù)據(jù)庫(kù),這個(gè)過(guò)程需要花費(fèi)大量的時(shí)間.另一類(lèi)是基于FP-growth的深度優(yōu)先算法[2-4],這種算法采用一種新穎的、緊湊的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)庫(kù)中所有的頻繁項(xiàng).因?yàn)轭l繁模式中的所有項(xiàng)必須是頻繁項(xiàng),所以挖掘過(guò)程不需要在整個(gè)數(shù)據(jù)庫(kù)中進(jìn)行.即先掃描數(shù)據(jù)庫(kù),得到所有的頻繁項(xiàng),把所有的頻繁項(xiàng)按照一定的順序插入到頻繁模式樹(shù)中(FP-tree).和Apriori相比,此算法不需要多次重復(fù)掃描數(shù)據(jù)庫(kù),前綴結(jié)構(gòu)也可以共享大量的節(jié)點(diǎn).但這種方法結(jié)構(gòu)復(fù)雜,FP-tree也只能存儲(chǔ)在內(nèi)存中,挖掘過(guò)程還將不斷的在內(nèi)存中產(chǎn)生條件模式樹(shù),所以數(shù)據(jù)集過(guò)大時(shí),FP-growth算法需要的空間將超過(guò)內(nèi)存空間.因此這種僅能在內(nèi)存中進(jìn)行的挖掘方法只能直接應(yīng)用于相對(duì)較小的數(shù)據(jù)集.

這兩類(lèi)方法都是耗時(shí)耗空間的過(guò)程,每個(gè)用戶(hù)對(duì)挖掘結(jié)果也有不同的要求,如果每次都對(duì)整個(gè)數(shù)據(jù)集進(jìn)行掃描,消耗是巨大的.文獻(xiàn)[5-6]提出了一種基于硬盤(pán)的數(shù)據(jù)結(jié)構(gòu)CFP(Condense Frequent Pattern Tree)樹(shù)來(lái)存儲(chǔ)從數(shù)據(jù)集中提取出來(lái)的頻繁閉模式[7],以后需要此數(shù)據(jù)集的某些信息只需要訪(fǎng)問(wèn)CFP樹(shù),而不需要再次掃描整個(gè)數(shù)據(jù)集.文中對(duì)CFP樹(shù)構(gòu)造算法提出一些改進(jìn),并應(yīng)用此CFP結(jié)構(gòu)來(lái)解決一些實(shí)際挖掘問(wèn)題,實(shí)驗(yàn)表明效果是顯著的.

1 CFP樹(shù)

1.1 CFP樹(shù)的結(jié)構(gòu)

CFP樹(shù)存儲(chǔ)的是整個(gè)數(shù)據(jù)庫(kù)的頻繁閉模式,這樣避免了存儲(chǔ)大量重復(fù)的模式.例如,{c:3,cp:3,cm:3,ca:3,cmp:3,cpa:3,cma:3,camp:3}這些模式可以由一個(gè)單一的頻繁閉模式cpma:3代替.一個(gè)模式X是頻繁閉模式就是不存在一個(gè)X的超模式X′,使X?X′且Support(X)=Support(X′).這樣的情況在現(xiàn)實(shí)數(shù)據(jù)集中是常見(jiàn)的.圖1a為數(shù)據(jù)集,圖1b、圖1c分別是此數(shù)據(jù)集的頻繁模式和頻繁閉模式,圖1d則是相應(yīng)的頻繁模式樹(shù).

如圖1d所示,每個(gè)CFP樹(shù)中每一個(gè)節(jié)點(diǎn)都表示成一個(gè)可變長(zhǎng)度的數(shù)組(root節(jié)點(diǎn)除外),數(shù)組中的每一項(xiàng)都可以當(dāng)作一個(gè)子樹(shù)入口,一個(gè)節(jié)點(diǎn)中的所有項(xiàng)根據(jù)它們的支持度按升序排列.此樹(shù)中的每一條完整路徑都代表一個(gè)頻繁閉模式,同一節(jié)點(diǎn)指向的子樹(shù)都有相同的前綴.對(duì)于某個(gè)節(jié)點(diǎn)中的入口E,假設(shè)從根到入口E代表的模式是p,那么入口E存儲(chǔ)如下四個(gè)方面的信息:①p中的最后一個(gè)項(xiàng);②p的支持計(jì)數(shù);③一個(gè)指向以p為前綴的子CFP樹(shù)根節(jié)點(diǎn)的指針;④一個(gè)hash表,用來(lái)表示指針指向的CFP樹(shù)中所有存在的項(xiàng).對(duì)于每一個(gè)入口E,E.item表示儲(chǔ)存在E中的項(xiàng),E.support表示其支持計(jì)數(shù),E.child表示指向子CFP樹(shù)根節(jié)點(diǎn)的指針,E.hashtable表示其hash表(root節(jié)點(diǎn)沒(méi)有在圖中畫(huà)出來(lái),它只是一個(gè)入口,和一個(gè)入口項(xiàng)對(duì)應(yīng)的hash表,并沒(méi)有任何項(xiàng)的信息).

圖1 CFP樹(shù)Fig.1 CFP-tree

1.2 CFP樹(shù)的性質(zhì)

CFP樹(shù)之所以是緊湊的,并不僅僅是因?yàn)樗淮鎯?chǔ)頻繁閉模式,而是不同模式的相同前綴可以存儲(chǔ)在一條路徑中.這一點(diǎn)可以節(jié)省大量的空間,而不必分開(kāi)存儲(chǔ)所有的頻繁模式.另外CFP樹(shù)還有如下重要性質(zhì)可以為將來(lái)的運(yùn)用提供方便[5-6].

(1) Apriori性質(zhì).對(duì)于CFP樹(shù)中節(jié)點(diǎn)的每一個(gè)入口E,由E指向的子樹(shù)中所有模式的支持計(jì)數(shù)都不可能大于E.support.可以利用這一性質(zhì)來(lái)簡(jiǎn)化查詢(xún)過(guò)程,如果入口的支持計(jì)數(shù)不滿(mǎn)足用戶(hù)定義的最小支持界限,那么就不需要繼續(xù)查詢(xún)E所指向的子CFP樹(shù).

(2) 左保留性質(zhì).從CFP樹(shù)的結(jié)構(gòu)可以看出,每一個(gè)節(jié)點(diǎn)中的項(xiàng)按頻繁計(jì)數(shù)升序排列,同時(shí)每一個(gè)入口所指向的子CFP樹(shù)中的項(xiàng)都是頻繁計(jì)數(shù)更高的項(xiàng),即對(duì)于入口E,E.item只可能出現(xiàn)在E以前的入口所指向的子樹(shù)或E自身中.也就是說(shuō),如果要找到一個(gè)包含E.item的模式,只需要查找E以前的入口和E自己所指向的子樹(shù).

(3) 提前返回性質(zhì).因?yàn)镃FP樹(shù)節(jié)點(diǎn)的每一個(gè)入口E都有一個(gè)hash表,表中記錄了E指向的子CFP樹(shù)包含的所有項(xiàng).也就是說(shuō)對(duì)一個(gè)入口E,如果其指向的子樹(shù)中包含項(xiàng)i,那么hash表的第j個(gè)位置將設(shè)為1,j=imodN,N是此hash表的長(zhǎng)度.有此結(jié)構(gòu),在訪(fǎng)問(wèn)子樹(shù)前,先通過(guò)檢查hash表來(lái)判斷要查找模式的所有項(xiàng)是否在子樹(shù)中,如果在,訪(fǎng)問(wèn)繼續(xù)進(jìn)行,否則,查詢(xún)過(guò)程提前終止.這樣,查詢(xún)過(guò)程不需要每次訪(fǎng)問(wèn)所有的節(jié)點(diǎn).在這里,hash表的大小是根據(jù)CFP樹(shù)的大小和查詢(xún)時(shí)間來(lái)平衡設(shè)定的.

1.3 CFP樹(shù)的構(gòu)造

CFP樹(shù)的一個(gè)重要性質(zhì)是它的每一條完整路徑都是一個(gè)頻繁閉模式,這樣大大節(jié)省了存儲(chǔ)空間,所以在樹(shù)的構(gòu)造過(guò)程中如何移除重復(fù)模式是一個(gè)重要問(wèn)題.文獻(xiàn)[5-6]中提出了有效的CFP構(gòu)造算法,但并沒(méi)有在樹(shù)的構(gòu)造過(guò)程中移除重復(fù)模式,而是在挖掘過(guò)程中進(jìn)行的.本文基于文獻(xiàn)[8-9]的研究,提出了對(duì)CFP算法的一些改進(jìn).

已知一個(gè)事務(wù)數(shù)據(jù)庫(kù)D和一個(gè)最小支持閾值,系統(tǒng)需要掃描兩次數(shù)據(jù)庫(kù)來(lái)構(gòu)造CFP樹(shù).首先掃描一次數(shù)據(jù)庫(kù)得到所有的頻繁項(xiàng)集,并根據(jù)它們的頻繁計(jì)數(shù)按升序排列.例如,系統(tǒng)得到頻繁項(xiàng)集F={i1,i2,…,im}.i1,i2,…,im按其頻繁計(jì)數(shù)升序排列.然后第二次掃描數(shù)據(jù)庫(kù),對(duì)每一個(gè)ij∈F,構(gòu)造條件數(shù)據(jù)庫(kù)Dij.在第二次掃描的過(guò)程中,刪除每一個(gè)事務(wù)t中的不頻繁項(xiàng)并使t中保留的項(xiàng)按F中的順序排列.如果此時(shí)事務(wù)t中的第一個(gè)項(xiàng)是ij,就把t放到條件數(shù)據(jù)庫(kù)Dij中.這樣條件數(shù)據(jù)庫(kù)就包含所要挖掘的全部信息,系統(tǒng)不需要再次訪(fǎng)問(wèn)原始數(shù)據(jù)庫(kù).

首先挖掘Di1得到所有包含i1的頻繁模式,挖掘條件數(shù)據(jù)庫(kù)跟挖掘原始數(shù)據(jù)庫(kù)采用一樣的方式,這是一個(gè)遞歸的過(guò)程,當(dāng)在Di1上的挖掘過(guò)程結(jié)束后,Di1可以立即被拋棄.雖然它還可能包含其他的項(xiàng),但這些項(xiàng)都會(huì)在挖掘結(jié)束后插入到別的條件數(shù)據(jù)庫(kù)中,所以?huà)仐塂i1并不會(huì)丟失任何挖掘信息.如對(duì)Di1中的事務(wù)t,此事務(wù)中i1的下一個(gè)項(xiàng)是ij,那么t=t-i1,然后把t插入到條件數(shù)據(jù)庫(kù)Dij中,顯然對(duì)i1挖掘以后,t別入到Di1以后的條件數(shù)據(jù)庫(kù)中.隨著j的增大,條件數(shù)據(jù)庫(kù)Dij中的事務(wù)將越來(lái)越多,但每條事務(wù)的長(zhǎng)度會(huì)變短.這一插入過(guò)程叫做PushRemain[5-6].

CFP樹(shù)最重要的特征是它只存儲(chǔ)頻繁閉模式,下面將討論如何在樹(shù)的構(gòu)造過(guò)程中移除重復(fù)模式.根據(jù)CFP樹(shù)的特點(diǎn),考慮一節(jié)點(diǎn)N,如果要在這個(gè)節(jié)點(diǎn)中插入i,假設(shè)從根節(jié)點(diǎn)到N所代表的模式為p,插入i后得到模式p∩i:sup(i).

考慮節(jié)點(diǎn)N的一個(gè)入口E所有指向的子樹(shù)包含i,而且支持度也為sup(i),此時(shí)存在模式p∩E.item∩i:sup(i),顯然

(1)

由式(1)可以得到,是否需要在節(jié)點(diǎn)N中插入i:sup(i),需要檢查N的任何子樹(shù)中是否包含i,且支持度也為sup(i).考慮CFP節(jié)點(diǎn)中有hash表,所以可以在N的每一個(gè)入口判斷i是否存在于某個(gè)子樹(shù)中,如存在,就向下找到在此模式的支持度,如果(p∩E.item∩i).sup(i)=(p∩i).sup(i),p∩i不可能是頻繁閉模式,因此i:sup(i)就不需要插入節(jié)點(diǎn)N中,從而達(dá)到重復(fù)移除的效果.算法偽碼如下:

Algorithm 1 CFP-Construct Algorithm

Input:

p是一個(gè)頻繁模式.

Dp是模式p的條件數(shù)據(jù)庫(kù).

Ep是CFP樹(shù)中模式p所代表的入口.

min_sup是最小支持度閾值.

Detail:

1) 掃描Dp,得到Dp中所有的頻繁項(xiàng)和它們各自的支持度,用F={i1:sup(i1),i2:sup(i2),…,in:sup(in)}表示這些頻繁項(xiàng)的排列;

2) 建立一個(gè)新節(jié)點(diǎn)cnode,Ep.child=cnode,新節(jié)點(diǎn)暫時(shí)為空;

3) 對(duì)于所有的i∈F,把i的信息填入hash表中,即Ep.hashtable[imodN]=1,Dp∪i=?; 循環(huán)結(jié)束(end for)

4) 對(duì)任一事務(wù)t∈Dp, 移除t中的非頻繁項(xiàng),把剩余的項(xiàng)按他們?cè)贔中的順序排列; 假設(shè)i是t中的第一項(xiàng),把t插入到Dp∪i中; 循環(huán)結(jié)束(end for)

5) 對(duì)所有的i:sup(i)∈F, 通過(guò)入口Ep所指向子樹(shù)的根節(jié)點(diǎn)rootp,檢查i是否存在于根節(jié)點(diǎn)rootp所有入口指向的子樹(shù)中,如果存在,訪(fǎng)問(wèn)子樹(shù),判斷子樹(shù)中i的支持度是否等于sup(i),如果等于p∩i不可能是頻繁閉模式,繼續(xù)F中的下一個(gè)項(xiàng); 否則,s=p∩{i},把i插入到rootp中的正確位置;Es=i在rootp中的正確位置; CFP_Construct(s,Ds,Es,min_sup); PushRemain(Ds); ∥把Ds中的事務(wù)按第一個(gè)元素插入到合適的條件數(shù)據(jù)庫(kù) 循環(huán)結(jié)束(end for)

2 CFP樹(shù)的應(yīng)用

這種基于磁盤(pán)的頻繁閉模式存儲(chǔ)結(jié)構(gòu)能為多次數(shù)據(jù)庫(kù)查詢(xún)提供方便,文獻(xiàn)[5-6]提出了最小支持度限制的查詢(xún)和項(xiàng)集限制的查詢(xún)方法.因?yàn)樵诂F(xiàn)實(shí)應(yīng)用中,不同用戶(hù)需要挖掘到不同的信息,在挖掘過(guò)程中插入不同的條件[10],所以需要對(duì)同一數(shù)據(jù)集進(jìn)行多次不同的挖掘.利用CFP結(jié)構(gòu),僅僅需要在此緊湊的數(shù)據(jù)結(jié)構(gòu)中進(jìn)行挖掘,而不需要訪(fǎng)問(wèn)龐大的原始數(shù)據(jù)庫(kù).而且CFP樹(shù)的結(jié)構(gòu)特點(diǎn),系統(tǒng)可以更大程度地減少開(kāi)銷(xiāo).

2.1 帶權(quán)的頻繁閉模式挖掘

CFP是數(shù)據(jù)集的所有頻繁閉模式組成的樹(shù)結(jié)構(gòu),由樹(shù)的構(gòu)造過(guò)程可知,同一個(gè)模式不可能出現(xiàn)在兩條路徑上,所以每次只需要訪(fǎng)問(wèn)一條路徑,可見(jiàn)在此結(jié)構(gòu)上提取頻繁閉模式非常方便.如訪(fǎng)問(wèn)到某個(gè)節(jié)點(diǎn),得到的前綴模式為p:sup(p),那么從其中的一個(gè)入口向下訪(fǎng)問(wèn),下一個(gè)項(xiàng)為i:sup(i),如果sup(i)

但通常用戶(hù)并不是要簡(jiǎn)單的找到頻繁閉模式.如對(duì)于一個(gè)大型的百貨公司,在一個(gè)星期內(nèi)賣(mài)出了100塊某種香皂,卻只賣(mài)出了10臺(tái)某一型號(hào)的電冰箱,但這10臺(tái)電冰箱顯然比100塊香皂能給商家?guī)?lái)更多的效益.所以在這里要引入一個(gè)權(quán)值(weight)的概念,權(quán)值通常用來(lái)衡量對(duì)象的重要程度.因此,帶權(quán)的模式挖掘有很多重要的作用,如上所述的商品利益也是挖掘的重要因素.帶權(quán)的模式挖掘還可以用來(lái)異常檢測(cè),醫(yī)療診斷等.

文獻(xiàn)[11]中提出利用FP-tree進(jìn)行帶權(quán)限制的無(wú)損頻繁閉模式挖掘,在這里將研究在CFP結(jié)構(gòu)中進(jìn)行此挖掘的算法,CFP結(jié)構(gòu)儲(chǔ)存的信息量不僅遠(yuǎn)小于由原始構(gòu)造的FP-tree,而且由于它自身的構(gòu)造特點(diǎn),可以有效的節(jié)省挖掘消費(fèi).

一般的頻繁模式挖掘都具有Apriori性質(zhì),但帶權(quán)的頻繁閉模式挖掘則不能應(yīng)用此性質(zhì),如對(duì)于圖1所示的數(shù)據(jù)集,假設(shè)每個(gè)項(xiàng)都有一個(gè)權(quán)值Weigths(F)={c:0.70,d:0.60,p:0.60,f:0.65,m:0.50,a:0.90}(冒號(hào)后面的小數(shù)代表權(quán)值),定義一個(gè)模式p的權(quán)值計(jì)算方法為

(2)

定義最小權(quán)值限制為2,對(duì)于模式cmp:3和cmpa:3,weigth(cmp)=1.800,weight(cmpa)=2.025,顯然模式cmp不滿(mǎn)足條件,而cmpa滿(mǎn)足,顯然不能應(yīng)用Apriori性質(zhì)通過(guò)一個(gè)模式不滿(mǎn)足條件而放棄檢查超模式.在此挖掘過(guò)程中,有權(quán)值和閉模式兩種限制,文獻(xiàn)[11]中已證明,這兩種限制要按照固定的順序插入到挖掘過(guò)程中,即先判斷權(quán)值條件是否滿(mǎn)足,然后判斷是否為閉模式,否則會(huì)造成信息丟失.挖掘算法WC_FPMining算法如下:

Algorithm 2 WC_FPMining Algorithm

Input:

P是一個(gè)頻繁模式

cnode是p指向的CFP樹(shù)節(jié)點(diǎn)

min_sup為最小支持度閾值

min_wei是最小權(quán)值閾值

算法:

1) 如果p≠?,weigth(p)≥min_sup,此時(shí)p滿(mǎn)足權(quán)值條件,然后節(jié)點(diǎn)p中的hash表中中找出支持度等于sup(p)且權(quán)值最大的項(xiàng)i;

2) 計(jì)算weigth(p∪i),如果weigth(p∪i)>min_wei,顯然還存在滿(mǎn)足條件的p的超集,這樣不需要輸出p,否則p就是一個(gè)帶權(quán)的頻繁閉模式;

3) for對(duì)于所有的入口E∈cnode, WC_FPMining(p,E.child,min_sup,min_wei); WC_FPMing(p∪E.item,E.child,min_sup,min_wei); End for(循環(huán)結(jié)束)

2.2 基于CFP樹(shù)的關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)規(guī)則的挖掘[12-14]是數(shù)據(jù)挖掘中的一個(gè)基本領(lǐng)域.關(guān)聯(lián)規(guī)則的定義如下:

在CFP中進(jìn)行關(guān)聯(lián)規(guī)則挖掘可以采用Apriori方法,逐代產(chǎn)生頻繁模式并判斷模式之間能否滿(mǎn)足可信度要求.在這個(gè)過(guò)程中可以用到CFP樹(shù)中的左保留性質(zhì),比如要判斷A?B是否為關(guān)聯(lián)規(guī)則,只需要在包含A或B的最后一個(gè)入口的左邊查找,這樣可以更加縮小操作的范圍.這樣不僅不需要訪(fǎng)問(wèn)龐大的原始數(shù)據(jù)庫(kù),還可以利用CFP樹(shù)本身的性質(zhì)提高挖掘效率.

3 實(shí)驗(yàn)和分析

為了檢驗(yàn)改進(jìn)的CFP結(jié)構(gòu)的工作效率及有效性,采用人工數(shù)據(jù)集,用VC++做平臺(tái)編寫(xiě)了部分實(shí)驗(yàn)代碼,在同一數(shù)據(jù)集上分別用FP-growth挖掘頻繁模式和先構(gòu)造CFP樹(shù)然后挖掘頻繁模式兩種方式進(jìn)行對(duì)比.

由于文中提出的CFP結(jié)構(gòu),其基本框架仍然是深度優(yōu)先策略,因而對(duì)單個(gè)實(shí)驗(yàn)而言,文中所提出的改進(jìn)CFP結(jié)構(gòu)的方法對(duì)提高數(shù)據(jù)庫(kù)的挖掘效率并沒(méi)有明顯的提高.但若對(duì)于多次不同的挖掘工作,實(shí)驗(yàn)表明:其一,對(duì)于適時(shí)數(shù)據(jù)集的挖掘,一旦數(shù)據(jù)集發(fā)生了更新,利用CFP結(jié)構(gòu)中存儲(chǔ)的原始數(shù)據(jù)集信息,可以只操作更新的信息,然后利用相應(yīng)的策略把更新的信息插入到此動(dòng)態(tài)結(jié)構(gòu)中,不需要操作整個(gè)更新的數(shù)據(jù)集就可以得到此數(shù)據(jù)集中有用的信息;其二,為分布式數(shù)據(jù)挖掘提供方便,因?yàn)榇私Y(jié)構(gòu)是基于硬盤(pán)的動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu),因而可以從每個(gè)客戶(hù)端得到一個(gè)存儲(chǔ)局部模式的CFP樹(shù),通過(guò)文件的形式傳遞給服務(wù)器,然后由服務(wù)器合成一個(gè)全局CFP樹(shù).此結(jié)構(gòu)可以有效的處理分布式數(shù)據(jù)庫(kù)的更新問(wèn)題.

4 結(jié) 論

文中對(duì)CFP結(jié)構(gòu)做了改進(jìn),并利用CFP結(jié)構(gòu)解決數(shù)據(jù)挖掘中的重要問(wèn)題.實(shí)驗(yàn)表明,經(jīng)改進(jìn)的CFP結(jié)構(gòu)在應(yīng)用中會(huì)大大提高數(shù)據(jù)挖掘的效率,它可以利用有限的資源完成需要解決的問(wèn)題.但此方法并沒(méi)有考慮CFP樹(shù)的更新和合成問(wèn)題,這是在適時(shí)數(shù)據(jù)流和分布式數(shù)據(jù)挖掘中的兩大關(guān)鍵問(wèn)題[15],在以后研究中,也會(huì)考慮加權(quán)聚類(lèi)的挖掘方式[16]與CFP方法的結(jié)合.

[1] Han J,Dong G,Yin Y.Efficient Mining of Partial Periodic Patterns in Time Series Database[C]∥Proceedings of 15th International Conference on Data Engineering,Sydney,NSW,1999.Washington,DC: IEEE Computer Society,1999:106-115.

[2] 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,2000.New York: ACM,2000:1-12.

[3] Xin D,Han J,Yan X,et al.Mining Compressed Frequent-Pattern Sets[C]∥Proceedings of the 31st International Conference on Very Large Data Bases,Trondheim,Norway,2005.VLDB Endowment,2005:709-720.

[4] Borgelt C.Keeping Thing Simple: Finding Frequent Item Sets by Recursive Elimination[C]∥Proceedings of the 1st International Workshop on Open Source Data Mining: Frequent Pattern Mining Implementations,Chicago,USA,2005.New York: ACM,2005:66-70.

[5] Liu G,Lu H,Lou W,et al.On Computing,Storing and Querying Frequent Patterns[C]∥Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,DC,USA,2003.New York: ACM,2003:607-612.

[6] Liu G,Lu H,Yu J X.CFP-Tree: A Compact Disk-Based Structure for Storing and Querying Frequent Itemsets[J].Information Systems,2007,32(2):295-319.

[7] Gade K,Wang J,Karypis G..Efficient Closed Pattern Mining in the Presence of Tough Block Constraints[C]∥Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2004.New York: ACM,2004:138-147.

[8] Hou J,Li C.A Pattern Growth Method Based on Memory Indexing for Frequent Patterns Mining[C]∥International Conference on Computational Intelligence for Modelling,Control and Automation,2005 and International Conference on Intelligent Agents,Web Technologies and Internet Commerce,Vienna,2005.IEEE: 663-668.

[9] Tseng F,Hsu C.Generating Frequent Pattern with the Frequent Pattern List[C]∥Proceedings of the 5th Pacific-Asia Conference on Knowledge Discovery and Data Mining,Hong Kong,China,2001.London: Springer-Verlag,2001:376-386.

[10] Chen Y,Hu Y.Constraint-Based Sequential Pattern Mining: The Consideration of Recency and Compactness[J].Decision Support Systems,2006,42(2):1203-1215.

[11] Yun U.Mining Lossless Closed Frequent Patterns with Weight Constraints[J].Knowledge-Based Systems,2007,20(1):86-97.

[12] Palshikar G K,Kale M S,Apte M M.Association Rules Mining Using Heavy Itemsets[J].Data & Knowledge Engineering,2007,61(1):93-113.

[13] Wolff R,Schuster A.Association Rule Mining in Peer-to-Peer Systems[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B: Cybernetics,2004,34(6):2426-2438.

[14] Nanopoulos A,Papadopoulos A N.,Manolopoulos Y.Mining Association Rules in Very Large Clustered Domains[J].Information Systems,2007,32(5):649-669.

[15] Chuang K,Chen M.Frequent Pattern Discovery with Memory Constraint[C]∥Proceedings of the 14th ACM International Conference on Information and Knowledge Management,2005.New York: ACM,2005:345-346.

[16] 原忠虎,李佳,張博.一種加權(quán)的系統(tǒng)聚類(lèi)方法及應(yīng)用[J].沈陽(yáng)大學(xué)學(xué)報(bào):自然科學(xué)版,2014,24(3):201-207.

(Yuan Zhonghu,Li Jia,Zhang Bo.A Weighted System Clustering Method and its Application[J].Journal of Shenyang University: Natural Science,2014,26(3):201-207.)

【責(zé)任編輯: 肖景魁】

Application Model Based on CFP in Mining Frequent Patterns

ChenDongling1,ZengWen2

(1.School of Information Engineering,Shenyang University,Shenyang 110044,China; 2.Institute of Scientific and Technical Information of China,Beijing 100038,China)

In order to further improve the efficiency of frequent patterns mining,the CFP construction algorithm is improved and some applications on this structure are proposed.The experiments demonstrate that,the improved CFP algorithm can make different applications more effective and efficient.

frequent pattern; mining algorithm; application method; CFP

2015-01-09

遼寧省博士啟動(dòng)基金資助項(xiàng)目(20101074); 國(guó)家社會(huì)科學(xué)基金資助項(xiàng)目(14BTQ038); 中國(guó)科學(xué)技術(shù)信息研究所科研項(xiàng)目預(yù)研資金資助項(xiàng)目(YY-201416).

陳冬玲(1973-),女,吉林四平人,沈陽(yáng)大學(xué)副教授,博士.

2095-5456(2015)04-0296-06

TP 274

A