鄔陽(yáng)陽(yáng)，郭文強(qiáng)，湯建國(guó)，任 艷

（新疆財(cái)經(jīng)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，新疆烏魯木齊830012）

經(jīng)典粗糙集（Pawlak粗糙集）最初由波蘭學(xué)者提出，是處理不確定性信息的強(qiáng)有力工具[1-4]，但建立在嚴(yán)格等價(jià)關(guān)系之上的Pawlak 粗糙集理論僅適用于處理離散型數(shù)據(jù).為了有效處理實(shí)際應(yīng)用中更為復(fù)雜的數(shù)據(jù)（多媒體數(shù)據(jù)、基因數(shù)據(jù)、金融數(shù)據(jù)等），一些學(xué)者將Pawlak 粗糙集模型進(jìn)行拓展和延伸，提出許多新粗糙集模型，如：模糊粗糙集[5-6]、覆蓋粗糙集[7-8]、鄰域粗糙集[9-11]、決策粗糙集[12]、變精度粗糙集[13]、多粒度粗糙集[14]等.這些拓展粗糙集模型大大拓寬了粗糙集理論的適用范圍，在諸如信息科學(xué)[15-17]、管理學(xué)[18-20]、金融[21-22]、醫(yī)學(xué)[23-25]等領(lǐng)域得以廣泛應(yīng)用，其屬性約簡(jiǎn)算法作為數(shù)據(jù)預(yù)處理的有效方法也受到國(guó)內(nèi)外學(xué)術(shù)界的廣泛關(guān)注.

屬性約簡(jiǎn)也稱特征選擇，指的是從原始屬性集合中選出具有代表性的屬性子集，是粗糙集理論研究的重點(diǎn)內(nèi)容之一.特征選擇可以在不影響最終決策質(zhì)量的前提下，有效去除數(shù)據(jù)的噪聲和冗余特征，提高學(xué)習(xí)效率[26]. 目前，各國(guó)學(xué)者經(jīng)過(guò)不斷努力，基于概念格、決策樹、隨機(jī)森林、支持向量機(jī)、粗糙集等理論設(shè)計(jì)出各類特征選擇算法. 其中，基于粗糙集理論的特征選擇算法不僅可以求解最優(yōu)或次優(yōu)約簡(jiǎn)結(jié)果，而且能夠在所選特征的基礎(chǔ)之上構(gòu)造出較高質(zhì)量的分類器[27]，在模糊、不一致信息分析處理中表現(xiàn)出較強(qiáng)的數(shù)據(jù)處理能力. 隨著人工智能、模式識(shí)別、數(shù)據(jù)挖掘等技術(shù)的迅速崛起，基于粗糙集的屬性約簡(jiǎn)算法在數(shù)據(jù)處理中發(fā)揮了重要作用.

現(xiàn)階段，粗糙集屬性約簡(jiǎn)得以廣泛研究，研究人員設(shè)計(jì)出很多高效的屬性約簡(jiǎn)算法，其約簡(jiǎn)理論也逐步完善，但約簡(jiǎn)算法在運(yùn)行效率、精確度、復(fù)雜數(shù)據(jù)處理等多方面還存在一些不足之處，有待于進(jìn)一步研究.文獻(xiàn)[28-30]對(duì)Pawlak粗糙集屬性約簡(jiǎn)研究成果作了系統(tǒng)總結(jié)和分析，為研究粗糙集屬性約簡(jiǎn)算法提供了有益借鑒.但作為粗糙集約簡(jiǎn)理論重要組成部分的拓展粗糙集模型屬性約簡(jiǎn)算法在算法設(shè)計(jì)方面也取得了豐碩的研究成果，卻尚未有文獻(xiàn)對(duì)其進(jìn)行系統(tǒng)梳理和分析. 針對(duì)上述問(wèn)題，本文選取屬性約簡(jiǎn)算法研究較為充分的幾類拓展粗糙集模型，依據(jù)一定標(biāo)準(zhǔn)對(duì)各類模型的屬性約簡(jiǎn)算法進(jìn)行分類，并在此基礎(chǔ)上按照某個(gè)相對(duì)清晰的研究主線對(duì)一些經(jīng)典算法進(jìn)行詳細(xì)分析.

1 屬性約簡(jiǎn)算法

粗糙集屬性約簡(jiǎn)算法大致可以分為兩類：一類是基于代數(shù)觀的屬性約簡(jiǎn)算法，其典型代表是基于正域的屬性約簡(jiǎn)算法[31]和基于辨識(shí)矩陣的屬性約簡(jiǎn)算法[32]；另一類是基于信息論的屬性約簡(jiǎn)算法[33].粗糙集的研究者將這些經(jīng)典屬性約簡(jiǎn)方法或約簡(jiǎn)思想融入到拓展粗糙集屬性約簡(jiǎn)算法的設(shè)計(jì)中，提出了一系列高效實(shí)用的屬性約簡(jiǎn)算法.

1.1 模糊粗糙集屬性約簡(jiǎn)算法

為了解決連續(xù)型和混合型數(shù)據(jù)離散化過(guò)程中信息損失的問(wèn)題，Dubois和Prade利用模糊集理論和粗糙集理論在數(shù)據(jù)處理上的互補(bǔ)性提出了模糊粗糙集模型[5-6].模糊粗糙集在一定程度上拓寬了Pawlak粗糙集的應(yīng)用范圍，對(duì)復(fù)雜數(shù)據(jù)的處理有著重要意義.當(dāng)前研究較為充分的模糊粗糙集屬性約簡(jiǎn)算法主要有基于辨識(shí)矩陣、屬性依賴度和信息觀三類.

1.1.1 基于辨識(shí)矩陣的屬性約簡(jiǎn)算法

