結合分辨矩陣與蟻群優化算法改進的特征選擇方法

摘要：目前已有蟻群算法優化的特征選擇方法，大多采用的是以屬性依賴度和信息熵屬性重要度作為路徑上啟發搜索因子，但這類搜索方法在某些決策表中存在算法早熟或搜索到的特征子集包含了冗余特征，從而導致選擇精度顯著下降。針對此類問題，根據條件屬性在分辨矩陣中的占比提出了一種屬性重要度的度量方法，以分辨矩陣重要度作為路徑上啟發因子，設計了一種基于分辨矩陣與蟻群算法優化的特征子集搜索方法。該算法從特征核出發，蟻群依次選擇概率大的特征加入特征核集，直至找到最小特征子集算法終止。通過實例驗證和UCI數據集實驗結果表明，與基于屬性依賴度和信息熵屬性重要度的特征選擇方法相比，在通常情況下，該算法能較小代價找到最小特征子集，并且可以有效減少計算工作量。

關鍵詞：粗糙集； 蟻群算法； 特征選擇； 分辨矩陣； 特征子集

中圖分類號：TP18文獻標志碼：A

文章編號：1001-3695（2022）04-027-1118-06

doi：10.19734/j.issn.1001-3695.2021.08.0360

Improved feature selection method combining discernibility matrix and ant colony optimization algorithm

Yang Zhenyu1， Ye Jun1，2， Ji Yuxuan1， Ao Jiaxin1， Wang Lei1，2

（1.College of Information Engineering， Nanchang Institute of Technology， Nanchang 330000， China; 2.Jiangxi Province Key Laboratory of Water Information Cooperative Sensing amp; Intelligent Processing， Nanchang 330000， China）

Abstract：At present， the existing feature selection methods based on ant colony algorithm optimization mostly use attribute dependence and information entropy attribute importance as the heuristic search factor on the path. However， this kind of search method has premature convergence in some decision tables or the searched feature subset contains redundant features， which leads to a significant decrease in selection accuracy. Aiming at such problems， this paper proposed an attribute importance measurement method based on the proportion of conditional attributes in the discernibility matrix. Taking the importance of the discernibility matrix as the heuristic factor on the path， this article designed a feature subset search method based on the discernibility matrix and ant colony algorithm optimization. The algorithm started from the feature core， and the ant colony selected features with high probability in turn to add to the feature core set， until the ant found the smallest feature subset. Validation of examples and experimental results of UCI data set show that compared with the feature selection method based on attribute dependence and information entropy attribute importance， under normal circumstances， this algorithm can find the smallest feature subset at a lower cost.

Key words：rough set; ant colony optimization; feature selection; discernibility matrix; feature subset

0引言

特征選擇是知識發現和數據挖據領域的重要研究內容。粗糙集理論［1］是一種處理不精確、不確定性及大量數據的數學工具，它能有效地進行特征選擇［2～4］和數據降維。屬性重要度是粗糙集理論中一個重要的概念，以屬性重要度作為啟發性因子進行特征搜索是粗糙集理論中較為常用的特征選擇方法。為優化這些特征選擇方法的計算工作量，研究者將其與群智能算法［5～8］相結合，設計了大量基于粗糙集屬性重要度與群智能優化算法的特征選擇算法，如文獻［9］引入人工蜂群算法與Pawlak屬性重要度方法結合提出一種求解最小特征子集的蜂群算法；文獻［10，11］將二元螢火蟲算法與屬性的依賴度相融合求約簡；文獻［12］則把粗糙集與鯨魚優化算法相結合，目標函數中引用屬性依賴度，提出基于鯨魚優化與粗糙集的特征選擇算法；文獻［13］引入果蠅優化算法，通過構造基于粗糙集特征重要度適應評估函數，提出了一種果蠅優化的特征子集搜索算法。這些算法都在不同程度上提高了特征選擇的速度和精度。

蟻群優化（ant colony optimization，ACO）算法是群智能算法的一種，它在組合優化的問題上具有比較良好的全局尋優能力。將它與粗糙集進行結合，有眾多學者對其進行了研究，文獻［14］率先將蟻群優化算法引入粗糙集中，提出了基于蟻群優化算法的特征選擇方法，該方法從隨機特征開始搜索，搜索到最小子集終止。文獻［15］以Pawlak的屬性重要度作為路徑上的啟發因子，提出了一種蟻群優化的粗糙集屬性重要度特征選擇算法，該算法從空集出發通過啟發因子搜索子集; 文獻［16，17］同樣是以Pawlak的屬性重要度作為路徑上的啟發因子，提出了蟻群優化的特征子集搜索算法，該算法把文獻［15］中從空集出發，修改為從特征核集出發，減少了搜索時間，提高了效率。但這些優化算法存在一定的局限性。因為Pawlak重要度是從定性的角度考查確定域的變化情況，能改變確定域的只有特征核，其度量的是特征核的重要度，并沒有反映其他特征的重要度。所以，在以非特征核重要度作為路徑上的啟發信息時，會導致蟻群無法準確選擇下一特征而造成算法早熟。為此，文獻［18～20］以粗糙集信息論中的條件熵重要度屬性作為啟發因子，提出了一種基于條件熵重要度與蟻群優化的特征選擇算法。條件熵的屬性重要度是從定量的角度度量不確定域的變化情況，任何一個特征的變化都有可能引起不確定域改變。因此，信息熵方法改善了其他特征重要度都為零的情況。但是，信息熵方法在某些決策表中會存在著冗余特征重要度會大于特征核重要度的情況，螞蟻尋找到的特征子集可能會包含冗余特征［21，22］，從而導致選擇精度顯著下降。

