第三章 差別矩陣

1、-作者xxxx-日期xxxx第三章 差別矩陣【精品文檔】第三章 差別矩陣粗集中的不確定性，是在論域上引入了某種限制性知識，這種限制性知識是取離散值的可稱作等價關(guān)系的屬性構(gòu)成的屬性集。由于對形成一種客觀性的劃分等價集，當(dāng)用知識對中非空子集中的元素進行分類時才產(chǎn)生了不確定性。雖然，Pawlak在上引入限制性知識，但屬性集并非是新的空間，中對象可以獲得種屬性的值，因而成為維特征空間中的點。這一點不論是在Cantor集中、模糊集中還是在經(jīng)典模式識別中，都被認為是已知事實。只是在粗集中限定的值域是有限離散集（連續(xù)值必須離散化），規(guī)定屬性值不完全相同的個體，分屬不同類，或說同一類中所有個體，對于每一種屬性

2、的取值都是一樣的。因為作了與的假定，才將論域客觀地劃分成若干等價類族。正因為對形成確定性分類才稱為知識，才導(dǎo)至中非空子集中元素用分類時產(chǎn)生不確定性。從這個角度講，粗集與Cantor集、模糊集一樣都是在一個空間上研究分類問題。粗集的特殊性在于：是在知識下考慮中元素是否屬于的非空子集（中屬于的元素才認為確定屬于，即可按知識準確分類）。§1 差別矩陣(The discernibility matrices)引例1 序 我們先考慮一個具體例子。例 1. 設(shè)信息系統(tǒng)=(,)由表1表示 1021000121202100022211210, , , , 是條件屬性集。表中不出現(xiàn)相同行，說明每個個體

3、都不同?？紤]下面表2：區(qū)分元素 個體個體注意到： 把與區(qū)分開的元素為, , ，, 并且每個元素都能區(qū)分開，故有一個就行，稱為析取關(guān)系，記作： 能把與區(qū)分開的只有。那么，能同時把，與區(qū)分開的元素是與()同時滿足，這種邏輯關(guān)系稱為合取關(guān)系，記作：()。由此把與，同時區(qū)分開的屬性應(yīng)滿足()() 第一列差別元素合取。把所有個體兩兩區(qū)分開的屬性應(yīng)滿足：所有列的差別元素的“合取式” 。當(dāng)表1（即信息系統(tǒng)）給定，則表2確定（稱為差別矩陣）,全部的差別元素的合取式也確定: 稱作差別函數(shù)。問題是：如何簡化差別函數(shù)。要進行關(guān)于析取，合取關(guān)系的邏輯變換需保證變換是等價的。考慮上面例子：=()()()()()()()

4、()方法:從最簡差別元素入手：在此為，含義是：要把,與同時區(qū)分開，要求。這樣，包含與的差別元素將失去意義而被吸收掉。因為存在且必須被保留，使得()失去存在價值。因為選其中或或不能把與區(qū)分開，還必須加上。而的加入，使, , 成為冗余。于是經(jīng)一次吸收得=()= ()()化為最簡析取范式后，每個析取子式對應(yīng)一個約簡。2 差別函數(shù)簡化的一般步驟對例1給出的差別函數(shù)，經(jīng)一次吸收律便得到欲求的約簡。但是，當(dāng)屬性個數(shù)、個體數(shù)很大時，對于包含個差別元素（且每個差別元素最多是個屬性的析取式）的合取式的化簡仍存在一個計算方法問題。下面給出一種簡化差別函數(shù)的速算法。步驟1：不用按表格形式構(gòu)造差別矩陣，而是直接從信息

5、表按下列規(guī)則提取保留差別元素；步驟2：從差別矩陣的第一列至第列對差別元素排序，序號為從至；步驟3：按順序從節(jié)拍開始，保留第 個差別元素，當(dāng)提取的第個差別元素和前面保留的差別元素之間存在包含關(guān)系時，則吸收所有包含集；否則，連同前面的保留差別元素均保留，且保留的差別元素之間為合取關(guān)系。步驟4：當(dāng)節(jié)拍=時，算法停止。 此時，所有保留差別元素的合取范式構(gòu)成差別函數(shù)。每個合取子式或是若干單一屬性的析取式或是單一屬性；并且這些合取子式作為屬性子集不存在包含關(guān)系。即如果有一個合取子式為單個屬性，則在其他所有合取子式中屬性不出現(xiàn)；若有一個合取子式為()，那么，在所有其它合取子式中最多只能包含或而不會同時包含與

