粗糙集

粗糙集 粗糙集理論及其應用

摘 要 在很多實際系統中均不同程度地存在著不確定性因素, 採集到的數據常常包含著雜訊，不精確甚至不完整. 粗糙集理論是繼概率論，模糊集，證據理論之後的又一個處理不確定性的數學工具。

本文介紹了粗糙集理論的基本概念，特點及有關應用.

關鍵詞 粗糙集, 不確定性, 數據分析, 軟計算

1 引言

在自然科學，社會科學和工程技術的很多領域中, 都不同程度地涉及到對不確定因素和對不完備( imperfect) 信息的處理. 從實際系統中採集到的數據常常包含著雜訊, 不夠精確甚至不完整. 採用純數學上的假設來消除或迴避這種不確定性, 效果往往不理想, 反之, 如果正視它，對這些信息進行合適地處理, 常常有助於相關實際系統問題的解決. 多年來, 研究人員一直在努力尋找科學地處理不完整性和不確定性的有效途徑. 模糊集和基於概率方法的證據理論是處理不確定信息的兩種方法, 已應用於一些實際領域. 但這些方法有時需要一些數據的附加信息或先驗知識, 如模糊隸屬函數，基本概率指派函數和有關統計概率分佈等, 而這些信息有時並不容易得到. 1982 年, 波蘭學者Z. Paw lak 提

出了粗糙集理論, 它是一種刻劃不完整性和不確定性的數學工具, 能有效地分析不精確，不一致( incon sisten t),不完整( incomp lete) 等各種不完備的信息, 還可以對數據進行分析和推理, 從中發現隱含的知識, 揭示潛在的規律. 粗糙集理論是建立在分類機制的基礎上的, 它將分類理解為在特定空間上的等價關係, 而等價關係構成了對該空間的劃分。粗糙集理論將知識理解為對數據的劃分, 每一被劃分的集合稱為概念。粗糙集理論的主要思想是利用已知的知識庫, 將不精確或不確定的知識用已知的知識庫中的知識來(近似) 刻畫。該理論與其他處理不確定和不精確問題理論的最顯著的區別是它無需提供問題所需處理的數據集合之外的任何先驗信息, 所以對問題的不確定性的描述或處理可以說是比較客觀的, 由於這個理論未能包含處理不精確或不確定原始數據的機制, 所以這個理論與概率論, 模糊數學和證據理論等其他處理不確定或不精確問題的理論有很強的互補性。本文簡要介紹了粗糙集理論的基本概念和實際應用.

2 粗糙集的理論

2. 1 粗糙集理論的產生和發展

在本世紀70 年代, 波蘭學者Z. Paw lak 和一些波蘭科學院，波蘭華沙大學的邏輯學家們，一起從事關於信息系統邏輯特性的研究. 粗糙集理論就是在這些研究的基礎上產生的. 1982年, Z. Paw lak 發表了經典論文Rough Set s , 宣告了粗糙集理論的誕生. 此後, 粗糙集理論引起了許多數學家，邏輯學家和計算機研究人員的興趣, 他們在粗糙集的理論和應用方面作了大量的研究工作.1991 年Z. Paw lak 的專著和1992 年應用專集的出版, 對這一段時期理論和實踐工作的成果作了較好的總結, 同時促進了粗糙集在各個領域的應用. 此後召開的與粗糙集有關的國際會議進一步推動了粗糙集的發展. 越來越多的科技人員開始了解並準備從事該領域的研究. 目前, 粗糙集已成為人工智慧領域中一個較新的學術熱點, 在機器學習，知識獲取，決策分析，過程式控制制等許多領域得到了廣泛的應用.

2. 2 粗糙集理論所處理的問題

粗糙集能有效地處理下列問題:

·不確定或不精確知識的表達;

·經驗學習並從經驗中獲取知識;

·不一致信息的分析;

·根據不確定，不完整的知識進行推理;

·在保留信息的前提下進行數據化簡;

·近似模式分類;

·識別並評估數據之間的依賴關係

2. 3 粗糙集理論的一些基本概念

2. 3. 1 知識的含義

