折延宏，武晉蘭，賀曉麗

(1.西安石油大學(xué) 理學(xué)院，陜西 西安 710000；2.西安石油大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710000)

0 引 言

大數(shù)據(jù)時(shí)代，數(shù)據(jù)的產(chǎn)生和收集速度急劇提升，樣本數(shù)量、特征維度都在爆炸式增長(zhǎng)，人們面臨的分類學(xué)習(xí)任務(wù)也變得越發(fā)復(fù)雜，需要學(xué)習(xí)的類別數(shù)量迅速增加.另外，分類任務(wù)的規(guī)模還隨著樣本特征的維數(shù)疾速增加，給分類建模帶來(lái)了新的挑戰(zhàn).標(biāo)簽的增加，及標(biāo)簽間可能會(huì)存在的語(yǔ)義結(jié)構(gòu)，導(dǎo)致了結(jié)構(gòu)化學(xué)習(xí)任務(wù)的產(chǎn)生.這種結(jié)構(gòu)通?？梢杂脤哟螛?shù)來(lái)表示，我們將這類任務(wù)稱為分層分類.層次結(jié)構(gòu)是分類學(xué)習(xí)的重要輔助信息，我們可以借助其挖掘到更多潛在有效信息.

特征選擇的目的，是在保證分類準(zhǔn)確性不發(fā)生降低的前提下，選擇一個(gè)能夠代表數(shù)據(jù)有效信息的特征子集.在高維度、大體量數(shù)據(jù)的分類任務(wù)中，特征選擇可以降低算法時(shí)間復(fù)雜度，對(duì)后續(xù)處理步驟的運(yùn)行時(shí)間和準(zhǔn)確性都有重要影響.在特征選擇中，一般會(huì)涉及實(shí)數(shù)型特征和離散型特征的處理.經(jīng)典的粗糙集僅適用于離散型特征數(shù)據(jù)，模糊粗糙集作為描述條件屬性和決策屬性之間不一致性的有效數(shù)學(xué)工具，模糊粗糙集可以直接應(yīng)用于數(shù)值或混合型數(shù)據(jù).在模糊粗糙集模型中，可以通過(guò)定義模糊相似關(guān)系來(lái)度量樣本之間的相似性，不再需要對(duì)數(shù)值屬性值進(jìn)行離散化，從而避免了重要信息的丟失，也就提高了分類精度.

在大規(guī)模數(shù)據(jù)的分類任務(wù)中，分層方法能夠比平面分類技術(shù)產(chǎn)生更好的性能.Deng等[1]利用基于WordNet層次結(jié)構(gòu)的類別距離度量方法推導(dǎo)了一個(gè)層次感知的分類代價(jià)函數(shù).另外，由于類的層次結(jié)構(gòu)提供了類的外部信息，一些研究側(cè)重構(gòu)建一個(gè)層次結(jié)構(gòu)來(lái)處理大規(guī)模分類.Freeman等[2]將遺傳算法融合到特征選擇中，構(gòu)造樹(shù)狀結(jié)構(gòu)分類器.每個(gè)基本分類器都將數(shù)據(jù)集分割成一個(gè)越來(lái)越小的類集.為每個(gè)基分類器單獨(dú)選擇特征，同時(shí)進(jìn)行樹(shù)的設(shè)計(jì)和特征的選擇.Jia等[3]設(shè)計(jì)了一種基于信息增益和特征頻率分布的層次分類系統(tǒng)特征選擇算法，以此得到具有較強(qiáng)判別性的特征子集，從而提高了分類效率和準(zhǔn)確率.

