折延宏，黃婉麗，賀曉麗，錢 婷

1.西安石油大學(xué) 理學(xué)院，西安 710065

2.西安石油大學(xué) 計(jì)算機(jī)學(xué)院，西安 710065

在大數(shù)據(jù)時(shí)代，數(shù)據(jù)標(biāo)簽類型和數(shù)量急劇增加，標(biāo)簽之間往往具有某種特殊的關(guān)系，其中層次結(jié)構(gòu)[1-3]最具有代表性，包括樹結(jié)構(gòu)和圖結(jié)構(gòu)。標(biāo)簽具有層次結(jié)構(gòu)的分類問(wèn)題是當(dāng)今的研究熱點(diǎn)。用層次結(jié)構(gòu)進(jìn)行大規(guī)模分類學(xué)習(xí)有很大的優(yōu)勢(shì)，對(duì)于超多類問(wèn)題，可以利用層次結(jié)構(gòu)將超多類問(wèn)題分解為多個(gè)子類學(xué)習(xí)任務(wù)，能有效提高建模的效率。

基于粒計(jì)算思想的分層分類建模是一種符合人腦認(rèn)知規(guī)律的數(shù)據(jù)建模方法。Bellmund 等人[4]在Science上發(fā)表的論文認(rèn)為人腦認(rèn)知和思維過(guò)程依靠多粒度的知識(shí)層次結(jié)構(gòu)完成。Aronov等人[5]在Nature上發(fā)表的論文認(rèn)為人腦的思考和認(rèn)知過(guò)程所形成的知識(shí)呈現(xiàn)出一種低維的幾何結(jié)構(gòu)。文獻(xiàn)[6]給出了一種在樣本標(biāo)記粒度不夠細(xì)化的情況下利用層次信息進(jìn)行建模的方法。文獻(xiàn)[7]給出了一種能同時(shí)體現(xiàn)共有特征與固有特征的分層特征選擇方法。在實(shí)際應(yīng)用中，用戶需求的多層次/多粒度也決定了挖掘任務(wù)的多層次/多粒度特征。而粒計(jì)算是模擬人類思考和解決大規(guī)模復(fù)雜問(wèn)題的自然模式[8-10]。模糊粗糙集是粒計(jì)算中的一個(gè)重要模型，因此利用模糊粗糙集對(duì)具有層次結(jié)構(gòu)的數(shù)據(jù)進(jìn)行?；幚砜梢愿浞值貙W(xué)習(xí)數(shù)據(jù)中蘊(yùn)含的信息。

目前，模糊粗糙集[11-12]在處理平面分類（與分層分類相對(duì)應(yīng)）問(wèn)題中已有許多應(yīng)用。許多學(xué)者將模糊粗糙集理論應(yīng)用到特征選擇（也稱為屬性約簡(jiǎn)）中，采用依賴度[13-14]、條件熵[15-16]、辨識(shí)矩陣[17]和相對(duì)辨識(shí)關(guān)系[18-19]等作為特征選擇的評(píng)價(jià)指標(biāo)?；谝蕾嚭瘮?shù)的啟發(fā)式算法[11]是模糊決策系統(tǒng)求約簡(jiǎn)的先驅(qū)工作。之后Bhatt 等人[20]定義了一個(gè)緊湊域來(lái)降低文獻(xiàn)[11]的時(shí)間復(fù)雜度。Hu 等人[21]提出了基于信息熵的模糊粗糙集的特征選擇算法。為了找到合適的約簡(jiǎn)，Tsang 等人[22]引入了基于辨識(shí)矩陣的方法來(lái)處理模糊粗糙集。Chen 等人[18]提出了樣本對(duì)選擇方法來(lái)搜索可識(shí)別矩陣中的所有最小元素，只使用所有的最小元素來(lái)尋找模糊決策系統(tǒng)的約簡(jiǎn)。Wang等人[14]提出了一種基于模糊粗糙集的特征選擇擬合模型，以更好地反映所選擇特征子集的分類能力。

