（计算机软件与理论专业论文）基于粗糙集理论的不完备决策系统数据挖掘方法研究.pdf

摘要 粗糙集理论是2 0 世纪8 0 年代初由波兰数学家首先提出的一种刻画不确定和 不完备知识的数学工具，能有效地分析和处理不精确、不一致、不完整等各种信 息，并从中发现隐含的知识，揭示潜在的规律。经典粗糙集理论以完备系统为研 究对象，以等价关系为基础，通过等价关系将论域划分为互不相交的等价类；然 而，在现实生活中，由于数据测量的误差，对数据理解或获取的限制等原因，使 得在知识获取时往往面临的是不完备系统，即可能存在部分对象的一些属性值未 知的情况，这就极大地限制了粗糙集理论向实用化方向发展。因此，如何从不完 备决策系统中应用粗糙集理论获取知识己经成为当前的一个重要研究课题。 本文首先综述了数据挖掘的原理和现状，从数据挖掘和知识分类的角度出 发，探讨了数据挖掘的相关概念、工作步骤和关键技术。深入分析了粗糙集的基 本理论以及粗糙集理论在不完备系统中的拓展。然后基于相容关系研究了把信息 论和集合论应用于不完备决策系统属性约简的方法，以及粗糙集理论与遗传算法 相结合的不完备决策系统属性约简算法，通过实验数据验证所提出的约简算法， 得到不完备决策系统相对应的约简结果。接下来研究了在属性约简后的决策表中 提取最优规则的算法并通过实例分析验证了算法的正确性。 本文最后设计和开发一个基于粗糙集理论的不完备决策系统的数据挖掘模 型，应用本文算法进行属性约简和最优规则提取，部分实现该模型的功能。 关键词：数据挖掘；不完备决策系统；粗糙集；属性约简；条件信息熵；遗传算 法；规则提取； a b s t r a c t r o u g l l 瞅t h 吖，i m r o d u c 酣b yp a w l a kz i nt l 把e 盯i y1 9 8 0 s ，i san e w m a t h e m a t i c a lt o o iu s e df o rd e a l i n gw i t hv 卿伽e 鹳a n du n c e n a i mi n f o 姗a t i o nt o d i s v e ri m p l i c i ti m o w l e d g eo rr e v e a ll a t e n tl a w s c i a s s i cr o u g t ls e tt h e o n rb a s e do n e q u i v a i e n c er e l a t i o nt a i k e sc o m p l e t es y s t e m 鹋o b j e c to fs t i l d y ，锄dd i v i d 部t h er e 西o n i n t os o m e n - i n t e 硌e c te q u i v a l e n c ec i a s s ：b u t i nt t 峙r e a ll i f 崴b e c a u s eo f t l 尬e 盯o r si n d a t am e a 娜r i n g ，u n d 盯s t 孤l d i n go fd a t a o rt h em s t r i c t i o ni i id a t ac o l l e c t i 锄，i t 啪 m a i 曲忙d e c i s i o f i - m a b n gs v 髓e mi n c o m p l e t e ，t h a ti s ，v a l u eo fa 晡b u t i o no fs o m e d b j e c t si su n k n o w i l w h i c hr e s 嘶n sd e v e l o p m e 眦o ft i 地t t l e o r yt op 豫c t i c a ld i r e c t i s oh o wt oa c q u i 佗l m o w l e d g e 蕾b mi n c o m p l e t ed i s i o n - m a i 【i n gs y s t e mh 船b e e na 咖c i a lr e s e a f c ht o p i cf e c 哪l y t h ep a p e r f i r s t i y ，刚m si l pt h ep f i n c i p l e sa n dm a i i t yo fd a t ai i l i n i n 岛锄d d i s c l i s s 懿t h ec o n e s p o n d i n gc o n p t s w o r k i n gs t e p sa n dk e yt e c h l o g i e sa b o u td 缸a m i n i n g 硒mt h ev i e w p o i mo fd 砒ai i l i n i n g 柚dl ( i l o w i e d g ec i 嬲s i f i c a l i o l l m a i 【i n ga d 唧姗l y s i sa b o u tb a s i ct h r i e sa n de ) ( t e n s i o ni nt h ei n c o m p l e t es v s t 锄t h e i l ， b a s e do nc o m p a t i b i er e i 砒i o l i 咖d yo fc o m b i n i n gi l l f 0 m a “o nt h e o r yw i t hs e tt t l e o n r 锄ds t i l d yo fc o m b i n i n gr o u g l ls e tt h r y 、) l ，i t hg e n e t i ca l g o r i t h mf o rr e d u c l i o nh a v e b e e nm a d e a l g o r i t h m s 硒rr c d u c t i o na r ev a l i d a t e db ye x p e r i m e m s ns h o w st h a tt h e s e a l g o r i l h m sc a n 丘n dc o r t e s p o n d i n gr e d u c t i o nr e 娜i t s n e ，【t “p i l t sf o 嗍d a na i g o r i t h m t h a t啪q u i r ed i r t l yd e c i s i o n m a k i n gn l l 铭i nd i s i o n m a l 【i n gt a b l e l a l g o r i t h m sa r ev a l i d a t e db ye x p e r i m e m s t h er e 蛐h so fw i l i c hs h o w 帆t h e a l g o r i t h m st i l mo m g h t a tl a s t ，i te s t a b l i s h e sag y s t e mf o rd a t am i n i n gi ni n m p l e t ed e c i s i o l l m a k i n g s y s t e i i l 印p i y i n gt h ea 】g o r i t h m sp u tf - o n 甜di nt h ep 印如r 删t i b u t i o nr e d u c t i o n 柚d o p t i m u mm l e 四【t i 砌i o nt o 如i f i l lt l l ef h n c t i o n so f t h em o d e l k e yw o r d s ： d a t a m i n i n g ；i n c o m p i e t ed 代i s j o n - m a k n g | y s 比m ；m u g hs h ； a n r i b u t i o nr e d u c t i o n ；c o n d i 6 0 n mi n f o r m a t i o ne n t m p ”g e n e t i c a i g o r j t h m ；邝l e “t m c t i 伽k n 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本 声明的法律后果由本人承担。 作者签名：勿忉褴日期：2 0 0 7 年夸月殆日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密冈。 ( 请在以上相应方框内打“”) 作者签名：勿1 乔菇& 日期：2 0 0 7 年钥巧目 导师签名：要歹 日期：2 0 0 7 年牛月艿日 长沙理工大学硕士论文 1 1 研究的目的和意义 第一章绪论 随着计算机、网络和通讯等信息技术的高速发展，信息处理在整个社会规模 上迅速产业化，信息爆炸或信息泛滥是当今数字化社会面临的一个巨大挑战。商 业上对条形码的普遍使用使得很多行业每天都积累了大量的数据。先进的现代观 测仪器的使用导致每天产生巨量的科研数据，大规模数据库的广泛使用和 i n t e r n e t 的迅猛扩展，使得全球范围内数据库中存储的数据量迅速增大，并且信 息系统中数据的不完备性更加显著。海量杂乱的数据背后隐藏着许多重要的信息， 目前的数据库系统虽然可以高效地实现数据的录入、查询、统计等功能，但无法 发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。缺乏 获取数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。人们 迫切需要新的技术和工具对其进行深入分析，以便从海量的数据中智能地、自动 地抽取出有价值的知识或信息来帮助人们进行商业分析和科学研究。一个新的研 究领域一一知识发现( k n o w l e d g ed i s c o v e r y ) 应运而生。由于蕴涵知识的信息大多 数存储于数据库中，数据库知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s 。 k d d ) ，又称数据挖掘。1 ( d a t am i n i n g ，d m ) 成为当前知识发现的主要研究课题， 而粗糙集理论作为一种应用于数据挖掘中的数学工具n “1 有着它不可替代的优点。 因此研究基于粗糙集理论的不完备信息系统数据挖掘有着极其重要的理论意义和 现实意义。 1 2 数据挖掘概述 1 2 1 数据挖掘的定义 数据挖掘就是从大量的、不完备的、有噪声的、模糊的、随机的实际应用数 据中，提取骆含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的 过程。公认的k d d 7 1 定义为：k n o w l e d g ed i s c o v e f yi nd a t a b a s e si st h en o n t r i v i a l p r o c e s so fi d e n t f y i n gv a l i d ，n o v e l ，p o t e n t i a l l yu s e f h l ，a n du i t i m a t e l yu n d e r s t 锄d a b l e p a t t e r n s i n d a t a 。即“从数据中识别出有效的、新颖的、潜在有用的，以及可以最 终被理解的模式的非平凡过程”。 从商业角度，数据挖掘被定义为：是一种新的商业信息处理技术，其主要特 点是对商业数据库中的大量业务数据进行抽取、转换、分析和其它模型化处理， 从中提取辅助商业决策的关键性数据。多数情况下，数据挖掘和k 叩被视为等同 长沙理工大学硕士论文 的。有学者认为数据挖掘是k d d 的一个处理阶段，k d d 一般在科研领域使用较多， 在工程应用领域多称之为数据挖掘。 1 2 2 数据挖掘的目的 数据挖掘技术是人工智能”1 “、统计理论。钉和数据库“引技术相结合的产物， 具有较为广泛的应用前景。专家预测数据挖掘在未来l o 年内会有革命性进展。数 据挖掘的目的是从数据中找出有意义的模式。 1 2 3 数据挖掘的方法 目前对数据挖掘方法的研究空前活跃，每年都有大量的研究文献涌现，从不 同角度、不同层面提出不同的挖掘方法。现有的数据挖掘方法主要有以下几种： 1 ) 决策树方法“。“1 利用信息论中的互信息“1 ( 信息增益) 寻找出数据集中具有最大信息的字段， 建立决策树中的每一个结点，再根据字段的不同取值建立树的分支的过程，即建 立决策树。国际上最有影响的决策树方法是q u i n l a n 研究的i d 3 方法“。 2 ) 神经网络方法“” 它模拟人脑神经元结构，以m p 模型和h e b b 学习规则为基础，建立了三大类神 经网络模型。前馈式网络，以反向传播模型、函数型网络为代表，用于预测、模 式识别等方面。反馈式网络，以h o p f i e l d 离散模型和连续模型为代表，分别用于 联想记亿和优化计算。自组织网络，以a p t 模型，k o h o i o n 模型为代表，用于聚类。 3 ) 模糊集合论方法心”“ 利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模 糊聚类分析。模糊性是客观存在的，系统的复杂性越高，模糊性越强，这是z a d e h 总结出的互克性原理。 4 ) 遗传算法0 2 】 是模拟生物进化过程的算法，由选择、交叉和变异三个基本算子组成。其中， 选择是指从父代中选出生命力强的个体，产生子代种群的过程；交叉是选择两个 不同的个体的部分基因进行交换，形成两个新的个体；变异是对某些个体的某些 基因进行突变。遗传算法己在优化计算和分类机器学习等方面发挥了显著的作用。 5 ) 租糙集方法“。“2 “ 粗糙集理论是8 0 年代初z p a w l a k 针对gf r e g 的边界域思想提出的，基于给定 训练数据内部的等价类，用上下近似集合来逼近数据库中的不精确概念。它用于 分类，可以发现不准确数据或噪声数据内在的结构联系；用于特征归约，可以识 别和删除无助于给定训练数据分类的属性；用于相关分析，可以根据分类任务评 估每个属性的贡献或意义。其主要思想是在保持分类能力不变的前提下，通过知 识约简，导出问题的决策或分类规则。 2 长沙理工大学硕士论文 此外，数据挖掘方法还有：云理论、统计分析、值预测等。数据挖掘是数据 领域中一个高速发展的分支，它应用于不同的领域，其它领域的知识和理论也广 泛地应用到数据挖掘的研究中，结合实际需要，往往能开发出更高效的算法。 1 2 4 数据挖掘的步骤 数据挖掘的实施大体可分为以下三步： 1 ) 数据准备( d a t ap r e p a r a t i o n ) ，本阶段包括两步： 数据集成：从操作型环境中提取数据并加以集成，解决语义的二义性问题， 消除脏数据。 数据选择和预分析：迸一步缩小数据范围，提高数据挖掘的质量。 2 ) 数据挖掘( d a t am i n i n g ) 首先决定如何产生假设，是让数据挖掘系统为用户产生假设，还是对于数据 库中可能包含的知识提出假设。前一种称为发现型的数据挖掘，后一种称为验证 型的数据挖掘；然后选择合适的工具，利用前面提到的数据挖掘方法挖掘数据库 中的知识；最后证实发现的知识。 3 ) 规则表述( r u l ep r e s e n t a t i o n ) 数据挖掘将获得的信息以方便用户理解和观察的方式反映给用户，这时可利 用可视化工具。这些基于不同数据集合的分析结果除了通过可视化工具提供给用 户外，还可以存储在知识库中，供日后进一步分析和比较。 1 2 5 数据挖掘发展概述 自1 9 8 9 年第十一届国际联合人工智能学术会议上提出知识发现以来，知识发 现和数据挖掘逐渐成为计算机领域的一个热门课题。数据挖掘界于1 9 9 5 年在加拿 大召开了第一次数据挖掘国际学术会议，并在1 9 9 8 年建立了一个新的学术组织 a c m s i g k d d 。数据挖掘界的专业学术期刊“d a t am i n i n ga n dk n o w l e d g e d i s c o v e f v ”从1 9 9 7 年开始出版发行。还有众多国际学术期刊刊载知识发现与数 据挖掘的论文。如i e e e 的k n o w l e d g ea n dd a t a e n g i n e e r i n g 会刊。a c m 数据库系统 汇刊，a c m 杂志，信息系统，v l d b 杂志，数据与知识工程，智能与信息系统国际 杂志乜副等。 到目前为止，数据挖掘的国际会议主要有：“a c m s i g m o d 数据管理国际会议” ( s i g m o d ) ，“超大型数据库国际会议”( v l d b ) ，“a c m s i g m o d s i g a r t 数据库原 理研讨会”，“数据工程国际会议”，“扩展数据库国际会议”，“数据库理论国际会 议”。“信息与知识管理国际会议”，“数据库与专家系统应用国际会议”，“数据仓 库与知识发现国际会议”，。数据库系统高级应用国际会议”，“知识发现与数据挖 掘太平洋亚洲会议”，“数据库中的知识发现原理与实践欧洲会议”，“机器学习国 际会议”，a c m 计算学习理论会议”，“人工智能国际联合会议”，“美国人工智能 长沙理工大学硕士论文 学会会议”等。 目前，世界上比较有影响的典型数据挖掘系统有：i b m 公司的i n t e l l i g e n t m i n e r 、s a s 公司的e n t e r p r i s em i n e r 、s g i 公司的s e tm i n e r 、s p s s 公司的 c l e m e n t i n e 、s y b a s e 公司的w a r e h o u s es t u d i o 、r u i eq u e s tr e s e a r c h 公司的s e e s 、 b u s i n e s so b i e c t s 公司的b 0 、f o r d s y s t e m s 公司c m 盯，还有c o v e rs t o r y e x p l o r a ， k n o w l e d g ed i s c o v e r vw o r k b e n c h ，d bm i n e r q u e s t 等拉 。 与国外相比，国内对数据库中知识发现的研究稍晚，1 9 9 3 年国家自然科学基 金首次支持该领域的研究项目，目前8 6 3 、9 7 3 以及地方自然科学基金都开始支持 数据挖掘项目，国内的许多科研单位和高等院校竞柜开展知识发现的基础理论及 其应用研究，其中比较著名是中科院计算所史忠植研究团队，复旦大学朱杨勇开 发团队，还有大量的研究单位投入到知识发现与数据挖掘中来，如清华大学、南 京大学、四川大学、中科院自动化所、上海交通大学、西安交通大学，东北大学 等。知识发现和数据挖掘起步虽然晚，但是现在进入空前热烈的研究氛围：在知 识发现与数据挖掘领域已经有多篇硕士、博士论文；中国目前虽没有专业的知识 发现与数据挖掘杂志，但计算机学报、软件学报、计算机研究与发展、模式识别、 控制与决策等杂志上刊登有数据挖掘的论文；国内的知识发现会议主要集中在数 据库学术会议”，“计算机应用联合学术会议”，“中国机器学习学术会议”等。 1 3 粗糙集理论概述 自z p a w l a k 提出粗糙集理论后，直到1 9 9 0 年前后，由于该理论在决策与分析、 模式识别、机器学习、知识发现等方面的成功应用，逐渐引起了国际上学术界的 广泛关注。1 9 9 1 年z p a w l a k 的专著r o u g hs e t s t h e o r e t i c a la s p e c t so f r e a s o n i n g a b o u t d a t a “”的问世，标志着粗糙集理论及其应用的研究进入了活跃时期。1 9 9 2 年在波兰召开了第一届国际粗糙集研讨会，以后每年都有以粗糙集理论为主题的 国际研讨会。1 9 9 5 年a c mc o m m u n i c a t i o n 将粗糙集列为新浮现的计算机科学的研 究课题。如今粗糙集理论己成为信息科学最活跃的研究领域之一。我国在该领域 的研究起步较晚，但已形成了若干专门的研究机构，如中科院自动化研究所、浙 江大学智能研究所等。此外，还有很多高校自发进行研究，如清华大学、西安交 通大学和重庆邮电学院等高校。目前国内与之相关的国家自然科学基金项目有： 重庆邮电学院王国胤教授主持的“基于r o u g h 集理论的不确定性信息处理研究” ( 编号：6 0 3 7 3 “1 ) ，浙江海洋学院吴伟志教授主持的“模糊与随机环境下的粗糙 集理论与知识获取”( 编号：6 0 3 7 3 0 7 8 ) ，山西大学梁吉业教授主持的“粗糙集理 论中的不确定性，模糊性与知识获取”( 编号：6 0 2 7 5 0 1 9 ) 等。同时，国内外学者 在海量数据挖掘的研究上也做了大量的工作，目前典型的对海量数据集进行挖掘 的方法主要有基于并行“引和基于抽样。们两种，我国的研究者们也取得了一定的成 4 长沙理工大学硕士论文 果。“”1 。这些方法分别解决了对大数据集的快速划分和数据抽样等问题，但这些 工作并没有利用粗糙集理论对海量数据进行处理的优势。 总的来看，完备信息系统情形下的粗糙集理论基础的研究日臻完善，已基本 构成了较为完整的理论基础，在各个方面的应用也取得了显著成效。但在某些特 定的现实情形( 如模糊、随机、空值等) 下，都还有必要从理论上、方法上进一步 深入研究。 1 4 不完备信息处理的研究现状及分析 在日常的信息化任务中，各层管理人员使用的主要是数据库( 表) 。这些数据 库不仅是巨大的，而且还常常遇到数据缺损( 信息不完备) 情况。例如，在为医学 诊断提供辅助决策支持的应急诊断智能系统中，智能系统辅助决策能力的强弱取 决于它从大量的病例数据库中获取的知识。而在数据库中，患者的症状一般是通 过病人描述、仪器检查、医生观察等方式来获得。但由于病人描述不清楚、或者 病人不适合做某项仪器检查、或者由于当时时间紧迫来不及做详细检查等原因， 病人( 对象) 的某些症状( 属性) 的描述就不能够获得。这种情形在银行贷款、供应 链管理、交通管理、故障诊断等领域也是不可避免的。 传统的数据挖掘技术对数据的质量要求较高，只能在精确集下进行数据挖掘。 对一些含有模糊信息的数据需要进行改变或摒弃噪声数据之后才可以进行处理， 这样很容易造成信息的丢失，而粗糙集却可以对这一类信息进行挖掘。粗糙集理 论作为集合论的扩展，其主要研究领域之一就是在信息不完备情况下的数据挖掘 技术。因此，基于粗糙集的数据挖掘技术在不完备信息系统领域的研究具有重要 的意义。 1 5 本文的工作 目前，国内外针对不完备系统数据挖掘的研究，尤其是在不改变原系统信息 成分的前提下进行挖掘还比较少。本文主要针对不完备系统的数据挖掘做了一些 研究，具体内容如下； 1 ) 综述了数据挖掘、粗糙集理论和不完备系统的研究现状，分析了粗糙集在 不完备系统数据挖掘中的优势； 2 ) 分析和研究基于经典粗糙集理论的属性约简，研究了粗糙集理论在不完备 系统下的拓展； 3 ) 在相容关系的基础上，把条件信息熵和和遗传算法应用到不完备系统，分 别探讨了不完备系统下基于条件信息熵的属性约简算法和基于自适应遗传的属性 约简算法，并进行了实例分析。 长沙理工大学硕士论文 4 ) 在相容关系的基础上，提出了从属性约简后的决策表直接进行最优规则提 取的算法，并进行了实例分析。 5 ) 设计了一个基于本文所提出的属性约简和规则提取方法的不完备决策系 统的数据挖掘模型。 1 6 本文的组织 本文章节及内容的安排如下： 第l 章绪论。概述数据挖掘、粗糙集理论以及不完备信息的发展和研究状况； 介绍本论文的工作安排。 第2 章粗糙集理论。介绍粗糙集理论的基本概念。 第3 章粗糙集理论在不完备系统中的拓展。介绍粗糙集理论在不完备系统中 的拓展以及不完备决策系统的知识约简。 第4 章基于条件信息熵的不完备决策表属性约简。提出了基于条件信息量的 不完备决策表属性约简算法的改进算法一一c i e a r a w c c 算法，并举例说明了该 算法能有效解决属性冗余问题。 第5 章基于遗传算法的不完备决策表属性约简。研究遗传算法在不完备决表 属性约简中的应用，并举例说明了算法对相容决策表和不完备决策表的通用性。 第6 章不完备决策系统的最优规则提取。提出了在经过属性约简后的决策表 中直接进行最优规则提取的a o r a i d t 算法。 第7 章不完备决策系统的数据挖掘模型。介绍了一个以粗糙集为基础的不完 备信息系统的数据挖掘模型。 第8 章结论与展望。总结了本文的研究工作，提出进一步研究的方向；阐明 本文研究工作中的难点和创新点。 6 长沙理工大学硕士论文 第二章粗糙集理论 r o u g hs e t 理论是波兰数学家z p a w l a k 于1 9 8 2 年提出的，研究模糊性和不确 定性的一种新的数学工具，它的重要特点是不需要预先给定某些特征或属性的数 量描述而直接从给定问题的描述集合出发，在保持分类能力不变的前提下，通过 知识约简，导出概念的分类规则，它能有效地处理不精确、不一致、不完备信息， 并从中发现隐含的知识，揭示潜在的规律。目前，r o u g hs e t 理论己被成功应用于 机器学习、人工智能、模式识别、数据挖掘、智能信息处理等领域。下面阐述粗 糙集理论的基础知识及其主要思想，作为后续章节的理论准备。 2 1 知识分类 设u 是我们感兴趣的对象组成的有限集合，亦即论域。任何子集z ( 厂， 称为u 中的一个概念或范畴。为规范化起见，我们认为空集也是一个概念。u 中 的任何概念族称为关于u 的抽象知识，简称知识。u 上的一族划分称为关于u 的 一个知识库，它构成了一个特定论域u 的分类。 定义2 1 设尺是u 上的一个等价关系，u r 表示r 的所有等价类构成的集 合，【x 1 蠢表示包含元素x ( ，的r 等价类。一个知识库就是一个关系系统足= ( u ，矗) 。 其中u 为非空有限集合，称为论域，r 是u 上的一个等价关系族。 定义2 2 设r 是u 上的一族等价关系，若尸月，且尸，则n 尸( p 中所 有等价关系的交集) 也是一个等价关系，称为尸上的不可分辨( i n d i s c e m i b i i i t y ) 关系，记为脚( 尸) ，即 胁d ( p ) = ( ( t y ) u u l ，( 墨口) = ，( 乃口) ，v 口p ) 且有 【明( p ) = f1 x 1 r r 二p 这样c ，耐俨) 表示与等价关系族尸相关的知识，称为足中关于u 的尸基本知 识。为简单起见，我们用尸代替u 胁以尸) ，胁烈户) 的等价类称为知识尸的基本 概念或基本范畴，p 的基本概念拥有知识p 的论域的基本特性一一知识的基本模 块。 同样，我们也可以定义：当置= ( u ，尺) 为一知识库，脚暇) 定义为置中所有等 价关系的族，记作砌( k ) = 蒯( p ) l p r ) 。 由上面的概念可知，知识实际上是一族等价关系，是区分论域中不同对象的 能力。它将论域分割成一系列的等价类，每个等价类是不可分辨的。 7 长沙理工大学硕士论文 例2 1表2 1 所示的个体集合( 1 ，2 ，3 ，4 ，5 ，6 称为论域，即所要考察的对象全 体。每个个体在四个属性( 头疼、肌肉疼、体温和流感) 上对应四个取值，那么每 个个体与其对应属性取值就构成了一个元组。如果我们按照某个或多个属性来描 述这些个体，就可以得到不同的分类知识。 表2 1 信息表 为方便起见，我们定义四个等价关系( 即属性) ：头疼足，肌肉疼足，体温 r 和流感r ，通过这些等价关系，我们可以得到下面四个等价类： u 冠= ( l ，2 ，3 ， 4 ，5 ，6 ” u ，足= l ，2 ，3 ，4 ， 5 ，6 u r = “l ，4 ，f 2 ，5 ，( 3 ，6 ) u r = ( ( 1 ，4 ，5 ， 2 ，3 ，6 也可以按照属性的组合来分类，例如： u ，饵u r = “l ，2 ，3 ，( 4 ，( 5 ，6 ) ) u 饵u r ) = ( ( 1 ) ，( 2 ，3 ，( 4 ，5 ， 6 由上例可以看出，我们可以用不同的标准来对论域进行分类，得到不同的概念 和抽象，有的概念是我们需要的，而有的则不需要，数据挖掘就是要探寻有用的概 念，并得到概念之间的联系。 2 2 信息系统与决策表 2 2 1 信息系统 定义2 3 形式上，四元组廖= ( 以彳，e 厂) 称为一个信息系统( i s ，i n f o r m a t i o n s y s t e m ) 。其中夥表示对象的非空有限集合，称为论域：4 表示属性的非空有限集 合，矿= u 。屹，圪表示属性口的值域；：u 4 寸矿是一个信息函数，它为每 个对象的每一个属性赋予一个信息值，即妇4 ，x u ，厂 口) 圪。若存在一 个x u ，口c ，厂( x ，口) 未知，( 记作( x ，口) = ) ，则称信息系统是不完备的：否 则称信息系统是完备的。在本小节中，如不做特殊说明，均认为信息系统是完备的。 信息系统的数据以关系表的形式表示，关系表的行对应要研究的对象，列对 8 长沙理工大学硕士论文 应对象的属性，对象的信息是通过指定对象的各属性值来表达。容易看出，个 属性对应一个等价关系，一个表可以看作是定义的一个等价关系簇，即知识库。 知识约简可以转化为属性约简和值约简。 2 2 2 决策表 决策表是一类特殊丽重要的知识表达系统，多数决策问题都可以用决策表形 式来表达。决策表可以根据知识表达系统定义如下： 定义2 4 对于信息系统俗= ( u ，4 ，矿，) ，如果4 r = c u d ，c 称为条件属性集 合，d 表示决策属性集合。且c n d = m ，则称信息系统s 为决策表。 条件属性c 和决策属性d 的等价关系删( c ) 和砌( d ) 的等价类分别称为条件 类和决策类。 一个决策表中的决策属性有时是唯一的，称为单一决策；有时是不唯一的，称 为多决策。因为一个多决策表可以交换成单一决策表，所以，本文只研究单一决策 表。 2 3 不精确范畴，租糙集与上、下近似集 上一节介绍的不可分辨关系是粗糙集理论的一个关键概念，它通常是和一个 属性集合联系在一起的。例如表2 l 中，考虑属性头疼和肌肉疼，对于对象4 和对 象6 ，其头疼的值都是“否”，肌肉疼的值都是“是”。因此从属性集( 头疼，肌肉： 疼) 的角度来看，这两个对象是不可分辨的。由此构成的不可分辨集 “l ，2 ，3 ，f 4 ，6 ) ，f 5 ) 称为基本集。任意多个基本集的并称为可定义集。 定义2 5 令x u ，r 为u 上的等价关系。当j 能表达成某些| r 基本范畴的 并时，称x 是r 可定义的；否贝| j 称z 是r 不可定义的。月可定义集也称作兄精确 集：r 不可定义集也称为尺非精确集或r 粗糙集。 对于粗糙集可以近似地定义，我们使用两个精确集，即粗糙集的上近似( u p p e r a p p r o x i m a t i o n ) 和下近似( l o w e ra p p r o x i m a t i o n ) 来描述。 定义2 6 给定信息系统晒= ( u ，爿，e ，) ，对于每个子集x u 和一个等价关系 尺4 ，定义两个子集： 村= u j r u ，尺i r 互x ) r x = u 】，( ，尺i r n x 西 分别称它们为x 的r 下近似集和r 上近似集。 由上近似和下近似，可以得到正区域( p o s i t i v e r e g i o n ) 、负域( n e g a t i v e r e g i o n ) 和边界域( b o u n d a r yr e g i o n ) 的概念。 定义2 7 给定信息系统岱= 彳，e ，) ，对于每个子集z u 和一个等价关系 r 4 ，集合x 相对于r 的正区域定义为： 9 长沙理工大学硕士论文 p o s r o x 、= 珏x 定义2 8 给定信息系统您= 融爿，以) ，对于每个子集彤u 和一个等价关系 尺4 ，集合x 相对于尺的负域定义为： n e g r 蛾1 = u r x 定义2 9 给定信息系统胚= ( u ，彳，e ，) ，对于每个子集x u 和一个等价关系 月彳，集合x 相对于月的边界域定义为： 魄( x ) = 肘一型 硝或怖( x ) 是由那些根据知识r 判断肯定属于x 的u 中的元素组成的集 合；剃是由那些根据知识r 判断可能属于x 的( ，中的元素组成的集合：6 ( 彳) 是那些根据知识尺既不能判断肯定属于x 又不能判断肯定属于一x 的u 中的元素 组成的集合。 有了上述定义，我们可以锝到上近似、下近似、正区域和边晃域之间的关系， 其表示如下： r ( x ) = p n ( x ) u 6 ( x ) = 星( x ) u 6 ( x ) = u 一星( x ) 例2 2 在表2 2 所示的信息表中，若取属性集p = ( 头疼，肌肉疼 ， x = p ：，气，气) ，则有： u p = ( k ，p 2 ，巳) ， 气，) ， p ，) ) x = 脚( x ) = 气，气) ，尸x = q ，p ：，巳，气，气) ，( x ) = u 一蹦= ，坼( x ) = 肘一丛= 乞，吃) 。 表2 2 信息表 2 4 近似分类和近似分类质量 集合的不精确往是由于边界域的存在而引起的，集合的边界域越大，其精确 性越低。为了更准确地表达这一点，我们引入了精度概念。 定义2 1 0 给定信息系统腰= ( u ，4 ，矿，) ，尺彳，设集合是论域u 上的一 个关于知识r 的粗糙集，则x 的月近似精度为； 吣) = 黑 1 0 长沙理工大学硕士论文 其中z m ，i z i 表示集合x 的基数，若x = o ，则定义( z ) = l 。 精度用来反映我们了解集合x 的知识的完全程度。显然o ( z ) l 。当 ( x ) = l 时，我们说集合z 是尺可定义的；当( x ) l 时，我们说集合x 是尺不 可定义的。 定义2 1 l 给定信息系统俗= ( ，彳，e ，) ，r 4 ，设集合z 是论域u 上的一 个关于知识r 的粗糙集，则z 的r 粗糙度定义为： 风( x ) = l 一( x ) 与x 韵r 精确度相反，j 的月粗糙度表示集合z 关于知识尺的不完备程度。 除了用数值( 近似程度的精度) 来表示粗糙集的特征外，也可以根据上下近似 的定义来表达粗糙集的另一个有用的特征，即拓扑特征。 定义2 1 2 给定信息系统腰= ( u ，彳，矿，) ，r 彳，设集合x 是论域u 上的一 个关于知识r 的粗糙集， ( 1 ) 如果墼西且冠u ，则称x 为r 粗糙可定义； ( 2 ) 如果丛= m 且取u ，则称x 为r 内不可定义； ( 3 ) 如果型m 且融= u ，则称x 为r 外不可定义； ( 4 ) 如果丛= m 且戤= u ，则称x 为尺全不可定义。 这个划分的直观意义如下：如果集合j 为尺粗糙可定义，则可以确定u 中某 些元素属于x 或x ；如果x 为r 内不可定义，意味着可以确定( ，中某些元素是 否属于一石但不能确定u 中任一元素是否属于x ；如果x 为尺外不可定义，可以 确定u 中某些元素是否属于x ，但不能确定u 中任一元素是否属于一x ；如果x 为月全不可定义，则我们确定u 中任一元素是否属于z 或一x 。 粗糙集的数字特征表示了集合边界域的大小，但没有说明边界域的结构；而 粗糙集的拓扑特征没有给出边界域大小的信息，它提供的是边界域的结构。因此 在粗糙集的实际应用中，我们需要将边界域的两种信息结合起来，既要考虑精度 因素，又要考虑到集合的拓扑结构。 粗糙集理论还对集合类关于近似空间的分类问题定义了上近似和下近似。 定义2 1 3 给定信息系统四= ，彳，以) ，月彳，令f = 五，五，k ) 是( ，的 一个划分，这个划分独立于知识r ，子集z 是划分f 的类。f 的下近似和上近 似分别定义为： 矽= ( 戤，战，墨k ， 即= 戤，瓯，眠 定义2 1 4 给定信息系统腰= ( 以4 ，矿，) ，尺4 ，令f = ( 五，五，以) 是u 的 个划分，这个划分独立于知识r ，子集置是划分f 的类，则根据知识月，的 近似分类精度定义为： 长沙理工大学硕士论文 m j 戤i ( f ) = 等一 i 取i i = i 定义2 1 5 给定信息系统腰= ( u ，彳，e ，) ，r 爿，令f = 五，置，以) 是u 的 一个划分，这个划分独立于知识尺，子集置是划分f 的类，则根据知识尺，f 的 近似分类质量定义为： j 戥i ( f ) 。气矿 近似分类的精度描述的是当使用知识尺分类对象时，可能的决策中正确决策 的百分比；分类的质量表示的是应用知识灭能确切地划入f 类的对象的百分比。 例2 3 在2 2 所示的信息表中，若f = 墨，五 ，墨= 娩，岛，巳，) ，置= 啊，气 ， 对于属性子集尺= 头疼，肌肉疼 ，论域u 的所有j r 基本集为 u r = “q ，e ：，巳 ，f 巳，吒) ， p ，) ) ，令8 = 巳，巳，巳) ，r = 气， ，月3 = 岛 ，有： 尺( 五) = r = 地 驴， 尺( 丘) = 矿， 尺( 五) = r u r u r = 巳，吃，巳，气，岛，气 = u ， r ( 五) = 墨u 是= q ，乞，岛，气，气) ， ( f ) = ( 1 + 0 ) ( 6 + 5 ) = 0 0 9 ， 靠( f ) = ( 1 + 0 ) 6 = o 1 7 。 将粗糙集的概念与普通集合论相比较，可以看出粗糙集的基本性质，如元素 的成员关系、集合的等价和包含等，都与不可区分关系所表示论域的知识有关。 因此，一个元素是否属于某一个集合，不是该元素的客观性质，而取决于我们对 它的了解程度；同样，集合的相等和包含也没有绝对的意义，也取决于我们对所 研究问题中集合的了解程度。 2 5 知识的依赖性与知识约简 知识约简是粗糙集理论的核心内容之一。众所周知，知识库中知识( 属性) 并不是同等重要的，甚至其中某些知识是冗余的。所谓知识约简，就是在保持知 识库分类能力不变的条件下，删除其中不相关或不重要的知识。通常我们只能根 据经验来选择权重，这依赖于人的先验知识。根据上节中介绍的知识尺对集合簇f 近似分类的质量( f ) 这一概念，我们可以对论域样本属性的重要程度进行度量， 而不依赖于人的先验知识。 长沙理工大学硕士论文 2 5 1 信息系统的知识约简 定义2 1 6 给定信息系统腰= ( u ，4 ，矿，) ，令尺为论域u 上的一个等价关系簇， ，r 4 丁，如果俐( r ) = 俐( 尺一 毋) ，则称p 为r 中不必要的；否则称p 为尺中 必要的。 定义2 1 7 给定信息系统腰= ( u ，4 ，矿，) ，令月为论域u 上的一个等价关系簇， 尹r 爿r ，如果每一个p 农都为尺中必要的，则称月为独立的，否则称r 为依 赖的。 定义2 1 8 给定信息系统岱= ( u ，4 ，矿，) ，设p 是定义在u 上的一个等价关系 族，p 中所有必要的关系组成的集合称为等价关系族尸的核，记作咖( 尸) 。 定义2 1 9 给定信息系统腰= ( u 4 以力，设尸和q 是定义在u 上的等价关系 族，q 三尸，如果 ( 1 ) m d ( q ) = 矗耐( 尸) ( 2 ) q 是独立的 则称q 为p 的一个约简。 显然，p 可以有多个约简。核与约简有如下关系： c d ，口( 尸) = n 朋d ( p ) 其中，删( p ) 表示j p 的所有约简。可以看出，核这个概念有两方面的用处： 首先它可以作为所有约简的计算基础，因为核包含在所有的约简之中，并且计算 可以直接进行；其次可解释为在知识约简时它是不能消去的知识特征集合。 2 5 2 决策表的知识约简 决策表( d t ，d e c i s i o n m a k i n gt a b l e ) 的属性约简，即相对约简，就是要从条件 属性集合中发现部分必要的条件属性，使得根据这部分条件属性形成的相对于决 策属性的分类和所有条件属性所形成的相对于决策属性的分类一致，即和所有条 件属性相对于决策属性d 有相同的分类能力。 定义2 2 0 在决策表d r = ( 以c u d 矿，) 中，p c ，设u ，d = 墨，艺，y 麻) 表 示决策属性集合d 在u 上形成的划分，则决策属性集d 对于条件属性集p 的相对 正域定义为： p 啤( d ) = u2 ( 鬈) 五u d d 的尸正域是u 中所有根据划分u 尸的信息可以准确地分类到关系d 的等 价类中去的对象集合。 定义2 2 1 在决策表d 丁= ，c ud 矿，j r ) 中，尺c