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

蘇莉

摘 要

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

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

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

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

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

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

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

1.2 依托ILP的挖掘算法

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

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

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

3 結束語

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

參考文獻

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

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

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

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