樹挖掘若干算法研究.pdf

1、近二十年來，數(shù)據(jù)挖掘已經(jīng)在理論研究方面取得了很大的進(jìn)展，應(yīng)用范圍也日趨廣泛。樹結(jié)構(gòu)作為一種特定的數(shù)據(jù)組織形式，對其組成的數(shù)據(jù)源進(jìn)行規(guī)則挖掘目前已成為數(shù)據(jù)挖掘研究領(lǐng)域中一個新的研究內(nèi)容。由于樹結(jié)構(gòu)本身的復(fù)雜性使得樹結(jié)構(gòu)數(shù)據(jù)庫的挖掘復(fù)雜度要比傳統(tǒng)數(shù)據(jù)庫挖掘的復(fù)雜度高很多，因此頻繁子樹挖掘算法的效率一直比較低。同時，由于頻繁子樹挖掘是其他樹挖掘算法的基礎(chǔ)，斷這也限制了樹挖掘應(yīng)用領(lǐng)域的拓最。例如，在分布環(huán)境下和數(shù)據(jù)流環(huán)境下的頻繁子樹挖掘，樹結(jié)構(gòu)

2、數(shù)據(jù)庫的分類問題等。再者，樹結(jié)構(gòu)本身的復(fù)雜性導(dǎo)致頻繁子樹的數(shù)目非常龐大，這也給用戶處理和使用頻繁子樹帶來了諸多不便，從而限制了其應(yīng)用的深入。針對以上問題，本論文研究工作著重于樹結(jié)構(gòu)數(shù)據(jù)庫中頻繁子樹挖掘的算法研究。同時對壓縮頻繁子樹集合的挖掘、分布環(huán)境下和數(shù)據(jù)流環(huán)境下的頻繁子樹挖掘以及樹結(jié)構(gòu)數(shù)據(jù)庫中的分類等問題作了相關(guān)研究。 具體而言，本論文在以下幾個方面進(jìn)行了深入研究，并取得了有效的進(jìn)展： 1)提出投影分支的概念和基于投

3、影分支的頻繁嵌入子樹挖掘算法，該算法掃描一遍數(shù)據(jù)庫即可生成當(dāng)前頻繁子樹的所有直接后繼頻繁嵌入子樹，可以有效地減小搜索空間，提高算法效率。 2)提出投影節(jié)點(diǎn)的概念和基于投影節(jié)點(diǎn)的頻繁導(dǎo)出子樹挖掘算法，該算法利用投影節(jié)點(diǎn)只需掃描一遍數(shù)據(jù)庫就能夠根據(jù)當(dāng)前的頻繁子樹直接生成所有直接后繼頻繁導(dǎo)出子樹，具有較高的效率。 3)引入壓縮頻繁子樹集合的框架6．聚類，并提出從數(shù)據(jù)庫中直接挖掘壓縮頻繁子樹集合的算法，挖掘出的壓縮頻繁子樹集合的

4、尺寸比閉合頻繁子樹集合的尺寸要小兩個數(shù)量級，而且由于使用搜索空間裁剪以及直接生成頻繁子樹等技巧，使得該算法具有較高的效率。 4)提出全局頻繁子樹挖掘算法，該算法在網(wǎng)絡(luò)各站點(diǎn)之間傳送局部頻繁投影分支節(jié)點(diǎn)集合，形成候選全局投影分支頻繁節(jié)點(diǎn)，從而計算得出全局投影分支頻繁節(jié)點(diǎn)，生成全局頻繁子樹，能夠充分利用分布多庫環(huán)境下的并行操作，有效地降低網(wǎng)絡(luò)通信量，提高挖掘全局頻繁子樹的效率。該算法將樹挖掘研究拓展到分布式環(huán)境。 5)提出了

5、數(shù)據(jù)流中頻繁子樹快速挖掘算法，該算法使用枚舉樹作為頻繁子樹的存儲結(jié)構(gòu)可以有效地提高候選子樹的搜索、插入、刪除等操作的效率；同時利用Chernoff不等式維護(hù)潛在頻繁子樹集合，可以顯著地減小丟失頻繁子樹的概率，從而有效地提高算法的效率和精度。 6)提出了半結(jié)構(gòu)化文檔的快速分類算法。該算法能夠從當(dāng)前頻繁結(jié)構(gòu)規(guī)則直接生成符合最小支持度閾值的后繼結(jié)構(gòu)規(guī)則，并結(jié)合分類的特點(diǎn)裁剪搜索空間，有效地減小了候選頻繁規(guī)則的數(shù)目，從而可以大大地提高分