9．1．5　基于粗糙集理論的分類算法

（1）基本概念

粗糙集（Rough Set）理論是波蘭數(shù)學家Z．Pawlak于1982年提出的，是一種新處理含糊性和不確定性問題的數(shù)學工具。它不需要關于數(shù)據(jù)任何預備的或額外的信息。其研究對象是由多值屬性描述的知識系統(tǒng)，形式化定義如下：

定義9－1　一個知識系統(tǒng)S可以定義為一個四元組：

其中U為關于對象的非空有限集，稱為論域；A為對象屬性的集合；V為屬性值的集合；f：U×A→V為一單一映射，即對A x∈U、A a∈A均有f（x，a）∈V為對象x的a屬性的值。

粗糙集是最重要的概念，即不可分辨關系。它是等價關系的交集，本身也是一個等價關系。

定義9－2　在S中，對于任意屬性子集P∈A，均可定義一個不可辨關系IND（P）：

在不產(chǎn)生混淆的情況下可以用P代替IND（P）。

IND（P）是集合U上的一個等價關系，因此集合U可以根據(jù)等價關系IND（P）進行等價類的劃分。

定義9－3　集合U對于等價關系IND（P）的劃分記為U/IND（P），其計算公式如下：

其中運算符×定義為：

在不發(fā)生混淆的情況下，U/IND（P）也可簡記為U/P。

示例：表9－1是一個知識表的例子^［5］。

表9－1　知識表示例表

在表9－1中，可以使用不同屬性對樣本集合進行分類。比如U/頭疼和肌肉疼＝｛｛e1，e2，e3｝｛e4，e5｝｛e6｝｝。其中｛e1，e2，e3｝彼此之間相對于屬性子集“頭疼和肌肉疼”都是不可辨的，｛e4，e5｝也是如此。也就是當給定屬性頭疼為“是”，肌肉疼為“是”時，我們無法確定所描述的對象是e1還是e2還是e3。

在不可分辨關系的基礎上可以定義粗糙集的上近似和下近似，從而刻畫集合的粗糙性，反映事物的知識粒度。

由此可以看出，粗糙集方法是一個基于一個或一組機構關于一些現(xiàn)實的大量數(shù)據(jù)，以觀察和測量這些數(shù)據(jù)進行分類的能力為基礎，從中發(fā)現(xiàn)、推理知識和分辨系統(tǒng)的某些特點、過程、對象等的方法。

（2）精確集與粗糙集

我們稱U/IND（P）中的元素（也是集合）為P基本集（在不發(fā)生混淆的情況下也簡稱基本集），精確集與粗糙集的概念都是在基本集之上定義的。

定義9－4　我們?nèi)我庥邢薅鄠€基本集并稱為P可定義集。對于樣例E≤U，若E是P可定義集，則稱E為P精確集（在不發(fā)生混淆的情況下可簡稱精確集），否則E就是粗糙集。

舉例如下：若P＝｛頭疼，肌肉疼｝，則集合｛e1，e2，e3，e4，e5｝是精確集，而集合｛e2，e4，e6｝則是粗糙集。

對于精確集，當給定任意屬性組合時，都可以判斷具備這些屬性的元素是屬于該集合還是不屬于該集合。而粗糙集則做不到這一點。如果想要將一個粗糙集變?yōu)榫_集，可以有兩種方法：第一種是補充一些元素，第二種是去掉一些不確定的元素。比如前面提到的粗糙集｛e2，e4，e6｝，可以將元素e2、e4去掉構成精確集｛e6｝；也可以補充元素e1、e3、e5構成精確集｛e1，e2，e3，e4，e5，e6｝。使用這兩個精確集就可以對粗糙集進行描述。這兩個集合都屬于粗糙集的近似集。

（3）近似集

一個對象x是否屬于集合X，需根據(jù)現(xiàn)有的知識來判斷，可分為三種情況：x肯定屬于X；x肯定不屬于X；x可能屬于X也可能不屬于X。為了能進行精確的數(shù)學計算，粗糙集中引入了一些傳統(tǒng)集合來對自身進行描述，這些集合包括下近似集、上近似集、正域、負域、邊界域等。

定義9－5　對于樣例E≤U，E的下近似集（E）和上近似集P（E）分別定義為：

定義9－6　對于樣例E≤U，E的正域POS _P（E）、負域NEG _P（E）和邊界域EN _P（E）分別定義為：

POS _P（E）＝（E）

NEG _P（E）＝U－（E）

假設將E視為一個概念，則上近似集可以表示這個概念的外延，外延之外的東西肯定不屬于該概念。下近似集可以表示這個概念的內(nèi)涵，內(nèi)涵之內(nèi)的東西肯定屬于該概念。邊界域上的元素則可能屬于這個概念，也可能不屬于這個概念，由此可以看出，概念之所以具有模糊性是因為邊界域的原因^［5］。

（4）決策表

只有在實例學習的基礎上，粗糙集理論才可以運用到知識獲取中。因此粗糙集理論在知識表的基礎上引入了決策表的概念。決策表同知識表一樣，也包含大量實例記錄，但決策表在知識表的基礎上還多一條決策屬性。知識獲取的目的就是對實例庫進行分析，確定哪些屬性對決策是有貢獻的，哪些屬性是不重要或者冗余的。比如在表9－1中，可以將“流感”這一條作為決策屬性，而其他與癥狀有關的屬性都可以作為條件屬性。決策表一般分為一致決策表和不一致決策表。

表9－2　決策表

舉例如下：設論域U＝｛x1，x2，…，x7｝，屬性集A＝C∪D，條件屬性集C＝｛a，b，c，d｝，決策屬性集D＝｛e｝。

由表9－2可知：

U/C＝｛｛x1｝，｛x2｝，｛x3｝，｛x4｝，｛x5｝，｛x6｝，｛x7｝｝

U/D＝｛｛x1，x2，x7｝，｛x3，x5，x6｝，｛x4｝

POSC（D）＝｛x1，x2，x3，x4，x5，x6，x7｝

可以求得決策集C對于屬性D的依賴度：

即為一致決策表。

在上述中系數(shù)k可以作為評估系統(tǒng)參數(shù)的重要性。而約簡系統(tǒng)參數(shù)則要依賴于決策表的約簡。前面已經(jīng)提到不同屬性對于決策的重要度是不相同的。此外決策表中還存在冗余現(xiàn)象。也就是在樣本集中，只需要少數(shù)屬性就可以重現(xiàn)整個決策。所謂屬性約簡是指在保持知識系統(tǒng)決策能力不變的情況下，刪除其中的冗余屬性。

目前已經(jīng)涌現(xiàn)出了很多屬性約簡算法，包括一般約簡算法、基于可識別矩陣（Discernibility Matrix）^［6］的算法、歸納屬性約簡算法、MIBARK算法、基于特征選擇的算法、基于最佳原理的算法等。