錢文彬，黃 琴，王映龍+，楊 珺

1.江西農(nóng)業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，南昌330045

2.江西農(nóng)業(yè)大學(xué) 軟件學(xué)院，南昌330045

+通訊作者E-mail:wangylx@126.com

1 引言

當(dāng)前，在社會生活和科學(xué)研究等各個領(lǐng)域中數(shù)據(jù)呈現(xiàn)爆發(fā)式增長，特別是多標(biāo)記高維數(shù)據(jù)的廣泛存在，傳統(tǒng)的單標(biāo)記分類將一個樣本只歸為某一個標(biāo)記，導(dǎo)致無法描述當(dāng)一個樣本同時屬于多個標(biāo)記的問題，需利用多標(biāo)記分類來描述多標(biāo)記的數(shù)據(jù)資源，對于多標(biāo)記數(shù)據(jù)的分析和挖掘已成為機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域中的重要研究內(nèi)容。近年來，多標(biāo)記分類問題引起了許多學(xué)者的廣泛關(guān)注和深入研究，且已成功應(yīng)用于圖像分類[1-4]、情感分類[5-7]、生物分類[8-10]、文本分類[11-12]等領(lǐng)域。

多標(biāo)記高維數(shù)據(jù)的維數(shù)災(zāi)難問題嚴(yán)重影響多標(biāo)記分類器的分類性能。目前，對于多標(biāo)記數(shù)據(jù)的特征選擇研究取得了一些有意義的研究成果。張振海等[13]使用特征與標(biāo)記集合之間的重要程度來設(shè)置合理的信息增益閾值，并根據(jù)閾值刪除多標(biāo)記數(shù)據(jù)中的不相關(guān)特征。Li 等[14]提出一種新穎的基于經(jīng)典粗糙集的多標(biāo)記屬性約簡算法。Liu等[15]利用特征與標(biāo)記集合間的互信息將特征按其重要度從高到低排序，將特征空間劃分為局部子空間，并根據(jù)采樣比例選擇冗余性小的特征。Lee等[16]設(shè)計(jì)了一種基于可擴(kuò)展標(biāo)準(zhǔn)的多標(biāo)記特征選擇算法，上述多標(biāo)記特征選擇算法主要是面向離散型完備數(shù)據(jù)。但在現(xiàn)實(shí)生活應(yīng)用中存在大量的連續(xù)型多標(biāo)記高維數(shù)據(jù)，若對連續(xù)型數(shù)據(jù)進(jìn)行離散化處理，將可能造成數(shù)據(jù)中信息的損失和增加計(jì)算的復(fù)雜性。

因此，針對多標(biāo)記連續(xù)型數(shù)據(jù)的特征選擇算法引起了眾多學(xué)者的關(guān)注，并取得一些有意義的研究成果。Lee等[17]根據(jù)已選特征與標(biāo)記集合的相關(guān)性，從多變量互信息的角度提出了一種多標(biāo)記特征選擇算法。Yu等[18]根據(jù)互信息和遺傳算法提出一種多標(biāo)記特征選擇算法。Lin等[19]利用實(shí)例邊界域來計(jì)算每個標(biāo)簽下的所有實(shí)例的鄰域粒度以及用三種不同的測量方法來計(jì)算鄰域互信息，在此基礎(chǔ)上，設(shè)計(jì)了一種基于鄰域互信息的多標(biāo)記特征選擇算法。Wang等[20]設(shè)計(jì)了一種基于信息?；亩鄻?biāo)記特征選擇算法。Yang 等[21]通過映射函數(shù)，將高維數(shù)據(jù)映射到低維空間，設(shè)計(jì)出基于共享子空間的多標(biāo)記學(xué)習(xí)方法。以上算法實(shí)現(xiàn)了對多標(biāo)記完備數(shù)據(jù)的特征選擇。而在許多應(yīng)用領(lǐng)域中由于診測成本或隱私保護(hù)等導(dǎo)致數(shù)據(jù)往往呈現(xiàn)不完備性，例如在醫(yī)學(xué)智能診斷系統(tǒng)中，可能存在有些病人，由于經(jīng)濟(jì)條件有限，他們不能做所有的檢查，因此不能獲得這些病人的某些檢查數(shù)據(jù)。目前對于連續(xù)型、不完備性多標(biāo)記高維數(shù)據(jù)下的特征選擇研究相對較少。

