梁吉業(yè)，李超偉，魏巍

（1.山西大學(xué) 計算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原 030006;2.山西大學(xué) 計算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006）

基于Rough Sets的特征選擇研究進(jìn)展

梁吉業(yè)1，2，李超偉1，2，魏巍1，2

（1.山西大學(xué) 計算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原 030006;2.山西大學(xué) 計算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006）

特征選擇是機(jī)器學(xué)習(xí)領(lǐng)域中的重要研究問題.作為一種重要的特征選擇方法，屬性約簡正在受到越來越多的關(guān)注，在許多應(yīng)用領(lǐng)域已經(jīng)得到了廣泛應(yīng)用.文章對基于Rough Sets理論的特征選擇算法作了系統(tǒng)的回顧和分析，具體包括啟發(fā)式屬性約簡、基于區(qū)分矩陣的屬性約簡和擴(kuò)展粗糙集模型的屬性約簡三個方面.此外，論文還給出了粗糙特征選擇算法的幾種常見應(yīng)用，并對該領(lǐng)域的進(jìn)一步發(fā)展進(jìn)行了展望.

特征選擇;粗糙集;屬性約簡;區(qū)分矩陣;啟發(fā)式搜索

0 引言

2011年出版的《Science》雜志在社論中指出，“數(shù)據(jù)推動著科學(xué)的發(fā)展”［1］.隨著計算機(jī)技術(shù)、網(wǎng)絡(luò)技術(shù)的不斷發(fā)展和普及，數(shù)據(jù)的采集和存儲變得更為便利和快捷，這使得數(shù)據(jù)的規(guī)模不斷增長，形成了高維海量的數(shù)據(jù)信息.這些數(shù)據(jù)中承載著大量的有效信息，在方便人類發(fā)展的同時卻也為許多應(yīng)用領(lǐng)域帶來了更嚴(yán)峻的挑戰(zhàn)，即如何保留復(fù)雜數(shù)據(jù)中的有效信息以及如何從這些數(shù)據(jù)發(fā)現(xiàn)有價值的知識［2－3］.美國學(xué)者M(jìn)jolsness和Decoste［4］在《Science》雜志上系統(tǒng)地分析了機(jī)器學(xué)習(xí)在科學(xué)研究各個階段扮演的重要角色，認(rèn)為機(jī)器學(xué)習(xí)技術(shù)能夠在各個方面協(xié)助眾多研究者加速科研進(jìn)程.

特征選擇是機(jī)器學(xué)習(xí)領(lǐng)域中一種常用的數(shù)據(jù)處理技巧，也是該領(lǐng)域中一個極具挑戰(zhàn)性的問題.特征選擇通過消除無關(guān)和冗余特征，來提高知識發(fā)現(xiàn)的效率以及改善分類器的性能.波蘭學(xué)者Pawlak提出的粗糙集理論（Rough Sets Theory）［5］是一種相對較新的處理不確定和不精確信息的軟計算工具，并已廣泛應(yīng)用于構(gòu)造特征選擇算法，逐漸成為一種重要的特征選擇理論框架.基于粗糙集理論的特征選擇稱為屬性約簡，它是在保持原始數(shù)據(jù)的屬性區(qū)分能力不變的前提下，選擇具有最小特征（屬性）數(shù)的特征子集.

由于粗糙集理論思想新穎、方法獨(dú)特，眾多研究者在近二十年里發(fā)展了大量的、可行的、有效的屬性約簡算法［6－8］.Skowron給出了基于區(qū)分矩陣的方法來求解給定信息系統(tǒng)的所有約簡，但由于求解所有約簡是一個NP-Hard問題［9］，眾多研究者進(jìn)行了更為系統(tǒng)的研究.比如，針對處理大規(guī)模數(shù)據(jù)集計算耗時過大的問題，許多學(xué)者提出了啟發(fā)式的搜索機(jī)制來尋找一個單一的約簡結(jié)果，從而有效降低計算代價.許多基于不同目標(biāo)函數(shù)定義的啟發(fā)式約簡算法被提出，這些算法從許多不同的角度來尋找滿足目標(biāo)函數(shù)的約簡結(jié)果.此外，其他的一些學(xué)者通過進(jìn)一步分析區(qū)分矩陣的定義，構(gòu)造了新的區(qū)分矩陣，并在此基礎(chǔ)上提出了許多新的基于區(qū)分矩陣的屬性約簡算法.在粗糙集理論的發(fā)展中，為從各類數(shù)據(jù)中獲取有用知識，眾多學(xué)者在經(jīng)典的Pawlak粗糙集模型基礎(chǔ)上，拓展了新的粗糙集模型（模糊粗糙集、優(yōu)勢關(guān)系粗糙集、決策理論粗糙集、變精度粗糙集等）.基于拓展的粗糙集模型，相應(yīng)的屬性約簡算法都有相應(yīng)的研究成果.

隨著粗糙集理論的快速發(fā)展，針對粗糙特征選擇算法的研究在理論和應(yīng)用上都已取得了很多成果.本文的主要目的是從特征選擇的視角對粗糙集理論中的屬性約簡算法進(jìn)行系統(tǒng)的分析.本文回顧并總結(jié)了已有的研究成果，并指出了進(jìn)一步的研究方向，希望進(jìn)一步推動并促進(jìn)這一領(lǐng)域的研究工作.

1 粗糙特征選擇算法