為改進上述以Pawlak重要度和條件熵重要度作為蟻群在路徑上啟發搜索因子的特征選擇方法的不足，本文定義了一種基于分辨矩陣的屬性重要度。與原有屬性重要度定義不同的是，新的屬性重要度是以條件屬性在分辨矩陣中出現的次數和權重占比為依據來度量屬性的重要度，它既可以避免Pawlak屬性重要度定義中非核屬性重要度都為零的情況，又克服了條件熵重要度中冗余屬性比核屬性重要度還要高的現象。在此基礎上，提出了一種以分辨矩陣屬性重要度為蟻群搜索路徑上啟發因子的特征選擇算法。新算法借鑒了上述文獻中的問題建模、局部解構建及從特征核集出發求解最小特征子集等思路。

1相關知識

在粗糙集理論中，對于屬性重要度的度量主要有基于粗糙集代數觀的Pawlak度量方法和信息觀的度量方法兩種。研究者們以這兩種重要度度量方法為啟發信息設計了許多特征選擇算法，下面簡要介紹這兩種屬性重要度定義方法，更詳細的信息參考文獻［1］。

1.1Pawlak屬性重要度定義方法

定義1［1］設近似空間K=（U，S），其中U是論域，S是論域上等價的關系簇，XU與U上的一個等價關系R∈IND（K），則X關于R的上近似與下近似分別是

（X）={x|（x∈U）∧（［x］R∩X≠）}（1）

R（X）={x|（x∈U）∧（［x］RX）}（2）

X的R邊界域為bnR（X）=（X）－R（X），X的R正域為POSR（X）=R（X）。

定義2［1］決策信息系統 AC。條件屬性集C和決策屬性集D之間的依賴度r（C，D）=|POSC（D）|/|U|，從條件屬性集AC中刪除AC后，AC關于AC的重要度為

sig（c，A，D）=r（A，D）-r（A-{c}，D）（3）

從條件屬性集AC中添加a后， a關于D的重要度為

sig（c，A，D）=r（A∪{c}，D）－r（A，D）（4）

Pawlak屬性重要度定義是以依賴度變化為基礎，通過添加或刪除某個屬性計算確定域的變化情況，而能引起確定域變化的只有核屬性。因此，它度量的是核屬性的重要度，無法度量其他屬性的重要度。

1.2條件熵屬性重要度定義方法

研究者將信息論引入粗糙集，提出了基于信息論粗糙集理論觀點［1］。其中，信息熵、條件熵和互信息等是粗糙集理論的信息論觀點中的重要概念［23，24］。下面簡要介紹條件熵重要度度量定義方法。

定義3［1］設C和D在U上導出的劃分分別為X，Y（X={X1，X2，…，Xn}，Y={Y1，Y2，…，Ym}），則C，D在U的子集組成的e代數上的概率分布為

［X：p］=X1X2…Xnp（X1）p（X2）…p（Xn）（5）

［Y：p］=Y1Y2…Ymp（Y1）p（Y2）…p（Ym）（6）

其中：p（Xi）=|Xi|/|U|，i=1，2，…，n；p（Yj）=|Yj|/|U|，j=1，2，…，m。

定義4［1］決策信息系統T=（U，C∪D，V，f），條件屬性集C關于決策屬性集D的條件熵為

I（D|C）=－∑ni=1p（Xi）∑mj=1p（Yj|Xi）log2p（Yj|Xi）（7）

從條件屬性集C中刪除c后，c關于D的重要度為

sig（c，C，D）=I（D|C－{c}）－I（D|C）（8）

從條件屬性集AC中添加a后， a關于D的重要度為

sig（a，A，D）=I（D|A）－I（D|A∪{a}）（9）

條件熵屬性重要度是以屬性對論域中不確定分類子集的影響為依據［24］，通過添加或刪除某個屬性后統計不確定域的變化情況，而任何一個屬性的變化都有可能改變不確定域。因此，在粗糙集代數觀下屬性重要度為零，信息觀下屬性重要度不一定為零［20］。顯然，相比代數方法，條件熵方法度量的重要度更為合理。但是，在某些不相容決策表中會得到冗余屬性重要度大于核屬性重要度的情況［21，22］。

1.3蟻群算法及其優化的特征選擇方法

