概率頻繁模式挖掘算法研究綜述

蘇莉

摘 要

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

【關鍵詞】概率頻繁模式 挖掘算法

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

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

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

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

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

1.2 依托ILP的挖掘算法

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

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

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

3 結(jié)束語

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

參考文獻

[1]喬少杰，韓楠，丁治明，金澈清，孫未未，舒紅平.多模式移動對象不確定性軌跡預測模型[J].自動化學報：1-11.

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

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

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