蘇莉

摘 要

本文圍繞圖集中的頻繁子圖挖掘算法、單圖中的頻繁子圖挖掘算法兩個(gè)方面展開討論，對概率頻繁模式挖掘算法進(jìn)行了研究以及綜述，并在此基礎(chǔ)上提出了一些筆者自己的見解，希望能夠?qū)窈蟮母怕暑l率模式挖掘算法的研究提供一些理論建議。

【關(guān)鍵詞】概率頻繁模式 挖掘算法

現(xiàn)階段，已有越來越多高效的算法被研發(fā)出來，用于對圖集進(jìn)行挖掘，其中也不乏有一些算法是用作對單圖中的模式進(jìn)行挖掘的，由于這些算法的應(yīng)用對象有所差別，因此他們的效果也存在一定的差異。而針對任何一個(gè)實(shí)際存在的問題，最大的挑戰(zhàn)在于如何進(jìn)行有效解決。在這一需求下，我們需要將這些不同的算法進(jìn)行分類。在本文中，筆者主要針對概率頻繁模式挖掘算法展開了研究與綜述，并根據(jù)圖的頻繁子圖挖掘算法的應(yīng)用對象分為圖集以及單圖兩類。

1 圖集中的頻繁子圖挖掘算法

1.1 依托貪心搜索的挖掘算法

有關(guān)貪心搜索下的頻繁子圖挖掘算法，早在一九九四年就已經(jīng)獲得了兩大代表性的研究成果，分別為SUBDUE以及GBI，筆者以SUBDUE舉例進(jìn)行說明。SUBDUE是在最小描述長度原則下，使用定點(diǎn)替代方式來識(shí)別出所有能夠有效壓縮原始輸入數(shù)據(jù)的模式。這一算法的以僅含有輸入圖 G中的一個(gè)定點(diǎn)所對應(yīng)的子圖為起點(diǎn)，在逐漸加入頂點(diǎn)的方式下使子圖得到擴(kuò)展。此外，SUBDUE還有一大優(yōu)勢即在于它能夠?qū)崿F(xiàn)與子圖近似值的匹配，此外它還能夠同預(yù)先定義子圖的方式來實(shí)現(xiàn)背景知識(shí)的嵌入。SUBDUE運(yùn)用了一種啟發(fā)式搜索模式來降低搜索空間大小，以此來達(dá)到提升計(jì)算性能的目的。此后，SUBDUE還被拓展成為了一種圖分類算法，被稱作SUBDUECL。這種新的算法不需要再使用最小的描述長度，而是使用以子圖置信度的啟發(fā)模式所取代。

另外一種GBI算法與SUBDUE存在極大的共同點(diǎn)，它也是使用一個(gè)頂點(diǎn)來替代每一個(gè)所識(shí)別的子圖從而來實(shí)現(xiàn)壓圖像的不斷壓縮，從而使圖規(guī)模不斷縮小。它使用了經(jīng)驗(yàn)圖規(guī)模定義，充分反映了壓縮圖以及圖區(qū)模式的規(guī)模，這種搜索方式的優(yōu)勢在于對不間斷壓縮產(chǎn)生了妨礙作用。此外，GBI還能夠?qū)τ虚]路徑中的有向或者無向標(biāo)簽圖進(jìn)行處理。搜索時(shí)的每一個(gè)環(huán)節(jié)都是使用邊或塊老搜索到對應(yīng)的連接頂點(diǎn)集合，在規(guī)范化標(biāo)記法的應(yīng)用下確認(rèn)獲取的子圖是否結(jié)構(gòu)相同。GBI還是一種特征構(gòu)造器，可以對圖數(shù)據(jù)中的決策樹分類器特征進(jìn)行構(gòu)造。

1.2 依托ILP的挖掘算法

我們可以簡單地使用一階邏輯來對圖進(jìn)行表達(dá)，因此在此基礎(chǔ)上設(shè)計(jì)了一個(gè)以ILP為依托的挖掘算法。在ILP算法的基礎(chǔ)上能夠總結(jié)出一個(gè)可以對正負(fù)樣本集進(jìn)行準(zhǔn)確分類的規(guī)則集合 。在ILP系統(tǒng)中對圖模型進(jìn)行構(gòu)建時(shí)，杉樹規(guī)則一般來說所對應(yīng)的均為子圖，基本上所有基于ILP的方法從根本上分析都未貪心算法，使用各種不同的啟發(fā)方式對可能的假設(shè)結(jié)果進(jìn)行剪輯。由此可見，它們更加傾向于識(shí)別一些支持性較高的子圖，而由DEHASPE等設(shè)計(jì)的ILP系統(tǒng)WARMR則另當(dāng)別論，它不是在圖形結(jié)構(gòu)處理這一需求導(dǎo)向下而特意設(shè)計(jì)而成的，同時(shí)也沒有使用圖模型 特定的優(yōu)化技術(shù)，所以說它對應(yīng)的計(jì)算量極高。此外，還有一個(gè)特例為WARMR系統(tǒng)，但是該系統(tǒng)在計(jì)算過程中較為復(fù)雜，因此一般情況下我們都將其應(yīng)用在出現(xiàn)頻率較高的子結(jié)構(gòu)當(dāng)中。