Dorigo［25］以自然界中真實螞蟻的覓食為研究對象，在模擬蟻群如何尋找到最短路徑的基礎上提出了蟻群算法。其最主要特點是通過正反饋、分布式協作來尋找最優路徑組合優化問題［26］。它在解決一些NP問題上取得了很好的效果，廣泛應用于TSP［27，28］、作業調度［29，30］等問題。針對以粗糙集代數觀和信息觀重要度為啟發因子的特征選擇算法計算工作量大，特別是隨著維數的增多，時間復雜度幾何級增長等問題。研究者引入蟻群算法進行優化以降低時間復雜度。文獻［14］首先將蟻群算法引入到粗糙集，將求解最小特征子集轉換為最優路徑組合優化問題，提出了基于蟻群優化算法的特征選擇方法。隨后，文獻［15～20］從不同角度對Jensen方法進行了改進，這些求解方法大致分為問題表示、信息素更新、概率選擇和構建解決方案四部分。下面簡要介紹蟻群算法優化的粗糙集特征選擇方法，更詳細內容參考文獻［14］。

1.3.1問題表示

文獻［14］模擬螞蟻的覓食行為，將特征選擇行為轉換為如圖1所示的完全圖形式，設決策信息系統T=（U，C∪D，V，f），C表示條件屬性集合，D為決策屬性集合，圖中每個節點表示特征，節點與節點之間的邊表示螞蟻選擇下一個特征的路經，路經上蘊涵著啟發信息，螞蟻以路徑上的啟發信息遍歷全圖，搜索到最優特征組合的標志是節點最少路徑最短。

1.3.2信息素更新

螞蟻經過一條路徑之后，需要更新該路徑的信息素。信息素更新規則一般是選擇k只螞蟻更新其選擇路徑上的信息素。當所有螞蟻都搜索到一個特征后，就完成了一次迭代。然后，采用式（10）更新信息素。

τij（t+1）=ρτij（t）+Δτij（t）（10）

其中：t表示蟻群的第t次迭代;τij（t）表示特征i到j路徑上的信息素濃度;ρ是信息素的揮發程度;Δτij（t）是經過的路徑上的全部信息素的和，公式為

Δτij（t）=∑q|R（t）|螞蟻經過路徑（i，j）

0others（11）

其中：|R（t）|表示t次迭代時最小特征子集的特征個數;q是設置的一個常數。

1.3.3概率轉換規則

概率轉換規則是確定螞蟻從一個特征遍歷到下一個特征的依據。一只螞蟻從選擇的特征出發，根據概率公式來選擇下一個特征，定義為

Pkij（t）=ταij（t）ηβij（t）∑l∈allowedkταil（t）ηβil（t）j∈allowedk（12）

其中：α、β分別表示信息素濃度與啟發信息的重要程度，其取值為0～1； allowedk表示第k只螞蟻還未選擇的特征屬性；k表示第k只螞蟻;τij（t）、ηij（t）分別表示特征i到j路徑上的信息素濃度和啟發信息，啟發信息ηij（t）表示特征屬性j的重要度，定義為

ηij（t）=sig（j，C，D）（13）

其中：sig（j，C，D）為1.1節中定義2和4的屬性重要度。例如，文獻［15～17］采用的是定義2，即Pawlak屬性重要度作為路徑上的信息素濃度和啟發信息。由于Pawlak重要度度量的是特征核的重要度，無法度量其他特征的重要度，所以，在以非特征核重要度作為路徑上的啟發信息時，蟻群無法準確選擇下一特征從而導致算法早熟。文獻［18～20］采用的是定義4即條件熵特征重要度作為路徑上的啟發信息，而信息熵方法在某些決策表中存在冗余特征大于特征核重要度的情況［21，22］，使得蟻群尋找到的特征子集可能會包含冗余特征，從而導致選擇精度顯著下降。

1.3.4局部解的構建

在求全局最優解之前， 首先求每只螞蟻在搜索結束后得出的一個局部解，局部解的構建是一個尋找特征子集的過程。以特征核為起點，當一只螞蟻隨機完成某個特征的選擇后，則繼續按照概率式（12）選擇下一個特征ck，Rk←Rk∪ck，Rk是第k只螞蟻搜索到的特征子集，表示完成了一次迭代。當滿足如下兩個條件時，則停止搜索，該只螞蟻消亡。

a）γRk（D）=γC（D），Rk的依賴度跟特征集合C的依賴度相等時，第k只螞蟻構建了一個局部解（Rk是第k只螞蟻所搜索到的特征子集）。

b）如果當前最小特征子集的基數小于第k只螞蟻搜索到集合的基數，則該螞蟻消亡。

在條件a）中，當第k只螞蟻所搜索到的特征子集R的特征依賴度與所有特征集合C的依賴度相等時，即兩者的分類能力相同，表示第k只螞蟻獲得了一個局部解R，若滿足|R|lt;|Rmin|，即局部解的基數比此時的最優解的基數更小，則局部解R成為全局最優解。顯然，R中的特征數越少，得到的解越優。對于條件b），表示第k只螞蟻搜索到的特征集合基數比全局最優解的特征子集基數大，說明無法獲得更好的解集，則第k只螞蟻沒有必要再繼續構建下去，則這只螞蟻消亡。

2分辨矩陣與蟻群優化的特征選擇方法

2.1基于分辨矩陣的屬性重要度定義方法

針對基于Pawlak重要度和條件熵重要度在蟻群優化的特征選擇方法中的缺陷，本文結合Skowron［25］提出的分辨矩陣的概念，給出一種基于分辨矩陣中的屬性重要度定義方法。下面首先介紹文獻[25]定義的分辨矩陣，其定義如下：

