面向層次結構數據的增量特征選擇

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

1.西安石油大學 理學院，西安 710065

2.西安石油大學 計算機學院，西安 710065

在大數據時代，數據標簽類型和數量急劇增加，標簽之間往往具有某種特殊的關系，其中層次結構[1-3]最具有代表性，包括樹結構和圖結構。標簽具有層次結構的分類問題是當今的研究熱點。用層次結構進行大規模分類學習有很大的優勢，對于超多類問題，可以利用層次結構將超多類問題分解為多個子類學習任務，能有效提高建模的效率。

基于粒計算思想的分層分類建模是一種符合人腦認知規律的數據建模方法。Bellmund 等人[4]在Science上發表的論文認為人腦認知和思維過程依靠多粒度的知識層次結構完成。Aronov等人[5]在Nature上發表的論文認為人腦的思考和認知過程所形成的知識呈現出一種低維的幾何結構。文獻[6]給出了一種在樣本標記粒度不夠細化的情況下利用層次信息進行建模的方法。文獻[7]給出了一種能同時體現共有特征與固有特征的分層特征選擇方法。在實際應用中，用戶需求的多層次/多粒度也決定了挖掘任務的多層次/多粒度特征。而粒計算是模擬人類思考和解決大規模復雜問題的自然模式[8-10]。模糊粗糙集是粒計算中的一個重要模型，因此利用模糊粗糙集對具有層次結構的數據進行粒化處理可以更充分地學習數據中蘊含的信息。

目前，模糊粗糙集[11-12]在處理平面分類（與分層分類相對應）問題中已有許多應用。許多學者將模糊粗糙集理論應用到特征選擇（也稱為屬性約簡）中，采用依賴度[13-14]、條件熵[15-16]、辨識矩陣[17]和相對辨識關系[18-19]等作為特征選擇的評價指標。基于依賴函數的啟發式算法[11]是模糊決策系統求約簡的先驅工作。之后Bhatt 等人[20]定義了一個緊湊域來降低文獻[11]的時間復雜度。Hu 等人[21]提出了基于信息熵的模糊粗糙集的特征選擇算法。為了找到合適的約簡，Tsang 等人[22]引入了基于辨識矩陣的方法來處理模糊粗糙集。Chen 等人[18]提出了樣本對選擇方法來搜索可識別矩陣中的所有最小元素，只使用所有的最小元素來尋找模糊決策系統的約簡。Wang等人[14]提出了一種基于模糊粗糙集的特征選擇擬合模型，以更好地反映所選擇特征子集的分類能力。

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

此外，已有的分層分類的特征選擇研究大多利用標簽的層次關系構建正則項、最小化損失函數和正則項，基于此建立優化模型[24-27]。然而，上述的方法都是針對靜態數據集。現實場景中數據是不斷動態增加的，相應地，一些基于動態數據信息的增量學習方法[28-32]被提出。然而，這些方法大多局限于平面分類中，分層分類中涉及的較少。Fan 等人[33]介紹了一種基于多核模糊粗糙集的增量層次分類方法，但它們更側重于目標概念的粗糙近似的更新，而不是特征選擇。Luo 等人[34]提出了一種迭代的增量粗糙集方法。而在分層分類下考慮使用包含策略的模糊粗糙集的增量研究也非常必要。

綜上，本文研究的動機如下：（1）在分層分類問題中，考慮模糊粗糙集的增量可以更好地模擬現實數據。（2）已有的研究大多針對的是數據標簽只分布在葉子節點，現實世界中標簽具有任意性，研究標簽分布在任意節點更具有現實意義。（3）包含策略能夠更好地學習標簽之間的層次信息，更適合應用標簽分布在任意節點的場景中。

因此，將針對標簽具有樹結構，且標簽分布在葉子節點和內部節點情形的動態數據集，將包含策略應用到模糊粗糙集模型中，基于此研究分層分類的增量特征選擇算法。基于文獻[23]提出一個基于包含策略的模糊粗糙集模型，設計一個非增量特征選擇算法，并引入增量機制，即當有新樣本加入時，研究下近似、正域和依賴度的增量更新策略。由此，本文設計一個增量特征選擇算法，并提出基于兩種不同策略的增量特征選擇框架。最后，通過數值實驗驗證所提算法是有效的。

本文主要貢獻如下：

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

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

（3）研究動態數據集，且標簽分布在內部節點和葉子節點，使得所提算法適用范圍更廣。

1 預備知識

本文所使用的符號含義如表1所示。

表1 符號描述Table 1 Symbol description

使用高斯函數[36]來計算模糊T-相似關系：

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