"知識"這個概念在不同的範疇內有多種不同的含義. 在粗糙集理論中,"知識"被認為是一種分類能力. 人們的行為是基於分辨現實的或抽象的對象的能力, 如在遠古時代, 人們為了生存必須能分辨出什麼可以食用, 什麼不可以食用; 醫生給病人診斷, 必須辨別出患者得的是哪一種病. 這些根據事物的特徵差別將其分門別類的能力均可以看作是某種"知識".

2. 3. 2 不可分辨關係與基本集

分類過程中, 相差不大的個體被歸於同一類, 它們的關係就是不可分辨關係( indiscernability relation). 假定只用兩種黑白顏色把空間中的物體分割兩類, {黑色物體},{白色物體},那麼同為黑色的兩個物體就是不可分辨的, 因為描述它們特徵屬性的信息相同, 都是黑色. 如果再引入方，圓的屬性, 又可以將物體進一步分割為四類: {黑色方物體},{黑色圓物體},{白色方物體},{白色圓物體}. 這時, 如果兩個同為黑色方物體, 則它們還是不可分辨的. 不可分辨關係也稱為一個等效關係(equivalence relationship ) , 兩個白色圓物體間的不可分辨關係可以理解為它們在白，圓兩種屬性下存在等效關係.

基本集(elementary set) 定義為由論域中相互間不可分辨的對象組成的集合, 是組成論域知識的顆粒. 不可分辨關係這一概念在粗糙集理論中十分重要, 它深刻地揭示出知識的顆粒狀結構 , 是定義其它概念的基礎. 知識可認為是一族 等效關係, 它將論域分割成一系列的等效類.

2. 3. 3 集合的下逼近，上逼近及邊界區

粗糙集理論延拓了經典的集合論, 把用於分類的知識嵌入集合內, 作為集合組成的一部分. 一個對象a 是否屬於集合X 需根據現有的知識來判斷, 可分為三種情況: (1) 對象a 肯定屬於集合X ; (2) 對象a 肯定不屬於集X ; (3) 對象a 可能屬於也可能不屬於集合X . 集合的劃分密切依賴於我們所掌握的關於論域的知識, 是相對的而不是絕對的。給定一個有限的非空集合U 稱為論域, I 為U 中的一族等效關係, 即關於U 的知識, 則二元對 稱為一個近似空間(approximation space). 設x 為U 中的一個對象, X為U 的一個子集, 表示所有與x 不可分辨的對象所組成的集合, 換句話說, 是由x 決定的

等效類, 即 中的每個對象都與x 有相同的特徵屬性(attribute).

集合X 關於I 的下逼近(Lower approximation) 定義為:

實際上由那些根據現有知識判斷肯定屬於X 的對象所組成的最大的集合, 有時也稱

為X 的正區(po sit ive region) , 記作PO S (X ). 類似地, 由根據現有知識判斷肯定不屬於X 的

對象組成的集合稱為X 的負區(negat ive region) , 記作N EG (X ).

集合X 關於I 的上逼近(U pper app rox im at ion) 定義為

I3 (X ) 是由所有與X 相交非空的等效類I (x ) 的並集, 是那些可能屬於X 的對象組成的最小

集合. 顯然,

集合X 的邊界區(Boundary region) 定義為

BND (X ) 為集合X 的上逼近與下逼近之差. 如果BND (X ) 是空集, 則稱X 關於I 是清晰的

(crisp ) ; 反之如果BND (X ) 不是空集, 則稱集合X 為關於I 的粗糙集( rough set).

下逼近，上逼近及邊界區等概念稱為可分辨區(discern ib ility region s) , 刻劃了一個邊界含

糊(vague) 集合的逼近特性. 粗糙程度可按按下式的計算

式中 # 表示集合# 的基數或勢(cardinality) , 對有限集合表示集合中所包含的元素的個數.

顯然

, 如果A

, 則稱集合X 相對於I 是清晰(crisp ) 的, 如果A

從上面的定義中, 可以看出粗糙集理論中"含糊"(vague) 和"不確定"(uncertain ty) 這兩個

