粗糙集理論及其應用與發展研究

摘要：粗糙集理論是一種研究不精確、不確定性、處理不完備知識的數學工具，目前被廣泛應用于人工智能、模式識別、機器學習、決策支持和數據挖掘等領域。該文通過介紹粗糙集理論及特點，敘述了粗糙集理論在各領域的應用發展情況，并且展望了其未來發展趨勢。

關鍵詞：粗糙集；屬性約簡；粗糙集應用；數據挖掘

中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2008)28-0172-03

Rough Set Theory and Its Application Research

WEI Liang

(Electronics and Information School， Tongji University， Shanghai 201804， China)

Abstract: Rough set theory is a math theory which processes non-accurate， uncertain and incomplete knowledge. Currently， it has already been applied successfully in the area of Artificial Intelligence， Pattern Recognition， Machine Learning， Decision Analyzing and Data Mining etc. This paper introduces the rough set theory and its characteristics， reviews the development of this theory in different fields， and suggests evolutional trend in the coming future.

Key words: rough set; attribute reduction; rough set application; data mining

1 引言

波蘭數學家Pawlak于1982年提出的粗糙集理論是一種新的處理模糊和不確定性知識的數學工具[1]。其主要思想就是在保持分類能力不變的前提下，通過知識約簡，導出問題的決策或分類規則。粗糙集理論能有效地分析和處理不精確、不一致和不完整等各種不完備信息，并從中發現隱含的知識，揭示潛在的規律。以粗糙集理論為基本框架的知識發現過程的研究，越來越引起人們的關注，特別是將粗糙集理論與機器學習、模式識別、數據庫理論等相結合，并融合其它有效的數學工具與方法的研究，顯示出基于粗糙集理論的多種軟計算方法相結合算法在知識發現和優化過程中的強大的優越性，為知識發現的理論基礎提供了一定的依據。目前粗糙集理論已成為人工智能領域中一個較新的學術熱點，引起了越來越多科研人員的關注。

2 粗糙集理論的基本概念

設U是非空有限論域，R是U上的二元等價關系，R稱為不可分辨關系，序對A=(U，R)稱為近似空間。?坌(x，y)∈U×U，若(x，y)∈R，則稱對象x與y在近似空間A中是不可分辨 的。U/R是U上由R生成的等價類全體，它構成了U的一個劃分。可以證明，U上劃分可以 與U上的二元等價關系之間建立一一對應。U/R中的集合稱為基本集或原子集。若將U中的 集合稱為概念或表示知識，則A=(U，R)稱為知識庫，原子集表示基本概念或知識模塊。任意有限的基本集的并和空集均稱為可定義集，否則稱為不可定義的。可定義集也稱為精確集，它可以在知識庫中被精確地定義或描述，可表示已知的知識。可以驗證所有可定義集全體可構成 U上的一個拓撲。

令知識庫K=(U，R)，集合X?哿U，R是一個等價關系：

■

分別稱RX為X的R下近似（Lower Approximation）和RX為X的R上近似（Upper Approximation）。稱集合BNR(X)=RX-RX為X的R邊界域；POSR(X)RX為X的R正域； NEGR(X)=U-RX為X的R負域。下近似RX包含了所有使用知識R可確切分類到概念X的元素。上近似RX則包含了所有那些可能是屬于概念X的元素。概念的邊界區域BNR(X)由不能肯定分類到這個概念X或其補集X中的所有元素組成。關系如圖1所示。

刻畫粗糙集的方法有以下兩種：一種是用表示近似精度的數值表示粗糙集的數字特征；數字特征表示粗糙集邊界域的相對大小，但沒有說明邊界域的結構。另一種是用粗糙集的拓撲分類表示粗糙集的拓撲特征。拓撲特征給出邊界域的結構信息，但沒有給出邊界域大小的信息。

由等價關系R定義的集合X的近似精度如下：

■

其中X≠Ф，|X|表示集合X的基數，顯然，0≤αR(X)≤1。定義PR(X)=1-αR(X)，稱PR(X)為X的R粗糙度。粗糙度反映了利用知識R近似表示X的不完全程度。

