頻繁子圖挖掘算法

定義與分類

(1)按照模式挖掘算法的輸入數據類型進行分類:分為graph-transaction和single-graph兩種類型。graph-transaction型模式挖掘所處理的輸入數據是由許多規模相對較小的圖構成的集合，每個圖可能只包含幾十到幾百個頂點;而single-graph型模式挖掘的對象則只有-個大圖，這個大圖包含成千上萬個頂點。這兩種類型的區別還在於它們計算候選子圖頻度時所使用的策略。graph-transaction型計算模式在圖集合每個圖中是否出現，不管它在同-個圖中出現了多少次均計數-次，而single-graph型則計算模式在這個大圖中不同位置出現的總次數。根據兩種類型的特徵，解決graph-transaction類型的算法不能用來解決single-graph類型模式挖掘，但是Single-graph類型的算法卻能方便套用於graph-transaction類型。

(2)按照採用度量的不同進行分類:分為支持度(support)、支持度-置信度、MDL(minimumdescri-Ptionlength)三種。支持度型挖掘是以子圖在輸入圖中出現的次數來作為度量的，大部分算法都是基於支持度的;MDL型挖掘是以壓縮輸入數據的程度來度量，-般採用公式valuo(s，g)=dl(g)/(dl(g1)+dl(g2))來計算，其中:是子圖，g是輸入的圖集合，dl(g)表示圖集合g的存儲空間，dl(g2)表示把g中所有出現:的地方都用同-個頂點替換後的圖形所需的存儲空間;支持度-置信度型挖掘是以既要滿足最小支持度又要滿足最小置信度來衡量的。還有其它-些度量方法，這裡就不再介紹了。

(3)按照挖掘出的頻繁子圖的類型進行分類:分為一般子圖、連通子圖、誘導子圖等。

算法思路

算法的思路比較簡單，以遞歸計數為基礎，可以挖掘出所有頻繁子圖。但是對於包含較多圖的輸入集合來說執行效率非常低，主要是因為挖掘算法在生成候選子圖時要判斷是否存在相同的k-1子圖，當川尺大時，這需要花費很長時間。並且通過每次添加一個頂點來產生候選子圖時會產生許多冗餘k+l子圖。

在剪枝的過程中，也需要很多時間來判斷每個k+l候選子圖的所有k子圖是否都是頻繁的。剪枝後的候選子圖仍然很多，因此需要大量的重複掃描輸入圖集合來計算候選子圖的支持度。這就占用了大量的記憶體空間和CPU處理時間，很難發現較大的模式子圖，執行效率不高。而頻繁子圖挖掘算法是在挖掘算法算法的基礎上提出來的。區別在於頻繁子圖挖掘算法旨在發現連通的頻繁子圖，採用了一些特殊的技巧以提高性能。

它引入了半連通圖的概念，圖G是半連通圖若且唯若G是連通圖或G只由一個連通分支和一個孤立點組成。在頻繁子圖挖掘算法中所使用的規範化標記將頂點的標號也考慮在內，同時還套用了諸如規範化標記發現和砂樹等技巧來提高其性能。Kuramochi.M等人提出的FSG算法採用完全不同的找尋方法挖掘頻繁子圖。在他們的算法中採取每次添加一條邊的策略，而不是每次添加一個頂點，並加強了候選子圖的剪枝，在計算候選子圖的支持度時採用TID列表幫助加速計算，使得執行效率較挖掘算法有所提高。

經典算法

Apriori算法

"generation and test" 思想:

k-頻繁子集用於生成 k+1-子集，根據downward closure property性質進行剪枝，生成 k+1候選集，通過對數

據庫進行掃描判斷候選子集中哪些是頻繁的。如此下去，直到不能找到頻繁項集。

"downward closure propert" 性質：

如果 k+1子集的任何一個k子集是非頻繁的，則是k+1子集一定也是非頻繁的。

a. AGM算法

每次添加一個頂點

b. FSG算法

每次添加一條邊

FP-growth算法

主要思想：

將產生頻繁集的數據壓縮到一棵頻繁模式樹FP-tree中，用FP-tree存儲項的關聯信息，然後對模式樹產生頻繁集。

a. gSpan算法

b. FFSM算法

算法流程圖

頻繁子圖挖掘算法

算法流程如圖所示：