結構化數(shù)據的挖掘算法研究.pdf

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

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

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

4、棵樹，這樣會導致精煉的頻繁樹挖掘思想在復雜的表示方式面前難以實施，從而使頻繁樹增長過程變得復雜，進而影響到了樹挖掘整體的挖掘效率。本文提出了基于父子關系標識的前序遍歷碼的概念，能夠簡單直觀地表示樹結構，并針對有序樹中的兩個重要問題頻繁Induced與Embedded子樹挖掘，提出了基于先序等價碼和模式增長思想的頻繁子樹挖掘算法ITMA和ETMA，提高了樹挖掘的效率。 此外，我們基于父子關系標識的前序遍歷碼的結構特點，提出了無序樹

5、中無序等價碼的標準化算法UTS，并結合有序樹中頻繁子樹的挖掘算法，提出了無序樹中的頻繁子樹挖掘的算法UITMA和UETMA。 (3)圖同構判斷是圖挖掘算法中的一個關鍵問題，解決該問題的現(xiàn)有算法雖然在既有的圖表示方式上都提出了相應的標準化的方法，從而使每一個圖都對應唯一的編碼，但這些同構判斷算法在效率上存在一定的局限性。因為在頻繁子圖生成過程中，每一次從k項頻繁圖增長到k+1頻繁圖時，都要調用同構判斷算法，因此判斷效率的高低會直接

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