設X是一個R粗糙集， 稱X是R粗糙可定義的，當且僅當RX≠Ф且RX≠U；稱X是R內不可定義的，當且僅當RX=Ф且RX≠U；稱X是R外不可定義的，當且僅當RX≠Ф且RX=U；稱X是R全不可定義的，當且僅當RX=Ф且RX=U。如果X是R粗糙可定義的，則意味著我們可以確定U中的某些元素屬于X或X；如果X是R內不可定義的，則意味著我們可以確定U中的某些元素是否屬于X，但不能確定U中任一元素是否屬于X；如果X是R外不可定義的，則意味著我們可以確定U中的某些元素是否屬于X，但不能確定U中任一元素是否屬于X；如果X是R全不可定義的，則意味著我們不能確定U中的任一元素是否屬于X或X。

粗糙集的數字特征（近似精度）和拓撲特征之間有一定的聯系：

若集合是內不可定義的或全不可定義的，則其近似精度為0；

若集合是外不可定義的或全不可定義的，則其補集的近似精度為0。

實際應用時，應綜合考慮邊界域的兩種信息。

3 屬性約簡

屬性約簡是粗糙集理論中的一個核心部分，同時也是粗糙集理論中最重要的概念之一。自粗糙集理論被提出后，研究學者在屬性約簡方面提出了許多算法，這些屬性約簡算法最終可以歸結為三類：基于約簡定義的Pawlak屬性約簡算法[2]；基于差別矩陣的屬性約簡算法；基于啟發式信息的屬性約簡算法。然而，到目前為止，還沒有一個公認的、高效的最佳屬性約簡算法，另一方面，科學家在理論上證明求取處理對象的所有屬性約簡、所有最小約簡是一個NP完全問題。

3.1 幾種典型的約簡算法

3.1.1 基本算法

基本算法首先在已有數據的基礎上構造差別矩陣。然后在差別矩陣的基礎上得到差別函數。對此得到的差別函數進行化簡，使之成為析取范式。最后得到的每個主蘊含式均為約簡。該算法可以求出所有的約簡。然而，由于對大數據集的差別函數的約簡是一個非常困難幾乎不可能的問題，因此，此算法只適合于非常小的數據集。

3.1.2 基于差別矩陣的啟發式算法

Skowron提出差別矩陣，并且提出差別矩陣可用于屬性約簡。在此基礎上，利用差別矩陣得到了許多啟發式約簡算法。這些算法的共同點都是先得到差別矩陣，由差別矩陣求出屬性核，在此基礎上根據如信息熵、屬性頻率等啟發式規則往屬性核加入屬性，直到滿足條件為止。

3.1.3 遺傳算法

己經有不少用遺傳算法計算約簡的算法。各種算法的不同之處主要在適應度函數的不同。Bjorvand和Komorowski提出了具有代表性的遺傳算法。每個位串代表差別矩陣的一項，即兩個對象的屬性集口某位為1時表示該屬性存在，否則不存在。這樣每個位串是一個約簡的候選。定義適應度函數如下：

■

其中N是屬性集合的長度，Lv是v中1的個數。Cv是v能區分的對象組合的個數。m是對象的個數。該函數由兩部分組成，前一部分的目的是希望Lv的長度盡可能的小。后一部分希望區分的對象盡可能多。在設計初始種群時，可以考慮將核或專家認為必要的屬性加入種群中，以加快算法的收斂速度。

3.1.4 擴展法則約簡算法

Starzyk， Nelson and Sturtz提出一種新概念，稱為強等價(strong equivalence)，進而發展為擴展法則，用于快速簡化差別函數。兩個屬性稱為局部強等價，若它們在差別函數的所有項中同時出現或不出現。當兩個屬性是局部強等價時，它們就可以僅用一個屬性代替。實驗表明該算法比基本算法快數十到數百倍。因而這種算法可以較基本算法處理更大的數據集。

3.1.5 動態約簡算法

動態約簡在某種意義上是給定決策表中最穩定的約簡，它們是從給定決策表中隨機抽樣形成的子表中最常出現的約簡。動態約簡能夠有效的增強約簡的抗噪音能力。動態約簡的計算過程較為簡明，主要是對決策表進行采樣，然后對采樣后的決策表計算所有約簡。在所有的子表中保持不變或近似保持不變的約簡就是動態約簡。

3.1.6 復合系統的約簡算法

