粗糙集與數(shù)據(jù)約簡

1、智能信息處理技術(shù)智能信息處理技術(shù)第第4章章 粗糙集與數(shù)據(jù)約簡粗糙集與數(shù)據(jù)約簡 不確定性理論不確定性理論1 粗糙集的基本理論與方法粗糙集的基本理論與方法2 知識的約簡知識的約簡3 決策表的約簡決策表的約簡4 粗糙集數(shù)據(jù)約簡的具體實現(xiàn)與應(yīng)用粗糙集數(shù)據(jù)約簡的具體實現(xiàn)與應(yīng)用5 粗糙集的研究現(xiàn)狀與展望粗糙集的研究現(xiàn)狀與展望64.1、不確定性理論、不確定性理論v 自然界和人類的社會活動的各種現(xiàn)象：確定性現(xiàn)象和不確定性現(xiàn)象。v 確定性現(xiàn)象：在一定條件下必然會出現(xiàn)的現(xiàn)象。v 不確定性的分類： 隨機性：因為事物的因果關(guān)系不確定，從而導(dǎo)致事件發(fā)生的結(jié)果不確定性。用概率來度量。概率表示事件發(fā)生可能性的大小。概率論的

2、運用是從隨機性中去把握廣義的因果律概率規(guī)律。 模糊性：因為事件在質(zhì)上沒有明確的含義，在量上沒有明確的界限，導(dǎo)致事件呈現(xiàn)“亦此亦彼”的性態(tài)，是事物類屬的不確定性，用隸屬度來度量。隸屬度表示事物多大程度屬于某個分類。模糊集合論的運用從模糊性中去確立廣義的排中律隸屬規(guī)律。 粗糙性：因為描述事件的知識（或信息）不充分、不完全，導(dǎo)致事件間的不可分辨性。粗糙集把那些不可分辨的事件都?xì)w屬一個邊界域。因此，粗糙集中的不確定性是基于一種邊界的概念，當(dāng)邊界域為一空集時，則問題變?yōu)榇_定性的。4.1、不確定性理論、不確定性理論v 經(jīng)典集合、模糊集合、粗糙集的關(guān)系 經(jīng)典集合認(rèn)為一個集合完全有其元素所決定，一個元素要么屬

3、于這個集合，要么不屬于這個集合。其隸屬函數(shù)x(x) 0,1是二值邏輯。 模糊集合認(rèn)為事物具有中介過渡性質(zhì)，而非突然改變，集合中每一個元素的隸屬函數(shù)x(x) 0,1，即在閉區(qū)間0,1可以任意取值，隸屬函數(shù)可以是連續(xù)光滑的，因此模糊集合對不確定信息的刻劃是精細(xì)而充分的。但隸屬函數(shù)不可計算，憑人的主觀經(jīng)驗給定。 粗糙集合把用于分類的知識引入集合。一個元素x是否屬于集合x，需要根據(jù)現(xiàn)有知識來判定，可分為三個情況：x肯定不屬于x；x肯定屬于x；x可能屬于也可能不屬于x。到達屬于哪種情況依賴于我們所掌握的關(guān)于論域的知識。粗糙集的隸屬函數(shù)為階梯狀，對不確定性信息的描述是粗糙的，但粗糙隸屬函數(shù)是可計算的。粗糙

4、集主要用于對信息系統(tǒng)進行約簡和分類。1.00.80.60.40.20.00.20.40.60.81.0第第4章章 粗糙集與數(shù)據(jù)約簡粗糙集與數(shù)據(jù)約簡 粗糙集的基本理論與方法粗糙集的基本理論與方法2 不確定性理論不確定性理論1 知識的約簡知識的約簡3 決策表的約簡決策表的約簡4 粗糙集數(shù)據(jù)約簡的具體實現(xiàn)與應(yīng)用粗糙集數(shù)據(jù)約簡的具體實現(xiàn)與應(yīng)用5 粗糙集的研究現(xiàn)狀與展望粗糙集的研究現(xiàn)狀與展望64.2 粗糙集的基本理論與方法粗糙集的基本理論與方法 粗糙集的基本概念粗糙集的基本概念1 粗糙集的基本思想粗糙集的基本思想2 粗糙集的基本特點粗糙集的基本特點34.2.1、粗糙集的基本概念、粗糙集的基本概念v 知識

5、與分類 在粗糙集理論中，知識被認(rèn)為是一種分類能力。人們的行為基本是分辨現(xiàn)實的或抽象的對象的能力。 假定我們起初對論域內(nèi)的對象（或稱元素、樣本、個體）已具有必要的信息或知識，通過這些知識能夠?qū)⑵鋭澐值讲煌念悇e。若我們對兩個對象具有相同的信息，則它們是不可區(qū)分的，即根據(jù)已有的信息不能將其劃分開。 粗糙集理論的核心是等價關(guān)系，通常用等價關(guān)系替代分類，根據(jù)這個等價關(guān)系劃分樣本集合為等價類。 從知識庫的觀點看，每個等價類被稱為一個概念，即一條知識（規(guī)則)。即，每個等價類唯一地表示了一個概念，屬于一個等價類的不同對象對該概念是不可區(qū)分的。4.2.1、粗糙集的基本概念、粗糙集的基本概念v 知識表達系統(tǒng) 一

