（计算机软件与理论专业论文）基于粗糙集理论的动态约简研究.pdf

中南大学硕士学位论文摘要 摘要 本论文的研究工作，主要围绕着基于粗糙集理论的动态约简和 完成约简后决策规则的如何制定展开。涵盖了粗糙集理论的基本原 理、不同决策表抽样策略的分析、如何利用差别矩阵和差别函数对 决策表进行约简等内容。形成了较为完善的决策表动态约简理论和 技术方案。 针对不同决策表约简的特殊要求，分析了现有约简方法的优缺 点。通过引入动态约简的概念，用动态约简方法处理决策表相当于 在决策表约简前预先对决策表进行了抽样处理，提高了约简的精度。 并且动态约简挑选出各子决策表中相对稳定的约简作为最终结果， 这种处理方法也提高了决策规则的稳定性和描述能力。 在对不同决策表随机抽样方法的研究中，采用了两种新的抽样 策略，并详细阐述了此两种抽样策略的适用范围和具体优势。结合 概率抽样策略和差别矩阵构造出一个动态约简算法。 从制定决策规则的角度，比较了当前求取决策规则的一些方法， 并详细阐述了各方法的优缺点。详细介绍了两种根据决策表直接求 取决策规则的方法，以及如何由动态约简计算决策规则。最后建立 了一种决策规则的修正算法，完善了决策规则制定后的误差修正。 总结全文，粗糙集理论与方法对于处理复杂系统不失为一种较 为有效的手段，被广泛应用于数据挖掘( d m ) 和数据库知识发现 ( ) d ) 领域中。而动态约简及其由约简结果制定决策规则的方法更 能为以上两个领域提供高效、精确的数据保证。 关键词粗糙集，决策表，动态约简，决策规则 中陌大学硕士学位论文a b s t r a c t a b s t r a c t t h er e s e a r c ho ft l l i st h e s i si sm a i n l va b o u tt h ed v n a m i cr e d u c t b a s e do nf o u g hs e tt h e o r ya sw e l la sh o wt oe s t a b l i s ha n dd e v e l o pt h e d e c i s i o nr u l e sa f t e rc o m p l e t i n gt h er e d u c t t h i sp a p e ra l s oc o v e r st h e b a s i cp n c i p l eo fr o u 曲s e t ，t h ea n a l y s i so ft 1 1 es a m p l es 打a t e g yo n d i 矗、e r e n td e c i s i o nt a b l e sa n dh o wt om a k eu s eo ft h ed i s c e m i b i l i t v m a t r i xa n dd i s c e m i b i l i t vf h n c t i o nt od or e d u c t i o nw i t ht h e ( 1 e c i s i o nt a b i e t h u sar c l a t i v e l y p e r f c c tt l l e o r y a n d t e c h n i q u e s c h e m eo fd y n 砌i c i d u c to fm ed e c i s i o nt a b l ei sf b 彻e d a c c o r d i n g t o s p e c i f i cr e q u i r e m e n t o ft h er e d u c to fd i f 诧r e n t d e c i s i o nt a b l e s ，t h ec o n c e p to fd v n a m i cr e d u c ti si n t r o d u c e di nt h i s d i s s e r t a t i o n l r o u 曲a n a l y s i so nc u r r n tm e m o d o fr e d u c t u s i n g t h em e t h o do fd y n a m i cr e d u c tt od e a lw i t ht h ed e c i s i o nt a _ b l e ， i se q u a lt ota ：k es 锄p l ef r o mt h ed e c i s i o nt a b l ei na d v 卸c eb e f o f et h e r e d u c t i o no fd e c i s i o nt l b l e w h i c hi n c r e a s e sm ea c c u r a c vo fr e d u c t i o n a n dm er e l a t i v e l vs t a b l er e d u c ta r ec h o s e nf o me a c hd e c i s i o ns u b t a b l e a sm eu l t i m a t er e s u l t s ，w h i c ha l s oi n c r e a s e ss t a b i l i t ya n dd e s c r i p t i o n a b i l i t vo ft h ei 【e c i s i o nm l e s a tt h e a s p e c to fr a n d o m l yc h o o s eas a m p l et o w a r d s d i f f i e r e n t d e c i s i o nt a b l e s ，t h i sp a p e rp u t sf o n a r dt w ol ( i n d so fn e ws a m p l i n g s 仃a t e g y ，a n de x p a t i a t e st 1 1 e i ra p p l i c a t i o ns c o p ea i l dc o n c r e t ea d v a l l t a g e s c o m b i n i n gt h em a x m t e s a m p l i n gs t r a t e g ya i l dm ed i s c e m i b i i i t ym a 仃i x t o g e m e r c r e a t e sm ed y i l 锄i cr c d u c ta l g o r i 山m f r o mm e a n g l eo fe s t a b i i s h i n gd e c i s i o nr u i e s ，m i sp a p e rc o m p a r e s c u r r e n tm e t h o d so na c c e s s i n gt h ed e c i s i o nr u l e s ，a n de x p a t i a t e st t 蛇i r m e r i ta l l ds h o n c o m i n g t h ep 印e re m p h a s i z e so nt 、v ok i n d so fm e m o d s o nd i r e c t l ya c c e s s i n gt h ed e c i s i o nm l e sw i md e c i s i o nt a b l ea n dh o wt o c a l c u l a t ed e c i s i o nr u l e sw i t hd v n a m i cr e d u c t f i n a l l y ， am o d i 矗e d a i g o r i t h m o fd e c i s i o nr u l e si s m e n t i o n e d ，w h i c hp e r f e c t t h ee r 玎” m o 出最c a t i o na r e rm ed e c i s i o nm l e sa r ee s t a b l i s h e d i nb r i e f t h er o u g hs e tt h e o r ya n dm e t h o di sq u i t ea ne f h c i e n tm e a n s t od e a lw i t hc o m p l e xs y s t e m ，w h i c hi s a p p l i e d t ot h e 是e l do fd a t a 中南大学硕士学位论文a b s t r a c t m i n i n g ( d m ) a n dl m o w l e d g ed i s c o v e ui nd a t a b a s e ( k d d ) m o r e o v e r ， d y n a m i cr e d u c t a i l dm em e t h o do n e s t a b l i s h i n g m ed e c i s i o nm l e s r e s u l t e d 疗o mi tc a no f 佗rm o r ee f n c i e n ta i l dp r e c i s ed a t af o rm et w o f i e l d sm e m i o n e da b o v e k e yw o r d s r o u g hs e t ， d e c i s i o n t h b l e ，d y 瑚m i cr e d u c t ， d e c i s i o nr u l e s 原创性声明 本人声明，所里交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单 位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均 已在在论文中作了明确的说明。 作者签名： 岛l 训 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文：学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：! 地 导师签名：五窆! 豳 日期：五鲨立年上月丛日 中南大学硕士学位论文 第一章绪论 第一章绪论 随着社会各行各业拥有数据的日益增长，分析这些数据，发现隐含在这些 数据中有用模式的要求愈显重要。但是，人们在分析现有的数据方面，尽管已 经提出了用于数据挖掘的简单的统计分析技术。但实用的智能数据分析技术目 前仍不成熟。因此，欲寻找一种快速、高效、智能的数据分析方法一直是数据 挖掘研究者重点研究的目标之一。粗糙集理论自提出以来，以其广阔的适用性 迅速引起各行业的重视。以它为基础研究数据分析技术的热潮方兴未艾。该理 论的最大优点是，只使用进行挖掘的已得数据集所提供的信息，不依赖于其他 的模型假设。 本章主要介绍粗糙集理论的产生和发展。首先介绍粗糙集理论的提出背景、 研究对象、应用现状；接着简述了粗糙集理论的基本问题、发展前景；最后介 绍了本论文的研究背景和各章节的主要安排。 1 1 粗糙集理论的产生和发展 l11 粗糙集理论的提出背景 经典逻辑中只有真、假二值，但实际上有大量含糊现象存在于真与假之间。 因此，长期以来许多逻辑学家和哲学家就致力于研究含糊概念。早在1 9 0 4 年， 谓词逻辑的创始人g f r e g e 就提出了含糊一词，并把它归结到边界线，也就是 说在全域上存在一些个体既不能在其某个子集上被分类，也不能在该子集的补 集上被分类。2 0 世纪6 0 年代初，l a z a d e h 提出了模糊集，不少理论计算机科 学家和逻辑学家，试图通过这一理论解决g f r e g e 的含糊概念，但遗憾的是， 模糊集是不可计算的，没有给出数学公式描述这一含糊概念，故无法计算出它 的边界线上的具体的含糊元素数目。时隔2 0 年后的8 0 年代初，zp a w l a k 针对 g f r e g e 的边界线区域思想提出了粗糙集( r s ，或粗集) “】，他把那些无法确认的 个体都归于边界线区域，而这种边界线区域被定义为上近似集和下近似集之差 集。由于上近似集和下近似集都可以通过等价关系给出确定的数学公式描述， 所以含糊元素数目可以被计算出来，即在真假二值之间的含糊程度可以计算， 从而实现了g f r e g e 的边界线思想。粗糙集理论主要兴趣在于它恰好反映了人 们用粗糙集方法处理不分明问题的常规性，即以不完全信息或知识去处理一些 不分明现象的能力，或依据观察、度量到的某些不精确的结果而进行分类数据 中南大学硕士学位论文 第一章绪论 的能力。 1 1 2 粗糙集理论的研究对象 粗糙集理论的研究对象是由一个多值属性( 特征、症状、特性等) 集合描 述的一个对象( 观察、病历等) 集合，对于每个对象及其属性都有一个值作为 其描述符号，对象、属性和描述符是表达决策问题的3 个基本要素。这种表达形 式也可以看成一个二维表格，表格的行与对象相对应，列对应于对象的属性。 各行包含了表示相应对象信息的描述符，还有关于各个对象的类别成员的信息。 通常，关于对象的可得到的信息不一定足以划分其成员类别。换句话说，这种 不精确性导致了对象的不可分辨性。给定对象问的一个等价关系，即导致由等 价关系构成的近似空间的不分明关系。粗糙集理论就用不分明对象类形成的上 近似和下近似来描述。这些近似分别对应了确定属于给定类的最大的对象集合 和可能属于给定类的最小的对象集合。下近似和上近似的差是一个边界集合， 它包含了所有不能确切判定是否属于给定类的对象。这种处理可以定义近似的 精度和质量。粗糙集方法可以解决重要的分类问题，所有冗余对象和属性的约 简包含属性的最小子集，能够很好地近似分类，得到可以接受质量的分类。而 且，它还可以用决策规则集合的形式表示最重要属性和特定分类之间的所有重 要关系。 11 3 粗糙集理论的特点 1 粗糙集理论不需要先验知识。模糊集和概率统计方法是处理不确定信息 的常用方法，但这些方法需要一些数据的附加信息或先验信息，如模糊隶属函 数和概率分布等，这些信息有并不容易得到。粗糙集理论分析方法仅利用数据 本身提供的信息，无须任何先验知识。 2 粗糙集理论是一个强大的数据分析工具。它能表达和处理不完备信息： 能在保留关键信息的前提下对数据进行化简并求得知识的最小表达式；能识别 并评估数据之间的依赖关系，揭示出概念简单的模式；能从经验数据中获取易 于证实的规则知识，特别适于智能控制。 3 粗糙集理论与模糊集分别刻画了不完备信息的两个方面【2 l ：粗糙集理论 以不可分辨关系为基础，侧重分类，模糊集基于元素对集合隶属程度的不同， 强调集合本身的含混性。从粗糙集理论的观点看，粗糙集合不能清晰定义的原 因是缺乏足够的论域知识，但可以用对清晰集合逼近。虽然粗糙集理论和模 中南大学硕士学位论文第一章绪论 糊集特点不同，但它们之间有着密切的关系，有很强的互补性【3 ，t ”。粗糙集理 论和证据理论也有一些相互交叠之处【6 1 ，在实际应用中可以相互补充。 1 1 4 粗糙集理论的应用现状 粗糙集理论是一种处理含糊和不精确性问题的新型数学工具，其基本思想 是在保持分类能力不变的前提下，通过知识约简，导出概念的分类规则。它自 问世以来，无论是在理论或应用上都是一种新的、最重要的并且是迅速发展的 一门既有理论又有应用的研究领域。 l 股票数据分析。文 7 应用粗糙集方法分析了十年间股票的历史数据， 研究了股票价格与经济指数之间的依赖关系，获得的预测规则得到了华尔街证 券交易专家的认可。 2 模式识别。文 8 应用r s 方法研究了手写字符识别问题，提取出了特征 属性。 3 地震预报。文 9 研究了地震前的地质和气象数据与里氏地震级别的依 赖关系。 4 冲突分析。文 1 0 应用r s 方法建立了反映以色列、巴勒斯坦、约旦、 叙利亚和沙特阿拉伯等六国关于中东和平问题各自立场的谈判模型。 5 从数据库中知识发现( 砌o w 如商弘旃s c d 坩，y 加出如6 位妃，肋d ) 【“1 “，是 当前人工智能和数据库技术交叉学科的研究热点之一。r s 方法现己成为k d d 的 种重要方法，其导出的知识精炼且更便于存储和使用。 6 粗糙控制i n 。1 。粗糙集理论根据观测数据获得控制策略的方法被称为从 范例中学习，属于智能控制范畴。基本步骤是：把控制过程中的一些有代表性 的状态以及操作人员在这些状态下所采取的控制策略都记录下来，形成决策表， 然后对其分析化简，总结出控制规则，形成为：i fc o n d i t i o n = n 满足t h e n 采 取d e c i s i o n = i 。粗糙集方法是一类符号化分析方法，需要将连续的控制变量离 散化，为此z p a w l a k 提出了粗糙函数的概念，为粗糙控制打下了理论基础。文 【1 6 ，1 7 】应用粗糙控制研究了“小车一倒立摆系统”这一经典控制问题，取得了 较好的结果。在过程控制领域，文【1 8 】应用粗糙集方法成功地提取出了水泥窑 炉的控制规则。粗糙控制的优点是简单迅速、实现容易、不需要象模糊控制那 样进行模糊化和去模糊化。因此在特别要求控制器结构与算法简单的场合，采 取粗糙控制较为合适。另外，由于控制算法完全来自观测数据本身，其决策和 推理过程可以很容易被检验和证实。一种新的有吸引力的控制策略“模糊一粗 中南大学硕士学位论文 第一章绪论 糙控制( 厅幔卜阳嘞c 明加，) ”正悄然兴起，其主要思路是利用r s 获取模糊控制 规则。 7 医疗诊断。粗集方法根据以往的病例归纳出诊断规则，用来指导新的病 例。现有的人工预测早产的准确率只有1 7 一3 8 ，应用粗糙集理论则可提高到 6 8 一9 0 1 2 稍。 8 专家系统( e s ) 。r s 抽取规则的特点，为构造e s 知识库提供了一条崭新 的途径【2 l l 。 9 人工神经网络( a n n ) 。训练时间过于漫长的固有缺点是制约a n n 实用化 的因素之一。文 2 2 】应用粗糙集化简神经网络训练样本数据集，在保留重要信 息的前提下消除了多余的数据，使训练速度提高了4 7 2 倍，获得了较好的效果。 文 2 3 ，2 4 】将r s 与a n n 结合起来，充分利用r s 处理不确定性的特长以增强a n n 的信息处理能力。 1 0 决策分析【25 1 。粗糙集的决策规则是在分析以往经验数据的基础上得到 的。粗糙集允许决策对象中存在一些不太明确、不太完整的属性，弥补了常规 决策方法的不足。希腊工业发展银行e t e v a 应用r s 理论协助制定信贷政策，是 粗糙集多准则决策方法的一个成功范例。 粗糙集理论对于人工智能和认知科学也是十分重要的，尤其在机器学习、 知识获取、决策分析、数据库的知识发现、专家系统、决燕支持系统、归纳推 理、矛盾归结、模式识别、模糊控制及其他各个方面的应用，它都为之提供了 种很有效的新的数学方法。粗糙集自提出以来一直得到模糊数学的创始人 z a d e h 的重视，并给与很高的评价，把他列入他新提倡的软计算的基础理论之 一。由此可见，粗糙集理论及其广泛应用越来越受到重视。 1 2 粗糙集理论研究的基本问题 1 2 1 决策表的约简 决策表是将信息系统中的具有代表性的数据，通过行列表格的形式抽样对 应而得的对象、属性集合表。粗糙集理论从决策表开采规则，辅助决策，其关 键步骤是求值约简或数据浓缩，包括属性约简和值约简两个过程。有些属性或 某些取值删除后对决策并没有多大影响，但它们占用存储空间和处理时间，为 了提高整体决策效率可以采用约简的方法，提取决策表中相对稳定的属性或值。 决策表约筒经常涉及到核和差别矩阵担q 两个重要的概念。一般来讲，决策表的 相对约简有许多，最小约简( 含有最少属性) 是人们期望的。但遗憾的是，z i a r k o 4 中南大学硕士学位论文 第一章绪论 已经证明了求决策表的所有约简是n p h a r d 问题，而且求取最小约简也是一个 n p h a r d 问题【2 ”。目前人们一方面通过借助启发式搜索算法解决最小约简的求 解问题，已经取得了一些可喜的成果。另一方面决策表的核是唯一的，它定义 为所有约简的交集。所以核可以作为求最小约简的起点。差别矩阵突出属性的 分辨能力，从中可以求出决策表的核以及约简。根据所求的约简制定决策规则， 是粗集理论研究决策表的重要目的。一个良好的决策规则集，不但能指导类似 决策表的约简，还能够依照此规则集制定有效的决策。 12 2 不完全决策表的处理 从不完全决策表( 含有空值暂时无法得到的值，称这种决策表为不完 全决策表) 产生决策树已被人工智能界注意。处理空值的简单方法是删除带有 空值的对象或用最常用值( 由取值概率确定) 代替空值。空值的概率分布可用 贝叶斯范式估计。也有用其他条件属性和决策属性的取值关系来估计空值的做 法。文 2 8 】利用模糊集理论处理空值引起的不确定。 在粗糙集商业软件u m s 中，还提到一种处理空值的方法：即用可能的取 值代替空值，根据不同的组合把不完全决策表转化为若干完全决策表。但这种 方法的复杂性高，在空值属性较多或空值可能取值较多的情况下，效率很低。 在文【2 9 】中，s l o w i n s k i 比较了几种不完全决策系统的分析方法，得出了以 下结论：( 1 ) 如果一个规则在原不完全系统的每个完全( 组合) 拓展中是确定的， 那么这个规则是确定的；( 2 ) 从不完全决策表中删除包含空值的对象后，获取 的知识可能为伪规则( 对原不完全系统不一定成立) 。文 3 0 应用差别矩阵，推 广了等价关系( 相似关系) 、集合近似等概念，研究了不完全决策表的决策表约 简和规则发现问题，从而为粗糙集理论的实用化迈出了可喜的一步。文 3 0 提 出的约简方法的特点是不需改变原不完全决策表。 有关不完全决策表的处理，文【3 1 】还提出了一种基于粗糙集的数据开采模 型。该模型先建立一系列不同简化层次的子系统，然后推导出各子系统的规则 集。在应用模型决策时，用给定对象的信息与模型相应层次节点的规则匹配， 根据某种算法做出决策。有关不完全信息的处理，仍是粗糙集应用的难点。 1 23 连续属性的离散化 粗糙集理论的数学基础是集合论，难以直接处理连续的属性。而现实决策 表中连续属性是普遍存在的。因此连续属性的离散化是制约粗糙集约简实用化 中南大学硕士学位论文 第一章绪论 的难点之一。这个问题一直是人工智能界关注的焦点，连续属性的离散化的根 本出发点是在尽量减少决策表信息损失的前提下( 保持决策表不同类对象的可 分辨关系) ，得到简化的和浓缩的决策表，以便用r o u g hs e t 理论分析，获得决 策所需要的知识。 最优离散化问题( 离散的切点数最少) 己被证明是n p - h a r d 问题，利用一 些启发式算法可以得到满意的结果。总体上讲，现有离散化方法主要分为非监 督离散化和监督离散化：前者包括等宽度( 将连续值属性的值域等分) 和等频 率离散化( 每个离散化区间所含的对象相同) 。非监督离散化方法简单，但因忽 略了对象的类别信息，也就难以获得较好的离散化效果，只能用在属性具有特 殊分布的情况；针对上述问题，监督离散化方法考虑了分类信息，提高了离散 效果。目前比较有代表性的监督离散化方法有以下几种：h o l t e 提出了一种贪婪 的单规则离散器方法、统计检验方法、信息熵方法、r o u 曲s e t 和布尔推理、聚 类法。 对相容决策表( 决策表中若存在两行条件属性值相同，而决策属性值亦相 同) ，应尽量保持连续属性离散前后决策表的相容性，否则决策表会因为失去部 分信息而引入噪声。这样开采的知识并不一定反映原决策表的实际情况。文 3 2 】 给出了一种一致性数据浓缩( 离散) 的经验公式： ，= 口c 捌0 9 丢+ d ( 1 - 1 ) d = o 3 2 8 一( 口c + 6 j o g 书】 ( 1 2 ) 其中s 为决策表对象数，爿为属性个数，c 为分类的类别数量，e 为中间距离。 分类法所得到的属性等价类的个数，即连续属性的离散值数目。这个经验公 式虽然与领域无关，但其系数口和6 的调整有一定的主观性。 此外还有回溯方法、贝叶斯决策法和超平面等。这些方法各有特点，但都 存在一个不足：每个属性的离散化过程是相互独立的，忽略了属性在区分对象 方面的关联性和互补性，从而使得离散的结果中含有冗余或不合理的分割点。 针对这个问题，文 3 3 】给出了一种连续属性的整体离散化方法：连续属性离散 化实质上是利用垂直于不同连续属性轴的超平面对属性空间进行超立方体划 分。单个连续属性的离散化相当于该属性轴与之垂直的超平面的交点。决策表 离散化的要求是在每个划分超立方体包含同类对象的前提下，获得最少的划分 超立方体个数。实验表明整体离散不仅能显著减少离散化划分点和归纳规则数， 而且提高了分类精度。 6 中南大学硕士学位论文第一章绪论 连续属性离散化目前还存在的问题是缺乏递增的离散化方法，即当新的对 象加入决策表时，原有的分割点可能不是最优或满意的。 1 2 4 粗糙集与其他软计算方法的集成 粗集约简和其他计算方法的结合，能够提高数据开采能力，这是由现实世 界的复杂性和处理方法有限能力的矛盾决定的。其中粗集与神经网络的结合是 研究的热点。通常，粗集约简对噪声敏感且泛化能力弱，可以用神经网络的优 点( 自组织、容错和推广能力) 来弥补；神经网络不能确定重要性的属性组合、 结构构造缺乏通用的房法且推理过程不透明等不足，可以用粗分析辅助。粗分 析和神经网络的结合实质上是人类两种思维方式逻辑思维和形象思维的结 合。寻找新的结合方法是一个值得讨论的问题。 有关粗糙集理论与遗传算法、模糊集理论等软计算方法的结合也屡见不鲜。 文【3 4 】在并行虚拟机环境下结合遗传算法和粗集理论结合实现了一种数据开采 模型，即利用遗传算法设计一种自适应粗糙集模型。这种模型能够获得比传统 粗糙集模型更好的结果。 此外，模糊集与粗集的约简思想结合用于模糊一粗控制器，用来获取和表 达知识。约简思想与统计方法结合，粗糙集与p e t r i 网、主分量分析( p c a ) 、支 撑向量机( s 订) 、b a y e s i a n 方法也有报道。粗糙集与其它软计算方法的集成是 数据开采的一种趋势。 1 3 粗糙集理论的典型成果及其研究前景 不确定性是粗糙集理论的关键词，它涉及集合论定义中的许多实质性内 容。集合的近似定义是现代数学中的重要概念之一，而与布尔逻辑非常相关的 经典集合论又是数字计算机运算的核心。众所周知，许多实践问题不能满足现 在计算机的求解条件，特别是机器学习、模式识别以及某些控制问题等，这种 困难常常使得不能建立描述个体的算法。而粗糙集理论及其扩充对于建立此类 个体的近似描述，提供了一种精确的数学技术。粗糙集方法对于处理这类问题 提供一种通用的由精确数学语言支持的哲学框架。可以预言，粗糙集方法将在 数据挖掘和软计算，特别是处理大型数据库和复杂问题等方面，显示出“英雄 有用武之地”的气魄。下面将列出一些粗糙集的典型软件和系统，以及未来的 可发展方向。 7 中南大学硕士学位论文 第一章绪论 131 基于粗集理论的典型软件与系统 美国缸娜大学开发了基于粗集方法学习的例子，并开发了基于粗集方法 的学习系统，即u ! r s ( k 口阳l 增加m 胁卵跆s6 娜耐删r s ) 。这个系统的知 识获取项对于用不完全信息工作的专家系统建立知识库是一个十分恰当的规则 归纳法的应用实例。在n a s a sj o h n s o n 空问中心多年的应用，充分显示了它 在开发专家系统进行全球气候变化的研究中起的作用，它是作为一种开发专家 系统的工具被引用的。r s 理论之所以提供了a i 的有效方法，是因为实现它的 程序可以很容易在平行机上运行。且基于r s 理论的r o u 曲逻辑将使单调逻辑 非单调化，从而在a i 的近似或不精确推理中将发挥不可估量的作用。 粗糙集方法用于决策分析己体现在波兰p c 伽册科技大学开发的计算机系 统中，称之为r o u 曲d a s 和r o u 曲c l a s s ，它们对任务分别执行解释和描述。 这两个系统在许多实际领域都有应用( r o u 曲d a s 执行信息系统数据分析任 务，r o u 曲c l a s s 支持新对象的分类，这两个软件都是基于d o s 操作系统的) 。 美国电力科学研究院( e p i u ) 对粗糙集的应用研究的潜力对十分重视，将其 作为战略性研究开发( s t r a t e g y r & d ) 项目，在1 9 9 6 年拨款资助s a n j o s e 州立大学 进行电力系统模糊粗糙控制器的研究。 加拿大尺p 鲥瑚大学开发的k 加r 是用c 编写的，在u n i x 环境下运行， k d d - r 基于变精度粗糙集模型【3 ”，通过改变粗糙程度而使数据中隐含的模式 更清楚的显示出来。加拿大r e d u c t s y s t 啪i n c 公司开发的用于数据库知识发现 的软件d a t a l o g i c 艉p6 】是用c 语言开发的，可安装在个人计算机上，为科研领 域和工业界服务| j ”。 1 3 2 粗糙集理论的可研究领域及发展前景 基于粗集理论的逻辑是粗集理论不确定推理的基础，发展这类逻辑理论基 础也是目前粗糙集研究的重要课题。今后，围绕着其逻辑特点和知识处理机理， 主要有下列研究方向值得注意。 1 数学理论的系统化和形式化：尽管粗集理论产生于真正的数学基础，但 许多理论问题仍有待于真正澄清。p a w l a i ( 粗糙集模型的推广一直是粗集理论研 究的主流方向，目前主要有构造性方法和代数性( 公理化) 方法。 2 算法的研究：粗集理论中有效算法研究是粗糙集在m 方向上研究的一 个主要方向。目前，粗集理论中有效算法研究主要集中在导出规则的增量式算 法，约简的启发式算法，粗糙集基本并行算法以及与粗糙集有关的神经网络与 中南大学硕士学位论文 第一章绪论 遗传算法等。这些研究的成功应用有的已经获得了商业价值。 3 面向粗糙集对象的专家系统和智能系统和粗糙集在工程技术方面的应 用。 4 与其他数学理论的联系：从算子的观点看粗集理论，与之关系较紧的有 拓扑空间，数理逻辑，格与布尔代数，模态逻辑，算子代数等。从构造性和集 合的观点来看，它与概率统计，模糊数学，证据理论，图论，信息论等联系较 为密切。粗集理论研究不但需要以这些理论作为基础，同时也相应地带动这些 理论的发展。随着r s 结构与代数结构，拓扑结构，序结构等各种结构的不断 整合，必将不断涌现出新的富有生机的数学分支。 粗集理论除了朝着逻辑及其近似推理方向发展以外，近些年来出现了大量 的r o u 曲数及r o u 曲函数的研究，发表了一系列关于r o u 曲函数方面的论文， 如r o u 曲函数的各种近似运算，r o u g h 函数的基本性质，关于它的r o u 曲连续， r o u g h 极限，r o u 曲可导，r o u 曲积分和r o u 曲稳定性，r o u 曲函数控制及建 立由r o u g h 实函数控制的离散动态系统都是典型的问题，这些问题都要求在 r o u 如函数理论的模型下给予公式化。这些问题的研究将有贡献于定性推理方 法的研究，这种研究实质上是使连续数学离散化，从而使连续数学也能被现代 计算机所接受。目前，对粗集理论的研究集中在其数学性质，粗集拓广，与其 它不确定方法的关系和互补，及有效算法等方面。 粗集理论数学性质方面的研究，主要讨论r s 的代数结构，拓扑结构，以 及粗集的收敛性问题。 粗集理论与其他不确定性方法之间的关系的研究中，目前主要讨论它与模 糊集理论和d s 证据理论的关系和互补。 在粗集约简算法方面的研究，主要集中于： f 1 1 导出规则的增量式算法：原有的算法是在固定的数据集上进行的，当 有新的数据增加到数据集时，若用原有算法导出规则是相当麻烦的，增量式算 法是对原有规则进行修正，从而得出关于新数据集的规则的方法。 f 2 1 约简的启发式算法：对于一个信息系统来说，找出其所有约简是n p 完全问题，很自然的想法是采用启发式方法找出最优或次优约简，这些算法的 共同特点是利用属性的重要性作为启发式： f 3 1 粗集基本运算的并行约简算法：粗集的基本性质决定它的很多基本运 算可以并行计算，粗集研究的初衷就是试图为大量数据的处理提供一个数学工 具。因此，这些性质就显得十分重要了。 从计算方面来讲，需要设计更有效的基于启发式算法的求解算法。尽管已 中南大学硕士学位论文 第一章绪论 经设计了基于各种模拟的遗传算法，将神经元网络嵌入遗传算法的混合智能算 法成功地求解了一系列不确定规划模型，但它们一般只能适用于小规模问题。 为适应求解更大规模的问题之需要，有必要在算法设计方面作进一步的改善或 进行新的尝试。例如，结合模型的数学性质而设计一些特殊的算法：将传统优 化算法和现代启发式算法结合起来的合成算法；应用模拟退火法，禁忌搜索， 并行算法以及专家系统；设计联合各种启发式算法的新型混合智能算法。我们 也可以考虑或者将各种模拟，神经元网络和模拟退火法集成一体形成混合智能 算法等。 1 4 论文的课题背景、主要研究内容和章节安排 随着社会各行各业拥有数据量的日益增长，分析这些数据，发现隐含在这 些数据中的有用模式的要求越来越显得重要。但是，人们在分析现有数据方面， 尽管用于数据挖掘的简单的统计分析技术已经提出，但实用的智能数据分析技 术目前依然不成熟。因此，找到一种快速、高效、相对稳定的数据分析方法一 直是数据挖掘研究者重点研究的目标之一。作为粗集约简分支之一的动态约简， 自被提出以来就广泛地被人们所重视。特别是在针对海量数据及其增量数据的 约简上，不完全规则的修正上，基于动态约简思想产生的算法，具有比静态约 简算法更高效，更稳定的特点。因而，对动态约简的研究对深刻理解粗集理论， 寻找高效约简的规律和方法都具有指导性意义。 本论文以动态约简的研究为核心内容，针对目前静态约简对海量数据表和 增量数据表处理上的不足，提出了兼顾海量数据与增量数据处理的动态约简算 法。并研究了动态规则的产生，提出了修正不完全规则的动态规则算法。 根据以上研究内容，论文的后续章节构成如下： 第二章，粗糙集理论的基本概念。本章首先描述了粗糙集理论所研究的知 识与不可分辨关系的特点，以及研究对象如何在知识范畴的划分下提高当前知 识的分辨能力；接着，以如何表达不可分辨关系为起点，引出粗糙集理论的一 些基本定理定义和性质；然后通过对知识约简的介绍引出核与约简这两个粗糙 集理论的重要概念；最后重点介绍了差别矩阵和差别函数的构造方法，以及如 何利用差分矩阵和差别函数这一有效的粗糙集约简工具完成对决策表的约简和 决策规则的提取。 第三章，动态约简计算法及其概率抽样动态约简算法。本章首先阐述动态 约简的特殊性定义和更为普遍的动态约简定义；再提出如何根据不同决策表所 1 0 中南大学硕士学位论文 第一章绪论 采取的不同子决策表抽样策略，以及如何计算动态约简和约简域；最后，重点 提出了已知决策表的概率抽样动态约简算法，并讨论了如何在后续数据发生变 化时的动态算法修正。 第四章，动态规则制定以及不完备规则修正。本章作为第三章研究工作的 延续，以决策表为研究对象首先分析了现有决策规则获取方法的缺陷；接着提 出了如何利用动态约简制定动态规则以及动态规则的优点；最后重点提出了在 不完备规则情况下的决策规则修正算法。 第五章，总结与展望。对本论文的研究工作进行总结，指出进一步研究工 作的重点和方向。 中南大学硕士学位论文 第二章魍糙集理论基本 第二章粗糙集理论基本概念 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其主要思想 就是在保持分类能力不变的前提下。通过知识约简，导出问题的决策或分类规 则。目前，粗糙集理论已被成功地应用于机器学习、决策分析、过程控制、模 式识别与数据挖掘等领域。本章介绍标准粗糙集理论( p a w l a l 粗糙集模型) 的基 本概念，作为后蔼各章节的理论基础。 2 1 知识与知识库 设u 庐是我们感兴趣的对象组成的有限集合，称为论域。任何子集 u ，称为u 中的个概念或范畴。为规范化起见，可以认为空集也是一个 概念。u 中的任何概念簇称为关于u 的抽象知识，简称知识。粗糙集理论主要 是对在u 上能形成划分的知识感兴趣。个划分f 定义为：f = ( 。z ：，彳。) ； 其中置e u ，z ，痧。对于f 歹，j ，_ ，= l ，2 ，3 ，”来说x 。ix ，= 。u 上的 族划分称为关于u 的个知识库。 也可从等价类的角度去描述知识库。设凡是u 上的一个等价关系，明r 表 示足的所有等价类( 或则u 上的分类) 构成集合，司。表示包含元素苫u 的霞 等价类。一个知识库也就是一个关系系统j o ( h r ) ，其中u 为非空有限集，称 为论域，r 是u 上的族等价关系。 若户r ，且j p 痧，则ip p 中所有等价关系的交集) 也是一个等价关系， 称为j p 上的不可区分关系，记为。且有 【n d = ii x l r( 2 ，1 ) r e ， 这样，聊眺托p ) ( 即等价关系删的所有等价类) 表示与等价关系族p 相关的知 识，称为矗中关于( ，的；p 基本知识( 尸基本集) 。为简单起见，可以用e 徊代替 卅加嘏p ) ，胁战i d ) 的等价类称为知识尸的基本概念或基本范畴。特别地，如果q e r ，则称q 为x 中关于u 的q 初等知识，q 的等价类为知识r 的q 初等概 念或初等范畴。 事实上，p 基本范畴是拥有知识p 的论域的基本特征。换句话说，它们是 知识的基本模块。同样，也可定义：当j u 固为一个知识库，f 湘定义为 k 中所有等价关系的族，记作扔d ( 髟) = f 耐c p ) 庐，r j 。 下面，本章将通过个实际应用来界定知识库中的不可分辨关系，以及论 2 中南大学硕士学位论文 第二章粗糙集理论基本概念 证在知识库中基本范畴的界定是不需要所有初等范畴参与这一定理。 例2 1 给定玩具积木的集合u = “，x ：，x 。) ，并假设这些积木有不同 的颜色( 红，黄，蓝) ，形状( 方，圆，三角) ，体积( 小，大) 。因此，这些积木都 可以用颜色、形状、体积这些知识来描述。如果根据某一属性描述这些积木的 情况，就可以按照颜色、形状、体积分类。 按颜色分类： x l ，x 3 ，x 7 ) 一一红； x 2 ，x 4 ) - 一蓝； x 5 ，x 6 ，z 8 一一黄。 按形状分类： x 1 ，x 5 ) 一一圆； x 2 ，x 6 卜- 一方：( x ，x 。，x 7 ，x 8 ) 一三角。 按体积分类： 如，x ，x 。) 一一大；，b ，x 。，t ，x 。) 一一小。 换言之，以上分类定义了三个等价关系( 即属性) ：颜色r ，形状尺：，体积 足，通过这些等价关系，可以得到三个等价类： u r = x l ，x 3 ，x 7 ) ， x 2 ，x 。) ， x 5 ，吒，x 8 ) ) ， u 月2 = “x i ，x 5 ) ， x 2 ，x 6 ) ， x 3 ，z 4 ，x 7 ，x 8 ) ) ， u 恐= “r 2 ，x 7 ，x g ) ， x i ，x 3 ，z 4 ，x 5 ，x 6 ) 。 这些等价类是由知识库j _ ( _ ( u ，月) 中的初等概念( 初等范畴) 构成的。 基本范畴是初等范畴的交集构成的，如下列集合： z i ，x 3 ，b ) i ( x 3 ，x 4 ，x 7 ，黾) = 屯，x 7 ， x 2 ，x 4 ) i x 2 ，x 6 = x 2 ， x 5 ，x 6 ，x 8 i b ，x 4 ，x 8 ) = x 8 ) 。 它们分别为 r ，j r ：) 的基本范畴，即：红色三角形，蓝色方形，黄色三角形。 依此类推，可以得到下列集合： x l ，墨，) i x 3 ，x 4 ，x 7 ，) i x 2 ，z 7 ，x 8 = x 7 ) ， x 5 ，k ，x 8 ) i x 3 ，x 4 ，x 7 ，) i x 2 ，x 7 ，) = ( x 8 ) a 它们分别为 r ，尺：，r ，) 的基本范畴，即：红色大三角形，蓝色大方形，黄 色大三角形。 由以上两个基本范畴的提取可以知道，基本范畴是不需要所有的初等范畴 中南大学硕士学位论文 第二章租糙集理论基本概念 参与构造的。并且，r 等价类中的所有不可区分关系的交集依然构成一个不可 区分关系。空范畴是指在当前知识库下无法得到的一些范畴，如：蓝色圆形， 红色方形等。 下面，将单一知识库的比较拓延，讨论两个知识库之间的关系。 令j p ( u ，尸) 和k7 = ( 矾q ) 为两个知识库，当f ，d ( p ) = 胁d ( q ) ，称这两个 知识库是等价的。因此，当k 和k7 有同样的基本范畴时，知识库k 和置中的 知识都能确切地表达关于论域的完全相同的事实。这个概念意味着可以用不同 的属性集对对象进行描述，以表达关于论域的完全相同的事实。这也是粗糙集 约简的理论依据之一。 对于以上这两个知识库，当打讲( p ) c 加d ( q ) 时，称知识p ( 知识库j l = ) 比知 识q ( 知识库k7 ) 更精细，或者说q 比尸更粗糙。这意味着，精细是将某些范畴 分割成更小的单元，粗糙是将某些范畴组合在一起。换句话说，粗糙集的约简 就是力求从知识库中找到相对精确的范畴以提高知识的分辨能力。 2 2 不精确范畴、近似与粗糙集 令x ( ，j r 为u 上的一个等价关系。当x 能表达成某些尺基本范畴的并 时，称x 是尺可定义的：否则称x 为r 不可定义的。 r 可定义集是论