屬性約簡是粗糙集理論的核心概念之一，它是在保持原始數(shù)據(jù)的屬性區(qū)分能力不變的前提下，選擇具有最小特征（屬性）數(shù)的特征子集.經(jīng)典的屬性約簡定義需要滿足兩個條件：（1）選擇到的屬性子集與原始的屬性集具有相同的區(qū)分能力;（2）選擇到的屬性子集中不存在冗余的屬性.基于該定義，許多學(xué)者發(fā)展了各種各樣的約簡算法.本節(jié)從三個方法闡述已有的屬性約簡的研究成果，分別是啟發(fā)式的屬性約簡、基于區(qū)分矩陣的屬性約簡和拓展粗糙集模型中的屬性約簡算法.

1.1 啟發(fā)式屬性約簡算法

問題求解中為減小搜索范圍而需要利用某些已知的、有關(guān)具體問題領(lǐng)域的特性信息，這種信息叫做啟發(fā)式信息，利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索方法.由于該方法實(shí)現(xiàn)過程比較簡單而且快速，在實(shí)際中應(yīng)用非常廣泛，如向前（向后）貪婪選擇、Relief方法等［10－11］.但是，啟發(fā)式搜索方法作為一種近似算法，通常不能得到最優(yōu)解，只能得到近似于最優(yōu)解的解.隨著粗糙集理論的提出以及對屬性約簡方法的深入探索，一些學(xué)者將啟發(fā)式搜索方法引入到屬性約簡的求解中，構(gòu)造了啟發(fā)式屬性約簡的求解機(jī)制.需要指出的是啟發(fā)式屬性約簡算法得到的約簡結(jié)果可能具有冗余屬性，可通過一個回溯的過程予以消除.

Hu和Cercone將啟發(fā)式搜索方法引入到屬性約簡的求解中［12］，提出了基于正區(qū)域的啟發(fā)式屬性約簡算法.該算法將屬性的重要度作為啟發(fā)式信息，屬性的重要度定義為去掉該屬性后正區(qū)域變化的大小.該算法比較簡單、直觀，以核屬性為求解約簡結(jié)果的出發(fā)點(diǎn)，按照屬性的重要度從大到小逐個加入屬性，直到約簡結(jié)果的屬性依賴度與原始屬性的屬性依賴度相同為止.為刪除所得約簡結(jié)果中的冗余屬性，該算法接著檢查所得結(jié)果中的每個屬性，如果刪除該屬性后約簡結(jié)果的屬性依賴度不變，則表明該屬性是冗余的，進(jìn)而刪除該屬性.

熵是起源于經(jīng)典熱力學(xué)中的一個概念，用于度量系統(tǒng)的無序和混亂程度.Shannon將熵引入到度量離散型隨機(jī)變量的隨機(jī)性大小，稱為信息熵（Shannon熵）.隨著粗糙集理論的發(fā)展，信息熵已經(jīng)被廣泛應(yīng)用于度量粗糙集意義下信息系統(tǒng)的不確定性.王國胤等從信息論的角度分析了粗糙集屬性約簡［13－14］，并提出了基于Shannon條件熵的決策表啟發(fā)式屬性約簡算法.該算法基于Shannon條件熵來構(gòu)造屬性重要度，以決策表核屬性集為起點(diǎn)，逐次選擇屬性重要度最大的屬性添加到核屬性中，直至滿足得到的約簡結(jié)果的條件熵與原始所有條件屬性的熵相等為止.考慮到Shannon熵并不能用于度量粗糙集的模糊性，梁吉業(yè)等將互補(bǔ)熵引入到粗糙集理論中［15－16］.互補(bǔ)熵不僅可以用于度量一個粗糙集的模糊性，也可以度量信息系統(tǒng)的不確定性.基于互補(bǔ)熵設(shè)計的啟發(fā)式屬性約簡算法主要通過保持給定目標(biāo)決策的條件互補(bǔ)熵不變，來尋找相應(yīng)的約簡結(jié)果［15－16］.此外，從知識含量的角度，錢宇華等根據(jù)等價類中可區(qū)分對象的對數(shù)提出了組合熵的概念［17］，并設(shè)計了基于組合熵的啟發(fā)式屬性約簡算法.該算法可以有效地刪除冗余屬性，得到滿足目標(biāo)決策的條件組合熵不變的屬性子集.通過分析條件屬性與決策屬性之間的互信息，苗奪謙等將添加某個條件屬性引起的互信息的變化大小作為屬性重要量［18］，從信息的角度，提出了一種基于互信息的知識相對約簡的啟發(fā)式屬性約簡算法.

上述的啟發(fā)式約簡都致力于降低粗糙特征選擇過程中的計算耗時，提高計算效率，并取得了一定的研究成果.近年來，隨著信息技術(shù)及數(shù)據(jù)處理工具的迅速發(fā)展，大規(guī)模高維數(shù)據(jù)集的不斷涌現(xiàn)為粗糙特征選擇技術(shù)提出了更嚴(yán)峻的挑戰(zhàn).為此，劉少輝等通過深入分析粗糙集理論中不可區(qū)分關(guān)系的性質(zhì)，給出了一種新的快速計算正區(qū)域的方法;并在此基礎(chǔ)上設(shè)計了正區(qū)域的漸增式計算方法，進(jìn)而提出了一種高效的屬性約簡算法［19］.比較原有的啟發(fā)式約簡算法，該算法可找到給定決策表的一個完備約簡（Pawlak約簡）.徐章艷等通過將基數(shù)排序思想引入到等價劃分的求解中，提出了一種時間復(fù)雜度為 max（OC｜C｜｜u｜，O（｜c(diǎn)｜2｜u／c｜）λ）的快速屬性約簡算法，有效地降低了約簡求解的計算耗時［20］.劉勇等通過證明不協(xié)調(diào)對象與正區(qū)域的等價關(guān)系，提出了基于Hash的正區(qū)域的求解算法，并在此基礎(chǔ)上設(shè)計了基于二次Hash的屬性約簡算法［21］.較原有的約簡算法，上述幾種高效算法在時間和空間復(fù)雜度上都取得了了一定程度的優(yōu)化.

