第七章粗糙集理论

1

人工智能

ArtificialIntelligence

粗糙集理论与应用董春游(ChunyouDong)PhD,ProfessorEmail:chunyoudong@126.com研究生学院2第十七讲粗糙集与数据约简

不确定性理论1

粗糙集的基本理论与方法2

知识的约简3

决策表的约简4

粗糙集数据约简的具体实现与应用5

粗糙集的研究现状与展望63概论：粗糙集理论的提出及发展

粗糙集（RoughSets）是波兰数学家Z.Pawlak于1982年提出的[1]（为开发自动规则生成系统及研究软计算问题而引入）。由于最初关于粗糙集理论的研究大部分是用波兰语发表的，因此当时没有引起国际计算机学界和数学界的重视。研究地域也局限在东欧一些国家，直到80年代末才引起各国学者的注意。九十年代初，人们才逐渐认识到它的意义。

1992年在波兰Kiekrz召开了第一届国际RS研讨会。这次会议着重讨论了集合近似定义的基本思想及应用，其中RS环境下的机器学习基础研究是这次会议的四个专题之一。41993年在加拿大Banff召开第二届国际RS理论与知识发现研讨会。这次会议积极推动了国际上对RS理论与应用的研究。由于当时正值KDD（数据库知识发现）成为研究的热门话题，一些著名KDD学习者参加这次会议，并且介绍了许多应用扩展RS理论的知识发现方法与系统。

1996年在日本东京召开了第5届国际RS研讨会，推动了亚洲地区对RS理论与应用的研究。

1995年，ACMCommunication将其列为新浮现的计算机科学的研究课题。5

1998年，国际信息科学杂志（InformationSciences）为粗糙集理论的研究出了一期专辑[2，3]。第一届中国RS理论与软计算学术研讨会，于2001年5月在重庆举行。第二届中国RS理论与软计算学术研讨会，于2002年10月在苏州大学举行。第三届中国RS理论与软计算学术研讨会，于2003年8月在重庆举行。第四届中国RS理论与软计算学术研讨会，将于2004年在舟山举行。第八届中国粗糙集与软计算学术会议

,2008年8月22日至8月24日在河南省新乡市召开中国6

粗糙集的理论及应用的文章主要发表在以下杂志国内：1．模式识别与人工智能

2．软件学报

3．科学通报

4．计算机科学

5．计算机学报

6．模糊系统与数学

7．计算机应用与软件

8．计算机研究与发展9．计算技术与自动化

国际：1．InformationSciences2．Fuzzysetsandsystems3．InternationalJournalofComputerandInformationSciences4．CommunicationoftheACM5．ComputationalIntelligence6．Journalofcomputerandsystemsciences7．AIMagazine8．AICommunications9．EuropeanJournalofOperationalResearch10．InternationalJournalofApproximateReasoning11．Theoreticalcomputersciences12．DecisionsupportSystems13．InternationalJournalofMan-Machinestudies14．FundamentaInformaticae15．IntelligentAutomationSciences

7粗糙集理论

性质：粗糙集理论是一种处理不精确、不确定与不完全数据的新的数学方法。

应用领域：机器学习与知识发现、数据挖掘、决策支持与分析、专家系统、归纳推理、模式识别等方面的广泛应用，现已成为一个热门的研究领域[2]。