6、。經(jīng)上述步驟，差別函數(shù)化為 =。其中為單個屬性；是包含至少有兩種屬性的析取式，并且中的屬性個數(shù)是的不減函數(shù)。 通常情況下，(+)<<。中屬性個數(shù)遠小于(為屬性數(shù))。步驟5：從開始施行合取關(guān)于析取關(guān)系的分配律。比如，若=.則化為=()() 分別對上述兩個析取子式應(yīng)用吸收律，在第一個子句中吸收掉包含的，在第二個析取子句中吸收掉包含的,得：=()()其中，, 步驟6：重復(fù)步驟5，直到將化為最簡析取范式，則每個析取子式對應(yīng)一個約簡。§2 差別矩陣差別矩陣也稱作可辨識矩陣或分明矩陣，是由斯科龍（Skowron）教授于1991年提出來的一種表示知識的方法，其優(yōu)點是可以解釋并便于計算數(shù)

7、據(jù)核和約簡。斯科龍最初提出差別矩陣的概念，也是為了計算約簡。1 信息系統(tǒng)的差別矩陣設(shè)是一個信息系統(tǒng)，其中，。稱階矩陣為信息系統(tǒng)的差別矩陣，其中 ， （1）稱為差別元素，它是使第個個體與第個個體屬性值不相等的那些屬性構(gòu)成的集合，或說是所有能區(qū)分開個體和的屬性構(gòu)成的集合。當(dāng)時，顯然，因為不存在把樣本與自身區(qū)分開的屬性。且是對稱的，可只用其下三角部分表示，即 和。設(shè)，能把個體和區(qū)分開的差別元素是這個屬性中的若干個。這若干個屬性間的關(guān)系是“或”，用“”表示。中的每一個屬性都能把與區(qū)分開。若能把與區(qū)分開的屬性是，則稱為析取范式，即每個差別元素都是由析取范試表達的屬性集。顯然，把與,都區(qū)分開的屬性應(yīng)是,

8、這些差別元素的“與”（同時成立），用“”表示，即這些差別元素的合取式：把所有個體都兩兩區(qū)分開就應(yīng)該是所有差別元素的合取式。通過邏輯運算將所有差別元素的合取式化為析取試后，記作，稱為信息系統(tǒng)的分明函數(shù)（差別函數(shù)），任意的差別矩陣都唯一地確定了一個差別函數(shù)。定理：設(shè)是一信息系統(tǒng)，是的差別矩陣，是信息系統(tǒng)的一個差別函數(shù)，則該函數(shù)的最小簡化的析取范式對應(yīng)信息系統(tǒng)的全體約簡。該命題給出了計算信息系統(tǒng)全體約簡的重要方法：只要將合取范式的差別函數(shù)展開成析取范式，便得到的全體約簡。例1 設(shè)信息系統(tǒng)由表1表示表11021000121202100022211210其中，由于容易推出：，。因為且使劃分等價類中只含一

9、個個體，并且從中任意去掉一種屬性將導(dǎo)致劃分能力改變在此不能將5個體都區(qū)分開，所以，是的一個約簡。同理也是信息表的一個約簡。現(xiàn)在我們換一個角度，用差別矩陣和差別函數(shù)來計算約簡。步驟1 計算信息系統(tǒng)的差別矩陣；步驟2 計算與差別矩陣相關(guān)的差別函數(shù)；步驟3 計算差別函數(shù)的最小析取范式，它將給出的所有約簡。解：步驟1 寫出的差別矩陣：步驟2 的差別函數(shù)為差別矩陣中下三角表示的個列構(gòu)成的合取范式。（把所有對象都區(qū)分開的屬性集）= 第一列 第二列 第三列最后一列將簡化利用邏輯運算中的吸收律= 步驟3 合取范式有結(jié)合律、交換律、合取對析取的分配律，但是，要求對每一列構(gòu)成的合取范式先化簡。即個大圓括號中的合取

