計算智能與深度學(xué)習(xí) 課件 10粗糙集

第11章粗糙集方法第11章粗糙集方法11.1基本概念11.2信息系統(tǒng)和決策表及其約簡11.3基于粗糙集的分類器設(shè)計11.1基本概念1近似空間2近似與粗糙集3粗糙集的特征描述4知識約簡5知識的依賴性提出背景粗糙集（RoughSet）理論是波蘭數(shù)學(xué)家Z.Pawlak于1982年提出的，是一種新的處理含糊性（Vagueness）和不確定性（Uncertainty）問題的數(shù)學(xué)工具。

粗糙集理論的主要優(yōu)勢之一就在于它不需要關(guān)于數(shù)據(jù)的任何預(yù)備的或額外的信息。粗糙集理論已廣泛應(yīng)用于知識發(fā)現(xiàn)、機器學(xué)習(xí)、決策支持、模式識別、專家系統(tǒng)、歸納推理等領(lǐng)域。

1991年，Z.Pawlak教授撰寫了第一本關(guān)于粗糙集理論的專著《RoughSets——TheoreticalAspectsofReasoningaboutData》。

1992年在波蘭召開了第一屆國際粗糙集研討會，以后每年都有以粗糙集理論為主題的國際研論會。

1995年，第11期的ACMCommunication將粗糙集列為人工智能及認(rèn)知科學(xué)領(lǐng)域新浮現(xiàn)的研究課題，并發(fā)表了Pawlak等人的《RoughSets》一文。

1.近似空間設(shè)U為所討論對象的非空有限集合，稱為論域；R為建立在U上的一個等價關(guān)系，稱二元有序組AS=(U,R)為近似空間（ApproximateSpace）。近似空間構(gòu)成論域U的一個劃分；若R是U上的一個等價關(guān)系，以[x]R表示x的R等價類，U／R表示R的所有等價類構(gòu)成的集合，即商集；R的所有等價類構(gòu)成U的一個劃分，劃分塊與等價類相對應(yīng)。（1）不可分辨關(guān)系令R為等價關(guān)系族，設(shè)P

R，且P

，則P中所有等價關(guān)系的交集稱為P上的不可分辨關(guān)系（IndiscernibilityRelation），記作IND(P)，即有：

顯然IND(P)也是等價關(guān)系。

（2）知識與知識庫

粗糙集理論將分類方法看成知識，分類方法的族集是知識庫。

等價關(guān)系對應(yīng)論域U的一個劃分，即關(guān)于論域中對象的一個分類，

從而不可分辨關(guān)系對應(yīng)論域U上的知識。稱論域U的子集為U上的概念（Concept），約定

也是一個概念，概念的集合稱為U上的知識；U上知識（分類）的族集構(gòu)成關(guān)于U的知識庫，也就是說，知識庫是分類方法的集合。

（2）知識與知識庫（續(xù)）設(shè)U為論域，R為等價關(guān)系族，P

R且P

，則不可分辨關(guān)系IND(P)的所有等價類的集合，即商集U／IND(P)稱為U的P基本知識，相應(yīng)等價類稱為知識P的基本概念。特別地，若等價關(guān)系Q

R，則稱U／Q為U的Q初等知識，相應(yīng)等價類稱為Q初等概念。由于選取R的不同子集P可以得到U上的不同知識，故稱K=(U,R)為知識庫（KnowledgeBase）。

為簡單起見，用U／P代替U／IND(P)。

2近似與粗糙集

（1）下近似與上近似設(shè)集合X

U，R是一個等價關(guān)系，定義：

RX為X的R下近似集（LowerApproximation）

為X的R上近似集（UpperApproximation）

下近似與上近似（續(xù)）稱集合BNR(X)=–RX為X的R邊界域；POSR

(X)=RX為X的R正域；NEGR(X)=U–為X的R負(fù)域。

（2）粗糙集當(dāng)BNR(X)=

時，即RX=

時，稱X是R精確集（或R可定義集）。當(dāng)BNR(X)