定義5［1］設有決策系統T=（U，C∪D，V，f），其中U為對象集，C為條件屬性集，D為決策屬性集，論域是對象的一個非空有限集合U={x1，x2，x3，…，xn}，|U|=n，則決策表的分辨矩陣為

Mn×n=（Cij）=c11c12…c1nc21c22…c2n

cn1cn2…cnn（14）

其中：i，j=1，2，…，n。

cij={a|（a∈C∧（f（xi）≠f（xj））fD（xi）≠fD（xj）

fD（xi）=fD（xj）（15）

由式（14）有cij=cji，（i，j=1，2，3，…，n）即M是上三角或下三角矩陣。文獻［1］給出了分辨矩陣中求特征核的方法，該方法簡單高效。

定理1［1］決策表T=（U，C∪D，V，f），其中C為條件屬性集，D是決策屬性集，在分辨矩陣中，所有單個屬性元素組成的集合就是C相對D的核屬性集，即

COREC={a|（a∈C）∧（cij，（（cij∈M）∧（cij={a}）））}

通過對式（15）分析可知，對象集U中的對象屬于同一個等價類時，這些對象不可分辨，即決策屬性值相等，則有cij=。對象集U中的對象處于不同的等價類，即決策屬性值不相等，這些對象能夠分辨，則cij是由條件屬性集C中能夠分辨這些對象的屬性組成，其成員可能包含了核屬性，也可能包含普通或冗余屬性。cij中的所有屬性在分辨不同等價類中的對象xi和xj 時都起了作用，只是作用不一樣，核屬性的作用應該最大，其他屬性貢獻要小。為能夠準確度量各條件屬性在分辨不同對象所起的作用，本文以這些條件屬性在cij中出現的頻次及在每次所占比例來度量其重要度，定義如下：

定義6設決策表T=（U，C∪D，V，f），其中C是條件屬性集，D是決策屬性集，cij是分辨矩陣M中的不為空元素， W是分辨矩陣M中所有非空cij總的個數，對c∈C屬性c對于D的重要度為

Nsig（c）=∑i，j=1，2，…，nrc∩cijW|cij|gt;1

1cij|=1（16）

rc∩cij=1|cij|c∩cij≠，i，j=1，2，…，n

0c∩cij=，i，j=1，2，…，n（17）

其中：|cij|表示cij集合中的屬性個數。

從式（16）可以看出，當|cij|=1既是單個屬性時，其重要度為1，表示單個屬性分辨不同等價類的對象貢獻度最大，這與定理1中單個屬性是核屬性相吻合。|cij|gt;1時，即cij集合中有多個屬性，表示分辨不同等價類的對象是由多個屬性共同作用完成的，這些可能是核屬性，也可能是普通屬性，每個屬性作用為1/cij。顯然，核屬性的重要度是由其作為單個屬性重要度1和作為多個屬性重要度兩部分之和，即

1+∑i，j=1，2，…，nrc∩cijW（18）

式（18）反映了核屬性區分鄰域對象的能力最強。

從式（16）中可以得到兩個結論。

結論1對分辨矩陣M中的非空元素集合cij， 若c∈C且c∈cij，則Nsig（c）gt;0。

證明c∈cij，若cij為單個屬性時，根據式（16）可知Nsig（c）=1gt;0。

c∈cij，若cij為多個屬性組成的集合時，即|cij|gt;1，根據式（17）則有c∩cij=1/|cij|gt;0，因此有（∑i，j=1，2，…，nrc∩cij）/Wgt;0。

從結論1可以看出，出現在集合cij中的屬性在分辨不同等價類的對象時都起了作用，其屬性的重要度都大于零，避免了Pawlak屬性重要度定義方法中非核屬性重要度都為零的情況。

結論2對分辨矩陣M中的非空元素集合cij，a，b∈cij， 若a∈CORE（C），b∈N，則有Nsig（a）gt;Nsig（b）gt;0。其中，CORE（C）表示分辨矩陣中核屬性元素集，N表示非核屬性元素集。

證明若a∈CORE（C）且a∈N，則有：

Nsig（a）=1+∑i，j=1，2，…，nra∩cijWgt;1

若b∈N且bCORE（C），根據定理1可知，集合元素cij中的特征屬性個數至少為一個以上，即|cij|gt;1，有b∩cij=1/|cij|lt;1。可知∑i，j=1，2，…，nrb∩cijlt;W，因此有

Nsig（b）=∑i，j=1，2，…，nrb∩cijWlt;WW=1

綜上所述可得 Nsig（a）gt;Nsig（b）gt;0。由結論2知道，核屬性的重要度比非核屬性重要度大，這就克服了信息熵重要度中冗余屬性比核屬性重要度還要高的現象。

2.2算法步驟描述

以上述定義的分辨矩陣屬性重要度替代Pawlak重要度和條件熵重要度，作為蟻群搜索路徑上啟發搜索因子，提出一種基于分辨矩陣屬性重要度與蟻群優化算法改進的特征選擇算法，算法分為兩部分：a）算法1是求解分辨矩陣屬性重要度及特征核；b）算法2是以分辨矩陣屬性重要度為啟發搜索因子的蟻群優化的特征選擇算法。具體描述如下：

算法1分辨矩陣特征重要度和特征核

輸入：分辨矩陣M。

輸出：屬性重要度Nsig（ct）;特征核CORE（D）。

1 Nsig（ct）=0；a=0；W=0；CORE（D）=；

2 for set in M： //遍歷分辨矩陣

3if |set|==1： // |set|表示set中的元素個數

4a←a+1;

5CORE（D）←CORE（D）∪set

6if |set|！=：

7b←b+1/|set|; W←W+1;

8 if a！=0：

9Nsig（ct）←1+b/|set|;

10 else：

11 Nsig（ct）←b/W;

算法2DMACO （分辨矩陣屬性重要度的特征選擇算法）

輸入：決策表T=（U，C∪D，V，f）;參數maxcycle；k。

輸出：最優約簡Rmin和其基數Lmin。

1 Rmin←C；Lmin←|C|；Rk←；t=0；

2 compute γC（D）；

3 compute M； //由式（15）得到分辨矩陣M

4 compute CORE（D） and Nsig（ct）；

/*根據算法1得出分辨矩陣特征核CORE（D）和特征重要度Nsig（ct）*/

5 while t lt;Rk←Rk∪ck do：

6Rk←Rk∪ck；t←t+1；

//按概率式（12）每只螞蟻都分別選擇下一個特征屬性ck

7 if γRk（D）==γC（D） or γRk（D）=γC（D）：

8 K=K-1；

9if γRk（D）==γC（D） and |Rk|lt;Lmin：

10 Rmin←Rk， Lmin←|Rmin|；

11τij（t+1）←ρτij（t）+Δτij（t）；//根據式（10）更新信息素

12if K==0：

13break；//K=0，全部螞蟻消亡，退出循環

2.3算法時間復雜度分析

本文算法的時間復雜度主要取決于螞蟻的個數K，迭代的次數t，屬性的個數n，以及重要度的計算時間。本文算法中計算分辨矩陣的時間復雜度為O（n|U|2），用分辨矩陣計算重要度的時間復雜度為O（W|U|），其中W為分辨矩陣中不為空的元素個數，算法總的時間復雜度為O（n|U|2+W|U|+tnK），而傳統的重要度用正域計算的算法求基本集的時間復雜度為O（n|U|2），用基本集求各個屬性重要度的時間復雜度為O（n|U|2），總的時間復雜度為O（2n|U|2+tnK），由此可見，本文算法時間復雜度較優。

3實驗數據分析

為了驗證本文基于分辨矩陣與蟻群優化的特征選擇算法的有效性和實用性，從決策表實例驗證和UCI數據集實驗兩個方面對實驗結果進行分析對比。

3.1實例分析

例1已知DT=（U，C∪D，V，f），其中C={c1，c2，c3，c4，c5}是條件屬性集，D是決策屬性集，論域為U={x1，x2，x3，x4，x5，x6，x7，x8，x9，x10}是一個非空有限集合，|U|=10，特征核集為{c5}，最小特征子集為{c1c3c5}，如表1所示。

對表1進行計算：

U/D={{x1，x4，x5，x9，x10}，{x2，x3，x6，x7，x8}}

U/{c5}={{x2，x4，x6}，{x1，x3，x5，x7，x8，x9，x10}}

U/{c1，c5}={{x1，x5，x7，x10}，{x2，x4}，{x3，x8，x9}，{x6}}

U/{c2，c5}={{x1，x5}，{x3，x7，x8，x9，x10}，{x2，x4，x6}}

U/{c3，c5}={{x1，x3，x5，x9}，{x7，x8，x10}，{x2，x4}，{x6}}

U/{c4，c5}={{x1，x5，x8}，{x3，x7，x9，x10}，{x2，x4，x6}}

計算重要度：

1）文獻［17］方法

sig（c5，C，D）=|POSC（D）－POSC－{c5}||U|=0.1

同理可得：sig（c1，C，D）=0， sig（c2，C，D）=0，sig（c3，C，D）=0，sig（c4，C，D）=0。

從上述計算結果可知，特征核為c5，其重要度為0.1，其他非核特征重要度都為0。由于非核特征ηij（t）=sig（j，C，D）=0，使得蟻群無法按照式（12）概率公式準確選擇下一個特征加入到解的集合中，從而導致算法過早收斂無法找到最小特征子集。

2）文獻［20］方法

由于sig（c5，C，D）=I（D|C－{c5}）－I（D|C）=0.0755，可知c5為特征核。相對于特征核其他特征的重要度為

sig（c2，{c5}，D）=I（D|{c5}）－I（D|{c2，c5}）=

［510（25log225+35log235）+310（13log213+23log223）］－

［310（13log213+23log223）+710（37log237+47log247）］=0.2042

同理可得：

sig（c1，{c5}，D）=0.1706

sig（c3，{c5}，D）=0.1706，sig（c4，{c5}，D）=0.0142

由計算結果可知sig（c2）gt;sig（c1）=sig（c3）gt;sig（c4），從特征核出發，按照概率選擇規則，螞蟻優先選擇重要度大的特征c2，螞蟻搜索到的最小特征子集為{c5，c2，c1，c3}，其中包含了冗余特征。而正確的最小特征子集為{c1c3c5}。

3）本文方法

按照定義5可得表1的分辨矩陣如下：

從分辨矩陣中可以得到非空元素個數W=22，單個屬性c5為特征核。下面計算非核特征的重要度。以c1為例，c1出現次數為14，例如{c1c2c4c5}、{c1c2c4}等，rc1∩cij分別為1/|{c1c2c4c5}|、1/|{c1c2c4}|等。根據式（16）有：

Nsig（c1）=13+14+13+13+13+14+12+12+13+15+12+13+12+1222=0.2364

同理可得

Nsig（c2）=0.1364，Nsig（c3）=0.2197，Nsig（c4）=0.1667

根據計算結果，從特征核出發，按照概率選擇規則，螞蟻優先選擇重要度最大的c1加入到核集，然后選擇c3，最終螞蟻搜索到的最小特征子集為{c1c3c5}，與正確結果一致。上述計算結果顯示，每個特征的重要度都大于0，這與本文得到的結論1相吻合。根據式（18）可計算特征核c5的重要度：

Nsig（c5）=1+14+14+…+1322=1.1061

有Nsig（c5）gt;Nsig（c1）gt;Nsig（c3）gt;Nsig（c4）gt;Nsig（c2），這個結果與本文得到的結論2相一致。綜上所述，以分辨矩陣重要度作為啟發信息，蟻群準確地找到了最優特征子集{c5c1c3}，這與用粗糙約簡理論得到結果一致，說明了本文算法的有效性。

3.2UCI數據集實驗分析

3.2.1相關對比算法及實驗參數設置說明

為了進一步驗證本文算法的有效性及可靠性，本文選用文獻［15］的ACORS、文獻［17］的ACOAR、文獻［18］的RACO、文獻［20］的IEACO和本文的DMACO五種算法進行比較實驗。其中，ACORS算法以Pawlak的屬性重要度作為路徑上的啟發因子，該算法從空集出發，把搜索到的特征逐個添加至空集中，直到搜索到最小特征子集。ACOAR算法同樣采用了粗糙集中的Pawlak重要度作為啟發信息，但該算法從特征核集出發，把搜索到的特征依次放入核集，直至獲得最小特征子集。RACO和IEACO算法是以條件熵屬性重要度作為路徑上的啟發因子，都是從特征核集出發，直到獲得最小特征子集。這兩種算法區別在于采用了不同的求特征核方法和信息素更新規則。為使實驗具有可比性，五種算法實驗時都設置相同的初始參數：α=0.9，β=0.1，初始信息素濃度為1，螞蟻數量滿足n=1.5k，其中，n為數據的特征個數，k為螞蟻數；最大迭代次數maxcycle=100，適應度函數中的λ取0.4。

3.2.2對比實驗

本文選取UCI機器學習庫中如表2所示的六個數據集進行實驗。從特征選擇效果、運行時間和適應度值三個方面進行對比。實驗環境如下：處理器IntelCoreTMi5-8265U @1.60 GHz @1.80 GHz，內存8 GB，采用Windows 10下的PyCharm64作為實驗平臺，編程語言Python。

每個算法分別運行20次，取平均值作為結果。特征選擇效果用得到的特征子集中的特征個數和特征約簡率兩個核心指標來進行衡量。五種算法在六個數據集上得到的特征子集中的特征個數如表3所示。

五種算法在六個數據集上得到的特征約簡率如圖2所示。其中，約簡率比較采用式（19）。

rate=|C|－|R||C|×100%（19）

其中：|C|表示全部的特征數;|R|是約簡后的特征數。

從表3和圖2可以看出，本文方法的降維效果要好于ACOAR和IEACO，約簡率明顯更高。

五種算法在數據集上的運行時間如表4所示。

由表4可知，本文算法運行時間比其他四種算法短，表明了本文算法時間復雜度更優。在六個數據集上適應度值隨迭代次數的變化曲線分別如圖3～8所示。其中，適應度函數為

fitness=λ×|POSRt（D）||U|+（1－λ）||C|－|R||C||（20）

其中：|C|表示全部的特征數；|R|是此時解的特征數；Rt是第t次迭代中搜索到的最優特征集。

從圖3～8可以看出，ACORS和ACOAR算法迭代次數多，其收斂速度更慢且它的適應度函數曲線基本是位于其他算法的曲線下方，說明以Pawlak特征重要度作為啟發信息的算法性能較低。相比于前兩個算法，IEACO和RACO算法收斂速度和函數適應度值要好，說明以條件熵屬性重要度作為啟發因子的方法比前者更優。本文DMACO算法的適應度曲線僅迭代初期與其他算法的曲線相近，隨著迭代次數的增加，其適應度比起其他四個算法都要大，且曲線比其他算法曲線更早趨于穩定，說明本文以分辨矩陣屬性重要度為啟發因子的方法，具有更快的收斂速度和更優的函數適應度值，進一步說明了本文算法的有效性和可應用性。

4結束語

本文給出的分辨矩陣屬性重要度的定義方法，改善了非核屬性重要度為零及冗余屬性重要度大于核屬性重要度的情況，合理地度量了各屬性在分辨不同對象所起的作用。并在此基礎上設計了基于分辨矩陣與蟻群優化的特征選擇算法。實例和UCI數據集實驗表明，新算法改進了基于Pawlak重要度和條件熵重要度的方法在蟻群優化中特征選擇方法的不足，可以有效搜索到最小特征子集，并且收斂速度快，為特征選擇方法提供了新思路。但本文提出的分辨矩陣屬性重要方法也存在局限性，在少數決策表中，并不是所有屬性都會出現在分辨矩陣中，沒有出現在分辨矩陣中的屬性其重要度也可能是零。 對這類決策表的特征選擇方法還需要進一步研究。

參考文獻：

[1]苗奪謙，李道國.粗糙集理論、算法與應用［M］.北京：清華大學出版，2008：163-190.（Miao Duoqian， Li Daoguo. Rough sets theory algorithms and applications［M］.Beijing：Tsinghua University Press，2008：163-190.）

［2]李郅琴，杜建強，聶斌，等.特征選擇方法綜述［J］.計算機工程與應用，2019，55（24）：10-19.（Li Zhiqin， Du Jianqiang， Nie Bin， et al. Summary of feature selection methods［J］.Computer Enginee-ring and Applications，2019，55（24）：10-19.）