序對(Dtree,?)[23]用來描述決策類的層次結構，Dtree={d0,d1,…,dl}，其中d0為根節點，不是真實的類，l是類的個數。“?”代表“子類”關系且滿足以下條件：（1）反對稱性?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 是一個Dtree的示例，Dtree={d0,d1,…,d6}，其中d0是樹結構的根節點，不是真實的標簽，不參與求子孫節點和包含節點的運算。以d1為例，d1的子孫節點為des(d1)={d3,d4}，d1的包含節點inc(d1)={d1,d3,d4}，d1的包含負節點(d1)={d2,d5,d6}。

圖1 標簽的樹結構示例Fig.1 Example of tree structure for labels

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

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

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

在分層分類問題中，負樣本只是選取了U中除di其余樣本的一部分，因此當x?di時，不一定滿足為了下近似具有更好的性質，將文獻[23]中基于包含策略的下近似修正如下。

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

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

通過定義2可以得出以下結論。

由性質1 可知依賴度關于屬性集的變化是單調的，這是依賴度可以作為特征選擇的評價指標的依據。下面基于定義3 提出一個適用于分層分類的屬性約簡定義。

2.2 算法

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

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

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

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

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

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

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

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

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

本節首先研究當分層決策表加入一些新樣本時，下近似的增量更新方法，進而探究正域以及依賴度的更新方法。

3.1.1 下近似的增量更新

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

（1）情況1：x∈U。

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

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

ΔU是新加入的樣本，在原分層決策表中沒有計算過x在所屬類的下近似中的隸屬度，因此需要額外而下近似的變化只與y有關，只判斷加入樣本后每個節點的包含負節點是否有新加入樣本。

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

表3 添加樣本的示例數據Table 3 Example data of incoming samples

圖2 添加樣本時樹結構變化Fig.2 Change of tree structure while incoming samples

3.1.2 正域的增量更新

3.1.3 依賴度的增量更新

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

3.2 算法

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

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

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

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

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

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

接下來，基于兩種策略提出兩個增量特征選擇框架，用以解決批處理大規模數據集的分層分類問題。先將訓練集劃分為N份子數據集，當不同的子數據集加入當前數據集T時采用兩種不同的策略尋找屬性約簡。策略1（對應算法5）：在每次子數據集加入時只執行添加屬性策略，當第N個子數據集都完成上述策略后再執行刪除冗余屬性策略；策略2（對應算法6）：在每次子數據集加入時執行添加屬性策略和刪除冗余屬性策略。

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

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

由于策略1 只進行一次刪除冗余屬性策略，從理論上看，Inc-IFS-v1 的運行時間小于Inc-IFS-v2。

4 實驗分析

本章先從運行時間、所選擇特征個數、FH測度（基于F1的分層分類準確率度量）[37-38]和平均TIE 四個指標將FFS-HC[23]與本文所提的Inc-NIDC、Inc-IFSv1 和Inc-IFS-v2 進行對比。然后對Inc-IFS-v1 和Inc-IFS-v2 進行參數ε敏感度分析。最后通過實驗結果對所提的三個特征選擇算法進行評價。

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

4.1 實驗設計

實驗環境：Intel?CoreTMi5-7200U CPU@2.50 GHz 2.71 GHz 12.0 GB，MATLAB R2016a。

數據集：表4 是在分層分類問題中經常使用的數據集，這些數據集的真實標簽在葉子節點，由于樹結構中父子節點存在語義關系，子節點樣本隱含在父節點中，為了構造出本文所研究類型的數據集，把葉子節點中部分樣本的標簽提升為其祖先節點，并使每個節點中的樣本盡可能地均勻分布，此時標簽的個數記為d′，如表4 所示。

表4 數據集Table 4 Datasets

為了使上層節點具有子節點樣本盡可能多的信息，將每個葉子節點中樣本按一定比例隨機劃分份數為dlayer，向上層節點劃分。numsamples表示該節點中樣本個數，numnodes表示該節點的父節點的子節點個數，dlayer表示需向上泛化的層數。該比例大小也會隨著向上泛化的迭代過程而動態變化。這樣既使葉子節點均勻，又使上層節點的樣本分布均勻，且盡可能均勻地包含下層節點樣本，可以避免樣本分布的不平衡。

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

數據處理：（1）對數據集進行最大最小歸一化處的層數。該比例大小也會隨著向上泛化的迭代過程而動態變化。這樣既使葉子節點均勻，又使上層節點的樣本分布均勻，且盡可能均勻地包含下層節點樣本，可以避免樣本分布的不平衡。

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

4.2 四個算法對比

