基于鄰域粗糙集和蟻群優化的屬性約簡算法

張冬雯，王 鵬，仇計清

（1.河北科技大學理學院，河北石家莊 050018；2.河北科技大學信息科學與工程學院，河北石家莊050018）

基于鄰域粗糙集和蟻群優化的屬性約簡算法

張冬雯1，王 鵬2，仇計清1

（1.河北科技大學理學院，河北石家莊 050018；2.河北科技大學信息科學與工程學院，河北石家莊050018）

在分析單一、給定的鄰域大小設定方法弊端的基礎上，提出了基于屬性數據標準差的閾值設定方法，并將蟻群優化算法引入到屬性約簡中，以屬性重要度為啟發信息，構造了基于鄰域粗糙集和蟻群優化的屬性約簡算法，使用了4個UCI數據集進行約簡。實驗結果表明，提出的算法在約簡的分類精度和約簡中屬性個數方面具有更好的性能。

鄰域粗糙集；蟻群優化；屬性約簡；標準差

屬性約簡的目的是在不降低預測分類精度的前提下對數據的屬性集合進行約簡，摒棄冗余的屬性，從而降低對數據處理時的時間和空間復雜度［1］。所有的屬性約簡算法都包括2個重要的部分：評價函數和子集生成器。評價函數是對屬性子集的分辨能力的一種量度，它能夠對屬性子集的預測分類精度進行評估；子集生成器是使用評價函數對屬性集合進行約簡，得到最優屬性子集的過程。作為一個重要的粒度計算工具，粗糙集理論（RST）［2］被廣泛應用于屬性約簡的算法中［3－5］。然而，粗糙集理論使用等價關系和等價類的概念對整個論域進行劃分，這只適用于處理離散型屬性的數據。對于現實應用中的大量數據，往往同時存在離散型和連續型2種屬性。對于連續型屬性，應用粗糙集理論就必須首先對這些屬性進行離散化，顯然，對連續型屬性進行離散化必然會帶來數據信息的丟失。文獻［6］提出了基于鄰域的粗糙集（NRS）模型來對連續型屬性進行約簡的算法。該算法使用鄰域關系對論域進行劃分，然后使用這種由鄰域關系形成的粒子族來對決策屬性進行逼近，從而提出了鄰域決策表模型，并基于此模型構造了連續型屬性的屬性約簡算法。作為該模型的一個重要參數，鄰域的大小對屬性約簡的結果有著重要的影響，但是在文獻［6］中并沒有對這一參數進行分析。在上面提到的屬性約簡的算法中，都使用了貪心算法作為屬性約簡的子集生成器。然而，由于貪心算法往往只能夠找到較優的約簡結果而不是最優的約簡結果，所以，許多研究者采用了基于群的算法作為子集生成器來構造最優約簡。例如：遺傳算法（GA）［7］，粒子群優化算法（PSO）［8］和蟻群優化算法（ACO）［2，9-11］。

筆者對文獻［6］中的方法進行改進，提出了一個基于鄰域粗糙集模型和蟻群優化的屬性約簡算法。在本算法中，筆者使用基于屬性數據分布特征的參數作為鄰域的大小，并將基于鄰域粗糙集的屬性重要度作為蟻群算法的啟發信息，使用蟻群算法作為子集生成器，得到屬性的最優約簡。

1 預備知識

1.1 鄰域粗糙集

定義1 給定樣本集合U＝｛x1，x2，…，xn｝，U 稱為論域，C是條件屬性集，D是決策屬性集，如果C中所有屬性能夠產生論域U上的一簇鄰域關系N，則稱NDT＝〈U，C∪D，N〉為一鄰域決策系統。

定義2 給定一鄰域決策系統NDT＝〈U，C∪D，N〉，決策屬性D將U劃分為M 個等價類：X1，X2，…，XM，δB（xi）是由B?C對xi生成的鄰域信息粒子，則決策屬性D關于B的上下近似定義為

1.2 蟻群優化算法

蟻群優化算法是一種基于螞蟻的社會行為模型的算法，它能夠將復雜的組合優化問題簡化為在圖中尋找最短路徑。它的主要思想是生產一定數量的螞蟻，通過螞蟻搜索路徑建立可行解。先將螞蟻隨機放置在若干結點上，每只螞蟻從初始結點出發，根據路徑上的啟發信息和信息素濃度以某種概率策略選擇下一結點，直到建立可行解。每只螞蟻根據解的優劣對路徑上的信息素濃度進行更新。如此周而復始，直到最終找到最優解。

1）選擇概率公式 1只螞蟻從結點i選擇結點j的概率為

定義3 給定一鄰域決策系統NDT＝〈U，C∪D，N〉，條件屬性子集B?C，則決策屬性D關于B的依賴度定義為

