基于多標簽數據的降維與分類算法的研究

湯文偉，于威威（上海海事大學，上?！?01306）

?

基于多標簽數據的降維與分類算法的研究

湯文偉，于威威
（上海海事大學，上海201306）

摘要：

關鍵詞：

0　引言

在傳統的數據分類中，我們一般把數據標注為單一的類別標簽。但是在實際的生活應用中，一個數據通?？梢酝瑫r被標注為多個標簽。例如，我們經常會看到一些非常美麗的照片或者是風景圖片，在這些圖片上往往會有山有水還有人物；很多影視作品，我們在其描述信息中會看到上映時間、作品類型、出品公司等信息；還有一些新聞性質的報導，我們可以把其標注為國家、實事、政治、經濟等。這類數據統稱為多標簽數據[1]。多標簽數據的分類就是針對給出的數據的特點，得到其對應的數據模型，最終要實現的就是依據此數據模型來判斷未知類別的過程[2]。與我們熟悉的單標簽數據分類最大的不同就是，多標簽分類最終會輸出多個結果。多標簽數據的分類在我們的現實生活中應用已經很廣泛了，如定基因功能分類[3]、定向營銷[4]、圖像語義注釋[5]等。

目前，已經有一些多標簽分類的學習算法，我們可以把這些算法大致分為兩類，即問題轉化方法和自適應方法。問題轉化方法實質上就是把多標簽分類的問題轉化為傳統單標簽分類問題，然后應用已有的單標簽分類方法進行數據的分類。該方法的主要轉化策略有選擇、標簽冪集、忽略、二元相關和復制等。另一種就是算法自適應方法，即在傳統分類算法的基礎上設置不同的約束條件，使其能直接處理多標簽數據，將其進行準確的分類。該方法的典型代表有支持向量機[6]、C4.5[6]和BP-MLL[7]等。

多標簽數據分類無疑能使我們將數據進行更詳細更完整的分類，但隨著新的分類技術的出現，多標簽數據正在面臨著高維度的問題。數據的高維性是一把雙刃劍，它一方面可以為分類模型的建立提供充足的分類信息，但另一方面也給分類算法帶來了許多弊端，如峰值問題、過擬合和維度災難等。所謂的峰值問題是指分類的性能剛開始時會隨著維數的增加而不斷提高，但當到達一定程度后，其性能會隨著維數的增加而降低；這里的維度災難簡而言之就是隨著數據維度的不斷增加，進行分類時所需要的訓練樣本數量將呈指數的形式增加。正是由于維數的雙面性，我們需要對維數進行約減，這里我們使用特征選擇的方式，特征選擇是一種有效的維數約減的技術，所謂的特征選擇就是根據某種評估標準從原始的特征空間中選擇一個最優的特征子集來代替原來的特征空間，以此來構建分類模型的過程。由于在進行特征選擇時是根據所選定的評估標準進行的，所以評估標準在特征選擇過程中起著決定性的作用，其選擇的好壞將直接決定特征選擇算法性能及最終分類模型的分類效果。到目前為止，已經存在了很多評估標準，如信息準則、一致性準則、距離準則和分類誤差準則等。

1　條件互信息

現有的基于互信息的多標簽特征選擇的方法可以有效地減少多標簽數據的維度。例如，Lee和Kim[8]提出一種基于多元互信息的多標簽特征選擇方法，通過選擇一個有效的特征子集來最大化所選特征與標簽之間的依賴。同時，Lee和Kim[9]提供了一個利用互信息進行多標簽特征選擇的算法。這個算法可以測量變量之間的依賴關系。此外，Lee和Kim[10]還提出一種迷因多標簽特征選擇方法，該方法通過重新定義特征來發現遺傳搜索子集。除此以外，Doquire和Verleysen[11]也設計了一種針對多標簽問題的基于互信息的特征選擇算法，該算法首先利用PPT轉換問題，然后使用基于互信息的貪婪搜索策略來選擇與分類最相關的特征。

