一種基于特征子圖的不確定圖分類算法

劉 意，王 勇＊，尚學群

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

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

1 構造特征子圖

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

1．1 挖掘頻繁子圖

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

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

假設不確定圖的各個邊是獨立的，一個不確定圖G包含某個確定圖G的概率為

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

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

其中

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

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

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

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

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

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

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

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

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

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

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

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

1．2 構造特征子圖

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

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

給定最小支持度比min＿p，當P（fre＿g，D，D1）≥min＿p，認為fre＿g為特征子圖，記為fea＿g．

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

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

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

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

與確定圖不同，不確定圖蘊含某個子圖是以一定概率存在的，在利用特征子圖對不確定圖分類的過程中，需要將概率考慮進去，即在文獻［2］利用特征子圖構造模型的基礎上，增加概率作為權重．

對于一個待判斷的不確定圖G，進行如下操作：

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

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

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

3 實驗結果與分析

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

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

通過實驗觀察，實驗結果的準確率是由最小支持度min＿sup和最小支持度比min＿p來控制的，且在本實驗中主要由min＿sup控制，這和實驗數(shù)據的特點有關．

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

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

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

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

4 結語

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

［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］．計算機研究與發(fā)展，2007，44（7）：1169－1176．

［3］王桂娟，印鑒，詹衛(wèi)許．一種新的基于嵌入集的圖分類方法［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］肖港松，陳曉云．基于代價敏感的圖分類算法［J］．福州大學學報：自然科學版，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］．計算機科學與應用，2011，47（10）：113－117．

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

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