為進(jìn)一步有效提高啟發(fā)式屬性約簡的計算效率，錢宇華和梁吉業(yè)等［22］提出了一種基于正向近似的屬性約簡加速器，并將加速器應(yīng)用到啟發(fā)式屬性約簡算法（包括文獻(xiàn)［18-19］中的算法）中，設(shè)計了一系列的屬性約簡加速器算法.值得指出的是，這是一種通用的啟發(fā)式屬性約簡加速器.文獻(xiàn)［12，14-15，17］中的約簡算法或者是基于其他屬性重要度構(gòu)造的啟發(fā)式約簡算法均可以借鑒文獻(xiàn)［22］中的方法設(shè)計新的加速算法.加速算法不僅可以有效降低約簡求解過程中的計算耗時，而且可以找到與原算法相同的約簡結(jié)果.文獻(xiàn)［22］從理論分析和實(shí)驗(yàn)結(jié)果都有效證明了加速算法的可行性和高效性.此外，在文獻(xiàn)［23-24］中，錢宇華和梁吉業(yè)進(jìn)一步設(shè)計了含缺失數(shù)據(jù)決策表的屬性約簡算法加速器，有效提高了含缺失數(shù)據(jù)意義下求解屬性約簡的計算效率.

由于實(shí)際應(yīng)用中，真實(shí)的數(shù)據(jù)往往是不斷增加的，當(dāng)數(shù)據(jù)動態(tài)增加后，數(shù)據(jù)庫的更新會直接導(dǎo)致其信息結(jié)構(gòu)的變化.類似地，在基于動態(tài)數(shù)據(jù)表的屬性約簡求解中，數(shù)據(jù)表的不斷更新同樣會影響相應(yīng)的約簡結(jié)果.然而，重新執(zhí)行相關(guān)屬性約簡算法顯然是耗時的，為了高效的獲取新的約簡結(jié)果，一些學(xué)者提出了增量式的屬性約簡求解算法.胡峰和王國胤等設(shè)計了基于正區(qū)域的增量式屬性約簡算法，該算法主要通過分析新增對象后正區(qū)域的變化來更新原有的約簡結(jié)果［25］.此外，通過討論新增單個對象后條件類和決策類的變化，梁吉業(yè)和魏巍等分析了互補(bǔ)熵的增量機(jī)制［26］，并給出了一種基于條件互補(bǔ)熵的增量核求解算法，該算法可以得到信息觀下的增量屬性核.

1.2 基于區(qū)分矩陣的屬性約簡方法

區(qū)分矩陣是粗糙集理論中的核心概念之一.Skowron和Rauszer利用任意兩個對象之間的不同屬性描述數(shù)據(jù)集中蘊(yùn)涵的分類知識，提出了區(qū)分矩陣的概念［27］.并提出了基于區(qū)分矩陣來求解信息系統(tǒng)的完備約簡的方法.該方法可以得到給定信息系統(tǒng)的所有約簡，但是計算耗時過大，眾多學(xué)者發(fā)展了一系列的基于區(qū)分矩陣的屬性約簡算法.通?；趨^(qū)分矩陣的粗糙集特征選擇算法分為兩類：一類是通過構(gòu)造區(qū)分函數(shù)，并計算區(qū)分函數(shù)的蘊(yùn)涵來獲取約簡結(jié)果，這類算法可以得到給定信息系統(tǒng)的所有約簡，是一種完備算法;另一類是基于區(qū)分矩陣來構(gòu)造屬性的重要度，進(jìn)而設(shè)計相應(yīng)的屬性約簡算法.

Skowron提出的區(qū)分矩陣是基于信息系統(tǒng)構(gòu)造的，Hu和Cercone將區(qū)分矩陣的概念擴(kuò)展到?jīng)Q策表中［28］，定義了決策表的區(qū)分矩陣，也是目前應(yīng)用較為廣泛的一種區(qū)分矩陣.葉東毅等分析了利用Hu的區(qū)分矩陣求解不協(xié)調(diào)決策表的核屬性時會得不到正確的核，并改進(jìn)了Hu的區(qū)分矩陣［29］.但是該方法在定義區(qū)分矩陣中的矩陣元素時增加了計算復(fù)雜度.為此，楊明等提出了新的求解區(qū)分矩陣的方法，該方法的空間復(fù)雜度低于Hu和葉東毅的區(qū)分矩陣，且計算量小于葉東毅的區(qū)分矩陣，為粗糙集中核的求解提供了新的理論基礎(chǔ)［30］.針對上述幾種區(qū)分矩陣，王國胤等在文獻(xiàn)［31］中對不同的區(qū)分函數(shù)得到的核屬性之間的包含關(guān)系作了進(jìn)一步的討論.