基于辨識(shí)矩陣的屬性約簡(jiǎn)算法是一類經(jīng)典約簡(jiǎn)算法.盡管此類約簡(jiǎn)算法的時(shí)間復(fù)雜度和空間復(fù)雜度都比較高，但有著嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)基礎(chǔ). 其主要設(shè)計(jì)思路是結(jié)合一些數(shù)理理論或智能算法從算法運(yùn)行效率方面對(duì)經(jīng)典約簡(jiǎn)算法進(jìn)行優(yōu)化或改進(jìn).基于辨識(shí)矩陣的模糊粗糙集屬性約簡(jiǎn)算法首先由Tsang 等人[34]和Jensen 等人[35]提出，但此后的研究者主要對(duì)Jensen 等人提出的模糊粗糙集快速屬性約簡(jiǎn)算法（FRQR）進(jìn)行了改進(jìn). Jensen 等人提出模糊辨識(shí)矩陣定義，并用其設(shè)計(jì)出計(jì)算屬性約簡(jiǎn)的啟發(fā)式算法，時(shí)間復(fù)雜度為O( ||C2||U2)，但該算法在計(jì)算依賴度時(shí)會(huì)消耗大量時(shí)間，不適用于處理大規(guī)模數(shù)據(jù).Anaraki等人[36]指出在多個(gè)屬性子集的屬性依賴度相等的情況下，用FRQR算法求得的最終約簡(jiǎn)結(jié)果未必是最優(yōu)約簡(jiǎn)，于是將模糊粗糙依賴度與基于關(guān)聯(lián)關(guān)系的啟發(fā)式相結(jié)合，在FRQR算法的基礎(chǔ)之上提出兩類屬性約簡(jiǎn)算法，但算法的最大時(shí)間復(fù)雜度仍不低于O( ||C2||U2).陳俞等人[37]則把隨機(jī)抽樣理論融入到模糊粗糙集約簡(jiǎn)算法的設(shè)計(jì)中，提出統(tǒng)計(jì)屬性約簡(jiǎn)的概念，利用抽樣方法計(jì)算估計(jì)值，并將估計(jì)值排序，設(shè)計(jì)出適用于大規(guī)模數(shù)據(jù)的序約簡(jiǎn)算法.相對(duì)于傳統(tǒng)屬性約簡(jiǎn)方法，該算法減少了時(shí)間和空間消耗，但約簡(jiǎn)精度有時(shí)會(huì)降低，時(shí)間復(fù)雜度為O( max(2k |C|2|U |), |C|2|S|2). 另外，Chen 等人[38]發(fā)現(xiàn)通過(guò)計(jì)算辨識(shí)矩陣中所有極小元素即可得到最優(yōu)約簡(jiǎn)，而不必計(jì)算辨識(shí)矩陣中所有元素，并基于此改進(jìn)了屬性約簡(jiǎn)算法，運(yùn)行效率得到進(jìn)一步提高，時(shí)間復(fù)雜度降為O( ||C ||U2).Chen等人[39]指出上述屬性約簡(jiǎn)算法多是從全局角度出發(fā)設(shè)計(jì)的，并不能刻畫關(guān)鍵條件屬性對(duì)特殊決策類的影響，所以從局部?jī)?yōu)化的角度出發(fā)，基于辨識(shí)矩陣設(shè)計(jì)出屬性約簡(jiǎn)算法.該算法在克服全局約簡(jiǎn)算法缺點(diǎn)的同時(shí)也進(jìn)一步提高了算法的運(yùn)行效率，其時(shí)間復(fù)雜度為O( ||C ||U2).

1.1.2 基于屬性依賴度的屬性約簡(jiǎn)算法

基于屬性依賴度的屬性約簡(jiǎn)算法并非結(jié)構(gòu)化方法，在某些特殊情況下無(wú)法得到真正約簡(jiǎn). 但這種方法約簡(jiǎn)效率較高，是粗糙集屬性約簡(jiǎn)算法的重要類型之一. 在模糊粗糙集理論中，這類約簡(jiǎn)算法主要是針對(duì)Shen等人[40]提出的算法在解空間搜索過(guò)程中時(shí)間復(fù)雜度過(guò)高的問(wèn)題，運(yùn)用不同方法對(duì)原算法進(jìn)行優(yōu)化，將時(shí)間復(fù)雜度從指數(shù)級(jí)降到平方級(jí).Shen 等人將經(jīng)典粗糙集中依賴度的定義擴(kuò)展到模糊粗糙集中，給出模糊粗糙集的依賴度定義，并提出基于依賴度的模糊粗糙集屬性約簡(jiǎn)算法（FRSAR），時(shí)間復(fù)雜度為O( ( |U|2+ |U |) 2 )，但該算法搜索整個(gè)解空間的時(shí)間復(fù)雜度為O(2||U). Bhatt 等人[41]借助緊計(jì)算域重新定義模糊粗糙集，提出基于模糊粗糙集緊計(jì)算域的屬性約簡(jiǎn)算法，將搜索解空間的時(shí)間復(fù)雜度降為O( ||U2)，但改進(jìn)后的算法并不能處理?xiàng)l件屬性和決策屬性均為連續(xù)型數(shù)值類型的決策表. 印勇等人[42]利用三角隸屬函數(shù)模糊化決策表的連續(xù)屬性，并從全部條件屬性出發(fā)，利用依賴度去除不會(huì)影響決策表信息量的屬性，達(dá)到了降低搜索解空間時(shí)間消耗的目的，算法的時(shí)間復(fù)雜度為O( ||U2). 周志平等人[43]指出文獻(xiàn)[40]中定義的模糊算子并不嚴(yán)格，所以重新給出模糊近似算子的定義，并重新界定了模糊粗糙集相對(duì)約簡(jiǎn)的概念，在此基礎(chǔ)上設(shè)計(jì)了模糊粗糙集屬性約簡(jiǎn)算法.該算法提高了分類精度，為處理更為復(fù)雜的數(shù)據(jù)提供了新方法，搜索解空間的時(shí)間復(fù)雜度為O( ||U2). 王世強(qiáng)等人[44]對(duì)模糊粗糙集屬性依賴度概念進(jìn)行擴(kuò)展，重新定義候選屬性集和冗余屬性集，并兩次使用屬性間依賴度這一概念設(shè)計(jì)出屬性約簡(jiǎn)算法，有效減少了冗余屬性，屬性集依賴計(jì)算的復(fù)雜度從指數(shù)級(jí)下降為平方級(jí)，即從O(2||U)降低到O( ||U2).

