頻繁子樹(shù)挖掘及其剪枝策略研究.pdf

1、頻繁子樹(shù)挖掘是一個(gè)重要的數(shù)據(jù)挖掘問(wèn)題，其主要任務(wù)是從大型數(shù)據(jù)庫(kù)中挖掘出頻繁子樹(shù)模式。由于其廣泛的應(yīng)用領(lǐng)域，已涉及到XML數(shù)據(jù)庫(kù)、分子數(shù)據(jù)庫(kù)、關(guān)系數(shù)據(jù)庫(kù)、圖形數(shù)據(jù)庫(kù)等應(yīng)用和研究領(lǐng)域，頻繁子樹(shù)挖掘已經(jīng)引起了數(shù)據(jù)庫(kù)研究人員和實(shí)踐者的強(qiáng)烈關(guān)注。
　　 現(xiàn)有的頻繁子樹(shù)挖掘算法大都基于Apriori性質(zhì)，主要包含候選模式的生成和支持度計(jì)算兩個(gè)主要步驟。在候選模式生成階段，所有的(k+1)階候選模式都是由頻繁的k階模式連接生成的。這些算法的主

2、要瓶頸在于會(huì)生成大量的候選模式，顯然對(duì)于這樣大量的候選模式做的支持度計(jì)算所花費(fèi)的代價(jià)是十分昂貴的。事實(shí)上大量的子樹(shù)候選模式是非頻繁的或者說(shuō)在數(shù)據(jù)庫(kù)中根本就不會(huì)出現(xiàn)。
　　 本文分析了現(xiàn)有頻繁子樹(shù)挖掘算法中采用的剪枝策略，在此基礎(chǔ)上我們提出了一種新的剪枝策略F2SC(Frequent2-Subtree Checking)。該策略將所有的頻繁2階子樹(shù)保存在一張哈希表中，當(dāng)生成k階子樹(shù)候選模式(k≥3)時(shí)，可通過(guò)檢測(cè)那張保存了F2的哈