［3]Elhasnony I M， Barakat S I， Elhoseny M， et al. Improved feature selection model for big data analytics［J］.IEEE Access，2020，8：66989-67004.

［4]Zebari R， Abdulazeez A， Zeebaree D， et al. A comprehensive review of dimensionality reduction techniques for feature selection and feature extraction［J］.Journal of Applied Science and Technology Trends，2020，1（2）：56-70.

［5]Qu Boyang， Li Chao， Liang Jing， et al. A self-organized speciation based multi-objective particle swarm optimizer for multimodal multi-objective problems［J］.Applied Soft Computing，2020，86：105886.

［6]Cui Zhihua， Chang Yu， Zhang Jiangjiang， et al. Improved NSGA-III with selection-and-elimination operator［J］.Swarm and Evolutio-nary Computation，2019，49：23-33.

［7]Wang Hui， Wang Weijun， Xiao Songyi， et al. Improving artificial bee colony algorithm using a new neighborhood selection mechanism［J］.Information Sciences，2020，527：227-240.

［8]Pan Linqiang， He Cheng， Tian Ye， et al. A classification-based surrogate-assisted evolutionary algorithm for expensive many-objective optimization［J］.IEEE Trans on Evolutionary Computation，2018，23（1）：74-88.

［9]葉東毅，陳昭炯.最小屬性約簡問題的一個有效的組合人工蜂群算法［J］.電子學報，2015，43（5）：1014-1020.（Ye Dongyi， Chen Zhaojiong. An efficient combinatorial artificial bee colony algorithm for solving minimum attribute reduction problem［J］.Acta Electronica Sinica，2015，43（5）：1014-1020.）