時，即RX

時，稱X為R粗糙集（或R不可定義集）。

若集合X是粗糙集，則X對應(yīng)一個粗糙概念，只能通過一對精確概念（即下近似集和上近似集）“近似”地描述。

（3）粗糙集的基本性質(zhì)R下近似和R上近似滿足下述性質(zhì)：

3粗糙集的特征描述

（1）刻畫粗糙集的方法有2種刻畫粗糙集的方法：

用近似精度（數(shù)值）表示粗糙集的數(shù)字特征；數(shù)字特征表示粗糙集邊界域的相對大小，但沒有說明邊界域的結(jié)構(gòu)。

用粗糙集的拓?fù)浞诸惐硎敬植诩耐負(fù)涮卣?。拓?fù)涮卣鹘o出邊界域的結(jié)構(gòu)信息，但沒有給出邊界域大小的信息。

（2）近似精度與粗糙度

由等價關(guān)系R定義的集合X的近似精度定義為：

其中X

，∣X∣表示集合X的基數(shù)，顯然，0≤αR(X)≤1。定義ρR(X)=1–αR(X)，稱ρR(X)為X的R粗糙度。粗糙度反映了利用知識R近似表示X的不完全程度。

(3）粗糙隸屬函數(shù)

R粗糙隸屬函數(shù)定義為：

顯然

的值可解釋為x隸屬于集合X的不確定程度。

（4）拓?fù)涮卣?/p>

設(shè)X是一個R粗糙集，

稱X是R粗糙可定義的，當(dāng)且僅當(dāng)

；稱X是R內(nèi)不可定義的，當(dāng)且僅當(dāng)

；稱X是R外不可定義的，當(dāng)且僅當(dāng)

；稱X是R全不可定義的，當(dāng)且僅當(dāng)

；數(shù)字特征和拓?fù)涮卣鞯穆?lián)系粗糙集的數(shù)字特征（近似精度）和拓?fù)涮卣髦g有一定的聯(lián)系：若集合是內(nèi)不可定義的或全不可定義的，則其近似精度為0；若集合是外不可定義的或全不可定義的，則其補集的近似精度為0。實際應(yīng)用時，應(yīng)綜合考慮邊界域的兩種信息。

4.知識約簡

知識庫中可能含有冗余的知識，知識約簡研究知識庫中哪些知識是必要的，以及在保持分類能力不變的前提下，刪除冗余的知識。

知識約簡是粗糙集理論的核心內(nèi)容之一，在數(shù)據(jù)挖掘領(lǐng)域具有重要的應(yīng)用意義。

（1）約簡和核

設(shè)R是一個等價關(guān)系族，R

R。若IND(R)=IND(R–{R})，則稱R為等價關(guān)系族R中可省的，否則稱為不可省的。若R中任意一個等價關(guān)系R都是不可省的，則稱R是獨立的，否則稱為依賴的。

設(shè)Q

P，若Q是獨立的，且IND(Q)=IND(P)，則稱Q是等價關(guān)系族P的一個約簡（Reduct）。P中所有不可省關(guān)系的集合稱為等價關(guān)系族P的核（Core），記作CORE(P)。

顯然，P可以有多個約簡，以RED(P)表示P的所有約簡的集合。

（2）約簡和核的關(guān)系定理：等價關(guān)系族P的核等于P的所有約簡的交集，即有：

CORE(P)=

RED(P)定理的意義在于:核可以作為所有約簡的計算基礎(chǔ)，并且計算是直接的；核可以解釋為知識庫中最重要的部分，是知識約簡時不能消去的知識。

（3）相對約簡和相對核

相對約簡和相對核的概念反映了一個分類與另一個分類的關(guān)系。

相對約簡的概念是通過正域定義的。①正域設(shè)P和Q為論域U上的等價關(guān)系，Q的P正域記作POSP(Q)，定義為：

Q的P正域是U中所有可以根據(jù)分類（知識）U／P的信息準(zhǔn)確分類到關(guān)系Q的等價類中去的對象構(gòu)成的集合。