10、式化簡。= =上述是不能再化簡的最小析取范式，每個合取式對應(yīng)的一個約簡：，上述算法，通常具有理論上的價值。表1101111211002310103410014511105611016表1是一張普通信息表，表1中每一行表示不同狀態(tài)的決策即每個個體看作是行為的不同狀態(tài)。有關(guān)屬性是否都必要呢？現(xiàn)在考慮屬性約簡。一、解法1數(shù)據(jù)分析法移去屬性，不出現(xiàn)相同的行，所以可約去；移去，則3與5不一致（即條件屬性值一樣，決策結(jié)果不同），所以是核屬性；移去，則2與5不一致，所以是核屬性；移去，則2與6不一致，所以是核屬性。故、中只有是可移去的，知是核，且核集自身是約簡，所以是唯一的最小約簡。二、解法2劃分等價類法屬

11、性、對劃分生成的等價類族為至： 由此得： 式表明屬性集能夠把個體一個一個區(qū)分開，故知識是充分的?？紤]對的劃分等價類，由得所以，與具有相同的分類能力。從中移去，由知不是約簡；移去，由知不是約簡；移去，不是約簡。故有唯一約簡。三、解法3差別矩陣法為清楚起見將從表1中提取的差別矩陣由表2表出。表2差別矩陣給定的差別矩陣為6階，其下三角由5列構(gòu)成，第（1）列中個差別元素的合取范式表示把個體分別與個體,（）區(qū)分開的屬性滿足的邏輯關(guān)系式。具體作法是按順序提取第1列，第2列，第列中的判別元素并構(gòu)成合取范式，對每列構(gòu)成的合取式用吸收律進行等價變換；將簡化后的個范式合取，進行第二輪化簡。例如，從差別矩陣中提取第

12、一列的差別元素構(gòu)成合取式為： 我們用邏輯運算中的吸收律對式進行等價變換。應(yīng)特別強調(diào)的一點是：變換必須是等價的。通俗點講就是：對第（在此）列差別元素構(gòu)成的合取式應(yīng)用吸收律時，對于能把個體與,區(qū)分開的不重復(fù)的所有屬性集一個不少的都求出來，而不僅僅是最?。〝?shù)目最少）屬性集；否則，不能保證最終求出的是約簡。例如，應(yīng)用吸收律簡化式時，顯然屬性能夠把個體與，都區(qū)分開，是最小屬性集；假若式簡化后為；顯然有：第2列差別元素合取范式可簡化為： 第3列差別元素的合取范式可簡化為： 第4列差別元素的合取范式可簡化為： 第5列差別元素的合取范式可簡化為： 將與、合取得 = 最終差別函數(shù)的化簡結(jié)果為，即得到一個約簡集。

13、由前面用數(shù)據(jù)分析計算結(jié)果知，本例有唯一約簡；顯然用差別矩陣求出的不是約簡。問題就出在：對第一列差別元素構(gòu)成的合取范式在應(yīng)用吸收律時，變換不是等價的。正確的作法如下： 由于的存在使得和可以被吸收；由于的存在可使與被吸收，所以，= 將式與、合取得= 則差別函數(shù)的最小簡化式為： = 即是唯一最小約簡，結(jié)論與前同。最初的錯誤結(jié)論源于在第一列差別元素合取范式用吸收律簡化時，漏了子句，使得變換不等價導(dǎo)致錯誤。所以，在對差別函數(shù)進行邏輯變換過程中，必須把個差別元素的合取式作為整體進行變換。這樣因為實行吸收率的范圍大而使簡化運算來得容易，在實施分配律時，應(yīng)選擇實行順序，方可使邏輯變換過程簡潔。結(jié)論用差別矩陣計

