黃 琴，錢(qián)文彬，王映龍，吳兵龍

(江西農(nóng)業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，南昌 330045)(江西省高等學(xué)校農(nóng)業(yè)信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，南昌 330045)

1 引 言

由于在許多現(xiàn)實(shí)應(yīng)用領(lǐng)域中，數(shù)據(jù)特征值的獲取通常是需要花費(fèi)金錢(qián)、時(shí)間或其他資源作為代價(jià)成本，因此，將代價(jià)引入到數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)領(lǐng)域是顯得尤為必要.近年來(lái)，代價(jià)敏感學(xué)習(xí)問(wèn)題作為數(shù)據(jù)挖掘領(lǐng)域的十大最具挑戰(zhàn)性問(wèn)題之一[1]，已受到越來(lái)越多研究者的關(guān)注，并被廣泛應(yīng)用于醫(yī)學(xué)[2，3]、模式識(shí)別[4]、人臉識(shí)別[5-8]等各個(gè)研究領(lǐng)域.另外，特征選擇作為一種有效的數(shù)據(jù)降維方法[9-12]，其目的是通過(guò)去除冗余特征，提高數(shù)據(jù)的質(zhì)量，加快數(shù)據(jù)挖掘的速度.由于基于代價(jià)敏感的特征選擇算法是對(duì)特征選擇問(wèn)題的擴(kuò)展，從而基于代價(jià)敏感的特征選擇問(wèn)題也受到了廣大研究者的關(guān)注.

近年來(lái)，基于代價(jià)敏感學(xué)習(xí)的單標(biāo)記特征選擇研究取得了一些有意義的成果.Li等[13]在C4.5算法的基礎(chǔ)上提出了基于兩種自適應(yīng)機(jī)制的代價(jià)敏感決策樹(shù)算法，一種是選擇自適應(yīng)分割點(diǎn)機(jī)制來(lái)構(gòu)建分類器，另一種機(jī)制即自適應(yīng)刪除屬性機(jī)制，在選擇節(jié)點(diǎn)的過(guò)程中刪除冗余屬性.Zhao等[14]用啟發(fā)式算法選擇結(jié)點(diǎn)中的屬性，并構(gòu)造了一種基于加權(quán)類分布批量刪除屬性機(jī)制的代價(jià)敏感決策樹(shù)算法.Zhao等[15]通過(guò)自適應(yīng)鄰域粗糙集模型和快速回溯算法構(gòu)造了一種基于自適應(yīng)鄰域粒度的多級(jí)置信度的代價(jià)敏感特征選擇算法.Zhou等[16]提出基于均勻森林的代價(jià)敏感特征選擇算法，其在構(gòu)建基礎(chǔ)決策樹(shù)過(guò)程中結(jié)合特征代價(jià)，從而生成低代價(jià)的特征子集.Fan等[17]通過(guò)測(cè)試代價(jià)構(gòu)造自適應(yīng)鄰域模型，從而實(shí)現(xiàn)對(duì)異構(gòu)數(shù)據(jù)的屬性約簡(jiǎn).Zhao等[18]提出不同粒度下對(duì)應(yīng)不同置信水平相關(guān)的數(shù)據(jù)精度，在覆蓋粗糙集模型下設(shè)計(jì)一種基于置信水平的代價(jià)敏感屬性選擇.Min等[19]提出了一種基于啟發(fā)式算法的最小化測(cè)試代價(jià)屬性約簡(jiǎn)方法，并用四種度量方法來(lái)評(píng)價(jià)約簡(jiǎn)算法的性能指標(biāo).Min等[20]提出基于測(cè)試代價(jià)約束問(wèn)題的特征選擇算法，并用回溯法和啟發(fā)式算法進(jìn)行分析.Liu等[21]通過(guò)優(yōu)化F-measures函數(shù)，解決不平衡類問(wèn)題，實(shí)現(xiàn)基于測(cè)試代價(jià)的特征選擇的算法.Dai等[22]在有效的索引能力的基礎(chǔ)上，提出了一種基于離散粒子群算法在測(cè)試代價(jià)敏感屬性約簡(jiǎn)中的應(yīng)用.

上述基于代價(jià)敏感的特征選擇算法研究主要面向單標(biāo)記分類問(wèn)題，但由于多標(biāo)記高維數(shù)據(jù)廣泛存在于社會(huì)生活中[23-25].由此，在代價(jià)敏感學(xué)習(xí)下對(duì)多標(biāo)記高維數(shù)據(jù)進(jìn)行特征選擇值得進(jìn)一步研究.同時(shí)，在現(xiàn)實(shí)生活應(yīng)用存在大量的連續(xù)型、不完備性多標(biāo)記高維數(shù)據(jù).若需對(duì)連續(xù)型數(shù)據(jù)進(jìn)行離散化處理以及缺失數(shù)據(jù)進(jìn)行填充處理，將會(huì)影響數(shù)據(jù)計(jì)算的精度和增加數(shù)據(jù)計(jì)算的復(fù)雜性.