近年來(lái)，模糊粗糙集理論在機(jī)器學(xué)習(xí)和模式識(shí)別領(lǐng)域中得到了廣泛的關(guān)注，相關(guān)的應(yīng)用研究也不少.Hu等[4]提出了一種信息測(cè)度來(lái)計(jì)算經(jīng)典等價(jià)關(guān)系和模糊等價(jià)關(guān)系的識(shí)別能力，構(gòu)造了基于該信息測(cè)度的兩種貪婪降維算法，分別用于無(wú)監(jiān)督和有監(jiān)督數(shù)據(jù)降維.Jenson等[5]使用基于經(jīng)典和模糊粗糙集的方法，設(shè)計(jì)了語(yǔ)義保持的降維方法.還有不少學(xué)者關(guān)注使用代表實(shí)例來(lái)進(jìn)行特征選擇.Zhang等[6]研究了基于模糊粗糙集的代表性實(shí)例的特征選擇問(wèn)題，對(duì)依賴函數(shù)進(jìn)行了新的定義，并提出了有效的約簡(jiǎn)算法.次年該團(tuán)隊(duì)研究了將代表實(shí)例應(yīng)用于基于模糊粗糙集的信息熵的增量特征選擇，并在文獻(xiàn)[7]中提出了主動(dòng)增量特征選擇算法.另外，Hu等[8]將高斯核與模糊粗糙集相結(jié)合，設(shè)計(jì)了一個(gè)基于核的模糊粗糙集模型，這是一種適用于大規(guī)模多模態(tài)的特征選擇算法.對(duì)于分層分類的應(yīng)用，Zhao等[9]設(shè)計(jì)了一種基于模糊粗糙集的分層分類的特征選擇方法，利用類的層次結(jié)構(gòu)關(guān)系構(gòu)造模糊粗糙集模型，提出了基于兄弟節(jié)點(diǎn)的特征選擇算法.后來(lái)，Zhao等[10]又提出了基于遞歸正則化的分層特征選擇框架，將數(shù)據(jù)的分類拆分成多個(gè)子分類任務(wù).但基于模糊粗糙集的分層分類方法研究仍然較少，鑒于模糊粗糙集對(duì)于描述不確定信息的優(yōu)勢(shì)，我們對(duì)其進(jìn)行了更加深入的研究，并提出本文的分層分類方法.

本文提出了一種用于分層分類的模糊粗糙集模型，并開(kāi)發(fā)了相應(yīng)的特征選擇算法.接下來(lái)的內(nèi)容組織如下.在第1節(jié)中，給出了一些關(guān)于模糊粗糙集的預(yù)備知識(shí)，以及在分層分類中的相關(guān)作用.然后，在第2節(jié)中，提出層次辨識(shí)矩陣和樣本對(duì)選擇的概念，并給出了基于此的特征選擇模型.在第3節(jié)引入了分層分類的評(píng)價(jià)指標(biāo).在第4節(jié)中，給出了實(shí)驗(yàn)結(jié)果并分析了分層特征選擇算法的有效性.最后，在第5節(jié)，總結(jié)了本文并提出未來(lái)研究方向.

1 預(yù)備知識(shí)

1.1 模糊粗糙集屬性約簡(jiǎn)

1.1.1 模糊粗糙集

(U,C,D)稱為模糊決策系統(tǒng),其中U為對(duì)象的集合，C是條件屬性集，D是決策屬性，其將樣本劃分為子集{d1,d2,…,dk}.

設(shè)U是一非空論域，R是U上一模糊二元關(guān)系，如果R滿足以下：

1) 自反性:R(x,x)=1；

2) 對(duì)稱性:R(x,y)=R(y,x)；

3) 最小最大傳遞性:miny(R(x,y),R(y,z))≤R(x,z).

則稱R為模糊等價(jià)關(guān)系.

對(duì)于任意x∈U，如果R是一個(gè)模糊相似關(guān)系，D是經(jīng)典決策屬性，di是決策類，x對(duì)于di的隸屬度定義為：

那么，模糊上、下近似分別為：

假設(shè)(U/D)={d1,d2,…,dk}，D相對(duì)于C的正域定義為：

定義1[11]設(shè)(U,C∪D)為一個(gè)模糊決策系統(tǒng)，稱子集P?C為C相對(duì)于D的一個(gè)約簡(jiǎn)，如果滿足以下：

1)對(duì)于任意x∈U,PosP(D)(x)=PosC(D)(x)；

2)對(duì)于任意a∈P，一定存在x∈U滿足PosP-{a}(D)(x)=PosP(D)(x).

1.1.2 辨識(shí)矩陣[12]

設(shè)U={x1,x2,…,xn}，如果cij是可以區(qū)分樣本對(duì)(xi,xj)的可辨識(shí)性特征集，則MD(U,C)=(cij)n×n稱為(U,C∪D)的辨識(shí)矩陣，其中元素cij的定義如下：

對(duì)于任意cij，如果在MD(U,C)中不存在另一個(gè)元素作為其子集，則稱cij為MD(U,C)中的極小元素.

1.2 分層分類中的模糊粗糙集

1.2.1 分層分類

本論文針對(duì)的是基于樹(shù)的層次類結(jié)構(gòu)，其他結(jié)構(gòu)暫不考慮.層次結(jié)構(gòu)信息在決策類之間強(qiáng)加一種父子關(guān)系，這意味著屬于特定類的實(shí)例也屬于它的所有祖先類.分類通常可以形式化地表示為(D,)，其中D是所有類的集合，“”表示從屬關(guān)系，它是具有以下屬性[13]的關(guān)系的子類:

1) 不對(duì)稱性: 對(duì)于任意di,dj∈D，若didj，則不會(huì)有djdi.

2) 反自反性: 對(duì)于任意di∈D，都不會(huì)有didi.

3) 傳遞性: 對(duì)于di,dj,dk∈D，若有didj且djdk，那么一定有didk.

1.2.2 分層分類中的模糊粗糙集

經(jīng)典模糊粗糙集的下近似在不同類別上的最小距離處取得，上近似在同一類別上的最大距離處取得.層次結(jié)構(gòu)定義了類節(jié)點(diǎn)之間的從屬關(guān)系，鑒于此，本文給出一種基于兄弟策略的模糊粗糙集模型，以進(jìn)行特征選擇以及分類.

基于樹(shù)的層次結(jié)構(gòu)可以表示為，其中U為對(duì)象的論域集，C為條件屬性的非空集，Dtree為決策屬性，其將樣本劃分為{d1,d2,…,dk}，k是決策類的數(shù)量.Dtree滿足上文中介紹的從屬關(guān)系.R是由特征集B?C導(dǎo)出的U上的模糊相似關(guān)系.根據(jù)基于樹(shù)層次結(jié)構(gòu)的分類問(wèn)題中需考慮的負(fù)樣本搜索范圍，我們定義了基于兄弟策略的下近似.

定義2設(shè)(U,C,Dtree)為一個(gè)模糊決策系統(tǒng)，若R是一個(gè)模糊相似關(guān)系，Dtree是滿足從屬關(guān)系的經(jīng)典決策屬性，對(duì)于任意x∈U，兄弟策略下近似定義為：

與經(jīng)典模糊粗糙集中下近似的定義相比，我們有以下結(jié)論[9]：

命題1已知是一個(gè)分層分類問(wèn)題，R是子集B?C所誘導(dǎo)的模糊相似關(guān)系，di是樣本的標(biāo)記, 對(duì)于x∈U，有：

命題2已知是一個(gè)分層分類問(wèn)題，R1和R2是子集B1和B2分別誘導(dǎo)的兩個(gè)模糊相似關(guān)系，且R1?R2，di是樣本的決策類, 對(duì)于x∈U，有：

2 分層特征選擇

傳統(tǒng)的特征選擇算法假定所有的類別是相互獨(dú)立的，部分學(xué)者借助類層次結(jié)構(gòu)將復(fù)雜的問(wèn)題分而治之，沒(méi)有將層次結(jié)構(gòu)信息融合到特征選擇任務(wù)中.粗糙集理論可以有效地利用條件屬性與決策類之間的相關(guān)性來(lái)進(jìn)行特征選擇.本文將葉節(jié)點(diǎn)設(shè)為實(shí)際類，采用上一節(jié)中的兄弟策略下近似來(lái)進(jìn)行特征選擇.

2.1 層次辨識(shí)矩陣

定義3給定一個(gè)分層分類問(wèn)題，R是由特征子集B?C所導(dǎo)出的模糊相似關(guān)系，即R(x,y)=∩{a(x,y):a∈B}.Dtree={d0,d1,d2,…,dl}，其中d0是樹(shù)的根節(jié)點(diǎn)，它不是真正的類.U被決策屬性劃分為{d1,d2,…,dl}，其中l(wèi)是類的數(shù)量.Dtree相對(duì)于B的模糊正域定義為：

如果a∈C滿足PosC-{a}(Dtree)=PosC(Dtree)，則稱a在C中相對(duì)于Dtree不必要，否則稱a在C中相對(duì)于Dtree必要.對(duì)于P?C，如果有PosP(Dtree)=PosC(Dtree)，且P中任何一個(gè)條件屬性在P中相對(duì)于Dtree都必要，則稱P是C的相對(duì)于Dtree的屬性約簡(jiǎn).C中相對(duì)于Dtree的全部必要條件屬性集合稱為C相對(duì)于Dtree的核心，記為CoreDtree(C).如果用RedDtree(C)表示C相對(duì)于Dtree的全部屬性約簡(jiǎn)集合，易證CoreDtree(C)=∩RedDtree(C).