6、個知識表達系統(tǒng)或信息系統(tǒng)s可以表示為有序四元組s=u,r,v,f其中，u=x1,x2,xn為論域，它是全體樣本的集合；rcd 為屬性集合，其中子集c是條件屬性集，反映對象的特征，d為決策屬性集，反映對象的類別； 為屬性值的集合，vr表示屬性r的取值范圍；f:urv 為一個信息函數(shù)，用于確定u中每一個對象x的屬性值，即任一xi u，r r，則f(xi,r)=vrrrrvv屬性對象條件屬性c決策屬性d頭疼r1肌肉疼r2體溫r3流感x1是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是4.2.1、粗糙集的基本概念、粗糙集的基本概念v 不可分辨關(guān)系 在粗糙集中，論域u中的對象

7、可用多種信息（知識）來描述。當(dāng)兩個不同的對象由相同的屬性來描述時，這兩個對象在該系統(tǒng)中被歸于同一類，它們的關(guān)系稱之為不可分辨關(guān)系。即對于任一屬性子集br，如果對象xi,xj u，r b，當(dāng)且僅當(dāng)f(xi,r)=f(xj,r)時，xi和xj是不可分辨的，簡記為ind(b)。不可分辨關(guān)系稱為等價關(guān)系。 例如：只用黑白兩種顏色把空間中的一些物體劃分成兩類：黑色物體、白色物體，那么同為黑色的物體就是不可分辨的，因為描述它們特征屬性的信息是相同的，都是黑色。如果引入方、圓的屬性，可將物體進一步劃分為4類：黑色方物體、黑色圓物體、白色方物體、白色圓物體。這時，如果有兩個同為黑色方物體，則它們還是不可分辨的

8、。 不可分辨關(guān)系這一概念在rs中十分重要，它反映了我們對世界觀察的不精確性。 另一方面，不可分辨關(guān)系反映了論域知識的顆粒性。知識庫中的知識越多，知識的顆粒度就越小，隨著新知識不斷加入到知識庫中，粒度會不斷減小，直致將每個對象區(qū)分開來。但知識庫中的知識粒度越小，則導(dǎo)致信息量增大，存儲知識庫的費用越高。4.2.1、粗糙集的基本概念、粗糙集的基本概念v 基本集合 由論域中相互不可分辨的對象組成的集合稱之為基本集合，它是組成論域知識的顆粒。 例如：考慮條件屬性：頭疼和肌肉疼。對于x1,x2,x3這三個對象是不可分辨的。x4,x6在這兩個屬性上也是不可分辨的。由此構(gòu)成的不可分辨集x1,x2,x3,x4,

9、x6,x5被稱為基本集合。 設(shè)論域u為有限集，r是u的等價關(guān)系簇，則k=u,r稱為知識庫，知識庫的知識粒度由不可分辨關(guān)系ind(r)的等價類反映。屬性對象條件屬性c決策屬性d頭疼r1肌肉疼r2體溫r3流感x1是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是4.2.1、粗糙集的基本概念、粗糙集的基本概念v 下近似集和上近似集 下近似集：根據(jù)現(xiàn)有知識r，判斷u中所有肯定屬于集合x的對象所組成的集合，即r-(x)=x u,xr x其中， xr 表示等價關(guān)系r下包含元素x的等價類。 上近似集：根據(jù)現(xiàn)有知識r，判斷u中一定屬于和可能屬于集合x的對象所組成的集合，即r(x)=x

10、 u,xr x其中， xr 表示等價關(guān)系r下包含元素x的等價類。 給定知識表達系統(tǒng)s=u,r,v,f，對于每個樣本子集x u和等價關(guān)系r，所有包含于x的基本集的并（邏輯和）為r-(x)；所有與x的交(邏輯積)不為空集的基本集的并為r(x)。4.2.1、粗糙集的基本概念、粗糙集的基本概念v 正域、負(fù)域和邊界域 正域：pos(x)=r-(x)，即根據(jù)知識r，u中能完全確定地歸入集合x的元素的集合。 負(fù)域：neg(x)=u-r-(x)，即根據(jù)知識r，u中不能確定一定屬于集合x的元素的集，它們是屬于x的補集。 邊界域：bnd(x)= r-(x) - r-(x) ，邊界域是某種意義上論域的不確定域，根據(jù)

11、知識r，u中既不是肯定歸入集合x，又不能肯定歸入集合x，的元素構(gòu)成的集合。 邊界域為集合x的上近似與下近似之差，如果bnd(x)是空集，則稱集合x關(guān)于r是清晰的；反之，如果bnd(x)不是空集，則稱集合x為關(guān)于r的粗糙集。因此，粗糙集中的“粗糙”（不確定性）主要體現(xiàn)在邊界域的存在。集合x的邊界域越大，其確定性程度就越小。4.2.1、粗糙集的基本概念、粗糙集的基本概念v 粗糙度（近似精確度） 對于知識r（即屬性子集），樣本子集x的不確定程度可以用粗糙度r(x)來表示為r(x)亦稱近似精確度，式中card表示集合的基數(shù)（集合中元素的個數(shù)）。 0r(x)1，如果r(x)1，則稱集合x相對于r是確定的