雖然以上方法在多標簽的特征選擇方面起到了一定的效果，但未涉及到對于減少冗余特征的選擇方法。在多標簽學習中，冗余不僅僅包括候選特征和使選特征之間的互信息，還包括當所有選特征已給定時候選特征之間的互信息。在本文中提出一種基于最大依賴和最小冗余的多標簽特征選擇的方法來提高特征在多標簽學習性能方面的能力。

1.1熵與互信息

香農熵[12]是一個不確定的隨機的變量，并廣泛應用于不同的領域。若A=｛a1，a2，a3，…，an｝是一個隨機變量，P（ai）是ai出現的概率。

那么A的熵可以被定義成：

如果B=｛b1，b2，b3，…，bm｝是一個隨機變量，A和B的聯合概率表示為p（ai，bi）。

那么A和B的熵可以被定義成：

假設A是已知的，那么B的熵的值則被定義為條件熵：

證明：

當A的熵減小后觀察B，我們會發現B的熵值也在變化，這就是A與B之間的互信息，被定義為：

互信息可以反映A與B之間統計關系之間的程度，我們有：

證明：

1.2基于最小冗余和最大依賴的特征選擇

特征選擇的目標就是選擇一個能最大化保持原始特征空間的緊湊的特征子集?；谛畔⒗碚摚珺ell和Wang[13]介紹了第一個公理化特征子集的選擇方法。

公理1：（學習信息的保存）給定一個數據集，其特征集為F標簽集為C，預期的特征子集為S，若S滿足MI（S；C）=MI（F；C），則保存此特征子集S。

公理2：（最小的編碼長度）[14]給定一個數據集，其特征集為F標簽集為C，S是其一個特征子集。若存在S1∈S使得聯合熵H（S1，C）最小，則S1可以作為標簽判斷的依據。

公理1和公理2給出了基于互信息的理論，一個好的特征子集需要具備的一些條件。不同于單標簽學習，多標簽分類中標簽是一個標簽的集合。

接下來提出一種新的針對多標簽學習的公理化方法。

公理3：（多標簽學習信息的保存）[15]給定一個數據集，其特征空間為F，標簽的空間為L，預期的特征子集為S，若S滿足MI（S；L）=MI（F；L），則S可以作為多標簽學習的特征子集。

公理4：（多標簽學習的最小編碼長度）

通過（1）我們可以得出以下屬性：

屬性1：如果待選的特征f+和每一類標簽li∈L是相互獨立的，那么f+和L之間的互信息[15]是最小的。

屬性2：如果每一類的標簽li∈L完全是由f+決定的，那么f+和L之間的互信息是最大的。

從屬性1和屬性2，我們可以使用公式（1）來選擇與所有類標簽有著最大依賴的特征。然而基于最大依賴的特征可能會產生冗余。因此當我們在特征選擇[16]時要衡量特征之間的冗余。不同于傳統的單標簽特征的選擇，在多標簽特征的選擇過程中不僅要考慮每個特征之間的冗余，還要考慮每個類標簽與特征之間[17]的最大依賴性。假設S為一個已選定的特征子集。則最小冗余可以用以下公式來衡量：

將式（3）進行轉化：

我們可以繼續對式（4）進行變換：

從（5）中我們可以更清晰地看出特征與標簽的最小冗余和最大依賴的關系了。

接下來就介紹一下基于最小冗余和最大依賴的多標簽特征選擇算法的基本步驟：

算法步驟：

輸入：N：被選擇特征的數目。

輸出：S：特征的排名。

①初始化S=?，F=｛f1，f2，…，fN｝；

②判斷|S|＜N，若不等式成立則執行③，否則退出；

③尋找f∈F，能使得（8）中的值最??；

④S=S∪｛f｝；

⑤F=F-｛f｝；

⑥返回S；

2　基于改進的KNN分類算法

在本文的第二節著重介紹了一下在進行多標簽數據分類之前所進行的特征選擇，這將大大提高我們多標簽分類的效率。當特征選擇完成之后，選擇什么樣的分類算法對分類的結果將有著至關重要的影響，在本節中我們將介紹一種改進的KNN算法。

算法步驟：

輸入1：多標簽訓練樣本集｛（Χi，Yi），i＝1，2，…，m｝，其中X=｛Χ1，Χ2，…，Χm｝，Χi∈X，Y=｛λ1，λ2，…，λn｝，Yi?Y。