［10]程美英，倪志偉，朱旭輝.融合粗糙集和擴散二元螢火蟲算法的屬性約簡方法［J］.系統工程與電子技術，2016，38（10）：2449-2456.（Chen Meiying， Ni Zhiwei， Zhu Xuhui. Attribute reduction method combined with spread binary glowworm swarm optimization and rough set［J］.Systems Engineering and Electronics， 2016，38（10）：2449-2456.）

［11]程美英，倪志偉，朱旭輝.融合粗糙集和二元螢火蟲算法的霧霾關鍵影響因素預測方法［J］.系統工程理論與實踐，2017，37（1）：241-252.（Chen Meiying， Ni Zhiwei， Zhu Xuhui. Rough set combine with binary glowworm swarm optimization for key haze influence factors［J］.Systems Engineering-Theory and Practice，2017，37（1）：241-252.）

［12]王生武，陳紅梅.基于粗糙集和改進鯨魚優化算法的特征選擇方法［J］.計算機科學，2020，47（2）：44-50.（Wang Shengwu， Chen Hongmei.Feature selection method based on rough sets and improved white optimization algorithm[J].Computer Science，2020，47（2）：44-50.）

［13]方波，陳紅梅，王生武.基于粗糙集和果蠅優化算法的特征選擇方法［J］.計算機科學，2019，46（7）：157-164.（Fang Bo， Chen Hongmei， Wang Shengwu. Feature selection algorithm based on rough set and fruit fly optimization［J］.Computer Science，2019，46（7）：157-164.）