為此，本文提出了一種面向多標(biāo)記不完備數(shù)據(jù)的特征選擇算法。首先，在粗糙集模型上采用了兩種不同的距離度量公式計(jì)算多標(biāo)記不完備數(shù)據(jù)下的鄰域粒度，并根據(jù)多標(biāo)記不完備數(shù)據(jù)中特征的標(biāo)準(zhǔn)差和特征參數(shù)計(jì)算出合理的鄰域閾值，其中參數(shù)閾值可根據(jù)標(biāo)準(zhǔn)差計(jì)算。然后，分析了一致性對象特征的重要性，給出了基于特征依賴度準(zhǔn)則的特征重要性度量方法。在此基礎(chǔ)上，根據(jù)特征的重要性排序設(shè)計(jì)了特征選擇算法。最后，利用五個多標(biāo)記分類器在Mulan 數(shù)據(jù)集上對特征選擇結(jié)果進(jìn)行實(shí)驗(yàn)比較和結(jié)果分析，且將本文算法與經(jīng)典粗糙集方法以及基于信息熵的特征選擇算法進(jìn)行實(shí)驗(yàn)對比和分析。實(shí)驗(yàn)結(jié)果表明，不完備鄰域粗糙集模型可直接處理連續(xù)型不完備數(shù)據(jù)，無需對數(shù)據(jù)進(jìn)行填充和離散化，使得該特征選擇算法對數(shù)據(jù)的描述更加客觀合理，為不完備多標(biāo)記高維數(shù)據(jù)的分析和挖掘提供了一種可借鑒的方法。

2 相關(guān)知識

在粒計(jì)算理論中，多標(biāo)記數(shù)據(jù)可表示成一個多標(biāo)記決策表MDT=(U,C?D,V,f)，U為樣本集{x1,x2,…,xn}，也稱為論域，C為條件特征集{c1,c2,…,cm}，D為多標(biāo)記決策特征{l1,l2,…,lk}，且C?D=?。V為全特征集的值域，其中V=?Vc，c∈C?D，Vc表示特征c的值域，f是U×(C?D)→V的信息函數(shù)。

定義1[22]當(dāng)多標(biāo)記決策表中存在缺失值時，記缺失值為“*”，即至少存在c∈C，x∈U，使得f(x,c)=?，此時數(shù)據(jù)稱為多標(biāo)記不完備決策表IMDT=(U,C?D,V,f)。

定義2[22]給定多標(biāo)記不完備決策表IMDT=(U,C?D,V,f)，對于任意特征子集B?C，定義特征子集B的容差關(guān)系T(B)如下：

由定義2 可知，T(B)滿足自反性和對稱性，但不一定滿足傳遞性。在特征子集B下，對象x具有容差關(guān)系的對象集合即在條件特征集下的容差類被定義為TB(x)={xi∈U|(x,xi)∈T(B)}。

定義3[22]給定多標(biāo)記不完備決策表IMDT=(U,C?D,V,f)，對于特征子集B?C所產(chǎn)生的容差類TB(x)，對于ct∈B，若?xi,xj∈TB(x)，有f(xi,D)≠f(xj,D)，則稱特征子集B中產(chǎn)生不一致對象。若B=C，則稱該多標(biāo)記決策表為不一致決策表。

3 問題描述

由于基于粗糙集的粒計(jì)算方法主要是處理名義型或符號型數(shù)據(jù)，但在現(xiàn)實(shí)應(yīng)用領(lǐng)域中多標(biāo)記數(shù)據(jù)的數(shù)值類型往往較復(fù)雜。當(dāng)需處理連續(xù)型數(shù)據(jù)，須先對數(shù)據(jù)進(jìn)行離散化，而對數(shù)據(jù)離散化將可能導(dǎo)致重要的信息丟失，從而影響分類算法的分類性能，為此，需對連續(xù)型數(shù)值的多標(biāo)記不完備數(shù)據(jù)開展特征選擇的研究。

定義4[23]對于N維的實(shí)數(shù)空間Ω中，Δ:RN×RN→R，?xi,xj,xk∈RN，則稱Δ為RN上的一個度量，若Δ滿足以下條件：

Δ(xi,xj)≥0，Δ(xi,xj)=0 當(dāng)且僅當(dāng)xi=xj成立；

其中，(Ω,Δ)為度量空間，Δ(xi,xj)為距離函數(shù)，表示元xi和xj之間的距離：