概念之間的關係:"含糊"用來描述集合, 指集合的邊界不清楚; 而"不確定"描述的是集合中的

元素, 指某個元素是否屬於某集合是不確定的.

2. 4 實例

下面用一個具體的實例說明粗糙集的概念. 在粗糙集中使用信息表( info rm at ion tab le) 描

述論域中的數據集合. 根據學科領域的不同, 它們可能代表醫療，金融，軍事，過程式控制制等方面

的數據. 信息表的形式和大家所熟悉的關係資料庫中的關係數據模型很相似, 是一張二維表

1 期韓禎祥等: 粗糙集理論及其應用39

1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

格, 如表一所示. 表格的數據描述了一些人的教育程度以及是否找到了較好工作, 旨在說明兩

者之間的關係. 其中王治，馬麗, 趙凱等稱為對象(ob ject s) , 一行描述一個對象. 表中的列描

述對象的屬性. 粗糙集理論中有兩種屬性: 條件屬性(condit ion at t ribu te) 和決策屬性(decision

at t ribu te). 本例中"教育程度"為條件屬性;"是否找到了好工作"為決策屬性.

表1 教育程度與是否找到好工作的關係

姓名教育程度是否找到了好工作

王治高中否

馬麗高中是

李得小學否

劉保大學是

趙凱博士是

設O 表示找到了好工作的人的集合, 則

O = {馬麗, 劉保, 趙凱}, 設I 表示屬性"教育

程度"所構成的一個等效關係, 根據教育程度

的不同, 該論域被分割為四個等效類: {王治,

馬麗},{李得},{劉保},{趙凱}. 王治和馬麗在

同一個等效類中, 他們都為高中文化程度, 是

不可分辨的. 則:

集合O 的下逼近(即正區) 為 {劉保，趙凱}

集合O 的負區為 {李得}

集合O 的邊界區為 {王治, 馬麗}

集合O 的上逼近為 {劉保，趙凱，王治，馬

麗}

根據表1, 可以歸納出下面幾條規則, 揭示了教育程度與是否能找到好工作之間的關係.

RUL E 1: IF (教育程度= 大學) OR (教育程度= 博士) THEN (可以找到好工作)

RUL E 2: IF (教育程度= 小學) THEN (找不到好工作)

RUL E 3: IF (教育程度= 高中) THEN (可能找到好工作)

從這個簡單的例子中, 我們還可以體會到粗糙集理論在數據分析，尋找規律方面的作用.

3 粗糙集理論的特點

3. 1 粗糙集是一種軟計算方法

軟計算(sof t compu t ing) 的概念是由模糊集創始人Zadeh[ 9 ]提出的. 軟計算中的主要工具

包括粗糙集，模糊邏輯(FL ),神經網路(NN ),_________概率推理(PR ),信度網路(Belief N etwo rk s),遺

傳演演算法(GA ) 與其它進化優化演演算法，混沌(Chao s) 理論等.

傳統的計算方法即所謂的硬計算(hard compu t ing) , 使用精確，固定和不變的演演算法來表達

和解決問題. 而軟計算的指導原則是利用所允許的不精確性，不確定性和部分真實性以得到易

於處理，魯棒性強和成本較低的解決方案, 以便更好地與現實系統相協調.

3. 2 粗糙集理論的特點

粗糙集方法的簡單實用性是令人驚奇的, 它能在創立后的不長時間內得到迅速應用是因

為具有以下特點:

(1) 它能處理各種數據, 包括不完整( incomp lete) 的數據以及擁有眾多變數的數據;

(3) 它能處理數據的不精確性和模稜兩可(am b igu ity) , 包括確定性和非確定性的情況;

(4) 它能求得知識的最小表達( reduct) 和知識的各種不同顆粒(granu larity) 層次;

(5) 它能從數據中揭示出概念簡單, 易於操作的模式(pat tern) ;

(6) 它能產生精確而又易於檢查和證實的規則, 特別適於智能控制中規則的自動生成.

40 信 息 與 控 制27 卷

1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

4 粗糙集理論的應用

