結(jié)構(gòu)化數(shù)據(jù)的挖掘算法研究.pdf

1、隨著計(jì)算機(jī)與信息技術(shù)的發(fā)展，數(shù)據(jù)挖掘技術(shù)已經(jīng)廣泛應(yīng)用到數(shù)據(jù)倉(cāng)庫(kù)、人工智能、模式識(shí)別、生物信息等許多領(lǐng)域。在研究逐步深入的過(guò)程中，愈來(lái)愈多的問(wèn)題也呈現(xiàn)在我們面前。生物信息技術(shù)、社會(huì)網(wǎng)絡(luò)模型分析、XML查詢路徑研究的迅速崛起，使事物之間的關(guān)系越來(lái)越復(fù)雜，人們開始意識(shí)到用樹和圖能更好地描述這些數(shù)據(jù)結(jié)構(gòu)，進(jìn)而在此基礎(chǔ)上進(jìn)行挖掘可以得到更多的有用信息。在樹和圖中，頂點(diǎn)對(duì)應(yīng)對(duì)象中的實(shí)體，邊對(duì)應(yīng)實(shí)體之間的關(guān)系。但是，傳統(tǒng)的針對(duì)序列、事務(wù)、文本等非結(jié)構(gòu)

2、化數(shù)據(jù)的挖掘方法已經(jīng)不能滿足不斷出現(xiàn)的結(jié)構(gòu)化數(shù)據(jù)的挖掘要求。因此，針對(duì)樹、圖等結(jié)構(gòu)化數(shù)據(jù)，并結(jié)合非結(jié)構(gòu)化數(shù)據(jù)挖掘方面的經(jīng)驗(yàn)和方法論，來(lái)實(shí)現(xiàn)結(jié)構(gòu)化數(shù)據(jù)高效挖掘的研究，已經(jīng)成為數(shù)據(jù)挖掘研究領(lǐng)域的重要的研究方向。 本文針對(duì)結(jié)構(gòu)化數(shù)據(jù)的挖掘與處理目前研究的主要問(wèn)題進(jìn)行了研究，包括有序樹和無(wú)序樹的頻繁Induced與Embedded子樹的挖掘、子圖同構(gòu)的判斷以及頻繁子圖挖掘、圖結(jié)構(gòu)數(shù)據(jù)的索引查詢以及圖的編輯距離的度量，具體做了以下一些工作

3、： (1)研究了數(shù)據(jù)挖掘和頻繁模式挖掘的相關(guān)知識(shí)和主要技術(shù)，其中，在樹挖掘和圖挖掘算法方面，分析了現(xiàn)有樹和圖的表示方式及標(biāo)準(zhǔn)化算法、頻繁樹和頻繁圖的增長(zhǎng)模式以及影響樹挖掘和圖挖掘效率的關(guān)鍵因素，并分別對(duì)現(xiàn)有的樹挖掘和圖挖掘算法在這些關(guān)鍵因素中的處理方法進(jìn)行了闡述和比較，指出它們所做的貢獻(xiàn)，同時(shí)指出算法中仍需改進(jìn)的地方。 (2)考慮到現(xiàn)有樹挖掘算法中，樹的表示方式雖然能夠等價(jià)地表示一棵樹，但是這些表示方式并不能直觀地表達(dá)一

4、棵樹，這樣會(huì)導(dǎo)致精煉的頻繁樹挖掘思想在復(fù)雜的表示方式面前難以實(shí)施，從而使頻繁樹增長(zhǎng)過(guò)程變得復(fù)雜，進(jìn)而影響到了樹挖掘整體的挖掘效率。本文提出了基于父子關(guān)系標(biāo)識(shí)的前序遍歷碼的概念，能夠簡(jiǎn)單直觀地表示樹結(jié)構(gòu)，并針對(duì)有序樹中的兩個(gè)重要問(wèn)題頻繁Induced與Embedded子樹挖掘，提出了基于先序等價(jià)碼和模式增長(zhǎng)思想的頻繁子樹挖掘算法ITMA和ETMA，提高了樹挖掘的效率。 此外，我們基于父子關(guān)系標(biāo)識(shí)的前序遍歷碼的結(jié)構(gòu)特點(diǎn)，提出了無(wú)序樹

5、中無(wú)序等價(jià)碼的標(biāo)準(zhǔn)化算法UTS，并結(jié)合有序樹中頻繁子樹的挖掘算法，提出了無(wú)序樹中的頻繁子樹挖掘的算法UITMA和UETMA。 (3)圖同構(gòu)判斷是圖挖掘算法中的一個(gè)關(guān)鍵問(wèn)題，解決該問(wèn)題的現(xiàn)有算法雖然在既有的圖表示方式上都提出了相應(yīng)的標(biāo)準(zhǔn)化的方法，從而使每一個(gè)圖都對(duì)應(yīng)唯一的編碼，但這些同構(gòu)判斷算法在效率上存在一定的局限性。因?yàn)樵陬l繁子圖生成過(guò)程中，每一次從k項(xiàng)頻繁圖增長(zhǎng)到k+1頻繁圖時(shí)，都要調(diào)用同構(gòu)判斷算法，因此判斷效率的高低會(huì)直接

6、影響到圖挖掘算法整體的效率。我們提出了基于關(guān)聯(lián)矩陣標(biāo)準(zhǔn)化的子圖同構(gòu)判斷算法，有效地降低了判斷的復(fù)雜度；在子圖擴(kuò)展方面，我們采用了深度優(yōu)先的子圖增長(zhǎng)策略，從而顯著地提高了圖挖掘算法的效率。 (4)圖結(jié)構(gòu)數(shù)據(jù)的查詢是圖挖掘中有著廣泛應(yīng)用背景的一個(gè)問(wèn)題，我們提出了以邊映射和頻繁圖分級(jí)建立圖索引以及圖庫(kù)篩選的方法，有效地提高了查詢速度。同時(shí)，在圖像比對(duì)中發(fā)揮重要作用的問(wèn)題——圖的相似性度量與編輯距離求解方面，根據(jù)現(xiàn)有的代價(jià)矩陣，我們提出