粗糙集理论及其应用

1、粗糙集理论及其最新进展粗糙集理论及其最新进展胡军 博士计算智能重庆市重点实验室主要内容主要内容 1.粗糙集发展历程 2.粗糙集的基本理论介绍 3.粗糙集对集合理论的扩展 4.粗糙集对数理逻辑的拓展 5.粗糙集的不确定性度量方法研究 6.粗糙集的属性约简算法研究 7.粗糙集的扩展模型 8.粗糙集的典型应用粗糙集发展历程粗糙集发展历程 1970s，Pawlak和波兰科学院、华沙大学的一些逻辑学家，在研究信息系统逻辑特性的基础上，提出了粗糙集理论的思想。 在最初的几年里，由于大多数研究论文是用波兰文发表的，所以未引起国际计算机界的重视，研究地域仅限于东欧各国。 1982年，Pawlak发表经典论文R

2、ough sets，标志着该理论正式诞生。 1991年，Pawlak的第一本关于粗糙集理论的专著Rough sets: theoretical aspects of reasoning about data；Pawlak教授（教授（1926年年-2006年）年）粗糙集发展历程粗糙集发展历程 1992年，Slowinski主编的Intelligence decision support: handbook of applications and advances of rough sets theory的出版，奠定了粗糙集理论的基础，有力地推动了国际粗糙集理论与应用的深入研究。 1992年，在波

3、兰召开了第一届国际粗糙集理论研讨会，有15篇论文发表在1993年第18卷的Foundation of computingand decision sciences上。 1995年，Pawlak等人在ACM Communications上发表“Rough sets”，极大地扩大了该理论的国际影响。粗糙集发展历程粗糙集发展历程 1993和1994年，分别在加拿大、美国召开第二、三届国际粗糙集与知识发现（或软计算）研讨会。 19961999年，分别在日本、美国、美国、日本召开了第4-7届粗糙集理论国际研讨会。 1998年至今，偶数年召开RSCTC, 奇数年召开RSFDGrC。 2001年至今，每年召

4、开CRSSC。 2006年至今，每年召开RSKT。 CRSSC2001, ChongqingCRSSC2002, SuzhouCRSSC2003,RSFDGrC2003, ChongqingCRSSC2004, ZhoushanCRSSC2006, JinhuaCRSSC2005, AnshanRSKT2006, ChongqingCRSSC2007, TaiyuanCRSSC2008, XinxiangRSKT2008, ChengduIFKT2008, ChongqingIFTGrCRSP2006,NanchangCRSSC2009, ShijiazhuangRSKT2010, Beiji

5、ngCRSSC2010, ChongqingTRS2010, Zhoushan主要内容主要内容 1.粗糙集发展历程 2.粗糙集的基本理论介绍 3.粗糙集对集合理论的扩展 4.粗糙集对数理逻辑的拓展 5.粗糙集的不确定性度量方法研究 6.粗糙集的属性约简算法研究 7.粗糙集的扩展模型 8.粗糙集的典型应用粗糙集的基本理论介绍确定问题的研究不确定问题的研究1980年，年，数学：确数学：确定性的丧失定性的丧失经典的数学工具，经典的数学工具，如集合论如集合论拓展的数学工具，拓展的数学工具，如概率论、模糊集、如概率论、模糊集、粗糙集、云理论等粗糙集、云理论等转移逐渐成为人工智逐渐成为人工智能研究中的热点

6、能研究中的热点问题问题粗糙集的基本理论介绍不不确确定定性性随机性随机性模糊性模糊性不完整不完整不稳定不稳定不一致不一致主要的特主要的特性性.粗糙集的基本理论介绍随机性随机性：是由于条件不能决定结果而表现是由于条件不能决定结果而表现出来的不确定性，反映了出来的不确定性，反映了因果律因果律的问题。解的问题。解决随机性问题的典型数学方法是决随机性问题的典型数学方法是概率论概率论。模糊性：模糊性：是由于概念外延边界的不清晰而表是由于概念外延边界的不清晰而表现出来的不确定性，反映了现出来的不确定性，反映了排中律排中律的问题。解的问题。解决模糊性的典型数学方法是决模糊性的典型数学方法是模糊集理论模糊集理论

