一種改進(jìn)的極大完全子圖挖掘算法

時(shí)燕++張玉琢

摘要：在計(jì)算機(jī)領(lǐng)域中，圖是最復(fù)雜的數(shù)據(jù)結(jié)構(gòu)之一。該文研究了圖的挖掘理論及算法。特別針對(duì)參考文獻(xiàn)[1]中圖的極大完全子圖算法 “MaxcodeFMCG”（Finding Maximal Complete Subgraph by Maxcode）進(jìn)行了改進(jìn)，使算法效率得到提高；并設(shè)計(jì)了相關(guān)數(shù)據(jù)結(jié)構(gòu)，在Microsoft Visual Studio 2008開(kāi)發(fā)軟件平臺(tái)上，進(jìn)行仿真實(shí)驗(yàn)，尋找出了無(wú)向圖所對(duì)應(yīng)的所有極大完全子圖，實(shí)驗(yàn)結(jié)果正確。

關(guān)鍵詞： 數(shù)據(jù)挖掘；頻繁模式；極大完全子圖

中圖分類(lèi)號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）07-0174-04

1 概述

近年來(lái)，數(shù)據(jù)挖掘引起信息產(chǎn)業(yè)界的極大關(guān)注，頻繁模式挖掘問(wèn)題的研究也已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域研究的熱點(diǎn)之一。尋找頻繁模式的兩大經(jīng)典算法是Apriori算法以及FP增長(zhǎng)算法，前者采用寬度優(yōu)先的方法遍歷數(shù)據(jù)，后者則采用深度優(yōu)先的方法遍歷數(shù)據(jù)，兩者都能實(shí)現(xiàn)頻繁模式的挖掘，但是當(dāng)數(shù)據(jù)量很大時(shí)，兩類(lèi)算法在執(zhí)行時(shí)都需要占用大量的內(nèi)存，從而降低了挖掘效率。研究發(fā)現(xiàn)：大部分現(xiàn)實(shí)中的事務(wù)數(shù)據(jù)都可以轉(zhuǎn)化為一定的圖結(jié)構(gòu)，結(jié)合圖的一些性質(zhì)，通過(guò)尋找圖的極大完全子圖，實(shí)現(xiàn)圖劃分操作，從而間接地把事務(wù)數(shù)據(jù)劃分為若干子事務(wù)。通過(guò)這種劃分方法解決了數(shù)據(jù)量巨大會(huì)導(dǎo)致兩個(gè)經(jīng)典算法的執(zhí)行時(shí)內(nèi)存不足、效率降低等問(wèn)題，之后只需要任選經(jīng)典算法中的一個(gè)，對(duì)劃分之后的每個(gè)子集進(jìn)行處理就可事半功倍的得到頻繁模式。

2 基本定義和定理

2.1圖

論文關(guān)注的是無(wú)向連通圖，并使用圖的鄰接矩陣表示圖的存儲(chǔ)結(jié)構(gòu)。

定義1 （鄰接矩陣G的code碼）設(shè)有n個(gè)頂點(diǎn)的圖G的鄰接矩陣A為：

算法思想分析：

基于性質(zhì)2的討論，我們可以簡(jiǎn)化4）和5），因?yàn)槊看蝺蓚€(gè)K階矩陣連接之前如果他們對(duì)應(yīng)的code碼不全為1，那么連接后生成的K+1階矩陣對(duì)應(yīng)的code碼也一定不全為1，那么之后對(duì)K+1階矩陣生成code碼并判斷是否全為1的過(guò)程也顯得徒勞。反之，只有兩個(gè)K階矩陣對(duì)應(yīng)的code碼全為1，那么之后對(duì)兩個(gè)矩陣連接生成的K+1階矩陣對(duì)應(yīng)的code碼進(jìn)行判斷分析才會(huì)有必要。但是如果兩個(gè)K階矩陣對(duì)應(yīng)的code碼全為1，即連接后生成K+1階矩陣所對(duì)應(yīng)的code碼的前K位一定全為1，那也就是說(shuō)，若要判斷兩個(gè)矩陣連接生成的K+1階矩陣對(duì)應(yīng)code碼全為1，就只需要判斷兩個(gè)K階矩陣中不相同的兩個(gè)頂點(diǎn)之間在當(dāng)前對(duì)應(yīng)的逆導(dǎo)出子圖G中是否有邊相連，若有邊相連則K+1階矩陣對(duì)應(yīng)code碼全為1，若無(wú)邊相連，則K+1階矩陣對(duì)應(yīng)code碼不全為1，其對(duì)應(yīng)的頂點(diǎn)集不屬于極大完全子圖。