這部分，通過對比FFS-HC[23]、Inc-NIFS、Inc-IFSv1 和Inc-IFS-v2 算法的運行時間、所選特征個數、FH測度和平均TIE 來評價所提的三個算法，結果如表5和圖3、圖4所示。

圖3 4個算法所選特征個數對比Fig.3 Comparison of the number of selected features for 4 algorithms

圖4 4個算法的FH值對比Fig.4 Comparison of FH for 4 algorithms

表5 算法FFS-HC、Inc-NIFS、Inc-IFS-v1和Inc-IFS-v2的運行時間對比Table 5 Comparison of running time for FFS-HC,Inc-NIFS,Inc-IFS-v1 and Inc-IFS-v2 algorithms 單位：s

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

表5 是FFS-HC、Inc-NIFS、Inc-IFS-v1 和Inc-IFSv2的運行時間。加粗表示運行時間最短。在Bridges數據集上Inc-NIFS 的運行時間最短，這是因為這個數據集太小，而樣本又分多次到達，導致增量計算時間較長；而在其他大規模數據集上除了SAIAPR 外，Inc-IFS-v1 的運行時間最短，且與FFS-HC 和Inc-NIFS 的運行時間差距非常大。尤其在VOC 數據集上，FFS-HC 約是Inc-IFS-v1 的7.3 倍，Inc-NIFS 約是Inc-IFS-v1的68.5倍。在SAIAPR5000數據集上，Inc-NIFS 約是Inc-IFS-v1的311.8倍。從實驗中也可以看出在所有數據集上Inc-IFS-v1 比Inc-IFS-v2 的時間效率更高。

圖3 是FFS-HC、Inc-NIFS、Inc-IFS-v1 和Inc-IFSv2 的所選特征個數。在所有數據集上FFS-HC 所選特征個數小于其他3 個算法；Inc-NIFS、Inc-IFS-v1 和Inc-IFS-v2 所選特征個數基本上區別不大；FFS-HC在SAIAPR5000 數據集上所選特征個數遠遠小于其他3個算法。

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

表6 是FFS-HC、Inc-NIFS、Inc-IFS-v1 和Inc-IFSv2 的平均TIE 值對比。加粗表示在對應分類器下平均TIE 值最小。平均TIE 值越小，表示算法越好。從全部數據集上看，SAIAPR5000 數據集上的算法的平均TIE 值大于其他數據集，說明在SAIAPR5000 這個數據集上分類誤差都大于其他數據集；從算法角度看，在分類器SVM上Inc-NIFS更占優勢，但是這些算法差別不大，相差不超過0.3。整體來看，FFS-HC、Inc-NIFS、Inc-IFS-v1 和Inc-IFS-v2 的平均TIE 幾乎沒有差別。

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

4.3 Inc-IFS-v1 和Inc-IFS-v2 的參數敏感性分析

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

圖5 Inc-IFS-v1和Inc-IFS-v2的運行時間對比Fig.5 Comparison of running time for Inc-IFS-v1 and Inc-IFS-v2

圖5 是Inc-IFS-v1 和Inc-IFS-v2 隨著閾值ε 的減小運行時間的變化。閾值ε越小，而添加屬性的條件就越嚴格，對應的運行時間就越長。在VOC 數據集上，Inc-IFS-v2 的運行時間遠遠大于其他參數，可能因為在這個參數下每次到達子數據集都會進行添加屬性和刪除冗余屬性策略，而再次增加樣本后原屬性約簡總不滿足，需要再次添加屬性和刪除冗余屬性，VOC 有1 000 個屬性，會使運行時間差距更明顯。綜合來看，Inc-IFS-v1 和Inc-IFS-v2 的運行時間隨著閾值減小變長，并且Inc-IFS-v1的運行時間總小于Inc-IFS-v2。

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

圖7 為Inc-IFS-v1 和Inc-IFS-v2 的FH值。在DD數據集上，閾值ε<0.005 時，Inc-IFS-v1 和Inc-IFS-v2的FH值在分類器SVM 和KNN 上減小。可能是因為隨閾值ε減少，所選特征個數變多，多了一些干擾性特征，使得分類精度下降。整體上看，隨著閾值ε的減少，Inc-IFS-v1 和Inc-IFS-v2 的FH值呈不明顯的上升趨勢。綜上，Inc-IFS-v1 和Inc-IFS-v2 的分類精度隨著閾值ε的變化，敏感性較弱。

綜合圖5～圖7，從時間上看，隨著閾值ε變小，Inc-IFS-v1 和Inc-IFS-v2 的運行時間越長，即運行時間的敏感性較大；從所選特征個數和分類精度看，隨著閾值ε變小，在有些數據集上分類精度有上升趨勢，在有些數據集上沒有明顯變化。

5 總結與展望

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

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