李程文　劉波

摘要：如今，圖數(shù)據(jù)分類變得越來越重要。最近幾十年對它的研究也越來越多，并且得到了廣泛應(yīng)用。傳統(tǒng)的圖數(shù)據(jù)分類研究主要集中在單標簽集，然而在很多應(yīng)用中，每個圖數(shù)據(jù)都會同時具有多個標簽集。這篇文章研究了關(guān)于圖數(shù)據(jù)的多標簽特征提取問題，并提出基于模糊測量函數(shù)的多標簽圖數(shù)據(jù)特征提取算法，用于搜索最優(yōu)子圖集。算法采用模糊測量函數(shù)作為評估標準評估子圖特征的重要性，然后通過邊枝界定算法修剪子圖搜索空間有效地搜索最優(yōu)子圖特征。實驗證明，該方法在現(xiàn)實應(yīng)用中有較高的精度。

關(guān)鍵詞：圖數(shù)據(jù)；模糊測量；多標簽；特征選取；邊枝界定

1.多標簽圖數(shù)據(jù)分類研究背景

傳統(tǒng)分類方法主要研究單標簽分類問題，使用的數(shù)據(jù)樣本只擁有單個標簽，如C4.5，SVM，K近鄰算法等。然而在許多實際問題中，樣本數(shù)據(jù)可能擁有多個標簽。多標簽分類就是針對多標簽數(shù)據(jù)的特點，利用數(shù)據(jù)的多個標簽獲取相應(yīng)的數(shù)學模型，并依此將一個實例準確地劃分到某一個類別中。多標簽分類算法廣泛地應(yīng)用于醫(yī)療診斷、音樂分類和場景分類中，在這些分類中每一個輸入數(shù)據(jù)樣本都擁有多個標簽。就像音樂分類系統(tǒng)，一首音樂可能同時屬于多個標簽，如古典音樂，輕音樂，流行音樂，爵士樂，鋼琴曲。對于多標簽數(shù)據(jù)，傳統(tǒng)的單標簽分類方法已無法滿足需求。

圖是一種最常用的數(shù)據(jù)結(jié)構(gòu)之一，用于表示事物之間復(fù)雜的關(guān)系。圖廣泛地應(yīng)用于很多分類領(lǐng)域，用于表示復(fù)雜結(jié)構(gòu)的物體。如文件分類和在線產(chǎn)品推薦。同時，圖數(shù)據(jù)的復(fù)雜性也成為研究中的難點。一個有效的圖數(shù)據(jù)應(yīng)該能夠提取或者找出這些圖的一個適當?shù)奶卣髯蛹杂糜诜治龌蛘哳A(yù)測。在現(xiàn)實應(yīng)用中，訓(xùn)練圖集的子圖特征數(shù)量也許會呈指數(shù)倍增長，這些數(shù)據(jù)中包含大量的冗余數(shù)據(jù)和錯誤數(shù)據(jù)。所以多標簽分類方法都將依賴于特征篩選程序以選擇最重要的子圖用來分類。

多標簽圖數(shù)據(jù)分類的一個基本挑戰(zhàn)是確定訓(xùn)練圖集的最優(yōu)特征子圖。圖分類問題已經(jīng)得到了廣泛的研究。傳統(tǒng)方法把主要研究方向放在單標簽分類問題（二分類）上，它明確或模糊地假設(shè)每一個圖只有一個標簽。對于單標簽分類問題，傳統(tǒng)圖數(shù)據(jù)挖掘方法可以擴展并用于找出單標簽圖數(shù)據(jù)集中的一個最具價值的子圖特征。但是在多標簽分類問題上，每一個圖擁有多個標簽，多個特征子圖集需要挖掘。

