粗糙集理论及其应用

2020/5/27,1,粗糙集理论及其应用,2020/5/27,2,主要内容,粗糙集发展历程粗糙集的基本理论介绍粗糙集对集合理论的扩展粗糙集的属性约简算法研究,2020/5/27,3,粗糙集发展历程,1970s，Pawlak和波兰科学院、华沙大学的一些逻辑学家，在研究信息系统逻辑特性的基础上，提出了粗糙集理论的思想。在最初的几年里，由于大多数研究论文是用波兰文发表的，所以未引起国际计算机界的重视，研究地域仅限于东欧各国。1982年，Pawlak发表经典论文Roughsets，标志着该理论正式诞生。1991年，Pawlak的第一本关于粗糙集理论的专著Roughsets:theoreticalaspectsofreasoningaboutdata；,2020/5/27,4,粗糙集发展历程,1992年，Slowinski主编的Intelligencedecisionsupport:handbookofapplicationsandadvancesofroughsetstheory的出版，奠定了粗糙集理论的基础，有力地推动了国际粗糙集理论与应用的深入研究。1992年，在波兰召开了第一届国际粗糙集理论研讨会，有15篇论文发表在1993年第18卷的Foundationofcomputinganddecisionsciences上。1995年，Pawlak等人在ACMCommunications上发表“Roughsets”，极大地扩大了该理论的国际影响。,2020/5/27,5,粗糙集发展历程,19961999年，分别在日本、美国、美国、日本召开了第4-7届粗糙集理论国际研讨会。20012002，中国分别在重庆、苏州召开第一、二届粗糙集与软计算学术会议。2001年至今，每年召开CRSSC。2003年，在重庆召开粗糙集与软计算国际研讨会。2004年，在瑞典召开RSCTC国际会议（偶数年会）。2005年，在加拿大召开RSFDGrC国际会议（奇数年会）。2006年至今，每年召开RSKT。,2020/5/27,6,主要内容,粗糙集发展历程粗糙集的基本理论介绍粗糙集的属性约简算法研究,2020/5/27,7,粗糙集的基本理论介绍,1980年，德国数学家克莱因在数学：确定性的丧失中指出：数学也存在不确定性问题。确定问题的研究,经典的数学工具，如集合论,不确定问题的研究,拓展的数学工具，如概率论、模糊集、粗糙集等,2020/5/27,8,粗糙集的基本理论介绍,不确定性,随机性模糊性不完整性不稳定性不一致性,主要的特性,2020/5/27,9,粗糙集的基本理论介绍,随机性：由于条件不能决定结果而表现出来的不确定性，反映了因果律的问题。解决随机性问题的典型数学方法是概率论。模糊性：由于概念外延边界的不清晰而表现出的不确定性，反映了排中律的问题。解决模糊性的典型数学方法是模糊集理论。,2020/5/27,10,粗糙集的基本理论介绍,自然界中大部分事物所呈现的信息都是：不完整的、不精确的、模糊的、含糊不清的经典集合论和逻辑方法无法准确的描述和解决这些问题。粗糙集理论的提出，主要是为了描述并处理“含糊”信息,2020/5/27,11,粗糙集的基本理论介绍,（1）经典集合特点：集合的边界没有宽度每个元素要么属于S，要么不属于，具有确定性。,2020/5/27,12,粗糙集的基本理论介绍,（2）“含糊”问题的提出1904年，谓词逻辑创始人G.Frege首次提出将含糊性归结到“边界线区域”在论域上存在一些个体，既不能被分到某一子集上，也不能被分到该子集的补集上。,2020/5/27,13,粗糙集的基本理论介绍,（3）模糊集合的提出1965年，美国Zadeh教授首次提出个体x与集合S的关系x以一定的程度属于S。,2020/5/27,14,粗糙集的基本理论介绍,模糊集虽然解决了边界域元素的“亦此亦彼”的现象，但：未给出计算含糊元素数目的数学公式未给出描述含糊元素隶属度的形式化方法隶属度函数本身不确定,2020/5/27,15,粗糙集的基本理论介绍,粗糙集运用集合论中的“等价关系（不可区分关系）”，将边界线区域定义为“上相似集”与“下相似集”的差集在“真”、“假”二值之间的“含糊度”可计算给出了含糊元素数目的计算公式,2020/5/27,16,粗糙集的基本理论介绍,边界线的不确定性,模糊集用隶属度（非精确方法）来描述,粗糙集用精确的边界线（上、下近似集）来描述,相互补充,2020/5/27,17,粗糙集的基本理论介绍,主要优点除数据集之外，无需任何先验知识（或信息）对不确定性的描述与处理相对客观用于分类，发现不准确数据或噪声数据内的结构联系【说明】：Bayes理论（先验分布）、证据理论（隶属度函数）等都需要先验知识，具有很大的主观性。,2020/5/27,18,粗糙集理论在知识发现中的作用,在数据预处理过程中，粗糙集理论可以用于对特征更准确的提取在数据准备过程中，利用粗糙集理论的数据约简特性，对数据集进行降维操作。在数据挖掘阶段，可将粗糙集理论用于分类规则的发现。在解释与评估过程中，粗糙集理论可用于对所得到的结果进行统计评估。,2020/5/27,19,粗糙集理论的基本概念,“知识”的定义使用等价关系集R对离散表示的空间U进行划分，知识就是R对U划分的结果。“知识库”的形式化定义等价关系集R中所有可能的关系对U的划分表示为：K=(U,R),2020/5/27,20,粗糙集理论的基本概念,“信息系统”的形式化定义S=U,A,V,f，U：对象的有限集A：属性的有限集，A=CD，C是条件属性子集，D是决策属性子集V：，Vp是属性P的域f：UAV是总函数，使得对每个xiU,qA,有f(xi,q)Vq一个关系数据库可看作一个信息系统，其“列”为“属性”，“行”为“对象”。,2020/5/27,21,粗糙集理论的基本概念,设PA，xi,xjU,定义二元关系INDP称为等价关系：称xi,xj在S中关于属性集P是等价的，当且仅当p(xi)=p(xj)对所有的pP成立，即xi,xj不能用P中的属性加以区别。,2020/5/27,22,等价关系示例：,2020/5/27,23,等价关系示例：,可知，U=1,2,3,4,5,6R=2weather,road,time,accident若P=weather,road，则xIND(P)=xINDweatherxINProad=1,3,6,2,5,41,2,4,3,5,6=1,2,4,3,6,5,2020/5/27,24,集合的上近似第2步.将赋给red；第3步.对任意aiA-red，计算/此处定义K(D)=0第4步.如果SIG(ak,red,D)0,将redUak赋给red，返回第3步；否则，返回red，结束。观看演示,2020/5/27,36,利用启发式搜索进行属性约简,2020/5/27,37,利用启发式搜索进行属性约简,第1步.aA:计算邻域关系a;在决策表中设置A=a1,a2,a3,a4,a5,a6,a7,a8,其中C=头痛，胸口痛，体温,D=流感那么，就可以设置C1=头痛，C2=胸口痛，C3=体温，所以A/C1=a1,a2,a3,a4,a5,a6,a7,a8(头痛分类）A/C2=a1,a2,a3,a4,a6,a8,a5,a7（胸口痛分类）A/C3=a1,a4,a2,a5,a7,a3,a6,a8(体温分类）,2020/5/27,38,利用启发式搜索进行属性约简,第2步.将赋给red；第3步.对任意aiA-red，计算/此处定义K(D)=0(A-C3):A/C1,C2=a1,a2,a3,a4,a6,a8,a5,a7(头疼与胸口疼的分类并集)(A-C2):A/C1,C3=a1,a2,a3,a4,a5,a7,a6,a8(A-C1):A/C2,C3=a1,a4,a2,a5,a7,a3,a6,a8A/C=a1,a2,a3,a4,a5,a7,a6,a8A/D=a1,a4,a5,a8,a2,a3,a6,a7Pos_c(D)=a1Ua2Ua3Ua4/C的正域,2020/5/27,39,利用启发式搜索进行属性约简,第2步.将赋给red；第3步.对任意aiA-red，计算/此处定义K(D)=0K（C,D）=Pos_c(D)/U=4/8=0.5/C的依赖程度(A-C1):A/C2,C3=a1,a4,a2,a5,a7,a3,a6,a8A/D=a1,a4,a5,a8,a2,a3,a6,a7Pos_(c-c1)D=a1,a2,a4!=Pos_c(D)K（C-C1,D）=Pos_c-c1(D)/U=3/8/C-C1的依赖程度SGF(c1,C,D)=K（C,D）-K（C-C1,D）=1/8/C1的有效值,2020/5/27,40,利用启发式搜索进行属性约简,第4步.如果SIG(ak,red,D)0,将redUak赋给red，返回第3步；SGF(c1,C,D)=K（C,D）-K（C-C1,D）=1/80/C1的有效值将c1加入到red集合中red=c1(A-C2):A/C1,C3=a1,a2,a3,a4,a5,a7,a6,a8A/D=a1,a4,a5,a8,a2,a3,a6,a7Pos_(c-c2)D=a1,a2,a3,a4=Pos_c(D)K（C-C2,D）=Pos_c-c2(D)/U=4/8/C-C1的依赖程度SGF(c2,C,D)=K（C,D）-K（C-C2,D）=0/C1的有效值C2不能进入集合red,2020/5/27,41,利用启发式搜索进行属性约简,第4步.如果SIG(ak,red,D)0,将redUak赋给red，返回第3步；(A-C3):A/C1,C2=a1,a2,a3,a4,a6,a8,a5,a7A/D=a1,a4,a5,a8,a2,a3,a6,a7Pos_(c-c3)