模糊粗糙集理論于2019 年首次被應(yīng)用到分層分類特征選擇的研究中[23]，文中利用類別之間的層次結(jié)構(gòu)，用排他策略、包含策略和兄弟策略來(lái)縮小負(fù)樣本空間，從而減少求解下近似的計(jì)算量，提出基于兄弟策略的依賴度計(jì)算算法和特征選擇算法。排他策略與平面的分類相同，即如果A 是正樣本，A 以外的其他樣本是負(fù)樣本，在該策略下的負(fù)樣本搜索空間非常大，因此使用合理的策略非常重要，目前大多關(guān)注的是兄弟策略，該策略只把A的兄弟節(jié)點(diǎn)中樣本看作負(fù)樣本，這種策略考慮的是同層次的橫向關(guān)系，忽略了不同層次之間樣本的關(guān)系。包含策略比兄弟策略更復(fù)雜，不僅考慮同層的橫向關(guān)系，也考慮上下層之間的父子關(guān)系。然而，已有的研究工作大多關(guān)注的是兄弟策略，相比而言包含策略考慮的層次范圍更廣，可以更好地彌補(bǔ)兄弟策略未能考慮上下層關(guān)系的缺點(diǎn)，這也是本文使用包含策略的一個(gè)研究動(dòng)機(jī)。

此外，已有的分層分類的特征選擇研究大多利用標(biāo)簽的層次關(guān)系構(gòu)建正則項(xiàng)、最小化損失函數(shù)和正則項(xiàng)，基于此建立優(yōu)化模型[24-27]。然而，上述的方法都是針對(duì)靜態(tài)數(shù)據(jù)集?，F(xiàn)實(shí)場(chǎng)景中數(shù)據(jù)是不斷動(dòng)態(tài)增加的，相應(yīng)地，一些基于動(dòng)態(tài)數(shù)據(jù)信息的增量學(xué)習(xí)方法[28-32]被提出。然而，這些方法大多局限于平面分類中，分層分類中涉及的較少。Fan 等人[33]介紹了一種基于多核模糊粗糙集的增量層次分類方法，但它們更側(cè)重于目標(biāo)概念的粗糙近似的更新，而不是特征選擇。Luo 等人[34]提出了一種迭代的增量粗糙集方法。而在分層分類下考慮使用包含策略的模糊粗糙集的增量研究也非常必要。

綜上，本文研究的動(dòng)機(jī)如下：（1）在分層分類問(wèn)題中，考慮模糊粗糙集的增量可以更好地模擬現(xiàn)實(shí)數(shù)據(jù)。（2）已有的研究大多針對(duì)的是數(shù)據(jù)標(biāo)簽只分布在葉子節(jié)點(diǎn)，現(xiàn)實(shí)世界中標(biāo)簽具有任意性，研究標(biāo)簽分布在任意節(jié)點(diǎn)更具有現(xiàn)實(shí)意義。（3）包含策略能夠更好地學(xué)習(xí)標(biāo)簽之間的層次信息，更適合應(yīng)用標(biāo)簽分布在任意節(jié)點(diǎn)的場(chǎng)景中。

因此，將針對(duì)標(biāo)簽具有樹結(jié)構(gòu)，且標(biāo)簽分布在葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)情形的動(dòng)態(tài)數(shù)據(jù)集，將包含策略應(yīng)用到模糊粗糙集模型中，基于此研究分層分類的增量特征選擇算法?；谖墨I(xiàn)[23]提出一個(gè)基于包含策略的模糊粗糙集模型，設(shè)計(jì)一個(gè)非增量特征選擇算法，并引入增量機(jī)制，即當(dāng)有新樣本加入時(shí)，研究下近似、正域和依賴度的增量更新策略。由此，本文設(shè)計(jì)一個(gè)增量特征選擇算法，并提出基于兩種不同策略的增量特征選擇框架。最后，通過(guò)數(shù)值實(shí)驗(yàn)驗(yàn)證所提算法是有效的。

本文主要貢獻(xiàn)如下：

（1）提出基于包含策略的模糊粗糙集模型，并設(shè)計(jì)基于該模型的非增量特征選擇算法；

（2）在該模型中引入增量機(jī)制，提出增量更新方法，以及基于包含策略的依賴度更新算法和增量特征選擇算法，兩個(gè)版本的增量特征選擇框架；

（3）研究動(dòng)態(tài)數(shù)據(jù)集，且標(biāo)簽分布在內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)，使得所提算法適用范圍更廣。

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

本文所使用的符號(hào)含義如表1所示。

