基于樣本對選擇的分層分類特征選擇算法研究

折延宏，武晉蘭，賀曉麗

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

0 引 言

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

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

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

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

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

1 預備知識

1.1 模糊粗糙集屬性約簡

1.1.1 模糊粗糙集

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

設U是一非空論域，R是U上一模糊二元關系，如果R滿足以下：

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

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

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

則稱R為模糊等價關系.

對于任意x∈U，如果R是一個模糊相似關系，D是經典決策屬性，di是決策類，x對于di的隸屬度定義為：

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

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

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

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

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

1.1.2 辨識矩陣[12]

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

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

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

1.2.1 分層分類

本論文針對的是基于樹的層次類結構，其他結構暫不考慮.層次結構信息在決策類之間強加一種父子關系，這意味著屬于特定類的實例也屬于它的所有祖先類.分類通?？梢孕问交乇硎緸?D,)，其中D是所有類的集合，“”表示從屬關系，它是具有以下屬性[13]的關系的子類:

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

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

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

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

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

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

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

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

命題1已知是一個分層分類問題，R是子集B?C所誘導的模糊相似關系，di是樣本的標記, 對于x∈U，有：

命題2已知是一個分層分類問題，R1和R2是子集B1和B2分別誘導的兩個模糊相似關系，且R1?R2，di是樣本的決策類, 對于x∈U，有：

2 分層特征選擇

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

2.1 層次辨識矩陣

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

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

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

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

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

定理1：假設P?C，那么P包含C的一個相對約簡，當且僅當對于任意cij≠?有P∩cij≠?成立.

2.2 尋找約簡

在本節(jié)中，首先用一個例子說明行文的動機.然后利用條件屬性的相對辨識關系來刻畫層次辨識矩陣中的極小元素.最后，設計了一個算法找到屬性約簡集.

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

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

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

定義5對于一個分層分類問題，R是U上的模糊等價關系.我們稱二元關系DIS(a)為條件屬性a對決策屬性的相對辨識關系，定義為：

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

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

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

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

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

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

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

對于Sij，Nij和cij，有下面的定理：

定理2.1對于任意(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對于兩個極小元素cij和cst，有(xi,xj)?Sst和(xs,xt)?Sij.

證明：對于兩個極小元素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當且僅當Sij是極大的，cij是MDtree(U,C)中的極小元素.

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

“?”：已知Sij是極大的，要證cij是極小元素，即對于任意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對應的極大樣本對集Sij可以刪除所有的Sst?Sij，但不會完全刪除其他極小元素cst對應的Sst.

推論3Nij最小的樣本對(xi,xj)對應一個極小元素cij.

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

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

推論4當且僅當DIS(C)=?時，所有極小元素cij對應的Sij都從DIS(C)中被刪除.

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

結合極小元素的這些性質，我們設計以下算法來得到條件屬性集的一個約簡：

算法:基于樣本對選擇的分層特征選擇算法(HierSPS-FS) 輸入:U,C,Dtree輸出:特征子集REDUCT1 初始化REDUCT為空集;2 計算每個特征的相對辨識關系DIS(a),DIS(C)和Nij;3 while(DIS(C)≠?) do4 找到DIS(C)中的最小值Ni0j0對應的(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設為inf;12 end if13 end for14 end while15 返回約簡集REDUCT;

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

3 評價方法

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

圖1 動物的類別層次Fig.1 Categorical irony level of animals

3.1 樹誘導損失

3.2 分層F1測度

分層F1測度的定義為:

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

4 實驗分析

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

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

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

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

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

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

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

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

4.2 實驗步驟

為了評估文中的分層特征選擇算法的性能，進行了一些對比實驗.具體的實驗研究安排如下：

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

2) 使用分層評價指標進行比較：將所提出的算法與平面特征選擇算法進行了比較.這里采用的平面特征選擇算法也是基于模糊粗糙集的特征選擇算法，CHEN等[16]定義了條件屬性的相對辨識關系，用相對辨識關系來表征模糊辨識矩陣中的極小元素，進而提出了一個基于模糊粗糙集的約簡算法這里記為FlatSPS-FS.

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

4.3 實驗結果分析

在以下幾方面來評估所提出的特征選擇算法的性能.

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

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

圖2 運行時間對比Fig.2 Comparison of runtime

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

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

2) 使用分層評價指標進行比較

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

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

表3 不同數(shù)據(jù)集上的分層評價指標

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

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

(2) 對于任意一個數(shù)據(jù)集來說，F(xiàn)_LCA的值都小于F_Hierarchical的值.這是因為有許多共同的祖先往往會使錯誤變得過于嚴重.LCA-F1可以避免此類錯誤.

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

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

表4 不同分層方法的Hierarchical_F1測度比較

5 結 論

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

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