為此，本文提出了一種面向代價(jià)敏感的多標(biāo)記不完備鄰域數(shù)據(jù)特征選擇算法，首先，算法在粗糙集模型上通過(guò)距離度量公式計(jì)算多標(biāo)記不完備數(shù)據(jù)下的鄰域粒度，并根據(jù)多標(biāo)記不完備數(shù)中特征的標(biāo)準(zhǔn)差和特征參數(shù)計(jì)算出合理的鄰域閾值，然后，通過(guò)均勻分布和正態(tài)分布為每個(gè)特征生成特征代價(jià)，在特征選擇過(guò)程中，根據(jù)歸一化后的正域和特征代價(jià)，提出了一種度量特征的重要性計(jì)算方法，并在特征核的基礎(chǔ)上，根據(jù)特征的重要性設(shè)計(jì)了啟發(fā)式的特征選擇算法；最后，在Mulan數(shù)據(jù)集上利用五個(gè)多標(biāo)記分類器對(duì)考慮代價(jià)和不考慮代價(jià)的多標(biāo)記特征選擇進(jìn)行實(shí)驗(yàn)比較和結(jié)果分析，實(shí)驗(yàn)結(jié)果表明，本文算法解決了多標(biāo)記連續(xù)型不完備數(shù)據(jù)在考慮代價(jià)情況下的特征選擇問(wèn)題，可選擇出代價(jià)總和相對(duì)較低的特征子集，這為基于代價(jià)敏感的多標(biāo)記不完備高維數(shù)據(jù)的分析提供了一種可借鑒的方法.

2 相關(guān)知識(shí)

在粒計(jì)算理論中，多標(biāo)記數(shù)據(jù)可表示成一個(gè)多標(biāo)記決策表MDT=(U，A∪D，V，f)中，U為對(duì)象集{x1，x2，…，xn}，也稱為論域，A為條件特征集{a1，a2，…，am}，D為多標(biāo)記決策特征{l1，l2，…，lk}，且A∩D=?.V為全特征集的值域，其中V=∪Va，a∈A∪D，Va表示特征a的值域，f是U×(A∪D)→V的信息函數(shù).

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

定義2.給定多標(biāo)記不完備決策表IMDT=(U，A∪D，V，f)，對(duì)于任意特征子集B?A，定義特征子集B的容差關(guān)系T(B)：

T(B)={(xi，xj)|(xi，xj)∈U×U，?at∈B?f(xi，at)=f(xj，at)∨f(xi，at)=*∨f(xj，at)=*}

定義3.對(duì)于N維的實(shí)數(shù)空間Ω中，Δ=RN×RN→R，?xi，xj∈RN，則稱Δ為RN上的一個(gè)度量，(Ω，Δ)為度量空間，Δ(xi，xj)為距離函數(shù)，表示元xi和xj之間的距離：

當(dāng)p=1時(shí)，稱為曼哈頓距離.當(dāng)p=2時(shí)，稱為歐氏距離.

3 問(wèn)題描述

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

定義4.[26]對(duì)于多標(biāo)記不完備鄰域決策表IMDT=(U，A∪D，V，f)，若有特征子集B?A，特征子集B上的鄰域粒度為

δB(xi)={x|x∈U，Δ(x，xi)≤δ}

其中，δ為鄰域的閾值大小.

下面以表1為例，若以曼哈頓距離作為鄰域度量標(biāo)準(zhǔn)，根據(jù)定義3計(jì)算各對(duì)象之間的鄰域粒度.

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

利用曼哈頓距離度量公式，若特征a1、a2、a3、a4、a5的鄰域閾值分別為0.21、0.22、0.24、0.18、0.15.根據(jù)定義4計(jì)算包含所有特征的每個(gè)對(duì)象的鄰域粒度：

δA(x1)={x1，x8}，δA(x2)={x2，x10}，

δA(x3)={x3，x5，x8}，δA(x4)={x4}，

δA(x5)={x3，x5，x7,x8}，δA(x6)={x6}，

δA(x7)={x5，x7}，δA(x8)={x1，x3，x5,x8}，

δA(x9)={x9}，δA(x10)={x2，x10}.

同理，可計(jì)算每個(gè)特征下每個(gè)對(duì)象的鄰域粒度.

定義5.在多標(biāo)記不完備鄰域決策表IMDT=(U，A∪D，V，f)中，假設(shè)U中包含N個(gè)對(duì)象空間，對(duì)象xi對(duì)應(yīng)的標(biāo)記集合用yi來(lái)表示，N個(gè)對(duì)象實(shí)例所對(duì)應(yīng)的向量用y=(y1，y2，…，yn)來(lái)表示.對(duì)象xi中所對(duì)應(yīng)的第k個(gè)標(biāo)記值用lk來(lái)表示，若lk=1，則表示yi集合中所對(duì)應(yīng)的存在第lk個(gè)標(biāo)記.

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