當(dāng)p=1 時，稱為曼哈頓距離；當(dāng)p=2 時，稱為歐氏距離；當(dāng)p=∞時，稱為切比雪夫距離。

定義5[23]給定實(shí)數(shù)空間上的非空有限集合U={x1,x2,…,xn}，對于任意樣本xi，若有特征子集B?C，則特征子集B上的鄰域粒度為：

其中，δ為鄰域的閾值大小。δB(xi)是由xi生成的δ鄰域信息粒度，簡稱為xi的鄰域粒子。根據(jù)度量的性質(zhì)可得：

（1）δB(xi)≠?，因?yàn)閤i∈δB(xi)；

（2）xj∈δB(xi)?xi∈δB(xj)；

為了直接處理不完備連續(xù)數(shù)據(jù)，而無須對此類數(shù)據(jù)進(jìn)行數(shù)據(jù)補(bǔ)齊或離散化等預(yù)處理，在鄰域關(guān)系的基礎(chǔ)上使用容差鄰域關(guān)系。

定義6對于多標(biāo)記不完備鄰域決策表IMDT=(U,C?D,V,f)，對于任意特征子集B?C，則特征子集B上的容差鄰域關(guān)系記為：

下面以表1為例，若以曼哈頓距離作為鄰域度量標(biāo)準(zhǔn)，根據(jù)定義4計(jì)算各樣本之間的鄰域大小。

利用曼哈頓距離度量公式，若特征c1、c2、c3、c4、c5的鄰域閾值分別為0.18、0.15、0.21、0.22、0.24，根據(jù)定義6 以及表1 中的數(shù)據(jù)可計(jì)算所有樣本的容差鄰域關(guān)系，以KC(x1,x4)的計(jì)算為例：

其中，由于f(x4,c3)=*，在容差鄰域計(jì)算過程中，令f(x4,c3)=f(x1,c3)，由此可知樣本x1、x4為容差鄰域關(guān)系。同理，可計(jì)算所有樣本在特征全集下的容差鄰域關(guān)系。

Table 1 Multi-label incomplete neighborhood decision table表1 多標(biāo)記不完備鄰域決策表

根據(jù)定義5 計(jì)算包含所有特征的每個樣本的鄰域粒度：

同理，可計(jì)算每個特征下每個樣本的鄰域粒度。

定義7在多標(biāo)記不完備鄰域決策表IMDT=(U,C?D,V,f)中，假設(shè)U中包含N個樣本空間，樣本xi對應(yīng)的標(biāo)記集合用yi來表示，N個樣本實(shí)例所對應(yīng)的向量用y=(y1,y2,…,yn)來表示。樣本xi中所對應(yīng)的第k個標(biāo)記值用lk來表示。若lk=1，則將lk標(biāo)記加入yi集合。

以表1為例，根據(jù)定義7可計(jì)算每個xi樣本所對應(yīng)的標(biāo)記集合yi為：

定義8在多標(biāo)記不完備鄰域決策表IMDT=(U,C?D,V,f)中，對于?lk∈D，分別計(jì)算存在標(biāo)記決策lk所對應(yīng)的樣本集合Dk：

其中，[x]lk為在標(biāo)記決策lk下，標(biāo)記決策的值分別為1和0所對應(yīng)的對象集合。

以表1 為例，根據(jù)定義8 可計(jì)算存在標(biāo)記決策lk所對應(yīng)的樣本集合Dk：

定義9[24]在多標(biāo)記不完備鄰域決策表IMDT=(U,C?D,V,f)中，將擁有類別標(biāo)記lk的樣本集合用Dk表示，將樣本xi所具有的標(biāo)記集合用yi來表示。給定B?C，多標(biāo)記不完備鄰域粗糙集的上下近似集為：

由定義9 可知，下近似集與鄰域粒度相關(guān)，且下近似集將隨鄰域粒度的增大而減小。

以表1為例，根據(jù)定義9可計(jì)算特征全集C下的下近似集。具體計(jì)算過程如下：

由于樣本x1所對應(yīng)的標(biāo)記是l1，因此只需判斷δC(x1)?D1是否成立。若成立，則樣本x1在正域范圍。因?yàn)棣腃(x1)={x1,x4}，δC(x1)?D1，所以。同理可得。由此可知特征全集C下的下近似集。

定義10在多標(biāo)記不完備鄰域決策表IMDT=(U,C?D,V,f)，對于特征子集B?C，特征子集B對應(yīng)的正域?yàn)椋?/p>