RS理论主要兴趣在于它恰好反映了人们用Rough集方法处理不分明问题的常规性，即以不完全信息或知识去处理一些不分明现象的能力。或依据观察，度量到的某些不确定的结果而进行分类数据的能力[4]。粗糙集理论的优点及局限性主要优点优点：除数据集之外，无需任何先验知识（或信息）对不确定性的描述与处理相对客观……【说明】：Bayes理论、模糊集理论、证据理论等都需要先验知识，具有很大的主观性。81、不确定性理论自然界和人类的社会活动的各种现象：确定性现象和不确定性现象。确定性现象：在一定条件下必然会出现的现象。（1）不确定性的分类：随机性：因为事物的因果关系不确定，从而导致事件发生的结果不确定性。用概率来度量。概率表示事件发生可能性的大小。概率论的运用是从随机性中去把握广义的因果律——概率规律。模糊性：因为事件在质上没有明确的含义，在量上没有明确的界限，导致事件呈现“亦此亦彼”的性态，是事物类属的不确定性，用隶属度来度量。隶属度表示事物多大程度属于某个分类。模糊集合论的运用从模糊性中去确立广义的排中律——隶属规律。粗糙性：因为描述事件的知识（或信息）不充分、不完全，导致事件间的不可分辨性。粗糙集把那些不可分辨的事件都归属一个边界域。因此，粗糙集中的不确定性是基于一种边界的概念，当边界域为一空集时，则问题变为确定性的。9（2）经典集合、模糊集合、粗糙集的关系经典集合认为一个集合完全有其元素所决定，一个元素要么属于这个集合，要么不属于这个集合。其隶属函数μX(x)∊{0,1}是二值逻辑。模糊集合认为事物具有中介过渡性质，而非突然改变，集合中每一个元素的隶属函数μX(x)∊[0,1]，即在闭区间[0,1]可以任意取值，隶属函数可以是连续光滑的，因此模糊集合对不确定信息的刻划是精细而充分的。但隶属函数不可计算，凭人的主观经验给定。粗糙集合把用于分类的知识引入集合。一个元素x是否属于集合X，需要根据现有知识来判定，可分为三个情况：①x肯定不属于X；②x肯定属于X；③x可能属于也可能不属于X。到达属于哪种情况依赖于我们所掌握的关于论域的知识。粗糙集的隶属函数为阶梯状，对不确定性信息的描述是粗糙的， 但粗糙隶属函数是可计算的。粗糙集主 要用于对信息系统进行约简和分类。1.00.80.60.40.20.00.20.40.60.81.0102、粗糙集的基本理论与方法

粗糙集的基本概念1

粗糙集的基本思想2

粗糙集的基本特点3111）粗糙集的基本概念（1）知识与分类在粗糙集理论中，知识被认为是一种分类能力。人们的行为基本是分辨现实的或抽象的对象的能力。假定我们起初对论域内的对象（或称元素、样本、个体）已具有必要的信息或知识，通过这些知识能够将其划分到不同的类别。若我们对两个对象具有相同的信息，则它们是不可区分的，即根据已有的信息不能将其划分开。粗糙集理论的核心是等价关系，通常用等价关系替代分类，根据这个等价关系划分样本集合为等价类。基本思想：从知识库的观点看，每个等价类被称为一个概念，即一条知识（规则)。即，每个等价类唯一地表示了一个概念，属于一个等价类的不同对象对该概念是不可区分的。12（2）知识表达系统一个知识表达系统或信息系统S可以表示为有序四元组

S={U,R,V,f}其中，U={x1,x2,…,xn}为论域，它是全体样本的集合；R＝C∪D为属性集合，其中子集C是条件属性集，反映对象的特征，D为决策属性集，反映对象的类别；为属性值的集合，Vr表示属性r的取值范围；f:U×R→V为一个信息函数，用于确定U中每一个对象x的属性值，即任一xi∊U，r∊R，则f(xi,r)=Vr属性对象条件属性C决策属性D头疼r1肌肉疼r2体温r3流感x1是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是13（3）不可分辨关系在粗糙集中，论域U中的对象可用多种信息（知识）来描述。当两个不同的对象由相同的属性来描述时，这两个对象在该系统中被归于同一类，它们的关系称之为不可分辨关系。即对于任一属性子集B⊆R，如果对象xi,xj∊U，∀r∊B，当且仅当f(xi,r)=f(xj,r)时，xi和xj是不可分辨的，简记为Ind(B)。不可分辨关系称为等价关系。例如：只用黑白两种颜色把空间中的一些物体划分成两类：{黑色物体}、{白色物体}，那么同为黑色的物体就是不可分辨的，因为描述它们特征属性的信息是相同的，都是黑色。如果引入方、圆的属性，可将物体进一步划分为4类：{黑色方物体}、{黑色圆物体}、{白色方物体}、{白色圆物体}。这时，如果有两个同为黑色方物体，则它们还是不可分辨的。不可分辨关系这一概念在RS中十分重要，它反映了我们对世界观察的不精确性。另一方面，不可分辨关系反映了论域知识的颗粒性。知识库中的知识越多，知识的颗粒度就越小，随着新知识不断加入到知识库中，粒度会不断减小，直致将每个对象区分开来。但知识库中的知识粒度越小，则导致信息量增大，存储知识库的费用越高。14（4）基本集合由论域中相互不可分辨的对象组成的集合称之为基本集合，它是组成论域知识的颗粒。例如：考虑条件属性：头疼和 肌肉疼。对于x1,x2,x3这三个 对象是不可分辨的。x4,x6在这 两个属性上也是不可分辨的。 由此构成的不可分辨集{x1,x2, x3},{x4,x6},{x5}被称为基本 集合。设论域U为有限集，R是U的等价关系簇，则K={U,R}称为知识库，知识库的知识粒度由不可分辨关系Ind(R)的等价类反映。属性对象条件属性C决策属性D头疼r1肌肉疼r2体温r3流感x1是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是15（5）下近似集和上近似集下近似集：根据现有知识R，判断U中所有肯定属于集合X的对象所组成的集合，即