針對利用區(qū)分矩陣來處理大規(guī)模數(shù)據(jù)耗時過大的缺陷，王玨等對Skowron定義的區(qū)分矩陣進(jìn)行簡化，使得每個屬性在區(qū)分矩陣中只出現(xiàn)一次，稱為Quasi－區(qū)分矩陣;并通過給定數(shù)據(jù)表中屬性的排序設(shè)計了基于Quasi-區(qū)分矩陣的屬性序算法［32］.該方法在面向用戶的數(shù)據(jù)挖掘中具有重要的意義［33］.胡峰、王國胤等提出了屬性序下的處理海量數(shù)據(jù)的快速屬性約簡算法［34］.該算法通過融入分治的思想，提出了分治策略的屬性約簡算法，極大地提高了給定屬性排序下的約簡求解的計算效率.

針對動態(tài)增加數(shù)據(jù)集，一些學(xué)者也提出了許多基于區(qū)分矩陣的增量式屬性約簡算法.楊明等提出一種基于改進(jìn)區(qū)分矩陣的核屬性增量式更新算法［35］，該算法在更新區(qū)分矩陣時僅需插入某一行和某一列，或刪除某一行并修改相應(yīng)的列，因而提高了屬性核的更新效率，該算法可以得到代數(shù)觀下決策表的增量屬性核.在此基礎(chǔ)上，楊明等提出了一種基于改進(jìn)區(qū)分矩陣的屬性約簡增量式更新算法，該算法可通過快速更新區(qū)分矩陣［36］，利用原有的屬性約簡有效地進(jìn)行屬性約簡的增量式更新，可提高屬性約簡的更新效率.

1.3 基于擴(kuò)展粗糙集模型的屬性約簡方法

實(shí)際應(yīng)用中，數(shù)據(jù)庫中的數(shù)據(jù)不只規(guī)模會不斷增大，所存儲數(shù)據(jù)也會越來越復(fù)雜.例如：數(shù)值型、名義型、模糊型、區(qū)間型、集值型、缺失數(shù)據(jù)、噪音數(shù)據(jù)、不完備數(shù)據(jù)等經(jīng)典粗糙集理論無法解決的問題.為此在近年來的研究中，出現(xiàn)了許多粗糙集的擴(kuò)展模型，如：鄰域粗糙集、模糊粗糙集、決策粗糙集、變精度粗糙集、優(yōu)勢關(guān)系粗糙集、基于覆蓋的粗糙集等各種拓展的粗糙集模型.

Pawlak的經(jīng)典粗糙集理論是采用等價關(guān)系將論域中的對象?；癁槿舾傻葍r類，作為描述論域中目標(biāo)概念的基本信息粒子.對給定的目標(biāo)概念，定義了兩個等價類的并集：下近似和上近似來逼近這個目標(biāo)概念［37］.由于Pawlak粗糙集要求由等價關(guān)系的基本信息粒子完全被包含或完全不被包含于待逼近的目標(biāo)概念，這導(dǎo)致該模型在應(yīng)用中不能有效地處理數(shù)據(jù)庫中的噪聲數(shù)據(jù).為了解決Pawlak粗糙集模型對數(shù)據(jù)噪聲敏感的問題，Ziarko提出了變精度粗糙集模型的定義［38］.變精度粗糙集重新定義了Pawlak粗糙集的上下近似，即，一個等價類中只要大部分樣本被包含在待逼近的粗糙集中，這個等價類就可以被劃入粗糙集的正域;反之，這個等價類就應(yīng)該被劃入粗糙集的負(fù)域.變精度粗糙集降低了噪聲數(shù)據(jù)對待逼近目標(biāo)概念的影響，從而方便了求解帶有噪聲數(shù)據(jù)的數(shù)據(jù)表的屬性約簡結(jié)果.變精度粗糙后來被進(jìn)一步拓展為Bayes粗糙集模型和概率粗糙集模型［39－41］，這兩種模型都是從概率論的視角出發(fā)來處理不確定性的.Yao和Zhao在文獻(xiàn)［42］中提出了決策理論粗糙集模型，該理論改變了以決策正域?yàn)樵u價機(jī)制的思想，而以多數(shù)決策原則產(chǎn)生的總的決策錯誤率為標(biāo)準(zhǔn)來定義屬性的評價標(biāo)準(zhǔn)［43］.基于決策理論粗糙集模型，Yao等設(shè)計了基于正區(qū)域的屬性約簡算法［44］.

由于Pawlak粗糙集、決策理論粗糙集模型以及變精度粗糙集等都只能處理符號數(shù)據(jù)，對于數(shù)值型數(shù)據(jù)只能先進(jìn)行離散化處理才能利用上述模型來求解屬性約簡.為此，一些學(xué)者將鄰域系統(tǒng)的概念引入粗糙集理論，提出了鄰域粗糙集模型［45－46］，鄰域系統(tǒng)的引入使得Pawlak粗糙集可以有效處理數(shù)值數(shù)據(jù).胡清華等在文獻(xiàn)［47-48］中重新定義并解釋了鄰域粗糙集模型，提出了基于鄰域?；痛植诒平臄?shù)值屬性約簡算法.王熙照等為解決粗糙集對模糊值屬性處理能力較弱的缺陷，提出了模糊不可區(qū)分關(guān)系的概念.并將約簡、核、相對約簡與相對核及規(guī)則等概念推廣到模糊環(huán)境下，提出了一種有效的模糊信息表的啟發(fā)式算法［49］.為有效利用粗糙集理論來處理混合數(shù)據(jù).胡清華等［50－51］等將Dubois和Prade［52］的模糊粗糙集引入到屬性約簡中，提出了模糊粗糙集背景下的相對正域、信息量等定義，并將其用于特征子集的評價，設(shè)計了面向混合數(shù)據(jù)的粗糙特征選擇算法.