表1 符號(hào)描述Table 1 Symbol description

使用高斯函數(shù)[36]來(lái)計(jì)算模糊T-相似關(guān)系：

其中，σ為參數(shù)，為x與y之間的距離，a(x)為x在屬性a下的值。

序?qū)?Dtree,?)[23]用來(lái)描述決策類的層次結(jié)構(gòu)，Dtree={d0,d1,…,dl}，其中d0為根節(jié)點(diǎn)，不是真實(shí)的類，l是類的個(gè)數(shù)?！?”代表“子類”關(guān)系且滿足以下條件：（1）反對(duì)稱性?di,dj∈Dtree，如果di?dj，那 么dj?di；（2）反自反性?di∈Dtree，di?di；（3）傳遞性?di,dj,dk∈Dtree，如果di?dj，dj?dk，那么di?dk。

例 1圖1 是一個(gè)Dtree的示例，Dtree={d0,d1,…,d6}，其中d0是樹結(jié)構(gòu)的根節(jié)點(diǎn)，不是真實(shí)的標(biāo)簽，不參與求子孫節(jié)點(diǎn)和包含節(jié)點(diǎn)的運(yùn)算。以d1為例，d1的子孫節(jié)點(diǎn)為des(d1)={d3,d4}，d1的包含節(jié)點(diǎn)inc(d1)={d1,d3,d4}，d1的包含負(fù)節(jié)點(diǎn)(d1)={d2,d5,d6}。

圖1 標(biāo)簽的樹結(jié)構(gòu)示例Fig.1 Example of tree structure for labels

2 基于包含策略的非增量特征選擇

本章先研究基于包含策略的模糊粗糙集模型，基于此，設(shè)計(jì)非增量依賴度計(jì)算算法和非增量特征選擇算法。

2.1 基于包含策略的模糊粗糙集模型

在分層分類問(wèn)題中，負(fù)樣本只是選取了U中除di其余樣本的一部分，因此當(dāng)x?di時(shí)，不一定滿足為了下近似具有更好的性質(zhì)，將文獻(xiàn)[23]中基于包含策略的下近似修正如下。

定義1在分層決策表中，RB是由B?C導(dǎo)出的模糊T-相似關(guān)系，di的下近似可以定義為：

定義2在分層決策表中，RB是由B?C導(dǎo)出的模糊T-相似關(guān)系，關(guān)于屬性集B的正域可以定義為：

通過(guò)定義2可以得出以下結(jié)論。

由性質(zhì)1 可知依賴度關(guān)于屬性集的變化是單調(diào)的，這是依賴度可以作為特征選擇的評(píng)價(jià)指標(biāo)的依據(jù)。下面基于定義3 提出一個(gè)適用于分層分類的屬性約簡(jiǎn)定義。

2.2 算法

基于包含策略的依賴度的定義，本文提出非增量依賴度計(jì)算算法和非增量特征選擇算法。

記RB(x,y) 中的 (DB(x,y))2為(x,y)。稱為距離平方矩陣。將簡(jiǎn)記為(Dtree)。

算法1基于包含策略的非增量依賴度計(jì)算算法（Inc-NIDC）

算法1 是基于包含策略的非增量依賴度計(jì)算算法。第1 步初始化為大于1 的數(shù)，第5 步計(jì)算距離平方矩陣，時(shí)間復(fù)雜度為O(|C|)；第4～10 步是計(jì)算，由于第2 步和第3 步是個(gè)雙循環(huán)，第4～10步被計(jì)算了|d1|+|d2|+…+|dl|=|U|次，因此第2～13步的時(shí)間復(fù)雜度為O(|C||U|2)；第14 步是計(jì)算關(guān)于B的依賴度。綜上，算法1的時(shí)間復(fù)雜度為O(|C||U|2)。

算法2基于包含策略的非增量特征選擇算法（Inc-NIFS）