R-(X)={x∊U,[x]R⊆X}

其中，[x]R表示等价关系R下包含元素x的等价类。上近似集：根据现有知识R，判断U中一定属于和可能属于集合X的对象所组成的集合，即

R－(X)={x∊U,[x]R∩X≠φ}

其中，[x]R表示等价关系R下包含元素x的等价类。给定知识表达系统S={U,R,V,f}，对于每个样本子集X⊆U和等价关系R，所有包含于X的基本集的并（逻辑和）为R-(X)；所有与X的交(逻辑积)不为空集的基本集的并为R－(X)。16（6）正域、负域和边界域正域：Pos(X)=R-(X)，即根据知识R，U中能完全确定地归入集合X的元素的集合。负域：Neg(X)=U-R-(X)，即根据知识R，U中不能确定一定属于集合X的元素的集，它们是属于X的补集。边界域：Bnd(X)=R-(X)-R-(X)，边界域是某种意义上论域的不确定域，根据知识R，U中既不是肯定归入集合X，又不能肯定归入集合~X，的元素构成的集合。边界域为集合X的上近似与下近似之差，如果Bnd(X)是空集，则称集合X关于R是清晰的；反之，如果Bnd(X)不是空集，则称集合X为关于R的粗糙集。因此，粗糙集中的“粗糙”（不确定性）主要体现在边界域的存在。集合X的边界域越大，其确定性程度就越小。17（7）粗糙度（近似精确度）对于知识R（即属性子集），样本子集X的不确定程度可以用粗糙度αR(X)来表示为αR(X)亦称近似精确度，式中Card表示集合的基数（集合中元素的个数）。0≤αR(X)≤1，如果αR(X)＝1，则称集合X相对于R是确定的，如果αR(X)<1则称集合X相对于R是粗糙的，αR(X)可认为是在等价关系R下逼近集合X的精度。定义：由属性集B定义X的近似质量为表示通过B中属性被正确分类的对象的相对频率，0《《118例1：以医疗信息表为例，对于属性子集R={头疼,肌肉疼}={r1,r2},计算样本子集X={x1,x2,x5}的上近似集、下近似集、正域、边界域。解：①计算论域U的所有R基本集：

U|Ind(R)={{x1,x2,x3},{x4,x6},{x5}}令R1={x1,x2,x3}R2={x4,x6}R3={x5}②确定样本子集X与基本集的关系

X∩R1={x1,x2}≠φX∩R2=φX∩R3={x5}≠φ③计算R-(X)、R－(X)、Pos(X)、Bnd(X)：

