第七章粗糙集理论

1、1人人 工工 智智 能能Artificial Intelligence粗糙集理论与应用粗糙集理论与应用董春游董春游(Chunyou Dong) PhD,Professor (Chunyou Dong) PhD,Professor Email:Email:研研究生究生学学院院2第十七讲 粗糙集与数据约简 不确定性理论不确定性理论1 粗糙集的基本理论与方法粗糙集的基本理论与方法2 知识的约简知识的约简3 决策表的约简决策表的约简4 粗糙集数据约简的具体实现与应用粗糙集数据约简的具体实现与应用5 粗糙集的研究现状与展望粗糙集的研究现状与展望63 粗糙集（粗糙集（Rough SetsRough Set

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

3、它的意义。 19921992年在波兰年在波兰KiekrzKiekrz召开了第一届国际召开了第一届国际RSRS研讨会。这次会议研讨会。这次会议着重讨论了集合近似定义的基本思想及应用，其中着重讨论了集合近似定义的基本思想及应用，其中RSRS环境下的机环境下的机器学习基础研究是这次会议的四个专题之一。器学习基础研究是这次会议的四个专题之一。4 1993 1993年在加拿大年在加拿大BanffBanff召开第召开第二届国际二届国际RSRS理论与知识发现研讨理论与知识发现研讨会。这次会议积极推动了国际上会。这次会议积极推动了国际上对对RSRS理论与应用的研究。由于当理论与应用的研究。由于当时正值时正值K

4、DDKDD（数据库知识发现）成（数据库知识发现）成为研究的热门话题，一些著名为研究的热门话题，一些著名KDDKDD学习者参加这次会议，并且介绍学习者参加这次会议，并且介绍了许多应用扩展了许多应用扩展RSRS理论的知识发理论的知识发现方法与系统。现方法与系统。 19961996年在日本东京召开了第年在日本东京召开了第5 5届国际届国际RSRS研讨会，推动了亚洲地研讨会，推动了亚洲地区对区对RSRS理论与应用的研究。理论与应用的研究。 19951995年，年，ACM CommunicationACM Communication将其列为新浮现的将其列为新浮现的计算机科学的计算机科学的研究课题。研究课

5、题。5 19981998年，国际信息科学杂志（年，国际信息科学杂志（Information Information SciencesSciences）为粗糙集理论的研究出了一期专辑）为粗糙集理论的研究出了一期专辑22，33。第一届中国第一届中国RSRS理论与软计算学术研讨会，于理论与软计算学术研讨会，于20012001年年5 5月月在重庆举行。在重庆举行。第二届中国第二届中国RSRS理论与软计算学术研讨会，于理论与软计算学术研讨会，于20022002年年1010月月在苏州大学举行。在苏州大学举行。第三届中国第三届中国RSRS理论与软计算学术研讨会，于理论与软计算学术研讨会，于20032003年

6、年8 8月月在重庆举行。在重庆举行。第四届中国第四届中国RSRS理论与软计算学术研讨会，将于理论与软计算学术研讨会，将于20042004年在年在舟山举行。舟山举行。第八届中国粗糙集与软计算学术会议第八届中国粗糙集与软计算学术会议 , 2008 年 8 月 22 日至 8 月 24日在河南省新乡市召开中国6 粗糙集的理论及应用的文章粗糙集的理论及应用的文章 主要发表在以下杂志主要发表在以下杂志国内：国内： 1模式识别与人工智能模式识别与人工智能 2软件学报软件学报 3科学通报科学通报 4计算机科学计算机科学 5计算机学报计算机学报 6模糊系统与数学模糊系统与数学 7计算机应用与软件计算机应用与软

7、件 8计算机研究与发展计算机研究与发展 9计算技术与自动化计算技术与自动化 国际：国际： 1Information Sciences 2Fuzzy sets and systems 3International Journal of Computer and Information Sciences 4Communication of the ACM 5Computational Intelligence 6Journal of computer and system sciences7 AI Magazine8 AI Communications9 European Journal of O

8、perational Research10International Journal of Approximate Reasoning11Theoretical computer sciences12Decision support Systems13International Journal of Man-Machine studies 14Fundamenta Informaticae15Intelligent Automation Sciences 7 性质：性质：粗糙集理论是一种粗糙集理论是一种处理不精确、不确定与不完全数据处理不精确、不确定与不完全数据的新的数学方法。的新的数学方法。

9、 应用领域：应用领域：机器学习与知识发现、数据挖掘、决策支持与分析、专家系机器学习与知识发现、数据挖掘、决策支持与分析、专家系统、归纳推理、模式识别统、归纳推理、模式识别等方面的广泛应用，现已成为一个热门的研究领域等方面的广泛应用，现已成为一个热门的研究领域2。 RS理论主要兴趣在于它恰好反映了人们用理论主要兴趣在于它恰好反映了人们用Rough集方法处理不分明问题的常规性，集方法处理不分明问题的常规性，即以不完全信息或知识去处理一些不分明现象的能力。或依据观察，度量到的某些不确即以不完全信息或知识去处理一些不分明现象的能力。或依据观察，度量到的某些不确定的结果而进行分类数据的能力定的结果而进行

10、分类数据的能力4。粗糙集理论的优点及局限性主要优点粗糙集理论的优点及局限性主要优点优点：除数据集之外，无需任何先验知识（或信息）优点：除数据集之外，无需任何先验知识（或信息）对不确定性的描述与处理相对客观对不确定性的描述与处理相对客观【说明】：【说明】：Bayes理论、模糊集理论、证据理论等都需要先验知识，具有很大的主理论、模糊集理论、证据理论等都需要先验知识，具有很大的主观性。观性。81、不确定性理论 自然界和人类的社会活动的各种现象：确定性现象和不确定性现象。 确定性现象：在一定条件下必然会出现的现象。（1）不确定性的分类：随机性：因为事物的因果关系不确定，从而导致事件发生的结果不确定性。

