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

?

基于多標(biāo)簽數(shù)據(jù)的降維與分類算法的研究

湯文偉，于威威
（上海海事大學(xué)，上海201306）

摘要：

關(guān)鍵詞：

0　引言

在傳統(tǒng)的數(shù)據(jù)分類中，我們一般把數(shù)據(jù)標(biāo)注為單一的類別標(biāo)簽。但是在實(shí)際的生活應(yīng)用中，一個(gè)數(shù)據(jù)通?？梢酝瑫r(shí)被標(biāo)注為多個(gè)標(biāo)簽。例如，我們經(jīng)常會(huì)看到一些非常美麗的照片或者是風(fēng)景圖片，在這些圖片上往往會(huì)有山有水還有人物；很多影視作品，我們?cè)谄涿枋鲂畔⒅袝?huì)看到上映時(shí)間、作品類型、出品公司等信息；還有一些新聞性質(zhì)的報(bào)導(dǎo)，我們可以把其標(biāo)注為國(guó)家、實(shí)事、政治、經(jīng)濟(jì)等。這類數(shù)據(jù)統(tǒng)稱為多標(biāo)簽數(shù)據(jù)[1]。多標(biāo)簽數(shù)據(jù)的分類就是針對(duì)給出的數(shù)據(jù)的特點(diǎn)，得到其對(duì)應(yīng)的數(shù)據(jù)模型，最終要實(shí)現(xiàn)的就是依據(jù)此數(shù)據(jù)模型來判斷未知類別的過程[2]。與我們熟悉的單標(biāo)簽數(shù)據(jù)分類最大的不同就是，多標(biāo)簽分類最終會(huì)輸出多個(gè)結(jié)果。多標(biāo)簽數(shù)據(jù)的分類在我們的現(xiàn)實(shí)生活中應(yīng)用已經(jīng)很廣泛了，如定基因功能分類[3]、定向營(yíng)銷[4]、圖像語義注釋[5]等。

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

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

1　條件互信息

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

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

1.1熵與互信息

香農(nóng)熵[12]是一個(gè)不確定的隨機(jī)的變量，并廣泛應(yīng)用于不同的領(lǐng)域。若A=｛a1，a2，a3，…，an｝是一個(gè)隨機(jī)變量，P（ai）是ai出現(xiàn)的概率。

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

如果B=｛b1，b2，b3，…，bm｝是一個(gè)隨機(jī)變量，A和B的聯(lián)合概率表示為p（ai，bi）。

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

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

證明：

當(dāng)A的熵減小后觀察B，我們會(huì)發(fā)現(xiàn)B的熵值也在變化，這就是A與B之間的互信息，被定義為：

互信息可以反映A與B之間統(tǒng)計(jì)關(guān)系之間的程度，我們有：

證明：

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

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

公理1：（學(xué)習(xí)信息的保存）給定一個(gè)數(shù)據(jù)集，其特征集為F標(biāo)簽集為C，預(yù)期的特征子集為S，若S滿足MI（S；C）=MI（F；C），則保存此特征子集S。

公理2：（最小的編碼長(zhǎng)度）[14]給定一個(gè)數(shù)據(jù)集，其特征集為F標(biāo)簽集為C，S是其一個(gè)特征子集。若存在S1∈S使得聯(lián)合熵H（S1，C）最小，則S1可以作為標(biāo)簽判斷的依據(jù)。

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

接下來提出一種新的針對(duì)多標(biāo)簽學(xué)習(xí)的公理化方法。

公理3：（多標(biāo)簽學(xué)習(xí)信息的保存）[15]給定一個(gè)數(shù)據(jù)集，其特征空間為F，標(biāo)簽的空間為L(zhǎng)，預(yù)期的特征子集為S，若S滿足MI（S；L）=MI（F；L），則S可以作為多標(biāo)簽學(xué)習(xí)的特征子集。

公理4：（多標(biāo)簽學(xué)習(xí)的最小編碼長(zhǎng)度）

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

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

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

