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

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

[關(guān)鍵詞]數(shù)據(jù)；挖掘；最大頻繁子圖；決策樹；子圖同構(gòu)

doi：10.3969/j.issn.1673 - 0194.2017.04.099

[中圖分類號]TP301.6 [文獻(xiàn)標(biāo)識碼]A [文章編號]1673-0194（2017）04-0-02

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

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

1 圖挖掘相關(guān)概念

（1）標(biāo)記圖用五元組G=（V，E，ΣV，ΣE，L）表示標(biāo)記圖，V是結(jié)點(diǎn)集，E是邊集，ΣV，ΣE分別為結(jié)點(diǎn)標(biāo)記和邊標(biāo)記的集合，L為V→ΣV，E→ΣE的映射。

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

G1為G2的子圖當(dāng)且僅當(dāng)：

V1V2，E1E2

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

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

（3）同構(gòu)如果圖G1=（V1，E1，ΣV1，ΣE1，L1）同構(gòu)于圖G2=（V2，E2，ΣV2，

ΣE2，L2）當(dāng)且僅當(dāng)存在映射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）子圖同構(gòu)若圖G1子圖同構(gòu)于圖G2，當(dāng)且僅當(dāng)在圖G2中存在子圖G2'，使G2'同構(gòu)于圖G1。

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

設(shè)

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

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

2 決策樹

決策樹是基于機(jī)器學(xué)習(xí)的數(shù)據(jù)挖掘技術(shù)，它形式簡單，分類速度快，無需先驗(yàn)知識，而且由決策樹表達(dá)的規(guī)則直觀清晰。應(yīng)用決策樹計(jì)算支持度的想法來源于FSM算法，F(xiàn)SM算法存在不能正確計(jì)算出支持度的問題，本文通過改進(jìn)決策樹解決這個(gè)問題，具體改進(jìn)如下。

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

2.1 構(gòu)造決策樹方法

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

（2）在構(gòu)造決策樹之前，首先找到圖集中所有不同的結(jié)點(diǎn)標(biāo)記，然后計(jì)算結(jié)點(diǎn)支持度生成兩個(gè)集合，分別為頻繁結(jié)點(diǎn)集和非頻繁結(jié)點(diǎn)集，如果某結(jié)點(diǎn)標(biāo)記的支持度為100%，則僅將該結(jié)點(diǎn)標(biāo)記添加到?jīng)Q策樹中第二層，將其作為根節(jié)點(diǎn)的孩子節(jié)點(diǎn)。

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

2.2 構(gòu)造決策樹實(shí)例

假設(shè)圖集中含有兩個(gè)圖，minsup=100%，為圖集構(gòu)造決策樹如下。①將圖進(jìn)行編號為G1、G2。②A、B、C均為頻繁的結(jié)點(diǎn)標(biāo)記，結(jié)點(diǎn)標(biāo)記A的支持度為100%，將A添加到?jīng)Q策樹的第二層，將其作為根節(jié)點(diǎn)的孩子節(jié)點(diǎn)。③現(xiàn)在從圖G1的結(jié)點(diǎn)A開始構(gòu)造它的決策樹，與A關(guān)聯(lián)的邊有兩條分別為（A，1，B）（A，2，C），將表示這兩條邊的節(jié)點(diǎn)添加在決策書的第三層，作為A的孩子節(jié)點(diǎn)。與（A，1，B）關(guān)聯(lián)的有兩條邊分別為（A，2，C）及（B，2，C），通過擴(kuò)展得到兩個(gè)含有兩條邊的圖，將其作為（A，1，B）的孩子添加到?jīng)Q策樹的第四層，以同樣的方式繼續(xù)擴(kuò)展圖，構(gòu)造出的決策樹如圖1所示。繼續(xù)將G2添加到?jīng)Q策樹中，同樣從結(jié)點(diǎn)A開始構(gòu)造，如果在當(dāng)前的決策樹中存在表示同一圖的節(jié)點(diǎn)則不重復(fù)添加節(jié)點(diǎn)，圖G1是圖G2的超圖則將表示圖G2的節(jié)點(diǎn)作為自身的孩子節(jié)點(diǎn)，編號為G2。

3 DMFS算法

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

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

圖2 剪枝后的決策樹

4 實(shí)驗(yàn)結(jié)果

模擬數(shù)據(jù)集由X.Yan 等人提供的數(shù)據(jù)模擬器進(jìn)行模擬，不同類型的關(guān)系模擬為邊標(biāo)記。本文用數(shù)據(jù)模擬器產(chǎn)生圖集時(shí)以參數(shù)D、E、V、L為基礎(chǔ)，D為圖集的大小，E、V分別為不同的邊標(biāo)記和結(jié)點(diǎn)標(biāo)記的數(shù)量，L為最大頻繁子圖的平均大小。在這個(gè)實(shí)驗(yàn)中L由4變化到12，D=1K，minsup=2℅，E=20，V=20。即生成圖的總數(shù)為1 000個(gè)，最大頻繁子圖的平均大小從4變化到12，不同的結(jié)點(diǎn)標(biāo)記的數(shù)量和不同的邊標(biāo)記的數(shù)量均為20。

圖3 MARGIN算法和DMFS算法的運(yùn)行時(shí)間

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

5 結(jié) 語

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

主要參考文獻(xiàn)

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

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

[3]Abraham Silberschatz，Henry F Korth，S Sudarshan.數(shù)據(jù)庫系統(tǒng)概念[M].第6版.楊冬青，李紅燕，唐世渭，譯.北京：機(jī)械工業(yè)出版社，2012.

[4]鄒兆年.不確定圖數(shù)據(jù)挖掘[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2013.

[5]譚浩強(qiáng).C語言程序設(shè)計(jì)題解與上機(jī)指導(dǎo)[M].北京：清華大學(xué)出版社，2000.

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

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

[8]唐德權(quán)，吳紹兵，凌志剛.一種新的圖聚類算法研究[J].計(jì)算機(jī)應(yīng)用與軟件，2014（6）.