2 單圖中的頻繁子圖挖掘算法

SUBDUE與GBI不僅能夠應(yīng)用在頻繁子圖外界當(dāng)中，同時(shí)它也是目前知名度最高的單圖頻繁子圖挖掘使用頂點(diǎn)編號對輸入圖進(jìn)行有損性壓縮，在此基礎(chǔ)上獲得一種數(shù)據(jù)結(jié)構(gòu)，叫做SUMMARY，這一數(shù)據(jù)機(jī)構(gòu)能夠在短時(shí)間內(nèi)排除所有頻率較低的候選子圖，若圖中的子圖類型較少但頻率極高，就能夠?qū)⑦@一方法進(jìn)行有效發(fā)揮，反之則無法有效發(fā)揮其效果。其中值得一提的是，有損壓縮、SEUS算法以及上文提到的兩種算法都不具備較高的精確度，Vanetik等研究學(xué)者設(shè)計(jì)了一種依托邊的子圖增長策略而形成的算法，這種算法能夠應(yīng)用在帶有標(biāo)識(shí)的無向單圖當(dāng)中，此外還能夠?qū)σ磺邪趦?nèi)的頻繁子圖進(jìn)行準(zhǔn)確挖掘，在這種算法當(dāng)中，每一個(gè)嵌入間邊均無法疊加在一起，且每一種子圖對應(yīng)的嵌入數(shù)量實(shí)際上也就是這一子圖的發(fā)生頻率。二零零五年，Ku-ramochi等研究學(xué)者設(shè)計(jì)了SiGram（ Pafi）算法，并與此同時(shí)提出了子圖間邊疊加頻繁的這一問題，然而遺憾的是，并沒有針對這一問題提出對策，這一算法抓住了邊無法疊加子圖反向閉包的這個(gè)特點(diǎn)，并使用了廣度以及深度兩個(gè)截然不同的增長辦法進(jìn)行計(jì)算，實(shí)現(xiàn)了有效的子圖挖掘目的?？莎B加挖掘算法對于后基因組分子生物學(xué)來說具有十分關(guān)鍵的意義。

3 結(jié)束語

隨著社會(huì)的不斷發(fā)展，各種現(xiàn)代化科學(xué)技術(shù)也在飛躍進(jìn)步，如生物信息學(xué)、計(jì)算機(jī)網(wǎng)絡(luò)學(xué)、Web分析學(xué)以及化學(xué)情報(bào)學(xué)等，這些學(xué)科的發(fā)展使得圖數(shù)據(jù)變得更加重要了，尤其是在一些結(jié)構(gòu)問題十分復(fù)雜的建模過程中，其重要性得到了不斷的突顯。為了能夠?qū)崿F(xiàn)對圖的深入特征化分析以及分類分析，頻繁子圖挖掘技術(shù)所肩負(fù)的任務(wù)也越來越艱巨。在本文中，筆者針對典型頻繁子圖挖掘算法進(jìn)行了詳細(xì)的綜述，并對這些算法的具體應(yīng)用情況以及相互之間的關(guān)系進(jìn)行了重點(diǎn)介紹，并提出了這些算法各種存在的不足以及長處。站在理論角度來分析，頻繁子圖挖掘算法無論是在同構(gòu)還是在圖特征方面都存在著許多問題，因此在今后的研究過程中還具有很大可挖掘的價(jià)值，現(xiàn)階段已經(jīng)發(fā)展成為了數(shù)據(jù)挖掘領(lǐng)域中的重點(diǎn)研究內(nèi)容。從一九九四年至今，該領(lǐng)域相關(guān)的論文已發(fā)表數(shù)百篇，足已顯現(xiàn)出其可觀的發(fā)展趨勢。

參考文獻(xiàn)

[1]喬少杰，韓楠，丁治明，金澈清，孫未未，舒紅平.多模式移動(dòng)對象不確定性軌跡預(yù)測模型[J].自動(dòng)化學(xué)報(bào)：1-11.

[2]杜戈王子.概率頻繁模式挖掘之U-apriori算法研究[J].湖南城市學(xué)院學(xué)報(bào)（自然科學(xué)版），2013（03）：71-75.

[3]韓蒙.RAKING：一種高效的不確定圖K-極大頻繁模式挖掘算法[A].中國計(jì)算機(jī)學(xué)會(huì)數(shù)據(jù)庫專業(yè)委員會(huì).NDBC2010第27屆中國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集A輯一[C].中國計(jì)算機(jī)學(xué)會(huì)數(shù)據(jù)庫專業(yè)委員會(huì)，2010：9.

[4]唐懿芳，穆志純，張師超，鐘達(dá)夫.挖掘數(shù)據(jù)流頻繁模式的相關(guān)技術(shù)和算法研究綜述[J].計(jì)算機(jī)工程與應(yīng)用，2009（26）：121-125.