此外，研究者還針對不同的問題提出了一些其它的粗糙集模型，例如優(yōu)勢關(guān)系粗糙集模型［53］、多粒度粗糙集模型［54］、基于覆蓋的粗糙集模型［55－56］等等，并基于這些粗糙集模型發(fā)展了相關(guān)的屬性約簡算法.這些研究成果對開拓粗糙集理論的應(yīng)用具有重要的意義.

粗糙集理論由于其在知識發(fā)現(xiàn)中的應(yīng)用而受到廣泛的關(guān)注，迅速發(fā)展為一種處理模糊、不確定信息的軟計算工具.粗糙特征選擇算法已被廣泛應(yīng)用于許多領(lǐng)域，作為粗糙集理論中的關(guān)鍵問題之一，下一節(jié)我們將列舉幾種代表性的應(yīng)用進(jìn)行評述.

2 粗糙特征選擇算法的應(yīng)用

基于粗糙集理論的特征選擇已廣泛應(yīng)用于許多領(lǐng)域，本節(jié)簡要介紹其在入侵檢測、醫(yī)療診斷、故障診斷和圖像處理幾個方面的一些研究成果.

2.1 入侵檢測

入侵檢測指對計算機(jī)或計算機(jī)網(wǎng)絡(luò)系統(tǒng)的攻擊行為進(jìn)行檢測，通常有誤用檢測和異常檢測兩類方法.在入侵檢測的過程中，利用基于粗糙集的特征選擇算法，對提取的網(wǎng)絡(luò)特征進(jìn)行選擇后，再通過支持向量機(jī)進(jìn)行分類訓(xùn)練，不僅可以減少計算量，而且克服了特征重要度衡量指標(biāo)制定過程中的主觀隨意性.蔡忠閩等［57］將粗糙集理論引入入侵檢測中的進(jìn)程正常模型的建模過程，利用基于粗糙集的特征選擇方法對訓(xùn)練數(shù)據(jù)集進(jìn)行簡化，然后基于特征子集生成預(yù)測規(guī)則集.將基于此模型的異常檢測算法用于實(shí)時檢測，對系統(tǒng)性能的影響很小，是一種高效低負(fù)荷的檢測方法.文獻(xiàn)［58］針對入侵?jǐn)?shù)據(jù)量大、特征數(shù)目繁多、連續(xù)性屬性多的特點(diǎn)，引入鄰域粗糙集約簡模型，構(gòu)造了一種基于鄰域粗糙集模型和粒子群優(yōu)化的特征選擇算法，仿真實(shí)驗(yàn)證明了該特征選擇方法的有效性.

2.2 醫(yī)療診斷

隨著醫(yī)療技術(shù)的進(jìn)步和各種醫(yī)療診斷設(shè)備的發(fā)展，醫(yī)療診斷中出現(xiàn)了空前增長的海量醫(yī)學(xué)數(shù)據(jù)，這些數(shù)據(jù)通常具有不完整、不確定、冗余等特點(diǎn).因此，利用先進(jìn)的計算機(jī)和信息處理技術(shù)等綜合開發(fā)可有效利用海量醫(yī)療數(shù)據(jù)信息，并實(shí)現(xiàn)診斷準(zhǔn)確率高的智能醫(yī)療診斷系統(tǒng)，已成為當(dāng)今醫(yī)療事業(yè)發(fā)展的一個至關(guān)重要的研究課題.而粗糙集理論的特點(diǎn)之一就是具有良好的數(shù)據(jù)處理能力，為此眾多學(xué)者將粗糙集理論應(yīng)用并拓展到處理各種類型的醫(yī)療數(shù)據(jù)中，并取得了成功的研究成果.Nakayama等將經(jīng)典粗糙集模型拓展到處理連續(xù)屬性取值的醫(yī)療數(shù)據(jù)（糖尿病人病變數(shù)據(jù)）的分析中［59］，建立了相應(yīng)的規(guī)則提取機(jī)制，并對實(shí)際數(shù)據(jù)進(jìn)行了有效的預(yù)測.此外，通過構(gòu)建相關(guān)的醫(yī)療知識庫，基于粗糙集理論進(jìn)行屬性約簡，從而降低診斷難度，提高診斷速度.Thangavel和Pethalakshmi基于模糊粗糙集提出一個從信息系統(tǒng)中進(jìn)行特征選擇的快速約簡算法［60］，并對大規(guī)模醫(yī)療數(shù)據(jù)庫的實(shí)際數(shù)據(jù)進(jìn)行測試，有效驗(yàn)證了該算法的有效性和可行性.

2.3 故障診斷

在診斷過程中，描述機(jī)器運(yùn)行的特征很多，有些特征是相關(guān)的，有些是獨(dú)立的.相關(guān)特征往往會產(chǎn)生冗余信息，同時會增加計算工作量，需要加以消除，基于粗糙集的特征選擇正好為去除這種冗余特征提供了有效的工具.Tay等將基于粗糙集的特征選擇應(yīng)用于柴油機(jī)的故障診斷中取得了較好的應(yīng)用效果［61］.Haiying等提出了基于粗糙集理論的變電站分層錯誤診斷新方法模型，也取得了較好的應(yīng)用［62］.

2.4 圖像處理