粗糙集理論是一門實用性很強的學科, 從誕生到現在雖然只有十幾年的時間, 但已經在不

少領域取得了豐碩的成果, 如近似推理，數字邏輯分析和化簡，建立預測模型，決策支持，控制

演演算法獲取，機器學習演演算法和模式識別等等. 下面介紹一下粗糙集應用的幾個主要領域.

4. 1 人工神經網路訓練樣本集化簡

人工神經網路具有并行處理，高度容錯和泛化能力強的特點, 適合應用在預測，複雜對象

建模和控制等場合. 但是當神經網路規模較大，樣本較多時, 訓練時間過於漫長, 這個固有缺點

是制約神經網路進一步實用化的一個主要因素. 雖然各種提高訓練速度的演演算法不斷出現, 問題

遠未徹底解決. 化簡訓練樣本集, 消除冗餘數據是另一條提高訓練速度的途徑.

文[ 10 ]正是沿著這條思路, 應用粗糙集化簡神經網路訓練樣本數據集, 在保留重要信息的

前提下消除了多餘(superf luou s) 的數據. 模擬實驗表明訓練速度提高了4. 77 倍, 獲得了較好

的效果.

4. 2 控制演演算法獲取

實際系統中有很多複雜對象難於建立嚴格的數學模型, 這樣傳統的基於數學模型的控制

方法就難以奏效. 模糊控制模擬人的模糊推理和決策過程, 將操作人員的控制經驗總結為一系

列語言控制規則, 具有魯棒性和簡單性的特點, 在工業控制等領域發展較快. 但是有些複雜對

象的控制規則難以人工提取, 這樣就在一定程度上限制了模糊控制的應用.

粗糙集能夠自動抽取控制規則的特點為解決這一難題提供了新的手段. 一種新的控制策

略—模糊- 粗糙控制(fuzzy2rough con t ro l) 正悄然興起, 成為一個有吸引力的發展方向. 應用

這種控制方法, 文[11 ]研究了"小車—倒立擺系統"這一經典控制問題, 文[12 ]研究了過程式控制制

(水泥窯爐) , 均取得了較好的控制效果. 應用粗糙集進行控制的基本思路是: 把控制過程的一

些有代表性的狀態以及操作人員在這些狀態下所採取的控制策略都記錄下來, 然後利用粗糙

集理論處理這些數據, 分析操作人員在何種條件下採取何種控制策略, 總結出一系列控制規

則:

規則1 IF Condit ion 1 滿足 THEN 採取decision 1

規則2 IF Condit ion 2 滿足 THEN 採取decision 2

規則3 IF Condit ion 3 滿足 THEN 採取decision 3

這種根據觀測數據獲得控制策略的方法通常被稱為從範例中學習( learn ing f rom exam2

p les). 粗糙控制( rough con t ro l) 與模糊控制都是基於知識，基於規則的控制, 但粗糙控制更加

簡單迅速，實現容易(因為粗糙控制有時可省卻模糊化及去模糊化步驟) ; 另一個優點在於控制

演演算法可以完全來自數據本身, 所以從軟體工程的角度看, 其決策和推理過程與模糊(或神經網

絡) 控制相比可以很容易被檢驗和證實(validate). 文[ 11 ]還指出在特別要求控制器結構與算

法簡單的場合, 更適合採取粗糙控制.

美國電力科學研究院(EPR I) 對粗糙集的應用研究的潛力對十分重視, 將其作為戰略性

研究開發(St rategy R&D) 項目, 在1996 年撥款 196, 600 資助San Jo se 州立大學進行電力系

統模糊- 粗糙控制器的研究.

1 期韓禎祥等: 粗糙集理論及其應用41

1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

4. 3 決策支持系統

面對大量的信息以及各種不確定因素, 要作出科學，合理的決策是非常困難的. 決策支持

系統是一組協助制定決策的工具, 其重要特徵就是能夠執行IF THEN 規則進行判斷分

析. 粗糙集理論可以在分析以往大量經驗數據的基礎上找到這些規則, 基於粗糙集的決策支持

