基于模糊測量函數的多標簽圖數據特征提取研究

李程文　劉波

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

關鍵詞：圖數據；模糊測量；多標簽；特征選取；邊枝界定

1.多標簽圖數據分類研究背景

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

圖是一種最常用的數據結構之一，用于表示事物之間復雜的關系。圖廣泛地應用于很多分類領域，用于表示復雜結構的物體。如文件分類和在線產品推薦。同時，圖數據的復雜性也成為研究中的難點。一個有效的圖數據應該能夠提取或者找出這些圖的一個適當的特征子集以用于分析或者預測。在現實應用中，訓練圖集的子圖特征數量也許會呈指數倍增長，這些數據中包含大量的冗余數據和錯誤數據。所以多標簽分類方法都將依賴于特征篩選程序以選擇最重要的子圖用來分類。

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

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

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

2.相關工作

由于關注的是基于圖數據的多標簽特征子圖的挖掘，首先回顧多標簽數據分類和子圖特征挖掘。

2.1多標簽數據分類

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

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

2.2圖數據挖掘

長期以來，圖數據挖掘問題在機器學習領域得到了廣泛關注。圖數據挖掘問題主要包括圖的匹配、圖數據中的關鍵字查詢、頻繁子圖挖掘、聚類以及分類等。其中頻繁子圖挖掘算法主要研究關于如何從圖數據中提取最具信息價值的子圖特征信息。常見的頻繁子圖挖掘算法可以分為4類：基于Apriori的算法、基于模式增長的算法、基于模式增長和模式歸約算法和基于最小描述長度的近似算法。基于Apriori的頻繁子圖挖掘算法包括基于Apriori算法的圖挖掘（Apriori-based Graph Mining，AGM）、Frequert子圖發現（FrequertSubgraph Discovery，FSG）、路徑連接算法等。基于模式增長的頻繁結構挖掘算法，包括gSpan，快速頻繁子圖挖掘（Fast Frequent Subgraph Mining，FFSM）、CloseGraph等。基于模式增長和模式歸約的精確稠密頻繁子結構挖掘算法，包括CloseCut及Splat等。基于最小描述長度的近似頻繁子結構挖掘算法，包括SUBDUE等。gSpan算法是一種由Yan～Han提出的基于深度優先搜索算法及最右路徑擴展技術生成頻繁子圖的算法。

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

3.基于模糊適應度函數的圖分類多標簽特征選取

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

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

3.2多標簽特征子圖評估

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

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

3.3子圖空間搜索算法

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

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

3.4基于模糊適應度函數的圖分類多標簽特征選取算法

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

3.4.1子圖列舉

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

3.4.2FSEI上界

通過上一步，本文已經可以列舉圖數據的所有的子圖模式。現在本文將設定FSEI上界值以便可以修剪搜索子空間。

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

3.4.3修剪子圖搜索空間

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

4.實驗

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

4.1數據集

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

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

4.2試驗方法與參數設定

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

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

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

4.3實驗結果評估

多標簽分類比傳統單標簽分類問題需要不同的實驗結果評估標準。在這里本文采用Ranking Loss和AveragePrecision以評估多標簽分類性能。假設多標簽圖數據為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實驗結果

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

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

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

5.結語

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