??? 摘 要：隨著對(duì)大量結(jié)構(gòu)化數(shù)據(jù)分析需求的增長(zhǎng)，從圖集合中挖掘頻繁子圖模式已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)。通過(guò)對(duì)目前有代表性的頻繁子圖挖掘算法的分析和比較，全面總結(jié)了各算法的特性及優(yōu)缺點(diǎn)，并預(yù)測(cè)了今后的發(fā)展趨勢(shì)。
??? 關(guān)鍵詞：數(shù)據(jù)挖掘；頻繁子結(jié)構(gòu)；子圖同構(gòu)
?
??? 隨著生物信息學(xué)(蛋白質(zhì)結(jié)構(gòu)、基因組識(shí)別和比較分析)、社會(huì)網(wǎng)絡(luò)(實(shí)體間的聯(lián)系)、Web分析(Web的鏈接結(jié)構(gòu)分析、Web內(nèi)容挖掘和Web日志的搜索)以及文本信息檢索(文檔的選擇、文檔的秩評(píng)定)等復(fù)雜結(jié)構(gòu)的廣泛應(yīng)用。圖作為一般數(shù)據(jù)結(jié)構(gòu)在這些結(jié)構(gòu)以及它們的建模方面日趨重要。為了進(jìn)一步對(duì)圖進(jìn)行特征化、區(qū)分、分類和聚類分析，挖掘頻繁子圖模式已經(jīng)成為一項(xiàng)重要的任務(wù)，日益受到人們的關(guān)注。
1 現(xiàn)有的頻繁子圖挖掘方法
??? 在各種各樣的圖模式中，頻繁子結(jié)構(gòu)是可以在圖集合中發(fā)現(xiàn)的非?；镜哪Ｊ?。在大型圖數(shù)據(jù)庫(kù)中可以用它建立圖索引并進(jìn)行相似性搜索，區(qū)分不同的圖組群，對(duì)圖進(jìn)行分類和聚類分析。目前已經(jīng)有了一些成熟的頻繁子結(jié)構(gòu)的挖掘方法，并且在許多領(lǐng)域得到了應(yīng)用，尤其在藥物發(fā)現(xiàn)和化合物合成領(lǐng)域的應(yīng)用更為流行，目前子結(jié)構(gòu)挖掘算法分類如下：
??? (1)基于Apriori的頻繁結(jié)構(gòu)挖掘算法：AGM、PSG、路徑連接算法；
??? (2)基于模式增長(zhǎng)的頻繁結(jié)構(gòu)挖掘算法：Espan、FFSM、CloseGraph；
??? (3)基于最小描述長(zhǎng)度的近似頻繁子結(jié)構(gòu)挖掘算法：SUBOUE；
??? (4)基于模式增長(zhǎng)和模式歸約的精確稠密頻繁子結(jié)構(gòu)挖掘算法：CloseCut、Splat。
1.1 基于Apriori的頻繁子結(jié)構(gòu)挖掘算法
??? 基于Apriori的頻繁子結(jié)構(gòu)挖掘算法與基于Apriori的頻繁項(xiàng)集挖掘算法相類似。頻繁圖的搜索開(kāi)始于小規(guī)模圖，按照自底向上的方式產(chǎn)生具有附加頂點(diǎn)、邊或路徑的候選圖。最近提出的基于Apriori的頻繁子結(jié)構(gòu)挖掘算法包括AGM、FSG和路徑連接方法等。
??? （1）由Inokuchi等人提出的計(jì)算高效性算法AGM[1]，能找到所有滿足某一最小支持度閾值的頻繁子圖，它與基于Apriori的項(xiàng)集挖掘算法具有類似的特點(diǎn)，使用基于頂點(diǎn)的候選產(chǎn)生方法，通過(guò)在每一步增加一個(gè)頂點(diǎn)來(lái)擴(kuò)展子結(jié)構(gòu)的規(guī)模。2個(gè)大小為k的頻繁圖進(jìn)行連接，僅當(dāng)它們具有相同的大小為k-1的子圖。新形成的候選包括1個(gè)大小為k-1的公共子圖和來(lái)自2個(gè)大小為k的模式中的2個(gè)附加頂點(diǎn)。AGM能夠處理帶有標(biāo)記的頂點(diǎn)和邊的圖，可以有效地挖掘不同類型的子圖，例如一般子圖、導(dǎo)出子圖、連通子圖、有序子樹、無(wú)序子樹和子路經(jīng)，特別對(duì)于合成密集型數(shù)據(jù)集具有良好的性能。這種方法常用于發(fā)生變異活動(dòng)的化合物分子結(jié)構(gòu)的分析。實(shí)驗(yàn)證明，在一個(gè)包含300個(gè)化合物的數(shù)據(jù)集中，當(dāng)最小支持度閾值從20%～10%變化時(shí)要找出所有的頻繁生成子圖需要40 min到8天的時(shí)間。AGM對(duì)于一個(gè)生成子圖可以是非連通的，包含幾個(gè)獨(dú)立的圖片段，但這種方法也需要很長(zhǎng)的處理時(shí)間。
??? （2）Kuramochi等人利用邊增長(zhǎng)策略進(jìn)一步發(fā)展了上述思想，提出了FSG算法[2]。該算法在具有多條邊和頂點(diǎn)標(biāo)記的圖數(shù)據(jù)集中能更好地運(yùn)行，運(yùn)行時(shí)間依賴于被發(fā)現(xiàn)的頻繁子圖的大小。它的輸入為圖集，但為了減小時(shí)間復(fù)雜度，F(xiàn)SG限用于連通圖，由于很多應(yīng)用都可以轉(zhuǎn)化為連通圖，所以FSG的這個(gè)限制并未影響到它的應(yīng)用范圍。為了提高導(dǎo)出規(guī)范標(biāo)記效率，它使用了一些圖頂點(diǎn)不變量(例如設(shè)定圖中的每個(gè)頂點(diǎn)的度)并且它通過(guò)引入TID(transaction ID)方法提高了頻繁子圖的候選產(chǎn)生效率。此外它采用基于邊的候選產(chǎn)生策略，通過(guò)每次增加一條邊來(lái)擴(kuò)展子結(jié)構(gòu)的規(guī)模。合并2個(gè)大小為k的頻繁子圖，當(dāng)且僅當(dāng)他們共享相同的具有k-1條邊的連通主子圖(該主子圖稱為核)，新形成的侯選包括核和來(lái)自2個(gè)大小為k的模式中的2條附加邊，通過(guò)這種合并方法還提高了FSG的連接效率。正因?yàn)镕SG引入了這些技術(shù)所以運(yùn)行速度很快，實(shí)驗(yàn)證明，它具有良好的性能并且能夠隨數(shù)據(jù)庫(kù)的大小呈線性比例變化，它能夠從一個(gè)包含8萬(wàn)個(gè)圖片支持度閾值為2%的合成數(shù)據(jù)集中，以少于500 s的時(shí)間發(fā)現(xiàn)所有的頻繁連通子圖。但是對(duì)于大型圖數(shù)據(jù)存儲(chǔ)TID列表要占用大量的內(nèi)存空間，而且不像合并項(xiàng)集那樣，2個(gè)大小為k的頻繁項(xiàng)集能夠只產(chǎn)生唯一的大小為k+1的項(xiàng)集，這里2個(gè)大小為k的子圖可能產(chǎn)生多個(gè)大小為k+1的候選子圖，生成大量的重復(fù)候選子圖，降低了算法的整體效率。
??? （3）邊不相交路徑方法[3]依據(jù)圖所擁有的不相交路徑的數(shù)量來(lái)分類。如果2條路徑不共享任何邊，那么就稱這兩條路徑是邊不相交的[4]。該方法提出一種合成關(guān)系(composition? relation)的結(jié)構(gòu)來(lái)表示邊不相交路徑的連接圖，這種結(jié)構(gòu)是一個(gè)二維表的形式，節(jié)點(diǎn)表示行，路徑表示列。另外還提出了雙射和(bijective sum)合成關(guān)系，接合(splice)合成關(guān)系以及合成關(guān)系的圖實(shí)現(xiàn)操作，雙射和是用來(lái)表示連接2個(gè)具有k條不相交路徑的子圖后形成的k+1條不相交路徑的圖，這個(gè)圖包括1個(gè)具有k-1條不相交路徑的公共子圖和添加到共享節(jié)點(diǎn)(指在2個(gè)具有k條路徑的圖中公共子圖連接另外一條路徑的節(jié)點(diǎn))上的2條附加路徑。接合是把一個(gè)圖中屬于2個(gè)不同路徑上的2個(gè)節(jié)點(diǎn)合并成一個(gè)節(jié)點(diǎn)的過(guò)程，以此確保挖掘的完全性。合成關(guān)系的圖實(shí)現(xiàn)是對(duì)于給定的一個(gè)有n條路徑的合并關(guān)系C，則可以構(gòu)造一個(gè)相對(duì)應(yīng)的圖。讓表中的行對(duì)應(yīng)圖的頂點(diǎn)并且定義邊(i，j)為：當(dāng)同一個(gè)路徑p的2個(gè)節(jié)點(diǎn)出現(xiàn)在第i行和第j行中，則在它們之間的那條邊。這種操作就稱為圖實(shí)現(xiàn)。
??? 算法的處理主要分成3個(gè)階段：
??? （1）通過(guò)每次增加一條邊來(lái)構(gòu)造頻繁路徑;
??? （2）構(gòu)造路徑數(shù)為2的頻繁圖。通過(guò)連接具有一條路徑的圖來(lái)完成，在此過(guò)程通過(guò)合成關(guān)系列出所有的兩條路徑連接的可能性，另外保留那些在圖實(shí)現(xiàn)中路徑數(shù)為2、而且通過(guò)計(jì)算支持度確定的頻繁圖，最后移除所有的非最小的同構(gòu)圖；
??? （3）通過(guò)連接具有k-1條路徑的圖來(lái)構(gòu)造具有k條路徑的頻繁圖。使用雙射和方法，把找到的2個(gè)具有k條路徑的圖(它們具有相同的k-1條路徑的公共子結(jié)構(gòu))連接成一個(gè)k+1條路徑的圖模式。但是因?yàn)槭褂秒p射和直接合成2個(gè)圖模式可能會(huì)造成路徑上個(gè)別的公共頂點(diǎn)的丟失，因此必須使用接合方法來(lái)彌補(bǔ)這一缺陷，添加丟失的公共頂點(diǎn)給候選模式以確保完全性。接下來(lái)移除同構(gòu)圖并計(jì)算支持度來(lái)確定頻繁性。最后移除所有不是最大的頻繁子圖。
1.2 基于模式增長(zhǎng)的頻繁子結(jié)構(gòu)挖掘算法
??? 當(dāng)連接2個(gè)大小為k的頻繁子結(jié)構(gòu)產(chǎn)生大小為k+1的圖候選時(shí)，基于Apriori算法的系統(tǒng)開(kāi)銷很大，為避免這種系統(tǒng)開(kāi)銷，提出了模式增長(zhǎng)的方法，主要包括gSpan、CloseGraph和FFSM等。這些算法均通過(guò)逐步擴(kuò)展頻繁邊得到頻繁子圖，但每個(gè)算法對(duì)圖的擴(kuò)展過(guò)程也有許多不同之處。
1.2.1 gSpan算法
??? gSpan算法[5]旨在減少?gòu)?fù)制圖二度發(fā)現(xiàn)的圖)的產(chǎn)生。它首次提出利用DFS(深度優(yōu)先搜索)法生成頻繁子圖，通過(guò)兩大技術(shù)的應(yīng)用——DFS詞典序、最小DFS編碼和最右擴(kuò)展，對(duì)每個(gè)圖建立DFS詞典序，并達(dá)到將每個(gè)圖用最小DFS編碼唯一標(biāo)記的目的，使得無(wú)需按Apriori算法的思想而直接生成頻繁子圖。該算法通過(guò)選擇一個(gè)起始頂點(diǎn)開(kāi)始訪問(wèn)，并為能分辨出已經(jīng)訪問(wèn)過(guò)的頂點(diǎn)對(duì)其做標(biāo)記，然后對(duì)被訪問(wèn)過(guò)的頂點(diǎn)集合反復(fù)擴(kuò)展，直到建立一個(gè)完全的深度優(yōu)先搜索(DFS)樹。在構(gòu)造DFS樹時(shí)，頂點(diǎn)的訪問(wèn)順序形成一個(gè)線性序(用下標(biāo)來(lái)記錄此次序)，設(shè)起始頂點(diǎn)為根，則最后訪問(wèn)的頂點(diǎn)稱為最右頂點(diǎn)，從根到最右頂點(diǎn)的直接路徑稱為最右路徑。gSpan擴(kuò)展時(shí)只進(jìn)行最右擴(kuò)展，即在DFS樹中一條新邊可以添加到最右頂點(diǎn)和最右路徑上另一個(gè)頂點(diǎn)之間或者引進(jìn)一個(gè)新的頂點(diǎn)并連接到最右路徑上的頂點(diǎn)。把每個(gè)加下標(biāo)的圖轉(zhuǎn)換為邊序列稱為DFS編碼，用{i，j，li，l(i，j)，lj}5元組表示，然后通過(guò)一定規(guī)則來(lái)建立邊序列之間的序，即DFS詞典序，基于詞典序，找到圖的最小DFS編碼。只有對(duì)最小DFS編碼執(zhí)行最右擴(kuò)展，才能減少?gòu)?fù)制圖的產(chǎn)生，也確保了挖掘結(jié)果的完全性。gSpan無(wú)論在計(jì)算時(shí)間上還是內(nèi)存消耗上都是一種高效的方法。但是由于它對(duì)圖模式的表示有一個(gè)非常嚴(yán)格的順序，于是有人又提出了挖掘閉頻繁圖的CloseGraph算法。
1.2.2 CloseGraph算法
??? CloseGraph算法[6]提出了一些新的方法，如同等出現(xiàn)(Equivalent Occurrence)和提前終止(Eearly Termination)，利用這些方法可以大大減少?zèng)]必要的子圖的生成，最終提高挖掘效率。
??? 給定圖g和圖數(shù)據(jù)集D={G1，G2，…，Gn}，設(shè)τ(g，D)為g在D的每個(gè)圖中的子圖同構(gòu)的總數(shù)目，圖g可以通過(guò)增加一個(gè)新邊e來(lái)擴(kuò)展形成新的圖g′，令ζ(g，g′，D)為在D的每個(gè)圖中g(shù)(對(duì)應(yīng)于g′)的可擴(kuò)展的子圖同構(gòu)的總數(shù)目。如果τ(g，D)＝ζ(g，g′，D)成立，則稱g和g′同等出現(xiàn)，即意味著在D中g(shù)出現(xiàn)時(shí)g′一定出現(xiàn)。如
不是閉的，此時(shí)僅需要擴(kuò)展g′來(lái)代替擴(kuò)展g，這種情況稱為提前終止。
??? CloseGraph算法的執(zhí)行主要分3個(gè)步驟：
??? (1)生成一個(gè)頻繁圖；
??? (2)根據(jù)一個(gè)頻繁圖g是閉的當(dāng)且僅當(dāng)不存在與g具有相同支持度的真超圖g′，亦即如果想知道一個(gè)圖是否是閉的，僅需要檢查比它多一條邊的超圖的支持度。如果二者支持度不相等，則g是閉的，否則不是閉的。通過(guò)這條規(guī)則可以檢查(1)中生成的圖是否是閉頻繁圖；
??? (3)檢查提前終止的條件和任何一種可能導(dǎo)致提前終止失敗的情況，來(lái)決定此生成圖是否應(yīng)該被擴(kuò)展。
??? CloseGraph算法不僅能夠減少不必要的生成子圖而且也能充分地提高挖掘的效率，特別是在挖掘大型圖數(shù)據(jù)集時(shí)(比如說(shuō)多于32條邊的較大的頻繁圖)，它的性能大概可以優(yōu)于gSpan性能的4～10個(gè)因子。
1.2.3? FFSM算法
??? FFSM算法[7]采用深度逐層遞歸來(lái)挖掘頻繁子圖。每個(gè)圖均用一個(gè)標(biāo)準(zhǔn)鄰接矩陣CAM(Canonical Adjacency? Matrix)來(lái)描述，它使用一種獨(dú)特的表示圖結(jié)構(gòu)的規(guī)范形式并且提出兩種有效的候選操作：FFSM聯(lián)接操作(子圖“交”)和FFSM擴(kuò)展操作；使用一種代數(shù)圖結(jié)構(gòu)(非最佳標(biāo)準(zhǔn)的CAM樹)能夠完全地列舉出所有的頻繁子圖；能通過(guò)對(duì)每1個(gè)頻繁子圖的嵌入集合測(cè)試完全避免子圖同構(gòu)。其中矩陣的聯(lián)接操作是合并兩個(gè)矩陣形成一個(gè)矩陣集，而對(duì)一個(gè)矩陣M的擴(kuò)展操作也會(huì)產(chǎn)生一個(gè)矩陣集，集合中的每一個(gè)矩陣增加了一個(gè)額外的節(jié)點(diǎn)以及連接此節(jié)點(diǎn)和M中最后一個(gè)節(jié)點(diǎn)的一條邊。
1.3 基于最小描述長(zhǎng)度的近似頻繁子結(jié)構(gòu)挖掘算法
??? SUBDUE[8]是一個(gè)基于圖的學(xué)習(xí)系統(tǒng)，該系統(tǒng)的輸入可以是帶標(biāo)記或不帶標(biāo)記的簡(jiǎn)單圖或圖集，采用了最小描述長(zhǎng)度(MDL)原則，挖掘近似的頻繁子結(jié)構(gòu)，并將它們精確地表示出來(lái)。它根據(jù)最小描述長(zhǎng)度原則，輸出最好的壓縮輸入集的子結(jié)構(gòu)模式，它采用了約束搜索(beam search)方法，通過(guò)擴(kuò)展節(jié)點(diǎn)遞增地增長(zhǎng)單個(gè)頂點(diǎn)。每次擴(kuò)展它都搜索最佳總描述長(zhǎng)度：模式的描述長(zhǎng)度和圖集合的描述長(zhǎng)度，模式全部實(shí)例都濃縮成單個(gè)節(jié)點(diǎn)。在發(fā)現(xiàn)了最好的子結(jié)構(gòu)以后輸入圖就被重寫，下一次迭代使用重寫的圖作為一個(gè)新的輸入圖，這樣，在每次迭代中，算法僅能找到一個(gè)子結(jié)構(gòu)。此外SUBDUE進(jìn)行近似匹配，允許子結(jié)構(gòu)有輕微變化，從而支持近似子結(jié)構(gòu)的發(fā)現(xiàn)，而且它也能以預(yù)先確定子圖的形式潛入到背景知識(shí)里去。
1.4 基于模式增長(zhǎng)和模式歸約的精確稠密頻繁子結(jié)構(gòu)挖掘算法
??? 關(guān)系圖是一種特殊的圖結(jié)構(gòu)，其中每個(gè)節(jié)點(diǎn)標(biāo)號(hào)在每個(gè)圖中僅用一次，它被廣泛地應(yīng)用于大型網(wǎng)絡(luò)(例如生物網(wǎng)絡(luò)、社會(huì)網(wǎng)絡(luò)、交通網(wǎng)絡(luò)和萬(wàn)維網(wǎng))的建模和分析中。在大型關(guān)系圖中頻繁高連通的子圖或稠密子圖是一種令人感興趣的模式。這種模式有助于在社會(huì)網(wǎng)絡(luò)中識(shí)別具有緊密聯(lián)系的人群，高連通的子圖也可以在生物學(xué)中表示相同功能組件中基因的集合。
??? CloseCut和Splat就是用來(lái)在大型關(guān)系圖中(大約有10 k個(gè)節(jié)點(diǎn)和1M條邊的關(guān)系圖)挖掘具有連通性約束的閉頻繁圖模式，采用邊連通性的概念并運(yùn)用相關(guān)的圖論知識(shí)來(lái)加速挖掘過(guò)程。
??? CloseCut實(shí)際上是一種基于模式增長(zhǎng)的方法，它首先開(kāi)始于一個(gè)小的頻繁候選圖，通過(guò)增加新邊來(lái)盡可能地?cái)U(kuò)展，直到找到具有相同支持度的閉超圖，在閉超圖中把先前候選圖的頂點(diǎn)壓縮成為一個(gè)頂點(diǎn)。然后分解這個(gè)高連通性的閉超圖，判斷每個(gè)頂點(diǎn)的度是否滿足連通性約束條件，提取滿足連通性約束的子圖，刪除所有的與不滿足連通性約束的頂點(diǎn)連接的邊。然后，通過(guò)增加新邊來(lái)擴(kuò)展候選圖，并且重復(fù)進(jìn)行上述操作直到?jīng)]有候選圖是頻繁的。
??? Splat是一種模式歸約的方法，它代替從小到大的枚舉圖，而且直接對(duì)關(guān)系圖取交并分解它們來(lái)得到高連通圖。令模式g是關(guān)系圖Gi1，Gi2，…，Gil(i1
??? 上述方法均是基于圖論的數(shù)據(jù)挖掘方法?；贏priori的方法必須使用寬度優(yōu)先搜索(BFS)策略，因?yàn)樗饘赢a(chǎn)生候選。這種方法為了確定大小為k+1的圖是否頻繁，必須檢查它的所有對(duì)應(yīng)的大小為k的子圖來(lái)獲得其頻度的上界。這樣，在挖掘任何大小為k+1的子圖之前，類Apriori的方法通常必須完成大小為k的子圖的挖掘。因此類Apriori的算法需要采用BFS，相反，模式增長(zhǎng)方法在搜索方式上更加靈活一些，它既可以使用寬度優(yōu)先搜索，也可以使用深度優(yōu)先搜索(DFS)，它要比基于Apriori的方法占用較少的內(nèi)存[4]。
??? AGM和FSG算法都利用鄰接矩陣分別對(duì)圖的頂點(diǎn)和邊進(jìn)行逐層構(gòu)造，以最終獲取頻繁子圖。所不同的是，AGM求出了導(dǎo)出子圖，圖不一定連通，而FSG則以邊為每次迭代的對(duì)象，求出了連通的頻繁子圖。
??? gSpan算法比AGM、FSG算法計(jì)算更高效，而且它采取從內(nèi)存到磁盤交換數(shù)據(jù)，減少了內(nèi)存的消耗。gSpan和FSG算法能夠找到所有符合用戶要求的子圖，但是不可否認(rèn)的是它們都產(chǎn)生大量的子結(jié)構(gòu)，而subDue的特色就在于它能高效地發(fā)現(xiàn)較少數(shù)量的但更有趣的最好地壓縮子結(jié)構(gòu)模式。而這些可能是gSpan和FSG不能發(fā)現(xiàn)的，但是在發(fā)現(xiàn)子圖同構(gòu)方面Subdue不比gSpan和FSG具有更高的效率，還需要進(jìn)一步擴(kuò)展。
??? CloseGraph算法類似于gSpan，但是它只挖掘閉頻繁子圖而且在對(duì)一個(gè)已經(jīng)生成的圖進(jìn)行最右擴(kuò)展之前，先檢查該圖是否存在提前終止。這樣CloseGraph可以經(jīng)常產(chǎn)生更少的圖模式，因此比挖掘全部模式集合的gSpan更有效。
??? FFSM算法能夠回避圖與圖之間直接的同構(gòu)測(cè)試，通過(guò)使用一種代數(shù)圖方法能高效地處理子圖同構(gòu)的基本問(wèn)題，它的性能優(yōu)于gSpan算法。特別是對(duì)合成數(shù)據(jù)集使用FFSM算法更高效。
??? 稠密子結(jié)構(gòu)的兩種挖掘算法在大的圖數(shù)據(jù)集上具有良好的可伸縮性。在對(duì)具有高支持度和低連通性的模式，CloseCut具有更好的性能，相反，在挖掘的初期階段，Splat能夠過(guò)濾低連通性的頻繁圖，對(duì)于高連通性約束，它具有更好的性能。但是，當(dāng)關(guān)系圖的數(shù)量增加時(shí)，它需要枚舉出取并的關(guān)系圖，此時(shí)Splat性能可能會(huì)惡化。
??? 在頻繁子圖挖掘算法中，需要解決的問(wèn)題是子圖同構(gòu)問(wèn)題和找出所有頻繁子圖的方法上，從頻繁子圖的挖掘上，已經(jīng)取得了較大進(jìn)展，上述這些算法都能夠在滿足一定的要求下，找到所需要的結(jié)果，但是子圖同構(gòu)問(wèn)題仍沒(méi)得到很好地解決(子圖同構(gòu)問(wèn)題已被證明是NP完全問(wèn)題)，需要對(duì)算法進(jìn)一步擴(kuò)展，有待進(jìn)一步研究。
??? 總結(jié)本文所提到的各種頻繁子結(jié)構(gòu)挖掘算法的共同特征及各自特點(diǎn)如表1所示。
?
??? 圖挖掘已經(jīng)具有了廣泛的應(yīng)用，包括化學(xué)、生物學(xué)、材料科學(xué)、通訊網(wǎng)絡(luò)等領(lǐng)域。利用圖挖掘方法挖掘出的各種頻繁子結(jié)構(gòu)可以被應(yīng)用在大型圖數(shù)據(jù)庫(kù)中建立圖索引、進(jìn)行結(jié)構(gòu)相似性搜索，對(duì)結(jié)構(gòu)數(shù)據(jù)集合的特征化以及進(jìn)行圖數(shù)據(jù)集的分類和聚類分析。雖然圖挖掘領(lǐng)域的研究剛剛起步，但是因?yàn)閳D拓?fù)浣Y(jié)構(gòu)在數(shù)學(xué)方面是最重要的結(jié)構(gòu)之一，并且同邏輯語(yǔ)言密切相關(guān)，因此圖挖掘理論和技術(shù)將會(huì)在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)方面作出突出的貢獻(xiàn)，并將在各個(gè)領(lǐng)域得到廣泛的實(shí)際應(yīng)用。
參考文獻(xiàn)
[1]?INOKUCHI A， WASHIO T， MMOTODA? H.An apriori-based algorithm for mining frequent substructures from graph data.In Proc.2000 European Symp.Principle of Data Mining and Knowledge Discovery(PKDD’00)，Lyon，F(xiàn)rance，1998(9):13-33.
[2] KURAMOCHI M， KARYPIS G.Frequent subgraphs discovery.In Proc.2001 Int.Conf.Data Mining(ICDM’01)，San Jose，CA，2001(11)：313-320.
[3] VANETIK N， GUDES E， SHIMONY S.E.Computing frequent graph patterns from semistructured data.In Proc.2002 Int.Conf.on Data Mining(ICDM’02)，Maebashi，Japan，2002(10)：458-465.
[4]?HAN J， KAMBER M.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社， 2007.
[5] YAN X.HAN J.gSpan：Graph-based substructure pattern mining.In Proc.2002 Int.Conf.Data Mining(ICDM’02)，Maebashi，Japan，2002(10)：721-724.
[6]?YAN X， HAN J.Closegraph：mining closed frequent graph patterns.In KDD，2003：286-295.
[7] HUAN J， WANG W， PRINS J.Efficient mining of frequent subgraphs in the presence of isomorphism.In ICDM，? 2003：549-552.
[8] KETKAR? S， HOLDER B， COOK J.Subdue：Compression-Based Frequent Pattern Discovery.In ACM， 2005：71-76.