［14]Jensen R， Shen Qiang. Finding rough set reducts with ant colony optimization［C］//Proc of UK Workshop on Computational Intelligence.2003：15-22.

［15]王璐，邱桃榮，何妞，等.基于粗糙集和蟻群優化算法的特征選擇方法［J］.南京大學學報：自然科學版，2010，46（5）：487-493.（Wang Lu， Qiu Taorong， He Niu， et al. A method for feature selection based on rough sets and ant colony optimization algorithm［J］.Journal of Nanjing University： Natural Sciences，2010，46（5）：487-493.）

［16]吳克壽，陳玉明，謝榮生，等.基于粗糙集與蟻群優化算法的特征選擇方法研究［J］.計算機應用研究，2011，28（7）：2436-2438.（Wu Keshou， Chen Yuming， Xie Rongsheng， et al. Rough sets and ant colony optimization based feature selection［J］.Application Research of Computers，2011，28（7）：2436-2438.）

［17]吳尚智，張文超，佘志用，等.利用蟻群優化算法的粗糙集屬性約簡方法［J］.計算機工程與科學，2019，41（3）：538-544.（Wu Shangzhi， Zhang Wenchao， She Zhiyong， et al. A rough set attribute reduction method using ant colony optimization algorithm［J］.Computer Engineering and Science，2019，41（3）：538-544.）

