粗糙集理论学习心得与基于ROSETTA的决策表属性约简实验--陈涛

粗糙集理论学习心得与基于ROSETTA的决策表属性约简实验陈涛(@chentao1999)@gmail.com摘要人类认知具有不确定性。粗糙集理论是处理这种不确定性的数学理论。粗糙集理论不断发展的同时，粗糙集的应用也越来越广泛。主要集中在两个方面：1.粗糙集的知识约简2.粗糙集与其他方法的融合。ROSETTA粗糙集数据分析工具集是挪威人AleksanderØhrn以他在博士论文期间开发的粗糙集工具基础上发展而来的。具有数据导入导出、补全、离散化、知识约简、过滤、分类、规则生成以及获取等价类、上下近似集等功能。本文是《软计算方法及其应用》课程学习期间的心得和实验总结。共分四部分。第一部分回顾《软计算方法及其应用》课程粗糙集部分的学习心得；第二部分介绍ROSETTA工具集的功能、使用方法和应用实例。第三部分介绍基于ROSETTA的决策表属性约简实验。第四部分是实验分析与总结。关键词：不确定性、粗糙集、知识约简、ROSETTA工具集1粗糙集理论学习心得：1.1概念的外延和内涵人类认知具有不确定性。人们表达一个不确定的概念时一般有两种方法：外延法和内涵法。符合某概念对象的全体构成此概念的外延，区别于其他概念的全体本质属性就是此概念的内涵。一个概念可以用枚举式的外延法表示，也可以用描述式的内涵法表示。粗糙集理论中的上下近似集就相当于人们日常表达的概念的外延和内涵。图1集合的上下近似如图1所示，折线相连构成的闭合区域表示不确定的概念X，灰色外边界和黑色外边界表示人们使用能够确定表达的概念，也就是概念X的外延和内涵。人们无法直接表达概念X，但可以通过X的外延和内涵间接表达。同时概念X的外延和内涵可以用来反映X的不确定性即概念的不精确性。图中灰色区域越大，表示概念X的精确性越低。由图1可以看出，概念X的表达只依赖于人们所了解的关于X的外延知识和内涵知识，不需要预先知道额外信息。粗糙集理论对事物的不精确性表达不需要任何假定的先验知识，只依赖于所给定的知识表达系统，通过上下近似算子直接计算得到，这一点与概率论和模糊集合理论完全不同，这也是粗糙集理论受到广泛关注的原因之一。1.2知识是一种分类能力粗糙集理论受到广泛关注的另一个原因是它对知识的观点。在粗糙集理论中，知识（人的智能）是一种对对象进行分类的能力。这里的“对象”包括：实物，状态，抽象概念，过程和时间等。我们通常用等价关系或关系来表示分类和知识。粗糙集理论把知识定义为关于论域的划分模式，从而使知识具有了颗粒性，我们称其为信息粒度或知识粒度，简称粒度。1.3信息系统图2信息系统实例粗糙集理论研究的对象一般是如图2所示的表格（信息表或决策表）。用形式语言表示为一个四元有序组S=U,V,f,A。其中U是对象（事例）的有限集合，U＝{x1,x2,...,xn}；A是属性的有限集合，A＝{A1,A2,...Am}；V是属性的值域集，V＝{V1,V2,...,Vm}，其中Vi是属性Ai的值域。f是信息函数（informationfunction），ｆ：Ｕ×Ａ→Ｖ，f(xi,Aj)Vj∈。图2是一个具体的信息系统实例。结合图2，U={x1,x2,x3,x4,x5,x6}，可以理解为x1,x2…x6，6个病人。A={头疼，肌肉疼，体温，流感}。V是A的值域，对于属性头疼V(头疼)={是，否}。信息函数f是粗线框框出的部分。1.4粗糙集的特征上文介绍了粗糙集理论中的概念：信息系统，上下近似集，划分等。下面介绍两种刻画粗糙集的方法：用近似程度的精确度来表示粗糙集的数字特征（表示集合边界域的大小，但没有说明边界域的结构）;用粗糙集分类表示粗糙集的拓扑特征（没有边界域大小的信息，提供了边界域的结构）。粗糙集的精度是下近似集元素个数与上近似集元素个数之商。集合（范畴或概念）的不精确性事由于边界域的存在而引起的，它的边界域越大，其精确性则越低。粗糙集中，精度反映对概念了解的程度，粗糙度反映对概念了解的不完全程度。近似分类的精度描述的是当前使用知识R对对象分类时，可能的决策中正确决策的百分比。近似分类质量表示的是应用知识R能确切地划入划分PI（U）的分类的对象的百分比。系统参数的重要度越大，集合X的R边界域越小，当它达到1时表明用知识R可精确描述集合X，对划分而言也是一样的。当它为0表明用知识R无法判定论域U中任意元素是否属于概念X，也就是说知识R是可以约简的。知识Q依赖于知识P的程度k，记为P→kQ，表示由Q导出的分类U/Q的正域覆盖来知识库中论域U的k×100%个元素。换句话说，论域中有k×100%个元素可以通过知识P准确划入到分类U/Q的等价类中。集合的近似与划分的近似是两个不同的问题。划分中每一个范畴，如果我们能确定论域中哪些元素是它的正例，也必然能确定它的反例。与粗糙集合的补集意义不同。1.5粗糙集的基本性质粗糙集的基本性质，如成员的隶属关系、集合的包含关系、集合的相等关系都是相对的，都与我们掌握的知识R相关。因此，可以认为粗糙集的方法是经典集合论方法的主观认识。粗糙集理论中，一个对象是否隶属于某一集合（概念），不是该元素的客观性质，而是取决于我们对它的了解程度，即知识R的分类能力。粗糙集中的粗糙包含关系，粗糙相等关系。主要是比较集合的拓扑结构而不是集合元素。在给定的知识库中，基于不同的知识，两个集合可能是精确相等，也可能是粗糙（近似）相等，或许是粗糙不相等。相等是相对的概念。1.6信息论的度量信息论的度量主要任务是度量颗粒性知识属性特征的重要性和属性特征之间关系的相依性程度。度量方法主要有：信息熵、条件熵和互信息。信息熵度量了信息源提供的平均信息量的大小。互信息量度了一个信息源从另一个信息源获取的信息量的大小。信息熵和互信息都随着知识粗糙性的增加而单调下降，通常反过来不成立。1.7知识约简信息系统和决策表中存在两种冗余：1.属性从整体角度而言存在冗余。2.属性从整体上讲是必要的，但对某对象在该属性上的取值可能存在冗余，即属性值的冗余。知识约简的一般步骤：1.删除表中重复对象。2.删除冗余的条件属性。3.删除每个对象的冗余属性值。4.求出其约简。知识的核是它最重要的部分，也就是最能体现知识特征的部分。1.核可以作为所有约简的计算基础。2.核可以解释为知识特征的最主要部分，在知识约简时它不能被删除，否则将减弱知识的分类能力。参数重要度强的属性对知识的分类能力越强，但将参数重要度强的知识结合在一起，分类能力不一定强。如果所有P中的知识对于论域U中的对象正确地划分到知识Q的基本范畴（IND（Q）等价类）都是必不可少的，那么知识P就是Q独立的。知识P的Q核是知识P最基本的特征部分。只有一个Q约简的知识P是确定的，因为当我们依照只是P的基本范畴将论域中的对象划分到知识Q的基本范畴中时只有一种P的知识基（P商集）可用。P有多个Q约简时是不确定的，因为有多种P的知识基可利用。P的Q核为空集时，知识P的不确定性达到最强。不相容决策表，粗糙集理论的处理方法是对每个决策概念计算其上下近似，从下近似导出的规则肯定成立，从上近似导出的规则可能成立，前者直接用于逻辑推理，后者有实例支持。属性约简算法分两种：1.盲目删除属性约简算法2.启发式算法：通过定义属性的一个重要度函数或差别函数来获取信息系统的属性约简。常见的属性约简算法有：1.基于Pawlak属性重要度的属性约简算法。2.基于Skowron差别矩阵的IS属性约简算法。3.基于信息熵的IS属性约简算法粗糙集理论的重要作用之一是提供了一种有效的从数据中获取规则的方法和工具。1.8粗糙集与自然语言的不确定性自然语言在表达事物的不确定性时往往用数量、频率、概率和程度等方式来描述事件从模糊到精确的变化，以便表示对某一命题的信任程度。程度型(A)：considerably,agreatdeal,(very)much,(quite)alot,rather,somewhat,abit,alittle,slightly,scarcely,hardly,onlyjust;程度型(B)：exactly,precisely,just,virtually,practically,moreorless,almost,nearly,approximately,about;数量型(C)：all/every/each,most,amajority,many/much,alot,enough,some,anumber,several,aminority,afew/little,no/none/not/any;频率型(D)：always,notnumerable,usual(ly),general(ly),regular(ly),often,frequent(ly),sometimes,occasional(ly),rate(ly),seldom,hardlyever;概率型(E)：certain(ly),definite(ly),undoubtedly,probably/probale,maybe,unlikely,improbable,doubtful,almostimpossible不确定性语言是可以度量的;事物的不确定性具有一定的不确定性区间;自然语言表示事物的不确定性和进行不确定性推理时，虽然信息本身有随机性，但人的表示和推理不是随机的，而是遵循一定的认识规律和行为法则。2ROSETTA工具集介绍：ROSETTA粗糙集数据分析工具集可能是目前最完整、最灵活和先进的粗糙集软件。它是由波兰华沙大学和挪威科技大学用C++联合开发的一个基于粗糙集理论框架的数据分析工具包。它的雏形是挪威人AleksanderØhrn在完成博士论文期间开发的粗糙集工具。ROSETTA实现了数据挖掘和知识发现的整个过程，包括多种数据导入导出、数据补全、数据离散化、知识约简、过滤、分类、规则生成验证与分析以及获取等价类、上下近似集等功能。它的C++库源代码可以在网站：上免费下载。图3ROSETTA图形界面展示1如图3所示，结点A表示从数据库导入的数据，结点A1表示对数据进行了补全操作。A2和A3结点表示将数据分为训练数据和测试数据两类，A4，A5，A6，A7是数据预处理阶段，分别对训练数据和测试数据进行部分离散化和全部离散化操作。RED结点表示对数据进行了约简，双击该结点可以看到属性约简的结果。RUL结点表示规则生成。图标的结点表示生成的结果数据文件。图4ROSETTA图形界面展示2图4展示的是ROSETTA的主要算法，包括数据补全、数据离散化、属性约简、过滤、分类、规则生成、上下近似集计算、等价类获取等。其中有RSES标注的是与粗糙集理论相关的算法。3实验操作3.1导入数据图5导入数据1图6选择数据格式图7导入的数据如图7所示，快速双击结点“Noname”即可看到导入的数据。慢速双击结点“Noname”将其重命名为“流感诊断数据”。3.2进行属性约简图8选择属性约简算法图9属性约简算法参数设定图10属性约简结果图8所示的属性约简算法中不同的算法约简的结果可能不一致。图10所示的属性约简结果：属性由原来的{头疼，肌肉疼，体温}，约简为{体温，头疼}。3.3规则生成图11规则生成图12生成的规则其中LHS是LeftHandSide的缩写，意指规则左边。RHS是RightHandSide的缩写，意指则右边。3.4等价类获取图13等价类获取1图14等价类获取2：选择属性图15选择属性{头疼，体温}得到的等价类图16等价类获取3：选择属性图17选择属性{头疼，肌肉疼}得到的结果3.5上下近似集获取图18获取上下近似集1图19获取上下近似集2：选择决策值和属性图20获取上下近似集3：结果图20中Universe表示论域U，Upper表示上近似集，Lower表示下近似集，Boundary表示边界域，Outside表示负域。4总结本实验选取的数据是《软计算方法及其应用》课程引用的例子，