嵌入式與導(dǎo)出式頻繁子樹挖掘算法研究.pdf

1、樹結(jié)構(gòu)數(shù)據(jù)以其表達(dá)事物清晰、完整等優(yōu)勢，在計(jì)算機(jī)網(wǎng)絡(luò)、Web挖掘、生物信息分析、XML文檔挖掘等領(lǐng)域有著日趨重要的應(yīng)用。本文針對有序標(biāo)號樹，以最右路徑擴(kuò)展技術(shù)為基礎(chǔ)，從改進(jìn)投影庫的構(gòu)造方法、減小投影庫的規(guī)模和提高投影庫中節(jié)點(diǎn)的計(jì)數(shù)效率等方面，對頻繁嵌入式與導(dǎo)出式子樹挖掘算法進(jìn)行了研究。主要研究內(nèi)容如下： ⑴給出了一種基于離散區(qū)間的嵌入式頻繁子樹挖掘算法DIFTM。首先，采用了最右路徑擴(kuò)展的方法，由頻繁k-子樹可直接擴(kuò)展成為頻繁（

2、k+1）-子樹，避免了候選生成；其次，利用離散區(qū)間構(gòu)造最右路徑投影庫，消除了部分冗余投影，有效地減小了投影庫的規(guī)模；再次，對投影庫中的節(jié)點(diǎn)計(jì)數(shù)時(shí)，先找離散區(qū)間，再在離散區(qū)間上計(jì)數(shù)頻繁節(jié)點(diǎn)，避免了對重復(fù)投影的重復(fù)掃描；最后，采用CSLOGS數(shù)據(jù)集，實(shí)驗(yàn)驗(yàn)證了算法的正確性和有效性。 ⑵給出了一種基于編碼的導(dǎo)出式頻繁子樹挖掘算法EFITM。首先，通過樹的寬度優(yōu)先編碼表示原始數(shù)據(jù)庫，使得最右路徑投影中不存在冗余節(jié)點(diǎn)，減小了投影庫中每個(gè)投