目前，粗糙集理論與計算機(jī)圖像處理的結(jié)合已經(jīng)成為計算機(jī)圖像處理的一個新的研究方向.利用粗糙集理論可對圖像特征進(jìn)行約簡，從而達(dá)到對圖像特征進(jìn)行降維的目的.Swiniarski將基于粗糙集的特征選擇應(yīng)用于人臉識別過程中［63］，有效降低了圖像特征的維數(shù)，且分類精度可以達(dá)到97.3%.胡靜等［64］提出了一種基于相容關(guān)系粗糙集進(jìn)行圖形圖像預(yù)檢索的新方法，仿真實(shí)驗(yàn)有效驗(yàn)證了該方法的可行性，有效提高了圖形圖像的檢索效率.文獻(xiàn)［65］介紹了粗糙集屬性約簡在處理乳房X線照片中的相關(guān)應(yīng)用.

從應(yīng)用領(lǐng)域來看，基于粗糙集的屬性約簡除了在上述入侵檢測、醫(yī)療診斷、故障診斷和圖像處理外，許多學(xué)者還成功應(yīng)用到文本分類［66］、網(wǎng)頁分類［67］、基因分析［68］及網(wǎng)絡(luò)支持系統(tǒng)［69］等領(lǐng)域，都取得了較好的效果.

3 總結(jié)與展望

本文從啟發(fā)式屬性約簡、基于區(qū)分矩陣的屬性約簡和拓展粗糙集模型的屬性約簡三個方面總結(jié)了目前粗糙特征選擇算法及其應(yīng)用的研究進(jìn)展.然而，隨著目前信息處理中數(shù)據(jù)的海量性、高維性、動態(tài)性與多源性越來越突顯，和經(jīng)典特征選擇算法一樣，粗糙特征選擇算法也遇到了前所未有的挑戰(zhàn).目前，主要應(yīng)關(guān)注以下幾個方面的研究.

（1）多源信息系統(tǒng)背景下的特征選擇方法;

（2）基于多粒度認(rèn)知策略設(shè)計海量數(shù)據(jù)的在線特征選擇算法;

（3）基于特征選擇的高維數(shù)據(jù)分析方法;

（4）動態(tài)數(shù)據(jù)的特征選擇與動態(tài)更新方法.

［1］Staff S.Challenges and Opportunities［J］.Science，2011，6018（331）：692-693.

［2］Liu H，Motoda H.Feature Selection for Knowledge Discovery and Data Mining［M］.Boston：Kluwer Academic Publishers，1998.

［3］Tsumoto S.Automated Discovery of Medical Expert System Rules from Clinical Databases Based on Rough Set［C］／／Proceedings of Second International Conference on Knowledge Discovery and Data Mining，USA，1996，32：63-72.

［4］Mjolsness E，Decoste D.Machine Learning for Science：State of the Art and Future Prospects［J］.Science，2001，293（14）：2051-2055.

［5］Pawlak Z.Rough Sets：Theoretical Aspects and Reasoning about Data［M］.Boston：Kluwer Academic Publishers，1991.

［6］劉清.Rough集及 Rough推理［M］.北京：科學(xué)出版社，2001：88-136.

［7］張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法［M］.北京：科學(xué)出版社，2001：128-209.

［8］張文修，仇國芳.基于粗糙集的不確定決策［M］.北京：清華大學(xué)出版社，2005：106-232.

［9］Lin T Y，Cercone N.Rough Sets and Data Mining：Analysis of Imprecise Data［M］.Boston：Kluwer Academic Publishers，1997.

［10］Kira K，Rendell L A.The Feature Selection Problem：Traditional Methods and a New Algorithm［C］／／Proceedings of 9th National Conference on Artificial Intelligence，1992：129-134.

［11］Kononenko I.Estimating Attributes：Analysis and Extension of Relief［C］／／Proceedings of European Conference on Machine Learning，1994：171-182.

［12］Hu X H，Cercone N.Learning in Relational Databases：A Rough Set Approach［J］.InternationalJournalofComputationalIntelligence，1995，11（2）：323-338.

［13］王國胤.決策表核屬性的計算方法［J］.計算機(jī)學(xué)報，2003，26（5）：611-615.

［14］王國胤，于洪，楊大春.基于條件信息熵的決策表約簡［J］.計算機(jī)學(xué)報，2002，25（7）：759-766.

［15］Liang J Y，Chin K S，Dang C Y，etal.A New Method For Measuring Uncertainty and Fuzziness in Rough Set Theory［J］.InternationalJournalofGeneralSystems，2002，31（4）：331-342.

［16］Liang J Y，Xu Z B.The Algorithm on Knowledge Reduction in Incomplete Information Systems［J］.InternationalJournalofUncertainty，F(xiàn)uzzinessandKnowledge-BasedSystems，2002，10（1）：95-103.

［17］Qian Y H，Liang J Y.Combination Entropy and Combination Granulation in Rough Set Theory［J］.InternationalJournalofUncertainty，F(xiàn)uzzinessandKnowledge-BasedSystems，2008，16（2）：179-193.

［18］苗奪謙，胡桂榮.知識約簡的一種啟發(fā)式算法［J］.計算機(jī)研究與發(fā)展，1999，36（6）：681-684.

［19］劉少輝，盛秋戩，吳斌，等.Rough集高效算法的研究［J］.計算機(jī)學(xué)報，2003，26（5）：524-529.