12、，如果r(x)kq。 當(dāng)k=1時，稱知識q完全依賴于知識p； 當(dāng)0k1時，稱知識q部分依賴于知識p； 當(dāng)k=0時，稱知識q完全獨立于知識p。 依賴度k反映了根據(jù)知識p將對象分類到q的基本概念中去的能力。確切的說，當(dāng)pkq時，論域中共有kcard(u)個屬于q的p正域的對象，這些對象可以依據(jù)知識p分類到知識q的基本概念中去。例 u=x1,x2,x8，u/p=x1,x2,x3,x4,x5,x6,x7,x8，u/q= x1,x2,x3,x4,x5,x6,x7,x8，求依賴度k。解：posp(q)=x1x2x3,x4x5,x6=x1,x2,x3,x4,x5,x6 k=6/8=0.75 即知識q相對于知

13、識p的依賴度為0.75第第4章章 粗糙集與數(shù)據(jù)約簡粗糙集與數(shù)據(jù)約簡 決策表的約簡決策表的約簡4 不確定性理論不確定性理論1 粗糙集的基本理論與方法粗糙集的基本理論與方法2 知識的約簡知識的約簡3 粗糙集數(shù)據(jù)約簡的具體實現(xiàn)與應(yīng)用粗糙集數(shù)據(jù)約簡的具體實現(xiàn)與應(yīng)用5 粗糙集的研究現(xiàn)狀與展望粗糙集的研究現(xiàn)狀與展望64.4 決策表的約簡決策表的約簡 決策表決策表1 分辨矩陣與分辨函數(shù)分辨矩陣與分辨函數(shù)3 屬性的重要性屬性的重要性2 決策表屬性約簡的分辨矩陣方法決策表屬性約簡的分辨矩陣方法4 決策規(guī)則的生成決策規(guī)則的生成54.4.1、決策表、決策表v決策表是一類特殊的知識表達系統(tǒng)，它是指當(dāng)滿足某些條件時，決

14、策應(yīng)該怎樣進行。多數(shù)決策問題都可以用決策表形式表達，這一工具在決策應(yīng)用中起著重要作用。v定義：設(shè)s=(u,r)為一知識表達系統(tǒng)，若r可劃分為條件屬性集c和決策屬性集d，則cd=r,cd=。具有條件屬性和決策屬性的知識表達系統(tǒng)可表示為決策表，記作t=(u,r,c,d)或簡稱cd決策表。ind(c)的等價類稱為條件類，ind(d)的等價類稱為決策類。 決策表可分為一致決策表和非一致決策表。 當(dāng)且僅當(dāng)d依賴于c，即cd時，稱決策表是一致的； 當(dāng)且僅當(dāng)ckd(0k1)時，稱決策表是不一致的。 決策表必須是一致的才能夠約簡。 對于不一致的決策表，首先要將其分解為兩個決策表，一個為一致決策表，另一個為非一

15、致決策表，然后再對一致決策表進行約簡。4.4.1、決策表、決策表例 設(shè)論域u=x1,x2,x7，屬性集r=cd，條件屬性集c=a,b,c,d，決策屬性集d=e。決策表如下所示：由決策表可知： 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故該決策表是一致決策表。uabcdex110211x210201x312002x412210 x521002x621102x7212111)()(ucarddposcardkc4.4.1、決策表、決策表u/(a)=x1,x2,x3,x4,x5,x6,x

16、7 pos(a)(d)=u/(b)=x1,x2,x3,x4,x5,x6,x7 pos(b)(d)=x1,x2u/(c)=x1,x2,x4,x7,x3,x5,x6 pos(c)(d)=x3,x5u/(d)=x1,x4,x7,x2,x3,x5,x6 pos(d)(d)=u/(a,b)=x1,x2,x3,x4,x5,x6,x7 pos(a,b)(d)=x1,x2u/(a,c)=x1,x2,x4,x3,x5,x6,x7 pos(a,c)(d)=x3,x5,x6,x7u/(a,d)=x1,x4,x2,x3,x5,x6,x7 pos(a,c)(d)=x5,x6,x7u/(b,c)=x1,x2,x3,x4,

17、x5,x6,x7 pos(b,c)(d)=x1,x2,x3,x4,x5,x6,x7 u/(b,d)=x1,x2,x3,x4,x5,x6,x7 pos(b,d)(d)=x1,x2,x3,x4,x5,x6,x7u/(c,d)=x1,x4,x7,x2,x3,x5,x6 pos(c,d)(d)=x2,x3,x5,x6u/(b,c,d)=x1,x2,x3,x4,x5,x6,x7 pos(b,c,d)(d)=x1,x2,x3,x4,x5,x6,x7u/(a,c,d)=x1,x4,x2,x3,x5,x6,x7 pos(a,c,d)(d)=x2,x3,x5,x6,x7u/(a,b,d)=x1,x2,x3,x4

18、,x5,x6,x7 pos(a,b,d)(d)=x1,x2,x3,x4,x5,x6,x7u/(a,b,c)=x1,x2,x3,x4,x5,x6,x7 pos(a,b,c)(d)=x1,x2,x3,x4,x5,x6,x7所以，b是c中d不可省的,b,c和b,d是兩個c的d約簡，c的d核為b。4.4.1、決策表、決策表例 不一致決策表分解。下表所示為一非一致決策表，其中c=a,b,c,d=d,e,將其分解為兩個決策表，一個是一致的，另一個是非一致的。uabcde132300201131323303401321522032611101701103832310uabcde323303401321522

19、032611101uabcde1323002011317011038323104.4 決策表的約簡決策表的約簡 屬性的重要性屬性的重要性2 分辨矩陣與分辨函數(shù)分辨矩陣與分辨函數(shù)3 決策表決策表1 決策表屬性約簡的分辨矩陣方法決策表屬性約簡的分辨矩陣方法4 決策規(guī)則的生成決策規(guī)則的生成54.4.2、屬性的重要性、屬性的重要性v 在一個知識系統(tǒng)中，不同的屬性具有的重要程度是不同的。在傳統(tǒng)的數(shù)據(jù)分析中，這種重要性需要事先假設(shè)，一般有領(lǐng)域?qū)＜医o出的權(quán)重表示，具有一定的主觀色彩。在粗糙集方法中，不需要事先假定的信息（先驗知識），利用決策表中的數(shù)據(jù)可以計算其屬性的重要性。v 判斷屬性重要性的方法：從決策表

