李程文　劉波

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

關(guān)鍵詞：圖數(shù)據(jù)；模糊測量；多標(biāo)簽；特征選?。贿呏缍?/p>

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

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

圖是一種最常用的數(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)該能夠提取或者找出這些圖的一個適當(dāng)?shù)奶卣髯蛹杂糜诜治龌蛘哳A(yù)測。在現(xiàn)實應(yīng)用中，訓(xùn)練圖集的子圖特征數(shù)量也許會呈指數(shù)倍增長，這些數(shù)據(jù)中包含大量的冗余數(shù)據(jù)和錯誤數(shù)據(jù)。所以多標(biāo)簽分類方法都將依賴于特征篩選程序以選擇最重要的子圖用來分類。

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

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

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

2.相關(guān)工作

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

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

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

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

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

長期以來，圖數(shù)據(jù)挖掘問題在機(jī)器學(xué)習(xí)領(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等?；谧钚∶枋鲩L度的近似頻繁子結(jié)構(gòu)挖掘算法，包括SUBDUE等。gSpan算法是一種由Yan～Han提出的基于深度優(yōu)先搜索算法及最右路徑擴(kuò)展技術(shù)生成頻繁子圖的算法。

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

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

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

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

3.2多標(biāo)簽特征子圖評估

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

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

3.3子圖空間搜索算法

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

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

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

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

3.4.1子圖列舉

為了列舉從圖數(shù)據(jù)集中所有的子圖，本文采用前文中提到的gspan算法。不同于列舉子圖和同構(gòu)測試，gSpan首先建立一幅圖的所有邊的一個詞典順序，然后找出每一幅圖的最小DFS編碼作為獨一無二的標(biāo)簽?；谶@個詞典順序，通過深度優(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ù)的多標(biāo)簽分類方法進(jìn)行對比性實驗。本文使用現(xiàn)實生活中的多標(biāo)簽數(shù)據(jù)集，通過對這些圖數(shù)據(jù)的實驗驗證本文算法的實用性與準(zhǔn)確性。

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

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

每一個標(biāo)簽代表一種癌癥的實驗結(jié)果?！癙os（%）”表示每個實驗的積極化合物的平均百分比。

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

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

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

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

4.3實驗結(jié)果評估

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

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

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)子圖進(jìn)行對比實驗。實驗結(jié)果如圖1-2所示。圖1表示Ranking Loss的實驗結(jié)果，圖2表示1-AvgPrec的實驗結(jié)果。

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

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

5.結(jié)語

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