由定義10 可知，正域?qū)㈦S下近似集的減小而減小。以表1 為例，根據(jù)定義10 可得特征全集C下的正域?yàn)椤?/p>

定義11在多標(biāo)記不完備鄰域決策表IMDT=(U,C?D,V,f)，對于特征子集B?C，特征子集B的特征依賴度為：

由定義11可知，正域與特征依賴度相關(guān)，特征依賴度隨正域的增大而增大。

定義12在多標(biāo)記不完備鄰域決策表IMDT=(U,C?D,V,f)，若特征子集B?C，對于任意特征ct∈C-B，特征ct在特征子集B基礎(chǔ)上相對于決策D的重要度為：

根據(jù)定義12 可知，特征重要度隨特征依賴度的減小而減少。且當(dāng)特征選擇后的特征子集和原特征集的特征依賴度一致或除特征子集外的特征重要度都為0時，說明特征子集外的特征是冗余的。

定義13[23]在多標(biāo)記不完備鄰域決策表IMDT=(U,C?D,V,f)，存在特征子集B?C，若特征子集B是多標(biāo)記不完備鄰域決策表的一個特征選擇結(jié)果，則B需滿足：

（1）γB(D)=γC(D)

（2）?ct∈B,γB-{ct}(D)＜γB(D)

條件（1）使得特征子集B和全特征集C下的正域樣本相同，條件（2）確保了特征子集B中沒有冗余特征。

性質(zhì)1在多標(biāo)記不完備鄰域決策表IMDT=(U,C?D,V,f)，鄰域閾值δ具有單調(diào)性，即若δ1≥δ2，則γδ1(D)≤γδ2(D)。

證明由定義5 可知，若δ1＞δ2，則對于任意的xi∈U，使得δ1(xi)＞δ2(xi)成立。當(dāng)δ1(xi)＞δ2(xi)時，并由定義9可知，使得(δ2(xi)?D)?(δ1(xi)?D)成立，由此可推導(dǎo)出----Nδ1D?----Nδ2D。同理可證，。當(dāng)時，由定義10可推導(dǎo)出POSδ1(D)?POSδ2(D)。由定義11和前面推導(dǎo)可得γδ1(D)≤γδ2(D)。當(dāng)且僅當(dāng)δ1=δ2時，使得POSδ1(D)=POSδ2(D)，γδ1(D)=γδ2(D)成立。□

性質(zhì)2多標(biāo)記不完備鄰域決策表IMDT=(U,C?D,V,f)中，特征子集B?C，當(dāng)?ct∈B，γB-{ct}(D)≤γB(D)，則有：

當(dāng)sig(ct,B,D)＞0 時，可知特征ct相對于特征子集B是必要的。若sig(ct,B,D)=0 時，說明特征ct是冗余特征。

證明由性質(zhì)1 可知，對于任意ct∈B，使得γB-{ct}(D)≤γB(D) 成立，由定義12 可知，當(dāng)γB-{ct}(D)≤γB(D)時，使得sig(ct,B,D)≥0 成立。當(dāng)γB-{ct}(D)=γB(D)，則sig(ct,B,D)=0 成立。由定義13 可知，若sig(ct,B,D)=0成立時，特征ct相對于特征子集B是冗余特征，否則為必要特征。 □

從性質(zhì)1和性質(zhì)2可知，鄰域粒度隨著鄰域閾值δ單調(diào)不減，即當(dāng)鄰域閾值δ越大，鄰域粒度將會越大或不變。

4 特征選擇算法

根據(jù)上述分析可知，針對多標(biāo)記不完備決策表的特征選擇，首先根據(jù)鄰域的閾值計(jì)算多標(biāo)記不完備決策表中每個樣本的鄰域粒度，并計(jì)算每個標(biāo)記特征的樣本集合。在此基礎(chǔ)上，得到多標(biāo)記不完備決策表的正域樣本集合。然后，分別計(jì)算每個條件特征下的鄰域粒度和特征的依賴度，并根據(jù)特征的依賴度計(jì)算特征的重要度，每次將重要度最大的特征加入當(dāng)前的特征子集中，直到特征子集下的正域樣本集合等于全特征集下的正域樣本集合，由此設(shè)計(jì)了一種面向多標(biāo)記不完備決策表的特征選擇算法，算法描述如下：

輸入：多標(biāo)記不完備決策表＜U,C?D,V,f＞，δ為鄰域的閾值。

輸出：特征子集Red。