1.1.3 基于信息觀的屬性約簡(jiǎn)算法

粗糙集在信息觀下的表示與其代數(shù)表示是完全等價(jià)的. 另外，基于信息觀表示的屬性約簡(jiǎn)算法更具直觀性，因此一部分研究者從信息觀角度出發(fā)，設(shè)計(jì)了模糊粗糙集屬性約簡(jiǎn)算法，主要研究思路是從多種信息熵出發(fā)，或?qū)υ屑s簡(jiǎn)算法進(jìn)行優(yōu)化，或在信息觀下對(duì)模糊粗糙集屬性約簡(jiǎn)重新進(jìn)行定義.Hu等人[45]引入信息測(cè)度來(lái)描述模糊等價(jià)關(guān)系，重新對(duì)混合數(shù)據(jù)的屬性依賴度、約簡(jiǎn)以及相對(duì)約簡(jiǎn)進(jìn)行定義，設(shè)計(jì)出處理混合數(shù)據(jù)的啟發(fā)式屬性約簡(jiǎn)算法.該算法首次從信息論角度研究模糊粗糙集屬性約簡(jiǎn)問(wèn)題，具有重要的理論意義，但文中使用的條件熵并不適用于廣義模糊決策系統(tǒng)[46].另外，文獻(xiàn)中定義的條件熵在一般模糊決策系統(tǒng)中并不滿足單調(diào)性[47].為解決上述兩個(gè)問(wèn)題，Zhang等人[47]重新給出條件信息熵概念，并設(shè)計(jì)了相應(yīng)的屬性約簡(jiǎn)算法. 徐菲菲等人[48]把Pawlak 粗糙集中的條件熵、知識(shí)熵推廣到模糊粗糙集中，從信息量角度度量模糊決策表的屬性重要度，提出約簡(jiǎn)模糊決策表的啟發(fā)式算法. 該算法在多數(shù)情況下能夠得到最小約簡(jiǎn). 徐菲菲等人[49]指出文獻(xiàn)[48]中基于互信息的屬性約簡(jiǎn)算法在數(shù)據(jù)屬性較多時(shí)計(jì)算復(fù)雜度過(guò)高，所以在屬性約簡(jiǎn)算法設(shè)計(jì)過(guò)程中采用最大相關(guān)性的評(píng)價(jià)標(biāo)準(zhǔn)和刪除依賴度較高屬性的方法設(shè)計(jì)出約簡(jiǎn)效率較高的算法. 潘瑞林等人[50]將α 信息熵概念引入到模糊粗糙集屬性約簡(jiǎn)理論中，結(jié)合模糊相似關(guān)系重新定義了屬性重要度，并以此作為啟發(fā)信息設(shè)計(jì)出較為高效的屬性約簡(jiǎn)算法，但文獻(xiàn)中并沒(méi)有對(duì)參數(shù)的取值原則進(jìn)行詳細(xì)探討.

此外，一些研究者將多重聚類[51]、散度測(cè)度[52]、距離測(cè)度[53]、極大辨識(shí)對(duì)[54]、并行計(jì)算[55]、增量計(jì)算[56-57]等多種方法引入到模糊粗糙集屬性約簡(jiǎn)理論中，從多個(gè)角度設(shè)計(jì)了模糊粗糙集屬性約簡(jiǎn)算法.

1.2 覆蓋粗糙集屬性約簡(jiǎn)算法

Zakowski[7]于1983 年將Pawlak 粗糙集中的等價(jià)關(guān)系替換為覆蓋關(guān)系，首先開啟了覆蓋粗糙集理論的研究工作. 同Pawlak 粗糙集模型相比，覆蓋粗糙集模型較為復(fù)雜，其約簡(jiǎn)理論由兩部分組成：第一部分是覆蓋元約簡(jiǎn)，通過(guò)去除論域中代表知識(shí)粒的冗余元找到上、下近似集不變的極小覆蓋；第二部分是覆蓋族約簡(jiǎn)（屬性約簡(jiǎn)），即刪除集族中冗余覆蓋.覆蓋族約簡(jiǎn)是本文討論的重點(diǎn). 目前，研究較為廣泛的覆蓋粗糙集屬性約簡(jiǎn)算法主要包括了基于辨識(shí)矩陣和信息觀的兩類.

1.2.1 基于辨識(shí)矩陣的屬性約簡(jiǎn)算法