［20］徐章艷，劉作鵬，楊炳儒，等.一個復(fù)雜度為 max（O（｜C｜｜U｜），O（｜C｜2｜U／C｜））的快速屬性約簡算法［J］.計算機(jī)學(xué)報，2006，29（3）：391-399.

［21］劉勇，熊蓉，褚健.Hash快速屬性約簡算法［J］.計算機(jī)學(xué)報，2009，32（8）：1493-1499.

［22］Qian Y H，Liang J Y，Pedrycz W，etal.Positive Approximation：An Accelerator for Attribute Reduction in Rough Set Theory［J］.ArtificialIntelligences，2010，174（9-10）：597-618.

［23］Qian Y H，Liang J Y，Pedrycz W，etal.An Efficient Accelerator for Attribute Reduction from Incomplete Data in Rough Set Framework［J］.PatternRecognition，2011，44：1658-1670.

［24］錢宇華，梁吉業(yè)，王鋒.面向非完備決策表的正向近似特征選擇加速算法［J］.計算機(jī)學(xué)報，2011，34（3）：435-442.

［25］Hu F，Wang G Y，Huang H，etal.Incremental Attribute Reduction Based on Elementary Sets［C］／／Proceedings of the 10th International Conference on Rough Sets，F(xiàn)uzzy Sets，Data Mining and Granular Computing，Regina，Canada，2005：185-193.

［26］梁吉業(yè)，魏巍，錢宇華.一種基于條件熵的增量核求解方法［J］.系統(tǒng)工程理論與實(shí)踐，2008（4）：81-89.

［27］Skowron A，Rauszer C.The Discernibility Matrices and Functions in Information Tables［J］.IntelligentDecisionSupport：HandbookofApplicationsandAdvancesofRoughSetTheory，1992：331-362.

［28］Hu X H，Cercone N.Learning in Relational Databases：A Rough Set Approach［J］.InternationalJournalofComputationalIntelligence，1995，11（2）：323-338.

［29］葉東毅，陳昭炯.一個新的差別矩陣及其求核方法［J］.電子學(xué)報，2002，30（7）：1086-1088.

［30］楊明，孫志軍.改進(jìn)的差別矩陣及其求核方法［J］.復(fù)旦大學(xué)學(xué)報：自然版，2004，43（5）：865-868.

［31］Wang G Y.Attribute Core of Decision Table［C］／／Proceedings of the Third International Conference on Rough Sets and Current Trends in Computing（RSCTC2002），LNCS2475，USA，2002：213-217.

［32］Wang Jue，Wang Ju.Reduction Algorithms Based on Discernibility Matrix：The Ordered Attributes Method［J］.Journal ofComputerScienceandTechnology，2001，16（6）：489-504.

［33］Han S Q，Wang J.Reduct and Attribute Order［J］.JournalofComputerScienceandTechnology，2004，19（4）：429-449.

［34］胡峰，王國胤.屬性序下的快速約簡算法［J］.計算機(jī)學(xué)報，2007，30（8）：1429-1435.

［35］楊明.一種基于改進(jìn)差別矩陣的核增量式更新算法［J］.計算機(jī)學(xué)報，2006，29（3）：407-413.

［36］楊明.一種基于改進(jìn)差別矩陣的屬性約簡增量式更新算法［J］.計算機(jī)學(xué)報，2007，30（5）：815-822.

［37］YAO Y Y.Information Granulation and Rough Set Approximation［J］.InternationalJournalofIntelligentSystems，2001，16（1）：87-104.

［38］Ziarko W.Variable Precision Rough Sets Model［J］.JournalofComputerandSystemSciences，1993，40：39-59.

［39］Yao Y Y.Probabilistic Approaches to Rough Sets［J］.ExpertSystems，2003，20（5）：287-297.

［40］Slezak D.Rough Sets and Bayes Factor［C］／／Lecture Notes in Computer Science.Transactions on Rough Sets III，2005，3400：202-209.

［41］Slezak D，Ziarko W.The Investigation of the Bayesian Rough Set Model［J］.InternationalJournalofApproximateReasoning，2005，40：81-91.

［42］Yao Y Y，Wong S K M，Lingras P.A Decision-theoretic Rough Set Model［C］／／Proceedings of the Fifthe International Symposium on Methodologies for Intelligent Systems，Methodologies for Intelligent Systems 5，Knoxville Tennessee，1990：17-24.

［43］Yao Y Y，Wong S K M.A Decision Theoretic Framework for Approximating Concepts［J］.InternationalJournalof Man-MachineStudies，1992，37（6）：793-809.

［44］Yao Y Y，Zhao Y.Attribute Reduction in Decision-theoretic Rough Set Models ［J］.InformationSciences，2008，178：3356-3373.

［45］Lin T Y，Liu Q，Huang K J.Rough Sets Neighborhood Systems and Approximation［C］／／Proceedings of the Fifthe International Symposium on Methodologies for Intelligent Systems，Methodologies for Intelligent Systems 5，Knoxville Tennessee，1990：130-141.

［46］Lin T Y.Neighborhood Systems and Relational Database［C］／／Proceedings of the 1988 ACM 16th Annual Conference on Computer Science，1988：725-726.

［47］胡清華，于達(dá)仁，謝宗霞.基于鄰域粒化和粗糙逼近的數(shù)值屬性約簡［J］.軟件學(xué)報，2008，19（3）：640-649.

［48］Hu Q H，Yu D R，Liu J，etal.Neighborhood Rough Set Based Heterogeneous Feature Subset Selection［J］.Information Sciences，2008，178：3577-3594.