輸入2：多標簽測試樣本集｛Χm+1，Χm+2，…，Χm+n｝。

輸出：圖片所屬類型。

①通過構造超球（以標簽（λ1，λ2，λ3）作為球心來構造超球），然后通過K近鄰算法來判斷每個超球[20]里面所包含的樣本，以歐氏距離作為判斷樣本是否屬于此類標簽的依據，K值的確定可以通過不斷訓練以找到最佳的K值；

②根據第一步得到的超球來構建一個二維數組（以Scene數據集為例，橫軸代表樣本，縱軸代表標簽）：

每個元素代表該樣本是否具有該標簽，若該樣本具有該標簽則將賦值為1，否則賦值為0；

③根據②中得到的二維矩陣進行縱向迭代，使其轉換為一組一維數組Χi[λ1，λ2，λ3]，由于選擇的數據庫是scene，所以得到的標簽值一共有64種情況，用算法在將其轉換為一個具體的數值（就是二進制與十進制的轉換）；

④前三步為訓練的過程，根據訓練的結果將訓練的樣本進行歸類。最后選取測試樣本進行測試，方法同上，可以得到測試樣本的一個具體標簽值，然后根據所得到的標簽值進行分類。

3　實驗結果與分析

為了驗證我們所提出方法的有效性，我們選擇了scene數據集作為我們的測試數據集，并且與一些現有的多標簽分類算法進行比較。本節首先簡要描述多標簽數據集和實驗的設置，以及給出四個評價標準。然后對實驗結果進行評價標準的討論。

3.1實驗基本設置

對于本次實驗我們選擇了Scene數據集作為測試數據集，以下是Scene數據集的基本信息。

表1　

我們分別采用最小冗余和最大依賴（MDMR）、MLNB、PMU、MDDMspc、MDDMproj四種特征選擇方法對特征進行選擇，然后在利用我們改進的KNN算法（K取值10）對圖像進行多標簽分類。

3.2評價標準

由于多標簽數據分類輸出的結果往往是多標簽的，那些基于單標簽的評價標準[24]（如查全率、查準率等）已無法滿足。因此，在本文中利用新的適合于多標簽分類[25]的四個評價標準。

（1）漢明損失（Hamming Loss）

漢明損失[26]是用來量化基于單個標簽的分類誤差，簡而言之，就是本該屬于該樣本的標簽沒有出現在該類標簽的集合，而相反不屬于的卻出現在集合中了。該值越小，說明分類性能越好。其定義是：

其中，Δ指的是對稱差算子[27]，表示兩個集合的對稱差只屬于一個集合而不是屬于另一個集合的元素組成的集合。

（2）Coverage

Coverage指的是所選特征子集的覆蓋范圍[28]。

（3）排序損失（Ranking Loss）

排序損失指的是所有標簽的出錯程度[25]，該值越小，性能越優。

（4）平均精度（Average Precision）

平均精度表示的是分類模型標簽預測準確程度[29]。該指標越大則分類模型性能越優。

3.3實驗結果

根據3.2中的評價標準，我們可以得出針對Scene數據集在不同多標簽分類算法下的分類效率。

各方法性能的比較如下表：

表2　

3.4結果分析

先對Scene數據集利用MDMR算法對特征進行選擇，然后使用本文提出的改進的KNN算法對圖像進行分類，通過上述實驗數據可以看出對比于其他多標簽分類算法（MLMB[30]、MDDMspc[31]、MDDMporj[32]、PMU[33]），在Hamming Loss、Coverage、Ranking Loss、Average Percision四個分類評價標準中，MDMR都有著明顯的優勢。

不同于傳統的單標簽數據的分類，標簽之間的相互依賴[34]是多標簽分類中的一個重要的特點。因此解決多標簽特征選擇的問題對于多標簽分類的效率有著至關重要的影響。

從以上實驗數據我們可以清晰地看到不同的多標簽特征選擇方法可以減少多標簽數據的維數，從而提高多標簽分類的效率。在本文中我們確定兩個重要的因素來衡量特征，即依賴和冗余。我們采取最大依賴和最小冗余的特征選擇策率對特征集進行選擇。最終，實驗結果表明我們給出的方法與現有的一些方法更加有效。

