（管理科学与工程专业论文）基于rough集理论的数据约简研究与应用.pdf

abs tract inre ccn t y e 娜， w i tht h e q u i ck d e v c 10 p m en t 0 f th e d a t a b as e t e c ho0 l o gyand t h c e x te ns i v c a p p 1 i cati on o f th e dst ab as e m 仙a g e m e n t s ys t e m ， t h e d a t a o f b a c k l o g inth c d a t ab as e o f b us in e s se n t e rp n s e a rem o r ean dm ore. h o w ev e r th ed at aexp l o s i 加 con ce a l man yi m portan t in fo n 盯 ai i on， lfw e w a n t t oca n yon t h e 朋al y si stoa l l 加 化 rmat i o nand。 田 了 yo nknow l edge excav a t i o n ， i t isu n w i s eandu nne c e s s 出 下 . l t i s i m p o rt an t fo r ust o 励d out s u i t ab l e m etho d s ， re d u “r e d u n d ant kn洲l e d g e and r e fi n e i m p o n a 刀 t d at as . r o u gh s e tsthe o ry， 面t i al 让 ed b y p ro仕 s s o r p a w l ak ine ar l y1 9 8 0 s h as b e enp ro v ed tob e 助 exce ll ent m athe m at j cal to o l d e a l i n g w i thun e rt a i 刀 and v a gu e d e s c ri p ti on ofobje ct s ，w h o s e b asic i d e a i s t o de r i v e c1 as s i fi ca ti oniule s o f con ce p t i o 刀 b y kno w l edg e r edu c t i o nw i t ht h e a b il i t yo f d s s s i fi cat i o nun比ang e dlim a y 枷dt h e 址 d in g 阳d pot e n ti alru l e s ， whj chi s 物 o w l ed ge ， fromt hed a taw i th o utany pr e l 加i n a r y ora d di t i o nal i n fo rma 石 皿.and th e r o u ghs et t h co ryh asp l a y ed胡加port 明 t role ins 吮 c o r 口 p u ting . the ma inp roc e d u r e s o f t his p a p e r are li s t edasfol l o w s : firs t，th ep aper introd u cedt h eth i n gs a bou t th er o u gh s c tth eory， t h eb as i c con cep t s o f r o u gh s etth eory andth ee x p ans i on of thc rou gh s dm o d e l ， s eco n d ， th e 时i d e h asma d e the furt b e r res e a r c h o nd a t a r edu ct i o 残w e p r e s ent a d i v i d ing m et b o d for incon s i sten t d e d s io 。扭 b 】e ;as w e l l aswe b r ingfo n 刀 肚 daw a ytoc o t d b in et he m e th eds ofrou ghs e t t h e o ryan d s ta t i s t i csinth e course o f i n con s i s t 叨t d e ci s fo n ru l c s e x tr a ct i o n 加 d th e r e s u l t in g- ru l e s a res i ft e d b y su p port 、优 胜 幻 川 y and cov c ra g e ， w h i cb can i m pro v e thc a c c u r a c yand r at i o n a l it y ind 州s i on 一 m ald n g . an d com b in e dw it bth e fe a t ur e s o f t ea 面n g w o rk， t 址 s p ap e r p u t s fo rwar d t h e m e 山 o d o f th e com p re h e ns i v e e v al u a t ion o f t e a c h i n gq u a l i t y ， w h i ch 阎u 概 t he e val u a t 咖 勿 d ex e soft e a chin g q u al i t y and asc e rt ai ns th c w e i ght o f eval u a t i o n i n d e x e s b ase d o nth e th e o ryo f r o u gh s e t s . t 卜 1 s m e t h o dr edu ces t h es c al e o f i n d e xs y s t em andw e ake n s th e s u bje ct i v i t yi n w 颐 ght as s i gn n l c nt f i n a l l y ， b y i n t e gr a t i n g r o u gh s e t ， s r e d u ct io nt h e o ryw i t h n c u r a l n e two r k ， t h e a rti ci e a d v anee s ro u ghn e u ra l n e tw o rkre d u ct i onm o d e i an d t h e ap p l i ca t j o n of t b a t mo d e l . ke y w o rds : r o u gh s e t ; i n con s i s t e n t d eei s i ontab l e ; a t trib u t e r e d u ct i on; ne u r a l ne t wo rk; 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。 据我所知，除了文中 特别加以 标注和致谢的地方外，论文中不包 含 其 他 人 已 经 发 表 或 撰写 过的 研究 成 果 ， 也 不 包 含为 获 得 南昌大学 或 其 他教 育 机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究 所做的 任何 贡献均己在论文中作了明确的说明并表示谢意。 学 位 论 文 作 者 签 名 (手 写 ): 袁 务 签 字 日 期 : 坷年 ; 月 日 学位论文版权使用授权书 本 学 位 论 文 作 者 完全了 解通述遭一有 关保留 、 使 用 学 位 论 文的 规 定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅 和 借阅 。 本 人 授 权南昌大嗦可以 将 学 位 论文 的 全 部 或部 分 内 容 编 入 有 关 数据 库 进 行检索，可以 采用影印、 缩印或 扫描等复 制手段保存、汇编学位 论文。 ( 保密的学位论文在解密后适用本授权书 ) 学 位 论 文 作 者 签 名 、 手 写 ): 未 责导 师 签 名 、手 写 ): 土 贼 签 字 日 期 : 坷年; 月 /君 日签 字 日 期 : 07 年 月 扎 学位论文作者毕业后去向: 工作单位: 通讯地址: 电话 : 邮编 : 引 言 引言 近年来 ，随着数据库技术的迅速发展以及数据库管理系统的广泛应用，企 业的 数据库或数据仓库中积累的数据越来越多。 然而激增的数据背后隐藏着许 多重要的 信息，人们希望能够对其进行更高层次的分析，以 便更好地利用这些 数据，为 企业以后的营销、发展 提供正确的决策方案。 在这个 “ 信息爆炸”的 时代，每天都有很多新的信息诞生，同时，每天都有很多信息失去利用价值。 所以， 想要 把企业数据库所有的 信息都进行分析和挖掘， 是不明 智也是不必要 的。我们着重要做的，就是找到合适的算法，约简冗余的数据，提炼出重要的 数据，以期达到去粗取精，去伪存真。 在20世纪80年代初， 波兰科学家 p awl aks 针对g fr ege 的 边界线区域问题 首次 提出了 经典r ough集的思想， 我们可以 把它看作是用 于处 理不完全、 不精 确信息系统的一种集合理论的扩展。 r ough集理论主要思想是 在保持分类能力不 变的 前提下， 通过知识约简， 导出问题的决策 或分类规则 门 。 r ough集理论在许 多重 要的实 际生活中 都有应用， 利用 r ou沙 集理论处理的问题包 括数据库中的 数据约简，数据相关性的发现，数据意义的 评估，由数据产生决策控制算法， 数据的近似分类， 数据中的相似性或差异性的发现，数据中范式的发现以及因 果关系的发 现闭 。 特别地， r ough集 方法在医学， 药学， 银行， 商业， 金融，市 场研究，工 程设计， 气象学，振动分析，决策分 析及其他领域都有重要的应用。 r ou助集理论现己 成为d m / k d d研究中的 最有力工具。 r ough集理论作为一种研究不精确性和不确定性知 识的 数学工具， 能够在缺 少关于数据的先验知识的情况下，仅以对观测数据的分类能力为基础，解决模 糊或不确定 性数 据的 分析和处理， 从而扩展了 原 有的集合 论t“ 。 r ough集方法的 优点在于: 不需要 预先给出额外信息;可去掉冗余输入信息， 简化输入 信息的 表达空间:算法简单 ， 易于操作。 r ough集方法是 模拟人 类的 抽象逻辑思维， 基 于不可分辨性的思 想和知识简化的方法。从数据中推理逻辑规则作为知 识系统 的模型，可以处理 输入定 性、 定量或者混合性信息， 特别是r ough 集理论方法 可以描绘知识表达中不同属性的重要性，进行知识表达空间的简化这一特性在 智能计算中发 挥了 重要作用。 但其容错性和自 适应外部变化的 能力，以 及实现 引言 实时处理信息的 速度等 方面常常感到美中不足。 人工神经网络理论在理论研究和应用研究方面己经历了半个多世纪的发 展，作为一个自 适应非 线性动态系统，在处理信 息的 整体活动 性质方面，显示 出人脑的 某些基 本特征: 例如:分布存储和容错 性、 并行操作 性、自 组织和自 适应性、可以 处理不 完整、不精确等知 识问 题. 神经网 络方法模拟形象直觉思 维，用神经网 络本身结 构表达输入与输出关联知 识的隐函数编码，可以实 现有 导师和无导师的聚类学习，特别是网络具有较强的容错性和 自 适应外部变化的 能 力，硬 件实现网 络并行实时处理信息的等特点 在智能计算中 得到广泛应用。 它的优点在于:具有大规模并行处理、网络全局作用、信息分布存储等特点: 通过例子学习，可以确定模型处理信息，以此快速获取知识;具有较强的抗噪 声干扰的 能力和鲁棒性， 其最大的 缺点是 “ 黑 箱” 性3 ， ， 人们难以 理解网 络的 学 习和决策过程 ，而且它是不能确定哪些知识是冗余的，哪些知识是有用的，难 以 评 估 系 统 参 数 的 重 要 性 。 可 见r ou gh 集 和 人 工 神 经 网 络 理 论 既 各 有 特 点， 又 具有很多 共同之处，探索两者的有机结合，取长补短，可望增强智能 计算的能 力。 近年来，企业中大型数据库或数据仓库信息量以爆炸式增长，而且存在噪 声干扰，单纯的使用 r ough 集理论 或者神经网 络均不能 达到预期的效果。 所以 本文通过用r ough 集理 论和神经网络相结合的 数据挖掘，可以 克服r ough 集对 噪声数据敏感的影响，同时可以减少神经网络的训练时间，从而提高数据挖掘 的效率。 本论文主要内容安排如下: 第一章: r ough集理 论概述。本章首先介绍了r ough集的 提出 背景、 研究 对 象、 r ough集 特点 ， 以 及 应 用 现 状。 然后 介 绍了r ou gh集 的 知 识 库， 约 简、 核 和知识表达系统与 决策表等相关概念以 及 r ough集模型的扩展。 第 二 章， r ou gh集 理 论的 数 据约 简 。 本 章 首 先 介 绍了 属 性 约 简 、 分 明 矩阵 ， 区分函数等相关概念。针对约简不一致决策表前经常要分离表中的不一致决策 规则和一致决策规则，本文以判断不一致性决策表的一些命题为基础，给出了 一种不一致决策表的划分方法， 根据该方法可以 把不一致决策表划分成一个完 全不一致的 决策表和一个完全一致的决 策表;接着将 r ough 集理论结 合概率 统 计知识，给出在不一致决策表中提取决策规则的方法， 在决策规则提取过程中， 该方法并不是去除 所有不一致决策规则，而是在满足决策规则力 度、肯定因 子 引言 和覆盖因子的基础上对不一致规则进行筛选， 从 而提高了 决策的 准确性和合理 性; 本章最后结合 教学工作的特点， 利用r ough集的 属性约简 和属性重要性一些 理论，提出 教学质量的 综合评价方法， 它解决了教学质量评价指标的约简以 及 各评价指标权重的 确定的问 题。 此方法有效的消减了 教学指标体系规模和削弱 了设置教学指标权重的主观性。 第三章 r ough 集约简理论 在神经网 络中 应用的 研究。 首先介绍人工神经网 络的一些基本概念， 重点 介绍了 b p神经网络模型以 及算法， 然后给出 r ough 焦神经网络豹简模型以及该模型的应用。 第 1 章 r ough集理 论概述 第1 章 r o u g h 集理论概述 rou gh集理论是一 种处 理不精确、 不相 容、 不完全数据的新型数学工具， 其 主要思想是在保持分类能力不 变的前 提下， 通过知 识约简，导出问 题的决 策或 分类规则。目 前 r ough 集已 被成功应用于 机器学习、决 策分析、 过程 控制、 模 式 识 别 与 数 据 挖掘 等 领 域。 本 章 介绍 经 典r ou gh 集 理 论 的 基 本 理 论及 其 模 型的 扩展。 roug h 集理 论的 提出 背 景“ 经典逻辑中只有真、假二值，但实际上有大量含糊现象存在于真与假之间。 因 此，长期以 来就有许多人致力于研究 含糊概念。 早在19 04年，谓词逻辑的 创 始人g.fr ege 就提出了 含糊一词，并把它归 结到边界线，也就是说在全域上存在 一些个体既不能在其某个子集上被分类， 也不能在该子集的补集上被分类。 20 世纪60年代初，l凡zad 比提出了模糊集，不少理论计算机科学家和逻辑学家， 试图 通过这一理论解决g. fr cg。 的含糊概念， 但遗 憾的是， 模糊集是 不可 计算的， 没有给出数学公式描述这一含糊概念，故无法计算出它的边界线上的具体的含 糊元素数目 。模糊集虽然可以 逼近任意非线性映射， 但它需要先验知识， 而且 至今没有给出完备的数学理论。 时隔20年后的 80年代初，z. p awl ak针对g. f r eg 。 的边界线区域思想提出了 r o u gh se t (r 5 ， 粗 糙 集或 粗集 ) ， 他 把 那 些 无 法 确 认的 个 体 都 归 于 边界 线区 域 ， 而这种边界线区域被定义为上近似集和下近似集之差集。由于上近似集和下近 似集都可以通过等价关系给出确定的数学公式描述，所以含糊元素数目可以被 计算出来，即 在真假二值之间的含糊程度可以 计算，从而实现了 g.fr eg e 的边界 线思想。 zr o u g h 集理论的研究对象 r ough集理论的基本思想是建立在这样一个假设之上的: 对于论域中 的每个 元素( 对象) ，都能够找到某些信息与它相互关联。由相同信息所刻划的元素， 第1 章 r ou助集理论概述 被认为是相对于 这些己 经获得的信息来说是相似的 或者说是不可分辨的。这种 不可分辨关系( 功 d i s cern i b i l i t y r e l at i o n ) 就是r o u gh集理论的数学基础。 由相似的 元素所组成的集合 被称为 基本集( el e m en tary set ) 。它 就是 构成论域的基本知识 颗粒(e ic m ent arykno w l ed geg t 明 ul c) 如果一个集合是由 一个基本集或者几 个基 本集的并集所构成的 话， 那么这个集合就被认为是精确集， 也就是说这类集合 能够由 论域中的基 本知识颗粒完全精确的描述。否则， 就认为 该集合是粗糙的。 r ough集理论是从新的 视角 对知 识进行了定 义， 把知识 看作是 关于论域的划分， 认为知识是有粒度的，它主要用于知识约简及知识依赖性的分析。 r ou沙集的研究 对象是由 一个多值 属性( 特征、 症状、 特性等) 集合描 述的一 个对象 ( 观察、病历等) 集合。对于每个对象及其属性都有一个值作为其描述符 号。 对象、属性和 描述符是表达决策问 题的3 个基本要素。 这种表达形式也可以 看成一个二维表格。表格的行与对象相对应，列对应于对象的属性: 各行包含了 表示相应对象信息的 描述符， 还有关于各个对象成员的 类别信息。 通常，关于 对象的可得到的属性信息不一定足以划分其成员类别，这就使得对象间有不可 分辨性。也就是说属 性给定对象间的等价关系，而这些 等价关系构成了 近似空 间的不分明分 类关系。 rou gh集就是 用不分明对象类形成的上 近似 和下近 似来描 述的。上近似对应了可能属于给定类的最小的对象集合，下近似对应了确定属 于给定类的最大的对象集合。上近似和下近似的差是一个边界集合，它包含了 所有不能确切判定 是否属于给定 类的 对象。 这种处理可以 定义 近似精 度和质量。 3r ough集理论的特点 r ough集的主要 特点是: 具有 较严格的数学定义， 不需要附加 任何先决条 件， 而是直接从给定问 题的 描述集合出 发， 通过不可 分辨关系 ( 等价关系) 确定 给定问 题的 近似域， 从而得到该问 题中 的内 在规律。 r o u gh 集理论的概念在某 种程度上和其他许多处理模糊和不确定 性的数学 工具有一些 相似之处。 但是相对于其他处理不确定性和模糊性的理论 工具而言， r ough集理论有 着许多不可替 代的 优越性。 r ou gh集理论最大的 优势就是 它不需 要任何预备的 或者 额外的 有关数据的 信息。 r ou沙 集能 够有效的处 理下列问 题: 不确定性或者不准确性知识的表示、经验学习并从经验中获取知识、不一致信 息的分析、在保持信息分类能力不变的前提下进行有效的数据约简、近似模式 第1 章 r ough集理论 概述 分类、根据不确定性或者不 完整的知识进行推理、 识别并且评估数据之间的相 互关联程度。 r ough集理 论简单实用， 这也是它能 够在 创立后 不久的时间内 得到 了 迅速的 发展应用的 主要原因。 但是， 必须指出的是， 在使用 r ougb 集方法来 提取规则时，其本质就是对数据集合在保持原有分类能力的 基础上进行约简， 然后归并 相同的数据，从而得出规则，经 过约简后获得的数据集合就是所谓的 被 提 取 的 规 则。 由 此 可 见 ， r ough集 方 法 是 通 过 去除 冗 余 数 据 来获 得 规则 的 。 但 是应该注意到的是， 数 据在一定程度上的 冗余可能提高其容错能力和推广能力。 因 此， r ou gh集 方法 存 在 着 容 错能 力 和 推 广 能 力 较 弱 的 问 题。 并 且， 在 使 用r ou gh 集方 法 进行知 识约 简的 时 候， 数 据集 合必 须使 用知 识 表达系 统 ( kno w led ge r e p r e s e n ta tio n s y s tems ) 的 形 式 表 示。 也 就 是 说 ， r o u g h 集 方 法 一 般 只能 够 处 理 离散型数据，而对于连续型数据必须首先进行离散化处理，而且离散化处理的 好坏 将对 最终的 约简结 果起到很 大的 影响， 这在一定程度上限制了r ough 集方 法的应用范围。 4r ough集的应用现状 rou gh集理论是一种处理含糊和不精 确性问 题的 新型数学 工具， 其基本思想 是在保持分类能力不变的前提下，通过知识约简，导出概念的分类规则。它自 问 世以 来， 无论是在理论或应用上都是 一种新的、最重要的并且是迅速发展的 一门既 有理论又有应用的 研究 领域。 下面介绍r ougb集在一些领域中的 应用。 1) 人工神经网络 ( a n n )。 rou gh集与神经网络的集成，已 引起了许多学者的 关注。这些集成系统在连续属性量化与地质样品分类、语音识别、网络设计， 时间序列分析，企业风险评估、学习、联想和记忆的功能，以及它的高度 自 组 织、 自 适应能力和灵活性而受到自 然科学领域学 者的 广泛重 视151 。 由 于人工神 经 网 络训练时间过于漫长的固 有缺点是制约人工神经网 络实用化的因素之一。 文 献1 6 1 首 先利用改 进的r ougb 集属性约简算法和消除 冗余属性的 方法约 简属性， 进而采用面向对象的概念泛化进一步对数据库进行约简，最后用神经网络训练 进行规则提取，并用南水北调动画演示系统作为实例说明该方法的有效性。文 献7 ， 8 将r ough集 与 人工 神经 网 络 结 合 ， 充分 利 用r o u g h 集 处 理 不 确定 性的 特长，以增强人工神经网络的信息处理能力。 2 ) 从数据库中知识发现( k n o w l e d 只 e d i s cov e rvi n d a t a b a s c ， 叨 d ) 1 9 ， 0 ， k d d 又 第1 章 r o u gh集理 论概述 称数据挖掘( d ata m 而n 乡，是当前人 工智能和 数据库技术交叉学科的研究 热点 之一， r 皿gh集 方法现己 成为 k l d 的一种重要方法， 其导出的 知识精 炼且更便于 存储和使用。 3) 粗糙控制。 r ough集 根据观测数据获得控制策略的方法被称为从范例中 学习( le arnin g ft o mexa m p l es ) ， 属于智能控 制范畴。 基本步 骤是: 把控制过程中 的 一些有代表性的状态以及操作人员在这些状态下所采取的控制策略都记录下 来， 形成 决策表， 然后对 其分析 化简， 总结出 控制规则， 形成为: ifcondi tion 二 n 满足t t 正 n 采取d e ci sj on= m。 r ough集方 法是一 类符 号化分析方法， 需要将连续 的 控制变量离散 化， 为此z. p aw】 ak 提出了 粗糙函 数的 概念， 为 粗糙控制打下了理 论 基础。文仁 n， 1 2 3 应用粗糙控制研究了“ 小 车 到 立摆系 统” 这一 经典控制问 题， 取得了 较好的结果。 在过程控制领域， 文1 3 应 用r ough集方法成功地提取 出了水泥窑炉的控制规则。 粗糙控制的优点是简 单迅速、 实现容易、不需要象 fuzz y 控制那样进行模糊化和去模糊化。 因此在特别要 求控制器结构与 算法简单 的场合，采取粗糙控制较为合适.另外，由于控制算法完全来 自 观测数据本身， 其决策和 推理过程可以 很容易被检验和证实。 一种新的 有吸引 力的控制策略“ 模 糊一粗糙 控制伍比 z y- r oughco 咖 d” 正悄然兴起， 其主要思路是利用rou gh集获 取模糊控制规则。 4)股票数 据分 析。 文 1 4 应用 r ough集方法分 析了 十年间 股票的历 史数据， 研究了股票价格与经济指数之间的依赖关系，获 得的预测规则得到了华尔街证 券交易专家的认可。 5 )决策 分析1 均 。r 。 。 gh集的决策规则是在分析以 往经验数据的 基础上得到 的。 r o u g h 集允许决策对象中存在一些不太明确、不 太完整的属性， 弥补了 常规 决策方法的 不足。 希腊工业发展 银行eteva 应用r ough集理论协助制定 信贷政策， 是r 。 。 gh集多 准则 决策方法的一个成功范例。 6) 医疗诊断。 r o ugh 集方法根据以 往的病例归 纳出 诊断规则， 用来 指导新 的病例。 现有的人工预 测早产的准确率只有1 7 卜3 8 % ， 应用r o u g h 集理论则可提 高 到 6 8 % 一 9 0 % 16 1 。 7 ) 知识获取和 机器学习。从 训练样 例中学习 得到的规则形式的 知识， 可以 用到基于 规则的专家系 统中。这些规则比原始输入 数据包含的 信息更为 概括， 对于一些和原始数据并不匹配的新样例，利用规则可以进行正确的分类。美国 k a n s as大学开发的实验学习系统，名为基于r ough集的样例学习系统( l ea rn i ng 第1 章 r ough集理论概 述 fromexalnp esba se d onro u ghse ts ， 简 称 l e r s)。系 统 的 规则 产生 有2 种 方式 : 机 器学 习方式和知 识获 取方式 ! 17。 前者 产 生 一 个 足以 覆 盖 所 有数 据的 规 则集 ， 后 者则产生隐含在数据中的所有规则， 规则集也因此较前者更大些。当专家系 统 需要在不完整的 信息下决策时，知识获取方法通常比机器学习 方法更为有效。 ler s 系统己 被n a s a 应用于开发空间站上的医疗决 策专家 系统。 比r s 的另一 个 应用是研究全球气候变化。它从太阳 能量接收、火山活动、二氧化碳残留 趋势 等属性描述的 数据中 导出了 描述影响全球温度的规则，使该领域专家获得了 有 关全球气 温变化机 制的 新发现115 。 rou gh集对于人 工智能 和认知 科学 似乎是十 分重要的， 尤 其在机器学习、 知 识获取、决策分析、数据库的知识发现、专家系统、决策支持系统、归纳推理、 矛盾归结、 模式识别、 模 糊控制及其他各个方面的应 用，它都为之提供了 一种 很有效的新的 数学 方法， r ough集自 提出以 来一 直得到模糊数学的 创始人zad eh 的重视， 并给与很高的评 价，把 他 列 入 他新 提 倡 的 软 计 算( so ft c o m p ut in 乡的 基 础理论之一。由 此可见， r o u gh集理论及其广泛应用越来越受到重视。 sr o u g h 集的基本概念 5 ， 1知识与知识库 rou gh集 理 论 认 为 知 识 ll， ll 是 一 种 分 类 能 力 ， 知 识 是 人 类 通 过 分 类 获 得 的 。 从简单到复杂的分类模式贯穿在人们获取、表达、运用知识的全过程，在理解 知识这个概念中，分类是一把钥匙。知识是经过加工、整理、解释、挑选和改 造而形成的信息，是人类在改造现实世界的实践过程中关于认识和经验的总和。 设 u，小是我们要研究的对象全体组成的有限集合， 称为论域。 u上的任意 子集 x称为 u中的一个概念 ( 或范畴) 。我们规定空集中也是一个概念 ( 或范 畴) 。 我们把u上任何一组概念的集合称为关于u的抽 象知识， 简称知 识。 实 际 上我 们 只研究能形成划分的知识。 所谓 划 分 定 义为 : 一 个 划 分a 一 x l ， x z ， 一 x ， ; 其 中 x ， 二 u ， x， 。 ， x ， n x ， 一 巾 ， ， ， j ， ， j 一 瓦 2 ， n 写 x ， 一 u u上的一组划分的集合称为关于 u 的一个知识库，知识库代表了人们的基 本分类技巧。这里应注意的是，我们对于对象的知识是清楚的，即不存在模糊 不清的知识。一个知识库也就是一个关系型系 统 k 二 ( u ，r)，其中u是论域， r 第1 章 rou 沙集理论概 述 是 u上的一组等价关系。 定义l l 设r是u上的 等价 关系， u 爪形成了 对u的 划分，即u上的商 集， u 瓜是关于r的 等价类的集合。 这里也可以 看 成是一 个信息granul ar 。 【 x r ， x 任 u ， 表示等 价类中的 一个子集。 定 义l z设p 二 r ， 且p #小 ， 则ind( p) 二n p ， 也 是 一 个等 价 关 系， 称 为 p 一 不 分 明 关 系 ， 有 x 1 。 (p ) 二 总lx l 定 义1 . 3给定p a w l 欧近似空间k 二( u ， r ) ， 非空子集p 互 r ，p称为k 中关 于u的p 一 基本知识， q 任 r ， q称为k中关于u的住原始知识; u 八 n d ( p ) 的等价类称作 p 基本概念或基本范畴，u /q 称作q原始概念或原始范畴。 例11 给定一玩具积木的集合u = x ; ， x z ， ， ， ， ， xs ， 并假设这些积木有不 同的颜色 ( 红、黄、蓝) ，形状 ( 方、圆、三角) ，体积 ( 小，大) 。因此，这些 积木都可以用颜色、形状、体积这些知识来描述。例如一块积木可以是红色、 小而圆的，或黄色、大而方的等。如果我们根据某一属性描述这些积木的情况， 就可以按颜色、形状、体积分类。 按颜色分类: xl声 3 沐 ， 一红; x z ，x 月 蓝; x ， ， 勒 ， x 一黄。 按形状分类: x l ， 、 5 一圆; x z ， x 6 一方; x ， ， 石 ， 勒， x s 三角。 按体积分类: x z ，x 7 ， 义 1 ，x 3 ， 大; 叉 匆， xs，x 石 一刁 、 。 定 义三个等价关系 ( 即 属性) : 颜色r l ， 形状r z 和体积r 3 ，通过 这些等价 关系， 可以 得到下面三个等价关系: u 瓜1 二 x l ， x 3 ，x ， ， x z ， x 小 x s ， x 6 ， x s ， u 瓜2 二 x l ， x s ， x z ， x 6 ， x 3 ， x4，x 7 ， x s ， u 瓜。 二 x z ， x 7 ，x s ， x l ，x 3 为， x s ，丸 。 第1 章 r ough集理论概述 这些 等价类是由知识 库k= ( u ， r l ， rz， r 3) 中 的 初 等 概 念( 初 等范 畴 ) 构成的。 基 本范畴是初等范畴的交集构成的， 例如下列集合: x ， ， x 3 ， x 7 门 x 3 ，x 4 ， x : ， x s 二 x 3 ， x 7 ， x z ， 勒 门 x z ， x 6 二 x z ， x ， ， x 6 ， x s 门 x 3 ， x ; ， x 7 ， x s 二 x s 。 它们分别为的基本范畴，即:红色三角形，蓝色方形，黄色大三角形。 下列集合: x l ， x 3 ， x 7 门 x 3 ， 勒 ， x ， ，x s 门 x z ， x 7 ，x s 二 x ， ， x z ， x ; 门 x z ，x 6 自 x z ，x 7 ， x s 二 x z ， x s ， x ， xs 门 x 3 ， x 4 ， x : ，x s 自 x z ， x 7 ，x s = x s 。 它们分 别为 r l ， r z ， r 3 的基 本范畴， 即: 红色大三角形， 蓝色大 方形， 黄 色大三角形。 定义1 .4 设k 二 ( u ， r ) ， k 二 ( u ， r ) 为两个知识库， 若ind ( r ) = i n d ( r ， ) 或u 爪= u /r， ， 则称k和k 是等价的， 记 作k 三k 。 若水d ( r ) c 以d ( r ) ， 则称 知识r是知识 r的细化。也就是知识 r比知识 r ， 更精细。 对于 知识库称 ( u ， r ) ，任 一子 集x 二 u ， r 是u上 任一 等 价 关 系 ， 那 么 当 x能表示成 r基本范畴的并时，称 x是 r可定义的，否则称 x是 r不可定 义的;对 于后一种情况我们用r ough集 11 的 方 法 来 解 决。 定义l s r 任 刃 峙 d ( k ) 你上所有等价关 系的集合) ，定义两个精 确集: 丑( x )= u v 任 u /r i v 二x 或 丑闪二 x 任ul x l ， 互x 双 ( x ) 二 u y 任 tj /r y 门 x ，。 或 r ( x)= x 任 tjl x 1 r 门 x ，。 1 分别称为x的r下近似集和r上近似集。二元组丑 ( x)和r (x ) 就 可 以 用 来 描 述r o u g h 集x 。其中下近似集是集合x中 包含的 基本范畴的最大并集， 而上近 似集则 是包含x的 基本范 畴的并 集中最小 的一个。 下近似集就是所谓的正区 域， 即p o s ， ( x ) 二 丑 (x)， 即依据我们的知识能够 确定是 属于集合x中的 元素的 集合。 在上近似集中 除去包含在下近似集中的 元素构 成了边界线集，即 依据我们的 知 识不能完全确定 其归属的元素的集合，记为b nd: ( x ) 二 r ( x) 一 丑 ( x)。 当b nd， ( x ) 是空集时，则x被称做可定义的， 否则被称做r o u gh的。 集合 ( 范畴)的不精确性是由于边界域的存在而引起的。集合的边界域越 第1 章 r ou 沙集理论概述 大，其精确性越低。为了 更准确 地表达 这一点，我 们引入精度的概念由于等价 关系r定义的集合 x的近似精度为 ( 1 ， 1) 回网 x 其中x 沪 ，!x 表 示 集 合 x 的 基 数 。 精度a ， 伏) 用来反映我们对于了 解集 合x的知 识的完全 程度。显然对每一 个r和x二 u有0 。 : (x) 1 。 当a ， ( x ) = 1 时， x的r边界域为空集， 集合x 为r可定义的;当。 : (x) 0) ， 称 为x 的 上 近 似集 . 由 此 可以 看出 ， r ou gh集定 义 的 两 种 方 法 都 是 强 调r ou gh集 概 念 的 各 个 方 面。由 近似定 义带来了 r ough 集的拓扑结构， 而隶属函数方法则 强调它的数 值 第1 章 r o u 助集理论概述 性质， 用概 率术语 可解释为: 在y 任 x的条件下，y 任 ! x， 的条件 概率。 自r ough集理论提出以来， 大致从两个方面研究r ough集理论及其应用 一方面是对r ough集的理论研究， 发 表了r ough集代 数， r ough集拓及其性质， r ough逻辑及 处理 近似推理的逻辑 工具等论文: 在 这些论 文中 充分论述了rou gh 集与fuzz y 集， 证据理论与r ough集理论之间的关系，它们 也建立了r ough集 与概率逻辑， r ough集与模态逻辑 等统一框架。 另 一方面， r ough集的研究者们 很重视 它的 逻辑研究， 发表了 一系列的rou gh逻辑方面的论文。 我们知道由 于经典r ough集的定义 所限，所以 经典r ough集的处理对象也 是有限的。 从代数、 逻辑或其他角度 对经典ro“ gh 集进行解释和扩展历来都是 rou gh 集 研究 过程中的 热点问 题.比 如针对经典 r ough 集只能处理属性值完备 的信息系 统， 人们提出了 在不完备信息系统下的r ou沙集方法，对 经典r ough 集的 相关概念进行适当 扩展，如文【 19 针 对经典 r ough 集只能处理离散数据， 人们对连续变量作了离散化处理;针对偏序关系，文 2 0提出了偏序决策表的 数据分 析与决策规则 挖掘;针对经典 助u gb 集在分 类上的 限制， 人们提出了可 变精 度的r o u gh集12 ， 1 、 r o u g 卜 f u z z y 集模型122和凡zz y 一 枷 gh集 模型 1 23 ; 文 2 4 在zi al k o 提出的 可变精度的r ough集模型基础上提出了 双可变精度的r ough集 模型; p awl ak 在实数集 上引入了r ough集的概念， 并由 此提出了 一系列与拓扑 学和 分析学中相对应的诸如闭包、 收敛、 连续、 rou gh 不 动点、 r ough实函数等 概念 四; 文 261 在此基础上对r ough连续映射做了 进一步的研究， 得出 了一些 与代 数学中类似的结果;文 2 7提出了r ough陪集 和r ough不变子群的 概念并 由此 得到了 一些类似于群论中的一些重要结果;文 2 8 在此基础上对 r ough 陪 集和r ough不变群进行了 进一步的研究并提出 了r ough双陪集的 概念等等。 rou gh 集理论在许多实际生活中都有应用，利用r ough 集理论处理的问 题 包括数据库中的数据约简，数据相关性的发现，数据意义的评估，由数据产生 决策控制算法，数据的近似分类，数据中的相似性或差异性的发现，数据中范 式的 发现以 及因果关系的发 现。目 前， 在世界范围内 基于 r ou gh 集理 论的数据 挖掘技术的研究 取得了 令人瞩目 的 成就，己 经成 功应用到了 市场、工 业、 金融、 工程与科学研究、 医疗保险、 司法等多种领域，对于它的研究具有重大的理论 意 义 和广阔的应用前景。 第1 章 r ough集理论概述 5 ， 2知识约简 知识约 简是 r oug b集理论的 核心内 容之一。 众所周知，知 识库中的知识 在 不同的情况下重要性并不是同 等的，甚至其中某些知识是 冗余的。所谓知识约 简就是在知识库分类能力保持不变的条件下，删除 其中不 相关或者不重要的 知 识。知识约简在信息系统分析和知识发现等领域具有十分重 要的应用意义。 知 识之间的依赖性决定知识是否可以进行约简，根据依赖性所定义的知识的重要 性 往 往 是 知 识 约 简 的 重 要 启发 式 信息 。 r ou gh集 理 论 的 两 个 最 基 本问 题 是 : 知 识 约简ii，lej 和数据的依 赖性。 知识约简就是考察 近似空间中 每个等价关系是否都是 必要的，能 不能 在保持原 有分类的基础上尽可能地删去冗余的 知识。知识约简 有两个基本的概念: 约简(r edu ct ) 和核( core ) 。直 观的 看， 约简就是指知识的本质 的部分，它足以定义所考虑的知识中所遇到的所有基本概念。而核是知识中最 重要的部分。 一、约简与核 定 义 1 .7设 r是一 等价关系族， r e r ， 当州d ( r)二 ind(r 一 r ” 时， 则称关系 r 在族集r之中是可省的 ( di 印 ens abl e) ; 否则 就是不可省的。 定 义l s 等 价 关 系 族r 是 独 立 的 (i nd ep en d en t) ， 当 v r 任 r ， r 是 不 可 约 去 的 。 否则称 r是依赖的或者非独立的。 定 义1 .9 等 价 关 系 族q 二 p ， 若帅 ( q ) 二 ind( p)， 且q是 独 立 的 ， 则 称q 是 关系 族集p 的 一个约简， p 中所有不可约去的等价关系的集合 称p的 核， 记为c o r e ( p ) 。 显然，约简不唯一，对于 p 可能有很多个约简。 下面的定理是有关约简和核的之间关系的重要性质: 定理 l l 等价关系族 p的核等于 p的所有约简的交集，即 c o r e ( p)二 n r e d ( p) 其 中r e d (p) 是p 的 所 有 约 简 的 集 合。 从上面的定理可以 看出，核的 概念有两个方面的意义。首先，可以 作为计 算所有约简的基础，因为核能 够包 含于每个约简之中，并且其 计算是 直接的; 其 次，核可以解释为知识最重要部分的集合，在进行知识约简时不能够将它删除。 在实际应用中，一个分类相对于另一个分类的关系十分重要，因此引入知 识的相对约简( r e l a t i v er e d u c t ) 和相对核( r e l a t i v ec o r e )的概念，首先需要 第1 章 rou gh集理 论概述 定义一个分 类关于另一个分 类的正区 域。 定义l 1 0 设p和 q是全域u上的 等价关系族集， q的p 一 正区 域， 记作 p o s p( q) ，定义为 p o s p( q)= u 尽x) ( 1 . 3 ) x曰了 j 口 q的p- 正区域是全域u的所有那些 使用分类u /p所表 达的 知识，能够正 确 地分类于u / q的等 价类之中的对象的集 合。 定义1 . 1 1 设p 和q是全 域u上的