粗糙集理论与应用发展

1、粗糙集理论与应用发展1、引言粗糙集(roughs ets,RS理论是20世纪80年代初由波兰科学家Pawlak提出的。其 主思想就是在保持分类能力不变的前提下，通过知识约简，导出概念的分类规贝U。 它从一个新的角度将知识定义为对论域的划分能力，并将其引入数学中的等价关系 来进行讨论，从而为数据分析，特别是不精确、不完整数据分析提供了一套新的 数学方法。同时，粗糙集理论具有无需提供除问题所需处理的数据集合之外的任何 先验信息，仅根据观测数据删除冗余信息，比较不完整知识的程度一粗糙度、属性 间的依赖性与重要性，抽取分类规则等的能力。近几年，这个理论已得到空前的发 展，无论在理论本身研究方面，还是在

2、理论应用方面都取得了令人瞩目的成果。2、粗糙集理论简介粗糙集理论是建立在分类机制的基础之上的，不可区分关系的概念是粗糙集理 论的基础。信息系统S由论域U和等价关系集A构成，表示成S=(U,A)，不可区分 关系ind(A)是信息系统S上的一个等价关系，它是A上全部等价关系的交集。信息 系统S所表示的知识可理解为*对论域U划分的结果。不可区分关系的等价类构成了 信息系统表示的知识的最小粒度，这个粒度内的对象不可区分。正是由于知识的 粒度性，造成使用已有知识不能精确地表示某些概念。为此，在 不可区分关系基础 上定义了上下近似，使粗糙集理论能够有效地逼近这些概念。令XCU是论域上对象 的一个集合，BC

3、A是一族等价关系，CXIs表示元素x在B下的等价类，则B( X )二 (xEUCxls(=X)B( X)二 XEUCx7B(1 X =t -0分别称为X的相对于B的下近似和上近似。如果上近似与下近似相同，则称X是 可定义 的，也称作精确集；否则，称为粗糙集。在粗 糙 集 理论中，消去冗余知 识，进行 知识简化的基本工作是利用两个基本概念：约简和核来进行的。令A为一等价关系集，且aEA当ind (A)=ind(A-a) 时，称a为A中不必要的；否则称 a为A中必要的。若每一个aEA都为A中必要的，则称A是独立的。设BCA若B是 独立的，且ind( B)= ind(A)，则称B为A的一个约简。A中

4、所有必要关系的集合，称 为A的核。3粗糙集的扩展模型对于Pa wlak提出的经典的粗糙集理论，由于它没有考虑到数 据噪音、数据缺失等情况，并且经典的粗糙集理论所涉及的概念和知识都是清晰的， 不能对论域U上的一个模糊集合进行描述，因此许多研究者对经典的粗糙集理论进行 了扩展，以使其应用的范围更加广泛。对一些著名扩展模型性质的研究正日益引起 学术界的关注，下面简要介绍几个著名的扩展模型：可变精度粗糙集模型(VPRS)可变精度粗糙集模型能够解决属性间无函数或不确定关系的数据分类问题，它 对经典粗糙集理论的主要扩充体现在它允许一定的误分类率9(018镇0-5)，定义户 多数包含关系为：若把集合X中的元

5、素分类到集合丫中，则会犯分类错误的可能性 小于夕。VPRS莫型和经典粗糙集是兼容的，只要令a二0,就和经典模型一致了。 随着a增大变精度粗糙集的近似边界区域变窄，即变精度粗糙集意义下的不确定区 域变小。因此，变精度粗糙集对数据不一致性有一定的容忍度，在某些场合可以增 强产生规则的鲁棒性，提高预测精度2 , Katzberg和Ziarko进一步提出了不对称边 界的VPRS莫型，即在上下近似的定义中的R可以是不相同的，从而使此模型更加 一般化3】相似莫型在经典的粗糙集莫型中，当数据中存在缺失的属性值的时候，不可区分关系或者 说是等价关系无法应付这种情形。为扩展粗糙集的处理能力，可以使用相似关系代

6、替粗糙集合中的不可区分关系。S 二(U, A T)是信息系统，令ACA T,在文4中定义的相似关系为 SI M (A )=(x,y)EUXU!V a E A , a( x) = a( y)or a ( x)= or a ( y )“，相似类一般不再构成U的划分，它们之间可能是相互重叠的，它们构成U的覆盖。由于相似类中的元素不一定属于同一决策 类，因此在相似关系的基础上定义了相对吸收集的概念，相对吸收集中的任意两个 元素都相似且具有同样的决策值；相对吸收集可以用来进行数据削减。莫糊粗糙集莫型在人们的实际生活中，涉及到的知识或概念往往是莫糊的不确定的，为了获得 对莫糊概念更好的近似表示，D.D u

7、dious和H.Prade提出了莫糊粗糙集的 莫型5】。 用类似经典粗糙集的方式对莫糊粗糙集的基本概念进行了定义，一个莫糊集合的下近 似和上近似为一对莫糊集合，它们的隶属函数分别表示论域中的对象肯定隶属于这 个莫糊集合的程度和可能隶属于这个莫糊集合的程度。Alpha粗糙集理论(a-RST)a粗糙集理论是将经典的粗糙集理论扩展成带有模糊性质的新理论。它表现了 a粗糙集的模糊的非空边界，并以带参数的不可区分关系为基础对粗糙集理 论 中的信息系统、依赖、可定义性、近似性、核等概念进行了推广，以此来对模糊概念 进行逼近。4与其他不确定理论的比较研究粗糙集理论在处理不确定性和模糊性方面具有很多 优点，例

8、如粗糙集理论在 处理大数据量，消除冗余信息等方面，有着良好的效果； 它仅利用数据本身提供的信息，无需任何先验知识，对问题的不确定性的描述或处理 更客观；粗糙集理论可以产生简洁准确、易于验证的规则知识等.但是，粗糙集本身特点又决定它在一 些问题的处理方面存在着不足，而一些其它的不确定理论也有着各自的优 点，这使得 粗糙集理论与其他不确定理论的互补性研究成为必然。目前对粗糙集 理论与模糊理 论及证据论的关系和互补性研究已经取得丰硕的成果，下面加以简要介绍。粗糙集以集合中元素的不可区分关系为基础，体现的是由于知识的粒度性而导 致的粗糙性，强调数据的不可区分，研究的是不同类中的对象组成的集合之间的关

9、系，重在分类；而模糊集是基于元素对集合隶属程度的不同，注重描述信息的含糊程 度，研究的是属于同一类的不同对象的隶属的关系，重在隶属的程度，强调集合本身 的含混性7】。它们处理的是两种不同的模糊和不确定性，分别刻画了不完备信息的 两个方面。因此两种方法相互补充可能可以更有效地处理不完全知识。粗糙集与Dempster-Shafter的证据理论之间有很多相似之处。二者的主要区别 在于Dempster-Shafter理论利用信度函数作为主要工具，而粗糙集理论主要利用上 近似集合和下近似集合1.D .D udious和H.P rade同时指 出，Dempster-Shafter 的证据理论和Z.Pa w

10、lak的粗糙集理论是不同术语下的同一个模型8。A.Sk owron和J.G razymala-Busse甚至指出，粗糙集理论可以看 作 是证据理论的基础，并在粗糙集理论的框架上重新解释了证据理论的基本概念，特别 是用上近似和下近似的术语解释了信念(belief)和似然(plausibility)函数，进而讨论了 二者之间的互补问题95粗糙集理论与其它方法的融合目前，粗糙集理论已成为信息科学最为活跃的研究领域之一，被广泛应用 于数 据挖掘、机器学习、决策支持系统和模式识别等众多领域。同时，该理论还 在医学、 化学、材料学、地理学、管理科学和金融等其他学科得到了成功的应用。在粗糙集理论的应用研究中

11、，将粗糙集理论与其它方法相融合的研究是当前 的一个研究热点。下面对粗糙集理论与神经网络、遗传算法、模糊逻辑、SVM方法 的融合加以简单介绍。神经网络具有分类精度高，鲁棒性强等优点，可以很好地弥补粗糙集理论对 错误描述的确定性机制过于简单，当数据中存在噪声时，其结果往往不稳定，精度 不高等缺点。文10叼讨论了将粗糙集理论和神经网络有效结合的方法，使用粗糙 集理论对输入到神经网络的数据进行属性约简和属性值约简，使得网络的学习速度大 大加快，分类精度显著提高。遗传算法具有全局搜索，自适应演化的优点，可被应用在粗糙集理论的很多 方面，例如用来求取连续属性值的最优量化区间个数及各个区间分点值，利用它计

12、算粗糙集的属性约简等。Lingras和Davies提出了一种粗糙遗传算法，该算法 用一对粗糙数来表示基因，给出了相应的适应度函数，并对交叉、变异等 操作进行 了定义。另外，遗传算法也被应用在粗糙集的推理过程中，例如著名的粗糙集系统 LERS 系统就采用了遗传算法的 BBA (Buckerbrigade algorithm)过程1617将粗糙集理论和模糊逻辑相结合是很自然的，比如利用模糊的概念对决策表中 的连续属性进行模糊化，将不可区分关系扩展成模糊相似关系及相应的扩展上 下近似 的概念，或者利用模糊推理进行决策以提高鲁棒性等12,13。文14建立了基于模糊 优势关系的上下累积模糊集合的粗糙近似

13、，利用模糊优势关系来代替不可区分关系， 这正是基于模糊逻辑与粗糙集理论融合的思想。经典的SVM算法是建立在二次规划基础之上，对于处理大数据量的模式分类问 题存在很多困难。文15中提出将粗糙集方法与SVM算法结合，禾U用粗糙集 理 论在处理大数据量、消除冗余信息等方面的优势，减少SVM训练数据，提高它的数据处理的实时性，缩短训练样本的时间；同时，借助SVM良好的分类性能， 对约简后的属性子集进行分类，具有快速、高识别率和抗干扰性强等优点。6、粗糙集 理论研究中存在的问题粗糙集理论是一种有效分析和处理不精确、不一致、不完整等各种不完备信 息 的工具。虽然目前在有关粗糙集理论及其相关的研究中取得了一

14、些令人瞩目的成果， 但是仍然存在一些至今还没有很好解决的问题。在粗糙集理论中，对错误判断的决定性机制非常简单。因此，由粗糙集产生 的决策规则很不稳定而且有较差的分类精确性18。因此为得到精确的决策规则U，必 须把粗糙集理论和其他数据挖掘方法结合起来。常用的方法是把粗糙集和神经网络及 模糊集等软计算方法结合应用。约简的有效计算问题，如何处理数据中的噪音和丢失值问题，连续属性离散 化等。虽然目前在这些方面已经有了一些初步的研究，但是到目前为止还没 有找到 真正令人满意的方法19粗糙集理论所处理的分类必须是完全正确或肯定的，因而它的分类是精确 的，亦即只考虑完全/包含0与/不包含0，而没有某种程度上

15、的/包含0与/属于 0；另一个方面它所处理的对象是已知的，且从模型中得到的结论仅适用于这 些对象。 但在实际应用中，往往需要把从小规模对象集中得到的结论应用于大规 模对象集上 去。因此，这些局限性限制了粗糙集在实际中的应用20。结语 粗糙集理论经过2。多年的发展，正日益受到重视且日趋完善，它为 处理 不确定信息提供了强有力的分析手段，并己得到广泛的应用。本文重点介绍了当前 粗糙集理论及应用的研究进展情况，可以看出对这个年轻并高速发展的学科来说， 还有非常广阔的空“值得我“，继续去研究探索。参考文献PawlakZ .R oughs ets.In ternationalJ ournalo fl n

16、formationa ndComputerS cie nce,19 82,11(5):342-356ZiarkoW .V ariableP recisionR oughS etM odel.Jo urnalo fC omputerandS ystem Scie nces,19 93s46:39a-59Katzberg J D. Ziarko W. Variable Precision Rough Sets with As ym m etricb ounds.I n:Z iarko W P,ed .P roc.o fR SKD93.Sp rin ge r-Verlag,1994.16 7A-17

17、74 KryszkiewiczM .R oughs eta pproacht oi ncompletei nformationsys te ms .in formations ciences,19 98, 112:39A-495 Dubois D,P rade H.R ough fuzzy sets and fuzzy roughset s. In ternationalJ ournalo fG eneralS ystems， 1990,17:191-209Quafafou M.a- RST: a generalization of rough set t heory.ln fo rmatio

18、nS ciences,20 00,124(4):301A-316DuboisD .PradeH .Pu ttingR oughS etsa ndF uzzyS etsT ogether.ln : S lowinskiR .In telligentD ecisionS upport:H andbooko fAp pl ica tionsa ndA dvanceso fth eR oughS etT heory.D ordrecht:Kl uw e rA cademicP ublishers,1 992.2 03.232YaoY Y .LingrasP .In terpretationo fb e

19、lieffu nctionsin t het heoryo fr oughs ets.In formationS ciences,19 98,104:81-106SkowronA ,Grgymala-BusseJ W .F rom roughs etth eoryt oe vidence t heory.In :A dvancesi ntheD empsterS haferT heoryo fEv ide nc e.N ew York:J ohnW iley$ ,.So nsI nc.,1 994-19 3A-236JelonekJ ,et a l.R oughS etR eductiono

20、fA ttributesa ndT heirDo ma ni ns for Neural Networks.Computational Intelligence,19 95 .1 1(2)LingrasP ,D aviesC .R oughG enetica lgorithms.In :Z hongN ,Sk ow ro n A eds.P roc.7 th Intl.W ksp on RSFD,S pringer,19 99 . 3 8A-46Chakrabarty K,B iswas R,N anda S.F uzziness in roughset s. F u zzyS etsa ndS ystems,2000,110(2):247-251FernandezS alidoJ M ,MurakamiS .R oughs eta nalysiso fa g eneralt yp eo ffu zzyd atau singt ransitivea ggregationso ffu zzys imilarit yr elations.F uzzyS etsa ndS ystems,2 003,1 39( 3):635 66 0LiuY unxiang,