粗糙集

粗糙集Roughset制作人：闵玉玲（06）江丽萍（12）吴佳（14）一、粗糙集的概念二、粗糙集的特点三、粗糙集的应用面对日益增长的数据库，将如何从这些浩瀚的数据中找出有用的知识？我们如何将所学到的知识去粗取精？什么是对事物的粗线条描述什么是细线条描述？一、粗糙集的概念（一）粗糙集概述在很多实际系统中均不同程度地存在着不确定性因素,采集到的数据常常包含着噪声,不精确甚至不完整.粗糙集理论是继概率论,模糊集,证据理论之后的又一个处理不确定性的数学工具。（二）相关概念知识:(举例说明）A={x1,x2,x3,x4,x5,x6,x7,x8}，每个积木块都有颜色属性，按照颜色的不同，我们能够把这堆积木分成R1={红，黄，兰}三个大类，那么所有红颜色的积木构成集合X1={x1,x2,x6}，黄颜色的积木构成集合X2={x3,x4}，兰颜色的积木构成集合X3={x5,x7,x8}。按照颜色这个属性我们就把积木集合A进行了一个划分(所谓A的划分就是指对于A中的任意一个元素必然属于且仅属于一个分类），那么我们就说颜色属性就是一种知识在这个例子中我们不难看到，一种对集合A的划分就对应着关于A中元素的一个知识假如还有其他的属性，比如还有形状R2={三角,方块,圆形}，大小R3={大,中,小}，这样加上R1属性对A构成的划分分别为：A/R1={X1,X2,X3}={{x1,x2,x6},{x3,x4},{x5,x7,x8}}（颜色分类）A/R2={Y1,Y2,Y3}={{x1,x2},{x5,x8},{x3,x4,x6,x7}}（形状分类）A/R3={Z1,Z2,Z3}={{x1,x2,x5},{x6,x8},{x3,x4,x7}}（大小分类）上面这些所有的分类合在一起就形成了一个基本的知识库。除了红的{x1,x2,x6}、大的{x1,x2,x5}、三角形的{x1,x2}这样的概念以外还可以表达例如大的且是三角形的{x1,x2,x5}∩{x1,x2}={x1,x2}，大三角{x1,x2,x5}∩{x1,x2}={x1,x2}，兰色的小的圆形({x5,x7,x8}∩{x3,x4,x7}∩{x3,x4,x6,x7}={x7}，兰色的或者中的积木{x5,x7,x8}∪{x6,x8}={x5,x6,x7,x8}。而类似这样的概念可以通过求交运算得到，比如X1与Y1的交就表示红色的三角形。所有的这些能够用交、并表示的概念以及加上上面的三个基本知识(A/R1,A/R2.A/R3)一起就构成了一个知识系统记为R=R1∩R2∩R3，它所决定的所有知识是A/R={{x1,x2},{x3},{x4},{x5},{x6},{x7},{x8}}以及A/R中集合的并。近似下近似集是在那些所有的包含于X的知识库中的集合中求并得到的，而上近似则是将那些包含X的知识库中的集合求并得到的。一般的，我们可以用右面的图来表示上、下近似的概念。这其中蓝色曲线围的区域是X的区域，紫色曲线围的部分是内部参考消息，是下近似，红色曲线围的内部部分就是上近似集。其中各个小方块可以被看成是论域上的知识系统所构成的所有划分。整个粗集理论的核心就是上面说的有关知识、集合的划分、近似集合等等概念。1.关于粗糙集的用途粗糙集是用来处理不确定信息不确定性按性质划分:1)随机性.例:明天可能会下雨2)模糊性:模糊性就是一个命题中所出现的某些言词概念上无明确的内涵和外延。模糊现象是指边界不清楚，在质上没有确定性的含义，在量上没有确切界限的事物的一种客观属性，是事物之间的差异存在一定的中间过渡的结果.例:这孩子是个聪明的孩子3)不完全性:例:在炒股票中.4)不一致性:相同原因产生不一样的结果5)时变性:随着时间会改变的事物一些基本术语论域：数学定义是：U={U1,U2,…,Um}解释：所要处理的所有对象（在数据库中即是所有数据）的总和例：例如，对于货票集合来说，其任意子集称为一个概念。根据运输距离对货票进行分类，可以形成不同的概念：概念1：运距在500公里（含500公里）以下的货票；概念2：运距在500公里－1500公里（含1500公里）间的货票；概念3：运距在1500公里以上的货票。对于上例来说U就是货票集合，它由价格分成了3个概念即类（U1,U2,U3）粗糙集理论建立在这样一个前提上：即所考虑的论域中的每一个对象都包含某种信息（数据和知识）。条件属性集：数学定义是：P={P1,P2,…,Pm}解释：就是对象的各种属性总和（也就是数据库中的字段）Pm就是这个对象的一个属性基本集（基本粒度）：定义：所有不可区分的对象形成的集合解释：可区分（可分辨）：如果Ui≠Uj就称这两个对象在其条件P下是可区分的（对于两个不同的对象至少有一个属性是不同的）否则即为不可区分例对于上表来说，U中有四个对象（概念），而现在条件集合中只有一个属性，对于U1和U2来说，它们的p不同所以可以通过p来区分，即u1,u2在p下可区分；而U2和U3虽然是不同的对象但是在P下却是相同的，即在p下不可区分，就成为不可区分粗糙集：一个集合若恰好等于基本集的任意并集称为一个清晰（crisp）集（精确集），否则称为粗糙（rough）集（不精确集）。解释：都可区分的是清晰集，有不可区分的对象为粗糙集主要特点:以不完全信息或知识去处理一些不分明现象的能力,或依据观察、度量到的某些不精确的结果而进行分类数据的能力.粗糙集体现了集合中元素间的不可区分性.主要优势:它不需要提供问题所需处理的数据集合之外的任何先验知识,而且与处理其它不确定性问题的理论有很强的互补性.属性约简粗糙集是处理模糊数据的有力工具，而要达到这样的目的需要有两个重要的步骤来进行处理—属性约简和值约简，属性约简是对粗糙集合（那些不能区分的集合）进行纵向的简化，把不必要的属性去掉，即去掉这些属性也不会影响对象的区分能力，这样便于以后进一步的简约处理关于属性约简的一些基本概念1.由可区分的概念引申出来：如果在整个信息系统S（即带所有P的所有U）上所有Ui都互不相等，那么就称为这个S在P下是可分辨的，一般记作ind(P)解释：这个标号说明是在P这个条件集合下是可分辨的，而且另一个P’下可能不可分辨，所以在对于一个S是否分辨取决于它的属性集合，因此ind(P)只需一个参数P即可2.如果去掉P中的某个属性集合Pi，系统S仍然是可以分辨的，那么P中的Pi是可以简约的，一般记作ind（P-Pi）=ind（P）3.如果P中的任何一条属性都是不可简约的，那么就称P是独立的解释：P是独立的说明P中的任何一个属性都是必不可少的，它独立的表达一个系统分类的特征。属性约简的算法分析：初始状态：所有数据已存入数据库(以下为模拟数据)uabcdE110011210001300000411010511022621022现在设e为决策属性，其他为条件属性，即对于不同的对象，不同的条件属性的组合会对决策属性有怎么样的影响？算法思路：基本假设是能影响属性e的只有a,b,c,d四个（即系统在a,b,c,d,e下可区分）基本原则是如果所有的条件属性都是一样的两个对象其决策属性也应该是一样的（因为否则说明这个对象还有能影响其决策属性的条件属性未被列入表内）那么如果去掉某个条件属性，对于任意两个不同的决策属性其他属性都不同，那么这个属性冗余，否则这个属性必需（即前面的概念2）实例如表一所示.描述了一些人的教育程度以及是否找到了较好工作,旨在说明两者之间的关系.表1教育程度与是否找到好工作的关系姓名教育程度是否找到了好工作王治高中否马丽高中是李得小学否刘保大学是赵凯博士是设O表示找到了好工作的人的集合,则O={马丽,刘保,赵凯},设I表示属性“教育程度”所构成的一个等效关系根据教育程度的不同,该论域被分割为四个等效类:{王治,马丽},{李得},{刘保},{赵凯}.王治和马丽在同一个等效类中,他们都为高中文化程度,是不可分辨的.集合O的下逼近(即正区)为I3(O)=POS(O)={刘保,赵凯}集合O的负区为NEG(O)={李得}集合O的边界区为BND(O)={王治,马丽}集合O的上逼近为I3(O)=POS(O)+BND(O)={刘保,赵凯,王治,马丽}根据表1,可以归纳出下面几条规则,揭示了教育程度与是否能找到好工作之间的关RULE1:IF(教育程度=大学)OR(教育程度=博士)THEN(可以找到好工作)RULE2:IF(教育程度=小学)THEN(找不到好工作)RULE3:IF(教育程度=高中)THEN(可能找到好工作)从这个简单的例子中,我们还可以体会到粗糙集理论在数据分析,寻找规律方面的作用二、粗糙集的特点粗糙集方法的简单实用性是令人惊奇的,它能在创立后的不长时间内得到迅速应用是因为具有以下特点：(1)它能处理各种数据,包括不完整(incomplete)的数据以及拥有众多变量的数据;(2)它能处理数据的不精确性和模棱两可(ambiguity),包括确定性和非确定性的情况;(3)它能求得知识的最小表达(reduct)和知识的各种不同颗粒(granularity)层次;(4)它能从数据中揭示出概念简单,易于操作的模式(pattern);(5)它能产生精确而又易于检查和证实的规则,特别适于智能控制中规则的自动生成.特点综述：粗糙集理论作为一种处理不精确(imprecise)、不一致(inconsistent)、不完整(incomplete)等各种不完备的信息有效的工具。一方面得益于他的数学基础成熟、不需要先验知识；另一方面在于它的易用性。由于粗糙集理论创建的目的和研究的出发点就是直接对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律，因此是一种天然的数据挖掘或者知识发现方法，它与基于概率论的数据挖掘方法、基于模糊理论的数据挖掘方法和基于证据理论的数据挖掘方法等其他处理不确定性问题理论的方法相比较，最显著的区别是它不需要提供问题所需处理的数据集合之外的任何先验知识，而且与处理其他不确定性问题的理论有很强的互补性(特别是模糊理论)。粗糙集理论所处理的问题•不确定或不精确知识的表达;•经验学习并从经验中获取知识;•不一致信息的分析;•根据不确定,不完整的知识进行推理;•在保留信息的前提下进行数据化简;•近似模式分类;•识别并评估数据之间的依赖关系三、粗糙集的应用粗糙集理论在许多领域得到了应用：①临床医疗诊断；②电力系统和其他工业过程故障诊断；③预测与控制；④模式识别与分类；⑤机器学习和数据挖掘；⑥图像处理；⑦其他。关于粗糙集算法研究了粗糙集理论属性约简算法和规则提取启发式算法，例如基于属性重要性、基于信息度量的启发式算法，另一方面研究和其他智能算法的结合，如：和神经网络的结合，利用粗糙集理论进行数据预处理，以提高神经网络收敛速度；和支持向量机SVM结合；和遗传算法结合；特别是和模糊理论结合，取得许多丰硕的成果，粗糙理论理论和模糊理论虽然两者都是描述集合的不确定性的理论，但是模糊理论侧重的是描述集合内部元素的不确定性，而粗糙集理论侧重描述的是集合之间的不确定性，两者互不矛盾，互补性很强，是当前国内外研究的一个热点之一。粗糙集展望粗糙集是一种较有前途的处理不确定性的方法,相信今后将会在更多的领域中得到应用.但是,粗糙集理论还处在继续发展之中,尚有一些理论上的问题需要解决,诸如用于不精确推理的粗糙逻辑(Roughlogic)方法,粗糙集理论与非标准分析(Nonstandardanalysis)和非参数化统计(Nonparametricstatistics)等之间的关系等等.将粗糙集与其它软计算方法(如模糊集,人工神经网络,遗传算法等)相综合,发挥出各自的优点,可望设计出具有较高的机器智商(MIQ)的混合智能系统(HybridIntelligentSystem),这是一个值得努力的方向.