圖1　

參考文獻：

[1]Tsoumakas G，Katakis I.Mutilabel Classification：An Overview[J].Data Warehousing and Mining，2007，3（3）：1-13.

[2]Tsoumakes G，Katakis I，Vlahavas I.Mining Multilabel Data[M].Data Mining and Knowledge Discovery Handbook.New York：Springer，2010.

[3]Boutell M R，Luo Jie-Bo，Shen Xi-Peng，Et Al.Learning Multilabel Scene Classification[J].Pattern Recognition，2004，37（9）：1757-1771.

[4]Zhang Yi，Burer S，Street W N.Ensemble Pruning Via Semidefinite Programming[J].Machine Learning Research，2006，7（12）：1315-1338.

[5]Blockeel H，Schietgat L，Struyf J，et al.Decision Trees for Hierarchical Mulilabel Classification：A Cass Study in Functional Genomics[M].New York：Spring Berlin Heidelberg，2006.

[6]Tsoumakas G，Vlahavas I.Random K-Labelsets：An Ensemble Method for Multilabel Classification：Machine Learning[M].New York：Spring Berlin Heidelberg，2007.

[7]Zhang Min-Ling，Zhou Zhi-Hua.Mutilabel Neural Networks with Application to Functional Genomics and Text Categorization[J].IEEE Transactions On Knowledge And Data Engineering，2006，18（10）：1338-1351.

[8]J.Lee，D.Kim，Feature Selection for Multi-Label Classification Using Multivariate Mutual Information，Pattern Recognit.Lett.34（2013）349-359.

[9]J.Lee，D.Kim，Mutual Information-Based Multi-Label Feature Selection Using Interaction Information，Expert Syst.Appl.42（2015）2013-2025

[10]J.Lee，D.Kim，Memetic Feature Selection Algorithm for Multi-Label Classification，Inf.Sci.293（2015）80-96.

[11]G.Doquire，M.Verleysen，Mutual Information-Based Feature Selection for Multilabel Classification，Neurocompution，122（2013）：148-155.

[12]C.Shannon，A Mathematical Theory Of Communication，Bell Syst.Tech.J.27（1948）：379-423，623-656.

[13]D.Bell，H.Wang，A Formalism For Relevance and Its Application In Feature Subset Selection，Mach.Learn.41（2000）：175-195.

[14]LEWIS D D，YANG Y，ROSE T G，et al.Rcvl：A New Benchmark Collection for Text Categorization Research[J].The Journal of Machine Learning Research，2004（5）：361-397.

[15]ZHANG M L，ZHOU Z H.Multilabel Nerural Networks with Applications to Functional Genomics and Text Categorization[J].IEEE Transzction on Knowledge and Data Engineering，2006，18（10）：1338-1351.

[16]湯進，黃莉莉，趙海峰，等.使用D適應線性回歸多標簽分類算法[J].華南理工大學學報（自然科學版），2012，40（9）：69-74.

[17]王國強.Rough集理論與知識獲取[M].西安：西安交通大學出版社，2001.

[18]張玲.問題求解理論及應用[M].北京：清華大學出版社，1990.

[19]D.Zhou，J.Huang，B.Scholkopf，Learning Form Labeled and Unlabeled Data on Adirected Graph[C].Proc.22 Nd Int'l Conf.Machine Learning，2005，1041-1048.

[20]Szummer，M.Jaakkola，T.Partially Labeled Classification With Markov Random Walks[C].Advances in Neural Information Procession Systems（NIPS），2001，14：1-8.

[21]Leo Grady，Random Walks for Image Segmentation[C].IEEE Transcation on Pattern Analysis and Machine Intelligence.，2006，28（11）：1768-1783.

[22]C.Ding，Spectral Clutering[C].Tutorial Presented at the 16th European Conf.Machine Learning（Ecml），2005.

[23]Tang L，Rajan S，Narayanan V.Large Scale Multi-Label Classification Via Metalabel[C].Proceedings of the 18th International World Wide Web Conference.Madrid：Acm，2009：211-220.