②等價關(guān)系的可省性設(shè)P和Q為論域U上的等價關(guān)系族，R

P，若

則稱R為P中Q可省的，否則稱R為P中Q不可省的。若P中的任一關(guān)系R都是Q不可省的，則稱P是Q獨立的（相對于Q獨立）。注意：為簡便起見，可以用POSP(Q)代替

POSIND(P)(IND(Q))。

③相對約簡與相對核設(shè)S

P，稱S為P的Q約簡，當(dāng)且僅當(dāng)S是P的Q獨立子族，且POSS(Q)=POSP(Q)。P中所有Q不可省的原始關(guān)系構(gòu)成的集合稱為P的Q核，記作COREQ(P)。

P的所有Q約簡構(gòu)成的集合記作REDQ(P)，P的Q約簡稱為相對約簡，P的Q核稱為相對核。

④相對約簡與相對核的關(guān)系定理：P的Q核等于P的所有Q約簡的交集

COREQ(P)=

REDQ(P)P的Q核是知識P的本質(zhì)部分。為了保證將對象分類到Q的概念中去的分類能力不變，Q核知識是不可消去的。

知識P的Q約簡是P的子集，該子集是Q獨立的，且具有與知識P相同的分類能力（把對象分類到知識Q的概念中去）。

⑤一般約簡與相對約簡請注意一般約簡和相對約簡的區(qū)別：一般約簡是在不改變對論域中對象的分類能力的前提下消去冗余知識；而相對約簡是在不改變將對象劃分到另一個分類中去的分類能力的前提下消去冗余知識。5.知識的依賴性知識庫中的知識并不是同等重要的，有些知識可以由其他知識導(dǎo)出。

設(shè)K=(U,R)為知識庫，P,Q

R，

知識Q依賴于知識P，記作P

Q，當(dāng)且僅當(dāng)IND(P)

IND(Q)知識P與知識Q等價，記作P

Q，當(dāng)且僅當(dāng)P

Q，且Q

P

知識P與知識Q獨立，記作P

Q，iifP

Q與Q

P均不成立

當(dāng)知識Q依賴于知識P時，也稱知識P可推導(dǎo)出知識Q。P

Q當(dāng)且僅當(dāng)IND(P)=IND(Q)。

①知識的部分依賴性知識的依賴性也可能是部分的，也就是說，知識P可部分地推導(dǎo)出知識Q。知識Q部分依賴于知識P可由知識的正域來定義。

①知識的部分依賴性設(shè)K=(U,R)為一個知識庫，且P,Q

R，令

稱知識Q依賴于知識P，依賴度為k，記作P

kQ。

顯然0≤k≤1。當(dāng)k=1時，稱知識Q完全依賴于知識P，P

1Q也簡記為P

Q；

當(dāng)0<k<1時，稱知識Q部分依賴于知識P；當(dāng)k=0時，稱知識Q完全獨立于P。

依賴度k反映了根據(jù)知識P將對象分類到知識Q的基本概念中去的能力。當(dāng)P

kQ時，論域中共有k∣U∣個屬于Q的P正域的對象，這些對象可以依據(jù)知識P分類到知識Q的基本概念中去。

11.2信息系統(tǒng)和決策表及其約簡1信息系統(tǒng)2決策表3決策規(guī)則1.信息系統(tǒng)稱4元有序組S=(U,A,V,f)為信息系統(tǒng)，其中

U為對象的非空有限集合，稱為論域；

A為屬性的非空有限集合；，為屬性a的值域；

f:U

A

V是一個信息函數(shù)，

x

U，a

A，f(x,a)

Va，對于給定對象x，f(x,a)賦予對象x在屬性a下的屬性值。信息系統(tǒng)也可簡記為S=(U,A)。

信息系統(tǒng)可以用數(shù)據(jù)表格來表示，表格的行對應(yīng)論域中的對象，列對應(yīng)描述對象的屬性。一個對象的全部信息由表中一行屬性的值來反映。