定義4對(duì)于一個(gè)分層分類問(wèn)題，R是U上的模糊等價(jià)關(guān)系.有一個(gè)n×n的矩陣(cij)，稱為模糊決策系統(tǒng)(U,C∪Dtree)的層次辨識(shí)矩陣，記為MDtree(U,C)，其中cij的定義為[14]：

式中：λi=PosB(Dtree)(xi).

布爾函數(shù)fU(C∪Dtree)=∧(∨cij)，cij≠?，是決策系統(tǒng)(U,C∪Dtree)的辨識(shí)函數(shù)，其中∨(cij)是所有滿足a∈cij的變量的析取.設(shè)gU(C∪Dtree)是fU(C∪Dtree)通過(guò)盡可能多的分配律和吸收律得到的最小析取形式，則存在t和Bi∈C，i=1,2,…,t，使得gU(C∪Dtree)=(∧B1)∨… ∨(∧Bt)，其中Bt中每個(gè)元素只出現(xiàn)一次.

定理1：假設(shè)P?C，那么P包含C的一個(gè)相對(duì)約簡(jiǎn)，當(dāng)且僅當(dāng)對(duì)于任意cij≠?有P∩cij≠?成立.

2.2 尋找約簡(jiǎn)

在本節(jié)中，首先用一個(gè)例子說(shuō)明行文的動(dòng)機(jī).然后利用條件屬性的相對(duì)辨識(shí)關(guān)系來(lái)刻畫層次辨識(shí)矩陣中的極小元素.最后，設(shè)計(jì)了一個(gè)算法找到屬性約簡(jiǎn)集.

例：假設(shè)U={x1,x2,…,x7}，C={c1,c2,c3,c4}，R={R1,R2,R3,R4}是由四個(gè)條件屬性導(dǎo)出的模糊相似關(guān)系，Dtree={d0,A,B}，d0是根節(jié)點(diǎn)，A和B是d0的直接子類.U被決策屬性劃分為{A,B}，A={x1,x2,x5}，B={x3,x4,x6,x7}.對(duì)于模糊決策系統(tǒng)(U,C∪Dtree)，由條件屬性導(dǎo)出的模糊相似關(guān)系及由整個(gè)條件屬性集導(dǎo)出的模糊相似關(guān)系R為：

根據(jù)層次辨識(shí)矩陣的定義有：

由極小元素的定義可知，{2}，{1,4}以及{3,4}是層次辨識(shí)矩陣的所有極小元素.辨識(shí)函數(shù)通過(guò)吸收律可以簡(jiǎn)化為fU(C∪Dtree)=(R2)∧(R1∨R4)∧(R3∨R4).如果我們可以在計(jì)算整個(gè)層次辨識(shí)矩陣之前得到這些極小元素，那么尋找約簡(jiǎn)的搜索范圍就會(huì)得到壓縮，計(jì)算復(fù)雜度也會(huì)大大降低.現(xiàn)在關(guān)鍵問(wèn)題是如何不計(jì)算整個(gè)層次辨識(shí)矩陣就能得到極小元素，接下來(lái)的理論可以為解決這個(gè)問(wèn)題提供支撐.

定義5對(duì)于一個(gè)分層分類問(wèn)題，R是U上的模糊等價(jià)關(guān)系.我們稱二元關(guān)系DIS(a)為條件屬性a對(duì)決策屬性的相對(duì)辨識(shí)關(guān)系，定義為：

DIS(C)=∩a∈CDIS(a).顯然，(xi,xj)∈DIS(a)?若cij≠?則有a∈cij.

定義6[15]Sij=∩{DIS(a):(xi,xj)∈DIS(a)}.

對(duì)于(xi,xj)∈DIS(C)，一定存在a∈C滿足(xi,xj)∈DIS(a)，那么一定存在Sij滿足(xi,xj)∈Sij，所以有∪Sij=DIS(C).

這里我們明確極大樣本對(duì)集的定義：對(duì)于任意Sst≠Sij，都有Sij?Sst，則稱Sij是極大的.

推論1從DIS(C)中刪除DIS(a)，會(huì)刪除所有滿足a∈cij的Sij.

定義7Nij=|{a:(xi,xj)∈DIS(a)}|.

Nij是滿足(xi,xj)∈DIS(a)的條件屬性a的個(gè)數(shù),容易看出Nij=|cij|.

對(duì)于Sij，Nij和cij，有下面的定理：

定理2.1對(duì)于任意(xs,xt)∈Sij，(xs,xt)≠(xi,xj)，有Sij?Sst和Nst≥Nij.