步驟1初始化Red←?。

步驟2對于?xi∈U，計(jì)算在特征集C下每個樣本的鄰域粒度δC(xi)。

步驟3對于?lk∈D，分別計(jì)算每個標(biāo)記lk下的樣本集合Dk。

步驟4若δC(xi)?Dk，則將樣本xi存入正域POSC(D)←POSC(D)?{xi}。

步驟5對于?cj∈C-Red，執(zhí)行操作：

步驟5.1計(jì)算條件特征集Red?cj下每個樣本的鄰域粒度δRed?cj(xi)；

步 驟5.2對 于 多 標(biāo) 記?lk∈D且lk=1，若δRed?cj(xi)?Dk，則POSRed?cj(D)←POSRed?cj(D)?{xi}；

步驟5.3計(jì)算特征集的依賴度：

步驟5.4若ct=arg max{Sig(cj,Red,D)}，則Red←Red?{ct}，即計(jì)算加入條件特征cj的重要度Sig(cj,Red,D)，選擇重要度最大的條件特征ct存入Red。

步驟6若POSRed(D)≠POSC(D)，則算法轉(zhuǎn)至步驟5，否則執(zhí)行步驟7。

步驟7輸出特征子集Red，算法結(jié)束。

算法的時間復(fù)雜度分析：

算法步驟1 初始化一個變量存放特征選擇后的特征子集，其時間復(fù)雜度為O(1)；算法步驟2 在整個條件特征集下通過樣本之間的比較計(jì)算得到每個樣本的鄰域粒度，其時間復(fù)雜度為O(|C||U|2)；算法步驟3分別計(jì)算每個標(biāo)記決策下的樣本集合，其時間復(fù)雜度為O(|C||D|)；算法步驟4 計(jì)算多標(biāo)記不完備決策表的正域樣本集，其時間復(fù)雜度為O(|U|2+|U||D|)；算法步驟5對多標(biāo)記不完備數(shù)據(jù)進(jìn)行特征選擇，最壞的時間復(fù)雜度為O(|C|2|U|2)；算法步驟6判斷約簡后的特征子集下正域與整個論域的正域是否一致，最壞的時間復(fù)雜度為O(|U|)。綜述分析，算法的時間復(fù)雜度為O(|U|2|C|2)。

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

5.1 數(shù)據(jù)集和性能指標(biāo)

為了驗(yàn)證本文中提出的特征選擇算法的有效性，從Mulan 數(shù)據(jù)集中選取了Emotions、Birds、Yeast和Scenes四個真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)測試和分析。四個數(shù)據(jù)集的相關(guān)信息如表2 所示。本實(shí)驗(yàn)的測試環(huán)境：CPU 為Intel?CoreTMi5-4590s（3.0 GHz），內(nèi)存8.0 GB，算法編程語言為C++和Java，使用的開發(fā)工具分別是Visual studio 2017和Eclipse 4.7。

Table 2 Multi-label datasets表2 多標(biāo)記數(shù)據(jù)集

在實(shí)驗(yàn)測試和分析的過程中，將每個數(shù)據(jù)集的訓(xùn)練樣本和測試樣本相結(jié)合，用隨機(jī)函數(shù)對四個數(shù)據(jù)集進(jìn)行5%的數(shù)據(jù)缺失處理，并采用10 倍交叉驗(yàn)證法對實(shí)驗(yàn)結(jié)果進(jìn)行驗(yàn)證。在實(shí)驗(yàn)過程中，首先分別利用曼哈頓距離和歐式距離兩種度量方法計(jì)算鄰域粒度。在此基礎(chǔ)上，根據(jù)特征重要度對每個數(shù)據(jù)集進(jìn)行特征降維。然后將特征降維后的特征子集通過五種多標(biāo)記分類器（又稱多標(biāo)記分類算法）基于隨機(jī)k標(biāo)記集的多標(biāo)記分類[25]（randomk-label sets，RAkEL）、基于依賴多標(biāo)記k近鄰的多標(biāo)記分類[26]（dependent multi-labelk-nearest neighbor，DMLkNN）、基于實(shí)例的邏輯回歸多標(biāo)記分類[27]（instance-based logistic regression for multi-label classification，IBLRML）、基于二元相關(guān)的k近鄰多標(biāo)記分類[28]（binary relevancek-nearest neighbor，BRkNN）和基于多標(biāo)記k近鄰的多標(biāo)記分類[29]（multi-labelk-nearest neighbor，MLkNN）驗(yàn)證了算法的性能，并從平均分類精度（average precision,AP）、漢明損失（Hamming loss,HL）、覆蓋率（coverage）、1 錯誤率（one error,OE）和排序損失（ranking loss,RL）這五種多標(biāo)記評價性能指標(biāo)評估和對比分類器的分類性能。其中平均分類精度越大越好，漢明損失、覆蓋率、1錯誤率、排序損失越小越好。

