頻繁子樹挖掘及其在XML挖掘中的應用研究.pdf

1、頻繁模式挖掘是數(shù)據(jù)挖掘領域中的一個重要問題，其研究范圍包括事務、序列、樹和圖。頻繁子樹挖掘在生物信息學，Web挖掘，化合物結構分析等領域具有十分重要的應用價值，因此受到研究人員的高度重視。XML己經成為Internet上數(shù)據(jù)描述和交換的標準。如何從XML數(shù)據(jù)中挖掘有價值的知識是一個具有挑戰(zhàn)性的研究課題。本文就頻繁子樹挖掘方法、最大頻繁Embedded子樹挖掘、基于可變支持度約束的最大頻繁Induced與Embedded子樹挖掘、以及頻繁

2、子樹挖掘在XML挖掘中的應用等方面作了深入的研究。本文的主要研究工作包括以下幾個方面： (1)對近些年來提出的頻繁子樹挖掘算法進行綜述與分析。論述了各種頻繁子樹挖掘算法的思想，并對典型算法的性能進行了實驗分析與比較。 (2)提出了一種高效的最大頻繁Embedded子樹挖掘算法-CMPEFreeMiner，該算法采用帶節(jié)點范圍的先序遍歷序列存儲樹，并采用偽投影技術對頻繁子序列進行投影，對投影序列中的每個節(jié)點編碼。在挖掘帶編

3、碼頻繁子序列過程中使用剪枝技術盡早刪除最終不能通過投影編碼生成最大頻繁Embedded子樹的帶編碼頻繁子序列，大大降低了搜索空間，節(jié)省了時間與空間的代價。實驗結果表明CMPETreeMiner具有較高的效率。 (3)提出了快速挖掘可變支持度約束的閉合與最大頻繁Induced子樹算法-SCCMTreeMiner，采用最右擴展技術枚舉候選子樹，并利用最小有效擴展性質進行剪枝，在變化的支持度約束下求出所有閉合頻繁子樹以及最大頻繁子樹。

4、實驗結果表明，SCCMTreeMiner算法不僅能夠有效地減少所產生子樹的數(shù)量，而且在執(zhí)行時間上也大大少于使用固定支持度的同類算法。 (4)提出了快速挖掘可變支持度約束的閉合與最大頻繁Embedded子樹算法--SCCMEFreeMiner，通過對頻繁k-子樹的每個增長點構造投影數(shù)據(jù)庫，將投影數(shù)據(jù)庫中的頻繁節(jié)點添加到頻繁k-子樹上直接得到頻繁(k+1)-子樹，無冗余的構造了Embedded子樹的增長空間。并利用最小有效擴展性質進

5、行剪枝，得到所有滿足約束的閉合頻繁子樹以及最大頻繁子樹。實驗結果表明，其不僅執(zhí)行時間少，最關鍵的是，得到了用戶感興趣的模式。 (5)提出了一種基于頻繁子樹模式的XML文檔結構聚類算法-GCFS。該算法采用基于后退的先序序列表示XML文檔樹，挖掘XML文檔集合中的閉合與最大頻繁Induced子樹，并將其作為聚類特征，根據(jù)頻繁子樹的大小賦予不同的權值，采用余弦函數(shù)定義相似度，利用K-Means算法聚類XML文檔。實驗結果表明，GCF