最大頻繁子圖挖掘算法DMFS

柴然++劉媛媛++郭彥穎

[摘 要]最大頻繁子圖挖掘得到的結果數量少而且不會丟失信息，有益于對結果的理解和應用。為了避免挖掘所有頻繁子圖，降低挖掘難度，本文應用決策樹挖掘最大頻繁子圖。挖掘過程中，首先構造決策樹，然后對決策樹進行剪枝得到最大頻繁子圖，最后通過實驗驗證算法的可行性以及正確性。

[關鍵詞]數據；挖掘；最大頻繁子圖；決策樹；子圖同構

doi：10.3969/j.issn.1673 - 0194.2017.04.099

[中圖分類號]TP301.6 [文獻標識碼]A [文章編號]1673-0194（2017）04-0-02

基于圖的數據挖掘提出時間不長，但圖論作為數學的研究領域已經有了很長的歷史，所以頻繁子圖挖掘得以很好地發展。但是頻繁子圖挖掘得到的結果數量巨大，影響著對結果的理解、應用以及分析工作。最大頻繁子圖包含了所有頻繁子圖，挖掘最大頻繁子圖可以保證信息的完整性，而且挖掘最大頻繁子圖可以得到少量結果從而節省了空間，簡化了分析工作?；诖耍梢詫㈩l繁子圖挖掘轉換為最大頻繁子圖挖掘。MARGIN算法和SPIN算法是經典的最大頻繁子圖挖掘算法，它們必須挖掘出所有的頻繁子圖，然后再挖掘最大頻繁子圖。雖然最大頻繁子圖挖掘得到的結果少了，但挖掘過程很復雜，難度很高。

針對最大頻繁子圖挖掘算法中存在的問題，本文提出新的最大頻繁子圖挖掘算法DMFS（Decision tree to Mining Maximal Frequent Subgraph）。DMFS算法利用決策樹來挖掘最大頻繁子圖，首先構造決策樹，其次對決策樹進行剪枝（剪掉決策樹中不頻繁的節點），最后通過剪枝后的決策樹來得到最大頻繁子圖集合。

1 圖挖掘相關概念

（1）標記圖用五元組G=（V，E，ΣV，ΣE，L）表示標記圖，V是結點集，E是邊集，ΣV，ΣE分別為結點標記和邊標記的集合，L為V→ΣV，E→ΣE的映射。

（2）子圖給定圖G1=（V1，E1，ΣV1，ΣE1，L1）和G2=（V2，E2，ΣV2，ΣE2，L2），

G1為G2的子圖當且僅當：

V1V2，E1E2

?u∈V1，L1（u）=L2（u）

?（u，v）∈E1，L1（u，v）=L2（u，v）

（3）同構如果圖G1=（V1，E1，ΣV1，ΣE1，L1）同構于圖G2=（V2，E2，ΣV2，

ΣE2，L2）當且僅當存在映射f：

?u∈V1，L1（u）=L2（f（u））

?u，v∈V1，（u，v）∈E1則（f（u））∈E2

?（u，v）∈E1則L1（u，v）=L2（f（u），f（v））

（4）子圖同構若圖G1子圖同構于圖G2，當且僅當在圖G2中存在子圖G2'，使G2'同構于圖G1。

（5）支持度給定一個大小為n的圖數據庫D={G1，G2，…，Gn}

設

則g在圖數據庫D中的支持度sup（g，D）=?（g，D）/n。

（6）頻繁子圖給定最小支持度minsup，如果圖g的支持度sup（g，D）≥minsup則稱圖g為頻繁子圖。如果頻繁子圖g的任意超圖均不頻繁，則圖g為最大頻繁子圖。

2 決策樹

決策樹是基于機器學習的數據挖掘技術，它形式簡單，分類速度快，無需先驗知識，而且由決策樹表達的規則直觀清晰。應用決策樹計算支持度的想法來源于FSM算法，FSM算法存在不能正確計算出支持度的問題，本文通過改進決策樹解決這個問題，具體改進如下。

①DMFS算法在構造決策樹時不是采取每次增加一個頂點的方式，而是每次增加一條邊。②FSM算法中將某節點的支持度計為其孩子節點的支持度的總和，忽略了決策樹中會有很多重復的leaf node，所以必須改變支持度的計算方法。③結合經典MARGIN算法的剪枝策略，通過對決策樹進行剪枝得到最大頻繁子圖。

2.1 構造決策樹方法

（1）為了正確且簡單地計算子圖的支持度，對圖集中的兩個圖進行編號。

（2）在構造決策樹之前，首先找到圖集中所有不同的結點標記，然后計算結點支持度生成兩個集合，分別為頻繁結點集和非頻繁結點集，如果某結點標記的支持度為100%，則僅將該結點標記添加到決策樹中第二層，將其作為根節點的孩子節點。