系統在這方面彌補了常規決策方法的不足, 允許決策對象中存在一些不太明確，不太完整的屬

性, 並經過推理得出基本上肯定的結論.

下面舉一個例子, 說明粗糙集理論可以根據以往的病例歸納出診斷規則, 幫助醫生作出判

斷. 表二描述了八個病人的癥狀. 從表二中可以歸納出以下幾條確定的規則:

表2 癥狀與感冒的關係

病人編號

病理癥狀診斷結果

是否頭痛體溫是否感冒

病人1 是正常否

病人2 是高是

病人3 是很高是

病人4 否正常否

病人5 否高否

病人6 否很高是

病人7 否高是

病人8 否很高否

1. IF (體溫正常) THEN (沒感冒)

2. IF (頭痛) AND (體溫高) THEN

(感冒)

3. IF (頭痛) AND (體溫很高) THEN

(感冒)

還有幾條可能的規則:

4. IF (頭不痛) THEN (可能沒感冒)

5. IF (體溫高) THEN (可能感冒了)

6. IF (體溫很高) THEN (可能感冒了)

病人5 和病人7, 病人6 和病人8, 癥狀

相同, 但是一個感冒另一個卻沒感冒, 這種情

況稱為不一致( incon sisten t). 粗糙集就是靠這種IF THEN 規則的形式表示數據中蘊含的

知識.

希臘工業發展銀行ETEVA 用粗糙集理論協助制訂信貸政策, 從大量實例中抽取出的規

則條理清晰, 得到了金融專家的好評[ 13 ].

4. 4 從資料庫中知識發現

現代社會中, 隨著信息產業的迅速發展, 大量來自金融，醫療，科研等不同領域的信息被存

儲在資料庫中. 這些浩如煙海的數據間隱含著許多有價值的但鮮為人知的相關性, 例如股票的

價格和一些經濟指數有什麼關係; 手術前病人的病理指標可能與手術是否成功存在某種聯繫;

滿足何種條件的夜空會出現彗星等天文現象等等.

由於資料庫的龐大, 人工處理這些數據幾乎是不可能的, 於是出現了一個新的研究方向—

資料庫中的知識發現(Know ledge D iscovery in Databases, KDD) , 也叫做資料庫(信息) 發掘

(M in ing) , 它是目前國際上人工智慧領域中研究較為活躍的分支. 粗糙集是其中的一種重要

的研究方法, 它採用的信息表與關係資料庫中的關係數據模型很相似, 這樣就便於將基於粗糙

集的演演算法嵌入資料庫管理系統中.

粗糙集引入核(co re),化簡( reduct) 等有力的概念與方法, 從數據中導出用IF THEN

規則形式描述的知識, 這些精練的知識更便於存儲和使用. 美國醫學工作者應用粗糙集理論對

大量的病歷進行分析, 發現黑人婦女患乳腺癌后的死亡率比白人婦女高. 到目前為止, 早產的

預測在醫學上還是比較困難的. 現有的人工預測方法準確率只有17à - 58à , 而應用粗糙集

理論則可將準確率提高到68à - 90à [ 8 ].

42 信 息 與 控 制27 卷

1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

5 粗糙集與模糊集，證據理論及其它一些情況

5. 1 粗糙集與模糊集，證據理論

粗糙集與模糊集都能處理不完備( imperfect) 數據, 但方法不同, 模糊集注重描述信息的含

糊(vagueness) 程度, 粗糙集則強調數據的不可辨別( indiscern ib ility) , 不精確( imp recision) 和

模稜兩可(am b igu ity). 使用圖像處理中的語言來作比喻, 當論述圖像的清晰程度時, 粗糙集強

調組成圖像象素的大小, 而模糊集則強調象素存在不同的灰度. 粗糙集研究的是不同類中的對

象組成的集合之間的關係, 重在分類; 模糊集研究的是屬於同一類的不同對象的隸屬的關係,

重在隸屬的程度. 因此粗糙集和模糊集是兩種不同的理論, 但又不是相互對立的, 它們在處理

不完善數據方面可以互為補充.