14、算約簡時，為了節(jié)省時空，可以省去寫出差別矩陣的中間環(huán)節(jié)，直接從信息表中依次提取第一至第列中差別元素并分別構(gòu)成合取式。并行地用吸收律簡化這個合取式；在保證變換等價前提下將并行計算得到的個簡化結(jié)果再合取。經(jīng)二次吸收（輔之合取的交換律、結(jié)合律，合取對析取分配律）將差別函數(shù)化為最簡析取范式，則析取范式的每個子句給出信息表的所有約簡，并且是約簡。但是，從第一列起：提取組由差別元素構(gòu)成的析取式作合取式，單獨對其用吸收律、分配律、結(jié)合律、交換律簡化時，未必“簡單”，比如，對式的簡化，就比較困難，稍有不慎將導(dǎo)致錯誤。而將個由差別元素（析取式）一并提出，以它們?yōu)樽泳錁?gòu)成合取式，把該合取式作為整體進行化簡，步驟為

15、：（1）觀察合取子句中是否有單個差別元素，若有則相同的保留一個，保留的單個差別元素作合取。同時去掉包含該單個差別元素的所有析取子句；若無則進行第二步。（2）觀察由兩個差別元素的析取式構(gòu)成的子句，相同的只保留一個，同時刪除包含著由兩個差別元素的析取式構(gòu)成的保留子句的所有析取式。（3）觀察由3個差別元素的析取式構(gòu)成的子句，當(dāng)所有個由析取式構(gòu)成的合取式中的所有析取式都被觀察過后第一輪簡化完畢。這時的合取式中，每個合取式或是單個差別元素或是兩個（不包含已有單個差別元素）差別元素的析取式或是由3個差別元素的析取式。第二輪化簡是應(yīng)用分配律將合取式化為析取式，每個析取式對應(yīng)一個約簡。§3 決策表屬

16、性約簡1 決策表設(shè)信息系統(tǒng)=中，屬性集，其中為條件屬性集，中含若干個條件屬性；為決策屬性集，其中含若干個決策屬性，最常見的是中只含一種決策屬性，這時。這時，信息系統(tǒng)稱作決策系統(tǒng)，簡稱決策表，記成。應(yīng)用中出現(xiàn)最多的是用決策表給出的信息系統(tǒng)。如表1，就是由決策表表達的一個知識表達系統(tǒng)。表1 決策表表達的知識表達系統(tǒng)110211212211321010421202512002表1中，論域，為條件屬性集，為決策屬性集，每個個體關(guān)于各屬性的屬性值在表中標出。表中每一行表示一條決策規(guī)則，比如第一條決策規(guī)則（即第一個個體關(guān)于各條件屬性與決策屬性取值的對應(yīng)關(guān)系）：含意是：當(dāng)個體關(guān)于,的取值分別為時，那么該個體

17、的決策屬性值為這作為一條決策規(guī)則。稱為決策規(guī)則的前件（條件部分）；稱為決策規(guī)則的后件（結(jié)論部分）。定義：如果和某條決策規(guī)則前件相同的所有其它決策規(guī)則，其后件也都與該條決策規(guī)則的后件相同，則稱該條決策規(guī)則是一致性規(guī)則，或協(xié)調(diào)規(guī)則；如果決策表中所有決策規(guī)則都是一致性決策規(guī)則，則稱決策表為一致性決策表，否則稱為不一致性決策表。決策表是一致的表明：條件等價類都包含于決策等價類中或說條件屬性完全決定了個體分類，記作；若決策表不一致，則說明存在這樣的條件等價類，其中的個體被劃分到不同的決策等價類中，這是條件屬性集不能完全決定個體的決策分類或說決策屬性集只是對條件屬性集部分依賴。2 決策表約簡中的基本概念設(shè)

18、為決策表，其中為論域，為條件屬性集，為決策屬性集。條件屬性集中所有等價關(guān)系的交記為，它把論域劃分成的等價類族記為：決策屬性集中所有等價關(guān)系的交記成，它把論域劃分成的等價類族為：等價類是的子集，的正域為=即是由對劃分等價類中完全包含在中的那些等價類的并集，所以，的正域中樣本可以按條件屬性精確分類。定義1 稱為的正域。描述的是條件屬性集對論域的劃分生成的等價類中完全包含于決策屬性集對論域劃分生成的等價類中的那些等價類（中包含的元素）的并集。中的元素由于都包含于的等價類中，所以都能被準確分類，即都能通過條件屬性集劃入分類。定義2 在知識下，能確切地劃入類的對象在論域中所占的百分比稱為根據(jù)，的近似分類

