基于序列模式的頻繁自由樹挖掘算法研究.pdf

1、數(shù)據(jù)挖掘（Data Mining，DM）是從大型數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)庫(kù)中提取隱含的、未知的、非平凡的及有潛在價(jià)值的信息或者模式。在數(shù)據(jù)挖掘概念提出以來(lái)十幾年間，數(shù)據(jù)挖掘技術(shù)得到日益的重視和廣泛的應(yīng)用、研究。因此，作為數(shù)據(jù)挖掘重要分支的頻繁項(xiàng)目集和關(guān)聯(lián)規(guī)則的挖掘，更是引起了廣泛的關(guān)注且得到的較大的研究、發(fā)展。
　　隨著數(shù)據(jù)挖掘應(yīng)用領(lǐng)域的不斷擴(kuò)大和涉及到的數(shù)據(jù)種類的增多，特別是網(wǎng)絡(luò)技術(shù)的發(fā)展，面向傳統(tǒng)領(lǐng)域的結(jié)構(gòu)化關(guān)系數(shù)據(jù)庫(kù)和事務(wù)數(shù)據(jù)庫(kù)的挖掘

2、技術(shù)，不能滿足非傳統(tǒng)領(lǐng)域的數(shù)據(jù)挖掘技術(shù)的要求，比如：半結(jié)構(gòu)化數(shù)據(jù)類型和非結(jié)構(gòu)化數(shù)據(jù)類型。而這些數(shù)據(jù)類型在生物信息學(xué)、Web挖掘、化合物結(jié)構(gòu)分析等領(lǐng)域有著廣泛的應(yīng)用。本文對(duì)面向非結(jié)構(gòu)化數(shù)據(jù)——樹和無(wú)環(huán)圖的挖掘技術(shù)進(jìn)行了深入的研究和分析。主要工作包括：
　　首先，對(duì)數(shù)據(jù)挖掘技術(shù)的相關(guān)背景知識(shí)進(jìn)行深入的介紹和分析。其中，重點(diǎn)闡述數(shù)據(jù)挖掘技術(shù)的一個(gè)重要分支——關(guān)聯(lián)規(guī)則挖掘。綜述關(guān)聯(lián)規(guī)則挖掘的不同種類，并對(duì)其中的頻繁項(xiàng)集挖掘做了全面深入的介

3、紹。
　　其次，對(duì)面向樹結(jié)構(gòu)的挖掘技術(shù)主要算法作了歸類，并比較兩大類算法的效率，得出結(jié)論深度優(yōu)先的算法效率較高。這樣為本文的研究方向找準(zhǔn)了的切入點(diǎn)，在后面作者的算法采用的是面向深度優(yōu)先，垂直搜索的方式。然后，分析當(dāng)前采用深度優(yōu)先算法中效率較高的兩個(gè)經(jīng)典算法，TreeMiner和FreeTreeMiner，總結(jié)和分析它們的優(yōu)缺點(diǎn)，并為作者后續(xù)算法所用。
　　然后，對(duì)面向無(wú)環(huán)圖(自由樹)類型的算法作了規(guī)劃，共分4個(gè)步驟：(1)尋

4、找自由樹的中心點(diǎn)，對(duì)此，作者提出高效的LWA(Longest Way Algorithm)算法，并證明該算法的正確性和高效性。(2)對(duì)有根無(wú)序樹作規(guī)范化，作者在這里提出規(guī)范化算法 Canonicalization，并分析此算法的時(shí)間復(fù)雜度，證明其時(shí)間復(fù)雜度與當(dāng)前效率最高的同類算法相當(dāng)。(3)挖掘頻繁序列模式，作者把“同分異構(gòu)”的思想引入頻繁序列挖掘，較大幅度的提高算法的速度效率。(4)引入索引的方法挖掘具有相同序列的不同結(jié)構(gòu)的頻繁子樹。