特征選取就是根據(jù)某種評估標準，從原始的特征空間中選取最優(yōu)的特征子圖集，代替原始數(shù)據(jù)用于分類。評估標準在特征選取中起著至關(guān)重要的作用，因為他直接決定特征選取算法的性能和分類模型的準確率。目前，特征提取算法中的評估標準主要有距離準則、一致性準則、分類誤差準則、信息準則和關(guān)聯(lián)評估準則等。其中關(guān)聯(lián)評估準則是一種應(yīng)用廣泛的評估準則，因為它能很好地度量特征之間的關(guān)聯(lián)性。雖然特征提取算法在傳統(tǒng)分類算法中得到了廣泛應(yīng)用，但在多標簽圖數(shù)據(jù)學習中并沒有得到很好的應(yīng)用。事實上，多標簽圖數(shù)據(jù)中包含大量冗余信息和分類信息量低的數(shù)據(jù)。因此，評估標準對于多標簽圖數(shù)據(jù)分類算法意義重大。

在這篇文章里，人們提出了一種全新的多標簽分類框架。這個方法被稱為基于模糊測量函數(shù)的多標簽圖數(shù)據(jù)特征提取。首先，利用基于模糊測量函數(shù)的特征子集評估標準評估特征子集，用于選取最優(yōu)的特征子圖。為了避免詳細地列舉所有的子圖特征，這里使用一種名flqgSpan的邊枝界定算法”，通過修剪子圖搜索空間有效的搜索最優(yōu)的子圖特征。實驗證明，特征選取算法對多標簽分類性能有顯著提高。

2.相關(guān)工作

由于關(guān)注的是基于圖數(shù)據(jù)的多標簽特征子圖的挖掘，首先回顧多標簽數(shù)據(jù)分類和子圖特征挖掘。

2.1多標簽數(shù)據(jù)分類

多標簽學習算法用于處理每一個實例都同時具有多種不同的標簽的數(shù)據(jù)。到目前為止主要有5種多標簽學習算法，即數(shù)據(jù)分解策略、算法延伸策略、混合策略、整體策略和標簽編碼策略。

數(shù)據(jù)分解策略主要是通過不同的分解技巧將多標簽數(shù)據(jù)分解成一個或多個單標簽數(shù)據(jù)集。如x～多（One VersusRest，OVR），二元關(guān)聯(lián)（Binary Relevance，BR），標簽冪集（Label Powerset，LP）。由于存在各種各樣的單標簽分類器和免費軟件，如二分類支持向量機OVR_SVM，可以非常方便地實現(xiàn)一個數(shù)據(jù)分解算法。數(shù)據(jù)延伸策略是同時考慮訓(xùn)練數(shù)據(jù)的全部標簽信息，延伸一個多類算法以處理多標簽數(shù)據(jù)集。這種類型的算法有，多標簽支持向量機（Rank-SVM），多標簽核向量機（Rank-CVM），多標簽神經(jīng)網(wǎng)絡(luò)（BP-MLL），但是這些算法需要解決復(fù)雜的最優(yōu)化問題。混合策略使用現(xiàn)有的單標簽分類方法，并且還明確地或者模糊地將多標簽數(shù)據(jù)集分解成一系列的子集。本質(zhì)上這些算法是通過稍微犧牲分類性能以減少運算量。典型的方法有多標簽K近鄰算法（ML-kNN），延伸后的支持向量機（OVR-ESVM）。整體策略是延伸一個現(xiàn)有的多標簽整體分類算法或者實現(xiàn)一個整合上述三種多標簽分類方法的算法?；谥腁daBoosting算法構(gòu)建了兩種不同的整體策略架構(gòu)，AdaBoost.MH和AdaBoost.MR。新的整體策略算法包括整體分類鏈算法（Entire Classification Chain，ECC），隨機K標簽集方法（RAkEL），預(yù)測聚類樹的隨機森林法（RF-PCT）。標簽編碼策略將二進制標簽向量轉(zhuǎn)化為離散的密碼詞和真正密碼詞，通過分類算法和回歸模型以預(yù)測新實例的密碼詞，并且通過得到的有噪音的密碼詞還原二進制標簽向量。有兩種實現(xiàn)方法：標簽擴展和壓縮編碼。這兩種方法的區(qū)別在于得到的編碼詞是否比原二進制標簽向量長。值得注意的是二進制標簽向量和離散密碼詞分類性能相似，真實編碼詞分類性能較差。

