粗糙集理论及其应用ppt课件.ppt

《粗糙集理论及其应用ppt课件.ppt》由会员分享，可在线阅读，更多相关《粗糙集理论及其应用ppt课件.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、刘坤寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集理论及其应用2023/3/181寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多主要内容 粗糙集发展历程 粗糙集的基本理论介绍粗糙集对集合理论的扩展 粗糙集的属性约简算法研究2023/3/182寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集发展历程l1970s，Pawlak和波兰科学院、华沙大学的一些逻辑学家，在研究信息系统逻辑

2、特性的基础上，提出了粗糙集理论的思想。l在最初的几年里，由于大多数研究论文是用波兰文发表的，所以未引起国际计算机界的重视，研究地域仅限于东欧各国。l1982年，Pawlak发表经典论文Rough sets，标志着该理论正式诞生。l1991年，Pawlak的第一本关于粗糙集理论的专著Rough sets:theoretical aspects of reasoning about data；2023/3/183寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集发展历程l1992年，Slowinski主编的Intelligen

3、ce decision support:handbook of applications and advances of rough sets theory的出版，奠定了粗糙集理论的基础，有力地推动了国际粗糙集理论与应用的深入研究。l1992年，在波兰召开了第一届国际粗糙集理论研讨会，有15篇论文发表在1993年第18卷的 Foundation of computingand decision sciences上。l1995年，Pawlak等人在ACM Communications上发表“Rough sets”，极大地扩大了该理论的国际影响。2023/3/184寒假来临，不少的高中毕业生和大学

4、在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集发展历程 19961999年，分别在日本、美国、美国、日本召开了第4-7届粗糙集理论国际研讨会。20012002，中国分别在重庆、苏州召开第一、二届粗糙集与软计算学术会议。2001年至今，每年召开CRSSC。2003年，在重庆召开粗糙集与软计算国际研讨会。2004年，在瑞典召开RSCTC国际会议（偶数年会）。2005年，在加拿大召开RSFDGrC国际会议（奇数年会）。2006年至今，每年召开RSKT。2023/3/185寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是

5、，目前社会上寒假招工的陷阱很多主要内容 粗糙集发展历程 粗糙集的基本理论介绍 粗糙集的属性约简算法研究2023/3/186寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集的基本理论介绍粗糙集的基本理论介绍 1980年，德国数学家克莱因在年，德国数学家克莱因在数学：确定性的数学：确定性的丧失丧失中指出：数学也存在不确定性问题。中指出：数学也存在不确定性问题。确定问题的研究经典的数学工具，如集合论不确定问题的研究拓展的数学工具，如概率论、模糊集、粗糙集等2023/3/187寒假来临，不少的高中毕业生和大学在校生都选择去打工。

6、准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集的基本理论介绍粗糙集的基本理论介绍不确定性随机性模糊性不完整性不稳定性不一致性主要的特性2023/3/188寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集的基本理论介绍粗糙集的基本理论介绍随随机机性性：由于条件不能决定结果而表现出来的不确定性，反映了因果律的问题。解决随机性问题的典型数学方法是概率论。模模糊糊性性：由于概念外延边界的不清晰而表现出的不确定性，反映了排中律的问题。解决模糊性的典型数学方法是模糊集理论。2023/3/189寒假来临，不少的

7、高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集的基本理论介绍粗糙集的基本理论介绍自然界中大部分事物所呈现的信息都是：不完整的、不精确的、模糊的、含糊不清的经典集合论和逻辑方法无法准确的描述和解决这些问题。粗糙集理论的提出，主要是为了描述并处理“含糊”信息2023/3/1810寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集的基本理论介绍粗糙集的基本理论介绍（1）经典集合特点：集合的边界没有宽度每个元素要么属于S，要么不属于，具有确定性。2023/3/1811寒假

8、来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集的基本理论介绍粗糙集的基本理论介绍（2）“含糊”问题的提出1904年，谓词逻辑创始人G.Frege首次提出将含糊性归结到“边界线区域”在论域上存在一些个体，既不能被分到某一子集上，也不能被分到该子集的补集上。2023/3/1812寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集的基本理论介绍粗糙集的基本理论介绍（3）模糊集合的提出1965年，美国Zadeh教授首次提出个体x与集合S的关系x以一定的程度属于