覆蓋粗糙集模型類型較多，又有新模型不斷被提出，導(dǎo)致一部分屬性約簡(jiǎn)算法并不具有普遍性.基于辨識(shí)矩陣的屬性約簡(jiǎn)算法在運(yùn)行過(guò)程中需要消耗大量時(shí)間和空間，研究者多以降低時(shí)間復(fù)雜度為研究主線，對(duì)基于辨識(shí)矩陣的約簡(jiǎn)算法進(jìn)行優(yōu)化.Chen 等人[58]定義協(xié)調(diào)和不協(xié)調(diào)覆蓋粗糙集決策信息系統(tǒng)，給出屬性約簡(jiǎn)的充分必要條件，并將辨識(shí)矩陣應(yīng)用到覆蓋粗糙集約簡(jiǎn)算法設(shè)計(jì)過(guò)程中，算法的時(shí)間復(fù)雜度為O( ||U2× ||Δ2).Wang等人[59]定義了覆蓋決策系統(tǒng)以及覆蓋決策系統(tǒng)的相對(duì)約簡(jiǎn)，并對(duì)辨識(shí)矩陣進(jìn)行改進(jìn)，在此基礎(chǔ)上提出覆蓋粗糙集屬性約簡(jiǎn)算法，時(shí)間復(fù)雜度小于O( ||U2× ||Δ2)，但該算法在約簡(jiǎn)過(guò)程中需要計(jì)算所有元素，增加了計(jì)算量，計(jì)算效率有待于進(jìn)一步提高.Li等人[60]研究發(fā)現(xiàn)文獻(xiàn)[58]中的算法在約簡(jiǎn)過(guò)程中并不需要計(jì)算所有元素，而只需求解極小元素就能得到?jīng)Q策信息系統(tǒng)的全部約簡(jiǎn). 由此，給出求解極小元素的算法以及求全部覆蓋的約簡(jiǎn)算法.該約簡(jiǎn)算法可以節(jié)約大量存儲(chǔ)空間和運(yùn)行時(shí)間，計(jì)算復(fù)雜度度降為O( ||U2× ||Δ ). 類似于文獻(xiàn)[60]中的算法優(yōu)化方法，Dong 等人[61]指出文獻(xiàn)[59]中的算法在約簡(jiǎn)時(shí)僅需計(jì)算極小元素就可以求解所有約簡(jiǎn)屬性，并設(shè)計(jì)出覆蓋粗糙集屬性約簡(jiǎn)算法，該算法最大時(shí)間復(fù)雜度為O( ||U2× ||Δ ). Wang 等人[62]利用覆蓋粗糙集相關(guān)性質(zhì)設(shè)計(jì)的屬性約簡(jiǎn)算法減少了樣本鄰域的比較次數(shù)，達(dá)到了對(duì)文獻(xiàn)[58]所定義的協(xié)調(diào)覆蓋系統(tǒng)辨識(shí)矩陣與非協(xié)調(diào)覆蓋系統(tǒng)辨識(shí)矩陣簡(jiǎn)化的目的，約簡(jiǎn)算法的時(shí)間復(fù)雜度為O( ||U2× ||Δ ). Tan 等人[63]引入新的矩陣和矩陣運(yùn)算，借助新矩陣方法能夠有效求解覆蓋信息系統(tǒng)的最大和最小描述，降低了求解所有屬性約簡(jiǎn)或最優(yōu)屬性約簡(jiǎn)的復(fù)雜度，算法 時(shí) 間 復(fù) 雜 度 為 O(U|2|C |+|U|2( |Δ |-i) ),與文獻(xiàn)[58]中的約簡(jiǎn)算法相比，該算法的約簡(jiǎn)效率有了進(jìn)一步提高.

1.2.2 基于信息觀的屬性約簡(jiǎn)算法

另一類重要的覆蓋粗糙集屬性約簡(jiǎn)算法是基于信息觀點(diǎn)的約簡(jiǎn)算法.此類算法并沒(méi)有明顯研究主線，一部分算法是對(duì)Li等人[64]提出的算法進(jìn)行改進(jìn)，還有部分算法是通過(guò)引入其他理論進(jìn)一步完善信息觀下覆蓋粗糙集的屬性約簡(jiǎn)理論. Li等人通過(guò)定義信息熵、條件熵設(shè)計(jì)了針對(duì)協(xié)調(diào)決策表的屬性約簡(jiǎn)算法，并基于限制條件熵提出不協(xié)調(diào)決策表的約簡(jiǎn)算法，最后還給出既適用于協(xié)調(diào)決策表也適用于不協(xié)調(diào)決策表的約簡(jiǎn)算法.這些算法都是Pawlak粗糙集約簡(jiǎn)理論在信息觀下的自然推廣. 覃麗珍等人[65]指出文獻(xiàn)[64]中定義的三類信息熵（限制互信息、限制信息熵和限制條件信息熵）并不具備嚴(yán)格的非負(fù)性或單調(diào)性，因此重新給出三類信息熵的定義，并用其度量條件覆蓋的重要性，設(shè)計(jì)了不協(xié)調(diào)覆蓋決策系統(tǒng)的屬性約簡(jiǎn)算法.該算法可以避免出現(xiàn)原算法無(wú)法度量條件覆蓋重要度的現(xiàn)象. 夏秀云等人[66]引入覆蓋交集方法，從條件信息熵角度探討了協(xié)調(diào)決策表的相關(guān)性質(zhì)，給出覆蓋粗糙集屬性約簡(jiǎn)的充分必要條件，并在信息觀下提出約簡(jiǎn)協(xié)調(diào)覆蓋粗糙集冗余或不必要屬性的方法. 張燕蘭等人[67]從信息量的角度提出不必要覆蓋粗糙集、必要覆蓋粗糙集和核心三個(gè)概念，并對(duì)覆蓋協(xié)調(diào)集的判定定理和覆蓋的重要度進(jìn)行定義，從而設(shè)計(jì)出基于信息觀的屬性約簡(jiǎn)算法. 覃麗珍等人[68]將信息量這一概念引入覆蓋粗糙集，在此基礎(chǔ)上給出覆蓋協(xié)調(diào)集和覆蓋約簡(jiǎn)的判定定理，并用信息量度量覆蓋的重要性，最后結(jié)合辨識(shí)矩陣方法設(shè)計(jì)出完備的覆蓋約簡(jiǎn)算法.該算法在搜索過(guò)程中可以逐步刪除冗余或不重要的覆蓋，提高了算法的約簡(jiǎn)效率.

另外，一些學(xué)者結(jié)合正態(tài)分布測(cè)量誤差[69]、相關(guān)族[70]、網(wǎng)絡(luò)拓?fù)鋄71]、超圖模型[72]、增量學(xué)習(xí)[73-74]等理論提出了其他類型的屬性約簡(jiǎn)算法.

1.3 鄰域粗糙集屬性約簡(jiǎn)算法

2008 年，胡清華等人[11]在Lin[9]、Yao[10]所提理論的基礎(chǔ)上，將鄰域模型和粗糙集模型相結(jié)合，對(duì)鄰域粗糙集模型進(jìn)行詳細(xì)闡述，正式提出鄰域粗糙集模型.鄰域粗糙集用鄰域關(guān)系和距離替代Pawlak粗糙集中較為嚴(yán)格的等價(jià)關(guān)系，彌補(bǔ)了Pawlak 粗糙集由于數(shù)據(jù)離散化導(dǎo)致信息損失的缺陷.部分學(xué)者對(duì)鄰域粗糙集屬性約簡(jiǎn)進(jìn)行了研究，現(xiàn)有鄰域粗糙集屬性約簡(jiǎn)算法的設(shè)計(jì)思路基本上是改進(jìn)或優(yōu)化胡清華提出的兩類屬性約簡(jiǎn)算法.

1.3.1 基于屬性重要度的屬性約簡(jiǎn)算法