算法2是基于包含策略的非增量特征選擇算法?！皉em”表示剩余屬性，“red”表示屬性約簡(jiǎn)。第2 步是求U的劃分，時(shí)間復(fù)雜度為O(l|U|)。第3 步計(jì)算每個(gè)di∈U/Dtree的包含負(fù)節(jié)點(diǎn)和包含負(fù)樣本，時(shí)間復(fù)雜度為O(l2)。第4步通過(guò)Inc-NIDC計(jì)算(Dtree)，時(shí)間復(fù)雜度為O(|C||U|2)。第5～12 步通過(guò)Inc-NIDC 計(jì)算依賴度，采用啟發(fā)式思想添加屬性，時(shí)間復(fù)雜度為O(|C|3|U|2)。第13～19 步刪除B中的冗余屬性直到滿足定義4 中的第二個(gè)條件為止，時(shí)間復(fù)雜度為O(|C|2|U|2)。綜上，算法2的時(shí)間復(fù)雜度為O(|C|3|U|2)。

3 基于包含策略的增量特征選擇

本章首先研究基于包含策略的模糊粗糙集的增量更新方法，然后基于此研究其增量算法，并基于兩種特征選擇策略提出兩個(gè)版本的增量特征框架。

3.1 基于包含策略的模糊粗糙集的增量更新方法

本節(jié)首先研究當(dāng)分層決策表加入一些新樣本時(shí)，下近似的增量更新方法，進(jìn)而探究正域以及依賴度的更新方法。

3.1.1 下近似的增量更新

將樣本分為x∈U和x∈ΔU兩種情況來(lái)研究下近似的變化。

（1）情況1：x∈U。

首先尋找U中的下近似可能發(fā)生變化的節(jié)點(diǎn)。當(dāng)使用包含策略時(shí)，下近似可能發(fā)生改變的節(jié)點(diǎn)與新加入樣本所屬的節(jié)點(diǎn)有關(guān)（這里的節(jié)點(diǎn)也是決策表中的類）。從定義1中，可以看到y(tǒng)的范圍影響下近似的變化。現(xiàn)假設(shè)新加入樣本在同一個(gè)類dt中，如果di(x∈di) 的包含負(fù)樣本中含有dt的樣本，即dt∈Dtree(des(di)∪{di})，則di的下近似可能改變。由于這些節(jié)點(diǎn)關(guān)系較復(fù)雜，將問(wèn)題轉(zhuǎn)化為尋找下近似不受加入樣本影響的節(jié)點(diǎn)。當(dāng)dt∈des(di) ∪{di}時(shí)，di的下近似不會(huì)改變。等價(jià)于存在新加入樣本的類為dt，在anc(dt)∪{dt}中的節(jié)點(diǎn)下近似不會(huì)發(fā)生改變。也就是Dtree(anc(dt) ∪{dt})中節(jié)點(diǎn)的下近似可能會(huì)發(fā)生變化。將所有下近似可能發(fā)生變化的節(jié)點(diǎn)集合記為

（2）情況2：x∈ΔU。

ΔU是新加入的樣本，在原分層決策表中沒(méi)有計(jì)算過(guò)x在所屬類的下近似中的隸屬度，因此需要額外而下近似的變化只與y有關(guān)，只判斷加入樣本后每個(gè)節(jié)點(diǎn)的包含負(fù)節(jié)點(diǎn)是否有新加入樣本。

表2 原分層決策表的示例數(shù)據(jù)Table 2 Example data of original hierarchical decision table

表3 添加樣本的示例數(shù)據(jù)Table 3 Example data of incoming samples

圖2 添加樣本時(shí)樹結(jié)構(gòu)變化Fig.2 Change of tree structure while incoming samples

3.1.2 正域的增量更新

3.1.3 依賴度的增量更新

通過(guò)定理3 和定義3 可得到以下依賴度的增量更新定理。

3.2 算法

基于模糊粗糙集的增量更新方法，設(shè)計(jì)一個(gè)基于包含策略的依賴度更新算法、增量特征選擇算法和兩個(gè)版本的增量特征選擇框架。

算法3基于包含策略的依賴度更新算法（Inc-IDU）

算法3 是基于包含策略的依賴度更新算法。第2～10 步是增量更新S中樣本正域的隸屬度，對(duì)這部分樣本的正域隸屬度進(jìn)行求和，時(shí)間復(fù)雜度為；第11～13 步是計(jì)算U-S中樣本的正域隸屬度之和，時(shí)間復(fù)雜度為O(|U-S|)；第14～19步是計(jì)算ΔU中樣本的正域隸屬度之和，時(shí)間復(fù)雜度為。綜上，算法3 的時(shí)間復(fù)雜度為

