圖的結(jié)構(gòu)及應(yīng)用

數(shù)據(jù)收集從大量、不完整、噪聲、模糊和隨機(jī)數(shù)據(jù)中提取，并嵌入其中。人們事先不知道的，但潛在有用的信息和知識流程。這些數(shù)據(jù)可以是結(jié)構(gòu)化的,如關(guān)系數(shù)據(jù)庫中的數(shù)據(jù),也可以是半結(jié)構(gòu)化的,如文本、圖形、圖像數(shù)據(jù),甚至是分布在網(wǎng)絡(luò)上的異構(gòu)型數(shù)據(jù)。針對半結(jié)構(gòu)化數(shù)據(jù)的研究已經(jīng)成為近年來國內(nèi)外數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn),而目前國內(nèi)的研究熱點(diǎn)主要集中在文本數(shù)據(jù)挖掘等領(lǐng)域,針對圖的數(shù)據(jù)挖掘研究才剛剛開始。與一般的數(shù)據(jù)比較,圖能夠表達(dá)更加豐富的語義,在科學(xué)研究和許多商業(yè)領(lǐng)域有著更為廣泛的應(yīng)用。同時(shí),這種豐富的語義也增加了數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性和挖掘令人感興趣的圖的子結(jié)構(gòu)的難度。因此,需要綜合應(yīng)用圖論知識與數(shù)據(jù)挖掘的各種技術(shù)。本文主要對經(jīng)典的Apriori算法進(jìn)行改進(jìn),引入圖論知識,使之能夠?qū)τ蔁o向圖組成的數(shù)據(jù)庫進(jìn)行頻繁子圖的挖掘。1頻繁子圖挖掘算法框架圖的數(shù)據(jù)挖掘主要是從圖的數(shù)據(jù)庫中找到大于最小支持度的頻繁子圖。Apriori算法是從購物籃分析中引出的經(jīng)典數(shù)據(jù)挖掘算法,可以有效地從事務(wù)數(shù)據(jù)庫中挖掘出頻繁項(xiàng)集,但是由于圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu),原始的Apriori算法不能用于圖的數(shù)據(jù)挖掘。因此,有必要對Apriori進(jìn)行數(shù)據(jù)結(jié)構(gòu)和算法的改進(jìn),使得改進(jìn)后的算法適合于頻繁子圖的挖掘。頻繁子圖挖掘必須解決子圖同構(gòu)問題。直觀地說,子圖同構(gòu)即是確定圖G’是否為圖G的子圖。子圖同構(gòu)已經(jīng)被證明是一個(gè)NP完全問題,所以必須附加限制條件來減少搜索空間,降低算法的時(shí)間復(fù)雜度。1.1理論的子圖挖掘子圖同構(gòu):圖G’子圖同構(gòu)于圖G,當(dāng)且僅當(dāng)圖G中存在子圖G’’,使得G’’同構(gòu)于G’。導(dǎo)出子圖:記V(G),E(G)分別為圖G的頂點(diǎn)集和邊集,則G’是G的導(dǎo)出子圖當(dāng)且僅當(dāng)V(G’)?V(G),E(G’)?E(G)且對?u,v∈V(G’),{u,v}∈E(G)?{u,v}∈E(G’)。直觀地說,G的導(dǎo)出子圖G’的頂點(diǎn)集是G的頂點(diǎn)集的子集,而G’的邊集由原圖決定,即:G’中任意兩頂點(diǎn)之間是否有邊與G中相應(yīng)的兩頂點(diǎn)之間是否有邊一一對應(yīng)。本文中所提到的子圖挖掘均針對導(dǎo)出子圖。其中圖1(b)是(a)的導(dǎo)出子圖并且圖1(b)子圖同構(gòu)于(a),圖1(c)是(a)的一般子圖。在引入這兩個(gè)概念之后,還要對圖的所有頂點(diǎn)和邊注明標(biāo)記,以區(qū)分不同的頂點(diǎn)和邊,同時(shí)允許同一個(gè)圖中出現(xiàn)相同的頂點(diǎn)標(biāo)記和邊標(biāo)記。如在化學(xué)有機(jī)物分子結(jié)構(gòu)圖中經(jīng)常出現(xiàn)相同的碳原子C或氫原子H標(biāo)記。這樣,有了頂點(diǎn)標(biāo)記和邊標(biāo)記之后,就可以大大減少子圖匹配時(shí)的搜索空間,從而在一定程度上回避了關(guān)于子圖同構(gòu)的NP完全問題所帶來的困難。給定圖的數(shù)據(jù)庫D={G0,G1,…,Gn},導(dǎo)出子圖G的支持度定義如下:而所謂頻繁導(dǎo)出子圖就是支持度大于指定的最小支持度min＿sup的導(dǎo)出子圖。另外,記size(G)表示圖G中頂點(diǎn)的個(gè)數(shù),這在后面的算法描述中將被用到。1.2基于規(guī)范矩陣的編碼無向圖的數(shù)據(jù)結(jié)構(gòu)定義采用鄰接矩陣表示法,為了提高算法的效率,根據(jù)對稱性,只保留鄰接矩陣的下三角陣。這樣無向圖G的鄰接矩陣元素xij定義如下:即對角線元素為頂點(diǎn)標(biāo)記,下三角陣其余元素為邊標(biāo)記或0(當(dāng)邊不存在時(shí))。同時(shí)規(guī)定,頂點(diǎn)標(biāo)記按詞典有序。這樣,圖1(a)的鄰接矩陣表示就如圖2所示(本文提到的鄰接矩陣的組成元素均為字符)?？梢?即使規(guī)定頂點(diǎn)標(biāo)記按詞典有序,由于允許出現(xiàn)相同的標(biāo)記,因此不能保證鄰接矩陣的唯一性。為此,本文引入規(guī)范矩陣的概念,使得該矩陣能夠與圖形成一一對應(yīng)關(guān)系。首先,對符合以上定義的鄰接矩陣X進(jìn)行如下方式的編碼:則規(guī)范矩陣定義為:當(dāng)圖G只有一個(gè)鄰接矩陣描述時(shí),該鄰接矩陣就是圖G的規(guī)范矩陣;當(dāng)圖G存在多個(gè)鄰接矩陣描述時(shí),取Code值最大的鄰接矩陣作為圖G的規(guī)范矩陣。Code值的大小比較遵循詞典有序規(guī)則,其中a>b>…>z>0。如圖2的兩個(gè)鄰接矩陣記為M1和M2,則它們的Code值分別為:因?yàn)镃ode(M1)>Code(M2),所以取M1作為圖1(a)的規(guī)范矩陣。1.3u3000jb3-3-k-項(xiàng)頻繁導(dǎo)數(shù)子圖Apriori算法利用候選集尋找頻繁項(xiàng)集。候選集的產(chǎn)生采用自底向上的思想,由頻繁k-項(xiàng)集產(chǎn)生候選k+1-項(xiàng)集,主要由兩步組成:連接步和剪枝步。其中,利用了Apriori性質(zhì)來壓縮搜索空間。所謂Apriori性質(zhì),即頻繁項(xiàng)集的所有非空子集都必須也是頻繁的。擴(kuò)展到圖的數(shù)據(jù)庫中,即頻繁導(dǎo)出子圖的所有非空導(dǎo)出子圖都必須也是頻繁的。以下具體說明改進(jìn)后的連接步和剪枝步以及計(jì)算候選子圖支持度的方法。(1)連接步:設(shè)矩陣Xk和Yk分別是含k個(gè)頂點(diǎn)的頻繁導(dǎo)出子圖對應(yīng)的規(guī)范矩陣,其中,則可以連接它們產(chǎn)生k+1個(gè)頂點(diǎn)的候選導(dǎo)出子圖所對應(yīng)的矩陣Zk+1,其中,xT和yT是(k-1)維行向量。zk+1,k的值由頂點(diǎn)標(biāo)記xkk和ykk之間是否存在邊來確定,這有兩種可能。有關(guān)文獻(xiàn)的方法是:將這兩種可能都直接加以肯定。而本文對此作了進(jìn)一步的改進(jìn)。本文確定zk+1,k的值的方法如下:如果頂點(diǎn)標(biāo)記xkk和ykk之間不存在邊,則zk+1,k取0,連接結(jié)果只有一個(gè);如果存在邊,則zk+1,k就等于該邊的邊標(biāo)記,同時(shí)也保留zk+1,k=0的情況,即連接結(jié)果有2個(gè)。另外,如果Zk+1對應(yīng)的子圖是頻繁的,則由Apriori性質(zhì),它所有的導(dǎo)出子圖也必須是頻繁的,所以如果xkk和ykk之間存在邊,則該邊一定是頻繁的,從而其必被包含在2-項(xiàng)頻繁導(dǎo)出子圖集合之中。由此,邊標(biāo)記的具體值可以通過掃描2-項(xiàng)頻繁導(dǎo)出子圖集來得到。圖3是一個(gè)具體的連接實(shí)例。其中圖3(c)中bc之間是否存在邊由頻繁2-項(xiàng)集決定。通過連接操作得到的矩陣Zk+1可能不再是規(guī)范矩陣,因此要將其調(diào)整為規(guī)范矩陣。(2)剪枝步:剪枝主要是為了減少候選空間,即考察Zk+1是否應(yīng)該作為頻繁導(dǎo)出子圖候選。同樣要用到Apriori性質(zhì),考察Zk+1的所有k-項(xiàng)子集Zk(Zk需要被調(diào)整為規(guī)范矩陣),當(dāng)且僅當(dāng)所有這樣的Zk都屬于k-項(xiàng)頻繁導(dǎo)出子圖集合時(shí),就把Zk+1添加到k+1-項(xiàng)頻繁導(dǎo)出子圖候選集合中。(3)計(jì)算Zk+1支持度:在k+1-項(xiàng)頻繁導(dǎo)出子圖候選集合產(chǎn)生后,就要通過掃描數(shù)據(jù)庫,計(jì)算其中每一個(gè)候選Zk+1的支持度,來決定它是否是頻繁導(dǎo)出子圖。當(dāng)Zk+1與數(shù)據(jù)庫中某一事務(wù)G的子圖G’的頂點(diǎn)標(biāo)記和邊標(biāo)記一一對應(yīng)時(shí),就將該候選的計(jì)數(shù)值增加1。在全部掃描完成后,將候選計(jì)數(shù)值除以數(shù)據(jù)庫事務(wù)總個(gè)數(shù)就得到該候選的支持度,如果該支持度大于指定的最小支持度,則將Zk+1添加到k+1-項(xiàng)頻繁導(dǎo)出子圖集合中。在算法的實(shí)際實(shí)現(xiàn)中,是首先將最小支持度與事務(wù)總個(gè)數(shù)相乘得到一個(gè)最小計(jì)數(shù)值,而每一個(gè)Zk+1的計(jì)數(shù)值只需和這個(gè)最小計(jì)數(shù)值相比較即可。2chl1lk-12輸入:以規(guī)范矩陣形式描述的圖的數(shù)據(jù)庫D={M1,M2,…,Mn}和最小支持度min＿sup。輸出:頻繁導(dǎo)出子圖集合L。主算法基本和Apriori算法相同,參見文獻(xiàn),需要改變的是第一步掃描數(shù)據(jù)庫時(shí)不僅要產(chǎn)生頻繁1-項(xiàng)集L1,而且要產(chǎn)生頻繁2-項(xiàng)集L2,而循環(huán)則從尋找頻繁3-項(xiàng)集開始。以下給出關(guān)鍵子程序算法的完整描述。(1)產(chǎn)生k-項(xiàng)頻繁導(dǎo)出子圖候選集Ck的子程序:1)foreachl1∈Lk-12)foreachl2∈Lk-1//頻繁k-1項(xiàng)集Lk-1中任意不同的//兩項(xiàng)僅連接1次,以避免重復(fù)連接3){5){6)掃描頻繁2-項(xiàng)集L2,確定頂點(diǎn)標(biāo)記為l1[k-1][k-1]和l2[k-1][k-1]的兩頂點(diǎn)之間是否存在邊標(biāo)記。若不存在,連接l1和l2,得到候選c1,其中c1[k][k-1]=0,其它元素由l1和l2確定;若存在邊標(biāo)記p,連接l1和l2,得到候選c1和c2,其中c1[k][k-1]=0,c2[k][k-1]=p,c1,c2的其它元素由l1和l2確定;7)調(diào)整步驟6)所產(chǎn)生的c1或者c1和c2為規(guī)范矩陣;8)對每一個(gè)c1或c2(當(dāng)c2存在時(shí))的k-1項(xiàng)子集s//剪枝過程9){10)調(diào)整s為規(guī)范矩陣;11)if(s不屬于Lk-1)12)刪除c1或c2,goto2;13)}14)添加c1或c2到Ck中;15)}//endif16)}(2)判斷矩陣c是否被t所包含(子圖同構(gòu))的子程序:1)x=c,n1=size(c),n2=size(t);//n1,n2是頂點(diǎn)個(gè)數(shù)(即行數(shù)或//列數(shù))2)遍歷t的對角線元素3)if(存在t[k][k]=x)goto5);4)returnFALSE;//判斷頂點(diǎn)標(biāo)記和邊標(biāo)記是否相同7)returnTRUE;8)elsereturnFALSE;3實(shí)驗(yàn)結(jié)果及分析本文中,算法性能的驗(yàn)證是通過對一個(gè)小型數(shù)據(jù)庫進(jìn)行仿真實(shí)驗(yàn)而得到的。該數(shù)據(jù)庫中的每個(gè)圖元素均以規(guī)范矩陣形式存儲,包含300個(gè)隨機(jī)數(shù)據(jù),每個(gè)數(shù)據(jù)最大頂點(diǎn)個(gè)數(shù)為10,最大邊個(gè)數(shù)為20。庫中頂點(diǎn)標(biāo)記和邊標(biāo)記的總個(gè)數(shù)都為100。實(shí)驗(yàn)環(huán)境為:奔騰Ⅲ1GHz處理器,128MB內(nèi)存,Windows2000操作系統(tǒng)。參數(shù)設(shè)置和實(shí)驗(yàn)結(jié)果如表1所示。其中,運(yùn)行時(shí)間和內(nèi)存消耗保留到小數(shù)點(diǎn)后1位。從表1中可以看出,當(dāng)支持度較小的時(shí)候,算法的運(yùn)行時(shí)間和內(nèi)存消耗隨著支持度的減小而急劇增加,近似于指數(shù)級的變化趨勢。4研究局限及建議本文用鄰接矩陣表示圖,以經(jīng)典的Apriori算法為基礎(chǔ),并且通過對其關(guān)鍵步驟:連接步和剪枝步的改進(jìn),得到頻繁導(dǎo)出子圖的候選集。同時(shí),提出了一種解決子圖同構(gòu)問題的算法,利用該算法來計(jì)算每一個(gè)候選的支持度。從而,得到了一種能夠有效地進(jìn)行頻繁導(dǎo)出子圖挖掘的方法。本研究仍存在需要改進(jìn)的地方:首先,本文的算法還只能處理無向圖,需要繼續(xù)研究能夠處理有向圖的方法;其次,大量的候選集的產(chǎn)生是算法執(zhí)行效率的瓶頸之一,因此應(yīng)該繼續(xù)研究減少候選集甚至不產(chǎn)生候選集的適應(yīng)于圖的數(shù)據(jù)挖掘的方法;最后,從算法的性能分析可以看出:當(dāng)最小支持度較小時(shí),算法的效率劇降,并挖掘出了一個(gè)很大的頻繁導(dǎo)出子圖集,然而有些頻繁導(dǎo)出子圖的實(shí)際意義不大,例如單個(gè)頂點(diǎn)標(biāo)記。所以在以后的