第一類屬性約簡(jiǎn)算法主要是從算法的時(shí)間復(fù)雜度這一方面對(duì)胡清華等人[11]提出的基于正域的屬性約簡(jiǎn)算法進(jìn)行改進(jìn).胡清華等人針對(duì)鄰域粗糙集模型提出鄰域粗糙集屬性約簡(jiǎn)算法.該算法以屬性重要度為選擇條件，約簡(jiǎn)過(guò)程中需進(jìn)行大量重復(fù)的鄰域計(jì)算，時(shí)間復(fù)雜度為O( ||C ||U2)，約簡(jiǎn)效率并不理想.接著，胡清華等人[75]又設(shè)計(jì)出前向搜索鄰域粗糙集屬性約簡(jiǎn)快速算法（FARNeMF）. 此算法充分利用鄰域粗糙集固有的數(shù)學(xué)性質(zhì)，即設(shè)計(jì)算法時(shí)僅考慮負(fù)域中的樣本，在一定程度上提高了計(jì)算速度，但約簡(jiǎn)過(guò)程中負(fù)域樣本的鄰域劃分操作仍需消耗大量時(shí)間，導(dǎo)致算法時(shí)間復(fù)雜度并未降低，仍為O( ||C ||U2).為提高屬性約簡(jiǎn)算法的效率，李三樂(lè)[76]對(duì)FARNeMF 算法進(jìn)行了改進(jìn)，新算法將計(jì)算相對(duì)核作為起點(diǎn)，并在屬性約簡(jiǎn)過(guò)程中運(yùn)用刪除法，減少了屬性約簡(jiǎn)的時(shí)間消耗.該算法不僅能夠求得最小屬性約簡(jiǎn)，效率也得到一定程度的提高，最大時(shí)間復(fù)雜度為O( ||C ||U2).為進(jìn)一步降低算法的時(shí)間復(fù)雜度，Liu 等人[77]給出一種快速屬性約簡(jiǎn)算法，該算法在進(jìn)行約簡(jiǎn)操作前首先對(duì)樣本進(jìn)行劃分，并在計(jì)算某個(gè)樣本的鄰域時(shí)省去與不相鄰樣本進(jìn)行比較這一步驟，進(jìn)一步減少了計(jì)算量，計(jì)算復(fù)雜度下降為O( ||C2||U ).另外，還有學(xué)者從約簡(jiǎn)精確度、鄰域半徑和算法適用范圍等方面對(duì)基于正域的屬性約簡(jiǎn)算法進(jìn)行改進(jìn). 徐波等人[78]指出文獻(xiàn)[11]中算法的鄰域半徑是固定不變的，這會(huì)使得約簡(jiǎn)結(jié)果的精確性和適應(yīng)性受到影響. 于是，在信息權(quán)重的基礎(chǔ)上提出加權(quán)依賴度，設(shè)計(jì)出基于加權(quán)依賴度的屬性約簡(jiǎn)算法，約簡(jiǎn)結(jié)果的精確度得到了提高，但時(shí)間復(fù)雜度增大到O2 |C |-k)(k+1) |U|2)，其中k 為約簡(jiǎn)屬性子集的屬性數(shù)量. 段潔等人[79]將鄰域粗糙集同多標(biāo)記學(xué)習(xí)相結(jié)合，重新定義依賴度和下近似，并在FARNeMF算法的基礎(chǔ)上設(shè)計(jì)出適用于多標(biāo)記學(xué)習(xí)任務(wù)的前向貪心算法，時(shí)間復(fù)雜度為O(N2Lnlogn)（其中n為決策表中樣本個(gè)數(shù)，N表示標(biāo)記個(gè)數(shù)，L為特征屬性個(gè)數(shù)）.

1.3.2 基于信息觀的屬性約簡(jiǎn)算法

第二類屬性約簡(jiǎn)算法主要是在Hu 等人[80]提出的屬性約簡(jiǎn)算法的基礎(chǔ)上，從約簡(jiǎn)效率、約簡(jiǎn)精度或算法的適用范圍等一個(gè)或幾個(gè)方面進(jìn)行優(yōu)化或改進(jìn). Hu等人定義了鄰域信息熵，引入鄰域互信息的概念，并以鄰域互信息為啟發(fā)信息設(shè)計(jì)出屬性約簡(jiǎn)算法.該算法從Pawlak粗糙集屬性約簡(jiǎn)算法中獲得啟發(fā)，將信息熵這一概念引入到鄰域粗糙集約簡(jiǎn)理論中，并對(duì)鄰域互信息的性質(zhì)進(jìn)行詳細(xì)探討，為在信息觀下研究鄰域粗糙集屬性約簡(jiǎn)理論做了開創(chuàng)性工作. 李少年等人[81]從鄰域區(qū)間內(nèi)決策屬性值分布出發(fā)，考察其變化對(duì)信息熵的影響，提出信息觀下不確定性的度量方法，同時(shí)在約簡(jiǎn)算法的設(shè)計(jì)中僅考慮負(fù)域內(nèi)的樣本，在一定程度上提高了算法的約簡(jiǎn)效率.續(xù)欣瑩等人[82]定義了不一致鄰域，利用相關(guān)性質(zhì)加快信息熵的計(jì)算速度，并結(jié)合辨識(shí)矩陣設(shè)計(jì)出基于信息觀的鄰域決策系統(tǒng)屬性約簡(jiǎn)算法，但文中沒(méi)有說(shuō)明算法在不同分類器下分類精度不同的原因.王光瓊[83]將鄰域條件熵和鄰域近似精度結(jié)合提出組合信息熵這一概念，可以從知識(shí)不確定性和集合不確定性兩個(gè)方面度量屬性的重要程度，實(shí)驗(yàn)表明基于鄰域組合熵的屬性約簡(jiǎn)算法可以提高約簡(jiǎn)結(jié)果的精度.張寧等人[84]引入測(cè)度，結(jié)合鄰域近似精度和鄰域條件熵給出鄰域近似條件熵的定義，并利用鄰域近似條件熵的單調(diào)性設(shè)計(jì)出一種啟發(fā)式算法.該算法能夠克服單純基于代數(shù)觀或信息觀的屬性約簡(jiǎn)算法的缺點(diǎn)，但算法時(shí)間復(fù)雜度過(guò)高，不適合用來(lái)處理大規(guī)模數(shù)據(jù).Lin等人[85]指出以往的鄰域粗糙集屬性約簡(jiǎn)算法僅適用于單標(biāo)簽學(xué)習(xí)任務(wù)，所以從不同認(rèn)知角度（悲觀、樂(lè)觀、中立）重新定義了鄰域信息熵以及相關(guān)概念，并提出優(yōu)化函數(shù)來(lái)度量候選屬性重要性的方法，進(jìn)而設(shè)計(jì)出相應(yīng)的屬性約簡(jiǎn)算法.

