一種基于信息熵加權的屬性約簡算法

摘 要：針對現有鄰域粗糙集模型中存在屬性權重都相同，無法保證關鍵屬性在屬性約簡時能夠被保留的問題，提出了一種基于信息熵加權的屬性約簡算法。首先，采用了類間熵、類內熵策略，以最大化類間熵最小化類內熵為原則給屬性賦予權重；其次，構造了基于加權鄰域關系的加權鄰域粗糙集模型；最后，基于依賴關系評估屬性子集的重要性，從而實現屬性約簡。在基于UCI數據集上與其他三種屬性約簡算法進行對比實驗，結果表明，該算法能夠有效去除冗余，提高分類精度。

關鍵詞：屬性約簡； 鄰域粗糙集； 屬性加權； 信息熵

中圖分類號：TP18文獻標志碼： A文章編號：1001－3695（2024）04－013－1047－05

doi：10.19734/j.issn.1001－3695.2023.07.0366

Novel method to attribute reduction based on information entropy weighting

Luo Fan， Jiang Yu

Abstract：Aiming at the problem that attributes in the existing neighborhood rough set model all have the same weight， which cannot ensure that the key attributes can be retained in attribute approximation，this paper proposed an attribute approximation algorithm based on information entropy weighting. Firstly，itadopted interclass entropy and intraclass entropy strategies to assign weights to attributes based on the principle of maximising interclass entropy and minimising intraclass entropy. Secondly， it constructed a weighted neighborhood rough set model based on weighted neighborhood relationships. Finally， it assessed the importance of attribute subsets based on dependency relationships to achieve attribute simplification. Comparison experiments with other three attribute approximation algorithms on UCI－based dataset show that the proposed algorithm can effectively remove redundancy and improve classification accuracy.

Key words：attribute reduction; neighborhood rough set; attribute weighting; information entropy

1982年Pawlak［1］提出的粗糙集理論是機器學習、模式識別、數據挖掘等領域強有力的數學分析工具。經典的Pawlak粗糙集理論需要嚴格的等價關系，因此它只適用于處理離散型數據。為了將粗糙集理論引入至對連續型數據的處理中，一些研究者提出了鄰域粗糙集［2］、模糊粗糙集［3］、基于優勢的粗糙集等模型［4］。這些廣義的粗糙集模型廣泛地應用于屬性約簡［5］、規則提取［6］、決策理論［7］、增量學習［8］等領域。

鄰域關系可以很好地描述樣本間的相似性，Hu等人［2］基于鄰域關系提出了鄰域粗糙集模型，利用鄰域關系替代等價關系，鄰域粗糙集成為粗糙集框架下處理連續型數據的主要模型之一。現有鄰域粗糙集約簡算法的設計思路大多是在文獻［2］的基礎上改進或優化而提出的兩類屬性約簡算法。

第一類是基于屬性重要度的屬性約簡算法。周長順等人［9］為了提高算法的運行效率，提出了一種改進的屬性重要度對條件屬性排序，利用排序結果對原始數據進行屬性約簡；Fan等人［10］針對鄰域粗糙集忽略了不包含在任何決策類中的邊界樣本的可分性這一問題，提出了最大決策鄰域粗糙集模型，基于此模型提出了一種改進的屬性約簡算法。

第二類是基于信息觀的屬性約簡算法。Wang等人［11］用鄰域區分指數來表征鄰域關系的判別信息，用來代替鄰域粗糙集中的信息熵，設計了一種屬性約簡算法；Xu等人［12］定義了鄰域可信度和鄰域覆蓋率，并將其引入鄰域聯合熵中，提出了一種基于鄰域粗糙集的信息與代數相結合的屬性約簡算法；Wang等人［13］針對特征選擇算法在計算特征相關性時沒有考慮特征交互性這一問題，提出了一種新的信息度量方法——鄰域對稱不確定性的概念，在此基礎上提出了一種特征交互的屬性約簡算法。

上述基于鄰域粗糙集的模型都沒有考慮屬性的權重。然而，在實踐中，每個屬性對學習任務的貢獻是有所差別的，需要對不同的屬性賦予不同的權重。本文通過計算屬性的權重，提出了一種基于信息熵加權的屬性約簡算法，該算法不僅能降低屬性空間維數，而且能有效提升分類器的分類性能。