y1={l2}，y2={l1}，y3={l2}，y4={l1，l2，l3}，y5={l1，l3}，y6={l2，l3}，y7={l1，l2，l3}，y8={l1，l2，l3}，y9={l1，l2}，y10={l3}.

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

Dk={[x]lk|x∈U}

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

D1={x2，x4，x5，x7，x8，x9}

D2={x1，x3，x4，x6，x7，x8，x9}

D3={x4，x5，x6，x7，x8，x10}

定義7.在多標(biāo)記不完備鄰域決策表IMDT=(U，A∪D，V，f)中，將擁有類別標(biāo)記lk的對(duì)象集合用Dk表示，將對(duì)象xi所具有的標(biāo)記集合用yi來(lái)表示.給定B?C，多標(biāo)記不完備鄰域粗糙集的上下近似集為：

定義8.在多標(biāo)記不完備鄰域決策表IMDT=(U，A∪D，V，f)，有特征子集B?A，特征子集B上的正域?yàn)椋?/p>

以表1為例，根據(jù)定義7和定義8可計(jì)算特征集A下的正域.具體的計(jì)算過(guò)程如下：

由于對(duì)象x1所對(duì)應(yīng)的標(biāo)記是l1，所以只需判斷δA(x1)?D2是否成立，若成立，則對(duì)象x1在正域范圍.因?yàn)棣腁(x1)={x1，x8}，δA(x1)?D2，所以x1∈POSA(D).同理可得x4∈POSA(D)，x6∈POSA(D)， x9∈POSA(D).由此可知，POSA(D)={x1，x4，x6，x9}.

定義9.在多標(biāo)記不完備鄰域決策表IMDT=(U，A∪D，V，f)中，多標(biāo)記不完備鄰域決策表基于正區(qū)域核的定義為：

Core(A)={a|a∈A，POSA-{a}(D)≠POSA(D)}

以表1為例，根據(jù)定義9可計(jì)算出特征集A下的核，由計(jì)算可知：POSA-{a5}(D)≠POSA(D)；由此可知，特征a5為核即Core(A)={a5}.

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

定義11.在多標(biāo)記不完備鄰域決策表IMDT=(U，A∪D，V，f)，特征子集B?A，若特征子集B是多標(biāo)記不完備鄰域決策表的一個(gè)特征選擇結(jié)果，則B需滿足：

1)γB(D)=γA(D)

2)?at∈B，γB-{at}(D)<γB(D)

條件1)確保了特征子集B和全特征集A下的正域?qū)ο笙嗤?，條件2)確保了特征子集B中沒(méi)有冗余特征.

當(dāng)前，由于在許多現(xiàn)實(shí)應(yīng)用領(lǐng)域中，數(shù)據(jù)特征值的獲取通常是需要花費(fèi)金錢(qián)、時(shí)間或其他資源作為代價(jià)成本，為此，基于代價(jià)敏感下多標(biāo)記不完備鄰域數(shù)據(jù)的特征選擇問(wèn)題值得進(jìn)一步研究.

定義12.當(dāng)多標(biāo)記不完備鄰域決策表中的特征需要考慮代價(jià)時(shí)，則稱該決策表為基于代價(jià)敏感的多標(biāo)記不完備鄰域決策表，其定義為：CIMDT=(U，A∪D，V，f，c)，c：A→R+∪{0}是獨(dú)立測(cè)試代價(jià)函數(shù)，其中代價(jià)為非負(fù)數(shù).

以表1為例，可給出多標(biāo)記不完備鄰域決策表的測(cè)試代價(jià)向量，如表2所示.

表2 測(cè)試代價(jià)向量表Table 2 Vector of test cost table

性質(zhì)1.基于代價(jià)敏感的多標(biāo)記不完備鄰域決策表CIMDT=(U，A∪D，V，f，c)，特征子集B?A，對(duì)于任意特征at，ai∈A-B，則基于測(cè)試代價(jià)的特征at的重要度為：

SIGcost(at，B，D)=POSB∪{at}(D)*-CostB∪{at}(D)*

為了方便性質(zhì)1中對(duì)測(cè)試代價(jià)的特征at的重要度計(jì)算，先需對(duì)基于特征子集的正域個(gè)數(shù)和測(cè)試代價(jià)分別進(jìn)行歸一化處理：

POSB∪{at}(D)*=

CostB∪{at}(D)*=

其中max(|POSB∪{ai}(D)|)、min(|POSB∪{ai}(D)|)分別為特征子集B中加入任意特征后的最大和最小正域個(gè)數(shù)，max(CostB∪{ai}(D))、min(CostB∪{ai}(D))分別為特征子集B中加入任意特征后所對(duì)應(yīng)的最大代價(jià)和最小代價(jià).