算法4基于包含策略的增量特征選擇算法（Inc-IFS）

算法4 是基于包含策略的增量特征選擇算法。第2 步求ΔU的類劃分，時(shí)間復(fù)雜度為O(l|U|)；第3 步計(jì)算，時(shí)間復(fù)雜度為O(k) ；第6 步通過(guò)Inc-IDU“Inc-NIDC+”和“Inc-NIDC-”的時(shí)更新依賴度，時(shí)間復(fù)雜度為間復(fù)雜度為O(|U|2)，第7～15 步為添加屬性策略，從剩余屬性中一直添加屬性，直到滿足定義4 中的條件（1）為止，此時(shí)間復(fù)雜度為O(|C|2|U|2)；第16～23 步為刪除冗余屬性策略，刪除B中的元素，直到滿足定義4的條件（2）為止，此時(shí)間復(fù)雜度為O(|C||U|2)。綜上，算法4 的時(shí)間復(fù)雜度為O(|C|2|U|2)。

綜上易得，算法4的時(shí)間復(fù)雜度小于算法2的時(shí)間復(fù)雜度。另外，由于算法3的時(shí)間復(fù)雜度也小于算法1的時(shí)間復(fù)雜度。

接下來(lái)，基于兩種策略提出兩個(gè)增量特征選擇框架，用以解決批處理大規(guī)模數(shù)據(jù)集的分層分類問(wèn)題。先將訓(xùn)練集劃分為N份子數(shù)據(jù)集，當(dāng)不同的子數(shù)據(jù)集加入當(dāng)前數(shù)據(jù)集T時(shí)采用兩種不同的策略尋找屬性約簡(jiǎn)。策略1（對(duì)應(yīng)算法5）：在每次子數(shù)據(jù)集加入時(shí)只執(zhí)行添加屬性策略，當(dāng)?shù)贜個(gè)子數(shù)據(jù)集都完成上述策略后再執(zhí)行刪除冗余屬性策略；策略2（對(duì)應(yīng)算法6）：在每次子數(shù)據(jù)集加入時(shí)執(zhí)行添加屬性策略和刪除冗余屬性策略。

算法5增量算法的框架1（Inc-IFS-v1）

算法6增量算法的框架2(Inc-IFS-v2)

由于策略1 只進(jìn)行一次刪除冗余屬性策略，從理論上看，Inc-IFS-v1 的運(yùn)行時(shí)間小于Inc-IFS-v2。

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

本章先從運(yùn)行時(shí)間、所選擇特征個(gè)數(shù)、FH測(cè)度（基于F1的分層分類準(zhǔn)確率度量）[37-38]和平均TIE 四個(gè)指標(biāo)將FFS-HC[23]與本文所提的Inc-NIDC、Inc-IFSv1 和Inc-IFS-v2 進(jìn)行對(duì)比。然后對(duì)Inc-IFS-v1 和Inc-IFS-v2 進(jìn)行參數(shù)ε敏感度分析。最后通過(guò)實(shí)驗(yàn)結(jié)果對(duì)所提的三個(gè)特征選擇算法進(jìn)行評(píng)價(jià)。

TIE（tree induced error）為樹誘導(dǎo)誤差[39]，TIE 值會(huì)隨著樣本量的增多而變大。平均TIE不受測(cè)試樣本量影響，可以更好地度量算法性能，因此這里采用平均TIE 來(lái)表示算法性能

4.1 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)環(huán)境：Intel?CoreTMi5-7200U CPU@2.50 GHz 2.71 GHz 12.0 GB，MATLAB R2016a。

數(shù)據(jù)集：表4 是在分層分類問(wèn)題中經(jīng)常使用的數(shù)據(jù)集，這些數(shù)據(jù)集的真實(shí)標(biāo)簽在葉子節(jié)點(diǎn)，由于樹結(jié)構(gòu)中父子節(jié)點(diǎn)存在語(yǔ)義關(guān)系，子節(jié)點(diǎn)樣本隱含在父節(jié)點(diǎn)中，為了構(gòu)造出本文所研究類型的數(shù)據(jù)集，把葉子節(jié)點(diǎn)中部分樣本的標(biāo)簽提升為其祖先節(jié)點(diǎn)，并使每個(gè)節(jié)點(diǎn)中的樣本盡可能地均勻分布，此時(shí)標(biāo)簽的個(gè)數(shù)記為d′，如表4 所示。