19、質(zhì)量，用表示。則定義3 稱 為根據(jù)，的近似分類精度。分類精度描述的是使用知識對對象分類時，可能的決策中正確決策的百分比。定義4 設(shè)為決策表，為條件屬性集，為決策屬性集。，若，則稱是上的可約去的；否則，是上不可約去的。定義5 若，如果上的每個等價關(guān)系都是上不可約去的，則稱關(guān)于是獨立的。定義6 等價關(guān)系是的約簡，當(dāng)且僅當(dāng)是的獨立子族并且 定義7 所有中不可約去的等價關(guān)系的集合，被稱為的核，記成命題1 為決策表，是條件屬性集中所有的約簡構(gòu)成的約簡族，是的核，則=注意幾個符號：的正域：的等價類，含于的等價類，由導(dǎo)入的約簡：在條件下，對約簡的核：在下的核例1 設(shè)為決策表，為條件屬性集且，為決策屬性集，已

20、知：，求的約簡。解 第一步：求的劃分等價類：第二步：求的正域，=第三步：為了計算的約簡，先確定中的核屬性，即從中哪個屬性是不可約去的。 因為=，所以，是中不可約去的。 因為=，所以，是中可約去的。最后去掉，得，所以，是中不可約去的。于是，的核為，它是唯一的的約簡。上述求的約簡過程中，先求的核，具體作法是：從中刪去一屬性后觀察是否改變的正域。知識的約簡是知識的最小子集，它提供的個體到知識的基本類與整體知識提供的個體到知識的基本類相同；本例中的約簡只有一個，這時，當(dāng)分類個體為知識的基本類時，利用知識來描述有唯一一種方法；如果知識有多個約簡，則利用知識分類個體為的基本類存在多種方法。關(guān)鍵語：按決策屬

21、性分類是已知的，那么，這些分類有哪些能用條件屬性去描述呢？而且是最少的條件屬性。這就要求的約簡。上面給出了求的約簡的具體算法，但比較煩索。下面利用決策表表達知識的特殊形式，簡化求核屬性的作法，在表中去掉一種條件屬性，看決策規(guī)則是否產(chǎn)生新的不一致。給定一個決策表，如，T如表1所示：表1 決策表AUabcde123451221101122202201101010212決策表1顯然是一致性決策表，因為表中每一條決策規(guī)則都是一致的。我們主要討論一致性決策表，但不一致的決策規(guī)則也是有用的。在后面的應(yīng)用中會看到這一點。對于一個一致性決策表，我們的問題是：決策規(guī)則中的條件屬性是否都是必要的，不必要的應(yīng)消去。

22、再者，每一條決策規(guī)則中的條件屬性值是否都是必要的，無關(guān)的應(yīng)消去。前者稱為屬性約簡，后者稱為屬性值約簡。因此，對一致性決策表的簡化分兩步：1. 屬性約簡：它等價于從決策表中消去一些不必要的列；2. 屬性值約簡：對于表中的每一條決策規(guī)則，消去一些無關(guān)緊要的屬性值。對決策表的屬性約簡，有下述定理:定理1 從決策表中，將條件屬性C中屬性逐個移去，每移去一個屬性即刻檢查其決策表，如果不出現(xiàn)新的不一致則該屬性是可以被約去的；否則，該屬性不能被約去，即該屬性必是C的D核屬性。稱這種方法為屬性約簡的數(shù)據(jù)分析法。在決策表約簡的基本概念中定義了D的C正域，C的D核，其中是C中的所有D約簡族。下面來證明，如果從C中