1 鄰域粗糙集模型

3 基于加權鄰域粗糙集的屬性約簡

通過計算類內熵、類間熵，以最小化類內熵、最大化類間熵為原則為屬性賦予權重，讓重要的屬性盡可能地被保留。

算法1 屬性加權算法

輸入：鄰域決策信息系統DIS=〈U，C，D〉。

輸出：屬性權重 w 。

a）for each a∈C

b） for each Dk∈D

c）根據式（13）計算當前屬性a在決策類Dk的類內熵

d） 根據式（14）計算當前屬性a的平均類內熵

e） for each Di∈D

f ）for each Dj∈D

g ） 根據式（15）計算當前屬性a在任意兩個決策類的類間熵

h）根據式（16）計算當前屬性a的平均類間熵

i ）根據式（17）（18）計算所有屬性的v， w

j）returnw

該算法的時間復雜度主要由步驟a）～h）的時間復雜度組成。步驟b）～d）是計算計算屬性的類內熵，時間復雜度為O（m∑ k/i=1 |Di|2），其中k是由決策屬性劃分的類簇的個數，m是屬性個數，|Di|代表第i個類簇樣本的個數。步驟e）～h）是計算屬性的類間熵，時間復雜度為O（m∑ k/i=1 ∑ k/j＞i |Di||Dj|），所以算法1的時間復雜度為O（m∑ k/i=1 ∑ k/j＞i |Di||Dj|）。基于所提出的加權鄰域粗糙集模型，構造了前向搜索屬性約簡算法，前向搜索算法能夠保證重要的屬性首先被加入到約簡集合中。算法的基本思路為：首先將約簡集red初始化為空集，其次計算每添加一個剩余屬性后的屬性重要度，選取使得屬性重要度最大的屬性添加至約簡集合中，直到所有剩余屬性添加到約簡集合時屬性重要度為零，即增加任意新的屬性，系統的依賴度都不會發生變化為止。

算法2 基于加權鄰域粗糙集的屬性約簡算法（WNRS）

輸入：鄰域決策信息系統DIS=〈U，C，D〉，鄰域半徑δ。

輸出：約簡集red。

a）初始化red=

b）計算每個條件屬性的權重 w

c）for each a∈C-red

d） 計算加權鄰域相似關系Wa

e）while C-red≠

f） for each a∈C-red

g） 計算加權依賴度wγred∪{a}（D）

h） 屬性重要度Sig（a，red，D）=wγred∪a（D）-wγred（D）

i） 選擇屬性ak使Sig（ak，red，D）=max（Sig（a，red，D））

j） if Sig（ak，red，D）＞0

k）red=red∪ak

l） else

m）break

n）return red

假設鄰域決策系統DIS=〈U，C，D〉，其中n為樣本個數，m為條件屬性個數，t為約簡集的個數，k為決策屬性劃分的類簇的個數。由算法1可知步驟b）的時間復雜度為O（m∑ k/i=1 ∑ k/j＞i |Di||Dj|）；步驟c）d）需要計算每個樣本在不同屬性下的鄰域，時間復雜度為O（mn2）；步驟e）～m）的時間復雜度為O（nm+n（m-1）+n（m-1）+…+n（m-t））＜O（mn2）。所以算法2的時間復雜度為O（mn2）。

4 實驗分析

為了驗證提出的加權鄰域粗糙集屬性約簡算法的有效性，在UCI數據集和盧布爾雅那大學生物信息實驗室［18］中選取10個數據集，如表1所示。為減少各屬性量綱不一致對結果的影響，實驗中將所有屬性值歸一化處理。

4.1 消融實驗

本文提出的屬性加權算法綜合考慮了類內熵（WEN）和類間熵（BEN），為驗證加權的有效，本節將表1的10個數據集在SVM分類器中進行了一系列消融實驗進行驗證，如表2所示。