證明：(xs,xt)∈Sij，Sij=∩{DIS(a):(xi,xj)∈DIS(a)}=∩{DIS(a):a∈cij}，那么能區(qū)分(xi,xj)的屬性也能夠區(qū)分(xs,xt)，但也存在其他屬性能夠區(qū)分(xs,xt)，因此有cij?cst.故由Sij定義知Sij?Sst，由Nij定義知Nij≤Nst.

定理2.2對(duì)于兩個(gè)極小元素cij和cst，有(xi,xj)?Sst和(xs,xt)?Sij.

證明：對(duì)于兩個(gè)極小元素cij≠cst，存在P∈cij，Q∈cst，但又P?cst，Q?cij.即(xi,xj)?(DIS(Q)，(xs,xt)?(DIS(P)，由Sij的定義知(xi,xj)Sst，(xs,xt)Sij.

定理2.3當(dāng)且僅當(dāng)Sij是極大的，cij是MDtree(U,C)中的極小元素.

證明：“?”：若cij是極小元素，由極小元素定義，對(duì)任意cst≠cij，都有cst?cij.即存在a∈cst，a?cij，則(xs,xt)∈DIS(a)，(xi,xj)?(DIS(a).根據(jù)Sst的定義及集合間的包含關(guān)系有(xi,xj)?Sst.又對(duì)于任意Sst≠Sij，一定有(xi,xj)∈Sij，由此能夠推出Sij?Sst，故Sij是極大的.

“?”：已知Sij是極大的，要證cij是極小元素，即對(duì)于任意cst≠cij，存在a∈cst且a?cij.若cst≠cij，那么cst?cij或cst?cij.根據(jù)Sij的定義，cst?cij，由此可推出Sij?Sst，然而，這與Sij是極大的相矛盾，故cst?cij，即存在a∈cst且a?cij.

推論2從DIS(C)中刪除極小元素cij對(duì)應(yīng)的極大樣本對(duì)集Sij可以刪除所有的Sst?Sij，但不會(huì)完全刪除其他極小元素cst對(duì)應(yīng)的Sst.

推論3Nij最小的樣本對(duì)(xi,xj)對(duì)應(yīng)一個(gè)極小元素cij.

定理2.4∪{Sij:cij是極小元素}=DIS(C).

證明：左邊?右邊顯然成立.下證右邊?左邊：對(duì)于任意(xs,xt)∈DIS(C)，有(xs,xt)∈Sst.由于極大樣本對(duì)集對(duì)應(yīng)極小元素，當(dāng)存在極大Sij使得Sst?Sij時(shí)，有(xs,xt)∈Sij，這時(shí)cij是極小元素.若不存在，那么Sst就是極大樣本對(duì)集，cst是極小元素.故對(duì)任意(xs,xt)∈DIS(C)，有(xs,xt)∈∪{Sij:cij是極小元素}.

推論4當(dāng)且僅當(dāng)DIS(C)=?時(shí)，所有極小元素cij對(duì)應(yīng)的Sij都從DIS(C)中被刪除.

根據(jù)以上定理和推論，通過(guò)對(duì)DIS(C)中的樣本對(duì)(xi,xj)升序排序，可以從DIS(C)中依次刪除最小Nij對(duì)應(yīng)的Sij，直到DIS(C)=?，這樣可以得到MDtree(U,C)中所有極小元素的集合.進(jìn)而通過(guò)辨識(shí)函數(shù)，可以找到所有約簡(jiǎn).但實(shí)際上我們只需要一個(gè)約簡(jiǎn)，即找到辨識(shí)函數(shù)的最小析取形式中的一個(gè)合取范式.我們只需選擇辨識(shí)函數(shù)中的一個(gè)元素a∈cij，而忽略辨識(shí)函數(shù)中其他包含a的元素，這與我們由辨識(shí)函數(shù)化為其簡(jiǎn)化形式的思路一致.

結(jié)合極小元素的這些性質(zhì)，我們?cè)O(shè)計(jì)以下算法來(lái)得到條件屬性集的一個(gè)約簡(jiǎn)：

算法:基于樣本對(duì)選擇的分層特征選擇算法(HierSPS-FS) 輸入:U,C,Dtree輸出:特征子集REDUCT1 初始化REDUCT為空集;2 計(jì)算每個(gè)特征的相對(duì)辨識(shí)關(guān)系DIS(a),DIS(C)和Nij;3 while(DIS(C)≠?) do4 找到DIS(C)中的最小值Ni0j0對(duì)應(yīng)的(xi0,xj0);5 for(a∈C) do6 if((xi0,xj0)∈DIS(a)) then7 if(a?REDUCT) then8 向子集REDUCT中追加特征;9 更新DIS(C)=DIS(C)-DIS(a);10 end if11 將Ni0j0設(shè)為inf;12 end if13 end for14 end while15 返回約簡(jiǎn)集REDUCT;

在特征選擇算法中，我們首先計(jì)算每個(gè)特征的層次相對(duì)辨識(shí)關(guān)系，然后計(jì)算原始特征集的層次相對(duì)辨識(shí)關(guān)系，以及每個(gè)樣本對(duì)能夠被多少特征區(qū)分.在接下來(lái)的循環(huán)中，我們根據(jù)Nij的大小對(duì)樣本對(duì)進(jìn)行排序，找到Nij值最小的樣本對(duì).然后遍歷整個(gè)特征集，找到能夠區(qū)分該樣本對(duì)的特征并加入約簡(jiǎn)集.這里我們只要找到一個(gè)能夠區(qū)分該樣本對(duì)的特征就退出該次循環(huán)，去尋找下一個(gè)關(guān)鍵的樣本對(duì)，因此節(jié)約了將冗余特征加入約簡(jiǎn)集的時(shí)間，但又保證約簡(jiǎn)集的辨識(shí)能力.

3 評(píng)價(jià)方法

傳統(tǒng)的多分類任務(wù)指標(biāo)，例如F1度量能夠反映分類器對(duì)于不同類別的分類能力，但是它在分層結(jié)構(gòu)中無(wú)法準(zhǔn)確地描述錯(cuò)分的程度.圖1是動(dòng)物的類別層次結(jié)構(gòu)，綠色方框表示某個(gè)樣本的真實(shí)標(biāo)簽，黃色方框表示兩個(gè)分類器的預(yù)測(cè)標(biāo)簽.假設(shè)該樣本的真實(shí)標(biāo)簽是貓，一個(gè)分類器將其預(yù)測(cè)為老虎，另一個(gè)分類器將其預(yù)測(cè)為青蛙，那么這兩種錯(cuò)誤的程度是不同的，但傳統(tǒng)分類評(píng)價(jià)標(biāo)準(zhǔn)無(wú)法實(shí)現(xiàn)這種對(duì)于錯(cuò)誤程度的區(qū)分，故需要一些基于層次結(jié)構(gòu)的分層分類評(píng)價(jià)指標(biāo).

圖1 動(dòng)物的類別層次Fig.1 Categorical irony level of animals

3.1 樹(shù)誘導(dǎo)損失

3.2 分層F1測(cè)度

分層F1測(cè)度的定義為:

3.3 最近公共祖先(LCA) F1測(cè)度

4 實(shí)驗(yàn)分析

在本節(jié)中，首先介紹我們實(shí)驗(yàn)中使用的兩個(gè)數(shù)據(jù)集.然后，將提出的分層特征選擇與[17]中提出的平面特征選擇進(jìn)行比較.所有數(shù)值實(shí)驗(yàn)均在MATLAB R2018b中實(shí)現(xiàn)，并在運(yùn)行速度為 3.00 GHz、內(nèi)存為 16.0 GB，64位Windows 10操作系統(tǒng)的Intel Core i7-9700上執(zhí)行.在訓(xùn)練集上選擇特征子集，并分別使用SVM、KNN和NB分類器在測(cè)試集上進(jìn)行測(cè)試.對(duì)于SVM分類器，使用線性核和c=1進(jìn)行十次交叉驗(yàn)證.對(duì)于KNN分類器，在初步實(shí)驗(yàn)的基礎(chǔ)上為類決策設(shè)置了參數(shù)k=5.

4.1 數(shù)據(jù)集

實(shí)驗(yàn)使用了三個(gè)數(shù)據(jù)集，表1提供了這些數(shù)據(jù)集的基本統(tǒng)計(jì)數(shù)據(jù).

表1 數(shù)據(jù)集基本信息

第一個(gè)數(shù)據(jù)集是來(lái)自加州大學(xué)歐文分校提出的用于機(jī)器學(xué)習(xí)的數(shù)據(jù)庫(kù)UCI中的Bridges[18]，它一般用于分類，是一個(gè)小型的數(shù)據(jù)集，只有108個(gè)樣本.

第二個(gè)數(shù)據(jù)集是DD數(shù)據(jù)集[19]，它是一個(gè)蛋白質(zhì)數(shù)據(jù)集.它有 3 625 個(gè)樣本和473個(gè)特征.它有27個(gè)實(shí)類和4個(gè)主要結(jié)構(gòu)類.

第三個(gè)數(shù)據(jù)集F194也是一個(gè)蛋白質(zhì)數(shù)據(jù)集[20]，它有 8 525 個(gè)樣本和473個(gè)特征.此數(shù)據(jù)集中有194個(gè)類，都是葉節(jié)點(diǎn).

最后一個(gè)SAIAPR[21]，是圖像相關(guān)的數(shù)據(jù)集，每個(gè)圖像都經(jīng)過(guò)手動(dòng)分割并根據(jù)預(yù)定義的標(biāo)簽詞匯表對(duì)結(jié)果進(jìn)行標(biāo)注；詞匯是按照語(yǔ)義概念的層次結(jié)構(gòu)組織的.根據(jù)文獻(xiàn)[22]，物體可以分為六個(gè)主要分支：“動(dòng)物”、“景觀”、“人造的”、“人類”、“食物”或“其他”.

4.2 實(shí)驗(yàn)步驟

為了評(píng)估文中的分層特征選擇算法的性能，進(jìn)行了一些對(duì)比實(shí)驗(yàn).具體的實(shí)驗(yàn)研究安排如下：

1) 基線對(duì)比：將選擇所有原始特征和進(jìn)行特征選擇后實(shí)驗(yàn)情況對(duì)比.文中的基于樣本對(duì)選擇的分層特征選擇算法記為HierSPS-FS.

2) 使用分層評(píng)價(jià)指標(biāo)進(jìn)行比較：將所提出的算法與平面特征選擇算法進(jìn)行了比較.這里采用的平面特征選擇算法也是基于模糊粗糙集的特征選擇算法，CHEN等[16]定義了條件屬性的相對(duì)辨識(shí)關(guān)系，用相對(duì)辨識(shí)關(guān)系來(lái)表征模糊辨識(shí)矩陣中的極小元素，進(jìn)而提出了一個(gè)基于模糊粗糙集的約簡(jiǎn)算法這里記為FlatSPS-FS.