7、。粗糙集的基本理论介绍自然界中大部分事物所呈现的信息都是：自然界中大部分事物所呈现的信息都是： 不完整的、不精确的、模糊的和含糊的不完整的、不精确的、模糊的和含糊的 经典集合论和逻辑方法无法准确、圆满地描经典集合论和逻辑方法无法准确、圆满地描述和解决这些问题。述和解决这些问题。 粗糙集理论的提出主要是为了描述并处理粗糙集理论的提出主要是为了描述并处理“含糊含糊”信息。信息。粗糙集的基本理论介绍（1 1）经典集合：）经典集合：个体个体x x与集合与集合S S的关系是的关系是xx属于属于S S 或者或者x x不属于不属于S S。Sx1x2特点特点：（1 1）集合的边界没有宽度；集合的边界没有宽度；

8、 （2 2）每个元素要么属于）每个元素要么属于S S，要么不属于，要么不属于S S，具有确定性。，具有确定性。粗糙集的基本理论介绍（2 2）“含糊含糊”（VagueVague）问题的提出）问题的提出 19041904年谓词逻辑创始人年谓词逻辑创始人G. Frege (G. Frege (弗弗雷格雷格) )首次提出将含糊性归结到首次提出将含糊性归结到 “边界线边界线区域区域” ” (Boundary region)(Boundary region)： 在论域上存在一些个体，它既不能被在论域上存在一些个体，它既不能被分类到某一个子集上，也不能被分类到该分类到某一个子集上，也不能被分类到该子集的补集

9、上。子集的补集上。G. Frege, Correspondence with Russell, in N. Salmon and S. Soames (eds.), Propositions and Attitudes, 1904. 粗糙集的基本理论介绍（3 3）模糊集合的提出：）模糊集合的提出：个体个体x x与集合与集合S S的关系是的关系是xx以一定的程度属于以一定的程度属于S S。哪些属于哪些属于“高个子高个子”这个集合？这个集合？19651965年美国的年美国的ZadehZadeh教授首次提出教授首次提出粗糙集的基本理论介绍 Eg. Mr. Smith is 180CM. He is

10、very tall (with a membership of 0.8). He is tall (with a membership of 0.9). x1x2Stall001180very tall001200stature(CM)stature(CM)粗糙集的基本理论介绍 模糊集虽然解决了边界域元素的模糊集虽然解决了边界域元素的“亦此亦彼亦此亦彼”的现象，但没有很好解决的现象，但没有很好解决G. FregeG. Frege提出的提出的“含糊含糊”问题，如：问题，如：未给出未给出计算含糊元素数目的数学公式计算含糊元素数目的数学公式；未给出未给出描述含糊元素隶属度的形式化方法描述含糊元素隶属

11、度的形式化方法；隶属度函数本身是不确定的隶属度函数本身是不确定的； 粗糙集的基本理论介绍180CM is very tall with a membership 0.8. Why not 0.81 or 0.79? What is the difference between 0.79, 0.80, and 0.81? How can we make the decision?Why triangle or trapezoid?粗糙集的基本理论介绍粗糙集运用集合论中的粗糙集运用集合论中的“等价关系（不可区等价关系（不可区分关系）分关系）” ，将，将边界线区域边界线区域定义为定义为“上近似上近似

12、集集”与与“下近似集下近似集”的差集；的差集；在在“真真”、“假假”二值之间的二值之间的“含糊度含糊度” 可可计算计算；给出了给出了含糊元素数目的计算公式含糊元素数目的计算公式；粗糙集的基本理论介绍中国版图的边界中国版图的边界例如例如粗糙集的基本理论介绍中国版图的上、下近似中国版图的上、下近似粗糙集的基本理论介绍中国版图边界域随知识粒度的细化而减小中国版图边界域随知识粒度的细化而减小 粗糙集的基本理论介绍边边界界线线的的不不确确定定性性模糊集用隶属度来描述模糊集用隶属度来描述粗糙集用精确的边界线粗糙集用精确的边界线（上、下近似集）来描述（上、下近似集）来描述用非精确的方法处用非精确的方法处理不

13、确定问题理不确定问题通过客观数通过客观数据计算据计算用精确的方法处理用精确的方法处理不确定问题不确定问题处理不确处理不确定性问题定性问题方面具有方面具有很强的互很强的互补性补性粗糙集的基本理论介绍 主要优点主要优点 除数据集之外，无需任何先验知识（或信息） 对不确定性的描述与处理相对客观 【说明】：Bayes理论（先验分布 ）、模糊集理论（隶属度函数）等都需要先验知识，具有很大的主观性。粗糙集理论的基本概念 “知识知识”的定义 使用等价关系集R对离散表示的空间U进行划分，知识就是R对U划分的结果，记为U|R。 “知识库知识库”的形式化定义 等价关系集R中所有可能的关系对U的划分 表示为：K =