在上述的消融實驗中，分別對應添加了WEN加權、BEN加權、綜合WEN和BEN加權以及未添加任何加權的方式。結果表明，不加權的平均分類精度最低，僅考慮WEN加權比不加權平均分類精度提高了1.64個百分點，只考慮BEN加權比不加權高1.03個百分點，而同時考慮WEN和BEN為屬性加權得到的分類精度最高，分別比WEN、BEN、不加權高1.67、2.28、3.31個百分點。實驗結果證明，本文提出的屬性加權算法在屬性約簡中具有很好的效果。

4.2 對比實驗

將本文提出的加權鄰域粗糙集的屬性約簡算法（WNRS）與以下三種經典的屬性約簡算法在約簡率、分類精度和運行時間進行對比，對比算法分別為：基于鄰域粗糙集的屬性約簡算法（NRS）［2］、基于可區分度的啟發式屬性約簡算法（DISAR）［19］、基于鄰域組合熵的屬性約簡算法（ARNCE）［20］。 三種算法都是在NRS的基礎上進行改進的，其中：DISAR定義了類內區分度和類間區分度，提出了一種新的屬性重要度判別準則以替代NRS中的屬性重要度； ARNCE則是通過鄰域條件熵和鄰域近似精度進行組合，定義了一種新的屬性重要度度量；而本文提出的WNRS則是首先通過決策類劃分類簇，計算屬性的類內熵和類間熵為屬性賦予權重，再重新定義加權鄰域相似關系和構造加權鄰域粗糙集模型，最后進行屬性約簡。

4.2.1 約簡率比較

在本節中，將WNRS與三種對比算法的約簡集的屬性個數和約簡率進行了比較，其中約簡率=（（|A|－|red|）/|A|）×100%。約簡率越高代表消除冗余屬性的能力越強。從表3的數據可以看出，WNRS在10個數據集上的平均約簡率高于其他三種算法，從約簡集的平均屬性個數看，WNRS也低于其他三種對比算法，表明WNRS具有較強的屬性約簡能力。分析原因在于，采用對屬性加權的策略，屬性的權重會同時促進或抑制屬性的重要性。通過引入權重，與區分能力強的屬性在重要度上得到了提升，相比于沒有權重作用的情況下，它們顯得更為突出，另一方面，冗余屬性的重要度則比沒有賦予權重時相應降低，更不容易被選擇到約簡集中。在表格中，將各數據集在四種約簡算法中的最優約簡集屬性個數和約簡率加粗。

4.2.2 分類精度比較

為了比較不同約簡算法所選屬性的分類能力，本文采用了支持向量機（SVM）、K近鄰（KNN）、分類回歸樹（CART）三種常見的分類器。對不同算法的約簡集進行10次十折交叉驗證得到分類精度，如表4～6所示。在每個表格中，分類精度都以平均值的形式表示，將每個數據集在四種約簡算法中的最優分類精度加粗。從表格中可以看出，在三種分類器中都表現出了優異的分類性能，其中WNRS在SVM分類器中比NRS、DISAR、ARNCE的平均分類精度分別提升了約3.3、2.6、2.8個百分點；在KNN分類器中，WNRS與三種對比算法相比都有所提升，最高提升了3.54個百分點；在CART分類器中，WNRS比NRS的平均分類精度高3.08個百分點，比DISAR高2.9個百分點，比ARNCE高3.36個百分點。從取得最優分類精度的數據集個數上看，WNRS是最多的，在SVM和KNN分類器中有8個數據集，在CART分類器中有9個數據集。從三種分類器的結果可以看出，事先對屬性賦予權重再進行屬性約簡，得到的約簡集具有更強的分類能力。造成這種結果的原因是：傳統屬性約簡算法在計算鄰域關系時使用相同的權重，沒有挖掘出屬性與決策之間的關系。而本文WNRS中，在屬性約簡前，使用類內熵和類間熵綜合評估屬性對不同決策樣本的區分能力，區分能力強的屬性被賦予更高的權重，在屬性約簡過程中更容易被添加到約簡集中，從而得到更高的分類精度。

4.2.3 運行時間比較

在本節中比較了幾種約簡算法的運行時間，最終的運行時間以3次約簡算法運行時間的平均值表示。由于ARNCE同時考慮信息熵和近似測度，時間復雜度較高，在原文中也沒有比較運行時間，所以本文算法只與其他兩種算法進行比較。本文更關注算法在規模與維度較高的數據集的表現能力，因此挑選了幾個維度較高的數據集進行實驗對比，結果用圖1柱狀圖表示。