3.2.2改進(jìn)后的算法思想

算法1：

根據(jù)以上分析可知，生成極大完全子圖頂點(diǎn)的算法過(guò)程的4）、5）、6）部分可以做些改進(jìn)，如下：

4） 將G中度最大的頂點(diǎn)V1與G中其余頂點(diǎn)組合成長(zhǎng)度為2的頂點(diǎn)集，并將它們放入Rset中；

5） for（K=2；K

分別將Rset中兩個(gè)長(zhǎng)度為K的頂點(diǎn)序列集進(jìn)行比較：

如果有它們K-1個(gè)頂點(diǎn)相同且存在一個(gè)頂點(diǎn)不同，那么繼續(xù)判斷兩個(gè)不同的頂點(diǎn)在圖G中是否有邊相連，如果有邊相連則將當(dāng)前兩個(gè)頂點(diǎn)集合并后生成的新的長(zhǎng)度K+1的頂點(diǎn)集存入Rset中；

否則兩個(gè)長(zhǎng)度為K的頂點(diǎn)進(jìn)行比較，直到將所有長(zhǎng)度為K的頂點(diǎn)集都兩兩比較完。

6）刪除φ（v1）中重復(fù)的頂點(diǎn)集，如果φ（v1）中某一頂點(diǎn)序列中某一頂點(diǎn)序列中的所有頂點(diǎn)均出現(xiàn)在另一個(gè)頂點(diǎn)序列中，則刪除該頂點(diǎn)序列，直到φ（v1）中不存在這樣的頂點(diǎn)序列為止。

3.2.3求圖的逆導(dǎo)出子圖算法設(shè)計(jì)

算法2：求圖的逆導(dǎo)出子圖

輸入數(shù)據(jù)：圖G

輸出圖G的逆導(dǎo)出子圖

1） 求當(dāng)前圖G中度最大的頂點(diǎn)在頂點(diǎn)表中的下標(biāo)。

2） G1G，將圖G的信息復(fù)制給G1。

3）遍歷圖G1并把圖G1中與度最大的頂點(diǎn)有邊相連的頂點(diǎn)在圖G中對(duì)應(yīng)存儲(chǔ)的信息依次全部刪除。

4）最后剩余的圖信息即為圖G的逆導(dǎo)出子圖。

3.3.4求圖的逆導(dǎo)出補(bǔ)圖算法設(shè)計(jì)

算法3

輸入數(shù)據(jù)：圖G，存儲(chǔ)逆導(dǎo)出補(bǔ)圖Gc的地址，當(dāng)前圖G中度最大的頂點(diǎn)在頂點(diǎn)表中的下標(biāo)。

輸出：圖的逆導(dǎo)出補(bǔ)圖。

1） 求當(dāng)前圖G中度最大的頂點(diǎn)在頂點(diǎn)表中的下標(biāo)。

2） GcG。

3）遍歷圖G1并把圖Gc中與度最大的頂點(diǎn)沒(méi)有邊相連的頂點(diǎn)在圖G中對(duì)應(yīng)存儲(chǔ)的信息依次全部刪除。

4）最后剩余的圖信息即為圖G的逆導(dǎo)出子圖。

3.3.5算法具體實(shí)現(xiàn)

上述算法在實(shí)現(xiàn)過(guò)程中用到的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)如下

1）每個(gè)逆導(dǎo)出子圖所對(duì)應(yīng)的極大完全子圖頂點(diǎn)集數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)

以圖G的逆導(dǎo)出子圖G1為例，G1所對(duì)應(yīng)的頂點(diǎn)集存儲(chǔ)結(jié)構(gòu)示例圖如下：

圖9 圖G1的極大完全子圖頂點(diǎn)集存儲(chǔ)結(jié)構(gòu)示例