由定義9可知，特征a5為核，因此，先將a5加入到特征子集B中，結(jié)合表1和表2 中的數(shù)據(jù)計(jì)算出特征a1、a2、a3、a4基于測(cè)試代價(jià)的特征重要度分別為：

SIGcost(a1，B，D)=0.7；

SIGcost(a2，B，D)=0.85；

SIGcost(a3，B，D)=0.25；

SIGcost(a4，B，D)=-0.2；

由上面計(jì)算可知，特征a2的特征重要度最大，由此將a2加入到特征子集B中，通過(guò)計(jì)算可知，此時(shí)POSB(D)=POSA(D)，則特征子集B={a2，a5}，結(jié)合表2中給出的代價(jià)可知，此時(shí)特征子集B所需花費(fèi)的測(cè)試代價(jià)是＄18，而整個(gè)特征全集下的測(cè)試代價(jià)為＄52.

4 特征選擇算法

根據(jù)上述分析可知，針對(duì)代價(jià)敏感的多標(biāo)記不完備鄰域決策表的特征選擇算法，首先，采用均勻分布和正態(tài)分布兩種分布函數(shù)分別為每個(gè)特征生成特征代價(jià)，根據(jù)鄰域的閾值計(jì)算基于代價(jià)敏感的多標(biāo)記不完備鄰域決策表中每個(gè)對(duì)象的鄰域粒度，在此基礎(chǔ)上，得到基于代價(jià)敏感的多標(biāo)記不完備鄰域決策表的正域?qū)ο蠹?然后，根據(jù)基于測(cè)試代價(jià)特征的重要度計(jì)算公式計(jì)算除特征核之外的每個(gè)條件特征的重要度，每次將特征重要度最大的特征加入當(dāng)前的特征子集中并更新特征子集中正域?qū)ο蠹?，直到特征子集下的正域?qū)ο蠹系扔谌卣骷碌恼驅(qū)ο蠹纱嗽O(shè)計(jì)了一種面向基于代價(jià)敏感多標(biāo)記不完備鄰域決策表的特征選擇算法，算法描述如下：

輸入：基于代價(jià)敏感的多標(biāo)記不完備鄰域決策表，δ為鄰域的閾值.

輸出：特征子集Red.

Begin：

Step1.初始化Red←?;

Step2.對(duì)于?xi∈U，計(jì)算在特征集A下每個(gè)對(duì)象的鄰域粒度δA(xi)；

Step3.對(duì)于?lk∈D，分別計(jì)算每個(gè)標(biāo)記lk下的對(duì)象集合Dk；

Step4.若δA(xi)?Dk，則將對(duì)象xi存入正域POSA(D)←POSA(D)∪{xi}；

Step5.對(duì)于?aj∈A，分別計(jì)算去除每個(gè)特征之后對(duì)象的正域集合POSA-{aj}(D)，若POSA-{aj}(D)≠POSA(D)，則將特征aj存入Red， 算法轉(zhuǎn)至Step7；

Step6.對(duì)于?aj∈A-Red，執(zhí)行操作：

Step6.1.計(jì)算條件特征集Red∪aj下每個(gè)對(duì)象的鄰域粒度δRed∪aj(xi)；

Step6.2.對(duì)于多標(biāo)記?lk∈D且lk=1，若δRed∪aj(xi)?Dk，則POSRed∪aj(D)←POSRed∪aj(D)∪{xi}；

Step6.3.若at=argmax{SIGCos t(aj，c，D)}，則Red←Red∪{at}，即計(jì)算加入條件特征aj的重要度SIGCos t(aj，c，D)， 選擇重要度最大的條件特征at存入Red；

Step7.若POSRed(D)≠POSA(D)，則算法轉(zhuǎn)至Step6，否則執(zhí)行Step8；

Step8.輸出特征子集Red，算法結(jié)束；

End

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

算法Step1初始化一個(gè)變量存放特征選擇后的特征子集，其時(shí)間復(fù)雜度為O(1)；算法Step2在整個(gè)條件特征集下通過(guò)對(duì)象之間的比較計(jì)算得到每個(gè)對(duì)象的鄰域粒度，其時(shí)間復(fù)雜度為O(|C‖U|2)；算法Step3分別計(jì)算每個(gè)標(biāo)記決策下的對(duì)象集合，其時(shí)間復(fù)雜度為O(|C‖D|)；算法Step4計(jì)算多標(biāo)記不完備決策表的正域?qū)ο蠹?，其時(shí)間復(fù)雜度為O(|U|2+|U‖D|)；算法Step5計(jì)算特征核的時(shí)間復(fù)雜度為O(|C|)；算法Step6對(duì)加入的新特征后的特征子集正域集合更新，實(shí)現(xiàn)對(duì)基于代價(jià)敏感的多標(biāo)記不完備數(shù)據(jù)的特征選擇，最壞的時(shí)間復(fù)雜度為O(|C‖U|)；算法Step7判斷約簡(jiǎn)后的特征子集下正域與整個(gè)論域的正域是否一致，最壞的時(shí)間復(fù)雜度為O(|U|).綜述分析，本文算法的時(shí)間復(fù)雜度為O(|C‖U|2).

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

