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

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

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