粗糙集理论

  • 更新时间: 2016-09-04
  • 来源: 原创或网络
  • 浏览数: 50次
  • 字数: 12018
  • 发表评论
粗糙集理论作为一种数据分析处理理论,在1982年由波兰科学家Z.Pawlak创立。最开始由于语言的问题,该理论创立之初只有东欧国家的一些学者研究和应用它,后来才受到国际上数学界和计算机界的重视。1991年,Pawlak出版了《粗糙集—关于数据推理的理论》这本专著,从此粗糙集理论及其应用的研究进入了一个新的阶段,1992年关于粗糙集理论的第一届国际学术会议在波兰召开。1995年ACM将粗糙集理论列为新兴的计算机科学的研究课题。

1 发展历史

粗糙集理论作为智能计算的科学研究,无论是在理论方面还是在应用实践方面都取得了很大的进展,展示了它光明的前景。粗集理论不仅为信息科学和认知科学提供了新的科学逻辑和研究方法,而且为智能信息处理提供了有效的处理技术。1982年,以波兰数学家Pawlak为代表的研究者首次提出了粗糙集理论,并于1991年出版第一本关于粗糙集的专著,接着1992年Slowinski R 主编论文集的出版,推动了国际上对粗糙集理论与应用的深入研究。1992年在波兰Kiekrz召开了第一届国际粗糙集合研讨会。这次会议着重讨论了集合近似定义的基本思想及其应用和粗糙集合环境下的机器学习基础研究,从此每年都会召开一次以粗糙集理论为主题的国际研讨会,从而推动了粗糙集理论的拓展和应用。我国RS研究起步较晚,所能搜索到的最早发表的论文时间是1990年,直到1998年由曾黄麟教授编著了国内最早的RS专著。粗糙集理论已成为国内外人工智能领域中一个较新的学术热点,引起了越来越多科研人员的关注。

2 理论及核心

理论简介

面对日益增长的数据库,人们将如何从这些浩瀚的数据中找出有用的知识?我们如何将所学到的知识去粗取精?什么是对事物的粗线条描述什么是细线条描述?

粗糙集合论回答了上面的这些问题。要想了解粗糙集合论的思想,我们先要了解一下什么叫做知识?假设有8个积木构成了一个集合A,我们记: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中集合的并。

下面考虑近似这个概念。假设给定了一个A上的子集合X={x2,x5,x7},那么用我们的知识库中的知识应该怎样描述它呢?红色的三角?****的大圆?都不是,无论是单属性知识还是由几个知识进行交、并运算合成的知识,都不能得到这个新的集合X,于是 我们只好用我们已有的知识去近似它。也就是在所有的现有知识里面找出跟他最像的两个一个作为下近似,一个作为上近似。于是我们选择了“蓝色的大方块或者蓝色的小圆形”这个概念:{x5,x7}作为X的下近似。选择“三角形或者蓝色的”{x1,x2,x5,x7,x8}作为它的上近似,值得注意的是,下近似集是在那些所有的包含于X的知识库中的集合中求并得到的,而上近似则是将那些包含X的知识库中的集合求交得到的。一般的,我们可以用下面的图来表示上、下近似的概念。

这其中曲线围的区域是X的区域,蓝色的内部方框是内部参考消息,是下近似 ,绿的是边界加上蓝色的部分就是上近似集。其中各个小方块可以被看成是论域上的知识系统所构成的所有划分。

核心

整个粗集理论的核心就是上面说的有关知识、集合的划分、近似集合等等概念。下面我们讨论一下关于粗糙集在数据库中数据挖掘的应用问题。考虑一个数据库中的二维表如下:

元素 颜色 形状 大小 稳定性

x1 红 三角 大 稳定

x2 红 三角 大 稳定

x3 黄 圆 小 不稳定

x4 黄 圆 小 不稳定

x5 蓝 方块 大 稳定

x6 红 圆 中 不稳定

x7 蓝 圆 小 不稳定

x8 蓝 方块 中 不稳定

可以看出,这个表就是上面的那个例子的二维表格体现,而最后一列是我们的决策属性,也就是说评价什么样的积木稳定。这个表中的每一行表示了类似这样的信息:红色的大三角积木稳定,****的小圆形不稳定等等。我们可以把所有的记录看成是论域A={x1,x2,x3,x4,x5,x6,x7,x8},任意一个列表示一个属性构成了对论域的元素上的一个划分,在划分的每一个类中都具有相同的属性。而属性可以分成两大类,一类叫做条件属性:颜色、形状、大小都是,另一类叫做决策属性:最后一列的是否稳定?下面我们考虑,对于决策属性来说是否所有的条件属性都是有用的呢?考虑所有决策属性是“稳定”的集合{x1,x2,x5},它在知识系统A/R中的上下近似都是{x1,x2,x5}本身,“不稳定”的集合{x3,x4,x6,x7,x8},在知识系统A/R中的上下近似也都是{x3,x4,x6,x7,x8}它本身。说明该知识库能够对这个概念进行很好的描述。下面考虑是否所有的基本知识:颜色、形状、大小都是必要的?如果我们把这个集合在知识系统中去掉颜色这个基本知识,那么知识系统变成A/(R-R1)={{x1,x2},{x3,x4,x7},,,}以及这些子集的并集。如果用这个新的知识系统表达“稳定”概念得到上下近似仍旧都是:{x1,x2,x5},“不稳定”概念的上下近似也还是{x3,x4,x6,x7,x8},由此看出去掉颜色属性我们表达稳定性的知识不会有变化,所以说颜色属性是多余的可以删除。如果再考虑是否能去掉大小属性呢?这个时候知识系统就变为:

A/(R-R1-R3)=A/R2={{x1,x2},{x5,x8},{x3,x4,x6,x7}}。同样考虑“稳定”在知识系统A/R2中的上下近似分别为:{x1,x2,x5,x8}和{x1,x2},已经和原来知识系统中的上下近似不一样了,同样考虑“不稳定”的近似表示也变化了,所以删除属性“大小”是对知识表示有影响的故而不能去掉。同样的讨论对于“形状”属性,“形状”属性是不能去掉的。A/(R-R2)={{x1,x2},x6,{x3,x4},x5,x7,x8},通过求并可以得知“稳定”的下近似和上近似都是{x1,x2,x5},“不稳定”的上下近似都是{x3,x4,x6,x7,x8}。最后我们得到化简后的知识库R2,R3,从而能得到下面的决策规则:大三角->稳定,大方块->稳定,小圆->不稳定,中圆->不稳定,中方块->不稳定,利用粗集的理论还可以对这些规则进一步化简得到:大->稳定,圆->不稳定,中方块->不稳定。这就是上面这个数据表所包含的真正有用的知识,而这些知识都是从数据库有粗糙集方法自动学习得到的。因此,粗糙集是数据库中数据挖掘的有效方法。

从上面这个例子中我们不难看出,实际上我们只要把这个数据库输入进粗糙集运算系统,而不用提供任何先验的知识,粗糙集算法就能自动学习出知识来,这正是它能够广泛应用的根源所在。而在模糊集、可拓集等集合论中我们还要事先给定隶属函数。

进入网络信息时代,随着计算机技术和网络技术的飞速发展,使得各个行业领域的信息急剧增加,如何从大量的、杂乱无章的数据中发现潜在的、有价值的、简洁的知识呢?数据挖掘(Data Mining)和知识发现(KDD)技术应运而生。

3 主要优势

粗糙集理论作为一种处理不精确(imprecise)、不一致(inconsistent)、不完整(incomplete)等各种不完备的信息有效的工具,一方面得益于他的数学基础成熟、不需要先验知识;另一方面在于它的易用性。由于粗糙集理论创建的目的和研究的出发点就是直接对数据进行分析和推理,从中发现隐含的知识,揭示潜在的规律,因此是一种天然的数据挖掘或者知识发现方法,它与基于概率论的数据挖掘方法、基于模糊理论的数据挖掘方法和基于证据理论的数据挖掘方法等其他处理不确定性问题理论的方法相比较,最显著的区别是它不需要提供问题所需处理的数据集合之外的任何先验知识,而且与处理其他不确定性问题的理论有很强的互补性(特别是模糊理论)。

4 研究方向

理论

①利用抽象代数来研究粗糙集代数空间这种特殊的代数结构。②利用拓扑学描述粗糙空间。③还有就是研究粗糙集理论和其他软计算方法或者人工智能的方法相接合,例如和模糊理论、神经网络、支持向量机、遗传算法等。④针对经典粗糙集理论框架的局限性,拓宽粗糙集理论的框架,将建立在等价关系的经典粗糙集理论拓展到相似关系甚至一般关系上的粗糙集理论。

应用领域

粗糙集理论在许多领域得到了应用,①临床医疗诊断;②电力系统和其他工业过程故障诊断;③预测与控制;④模式识别与分类;⑤机器学习和数据挖掘; ⑥图像处理;⑦其他。

算法

一方面研究了粗糙集理论属性约简算法和规则提取启发式算法,例如基于属性重要性、基于信息度量的启发式算法,另一方面研究和其他智能算法的结合,比如:和神经网络的结合,利用粗糙集理论进行数据预处理,以提高神经网络收敛速度;和支持向量机SVM结合;和遗传算法结合;特别是和模糊理论结合,取得许多丰硕的成果,粗糙理论理论和模糊理论虽然两者都是描述集合的不确定性的理论,但是模糊理论侧重的是描述集合内部元素的不确定性,而粗糙集理论侧重描述的是集合之间的不确定性,两者互不矛盾,互补性很强,是当前国内外研究的一个热点之一。

我来评分 :6
0

转载注明:转自5lulu技术库

本站遵循:署名-非商业性使用-禁止演绎 3.0 共享协议