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

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

（新疆財經大學計算機科學與工程學院，新疆烏魯木齊830012）

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

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

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

1 屬性約簡算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

另外，一些學者結合正態分布測量誤差[69]、相關族[70]、網絡拓撲[71]、超圖模型[72]、增量學習[73-74]等理論提出了其他類型的屬性約簡算法.

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

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

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

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

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

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

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

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

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

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

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

1.4.2 標準優化的屬性約簡算法

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

此外，一些學者或將決策規則和決策代價相結合[101]，或從多種代價出發[102]，或從提高屬性約簡效率出發[103]，或從局部視角出發[104-105]設計了決策粗糙集屬性約簡算法.

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

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

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

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

2 問題和方向

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

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

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

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

3 結語

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