3) 將提出的算法與其他兩種分層方法進(jìn)行比較.文獻(xiàn)[9]中的HierDep-FS也是一種基于模糊粗糙集的分層分類算法，其本質(zhì)是根據(jù)模糊近似空間中下近似以及特征的依賴函數(shù)，最后得到能夠代表整個(gè)特征空間的約簡(jiǎn)集.該論文的作者還在文獻(xiàn)[10]中研究了一種基于正則項(xiàng)的特征選擇方法HiRR-FS，該方法是一種局部約簡(jiǎn)方法，為每個(gè)子分類器選擇不同的約簡(jiǎn)集.

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

在以下幾方面來(lái)評(píng)估所提出的特征選擇算法的性能.

1) 與基線方法的比較(選擇所有特征)

文中的算法是針對(duì)具有層次關(guān)系的大規(guī)模數(shù)據(jù)集而設(shè)計(jì)的，因此可能會(huì)出現(xiàn)特征量成百上千，甚至更多的情況，但數(shù)據(jù)具有判別性的特征，事實(shí)上只占很小一部分.如果直接對(duì)原數(shù)據(jù)進(jìn)行訓(xùn)練，那么其他無(wú)關(guān)特征可能會(huì)影響分類準(zhǔn)確率.其次，特征量和樣本量都是影響運(yùn)行時(shí)間的重要因素，巨大的特征量使模型訓(xùn)練需要更長(zhǎng)的時(shí)間，幾個(gè)小時(shí)甚至幾天.圖2是本文使用的四個(gè)數(shù)據(jù)集在進(jìn)行特征選擇和直接用原特征集進(jìn)行分類的時(shí)間對(duì)比，由于Bridges數(shù)據(jù)集的樣本量和特征數(shù)量均較小，運(yùn)行時(shí)間對(duì)比并不明顯，但根據(jù)其他幾個(gè)較大數(shù)據(jù)集的實(shí)驗(yàn)數(shù)據(jù)仍可以明顯看出，本文所提出的特征選擇算法對(duì)分類運(yùn)行時(shí)間的壓縮效果.

