（管理科学与工程专业论文）基于粗糙集的增量式知识获取算法研究与实现.pdf

山东师范大学硕士学位论文 基于粗糙集的增量式知识获取算法研究与实现 摘要 目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数 据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势，缺乏挖掘数据背后隐 藏的知识的手段，导致了“数据爆炸但知识贫乏 的现象。于是知识发现( k n o w l e d g e d i s c o v e r yi nd a t a ，k d d ) 和数据挖掘( d a t am i n i n g ，d m ) 技术应运而生。知识发现是近 几年随着数据库和人工智能发展起来的一门新兴的数据库技术。通过知识发现技术，我们 可以将信息变为知识，从“数据矿山”中找到蕴藏的“知识金块 。因此，研究高效智能 的知识发现方法具有很大的现实意义。 粗糙集理论是1 9 8 2 年由波兰数学家z p a w l a k 教授提出来的，它是一种处理不完整、 不确定信息的新型数学工具。由于粗糙集理论不需要任何预备的或额外的有关数据信息， 这样就避免了对知识的主观评价所带来的误差。经过2 0 多年的发展，粗糙集理论不但在 理论本身研究方面不断完善，而且在其它领域中也得到了成功的应用，如机器学习，决策 分析，近似推理，图像处理，专家系统，过程控制，冲突分析，数据库知识发现( k d d ) ， 医疗诊断，金融数据分析等方面得到了较为成功的应用。 近几年在粗糙集理论研究中对求解属性的最小约简和较小约简以及求取最简规则集 的算法已经进行了一些研究，但这些研究都是针对静态数据的。而数据库是动态的，因此 许多研究者建议，数据库知识发现算法应该是增量式的。属性最小约简的增量式算法以及 增量式更新概念格的算法已经开始被研究，但对于增量式规则获取算法的研究工作还比较 少。在以上工作的基础上，本文研究了基于粗糙集的增量式规则获取问题。 本文所做的主要工作有：介绍了粗糙集理论的发展历程、特点、应用领域和基本理论。 给出了决策表中对象“相关 和“相互独立的定义，证明了当新对象加入时哪些规则需 要更新，提出了一个基于粗糙集和搜索树的增量式规则提取算法。该算法在深度优先搜索 中将已获取规则作为启发信息，大大提高了算法的效率；在时间复杂度不变的条件下，无 需建立传统算法中的差别矩阵，具有较好的空间复杂度。由于现实中的决策表往往是不一 致的，为了能够提取不确定性规则，本文引入可变精度粗糙集模型给出了基于可变精度粗 糙集的增量式规则获取算法。最后，通过实验对比证明了算法的正确性和有效性。 本文的主要创新点在于： ( 1 )给出了一个基于粗糙集理论和搜索树的增量式规则提取算法( r d b r d f s t ) 。 该算法引入启发信息，无需建立差别矩阵，具有较好的时空复杂性。 ( 2 ) 引入可变精度粗糙集模型给出了基于可变精度粗糙集的增量式规则获取算 法。该算法较好的解决了不一致决策表中不确定性规则的增量式获取问题，可通过设嚣不 同的规则嚣信度束凋整规则的获取。 山东师范大学硕士学位论文 r e s e ar c ha n dlm pie m e n t a tio na b o u ta nin c r e m e n t al k n o wie d g e a c q u isitio naig o rit h m sb a s e do nr o u g hs e t a b s t r a c t t h ep r e s e n td a t a b a s es y s t e mm a yr e a l i z ef u n c t i o n sh i 酿l ye 舵c t i v e ，s u c ha sd a t ai n p u t ， i n q u i s t a t i s t i c s ，b u ti su n a b l et of i n dt h er e l a t i o n sa 1 1 dt h em l e si nt h ed a t a ，w i l l b eu n a b l et o f o p e c a s tt h ef u t u r ea c c o r d i n gt ot h ee x i s t i n gd a t a ，a n dl a c ko fd a t am i n i n gh i d d e nl 【1 1 0 w l e d g e m e a n s ，l e dt ot h e ”d a _ t ae x p l o s i o nb ml ( 1 1 0 w l e d g ep o v c n y ”w i t l lt h ed e v e l o p m e n to fd a t a b a s e a n da n i f i c i a li n t e l l i g e n c e ，k j l o w l e d g ed i s c o v e 巧i nd a t a ( k d d ) h a u sb e c o m ean e wd a t a b a s e t e c h n o l o g yi nt h ep a s tf e wy c a r s w i t hk d dt e c l l l l o l o g y w ec 觚t 嘲i n f o n l l a t i o ni n t o l 【i l o w l e d g ea 1 1 df o u l l dm e l ( i l o w l e d g e 肌g g e t s 舶mm e “d a t am i i l i n g ”w h e r e f o r e ，r e s e 觚i h e 伍c i e n t 缸e 1 1 i g e n tk n o w l e d g ed i s c o v e r ym e m o d sh a v e 黟e a tp r a c t i c a ls i g l l i f i c a i l c e r d u 班tt h e o d rm a tw a u sp u tf o 刑a r db yp 0 1 ez p a w l 狄i n1 9 8 2i san e wd a t a 孤a l y s i s t h e o r yo fa 芏l a l ) ，z i i l ga n dd e a l i n gw i t hu n c 瞰a i n 锄di n c o m p l e t ed a t a i tm a l ( e su s eo ft h e e q u i v a l 锄c er e l a t i o 璐t 0m e a s u 托t h ei i l d e t i e r m i i l a t i o nd e g r e eo fk n o w l e d g e 锄di t d o e s n tn e e d a n yk n o w l e d g eo u t s i d eo ft h ed a t aw t l i c hn e e d st ob ep r o c e s s e d t h e r e f o r ct l l ee r r o rc a 吣e db y s l l b je c t i v e 印p 两s a lc 觚b ea v o i d e d w i t h2 0y e a r sd e v e l o p m e n t ，l er o l l 曲s e tm e o r ) rn o to n l y i nt h e 也e o r e t i c a ls t u d yo fc o n t i n u o l l s l yi l n p r 0 v ei t s e l b u ta l s 0i no m e ff i e l d sh a v ea l s ob e e i l s u c c 骼s f i l li na p p l i c a t i o n s ，s u c h 嬲m a c h i n e1 e 锄i n g ，d e c i s i o na i l a l y s i s ，a p p r o x i m a t er e a s o n i n 岛 i m a g ep r o c e s s i n g ，e x p e r ts y s t e m s ，p r o c e s sc o n t r o l ，c o n n i c ta l l a l y s i s ，k n o w l e d g ed i s c o v e 拶i l l d a t a b a s e s ，m e d i c a ld i a 印o s i s ，s u c h 弱丘n a n c i a ld a t aa i l a l y s i sh a sr e c e i v e dm o r es u c c e s s m l 印p l i c a t i o n s h lr e c e n ty e a r s ，r e s e a r c hi nt h er o u g hs e tt h c 0 巧南rs o l v i n gn l em i n i m 啪a t t r i b u t e r e d u c t i o na i l das m a l l e rr e d u c t i o 玛嬲w e l la sg e t t i n gas i m p l e s tn l l es e ta 1 9 0 r i t h mh a sb e e n g o i i l go nf o rs 咖es t u d i e s ，b u tt h e s es t u d i e sa r ed i r e c t e da tt 1 1 e s t a t i cd a t a t h ed a t a b a s ei s d ) ，1 1 锄i c m a l l yr e s e a r c h e r ss u g g e s t e dt h a tt h ed a t a b a s el 【i l o w l e d g ed i s c o v e 巧a l g o r i t 胁i st h e i n c r e m e n t a l a t t r i b u t em 谳m u mi n c r e m e n t a lr e d u c t i o na l g o r i t l l i i la i l di i l c r e m e n t a lu p d a t i n gt h e c o n c 印tl a t t i c ea l g o r i t l l n lh a sb e g u nt ob es t i l d i e d ，b u tt l l er e s e a r c hi i li n c r e m e n t a lm l ee x t r a c t a l g o r i t h mi s s t i l l r e l a t i v e l ys m a l l o nt h eb a s i so fm ea b o v ew o r k ，m i sp a p e rs t u d i e sm e i n c r e m e l l t a l1 1 j l ee x t r a c ta l g o r i t l l i l lb a s e do nr o u 曲s e t 1 1 1t h i sp a p e r t h em a i nw o r kd o n e ：i i l t d u c er o u g hs e tm e o r yc o u r s co ft h ed e v e l o p m e n t ， f e a t u r e s ， 印p l i c a t i o t l sa n db a s i ct h e o 巧； p u tf 0 n a r dt h ed e f i n i t i o n so f “r e l e v a n t ” a n d “i n d 印e n d e n t ”b e 帆e e nt h eo b j e c t si nt h ed e c i s i o nt a b l e ；w h i c hm l e sn e e dt ob eu p d a t e dw h e na n e wo b j e c ti sp u ti n t ot h ed e c i s i o nt a b l e ；p r o p o s e da ni n c r e m e n t a lm l ee x t r a c t i o na l g o r i t i i i 山东师范大学硕士学位论文 第一章引言 随着计算机和数据库技术的迅猛发展，人类积累的数据量正以惊人的速度增长。人们 都希望从这些海量的数据中提取或发现对自己有价值的知识。目前的数据库系统可以高效 地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据 现有的数据预测未来的发展趋势，缺乏挖掘数据背后隐藏的知识的手段，导致了“数据 爆炸但知识贫乏 的现象。于是知识发现( k n o w l e d g ed i s c o v e r yi nd a t a ，k d d ) 和数据挖 掘( d a t am i n i n g ，d m ) 技术应运而生。知识发现是近几年随着数据库和人工智能发展起来 的一门新兴的数据库技术。通过知识发现技术，我们可以将信息变为知识，从“数据矿山 中找到蕴藏的“知识金块”。因此，研究高效智能的知识发现方法具有很大的现实意义。 1 1 知识发现 知识发现是从海量数据特别是从异构的海量数据平台中提取出有效的、新颖的、具有 潜在价值并以适当形式能被人们理解的规则与模式数据收集、数据清洁、降低复杂度、 规则归纳、模式识别、数据结果分析及评估、可视化输出等多种过程于一身，是统计学、 计算机科学、模式识别、人工智能、机器学习及其他学科相结合的产物。知识发现的范围 很广，可以是经济、商业方面的数据，也可以是军事、科学以及卫星观测方面的数据。数 据的类型可以是结构化的，如关系数据库中的数据：也可以是非结构化的，如文本、图形 图像数据，甚至分布在互联网上的异构式数据。 知识发现的对象包括以下几种：广义型知识，反映同类事物共同性质的知识；特征 型知识，反映事物各方面的特征知识；差异型知识，反映不同事物之间属性差别的知识； 关联型知识，反映事物之间依赖或关联的知识；预测型知识，根据历史的和当前的数据推 测未来数据；偏离型知识，揭示事物偏离常规的异常现象。所有这些知识都可以在不同的 概念层次上被发现，随着概念树的提升，从微观到中观再到宏观，以满足不同用户、不同 层次决策的需要。 知识发现的过程一般可分为数据准备、数据预处理、数据挖掘、预测评估和知识表示 五个阶段，如图1 1 所示。 ，j !； 一。一一j 一- - 一一f 一一， 图1 1 知识发现的一般过程 一 知识发现的过程首先要进行数据采集，就是根据需要通过各种渠道或一定的技术手段 从现实世界中收集数据。从这些现实数据库中抽取我们感兴趣的、适合于特定知识发现任 务的数据的过程就是数据准备。现实世界中的数据多半是不规范的，如含有噪声数据、空 山东师范大学硕士学位论文 缺值等。数据中这些缺陷的存在将对知识发现产生严重的影响。数据预处理”3 就是根据知 识发现的任务和要求，选择合适的方法对原始数据进行格式化、规范化处理，包括消除噪 声、消除不确定属性值、删除重复记录以及完成数据类型转换等工作数据预处理是知识 发现过程的重要环节，因为“原料”的好坏将直接影响到所生产出来“产品”的质量。数 据挖掘阶段则根据最终用户的决策目标对数据库进行信息提取，把最有价值的信息差别出 来，并且通过决策支持工具提交给决策者。知识表示过程就是利用可视化技术和知识表示 技术，为用户提供所发现的知识。需要指出的是，整个知识发现过程是一个不断反馈的过 程。比如，用户在挖掘过程中发现选择的数据不理想，或使用的挖掘技术无法产生期望的 结果，用户需重复先前的过程，甚至从头开始。 知识发现的常用方法有统计分析、机器学习、神经网络和基于数据库的方法等。从知 识发现的研究对象可以看出，该技术主要应用于数据量比较大、数据格式比较规范的行业， 如金融、电信、零售业、生物医学等领域，对于数据格式不规范的情况，则必须进行前期 的数据预处理。从领域分布来看，知识发现应用有两个主流：一是针对传统数据库、数据 仓库的挖掘，我们称之为数据库中的知识发现；另一个是针对i n t e r n e t 的挖掘，称之为 互联网中的知识发现。 1 2 粗糙集理论 粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年口1 提出的。这一理论为处理具有模糊、 不精确或不完全信息的分类问题提供了一种新的工具。起初，由于这个理论建立在商集基 础之上，较为复杂的数学使得这个理论未能引起人工智能研究者的注意，研究地域也仅局 限于波兰等东欧一些国家。当时许多波兰学者对粗糙集理论及其应用进行了坚持不懈的研 究，其中对粗糙集理论的数学性质与逻辑系统进行了广泛的分析。当时大多数研究成果发 表在，”b u l l e t i no ft h ep o l i s ha c a d e m i co fs c i e n c e s ”上，同时，他们也开发了一些 应用系统，但都处于萌芽阶段n 1 。到1 9 9 0 年前后，由于该理论在数据的决策与分析、模 式识别、机器学习与知识发现等方面的成功应用h 1 ，才逐渐引起世界数学界和计算机界 的广泛关注。1 9 9 1 年p a w l a kz 的专著粗糙集一关于数据推理的理论问世 1 ，该书与 在1 9 9 2 年出版的r s 理论应用专集较好地总结了这一时期r s 理论与实践的研究成果，促 进了它的进一步发展，现已成为学习和应用r s 理论的重要文献。 粗糙集理论的特点有：l 、粗糙集理论不需要先验知识。模糊集和概率统计方法是处 理不确定信息的常用方法，但这些方法需要一些数据的附加信息或先验知识，如模糊隶属 函数和概率分命等，这些信息有时并不容易得到。柑糙集分析方法仅利用数据本身提供的 信息，无需任何先验知识。2 、粗糙集是一个强大的数据分析工具。它能表达和处理不完 备信息；能在保留关键信息的前提下对数据进行化简并求得知识的最小表达；能识别并评 2 山东师范大学硕士学位论文 乎都不同程度地受到评价者主观因素影响，评价过程中指标权重的确立过多依赖人为赋值 和评分，主观性较强的问题。 ( 9 ) 在冲突分析方面。文献 3 3 应用粗糙集方法建立了反映以色列、巴勒斯坦、约旦、 埃及、叙利亚和沙特阿拉伯六国关于中东和平问题各自立场的谈判模型。 ( 1 0 ) 在数据库知识发现方面。k d d 是当前人工智能和数据库技术交叉学科的研究热点 之一。粗糙集方法已成为k d d 的一种重要方法，其导出的知识精练且更便于存储和使用， 与其它知识发现方法比较，粗糙集方法有如下特点：粗糙集方法的伸缩性强；鲁棒性和抗 噪音能力强；知识的可理解性和开放性较好；比较适合于符号信息。此外，粗糙集方法可 以对数据进行预处理，去掉多余属性，可提高发现效率，降低错误率。 虽然粗糙集理论至今只有二十几年的发展历史，但取得的研究成果是令人瞩目的。它 是一种非常有前途的软计算方法，为处理不确定信息提供了强有力的分析手段。我们相信 粗糙集理论具有广阔的发展空间，今后会在更多的实际领域中发挥作用。 1 3 基于粗集理论的知识获取 f a y y a d 等对数据库知识获取作了如下定义：知识获取是识别出存在于数据库中有效 的，新颖的，具有潜在效用的乃至最终可理解的模式的非平凡过程。他们将知识获取大致 归纳为如下步骤，。 ( 1 ) 理解领域知识和相关的先验知识，明确系统目标； ( 2 ) 创建相关的目标数据集( 原始样例库) ，即选择需要进行知识获取的变量或数据样 本的一个子集： ( 3 ) 数据整理和预处理，例如去除明显错误的冗余的噪音数据，收集噪音信息以决定 在后续步骤采取何种解决噪音问题的方法； ( 4 ) 数据约简和投影，寻找依赖于获取目标的表达数据的有用特征，以约简数据模式； ( 5 ) 选择一种与第( 1 ) 步所选目标相应的知识获取方法，如分类，综和，回归，聚类等； ( 6 ) 选择知识获取算法，即选择用于搜索数据中模式的方法； ( 7 ) 实施知识获取算法，得到分类规则或聚类等形式来表达的感兴趣的模式； ( 8 ) 解释得到的模式，也可采用可视化表示等方法；可重复第( 1 ) 步到第( 7 ) 步的迭代 过程： ( 9 ) 巩固得到的知识，如检查与其他知识是否冲突，将知识合并到另一系统，以进一 步加工利用等。上述各步都可以与用户交互，以得到用户感兴趣的好的知识结果。 目前，众多知识获取方法的研究主要专注于知识获取过程的第( 6 ) 步到第( 7 ) 步，这些 算法大多应用和发展了机器学习理论，就知识获取过程整体而言，尚缺乏坚实的理论基础。 粗糙集理论可支持知识获取的多个步骤，如数据预处理，数据约简，舰则生成，数据 山东师范大学硕士学位论文 依赖关系获取等。近年来，粗糙集理论对模糊和不完全知识的处理比较出色，成为数据库 知识获取研究中的有力工具。 基于粗糙集的知识获取的核心问题是对信息系统进行数据约简后提取规则。近几年在 基于半且糙集的知识获取研究中对求解属性的最小约简和较小约简以及求取最简规则集的 算法已经取得了一些成果。诗剐，但这些研究都是针对静态数据的。而数据库是动态的，因 此许多研究者。竹侧建议，数据库知识发现算法应该是增量式的。当拳h 糙集理论应用于数据 挖掘或在线学习时，其增量式学习能力显得非常重要。这主要有两个原因：首先，在实际 应用中数据量往往是逐渐增加的；其次，对一个训练好的系统进行修改的时间代价通常低 于重新训练一个包含新增数据的系统所花的代价，系统每增加一个新的数据就进行一次规 则集的重新计算显然会浪费更多的时间和空间资源。增量式获取知识的主要目标是在动态 环境中保持知识库。一般的，对粗糙集方法来说，就是指当新对象加入决策表时，以增量 式的方式接受新对象，更改现存的规则或约简，而不是对整个决策表重新计算得出。因此， 研究基于粗糙集的增量式的知识获取是很有意义的。 1 4 本文组织结构 本文讨论了基于粗集理论的增量式知识获取算法。其组织结构如下： 第二章：介绍了粗糙集理论及其扩展模型，以及本文中所使用的一些概念。 第三章：介绍了增量式规则获取算法的研究现状及存在的问题，给出了决策表中对象 “相关 和“相互独立”的定义，证明了当有新对象加入时哪些已有规则需要更新，并将 粗糙集理论与搜索树相结合提出了深度优先搜索的启发式增量规则获取算法，最后进行了 算法复杂性分析和实例分析。 第四章：证明了在不一致决策表中当新对象加入时哪些已有规则需要更新及更新后规 则的置信度，引入可变精度粗糙集理论，使得改进算法可以从不一致决策表中提取大于某 一置信度的规则。最后，给出了算法复杂性分析和实例分析。 第五章：通过实验证明了算法的正确性和有效性。 6 山东师范大学硕士学位论文 2 1 粗糙集理论 第二章粗糙集理论及其扩展模型 2 1 1 知识与知识库 假设给定对象全域u ( 非空) ，x u 称为u 上的一个概念。概念的族集就是u 上的 知识。u 上分类的族集( 即等价关系的族集) 称为u 上的一个知识库，记u r 为u 上等价 关系r 的所有等价类( 或者u 上的分类) 构成的集合。 定义2 1 一个知识库是一个关系系统k _ ( u ，a ) ，其中u o 为有限集合，称为全域， a 是u 上的等价关系族。 若p 彳，且p g ，则n p ( p 中所有等价关系的交集) 也是一个等价关系，称为p 上的不可差别关系，记为i n d ( p ) 。对于p 么，则尸上的不可差别关系表示为 切d ( 尸) = ( x ，少) u uiv 口p ，厂( 毛口) = 厂( y ，口) 。对于石u ，用集合 h 】p = y 【，i ( x ，y ) f 棚( p ) 来表示包含元素x 的等价类。 这样，u i n d ( p ) ( 即等价关系i n d ( p ) 的所有等价类) 表示与等价关系族p 相关的知识， 称为k 中关于u 的尸基本知识( 尸基本集) 。为简单起见，用u p 代替u i n d ( p ) ，i n d ( p ) 的等价类称为知识p 的基本概念或基本范畴。特别地，如果q a ，则称q 为k 中关于u 的q 初等知识，q 的等价类为知识a 的q 初等概念或q 初等范畴。 2 1 2 近似与粗糙集 令肖u ，r 为u 上的一个等价关系。当x 能表达成某些r 基本范畴的并时，称x 是r 可定义的；否则称x 为r 不可定义的。 r 可定义集是论域的子集，它可在知识库k 中精确地定义，而r 不可定义集不能在 这个知识库中定义。r 可定义集也称作r 精确集，而r 不可定义集也称为r 非精确集或 r 粗糙集。 当存在等价关系r 伽d ( k ) 且x 为r 精确集时，集合x u 称为k 中的精确集；当 对于任何r f 蒯( k ) ，x 都为r 粗糙集，则x 称为k 中的粗糙集。 对于粗糙集可以近似地定义，在粗糙集理论中使用两个精确集，即粗糙集的上近似 ( u p p e ra p p r o x i m a t i o n ) 和下近似( 1 0 w e ra p p r o x i m a t i o n ) 来描述。 定义2 2 给定知识库k = ( u ，f ) ，对于每个子集x u 和一个等价关系r f 蒯( k ) ， 定义两个子集： 7 山东9 币范大学硕士学位论文 尺= u 】，ll ，u 尺，y x 墨x = u yly u 尺， ，n = o 分别称它们为x 的r 下近似集和r 上近似集。 下近似、上近似也可用下面的等式表达： r x = u xx u ，【x 】r x 丛= u x u ，h 。n x a 集合p 呱( x ) = 丛称为x 的r 正域；慨( x ) = u 一心称为x 的负域； 剧( x ) = 肘一丛称为x 的r 边界域。 型或p 呱( x ) 是由那些根据知识r 判断肯定属于x 的u 中元素组成的集合；见y 是 那些根据知识r 判断可能属于x 的u 中元素组成的集合；叫r ( x ) 是那些根据知识r 既 不能判断肯定属于x 又不能判断肯定属于 x ( 即u x ) 的u 中元素组成的集合；慨( x ) 是那些根据知识r 判断肯定不属于x 的u 中元素组成的集合。 显而易见有如下性质： 定理2 1x 为r 可定义集当且仅当尺x = 麟，x 为r 粗糙集当且仅当心肘。 2 1 3 知识约简和核 知识约简是粗糙集理论的核心内容之一。知识库中知识并不是同等重要的，甚至其中 某些知识是冗余的。所谓知识约简，就是在保持知识库分类能力不变的条件下，删除其中 不相关或不重要的知识。知识约简中有两个基本概念：约简和核。 p 为知识库k - ( u ，f ) 上的一族等价关系，r p ，如果i n d ( p ) = i n d ( p - r ) ，则称 r 为p 中不必要的；否则称r 为p 中必要的。如果每一个r p 都为p 中必要的，则称p 为独立的，否则称p 为依赖的。 定义2 3 令p 为知识库k = ( u ，f ) 上的一族等价关系，q p ，如果q 是独立的， 且i n d ( q ) = i n d ( p ) ，则称q 为尸的一个约简。显然，p 有多种约简。p 中所有必要关系组 成的集合称为p 的核，记作c d ，p ( p ) 。 定理2 2 令p 为知识库l o ( u ，f ) 上的一族等价关系为c d ， x 山东师范大学硕士学位论文 2 1 4 知识的相对约简和相对核 在应用中，一个分类相对于另一个分类的关系十分重要，因此介绍一下知识的相对约 简和相对核的概念是必要的。 令p 和q 为u 中的等价关系，q 的p 正域记为p 傩p ( q ) ，即 p 晒( q ) = u 丛。 x e u q 令p 和q 为等价关系族，r p ，如果 p ( 碜耐( p ) ( f 玎d ( q ) ) = p ( 砭耐p 一 只 ) ( f 疗d ( q ) ) 则称r 为p 中q 不必要的；否则r 为p 中q 必要的。 为简单起见，我们用尸晖( q ) 代替尸d ( p ) ( 加d ( q ) ) 。 如果p 中的每个r 都为q 必要的，则称p 为q 独立的( 或p 相对于q 独立) 。 设ss 尸，s 为p 的q 约简当且仅当s 是p 的q 独立子族且p 呱( q ) = 尸吗( q ) 。p 的q 约简简称为相对约简。 p 中所有q 必要的原始关系构成的集合称为p 的q 核，简称为相对核，记为c 0 ( p ) 。 定理2 3 ( p ) = n 比如( p ) ，其中旭如( p ) 是所有p 的q 约简构成的集合。 2 1 5 信息系统与决策表 定义2 4 信息系统是指一个四元组s = ( u ，么，矿，厂) ，其中u 为一个有限对象集，a 是一个有限属性集。y = u 圪，圪是属性口的值域。信息函数：【，彳口满足 口e ( 工，口) y ，以么，x u 。信息系统也可简记为s = ( u ，么) 。 对于等价类 x 】p ，我们用d 田( 【x 】p ) = 岔口v ，v y 来对它的特性进行描述。 信息系统可以用数据表格来表示，表格的行对应论域中的对象，列对应描述对象的属 性。一个对象的全部信息由表中一行属性的值来反映。 信息系统实例如表2 1 ： 表2 1 信息系统s uab cd x l oooo x 2 02ll x 3 o1 oo x 4 l2l2 9 山东师范大学硕士学位论文 l x 6 lo l l 2 i表2 4) 【42o x 5 2 x 6 2 定义27设s=(u，彳，矿，厂)为信息系统，若a可划分为条件属性集c和决策属性集 d ，即c u d = 4 ，c n d = 囝，则称该信息系统为决策表。加d ( c ) 的等价类称为条件类，砌d ( d ) 的等价类称为决策类。 称决策表是一致的当且仅当d 依赖与c ，即c d ；称决策表是不一致的当且仅当cj td ( o 吐 o 6 3 a ，jd ， 1 6 2j4 o 5 9 玩jd 2 1 巳j ( f l o 5 6 qj4 o 9 1 表4 3 相关对象集s abcd 3 513 35l 4 l 231 223 2 2 332 34 33 按照规则更新算法，原规则集中规则口，以的置信度更新为o 9 2 ；规则巳j 吐的置 信度更新为o 5 ( ，l 0 9 l q 以lj 幽 1 山东师范大学硕士学位论文 4 3jd 3 o 9 2 g 6 2j 吐 o 6 3 玩jd 3 o ，6 7 4 7 本章小结 本章在第三章r d b r d f s t 算法的基础上，引入可变精度粗糙集模型提出了基于可变 精度粗糙集的增量式规则获取算法( r d b v p r s t ) ，该算法较好的解决了不一致决策表中 不确定性规则的增量式提取问题，可根据需要调整规则的置信度，从而获取符合要求的规 则集。该算法具有较低的空间复杂度，特别是对于大规模样本的规则提取，它的优势更加 明显。 山东师范大学硕士学位论文 第五章实验分析 为了验证算法的有效性以及算法处理数据的能力，对增量式规则提取算法在v c 6 o 下编制代码，并把该算法与粗糙集非增量式规则提取算法进行了比较，实验采用了 r o s e t t ag u iv e r s i o n1 4 4 0 ( 如图5 1 ) 和u c im a c h i n el e a m i n gr e p o s i t o r y ：b r e a s tc a n c e r w i s c o n s i n 经典数据集。 铆m h t 残嚣黧麴黝戮篱篓溪鬻ii jo剖到 0 i e 翻建垫e 脚幽喇。荆h e 移 d i 圆| 潮| 、卜j | 戮l 荔| 剑 组幽一圜豳嘲黝辫豳缀戮霸 口鳓u c t 5 。翻a i r l t h m s 番圜1 7 0 埠囝c 蛳p l e i o n 鬻翻魄c r e t l z 教洳 羊圜r e d u c t i 拳圜f 溉e r 衲g 謦圜c l 群s 敝a 阳 圜c o 仃盯河i de x e c