［18]任志剛，馮祖仁，柯良軍.蟻群優化屬性約簡算法［J］.西安交通大學學報，2008，42（4）：440-444.（Ren Zhigang， Feng Zuren， Ke Liangjun. Ant colony optimization approach to attribute reduction problem［J］.Xi’an Jiaotong University Xuebao，2008，42（4）：440-444.）

［19]Chen Yuming， Miao Duoqian， Wang Ruizhi. A rough set approach to feature selection based on ant colony optimization［J］.Pattern Re-cognition Letters，2010，31（3）：226-233.

［20]陳穎悅，陳玉明.基于信息熵與蟻群優化的屬性約簡算法［J］.小型微型計算機系統，2015，36（3）：586-590.（Chen Yingyue， Chen Yuming. Attribute reduction algorithm based on information entropy and ant colony optimization［J］.Journal of Chinese Computer Systems，2015，36（3）：586-590.）

［21]劉啟和，李凡，閔帆，等.一種基于新的條件信息熵的高效知識約簡算法［J］.控制與決策，2005，20（8）：878-882.（Liu Qihe， Li Fan， Min Fan， et al. An efficient knowledge reduction algorithm based on new conditional information entropy［J］.Control and Decision，2005，20（8）：878-882.）

［22]葉軍，王磊.一種基于區分矩陣的屬性組合權重構造方法［J］.計算機科學，2014，41（11）：273-277.（Ye Jun， Wang Lei. Approach of ascertaining combinatorial attribute weight based on discernibility matrix［J］.Computer Science，2014，41（11）：273-277.）

［23]高文華，梁吉業，王寶麗，等.非完備決策信息系統中的不確定性度量［J］.智能系統學報， 2019，14（6）：1100-1110.（Gao Wenhua， Liang Jiye， Wang Baoli， et al. Uncertainty measure in incomplete decision information system［J］.CAAI Trans on Intelligent Systems，2019，14（6）：1100-1110.）

［24]周濤，陸惠玲，任海玲，等.基于粗糙集的屬性約簡算法綜述［J］.電子學報，2021，49（7）：1439-1449.（Zhou Tao， Lu Huiling， Ren Hailing， et al. Survey on attribute reduction algorithm of rough set［J］.Acta Electronica Sinica，2021，49（7）：1439-1449.）

［25]Dorigo M， Maniezzo V， Colorni A. Ant system： optimization by a colony of cooperating agents［J］.IEEE Trans on Systems Man and Cybernetics，1996，26（1）：29-41.

［26]覃遠年，梁仲華.蟻群算法研究與應用的新進展［J］.計算機工程與科學，2019，41（1）：173-184.（Qin Yuannian， Liang Zhonghua. New progress of the and colony algorithm in research and applications［J］.Computer Engineering and Science，2019，41（1）：173-184.）

［27]李二超，齊款款.改進雙向蟻群算法的移動機器人路徑規劃［J］.計算機工程與應用，2021，57（18）：281-288.（Li Erchao， Qi Kuankuan. Improved bidirectional ant colony algorithm mobile robot path planning［J］.Computer Engineering and Applications，2021，57（18）：281-288.）

［28]Song Qi， Zhao Qinglei， Wang Shuxin， et al. Dynamic path planning for unmanned vehicles based on fuzzy logic and improved ant colony optimization［J］.IEEE Access，2020，8：62107-62115.

［29]Deepalakshmi P， Shankar K. Role and impacts of ant colony optimization in job shop scheduling problems： a detailed analysis［J］.Evolutionary Computation in Scheduling，2020：11-35.

［30]劉博省，毛范海，錢峰.蟻群禁忌搜索融合算法求解調度問題［J］.機械設計與制造，2021（9）：228-230，235.（Liu Boxing， Mao Fanhai， Qian Feng. Ant colony and tabu search fusion algorithm to solve scheduling problem［J］.Machinery Design and Manufacture，2021（9）：228-230，235.）

收稿日期：2021-08-23；

修回日期：2021-10-27

基金項目：江西省教育廳科技項目（GJJ211920，GJJ170995）；國家自然科學基金資助項目（61562061）

作者簡介：楊震宇（1996-），男，湖南桃江人，碩士研究生，主要研究方向為粗糙集、機器學習；葉軍（1968-），男（通信作者），江西萬安人，教授，碩導，碩士，主要研究方向為粗糙集、數據挖掘等（1208561815@qq.com）；季雨瑄（1998-），女，江蘇南京人，碩士研究生，主要研究方向為粗糙集、機器學習；敖家欣（1997-），男，江西新余人，碩士研究生，主要研究方向為粗糙集、機器學習；王磊（1967-），男，湖北鄂州人，教授，碩導，博士，主要研究方向為粗糙集、數據挖掘等.