表4 數(shù)據(jù)集Table 4 Datasets

為了使上層節(jié)點(diǎn)具有子節(jié)點(diǎn)樣本盡可能多的信息，將每個(gè)葉子節(jié)點(diǎn)中樣本按一定比例隨機(jī)劃分份數(shù)為dlayer，向上層節(jié)點(diǎn)劃分。numsamples表示該節(jié)點(diǎn)中樣本個(gè)數(shù)，numnodes表示該節(jié)點(diǎn)的父節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)，dlayer表示需向上泛化的層數(shù)。該比例大小也會(huì)隨著向上泛化的迭代過(guò)程而動(dòng)態(tài)變化。這樣既使葉子節(jié)點(diǎn)均勻，又使上層節(jié)點(diǎn)的樣本分布均勻，且盡可能均勻地包含下層節(jié)點(diǎn)樣本，可以避免樣本分布的不平衡。

分類器：支持向量機(jī)（support vector machine,SVM[40]）、K 近 鄰（k-nearest neighbors，KNN[41]）（k設(shè)為常用值3）、隨機(jī)森林（random forest，RF[42]）。

數(shù)據(jù)處理：（1）對(duì)數(shù)據(jù)集進(jìn)行最大最小歸一化處的層數(shù)。該比例大小也會(huì)隨著向上泛化的迭代過(guò)程而動(dòng)態(tài)變化。這樣既使葉子節(jié)點(diǎn)均勻，又使上層節(jié)點(diǎn)的樣本分布均勻，且盡可能均勻地包含下層節(jié)點(diǎn)樣本，可以避免樣本分布的不平衡。

分類器：支持向量機(jī)（support vector machine,SVM[40]）、K 近鄰（k-nearest neighbors，KNN[41]）（k設(shè)為常用值3）、隨機(jī)森林（random forest，RF[42]）。

4.2 四個(gè)算法對(duì)比

這部分，通過(guò)對(duì)比FFS-HC[23]、Inc-NIFS、Inc-IFSv1 和Inc-IFS-v2 算法的運(yùn)行時(shí)間、所選特征個(gè)數(shù)、FH測(cè)度和平均TIE 來(lái)評(píng)價(jià)所提的三個(gè)算法，結(jié)果如表5和圖3、圖4所示。

圖3 4個(gè)算法所選特征個(gè)數(shù)對(duì)比Fig.3 Comparison of the number of selected features for 4 algorithms

圖4 4個(gè)算法的FH值對(duì)比Fig.4 Comparison of FH for 4 algorithms

表5 算法FFS-HC、Inc-NIFS、Inc-IFS-v1和Inc-IFS-v2的運(yùn)行時(shí)間對(duì)比Table 5 Comparison of running time for FFS-HC,Inc-NIFS,Inc-IFS-v1 and Inc-IFS-v2 algorithms 單位：s

參數(shù)設(shè)置：Inc-NIFS、Inc-IFS-v1 和Inc-IFS-v2 中令ε=0.01，σ=0.2，N=10。

表5 是FFS-HC、Inc-NIFS、Inc-IFS-v1 和Inc-IFSv2的運(yùn)行時(shí)間。加粗表示運(yùn)行時(shí)間最短。在Bridges數(shù)據(jù)集上Inc-NIFS 的運(yùn)行時(shí)間最短，這是因?yàn)檫@個(gè)數(shù)據(jù)集太小，而樣本又分多次到達(dá)，導(dǎo)致增量計(jì)算時(shí)間較長(zhǎng)；而在其他大規(guī)模數(shù)據(jù)集上除了SAIAPR 外，Inc-IFS-v1 的運(yùn)行時(shí)間最短，且與FFS-HC 和Inc-NIFS 的運(yùn)行時(shí)間差距非常大。尤其在VOC 數(shù)據(jù)集上，F(xiàn)FS-HC 約是Inc-IFS-v1 的7.3 倍，Inc-NIFS 約是Inc-IFS-v1的68.5倍。在SAIAPR5000數(shù)據(jù)集上，Inc-NIFS 約是Inc-IFS-v1的311.8倍。從實(shí)驗(yàn)中也可以看出在所有數(shù)據(jù)集上Inc-IFS-v1 比Inc-IFS-v2 的時(shí)間效率更高。

