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

趙 陽，白 凡

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

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

趙 陽，白 凡

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

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

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

0 引 言

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