5.2 λ 特征參數(shù)的分析

對于多標(biāo)記不完備鄰域決策表，鄰域參數(shù)的選擇直接關(guān)系到特征選擇的結(jié)果和分類器的分類性能。為此，在曼哈頓距離的度量方法中，鄰域參數(shù)的計(jì)算方式為δ=stdai/λ，其中stdai為通過本文算法進(jìn)行特征選擇之后的每個特征的標(biāo)準(zhǔn)差。歐氏距離度量的鄰域參數(shù)計(jì)算方式為δ=(stdan/n)/λ，其中stdan/n是通過本文算法進(jìn)行特征選擇之后的所有特征的平均標(biāo)準(zhǔn)差。由于每個數(shù)據(jù)集在不同的距離度量方法下其特征值的標(biāo)準(zhǔn)差是固定的，λ的取值直接關(guān)系到鄰域參數(shù)δ的值[30]。通過實(shí)驗(yàn)分析發(fā)現(xiàn)，λ的取值范圍從0.1到2.0的特征選擇結(jié)果所對應(yīng)的分類性能較好。為了詳細(xì)分析λ值對特征選擇結(jié)果和分類器的分類性能影響，在實(shí)驗(yàn)過程中將λ值每次變化0.1進(jìn)行實(shí)驗(yàn)分析和結(jié)果對比。

下面將以scene 數(shù)據(jù)集為例，詳細(xì)分析在曼哈頓距離和歐氏距離這兩種度量標(biāo)準(zhǔn)下λ（在圖中用Lambda 表示λ）變化對于特征選擇的個數(shù)和分類器的分類性能影響，實(shí)驗(yàn)結(jié)果如圖1和圖2所示。

由圖1可知，對于scene數(shù)據(jù)集來說，在曼哈頓距離度量標(biāo)準(zhǔn)下，由圖1（a）可知,當(dāng)λ=0.1 時，本文算法將特征個數(shù)由294 減少至4 個，但5 個分類器的平均分類精度較低；當(dāng)λ的取值為0.3～0.4 時，5 個分類器的平均分類精度的上升趨勢顯著，由圖1（b）可得，漢明損失在這個區(qū)間的變化趨勢較為平緩，由圖1（c）、（d）和（e）可看出，5個分類器的覆蓋率、1錯誤率和排序損失的值都呈下降趨勢。當(dāng)λ的取值在0.4～0.9時，特征選擇的個數(shù)下降明顯，5個分類器的平均分類精度、漢明損失、覆蓋率、1 錯誤率、排序損失的值較好。當(dāng)λ的取值在1.0～2.0 之間，由圖1（a）的變化曲線發(fā)現(xiàn)特征選擇的個數(shù)和5 個分類器的平均分類精度變化并不明顯，且由圖1（b）、（c）、（d）和（e）對應(yīng)的漢明損失、覆蓋率、1錯誤率、排序損失的值呈現(xiàn)出平緩上升。

Fig.1 Size of feature selection and classification performance with varying λ under Manhattan distance圖1 曼哈頓距離度量下特征選擇的個數(shù)和分類性能隨λ 值的變化

Fig.2 Size of feature selection and classification performance with varying λ under Euclidean distance圖2 歐氏距離度量下特征選擇的個數(shù)和分類性能隨λ 值的變化

由圖2 可知，在歐氏距離度量標(biāo)準(zhǔn)下，當(dāng)λ的值在0.1～1.0范圍內(nèi)，特征選擇個數(shù)隨λ單調(diào)遞減，且分類器的平均分類精度也呈現(xiàn)遞減趨勢。由圖2（a）中曲線的變化趨勢可知，5個分類器的平均精度明顯下降，而由（b）、（c）、（d）和（e）中的曲線變化可知，漢明損失、覆蓋率、1錯誤率和排序損失的值都呈上升趨勢。其中，當(dāng)λ=1.0時，特征選擇的效果最優(yōu)，特征個數(shù)由原有的294 減少至50。當(dāng)λ=0.6 時，5 個分類器的平均分類精度、漢明損失、覆蓋率、1 錯誤率、排序損失的值較優(yōu)。當(dāng)λ的取值在1.2～2.0 時，隨著特征選擇的個數(shù)增加，由（a）可知，5個分類器的平均分類精度得到明顯改善，且由圖2（b）、（c）、（d）和（e）對應(yīng)的漢明損失、覆蓋率、1錯誤率、排序損失的值也越來越小。

