劉 意，王 勇＊，尚學(xué)群

（1西北工業(yè)大學(xué) 理學(xué)院；2西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安710072）

圖分類在化學(xué)、生物信息學(xué)、計(jì)算機(jī)科學(xué)等許多領(lǐng)域都有重要的研究和應(yīng)用價(jià)值．例如，在生物和化學(xué)領(lǐng)域判斷一種化合物是否有毒就是很常見的實(shí)例，其中分子化合物中原子構(gòu)成圖的頂點(diǎn)，原子鍵構(gòu)成圖的邊，從大量有毒的分子化合物結(jié)構(gòu)圖中尋找頻繁子圖，這樣的子圖可以用來判斷其他分子化合物是否有毒．目前，圖分類的方法主要包括基于頻繁子圖的分類方法［1－4］和基于圖核函數(shù)的分類方法［5－6］，它們在一定程度上解決了圖分類問題．然而由于硬件條件、人為原因和環(huán)境等因素的影響，圖結(jié)構(gòu)中存在大量的不確定性，不確定圖不同節(jié)點(diǎn)之間的聯(lián)系是以一定概率存在的，因此不能簡單地采用以往的分類方法來處理不確定圖分類．而現(xiàn)實(shí)中的應(yīng)用對不確定圖的分類提出需求，例如，人類大腦不同區(qū)域功能之間聯(lián)系就存在不確定性，通過對大腦區(qū)域結(jié)構(gòu)圖的分類，可以判斷人是否患有某種腦部疾病，因此研究不確定圖分類是很有必要的．基于上述原因，研究不確定圖分類算法，這種算法也適用于確定圖分類（確定圖是特殊的不確定圖）．先根據(jù)頻繁子圖構(gòu)造特征子圖［7］，然后由特征子圖產(chǎn)生分類規(guī)則．本文在文獻(xiàn)［2］構(gòu)造分類模型的基礎(chǔ)上，考慮不確定圖的特點(diǎn)，采用以蘊(yùn)含子圖概率作為權(quán)重的方法，使分類模型可以適用于不確定圖分類，同時(shí)提出AGF（Apriori for Graph Frequent Sets）頻繁子圖挖掘算法，將頻繁子圖挖掘問題轉(zhuǎn)換為頻繁項(xiàng)集挖掘問題，可以高效地發(fā)掘頻繁子圖．

1 構(gòu)造特征子圖

本文研究不確定圖分類問題．算法的步驟是：首先采用AGF算法挖掘頻繁子圖，再從頻繁子圖集中篩選特征子圖，最后通過特征子圖生成分類規(guī)則．

1．1 挖掘頻繁子圖

在給出頻繁子圖挖掘算法之前，先通過定義引出子圖期望支持度的計(jì)算公式．

定義1（不確定圖） 一個(gè)不確定圖G＝（V，E，p），其中V＝ ｛v1，v2，…vn｝表示頂點(diǎn)集，E?V×V表示邊集，p：E→ （0，1］表示邊上的概率．相應(yīng)的，確定圖表示為G＝（V，E）．不確定圖集合表示為D＝｛G1，G2，…Gn｝，D可以分為D＋和D－，分別為不確定圖的正例和負(fù)例集合．

假設(shè)不確定圖的各個(gè)邊是獨(dú)立的，一個(gè)不確定圖G包含某個(gè)確定圖G的概率為

定義2（子圖） 子圖g＝ （V′，E′）為某個(gè)確定圖G＝（V，E）的子圖當(dāng)且僅當(dāng)V′?V且E′?E，記為g?G．通常情況下，子圖是針對確定圖而言的概念．

對于不確定圖，g為G的子圖用概率表示為

其中

可以計(jì)算出子圖g在不確定圖集合D中的期望支持度：

公式（2）可以用來計(jì)算子圖的期望支持度．給定最小支持度min＿sup，當(dāng)子圖g滿足exp（g?D）＞min＿sup，則g為頻繁子圖，記為fre＿g．

定理1 給定不確定圖集合D，子圖在D中的期望支持度滿足Apriori性質(zhì)，即對任意的子圖g和g′，若g是g′的子圖，那么exp（g?D）≥exp（g′?D）．

以定理1為理論依據(jù)，挖掘頻繁子圖可以采用Apriori算法中的剪枝方法．

由于子圖的連接方式有很多種，候選子圖產(chǎn)生問題一直是頻繁子圖挖掘的難點(diǎn)．近年來，有關(guān)頻繁子圖挖掘算法一直將注意力集中在如何有效地生成候選子圖［8－10］．將頻繁子圖的挖掘轉(zhuǎn)換為頻繁項(xiàng)集的挖掘，可以簡化繁瑣的過程，從而節(jié)省時(shí)間．

下面介紹AGF算法．假設(shè)每個(gè)不確定圖擁有相同的頂點(diǎn)及頂點(diǎn)標(biāo)號，也就是說，不同的不確定圖的差異在于兩個(gè)頂點(diǎn)之間的邊存在性以及存在的概率．這樣的假設(shè)是有意義的，比如對人腦結(jié)構(gòu)的分析，每個(gè)人的腦結(jié)構(gòu)都是一樣的，而人腦不同部分之間的聯(lián)系是不確定的．