①信息系統(tǒng)實例②屬性子集P導(dǎo)出的二元關(guān)系設(shè)P

A且P

，定義由屬性子集P導(dǎo)出的二元關(guān)系如下：

IND(P)={(x,y)|(x,y)

U

U,

a

P,f(x,a)=f(y,a)}

可以證明IND(P)是等價關(guān)系，稱其為由屬性集P導(dǎo)出的不可分辨關(guān)系。

若(x,y)

IND(P)，則稱x和y是P不可分辨的，即依據(jù)P中所含各屬性無法將x和y區(qū)分開。

③屬性a導(dǎo)出的等價關(guān)系若定義由屬性a

A導(dǎo)出的等價關(guān)系為：

則P

A導(dǎo)出的不可分辨關(guān)系亦可定義為：

給定信息系統(tǒng)S=(U,A)，A的每個屬性對應(yīng)一個等價關(guān)系，而屬性子集對應(yīng)不可分辨關(guān)系。信息系統(tǒng)與一個知識庫相對應(yīng)，因此一個數(shù)據(jù)表格可以看成一個知識庫。前幾節(jié)討論的知識依賴性、知識約簡等問題，在信息系統(tǒng)中可以轉(zhuǎn)化為屬性依賴性、屬性的約簡等問題。

④分辨矩陣令S=(U,A,V,f)為一信息系統(tǒng)，論域U中元素的個數(shù)∣U∣=n，∣A∣=m，S的分辨矩陣M定義為一個n階對稱矩陣，其i行j列處元素定義為：

即mij是能夠區(qū)別對象xi和xj的所有屬性作為元素所構(gòu)成的集合。

⑤分辨函數(shù)對于每一個a

A，指定布爾變量，將信息系統(tǒng)的分辨函數(shù)定義為一個m元布爾函數(shù)，形式如下：

即ρ為(

mij)的合取，而(

mij)為mij中各屬性對應(yīng)的布爾變量的析取。

分辨函數(shù)的析取范式中的每一個合取式對應(yīng)一個約簡。

實例信息系統(tǒng)的分辨矩陣與分辨函數(shù)約簡后的信息系統(tǒng)信息系統(tǒng)有兩個約簡{a,b}和{b,d}，核是。得到兩個約簡的數(shù)據(jù)表格如下表所示：2.決策表設(shè)S=(U,A,V,f)為信息系統(tǒng)，若A可劃分為條件屬性集C和決策屬性集D，即C

D=A，C

D=

，則稱信息系統(tǒng)為決策表（DecisionTable）。IND(C)的等價類稱為條件類，IND(D)的等價類稱為決策類。

①決策表的分類

稱決策表是一致的當(dāng)且僅當(dāng)D依賴于C，即C

D；

稱決策表是不一致的當(dāng)且僅當(dāng)C

kD（0<k<1）；

②決策表實例設(shè)論域U={x1,

x2,…,x7}，屬性集A=C

D，條件屬性集C={a,b,c,d}，決策屬性集D={e}③決策表的分辨矩陣決策表的分辨矩陣是一個對稱的n階方陣，其元素定義為：

④決策表的分辨函數(shù)決策表的分辨函數(shù)定義如下：函數(shù)ρ*的極小析取范式中各個合取式分別對應(yīng)C的D約簡。實例決策表的分辨矩陣實例決策表的分辨函數(shù)實例決策表的約簡C的D約簡有兩個，分別為{b,c}和{b,d}，C的D核為。實例決策表可以約簡為如下兩表：

3.決策規(guī)則設(shè)S=(U,A,V,f)是決策表，A=C

D，C為條件屬性集，D為決策屬性集。令Xi和Yj分別表示條件類和決策類。

Des(Xi)表示條件類Xi的描述，定義為：

Des(Xi)={(a,va)|f(x,a)=va,

a

C}

Des(Yj)表示決策類Yj的描述，定義為：

Des(Yj)={(a,va)|f(x,a)=va,

a

D}決策規(guī)則定義為：

Tij:Des(Xi)