式中：τij是在給定的邊（i，j）上的信息素；α是控制信息素對概率影響的參數；ηij是結點j對結點i的啟發信息；β是控制啟發信息對概率影響的參數。

2）信息素更新公式 每條邊上的信息素會因為螞蟻的走過而增強，同時會隨時間而蒸發，其更新的公式為

式中：τij是在給定的邊（i，j）上的信息素；ρ是信息素蒸發的速率；Δτij是信息素增強值。

2 主要研究成果

2.1 鄰域大小的設定

在鄰域粗糙集中，鄰域的大小是一個關鍵的參數，如何設定一個合適的閾值將直接影響屬性約簡的結果。鄰域信息粒度是由鄰域大小決定的，這個閾值過大時，對某一條件屬性集合，幾乎所有的樣本會被劃分到同一個鄰域關系里，這時，決策屬性對該屬性的依賴度將變得非常小，從而使得約簡后的屬性變得太少。相反，這個閾值為0時，鄰域粗糙集將會等價于經典的粗糙集理論。為了說明閾值的大小對決策屬性依賴度的影響，現舉例如下。

例1 在表1中，F1和F2是2個條件屬性，首先設定鄰域大小的閾值δ＝0.6，則可以通過式（3）計算出γF1（D）＝0。同理，設定δ＝0.04，可以得到γF1（D）＝1。可見，鄰域大小的設定對屬性的依賴度有著重要的影響。

例2 鄰域大小對屬性依賴度有一定的影響，圖1顯示了不同的閾值對屬性依賴度的影響。筆者選用UCI數據集中的Wine數據集作為源數據，選取第8，9，10，11，12，13屬性作為屬性集合，閾值從0到0.5以0.1為步長分別計算該屬性集合的依賴度。從圖1中可以發現，當閾值為0時，屬性集合的依賴度為1.0；而當閾值接近0.5時，依賴度變為0。而且，隨著閾值的變大，依賴度逐漸變小。

表1 閾值分析實例Tab.1 An example of threshold analysis

由以上2例可以看出，閾值的設置對屬性約簡有重要的影響，如果為鄰域設定一個特定的值，往往不能夠得到正確的屬性約簡。而且每一屬性的值，即使將它們都規范化到［0，1］，其數據的分布特征也是不相同的，以例1中的數據為例，通過對屬性F1和F2中數據的標準差進行計算可以發現，F1的標準差SDF1遠大于F2的標準差SDF2，所以，當為屬性F1和F2設置相同的閾值時，必然會為屬性約簡帶來更大的誤差。

為了減小這些誤差，筆者一方面采用一個閾值集合取代單一的閾值來設置鄰域的大小，這些閾值對應于每一個屬性；另一方面采用基于屬性值的分布特征的參數作為閾值。作為一個統計量，標準差顯示了數據在平均值的平均波動大小。當標準差小時，所有的數據都接近于平均值，這時需要為鄰域設定一個較小的閾值；相反，當標準差較大時，這個閾值也要變大。正是由于閾值與標準差之間的線性關系，筆者選擇SD／n作為鄰域大小的閾值，這里n是控制這種線性關系的參數，可以針對不同的數據在實驗中進行設置。

圖1 鄰域大小對屬性依賴度的影響Fig.1 Influence of neighborhood on feature dependability

定義6 給定一鄰域決策系統NDT＝〈U，C∪D，N〉，SD＝｛SD1，SD2，…，SDm｝是包含每個屬性的數據的標準差的集合，m是屬性的個數，s是U中的樣本總個數，對屬性i（1≤i≤m）在U上的鄰域關系Ni的關系矩陣為

2.2 基于NRS和ACO的屬性約簡算法

屬性約簡的目的是在保持較高分類精度的前提下，找出初始屬性集合的最小屬性子集。筆者采用ACO算法作為屬性約簡算法的子集生成器。首先，將屬性約簡問題轉化成1個可以使用ACO算法的模型。如圖2所示，1個結點代表了1個屬性，連接2個結點的邊代表從一屬性對下一屬性的選擇。螞蟻在圖2中對所有節點進行遞增的移動，當滿足終止條件時停止移動，就得到一條路徑，這樣屬性約簡的問題就轉化為在圖2中找出最短路徑的問題。

1）基于ACO的屬性約簡算法的啟發信息

在以往的研究中，很多的量度方法被作為啟發信息應用到ACO算法中，如基于信息熵的方法［11］、基于粗糙集的方法［2］。筆者使用基于鄰域粗糙集的量度方法作為ACO算法的啟發信息。

定義7 給定一只螞蟻走過的屬性的集合B，p為螞蟻當前所在的屬性結點，r為螞蟻可能選擇的下一屬性結點，則r對p的啟發信息定義為

