模式識(shí)別與智能計(jì)算楊淑瑩天津理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院第八章粗糙集分類器設(shè)計(jì)8.1粗糙集理論的基本概念8.2粗糙集在模式識(shí)別中的應(yīng)用8.3粗糙集理論的分類方法

8.1粗糙集理論的基本概念知識(shí)表達(dá)系統(tǒng)：

知識(shí)表達(dá)系統(tǒng)可用一個(gè)四元組S表示：式中,為一個(gè)非空有限對(duì)象的集合，稱為論域＝｛X1，X2，…，XN｝,其中Xi為對(duì)象；R為對(duì)象的屬性集合；V為屬性值的集合，Va是屬性a∈R的值域；f為R—>V的一個(gè)信息函數(shù)，它為每個(gè)對(duì)象X的每個(gè)屬性a賦予一個(gè)屬性值,即

a∈R，X∈,fa(X)∈Va。8.1粗糙集理論的基本概念決策表：設(shè)

是一個(gè)信息系統(tǒng)（知識(shí)表達(dá)系統(tǒng)），R＝C∪D，C稱為條件屬性集合，D稱為決策屬性集。具有條件屬性和決策屬性的信息系統(tǒng)稱為決策表。

8.1粗糙集理論的基本概念等價(jià)關(guān)系：

設(shè)A代表某種屬性集合。a代表屬性中的某一種取值。如果有兩個(gè)樣品Xi，Xj滿足如下關(guān)系：對(duì)于

，它們的屬性值相同，即fa（Xi）＝fa（Xj）成立，稱對(duì)象Xi和Xj是對(duì)屬性A的等價(jià)關(guān)系，表示為可見屬性值相同的兩個(gè)樣品之間的關(guān)系為等價(jià)關(guān)系。8.1粗糙集理論的基本概念等價(jià)集：

在中，對(duì)屬性集A中具有相同等價(jià)關(guān)系的元素集合成為等價(jià)關(guān)系IND（A）

的等價(jià)集，［X］A表示在屬性A下與X具有等價(jià)關(guān)系的元素集合。

8.1粗糙集理論的基本概念等價(jià)劃分：

從所采集的訓(xùn)練集中把屬性值相同的樣品聚類，形成若干個(gè)等價(jià)集，構(gòu)成A集合。在中對(duì)屬性A的所有等價(jià)集形成的劃分表示為具有特性：①Ei≠?；

②當(dāng)i≠j時(shí)，Ei∩Ej＝?；

③

＝∪Ei。8.1粗糙集理論的基本概念

［例1］設(shè)

＝｛a（血壓正常），b（血壓正常），c（血壓正常），d（血壓高），e（血壓高），f（血壓很高）｝，

對(duì)于屬性A（血壓）的等價(jià)關(guān)系有

IND（A）＝｛（a，b），（a，c），（b，c），（d，e），（a，a），（b，b），（c，c），（d，d），（e，e），（f，f）｝

屬性A的等價(jià)集有E1＝［a］A＝［b］A＝［c］A＝｛a，b，c｝

E2＝［d］A＝［e］A＝｛d，e｝

E3＝［f］A＝｛f｝

中對(duì)屬性A的劃分為A＝｛E1，E2，E3｝

＝｛｛a，b，c｝，｛d，e｝，｛f｝｝8.1粗糙集理論的基本概念上近似集和下近似集：

下近似集定義：對(duì)任意一個(gè)決策屬性的等價(jià)集

，屬性A的等價(jià)集

，有或表示等價(jià)集Ei＝［X］A中的元素X都屬于Y，即

，則X一定屬于Y。A_（Y）表示下近似集。8.1粗糙集理論的基本概念上近似集定義：對(duì)任意一個(gè)決策屬性的等價(jià)集

，屬性A的等價(jià)集Ei=[X]A，有或表示等價(jià)集Ei＝［X］A中的元素X可能屬于Y，即

，則X可能屬于Y，也可能不屬于Y。A—（Y）表示上近似。8.1粗糙集理論的基本概念正域、負(fù)域和邊界的定義：全集可以劃分為3個(gè)不相交的區(qū)域，即正域（POSA）、負(fù)域（NEGA）和邊界（BNDA）：正域：POSA（Y）＝A_(Y)負(fù)域：邊界：由此可見：8.1粗糙集理論的基本概念從圖8-1中可以看出：任意一個(gè)元素X∈POS（Y），一定屬于Y；任意一個(gè)元素X∈NEG（Y），一定不屬于Y；集合Y的上近似是其正域和邊界的并集，即對(duì)于元素X∈BND（Y），無法確定其是否屬于Y，因此對(duì)于任意元素X∈A—（Y），只知道X可能屬于Y。

圖8-1Y關(guān)于屬性A的正域、負(fù)域和邊界8.1粗糙集理論的基本概念粗糙集：若A—（Y）＝A_（Y），即BNDA（Y）＝?，即邊界為空，稱Y為A的可定義集；否則Y為A的不可定義集，即A—（Y）≠A_（Y），稱Y為A的粗糙集（Roughset）。8.1粗糙集理論的基本概念確信度：確信度αA（Y）表示為其中||和｜A—（Y）-A_（Y）｜分別表示集合

