幾類拓展粗糙集模型屬性約簡研究綜述

鄔陽陽，郭文強，湯建國，任 艷

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

經(jīng)典粗糙集（Pawlak粗糙集）最初由波蘭學(xué)者提出，是處理不確定性信息的強有力工具[1-4]，但建立在嚴格等價關(guān)系之上的Pawlak 粗糙集理論僅適用于處理離散型數(shù)據(jù).為了有效處理實際應(yīng)用中更為復(fù)雜的數(shù)據(jù)（多媒體數(shù)據(jù)、基因數(shù)據(jù)、金融數(shù)據(jù)等），一些學(xué)者將Pawlak 粗糙集模型進行拓展和延伸，提出許多新粗糙集模型，如：模糊粗糙集[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)用，其屬性約簡算法作為數(shù)據(jù)預(yù)處理的有效方法也受到國內(nèi)外學(xué)術(shù)界的廣泛關(guān)注.

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

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

1 屬性約簡算法

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

1.1 模糊粗糙集屬性約簡算法

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

1.1.1 基于辨識矩陣的屬性約簡算法

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

1.1.2 基于屬性依賴度的屬性約簡算法

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

1.1.3 基于信息觀的屬性約簡算法

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

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

1.2 覆蓋粗糙集屬性約簡算法

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

1.2.1 基于辨識矩陣的屬性約簡算法

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

1.2.2 基于信息觀的屬性約簡算法

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

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

1.3 鄰域粗糙集屬性約簡算法

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

1.3.1 基于屬性重要度的屬性約簡算法

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

1.3.2 基于信息觀的屬性約簡算法

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

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

1.4 決策粗糙集屬性約簡算法

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

1.4.1 標準保持的屬性約簡算法

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

1.4.2 標準優(yōu)化的屬性約簡算法

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

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

1.5 變精度粗糙集屬性約簡算法

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

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

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

2 問題和方向

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

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

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

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

3 結(jié)語

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