（3）從編號為1的圖以每次添加一條邊的方式構造圖集的決策樹。

2.2 構造決策樹實例

假設圖集中含有兩個圖，minsup=100%，為圖集構造決策樹如下。①將圖進行編號為G1、G2。②A、B、C均為頻繁的結點標記，結點標記A的支持度為100%，將A添加到決策樹的第二層，將其作為根節點的孩子節點。③現在從圖G1的結點A開始構造它的決策樹，與A關聯的邊有兩條分別為（A，1，B）（A，2，C），將表示這兩條邊的節點添加在決策書的第三層，作為A的孩子節點。與（A，1，B）關聯的有兩條邊分別為（A，2，C）及（B，2，C），通過擴展得到兩個含有兩條邊的圖，將其作為（A，1，B）的孩子添加到決策樹的第四層，以同樣的方式繼續擴展圖，構造出的決策樹如圖1所示。繼續將G2添加到決策樹中，同樣從結點A開始構造，如果在當前的決策樹中存在表示同一圖的節點則不重復添加節點，圖G1是圖G2的超圖則將表示圖G2的節點作為自身的孩子節點，編號為G2。

3 DMFS算法

DMFS算法從決策樹的倒數第二層依次向上判斷，剪枝的原則為：①若節點v不頻繁且其所有兄弟節點都不頻繁，此時如果節點v的雙親節點u是頻繁的，則刪除以v和它的兄弟節點為根節點的決策樹，使u成為葉子節點，不再判斷u的雙親節點；②如果節點v是頻繁的，例如圖（（A，1，B）（A，2，C）），則只刪除以v的不頻繁的兄弟節點，例如圖（（A，1，B）（B，2，C））的節點，為根節點的決策樹，不再判斷v的雙親；③對決策樹進行剪枝后得到新的決策樹，但在新的決策樹中可能存在重復的葉子，或某些葉子節點同構，所以為了得到最大頻繁子圖集合還是需要進行子圖同構判斷。

對圖1中的決策樹進行剪枝后得到新的決策樹如圖2所示。

圖2 剪枝后的決策樹

4 實驗結果

模擬數據集由X.Yan 等人提供的數據模擬器進行模擬，不同類型的關系模擬為邊標記。本文用數據模擬器產生圖集時以參數D、E、V、L為基礎，D為圖集的大小，E、V分別為不同的邊標記和結點標記的數量，L為最大頻繁子圖的平均大小。在這個實驗中L由4變化到12，D=1K，minsup=2℅，E=20，V=20。即生成圖的總數為1 000個，最大頻繁子圖的平均大小從4變化到12，不同的結點標記的數量和不同的邊標記的數量均為20。

圖3 MARGIN算法和DMFS算法的運行時間

從圖3可以看出，當L很小時DMFS算法與最大頻繁子圖挖掘算法MARGIN運行時間相差不是很明顯，但隨著L的增大，算法DMFS的優勢越來越明顯，且運行時間隨挖掘得到的最大頻繁子圖的增大不斷增長。通過理論和實驗相結合，可知DMFS算法優于MARGIN算法。

5 結 語

本文提出了新的最大頻繁子圖挖掘算法DMFS，通過構造決策樹并對其進行剪枝來得到最大頻繁子圖，減少了子圖同構判斷的次數，提高了算法的挖掘效率。DMFS算法采用的是自頂向下的挖掘思想，可以避免挖掘所有的頻繁子圖，降低挖掘難度。最后，實驗驗證了DMFS算法較經典的最大頻繁子圖挖掘算法MARGIN算法更高效。

主要參考文獻

[1]王映龍，楊珺，周法國，等.加權最大頻繁子圖挖掘算法的研究[J].計算機工程與應用，2009（20）.

[2]Jiawei Han，Micheline Kamber.數據挖掘概念與技術[M].范明，孟小峰，譯.北京：機械工業出版社，2012.

[3]Abraham Silberschatz，Henry F Korth，S Sudarshan.數據庫系統概念[M].第6版.楊冬青，李紅燕，唐世渭，譯.北京：機械工業出版社，2012.

[4]鄒兆年.不確定圖數據挖掘[M].哈爾濱：哈爾濱工業大學出版社，2013.

[5]譚浩強.C語言程序設計題解與上機指導[M].北京：清華大學出版社，2000.

[6]陳曉，劉鳳春，李建晶，等.一種新的自頂向下挖掘最大頻繁子圖的算法[J].計算機工程與科學，2013（4）.

[7]郭景峰，張偉，柴然.一種新的頻繁子圖挖掘算法[J].計算機工程，2011（20）.

[8]唐德權，吳紹兵，凌志剛.一種新的圖聚類算法研究[J].計算機應用與軟件，2014（6）.