20、中去掉一些屬性，再來考慮沒有該屬性后分類會怎樣變化：若去掉該屬性會相應(yīng)地改變分類，則說明該屬性的強度大，而重要性高；反之說明該屬性的強度小，即重要性低。v 對于屬性的重要性可以利用依賴度rp(q)來描述。對于屬性集d導(dǎo)出的分類屬性集bb的重要性，采用兩者的依賴度的差來度量，即rb(d)- rb-b(d)。這表示從集合b中去掉某些屬性子集b后對對象進行分類時，分類u/d的正域?qū)艿皆鯓拥挠绊憽?.4.2、屬性的重要性、屬性的重要性例 某一知識表達系統(tǒng)如表所示。計算表中屬性a,b,c相對屬性d,e的重要性。解：定義c=a,b,c,d=d,e，則可以構(gòu)成各種分類： u/(b,c)=1,5,2,7,

21、8,3,4,6 u/(a,c)=1,5,2,8,3,6,4,7 u/(a,b)=1,5,2,8,3,4,6,7 u/(a,b,c)=1,5,2,8,3,4,6,7 u/(d,e)=1,2,7,3,6,4,5,8uabcde1102202011123200114110225102016220117211128011014.4.2、屬性的重要性、屬性的重要性 posc(d)=3,4,6,7 posc-a(d)=3,4,6 posc-b(d)=3,4,6,7 posc-c(d)=3,4,6,7故 rc(d)=card(posc(d)/card(u)=4/8=0.5 rc-a(d)=card(posc

22、-a(d)/card(u)=3/8=0.375 rc-b(d)=card(posc-b(d)/card(u)=4/8=0.5 rc-c(d)=card(posc-c(d)/card(u)=4/8=0.5因此 rc(d) rc-a(d)0.125 rc(d) rc-b(d)0 rc(d) rc-c(d)0可知，屬性a是最重要的，其將u/d的正域改變的最多；屬性b和c無關(guān)緊要，去掉它們后，分類依賴度未產(chǎn)生變化。4.4 決策表的約簡決策表的約簡 分辨矩陣與分辨函數(shù)分辨矩陣與分辨函數(shù)3 決策表決策表1 屬性的重要性屬性的重要性2 決策表屬性約簡的分辨矩陣方法決策表屬性約簡的分辨矩陣方法4 決策規(guī)則的生

23、成決策規(guī)則的生成54.4.3、分辨矩陣與分辨函數(shù)、分辨矩陣與分辨函數(shù)v分辨矩陣 設(shè)s(u,r,v,f)為一信息系統(tǒng)，rcd是屬性集合，子集c=ai|i=1,2,m和dd分別為條件屬性集和決策屬性集，u=x1,x2,xn為論域，ak(xj)是樣本xj在屬性ak上的取值。定義系統(tǒng)的分別矩陣為m(s)=mijnn，其i行j列處元素為因此，分辨矩陣中元素mij是能夠區(qū)別對象xi和xj的所有屬性的集合；但若xi和xj屬于同一決策類時，則分辨矩陣中元素mij的取值為空集。 分辨矩陣是一個依主對角線對稱的n階方陣，在進行分辨矩陣運算時，只需考慮其上三角(或下三角)部分。njixdxdxdxdxaxacamj

24、ijijkikkij, 2 , 1,)()(,)()()()(,4.4.3、分辨矩陣與分辨函數(shù)、分辨矩陣與分辨函數(shù)v分辨函數(shù) 對于每一個分辨矩陣m(s)對應(yīng)唯一的分辨函數(shù)fm(s)，其定義為：信息系統(tǒng)s的分辨函數(shù)是一個具有m元變量a1,a2,am(aic,i=1,2,m)的布爾函數(shù),它是(mij)的和取，而(mij)是矩陣項mij中的各元素的析取，即 fm(s)(a1,a2,am)=mij, 1j in, mij v分辨函數(shù)的析取范式中的每一個合取式對應(yīng)一個約簡。而核則是分辨矩陣中所有單個元素組成的集合，即 core(r)=akr:mij=ak, 1j inv根據(jù)分辨函數(shù)與約簡的對應(yīng)關(guān)系，可以

25、得到計算信息系統(tǒng)s約簡red(s)的方法： 計算信息系統(tǒng)s的分辨矩陣m(s)； 計算分辨矩陣m(s)對應(yīng)的分辨函數(shù)fm(s)； 計算分辨函數(shù)fm(s)的最小析取范式，其中每個析取分量對應(yīng)一個約簡。4.4.3、分辨矩陣與分辨函數(shù)、分辨矩陣與分辨函數(shù)例 設(shè)有信息系統(tǒng)s=(u,r),u=x1,x2,x6,r=a,b,c,d，其數(shù)據(jù)表格如右表所示。利用分辨矩陣及分辨函數(shù)求約簡及核。解：分辨矩陣m(s)如表格所示：分辨函數(shù)為：fm(s)(a,b,c,d)=(bcd)(b)(abcd) (ad)(abcd) (bcd)(ad) (abc)(ad) (abcd) (abd) (abcd)(bcd) (bcd

26、) =b(ad)=abbd因此該信息系統(tǒng)有兩個約簡a,b和b,d，核是babcdx10000 x20211x30100 x41212x51001x61212x1x2x3x4x5x6x1x2b,c,dx3bb,c,dx4a,b,c,da,da,b,c,dx5a,da,b,c a,b,d b,c,dx6a,b,c,da,da,b,c,d b,c,d4.4 決策表的約簡決策表的約簡 決策表屬性約簡的分辨矩陣方法決策表屬性約簡的分辨矩陣方法4 分辨矩陣與分辨函數(shù)分辨矩陣與分辨函數(shù)3 決策表決策表1 屬性的重要性屬性的重要性2 決策規(guī)則的生成決策規(guī)則的生成54.4.4、決策表屬性約簡的分辨矩陣方法、決策

27、表屬性約簡的分辨矩陣方法v 采用分辨矩陣可以方便的求解屬性集合的核和約簡。v c的d核就是分辨矩陣中所有只有一個元素的矩陣項mij的集合，即 cordd(c)=akc:mij=ak, 1j inv 分辨矩陣fm(s)的極小析取范式中各個合取式分別對應(yīng)c的d約簡，即若屬性集合cc是滿足以下條件 cmij 對所有mij 的一個最小屬性子集，則稱c是c的d約簡(相對約簡)。4.4.4、決策表屬性約簡的分辨矩陣方法、決策表屬性約簡的分辨矩陣方法例 求下面決策表的屬性約簡。解：分辨矩陣如下表所示：uabcdex110211x210201x312002x412210 x521002x621102x7212

28、11ux1x2x3x4x5x6x7x1x2x3b,c,db,cx4bb,dc,dx5a,b,c,da,b,ca,b,c,dx6a,b,c,da,b,ca,b,c,dx7a,b,c,da,bc,dc,d4.4.4、決策表屬性約簡的分辨矩陣方法、決策表屬性約簡的分辨矩陣方法分辨函數(shù)為：fm(s)(a,b,c,d)=(bcd)(b)(abcd)(abcd)(bc)(bd) (abc)(abc)(cd)(abcd)(abcd) (ab)(cd)(cd) =b(cd) =bcbd故c的d約簡有兩個，分別是b,c和b,d,c的d核為b。約簡后的決策表如下所示ubcex1021x2021x3202x4220

29、 x5102x6112x7121ubdex1011x2001x3202x4210 x5102x6102x71114.4 決策表的約簡決策表的約簡 決策規(guī)則的生成決策規(guī)則的生成5 分辨矩陣與分辨函數(shù)分辨矩陣與分辨函數(shù)3 決策表決策表1 屬性的重要性屬性的重要性2 決策表屬性約簡的分辨矩陣方法決策表屬性約簡的分辨矩陣方法44.4.5、決策規(guī)則的生成、決策規(guī)則的生成v 決策表是對信息系統(tǒng)中有效事實和規(guī)律的描述，根據(jù)表中數(shù)據(jù)能夠推導(dǎo)出所有可能的規(guī)律。v 從決策表生成決策規(guī)則是粗糙集的主要應(yīng)用之一。v 設(shè)t=(u,r,v,f)是決策表，r=cd，c為條件屬性集，d為決策屬性集。令xi和yi分別表示條件類

30、和決策類。 des(xi)表示條件類xi的描述，定義為 des(xi)(a,va)|f(x,a)=va,ac des(yj)表示決策類yj的描述，定義為 des(yj)(a,va)|f(x,a)=va,ad 決策規(guī)則定義為 tij：des(xi)des(yj),xiyj 規(guī)則tij的確定因子為 (xi,yj)=card(xiyj)/card(xi) 顯然，01 當(dāng)(xi,yj)1時，tij是確定性規(guī)則； 當(dāng)01時，tij是不確定的規(guī)則，此時(xi,yj)反映xi中的對象可分類到y(tǒng)j中的比例。4.4.5、決策規(guī)則的生成、決策規(guī)則的生成v 決策表中所有決策規(guī)則的集合稱為決策算法。從決策表中提取決策

31、規(guī)則時，如果多個對象的信息（屬性值）完全相同，則只保留其中一個（它們反映相同的決策規(guī)則），然后求條件屬性的相對約簡，得到約簡的決策表。約簡后的決策表具有更少的條件屬性，但具有和原決策相同的知識。v從決策表中生成規(guī)則需要經(jīng)過以下步驟： 數(shù)據(jù)預(yù)處理。將知識表達系統(tǒng)中的初始數(shù)據(jù)信息轉(zhuǎn)換為粗糙集形式，并明確條件屬性和決策屬性； 數(shù)據(jù)約簡。生成分別矩陣，并在分辨矩陣的基礎(chǔ)上生成約簡的屬性集； 發(fā)現(xiàn)規(guī)則。在約簡的決策表中，根據(jù)預(yù)先設(shè)定的確定性因子發(fā)現(xiàn)決策規(guī)則。ubcex1021x2021x3202x4220 x5102x6112x7121(b,0)(c,2)(e,1)(b,2)(c,0)(e,2)(b,2

32、)(c,2)(e,0)(b,1)(c,0)(e,2)(b,1)(c,1)(e,2)(b,1)(c,2)(e,1)第第4章章 粗糙集與數(shù)據(jù)約簡粗糙集與數(shù)據(jù)約簡 粗糙集數(shù)據(jù)約簡的具體實現(xiàn)與應(yīng)用粗糙集數(shù)據(jù)約簡的具體實現(xiàn)與應(yīng)用5 不確定性理論不確定性理論1 粗糙集的基本理論與方法粗糙集的基本理論與方法2 知識的約簡知識的約簡3 決策表的約簡決策表的約簡4 粗糙集的研究現(xiàn)狀與展望粗糙集的研究現(xiàn)狀與展望64.5、粗糙集數(shù)據(jù)約簡的具體實現(xiàn)與應(yīng)用、粗糙集數(shù)據(jù)約簡的具體實現(xiàn)與應(yīng)用 屬性值的離散歸一化屬性值的離散歸一化1 基于分辨矩陣的啟發(fā)式屬性約簡算法基于分辨矩陣的啟發(fā)式屬性約簡算法2 基于粗糙集方法的實例基于

33、粗糙集方法的實例34.5.1、屬性值的離散歸一化、屬性值的離散歸一化v 運用粗糙集處理決策表時，要求決策表中的值用離散數(shù)據(jù)表達。因此在智能信息處理中，對定性的屬性或?qū)傩缘闹涤蚴沁B續(xù)的數(shù)據(jù)要進行預(yù)先處理，將其離散化，轉(zhuǎn)換為粗糙集理論所識別的數(shù)據(jù)，從而提取有用信息，從中發(fā)現(xiàn)知識。v 將屬性值的定性和定量描述都叫作連續(xù)值，則把粗糙集方法中的數(shù)據(jù)處理稱為離散歸一化。v 離散歸一化方法應(yīng)該滿足下列條件 屬性離散歸一化后的空間維數(shù)盡量小，也就是每一離散歸一化后的屬性值的種類盡量少； 屬性值被離散歸一化后的信息丟失盡量少。v定性說明型屬性值的離散化 對每一種定性說明概念，可用一種字母或數(shù)字代替，作為屬性值的

34、離散歸一化值。例如顏色屬性，屬性值為“紅”、“黃”、“藍”、“白”，可以使用“r”、“y”、“b”、“w”或“1”、“2”、“3”、“4”代表。 對每一種層次說明概念，可用一種字母或數(shù)字代替，作為屬性值的離散歸一化值。例如溫度屬性，屬性值為“冷”、“涼”、“暖”、“熱”，可以使用“a”、“b”、“c”、“d”或“1”、“2”、“3”、“4”代表。4.5.1、屬性值的離散歸一化、屬性值的離散歸一化v 連續(xù)型屬性值的離散化 等距離劃分在每個屬性上，根據(jù)給定的參數(shù)把屬性值簡單地劃分為距離相等斷點段，不考慮每個斷點段中屬性值個數(shù)的多少。假設(shè)某個屬性的最多屬性值是xmax，最小屬性值是xmin,給定的參

35、數(shù)為k,則斷點間隔為=(xmax-xmin)/k,得到此屬性上的斷點為xmini,i=0,1,k。這些斷點間的距離相等。 等頻率劃分根據(jù)給定的參數(shù)k把m個對象分成段，每段有m/k個對象。假設(shè)某個屬性的最多屬性值為xmax，最小屬性值為xmin，給定的參數(shù)k，則需將這個屬性在所有實例上的取值從大到小排列，然后平均分成k段，即得斷點集。 naive scaler算法對于每一個屬性ac,進行如下過程：根據(jù)a(x)的值，從小到大排列實例xu從上到下掃描,設(shè)xi和xj代表相鄰實例：如果a(xi)=a(xj),則繼續(xù)掃描;如果d(xi)=d(xj),即決策相同，則繼續(xù)掃描；否則，得到一個斷點c，c=(a(

36、xi)+a(xj)/2。4.5、粗糙集數(shù)據(jù)約簡的具體實現(xiàn)與應(yīng)用、粗糙集數(shù)據(jù)約簡的具體實現(xiàn)與應(yīng)用 基于分辨矩陣的啟發(fā)式屬性約簡算法基于分辨矩陣的啟發(fā)式屬性約簡算法2 屬性值的離散歸一化屬性值的離散歸一化1 基于粗糙集方法的實例基于粗糙集方法的實例34.5.2、基于分辨矩陣的啟發(fā)式屬性約簡算法、基于分辨矩陣的啟發(fā)式屬性約簡算法v 基于分辨矩陣的啟發(fā)式最小約簡算法可以解決復(fù)雜決策表在進行分辨矩陣約簡過程中過大的存儲空間的問題。v 如果一個約簡和分辨矩陣的某項mij的交為空的話，對象i和對象j對于該約簡就是不可分辨的。這和約簡是能夠區(qū)分所有對象的最小屬性集合相矛盾。所以，可以得出結(jié)論：一個約簡和分辨矩

37、陣的非空項的交都不能為空。v 由于原始數(shù)據(jù)未進行約簡，所以其候選約簡集合r=。檢查分辨矩陣的每一項mij和候選約簡集合的交，如果交為空，隨機從mij中選擇一個屬性，加到候選約簡集合r中；若不為空，就跳過這一項。重復(fù)這一過程，直到分辨矩陣中的每一項都檢查過了。此時，在r中得到一個“約簡”。但這并不是約簡本身。例如，假定分辨矩陣中有這樣三項：a1,a3,a2,a3,a3。根據(jù)此算法，可能會得到候選約簡集合為a1,a2,a3或a1,a3，而不是a3。這是因為這個結(jié)論是約簡的必要而非充分條件。v 一個簡單而有效的方法是根據(jù)|mij|來對條件屬性進行排序。如果mij中只有一個屬性，該屬性一定是約簡的成員

38、。從分辨矩陣的定義可以看出，分辨矩陣中某項的長度越短，該項就對分類所起的作用越大。而且該項出現(xiàn)的越頻繁，該項越重要。因此，對分辨矩陣排序時，除了按長度外，在長度相同的情況下，出現(xiàn)頻率高的屬性更重要。4.5.2、基于分辨矩陣的啟發(fā)式屬性約簡算法、基于分辨矩陣的啟發(fā)式屬性約簡算法v 由此，提出一種新的基于分辨矩陣的計算屬性重要性的方法。在生成分辨矩陣的時候，每個屬性出現(xiàn)的頻率同時被記錄，以供以后使用。這些頻率被用來評估屬性的重要性，并用于屬性的優(yōu)先選擇。這是基于如果一個屬性出現(xiàn)的越頻繁，它的潛在區(qū)分能力就越大的考慮。在計算屬性的出現(xiàn)頻率時，并不是簡單的計數(shù)，而是加權(quán)，加權(quán)的大小根據(jù)屬性出現(xiàn)的分辨矩

39、陣中的長度。因此，對于一個分辨矩陣m=(mij)nn，相應(yīng)的屬性a的重要性計數(shù)公式為：式中，|mij|mij包含屬性的個數(shù)公式體現(xiàn)了兩個重要的啟發(fā)式思想：屬性在分辨矩陣中出現(xiàn)的次數(shù)越多，屬性的重要性越大。屬性出現(xiàn)在分辨矩陣中的項越短，屬性的重要性越大。 ijijijninjijijmamamaf,1,0)(114.5.2、基于分辨矩陣的啟發(fā)式屬性約簡算法、基于分辨矩陣的啟發(fā)式屬性約簡算法v 基于分辨矩陣的啟發(fā)式約簡算法如下： 輸入：決策表(u,ad,其中a=ai,i=1,2,n)。 輸出：約簡(reduct)。步驟： 令約簡后得到的屬性集合等于條件屬性集合，即reduct=r； 計算分辨矩陣m

40、，并找出所有不包含核屬性的屬性組合s； 將所有不包含核屬性的屬性組合表示為析取范式的形式，即 p=aik,i=1,2,s,k=1,2,m 將p轉(zhuǎn)化為析取范式的形式，并計算屬性的重要性； 選擇其中重要性最小的屬性a，使得reduct=reduct-a； 判斷約簡操作是否成立，若成立，刪除因條件屬性約簡而引入的冗余樣本和不一致樣本，i=i+1，轉(zhuǎn)步驟；否則恢復(fù)約簡該屬性前的樣本數(shù)據(jù)，結(jié)束約簡。步驟步中的判斷條件為 p1/p0式中，p0為執(zhí)行本次約簡操作前信息表中樣本的數(shù)量；p1為執(zhí)行約簡后引入的不一致樣本數(shù)；為閾值，根據(jù)實際需要確定，通常取=5%。4.5、粗糙集數(shù)據(jù)約簡的具體實現(xiàn)與應(yīng)用、粗糙集數(shù)據(jù)

41、約簡的具體實現(xiàn)與應(yīng)用 基于粗糙集方法的實例基于粗糙集方法的實例3 屬性值的離散歸一化屬性值的離散歸一化1 基于分辨矩陣的啟發(fā)式屬性約簡算法基于分辨矩陣的啟發(fā)式屬性約簡算法24.5.3、基于粗糙集方法的實例、基于粗糙集方法的實例實例1：以氣象狀況實例作為決策表，如下表所示，則c=a1,a2,a3,a4,a5,a6,d=du天氣a1溫度a2濕度a3風(fēng)a4沙塵a5污染指數(shù)a6決策屬性dx1晴熱高否是中度nx2晴溫暖高是否中度nx3晴溫暖高否否輕度nx4雨溫暖高是是中度nx5雨涼正常是是中度nx6雨涼正常否否輕度px7多云涼正常是否重度px8多云熱高否是重度px9晴溫暖正常是否輕度px10雨溫暖正常否

42、否輕度px11晴溫暖正常是是中度px12多云溫暖高是否中度px13多云熱高否是中度px14雨溫暖高否是中度p4.5.3、基于粗糙集方法的實例、基于粗糙集方法的實例項目離散化結(jié)果：u天氣a1溫度a2濕度a3風(fēng)a4沙塵a5污染指數(shù)a6決策屬性dx1332212nx2322122nx3322221nx4122112nx5111112nx6111221px7211123px8232213px9321121px10121221px11321112px12222122px13232212px14122212p4.5.3、基于粗糙集方法的實例、基于粗糙集方法的實例分辨矩陣如下：ux1x2x3x4x5x6x7

43、x8x9x10 x11x12x13x14x1x2x3x4x5x61,2,3,5,61,2,3,4,61,2,32,3,4,5,64,5,6x71,2,3,4,5,61,2,3,61,2,3,4,6 1,2,3,5,61,5,6x81,61,2,4,5,61,2,5,61,2,4,61,2,3,4,6x92,3,4,5,63,63,41,3,5,61,2,5,6x101,2,3,5,61,3,4,61,33,4,5,62,4,5,6x112,3,43,53,4,5,61,31,2x121,2,4,511,4,61,51,2,3,5x1311,2,4,51,2,5,61,2,41,2,3,4x14

44、1,21,4,51,5,642,3,44.5.3、基于粗糙集方法的實例、基于粗糙集方法的實例由可辨識矩陣求出該決策表的核core=a1,a4。不含核屬性的屬性組合為 p=(a3a5)(a3a6)=a3(a5a6)這個析取式的每一項中的元素與核元素就組成了約簡后的屬性集合，即最終得到的屬性集合為：a1,a3,a4和a1,a4,a5,a64.5.3、基于粗糙集方法的實例、基于粗糙集方法的實例實例2：某科研基金立項評審系統(tǒng)指標(biāo)體系的優(yōu)化。下表是原有的項目評審指標(biāo)體系，其中可得條件屬性15個（0115號），決策屬性1個（16號），根據(jù)已有的樣本對該指標(biāo)體系進行約簡，重建更加科學(xué)、合理、簡捷的科研項目評

45、審指標(biāo)體系。項目指標(biāo)立項依據(jù)科學(xué)意義(01)；應(yīng)用前景(02)；創(chuàng)新程度(03)；立項依據(jù)(04)；國內(nèi)外研究現(xiàn)狀(05)研究方案研究內(nèi)容(06)；研究方法和技術(shù)路線(07)；實現(xiàn)目標(biāo)的可信度08；經(jīng)費預(yù)算和落實情況(09)研究基礎(chǔ)與項目有關(guān)的研究工作積累(10)；已具備的研究條件(11)；研究隊伍(12)綜合意見評審專家對本項目的熟悉程度(13)；綜合評價(14)；是否交叉學(xué)科或新興學(xué)科(15)；資助(16)4.5.3、基于粗糙集方法的實例、基于粗糙集方法的實例(1)對已有樣本進行離散化。隨機抽取30個樣本，離散化結(jié)果如下表所示（部分?jǐn)?shù)據(jù)），其中第114指標(biāo)離散化為3個值：1(優(yōu))、2(良)

46、、3(差)，第15指標(biāo)離散化為2個值：1(是)、2(否)；決策屬性(16)值2個：0(不資助)、1(資助)。u12345678910111213141516003921222213223131210040333221211132222000412333323333323220013121112221212131210132322222222233332001332113212112321210013421323233222112104.5.3、基于粗糙集方法的實例、基于粗糙集方法的實例(2)計算分辨矩陣。決策表共30項，15個條件屬性，1個決策屬性。經(jīng)計算決策表的核屬性為空，不包含核屬性的屬性

47、組合如下所示：根據(jù)分辨矩陣的啟發(fā)式約簡算法，計算15個屬性的重要性：f(1)=3.2644； f(2)=3.2973； f(3)=2.8719； f(4)=3.2195； f(5)=3.1049； f(6)=2.1064； f(7)=3.7537； f(8)=2.8656； f(9)=3.0751； f(10)=3.8406；f(11)=3.0957；f(12)=3.3640；f(13)=2.7445；f(14)=3.1699；f(15)=2.5283；由此得出屬性的重要性排序為：1071221414511938131561513121098621)18, 718, 4(14131282)27, 2(141298521)5 , 2(13121198765321)5 , 728, 26 , 2(1413108654)18, 1 (cccccccc77774.5.3、基于粗糙集方法的實例、基于粗糙集方法的實例(3)屬性約簡。根據(jù)精度要求，取=5%，得屬性約簡結(jié)果如下表所示