從圖1可以看出，在以下數據集中WNRS與其他兩種算法相比運行時間最少，分析其原因可能是相比于NRS，盡管WNRS對屬性計算權重時需要花費額外的時間，但是WNRS的約簡能力更強，保證分類精度的情況下選擇的屬性更少，而WNRS與NRS都采用前向搜索算法，選擇的屬性越少，約簡算法越快結束，運行時間越少。而DISAR的運行時間明顯高于其他兩種算法，這是因為DISAR的終止條件會使得約簡屬性集存在過擬合的問題，導致運行時間過長。

4.3 鄰域半徑的選擇分析

對于加權鄰域粗糙集屬性約簡算法，在不同的鄰域半徑選擇的屬性子集和分類精度不同，圖2是部分數據集在不同鄰域半徑下的約簡集個數和分類精度變化的曲線。從圖2可以發現，對于大多數數據集來說，隨著鄰域半徑的增加，所選擇的屬性個數也在增加，分類精度先增大后保持不變或者減小。每個圖中的虛線框的位置是最佳約簡結果，即所選擇的屬性子集少且分類精度較高。

4.4 算法應用

為了驗證WNRS算法的實用性，將該算法用于紅斑鱗狀皮膚病診斷，旨在幫助醫生和研究人員在進行皮膚病診斷時提供依據。所用數據集是UCI數據庫中的dermatology dataset，有366個樣本數據，該數據包含34個屬性，其中12個臨床屬性以及22個病理學屬性。為驗證算法的有效性和實用性，先通過本文改進的算法將屬性集合進行約簡，然后通過SVM、KNN、CART分類器進行分類，為展示正確和錯誤的分類結果，采用混淆矩陣進行評價。

通過本文的WNRS算法將屬性約簡至8個，約簡集為{4、5、15、16、22、27、31、33}，屬性的約簡率達到76.5%。同時在訓練集和測試集之比為7∶ 3的情況下， SVM、KNN、CART三種分類器的分類精度為0.990 9、0.981 8、0.981 8；混淆矩陣結果如圖3所示，據圖可知，經過屬性約簡后，三種分類器在預測3、5、6類皮膚病上的準確率都是100%，此外SVM分類器在2、4類皮膚病的準確率也是100%。通過屬性約簡后，數據特征數量得到有效降低的同時，分類結果也能夠得到有效保證，都體現了WNRS算法的合理性以及有效性，證明了該算法具有應用價值。

5 結束語

針對傳統鄰域粗糙集的屬性約簡在計算鄰域關系時使用相同的權重，沒有充分挖掘屬性和決策之間的關系這一缺點，本文提出了一種基于信息熵加權的鄰域粗糙集的屬性約簡算法。本文的主要工作是使用類內熵、類間熵給每個屬性賦予權重，再構造加權鄰域粗糙集模型，將加權鄰域依賴關系作為度量屬性重要度的函數，最后進行屬性約簡。

通過實驗仿真結果驗證了WNRS算法的可行性和有效性，在大多數數據集上的約簡結果表明本文算法可以在維持原始分類能力的情況下去除冗余屬性，有較好的約簡效果。

參考文獻：

［1］Pawlak Z. Rough sets［J］.International Journal of Computer amp; Information Sciences ， 1982， 11 ： 341－356.

［2］Hu Qinghua，Yu Daren，Liu Jinfu，et al . Neighborhood rough set based heterogeneous feature subset selection［J］.Information Sciences ， 2008， 178 （18）： 3577－3594.

［3］Sheeja T K， Kuriakose A S. A novel feature selection method using fuzzy rough sets［J］.Computers in Industry ， 2018，97 ： 111－116.

［4］Greco S， Matarazzo B， Slowinski R. Rough sets theory for multicriteria decision analysis［J］.European Journal of Operational Research ， 200 129 （1）： 1－47.

［5］Qu Kanglin， Xu Jiucheng， Han Ziqin，et al . Maximum relevance minimum redundancy－based feature selection using rough mutual information in adaptive neighborhood rough sets［J］.Applied Intelligence ， 2023， 53 （14）：17727－17746.