其中SIG是在定義5中給出的屬性重要度函數。

2）基于ACO的屬性約簡算法的信息素更新

在每只螞蟻構建出一個解后，在每條邊上的信息素將按式（6）進行更新，每一條邊都會進行信息素的揮發，而只有構建出較優解時，螞蟻才會在這個較優解中的各屬性結點之間的邊上對信息素進行加強。在時間t，信息素加強的數量為

圖2 屬性約簡轉化成ACO問題的模型Fig.2 Model of feature selection reformulated as ACO

式中：q為一個給定的參數；R（t）為在時間t的最優解。

3）基于ACO的屬性約簡算法的終止條件

每只螞蟻獨立進行解的生成，當達到終止條件時，解的生成過程將結束。終止條件有2個：1）根據定義3判斷當前構筑的解是否為所有屬性的一個約簡；2）當前的解中屬性的個數是否小于臨時最優解。

第1個條件表明螞蟻找到了1個新的約簡，第2個條件將新得到的約簡與臨時最優解進行比較，如果當前的約簡優于臨時解，則用當前約簡替換臨時解。

在時間t達到最大值時，整個算法將結束，然后輸出最終的解。算法的主要步驟如下。

Step1 初始化

1）Rmin＝C，C為條件屬性集合；

2）設置Tτ，Tτ為每個條件屬性的信息素數量的集合；

3）定義最大的時間和螞蟻個數；

4）定義參數α，β，p，q的大小。

Step2 計算每1個條件屬性的鄰域關系

對C中每個屬性，通過式（7）計算其領域關系矩陣。

Step3 解的生成

1）每只螞蟻都隨機選擇第1個屬性，然后獨立進行解的生成；

2）通過式（5）和式（8）計算出每個待選屬性的選擇概率，螞蟻選擇概率最大的屬性作為下一屬性；

3）當達到終止條件1）時，生成解的過程將結束；

4）構筑的解即為C的一個約簡。

Step4 更新Rmin

當達到終止條件2）時，即當前的約簡中屬性的個數小于Rmin中屬性的個數，則將當前的約簡賦值給Rmin，否則繼續。

Step5 更新信息素

1）當Rmin發生更新時，在Rmin中每個屬性的信息素通過式（6）進行加強；

2）對每個時間t，每個屬性的信息素都通過式（9）進行蒸發。

Step6 判斷終止條件

當迭代次數達到最大迭代數時，算法將結束，并輸出Rmin，否則繼續。

Step7 轉到Step3，然后繼續。

3 實驗和結果

為了驗證筆者提出的算法性能，使用4個UCI數據集進行實驗，并與文獻［7］中提供的算法（FSNMA）進行比較，使用C4.5和Navie Bayes（NB）機器學習的算法，評估和FSNMA算法在約簡檢測精度上的差異。所有的實驗是在3.0 GHz CPU，1 GB內存的計算機上完成的，使用Matlab實現。

3.1 數據集

從UCI數據集中選取4個數據集作為實驗的數據，即Ionosphere數據集、Sonar數據集、S-soybean數據集和Wine數據集。表2詳細給出了4個數據集的樣本個數、屬性個數以及各自的類別種類。

3.2 參數設置

在筆者提供的方法中，用于子集生成器的參數進行如下的設置：α＝1，β＝0.1，ρ＝0.2，q＝1，螞蟻的個數為條件屬性的個數，最大迭代數為50。參數n是控制鄰域大小的關鍵參數，為了得到最佳的參數設置，以0.1為步長，從2到3為n進行賦值，以評估不同的參數值對分類精度的影響，從而確定最佳的參數值。以Ionosphere數據集為例，圖3顯示了參數n的不同取值對分類精度的影響。

表2 4個UCI數據集Tab.2 Detail of the four UCI datasets

從圖3中可發現，當n的取值為2.8時，C4.5算法和NB算法都能達到較高準確性，雖然當n為2.2時C4.5算法擁有最高的準確性，但此時NB算法的準確性卻很低，所以，棄用n＝2.2。同理，n＝2.6也不會被選擇。用以上的評估方法，分別為Sonar，S-soybean，Wine數據集設置參數n為2.2，2.0，2.0。

3.3 實驗結果

表3顯示了使用該算法和FSNMA算法得到的約簡中的屬性個數。從表3可以看出，2種屬性約簡算法都能有效降低數據的屬性個數。FSNMA算法將屬性的平均個數從35.5個約簡到7.25個，而本文算法能夠約簡到5.75個。具體到4個數據集，在Sonar，S-soybean，Wine數據集2種算法的約簡在屬性個數上相同，但具體屬性不同，而在Ionosphere數據集上本文算法得到約簡中的屬性個數明顯比FSNMA算法少。從表3結果可以看出，本文算法在約簡的屬性個數上具有一定優勢。表4中給出了本文算法所得到約簡的具體屬性。