14、 (U, R)粗糙集理论的基本概念 “信息系统信息系统”的形式化定义的形式化定义 S = U, A, V, f， U：对象的有限集 A：属性的有限集，A=CD，C是条件属性子集，D是决策属性子集 V： ， Vp是属性P的域 f：U A V是总函数，使得 对每个xi U, q A, 有f(xi, q) Vq 一个关系数据库可看作一个信息系统，其一个关系数据库可看作一个信息系统，其“列列”为为“属性属性”，“行行”为为“对象对象”。PApVV粗糙集理论的基本概念 设PA，xi, xj U, 定义二元关系INDP称为等价关系等价关系： 称xi, xj在S中关于属性集P是等价的，当且仅当p(xi)=p

15、(xj)对所有的pP 成立，即xi, xj不能用P 中的属性加以区别。一般，等价关系INDP也可简记为P。)()(,|),()(jijixpxpPpUUxxPIND等价关系示例等价关系示例：objectweatherroadtimeaccident1mistyicydayyes2foggyicynightyes3mistynot icynightyes4sunnyicydayno5foggynot icyduskyes6mistynot icynightno等价关系示例等价关系示例： 可知， U = 1, 2, 3, 4, 5, 6 R = 2 weather, road, time, acc

16、ident 若P = weather, road，则 U|P= U| weather U| road = 1, 3, 6, 2, 5, 4 1, 2, 4, 3, 5, 6 = 1, 2, 4, 3, 6, 5 集合的上近似 & 下近似 在信息系统S = U, A, V, f中，设XU是论域上的子集，PA，则X的下和上近似集及边界区域分别为： 若 ，成X是可定义的，否则是不可定义的，或者称为粗糙的。 X是包含于X的最大可定义集； X是包含X的最小可定义集。/|P XYUPYX/|P XYUP YX PXPXPP正域、边界域和负域正域、边界域和负域上、下近似将论域U划分成三个区域：正域、

17、边界域和负域。其定义如下：其中，BNDP(X)是既不能在XU上被分类，又不能在U-X上被分类的那些元素的集合。()()()pPpPOSXPXBNDXPXPXNEGXUPX上、下近似关系举例上、下近似关系举例： X1 = u | Flu(u) = yes = u2, u3, u6, u7 RX1 = u2, u3 = u2, u3, u6, u7, u5, u8X2 = u | Flu(u) = no = u1, u4, u5, u8RX2 = u1, u4 = u1, u4, u5, u8, u6, u7X2RU Headache Temp. Flu U1 Yes Normal No U2 Y

18、es High Yes U3 Yes Very-high Yes U4 No Normal No U5 N N No o o H H Hi i ig g gh h h N N No o o U6 No Very-high Yes U7 N N No o o H H Hi i ig g gh h h Y Y Ye e es s s U8 No Very-high No 由R = Headache, Temp. 划分出来的等价类有:u1, u2, u3, u4, u5, u7, u6, u8.X1R主要内容主要内容 1.粗糙集发展历程 2.粗糙集的基本理论介绍 3.粗糙集对集合理论的扩展 4.粗糙

19、集对数理逻辑的拓展 5.粗糙集的不确定性度量方法研究 6.粗糙集的属性约简算法研究 7.粗糙集的扩展模型 8.粗糙集的典型应用 3.The extension of set theory3.The extension of set theory The classical set theory was founded by Cantor, and it is the basis of mathematics and logic. However, the classical set theory can not be used to address the problems with unce

20、rtainty. So, it is necessary to extend set theory.The operation of Cantor setsThe operation of Cantor sets |ABx xAxBABU |Ax xAxUUAThe operation of Cantor sets |ABx xAxBABU |ABx xAxBABU Zadeh used fuzzy membership function to characterize the belonging of an element to a set with uncertainty, and cal

21、led it fuzzy sets.Fuzzy setsFuzzy setsThe complement of a fuzzy setThe complement of a fuzzy setLet A be a fuzzy set：( )1( )AAxx AAThe intersection of two fuzzy setsThe intersection of two fuzzy setsLet A and B be two fuzzy sets：( )min( ),( )ABABxxxAB( )max( ),( )ABABxxxABLet A and B be two fuzzy se

22、ts：The Union of two fuzzy setsThe Union of two fuzzy setsRough setsRough sets Fuzzy set theory mainly used to addressed the problems with vagueness boundary. In real problem, the uncertainty can be induced by imprecision or incompleteness of knowledge.The ellipse can not be described accurately. Paw

23、lak used upper and lower approximation to describe an object set. That provide a method to characterize a set approximately.| ;RRXx U xX| RRXx U xXX()RXRXThe complement of rough The complement of rough sets(lower approximation)sets(lower approximation)RX()RXXX()RXRXThe complement of rough sets(upper

24、 approximation)RX()RXXXABThe union of rough setsThe union of rough sets（lower approximationlower approximation）()R ABRARB()R ABRARBABThe union of rough sets（lower approximation）()R ABRARB()R ABRARBABABThe boundary decreases by The boundary decreases by unionunionThe intersection of rough The interse

25、ction of rough setssets（lower approximationlower approximation）()R ABRARB()R ABRARBABABThe intersection of rough The intersection of rough sets(upper approximation)sets(upper approximation)()R ABRARB()R ABRARBABABThe difference of rough setsThe difference of rough sets（lower approximationlower appro

26、ximation）()( )R ABRAR B()R ABRA( )R BABABThe difference of rough setsThe difference of rough sets（upper approximationupper approximation）()( )R ABRAR B()R ABRA( )R BABABThe boundary increases by The boundary increases by intersectionintersectionThe relationship of rough The relationship of rough set

27、s and fuzzy setssets and fuzzy sets(1)(1) Rough set theory uses precise method to process Rough set theory uses precise method to process uncertainty, but fuzzy set theory uses imprecise uncertainty, but fuzzy set theory uses imprecise method to process uncertainty. method to process uncertainty. (2

28、)(2) Fuzzy membership function is the key in Fuzzy membership function is the key in processing problems, but it relies on domain expert. processing problems, but it relies on domain expert. Rough set theory do not rely on prior knowledge.Rough set theory do not rely on prior knowledge.(3)(3) In som

29、e real problem, combination of these two In some real problem, combination of these two theory can be used to process more complex problems theory can be used to process more complex problems that can not be processed by any one of them. that can not be processed by any one of them. The key to the p

30、resented approachis provided by the exact mathematical formulation,of the concept of approximative (rough) equalityof sets in a given approximation space. Zdzisaw Pawlak, 1982.主要内容主要内容 1.粗糙集发展历程 2.粗糙集的基本理论介绍 3.粗糙集对集合理论的扩展 4.粗糙集对数理逻辑的拓展 5.粗糙集的不确定性度量方法研究 6.粗糙集的属性约简算法研究 7.粗糙集的扩展模型 8.粗糙集的典型应用 4.4.粗糙集对数理

31、逻辑的拓展粗糙集对数理逻辑的拓展 伴随着粗糙集理论的发展，伴随着粗糙集理论的发展，RoughRough逻辑逻辑得到了研究，并建立得到了研究，并建立了了Rough Rough 逻辑演绎系逻辑演绎系统统。Rough逻辑6 5 2 1 1 0信息系统 IS=(U,A)Rough逻辑是一种被定义逻辑是一种被定义在信息系统在信息系统S=(U,A)上的上的非标准逻辑非标准逻辑。这种逻辑。这种逻辑的谓词被定义在属性集的谓词被定义在属性集A上，谓词的取值是上，谓词的取值是A上的上的一个属性。一个属性。011256221235210204220433120432110451edcbaAURough逻辑6 5 2

32、 1 1 0信息系统 IS=(U,A)个体变量的取值可以个体变量的取值可以是是U U上的一个对象；上的一个对象；011256221235210204220433120432110451edcbaAU6 5 2 1 1 0比如对象比如对象6 6Rough逻辑6 5 2 1 1 0信息系统 IS=(U,A)011256221235210204220433120432110451edcbaAUab234334个体变量的取值也可个体变量的取值也可以是以是U U上的一个粒上的一个粒( (依赖于某种因素的对依赖于某种因素的对象集合象集合) ) 信息系统 IS=(U,A)UAabcd/p>

33、1334022402012532122652110从该系统IS上可提取公式 如提取下面公式如提取下面公式: a3 b4c0340abcUNameSexAgeTVp1WangMale653.5p2LiFemale303.2p3ZhangMale704.3p4LiuFemale555.1p5LiFemale483.8一个中医诊疗信息系统这个系统具有测试这个系统具有测试患者血液粘滞浓度患者血液粘滞浓度的功能，从临床的功能，从临床采集的患者数据集合采集的患者数据集合, ,如：如： P=NameP=Namex x,Sex,Sexy y,Age,Agez z, ,TVTVw w 最后最后, , 这个患者这

34、个患者WangWang被诊断为级别被诊断为级别 Level=-5, Level=-5, 属于低血液粘滞综合征属于低血液粘滞综合征 (BLVS)(BLVS)。专家的经验推理专家的经验推理转化为转化为利用利用RoughRough逻辑公式的语义分析的逻辑公式的语义分析的一种推理一种推理. . UNameSexAgeTVp1WangMale653.5p2LiFemale303.2p3ZhangMale704.3p4LiuFemale555.1p5LiFemale483.8一个中医诊疗信息系统 RoughRough逻辑可实现逻辑可实现非单调的近似推理非单调的近似推理 RoughRough逻辑定义在逻辑定

35、义在信息系统信息系统上上, , 具体直观具体直观 RoughRough逻辑演算要求的逻辑演算要求的条件比较宽松条件比较宽松主要内容主要内容 1.粗糙集发展历程 2.粗糙集的基本理论介绍 3.粗糙集对集合理论的扩展 4.粗糙集对数理逻辑的拓展 5.粗糙集的不确定性度量方法研究 6.粗糙集的属性约简算法研究 7.粗糙集的扩展模型 8.粗糙集的典型应用不确定性度量概述不确定性度量概述 根据度量的对象 概念的不确定性，如粗糙集的粗糙度、粗糙熵、模糊度、模糊熵和修正模糊度等 。 决策的不确定性，如近似分类精度、近似分类质量和条件信息熵等 。知识的粒度对粗糙集的不确定性和决策规则的不确知识的粒度对粗糙集的

36、不确定性和决策规则的不确定性起决定作用。反之，粗糙集的不确定性和决策定性起决定作用。反之，粗糙集的不确定性和决策规则的不确定性也一定程度反映了知识的粒度。规则的不确定性也一定程度反映了知识的粒度。 知识粒度知识粒度 一般而言，知识粒度越细，则其对概念的描述越精确，相应概念的不确定性越小。知识粒度的定性分析知识粒度的定性分析因而，若要判断两个知识之间是否存在较细关系，可以从三个角度来进行分析。知识粒度的性质知识粒度的性质知识粒度实例知识粒度实例知识粒度性质知识粒度性质知识粒度的定量分析知识粒度的定量分析定理定理1 1说明知识粒度越小，则其信息熵越大，这与人说明知识粒度越小，则其信息熵越大，这与人

37、们的直观认识是相符的。但是，该定理的逆并不成们的直观认识是相符的。但是，该定理的逆并不成立。立。 苗夺谦, 王珏. 粗糙集理论中知识粗糙性与信息熵关系的讨论. 模式识别与人工智能. 1998, 11(1): 34-40 知识粒度的定量分析知识粒度的定量分析Liang J Y, Chin K S, Dang C Y, et al. A new method for measuring uncertainty and fuzziness in rough set theory. International Journal of General Systems. 2002, 31(4): 331-3

38、42 Liang J Y, Shi Z Z. The information entropy, rough entropy and knowledge granulation in rough set theory. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems. 2004, 12(1): 37-46粗糙集（概念）的不确定性度量粗糙集（概念）的不确定性度量 三种思路 基于粗糙集的物理特征，如粗糙度； 基于信息熵的定义，如粗糙熵； 基于不确定的转换，如模糊度，模糊熵；粗糙集的粗糙度粗糙集的粗

39、糙度Pawlak Z. Rough sets: theoretical aspects of reasoning about data. Boston: Kluwer Academic Publishers, 1991 粗糙度的问题分析粗糙度的问题分析粗糙集的粗糙熵粗糙集的粗糙熵Liang J Y, Shi Z Z. The information entropy, rough entropy and knowledge granulation in rough set theory. International Journal of Uncertainty, Fuzziness and Kn

40、owledge-Based Systems. 2004, 12(1): 37-46粗糙熵的问题分析粗糙熵的问题分析粗糙集的模糊度粗糙集的模糊度Chakrabarty K, Biswas R, Nanda S. Fuzziness in Rough Sets. Fuzzy Sets and Systems. 2000, 110: 247-251 模糊度的问题分析模糊度的问题分析粗糙度的修正粗糙度的修正 设为Pawlak近似空间，为的任意子集，则在中的修正粗糙度定义如下： 显然，上述定义在下近似为空的情况下，仍然具有区分能力。 1 |( )| ( )|( )()2|XR XR XXXXUX胡军,

41、王国胤, 粗糙集的不确定性度量准则研究, 模式识别与人工智能, 2010，23(5): 606-615 模糊度的修正模糊度的修正 设为Pawlak近似空间，X为U的任意子集，则粗糙集的修正模糊度定义如下： 上述定义修正了Chakrabarty等人提出的粗糙集模糊度随着知识粒度减小反而可能增加的缺陷。11( )( )ln( ) (1( )ln(1( )ln2RRRRXXXXniiiiFFFFid Xxxxxn王国胤, 张清华, 不同知识粒度下粗糙集的不确定性研究, 计算机学报, 31(9): 1588-1598 主要内容主要内容 1.粗糙集发展历程 2.粗糙集的基本理论介绍 3.粗糙集对集合理论

42、的扩展 4.粗糙集对数理逻辑的拓展 5.粗糙集的不确定性度量方法研究 6.粗糙集的属性约简算法研究 7.粗糙集的扩展模型 8.粗糙集的典型应用属性约减的分类属性约减的分类 绝对约减 所谓绝对约减是指去掉部分属性后，不改变信息系统的区分能力。 相对约减 所谓相对约减是指去掉部分条件属性后，不改变信息系统对决策的分类能力。绝对约减绝对约减绝对约减绝对约减绝对约减实例绝对约减实例相对约减相对约减相对约减相对约减相对约减实例相对约减实例利用区分矩阵进行属性约简利用区分矩阵进行属性约简区分矩阵区分矩阵（discernibility matrixdiscernibility matrix）：）：在信息系统

43、T= (U, CD, V, f)中，C为条件属性，D为决策属性，设对象全集U按决策属性D被分成不相交的类族，即X1,X2,Xm，则S中C的区分矩阵M(C)= mi,jnxn定义为：, , 1, , ( , )( ,) : ( , )( ,), ,iji jijijijijx xDmx xDcC f c xf c xcC f c xf c xx xD 的同一等价类的不同等价类，对 的不同等价类其中，1 i j n。 利用区分矩阵进行属性约简利用区分矩阵进行属性约简 令M是决策表T的可辨识矩阵，A=a1,a2,.,an,是T中所有条件属性的集合.S是M中所有属性组合的集合，且S中不包含重复项.令S

44、中包含有s个属性组合，每个属性组合表示为Bi，其公式化描述为: BiS, BjS, BiBj (i,j=1,2,.,s). 令Card(Bi)=m，则Bi中每个条件属性表示为 bi,k Bi (k=1,2,.,m) 令C0是M中的核属性集，则有C0 A.利用区分矩阵进行属性约简利用区分矩阵进行属性约简算法步骤算法步骤： 第1步. 将核属性列入属性约简后得到的属性集合，即red=C0； 第2步. 在可辨识矩阵中找出所有不包含核属性的属性组合S，即 第3步. 将属性组合S与red表示为合取范式的形式，即 P=red bi,k :(i=1,2,.,s;k=1,2,.,m)第4步. 将P转化为析取范式

45、形式；第5步. 根据需要选择满意的属性组合., 2 , 1,:siredBBSii利用区分矩阵进行属性约简利用区分矩阵进行属性约简U/Aabcdeu110210u200121u320210u400222u511210实例：T=（U，A，V，f），A=a,b,c,de uu1u2u3u4u5u1 u2 ca, b, c, du3 u4 u5 a, c, da, da, c, da, da, b, d利用区分矩阵进行属性约简区分矩阵：利用利用区分区分矩阵进行矩阵进行属性属性约简约简 由上述差别矩阵很容易得到核为： c 区分函数fM(S)为：c(ad)，即 (ac)(cd) 得到两个约简 a, c和

46、c, d 利用区分矩阵进行属性约简利用区分矩阵进行属性约简UAaceu1120u2011u3220u4022u5120UAcdeu1210u2121u3210u4222U5210根据得到的两个约简，可得两个约简后的新决策表：利用启发式搜索进行属性约简利用启发式搜索进行属性约简 正区域：正区域：在信息系统S=(U, CD, V, f)中，设D*= X1,X2,Xm，属性子集PC关于决策属性D的“正区域”定义为： :)(*DXXBDPOSP P关于D的正区域表示那些根据属性子集P就能分入正确类别的所有对象。利用启发式搜索进行属性约简利用启发式搜索进行属性约简相关程度：相关程度： 条件属性子集PC与

47、决策属性D的相关程度（也称依依赖程度赖程度）定义为：)()(),(UcardDPOScardDPkP 显然，0 k(P, D) 1。k(P, D)为计算条件属性子集P与决策属性D之间的相关程度提供了非常有力的手段。利用启发式搜索进行属性约简利用启发式搜索进行属性约简有效值：有效值： 一个属性pPC的有效值(significant value)定义为：),(),(),(DpPKDPkDPpSGF)()()(UcardDPOScardDPOScardpPP【说明】：属性p的有效值越大，说明其对条件属性与决策属性之间的影响越大，即其重要性也越大。 利用启发式搜索进行属性约简利用启发式搜索进行属性约简

48、性质1： 若M N C，则POS M （D） POSN （D）性质2： M N C ，X U，则对任意x U，若x POS M （D） ，则x POSN （D）. 利用启发式搜索进行属性约简利用启发式搜索进行属性约简算法步骤算法步骤： 第1步. a A: 计算邻域关系a ; 第2步. 将 赋给red ； 第3步. 对任意aiA-red ， 计算 /此处定义K(D) = 0 第4步. 选择ak ，其满足: SIG(ak,red,D) = maxi(SIG(ai,red,D )） 第5步. 如果SIG(ak,red,D) 0 ,将red U ak 赋给red ， 返回第3步； 否则，返回red，结

49、束。)()(),(DKDKDredaSIGredaredii主要内容主要内容 1.粗糙集发展历程 2.粗糙集的基本理论介绍 3.粗糙集对集合理论的扩展 4.粗糙集对数理逻辑的拓展 5.粗糙集的不确定性度量方法研究 6.粗糙集的属性约简算法研究 7.粗糙集的扩展模型 8.粗糙集的典型应用经典粗糙集存在的问题经典粗糙集存在的问题 经典粗糙集理论的主要存在的问题是： 1)对具有噪声的数据缺乏容忍性； 2)对不完备的数据不能直接处理；UMathematicsPhysicsLiteratureOver classX1goodgoodbadgoodX2goodmediumgoodgoodX3goodmed

50、iumgoodmediumX4mediummediumgoodmediumX5mediumbadbadmediumX6goodmediumgoodmediumX7goodmediumgoodmedium1236745/ , , U Cxx x x xxx1234567/ ,UDx xx xx xx34567,Xx xx x x11223673445 , RxRx x x xRxRxUMathematicsPhysicsLiteratureOver classX1goodgoodbadgoodX2goodmediumgoodgoodX3goodmediumgoodmediumX4mediumme

51、diumgoodmediumX5mediumbadbadmediumX6goodmediumgoodmediumX7goodmediumgoodmedium45(),apr Xx x34567,Xx xx x x22367,Rxx xx2367BND(),Xx x x x边界域太大，对错误敏感边界域太大，对错误敏感可变精度粗糙集模型可变精度粗糙集模型 W.Ziarko提出了一种称之为可变精度粗糙集模型，该模型给出了错误率低于预先给定值的分类策略，定义了该精度下的正区域、边界区域和负区域。下面扼要地介绍其思想： 一般地，集合X包含于Y并未反映出集合X的元素属于集合Y的“多少”。为此，VPRS定义

52、了它的量度： C(X, Y)=1card(XY)/card(X) 当card(x)0， C(X, Y)=0 当card(x)=0。 C(X, Y)表示把集合X归类于集合Y的误分类度，即有C(X, Y)100%的元素归类错误。显然，C(X, Y)=0时有XY。如此，可事先给定一错误分类率(00.5)，基于上述定义，我们有XY，当且仅当C(X,Y)。可变精度粗糙集模型可变精度粗糙集模型在此基础上，设U为论域且R为U上的等价关系，U/R=A=X1, X2, , Ak ，这样，可定义集合X的-下近似下近似为 RX =Xi (C(Xi, X), i=1, 2, , k)， 并且RX称为集合X的-正区域正

53、区域，集合X的-上近似上近似为 RX =Xi (C(Xi, X)1, i=1, 2, , k)，这样，-边界区域边界区域就定义为： BNRX =Xi (C(Xi, X) 2hours ) （道路边）（道路边）$2.00$12.00 （停车场）（停车场）$7.00$7.001a2a12(|)ija损失函数贝叶斯决策论贝叶斯决策论例：开会停车问题例：开会停车问题1(| )0.8Px21(| )1(| )0.2PxPxActionsStates ( 2hours ) ( 2hours ) （道路边）（道路边）$2.00$12.00 （停车场）（停车场）$7.00$7.001a2a12(|)ija损失

54、函数111(| )(|)(| )xxsjjjR aaP111122(|) (| )(|) (| )xxaPaP$2.00*0.80$12.00*0.20$3.002(| )$7.00*0.80$7.00*0.20$7.00 xR a因为$3.00 2hours ) （道路边）（道路边）$2.00$12.00 （停车场）（停车场）$7.00$7.001a2a12(|)ija损失函数112(| )$2.00(| )$12.00(| )xR aPxPx如果一个人想知道将车停在哪里更合理，怎么办？将车停在道路边的风险11$2.00(| )$12.00(1(| )PxPx$7.001(| )0.5xP选

55、择将车停在道路边更经济合理决策粗糙集决策粗糙集,XX 状态(state)集：,PBNaaa 行动(action)集：PaBaNa()xPOS X()xBND X()xNEG X表示表示表示接受决策延迟决策拒绝决策新的语义解释新的语义解释决策粗糙集决策粗糙集(| )PXx(| )P Xx(| )(| )(| )PPPPNR axP XxPXx接受决策的代价:(| )(| )(| )BBPBNR axP XxPXx延迟决策的代价:(| )(| )(| )NNPNNR axP XxPXx拒绝决策的代价: x是否属于X? 如何决策风险最小化理论风险最小化理论 , ,argmin(| )jjP B NR

56、 ax决策粗糙集决策粗糙集(| )(| )PBRxRx(| )(| )PNRxRxxPOS X(| )(| )BPRxRx(| )(| )BNRxRxxBND X(| )(| )NPRxRx(| )(| )NBRxRxxNEG X根据最小风险决策规则根据最小风险决策规则(P)：如果且则则则(B)：如果(N)：如果且且P|xP|x1XXPPBPNPNNBNPN考虑概率条件考虑损失函数条件将一个属于X的对象x划分到正域POS(X)的损耗小于或者等于将其划分到边界域BND(X)的损耗；而且，上述两种损耗应该小于将这个对象划分到负域NEG(X)的损耗。决策粗糙集决策粗糙集(| )(| )PBRxRx根

57、据最小风险决策规则根据最小风险决策规则, 确定阈值确定阈值 和和 关于规则(P)：P(| )P(| )P(| )P(| )PPPNBPBNXxXxXxXxP(| )(1P(| )P(| )(1P(| )PPPNBPBNXxXxXxXx()P(| )()()PNBNPNBNBPPPXx(| )(| )PNRxRxN)(P(| )(NPNNNPPPNNPXx决策粗糙集决策粗糙集(| )(| )BPRxRx根据最小风险决策规则根据最小风险决策规则, 确定阈值确定阈值 和和 关于规则(B)(P(| )(BNPNBNPPPNBPXx(| )(| )BNRxRxN)(P(| )(NPNNNPPPNNPXx

58、(| )(| )NPRxRx关于规则(N)(P(| )(NNPNNNPPPNNPXx(| )(| )NPRxRxN)(P(| )(NBNNNBPBNNPXx决策粗糙集决策粗糙集根据最小风险决策规则根据最小风险决策规则, 确定阈值确定阈值 和和 )()(BNPNBNPPPNBPN)()(NPNNNPPPNNPN)()(NBNNNBPBNNP(| )P Xx(| )P XxxPOS X(P)：如果且则(| )P Xx(| )P XxxNEG X(N)：如果且则(| )P Xx(| )P XxxBND X(B)：如果且则决策粗糙集决策粗糙集根据最小风险决策规则根据最小风险决策规则, 确定阈值确定阈值

59、 和和 (| )P XxxPOS X(P)：如果则(| )P XxxBND X(B)：如果则(| )P Xx(N)：如果xNEG X则概率正域：概率边界域：概率负域：( , )() |,P(| )POSXx xUXx ( ,)() |,P(| )BNDXx xUXx (,)() |,P(| )NEGXx xUXx 非等价关系模型非等价关系模型 在数据中存在缺失的属性值的时候（在数据库中很普遍），等价关系无法处理这种情形。为扩展粗糙集的能力，有许多作者提出了用非等价关系来代替等价关系作为粗糙集的基础。 基于容差关系的粗糙集基于容差关系的粗糙集基于非对称相似关系的粗糙集基于非对称相似关系的粗糙集基

60、于限制容差关系的粗糙集基于限制容差关系的粗糙集主要内容主要内容 1.粗糙集发展历程 2.粗糙集的基本理论介绍 3.粗糙集对集合理论的扩展 4.粗糙集对数理逻辑的拓展 5.粗糙集的不确定性度量方法研究 6.粗糙集的属性约简算法研究 7.粗糙集的扩展模型 8.粗糙集的典型应用2021-9-21计算机科学与技术研究所124CHONGQING UNIVERSITY OF POSTS AND TELECOMMUNICATIONS (一）故障诊断一）故障诊断2021-9-211252021-9-21计算机科学与技术研究所125CHONGQING UNIVERSITY OF POSTS AND TELECOMMUN