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

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

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

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

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

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

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

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

0 引言

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

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

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

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

1 粗糙特征選擇算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 入侵檢測(cè)

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

2.2 醫(yī)療診斷

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

2.3 故障診斷

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

2.4 圖像處理

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

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

3 總結(jié)與展望

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

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

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

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

（4）動(dòng)態(tài)數(shù)據(jù)的特征選擇與動(dòng)態(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］張文修，仇國(guó)芳.基于粗糙集的不確定決策［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］王國(guó)胤.決策表核屬性的計(jì)算方法［J］.計(jì)算機(jī)學(xué)報(bào)，2003，26（5）：611-615.

［14］王國(guó)胤，于洪，楊大春.基于條件信息熵的決策表約簡(jiǎn)［J］.計(jì)算機(jī)學(xué)報(bào)，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］苗奪謙，胡桂榮.知識(shí)約簡(jiǎn)的一種啟發(fā)式算法［J］.計(jì)算機(jī)研究與發(fā)展，1999，36（6）：681-684.

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

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

［21］劉勇，熊蓉，褚健.Hash快速屬性約簡(jiǎn)算法［J］.計(jì)算機(jī)學(xué)報(bào)，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］錢(qián)宇華，梁吉業(yè)，王鋒.面向非完備決策表的正向近似特征選擇加速算法［J］.計(jì)算機(jī)學(xué)報(bào)，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è)，魏巍，錢(qián)宇華.一種基于條件熵的增量核求解方法［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］葉東毅，陳昭炯.一個(gè)新的差別矩陣及其求核方法［J］.電子學(xué)報(bào)，2002，30（7）：1086-1088.

［30］楊明，孫志軍.改進(jìn)的差別矩陣及其求核方法［J］.復(fù)旦大學(xué)學(xué)報(bào)：自然版，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］胡峰，王國(guó)胤.屬性序下的快速約簡(jiǎn)算法［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30（8）：1429-1435.

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

［36］楊明.一種基于改進(jìn)差別矩陣的屬性約簡(jiǎn)增量式更新算法［J］.計(jì)算機(jī)學(xué)報(bào)，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ù)值屬性約簡(jiǎn)［J］.軟件學(xué)報(bào)，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集理論的模糊值屬性信息表簡(jiǎn)化方法［J］.計(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］蔡忠閩，管曉宏，邵萍，等.基于粗糙集理論的入侵檢測(cè)新方法［J］.計(jì)算機(jī)學(xué)報(bào)，2003，26：361-366.

［58］陳仕濤，陳國(guó)龍，郭文忠，等.基于粒子群優(yōu)化和鄰域約簡(jiǎn)的入侵檢測(cè)日志數(shù)據(jù)特征選擇［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ì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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］盧嬌麗，鄭家恒.基于粗糙集的文本分類(lèi)方法研究［J］.中文信息學(xué)報(bào)，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

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

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