通過對圖的頂點(diǎn)個(gè)數(shù)和標(biāo)號的限定，把頻繁子圖挖掘轉(zhuǎn)化為傳統(tǒng)的頻繁項(xiàng)集的挖掘，具體做法如下：對于每一個(gè)不確定圖（圖1），可以用其鄰接矩陣來表示．這樣，每個(gè)邊就用兩個(gè)點(diǎn)表示，進(jìn)而每個(gè)子圖可以用字符串表示．下面舉例說明字符串的表示：圖1中，v0v1表示邊e1（下標(biāo)由小到大），e1e2e3表示整個(gè)不確定圖（下標(biāo)由小到大），從而v0v1v0v2v2v3也表示整個(gè)圖．這樣，每個(gè)圖以及每個(gè)子圖，采用上

圖1 某不確定圖Fig．1 An uncertain graph

在使用Apriori算法時(shí)，有一點(diǎn)需要注意，由于子圖都是聯(lián)通的，所以，在計(jì)算頻繁二項(xiàng)集時(shí)，需要簡單的處理：兩個(gè)頻繁一項(xiàng)集合并時(shí)，必須有公共頂點(diǎn)．比如v0v1和v2v3就不能合并．可以發(fā)現(xiàn)，僅僅在處理二項(xiàng)集時(shí)，才需要這樣的處理．把不確定圖集合D＋和D－中的頻繁子圖集合記為F＋和F－．

以正例集合為例，具體算法如下：

輸入：D＋／／由帶有頂點(diǎn)標(biāo)號的圖數(shù)據(jù)集合正例轉(zhuǎn)換來的字符串；min＿sup／／最小支持度

輸出：F＋／／正例頻繁圖數(shù)據(jù)集合

1．2 構(gòu)造特征子圖

并不是每個(gè)頻繁子圖對分類都有意義，比如當(dāng)某個(gè)子圖g在兩個(gè)不確定圖集合中都頻繁但支持度相差很小，那么它的支持度比就很小，認(rèn)為它不是特征子圖．

定義3（特征子圖） 對于D中的某個(gè)頻繁子圖fre＿g，其支持度為sup1，fre＿g在另一個(gè)不確定圖集合1中的支持度為sup 2．可以計(jì)算支持度比：

給定最小支持度比min＿p，當(dāng)P（fre＿g，D，D1）≥min＿p，認(rèn)為fre＿g為特征子圖，記為fea＿g．

構(gòu)造特征子圖就是對頻繁子圖正例集合F＋和負(fù)例集合F－的篩選，去除其中的非特征子圖，從而得到特征子圖集合．分別記為F＋和F－．

需要注意的是，存在這樣一種可能，對于一個(gè)被測不確定圖G，某個(gè)特征子圖的真子集仍然是特征子圖．那么在利用特征子圖分類時(shí)，這個(gè)子集作為分類特征的意義不大，應(yīng)該篩選掉．即對于被測圖G，g1和g2都是特征子圖，若g1?g2，篩選掉g1．

2 具體分類實(shí)現(xiàn)

學(xué)習(xí)步．對于不確定圖集合D＋和D－，首先通過AGF算法分別得到頻繁子圖集合F＋和F－，再由公式（3）和最小支持度比篩選出特征子圖集合F＋和F－．

與確定圖不同，不確定圖蘊(yùn)含某個(gè)子圖是以一定概率存在的，在利用特征子圖對不確定圖分類的過程中，需要將概率考慮進(jìn)去，即在文獻(xiàn)［2］利用特征子圖構(gòu)造模型的基礎(chǔ)上，增加概率作為權(quán)重．

對于一個(gè)待判斷的不確定圖G，進(jìn)行如下操作：

步驟1 分別對F＋和F－中的每個(gè)成員fea＿gi與待判斷圖G做子圖匹配，對于不確定圖來說，蘊(yùn)含某個(gè)子圖的概率可以利用公式（1）計(jì)算得到P（fea＿gi?G）．

步驟2 由公式（3）可知，當(dāng)正例集合D1中的某個(gè)特征子圖fea＿gi在負(fù)例集合D2中越頻繁，則P（fea＿gi，D1，D2）越 小，在D2中越不頻繁，則P（fea＿gi，D1，D2）越大，即特征越明顯．對不確定圖G，計(jì)算得分?jǐn)?shù)s．

步驟3 根據(jù)得分?jǐn)?shù)s，對G分類．如果s＞0，不確定圖G歸為D1；否則，不確定圖G歸為D2．

3 實(shí)驗(yàn)結(jié)果與分析