圖3 是FFS-HC、Inc-NIFS、Inc-IFS-v1 和Inc-IFSv2 的所選特征個(gè)數(shù)。在所有數(shù)據(jù)集上FFS-HC 所選特征個(gè)數(shù)小于其他3 個(gè)算法；Inc-NIFS、Inc-IFS-v1 和Inc-IFS-v2 所選特征個(gè)數(shù)基本上區(qū)別不大；FFS-HC在SAIAPR5000 數(shù)據(jù)集上所選特征個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于其他3個(gè)算法。

圖4 是FFS-HC、Inc-NIFS、Inc-IFS-v1 和Inc-IFSv2 的FH測(cè)度，其中PF 表示全部特征，加粗表示4 個(gè)算法中FH值最大的。本文分別在分類器SVM、KNN和RF 上對(duì)比不同算法的效果。在數(shù)據(jù)集DD 上，算法之間的FH測(cè)度受分類器的影響，4 個(gè)算法的FH值在分類器SVM 和KNN 上都大于PF，而在分類器RF上卻均小于PF；在VOC數(shù)據(jù)集上，F(xiàn)FS-HC的FH值在KNN 和RF 上最大，其余數(shù)據(jù)集上Inc-NIFS 的FH值最大的情況居多，有些情況下，Inc-IFS-v1 最大。在大部分?jǐn)?shù)據(jù)集上，Inc-NIFS、Inc-IFS-v1 和Inc-IFS-v2之間的FH值基本一致，相差不超過(guò)1 個(gè)百分點(diǎn)。因此，可以充分說(shuō)明Inc-NIFS、Inc-IFS-v1 和Inc-IFS-v2可行并且有效。

表6 是FFS-HC、Inc-NIFS、Inc-IFS-v1 和Inc-IFSv2 的平均TIE 值對(duì)比。加粗表示在對(duì)應(yīng)分類器下平均TIE 值最小。平均TIE 值越小，表示算法越好。從全部數(shù)據(jù)集上看，SAIAPR5000 數(shù)據(jù)集上的算法的平均TIE 值大于其他數(shù)據(jù)集，說(shuō)明在SAIAPR5000 這個(gè)數(shù)據(jù)集上分類誤差都大于其他數(shù)據(jù)集；從算法角度看，在分類器SVM上Inc-NIFS更占優(yōu)勢(shì)，但是這些算法差別不大，相差不超過(guò)0.3。整體來(lái)看，F(xiàn)FS-HC、Inc-NIFS、Inc-IFS-v1 和Inc-IFS-v2 的平均TIE 幾乎沒(méi)有差別。

綜合表5、表6 和圖3、圖4，從運(yùn)行時(shí)間上看，Inc-IFS-v1的時(shí)間效果最好，Inc-IFS-v2次之；從分類效果上看，Inc-NIFS、Inc-IFS-v1 和Inc-IFS-v2 都不低于FFS-HC，且3 個(gè)算法之間差別不大。綜合時(shí)間和分類效果，Inc-IFS-v1 能在最短時(shí)間內(nèi)完成特征選擇，且最大程度地保證分類精度。

4.3 Inc-IFS-v1 和Inc-IFS-v2 的參數(shù)敏感性分析

本節(jié)從運(yùn)行時(shí)間、所選擇特征個(gè)數(shù)、FH測(cè)度方面分析 Inc-IFS-v1 和 Inc-IFS-v2 的 ε 在{0.05,0.01,0.005,0.001,0.000 5,0.000 1}上的敏感度，參數(shù)σ=0.2，N=10，結(jié)果如圖5～圖7所示。

圖5 Inc-IFS-v1和Inc-IFS-v2的運(yùn)行時(shí)間對(duì)比Fig.5 Comparison of running time for Inc-IFS-v1 and Inc-IFS-v2