粗糙集理論與證據理論雖有一些相互交疊的地方, 但本質不同, 粗糙集使用集合的上，下

逼近而證據理論使用信任函數(belief funct ion) 作為主要工具. 粗糙集對給定數據的計算是客

觀的, 無須知道關於數據的任何先驗知識(如概率分佈等) , 而證據理論則需要假定的似然值

(p lau sib ility).

5. 2 近年來召開的與粗糙集有關的國際會議

相繼召開的以粗糙集理論為主題的國際會議, 促進了粗糙集理論的推廣. 這些會議發表了

大量的具有一定學術和應用價值的論文, 方便了學術交流, 推動了粗糙集在各個科學領域的拓

展和應用. 下面列出了近年召開的一些會議:

· 1992 年第一屆國際研討會(Rough Set s: State of the A rt and Perspect ives) 在波蘭

K iek rz 召開;

·1993 年第二屆國際研討會(The Second In ternat ionalWo rk shop on Rough Set s and

Know ledge D iscovery, RSKD'93) 在加拿大Banff 召開;

·1994 年第三屆國際研討會(The Th ird In ternat ionalWo rk shop on Rough Set s and Sof t

Compu t ing, RSSC'94) 在美國San Jo se 召開;

·1995 年在美國No rth Caro lina 召開了題為"Rough Set Theo ry, RST'95"的國際會議;

·1996 年第四屆國際研討會(The Fou rth In ternat ionalWo rk shop on Rough Set s, Fuzzy

Set s, andM ach ine D iscovery, RSFD'96) 在日本東京召開;

·1997 年3 月在美國No rth Caro lina 召開了第五屆國際研討會(The F if th In ternat ional

Wo rk shop on Rough Set s and Sof t Compu t ing, RSSC'97)

5. 3 國際上一些有關粗糙集的軟體

目前, 國際上研究粗糙集的機構和個人開發了一些應用粗糙集的實用化軟體, 也出現了商

業化的軟體. 加拿大Reduct System Inc. 公司開發的用於資料庫知識發現的軟體DataLogic

R [ 14 ]是用C 語言開發的, 可安裝在個人計算機上, 為科研領域和工業界服務.

美國肯薩斯大學開發了一套基於粗糙集的經驗學習系統[ 15 ] , 名為L ERS (L earn ing f rom

Examp les based on Rough Set s) , 它能從大量經驗數據中抽取出規則. L ERS 已被美國國家航

空航天管理局(NA SA ) 的約翰遜(John son) 空間中心採用, 作為專家系統開發工具, 為"自由

號"(F reedom ) 空間站上的醫療決策服務. 美國環境保護署(U S Environm en tal P ro tect ion A 2

gency) 資助的一個項目中也採用了L ERS.

波蘭波茲南工業大學(Poznan U n iversity of Techno logy) 開發的軟體RoughDA S 和

1 期韓禎祥等: 粗糙集理論及其應用43

1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

RoughClass, 也在不少實際領域中得到應用[ 5 ].

加拿大Regina 大學開發的KDD- R 是用C 編寫的, 在UN IX 環境下運行, KDD2R 基於

變精度粗糙集模型[ 16 ] (V ariab le P recision Rough Set, V PRS) , 通過改變粗糙程度而使數據中

隱含的模式更清楚的顯示出來.

6 結束語

粗糙集是一種較有前途的處理不確定性的方法, 相信今後將會在更多的領域中得到應用.

但是, 粗糙集理論還處在繼續發展之中, 正如粗糙集理論的創立人Z. Paw lak 所指出的那

樣[ 8 ] , 尚有一些理論上的問題需要解決, 諸如用於不精確推理的粗糙邏輯(Rough logic) 方法,

粗糙集理論與非標準分析(Non standard analysis) 和非參數化統計(Nonparam et ric stat ist ics)

等之間的關係等等.

將粗糙集與其它軟計算方法(如模糊集，人工神經網路，遺傳演演算法等) 相綜合, 發揮出各自

的優點, 可望設計出具有較高的機器智商(M IQ ) 的混合智能系統(Hyb rid In telligen t

System ) , 這是一個值得努力的方向.