［49］王熙照，趙素云，王靜紅.基于Rough集理論的模糊值屬性信息表簡化方法［J］.計算機(jī)研究與發(fā)展，2004，41（11），1974-1981.

［50］Hu Q H，Yu D R，Xie Z X.Information-Preserving Hybrid Data Reduction Based on Fuzzy-Rough Techniques［J］.PatternRecognitionLetters，2006，27（5）：414-423.

［51］Hu Q H，Xie Z X，Yu D R.Hybrid Attribute Reduction Based on A Novel Fuzzy-Rough Model and Information Granulation［J］.PatternRecognition，2007，40：3509-3521.

［52］Dubois D，Prade H.Rough Fuzzy Sets and Fuzzy Rough Sets［J］.InternationalJournalofGeneralSystems，1990，17：191-208.

［53］Greco S，Matarazzo B，Slowinski R.Rough Approximation of A Preference Relation by Dominance Relations［J］.EuropeanJournalofOperationalResearch，1999，117（1）：63-83.

［54］Qian Y H，Liang J Y，Yao Y Y，etal.MGRS：A Multi-granulation Rough Set［J］.InformationSciences，2010，180：949-970.

［55］Zhu W，Wang F Y.On Three Types of Covering-based Rough Sets［J］.IEEETransactionsonKnowledgeandDataEngineering，2007，19（8）：1131-1144.

［56］Li T J.Generalized Fuzzy Rough Approximation Operators Based on Fuzzy Coverings［J］.InternationalJournalofApproximateReasoning，2008，43（3）：836-856.

［57］蔡忠閩，管曉宏，邵萍，等.基于粗糙集理論的入侵檢測新方法［J］.計算機(jī)學(xué)報，2003，26：361-366.

［58］陳仕濤，陳國龍，郭文忠，等.基于粒子群優(yōu)化和鄰域約簡的入侵檢測日志數(shù)據(jù)特征選擇［J］.計算機(jī)研究與發(fā)展，2010，47（7）：1261-1267.

［59］Nakayama H，Hattori Y，Ishii.Rule Extraction Based on Rough Set Theory and Its Application to Medical Data Analysis［C］／／Proceedings of IEEE SMC ’995’，1999：924-929.

［60］Thangavel K，Pethalakshmi A.Feature Selection for Medical Database using Rough System［J］.InternationalJournalon ArtificialIntelligenceandMachineLearning，2005，6（1）：11-17.

［61］Tay F E H，Shen L X.Fault Diagnosis Based on Rough Set Theory［J］.EngineeringApplicationsofArtificialIntelligence，2003，16：39-43.

［62］Dong H Y，Zhang Y B，Xue J Y.Hierarchical Fault Diagnosis for Substation Based on Rough Set［C］／／International Conference on Power System Technology，Kunming，China，2002，4：2318-2321.

［63］Swiniarski R W.Rough Sets Methods in Feature Reduction and Classification［J］.InternationalJournalonApplied MathematicsandComputerScience，2001，11（3）：565-582.

［64］胡靜，曹先彬，王煦法.基于相容粗糙集的圖形圖像信息預(yù)檢索［J］.計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2002，14（3），242-246.

［65］Thangavel K，Karnan M，Pethalakshmi A.Performance Analysis of Rough Reduct Algorithms in Mammogram［J］.InternationalJournalonGlobalVisionandImageProcessing，2005，5（8）：13-21.

［66］盧嬌麗，鄭家恒.基于粗糙集的文本分類方法研究［J］.中文信息學(xué)報，2005，19（2），66-70.

［67］Jensen R，Shen Q.Fuzzy Rough Attribute Reduction with Application to Web Categorization［J］.FuzzySetsandSystem，2004，141：649-485.

［68］Saeys Y，Inza I，Lamnaga P.A Review of Feature Selection Techniques in Bioinformatics［J］.Bioinformatics，2007，23：2507-2517.

［69］Yao J T，Herbert J P.Web-Based Support Systems with Rough Set Analysis［C］／／KRYSZKIEWICZ M.Proceedings of International Conference on Rough Sets and Intelligent Systems Paradigms 2007，Lecture Notes in Artificial Intelligence 4585.Berlin：Springer，2007：360-370.

Advanced in Feature Selection Based on Rough Sets

LIANG Ji-ye1，2，LI Chao-wei1，2，WEI Wei1，2
（1.KeyLaboratoryofMinistryofEducationforComputationIntelligence＆ChineseInformationProcessing，ShanxiUniversity，Taiyuan030006，China;2.SchoolofComputer＆InformationTechnology，ShanxiUniversity，Taiyuan030006，China）

Feature selection is an important issue in the field of machine learning.As a significant feature selection algorithm，attribute reduction has attracted much attention and been applied in many areas.This paper systematically reviews and analyzes the feature selection algorithms based on rough set theory，which are introduced from three aspects：heuristic attribute reduction，attribute reduction based on discernibility matrix and reduction for generalized rough set models.In addition，the paper concludes some common applications of rough feature selection algorithms，and gives a prospect for the further development.

feature selection;rough sets;attribute reduction;discernibility matrix;heuristic search

TP18

A

0253-2395（2012）02-0211-08＊

2012-03- 10;

2012-03-19

國家自然科學(xué)基金（71031006）;國家973計劃前期研究專項(xiàng)課題（2011CB311805）

梁吉業(yè)（1962－），男，山西晉城人，博士，教授，研究領(lǐng)域：計算智能、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等.E-mail：ljy＠sxu.edu.cn