5.1 數(shù)據(jù)集及實(shí)驗(yàn)設(shè)置

為了驗(yàn)證本文中所提出的基于代價(jià)敏感多標(biāo)記不完備數(shù)據(jù)特征選擇算法的有效性，從Mulan數(shù)據(jù)集中選取了yeast、emotions、scenes、birds 4個(gè)真實(shí)數(shù)據(jù)集，并分別用均勻分布(Uniform Distribution)和正態(tài)分布(Normal Distribution)兩種分布函數(shù)(Cumulative Distribution Function，記為CDF)分別為這4個(gè)數(shù)據(jù)集生成測(cè)試代價(jià)，在對(duì)基于測(cè)試代價(jià)的多標(biāo)記數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)測(cè)試和分析，均勻分布的均勻數(shù)取值在0～100之間，正態(tài)分布以100為期望值，以30為標(biāo)準(zhǔn)差，4個(gè)數(shù)據(jù)集的相關(guān)信息和不同分布函數(shù)下4個(gè)數(shù)據(jù)集所對(duì)應(yīng)的測(cè)試總代價(jià)分別如表3、表4所示.

本次實(shí)驗(yàn)的硬件配置為CPU為Inter(R)Core(TM)i5-4590s(3.0GHz)，內(nèi)存8.0GB.設(shè)計(jì)算法所使用的編程語(yǔ)言為Python和Java，使用的開(kāi)發(fā)工具分別是記事本和Eclipse 4.7.

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

表4 數(shù)據(jù)集總測(cè)試代價(jià)表Table 4 Cost of multi-label datasets table

5.2 性能指標(biāo)

1)代價(jià)約簡(jiǎn)率是考慮特征代價(jià)的特征子集B的代價(jià)占全特征集A總代價(jià)的比率：

2)平均精度是指在標(biāo)記預(yù)測(cè)序列中，排在相關(guān)標(biāo)記之前的標(biāo)記仍是相關(guān)標(biāo)記的比率：

3)漢明損失是指預(yù)測(cè)出的標(biāo)記與實(shí)際標(biāo)記的平均差異值：

其中Δ為Yi、Zi兩個(gè)集合之間的對(duì)稱差.

4)覆蓋率是指所有對(duì)象實(shí)際包含的所有標(biāo)記所需最大的排序距離：

5)1錯(cuò)誤率是指預(yù)測(cè)出的標(biāo)記排序最靠前的標(biāo)記不在實(shí)際對(duì)象中的比率：

6)排序損失是指預(yù)測(cè)出的標(biāo)記中實(shí)際不包含的標(biāo)記比實(shí)際包含的標(biāo)記排序高的比率：

其中平均分類精度越大越好，漢明損失、覆蓋率、1錯(cuò)誤率、排序損失越小越好.

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

由于文中的多標(biāo)記數(shù)據(jù)特征選擇算法是基于代價(jià)敏感的，所以在進(jìn)行實(shí)驗(yàn)測(cè)試之前，需先用均勻分布和正態(tài)分布兩種分布函數(shù)分別為以上4個(gè)數(shù)據(jù)集的特征生成測(cè)試代價(jià)，通過(guò)比較基于不同分布函數(shù)的特征代價(jià)來(lái)評(píng)價(jià)測(cè)試代價(jià)對(duì)多標(biāo)記數(shù)據(jù)特征選擇算法的影響.同時(shí)，文中研究的是不完備數(shù)據(jù)，因此，需用均勻函數(shù)對(duì)以上4個(gè)數(shù)據(jù)集進(jìn)行5%的數(shù)據(jù)缺失處理.在實(shí)驗(yàn)測(cè)試和分析的過(guò)程中，為了避免實(shí)驗(yàn)結(jié)果的均勻性，采用10倍交叉驗(yàn)證法對(duì)每個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果進(jìn)行驗(yàn)證.在實(shí)驗(yàn)過(guò)程中，首先利用曼哈頓距離度量方法計(jì)算鄰域粒度，同時(shí)，在特征核的基礎(chǔ)上，對(duì)每個(gè)數(shù)據(jù)集進(jìn)行特征選擇.然后比較考慮代價(jià)和不考慮代價(jià)特征選擇的結(jié)果，通過(guò)5種多標(biāo)記分類器(RAkEL、DMLkNN、IBLR_ML、BRkNN、MLkNN)驗(yàn)證了算法的性能，且通過(guò)多標(biāo)記的五大評(píng)價(jià)性能指標(biāo)評(píng)估和對(duì)比分類器的分類性能.

5.3.1λ特征參數(shù)的確定

