：粗糙集RoughSet

1、第三節(jié)粗糙集(Rough Set RS)如果我們將研究對象看成是現象，那么我們可以將這些現象分類?，F象被 分為確定現象與不確定現象。不確定現象有分為隨機現象，模糊現象和信息不 全的粗糙現象。如下所示：膈定現象精 機現象，0 -1律，多種可能性滿足分布規(guī)律?，F象w不確定現象J模糊現象，律屬度？40,1),不是非此即彼。T'粗糙現象，研究那些因為信息不充分而導致的不確定性相對于前兩種現象的處理，粗糙現象是基于不完全的信息或知識去處理不分明 的現象，因此需要基于觀測或者測量到的部分信息對數據進行分類，這就需要 與概率統(tǒng)計和模糊數學不同的處理手段，這就是粗糙集理論。直觀地講，粗糙 集是基于一系

2、列既不知道多了還是少了，也不知道有用還是沒用的不確定、不 完整乃至于部分信息相互矛盾的數據或者描述來對數據進行分析、推測未知信 息。下面我們對粗糙集的基本特征、以及數學符號進行簡述。1.粗糙集的特點粗糙集的特點是利用不精確、不確定、部分真實的信息來得到易于處理、 魯棒性強、成本低廉的決策方案。因此更適合于解決某些現實系統(tǒng)，比如，中 醫(yī)診斷，統(tǒng)計報表的綜合處理等。粗糙集的另一個重要特點就是它只依賴于數 據本身，不需要樣本之外的先驗知識或者附加信息，因此挑選出來的決策屬性 可以避免主觀性，有英雄不問出身的意味。用粗糙集來處理的數據類型包括確 定性的、非確定性的、不精確的、不完整的、多變量的、數值的

3、、非數值的。 粗糙集使用上、下近似來刻畫不確定性，使得邊界有了清晰的數學意義并且降 低了算法設計的隨意性。3.粗糙集的基本概念粗糙集要涉及論域U (這與模糊系統(tǒng)相似)，還要涉及屬性集合r=cUd(這被認為是知識，或者知識庫)。當然，也要有屬性值域V ,以及從U ><R至lJV 的信息函數f。因此，一個信息系統(tǒng)S可以表示為一個四元組S=U,R,V, f。 在不混淆的情況下，簡記為S =(U , R),也稱為知識庫。等價關系(通常用來代替分類)是不可或缺的概念，根據等價關系可以劃 論域中樣本為等價類。而每個等價類被稱為同一個對象。但是，等價關系又是 建立在不可分辨概念之上的，為了便于描

4、述這里的等價關系，我們首先介紹不 可分辨性。設B鼻R為一個非空子集，如果xi,xj SU，均有f (xi, r) = f (xj,r), /r W B成 立，那么，我們稱xi和Xj關于屬性子集B不可分辨。B不可分辨關系，簡記為 Ind (B),是一種等價關系(易驗證它滿足等價關系的數學公理)，于是Ind (B)可 以將論域U中的元素分成若干等價類，每一個等價類稱為知識庫的知識顆粒。全體等價類組成的集合記為U / Ind (B),稱之為基本集合。若集合 X可以表示成 某些基本集的并時，則稱 X是B精確集，否則稱為B粗糙集。粗糙集中的“粗糙” 主要體現在邊界域的存在，而邊界又是由下、上近似 來刻畫