另外，將圖1 和圖2 進(jìn)行對比可以發(fā)現(xiàn)，平均精度、漢明損失、覆蓋率、1 錯誤率和排序損失在圖1 中的變化區(qū)間分別約為40%、10%、180%、60%和35%，而在圖2 中分別約為26%、7%、110%、35%和22%。通過數(shù)值對比發(fā)現(xiàn)，圖1中的5種多標(biāo)記分類器的分類性能的變化幅度趨勢大于圖2，由此可得，以歐氏距離作為鄰域度量標(biāo)準(zhǔn)與以曼哈頓距離作為鄰域度量標(biāo)準(zhǔn)相比，降維后的特征子集分類性能的穩(wěn)定性更好。

綜上可知，以scene數(shù)據(jù)集為例，把歐氏距離作為鄰域度量標(biāo)準(zhǔn)，算法的特征選擇效果較好，且5 個分類器的分類性能也都較優(yōu)。且從特征降維的效果及分類器的5個性能指標(biāo)來看，對于scene數(shù)據(jù)集，在曼哈頓度量標(biāo)準(zhǔn)下λ的取值為0.9較優(yōu)，在歐氏距離度量標(biāo)準(zhǔn)下λ的取值為0.6較好。

同時通過確定λ特征參數(shù)的實(shí)驗(yàn)可知，當(dāng)λ的值越大，則δ鄰域閾值將會越小，鄰域粒度也越小。此時，多標(biāo)記鄰域數(shù)據(jù)的下近似集將隨鄰域粒度的減小而增大，正域中的對象將隨下近似集的增大而增大，特征依賴度也隨正域的增大而變大。

5.3 實(shí)驗(yàn)比較與分析

為進(jìn)一步驗(yàn)證本文算法的有效性，下面將以RAkEL 分類器為例，將兩種距離度量標(biāo)準(zhǔn)下的本文算法與MLFSIE（multi-label feature selection based on information entropy）[17]、MLFSPA（multi-label feature selection based on positve approximation）[31]和MLFSDM（multi-label feature selection based on discernibility matrix）[32]這3種算法對4個數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)分析和對比。其中，MLFSIE是基于信息熵的多標(biāo)記特征選擇算法，MLFSPA是本文對數(shù)據(jù)離散化后基于正區(qū)域思想改造的多標(biāo)記特征選擇算法，MLFSDM 是本文對數(shù)據(jù)離散化后基于差別矩陣思想改造的多標(biāo)記特征選擇算法。Manhattan distance 和Euclidean distance分別表示本文算法使用曼哈頓距離方法和歐氏距離方法作為鄰域度量標(biāo)準(zhǔn)時，根據(jù)特征重要度進(jìn)行特征降維后，所獲得的特征子集的分類性能。另外，由于上述4 個數(shù)據(jù)集的特征值均是連續(xù)型數(shù)據(jù)，但MLFSIE、MLFSPA 和MLFSDM 算法處理的是離散型數(shù)據(jù)，因此在實(shí)驗(yàn)中需先利用等距離散化方法對4 個數(shù)據(jù)集進(jìn)行離散化處理。實(shí)驗(yàn)結(jié)果如表3～表6 所示，加粗字體表示所對應(yīng)數(shù)據(jù)集及5 個性能指標(biāo)下算法的最優(yōu)值。

從表3～表6 中的5 項(xiàng)多標(biāo)記分類性能指標(biāo)實(shí)驗(yàn)結(jié)果可知，與其他3 種算法相比，本文算法的分類性能總體較優(yōu)。另外，在RAkEL分類器下，鄰域度量方法使用歐氏距離度量方法時得到的降維后的特征子集的分類性能總體優(yōu)于使用曼哈頓距離度量方法。