R-(X)=R3={x5} R－(X)=R1∪R3={x1,x2,x3,x5}Pos(X)=R-(X)={x5} Bnd(X)=R－(X)-R-(X)={x1,x2,x3}④计算近似精确度：属性对象条件属性C决策属性D头疼r1肌肉疼r2体温r3流感x1是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是19例2：右表是考生情况调查表，其中U为被调查对象，即论域；R为高考成绩(A－优，B－良，C－中，D－差)；X为升学情况(+为上，/为未上)。根据高考成绩和升学情况进行分类时：按成绩：U/R={{1,6},{2},{3,5},{4}}={Y1,Y2,Y3,Y4}按升学：U/X={{2,3,5,6},{1,4}}={X1,X2}分别计算出下近似集、上近似集、边界域和近似精度：R-(X1)=Y2∪Y3={2,3,5} R-(X2)=Y4={4}R-(X1)=Y2∪Y3∪Y1={2,3,5,6,1} R-(X2)=Y1∪Y4={4,6,1}Bnd(X1)=Y1={1,6} Bnd(X2)=Y1={1,6}αR(X1)=Card(R-(X1))/Card(R-(X1))=3/5αR(X2)=Card(R-(X2))/Card(R-(X2))=1/3URX1C/2B+3A+4D/5A+6C+根据ifRThenX根据ifRThenXR-(X1)高考成绩(A,B)一定(+)能上R-(X2)高考成绩(C,D)可能(/)不能上R-(X2)高考成绩(D)一定(/)不能上Bnd(X1)高考成绩(C)可能(+)也可能(/)R-(X1)高考成绩(A,B,C)可能(+)能上Bnd(X2)高考成绩(C)可能(+)也可能(/)20例3：表1所示的关于全球变暖的一个信息系统,a1—太阳能(Solarenergy)，a2—火山活动(Volcanicactivity),a3—二氧化碳含量（ResidualCO2,），d—温度（Temperature）21

对论域进行划分，可得如下等价类

U/C={X1,X2,X3,X4,X5,X6}其中：X1={n1}，X2={n2}，X3={n3}，X4={n4,n5,n6,n9}，X5={n7}，X6={n8}YH={n2,n3,n4,n5,n6,n8}，YL={n1,n7,n9}22X1={n1}，X2={n2}，X3={n3}，X4={n4,n5,n6,n9}，X5={n7}，X6={n8}YH={n2,n3,n4,n5,n6,n8}，YL={n1,n7,n9}据此可求得粗糙近似如下:YH的下近似：apr(Yn)={{n2},{n3},{n8}}YH的上近似：{{n2},{n3},{n8},{n4,n5,n6,n9}}YL的下近似：apr(YL)={{n1},{n7}}YL的上近似：{{n1},{n7},{n4,n5,n6,n9}

}YL的分类精度=3/7=0.43YH的分类精度=2/6=0.33