對(duì)于基于代價(jià)敏感的多標(biāo)記不完備鄰域決策表，特征選擇的結(jié)果與特征代價(jià)直接相關(guān)，因此，在實(shí)驗(yàn)過(guò)程中，對(duì)基于均勻分布和正態(tài)分布生成的兩種特征代價(jià)獲得的特征選擇結(jié)果進(jìn)行對(duì)比，同時(shí)，由于鄰域參數(shù)的選擇直接關(guān)系到特征選擇的結(jié)果和分類器的分類性能.為此，在曼哈頓距離度量方法中，鄰域參數(shù)的計(jì)算方式為δ=stdai/λ，其中stdai通過(guò)本文算法進(jìn)行特征選擇之后的每個(gè)特征的標(biāo)準(zhǔn)差，λ的取值直接關(guān)系到鄰域參數(shù)δ的值[27].通過(guò)實(shí)驗(yàn)分析發(fā)現(xiàn)，λ的取值范圍從1.0到2.0的特征選擇結(jié)果所對(duì)應(yīng)的分類性能較好，為此，為了詳細(xì)分析λ值對(duì)特征選擇結(jié)果和分類器的分類性能影響，在實(shí)驗(yàn)過(guò)程中將λ值每次變化0.1進(jìn)行實(shí)驗(yàn)分析和結(jié)果對(duì)比.

下面將分析不同分布函數(shù)隨著λ變化對(duì)特征選擇結(jié)果以及代價(jià)的影響，詳細(xì)分析基于不同分布函數(shù)生成的測(cè)試代價(jià)在曼哈頓距離度量標(biāo)準(zhǔn)下λ(在圖中用Lambda表示λ)變化對(duì)于特征選擇的個(gè)數(shù)和特征子集總代價(jià)影響.圖中UDASBC、NDASBC分別表示在均勻分布和正態(tài)分布下考慮特征代價(jià)的特征選擇個(gè)數(shù)，UDAS、NDAS分別表示在均勻分布和正態(tài)分布下不考慮特征代價(jià)的特征選擇個(gè)數(shù)，UDCPBC、NDCPBC分別表示在均勻分布和正態(tài)分布下的代價(jià)約簡(jiǎn)率，即考慮特征代價(jià)的特征子集代價(jià)占總代價(jià)的百分比(由于兩種分布函數(shù)生成的代價(jià)不同，因此兩種分布函數(shù)通過(guò)代價(jià)百分比分析)，UDCP、NDCP分別表示在均勻分布和正態(tài)分布下不考慮特征代價(jià)的特征子集代價(jià)占總代價(jià)的百分比.具體實(shí)驗(yàn)結(jié)果如圖1所示.

圖1 4個(gè)數(shù)據(jù)集在兩種分布函數(shù)下特征選擇的個(gè)數(shù)和代價(jià)百分比隨λ值的變化情況Fig.1 Variation of the number of feature selection and the value of the cost percentage for the four datasets under the two distribution functions with λ

由圖1可知，對(duì)于4個(gè)數(shù)據(jù)集來(lái)說(shuō)，隨著λ變化，特征選擇個(gè)數(shù)和代價(jià)百分比都呈下降趨勢(shì).考慮測(cè)試代價(jià)比不考慮測(cè)試代價(jià)的特征選擇效果更優(yōu)，例如對(duì)于圖1(e)和圖1(f)中的scenes數(shù)據(jù)集，當(dāng)不考慮測(cè)試代價(jià)時(shí) ，特征選擇個(gè)數(shù)最小為39，當(dāng)考慮測(cè)試代價(jià)時(shí)，均勻分布和正態(tài)分布下特征個(gè)數(shù)最小分別為17、22，分別占不考慮測(cè)試代價(jià)特征選擇結(jié)果的43%、56%；同時(shí)，考慮測(cè)試代價(jià)的代價(jià)百分比不考慮測(cè)試代價(jià)的代價(jià)百分比相對(duì)更小，當(dāng)考慮測(cè)試代價(jià)時(shí)，均勻分布和正態(tài)分布下代價(jià)百分比最小分別為0.40%、3.60%，而不考慮測(cè)試代價(jià)時(shí)，均勻分布和正態(tài)分布下代價(jià)百分比最小分別為13.26%、13.19%，代價(jià)分別減少了12.86%、9.59%.另外，當(dāng)代價(jià)百分比最小時(shí)，在均勻分布下代價(jià)百分比相差最為顯著的是圖1(a)中的yeast和圖1(e)中的scenes數(shù)據(jù)集，最小代價(jià)百分比相差大于11%，在正態(tài)分布下代價(jià)百分比相差較明顯的是圖1(b)中yeast、圖1(d)中的emotions和圖1(f)中的scenes數(shù)據(jù)集，最小代價(jià)百分比相差大于9%.由此可知，對(duì)于yeast和scenes數(shù)據(jù)集來(lái)說(shuō)，考慮代價(jià)與不考慮代價(jià)的代價(jià)百分比的差在均勻分布下比正態(tài)分布下大.當(dāng)λ取值為1.9或2.0時(shí)，特征選擇個(gè)數(shù)和代價(jià)百分比最小.

