粗糙集课件.pdf-资料库

研究生教材《智能信息处理》第五章粗糙集粗糙集（Rough Set，RS）理论是一种刻划不完整性和不确定性的数学工具，能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律。该理论是由波兰学者 Z.Pawlak 教授在 1982 年提出的[12]，1991 年的 Z.Pawlak 出版了第一本关于粗糙集的专著[51]，系统全面地阐述了 RS 理论，奠定了严密的数学基础。该书和 1992 年 R.Slowinski 主编出版的关于粗糙集应用及其相关方法比较研究的论文集较好地总结了这一时期 RS 理论与实践的研究成果[52]，促进了国际上对粗糙集理论与应用的深入研究。从 1992 年至今，每年召开以 RS 为主题的国际会议，推动了 RS 理论的拓展和应用。国际上成立了粗糙集学术研究会。目前 RS 理论已成为人工智能以及计算智能中一个较新的学术热点，且在机器学习、决策分析、数据挖掘和知识发现等领域得到了具体应用和发展，并引起越来越多的科研人员的关注[13,52,53]。粗糙集理论主要研究属性约简和规则提取，为此，本章主要介绍知识约简、属性约简和规则提取等方法。 5.1 粗糙集的基本概念 5.1.1 知识表达系统为了处理智能数据，需要知识的符号表达，而知识表达系统（KRS）的基本成分是研究对象的集合，因此可以表达为： fVQUK = , ( , , ) （5.1.1）这里，U 是论域，即为对象的集合；Q 是属性集合，分为条件属性集C 和决策属性集 D ，Q =C U D ， V C I D =∅ ；是属性值的集合， aV 表示了属性 Qa ∈ 的范围； f 是 VQU →× 的映射。 aQa V = U ∈ 知识表达系统K 有时可以简写为：K =(U ,Q )，它常用表格表达或决策表来实现。 5.1.2 不可辨识关系对于 yx, ∈U ， P ⊆ Q ，如果满足∀ q∈ P : f y、是可辨识的。由P 决定的不可辨识关系记为 ind(P )，即P 中所有等价关系的交集。 x )( = f y )( ，则称对象 x y、对于属性集合 P 是不可辨 q q ∈= { xUy ind( P ) y }表示包含元素 Ux ∈ 的 P 等价类，定义集合Y 的下近识的。否则，称 x 5.1.3 上近似、下近似及近似精度设 P ⊆ Q ，Y ⊂ U ， x P ][ 似PY 和上近似PY 分别为： PY = PY = { − )(Y posP { = xUx P I][ ∈ } Y P ⊆ xUx ][ ∈ （5.1.2） Y ∅ } （5.1.3） bnP ≠ YP bnP Y =)( 此外，定义 YPYP ∅ 或 YP ≠ ，则集合Y 就是一个粗糙集概念。下近似包含了所有那些可能是属于Y 的元素。上近似与下近似的差就是此概念的边界区域，它由不能肯定分类到这个概念或其补集中的所有元素组成。在粗糙集中也采用下面的说称为集合Y 的P -反称为集合Y 的P -正区域（ −P positive region），为 Y 的边界或边界区域（boundary ）。显然，若 YPUY =)( ≠)(Y Y =)( 法，区域（ −P negative region）。如图 5.1 所示，为区域划分的示意图。 neg P posP YP − 78 图 5.1 区域划分示意图注：图中斜线部分为边界；边界所包围的全部区域是上近似区域，中间的空白区为下近似区域，即正区域。

第五章粗糙集由等价关系P 定义的集合Y 的近似精度为： card YP ( card YP ( card U ) )/ ( card YP )/ ( card 表示集合Y 所含元素的个数。 YP )( γ = YP )( =α )(Y 其中， ≠Y ∅ ，（5.1.4） ) （5.1.5）设集合 L 为由决策属性 D 所决定的U 的划分{ 1Y , 2Y ,…, kY }组成，依据上述两个近似精度，则划分 L 关于属性集P 的近似精度为： L )(γ P = k ∑ i 1 = card ( PY i /) card U ( ) （5.1.6） card ( PY i ) （5.1.7） ) ，其中 U = xx ,{ 0 1 , L , x 10 } ，且R 有下列的等 E = 4 XR = xx ,{ 8 4 E = 1 E = ， 5 E 。 } U 4 1 xx ,{ 7 10 } 。 X 2 )/card( )XR 2 = 2/18/4 = 。 L )(α P = k ∑ i 1 = card ( PY i 例 5.1.1 给定一知识库价类： ( QUK = , ) 和一个等价关系 R ∈ /) k ∑ i 1 = ind (K E = 1 集合集合 0 1 ， xx E = },{ 2 X = xxxx ,{ , , 0 xxxxxx X = , , , ,{ 0 xx xxx ,{ ,{ } , 2 为R 的可定义集，因为R } , ， X 为R 粗糙可定义集。 E = ， } } 10 9 6 8 4 1 1 5 3 1 8 5 4 3 2 3 3 2X 的近似集、边界和近似精度分别为： E E xxxx , ,{ } , = U 3 5 8 E E E xxxxxxxx E , ,{ , , , = U U U 3 1 4 0 10 5 8 1 3 7 XR E XR E xxxx } ) ,{ , = − = = ， U 2 2 2 1 5 10 0 card(R card XR cardU ) ( ) /) 11/4 = = = ， 2 为R 内不可定义。因为 xxx ,{ }, 0 3 1 Rα 7 X ， , ( } , , 5 4 2 4 2 ， 3 4 2 集合 2XR ＝ XR = 2 bnR X ( XRγ ( X = 3XR =∅ ， XR E = = U xxxxxx X = ,{ , , 0 4 E = 4XR ＝， U XR =4 ， bnR X E E ) ( = U 4 4 =XRγ ( ) 11/2 。 X = xxxxx , , ,{ , 0 5.1.4 知识约简 E 2 , , 2 xx },{ 1 集合集合 E U U } 3 3 3 1 4 0 1 3 2 7 4 3 2 5 1 , , xxxxxxx ,{ , 0 为R 外不可定义， 4X 的近似集，边界和精度为： } 。 U ≠ } , , 3 2 1 7 9 6 5 E E 5 = 4 U xxxxxxxxx ,{ , 2 , , , , , , 9 8 7 6 5 4 3 10 } ，为 R 全不可定义，因为： 5XR ＝∅ ， XR =5 U 。（1）一般约简设 p ∈ P ，若 ind( P ) = ind( P －{ p })，称 p 是 P 中可省的（或可约简的）属性，否则称 p 是不可省的（或不可约简的）。若对 p ∈P 都是不可省的，称集合P 是独立的，否则称集合P 是相关的。若Q ⊆ P 是独立的，且 ind(Q )=ind( P )，则称Q 是 P 的一个约简。 P 中所有不可省属性的集合称为P 的核，记为 core(P )。设 red(P )是P 的所有约简族，则有关系：core(P )＝∩red (P ) 。核的概念有两方面的意义：第一是它是所有约简的基础，因为核包含于任何约简集之中，并且其计算是直接的；第二，核可以解释为知识最重要部分的集合，进行约简时不能删掉它。一般产生约简的方法是逐个向核中添加可省的关系，并进行检查。计算所有约简核最佳约简都是 NP 难题。（2）相对约简设P 和Q 是全域U 上的等价关系的族集，定义Q 的P -正区域为： pos P Q ( ) = U QUY / ∈ YP 。 79

研究生教材《智能信息处理》 Q ( ) ( P }) ) = aP { − Q ( pos pos 若 Pa ∈ ，，则称关系a 在族集P 中是Q -可省的，否则称为Q -不可省的。若在族集P 中每个关系a 都是Q -不可省的，则称P 关于Q 是独立的，否则就称为是依赖的。如果知识P 仅仅只有一个Q -约简，则知识 P 就是确定的。当知识 P 为不确定的，一般就有多种使用知识 P 的方式。若核为空，则这种不确定性就尤其严重。 = 若 R ⊆ P ， pos pos ，即前后划分 L 的近似精度是不变的。族集 P 中的所有Q -不可省的初等关系的集合成为核，记为 redQ 是P 的所有Q -约简的族集，则有关系 core Q red ，则称 R 是 P 的一个相对约简。由此看出，约简 coreQ 。设。在相对约简中，核是不能删除的。 )(LRγ = )(LPγ Q ( Q ( (P P P ) ) ( ) ( ) ) Q R P I= ) (P （3）知识的依赖性设 , ( RUK = ) Q ，记做 Q QP = 。当且仅当 P ⇒ 。当且仅当 P ⇒ 且 Q 是一个知识库， RQP ⊆, Qind ，则称Q 依赖于P 或P 可推导出 ( ) Qind ，则称 P 和 Q 是等价的，记作 ) ( QP ≠ 。 Q ⇒ 均不成立，则称P 和Q 是独立的，记。当且仅当 Q ⇒ ，即 P ⇒ 且 ind ind ⊆ = P P Q ( ( ) ) P P 依赖性也可以是部分成立的，部分依赖性（部分可推导性）可以由知识的正区域来定义，即 k Q card U pos ( ) ( ) ( = γ = P 依赖于知识 P ,记作 ≤≤ k 我们称知识Q 以依赖度 k )1 0( P ⇒ ；当 Q << k ，则称知识Q 部分依赖于知识P ；当 0=k 0 1⇒ 也记做（5.1.8） P k⇒ 。当 1=k ，则称知识Q 完全依赖于知，则称知识Q 完 card /)) Q ( Q 1 P P 识 P ，即 Q 全独立于知识P 。（4）属性的重要性按照式（5.1.8），条件属性C 和决策 D 间的依赖度可以写成关于D 的重要性为： ' D ( ) = γ C 依赖度的变化，可以定义属性子集 σ CD − γ C = 时，属性a ∈C 关于D 的重要性为： γ CC ⊆' )' a }{' 特别当 a )( C ( D D CC = − ) ( ( ) ( − }{ D aC − σ CD γ C γ C ( D ) = card ( pos C ( D /)) card U ( ) 。根据（5.1.9） ) （5.1.10）一般来说，属性重要性即指属性在信息表中的重要程度，其数值大，则重要性高；反之，其重要性低。在相对属性约简中，属性重要性主要用来作为启发式信息。目前，关于属性重要性的定义有多种，比如有根据信息熵和根据差别矩阵出现的频度等形式的定义，不同定义下的属性重要性计算结果可能有所变化。（5）决策规则的确定性知识系统一般用决策表来表示，在决策表的约简后，最重要的是决策规则的产生。令 iX 和 jY 分别代表 jY )表示对于各决策属性值的特 iX )表示对于各条件属性值的特定取值，des( iX ) → des( jY )， ≠i ∅ Y I X j CU / 与 DU / 中各个等价类，des( 定取值。决策规则定义为： ijr ：des( 规则的确定性因子为 i YXμ , ( j ) ＝ card Y ( X i /) card ( X j I ) ， 0 < i YXμ , ( 1) ≤ i ， ijr 是不确定的。任何有限决策规则集就称为决 j （5.1.11）当 i YXμ ( , 策算法。 ) ＝1 时， ijr 是确定的；当 0 j < i YXμ , ( j 1) < （6）决策表的一致性当且仅当 C ⇒ ，决策表 D DCAUT = ( , , , ) 是一致的（或相容的）。显然，很容易通过计算条件属性和决策属性间的依赖程度来检查一致性。当依赖程度等于 1 时，决策表就是一致的，否则不一致（或称不相容）。使得表 1T 中 , ( 每个决策表 DCAUT = , C 1⇒ 和 2T 中 T = 都可以唯一分解两个决策表 1 D U ) , << k ，即表的结果不一致，则可以将表分解 0 可见，假设我们已经计算出条件属性的依赖度，若依赖度 DCAU , , ( ) bn X ( ) CU= , 1 DCAU T = ) ( 2 UX ∈ / 。 ) 0⇒ 。这里 , 2 ind , D ( pos ,这样 , C , ) U D D 和 = ( , C 1 1 2 成两个子表：其中一个表完全不一致，依赖度为 0，另一个表则完全一致，依赖度为 1。下面举一典例来简单说明知识约简的基本计算过程。例 5.1.2 决策表可以根据知识表达系统定义如下： 80

第五章粗糙集表 5.1.1 知识表达系统条件属性决策属性病人头疼肌肉疼体温 e1 是是正常 e2 是是高 e3 是是很高 e4 否是正常 e5 否否高 e6 否是很高 e7 否否高 e8 否是很高流感否是是否否是是否表 5.1.1 中给出了一个关于某些病人的决策表，其中 U ＝{流感}。令 1C ＝头疼， 2C ＝肌肉疼， 3C ＝体温，则有 = ee ,{ 1 2 , e }, 8 L ，C ＝{头疼，肌肉疼，体温}，D 8 3 2 5 2 1 2 4 6 1 1 2 3 5 , , CU eee eeeee / {{ , , ,{}, , , }} = ， 4 7 6 CU eeeeee ee / {{ , , , , ,{}, , }} = ， 8 3 5 7 CU eee ee eee / {{ {}, , , }{ }} = ； 6 7 4 1 CCU eee eee ee , /{ }} {{ , ,{}, } , ,{}, , = ， 1 7 3 4 8 5 2 1 2 CCU ee ee e e e e /{ , } {{ {}, {}, {}, ,{}, ,{}, = 6 5 7 4 3 2 CCU eee ee e ee , /{ , }} ,{}, ,{}, {}, , {{ } = 5 3 8 1 3 2 CU e e ee e ee e ,{}, {}, ,{}, / {{ {}, {}, }} = ， 5 6 3 4 eeee eeee DU }} , ,{}, , , {{ / , = 。 1 , 8 3 6 1 3 1 7 2 4 7 2 1 8 5 4 7 6 3 2 6 8 ， }} 8 ；因为 posC D ( ) = )D( k = γ C eeee e ,{}{}{}{}{ }, 4 3 1 1 / )U( 84 = = e e U /)D( ） = 4 card U card U pos e 2 （ , 2 = 3 ， . 50 ， C ) ( ( 2 − CC CC 1 所以D 部分依赖（依赖度为 0.5）于C ，决策表是不一致的。又因为 pos eee ,{ }, = ≠ 1 4 eeee ,{ }, , = = 1 4 (D posC ) ≠ = ∅ ee pos D },{ ) ≠ = C 4 1 posC (D D ) ) ≠ = ∅ 所以C 的D 约简（相对约简）为 CC ,{} { = − 1 D ( ) D ( ) D ) () ( (}) pos pos pos pos pos D ( C pos CC D CCC 1 CCC ( ) ( D ) CC − ) { − { − }) C − 3 2 2 ( ( ( ) , , 2 3 2 3 2 } 3 ，C 的 D 核（相对核）也为 1 CC ,{ } 。 3 在决策表中，不同的属性可能具有不同的重要性。例如，当由症状描述病人的情况时，对于识别病人的身体状况有些症状具有更重要的意义。由公式 σ CD r )( = γ C ( D ) − γ }{ D ( rC − ) 计算得： CDσ (头疼)＝4/8－3/8=1/8； CDσ (肌肉疼)＝4/8－4/8=0； CDσ (体温)＝4/8－0=4/8＝0.5 由此可见，在决策表 5.1.1 中，{体温}最重要，其次是{头疼}，{肌肉疼}是不重要的。约简后的决策表如下表 5.1.2 所示。表 5.1.2 约简后的知识表达系统条件属性决策属性流感 D 病人头疼 C1 体温 C2 e1 是正常 e2 是高 e3 是很高 e4 否正常 e5 否高 e6 否很高 e7 否高 e8 否很高否是是否否是是否在约简后的决策表中，最重要的是决策规则的产生。 81

令研究生教材《智能信息处理》 e e e CCU {}, {}, } {}, /{ 3 4 2 3 DU eeee eeee , , ,{}, , / {{ 1 ee ,{}, 6 8 7 1 YY ,{ } 2 ee ,{}, 5 }} ＝ e {{ 1 , { ＝ , 1 = = , }} 8 5 1 4 由表 5.2 可知，确定性决策规则有： 7 6 3 2 XXXXXX , , , , , 4 5 2 3 } ； 6 12r ： 1C （是） 3C （正常）→（流感，否）； 21r ： 1C （是） 3C （高）→（流感，是）； 31r ： 1C （是） 3C （很高）→（流感，是）； 42r ： 1C （否） 3C （正常）→（流感，否）。不确定性规则有： 51r ： 1C （否） 3C （高）→（流感，是）；规则的确定性因子为 0.5。 52r ： 1C （否） 3C （高）→（流感，否）；规则的确定性因子为 0.5。 61r ： 1C （否） 3C （很高）→（流感，是）；规则的确定性因子为 0.5。 62r ： 1C （否） 3C （很高）→（流感，否）；规则的确定性因子为 0.5。则表 5.1.2 可以分解为如下完全一致和完全不一致两个子表。表 5.1.3 完全一致的决策表表 5.1.4 完全不一致的决策表病人头疼 C1 体温 C2 D 病人头疼 C1 体温 C2 D e1 是正常否 e5 否高否 e2 是高是 e7 否高是 e3 是很高是 e6 否很高是 e4 否正常否 e8 否很高否（7）决策表的约简决策表的约简在工程应用中相当重要，同样的决策可以基于更少量的条件，通过一些简单的手段就能获得同样要求的结果。对于一致决策表的约简，其约简步骤是：第一步，对决策表进行条件属性的约简，即从决策表中消去某一列；第二步，消去重复行；第三步，消去每一决策规则中属性的冗余值。对于非一致决策表的约简，其约简步骤与一致决策表的约简步骤类似，只是在重复行的删除中，要视决策规则的一致性而定，若决策规则是一致的，则可删除；若是非一致的，则不能删除。具体约简方法有两种，一种是考虑正域（或近似精度）的变化，按照一致决策表的约简方法进行；另一种是分成完全一致和完全不一致两个子表。对于完全一致子表，采用一致表的约简方法进行约简；对于完全不一致子表，可以直接生成带粗糙算子的决策规则。下面举例说明决策表的约简方法。例 5.1.3：表 5.1.5 为完全一致决策表（k＝简后得到如表 5.1.6 所示。 )D(rC ＝1），其中 a，b，c，d 是条件属性，e 是决策属性，经属性约表 5.1.5 某一致决策表表 5.1.6 消去 c 后的决策表 U a b c d e U a b d e 1 1 0 0 1 1 1 1 0 1 1 2 1 0 0 0 1 2 1 0 0 1 3 0 0 0 0 0 3 0 0 0 0 4 1 1 0 1 0 4 1 1 1 0 5 1 1 0 2 2 5 1 1 2 2 6 2 1 0 2 2 6 2 1 2 2 7 2 2 2 2 2 7 2 2 2 2 下面约简每个决策规则中的条件属性的冗余值，为此须先计算决策规则中条件属性的核值。这里以决策规则 1 的条件属性的核值为例来加以说明。对于决策规则 1，集合 F ＝｛[1] a ，[1] b ，[1] d ｝＝｛[1,2,4,5]，[1,2,3]，[1,4]｝；这里 a (1)＝1， b (1)＝0， d (1)＝1。 82

第五章粗糙集故 [1](a,b,d)＝ ]1[ ]1[ b I ]1[ d a I ＝｛1,2,4,5｝I ｛1,2,3｝I ｛1,4｝＝｛1｝。为了求出可省略范畴（论域 U 的任何子集均称为 U 的一个范畴），必须每次去掉一个范畴，并检查其余范畴的交是否还包含在决策范畴 [1] e ＝｛1,2｝，即： = = = F 1 F 2 F 3 这样就得到决策规则 1 的核值为b (1)＝0。类似地，我们可以计算其它决策规则的核值，其结果如下表。＝｛1,2,3｝I ｛1,4｝＝｛1｝; ＝｛1,2,4,5｝I ｛1,4｝＝｛1,4｝; ＝｛1,2,4,5｝I ｛1,2,3｝＝｛1,2｝; ]1[ I d ]1[ I ]1[ I ]1[ b ]1[ ]1[ d a b a 表 5.1.7 条件属性核值表 U a b d e 1 － 0 － 1 2 1 －－ 1 3 0 －－ 0 4 － 1 1 0 5 －－ 2 2 6 －－－ 2 7 －－－ 2 计算了条件属性的核值后，接着就可以计算属性值的约简。仍以计算决策规则 1 的属性值约简为例。为了计算族F 的约简，必须求出所有的子族 F⊆θ }21{ ，且 ]1[ 。 , ⊆θI e = 这里，F 的三个子族为 1F 、 2F 和 3F ，其中仅有 1F 和 3F 是F 的约简。因此有两个约简值b (1)＝0、d (1)＝1 和 a (1)＝1、d (1)＝1，这表明属性b 、d 的属性值或属性a 、d 的属性值是决策规则 1 的特征，在该决策表中，这个特征不会在其它决策类中出现。同时可以看到属性b 的值是两个属性值的约简的交，即b (1)＝0 是其核值。各决策规则的属性值的约简如表 5.1.8 所示。表 5.1.8 各决策规则的属性约简表 U a b d e 1 1 0 × 1 1’ × 0 1 1 2 1 0 × 1 2’ 1 × 0 1 3 0 × × 0 4 × 1 1 0 5 × × 2 2 6 × × 2 2 6’ 2 × × 2 7 × × 2 2 7’ × 2 × 2 7’’ 2 × × 2 从表 5.1.8 可以看到，决策规则 1、2 有两个条件属性值的简化，决策规则 3、4、5 只有一个条件属性值的简化，决策规则 6 有两个条件属性值的简化，决策规则 7 有三个条件属性值的简化。因此，决策规则 1、2 有两种简化形式，决策规则 3、4、5 只有一种简化形式，而决策规则 6、7 分别有两种和三种简化形式。这样，该问题一共有 24 种解，即（2×2）×（1×1×1）×2×3＝24。例如，其中两种解如表 5.1.9 和表 5.1.10 所示。表 5.1.9 一种决策规则的属性约简表表 5.1.10 一种决策规则的属性约简表 U a b d e U a b d e 1 1 0 × 1 1 1 0 × 1 2 1 × 0 1 2 1 0 × 1 3 0 × × 0 3 0 × × 0 4 × 1 1 0 4 × 1 1 0 5 × × 2 2 5 × × 2 2 6 × 2 × 2 6 × × 2 2 7 2 × × 2 7 × × 2 2 83

由表 5.3.6 可知，合并重复行，最后得到该问题的最小解，其中一个最小解如表 5.1.11 所示。研究生教材《智能信息处理》表 5.1.11 决策规则的一种最小解 U a b d e 1 1 0 × 1 2 0 × × 0 3 × 1 1 0 4 × × 2 2 根据本文介绍的方法，利用决策表对知识约简，首先要进行条件属性的约简，消去复重行，然后对每一决策规则进行冗余属性值的约简，合并重复行，导出约简决策表，得到最小解的简单算法。值得指出的是，决策表的约简不是唯一的，即问题的最小解不是唯一的，这样就可以按照某些要求对问题的解进行优化。下面举例说明对于非一致决策表的约简过程。这里采用分成完全一致和完全不一致两个子表的方法，对于完全一致子表，使用一致表的约简方法进行约简；对于完全不一致子表，直接生成带粗糙算子的决策规则。例 5. 1.4 如表 5.1.12 所示的知识表达系统， C = ={{1,5},{2,8},{3},{4},{6},{7}}, cba }, ,{ DU / ={{1},{2,7},{3,6},{4},{5,8}}， },{ edD = 和分别为条件属性和决策属性。 posC (D ) ={{3},{4},{6},{7}},则因为 Dr ( = C CU / ) = k 18/4 ≠ ,这表明表 5.1.12 是不一致的。故可分解为如下的两个子表 5.1.13 和 5.1.14。表 5.1.12 一个知识表达系统的决策表 U a b c d e 1 1 0 2 2 0 2 0 1 1 1 2 3 2 0 0 1 1 4 1 1 0 2 2 5 1 0 2 0 1 6 2 2 0 1 1 7 2 1 1 1 2 8 0 1 1 0 1 ={{3},{4},{6},{7}}， DU / 对于表 5.1.13， CU / 5.1.13 是完全一致的，该表中所有的决策规则是一致的。 ={{3,6},{4},{7}}， posC (D ) ={{3},{4},{6},{7}}，因此表对表 5.1.14， CU / ={{1,5},{2,8}}, DU / ={{1},{2},{5,8}}，的，该表中对应的决策规则是不一致的。 =DrC ) ( 4/0 = 0 ，因此表 5.1.14 是完全不一致对表 5.1.13 进行约简，得到它对应的条件属性约简为 },{ ba 、 },{ ca 和 },{ cb 。取约简 },{ ba ，对应的表如表 5.1.15 所示。表 5.1.13 完全一致的决策表表 5.1.14 完全不一致的决策表表 5.1.15 表 5.1.13 去掉c 的决策表 a b c d e a b c d e a b d e 2 0 0 1 1 1 0 2 2 0 2 0 1 1 1 1 0 2 2 0 1 1 1 2 1 1 2 2 2 2 0 1 1 1 0 2 0 1 2 2 1 1 2 1 1 1 2 0 1 1 0 1 2 1 1 2 b 0 →∨ 对表 5.1.15 进行条件属性值的约简，得到其对应的决策规则： ed 21 对表 5.1.14 不进行处理，直接生成带粗糙算子的决策规则： → ed 22 ba 12 ed 11 → → → → b 2 ed 21 , cba 201 cba 201 ed 02 , cba 110 a 1 5.0 5.0 , , ed 10 , cba 10 12 → 5.0 ed 10 5.0 最后，将两个决策表的决策规则合并，即可得到原决策表的决策算法。 5.2 属性约简属性约简就是消去知识中的冗余属性，这是决策表约简的重要环节。由于所有约简的计算是 NP 难题[83]，因此运用启发信息来简化计算以找出最优或次优约简是必要的。现今属性约简算法一般都是用核作为约简的出发点 [83]，计算一个最好的或者用户指定的最小约简。将属性重要性作为启发规则，按照属性重要性从大到小逐个加入属性，直到该集合是一个约简为止。为此本节在介绍差别矩阵法后，着重介绍基于启发性信息的属性约简 84

方法。 5.2.1 差别矩阵方法第五章粗糙集 1991 年 A Skowron 从粗糙集理论出发提出用差别矩阵（discernibility matrix）的形式来表示知识的方法[56]有很多优点，特别是它能容易地计算核与约简，目前已成为一种常用的计算所有属性约简的方法[52,53]。属性集合，信息系统L 的差别矩阵设信息系统L =(U , A )，其中U ＝{ 1x , )(LM ＝[ c ∈= 2x ,…, ] nnijc × xaAa { : ( ij ，其中矩阵项的定义如下： ) ≠ xa ( j i ji ,), = ,...,2,1 n } nx }是论域，即所讨论的个体的集合； A ＝{ 1a , 2a ,…, ma }是因此， ijc 是 ix 与 jx 有区别的所有属性的集合。核 core( A )是差别矩阵中所有单个元素组成的集合。采用差别矩阵法进行属性约简的基本步骤如下。第一步，计算信息系统L 的差别矩阵第二步，计算与 )(LM 相关联的差别函数 )(LM ，因为 (LMf ； ) )(LM 是对称的，常用下三角形表示之；第三步，求出差别函数该方法与一般约简算法相比，可以降低一半计算量，但存在的问题就是它只适合于非常小的数据集。 (LMf 的最小析取范式，它将给出所有的属性约简。 ) 例 5.2.1：采用差别矩阵法求约简集表 5.2.1 信息表 )(L 表 5.2.2 差别矩阵 )(LM U a b c d U 1 2 3 4 5 1 0 1 2 0 1 2 1 2 0 2 2 a,b,c,d 3 1 0 1 0 3 a,b,c a,b,c,d 4 2 1 0 1 4 a,c,d a,b,d a,b,c,d 5 1 1 0 2 5 a,c,d b b,c,d a,d 由信息表（表 5.2..1）计算得到的差别矩阵 )(LM 如表 5.2.2 所示，然后计算与 )(LM 相关联的差别函数 (LMf ，即 ) (LMf ) = [(a∨b∨c∨d) ( a∨b∨c) (a∨c∨d) (a∨c∨d)] ·[ (a∨b∨c∨d) (a∨b∨d) b] ·[ (a∨b∨c∨d) (b∨c∨d) ]· [(a∨d)] = ab∨bd 。具体运算如下：其中第一列(a∨b∨c∨d) (a∨b∨c) (a∨c∨d)，经吸收等逻辑运算并化简为①：(a∨b∨c)∧ (a∨c∨d)；同理，第二列经类似处理后并加上①简化为：b (a∨b∨c) (a∨c∨d)，得到②：b (a∨c∨d) ；第三列范式加上②简化为：(b∨c∨d) b (a∨c∨d)，简化得到③：b (a∨c∨d)；第四列加上③：(a∨d) b (a∨c∨d)，简化得到：(a∨d) b = ab∨bd。即得到最小析取范式。则这个知识表达系统有两个约简{a,b}和{b,d}，核是{b}。对于决策表L =(U , A )， A =C U D ，C I D =∅ ，也可以类似计算出相对约简和核，只是当决策属性相同时不参与计算，核由单个元素的组成。下面举例说明之。例 5.2.2：采用差别矩阵法求决策表的约简集，其中条件属性为 a、b、c、d，决策属性为 e。 )(LM 表 5.2.3 信息表 )(L 表 5.2.4 差别矩阵 U a b c d e U 1 2 3 4 5 1 1 0 2 1 0 1 2 0 0 1 2 1 2 a,c,d 3 2 0 2 1 0 3 a,c,d 4 0 0 2 2 2 4 a,d c a,d 5 1 1 2 1 0 5 a,b,c,d a,b,d 由决策表（表 5.2..3）计算得到的差别矩阵 )(LM 如表 5.2.4 所示，然后计算与 )(LM 相关联的差别函数 (LMf ，即 ) 85

资料库

粗糙集课件.pdf

相关推荐

课程资源

热门标签

最新资料