圖模式挖掘技術(shù)的研究.pdf

1、作為一種通用的數(shù)據(jù)結(jié)構(gòu)，圖可以用來表示數(shù)據(jù)對象之間的各種復(fù)雜關(guān)系。例如：圖可以表示化合物的分子結(jié)構(gòu)，蛋白質(zhì)交互網(wǎng)絡(luò)，社會網(wǎng)絡(luò)，Web結(jié)構(gòu)圖等。隨著科學(xué)與工程領(lǐng)域中圖數(shù)據(jù)的大量出現(xiàn)，從圖數(shù)據(jù)庫中發(fā)現(xiàn)有用的知識已成為數(shù)據(jù)挖掘領(lǐng)域一項(xiàng)重要的研究課題。圖模式挖掘是其中最重要的一個研究分支，因?yàn)榕c圖有關(guān)的絕大部分應(yīng)用(例如：圖查詢、圖分類、圖聚類等)都需要利用圖模式來管理、查詢和分析圖數(shù)據(jù)。本文主要對圖模式挖掘技術(shù)進(jìn)行深入研究，歸納總結(jié)了現(xiàn)有研究

2、成果的主要思想和優(yōu)缺點(diǎn)，提出了一些新的圖模式挖掘問題和解決方法，主要研究成果如下：
　　第一、提出從圖數(shù)據(jù)庫中挖掘代表模式問題及其有效解決方法。目前的頻繁子圖挖掘算法通常產(chǎn)生大量的甚至指數(shù)級數(shù)量的頻繁子圖，嚴(yán)重地影響了挖掘結(jié)果的可用性。挖掘代表模式既可以極大地減少圖模式的輸出數(shù)量，又能使有有意義的圖模式保留在挖掘結(jié)果中。本文給出了挖掘代表模式問題的形式化定義，并證明了該問題是NP-hard。提出了一系列新的概念：δ-覆蓋圖，跳躍值

3、，δ-跳躍模式等。發(fā)現(xiàn)了δ-跳躍模式的一個重要性質(zhì)：δ-跳躍模式一定是代表模式。利用δ-跳躍模式的性質(zhì)，提出了挖掘代表模式的三個算法：RP-FP，RP-GD，RP-Leap。RP-FP和RP-GD挖掘完整的代表模式集合，RP-Leap挖掘近似的代表模式集合。RP-FP從頻繁閉圖模式中計(jì)算代表模式，具有緊的近似比保證。然而，當(dāng)頻繁閉圖模式數(shù)量大時(shí)，RP-FP效率低。RP-GD采用聯(lián)機(jī)算法的思想，直接從圖數(shù)據(jù)庫中挖掘代表模式。算法復(fù)雜性分析

4、表明RP-GD的效率要遠(yuǎn)遠(yuǎn)高于RP-FP的效率。RP-Leap利用了圖模式搜索空間中大量分枝之間的相似性，快速跳過那些幾乎不產(chǎn)生代表模式的分枝，來挖掘一個近似代表模式集合。實(shí)驗(yàn)結(jié)果表明：(1) RP-FP，RP-GD，RP-Leap能得到一個小的而有意義的代表模式集合；(2) RP-GD的挖掘效率遠(yuǎn)遠(yuǎn)高于RP-FP的挖掘效率；而在結(jié)果質(zhì)量方面，RP-GD類似于RP-FP；(3) RP-Leap以丟失少量代表模式的代價(jià)，取得了比RP-GD

5、快一個數(shù)量級的性能改善。
　　第二、提出從圖數(shù)據(jù)庫中挖掘核心子結(jié)構(gòu)問題及其有效解決方法。核心子結(jié)構(gòu)在真實(shí)的圖數(shù)據(jù)庫中大量存在，例如化合物中的功能團(tuán)就是一類核心子結(jié)構(gòu)。針對核心子結(jié)構(gòu)的特征，本文給出了核心子結(jié)構(gòu)的形式化定義，稱為△-跳躍模式。發(fā)現(xiàn)了△-跳躍模式的很多重要性質(zhì)。例如：△跳躍模式是穩(wěn)定的，它們對躁聲和數(shù)據(jù)的變化不敏感，△值越大，它們的抗干擾能力越強(qiáng)。然而，△-跳躍模式不具有反單調(diào)性質(zhì)性質(zhì)，挖掘它們非常具有挑戰(zhàn)性。通過仔細(xì)