Kryszkiewicz和Rybinski研究了在復合信息系統中尋求約簡的問題。即怎樣利用現有的子系統的約簡求復合系統的約簡。其主要思想是將布爾函數的約簡問題轉化為集合空間的邊界搜索問題。而在己知子系統的約簡的情況下，統的搜索空間將得到簡化。設有信息系統S1，S2，它們的屬性集合相同f1和f2分別是它們的差別函數。則整個信息系統S的差別函數f可表示為f=f1∧f2∧f12。其中f12代表S1、S2中的對象分別作為橫縱坐標組成的差別函數。根據上面的討論，如果已知S1和S2的約簡時，則S的約簡只需在空間[MINS(f1∧f2)，{c}]上搜索而不必從頭開始。其中MINS(f1∧f2)是兩個子系統約簡的并的最小值，因而使搜索空間大大減小。

4 粗糙集理論的應用與發展趨勢

4.1 粗糙集理論的研究對象

粗糙集理論的研究對象是由一個多值屬性(特征、癥狀、特性等)集合描述的一個對象(觀察、病歷等)集合，對于每個對象及其屬性都有一個值作為其描述符號，對象、屬性和描述符是表達決策問題的3個基本要素[4]。這種表達形式也可以看成一個二維表格，表格的行與對象相對應，列對應于對象的屬性；各行包含了表示相應對象信息的描述符，還有關于各個對象的類別成員的信息。通常，關于對象的可得到的信息不一定足以劃分其成員類別。換句話說，這種不精確性導致了對象的不可分辨性。給定對象間的一個等價關系，即導致由等價關系構成的近似空間的不分明關系，粗糙集就用不分明對象類形成的上近似和下近似來描述。這些近似分別對應了確定屬于給定類的最大的對象集合和可能屬于給定類的最小的對象集合[3]。下近似和上近似的差是一個邊界集合，它包含了所有不能確切判定是否屬于給定類的對象。這種處理可以定義近似的精度和質量。粗糙集方法可以解決重要的分類問題，所有冗余對象和屬性的約簡包含屬性的最小子集，能夠很好地近似分類，得到可以接受質量的分類。而且，它還可以用決策規則集合的形式表示最重要屬性和特定分類之間的所有重要關系。

4.2 粗糙集理論的應用情況

粗糙集的生命力在于它具有較強的實用性，從誕生到現在雖然只有20多年，但已經在許多領域取得了令人鼓舞的成果。

1) 粗糙集應用于智能控制。粗糙集根據觀測數據獲得控制策略的方法稱為從范例中學習(learning from examples)，屬于智能控制的范疇。基本步驟是：把控制過程中的一些有代表性的狀態以及操作人員在這些狀態下所采取的控制策略都記錄下來，形成決策表，然后對其分析化簡，總結出控制規則。形式為：IF Condition = N滿足THEN采取Decision = M。粗糙集方法是一類符號化分析方法，需要將連續的控制變量離散化，為此Pawlak提出了粗糙函數(rough function)的概念，為粗糙控制打下了理論基礎[2]。

2) 粗糙集應用于神經專家系統。在專家系統中，知識獲取是一個非常關鍵的階段，定義又很困難。由蘇丹卡同大學、馬來西亞大學和普恰大學的M.E. Yahia、R.Mahmod等研制的粗糙神經專家系統中提出將神經網絡作為專家知識庫。而運用粗糙集作為數學工具來處理不確定與不精確數據，將兩者結合形成稱之為粗糙神經專家系統的混合結構。該系統應用于醫學診斷，并進行肝炎病例的檢測。

3) 粗糙集應用于決策分析。在決策分析方面，粗糙集理論的決策規則是在分析以往經驗數據的基礎上得到的，它允許決策對象存在一些不太明確的屬性。希臘發展銀行ETEVA應用粗糙集理論協助制訂信貸政策，是粗糙集理論多準則決策方法的一個成功范例。另外，由意大利卡塔亞大學學者Salvatore Greco和波蘭波茲納特大學的Roman Slowinshi提出可以將粗糙集應用于多標準決策分析。

4) 粗糙集和模糊集在詞匯挖掘中的應用。美國Lowa University和Louisiana State University的Padmini Srinivasan、MiguelE.Ruiz等人研究了一種新的詞匯挖掘機制，它采用了粗糙集與模糊集的結合，運用粗糙集和可變精度模型，解決了多詞匯視圖的問題。最后分析了應用該詞匯挖掘結構的聯合醫療語言系統。

