10粗糙集理论及其应用

刘坤2020/3/41粗糙集理论及其应用2020/3/42主要内容􀁺粗糙集发展历程粗糙集的基本理论介绍􀁺粗糙集的属性约简算法研究􀁺粗糙集的扩展模型在文本分类中的应用现有工具简介2020/3/43粗糙集发展历程1970s，Pawlak和波兰科学院、华沙大学的一些逻辑学家，在研究信息系统逻辑特性的基础上，提出了粗糙集理论的思想。在最初的几年里，由于大多数研究论文是用波兰文发表的，所以未引起国际计算机界的重视，研究地域仅限于东欧各国。1982年，Pawlak发表经典论文《Roughsets》，标志着该理论正式诞生。1991年，Pawlak的第一本关于粗糙集理论的专著《Roughsets:theoreticalaspectsofreasoningaboutdata》；2020/3/44粗糙集发展历程1992年，Slowinski主编的《Intelligencedecisionsupport:handbookofapplicationsandadvancesofroughsetstheory》的出版，奠定了粗糙集理论的基础，有力地推动了国际粗糙集理论与应用的深入研究。1992年，在波兰召开了第一届国际粗糙集理论研讨会，有15篇论文发表在1993年第18卷的《Foundationofcomputinganddecisionsciences》上。1995年，Pawlak等人在《ACMCommunications》上发表“Roughsets”，极大地扩大了该理论的国际影响。2020/3/45粗糙集发展历程1996～1999年，分别在日本、美国、美国、日本召开了第4-7届粗糙集理论国际研讨会。2001～2002，中国分别在重庆、苏州召开第一、二届粗糙集与软计算学术会议。2003年，在重庆召开粗糙集与软计算国际研讨会。2004年，在瑞典召开RSCTC国际会议（年会）。2005年，在加拿大召开RSFDGrC国际会议（年会）。……2020/3/46主要内容􀁺粗糙集发展历程粗糙集的基本理论介绍􀁺粗糙集的属性约简算法研究􀁺粗糙集的扩展模型在文本分类中的应用现有工具简介2020/3/47粗糙集的基本理论介绍主要优点除数据集之外，无需任何先验知识（或信息）对不确定性的描述与处理相对客观……【说明】：Bayes理论（先验分布）、证据理论（隶属度函数）等都需要先验知识，具有很大的主观性。2020/3/48粗糙集理论在知识发现中的作用在数据预处理过程中，粗糙集理论可以用于对特征更准确的提取在数据准备过程中，利用粗糙集理论的数据约简特性，对数据集进行降维操作。在数据挖掘阶段，可将粗糙集理论用于分类规则的发现。在解释与评估过程中，粗糙集理论可用于对所得到的结果进行统计评估。2020/3/49粗糙集理论的基本概念“知识”的定义使用等价关系集R对离散表示的空间U进行划分，知识就是R对U划分的结果。“知识库”的形式化定义等价关系集R中所有可能的关系对U的划分表示为：K=(U,R)2020/3/410粗糙集理论的基本概念“信息系统”的形式化定义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2020/3/411粗糙集理论的基本概念设PA，xi,xjU,定义二元关系INDP称为等价关系：称xi,xj在S中关于属性集P是等价的，当且仅当p(xi)=p(xj)对所有的pP成立，即xi,xj不能用P中的属性加以区别。)}()(,|),{()(jijixpxpPpUUxxPIND2020/3/412等价关系示例：factweatherroadtimeaccident1mistyicydayyes2foggyicynightyes3mistynoticynightyes4sunnyicydayno5foggynoticyduskyes6mistynoticynightno2020/3/413等价关系示例：可知，U={1,2,3,4,5,6}R=2{weather,road,time,accident}若P={weather,road}，则[x]IND(P)=[x]IND{weather}[x]INP{road}={{1,3,6},{2,5},{4}}{{1,2,4},{3,5,6}}={{1},{2},{4},{3,6},{5}}2020/3/414集合的上近似&下近似在信息系统S={U,A,V,f}中，设XU是个体全域上的子集，PA，则X的下和上近似集及边界区域分别为：}:/{XYPUYXP}:/{XYPUYXPXPXPXBndP)(•X是XU上必然被分类的那些元素的集合，即包含在X内的最大可定义集；•X是U上可能被分类的那些元素的集合，即包含X的最小可定义集。•BndP(X)是既不能在XU上被分类，又不能在U-X上被分类的那些元素的集合。PP2020/3/415集合的上、下近似概念示意图XAprAXAprAX2020/3/416上、下近似关系举例：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}.X1R2020/3/417近似精度&分类质量设S={U,A,V,f}为一信息系统，且XU，PA，则S上X的近似精度为：)()()()()(XPcardXPcardXXXPPP注：card(X)表示集合X中元素个数设S为一信息系统，PA，且令={X1,X2,…,Xn}是U的一个分类（子集族），其中XiU，则的P-下近似和P-上近似分别表示为：},,,{21nXPXPXPP},,,{21nXPXPXPP2020/3/418近似精度&分类质量由属性子集PA确定的分类的分类质量为：)()()(1UcardXPcardiniP分类质量表示通过属性子集P正确分类的对象数与信息系统中所有对象数的比值。这是评价属性子集P的重要性的关键指标之一。2020/3/419属性约简&“核”属性约简(AttributeReduction)：在一个信息系统S中，设是S上的一个分类，经约简后的最小属性子集具有同原始属性集相同的分类质量，即存在RPQ，使得R()=P()，称之为属性集P的-约简，记作REDU(P)。所有-约简的交集称为-核，即CORE(P)=REDU(P)，核是信息系统中一系列最重要的属性之一。【说明】：在大多数情况下，分类是由几个甚至一个属性来决定的，而不是由关系数据库中的所有属性的微小差异来决定。属性约简及核的概念为提取系统中重要属性及其值提供了有力的数学工具，而且这种约简是本着不破坏原始数据集的分类质量的，通俗地说，它是完全“保真”的。2020/3/420主要内容􀁺粗糙集发展历程粗糙集的基本理论介绍􀁺粗糙集的属性约简算法研究􀁺粗糙集的扩展模型在文本分类中的应用现有工具简介2020/3/421利用区分矩阵进行属性约简区分矩阵（discernibilitymatrix）：在信息系统T=(U,CD,V,f)中，C为条件属性，D为决策属性，设对象全集U按决策属性D被分成不相交的类族，即{X1,X2,…,Xm}，则S中C的区分矩阵M(C)={mi,j}nxn定义为：,,,{1},,,(,)(,){:(,)(,)},,ijijijijijijxxDmxxDcCfcxfcxcCfcxfcxxxD的同一等价类的不同等价类，对的不同等价类其中，1ijn。2020/3/422利用区分矩阵进行属性约简令M是决策表T的可辨识矩阵，A={a1,a2,...,an},是T中所有条件属性的集合.S是M中所有属性组合的集合，且S中不包含重复项.令S中包含有s个属性组合，每个属性组合表示为Bi，其公式化描述为:Bi∈S,Bj∈S,Bi≠Bj(i,j=1,2,...,s).令Card(Bi)=m，则Bi中每个条件属性表示为bi,k∈Bi(k=1,2,...,m)令C0是M中的核属性集，则有C0A.2020/3/423利用区分矩阵进行属性约简算法步骤：第1步.将核属性列入属性约简后得到的属性集合，即red=C0；第2步.在可辨识矩阵中找出所有不包含核属性的属性组合S，即第3步.将属性组合S与red表示为合取范式的形式，即P=red∧{∨bi,k:(i=1,2,...,s;k=1,2,...,m)}第4步.将P转化为析取范式形式；第5步.根据需要选择满意的属性组合.如需属性数最少，可直接选择合取式中属性数最少的组合；如需规则最简或数据约简量最大，则需先进行属性值约简.观看演示},,2,1,:{siredBBSii2020/3/424利用区分矩阵进行属性约简U/Aabcdeu110210u200121u320210u400222u511210实例：T=（U，A，V，f），A={a,b,c,d}∪{e}2020/3/425uu1u2u3u4u5u1u2ca,b,c,du3u4u5a,c,da,da,c,da,da,b,d利用区分矩阵进行属性约简区分矩阵：2020/3/426利用区分矩阵进行属性约简由上述差别矩阵很容易得到核为：{c}区分函数fM(S)为：c∧(a∨d)，即(a∧c)∨(c∧d)得到两个约简{a,c}和{c,d}2020/3/427利用区分矩阵进行属性约简U\Aaceu1120u2011u3220u4022u5120U\Acdeu1210u2121u3210u4222U5210根据得到的两个约简，可得两个约简后的新决策表：2020/3/428利用启发式搜索进行属性约简几个概念：正区域：在信息系统S=(U,CD,V,f)中，设D*={X1,X2,…,Xm}，属性子集PC关于决策属性D的“正区域”定义为：}:{)(*DXXBDPOSPP关于D的正区域表示那些根据属性子集P就能分入正确类别的所有对象。2020/3/429利用启发式搜索进行属性约简相关程度：条件属性子集PC与决策属性D的相关程度（也称依赖程度）定义为：)())((),(UcardDPOScardDPkP显然，0k(P,D)1。k(P,D)为计算条件属性子集P与决策属性D之间的相关程度提供了非常有力的手段。2020/3/430利用启发式搜索进行属性约简有效值：一个属性pPC的有效值(significantvalue)定义为：)},{(),(),,(DpPKDPkDPpSGF)())(())((}{UcardDPOScardDPOScardpPP【说明】：属性p的有效值越大，说明其对条件属性与决策属性之间的影响越大，即其重要性也越大。2020/3/431利用启发式搜索进行属性约简性质1：若M⊆N⊆C，则POSM（D）⊆POSN（D）性质2：M⊆N⊆C，X⊆U，则对任意x∈U，若x∈POSM（D），则x∈POSN（D）.2020/3/432利用启发式搜索进行属性约简算法步骤：第1步.∀a∈A:计算邻域关系Νa;第2步.将∅赋给r