頻繁子樹挖掘及其相關(guān)技術(shù)的研究.pdf

1、隨著計(jì)算機(jī)與信息技術(shù)的發(fā)展，人們在日常事務(wù)處理和科學(xué)研究中積累了大量數(shù)據(jù)。如何從中提取或“挖掘”用戶所需要的信息，是當(dāng)前信息科學(xué)技術(shù)領(lǐng)域面臨的一大挑戰(zhàn)。數(shù)據(jù)挖掘正是在這樣的背景下發(fā)展而來。 目前，數(shù)據(jù)挖掘及其應(yīng)用已經(jīng)滲透到多個(gè)學(xué)科，并在人工智能與機(jī)器學(xué)習(xí)、數(shù)據(jù)庫、模式識別、生物信息學(xué)、神經(jīng)網(wǎng)絡(luò)等領(lǐng)域取得了豐碩的成果。頻繁模式挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)基本問題，其研究范圍包括事務(wù)、序列、樹和圖。其方法被廣泛應(yīng)用于許多其它數(shù)據(jù)挖掘任務(wù)

2、中，如相關(guān)性分析，周期分析，最大模式，閉合模式，查詢，分類，索引等等。 在現(xiàn)實(shí)積累的大量數(shù)據(jù)中有一類諸如樹、圖等結(jié)構(gòu)化的數(shù)據(jù)，它們具備很強(qiáng)的層次表達(dá)能力，幾乎能夠模擬所有的事物之間的聯(lián)系，因此基于樹的數(shù)據(jù)挖掘有著廣闊的應(yīng)用空間，如Web挖掘、空間數(shù)據(jù)挖掘、生物信息學(xué)中蛋白質(zhì)結(jié)構(gòu)挖掘、藥物分子設(shè)計(jì)及其功能預(yù)測等等。如何發(fā)現(xiàn)挖掘頻繁子樹的高效算法，已日益成為數(shù)據(jù)挖掘中的一個(gè)新的研究熱點(diǎn)，對頻繁子樹挖掘算法的研究將成為一個(gè)具有重要的理

3、論意義和應(yīng)用價(jià)值的研究課題。 本文主要研究工作包括： (1)提出了一種基于子樹向量的快速導(dǎo)出子樹挖掘算法-ITMSV(induced subtrees mining based on subtree vector)。算法基于子樹向量和哈希表構(gòu)建一個(gè)多層的數(shù)據(jù)結(jié)構(gòu)，在挖掘過程中能夠減少樹同構(gòu)的判別時(shí)間，并且只需要進(jìn)行一次數(shù)據(jù)庫的掃描操作，減少了掃描次數(shù)，提高了算法的運(yùn)行效率。 (2)提出了一種可以在大型樹數(shù)據(jù)庫中高

4、效挖掘無序樹的算法—UTMiner(unordered trees miner)，由于所挖掘的樹具有無序的特性，因此為了避免挖掘出相同子樹的情況，本文提出了一種高效的無序樹的標(biāo)準(zhǔn)化方法，將無序樹轉(zhuǎn)化為標(biāo)準(zhǔn)化子樹，再利用本文提出的快速有序樹挖掘算法得到所有的標(biāo)準(zhǔn)化子樹。 (3)提出一種基于最小閉樹特征集的聚類與分類方法，有效地解決了在實(shí)際應(yīng)用中因數(shù)據(jù)量大而無法聚類與分類的問題。其基本思想為：提出以最小閉樹特征集作為候選聚類與分類特