從屬性1和屬性2，我們可以使用公式（1）來選擇與所有類標(biāo)簽有著最大依賴的特征。然而基于最大依賴的特征可能會(huì)產(chǎn)生冗余。因此當(dāng)我們?cè)谔卣鬟x擇[16]時(shí)要衡量特征之間的冗余。不同于傳統(tǒng)的單標(biāo)簽特征的選擇，在多標(biāo)簽特征的選擇過程中不僅要考慮每個(gè)特征之間的冗余，還要考慮每個(gè)類標(biāo)簽與特征之間[17]的最大依賴性。假設(shè)S為一個(gè)已選定的特征子集。則最小冗余可以用以下公式來衡量：

將式（3）進(jìn)行轉(zhuǎn)化：

我們可以繼續(xù)對(duì)式（4）進(jìn)行變換：

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

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

算法步驟：

輸入：N：被選擇特征的數(shù)目。

輸出：S：特征的排名。

①初始化S=?，F(xiàn)=｛f1，f2，…，fN｝；

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

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

④S=S∪｛f｝；

⑤F=F-｛f｝；

⑥返回S；

2　基于改進(jìn)的KNN分類算法

在本文的第二節(jié)著重介紹了一下在進(jìn)行多標(biāo)簽數(shù)據(jù)分類之前所進(jìn)行的特征選擇，這將大大提高我們多標(biāo)簽分類的效率。當(dāng)特征選擇完成之后，選擇什么樣的分類算法對(duì)分類的結(jié)果將有著至關(guān)重要的影響，在本節(jié)中我們將介紹一種改進(jìn)的KNN算法。

算法步驟：

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

輸入2：多標(biāo)簽測(cè)試樣本集｛Χm+1，Χm+2，…，Χm+n｝。

輸出：圖片所屬類型。

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

②根據(jù)第一步得到的超球來構(gòu)建一個(gè)二維數(shù)組（以Scene數(shù)據(jù)集為例，橫軸代表樣本，縱軸代表標(biāo)簽）：

每個(gè)元素代表該樣本是否具有該標(biāo)簽，若該樣本具有該標(biāo)簽則將賦值為1，否則賦值為0；

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

④前三步為訓(xùn)練的過程，根據(jù)訓(xùn)練的結(jié)果將訓(xùn)練的樣本進(jìn)行歸類。最后選取測(cè)試樣本進(jìn)行測(cè)試，方法同上，可以得到測(cè)試樣本的一個(gè)具體標(biāo)簽值，然后根據(jù)所得到的標(biāo)簽值進(jìn)行分類。

3　實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證我們所提出方法的有效性，我們選擇了scene數(shù)據(jù)集作為我們的測(cè)試數(shù)據(jù)集，并且與一些現(xiàn)有的多標(biāo)簽分類算法進(jìn)行比較。本節(jié)首先簡(jiǎn)要描述多標(biāo)簽數(shù)據(jù)集和實(shí)驗(yàn)的設(shè)置，以及給出四個(gè)評(píng)價(jià)標(biāo)準(zhǔn)。然后對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià)標(biāo)準(zhǔn)的討論。

3.1實(shí)驗(yàn)基本設(shè)置

對(duì)于本次實(shí)驗(yàn)我們選擇了Scene數(shù)據(jù)集作為測(cè)試數(shù)據(jù)集，以下是Scene數(shù)據(jù)集的基本信息。

表1　

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

3.2評(píng)價(jià)標(biāo)準(zhǔn)

由于多標(biāo)簽數(shù)據(jù)分類輸出的結(jié)果往往是多標(biāo)簽的，那些基于單標(biāo)簽的評(píng)價(jià)標(biāo)準(zhǔn)[24]（如查全率、查準(zhǔn)率等）已無法滿足。因此，在本文中利用新的適合于多標(biāo)簽分類[25]的四個(gè)評(píng)價(jià)標(biāo)準(zhǔn)。

（1）漢明損失（Hamming Loss）

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

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

（2）Coverage

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

（3）排序損失（Ranking Loss）

排序損失指的是所有標(biāo)簽的出錯(cuò)程度[25]，該值越小，性能越優(yōu)。

（4）平均精度（Average Precision）

平均精度表示的是分類模型標(biāo)簽預(yù)測(cè)準(zhǔn)確程度[29]。該指標(biāo)越大則分類模型性能越優(yōu)。

3.3實(shí)驗(yàn)結(jié)果

根據(jù)3.2中的評(píng)價(jià)標(biāo)準(zhǔn)，我們可以得出針對(duì)Scene數(shù)據(jù)集在不同多標(biāo)簽分類算法下的分類效率。

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