綜上可知，考慮代價(jià)的特征選擇效果優(yōu)于不考慮代價(jià)的特征選擇效果，考慮特征代價(jià)的代價(jià)百分比小于不考慮特征代價(jià)的百分比.

圖2 4個(gè)數(shù)據(jù)集在兩種分布函數(shù)下平均精度隨λ值的變化情況Fig.2 Variation of the average precision with the values of the four datasets under the two distribution functions with λ

由圖2可知，當(dāng)λ取值在1.0-2.0之間，在兩種分布函數(shù)下，特征選擇的個(gè)數(shù)都呈下降趨勢(shì).在均勻分布下，對(duì)于圖2(a)中的yeast、圖2(e)中的scenes和圖2(g)中的birds數(shù)據(jù)集來(lái)說(shuō)，隨λ取值的變化，5個(gè)分類器的平均分類精度的變化相對(duì)不明顯，當(dāng)λ=2.0時(shí)，3個(gè)數(shù)據(jù)集的特征選擇結(jié)果和分類性能較優(yōu)；對(duì)于圖2(c)中的emotions數(shù)據(jù)集來(lái)說(shuō)，平均精度隨λ取值的變化無(wú)明顯規(guī)律，當(dāng)λ=1.2時(shí)，5個(gè)分類器的平均精度較優(yōu).在正態(tài)分布下，隨λ取值的變化，圖2(d)中的emotions數(shù)據(jù)集的平均精度的變化顯著，圖2(b)yeast和圖2(f)scenes數(shù)據(jù)集的平均精度變化較平緩，圖2(h)中的birds數(shù)據(jù)集在λ=1.2，除RAKEL分類器外，其他4個(gè)分類器的平均精度顯著下降，參數(shù)λ在變化到1.2之后的平均精度變化相對(duì)平緩.對(duì)于yeast、emotions、scenes、birds數(shù)據(jù)集來(lái)說(shuō)，當(dāng)λ取值分別為2.0、1.4、1.9、2.0時(shí)對(duì)應(yīng)數(shù)據(jù)集的特征選擇結(jié)果和分類性能較優(yōu).

綜上可知，每個(gè)數(shù)據(jù)集在5個(gè)多標(biāo)記分類器上最優(yōu)的平均分類精度所對(duì)應(yīng)的λ參數(shù)不盡相同，參數(shù)λ的取值也影響特征選擇的結(jié)果.

5.3.2 實(shí)驗(yàn)結(jié)果和討論

為進(jìn)一步驗(yàn)證本文算法的有效性，下面將在4個(gè)Mulan數(shù)據(jù)集上利用兩種分布函數(shù)為特征生成測(cè)試代價(jià)，通過(guò)5個(gè)多標(biāo)記性能指標(biāo)在曼哈頓距離度量下進(jìn)行實(shí)驗(yàn)對(duì)比和分析，實(shí)驗(yàn)結(jié)果如表5-表8所示，其中，λ為特征參數(shù)，AS為特征選擇的個(gè)數(shù)，PC為代價(jià)百分比，AP為分類器的平均分類精度，HL為漢明損失，Coverage為覆蓋率 、OE為1錯(cuò)誤率、RL為排序損失，帶有↑的性能指標(biāo)表示值越大越好，↓性能能指標(biāo)表示值越小越好.另外，表中分別給出5個(gè)分類器的平均精度最優(yōu)時(shí)，對(duì)應(yīng)的λ參數(shù)、特征子集的大小、特征子集的代價(jià)百分比和其他4個(gè)分類性能指標(biāo)的值.

表5 兩種分布函數(shù)下Yeast數(shù)據(jù)集的分類性能指標(biāo)比較Table 5 Comparison of classification performance of yeast dataset under two distribution functions