由表3的實(shí)驗(yàn)結(jié)果可知，針對Yeast數(shù)據(jù)集，使用本文算法降維后的特征子集的分類性能優(yōu)于其他3種算法。例如，其在兩種度量方法下AP的均值分別比MLFSIE、MLFSPA 和MLFSDM 算 法 提 高 了2.05%、0.55%和2.50%，且HL、Coverage、OE 和RL 的均值也明顯低于其他3 種算法。此外，在Yeast 數(shù)據(jù)集中，兩種鄰域度量方法的Coverage 和RL 值相等，且其AP 的值也僅相差0.000 1 的方差。由此可知，RAkEL分類器的分類性能與鄰域度量方法的相關(guān)性較小。

Table 3 Comparison of experiments in Yeast dataset表3 Yeast數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果對比

Table 4 Comparison of experiments in Emotions dataset表4 Emotions數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果對比

Table 5 Comparison of experiments in Scenes dataset表5 Scenes數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果對比

Table 6 Comparison of experiments in Birds dataset表6 Birds數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果對比

由表4中Emotions數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果可得，使用本文算法降維后的特征子集的分類性能顯著優(yōu)于其他3 種算法，其中分類性能差值最大的是MLFSIE算法。以曼哈頓距離度量方法的本文算法與MLFSIE算法在五大性能指標(biāo)的比較為例，其AP的值提高了15.45%，且HL、Coverage、OE 和RL 的值也分別降低了12.41%、81.07%、24.79%和17.72%。另外，在曼哈頓距離度量方法下，HL、Coverage和RL的值較優(yōu)，在歐氏距離度量方法下，AP和OE的值更優(yōu)。

從表5中Scenes數(shù)據(jù)集的實(shí)驗(yàn)對比結(jié)果可得，該數(shù)據(jù)集適用于使用歐氏距離作為鄰域度量標(biāo)準(zhǔn)。同時，將本文算法與其他3 種算法相比，與其分類性能最為相近的是MLFSPA算法，其AP、HL、OE和RL的差值都相對較小，分別為1.57%、0.83%、1.45%和1.61%，相差較為明顯的是Coverage，其差值為8.52%。

由表6可看出，在Birds數(shù)據(jù)集中，分類性能較優(yōu)的是MLFSDM算法，其AP的值最優(yōu)，為61.64%。將MLFSDM 算法與歐氏距離度量方法的本文算法相比，其AP、Coverage、OE 和RL 的值相對較優(yōu)，但其HL值在本文算法更優(yōu)；同時通過實(shí)驗(yàn)的結(jié)果可發(fā)現(xiàn)，利用歐氏距離的度量方法要優(yōu)于曼哈頓距離的度量方法，其中最為明顯的兩個指標(biāo)分別為AP 和Coverage，差值分別為4.45%和36.39%。本文算法與MLFSDM 算法相比，其降維后的特征子集的分類性能相對較差，本文算法與MLFSIE、MLFSPA 這兩種算法相比，本文算法效果較優(yōu)。

綜上所述，將本文算法與3種不同的多標(biāo)記特征選擇算法在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對比和分析可知，本文算法總體上提高了分類器的分類性能。為此，本文研究結(jié)果為多標(biāo)記不完備數(shù)值數(shù)據(jù)的處理和分析提供了一種可借鑒的分析方法。

6 結(jié)束語

由于數(shù)據(jù)存在獲取限制、理解有誤和數(shù)據(jù)遺漏等問題，且在生活中連續(xù)型數(shù)據(jù)往往較多，為此針對多標(biāo)記數(shù)據(jù)中存在缺失值和連續(xù)值的問題，提出了一種面向不完備特征鄰域決策表的多標(biāo)記特征選擇算法。算法無需對缺失數(shù)據(jù)進(jìn)行填充，且可直接處理連續(xù)型數(shù)據(jù)。通過兩種不同的距離度量標(biāo)準(zhǔn)對不完備特征鄰域決策表進(jìn)行鄰域?；?，在此基礎(chǔ)上設(shè)計(jì)了特征的重要性度量方法，并采用啟發(fā)式搜索策略對多標(biāo)記不完備決策表進(jìn)行特征選擇。通過不同的多標(biāo)記分類器對算法進(jìn)行實(shí)驗(yàn)以及與3 種經(jīng)典的多標(biāo)記特征選擇算法對比分析說明了本文算法的有效性。由于現(xiàn)實(shí)生活中許多復(fù)雜問題的不同標(biāo)記之間存在相關(guān)性，下一步工作將研究復(fù)雜數(shù)據(jù)中多標(biāo)記之間的相關(guān)性問題。