圖2 運(yùn)行時(shí)間對(duì)比Fig.2 Comparison of runtime

接下來(lái)，在表2中列出的數(shù)據(jù)集上，直觀地比較所提出算法與平面算法以及不進(jìn)行特征選擇的分類精度.每項(xiàng)指標(biāo)的最佳表現(xiàn)都以粗體突出顯示.可以觀察到，通過(guò)分層方法選擇的特征的性能優(yōu)于平面方法.

表2 基線算法、平面特征選擇算法和分層特征選擇算法在不同數(shù)據(jù)集上的分類準(zhǔn)確率

2) 使用分層評(píng)價(jià)指標(biāo)進(jìn)行比較

在平面分類問(wèn)題中，通常使用SVM、KNN和NB等算法來(lái)測(cè)試分類精度.在層次分類問(wèn)題中，文中仍然使用這三種最常見(jiàn)的分類器，但由于層次分類的輸出只是類層次結(jié)構(gòu)的一部分，因此使用的評(píng)價(jià)指標(biāo)有所調(diào)整.在上一節(jié)中，詳細(xì)分析了平面分類和分層分類的特點(diǎn)，并引入了分層分類的評(píng)價(jià)指標(biāo).因此，我們接下來(lái)使用分層評(píng)價(jià)指標(biāo)來(lái)評(píng)估本文算法的性能.表3中，我們使用不同的分類器來(lái)測(cè)試不同的數(shù)據(jù)集上的樹(shù)誘導(dǎo)損失以及基于最近公共祖先的F1測(cè)度，可以直觀地比較所提出算法在3種分類器下的效果.可以觀察到，在SVM上使用分層方法選擇的特征的分類準(zhǔn)確度更高.