從表5-表8的實(shí)驗(yàn)結(jié)果可知，當(dāng)分類器的平均分類精度最優(yōu)時(shí)，均勻分布與正態(tài)分布相比，4個(gè)數(shù)據(jù)集在均勻分布下，5個(gè)分類器的分類性能相對(duì)較優(yōu).在均勻分布下，yeast、emotions、scenes和birds這4個(gè)數(shù)據(jù)集所對(duì)應(yīng)的5個(gè)分類器的平均特征個(gè)數(shù)分別是33、27、43、31，分別占原有特征的32.0%、27.2%、14.6%、11.9%；在正態(tài)分布下，這4個(gè)數(shù)據(jù)集所對(duì)應(yīng)的平均特征個(gè)數(shù)分別是23、20、42、30，分別占原有特征的22.9%、27.8%、14.29%、11.5%.其中，在yeast數(shù)據(jù)集中，使用均勻分布比正態(tài)分布下的特征選擇算法效果提高了9.1%，而其他4個(gè)數(shù)據(jù)集特征選擇的差異并不明顯.同時(shí)，在均勻分布下，yeast、emotions、scenes和birds這4個(gè)數(shù)據(jù)集所對(duì)應(yīng)的五個(gè)分類器的特征選擇結(jié)果的代價(jià)百分比分別是14.60%、33.52%、3.62%、9.94%；在正態(tài)分布下，這4個(gè)數(shù)據(jù)集所對(duì)應(yīng)的特征選擇結(jié)果的代價(jià)百分比分別是14.45%、20.39%、8.89%、9.22%，由此可知，emotions和scenes數(shù)據(jù)集在不同分布函數(shù)下代價(jià)百分比的差異較大.由實(shí)驗(yàn)結(jié)果可知，本文的基于代價(jià)敏感的特征選擇算法降低了多標(biāo)記學(xué)習(xí)的計(jì)算時(shí)間和空間消耗，且有效地節(jié)省了成本代價(jià).同時(shí)，由表5-表8的實(shí)驗(yàn)結(jié)果對(duì)比發(fā)現(xiàn)，選擇的特征子集直接影響到多標(biāo)記分類器的分類性能.在上述4個(gè)數(shù)據(jù)集中，由于特征子集的結(jié)果不同，導(dǎo)致5種分類器的分類性能也不相同.例如，在均勻分布下，birds數(shù)據(jù)集在RAkEL分類器下的平均分類精度為75.60%，而在IBLR_ML分類器下的平均分類精度為60.79%，兩個(gè)分類器的性能差異超過(guò)14%；在正態(tài)分布下，birds數(shù)據(jù)集在RAkEL分類器下的平均分類精度為76.26%，而在BRkNN分類器下的平均分類精度為58.20 %，兩個(gè)分類器的性能差異超過(guò)18%.由實(shí)驗(yàn)結(jié)果可知，對(duì)于yeast數(shù)據(jù)集來(lái)說(shuō)，IBLR_ML分類器的分類性能優(yōu)于其他4個(gè)分類器的分類性能；對(duì)于emtions、scenes和birds數(shù)據(jù)集來(lái)說(shuō)，RAkEL分類器分類性能較其他4個(gè)分類器的分類性能更優(yōu).

表6 兩種分布函數(shù)下Emotions數(shù)據(jù)集的分類性能指標(biāo)比較Table 6 Comparison of classification performance of Emotions dataset under two distribution functions

表7 兩種分布函數(shù)下Scenes數(shù)據(jù)集的分類性能指標(biāo)比較Table 7 Comparison of classification performance of Scenes dataset under two distribution functions

表8 兩種分布函數(shù)下Birds數(shù)據(jù)集的分類性能指標(biāo)比較Table 8 Comparison of classification performance of Birds dataset under two distribution functions

綜上所述，本文算法特征選擇的結(jié)果和分類性能與特征代價(jià)、λ參數(shù)和分類器的選擇相關(guān).通過(guò)表5-表8的實(shí)驗(yàn)結(jié)果和分析可知，本文算法解決了對(duì)代價(jià)敏感下多標(biāo)記不完備鄰域數(shù)據(jù)的特征選擇問(wèn)題，有效剔除了數(shù)據(jù)中的冗余特征，降低特征的代價(jià)成本，提高了分類器的分類性能.

6 結(jié)束語(yǔ)

針對(duì)多標(biāo)記高維數(shù)據(jù)中的連續(xù)值、缺失值以及特征的測(cè)試代價(jià)等問(wèn)題，從代價(jià)敏感學(xué)習(xí)的視角，提出了一種面向不完備特征鄰域決策表的多標(biāo)記特征選擇算法，算法利用均勻分布和正態(tài)分布兩種分布函數(shù)分別為每個(gè)數(shù)據(jù)特征生成代價(jià)，分析特征代價(jià)對(duì)特征選擇的影響；算法可直接對(duì)不完備連續(xù)型數(shù)據(jù)進(jìn)行處理，無(wú)需對(duì)缺失數(shù)據(jù)進(jìn)行填充及對(duì)連續(xù)數(shù)據(jù)進(jìn)行離散化.算法通過(guò)距離度量對(duì)不完備特征鄰域決策表進(jìn)行鄰域?；?，并根據(jù)正域計(jì)算出核特征，在此基礎(chǔ)上，采用啟發(fā)式搜索策略對(duì)多標(biāo)記不完備決策表進(jìn)行特征選擇，在實(shí)驗(yàn)結(jié)果中通過(guò)對(duì)考慮特征代價(jià)和不考慮特征代價(jià)的數(shù)據(jù)集的特征選擇結(jié)果進(jìn)行實(shí)驗(yàn)和分析驗(yàn)證了算法的有效性.由于現(xiàn)實(shí)生活中除需要考慮測(cè)試代價(jià)之外，還需考慮誤分類代價(jià)，下一步工作將研究基于測(cè)試代價(jià)和誤分類代價(jià)的多標(biāo)記數(shù)據(jù)特征選擇問(wèn)題.