11、用概率来度量。概率表示事件发生可能性的大小。概率论的运用是从随机性中去把握广义的因果律概率规律。模糊性：因为事件在质上没有明确的含义，在量上没有明确的界限，导致事件呈现“亦此亦彼”的性态，是事物类属的不确定性，用隶属度来度量。隶属度表示事物多大程度属于某个分类。模糊集合论的运用从模糊性中去确立广义的排中律隶属规律。粗糙性：因为描述事件的知识（或信息）不充分、不完全，导致事件间的不可分辨性。粗糙集把那些不可分辨的事件都归属一个边界域。因此，粗糙集中的不确定性是基于一种边界的概念，当边界域为一空集时，则问题变为确定性的。9（2）经典集合、模糊集合、粗糙集的关系 经典集合认为一个集合完全有其元素所决

12、定，一个元素要么属于这个集合，要么不属于这个集合。其隶属函数X(x) 0,1是二值逻辑。 模糊集合认为事物具有中介过渡性质，而非突然改变，集合中每一个元素的隶属函数X(x) 0,1，即在闭区间0,1可以任意取值，隶属函数可以是连续光滑的，因此模糊集合对不确定信息的刻划是精细而充分的。但隶属函数不可计算，凭人的主观经验给定。 粗糙集合把用于分类的知识引入集合分类的知识引入集合。一个元素x是否属于集合X，需要根据现有知识来判定，可分为三个情况：x肯定不属于X；x肯定属于X；x可能属于也可能不属于X。到达属于哪种情况依赖于我们所掌握的关于论域的知识。粗糙集的隶属函数为阶梯状，对不确定性信息的描述是粗

13、糙的，但粗糙隶属函数是可计算的。粗糙集主要用于对信息系统进行约简和分类行约简和分类。1.00.80.60.40.20.00.20.40.60.81.0102、 粗糙集的基本理论与方法 粗糙集的基本概念粗糙集的基本概念1 粗糙集的基本思想粗糙集的基本思想2 粗糙集的基本特点粗糙集的基本特点3111）粗糙集的基本概念（1）知识与分类 在粗糙集理论中，知识被认为是一种分类能力在粗糙集理论中，知识被认为是一种分类能力。人们的行为基本是分辨现实的或抽象的对象的能力。 假定我们起初对论域内的对象（或称元素、样本、个体）已具有必要的信息或知识，通过这些知识能够将其划分到不同的类别。若我们对两个对象具有相同的

14、信息，则它们是不可区分的，即根据已有的信息不能将其划分开。 粗糙集理论的核心是等价关系，通常用等价关等价关系替代分类系替代分类，根据这个等价关系划分样本集合为等价类。基本思想：从知识库的观点看，每个等价类被称每个等价类被称为一个概念为一个概念，即一条知识（规则)。即，每个等价类唯一地表示了一个概念，属于一个等价类的不同对象对该概念是不可区分的。12（2）知识表达系统 一个知识表达系统或信息系统S可以表示为有序四元组S=U,R,V,f其中，U=x1,x2,xn为论域，它是全体样本的集合；RCD 为属性集合，其中子集C是条件属性集，反映对象的特征，D为决策属性集，反映对象的类别； 为属性值的集合，

15、Vr表示属性r的取值范围；f:URV 为一个信息函数，用于确定U中每一个对象x的属性值，即任一xi U，r R，则f(xi,r)=VrRrrVV属性对象条件属性C决策属性D头疼r1肌肉疼r2体温r3流感x1是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是13 （3）不可分辨关系不可分辨关系在粗糙集中，论域U中的对象可用多种信息（知识）来描述。当两个不同的对象由相同的属性来描述时，这两个对象在该系统中被归于同一类，它们的关系称之为不可分辨关系。即对于任一属性子集BR，如果对象xi,xj U，r B，当且仅当f(xf(xi i,r)=f(x,r)=f(xj j,r),r

16、)时，xi和xj是不可分辨的，简记为Ind(B)Ind(B)。不可分辨关系称为等价关系不可分辨关系称为等价关系。例如：只用黑白两种颜色把空间中的一些物体划分成两类：黑色物体、白色物体，那么同为黑色的物体就是不可分辨的，因为描述它们特征属性的信息是相同的，都是黑色。如果引入方、圆的属性，可将物体进一步划分为4类：黑色方物体、黑色圆物体、白色方物体、白色圆物体。这时，如果有两个同为黑色方物体，则它们还是不可分辨的。不可分辨关系这一概念在RS中十分重要，它反映了我们对世界观察的不精确性。另一方面，不可分辨关系反映了论域知识的颗粒性论域知识的颗粒性。知识库中的知识越多，知识的颗粒度就越小，随着新知识不

17、断加入到知识库中，粒度会不断减小，直致将每个对象区分开来。但知识库中的知识粒度越小，则导致信息量增大，存储知识库的费用越高。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是是正常

18、否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是15（5）下近似集和上近似集 下近似集：根据现有知识R，判断U中所有肯定属于集合X的对象所组成的集合，即R R- -(X)=x(X)=x U,xU,xR R XX其中，其中， xxR R 表示等价关系表示等价关系R R下包含元素下包含元素x x的等价类。的等价类。 上近似集：根据现有知识R，判断U中一定属于和可能属于集合X的对象所组成的集合，即R(X)=x U,xR X其中， xR 表示等价关系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