（计算机应用技术专业论文）基于粗糙集的约简优化计算方法研究.pdf

摘要 粗糙集理论是一种处理含糊和不确定性信息的新型数学工具，其 理论提出以来得到迅速的发展和广泛的应用。知识约简是粗糙集理论 重要研究内容之一，它的主要目的在于去除数据中的冗余信息，同时 保持原决策信息系统的分类能力不变。针对大量或海量数据，原有约 简方法效率低，须对粗糙集约简计算理论进行优化，发展完善相关计 算算法，以提高知识约简的效率。本文基于粗糙集理论，针对知识约 简优化计算问题进行了较为深入的研究。 对粗糙集理论三种知识约简方法进行比较，分析各类方法的优缺 点以及它们之间的相互关系。通过改进原有差别矩阵，在对象比较过 程中一次性提取核与用于求约简的所有分辨信息，并保证分辨信息之 间不存在包含关系。在此分辨信息基础上以属性频度为启发式信息给 出了种基于改进差别矩阵的启发式约简及增量式更新方法。理论分 析与实验仿真表明，新启发式算法产生约简与分辨函数思想产生的最 优约简一致，说明算法的有效性。 深入研究约简算法完备性理论，指出现有知识约简算法的不完备 性，对本文的新启发式约简算法的完备性给出的了充分的证明。其次， 在p a w l a k 知识约简定义下，证明了任意决策信息系统约简个数是条件 属性的组合函数。利用已证明的重要性质提出一种非指数级的所有约 简计算方法，低于所有相关文献算法的时间复杂度。该结论有助于改 进知识约简的效率，进一步提高粗糙集数据分析能力。 关键词粗糙集，知识约简，差别矩阵，包含关系，完备性 a bs t r a c t r o u g hs e tt h e o r yi s an e wm a t h e m a t i c a lt o o lt or e a s o na b o u t u n c e r t a i na n dv a g u ei n f o r m a t i o n i th a sb e e nr a p i d l y d e v e l o p e da n d w i d e l ya p p l i e di nm a n yf i e l d s r e d u c ti st h em o s ti m p o r t a n tc o n c e p ti n r o u g hs e t ，w h o s em a i np u r p o s ei st or e m o v et h er e d u n d a n ti n f o r m a t i o n a n dp r e s e r v e sc l a s s i f i c a t i o na c c u r a c yo fo r i g i n a li n f o r m a t i o ns y s t e m f a c i n gw i t hh u g ea m o u n t so fd a t a ，t h eo l da l g o r i t h m sf o rr e d u c ti sn o t f e a s i b l e i ti sn e c e s s a r yt oo p t i m i z et h ec o m p u t a t i o nt h e o r y , a n dp r o p o s e s s o m ep r a c t i c a la l g o r i t h m st oi m p r o v et h ee f f i c i e n c yo fr e d u c t b a s e do n r o u g hs e tt h e o r y , t h et h e s i sm a i n l yf o c u s e so nt h ep r o b l e m so fo p t i m i z e d c o m p u t a t i o nf o rr e d u c t n o to n l yt h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h r e ek i n d so fr e d u c t i nr o u g hs e tb u ta l s ot h e i rr e l a t i o n sh a v eb e e nc o m p a r e da n da n a l y s e d t h r o u g hi m p r o v i n gd i s c e r n i b i l i t ym a t r i x ，t h ei n f o r m a t i o nf o rc o r ea n d r e d u c tw i t h o u ti n c l u s i o nr e l a t i o ni sg a i n e di nt h ep r o c e s so fc o m p a r i n g o b j e c t s b a s e do nt h i si n f o r m a t i o n ，an e wh e u r i s t i ca l g o r i t h mf o rr e d u c ti s p r o p o s e d t h ee x p e r i m e n t a l r e s u l t si n d i c a t et h a tt h er e d u c to fn e w h e u r i s t i ca l g o r i t h mi si d e n t i c a lw i t ht h em i n i m a lr e d u c t ，s h o w i n gt h e e f f i c i e n c yo fn e wa l g o r i t h m w i t hd e e p l ys t u d y i n gt h e c o m p l e t e n e s so fr e d u c ta l g o r i t h m ，t h e i n c o m p l e t e n e s so fe x i s t i n ga l g o r i t h m sf o rr e d u c ti sp o i n t e do u t ，a n dt h e t h e s i sa l s op r o v i d e st h ep r o o ft op r o v et h ec o m p l e t e n e s so fn e wh e u r i s t i c a l g o r i t h mf o rr e d u c t t h e n ，u n d e rt h ep a w l a k sd e f i n i t i o nf o rr e d u c t ，i ti s c e r t i f i e dt h a tt h en u m b e ro fr e d u c ti na n yd e c i s i o ni n f o r m a t i o ns y s t e mi s t h ec o m b i n a t i o nf u n c t i o no fc o n d i t i o na t t r i b u t e b a s e do nt h i sp r o p e r t y , a n o n e x p o n e n t i a la l g o r i t h mi sp u tf o r w a r dt oc o m p u t e a l lr e d u c t s ，w h i c hi s l e s st h a no t h e ra l g o r i t h m si nt h ec o m p l e x i t yo ft i m ea n ds p a c e t h e c o n c l u s i o ni sh e l p f u lt oi m p r o v et h ee f f i c i e n c yo fr e d u c ta n de n h a n c e r o u g hs e t sc a p a c i t yo fa n a l y s i st ol a r g e rd a t a s e t k e yw o r d s r o u g hs e t ，r e d u c t ，d i s c e r n i b i l i t ym a t r i x ，i n c l u s i o n r e l a t i o n ，c o m p l e t e n e s s l l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：i 妄丛日期：立翌登年) 弓_ l e t 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：蔫出) 导师签名：杰趔! 闫日期：避年羔月垒日 硕士学位论文第一章绪论 第一章绪论 粗糙集理论是一种处理不精确、不一致和不完备信息的新型数学工具，该理 论自提出以来在理论研究与实际应用上都得到不断完善与发展。随着信息技术不 断发展，实际问题相关数据规模和复杂程度与日俱增，但目前的粗集知识约简方 法对于大数据集或海量数据分析难度较大。对知识约简计算过程进行优化，有效 地提高粗糙集数据分析效率和质量，使大量或海量数据分析成为可能，有着广泛 而深远的意义。 1 1 引言 随着数据库与计算机网络技术的飞速发展，各个领域的数据和信息呈爆炸性 趋势急剧增长。然而，人们处理与分析数据的能力却相当有限。这些数据被描述 为丰富的数据、贫乏的知识。存储数据的急剧增长已激起对新技术和自动化信息 处理工具的需求，以便帮助我们将海量数据转换成信息和知识。数据挖掘和知识 发现【1 】【2 1 【3 1 应运而生，它试图从大量的数据中挖掘出潜在的、有利用价值的信息和 知识，己成为人工智能研究的一个崭新领域和研究热点。 1 9 世纪末德国著名数学家康托尔( c 锄t o r ) 创立了集合论。他对集合所下的定 义是：把若干确定的有区别的( 不论是具体的或抽象的) 事物合并起来，看作一个 整体，就称为一个集合，其中各事物称为该集合的元素。康托尔所创立的集合论 被誉为2 0 世纪最伟大的数学创造，集合概念大大扩充了数学的研究领域，给数 学结构提供了一个基础，集合论不仅影响了现代数学，而且也深深影响了现代哲 学和逻辑。在经典逻辑中，事实与概念都只有真、假之分，所以逻辑推理的结论 要么是真要么是假。然而在现实中常常有大量含糊现象存在，它们不能明确地被 断定为真或是假，这种含糊现象存在于真假二值之间。19 0 4 年著名哲学家g f r e g e 提出含糊概念，并把其命名为边界线区域，即在全域上存在一些个体既不能完全 包含于某个子集，也不能在该子集的补集上被分类。1 9 6 5 年，l a z a d e h 提出模 糊集理论，但模糊集不能对含糊概念用数学公式进行描述，边界区域上含糊元素 的具体数目无法计算。19 8 2 年，波兰数学家z p a w l a k 教授提出粗糙集理论【4 】【5 1 1 6 】【7 】， 通过对上近似集和下近似集的定义，把这些无法确认的个体都归属于上、下近似 集合之差集，称为边界线区域。由于上近似集和下近似集都可通过等价关系给出 确定的数学公式描述，因此含糊元素数目可以被计算。 硕士学位论文 第一章绪论 粗糙集理论基本思想是通过关系数据库分类归纳形成概念和规则。在粗糙集 理论中有两个重要的概念，一是近似算子，一是约简与核。用上、下近似算子产 生确定性规则与不确定性规则，通过约简与核简化规则使之具有较好的泛化能 力。在具有有限属性值的关系数据库上运用糙集理论，通过等价关系的以及分类 对于目标的近似，可实现知识发现的过程。粗糙集理论与其他处理不确定和不精 确问题理论的最显著的区别是它无需提供问题所需处理的数据集合之外的任何 先验信息，所以对问题的不确定性的描述或处理可以说是比较客观的，由于这个 理论未能包含处理不精确或不确定原始数据的机制，所以这个理论与概率论，模 糊数学和证据理论等其他处理不确定或不精确问题的理论有很强的互补性。 1 2 国内外研究现状 2 0 世纪8 0 年代，波兰华沙大学数学家z p a w l a k 教授在集合论与模糊集基础 上提出了粗糙集理论，在数学性质与逻辑系统上进行了深入的分析。由于最初的 研究成果大多数发表在波兰的学术期刊，因此在当时并未引起国际上数学界和计 算机界的重视。 1 9 9 1 年，z p a w l a k 出版了第一本关于粗糙集( r sr o u g hs e t s ) i f 论专著【4 】， 系统全面地介绍了粗糙集理论相关知识。1 9 9 2 年r s l o w i n s k i 出版的粗糙集理论 应用论文集【8 】较好地总结了这一时期r s 理论与实践的研究成果，促进了粗糙集 在各个领域的应用与发展。从此，粗糙集理论得到世界学者的关注，掀起了粗糙 集的研究热潮。 1 9 9 2 年在波兰k i e k r z 召开了第一届国际粗糙集理论研讨会，这次会议着重 讨论了集合近似的基本思想及其应用。自此，每年都召开以粗糙集为主题的国际 会议。19 9 4 年，国际粗糙集研究学会( i n t e r n a t i o n a lr o u g hs e ts o c i e t y ) 成立。19 9 6 年在日本东京召开的第五届国际粗糙集理论研讨会，极大的推动了亚洲地区对粗 糙集理论与应用的研究。1 9 9 8 年，国际信息科学杂志为粗糙集理论的研究出版 一期专辑。2 0 0 4 年，国际粗糙集协会出版发行第一本粗糙集国际期干1 。在这些会议与期刊上吸收了大量有价值的学术论文，为推动粗 糙集在全世界的发展作出了巨大的贡献。 国内学者对粗糙集理论的研究起步较晚，但发展相当迅速。2 0 0 1 年5 月， 第一届粗糙集与软计算学术研讨会在重庆邮电学院召开，邀请了粗糙集理论创始 人z p a w l a k 教授做了学术报告。2 0 0 3 年5 月，重庆邮电学院成功承办了第九届 国际粗糙集、模糊集、数据挖掘与粒度计算学术研讨会。目前，许多高等院校 和科研单位相继开展粗糙集的基础理论及应用的研究，并在各自的研究领域取得 2 硕士学位论文第一章绪论 了一定的成绩。曾黄麟1 9 l 【1 0 1 、王国胤i 1 、刘清【佗1 、张文修【1 3 】l h 】【1 5 1 1 怕i 、史开泉【1 7 1 、 苗夺i 兼【1 8 i 、梁吉业1 1 9 】和胡寿松1 2 0 1 等先后出版了关于粗糙集理论的专著。 粗糙集理论作为一种新兴的数据处理工具，其研究日益广泛深入，它的应用 遍及各种领域，从最初的计算机科学领域1 2 1 1 的机器学习、模式识别、专家系统、 图像处理等，到工程技术领域的故障诊断、控制策略，经济商业领域的市场分析 1 2 2 、股票数据分析、银行数据分析，生物医学领域的医疗诊断，d n a 数据分析， 全球气候分析、决策支持【2 3 i ，预测建模等；实际应用的成功也进一步推动r s 理 论的发展。粗糙集理论理论的特点决定了其在以上各领域的应用大都可以归入两 类任务【7 1 【2 4 i ：无决策的分析和有决策的分析。前者主要是知识约简，去除多余属 性，分析提取有用信息，尤其是从大型数据库进行知识发现；后者主要是规则获 取，即利用粗糙集理论提供的值约简方法由实例集直接获取规则集。不管糙集理 论处理属于哪一类任务，多数共同的目的是要从大量数据中得到潜在的、有用的、 不易被直观发现的规律、模式，这就是所谓的“数据挖掘 ( 或k d d ) 。 粗糙集的理论研究涉及知识约简、规则生成、粗集代数公理化、粗糙逻辑与 决策支持、变精度粗集模型等。知识约简( 特征选择) 作为粗糙集理论重要研究内 容，它是在保持原决策信息系统的分类能力不变情况下，去除数据的冗余信息， 提高知识发现的效率。因此，提高知识约简算法的效率是粗糙集理论研究的重要 课题。一般来讲，粗糙集知识约简分析算法大体上可以分为三大类：第一类是基 于差别矩阵和分辨函数；第二类是基于代数观核与启发式；第三类是基于信息熵 理论。以上几种约简模型各有其优缺点，实际中方法的选择主要决定于分析处理 的数据对象。目前对各种约简模型研究进展概述如下： l 。差别矩阵和分辨函数 粗糙集创始人z p a w l a k 提出了简单数据分析法，s k o w r o n 在此方法上提出 的差别矩阵( d i s c e r n i b i l i t ym a t r i x ) 方法。该算法通过引入代数知识，把对信息系 统的决策表的知识约简问题转化为对差别矩阵化简问题。同时s k o w r o n 已经严 格证明，差别矩阵原理与p a w l a k 的粗糙集理论等价。该算法的特点就是简单、 容易理解，同时在实际应用中较容易实现。缺点就是由于要求生成差别矩阵的中 间环节，时空浪费严重【2 5 1 。 针对以上缺陷文献【2 6 】对差别矩阵进行简化。该方法就是在s k o w r o n 提出的 差别矩阵方法基础之上进行改进，主要是不用生成差别矩阵。它直接从信息系统 中提取关于属性分辨信息，并构造成分辨合取范式，同时做这种逻辑公式的等价 变换直接得到最小的析取范式。该运算过程中不用生成差别矩阵的中间环节，从 而节省了空间和时问，提高约简算法的效率。还有一些不用生成差别矩阵【2 7 1 1 2 8 1 【2 9 】1 3 0 1 ，用等价代换求得差别矩阵核与属性重要度的方法。文献 1 2 1 1 3 1 提出了拓 硕士学位论文第一章绪论 广差别矩阵方法。它是按决策划分论域，将不同类的个体分别置于行和列构造差 别矩阵，空间复杂度有明显的降低。 对于由s k r o w o n 差别矩阵到分辨函数析取范式的生成，还是停留在人工转 化的状态或是全局搜索的方法。在实际的数据挖掘和决策支持系统项目应用中， 对于稍微复杂的差别矩阵的约简结果，两种方法就显得低效，成为差别矩阵到规 则生成的效率瓶颈。文献【3 2 通过约简后的差别矩阵与析取范式之间存在着内在 规律，并建立了分辨函数的合取项矩阵转化为析取项矩阵的数学模型，提出了直 接生成析取项的算法。 2 代数观核与启发式 z p a w l a k 提出知识约简代数观点的定义，约简前后只需保证正域元素不变， 无需考虑边界域元素。目前代数约简的算法一般采用启发式思想，先计算信息系 统的核属性，再应用属性重要度启发式信息求得最优或次优约简。此计算方法时 空复杂度代价较小，但系统所有约筒求取的复杂度是指数级的，且算法大多数是 不完备。一般核属性求取方法概述如下： 1 ) 差别矩阵求核 s k o w r o n 定义差别矩阵，h u 对它进行改进1 3 3 1 ，矩阵中单属性元素即为核， 这对相容信息表是成立的。文献 3 4 1 在h u 的基础上增加对不相容数据之间判断 各自等价类决策的最小基，此时核即为矩阵中单属性，解决不相容求核的问题。 文献 3 5 】在以上基础进一步降低计算代价。 2 ) 不构造差别矩阵求核 文献【3 6 】通过列出信息系统中的不相容规则，两不相容之间不需比较。其它 两两比较生成属性集合项，若两项中含有相同的属性元素，则在这些元素中必含 有核，取两项交集构成核属性项：若两项中所含属性元素完全不同，则这两项中 都必含有核属性，只需取其并集。当所有属性集合项运算完成最终得核属性集合。 实际上发现在差别矩阵生成核过程，在求得某核的前提下，后继差别矩阵生成中 只要含有核元素，则无需再进行比较。且运算过程中只存储核元素集合，省去差 别矩阵中扫描单属性的过程。 3 、) 不可缺少属性求核 在信息系统中，属性核是属性重要度不为零的条件属性【3 7 i 。这些属性在根据 属性重要性进行的约简运算过程中都不能被约简。文献【3 8 给出了详细的证明。 因此可在条件属性下对所有属性分别进行重要度计算，重要度不为零为核属性。 但此方法对每个属性重要度计算都要对信息系统扫描一次，完成所有核属性检测 需要重复扫描信息表。 4 ) 其它 4 硕士学位论文第一章绪论 文献 3 9 1 应用分冶思想，将计算整个全域上的核与约简问题转化为计算在相 应划分的子区域上知识约简问题。对于一般比较大的数据集而言，提高效率比较 明显，提高了知识约简的可计算性。文献【4 0 】基于细分关系求信息系统核，进一 步减少的计算的复杂度。 通过以上各类求核方法计算核属性后，以属性的重要性作为约简的启发信 息，计算最优约简与次优约简。该类启发式度量方法主要有： 1 ) 基于差别矩阵( d m ) 的方法 此类方法需先存储差别矩阵，对差别矩阵中各元素项中的属性统计出现的频 率。以此频率作为该属性重要性的度量，称为属性频度函数1 。在核的基础上， 逐次加入属性重要度最大的属性，同时删除差别矩阵中含有此属性的元素项，直 至差别矩阵为空，所得条件属性集合即为约简。 2 ) 基于代数观的方法 粗糙集理论中所有的概念和运算都是通过代数学的等价关系和集合运算来 定义的，称为粗糙集理论的代数表示。利用粗糙集中集合或分类的正域、相对正 域以及近似精度的概念【4 2 1 ，根据属性重要度逐次加入直至形成约简。算法一般能 生成次优、最优约简1 4 3 1 。 3 ) 基于信息论的方法 所谓“知识的信息表示 是将粗糙集理论中的知识( 属性) 看作是定义在论 域的子集组成的随机变量，从而引入了知识熵与互信息的概念，并给出知识约简 的新定义，同时证明了它与p a w l a k z 的代数表示的等价性【4 4 1 ；从而可以从信息 熵的角度定义属性的重要性。 3 信息熵的知识约简 基于信息熵【4 5 l 的知识约简也分两种：先求核再用信息熵属性重要度启发式构 造约简；另法先根据信息熵属性重要度进行排序，再属性从初始条件属性集，采 用逐步删除不影响信息表条件熵属性来达到约简的目的。现就目前信息熵主要算 法分析如下： 11m i b a r k ( m u t u a li n f o r m a t i o n - b a s e da l g o r i t h mf o rr e d u c t i o no fk n o w l e d g e ) 此算法由文献【4 6 】提出。m i b a r k 先计算决策表的核，然后在核属性基础上 进行约简。算法是建立在条件属性与决策属性的互信息基础之上的，以互信息的 变化量作为属性对于决策的相对重要度，并以此为启发式信息，以互信息相等作 为算法的终止条件。 2 1c e b a r k c c ( c o n d i t i o n a le n t r o p yb a s e da l g o r i t h mf o rr e d u c t i o no fk n o w l - e d g ew i t hc o m p u t i n gc o r e ) 文献【4 7 1 提出与m i b a r k 相似的算法c e b a r k c c ，但算法以条件属性相对 硕士学位论文 第一章绪论 于决策属性的条件信息熵为基础构造属性重要度的启发式算法，约简前后能保证 信息系统条件熵不发生变化。 3 、c e b a r k n c ( c o n d i t i o n a le n t r o p yb a s e da l g o r i t h mf o rr e d u c t i o no fk n o w l - e d g ew i t h o u tc o m p u t i n gc o r e ) 此算法也由文献 3 0 1 提出，但它不用计算决策表的核属性，在条件属性集的 条件熵的基础之上直接对原有的决策表条件属性集进行约简。文献 4 8 以反例证 明了c e b a r k n c 算法对于不一致决策表仍可能存在冗余属性。通过综合代数观 与信息观属性重要度的度量方法，提出了一种新的方法，复杂度与c e b a r k n c 同。文献【3 0 对三个算法进行了详细的分析。它引入核值比( 核的基约简结果的 基) ，当核值比较大时m i b a r k 与c e b a r k c c 比c e b a r k n c 效果要好，而核 值比较小时相反。 4 其他知识约简算法 除了以上方法外，学者们通过综过几种观点的综合或引入新的知识概念产生 了许多不同计算方法，文献 5 提出归并的约简分析方法，文献 4 9 】通过与遗传算 法相结合，并采用加权平均的属性重要度和知识量作为启发式信息指导约简，提 出了一种改进的基于核子集的知识约简算法。文献 2 7 】 5 0 】综合信息观与代数观 的优缺点提出了两种观点的综合方法。文献 5 1 分析代数约简与启发式两种属性 重要度定义的不完备性，提出一种加权平均属性重要度定义构造的相关算法。文 献 5 2 1 提出平均决策强度和决策熵的概念建立两种新的知识约简定义，使之对不 相容决策表约简的结果也是一致的。此外还有文献 5 3 】【5 4 的概念格、滤除性质 1 5 5 11 5 6 1 、模糊粗糙【5 7 i1 5 s l 、遗传【”11 6 0 1 、蚁群【6 1 1 、集值【6 2 】等。 对于不协调信息系统，文献【6 3 】给出了不协调信息系统知识约简的两种定 义，即分布约简与分配约简，讨论了它们的等价形式。文献 6 4 提出一种最大分 布约简不协调信息系统的知识约简概念，它弱于分布约简，克服了对信息系统过 于苛刻的要求。同时，它又克服了分配约简可能产生与原系统不相容命题规则的 缺陷。文献【6 5 】给出两种变精度粗糙集模型上的知识约简概念，即p 上、下分布 约简。讨论各种知识约简之间的关系。证明了分布协调集既是b 上分布协调集， 也是b 下分布协调集。同时给出了最大分布约简与p 下分布约简、分配约简与p 上分布约简等价的条件。文献【6 6 】用严凸函数定义决策表的知识约简，证明用严 凸函数定义的知识约简同分布约简是等价的，并给出严凸函数定义的相对约简的 一个判定定理。 知识约简的目标就是求得最优约简，但目前约简算法寻找一个信息系统的最 小约简具有指数级复杂度。对启发式算法的改进只是对属性重要度的度量方式的 修改，并不能改变贪心算法易落入局部最优的趋向；基于遗传算法的知识约简虽 6 硕士学位论文第一章绪论 然做到了并行搜索，同时缩小了搜索空间，但其收敛性还是个待研究的问题，且 该算法也并不能保证搜索方向不落入局部最优。因此，寻求快速高效的知识约简 算法仍然是粗糙集理论的主要研究内容。 1 3 本文主要研究内容 粗糙集理论作为处理不精确、不一致和不完备信息的新型数学工具具有许多 优点。粗糙集理论具有严格的数学基础，有一整套处理数据分类问题的数学方法， 特别当数据是不确定，不完整和不精确的时候；将知识定义为不可分辨关系的簇， 因此，知识有比较清晰的数学含义，很方便用数学方法来分析处理；运用粗糙集 理论可分析隐藏信息中的规则，不对原始数据做任意的处理，只对所产生的规则 区为确定与不确定规则；粗糙集理论无需提供除问题所需处理的数据集合之外的 任何附加知识，对问题的处理比较客观的。 但粗糙集理论在实际运用中针对大量或海量数据，原有数据分析方法效率 低，在一定程度上限制了该理的发展，须对粗糙集计算理论进行优化，发展完善 相关算法。本文分析了算法低效性的根源，针对粗糙集知识约简计算理论与方法 的相关问题进行研究，主要研究工作包括： ( 1 ) 比较粗糙集理论几种传统知识约简模型，阐述各种方法的优缺点；对原 有知识约简模型的核与约简进行深入研究，证明了差别矩阵约简模型与基于正域 约简模型两者的等价性，代数观与信息熵观点约简模型之间的包含性。 ( 2 ) 分析差别矩阵知识约简的本质，对原有差别矩阵进行修正；在差别矩阵 求核过程中，同时提取用于约简的有效分辨信息。通过有效分辨信息集合包含关 系的消除，提出一种以属性频度作为启发式信息的最优约简计算方法。同时在数 据动态更新时，给出了分辨信息集下核与约简的增量式更新算法。实验仿真结果 显示，新启发式约简算法得到约简与所有约简计算算法产生的最优约简一致，说 明了算法的有效性。 ( 3 ) 在p a w l a k 知识约简定义下，证明了决策信息系统约简的重要性质。基于 证明的性质给出了一种新的基于改进差别矩阵所有约简计算算法，将所有约简计 算时间复杂度降为非指数级，低于已有文献提出的约简计算复杂度。理论分析与 仿真实验表明，新算法在效率上较现有的算法有显著的提高。 ( 4 ) 深入研究知识约简完备算法的定义，指出了现有差别矩阵知识约简算法 的不足，对本文提出的新算法完备性进行证明，从理论上完善了粗糙集理论知识 约简方法。 硕士学位论文第一章绪论 1 4 本文结构组织 本文共分五章，总体结构组织如下： 第一章主要介绍粗糙集理论提出的背景，知识约简国内# i - # h 关研究现状，简 述本文主要研究研究工作，并给出论文各章结构安排。 第二章简要介绍经典粗糙集方法的基本理论。主要包括知识、划分、等价关 系、上下近似、约简、核、信息系统和决策系统等概念以及粗糙集的基本知识约 简各类方法相关定义等。 第三章着重分析差别矩阵知识约简方法，对原有差别矩阵求核过程进行改进 与扩展，提出一种基于改进差别矩阵最优约简计算及增量式更新方法，并对算法 的有效性与效率与同类相关算法进行实验仿真对比。 第四章针对约简算法完备性深入分析，差别矩阵信息进行包含关系消除，改 进原有属性重要性度量方法，提出新的所有约简计算算法。证明了本文提出的新 算法完备性，并对新所有约简计算算法进行理论分析与实验仿真。 第五章归纳总结本文的研究工作，并展望今后进一步的研究工作。 1 5 本章小结 现实应用中，数据量的不断增大给正在迅速发展中的粗糙集理论方法与技术 提出了挑战，知识约简算法优化的研究是解决大型决策信息系统海量性和复杂性 问题的一种有效方法。本章主要简介粗糙集理论的诞生背景、发展历程、以及一 些应用领域；对知识约简国内外相关研究现状进行综述；简述本文的研究内容； 最后给出论文的总体结构组织。 8 镢i l | 论文第二章粗糙集理论 第二章粗糙集理论 机糙集理论是一种刻画不完整性和不确定性的数学工具，能有效地分析和 处理各种信息，并从中发现隐含的知识，揭示潜在的规律。它自问世以来得到了 广泛应用和深入发展，为机器学习、知识发现、决策分析、专家系统、模式识别、 模糊控制等各领域提供了一种新的数据分析方法。 2 1 集合与关系 集合是现代数学中非常重要的概念，粗糙集理论是对经典集合理论的扩展。 一定范围的、确定的、可以区别的事物，当作一个整体来看待，就叫做集合，简 称集，其中各事物叫做集合的元素或简称元。本节简单介绍在粗糙集中将要用到 的关于集合和关系的基本知识【6 7 】f 6 引。 给定两个的元素x 、y 组成的序列记作q ，炉，称为二重组或序偶。序偶可以 看作是具有两个元素的集合，但它与一般集合不同之处是序偶具有确定的次序。 在集合中 x ，y ) = 钞，x ) ，但对序偶q ，户9 ，痧。 定义2 1 令彳和曰是任意两个集合，若序偶的第一个成员是么的元素，第 二个成员是b 的元素，所有这样的序偶集合，称为集合彳和b 的笛卡尔乘积或 叉积。记作a x b ，而a x b 的子集叫做a 到b 的一个二元关系。 a x b = x r z ) 二元关系的反自反、反对称的定义可参照自反与对称似定义。如给定一集合 a ，且尺为定义在集合彳上的一个二元关系，若r 满足自反、对称和传递性质， 则尺称为等价关系。 定义2 5 设尺为集合彳上的等价关系，对任何口彳，集合 a l r = x ix 彳，池) 称为元素a 形成的r 等价类。 定义2 6 设r 为集合a 上的等价关系，其等价类集合 a r l a e a 称作4 关于 尺的商集，记作a r 。 集合彳上的等价关系r 实际上决定了一个划分，该划分就是商集a r 。集合 a 上的一个划分也确定彳的元素间的一个等价关系。 粗糙集理论基础源于经典集合理论，等价关系、等价类、划分这些概念在粗 糙集理论中起着非常重要的作用。 2 2 知识与分类 在粗糙集理论中，知识被认为是对对象进行分类的能力。假定具有全域内对 象的必要信息或知识，则通过这些知识能够将中的对象划分到不同的类集。而分 类实际上可以理解为等价关系，这些等价关系可对论域进行划分。对于论域中由 等价关系划分出的任意子集称之为等价类。知识可认为是一族等价关系，它将论 域划分成一系列的等价类。在分类过程中，相同的个体被归于同一类等价类，它 们之间的关系就是等价关系，也称为不可分辨分系。不可分辨关系这一概念在粗 糙集理论中十分重要，它是定义其它概念的基础。 设u 是非空有限论域，r 是【，上的二元等价关系，也称为不可分辨关系， 序对么= ( ur ) 称为近似空间。p ，力u x u ，若0 ，j ，) r ，则称对象x 与y 在近似 空间彳中是不可分辨的。u r 表示u 上由尺生成的等价类构成的集合，它构成 了u 的一个划分。在粗糙集理论中，等价关系r 下对集合u 的划分称为知识， 记为碱r 。 1 0 硕士学位论文第二章粗糙集理论 表2 - 1 实例表1 定义三个等价关系( 即属性) ：头疼尺l 、体温r 2 、肌肉疼和体温尺3 ，通过这 些等价关系，可以得到下面的三个等价类。 u 侬l = 1 ，2 ，3 ) ， 4 ，5 ，6 ) ， u 肷2 = “1 ，4 ， 2 ，5 ) ， 3 ，6 ) ) ， u r 3 = “l ，4 ) ， 2 ) ， 3 ，6 ) ， 5 ) ) 。 由此可以看出，我们可以按不同的等价关系对论域进行分类，得到不同的概 念和抽象。其中，有的概念是有用的，有的是无价值的，知识获取就是要用最小 的知识获得有用的概念，并得到概念之问的关系。 2 3 信息系统和上、下近似 对于某个领域的知识和信息，一般用信息系统来表示，它基本成分是研究对 象的集合，而这些对象的知识是通过指定对象的基本特征( 属性) 和它们的特征值 ( 属性值) 来描述。信息系统的数据以二元关系表的形式表示，关系表的行对应要 研究的对象，列对应对象的属性，对象的信息是通过指定的各属性值来表达。 一个信息系统可以表示为s = ( u a ，v , ) ，其中，u 是对象非空有限的集合， 即论域；a 是属性非空有限集合；v = u 砌圪，圪表示属性a 的值域；厂：u 彳_ y 是一个信息函数，它指定u 中每一个对象x 的属性值，即对x u ，口彳有口o ) 圪。 如果属性集合彳可以分为条件属性集c 和决策属性集d ，即a = cud ， c n d = 9 ，则该信息系统称为决策信息系统或决策表。 容易看出，任一属性对应一个等价关系，一个信息系统可以看作是一族等价 关系，即知识库。 在信息系统s = ( u , a ，) 中，令p c a ，则属性子集p 的不可分辨关系i n d ( p ) 定义为： 肋故p ) 2 g ，力u xu ：v a m p ，a ( x ) = a ) ( 2 2 ) 1 r i d ( p ) 是个等价关系，构成了u 的一个划分，用u i n d ( p ) 表示，简记为 硕士学位论文第二章粗糙集理论 u p 。u p 中的任何元素i x p = 钞i v a c p , a ( x ) = a o ) ) 称为等价类。 给定决策信息系统s = ( u , a ，v , ) ，其中a = c u d ，条件属性c 和决策属性d 导出的不可分辨关系表示为劬e = ，兄，u c i ) ，u d = y j ，圪，5 u d ) ，其中 u c 中的每一个元素x ，称为条件类，u d 中的每一个元素r 称决策类。 令艉u ，r 为一等价关系，当x 能用等价关系尺确切地描述( 即是等价关系 尺所确定u 上的基本集的并时) ，我们称x 是尺可定义的，否则称x 为尺不可 定义的。r 可定义集是论域的子集，它可在信息系统知识库中被精确地定义，而 r 不可定义集不能在这个知识库中被定义。r 可定义集也称作r 精确集，r 不可 定义集也称为尺非精确集或尺粗糙集( 在不发生混淆的情况下也简称粗集) 。 粗糙集可以近似地定义，为达到这个目的，使用两个精确集即粗糙集的上近 似( u p p e ra p p r o x i m a t i o n ) * l l 下近似( 1 0 w e ra p p r o x i m a t i o n ) 来描述。 定义2 7 给定信息系统s = ( u , a ，妙) ，设逛u ，对任一属性子集b _ c a ，x 关 于曰的下近似定义为： 星2 u 啪ly s 研( 2 - 3 ) 彳关于b 的上近似记作b ( m ，定义为： b = u y e 研b iy n 烨囝 ( 2 - 4 ) 上近似和下近似也可用以下元素集合表达： 垦( 的= x 硼i x 】曰硼( 2 - 5 ) b ( 的= x e 嘲占m 降o ( 2 - 6 ) 联于b 的下近似汜作垦( 固也称为x 的j 下域，记作p o s b ( x ) ；嘲c 矽= u 一堡 称为确负域；联于b 的上近似与下近似的差称为x 的边界域，记作b n d b ( x ) ， b n d b ( x ) = b ( x ) - - b ( x ) 。 垦或尸o s b ( x ) 是根据知识b 判断肯定能归入集删元素构成的集合。b 是根据知识b 判断可能属于x 的元素构成的集合；类似地，根据现有知识判断肯 定不属删对象组成的集合称为哟负域。边界域b n d “, x ) 是某种意义上论域的 不确定域，边界域所包含的元素是论域中不能确定是否属训元素，边界域是 判断精确与不精确、清晰与不清晰的根据。当b n d b ( x ) = o 时，则枞于b 是可 定义的，也称彤是关于b 的精确集；当b n d b ( x ) o 时，则称是关于b 的粗糙集 ( r o u g hs e t ) 。 粗糙集的不可定义性( 不确定性) 是由于粗集x 的边界不确定性引起的。集合 翮边界区域越大，其确定性程度就越小。所以可以用集合x 的近似精度和粗糙 度这两个概念来描述粗糙集x 的不确定性程度。由等价关系b 定义的集合肖的近 似精度为： 0 c 文柳= i 垦( 矽i ibc 矽i( 2 7 ) 1 2 硕士学位论文第二章粗糙集理论 其中集合牌a ，ix i 表示集合x 的基数。 近似精度是含糊信息的数学描述，成功的解决了边界区域上含糊元素的具体 数目无法计算问题。 2 4 知识约简 给定的一个知识库，是否可以用较少的知识表达同样的概念。也就是说，删 除知识库中的一些知识是否又使它能够与原来的知识库具有相同的表达能力，这 就是知识约简。知识约简是糙集理论的核心内容之一，在数据挖掘领域具有重要 的应用意义。 给定信息系统s = ( u , a ，) ，我们记由属性集b 彳所导出的等价关系为 i n a ( 8 ) 。v a a ，若锄d ( 彳) = i 力a ( a 一 d ) ) ，则称属性口是不必要的，否则口是 a 中必要的。 若在信息系统中彳中的任意属性都是必要的，则称么是独立的；否则称彳是 依赖的。 定义2 8 给定信息系统s = ( m 彳，v , ) ，子集b a 称为是a 的约简，若 i n d ( b ) = i n d ( a ) 且b 是独立的。记为：r e d ( a ) 。 根据这个定义可知，约简有两个方面的性质：首先，约简所表达的对系统 的划分与原来的知识库所形成的划分是完全一致的，即约简所表达的知识和原来 的知识具有相同的表达能力；其次，就是独立性，即最小性，约简是能够表达原 来的知识库的最小集合，约简集合中的属性不可再进行删除。 定义2 9 给定信息系统s = ( u , a ，v , ) ，么的所有约简的交集称为彳的核，记 为：c o r e ( a ) ，即c o r e ( a ) = nr e d ( a ) 。 由独立和核的定义可知，若彳是独立的，则彳中的每一个属性都为其核属性。 约简是属性中最小的子集，这个子集导出的原子集数目与由整个属性集导出的原 子集数目相同，即对论域的划分不变，它可以通过初始信息系统识别出所有可分 辨的对象。核是属性中最重要的部分，是所有约简的公共部分，其中任何一个元 素都不可能在不影响属性分类能力的情况下被删除。核是唯一的，而约简不唯一。 约简与核是粗糙集理的两个基本概念，也是信息系统知识约简的基础。 2 4 1 代数观约简 一般来说，信息系统分为有决策与无决策两种类型。对于无决策的信息系统 我们简称为信息表，带决策属性的信息系统称为决策信息系统，简称决策表。信 1 3 硕士学位论文第二章粗糙集理论 息表的约简有时也称为绝对约简，它只需保证约简后的属性是独立的。而对于决 策表的约简一般称为相对约简，由于带有决策属性，相对约简较之绝对约简相对 复杂。代数观约简就是一种相对约简计算方法。 在决策信息系统弘 中，决策属性集d 将论域u 中的对象分类， 产生划分u d ，因此可考虑属性分类相对另一属性分类的关系，即属性的相对约 简和相对核的概念。 定义2 1 0 令p 和q 是论域u 上的属性集，9 的p 的正域记为p o s e ( q ) ，定 义为： p o s e ( o ) = u 艇磁丝 ( 2 - 8 ) 相对正域p o s e ( q ) 是论域u 的所有那些使用分类u p 所表达的知识中能够 正确地分类到u q 的等价类之中的对象的集合。可以认为是一个集合类的下近 似的并集。