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

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

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