5、的。對于任意X UU , X關于現有知識R的下、上近似分別定義為：R_( X ) =x WU , xR 三 X , R-(x) = x w U , xR c X ¥句。X的確定域Pos(X尸R_(X卜是指論域U中那些在現有知識R之下能夠確定地 歸入集合X的元素的集合。反之，Neg (X尸U -RJX )被稱為否定域。邊界域 是某種意義上論域的不確定域，即在現有知識 R之下U中那些既不能肯定在X 中，又不能肯定歸入X =U X中的元素的集合，記為BndR(X )。樣本子集X的不確定性程度可以用粗糙度aR (X )來刻畫，粗糙度的定義為：aR X =Card R_ XCard R_ X式

6、中Card表示集合的基數(集合中元素的個數)。顯然，0<aR(X )<1 ,如果aR (X )=1 ,則稱集合X關于R是確定的；如果aR(X戶1 ,則稱集合X關于R是粗糙的，aR(X )可認為是在等價關系R下逼近集合X的精度。為了使得上述概念具體化，下面我們舉一個例子說明如何理解和計算以上 相應的概念和對應量。例.針對一下醫(yī)學信息表我們來理解前面所提到的概念。表1某醫(yī)療信息表屬性對象條件屬性C決策屬性D頭疼ri肌肉疼一體溫r 3流感xi是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是依據此表，如果取屬性子集 R=頭疼，肌肉疼 = /, X =“X2,X3

7、。那么我們下面給出X的上近似集、下近似集、確定域、邊界域、粗糙度。解：計算論域U的所有R基本集：U / Ind ( R ) = 板,x2, x3 ,x4,x6,x5令R1 - H, x2, x3 J R2 - 1x4, x6 R3 - x5:112324635確定樣本子集X與基本集的關系X C R = %, x2X c R2 =句 X c R3 = x5手中計算 R （X 卜 R_（X 卜 Pos（X 戶口 Bnd （X ）：R一（X 尸 Ri u R3 = xi, x?x3, *5 ；R_（ X ）= R3 = x5Pos（X ）=R_（X ）=x5；Bnd（X ）=R1（X ）-R_（X1

8、"計算近似精確度：aR Z =Card R_ X= 1/4 =0.25Card R X與粗糙度類似，在給出了兩個知識集(特征屬性)的相對肯定域的概念PoSp(Q)之后，我們也可以一個量來刻畫兩個知識集的依賴度。設 K=(U,R)為一個知識庫，P,QR為兩個知識集。令 k=rP(Q)=Card (Pos P (Q )/Card (U ),稱為知識Q依賴于知識P的依賴度。特別，當k =1時稱為完全依賴；0 <k cl時,部分依賴；k = 0時，Q完全獨立于知識P 。3.知識約簡知識約簡是粗糙集的核心內容之一，它是研究知識庫中哪些知識是必要的， 以及在保持分類能力不變的前提下，刪除冗

9、余的知識。在粗糙集應用中，約簡 與核是兩個最重要的基本概念。(1) 一般約簡設P,Q是屬性集，Q中的每一個屬性都是不可省略的。如果Q J P且 Ind (Q) =ind (P),則稱Q是p的一個約簡(Reduce),記為Red (P )。另外，若 以Core (P)記P中所有不可省略的屬性集合稱為 P的核(Core),那么所有約簡 Red (P )的交正女?等于P的核，即Core (P產cRed(P )。該式的意義在于，不僅 體現了核與所有約簡的關系直接由約簡得到，而且也表明了核是知識庫中最重 要的部分，是進行知識約簡的過程中不能刪除的知識。(2)相對約簡一般地，考慮一個分類相對于另一個分類的

10、關系，這就導出了相對約簡與 相對核的概念。在粗糙集中，相對約簡的概念是條件屬性相對決策屬性的約簡。 我們需要給出如下的概念：設P和Q為論域U上的兩個等價關系，定義 Q關于P的相對肯定域，記為Posp (Q ),為論域U中的所有那些對象構成的集合，它們可以在分類U / P的知識指導下，被正確地劃入到U /Q的等價類之中。即Pos P Q P_ XX U / Q其中，P_(X )是集合X的下近似。設P和Q為論域U上的兩個等價關系，r W P。如果Pos P Q =PoS(P4r) Q那么稱r關于Q可省略，否則稱為Q不可省略。特別，當Pr為P中的獨立子 集(即它的每個元素都再不可省略)，且Pos p

11、 (Q戶Pos(Q )。那么稱P r 為P的關于Q的相對約簡，記為Ind q(P)。P的所有關于Q的相對約簡之交稱為 P的關于Q的核，記為CoreQ (P)。此時有Core q (P) =Dlnd q(P)。比較相對約簡與一般約簡的定義，我們能夠發(fā)現，前者是在不改變決策屬 性Q的前提下對特征屬性集P的約簡，而后者是不改變對于論域中對象的分辨 能力的前提下對于特征屬性集的約簡。(3)決策表的約簡決策表約簡的重要內容之一是簡化決策表中的條件屬性使得約簡前后的決 策表具有相同的功能。同樣的決策可以通過基于更少量的條件，便于我們借助 一些簡單的手段就能獲得同樣要求的結果，這是事半功倍的好事。(1)分辨

12、矩陣和分辨函數分辯矩陣是粗糙集中又一個重要概念，它將決策表中關于屬性區(qū)分的信息 濃縮進一個矩陣當中，可用于決策表的屬性約簡。一信息系統(tǒng)S =(U ,R,V, f )中，U =X1,X2，Xn為論域，R = CuD是屬性 集合，C =3" =1,2，m與D = d j , j = 1,2，l分別為條件屬性集和決策屬性 集，ak (xj )是樣本Xj在屬性ak上的取值。該系統(tǒng)的分辨矩陣定義為一個n=< n階 矩陣M(S戶mJ淅，其中第i行j行處元素mjak C, ak 二 ak Xj D 為"D 為j電 D (為)=D(xj )i, j =1,2,., n也即，分辨矩陣中

13、元素mij是能夠區(qū)別對象為和Xj的所有屬性的集合。但若Xi和Xj屬于同一個決策類時，則分辨矩陣中元素 mj的取值為空集*0由定義可見,M(S) = mijn>n是一個對稱矩陣，主對角線上的元素是空集。因此只要考慮上半或者下半三角部分足亦。每一個分辨矩陣M(S),可以誘導出一個分辨函數fM(s)如下：fM( ja，a2,，am 產八 vmij ,1 < j <i < n, m. # ®它實際上是一個具有 m元變量aia,., am,(aiC,i=1,2,，m)的布爾函數,它是(vm吠勺合取，而(“mu同矩P筆叫mj中的各元素的析取。根據分辨函數與約簡的對應關系，

14、可以得到計算信息系統(tǒng)S約簡Red(S)的方法為：1)計算信息系統(tǒng)S的分辨矩陣M (S2)計算分辨矩陣M (S )對應的分辨函數fmij ;3)計算分辨函數fm(s 勺最小析取范式，其中每個析取分量對應一個約簡.下面舉例說明如何利用分辨矩陣及分辨函數求約簡及核。設有信息系統(tǒng) S =(U , R), U = x, x，x , R= a ,b ,c ,d某數據表 格如下表所小。表信息系統(tǒng)數據表U/RabcdU/RabcdX10000X41212X20211X51001X30100X61212解：根據式(1-11),分辨矩陣M (S)為：表1-5 分辨矩陣UX1X2X3X4X5X6X1X2b,c,dX

15、3bb,c,dX4a,b,c,da,da,b,c,dX5a,da,b,ca,b,db,c,dX6a,b,c,da,ba,b,c,d一b,c,d再根據式(1-12),分辨函數為fm s a,b,c,d=bc d ) b i：a b c da da b c d b c d a d a b c d |ia b c d i ib c dbcd=bad = ad bd因此，該信息系統(tǒng)有兩個約簡a,b和b,d,核是b。由此得到兩個約簡的數據表格，如表 1-6所示。表1-6兩個約簡數據表UabUbdXi00Xi00X202X221X301X310X412X422X510X501X612X622(2) 決策表

16、決策表是一類特殊而重要的知識表達系統(tǒng)，它是指當滿足某些條件時，決 策應該怎樣進行，多數決策問題都可以用決策表形式來表達，決策表根據知識 表達系統(tǒng)定義如下：設S =(U ,R )為一知識表達系統(tǒng)，若R可劃分為條件屬性集C和決策屬性集D,即 C=D = R,CCD =巾。則稱為 CD 決策表， 改記為 T =(U ,R,C,D )。Ind (C) 的等價類稱為條件類，Ind(D)的等價類稱為決策類。決策表可分為一致決策表和非一致決策表。當D完全依賴于C(Cn D)時,稱為一致的；當部分依賴(C = kD(0<k<1)時，稱決策表是不一致的。特別指出，決策表是否能夠約簡，取決于它是否為一

17、致決策表。這是因為 不同原因可以產生相同結果，但同一個原因則不允許導致多種結果。對于一個 決策表，一般首先將其分解為一個一致決策表與一個不一致的決策表，然后再 對一致決策表進行約簡。約簡的方法還是使用分辨矩陣的方法。此時，屬性特 征集C相對于決策屬性集D的核Core d (C )恰為分辨矩陣中所有m”為單元素集 決定。也即Core d (C) - la" m。s.t. m” =aj, 1 Mi, j 三 n J特別，如果C七C是滿足條件C'Clmj"/x/mj#®, 且C，是最小的，那么稱L為C相對于決策屬性集D的約簡。約簡之后的決策表具有更少的條件屬性，

18、但卻沒有損失知識含量。同樣對 于決策屬性也可以約簡。但是約簡后的決策表還是不能直接看出條件與決策屬 性之間的關系，因此還需要挖掘出決策生成規(guī)則。為此我們引入另外一個量來 刻畫條件屬性子集Xi CC與決策屬性子集Yj U D之間關聯(lián)強度。令Des (X i) - 1(x, vx) | Tx U , vx V s.t. f(x,a) =vx,_a Xi JDes (Yj) - l(x, vx) | _x - U , vx - V s.t. f (x, d ) = vx, 一 d - Yj ?分別稱為屬性子集Xi u C與決策屬性子集Yj u D的描述集。此時，Des(Xi)與Des(Yj)同在空間

19、U MV中，于是可以作如下兩件事：1 .當 Des(Xj 1 Des(Yj) 時， 定義 Des(Xi)到 Des(Yj)的映射 Tj。2 .當Des(Xi)CDes(Yj) 時，定義確定因子度(Xi,Yj) =Card Des (Xi) Des (Yj) /Card (Des (Xi)特別，當邑（Xi，Yj） =1時,品是確定的規(guī)則；當2（Xj,Yj）1時,冊是不確定的規(guī)則。出Xi，Yj）的大小反映的是滿足屬性子集 Xi U C的對象中又能夠滿足決策屬性子集Yj U D的對象所占的比例。5.基于分辨矩陣的啟發(fā)式最小約簡算法以上介紹的約簡的理論方法雖然簡單，但只有通過計算機程序實現才有應 用意

20、義。對于決策表比較復雜，條件屬性較多的情況下，由于對存儲空間的要 求過大，單純使用分辨矩陣很難實現。下面建立一種基于分辨矩陣的啟發(fā)式最 小約簡算法，可以較好地解決這個問題?；诩s簡是必須能夠區(qū)分所有對象的最小屬性集合可以推出：一個約簡與 分辨矩陣的每一項的交都不空（加入與m,不相交，那么對象i與j關于該約簡是 不可分辨的）。于是得出如下“準約簡”算法：輸入：決策表（U,CUD）,其中C =自，i =1,2,，m1 .選取初始約簡Ro o2 .對于所有i, j檢查分辨矩陣的每一項mj和候選約簡集合Ro的交 mj C Ro ,判斷：a）如果mj c Ro為空集，隨機從mij中選擇一個屬性，加到候選約簡 集合Ro中；b）若不空，檢查下一項。3 .重復這一過程，直到分辨矩陣中的每一項都檢查過了。輸出：準約簡。程序完成之后，我們可以得到R=CUD中的一個條件屬性子集R 。但是，一般 R'僅僅是一個“準約簡”。因為上面的算法沒有考慮它的最小性。為了使之變成 真的約簡，我們需要如下的啟發(fā)知識。一個簡單而有效的方法是根據| mij |來對條