清华大学学报(自然科学版) 2001年第41卷第1期
CN 1122223 N . 41, N o . 1J T singhua U niv (Sci &Tech ) , 2001, V o l 17 32
6468
粗糙集理论及其应用进展
胡可云, 陆玉昌, 石纯一
(清华大学计算机科学与技术系, 北京100084)
摘 要:粗糙集理论是一种新型的处理模糊和不确定知识的数学工具。目前已在人工智能、知识与数据发现、模式识别与分类、故障检测等方面得到了广泛应用。首先描述了粗糙集的基本算法及其复杂度, 包括等价关系, 上下近似及各种约简算法; 接着对粗糙集扩展理论, 如可变精度模型, 相似模型等进行了讨论, 然后对粗糙集在数据挖掘、大数据集、粗糙逻辑、多方法融合等领域中的应用进展情况进行了论述, 最后给出了建议的研究方向。
关键词:粗糙集; 知识发现; 中图分类号:T 文章编号:([1**********]205
:是造成使用已有知识不能精确地表示某些概念的原
因。通过引入不可区分关系作为粗糙集理论的基础, 并在此基础上定义了上下近似等概念, 粗糙集理论能够有效地逼近这些概念。
。, , 只和已知数据。
。粗糙集理论将知识定义为不可区分关系的一个族集, 这使得知识具有了一种清晰的数学意义, 并可使用数学方法进行处理。粗糙集理论能够分析隐藏在数据中的事实而不需要关于数据的任何附加信息。
但是, 在粗糙集合应用于实际系统时, 仍然存在一些实际问题。例如约简的有效计算问题, 如何处理数据中的噪音和丢失值问题。为解决上述问题, 有许多工作集中在寻求有效的约简算法和对经典粗糙集理论的扩展上。
Advances i n rough set theory
and its appli a tion s
H U Ke yun , LU Yucha ng , S HI Chunyi
(D epartm ent of Computer Science and T echno logy, T singhua U niversity, Beijing 100084, China )
Abstract :Rough set theo ry, a new m athem atical too l dealing w ith vagueness and uncertainty, w as introduced by Paw lak in 1982. It has been w idely used in the area of A I, data m ining, pattern recogniti on, fault diagno sitics, etc . T his paper describes the basic algo rithm s fo r rough set theo ry, including equivalent relati on, upper low er app roxi m ati on and reducti on . T hen several extensi ons of rough set theo ry are discussed such as V PR S, si m ilarity based model, and app licati ons of rough set theo ry in areas like data m ining, rough logic, etc . Further research directi ons are then discussed .
Key words :rough set; know ledge discovery; data analysis
1 基本算法及其复杂度
1. 1 求等价关系
求等价关系的的最坏复杂度为O ( A U 2) 。其中A 为属性集合。 O 为对象集合。这是因为在最坏情况下需要扫描对象集合两次。每个对象一次, 每个对象的等价类一次。一个改进的算法是首先按给定属性集对对象排序, 然后扫描一遍即可。这样它的复杂度就降低到O ( A U lg U ) 。1. 2 上下近似
粗糙集(rough set ) 理论是一种新型的处理模糊和不确定知识的数学工具。目前已经在人工智能、知识与数据发现、模式识别与分类、故障检测等方面得到了较为成功的应用。
粗糙集理论具有一些独特的观点。这些观点使得粗糙集特别适合于进行数据分析。如:
知识的粒度性。粗糙集理论认为知识的粒度性
如果已经给定条件属性和决策属性的等价类
收稿日期:1999212221
基金项目:国家自然科学基金资助项目(79990580) ; 国家“九七三”
基础研究项目(G 1998030414)
作者简介:胡可云(19702) , 男(汉) , 湖北, 博士研究生。
胡可云, 等:
粗糙集理论及其应用进展65
(或划分) , 求某个集合的上下近似是直接了当的事
情。只需测试该集合在条件属性下的等价类是否包含或部分包含在决策属性下的等价类中即可。等价类的个数在最坏的情况下等于 U 。因此在已给定划分(等价类) 下求上下近似的复杂度为O ( U ) 。这样整个的复杂度最坏在O ( A U lg U ) 。Chan 给出一种在属性增减时上下近似的更新方法[1]。作者指出该方法的一种可能的应用是动态属性泛化。该方法使得更新后的上下近似可以用原属性集合的上下近似, 原属性集合的边界, 新增单个属性的上下近似, 新增单个属性的边界来表示。这使得增加一个属性时, 上下近似的更新只需计算单个属性的上下近似即可。
1. 3 属性重要性及核
该属性是否会改变该集合的对决策属性依赖度。如
果不影响, 则将其删除。此算法的最坏复杂度在O ( A 2 U lg U ) 。因为循环的执行次数最多为 A , 而求属性间的依赖程度的复杂度和计算正区域相同。
算法3(遗传算法) 已经有不少用遗传算法计算约简的算法。各种算法的不同之处主要在表示和适值函数的不同。这里介绍具有代表性的B jo rvand 和Kom o row sk i 提出的遗传算法[3]。表示:每个位串代表区分矩阵的一项, 即两个对象的区分属性集。某位为1时表示该属性存在, 否则不存在。这样每个位串是一个约简的候选。定义适值函数如下
F (v ) =
n
+
,
(m -m ) 2
2
属性的重要性在于去掉该属性后正区域的变化大小。其时间复杂度的主要取决于正区域。因此计度相同。若。因
O ( X A U lg U ) 。其中核X 是条件属性的子集。1. 4 约简
其中:N 是属性集合的长度, v 是v 中1的个数。C v v 。m 是对象的个数L 。在设计初始种群时, 可以考虑将核或专家认为必要的属性加入种群中, 以加快算法的收敛。
算法4(复合系统的约简) K ryszk iew icz 和R yb in sk i 研究了在复合信息系统中寻求约简的问
题。即怎样利用现有的子系统的约简求复合系统的约简[4]。其主要思想是将布尔函数的化简问题转化成集合空间中的边界搜索问题。而在已知子系统的约简的情况下, 复合系统的搜索空间将得到简化。设有信息系统S 1, S 2。它们的属性集合相同。设f 1和f 2分别是它们的区分函数。则整个信息系统S 的区分函数f 可表示为f =f 1∧f 2∧f 12。其中f 12代表
S 1, S 2中的对象分别作为纵横坐标组成的区分函
约简是粗糙集用于数据分析的重要概念。然而最小约简的计算是N P 2hard 的。因此运用启发信息来简化计算是必要的。事实上, 计算最小约简的问题有些类似于机器学习中的最小属性子集问题。如前所述粗糙集中的约简计算可以转化成布尔函数化简问题。因此可以使用许多布尔函数化简中的技巧及算法。有许多作者讨论了计算约简的问题。这里我们介绍一些典型算法。
算法1(基本算法) 基本算法首先构造区分矩阵。在区分矩阵的基础上得出区分函数。然后应用吸收律对区分函数进行化简, 使之成为析取范式。则每个主蕴含式均为约简。基本算法可以求出所有的约简, 但是只适合于非常小的数据集。基本算法的时间复杂度为O (2 X A U lg U ) 。
算法2(属性的重要性) 由H u 提出[2]。该算法非常简单和直观。它使用核作为计算约简的出发点。计算一个最好的或者用户指定的最小约简。算法将属性的重要性作为启发规则。首先按照属性的重要程度从大到小逐个加入属性, 直至该集合是一个约简为止。接着检查该集合中的每个属性, 看移走
数。根据上面的讨论, 如果我们已知S 1和S 2的约简
时, 则S 的约简只需在空间[M I N S (f 1∧f 2) , {A }]上搜索而不必从头开始。其中M I N S (f 1∧f 2) 是两个子系统的约简的并的最小值。因而搜索空间大大减小。
算法5(扩展法则) Starzyk , N elson 和Stu rtz 提出一种新概念, 称为强等价(strong equ ivalence ) , 进而发展为扩展法则, 用于快速简化
区分函数[5]。两个属性称为局部强等价, 若它们在区分函数的所有项中同时出现或不出现。当两个属性是局部强等价时, 它们就可以仅用一个属性代替。实验表明该算法比基本算法快数十到数百倍。因而能处理更大的数据集。
算法6(动态约简) 动态约简在某种意义上是
66
清华大学学
报(自然科学版) 2001, 41(1)
给定决策表中最稳定的约简, 它们是在从给定决策表中随机抽样形成的子表中最常出现的约简。动态约简能够有效的增强约简的抗噪音能力[6]。动态约简的计算过程较为简明, 主要是对决策表进行采样, 然后对采样后的决策表计算所有约简。在所有的子表中保持不变或近似保持不变的约简就是动态约简。
型能够保持绝大多数经典模型的良好性质。这为它的广泛应用打下了基础。
Katzberg 和Ziarko 进一步提出了不对称边界的V PR S 模型, 即在上下近似的定义中的Β可以是不相同的。从而使此模型更加一般化[8]。2. 2 相似模型
2 扩展模型
粗糙集理论应用于数据分析时, 会遇到噪音、数据缺失、大数据量等一系列经典理论解决不够理想的问题。因此在近几年的研究中, 出现了许多粗糙集的扩展模型。其中典型的有可变精度粗糙集模型, 相似模型等。
2. 1 可变精度模型(VPRS )
经典粗糙集模型的基础——不可区分关系——
是很强的。在数据中存在缺失的属性值的时候(在数据库中很普遍) , 不可区分关系或者说是等价关系无法应付这种情形。为扩展粗糙集的能力, 有许多作者提出了用相似关系来代替不可区分关系作为粗糙集的基础[9]。
在使用相似关系代替粗糙集合中的不可区分关系后, 的划分了。类似于等价类, x 在属性集合I S I M B (x ) 。因此还需定义相似决策类, 即相似集对应的决策类集合。
由于相似集的元素并不一定属于同一个决策类, 为此定义相对吸收集。子集Y ΑU 称为相对吸收集, 如果对于每个x ∈U , 存在y ∈Y 与之相似, 并且具有同样的决策值。显然相对吸收集可以用来进行数据削减。利用相似集可以很容易地定义正区域的概念。它就是所有包含在决策类中的相似集的并。依赖度和约简的概念都可以类似经典集合的方式定义。
实践证明, 相似模型在实践使用中具有比经典粗糙集模型更好的性能。在解决数据库中缺少值的情况时, 一个简单的相似关系可以定义为(其中3代表不知道或不关心) :
ΣC (x , y ) ={x ∈U , y ∈U Πa ∈C , a (x ) =a (y ) o r a (x ) =3o r a (y ) =3}.
在数据集中存在噪音等干扰情况下, 经典理论会由于对数据的过拟合而使其对新对象的预测能力大为降低。而在实际应用中, , 种可变精度[7], V PR S 率。为此, 引进一个精度Β(0≤Β≤0. 5) 。定义Β2多
数包含关系为:若把集合X 中的元素分类到集合Y 中, 则会犯分类错误的可能性小于Β。显然, 若Β=0, 则Β2多数包含关系就退化成标准的包含关系。这
样就可以用Β2多数包含关系来解释粗糙集中的上下近似。
集合X 的下近似可解释为那些U 中的元素分类到X 中分类错误率不大于Β的等价类集合。X
ϖΒX 包含所有U 中不可能在误分类率的Β2上近似R
小于Β之下分类到2X 中的所有元素。
根据经典粗糙集同样的方式, 利用集合的下近
似, 可以定义属性的Β2近似依赖。粗糙依赖量度是精确分类, 即对对象的无错误分类的综合能力的评价, 而近似依赖量度是度量分类错误率在预先给定的可容忍极限Β之内的分类能力。近似分类与粗糙分类相反, 不能解释为属性的函数或部分函数依赖。近似依赖的性质弱于函数依赖的性质, 例如传递性就不再成立。
根据扩展的近似依赖的定义, Β2约简或称近似约简可以定义为在近似依赖度不变的前提下的最小子集。因为只要V PR S 模型是和经典粗糙集兼容的。
令Β=0, 那么就和经典模型一致了。因此V PR S 模
3 应 用
可以说, 粗糙集理论由于其在数据挖掘方面的应用而受到广泛的关注。最近几年, 粗糙集理论的应用研究得到了长足发展。这里从几个方面简述相关的应用。由于在粗糙集的文献非常多, 我们仅列举其中极少数代表性应用。
数据缩减与规则生成。Kohavi 和F rasca 等用实验证明, 数据库中最有用的子集并不一定是粗糙集中的相对核, 甚至可能不包括完全的核属性集[10]。N ing Shan 则讨论了基于R S 的从数据中发
胡可云, 等: 粗糙集理论及其应用进展67
现规则的增量自适应算法[11]。提出了一种找到最大泛化的规则和约简的算法和规则与缩减的增量算法。Grzym ala 2B u sse 和Zoub i 比较了同时使用可能规则及确定规则和只使用确定规则的性能, 发现前者产生较小的错误率[12]。Choubey 和D eougun 等的研究得出了同样的结论。他们还在属性选择的题目下研究了近似约简问题。并给出了几个启发式算法[13]。L enarcik 和P iasta 研究了在每个对象的Co st 不一样时的粗糙分类器。他们的主要方法是对所有的对象定义一个新的Co st 属性[14]。M o llestad T 和Kom o row sk i J 提出了在粗糙集框架下缺省规则生成的格搜索算法, 并给出一组启发式搜索策略。
大数据集。由于粗糙集在数据挖掘中具有较大的计算复杂度, 受关联规则挖掘算法的启发, 有些作者提出了将关联规则挖掘技巧应用于粗糙集的确定和可能规则生成中来, 以减小粗糙集方法的计算复杂度[16]。N guyen 和Skow ron 分解方法[17]) , , 不满足的为另一部分。将该过程递归进行, 直至决策表的大小满足要求为止。然后再对小决策表生成规则。当新对象到来时, 从顶部开始匹配, 直至叶子的规则。
多方法融合。Jelonek 等研究了将R S 理论用于神经网络训练数据的预处理, 主要进行了属性的缩减和属性值域的缩减, 上述处理有利于提高学习效率, 并且保持了较低的稳定的近似分类误分类差错率。H u 等人提出了一种将基于属性的归纳概念方法和R S 结合的方法[2], 首先使用面向属性的概念树爬升技术对属性进行泛化, 然后使用R S 方法计算缩减并生成规则。由于在泛化过程中消除了不必要的属性值和在缩减过程中去掉了不相关的属性, 最后的规则是很一般的形式并且可用高层次抽象概念表达。L ingras 和D avies 研究了粗糙集和遗传算法的集合, 提出了一种粗糙遗传算法[19]。在该算法中, 基因用粗糙数表示。
信息检索。B eaubouef 等在R S 理论基础上提出了一种Rough 关系数据库模型[20], 并定义了各种Rough 关系算子。该模型将R S 的重要性质引入到基本关系模型中, 从而使之具有更好的检索能力和适应性。在此模型中, 查询结果返回的是基于属性的Rough 关系, 它不仅包含一个查询的确定应答, 还
[18]
[15]
包含可能的应答, 例如上近似所包含的元组等。
粗糙逻辑。不少逻辑学家和理论计算机科学家试图通过R S 建立Rough 逻辑。Paw lak 等在CA C M 1995年11期上发表综述, 认为研究粗糙逻辑——基于R S 的不精确推理逻辑——是粗糙集应用研究中最重要的课题之一。L in 和L iu 等基于拓扑学观念定义了Rough 下近似算子L 和Rough 上近似算子H
[21]
, 这2个算子的语法性质分别与模态
逻辑中的必然算子(和可能算子◆十分相似, 因而带
L 和H 算子的逻辑公式被称为Rough 逻辑公式,
并且建立了与模态逻辑相似的公理化Rough 集的逻辑演绎系统和相平行的演绎规则。Yao 和L in 通过研究粗糙集和模态逻辑的关系, 提出并研究了一系列扩展粗糙集的性质[22], , 。它还。例如同类的商品我们认。为使经典粗糙集理论适用决策支持的要求, Greco , M atarazzo 和Slow in sk i 给出了扩展经典粗糙集的方法[23]。主要是采用一种和评价准则有关的支配关系(dom inance , 自反和传递的) 代替等价关系的方法。并提出以模糊属性评估方法代替粗糙集中的属性重要性方法。
原型系统。典型系统如KDD 2R , L ER S , RoughDA S&RoughCLASS , Ro setta , Rough
[24]
这些系统为了实际的需要, Enough , Grob ian 等。一般会对经典理论有所扩展。
其它方面的应用例子有字符识别, 医疗诊断, 市场预测等等。这些应用主要是利用粗糙集及其扩展方法进行规则获取后在具体领域的应用。这里我们不一一讨论。有兴趣的读者可参看有关文献。
4 结 语
粗糙集合以其独特的优势正在赢得越来越多的研究者关注, 并在各个应用领域获得了广泛的应用。然而这仍是一个极其年轻并在高速发展的学科。下面从数据库知识发现角度列举一些可能的研究方向及应用领域。这些方向实际上是相互关联的。
高效约简算法。高效的约简算法是粗糙集应用于知识发现的基础。现尚不存在一种非常有效的方法。因此寻求快速的约简算法及其增量版本仍然是主要研究方向之一。
大数据集问题。现实中的数据库已经越来越大。
68
清华大学学报(自然科学版) 2001, 41(1)
粗糙集理论如何应付这一挑战仍旧是一个问题。虽然现在已经有一些有益的探索, 但是还没有找到一种令人满意的方法。可能的解决方案有采样、并行化等。需要发展相应的算法。
多方法融合。现在有许多种数据挖掘方法。实验表明, 还没有一种在所有的测试集上表现都比其它方法出色。因此多种方法的融合可能是进一步提高分类效能的方法之一。此外, 最近提出的comm ittee 学习方法在粗糙集方法上的应用也是有意义的课题之一。
参考文献 (References )
[1]Chan C C. A rough set app roach to attribute generalizati on in
data m ining [J]. Info rm ati on Sciences, 1998, 107:169176. [2]H u X. Know ledge D iscovery in D atabases:A n
A ttribute 2o riented Rough Set A pp roach [D]. U niversity of R egina, Canada, 1995. [3]B j o rvand A T. ‘Rough Enough ’2A system suppo rting Rough Sets A pp roach [EB OL ]. http:e . ～to rvill .
[4]K ryszk iew icz M R i in sed
info r m on s ]W P () . roceedings of R SKD ’93V erlag, 1994. 261273. [5]Starzyk J , N D E, Sturtz K . R educt generati on in
info r m ati on system [J]. Bulletin of Internati onal Rough Set Society, 1999. 3(1 2) :1922.
[6]Bazan J G, Skow ron A , Synak P. D ynam ic reducts as a too l
fo r extracting law s from decisi ons tables [A]. R as Z W , Zem ank iva M. M ethodo logies fo r Intelligent System s [C]. Berlin:Sp ringer 2V erlag, 1994. 346355.
[7]Ziarko W. V arable p recisi on rough set model [J]. Journal of
Computer and System Sciences, 1993. 46:3959.
[8]Katzberg J D , Ziarko W. V ariable p recisi on rough sets w ith
asymm etric bounds [A]. Ziarko W P. P roceedings of R SKD ’93[C]. Sp ringer 2V erlag, 1994. 167177.
[9]K ryszk iew icz M. Rough set app roach to incomp lete
info r m ati on system s [J]. Info rm ati on Sciences, 1998. 112:3949.
[10]Kohavi R , F rasca B. U serful feature subsets and rough set
reducts [A]. P roc on R SSC’94[C]. 1994.
[11]Shan N , Ziarko W. D ata 2based acquisiti on and increm ental
modificati on of classificati on rules [J]. Computati onal Intelligence, 1995. 11:357370. [12]Grzym ala 2Busse J W , Z OU X. C lassificati on strategies using
certain and po ssible rules [A]. P roc of 1st Conf on R SCTC [C]. Po land, 1998. 3744.
[13]Choubey S K, D eougun J S, R aghavan V V , et al . A
comparison of feature selecti on algo rithm in the context of rough classifiers [A]. 5th IEEE Int Conf Fuzzy System s [C]. N ew O rleans, 1996. 11221128.
[14]L enarcik A , P iasta Z . Rough classifiers sensitive to co sts
varying from object to object [A]. P roc of 1st Conf on R SCTC [C]. Po land, 1998. 222230.
[15]M o llestad T , Komo row sk i J. A rough set fram ewo rk fo r
m ining p ropo siti onal default rules [A]. Pal S K, Skow ron A eds . Rough Fuzzy H ybridizati on [C]. Sp ringer, 1999. 233262.
[16]L in T Y . Rough set theo ry in very large databases [A].
P roceedings of I M A CS M ulticonference [C]. vo lum e 2, L ille, Internati onal A ssociati on fo r M athem atics and Computers in Si m ulati on, 1996. 947.
[17]N S H , Skow P, et al . Know ledge
in roach [A]. P roc of ]. P rague, 209.
[]J K insk i R. Rough set reducti on of
their dom ains fo r neural netwo rks [J]. onal Intelligence, 1995. 11(2) :339347.
[19]L ingras P, D avies C. Rough Genetic algo rithm s [A]. Zhong
N , Skow ron A eds . P roc 7th Intl W k sp on R SFD [C]. Sp ringer, 1999. 3846.
[20]Beaubouef T , Petry F E. A rough set model fo r relati onal
databases [A]. Ziarko W P eds . P roc of R SFD ’93[C]. Sp ringer 2V erlag, 1994. 100107.
[21]L in T Y, L iu Q , Yao Y Y . L ogic system s fo r app roxi m ate
reasoning:via rough sets and topo logy [A]. R as Z W , Zem ank iva M eds . M ethodo logies fo r Intelligent System s [C]. Berlin:Sp ringer 2V erlag, 1994. 6574.
[22]Yao Y Y, L in T Y . Generalizati on of rough sets using modal
logics [J]. Intelligent A utom ati on and Soft Computing . 1996. 2(2) :103120.
[23]Greco S, M atarazzo B, Slow ink si R. Fuzzy m easure
technique fo r rough set analysis
[A]. 6th Euro Congress Intelligent T echniques&softComputing [C]. Germ any, 1998. 99103.
[24]Rough set based kdd System s[EB OL ]. h ttp: www.
kdnuggets . com , 1999.