、A—（Y）-A_（Y）中的元素個(gè)數(shù)。確信度性質(zhì)：0≤αA（Y）≤18.1粗糙集理論的基本概念相對(duì)正域：設(shè)決策屬性D的劃分Y＝（Y1，Y2，…YM），條件屬性C相對(duì)于決策屬性D的正域定義為POS（C，D）＝∪C_（Yi）8.1粗糙集理論的基本概念決策表的一致性：

決策表中的對(duì)象X按條件屬性與決策屬性關(guān)系看做一條決策規(guī)則，寫成

∧fCi（X）＝fD（X）式中，Ci表示多個(gè)條件屬性；D表示決策屬性；fCi（X）表示對(duì)象X在Ci的取值；∧表示邏輯“與”關(guān)系。（1）一致性決策規(guī)則定義如果對(duì)任一個(gè)對(duì)象Xi≠Xj，若條件屬性有fCi（Xi）＝fCi（Xj），則決策屬性必須有fD（Xi）＝fD（Xj），即一致性決策規(guī)則說明條件屬性取值相同時(shí)，決策屬性取值必須相同。該定義允許：若條件屬性有fCi（Xi）≠fCi（Xj），則決策屬

性可以是fD（Xi）＝fD（Xj）或fD（Xi）≠fD（Xj）。

（2）決策表一致的定義在決策表中如果所有對(duì)象的決策規(guī)則都是一致的，則該信息表示一致的，否則信息表示不一致的。在進(jìn)行屬性約簡(jiǎn)時(shí)，每約簡(jiǎn)掉一個(gè)屬性時(shí)要檢查決策表，若保持一致性，則可以刪除，否則不可以刪除。8.1粗糙集理論的基本概念8.1粗糙集理論的基本概念屬性約簡(jiǎn)：

（1）屬性依賴度：決策表中決策屬性D依賴條件屬性C的依賴度定義為

γ（C，D）＝｜POS（C，D）｜/｜｜式中，｜POS（C，D）｜為正域POS（C，D）元素的個(gè)數(shù)，｜｜

為整個(gè)對(duì)象集合的個(gè)數(shù)。γ（C，D）的性質(zhì)如下：①若γ＝1，表示在已知條件C下，可以將

上全部個(gè)體分類到?jīng)Q策屬性D的類別中去。②γ＝0，即利用條件C不能分類到?jīng)Q策屬性D的類別中去。③0＜γ＜1，即在已知條件C下，只能將

上那些屬于正域的個(gè)體分類到?jīng)Q策屬性D的類別中去。8.1粗糙集理論的基本概念屬性約簡(jiǎn)：

（2）屬性重要度：C，D?A，C為條件屬性集，D為決策屬性集，a∈C，屬性a關(guān)于D的重要度定義為SGF（a，C，D）＝γ（C，D）-γ（C-｛a｝，D）式中，γ（C-｛a｝，D）表示在C中缺少屬性a后，條件屬性與決策屬性的依賴程度；SGF（a，C，D）表示C中缺少屬性a后，導(dǎo)致不能被準(zhǔn)確分類的對(duì)象在系統(tǒng)中所占的比例。SGF（a，C，D）的性質(zhì)：①SGF（a，C，D）∈［0，1］。②SGF（a，C，D）＝0，表示屬性a關(guān)于D是可約簡(jiǎn)的。③SGF（a，C，D）≠0，表示屬性a關(guān)于D是不可約簡(jiǎn)的。8.1粗糙集理論的基本概念屬性約簡(jiǎn)：

（3）最小屬性集概念：設(shè)C，D分別是信息系統(tǒng)S的條件屬性集和決策屬性集，若屬性集P（P?C）是C的一個(gè)最小屬性集，當(dāng)且僅當(dāng)γ（P，D）＝γ（C，D）并且

時(shí)，則P具有與C同樣的區(qū)分決策類的能力。8.1粗糙集理論的基本概念規(guī)則獲取：

通過分析中的兩個(gè)劃分C＝｛Ei｝和D＝｛Yj｝之間的關(guān)系，把C視為分類條件，D視為分類結(jié)論，可以得到下面的分類規(guī)則：①當(dāng)Ei∩Yj≠?時(shí)，則有：rij：Des（Ei）→Des（Yj）

