頻繁模式增長(zhǎng)算法FP-growth的優(yōu)化研究.pdf

1、長(zhǎng)期以來(lái),挖掘頻繁模式主要采用Apriori算法及其改進(jìn)形式,這類算法需要產(chǎn)生大量候選項(xiàng)集,并反復(fù)掃描數(shù)據(jù)庫(kù),降低了挖掘的效率。FP-growth算法是一種基于模式增長(zhǎng)的頻繁模式挖掘算法,避免了大量候選項(xiàng)集的產(chǎn)生,只需掃描數(shù)據(jù)庫(kù)兩次。效率比Apriori算法快一個(gè)數(shù)量級(jí)。然而,此算法在挖掘頻繁模式時(shí)不可避免地需要遞歸地創(chuàng)建附加數(shù)據(jù)結(jié)構(gòu)(如條件FP-tree,項(xiàng)頭表),并且每當(dāng)模式增長(zhǎng)時(shí)就要?jiǎng)?chuàng)建一次。動(dòng)態(tài)地創(chuàng)建如此大量的附加數(shù)據(jù)結(jié)構(gòu),將耗

2、費(fèi)大量時(shí)間和空間。
　　本文提出了 FP-growth算法的一種優(yōu)化方法:基于升序 FP-tree的挖掘算法SAFP-merge。其通過(guò)采用基于支持度計(jì)數(shù)升序排列的頻繁1-項(xiàng)集的構(gòu)造策略,和引入第一棵子樹(shù)及擴(kuò)展頻繁集等概念,使整個(gè)挖掘過(guò)程直接在初始生成的升序FP-tree中進(jìn)行,而不需要另外遞歸創(chuàng)建條件FP-tree和項(xiàng)頭表。挖掘時(shí),首先挖掘第一棵子樹(shù);然后將第一棵子樹(shù)根結(jié)點(diǎn)的所有分支與升序FP-tree的其他分支歸并,并同時(shí)剪掉

3、第一棵子樹(shù);最后對(duì)新的升序FP-tree遞歸調(diào)用挖掘過(guò)程,直到樹(shù)只有一棵子樹(shù),且已經(jīng)挖掘完該子樹(shù)。為了驗(yàn)證SAFP-merge算法的性能,我們?cè)谝欢ǖ膶?shí)驗(yàn)條件下對(duì)優(yōu)化算法SAFP-merge和FP-growth算法進(jìn)行了測(cè)試,實(shí)驗(yàn)結(jié)果表明:使用相同的稀疏數(shù)據(jù)集,優(yōu)化算法速度是 FP-growth算法的3倍,而所需要的存儲(chǔ)空間比FP-growth算法節(jié)省了1/3;對(duì)于稠密數(shù)據(jù)集,優(yōu)化算法的優(yōu)勢(shì)更加顯著。
　　目前數(shù)據(jù)挖掘技術(shù)在國(guó)外應(yīng)