除上述研究較為充分的兩類鄰域粗糙集屬性約簡(jiǎn)算法外，還有學(xué)者結(jié)合布爾矩陣[86]、鄰域區(qū)分度[87]、并行計(jì)算[88]、增量學(xué)習(xí)[89]、粒計(jì)算[90]等理論設(shè)計(jì)了屬性約簡(jiǎn)算法.

1.4 決策粗糙集屬性約簡(jiǎn)算法

Yao 等人通過(guò)將Bayes 風(fēng)險(xiǎn)決策思想引入到粗糙集模型中提出決策粗糙集[12]. 決策粗糙集在分類決策問(wèn)題處理過(guò)程中表現(xiàn)出更強(qiáng)的抗噪聲能力以及風(fēng)險(xiǎn)代價(jià)敏感性，一經(jīng)提出就成為了粗糙集領(lǐng)域的研究熱點(diǎn). 由于引入概率閾值，決策粗糙集的決策域（正域或非負(fù)域）不再具備單調(diào)性，其屬性約簡(jiǎn)理論相對(duì)復(fù)雜. 本文采用文獻(xiàn)[91]和文獻(xiàn)[92]的觀點(diǎn)，即從決策粗糙集屬性約簡(jiǎn)目標(biāo)出發(fā)，將決策粗糙集屬性約簡(jiǎn)算法大致分為兩類：標(biāo)準(zhǔn)保持的屬性約簡(jiǎn)算法和標(biāo)準(zhǔn)優(yōu)化的屬性約簡(jiǎn)算法.

1.4.1 標(biāo)準(zhǔn)保持的屬性約簡(jiǎn)算法

標(biāo)準(zhǔn)保持的屬性約簡(jiǎn)的基本思想是將屬性約簡(jiǎn)視為不確定性度量的保持[92]. 這類算法主要從分析一些經(jīng)典屬性約簡(jiǎn)算法的不足出發(fā)，引入一些概念，并重新定義決策粗糙集屬性約簡(jiǎn). Li 等人[93]對(duì)比分析了經(jīng)典粗糙集和決策粗糙集正域的單調(diào)性，發(fā)現(xiàn)決策粗糙集的正域隨著屬性的減少可能是遞增的，并對(duì)基于正域的決策粗糙集約簡(jiǎn)重新進(jìn)行定義，提出基于正域基數(shù)的非單調(diào)性啟發(fā)式屬性約簡(jiǎn)算法.黃國(guó)順[94]指出文獻(xiàn)[93]中的正域受閾值取值的影響，且僅進(jìn)行集合基數(shù)比較可能會(huì)出現(xiàn)可信度高的正規(guī)則在約簡(jiǎn)后發(fā)生變化的情況. 基于以上原因，給出保正域不變的屬性約簡(jiǎn)定義，并討論了基于辨識(shí)矩陣的計(jì)算方法. 馬希驁等人[95]為達(dá)到保證每個(gè)決策類的決策域不發(fā)生變化的目的，提出決策域（正域、非負(fù)域）分布保持的約簡(jiǎn)定義，并定義正域和非負(fù)域條件信息量，將其作為啟發(fā)式信息以降低算法設(shè)計(jì)的難度，最后結(jié)合遺傳算法設(shè)計(jì)出決策域保持的屬性約簡(jiǎn)算法. Wang 等人[96]指出決策域具有非單調(diào)性，這使得基于決策域的啟發(fā)式算法在約簡(jiǎn)過(guò)程中可能會(huì)出現(xiàn)過(guò)約簡(jiǎn)現(xiàn)象，于是引入(α,β)正域、邊界域、負(fù)域保持約簡(jiǎn)的概念，并在屬性約簡(jiǎn)定義中使用不同的閾值對(duì)，最后結(jié)合信息觀設(shè)計(jì)出屬性約簡(jiǎn)算法.Gao等人[92]提出極大決策熵概念，用其來(lái)測(cè)量不確定性，并定義了正域、邊界域和負(fù)域保持約簡(jiǎn).設(shè)計(jì)的約簡(jiǎn)算法不僅最大化了約簡(jiǎn)與類屬性的相關(guān)性，也最小化了條件屬性的冗余.

1.4.2 標(biāo)準(zhǔn)優(yōu)化的屬性約簡(jiǎn)算法