6、研究跳躍模式自身的特性，本文提出了兩種新的裁剪技術(shù)，基于內(nèi)擴(kuò)展的裁剪和基于外擴(kuò)展的裁剪。利用這兩裁剪技術(shù)，設(shè)計(jì)了一個高效的跳躍模式挖掘算法GraphJP。在理論上，嚴(yán)格地證明了這兩種裁剪技術(shù)的正確性以及算法GraphJP的正確性。實(shí)驗(yàn)結(jié)果表明：這兩種新的裁剪技術(shù)能有效地裁剪圖模式搜索空間，算法GraphJP能高效可擴(kuò)展地挖掘頻繁跳躍模式，而且挖掘結(jié)果中含有圖數(shù)據(jù)庫中的核心子結(jié)構(gòu)。
　　第三、提出基于聯(lián)合意義度量的Top-K圖模式挖

7、掘問題及其有效解決方法。傳統(tǒng)Top-K挖掘并不考慮圖模式之間的相關(guān)性，輸出的Top-K模式在結(jié)構(gòu)上非常相似。如果用戶得到其中一個圖模式，就對其它圖模式失去了興趣。聯(lián)合意義度量的作用域是圖模式集合而不是圖模式。因此，基于聯(lián)合意義度量的Top-K挖掘，隱含排斥相關(guān)的圖模式，可以得到一個多樣化而有意義的圖模式集合。本文討論了適用于圖模式集合的聯(lián)合意義度量，并利用信息論中的概念(聯(lián)合熵和信息增益)給出了兩個具體的問題定義MES和MIGS，證明了

8、它們是NP-hard問題。提出了兩個高效的Top-K挖掘算法Greedy-TopK和Cluster-TopK。Greedy-TopK先產(chǎn)生頻繁圖模式，然后增量貪心地選擇K個圖模式。如果用戶給定的意義度量滿足submodular性質(zhì)，Greedy-TopK能提供近似比保證。為了進(jìn)一步提高Greedy-TopK的效率，針對MES和MIGS這兩個具體問題的意義度量又設(shè)計(jì)了一系列有效的裁剪技術(shù)，將其嵌入到頻繁子圖挖掘框架中幫助裁剪圖模式搜索空間

9、。然而，當(dāng)頻繁圖模式數(shù)量多時(shí)，Greedy-TopK仍然效率低，可擴(kuò)展性差。為克服Greedy-TopK的缺點(diǎn)，Cluster-TopK先從圖數(shù)據(jù)庫中挖掘所有頻繁圖模式的一個代表模式集合，然后從代表模式中增量貪心地選擇K個圖模式。Cluster-TopK最大的優(yōu)點(diǎn)是無需產(chǎn)生頻繁圖模式就能快速地從圖數(shù)據(jù)庫中挖掘一個代表模式集合。本文從理論上證明了Cluster-TopK產(chǎn)生的解和Greedy-TopK產(chǎn)生的解非常接近。實(shí)驗(yàn)結(jié)果表明：在結(jié)果

10、質(zhì)量和可用性方面，本文提出的Top-K挖掘遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)的Top-K挖掘。Cluster-TopK比Greedy-TopK快一到兩個數(shù)量級。而且，Cluster-TopK的挖掘結(jié)果質(zhì)量非常接近于Greedy-TopK的挖掘結(jié)果質(zhì)量。
　　第四、提出了一種基于頻繁閉顯露模式的圖分類框架CEP。CEP包括三個主要步驟：(1)挖掘頻繁閉圖模式；(2)過濾非顯露模式；(3)構(gòu)造分類規(guī)則。第一步，CEP挖掘所有頻繁閉圖模式作為候選分類特征。第

11、二步，CEP保留頻繁閉圖模式中的顯露模式。該步需要計(jì)算圖模式在不同類別數(shù)據(jù)庫中的支持度，涉及大量子圖同構(gòu)測試。為改善CEP的效率，CEP將頻繁閉圖模式組織成一個樹型結(jié)構(gòu)T。對數(shù)據(jù)庫中的每個圖G，采用深度優(yōu)先方式遍歷樹T。在遍歷過程中，利用Aprior(反單調(diào))性質(zhì)進(jìn)行裁剪：如果G不包含節(jié)點(diǎn)P，G也不可能包含P的孩子節(jié)點(diǎn)。通過這種方式，可以極大地減少子圖同構(gòu)測試次數(shù)。第三步，CEP根據(jù)剩余的顯露模式構(gòu)造分類規(guī)則。在構(gòu)造分類規(guī)則時(shí)，提出了一