9、S。2023/3/1813寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集的基本理论介绍粗糙集的基本理论介绍模糊集虽然解决了边界域元素的“亦此亦彼”的现象，但：未给出计算含糊元素数目的数学公式未给出描述含糊元素隶属度的形式化方法隶属度函数本身不确定2023/3/1814寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集的基本理论介绍粗糙集的基本理论介绍粗糙集运用集合论中的“等价关系（不可区分关系）”，将边界线区域定义为“上相似集”与“下相似集”的差集

10、在“真”、“假”二值之间的“含糊度”可计算给出了含糊元素数目的计算公式2023/3/1815寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集的基本理论介绍粗糙集的基本理论介绍边界线的不确定性模糊集用隶属度（非精确方法）来描述粗糙集用精确的边界线（上、下近似集）来描述相互补充2023/3/1816寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集的基本理论介绍粗糙集的基本理论介绍 主要优点主要优点n除数据集之外，无需任何先验知识（或信息）n对不确定性的

11、描述与处理相对客观n用于分类，发现不准确数据或噪声数据内的结构联系n【说明】：Bayes理论（先验分布）、证据理论（隶属度函数）等都需要先验知识，具有很大的主观性。2023/3/1817寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集理论在知识发现中的作用粗糙集理论在知识发现中的作用在数据预处理过程中，粗糙集理论可以用于对特征更对特征更准确的提取准确的提取在数据准备过程中，利用粗糙集理论的数据约简特性，对数据集进行降维操作。对数据集进行降维操作。在数据挖掘阶段，可将粗糙集理论用于分类规则的发用于分类规则的发现。现。在解释

12、与评估过程中，粗糙集理论可用于对所得到的对所得到的结果进行统计评估结果进行统计评估。2023/3/1818寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集理论的基本概念粗糙集理论的基本概念“知识知识”的定义n使用等价关系集R对离散表示的空间U进行划分，知识就是R对U划分的结果。“知识库知识库”的形式化定义n等价关系集R中所有可能的关系对U的划分n表示为：K=(U,R)2023/3/1819寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集理论的基本概

13、念粗糙集理论的基本概念“信息系统信息系统”的形式化定义的形式化定义nS=U,A,V,f，nU：对象的有限集nA：属性的有限集，A=CD，C是条件属性子集，D是决策属性子集nV：，Vp是属性P的域nf：U A V是总函数，使得对每个xi U,q A,有f(xi,q)Vq一个关系数据库可看作一个信息系统，其一个关系数据库可看作一个信息系统，其“列列”为为“属性属性”，“行行”为为“对象对象”。2023/3/1820寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多粗糙集理论的基本概念粗糙集理论的基本概念 设PA，xi,xj U,定义

14、二元关系INDP称为等价关系等价关系：称xi,xj在S中关于属性集P是等价的，当且仅当p(xi)=p(xj)对所有的pP 成立，即xi,xj不能用P 中的属性加以区别。2023/3/1821寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多等价关系示例：factweatherroadtimeaccident1mistyicydayyes2foggyicynightyes3mistynot icynightyes4sunnyicydayno5foggynot icyduskyes6mistynot icynightno2023/3

15、/1822寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多等价关系示例：可知，U=1,2,3,4,5,6R=2 weather,road,time,accident 若P=weather,road，则xIND(P)=xINDweatherxINProad =1,3,6,2,5,4 1,2,4,3,5,6 =1,2,4,3,6,5 2023/3/1823寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多集合的上近似集合的上近似&下近似下近似 在信息系统S=U,A,

16、V,f中，设XU是个体全域上的子集，PA，则X的下和上近似集及边界区域分别为：X是XU上必然被分类的那些元素的集合，即包含在X内的最大可定义集；X是U上可能被分类的那些元素的集合，即包含X的最小可定义集。，则X是可定义的，否则是不可定义的，即粗糙的若2023/3/1824寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多集合的上近似集合的上近似&下近似下近似上、下近似集将论域上、下近似集将论域U U划分成三个区域：正域、边界域和负域，其定义如划分成三个区域：正域、边界域和负域，其定义如下：下：BndP(X)是既不能在XU上被分类

17、，又不能在U-X上被分类的那些元素的集合。2023/3/1825寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多集合的上、下近似概念示意图X2023/3/1826寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多上、下近似关系举例上、下近似关系举例：X1=u|Flu(u)=yes=u2,u3,u6,u7RX1=u2,u3=u2,u3,u6,u7,u5,u8X2=u|Flu(u)=no=u1,u4,u5,u8RX2=u1,u4 =u1,u4,u5,u8,u6,u7