［6］Luo Chuan， Li Tianrui， Chen Hongmei，et al . Incremental approaches for updating approximations in set－valued ordered information systems［J］.Knowledge－Based Systems ， 2013， 50 ： 218－233.

［7］Guo Yanting， Tsang E C C， Hu Meng，et al . Incremental updating approximations for double－quantitative decision－theoretic rough sets with the variation of objects［J］.Knowledge－Based Systems ， 2020， 189 ： 105082.

［8］Pan Yanzhou， Xu Weihu Ran Qinwen. An incremental approach to feature selection using the weighted dominance－based neighborhood rough sets［J］.International Journal of Machine Learning and Cybernetics，2023， 14 （4）： 1217－1233.

［9］周長順，徐久成，瞿康林，等. 一種基于改進鄰域粗糙集中屬性重要度的快速屬性約簡方法［J］.西北大學學報：自然科學版， 2022， 52 （5）：745－752. （Zhou Changshun， Xu Jiucheng， Qu Kanglin， et al . A fast attribute reduction method based on improved attribute importance in neighborhood rough sets［J］.Journal of Northwest University：Natural Science Edition ， 2022， 52 （5）：745－752.）

［10］Fan Xiaodong， Zhao Weid Wang Changzhong，et al . Attribute reduction based on max－decision neighborhood rough set model［J］.Knowledge－Based Systems ， 2018，151 ： 16－23.

［11］Wang Changzhou， Hu Qinghu Wang Xizhao，et al . Feature selection based on neighborhood discrimination index［J］.IEEE Trans on Neural Networks and Learning Systems ， 2017， 29 （7）： 2986－2999.

［12］Xu Jiucheng， Qu Kanglin， Yuan Meng， et al. Feature selection combining information theory view and algebraic view in the neighborhood decision system［J］.Entropy ， 202 23 （6）： 704.

［13］Wang Wenjing， Guo Min， Han Tongtong，et al . A novel feature selection method considering feature interaction in neighborhood rough set［J］.Intelligent Data Analysis，2023，27 （2）： 345－359.

［14］Rényi A. On measures of entropy and information［C］//Proc of the 4th Berkeley Symposium on Mathematical Statistics and Probability. 1961： 547－562.

［15］Parzen E. On estimation of a probability density function and mode［J］.The Annals of Mathematical Statistics ， 1962，33 （3）： 1065－1076.

［16］Jenssen R， Eltoft T， Erdogmus D，et al . Some equivalences between kernel methods and information theoretic methods［J］.Journal of VLSI Signal Processing Systems for Signal， Image and Video Technology ， 2006，45 ： 49－65.

［17］Liang Jiye， Zhao Xingwang， Li Deyu，et al . Determining the number of clusters using information entropy for mixed data［J］.Pattern Recognition ， 2012，45 （6）： 2251－2265.

［18］University of Ljubljana Faculty of Bioinformatics Laboratory. Orange DataMining ［DB/OL］. ［2017－03－22］. https：//file.biolab.si/biolab/supp/bi－cancer/projections/info/DLBCL.html.

［19］張敏， 朱啟兵， 黃敏. 基于可區分度的連續空間屬性約簡算法研究 ［J］. 計算機應用研究， 2022，39 （4）： 1013－1018. （Zhang min， Zhu Qibing， Huang Min. Research on continuous space attri－bute reduction algorithm based on discrimination［J］.Application Research of Computers ， 2022， 39 （4）： 1013－1018.）

［20］王光瓊. 基于鄰域組合熵的屬性約簡算法 ［J］. 計算機應用與軟件， 2018， 35 （12）：269－273，284. （Wang Guangqiong. Attribute reduction algorithm based on neighborhood combinatorial entropy［J］.Computer Applications and Software ， 2018， 35 （12）： 269－273，284.）

收稿日期：2023－07－19；修回日期：2023－10－08

作者簡介：羅帆（1999—），女，四川南充人，碩士研究生，主要研究方向為數據挖掘、粗糙集；蔣瑜（1980—），男（通信作者），四川鄰水人，副教授，碩士，主要研究方向為數據挖掘、粗糙集與智能計算（jiangyu@cuit.edu.cn）．