分类质量=5/9=0.56 `232）粗糙集的基本思想RS的基本思想RS认为知识就是将论域中的对象进行分类的能力。对对象的认知程度取决于所拥有的知识的多少，知识越多，则分类能力越强。知识越少，则对象间的区分越模糊。在没有掌握所有关于对象域的知识的情况下，为了刻画模糊性，RS使用了一对称为下近似与上近似的精确概念来表示每个不精确概念，即使用一对逼近来描述对象域上的集合。下近似和上近似的差是一个边界集合，它包含了所有不能确切判定是否属于给定类的对象。这种处理可以定义近似的精确度，能够很好的近似分类，得到可以接受质量的分类。在RS中，论域中的对象可用多种知识来描述(通常描述为属性)。当两个不同的对象由相同的属性来描述时，这两个对象在系统中被归于同一类，它们的关系称之为不可分辨关系或等价关系。不可分辨关系是RS理论的基石，它反映了论域知识的颗粒性。影响分类能力的属性很多，不同的属性重要程度不同，其中某些属性起决定性作用；属性的取值不同对分类能力也会产生影响。RS理论提出知识的约简方法、在保留基本知识、对对象的分类能力不变的基础上，消除重复、冗余属性和属性值，实现了对知识的压缩和再提炼。243）粗糙集的基本特点RS的基本特点

RS的基本方法是使用等价关系将集合中的元素(对象)进行分类，生成集合的某种划分，与等价关系相对应。根据等价关系的理论，同一分类(等价类)内的元素是不可分辨的，对信息的处理可以在等价类的粒度上进行，由此可以达到对信息进行简化的目的。RS是一种软计算方法，传统的知识处理是一种硬计算方法，使用精确、固定和不变的算法来表达和求解问题。而软计算方法则允许利用不精确性、不确定性和部分真实性以得到易于处理、鲁棒性强和低成本的解决方案。RS仅仅从数据本身进行分析，无需提供所要分析的样本数据以外的任何先验知识或附加信息，不要预先给予主观评价，如统计学中要假定概论分布，模糊集中要给定隶属度，证据理论中要赋予似然值等。RS能分析各种数据，包括确定性和非确定性的；不精确的和不完整的以及拥有众多变量的数据，并对数据进行简化，从而发现知识、推理决策规则，不仅是一种决策分析方法，而且是一种系统建模方法。25RS的基本特点（续）RS与其他不确定方法一样，它们都是处理含糊性和不确定性问题的数学工具。但它们又有不同之处：主观Bayes中，不确定性看成概率；D/S证据理论中，不确定性是可信度；模糊集合理论中，不确定性是集合的隶属度；RS理论中，不确定性是上下近似集之差，有确定的数学公式来描述。由于RS理论本身未包含处理不精确或不确定原始数据的机制，在实际应用中，RS方法常常需要与其他方法结合起来使用，互为补充。263知识的约简设U为所讨论对象的非空有限集论域，R为非空的属性有限集，则称二元有序组K={U,R}为一个知识库，亦称近似空间。在知识库中可能含有冗余的知识，知识约简是研究知识库中哪些知识是必要的，以及在保持分类能力不变的前提下，删除冗余的知识。特别是，当信息系统中的数据是随机采集的其冗余性更为普遍。知识约简是粗糙集理论的核心内容之一，在信息系统分析与数据挖掘等领域具有重要的应用意义。

271）一般约简一般约简 在粗糙集理论中，约简与核是两个最重要的基本概念。设R是一个等价关系族，且r∊R,若有

Ind(R)=Ind(R-{r})则称r在等价关系族R中是可省略的，否则r为R中不可省略的。若族R中每一个r都是不可省略的，则称族R为独立的。在用属性集R表达系统的知识时，R为独立的意味着属性集中的属性是必不可少的。它独立地构成一组表达系统分类知识的特征。定义：设Q⊆P，若Q是独立的，且Ind(Q)=Ind(R),则称Q是等价关系族P的一个约简，记为Red(P)。在P中所有不可省略关系的集合称为等价关系族P的核，记为Core(P)。知识约简与核的关系是：约简集Red(P)的交集等与P的核，即

Core(P)=∩Red(P)一方面核是所有约简的计算基础；另一方面，核是知识库中最重要的部分，是进行知识约简时不能删除的知识。28一般约简（续）例：设有知识库K={U,R},其中U={x1,x2,…,x8},R={R1,R2,R3},等价关系R1，R2，R3的等价类如下：

U/R1={{x1,x4,x5,x6},{x2,x3},{x7,x8}} U/R2={{x1,x2,x5},{x4,x6,x7},{x3,x8}} U/R3={{x1,x2,x5},{x4,x6},{x3,x7},{x8}}求约简和核。解：由题意有下列等价类：

U/Ind(R)={{x1,x5},{x2},{x3},{x4,x6},{x7},{x8}}U/Ind(R-R1)=U/{R2,R3}={{x1,x2,x5},{x3},{x4,x6},{x7},{x8}}≠U/Ind(R)U/Ind(R-R2)=U/{R1,R3}={{x1,x5},{x2},{x3},{x4,x6},{x7},{x8}}=U/Ind(R)U/Ind(R-R3)=U/{R1,R2}={{x1,x5},{x2},{x3},{x4,x6},{x7},{x8}}=U/Ind(R)因此，R1是R中不可省的，R2和R3是R中可省的。又因为U/Ind({R1,R2})≠U/Ind(R2),且U/Ind({R1,R2})≠U/Ind(R1)，因此R1和R2是独立的，所以{R1,R2}是R的一个约简。同理{R1,R3}也是R的一个约简。故核Code(R)={R1,R2}∩{R1,R3}=R1292）相对约简相对约简在实际应用中，一个分类相对于另一个分类的关系非常重要。在粗糙集中相对约简的概念，即条件属性相对决策属性的约简。设P和Q为论域U上的等价关系，Q的P正域记为PosP(Q),即

PosP(Q)=∪P-(X)Q的P正域是论域U中的所有那些使用分类U/P所表达的知识，能够正确地划入到U/Q的等价类之中的对象给出的集合。一个集合X相对于一个等价关系P的正区域就是这个集合的下近似P-(X)；而一个等价关系Q相对于另一个等价关系P的正区域的概念是解决分类Q的等价类(一般视为决策类)之中的那些对象可由分类P的等价类(一般视为条件类)来分类的问题。304.3.2、相对约简例考试(R)升学(X)表中，R和X为U中的等价关系，计算如下：R-(X1)=Y2∪Y3={2,3,5}R-(X2)=Y4={4}X的正域记为PosR(X),将所有的R-(X)取并集得PosR(X)＝∪R-(X)=R-(X1)∪R-(X2)={2,3,4,5}设P和Q为论域U上的等价关系，r∊P。若PosP(Ind(Q))=Pos(p-{r})(Ind(Q))则称r∊P为P中Q可省的，否则称r为P中Q不可省的。上式可记为PosP(Q)=Pos(p-{r})(Q)当P中的每一个r都是Q不可省的，则称P是相对于Q独立的，否则就称为是依赖的。当(P-r)为P的Q独立子族，且PosP(Q)=Pos(p-{r})(Q),则族(P-r)称为P的Q相对约简，记为RedQ(P)。它是用属性P表达属性Q必不可少的属性集，如果从分类的观点看，就是用一种分类关系表达另一种分类关系必不可少的关系集合。P所有Q约简的交集，称为P的Q核，记为CoreQ(P),亦称相对核。相对核和相对约简的关系为：CoreQ(P)=∩RedQ(P)URX1C/2B+3A+4D/5A+6C+31例设K={U,P}为知识库，U={x1,x2,…,x8},P={R1,R2,R3}。等价关系R1,R2,R3的等价类集合如下：

U/R1={(x1,x2,x3,x4},{x5,x6,x7,x8}} U/R2={(x1,x3,x4,x7},{x2,x6},{x5,x8}} U/R3={(x1,x5,x8},{x2,x3,x4},{x6,x7}}由等价关系族Q导出的不可分辨关系的等价类集合为

U/Q=U/Ind(Q)={{x1,x3,x4},{x2,x5,x6},{x7,x8}}求P的Q约简及P的Q核。解：等价关系族P导出的不可分辨关系Ind(P)的等价类为

U/P=U/Ind(P)={{x1},{x2},{x3,x4},{x5,x8},{x6},{x7}}Q的P正域为

PosP(Q)={x1}∪{x2}∪{x3,x4}∪{x6}∪{x7}={x1,x2,x3,x4,x6,x7}P中不可省的关系为U/(P-R1)=U/(R2,R3)={{x1},{x2},{x3,x4},{x5,x8},{x6},{x7}}U/(P-R2)=U/(R1,R3)={{x1},{x2,x3,x4},{x5,x8},{x6,x7}}U/(P-R3)=U/(R1,R2)={{x1,x3,x4},{x2},{x5,x8},{x6},{x7}}32Pos(P-R1)(Q)={x1}∪{x2}∪{x3,x4}∪{x6}∪{x7}={x1,x2,x3,x4,x6,x7}=PosP(Q)Pos(P-R2)(Q)={x1}≠PosP(Q)Pos(P-R3)(Q)={x1,x3,x4}∪{x2}∪{x6}∪{x7}={x1,x2,x3,x4,x6,x7}=PosP(Q)可见R2是P中Q