23、移去一屬性比如a，其決策表將出現(xiàn)新的不一致，則該屬性必是C的D核屬性，是不能被約簡的。證明：不妨討論一致性決策表。假如移去a屬性決策表將出現(xiàn)新的不一致，這種新的不一致是因?qū)傩灾狄鸬?，即至少有兩個個體（不妨設(shè)為）的a屬性值不同其余的條件屬性值均相同，但與的決策屬性值不同。這樣與因a屬性被刪除將被劃分到的同一個等價類中。即原來不在一個等價類中的個體，因a屬性刪除被劃分到同一個等價類中。另一方面，因為與的屬性值不同，所以，將被劃分到C的不同等價類中，如果與個體（或）的各條件屬性值相同的僅有（和）（即一致性決策表T中相同的行只有一行，否則可以去掉其它相同行只保留（或）所在行，那么，C的包含（或）的等

24、價類中只有（或）一個元素。顯然，只包含（或）的等價類被包含在中，可見。故屬性是不能被約去的，即必是C關(guān)于D的核屬性，證畢。這樣，在決策表T中，當(dāng)移去屬性后，決策表出現(xiàn)新的不一致性，就可確定是C關(guān)于D的核屬性。由此，可求出C的D核?？梢?，定理1給出了求相對核的方法，而不用先求C的D約簡族，再通過求C的D核?，F(xiàn)在按此算法求決策表中C的D核及C關(guān)于D的全部約簡。對決策表1，表1 一致性決策表AUabcde123451221101122202201101010212解法一：由于表1中不存在條件屬性值相同的行，顯然，表1是一致性決策表。從表中移去條件屬性a，則決策表不出現(xiàn)新的不一致，即兩個個體的條件屬性

25、值相同而決策屬性值不同，故條件屬性a是可以被約去的；從表中移去b，也不出現(xiàn)新的不一致性，所以b也是可以被約去的；從表中移去c，所得決策表是不一致的，因為第二、三條決策規(guī)則出現(xiàn)不一致，所以，條件屬性是a,b,c關(guān)于D=d,e的核，而a,b都是可以約去的非核屬性。但是，核屬性自身不構(gòu)成約簡。因為：去掉后的規(guī)則1，3不協(xié)調(diào)；2，5不協(xié)調(diào)。而、均是約簡。由此得兩個約簡： ， 解法二：下面通過的正域求相對核、相對約簡。決策屬性D、各條件屬性對論域U的劃分分別為：U/D=1,4,2,3,5U/a=1,4,5,2,3，U/b=1,2,3,4,5，U/c=1,3,4,2,5所以U/C=1,4,5,2,3，由此

26、得=1,3,2,4,5，所以a是可約去的，即a不是核屬性。=1,4,5,2,3，所以b是可約去的，即b不是核屬性。=1,4,5,2,3，所以，從C中去掉后改變了D的C正域，所以屬性c不能約去，c是核屬性。那么a,c與b,c能否構(gòu)成D的約簡呢？這是顯然的。因為a,c是獨立的，b,c也是獨立的，即從中去掉任何一屬性將改變D的C正域；a,c，b,c與C具有同樣的對D的劃分能力。這樣，從兩個角度計算了相對核與相對約簡，故在求決策表的相對核與相對約簡時，有兩個途境：從D的C正域考慮；用移去某一屬性列的數(shù)據(jù)分析方法考慮。比較相對約簡的兩條途境，易見，數(shù)據(jù)分析法（即解法一）相對來說操作簡單，所以，對決策表T

27、的簡化通常采用數(shù)據(jù)分析法。§4 決策表屬性約簡的差別矩陣方法前面針對信息表定義了其差別矩陣及與對應(yīng)的差別函數(shù)。通過吸收律，合取范式的結(jié)合律、交換律，合取關(guān)于析取式的分配律將由差別元素的析取式表示的所有子句組成的合取式化成最簡析取范式，則每個最簡析取范式對應(yīng)的一個約簡。由此給出針對信息表的計算約簡的一種算法。現(xiàn)在給出針對決策表的差別矩陣概念。設(shè)為決策系統(tǒng)，其中為論域，為條件屬性集，為決策屬性集，對于，任意，為個體在屬性上的值，為的值域。決策表的差別矩陣定義為：其中是中第行第列上的元素，稱做差別元素，其表達式為：=其中。上述定義表明：的第行第列上的差別元素是條件屬性構(gòu)成的集合或數(shù)值0。（1）當(dāng)與的決策屬性值不同時，那么使與有不同值的所有條件屬性構(gòu)成差別元素，