2.2圖數(shù)據(jù)挖掘

長期以來，圖數(shù)據(jù)挖掘問題在機器學習領(lǐng)域得到了廣泛關(guān)注。圖數(shù)據(jù)挖掘問題主要包括圖的匹配、圖數(shù)據(jù)中的關(guān)鍵字查詢、頻繁子圖挖掘、聚類以及分類等。其中頻繁子圖挖掘算法主要研究關(guān)于如何從圖數(shù)據(jù)中提取最具信息價值的子圖特征信息。常見的頻繁子圖挖掘算法可以分為4類：基于Apriori的算法、基于模式增長的算法、基于模式增長和模式歸約算法和基于最小描述長度的近似算法?；贏priori的頻繁子圖挖掘算法包括基于Apriori算法的圖挖掘（Apriori-based Graph Mining，AGM）、Frequert子圖發(fā)現(xiàn)（FrequertSubgraph Discovery，F(xiàn)SG）、路徑連接算法等?；谀Ｊ皆鲩L的頻繁結(jié)構(gòu)挖掘算法，包括gSpan，快速頻繁子圖挖掘（Fast Frequent Subgraph Mining，F(xiàn)FSM）、CloseGraph等?；谀Ｊ皆鲩L和模式歸約的精確稠密頻繁子結(jié)構(gòu)挖掘算法，包括CloseCut及Splat等。基于最小描述長度的近似頻繁子結(jié)構(gòu)挖掘算法，包括SUBDUE等。gSpan算法是一種由Yan～Han提出的基于深度優(yōu)先搜索算法及最右路徑擴展技術(shù)生成頻繁子圖的算法。

盡管多標簽圖數(shù)據(jù)分類算法得到了廣泛的研究，但將模糊理論用于多標簽圖數(shù)據(jù)子圖特征挖掘的研究相對較少。該算法引進模糊測量方法，根據(jù)子圖和母圖之間的隸屬度關(guān)系，建立隸屬度函數(shù)，然后通過隸屬度函數(shù)評估子圖的重要性。為了避免詳細地列舉所有的子圖特征，使用頻繁子圖挖掘算法gSpan，通過修剪子圖搜索空間有效地搜索最優(yōu)的子圖特征。

3.基于模糊適應(yīng)度函數(shù)的圖分類多標簽特征選取

這一節(jié)將詳細介紹本文提出的基于模糊測量函數(shù)的多標簽圖數(shù)據(jù)特征提取方法。為了更好地闡述算法，首先介紹本文需要用到的相關(guān)概念，其次介紹多標簽特征評估標準，最后介紹gSpan算法修剪子圖搜索空間。

多標簽圖數(shù)據(jù)分類的特征選取的關(guān)鍵在于如何從多標簽圖數(shù)據(jù)中找出最具有信息量的子圖。所以，本篇論文的研究問題可以描述為如下形式：為了訓(xùn)練一個有效的多標簽圖分類，如何從多標簽圖數(shù)據(jù)中有效地找出一個最優(yōu)的子圖特征集。挖掘多標簽圖數(shù)據(jù)的最優(yōu)子圖特征是一個非常有意義的任務(wù)，因為以下原因：（1）如何基于圖的多種標簽正確的評估子圖特征集的有用性？（2）如何基于圖的多種標簽用合理的時間消耗確定最優(yōu)子圖特征，避免詳細列舉？圖的子圖的特征空間通常是非常巨大的，因為子圖的數(shù)量隨著圖的大小呈指數(shù)倍增長。

3.2多標簽特征子圖評估

首先把集合A定義為子圖和母圖之間的模糊集。被稱為模糊測量的模糊子集的評估標準被提出來評估模糊集A的模糊性的自由度。模糊性的自由度用于在全局水平中表示元素是否屬于模糊集A的程度。在這里采用模糊熵為模糊性的自由度的測量方式。