樹(shù)誘導(dǎo)損失TIE可以體現(xiàn)由層次結(jié)構(gòu)引起的一些不同程度的錯(cuò)誤，TIE之后的“↓”表示該值“越小越好”；Hierarchical-F1和LCA-F1是基于集合的度量，能夠平衡分層精確度和召回率，其后的“↑”表示該值“越大越好”.在表3中描述了在3個(gè)數(shù)據(jù)集上分層評(píng)價(jià)指標(biāo)的結(jié)果.可以看出，分層特征選擇比平面特征選擇具有更好的性能.

表3 不同數(shù)據(jù)集上的分層評(píng)價(jià)指標(biāo)

關(guān)于表3中的三項(xiàng)評(píng)估度量，有以下發(fā)現(xiàn)：

(1) TIE的值與數(shù)據(jù)集中決策類的層次結(jié)構(gòu)的規(guī)模有較大關(guān)系.

(2) 對(duì)于任意一個(gè)數(shù)據(jù)集來(lái)說(shuō)，F(xiàn)_LCA的值都小于F_Hierarchical的值.這是因?yàn)橛性S多共同的祖先往往會(huì)使錯(cuò)誤變得過(guò)于嚴(yán)重.LCA-F1可以避免此類錯(cuò)誤.

(3) 與其他分層方法進(jìn)行比較

表4列出了不同數(shù)據(jù)集上不同特征選擇算法的分層F1度量結(jié)果.對(duì)于分層F1度量，越高越好.

表4 不同分層方法的Hierarchical_F1測(cè)度比較

5 結(jié) 論

為了加快大規(guī)模數(shù)據(jù)集的分類速度，以及更好地評(píng)估具有層次結(jié)構(gòu)數(shù)據(jù)集的分類準(zhǔn)確度，本文提出了一種基于樣本對(duì)選擇的分層分類特征選擇算法.基于大規(guī)模數(shù)據(jù)集復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，使用兄弟節(jié)點(diǎn)的樣本作為負(fù)樣本集來(lái)計(jì)算模糊下近似值，提出了一種考慮兄弟策略的層次辨識(shí)矩陣，并引入了新的相對(duì)辨識(shí)關(guān)系，最后通過(guò)一些嚴(yán)謹(jǐn)且巧妙的方法找到約簡(jiǎn).

該算法目前僅考慮了決策類標(biāo)簽的樹(shù)結(jié)構(gòu)，事實(shí)上還有一些其他復(fù)雜的結(jié)構(gòu)，比如有向無(wú)環(huán)圖和鏈結(jié)構(gòu)等.在未來(lái)的研究工作中，將討論這類任務(wù)的特征選擇算法.此外，該算法僅從原始特征集合中選擇一些判別行特征，對(duì)層次關(guān)系的利用不夠充分.可以擴(kuò)展模糊粗糙集的優(yōu)勢(shì)，根據(jù)類標(biāo)簽結(jié)構(gòu)，為每一個(gè)子分類任務(wù)選擇一個(gè)約簡(jiǎn)子集.未來(lái)將設(shè)計(jì)相關(guān)用于分層特征選擇的模型和算法.