Des（Ei）和Des（Yj）分別是等價(jià)集Ei和等價(jià)集Yj中的特征描述：當(dāng)Ei∩Yj＝Ei時(shí)，即下近似，建立的規(guī)則rij是確定的，規(guī)則的可信度cf＝1。當(dāng)Ei∩Yj≠Ei時(shí)，即上近似，建立的規(guī)則rij是不確定的，規(guī)則的可信度為②當(dāng)Ei∩Yj＝?時(shí)，Ei和Yj不能建立規(guī)則。8.2粗糙集在模式識(shí)別中的應(yīng)用表8-1決策表樣例8.2粗糙集在模式識(shí)別中的應(yīng)用等價(jià)集、下近似集和依賴度的計(jì)算：（1）條件屬性C（a，b，c）的等價(jià)集E1｛e1｝，E2｛e2｝，E3｛e3｝，E4｛e4｝，E5｛e5｝，E6｛e6｝，E7｛e7｝，E8｛e8｝（2）決策屬性D（d）的等價(jià)集Y1：｛e1，e4，e5，e8｝，Y2：｛e2，e3，e6，e7｝8.2粗糙集在模式識(shí)別中的應(yīng)用等價(jià)集、下近似集和依賴度的計(jì)算：（3）決策屬性的各等價(jià)集的下近似集C—Y1＝｛e1，e4，e5，e8｝C—Y2＝｛e2，e3，e6，e7｝8.2粗糙集在模式識(shí)別中的應(yīng)用等價(jià)集、下近似集和依賴度的計(jì)算：（4）計(jì)算POS（C，D）和γ（C，D）POS（C，D）＝C—Y1∪C—Y2＝｛e1，e2，e3，e4，e5，e6，e7，e8｝｜POS（C，D）｜＝8，｜｜＝8，γ（C，D）＝1，表明在已知條件C（a，b，c）下，可將

上全部個(gè)體分類到?jīng)Q策屬性D的類別中。8.2粗糙集在模式識(shí)別中的應(yīng)用屬性約簡(jiǎn)：a的重要度計(jì)算條件屬性C（b，c）的等價(jià)集：E1｛e1，e4｝，E2｛e2｝，E3｛e3，e6｝，E4｛e5，e7｝，E5｛e8｝決策屬性D（d）的等價(jià)集仍為Y1和Y2。決策屬性的各等價(jià)集的下近似集：C—Y1＝｛e1，e4，e8｝C—Y2＝｛e2，e3，e6｝計(jì)算POS（C-｛a｝，D）和γ（C-｛a｝，D）：POS（C-｛a｝，D）＝C—Y1∪C—Y2＝｛e1，e2，e3，e4，e6，e8｝｜POS（C-｛a｝，D）｜＝6γ（C-｛a｝，D）＝6/8屬性a的重要程度：SGF（C-｛a｝，D）＝γ（C，D）-γ（C-｛a｝，D）＝1/4≠0結(jié)論：屬性a是不可省略的。8.2粗糙集在模式識(shí)別中的應(yīng)用8.2粗糙集在模式識(shí)別中的應(yīng)用表8-2簡(jiǎn)化決策表8.2粗糙集在模式識(shí)別中的應(yīng)用等價(jià)集、上下近似集的計(jì)算：①條件屬性的等價(jià)集：②決策屬性D（d）的等價(jià)集：8.2粗糙集在模式識(shí)別中的應(yīng)用獲取規(guī)則：8.2粗糙集在模式識(shí)別中的應(yīng)用規(guī)則化簡(jiǎn)：①對(duì)r11和r41進(jìn)行合并，有（a＝0∨a＝1）∧c＝0→d＝0其中a的取值包括了全部取值，故屬性a可以刪除，即c＝0→d＝0②對(duì)r32和r62進(jìn)行合并，有（a＝0∨a＝1）∧c＝2→d＝1同樣，可以刪除屬性a，得到c＝2→d＝18.2粗糙集在模式識(shí)別中的應(yīng)用最后的規(guī)則：①發(fā)燒＝正?！忻埃椒?，即c＝0→d＝0②咳嗽＝否∧發(fā)燒＝低燒→感冒＝否，即a＝0∧c＝1→d＝0③發(fā)燒＝高燒→感冒＝是，即c＝2→d＝1④咳嗽＝是∧發(fā)燒＝低燒→感冒＝是，即a＝1∧c＝1→d＝1對(duì)于一個(gè)條件屬性已知，決策屬性未知的新對(duì)象，利用最后獲取的規(guī)則，可以得到該對(duì)象的決策屬性，實(shí)現(xiàn)模式分類。8.3粗糙集理論的分類方法決策表構(gòu)造：8.3粗糙集理論的分類方法規(guī)則訓(xùn)練：規(guī)則訓(xùn)練是指利用粗糙集理論，通過對(duì)決策表進(jìn)行條件屬性約簡(jiǎn)、決策規(guī)則約簡(jiǎn)，獲取最小決策規(guī)則，作為最終分類規(guī)則。（1）等價(jià)集、下近似集和依賴度的計(jì)算（2）屬性約簡(jiǎn)（3）等價(jià)集計(jì)算（4）獲取規(guī)則（5）規(guī)則化簡(jiǎn)

8.3粗糙集理論的分類方法分類判別：利用訓(xùn)練好的規(guī)則，對(duì)待測(cè)樣品X，已知其條件屬性（即特征），在訓(xùn)練規(guī)則中檢索，找到符合規(guī)則，其決策屬性即為其類別。8.3粗糙集