其中H（QJ）表示由第Q個子圖有第，個類標簽的熵，X_i表示在模糊集中第q個子圖的第價特征表示。關(guān)于FSE哽加詳細的描述可以在文獻中找到。

3.3子圖空間搜索算法

為了能夠列舉圖數(shù)據(jù)的全部子圖，本文采用一種有效的算法，這是由Yan和Han提出的gSpan算法。他們首先在所有圖的邊界上建立一個詞典序列，然后繪制每一幅圖的獨一無二的最小DFs編碼作為圖的標準標簽。當且僅當兩幅圖形狀完全相同時它們的最，JxDSP編碼才相等?；谶@個詞典序列，利用深度優(yōu)先搜索策略（DFs）有效地在DFS編碼樹上搜索所有子圖。通過深度優(yōu)先算法搜索DSF編碼樹的節(jié)點，可以在圖的DFS編碼序列中列舉每一個圖的所有子圖，并且可以在樹上直接修剪不是最小DFS的節(jié)點。下列詳細介紹一TgSpan算法。

gspaJl算法思想：同一幅圖可以生成多個不同的DFS樹，gSpan算法就是按照DFS自動順序選擇其中一個作為基本的DFS樹，然后對其進行最右擴展以尋找最優(yōu)秀子圖。具體過程如下：（1）掃描圖數(shù)據(jù)集，去掉不符合的頂點和邊。（2）將得到的包含k條邊的子圖作為種子圖，根據(jù)最右路生長規(guī)則生成k+l條邊的候選子圖。如果該子圖是最小DFs詞典順序，則計算（FSEI），不符合的進行修剪。（3）重復(fù)（2），直到?jīng)]有新的候選子圖生成為止。詳細請見文獻。

3.4基于模糊適應(yīng)度函數(shù)的圖分類多標簽特征選取算法

受最近在圖數(shù)據(jù)分類算法上研究的啟發(fā)。這些算法把評估標準加到子圖模式挖掘步驟中并且通過約束以修剪搜索空間，本文也采用相似的算法。主要有3個步驟：（1）采用一個標準的搜索空間，其中包含可以列舉的所有子圖模式。（2）搜索子圖空間，通過FESI找出最優(yōu)的子圖特征。（3）提出一個FESI上界用于修剪搜索空間。

3.4.1子圖列舉

為了列舉從圖數(shù)據(jù)集中所有的子圖，本文采用前文中提到的gspan算法。不同于列舉子圖和同構(gòu)測試，gSpan首先建立一幅圖的所有邊的一個詞典順序，然后找出每一幅圖的最小DFS編碼作為獨一無二的標簽。基于這個詞典順序，通過深度優(yōu)先策略可以有效地搜索DFS編碼樹中的所有子圖。

3.4.2FSEI上界

通過上一步，本文已經(jīng)可以列舉圖數(shù)據(jù)的所有的子圖模式?，F(xiàn)在本文將設(shè)定FSEI上界值以便可以修剪搜索子空間。

定理2（FSEI上界）對于任何兩個子圖g，g∈s，g是圖g的母圖（gg）。則g的FSEI值受到g的FSEI值約束，即（FSEI（g）

3.4.3修剪子圖搜索空間

在這一步，本文通過FSEI上界有效的修剪子圖搜索空間。在深度搜索DFS編碼樹時，在完全找出所有（FSEI）值時維持暫時的次優(yōu)的FSEI值（用φ符號表示）。如果φ

4.實驗

在這一部分，本文拿本文的方法和圖數(shù)據(jù)的多標簽分類方法進行對比性實驗。本文使用現(xiàn)實生活中的多標簽數(shù)據(jù)集，通過對這些圖數(shù)據(jù)的實驗驗證本文算法的實用性與準確性。

4.1數(shù)據(jù)集

本文使用一組化合物抗癌活性性能數(shù)據(jù)集，NCI，作為實驗用的基于圖的多標簽數(shù)據(jù)集。這組數(shù)據(jù)包含了化合物對于10種癌癥（如：白血病，前列腺癌，乳腺癌）的抗癌活性性能的記錄，將10種癌癥中那些不完全的記錄移除，最終得到812個被分配了10個標簽的圖。表2是關(guān)于NcI數(shù)據(jù)集中標簽和癌癥的簡介。