[24]Fan R，Lin C.A Study on Threshold Selection For Multi-Label Classification[R].Taiwan：Department of Computer Science，National Taiwan University.2007：1-23.

[25]鄭偉，王朝坤，劉璋，王建民.一種基于隨機游走模型的多標簽分類算法.計算機學報，2010，33（8）：1418-1426.

[26]張敏靈.一種新型多標簽懶惰學習算法[J].計算機研究與發展，2012，49（11）：2271-2282.

[27]張賢達.矩陣分析（M）.1版.北京：清華大學出版社，2008.

[28]王國胤，張清華，胡軍.粒計算研究綜述[J].智能系統學報，2007，2（6）：8-26.

[29]Jain A.K，Murty M.N，Flynn P.J.Data Clustering；A Review[J].ACM Compution Surveysm，1999，31（3）：264-323.

[30]Weiwei Cheng，Eyke Hullermeier.Combining Instance-Based Learning And Logistic Regession for Multilabel Classification[J].Machine Learning.Volume 76 Number 2-3，211-255.

[31]Huawen Liu，Shichao Zhang.Noisy Data Elimination Using Mutual K-Nearest Neighbor for Classification Mining[J].The Journal of System And Software 2012，85：1067-1074.

[32]J.Read，B.Pfahringer，G Holmes，et al.Classifier Chains for Multi-Label Classification[J].Lecture Notes in Artificial Intelligence 5782，2009：254-269.

[33]Weizorkowska A，Synak P，et al.Multi-Label Classification of Emotion in Music[J].Advances in Soft Computing，2006，Volume 35/ 2006，307-315.

[34]Furnkranz J，Hollermeier E，et al.Multilabel Classification Via Calibrated Label Ranking[J].Machine Learning，2008，72（2）：133-153.

Research on Dimension Reduction and Classification Algorithm Based on Multi Label Data

TANG Wen-wei，YU Wei-wei
（Shanghai Maritime Univeristy，Shanghai 201306）

Abstract：

Now，is well known that the classification of a single label，the traditional method of supervised learning are used in data in a single label，but the increasing rich data，single-label can no longer complete description of a sample of the information，a sample often can corresponds more tags todays，so multi-label classification data gradually become an important research direction of data mining.While many labels to better information to describe a sample，multi-label data is usually characterized by a large number of the kind of data，so it is difficult to process such data directly，and these high-dimensional data while there is often the curse of dimensionality problem，Data before doing so multi-label data classification dimension reduction on the final classification and plays an essential role.Presents for this condition based on the use of mutual information（Minimum Redundancy AND Maximum Dependent）to select the feature set，removing useless features information，and then through an improved KNN algorithm for data classification，experimental results show that this method is that the average recall rate increased by 2.5％.

Keywords：

現在為人們所熟知的是單標簽的分類，傳統的監督學習的方法主要應用在單標簽的數據中，但隨著數據的日益豐富，單標簽已經不能再完整地描述一個樣本的信息，現在往往一條樣本會對應多個標簽，所以多標簽數據的分類逐漸的成為數據挖掘的一個重要研究方向。雖然多標簽能夠更好地去描述一個樣本的信息，但多標簽數據通常是那種特征數目很大的數據，對這樣的數據直接進行處理很困難，同時這些高維數據往往存在維度災難的問題，所以對多標簽數據進行分類之前做好數據的降維對最終的分類起著不可忽視的作用。提出一種基于采用條件互信息（最小冗余最大依賴準則，MDMR）來進行特征集的選擇，去除無用的特征信息，然后通過一種改進的KNN算法對數據進行分類，實驗表明這種方法使平均查全率提高2.5％。

單標簽；多標簽；條件互信息；特征提取；KNN算法

文章編號：1007-1423（2016）14-0003-07

DOI：10.3969/j.issn.1007-1423.2016.14.001

作者簡介：

湯文偉（1990-），男，江蘇常州人，碩士，研究方向為圖像處理、模式識別

收稿日期：2016-03-08修稿日期：2016-05-20

Single-Label；Multi-Label；Conditional Mutual Information；Feature Extraction；KNN Algorithm