粗糙集理论及其应用

粗糙集理论及其最新进展胡军博士计算智能重庆市重点实验室主要内容•1.粗糙集发展历程•2.粗糙集的基本理论介绍•3.粗糙集对集合理论的扩展•4.粗糙集对数理逻辑的拓展•5.粗糙集的不确定性度量方法研究•6.粗糙集的属性约简算法研究•7.粗糙集的扩展模型•8.粗糙集的典型应用粗糙集发展历程•1970s，Pawlak和波兰科学院、华沙大学的一些逻辑学家，在研究信息系统逻辑特性的基础上，提出了粗糙集理论的思想。•在最初的几年里，由于大多数研究论文是用波兰文发表的，所以未引起国际计算机界的重视，研究地域仅限于东欧各国。•1982年，Pawlak发表经典论文《Roughsets》，标志着该理论正式诞生。•1991年，Pawlak的第一本关于粗糙集理论的专著《Roughsets:theoreticalaspectsofreasoningaboutdata》；Pawlak教授（1926年-2006年）粗糙集发展历程•1992年，Slowinski主编的《Intelligencedecisionsupport:handbookofapplicationsandadvancesofroughsetstheory》的出版，奠定了粗糙集理论的基础，有力地推动了国际粗糙集理论与应用的深入研究。•1992年，在波兰召开了第一届国际粗糙集理论研讨会，有15篇论文发表在1993年第18卷的《Foundationofcomputinganddecisionsciences》上。•1995年，Pawlak等人在《ACMCommunications》上发表“Roughsets”，极大地扩大了该理论的国际影响。粗糙集发展历程•1993和1994年，分别在加拿大、美国召开第二、三届国际粗糙集与知识发现（或软计算）研讨会。•1996～1999年，分别在日本、美国、美国、日本召开了第4-7届粗糙集理论国际研讨会。•1998年至今，偶数年召开RSCTC,奇数年召开RSFDGrC。•2001年至今，每年召开CRSSC。•2006年至今，每年召开RSKT。•……CRSSC2001,ChongqingCRSSC2002,SuzhouCRSSC2003,RSFDGrC2003,ChongqingCRSSC2004,ZhoushanCRSSC2006,JinhuaCRSSC2005,AnshanRSKT2006,ChongqingCRSSC2007,TaiyuanCRSSC2008,XinxiangRSKT2008,ChengduIFKT2008,ChongqingIFTGrCRSP2006,NanchangCRSSC2009,ShijiazhuangRSKT2010,BeijingCRSSC2010,ChongqingTRS2010,Zhoushan主要内容•1.粗糙集发展历程•2.粗糙集的基本理论介绍•3.粗糙集对集合理论的扩展•4.粗糙集对数理逻辑的拓展•5.粗糙集的不确定性度量方法研究•6.粗糙集的属性约简算法研究•7.粗糙集的扩展模型•8.粗糙集的典型应用粗糙集的基本理论介绍德国数学家克莱因指出：“数学曾经被认为是精确论证的顶峰，真理的化身，是关于宇宙设计的真理”是一个错误观点，指出数学也存在不确定性问题。确定问题的研究不确定问题的研究1980年，《数学：确定性的丧失》经典的数学工具，如集合论拓展的数学工具，如概率论、模糊集、粗糙集、云理论等转移逐渐成为人工智能研究中的热点问题粗糙集的基本理论介绍不确定性随机性模糊性不完整不稳定不一致主要的特性...粗糙集的基本理论介绍随机性：是由于条件不能决定结果而表现出来的不确定性，反映了因果律的问题。解决随机性问题的典型数学方法是概率论。模糊性：是由于概念外延边界的不清晰而表现出来的不确定性，反映了排中律的问题。解决模糊性的典型数学方法是模糊集理论。粗糙集的基本理论介绍自然界中大部分事物所呈现的信息都是：◆不完整的、不精确的、模糊的和含糊的◆经典集合论和逻辑方法无法准确、圆满地描述和解决这些问题。粗糙集理论的提出主要是为了描述并处理“含糊”信息。粗糙集的基本理论介绍（1）经典集合：个体x与集合S的关系是——x属于S或者x不属于S。Sx1x2特点：（1）集合的边界没有宽度；（2）每个元素要么属于S，要么不属于S，具有确定性。粗糙集的基本理论介绍（2）“含糊”（Vague）问题的提出1904年谓词逻辑创始人G.Frege(弗雷格)首次提出将含糊性归结到“边界线区域”(Boundaryregion)：在论域上存在一些个体，它既不能被分类到某一个子集上，也不能被分类到该子集的补集上。G.Frege,CorrespondencewithRussell,inN.SalmonandS.Soames(eds.),PropositionsandAttitudes,1904.粗糙集的基本理论介绍（3）模糊集合的提出：个体x与集合S的关系是——x以一定的程度属于S。哪些属于“高个子”这个集合？1965年美国的Zadeh教授首次提出粗糙集的基本理论介绍–Eg.Mr.Smithis180CM.–Heisverytall(withamembershipof0.8).–Heistall(withamembershipof0.9).–x1x2Stall001180verytall001200stature(CM)stature(CM)粗糙集的基本理论介绍•模糊集虽然解决了边界域元素的“亦此亦彼”的现象，但没有很好解决G.Frege提出的“含糊”问题，如：未给出计算含糊元素数目的数学公式；未给出描述含糊元素隶属度的形式化方法；隶属度函数本身是不确定的；……粗糙集的基本理论介绍180CMisverytallwithamembership0.8.Whynot0.81or0.79?Whatisthedifferencebetween0.79,0.80,and0.81?Howcanwemakethedecision?Whytriangleortrapezoid?粗糙集的基本理论介绍粗糙集运用集合论中的“等价关系（不可区分关系）”，将边界线区域定义为“上近似集”与“下近似集”的差集；在“真”、“假”二值之间的“含糊度”可计算；给出了含糊元素数目的计算公式；……粗糙集的基本理论介绍中国版图的边界例如粗糙集的基本理论介绍中国版图的上、下近似粗糙集的基本理论介绍中国版图边界域随知识粒度的细化而减小粗糙集的基本理论介绍边界线的不确定性模糊集用隶属度来描述粗糙集用精确的边界线（上、下近似集）来描述用非精确的方法处理不确定问题通过客观数据计算用精确的方法处理不确定问题处理不确定性问题方面具有很强的互补性粗糙集的基本理论介绍•主要优点–除数据集之外，无需任何先验知识（或信息）–对不确定性的描述与处理相对客观–……【说明】：Bayes理论（先验分布）、模糊集理论（隶属度函数）等都需要先验知识，具有很大的主观性。粗糙集理论的基本概念•“知识”的定义–使用等价关系集R对离散表示的空间U进行划分，知识就是R对U划分的结果，记为U|R。•“知识库”的形式化定义–等价关系集R中所有可能的关系对U的划分–表示为：K=(U,R)粗糙集理论的基本概念•“信息系统”的形式化定义–S={U,A,V,f}，–U：对象的有限集–A：属性的有限集，A=CD，C是条件属性子集，D是决策属性子集–V：，Vp是属性P的域–f：U×A→V是总函数，使得对每个xiU,qA,有f(xi,q)Vq•一个关系数据库可看作一个信息系统，其“列”为“属性”，“行”为“对象”。PApVV粗糙集理论的基本概念•设PA，xi,xjU,定义二元关系INDP称为等价关系：称xi,xj在S中关于属性集P是等价的，当且仅当p(xi)=p(xj)对所有的pP成立，即xi,xj不能用P中的属性加以区别。一般，等价关系INDP也可简记为P。)}()(,|),{()(jijixpxpPpUUxxPIND等价关系示例：objectweatherroadtimeaccident1mistyicydayyes2foggyicynightyes3mistynoticynightyes4sunnyicydayno5foggynoticyduskyes6mistynoticynightno等价关系示例：•可知，•U={1,2,3,4,5,6}•R=2{weather,road,time,accident}•若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}中，设XU是论域上的子集，PA，则X的下和上近似集及边界区域分别为：•若，成X是可定义的，否则是不可定义的，或者称为粗糙的。•X是包含于X的最大可定义集；•X是包含X的最小可定义集。{/|}PXYUPYX{/|}PXYUPYXPXPXPP正域、边界域和负域•上、下近似将论域U划分成三个区域：正域、边界域和负域。其定义如下：•其中，BNDP(X)是既不能在XU上被分类，又不能在U-X上被分类的那些元素的集合。()()()pPpPOSXPXBNDXPXPXNEGXUPX上、下近似关系举例：X1={u|Flu(u)=yes}={u2,u3,u6,u7}RX1={u2,u3}={u2,u3,u6,u7,u5,u8}X2={u|Flu(u)=no}={u1,u4,u5,u8}RX2={u1,u4}={u1,u4,u5,u8,u6,u7}X2RUHeadacheTemp.FluU1YesNormalNoU2YesHighYesU3YesVery-highYesU4NoNormalNoU5NNNoooHHHiiiggghhhNNNoooU6NoVery-highYesU7NNNoooHHHiiiggghhhYYYeeesssU8NoVery-highNo由R={Headache,Temp.}划分出来的等价类有:{u1},{u2},{u3},{u4},{u5,u7},{u6,u8}.X1R主要内容•1.粗糙集发展历程•2.粗糙集的基本理论介绍•3.粗糙集对集合理论的扩展•4.粗糙集对数理逻辑的拓展•5.粗糙集的不确定性度量方法研究•6.粗糙集的属性约简算法研究•7.粗糙集的扩展模型•8.粗糙集的典型应用•3.TheextensionofsettheoryTheclassicalsettheorywasfoundedbyCantor,anditisthebasisofmathematicsandlogic.However,theclassicalsettheorycannotbeusedtoaddresstheproblemswithuncertainty.So,itisnecessarytoextendsettheory.TheoperationofCantorsets{|}ABxxAxBABU{|}AxxAxUUATheoperationofCantorsets{|}ABxxAxBABU{|}ABxxAxBABUZadehusedfuzzymembershipfunctiontocharacterizethebelongingofanelementtoasetwithuncertainty,andcalleditfuzzysets.00.20.40.60.811.200.30.60.91.21.51.82.12.42.733.33.63.94.24.54.8xu(x)Fuzzysets00.20.40.60.811.200.30.60.91.21.51.82.12.42.733.33.63.94.24.54.8xu(x)ThecomplementofafuzzysetLetAb