數(shù)據(jù)集來自于LONI網(wǎng)站的對老年癡呆患者大腦結(jié)構(gòu)的觀察，可以從相關(guān)網(wǎng)站（http∥adni．loni．ucla．edu）申請得到．?dāng)?shù)據(jù)集分為正例和負(fù)例兩類，正例為老年癡呆患者的腦部結(jié)構(gòu)圖，負(fù)例為正常人的腦部結(jié)構(gòu)圖，每類各200個(gè)實(shí)例，其中100個(gè)用來學(xué)習(xí)，100個(gè)用來測試．如圖2所示，兩個(gè)圖分別表示正例和負(fù)例的大腦結(jié)構(gòu)區(qū)域聯(lián)系圖，其中點(diǎn)代表大腦結(jié)構(gòu)中的各個(gè)區(qū)域，加權(quán)邊代表各個(gè)區(qū)域以一定的概率存在相互的聯(lián)系．不同的實(shí)例具有相同的頂點(diǎn)個(gè)數(shù)以及頂點(diǎn)位置，這也正好符合前面做的假設(shè)．在實(shí)驗(yàn)開始前需要用鄰接矩陣表示結(jié)構(gòu)圖．

圖2 老年癡呆患者和正常人的腦部結(jié)構(gòu)圖Fig．2 An example figure of an Alzheimer patient and a healthy people

通過實(shí)驗(yàn)觀察，實(shí)驗(yàn)結(jié)果的準(zhǔn)確率是由最小支持度min＿sup和最小支持度比min＿p來控制的，且在本實(shí)驗(yàn)中主要由min＿sup控制，這和實(shí)驗(yàn)數(shù)據(jù)的特點(diǎn)有關(guān)．

圖3 最小支持度與分類正確率關(guān)系圖Fig．3 The diagram of the smallest support and the accuracy of classification

圖3和圖4都可以說明在min＿sup設(shè)置合適時(shí)，比如0．8，該算法具有良好的分類正確率．當(dāng)min＿sup取值過大，會(huì)因?yàn)檫^濾掉許多本身具有良好分類能力的子圖而影響分類能力，當(dāng)min＿sup取值過小，則影響算法的效率．從圖3可以看出，當(dāng)min＿sup＝0．95時(shí)，正確率非常低，而隨著min＿sup的減小，正確率迅速增高并且在min＿sup＝0．8后趨于平緩，其后基本穩(wěn)定在90%以上．當(dāng)min＿sup低于0．5后，實(shí)驗(yàn)不予考慮，因?yàn)橐呀?jīng)不屬于頻繁子圖的范疇．從圖4也同樣可以看出，隨著min＿sup的

圖4 最小支持度與平均得分的關(guān)系圖Fig．4 The diagram of the smallest support and the score

逐漸降低，正例平均得分逐漸增高且在min＿sup＝0．8后趨于平緩，負(fù)例平均得分逐漸降低且在min＿sup＝0．8后趨于平緩，隨著min＿sup的降低，二者得分之差越來越大，可以理解為算法將正負(fù)例區(qū)分的越來越明顯．

4 結(jié)語

研究了一種新的頻繁子圖挖掘算法——AGF算法．通過論證該算法具有高效性，同時(shí)也具有局限性，即研究對象必須為同構(gòu)圖．在利用AGF算法高效生成頻繁子圖的前提下，提出針對不確定圖的分類算法．通過對實(shí)驗(yàn)結(jié)果的觀察及分析，可以得出：在最小支持度min＿sup和最小支持度比min＿p設(shè)置合適的情況下，算法對不確定圖具有良好的分類能力．

［1］Deshpande M，Kuramochi M，Karypis G．Frequent substructure based approaches for classifying chemical compounds［J］．IEEE Transactions on Knowledge and Data Engineering，2005，17（8）：1036－1050．

［2］劉勇，李建中，朱敬華．一種新的基于頻繁閉顯露模式的圖分類方法［J］．計(jì)算機(jī)研究與發(fā)展，2007，44（7）：1169－1176．

［3］王桂娟，印鑒，詹衛(wèi)許．一種新的基于嵌入集的圖分類方法［J］．計(jì)算機(jī)研究與發(fā)展，2012，49（11）：2311－2319．

［4］Liu Yang，Wu Bin，Wang Hongxu．BPGM：A big graph mining tool［J］．Tsinghua Science and Technology，2014，19（1）：33－38．

［5］Horvath T，Garner T，Wrobel S．Cyclic pattern kernels for predictive graph mining［C］／／Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining．Seattle：Association for Computing Machinery，2004：158－167．

［6］肖港松，陳曉云．基于代價(jià)敏感的圖分類算法［J］．福州大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，40（3）：316－321．

［7］Cheng Hong，Yan Xifeng，Han Jiawei．Discriminative frequent pattern analysis for effective classification［C］／／IEEE 23rd International Conference on Data Enginering．Istanbul：IEEE Computer Society，2007：716－725．

［8］陳立寧，羅可．Apriori算法用于頻繁子圖挖掘的改進(jìn)方法［J］．計(jì)算機(jī)科學(xué)與應(yīng)用，2011，47（10）：113－117．

［9］高琳，楊建業(yè)，覃桂敏．動(dòng)態(tài)網(wǎng)絡(luò)模式挖掘方法及其應(yīng)用［J］．軟件學(xué)報(bào)，2013，24（9）：2042－2061．

［10］鄒兆年，李建中，高宏．從不確定圖中挖掘頻繁子圖模式［J］．軟件學(xué)報(bào)，2009，20（11）：2965－2976．