18、由R=Headache,Temp.划分出来的等价类有:u1,u2,u3,u4,u5,u7,u6,u8.2023/3/1827寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多近似精度近似精度&分类质量分类质量设S=U,A,V,f为一信息系统，且XU，PA，则S上X的近似精度近似精度为：注：card(X)表示集合X中元素个数设S为一信息系统，PA，且令=X1,X2,Xn是U的一个分类（子集族），其中XiU，则的P-下近似和 P-上近似分别表示为：2023/3/1828寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充

19、实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多近似精度近似精度&分类质量分类质量由属性子集PA确定的分类的分类质量分类质量为：分类质量分类质量表示通过属性子集P正确分类的对象数与信息系统中所有对象数的比值。这是评价属性子集P的重要性的关键指标之一。2023/3/1829寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多属性约简属性约简&“核核”属性约简属性约简(Attribute Reduction)：在一个信息系统S中，设是S上的一个分类，经约简后的最小属性子集具有同原始属性集相同的分类质量，即存在RPQ，使得R()=P

20、()，称之为属性集属性集P P的的-约简约简，记作REDU(P)。所有-约简的交集称为-核核，即CORE(P)=REDU(P)，核是信息系统中一系列最重要的属性之一。【说明说明】：在大多数情况下，分类是由几个甚至一个属性来决定的，而不是由关系数据库中的所有属性的微小差异来决定。属性约简及核的概念为提取系统中重要属性及其值提供了有力的属性约简及核的概念为提取系统中重要属性及其值提供了有力的数学工具数学工具，而且这种约简是本着不破坏原始数据集的分类质量的，通俗地说，它是完全“保真”的。2023/3/1830寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前

21、社会上寒假招工的陷阱很多主要内容 粗糙集发展历程 粗糙集的基本理论介绍 粗糙集的属性约简算法研究2023/3/1831寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多利用启发式搜索进行属性约简几个概念：正区域：正区域：在信息系统S=(U,CD,V,f)中，设D*=X1,X2,Xm，属性子集PC关于决策属性D的“正区域”定义为：P关于D的正区域表示那些根据属性子集P就能分入正确类别的所有对象。2023/3/1832寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多

22、利用启发式搜索进行属性约简相关程度：相关程度：条件属性子集PC与决策属性D的相关程度（也称依依赖程度赖程度）定义为：显然，0k(P,D)1。k(P,D)为计算条件属性子集P与决策属性D之间的相关程度提供了非常有力的手段。2023/3/1833寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多利用启发式搜索进行属性约简有效值：有效值：一个属性pPC的有效值(significant value)定义为：【说明】：属性p的有效值越大，说明其对条件属性与决策属性之间的影响越大，即其重要性也越大。2023/3/1834寒假来临，不少的高中

23、毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多利用启发式搜索进行属性约简算法步骤算法步骤：第1步.a A:计算邻域关系a;第2步.将 赋给red；第3步.对任意aiA-red，计算 /此处定义K(D)=0 第4步.如果SIG(ak,red,D)0,将red U ak 赋给red，返回第3步；否则，返回red，结束。观看演示观看演示2023/3/1835寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多利用启发式搜索进行属性约简2023/3/1836寒假来临，不少的高中毕业生和大学

24、在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多利用启发式搜索进行属性约简第1步.a A:计算邻域关系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(体温分类）2023/3

25、/1837寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多利用启发式搜索进行属性约简 第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,a7Po

26、s_c(D)=a1Ua2Ua3Ua4/C的正域2023/3/1838寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多利用启发式搜索进行属性约简 第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

27、/C-C1的依赖程度SGF(c1,C,D)=K（C,D）-K（C-C1,D）=1/8/C1的有效值2023/3/1839寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多利用启发式搜索进行属性约简第4步.如果SIG(ak,red,D)0,将red U ak 赋给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

28、_(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不能进入集合red2023/3/1840寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多利用启发式搜索进行属性约简第4步.如果SIG(ak,red,D)0,将red U ak 赋给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)D=!=Pos_c(D)K（C-C3,D）=Pos_c-c3(D)/U=0/C-C3的依赖程度SGF(c2,C,D)=K（C,D）-K（C-C2,D）=4/80/C3的有效值C3赋给集合red=c1，c3根据约简结果，C2属性可以去除。属性约简后为c1(头痛)，c3（体温）对流感有影响，并且属性C3的有效值更大，说明其对条件属性与决策属性之间的影响更大，即其重要性也更大。2023/3/1841寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多谢谢！欢迎大家提问2023/3/1842