頻繁子樹挖掘及其在XML挖掘中的應(yīng)用研究.pdf

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

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

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

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

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