為了簡(jiǎn)化對(duì)堆串中數(shù)據(jù)的增刪改的操作，對(duì)堆串的結(jié)構(gòu)進(jìn)行了適當(dāng)?shù)母倪M(jìn)，同一個(gè)Type所對(duì)應(yīng)的頂點(diǎn)序列集存儲(chǔ)在同一個(gè)連續(xù)的存儲(chǔ)單元中，反之不同Type的頂點(diǎn)序列集存儲(chǔ)在不同的數(shù)組中，這樣可以減少對(duì)頂點(diǎn)序列集操作時(shí)的工作量，另外為了在通過(guò)K個(gè)頂點(diǎn)生成K+1個(gè)頂點(diǎn)的過(guò)程中方便判斷某兩個(gè)頂點(diǎn)之間是否在當(dāng)前圖逆導(dǎo)出子圖中有邊相連，為了方便讀者理解，本文所有對(duì)極大完全子圖頂點(diǎn)集的存儲(chǔ)結(jié)構(gòu)圖示中，標(biāo)出的是頂點(diǎn)的名稱(chēng)而不是下標(biāo)。

2）圖G的每個(gè)逆導(dǎo)出子圖所對(duì)應(yīng)的極大完全子圖圖集的數(shù)據(jù)結(jié)構(gòu)

還是以圖G所對(duì)應(yīng)極大完全子圖為例，存儲(chǔ)結(jié)構(gòu)示意圖如下：

圖10 帶頭結(jié)點(diǎn)的Nset類(lèi)型空單鏈表

圖11 圖G的所有極大完全子圖存儲(chǔ)示意圖。

3）程序運(yùn)行結(jié)果

用鄰接矩陣存儲(chǔ)圖，使用該文的算法，得到圖G的所有極大完全子圖{ABD，AFG，AGH，ABHI，ADEF，BCD，BHI，HIJ}。

4 結(jié)論

本文對(duì)MaxcodeFMCG（Finding Maximal Complete Subgraph by Maxcode）算法進(jìn)行了研究，發(fā)現(xiàn)了幾個(gè)有意義的性質(zhì)和結(jié)論，如：性質(zhì) 2，結(jié)論1，結(jié)論2，并對(duì)其進(jìn)行論述或者證明，這為進(jìn)一步簡(jiǎn)化算法操作奠定了理論基礎(chǔ)。結(jié)合新的性質(zhì)和結(jié)論，對(duì)算法1中矩陣合并部分的操作進(jìn)行簡(jiǎn)化，簡(jiǎn)化了很多重復(fù)的操作，進(jìn)一步提高了整個(gè)算法的執(zhí)行效率。最后通過(guò)C語(yǔ)言實(shí)現(xiàn)了整個(gè)算法，成功的實(shí)現(xiàn)找出了任意圖的所有極大完全子圖。參考文獻(xiàn)：

[1] 康艷榮.基于圖結(jié)構(gòu)挖掘算法的研究與應(yīng)用[D].重慶：重慶大學(xué)，2005.

[2] Han J，Pei J，Yin Y.Ming frequent patterns without candidate generation[M].SIGMOD.2000

[3] 左孝凌，李為鑒，劉永才.離散數(shù)學(xué)[M].上海：上課科學(xué)技術(shù)文獻(xiàn)出版社，1982：271-328.

[4] 耿國(guó)華.數(shù)據(jù)結(jié)構(gòu)—用C語(yǔ)言描述（2011年版）[M].北京：高等教育出版社，2011：215-266.

[5] jiawei Han，Micheline Kamber. Data MiningConcepts and Techniques[M].2nd ed. morgan kaufmann publishers，2006：1-10.

[6] pang-Ning，Tan，Michael Steinbach，Vipin kumar. Introduction to Datamining. Addison Wesley，2005：146-181.

[7] Tan pang-Ning，Michael Steinbach，Vipin kumar. Introduction to Datamining[M]. Addison Wesley， 2005：146-181.

[8] 王珊，薩師煊.數(shù)據(jù)庫(kù)系統(tǒng)概論[M].4版.北京：高等教育出版社，2007：1-39.

[9] 李偉.頻繁子樹(shù)挖掘研究[D].秦皇島：燕山大學(xué)，2007.

[10] 董敏，湯建鋼.求解最大完全子圖的一種DNA算法[J].漢江大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，44（1）：20-23.

[10] 萬(wàn)市場(chǎng)，蘭紹玉.極大完全子圖在管理決策中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，1995，15（4）：29-31.

[11] 張良均，陳俊德，劉名軍，等.數(shù)據(jù)挖掘：實(shí)用案例分析[M].北京：機(jī)械工業(yè)出版社，2013：1-42.

[12] 楊仕博，賀燕琨，馬志新.一種基于極大完全子圖的最大頻繁項(xiàng)集并行挖掘算法[J].微電子學(xué)與計(jì)算機(jī)，2007，24（10）：29-35.