圖5 是Inc-IFS-v1 和Inc-IFS-v2 隨著閾值ε 的減小運(yùn)行時(shí)間的變化。閾值ε越小，而添加屬性的條件就越嚴(yán)格，對(duì)應(yīng)的運(yùn)行時(shí)間就越長(zhǎng)。在VOC 數(shù)據(jù)集上，Inc-IFS-v2 的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)大于其他參數(shù)，可能因?yàn)樵谶@個(gè)參數(shù)下每次到達(dá)子數(shù)據(jù)集都會(huì)進(jìn)行添加屬性和刪除冗余屬性策略，而再次增加樣本后原屬性約簡(jiǎn)總不滿足，需要再次添加屬性和刪除冗余屬性，VOC 有1 000 個(gè)屬性，會(huì)使運(yùn)行時(shí)間差距更明顯。綜合來(lái)看，Inc-IFS-v1 和Inc-IFS-v2 的運(yùn)行時(shí)間隨著閾值減小變長(zhǎng)，并且Inc-IFS-v1的運(yùn)行時(shí)間總小于Inc-IFS-v2。

圖6 是Inc-IFS-v1 和Inc-IFS-v2 所選擇特征的個(gè)數(shù)比較。從圖中可以看到，閾值ε越小，屬性約簡(jiǎn)的條件越嚴(yán)格，Inc-IFS-v1 和Inc-IFS-v2 所選擇特征的個(gè)數(shù)越多，且Inc-IFS-v1 和Inc-IFS-v2 所選擇特征的個(gè)數(shù)基本差別不大。在VOC數(shù)據(jù)集上，當(dāng)ε=0.000 5時(shí)，Inc-IFS-v1只挑選了7個(gè)特征，在CLEF數(shù)據(jù)集上，當(dāng)ε=0.005 時(shí)，Inc-IFS-v2 只挑選了1 個(gè)特征。這可能因?yàn)檫@種情況下許多特征作為冗余屬性被刪除，而這些少量特征仍然符合約簡(jiǎn)定義。

圖7 為Inc-IFS-v1 和Inc-IFS-v2 的FH值。在DD數(shù)據(jù)集上，閾值ε<0.005 時(shí)，Inc-IFS-v1 和Inc-IFS-v2的FH值在分類器SVM 和KNN 上減小?？赡苁且?yàn)殡S閾值ε減少，所選特征個(gè)數(shù)變多，多了一些干擾性特征，使得分類精度下降。整體上看，隨著閾值ε的減少，Inc-IFS-v1 和Inc-IFS-v2 的FH值呈不明顯的上升趨勢(shì)。綜上，Inc-IFS-v1 和Inc-IFS-v2 的分類精度隨著閾值ε的變化，敏感性較弱。

綜合圖5～圖7，從時(shí)間上看，隨著閾值ε變小，Inc-IFS-v1 和Inc-IFS-v2 的運(yùn)行時(shí)間越長(zhǎng)，即運(yùn)行時(shí)間的敏感性較大；從所選特征個(gè)數(shù)和分類精度看，隨著閾值ε變小，在有些數(shù)據(jù)集上分類精度有上升趨勢(shì)，在有些數(shù)據(jù)集上沒(méi)有明顯變化。

5 總結(jié)與展望

本文給出了包含策略和基于包含策略的模糊粗糙集新的形式化定義，提出了基于包含策略的模糊粗糙集模型，并設(shè)計(jì)了一個(gè)非增量特征選擇算法Inc-NIFS。然后引入依賴度的增量機(jī)制，設(shè)計(jì)距離平方矩陣來(lái)縮短添加屬性過(guò)程的時(shí)間。由此，提出了增量特征選擇算法Inc-IFS，以及兩種增量特征選擇框架Inc-IFS-v1 和Inc-IFS-v2，兩者效率均高于Inc-NIFS，且Inc-IFS-v1的效率最高。

除了樣本增加外，還包括特征添加和特征值動(dòng)態(tài)變化的情況。分層分類學(xué)習(xí)中，可以選擇的策略也多種多樣，除了包含策略，還有兄弟策略、排他策略、排他兄弟策略、排他包含策略等。這些均可作為未來(lái)的研究工作。在未來(lái)的研究中，將考慮隨著樣本到達(dá)，基于兄弟策略的模糊粗糙集增量，與本文所提的算法進(jìn)行對(duì)比分析；將研究在特征動(dòng)態(tài)增加的情況下基于包含策略、兄弟策略以及其他策略的增量機(jī)制。