標(biāo)準(zhǔn)優(yōu)化的屬性約簡(jiǎn)算法設(shè)計(jì)的基礎(chǔ)是將決策粗糙集屬性約簡(jiǎn)看作是不確定性度量的優(yōu)化問(wèn)題.這類屬性約簡(jiǎn)算法不僅包括用辨識(shí)矩陣、粒子群算法和回溯算法等方法優(yōu)化屬性約簡(jiǎn)過(guò)程的算法，還包括決策代價(jià)最小化的屬性約簡(jiǎn)算法.Zhao等人[91]將經(jīng)典粗糙集屬性約簡(jiǎn)的辨識(shí)矩陣方法引入到?jīng)Q策粗糙集模型中，定義了基于正決策的辨識(shí)矩陣和一般決策的辨識(shí)矩陣，設(shè)計(jì)出正域保持的屬性約簡(jiǎn)算法. 但該算法擴(kuò)大了正域，有可能會(huì)增加決策風(fēng)險(xiǎn).Stevanovic 等人[97]引入粒子群算法，基于規(guī)則退化和決策粗糙集屬性代價(jià)設(shè)計(jì)出適應(yīng)度函數(shù)，并通過(guò)把個(gè)體特征置信度加入到置信函數(shù)對(duì)原適應(yīng)度函數(shù)進(jìn)行改進(jìn)，最后提出兩個(gè)基于粒子群算法的決策粗糙集屬性約簡(jiǎn)算法. 張智磊等人[98]從決策風(fēng)險(xiǎn)角度出發(fā)求解決策粗糙集的最小屬性約簡(jiǎn)，設(shè)計(jì)出相應(yīng)的適應(yīng)度函數(shù)，并借助回溯搜索算法在全局搜索方面的優(yōu)良性能提出決策粗糙集屬性約簡(jiǎn)算法.該算法可以求解出較多最小屬性約簡(jiǎn). Jia 等人[99]通過(guò)分析現(xiàn)存決策粗糙集屬性約簡(jiǎn)定義指出決策單調(diào)作為約簡(jiǎn)標(biāo)準(zhǔn)較為主觀，所以將決策代價(jià)作為客觀標(biāo)準(zhǔn)給出屬性約簡(jiǎn)定義，并利用遺傳算法和模擬退火算法求解最小化屬性約簡(jiǎn)的代價(jià)，提出了決策粗糙集的最小代價(jià)屬性約簡(jiǎn)算法. Bi 等人[100]指出文獻(xiàn)[99]中的約簡(jiǎn)算法僅將決策代價(jià)作為啟發(fā)信息，沒(méi)有考慮所選屬性的分類能力，于是引入互信息重新定義了屬性重要度.同時(shí)該算法應(yīng)用極大相關(guān)性和極大重要性近似計(jì)算條件屬性和決策屬性間的互信息，降低了計(jì)算的復(fù)雜度.

此外，一些學(xué)者或?qū)Q策規(guī)則和決策代價(jià)相結(jié)合[101]，或從多種代價(jià)出發(fā)[102]，或從提高屬性約簡(jiǎn)效率出發(fā)[103]，或從局部視角出發(fā)[104-105]設(shè)計(jì)了決策粗糙集屬性約簡(jiǎn)算法.

1.5 變精度粗糙集屬性約簡(jiǎn)算法

為了有效處理噪聲數(shù)據(jù)，Ziarko 于1993 年引入包含度β，將Pawlak 粗糙集模型中嚴(yán)格的包含關(guān)系替換為部分包含關(guān)系，提出了變精度粗糙集模型[13].作為一類特殊的概率粗糙集模型，變精度粗糙集模型中閾值的存在使其正域、邊界域、負(fù)域并不具備單調(diào)性. 因此，Pawlak 粗糙集屬性約簡(jiǎn)理論的一些經(jīng)典約簡(jiǎn)思想和方法無(wú)法被直接引入到變精度粗糙集模型中.

早期的變精度粗糙集屬性約簡(jiǎn)算法存在一定缺陷，約簡(jiǎn)算法的設(shè)計(jì)經(jīng)歷了一個(gè)探索和修正過(guò)程.Ziarko引入依賴函數(shù)，率先提出了變精度粗糙集的β約簡(jiǎn)定義[13]，是一項(xiàng)開創(chuàng)性工作，但β約簡(jiǎn)會(huì)產(chǎn)生約簡(jiǎn)異常現(xiàn)象. Kryszkiewicz[106]給出變精度粗糙集相對(duì)正域?qū)哟蔚膶傩约s簡(jiǎn)定義，雖然該定義可以保證各個(gè)決策類的下近似不發(fā)生變化，但卻沒(méi)有考慮到閾值β 的區(qū)間概念，導(dǎo)致約簡(jiǎn)結(jié)果出現(xiàn)異常. Beynon[107]在Ziarko 約簡(jiǎn)定義的基礎(chǔ)上，將原來(lái)固定閾值β擴(kuò)展到一個(gè)區(qū)間，重新給出屬性約簡(jiǎn)定義，提出了變精度粗糙集區(qū)間約簡(jiǎn)模型，但區(qū)間約簡(jiǎn)依然存在區(qū)間異常、分類異常等約簡(jiǎn)異常. Mi 等人[108]指出β 約簡(jiǎn)不能保持各個(gè)下近似不變，可能會(huì)導(dǎo)致錯(cuò)誤約簡(jiǎn)，并提出變精度粗糙集β上（下）分布約簡(jiǎn)算法.此算法可以使每個(gè)決策類的上（下）近似保持不變，約簡(jiǎn)后導(dǎo)出的決策規(guī)則與原決策表導(dǎo)出的規(guī)則兼容，但它不適用于不完備決策表.為解決這一問(wèn)題，趙亞娣等人[109]基于相容關(guān)系定義了β上（下）分布約簡(jiǎn)，并利用差別矩陣構(gòu)造出約簡(jiǎn)算法，但該算法在處理不協(xié)調(diào)決策表時(shí)會(huì)出現(xiàn)約簡(jiǎn)錯(cuò)誤. 接著，林春杰等人[110]證明了β 上（下）分布約簡(jiǎn)的判定定理，并在改進(jìn)的上、下分布辨識(shí)矩陣的基礎(chǔ)上導(dǎo)出可辨識(shí)公式，進(jìn)一步完善了不完備決策表的約簡(jiǎn)理論.另外，曾子林等人[111]給出約簡(jiǎn)算法應(yīng)滿足的四條性質(zhì)，又從邏輯角度出發(fā)重新對(duì)變精度粗糙集理論進(jìn)行解釋，并在此邏輯解釋下提出變精度粗糙集的上（下）分布約簡(jiǎn)算法. Liu 等人[112]從正域集合覆蓋的角度研究約簡(jiǎn)算法，提出基于集合覆蓋的約簡(jiǎn)算法，用來(lái)求解β 下分布約簡(jiǎn)，為變精度粗糙集屬性約簡(jiǎn)問(wèn)題的研究提供了新思路.

同時(shí)許多研究者從其他角度研究變精度粗糙集的屬性約簡(jiǎn)問(wèn)題，提出多種其他類型的變精度粗糙集屬性約簡(jiǎn)算法[113-118]，進(jìn)一步豐富了變精度粗糙集屬性約簡(jiǎn)理論.

2 問(wèn)題和方向