5) 粗糙集應用于股票數據分析。Golan和Ziarko應用粗糙集理論分析了10年股票的歷史數據，研究了股票價格與經濟指數之間的依賴關系，獲得的預測規則得到了華爾街證券交易專家的認可。

6) 粗糙集應用于醫療診斷。在醫療診斷方面，用粗糙集方法根據以往病例歸納出診斷規則，用來指導新的病例。人工預測早產準確率只有17%～38%，應用粗糙集理論可提高到68%～90% 。

粗糙集理論的應用領域還包括：地震預報、沖突分析、近似推理、軟件工程數據分析、圖像處理、材料科學中的晶體結構分析、預測建模、結構建模、投票分析、電力系統等。

4.3 粗糙集理論研究的發展趨勢

4.3.1 大數據集問題的解決

現實中的數據庫已經越來越大，如何降低算法的執行效率和復雜度，從眾多數據中尋找最有用的數據，是粗糙集理論需要應對的一個挑戰。雖然目前這方面已有了一些研究成果，但是還不完善，仍需要進一步研究。

4.3.2 缺失值處理方法研究

在對樣本數據進行處理時，往往會遇到數據丟失的問題，即不完備的信息系統。造成數據丟失的原因很多，如對數據測量的誤差、數據處理和數據獲取的限制等。由于經典粗糙集理論是基于完備信息系統的，為了使這一理論適合于不完備信息系統的處理，需要采用特定的方法對缺失值進行處理，建立處理不完備信息系統的擴展粗糙集模型。

4.3.3 高效約簡算法探索

屬性約簡的求解是一個NP困難問題，導致該問題的主要原因是屬性的組合爆炸。高效的約簡算法是粗糙集理論應用于知識發現的基礎，要在令人可接受的時間內獲得約簡的通常做法是基于啟發式知識的約簡方法。國內外學者在這方面做了大量的研究，但是目前還不存在一種非常有效的方法，因此尋找快速的約簡算法及其增量版本這一問題仍是粗糙集理論的研究熱點之一。

4.3.4 多方法融合

由于粗糙集在處理數據時存在一定的缺點，因此有必要把粗糙集和其他不確定方法結合起來。目前比較常用的做法是粗糙集和神經網絡及模糊集的結合應用。雖然在這方面已經取得了一定的成績，但是還有很多難點并沒有解決，仍需進一步的研究。

4.3.5 連續屬性的離散化處理

因為粗糙集只能處理離散化的屬性，而現實中存在的數據一般具有連續型的屬性，因此，連續屬性的離散化變得極為重要，已成為制約粗糙集實際應用的一個很大障礙。目前已經有了一些這方面的相關研究，但是這些方法或多或少的都存在一定的缺陷，還沒有一種比較公理化的方法，因此該問題的研究仍是今后的熱點。

5 結束語

粗糙集理論是一種新穎、有效的軟計算方法，能夠分析和處理不完備信息，其對不確定信息處理的方式及與其他軟科學和軟計算方法的結合[5]，是人工智能領域的進一步發展方向，其應用中的巨大潛力，必將開拓基于粗糙集諸多實際應用領域的發展空間。但是，粗糙集理論還處在繼續發展之中，正如粗糙集理論的創立人Pawlak所指出的那樣，尚有一些理論上的問題需要解決，而且粗糙集理論及其應用研究在我國還處于發展階段，還有待于進一步的研究和探討。但是相信，粗糙集理論仍具有廣闊的發展空間，今后將會在更多的實際領域中發揮作用。

參考文獻：

[1] Pawlak Z. Rough sets[J]. International Journal of Information and Computer Science，1982，5(11):341-356.

[2] Pawlak Z. Rough Classification[J]. International Journal of Human-Computer Studies，1991，(51): 369-383.

[3] Pawlak Z. Vagueness and uncertainty-a rough set perspective[J]. Computational Intelligence，1995，11(2):227-232.

[4] 王國胤.Rough集理論與知識獲取[M].西安:西安交通大學出版社，2001.

[5] 苗奪謙，王國胤，劉清，等.粒計算:過去，現在與展望[M].北京:科學出版社，2007.