每一個標簽代表一種癌癥的實驗結(jié)果。“Pos（%）”表示每個實驗的積極化合物的平均百分比。

4.2試驗方法與參數(shù)設(shè)定

為了能體現(xiàn)出本文提出的算法的有效性與實用性，文章將實現(xiàn)以下方法進行對比。

（1）多標簽特征選擇+多標簽分類（MLFS～SVM），本文首先采用本文的方法找出最優(yōu)的子圖特征集，然后用SVM—對多的訓(xùn)練每一個類并用于多標簽分類。本文用SVMqight軟件包訓(xùn)練多個SVM，其中的參數(shù)設(shè)置成默認模式。

（2）二元分解+單標簽特征選擇+二分類（BinarIG+SVM）：本文和另外的一個將多標簽問題分解成多個單標簽問題的算法就行對比。對于每一個二分類任務(wù)，本文都用Information Gain（IG）作為一個熵，以從頻繁子圖中選擇最具識別力的特征子集。使用SVM的二分類模式分別將圖分類成多個二分類。

4.3實驗結(jié)果評估

多標簽分類比傳統(tǒng)單標簽分類問題需要不同的實驗結(jié)果評估標準。在這里本文采用Ranking Loss和AveragePrecision以評估多標簽分類性能。假設(shè)多標簽圖數(shù)據(jù)為D=（G₁，y₁），…，（G_n，y_n）。其中圖G_i被標記為y_i∈（0，1）^Qf（G_i，k

AvgPrec∈[0，1]值越大，性能越好。在這個實驗中本文采用llAvgPrec～Average Precision。因此，所有的評估標準的值越小，性能越好。

4.4實驗結(jié)果

在本文的實驗中，每一個圖數(shù)據(jù)集都將其平均的分割成10個小的數(shù)據(jù)集。在這10個數(shù)據(jù)集中本文只采用其中的1個作為測試集，其他的9個數(shù)據(jù)集作為訓(xùn)練集。本文實驗分別選擇[5，10，15，20，25，30，35，40]個不同的最優(yōu)子圖進行對比實驗。實驗結(jié)果如圖1-2所示。圖1表示Ranking Loss的實驗結(jié)果，圖2表示1-AvgPrec的實驗結(jié)果。

如圖1-2所示，橫坐標表示本文實驗最終選取的最優(yōu)子圖數(shù)量，縱坐標則分別表示Ranking Loss和1-AvgPrec值。從圖2曲線圖可以知道，隨著選取的標簽節(jié)點數(shù)的增加，本文方法（MLFS+SVM）輸出效果比（Binary IG+SVM）的輸出效果略好。由圖2本文可以看出，在最優(yōu)子集選取數(shù)量少時本文的算法優(yōu)于對比算法，但隨著選取的子圖數(shù)量增加，本文的算法輸出效果和對比算法很接近。值得注意的是本文的算法是同時考慮多個標簽的信息價值，將多個標簽同時應(yīng)用于圖數(shù)據(jù)分類問題。而Binary IG+SVM算法則是單獨選擇每一個標簽的特征集，這些特征集分別用于SVM進行圖數(shù)據(jù)分類。所以本文的方法在實用性上有可取之處。

總之，文中的方法同時采用多個標簽進行分類，在一定程度上對圖數(shù)據(jù)的分類結(jié)果有較好的影響。

5.結(jié)語

在這篇文章中，筆者采用模糊測量方法對具有不同標簽的子圖進行評估，有效地結(jié)合了多個標簽信息對圖數(shù)據(jù)分類的作用；通過邊枝界定算法對子圖搜索空間進行修剪，避免了詳細列舉大量子圖。在以后的研究工作中，本文將會繼續(xù)完善本文的方法，并尋找更優(yōu)秀的多標簽圖數(shù)據(jù)的子圖選擇算法。