拓展粗糙集是Pawlak 粗糙集在實(shí)際應(yīng)用中的自然推廣，拓寬了粗糙集在處理現(xiàn)實(shí)數(shù)據(jù)方面的應(yīng)用范圍，為有效處理不同場(chǎng)景下不確定性信息提供了強(qiáng)有力的理論支撐.作為粗糙集主要研究?jī)?nèi)容之一的屬性約簡(jiǎn)在拓展粗糙集模型中也得以廣泛研究，但同Pawlak 粗糙集屬性約簡(jiǎn)理論相比，拓展粗糙集屬性約簡(jiǎn)理論并不完善，同時(shí)也為了有效應(yīng)對(duì)各類復(fù)雜數(shù)據(jù)處理過(guò)程中存在的挑戰(zhàn)，仍需對(duì)拓展粗糙集屬性約簡(jiǎn)算法作進(jìn)一步研究.

第一，借鑒Pawlak 粗糙集屬性約簡(jiǎn)算法的設(shè)計(jì)思路和算法思想完善拓展粗糙集屬性約簡(jiǎn)理論.許多拓展粗糙集屬性約簡(jiǎn)算法的設(shè)計(jì)方法是直接從Pawlak 粗糙集借鑒而來(lái)的，如基于信息熵、辨識(shí)矩陣、正域等的屬性約簡(jiǎn)方法. 因此，一方面對(duì)Pawlak粗糙集屬性約簡(jiǎn)算法進(jìn)行研究，將一些較為有效的思想方法推廣到各類拓展粗糙集是研究拓展粗糙集屬性約簡(jiǎn)算法的常規(guī)且重要的研究思路.同時(shí)也要注意一部分拓展粗糙集模型也有其特殊性，比如：覆蓋粗糙集模型具有多樣性，決策粗糙集并不具備Pawlak 粗糙集所具有的單調(diào)性. 所以簡(jiǎn)單的平移策略并不適用于所有拓展粗糙集模型約簡(jiǎn)算法的設(shè)計(jì). 在設(shè)計(jì)屬性約簡(jiǎn)算法時(shí)，要根據(jù)模型的具體性質(zhì)設(shè)計(jì)相應(yīng)的屬性約簡(jiǎn)算法. 另一方面，粗糙集屬性約簡(jiǎn)算法是NP-hard 問(wèn)題[119]，借助一些優(yōu)化方法（模擬退火算法、粒子群算法、人工魚群算法等）對(duì)拓展粗糙集的經(jīng)典屬性約簡(jiǎn)算法進(jìn)行優(yōu)化或改進(jìn)也是拓展粗糙集屬性約簡(jiǎn)理論的一個(gè)研究方向.

第二，大數(shù)據(jù)的處理.在當(dāng)今信息爆炸的時(shí)代，大數(shù)據(jù)呈現(xiàn)出5V特征（數(shù)據(jù)量大、數(shù)據(jù)結(jié)構(gòu)復(fù)雜、數(shù)據(jù)呈動(dòng)態(tài)變化、數(shù)據(jù)的價(jià)值性、數(shù)據(jù)的真實(shí)性）.將粗糙集應(yīng)用于大數(shù)據(jù)預(yù)處理，對(duì)機(jī)器學(xué)習(xí)、模式識(shí)別以及金融、管理等各個(gè)領(lǐng)域的數(shù)據(jù)分析具有重要意義. 一些學(xué)者將拓展粗糙集模型與并行計(jì)算、增量學(xué)習(xí)、粒計(jì)算等理論結(jié)合，主要針對(duì)大數(shù)據(jù)三個(gè)特征（海量、動(dòng)態(tài)、多樣）中的某個(gè)特征設(shè)計(jì)出相應(yīng)的屬性約簡(jiǎn)算法，這些算法較之于基于Pawlak 粗糙集的屬性約簡(jiǎn)算法更適合處理大數(shù)據(jù)，但算法卻不適用于具備多種特征的復(fù)雜數(shù)據(jù)，所以融合多種理論設(shè)計(jì)出適用于復(fù)雜數(shù)據(jù)處理的屬性約簡(jiǎn)算法是一個(gè)亟需解決的問(wèn)題.

第三，特殊類型數(shù)據(jù)的處理. 現(xiàn)實(shí)生活中的應(yīng)用場(chǎng)景復(fù)雜，需要處理的數(shù)據(jù)類型多樣，而以往設(shè)計(jì)的多數(shù)屬性約簡(jiǎn)方法并不適用于某些特殊類型的數(shù)據(jù).這在一定程度上限制了粗糙集屬性約簡(jiǎn)理論在處理實(shí)際數(shù)據(jù)中的使用范圍. 根據(jù)數(shù)據(jù)的具體特征，選擇合適的粗糙集模型，并結(jié)合其他理論方法設(shè)計(jì)相應(yīng)的屬性約簡(jiǎn)算法對(duì)于實(shí)際問(wèn)題的解決以及粗糙集屬性約簡(jiǎn)理論的完善都有著重要意義，如：部分標(biāo)記數(shù)據(jù)在現(xiàn)實(shí)應(yīng)用中廣泛存在，如何結(jié)合半監(jiān)督學(xué)習(xí)的一些理論設(shè)計(jì)出適用于部分標(biāo)記數(shù)據(jù)的高效屬性約簡(jiǎn)算法是一個(gè)熱點(diǎn)研究問(wèn)題.

3 結(jié)語(yǔ)

粗糙集模型的屬性約簡(jiǎn)算法在理論研究方面取得了豐碩成果，在實(shí)際數(shù)據(jù)處理中也發(fā)揮了巨大作用.本文詳細(xì)總結(jié)分析了模糊粗糙集、覆蓋粗糙集、鄰域粗糙集、決策粗糙集、變精度粗糙集等幾類拓展粗糙集模型的經(jīng)典屬性約簡(jiǎn)算法和一些最新研究成果，并對(duì)拓展粗糙集屬性約簡(jiǎn)的未來(lái)研究方向進(jìn)行了展望，或?yàn)橥卣勾植诩Ｐ蛯傩约s簡(jiǎn)算法的研究提供借鑒.