第五讲：粗糙集(Rough-Set)

1第三节粗糙集（RoughSet，RS）如果我们将研究对象看成是现象，那么我们可以将这些现象分类。现象被分为确定现象与不确定现象。不确定现象有分为随机现象，模糊现象和信息不全的粗糙现象。如下所示：确定现象随机现象，0－1律，多种可能性满足分布规律。现象不确定现象模糊现象，律属度Î(0，1），不是非此即彼。粗糙现象，研究那些因为信息不充分而导致的不确定性相对于前两种现象的处理，粗糙现象是基于不完全的信息或知识去处理不分明的现象，因此需要基于观测或者测量到的部分信息对数据进行分类，这就需要与概率统计和模糊数学不同的处理手段，这就是粗糙集理论。直观地讲，粗糙集是基于一系列既不知道多了还是少了，也不知道有用还是没用的不确定、不完整乃至于部分信息相互矛盾的数据或者描述来对数据进行分析、推测未知信息。下面我们对粗糙集的基本特征、以及数学符号进行简述。1．粗糙集的特点粗糙集的特点是利用不精确、不确定、部分真实的信息来得到易于处理、鲁棒性强、成本低廉的决策方案。因此更适合于解决某些现实系统，比如，中医诊断，统计报表的综合处理等。粗糙集的另一个重要特点就是它只依赖于数据本身，不需要样本之外的先验知识或者附加信息，因此挑选出来的决策属性可以避免主观性，有英雄不问出身的意味。用粗糙集来处理的数据类型包括确定性的、非确定性的、不精确的、不完整的、多变量的、数值的、非数值的。粗糙集使用上、下近似来刻画不确定性，使得边界有了清晰的数学意义并且降低了算法设计的随意性。3．粗糙集的基本概念粗糙集要涉及论域U（这与模糊系统相似），还要涉及属性集合RCD2（这被认为是知识，或者知识库）。当然，也要有属性值域V，以及从UR到V的信息函数f。因此，一个信息系统S可以表示为一个四元组,,,SURVf。在不混淆的情况下，简记为(,)SUR，也称为知识库。等价关系（通常用来代替分类）是不可或缺的概念，根据等价关系可以划论域中样本为等价类。而每个等价类被称为同一个对象。但是，等价关系又是建立在不可分辨概念之上的，为了便于描述这里的等价关系，我们首先介绍不可分辨性。设BR为一个非空子集，如果,ijxxU，均有(,)(,),ijfxrfxrrB成立，那么，我们称ijxx和关于属性子集B不可分辨。B不可分辨关系，简记为()IndB，是一种等价关系（易验证它满足等价关系的数学公理），于是()IndB可以将论域U中的元素分成若干等价类，每一个等价类称为知识库的知识颗粒。全体等价类组成的集合记为/()UIndB，称之为基本集合。若集合X可以表示成某些基本集的并时，则称X是B精确集，否则称为B粗糙集。粗糙集中的“粗糙”主要体现在边界域的存在，而边界又是由下、上近似来刻画的。对于任意XU，X关于现有知识R的下、上近似分别定义为：_(){,[]}RRXxUxX，(){,[]}RRxxUxX。X的确定域PosXRX，是指论域U中那些在现有知识R之下能够确定地归入集合X的元素的集合。反之，NegXURX被称为否定域。边界域是某种意义上论域的不确定域，即在现有知识R之下U中那些既不能肯定在X中，又不能肯定归入\XUX中的元素的集合，记为RBndX。样本子集X的不确定性程度可以用粗糙度RaX来刻画，粗糙度的定义为：RCardRXaXCardRX式中Card表示集合的基数（集合中元素的个数）。显然，01RaX，如果1RaX，则称集合X关于R是确定的；如果1RaX，则称集合X关于R是粗糙的，RaX可认为是在等价关系R下逼近集合X的精度。为了使得上述概念具体化，下面我们举一个例子说明如何理解和计算以上相应的概念和对应量。3例.针对一下医学信息表我们来理解前面所提到的概念。表1某医疗信息表属性对象条件属性C决策属性D头疼r1肌肉疼r2体温r3流感1x是是正常否2x是是高是3x是是很高是4x否是正常否5x否否高否6x否是很高是依据此表，如果取属性子集12,,Rrr头疼肌肉疼，123,,Xxxx。那么我们下面给出X的上近似集、下近似集、确定域、边界域、粗糙度。解：①计算论域U的所有R基本集：123465/,,,,,UIndRxxxxxx令112324635,,,RxxxRxxRx②确定样本子集X与基本集的关系112235{,}{}XRxxXRXRx；；③计算RX、RX、PosXBndX和：131235355123{,,}{}{}{,,}RXRRxxxxRXRxPosXRXxBndXRXRXxxx；；④计算近似精确度：1/40.25RCardRXaZCardRX与粗糙度类似，在给出了两个知识集（特征属性）的相对肯定域的概念()PPosQ之后，我们也可以一个量来刻画两个知识集的依赖度。设(,)KUR为一个知识库，,PQR为两个知识集。令()(())/()PPkrQCardPosQCardU，4称为知识Q依赖于知识P的依赖度。特别，当1k时称为完全依赖；01k时，部分依赖；0k时，Q完全独立于知识P。3．知识约简知识约简是粗糙集的核心内容之一，它是研究知识库中哪些知识是必要的，以及在保持分类能力不变的前提下，删除冗余的知识。在粗糙集应用中，约简与核是两个最重要的基本概念。（1）一般约简设,PQ是属性集，Q中的每一个属性都是不可省略的。如果QP且()()IndQIndP，则称Q是P的一个约简（Reduce）,记为Re()dP。另外，若以()CoreP记P中所有不可省略的属性集合称为P的核（Core），那么所有约简RedP的交正好等于P的核，即ReCorePdP。该式的意义在于，不仅体现了核与所有约简的关系直接由约简得到，而且也表明了核是知识库中最重要的部分，是进行知识约简的过程中不能删除的知识。（2）相对约简一般地，考虑一个分类相对于另一个分类的关系，这就导出了相对约简与相对核的概念。在粗糙集中，相对约简的概念是条件属性相对决策属性的约简。我们需要给出如下的概念：设P和Q为论域U上的两个等价关系，定义Q关于P的相对肯定域，记为PPosQ，为论域U中的所有那些对象构成的集合，它们可以在分类/UP的知识指导下，被正确地划入到/UQ的等价类之中。即/PPosQPXXUQ其中，PX是集合X的下近似。设P和Q为论域U上的两个等价关系，rP。如果({})PPrPosQPosQ5那么称r关于Q可省略，否则称为Q不可省略。特别，当{}Pr为P中的独立子集（即它的每个元素都再不可省略），且({})PPrPosQPosQ。那么称{}Pr为P的关于Q的相对约简，记为()QIndP。P的所有关于Q的相对约简之交称为P的关于Q的核，记为()QCoreP。此时有()()QQCorePIndP。比较相对约简与一般约简的定义，我们能够发现，前者是在不改变决策属性Q的前提下对特征属性集P的约简，而后者是不改变对于论域中对象的分辨能力的前提下对于特征属性集的约简。（3）决策表的约简决策表约简的重要内容之一是简化决策表中的条件属性使得约简前后的决策表具有相同的功能。同样的决策可以通过基于更少量的条件，便于我们借助一些简单的手段就能获得同样要求的结果，这是事半功倍的好事。（1）分辨矩阵和分辨函数分辩矩阵是粗糙集中又一个重要概念，它将决策表中关于属性区分的信息浓缩进一个矩阵当中，可用于决策表的属性约简。一信息系统,,,SURVf中，12{,,...,}nUxxx为论域，RCD是属性集合，{,1,2,...,}iCaim与{,1,2,...,}jDdjl分别为条件属性集和决策属性集，jaxk是样本jx在属性ak上的取值。该系统的分辨矩阵定义为一个nn阶矩阵[]nnijmMS，其中第i行j行处元素,,1,2,...,kkikjiiijaCaxaxDxDxDxDxijnijm，也即，分辨矩阵中元素ijm是能够区别对象ix和jx的所有属性的集合。但若ix和jx属于同一个决策类时，则分辨矩阵中元素ijm的取值为空集。由定义可见，[]ijnnmMS是一个对称矩阵，主对角线上的元素是空集。因此只要考虑上半6或者下半三角部分足亦。每一个分辨矩阵M(S)，可以诱导出一个分辨函数Msf如下：12,,...,{1}mijijMsfaaamjinm，，它实际上是一个具有m元变量12,,...,,,1,2,...,miaaaaCim的布尔函数，它是ijm的合取，而ijm是矩阵项ijm中的各元素的析取。根据分辨函数与约简的对应关系，可以得到计算信息系统S约简Red(S)的方法为：;2);3),msSMSMSfmij1)计算信息系统的分辨矩阵计算分辨矩阵对应的分辨函数f计算分辨函数的最小析取范式其中每个析取分量对应一个约简.下面举例说明如何利用分辨矩阵及分辨函数求约简及核。设有信息系统126,,{,,...,},{,,,}SURUxxxRabcd其数据表格如下表所示。表信息系统数据表U/RabcdU/Rabcd1x00004x12122x02115x10013x01006x1212解：根据式（1-11），分辨矩阵M（S）为：表1-5分辨矩阵U1x2x3x4x5x6x1x2xb,c,d3xbb,c,d74xa,b,c,da,da,b,c,d5xa,da,b,ca,b,db,c,d6xa,b,c,da,ba,b,c,d—b,c,d再根据式（1-12），分辨函数为,,,{)msfabcdbcdbabcdadabcdbcdadabcdadabcdabcdabcdbcdbcdbadadbd因此，该信息系统有两个约简{,}{,}{}abbdb和，核是。由此得到两个约简的数据表格，如表1-6所示。表1-6两个约简数据表UabUbd1x001x002x022x213x013x104x124x225x105x016x126x22（2）决策表决策表是一类特殊而重要的知识表达系统，它是指当满足某些条件时，决策应该怎样进行，多数决策问题都可以用决策表形式来表达，决策表根据知识表达系统定义如下：,SUR设为一知识表达系统，若R可划分为条件属性集C和决策属性集D，即,CDRCD。则称为CD决策表，改记为,,,TURCD。Ind（C）8的等价类称为条件类，Ind(D)的等价类称为决策类。决策表可分为一致决策表和非一致决策表。当D完全依赖于C（CD）时，称为一致的；当部分依赖（01CkDk）时，称决策表是不一致的。特别指出，决策表是否能够约简，取决于它是否为一致决策表。这是因为不同原因可以产生相同结果，但同一个原因则不允许导致多种结果。对于一个决策表，一般首先将其分解为一个一致决策表与一个不一致的决策表，然后再对一致决策表进行约简。约简的方法还是使用分辨矩阵的方法。此时，属性特征集C相对于决策属性集D的核()DCoreC恰为分辨矩阵中所有ijm为单元素集决定。也即()|..{},1,DkijijkCoreCamstmaijn特别，如果CC是满足条件,ijijCmm，且C是最小的，那么称C为C相对于决策属性集D的约简。约简之后的决策表具有更少的条件属性，但却没有损失知识含量。同样对于决策属性也可以约简。但是约简后的决策表还是不能直接看出条件与决策属性之间的关系，因此还需要挖掘出决策