表2　

3.4結(jié)果分析

先對(duì)Scene數(shù)據(jù)集利用MDMR算法對(duì)特征進(jìn)行選擇，然后使用本文提出的改進(jìn)的KNN算法對(duì)圖像進(jìn)行分類，通過上述實(shí)驗(yàn)數(shù)據(jù)可以看出對(duì)比于其他多標(biāo)簽分類算法（MLMB[30]、MDDMspc[31]、MDDMporj[32]、PMU[33]），在Hamming Loss、Coverage、Ranking Loss、Average Percision四個(gè)分類評(píng)價(jià)標(biāo)準(zhǔn)中，MDMR都有著明顯的優(yōu)勢(shì)。

不同于傳統(tǒng)的單標(biāo)簽數(shù)據(jù)的分類，標(biāo)簽之間的相互依賴[34]是多標(biāo)簽分類中的一個(gè)重要的特點(diǎn)。因此解決多標(biāo)簽特征選擇的問題對(duì)于多標(biāo)簽分類的效率有著至關(guān)重要的影響。

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

圖1　

參考文獻(xiàn)：

[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，F(xiàn)eature 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]湯進(jìn)，黃莉莉，趙海峰，等.使用D適應(yīng)線性回歸多標(biāo)簽分類算法[J].華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，40（9）：69-74.

[17]王國(guó)強(qiáng).Rough集理論與知識(shí)獲取[M].西安：西安交通大學(xué)出版社，2001.

[18]張玲.問題求解理論及應(yīng)用[M].北京：清華大學(xué)出版社，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]鄭偉，王朝坤，劉璋，王建民.一種基于隨機(jī)游走模型的多標(biāo)簽分類算法.計(jì)算機(jī)學(xué)報(bào)，2010，33（8）：1418-1426.

[26]張敏靈.一種新型多標(biāo)簽懶惰學(xué)習(xí)算法[J].計(jì)算機(jī)研究與發(fā)展，2012，49（11）：2271-2282.

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

[28]王國(guó)胤，張清華，胡軍.粒計(jì)算研究綜述[J].智能系統(tǒng)學(xué)報(bào)，2007，2（6）：8-26.

[29]Jain A.K，Murty M.N，F(xiàn)lynn 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：

現(xiàn)在為人們所熟知的是單標(biāo)簽的分類，傳統(tǒng)的監(jiān)督學(xué)習(xí)的方法主要應(yīng)用在單標(biāo)簽的數(shù)據(jù)中，但隨著數(shù)據(jù)的日益豐富，單標(biāo)簽已經(jīng)不能再完整地描述一個(gè)樣本的信息，現(xiàn)在往往一條樣本會(huì)對(duì)應(yīng)多個(gè)標(biāo)簽，所以多標(biāo)簽數(shù)據(jù)的分類逐漸的成為數(shù)據(jù)挖掘的一個(gè)重要研究方向。雖然多標(biāo)簽?zāi)軌蚋玫厝ッ枋鲆粋€(gè)樣本的信息，但多標(biāo)簽數(shù)據(jù)通常是那種特征數(shù)目很大的數(shù)據(jù)，對(duì)這樣的數(shù)據(jù)直接進(jìn)行處理很困難，同時(shí)這些高維數(shù)據(jù)往往存在維度災(zāi)難的問題，所以對(duì)多標(biāo)簽數(shù)據(jù)進(jìn)行分類之前做好數(shù)據(jù)的降維對(duì)最終的分類起著不可忽視的作用。提出一種基于采用條件互信息（最小冗余最大依賴準(zhǔn)則，MDMR）來進(jìn)行特征集的選擇，去除無用的特征信息，然后通過一種改進(jìn)的KNN算法對(duì)數(shù)據(jù)進(jìn)行分類，實(shí)驗(yàn)表明這種方法使平均查全率提高2.5％。

單標(biāo)簽；多標(biāo)簽；條件互信息；特征提取；KNN算法

文章編號(hào)：1007-1423（2016）14-0003-07

DOI：10.3969/j.issn.1007-1423.2016.14.001

作者簡(jiǎn)介：

湯文偉（1990-），男，江蘇常州人，碩士，研究方向?yàn)閳D像處理、模式識(shí)別

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

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