圖3 參數n對分類精度的影響Fig.3 Influence of n on classification accuracy

表3 屬性約簡中屬性的個數Tab.3 Number of features selected

表4 4個數據集的屬性約簡Tab.4 Feature selection of the four datasets

為了評估本文算法在分類精度上的性能，筆者采用C4.5和NB分類算法對全部屬性、本文算法和FSNMA算法的約簡結果進行分類精度的計算，并將結果匯總到表5中。

表5 分類精度Tab.5 Classification accuracy

從表5中可以看出，2種約簡算法得到的約簡在分類精度上都要優于全部屬性，同時由于屬性個數的降低，從而減少了分類算法進行分類精度計算時的時間。特別是對S-soybean數據集，約簡后的分類精度能夠達到100%。對比本文算法和FSNMA算法，除在S-soybean數據集上兩者都達到100%的分類精度外，本文算法都表現了更好的分類精度。

綜合表3、表5可以看出，相比于全部屬性，本文算法能夠有效找到屬性約簡，而且約簡的分類精度更高。相比于FSNMA算法，本文算法得到的約簡不僅屬性個數更小，同時在分類精度上具有更好的性能。

4 結 語

提出了一種基于鄰域粗糙集和蟻群優化的屬性約簡算法。在仔細分析了鄰域大小的閾值對屬性依賴度的影響后，提出了依賴于屬性數據本身標準差的參數作為鄰域大小的閾值。通過使用C4.5和NB算法對屬性約簡的結果進行分類精度比較，實驗結果表明本文算法能夠得到較好的性能。

［1］ RICHARD J，QIANG S.Computational and Feature Selection：Rough and Fuzzy Approaches［M］.Hoboken：Whiey-IEEE Press，2008.

［2］ 苗奇謙，李道國.粗糙集理論、算法與應用［M］.北京：清華大學出版社，2008.

［3］ SWINIARSKI R W，SKOWRON A.Rough set methods in feature selection and recognition［J］.Pattern Recognition Letters，2003，24（6）：833-849.

［4］ ZHAI Lian-yi，KHOO L P.Feature extraction using rough set theory and genetic algorithms-an application for the simplification of product quality evaluation［J］.Computers ＆Industrial Engineering，2002，43（4）：661-676.

［5］ ZHONG N，DONG J.Using rough sets with heuristics for feature selection［J］.Journal of Intelligent Information Systems，2004，16（3）：199-214.

［6］ 胡清華，于達仁.基于鄰域?；痛植诒平臄抵祵傩约s簡［J］.軟件學報（Journal of Software），2008，19（3）：640-649.

［7］ 蒙祖強，黃柏雄.不一致不完備決策系統中屬性約簡的比較研究［J］.控制與決策（Contrd and Decision），2011，26（6）：867-872.

［8］ 胡 峰，王國胤.屬性序下的快速約簡算法［J］.計算機學報（Chinese Journal of Computers），2007，30（8）：1 429-1 435.

［9］ KE L L，FENG Z R.An efficient ant colony optimization approach to attribute reduction in rough set theory［J］.Pattern Recognition Letters，2008，29（9）：1 351-1 357.

［10］ CHEN Y M，MIAO D Q.A rough set approach to feature selection based on ant colony optimization［J］.Pattern Recognition Letters，2010，31（3）：226-233.

［11］ DORIGO M.Ant Colony Optimization［M］.Cambridge：MIT Press，2004.

Approach to feature selection based on neighborhood rough set and ant colony optimization

ZHANG Dong-wen1，WANG Peng2，QIU Ji-qing1
（1.College of Sciences，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China；2.College of Information Science and Engineering，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China）

This paper analyses the weakness of setting a single，specified threshold for the size of neighborhood，and then puts forward a new neighborhood setting method based on the standard deviation of feature data.The paper introduces ant colong opbimization（ACO）into feature selection and proposes an approved feature selection algorithm based on NRS and ACO，in which the feature importance is taken as the heuristic information.In order to evaluate the performance of the proposed algorithm，four datasets from UCI are used and the experimental results show that the proposed algorithm has a better performance in classification accuracy of reduct and feature number in reduct.

neighborhood rough set；ant colony optimization；feature selection；standard deviation

O231

A

1008-1542（2011）05-0403-06

2010-12-26；

2011-06-08；責任編輯:張 軍

國家自然科學基金資助項目（60874003）

張冬雯（1964-），女，河北石家莊人，教授，博士，主要從事優化、預測控制方面的研究。