（运筹学与控制论专业论文）基于信息熵的数据约简算法.pdf

i at h e s i si no p e r a t i o n a lr e s e a r c ha n dc y b e r n e t i c s d a t ar e d u c t i o n a l g o r i t h m b a s e do n i n f o r m a t i o n e n t r o p y b y a ns h u a n g s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rz h a n gx u e f e n g n o r t h e a s t e r nu n i v e r s i 够 j a n u a r y2 0 0 8 ，il iiullilj， jjl-ll 1，j ，flf 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包括其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示感 谢。 学位论文作者签名：譬炙 签字日期：2 叩富年1 月1 日 学位论文版权使用授权书 本学位论文作者完全了解东北大学有关保留、使用学位论文的规定： 即学校有权保留并向国家有关部门和机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容 编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： - j 东北大学硕士学位论文 摘要 基于信息熵的数据约简算法 摘要 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来 越多，而大量激增的数据背后隐藏着许多重要的信息。数据挖掘，就是从大量数据中提 取或“挖掘”隐含的、事先未知的、潜在有用的信息。 粗糙集理论是一种新的处理模糊和不确定知识的数学工具。该理论的特点是不需要 任何先验知识，或任何附加信息，能有效地分析和处理不精确、不完整和不一致等各种 不完备信息，并从中发现隐含知识，揭示潜在规律。它是一种新的数据挖掘技术。属性 约简是粗糙集理论的核心内容之一。 本文把信息熵理论中的互信息作为启发信息，得出两种新的属性约简算法。第一个 算法是以互信息作为启发信息，对于能够直接决策的对象直接列出决策结果，然后再对 其余的对象进行决策，这样做减少了不必要的重复。这里注意的是同一路径上的属性是 不能重复的，这也是决策树的一种剪枝方法。第二个算法以空集作为约简的起点开始搜 索，采用回溯的分析方法，减少了搜索空间，提高了算法的效率。这两种算法都可以减 小搜索的次数，从而减少了搜索空间。最后分别用实例验证了这两种算法的正确性和高 效性。 经典的粗糙集理论主要用于离散特征值的情形，信息熵也主要用于离散值信息系 统，而实际的数据不仅有离散的也有连续的情形。最后介绍了模糊粗糙集信息熵的基本 理论，并将其应用到连续值评估模型中，提出了一种基于模糊熵的评估模型的属性约简 算法，并且用实例验证了算法的有效性。 【关键词：粗糙集：数据挖掘；可辨识矩阵；属性约简；信息熵；模糊熵 l 0 l l y i n f 0 r m a t i o ne n t r o p v iv a bs t r a c t a 1 0 n gw i t l lm eq u i c kd e v e l o p m e n to fd a t a b 嬲et e c h m ca i l dw i d e l y 印p l i c a t i o no f d a t a b a s em a i l a g e m e n ts y s t e m ，m e r ea r cm o r ea i l dm o r ed a t a b a u s e sm a tp e o p l eh a v e a c c l m l u l a t e d t h e r ei sm u c hi r i l p o r t 锄ti n f o r m a t i o nb e h i n d 黟e a tq u a l l t i t i e sd a t a d a t am i m n g i sc x 仃a c t i n go rm i i l i n gi n f o 咖a t i o nt l l a ti si m p l i e d ，u n l ( 1 1 0 w n ，l a t e n ta n du s e m l r o u 曲s e tn l e o r yi san e w m a t ht o o lt 0d e a lw i m 如z z y 觚du n c e r t a i nk r l o w l e d g e t h e 仃a j to fr o u 曲s e ti st 1 1 a tr o u g hs e td on o tn e e da n y 仃a l l s c e n d e n tk n o w l e d g eo r 印p e n d i n f o 肌a t i o n r o u 曲s e tc 0 u l dd e a lw i mi m p r e c i s e 、h a l 铀a l ( e d 、d i s a c c o r di n f o 册a t i o n ，丘o m w h i c hi tc o u l df o u n di m p l i e di m o w l e d g ea n do p e no u tl a t e n tm l c s r o u 曲s e ti san e wt o o lo f d a t am i i l i n g a t t r i b u t er e d u c t i o ni sc o r eo fr o u g l ls e tt l l e o r y t h i sa n i c l et a l ( e se n 仃d p ya sh e u r i s t i ci n f o m a t i o n t w on e wa 嘶b u t er e d u c t i o n a l g o r i t s 盯eo b t a i n e d t l l ef i r s to n e t a l ( e se n t r o p y 鹊h e 谢s t i ci n f o m a t i o n ，a n dl i s t sa l lt 1 1 e r e s u l t sw h e nm eo b j e c t sc o u l dr e a c had e c i s i o nd i r e c t l y ，a n dt h e na n a l y s e st h eo m e ro b j e c t s s ot h ea l g o r i t h mc o u l d 倒u c en e e d l e s sr e p e a t i ts h o u l dp a ya t t e n t i o nt ot h a ta t t r i b u t e sn e e d n o tr 印e a tw h i c ha u r e0 nt h es 锄eb r a i l c h ，w h i c hi sag o o dw a yo fp m n i n g t h es e c o n do n e s t a r t ss e a r c h i n gb a s e do ne m p t ys e t ，锄da d o p t sb a c k d a t ea l g o r i t h n l t h ea l g o r i t h i nc o u l d r e d u c es e a r c h i n gs p a c ea j l de n h a n c ea l g o r i t h me 伍c i e n c y t h et w oa l g o r i t h m sc o u l dr e d u c e s e a r c h i n gt i m e s a j l d s p a c e a tl a s t ，t h ee 伍c i e n c yo ft h et w oa l g o r i t h m s i s p r o v e nb y i n u s t r a t i o n s c l a s s i c a lr o u g hs e tt h e o 巧i su s e dt od e a lw i t hd i s c r e t ev a l u e s e n t r o p yi sa l s ou s e dt o d e a lw i t hi n f o r n l a t i o ns y s t e mw i t hd i s c r e t ev a i u e s b u tt h er e a ld a t aa r en o to n l yd i s c r e t e v a l u e sb u ta l s or e a lv a l u e s a tl a s t ，t h ea r t i c l ei n t r o d u c e sb a s i ct h e o 叫o fm z z ye n t r o p ya n d e v a l u a t i o nm o d e l i tp u t sf o n v a r da na l g o n t h mb a s e do n 几z z ye n t m p ya p p l i e di ne v a l u a t i o n m o d e l t h ev a l i d i t yo ft h ea l g o r i t h mi sp r o v e nw i t ha ne x a m p l e 厂 一，、i 东北大学硕士学位论文 a b st r a c t k e yw o r d s ：加u g hs e t ；d a t am i i l i n g ；d i s c e n l i b l em a 伍x ；a t t r i b u t er e d u c t i o n ；i n f o n i l a t i o n e n t r o p y ；勉z ye i l 仃o p y i v 东北大学硕士学位论文目录 目录 独创性声明i 摘要i i a b s t r a c t ：i i i 第1 章绪论1 1 1 课题的研究背景与意义1 1 2 粗糙集的研究现状及在数据挖掘中的应用现状1 1 3 论文内容及结构介绍3 第2 章数据挖掘概述5 2 1 数据挖掘与知识发现的概述5 2 2 数据挖掘的定义6 2 2 1 数据挖掘的技术定义6 2 2 2 数据挖掘的商业定义6 2 3 数据挖掘的过程7 2 4 数据挖掘分类方法8 2 5 数据挖掘常用工具1 0 2 6 本章小结l o 第3 章粗糙集理论基础1 l 3 1 粗糙集理论基本概念1 l 3 2 信息系统理论基本概念：1 3 3 3 本章小结1 4 第4 章几种常见的约简算法1 5 4 1 几种常见的约简算法1 5 4 1 1 一般约简算法1 5 4 1 2 值约简算法1 6 4 1 3 基于可辨识矩阵的基本属性约简算法17 v 东北大学硕士学位论文目录 4 1 4 基于可辨识矩阵的属性频度约简算法1 8 4 2 基于可辨识矩阵的约简算法的改进算法1 9 4 2 1 对算法4 4 的分析1 9 4 2 2 基于可辨识矩阵的改进算法1 9 4 2 3 实例分析2 1 4 3 本章小结2 2 第5 章基于信息熵的约简算法2 3 5 1 信息熵基础知识2 3 5 2 基于互信息的相对约简算法2 5 5 3 基于信息熵与决策树的规则提取算法2 6 5 3 1 决策树2 6 5 3 2 基于互信息与决策树的规则提取算法2 6 5 3 3 实例分析2 8 5 4 基于信息熵和回溯算法的约简算法3 0 5 4 1 回溯算法的主要思想3 0 5 4 2 算法具体步骤及程序3 l 5 4 3 实例分析3 2 5 5 本章小结3 3 第6 章基于模糊熵的评估模型的属性约简3 4 6 1 模糊粗糙集的基本概念3 4 6 2 模糊粗糙集的信息熵3 5 6 3 评估决策的基本思想3 6 6 4 基于模糊熵的评估模型的属性约简3 8 6 5 实例分析3 9 6 6 本章小结3 9 第7 章结论与展望4 l 参考文献4 3 致谢4 6 v i 东北大学硕士学位论文第1 章绪论 第1 章绪论 1 1 课题的研究背景与意义 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来 越多，而大量激增的数据背后隐藏着许多重要的信息，因此人们希望能够对其进行更高 层次的分析，以便能够更好地利用这些数据。目前数据库系统可以高效地实现数据录入、 查询、统计等功能，但是无法发现数据中存在的关系和规则，无法根据现有数据库中的 数据预测未来的发展趋势，缺乏挖掘数据背后隐藏的知识的手段方法，导致了“数据爆 炸但知识贫乏 的现射1 1 。 由此，数据挖掘于2 0 世纪8 0 年代中后期出现了，并在9 0 年代得到了飞速的发展。 数据挖掘，就是从大量数据中提取或“挖掘 隐含的、事先未知的潜在有用信息。数据 挖掘涉及到多学科技术的集成。在数据挖掘中，所存储的数据往往含有大量冗余或者不 完整的属性，严重降低了数据挖掘算法的时间效率和算法质量。如何删除冗余的属性， 却是一个极其具有挑战性的工作。这就是特征选择所需要完成的工作。 近来，粗糙集理论在数据挖掘与知识发现方面得到了广泛的发展。粗糙集理论的特 点是它无需提供问题所需处理的数据集合之外的任何先验信息，如统计中要求的先验概 率和模糊集中要求的隶属度，而且算法简单、易于操作等。近几年来，粗糙集理论已应 用于机器学习、知识发现、决策支持和分析、专家系统、智能控制、模式识别等领域。 属性约简是粗糙集理论的核心内容之一【2 】，众所周知，知识库中的知识( 属性) 并 不是同等重要的，甚至其中某些知识是冗余的。特别是当数据是随机采集时，其冗余性 更为普遍。冗余知识的存在，一方面是对资源( 存储空间) 的浪费；另一方面，干扰人 们作出正确而简洁的决策。所谓属性约简，就是在保持数据库分类或决策能力不变的条 件下，删除其中不相关或不重要的知识。这种思想和方法给数据挖掘注入了新的生命力， 大大促进了数据挖掘的发展。 1 2 粗糙集的研究现状及在数据挖掘中的应用现状 粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年首先提出的的一个分析数据的数学理 论，在分类的意义下，这个理论定义了模糊性和不确定性的概念。在该理论刚刚问世的 东北大学硕士学位论文第1 章绪论 几年，由于理论还不成熟，因而并未受到国际计算机学界的重视，当时主要在波兰等几 个东欧国家进行研究。直到8 0 年代末，粗糙集理论才引起了世界各国学者的注意。自 1 9 9 2 年在波兰举行了粗糙集理论的第一界国际研讨会以来，每年一度的国际粗糙集理论 研究会才定期在世界各国召开。目前粗糙集理论已经成为国际上人工智能研究的热点。 迄今为止，国内外的知名专家学者发表了大量高质量、高水平的学术论文和研究成 果，粗糙集已在网络应用、模式识别、预测与诊断和知识发现等方面得到了广泛应用。 目前，基于粗糙集理论的k d d ( k h o w l e d g ed i s c o v e 巧i i ld a t a b a l s e s ) 系统主要有 l e r s 、r o s e 、k d d - r 、和r o u 曲e n o u 曲等。基于粗糙集的k d d 系统一般由数据预 处理、基于粗糙集或其扩展理论的数据约简、决策算法等部分组成。 l e r s ( l e 锄i n gf 而me x a i r l p l e sb a s e do nr o u g l ls e t ) 系统是美国k a n s a s 大学开发的基 于粗糙集的实例学习系统，它已经在n a s a 的j o l l l l s o n 空间中心应用多年。它是作为一 种开发专家系统的工具被应用的，l e r s 还被广泛地用于环境保护、气候研究和医疗研究。 r o 是由波兰p o z i l a i l 科技大学开发的，主要用于决策分析。r o s e 是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 支持新对象的分类。r o s e 已经在许多实际领域中得到应用，其计算模块具有以下功能： 数据校验和预处理、连续属性值的离散化、用标准粗糙集模型或可变精度粗糙集模型对 条件属性进行约简、考察属性对分类属性的重要性、获取决策规则、对新目标进行分类 盘莹 专手。 加拿大r e 百n a 大学基于可变精度粗糙集模型，采用知识发现的决策矩阵方法开发 了k d d r 系统，该系统被用于医疗数据分析，电信工业的市场研究等领域。 挪威t r o l ld a t ah c 公司开发了数据挖掘工具r o u g he n o u 曲。该系统根据信息系统 计算得到区分矩阵，采用遗传算法生成约简。 w z i a r k o 提出一种可变精度粗糙集模型v p r s ( a b l ep r e c i s i o nr o u 曲s e t m o d e l 2 ) 1 8 】，该模型引入错误分类率( 0 0 5 ) ，给出错误率低于预先给定值的分类 策略。而且v p r s 是p a w l a k 粗糙集模型的直接扩展，它完全继承了粗糙集的性质，拥 有粗糙集的所有优点；当错误分类率为o 时，v p r s 模型就蜕化为传统的粗糙集模型。 可变精度粗糙集模型很好的解决了属性间无函数或不确定关系的数据分类问题，拓广了 粗糙集理论的应用范围。在此基础上j d k a t z b e r g 和w z i 酞。又进一步提出了不对称边 界的v p r s 模型【3 1 ，即在上下近似的定义中可以取不同值，从而拓广了v p r s 的应用 东北大学硕士学位论文第1 章绪论 范围，使模型更具应用潜力。 数据集中往往存在缺失的属性值，以不可区分关系为基础的p a w l a l ( 粗糙集理论无 法处理这种情形，为扩展粗糙集的能力，可用相似关系来代替不可区分关系作为粗糙集 的基础【4 1 ，并建立相应的粗糙集模型。当面对数据库中缺失属性值的情况时，一个简单 的相似关系可定义如下，这里? 代表未知或不需考虑：乇( x ，y ) = 缸u ，j ，【厂iv 口( 功 = 口( j ，) 或口( x ) = ? 或口( y ) = ? ) 利用相似关系替代不可区分关系后产生的最主要的变化就是 相似类不再形成对集合的划分，它们之间可能是相互重叠的。在相似关系的基础上定义 了相似集、相似决策类及相对吸收集，相似模型在实践使用中具有比经典粗糙集模型更 好的使用性能。 粗糙集理论具有广阔的发展空间，值得重视的课题包括基于粗糙集理论的粗糙逻辑 的研究、粗糙函数的理论和实践的研究、基于粗糙集理论的控制、粗糙集理论对神经网 络和遗传算法的开发等。同时如何将粗糙集理论、模糊集理论、证据理论和概率论等不 确定的理论用一个统一的逻辑模型来解释也值得关注【矧。从数据库知识发现的角度，也 有一些可能的研究方向及应用领域，包括高效约简算法、大数据集问题、多方法融合、 增量算法、信息不一致问题等。 粗糙集理论以基于集合的整体直接逼近的方式，去完成非确定不完全信息条件下的 知识推理，作为一种较有前途的软计算方法，其取得的研究成果是令人瞩目的，未来会 在更多的领域中发挥作用。 1 3 论文内容及结构介绍 本文主要介绍了基于粗糙集的数据挖掘方法，各章节的安排如下： 第1 章：课题的研究意义与背景，主要介绍了数据挖掘是在什么背景下提出的以及 粗糙集成为数据挖掘的方法之一：粗糙集的国内外研究现状及其在数据挖掘中的应用现 状，主要介绍了粗糙集的研究发展进展情况和取得的成果。 第2 章：对数据挖掘进行概述，主要包括数据挖掘与知识发现的概述；数据挖掘的 定义，包括技术定义和商业定义；数据挖掘的过程，包括三个主要阶段：数据准备，数 据挖掘以及结果表达和理解：数据挖掘分类方法，包括9 种常见的方法以及数据挖掘的 常用工具。 第3 章：主要介绍粗糙集理论基础，包括 f l 糙集理论基本概念、信息系统理论基本 东北大学硕士学位论文第1 章绪论 概念。这些概念为后面章节的约简算法做了铺垫。 第4 章：主要介绍了几种约简方法，包括值约简算法，基于可辨识矩阵的基本属性 约简算法和基于可辨识矩阵的属性频度约简算法。然后对基于可辨识矩阵的基本属性约 简算法进行了的改进，并且通过新老算法的比较证明了新算法的有效性。 第5 章：主要介绍了信息熵的基本理论，提出了一种基于信息熵和决策树的决策规 则提取算法，并且通过实例验证了该算法的有效性、正确性及先进性。同时提出了一种 基于信息熵与回溯算法的约简算法，并用实例加以验证。 第6 章：介绍了模糊熵的基本概念和评估模型的基本思想，提出了一种基于模糊熵 的评估模型的属性约简算法，并且用实例验证了算法的有效性，实现了对连续值信息系 统的属性约简。 第7 章：结论与展望。 4 东北大学硕士学位论文第2 章数据挖掘概述 第2 章数据挖掘概述 2 1 数据挖掘与知识发现的概述 随着计算机、网络和通讯等信息技术的高速发展，信息处理在整个社会规模上迅速 产业化。而这种产业化在技术上就表现为整个社会规模的大规模数据操作的产业化。近 些年来，商务贸易电子化、企业和政府事务电子化的迅速普及都产生了大规模的数据， 同时日益增长的科学计算和大规模的工业生产过程也提供了海量数据；而日益成熟的数 据库系统和数据库管理系统都为这些海量数据的存储和管理提供了技术上的保证；另一 方面，计算机网络技术的长足进步和规模的爆炸性增长，则为数据的传输和远程交互提 供了技术手段，特别是国际互联网更是将全球的信息源纳入了一个共同的数据库系统之 中。 毫无疑问，这些庞大的数据库及其中的海量数据是极其丰富的信息源，但是仅仅依 靠传统的数据检索机制和统计分析方法已经远远不能满足需要了。随着数据库技术的迅 速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多。激增的数据背后隐 藏着许多重要的信息，人们希望能够对其进行更高层次上的分析，以便更好的利用这些 数据。由于传统的数据库管理系统不能满足人们对大量数据进行知识抽取、发现数据间 隐藏的依赖关系，从而为决策提供科学支持的需要。数据挖掘和知识发现正是在这种情 况下产生发展的一种新型数据分析技术。 用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后 的知识，这两者的结合促成了数据库中的知识发现的产生。因此，一门新兴的自动信息 提取技术：数据挖掘【5 1 和知识发现【6 】，应运而生并得到迅速发展。它的出现为自动和智能 地把海量的数据转化成有用的信息和知识提供了有效的手段。 知识发现( k d d ，l o o w l e d g ed i s c o v e 叫i nd a t a b a s e ) 于1 9 9 5 年在加拿大召开了第一届 知识发现和数据挖掘国际学术会议上给出了确切的定义。知识发现的确切字面定义是识 别出存在于数据中的有效的、新颖的、具有潜在价值的并能够最终被理解的模式的过程。 数据挖掘( d m ，d a t am i n i n g ) 是指从数据库的大量数据中提取隐含的、先前未知的并 有潜在价值的信息和知识的过程。在这个定义中，要求数据源应该是大量的、真实的、 含有噪音的，所发现的信息和知识是潜在的并隐藏在大量数据背后的，是用户感兴趣的、 东北大学硕士学位论文第2 章数据挖掘概述 可理解的、可运用的知识。 可见，这两个术语的内涵大致相同，但知识发现是从数据库中发现知识的全部过程， 而数据挖掘是此过程的一个特定的、关键的步骤。数据挖掘是知识发现最关键的步骤， 也是知识发现技术难点，所以在通常情况下可以不加区分的使用二者。 2 2 数据挖掘的定义 数据挖掘的定义有很多，表达方式虽然不同，但本质都是一样的。这里主要从技术 角度和商业角度给出数据挖掘的定义。 2 2 1 数据挖掘的技术定义 从技术角度【，j 看，数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实 际数据中，提取隐含在其中的、人们不知道的、但又是潜在有用的信息和知识的过程。 人们将数据看作形成知识的源泉，好象从含金的大量矿石中淘金一样。原始数据可 以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形和图象数 据，甚至是分布在网络上的异构数据。发现知识的方法可以是数学的，也可以是非数学 的；可以是演绎的，也可以是归纳的。发现的知识可以用于信息管理，查询优化，决策 支持和过程控制等。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次 的简单查询，提升到从数据库中挖掘知识，提供决策支持。在这种需求的推动下，汇集 了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并 行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的 技术研究和开发热点。 2 2 2 数据挖掘的商业定义 从商业应用角度【7 1 看，数据挖掘是一种崭新的商业信息处理技术。其主要特点是对 商业数据库中大量业务数据进行抽取、转化、分析和模式化处理，从中提取辅助商业决 策的关键知识，即从一个数据库中自动发现相关商业模式。 数据挖掘是利用统计学和机器学习的技术，探求那些符合市场、客户行为的模式。 目前，数据挖掘己经可使挖掘技术自动化，将数据挖掘和商业数据仓库相结合，以适当 的形式将挖掘结果展示给企业经营管理人员。对于数据挖掘的应用不仅依靠良好的算法 6 东北大学硕士学位论文第2 章数据挖掘概述 建立模型，而且更重要的是要解决如何将数据挖掘技术集成到当今复杂的信息技术应用 环境中。其次，还要有数据挖掘分析人员的参与，因为数据挖掘技术不具备人所特有的 经验和直觉，不能区分哪些挖掘出的模式在现实中是有意义的，哪些是没有意义的。因 此，数据挖掘分析人员的参与是必不可少的。 2 3 数据挖掘的过程 数据挖掘的过程【刀可以分为三个主要阶段：数据准备，数据挖掘以及结果表达和理 解。如图2 1 所示。 数据源 图2 1 数据挖掘的过程 f i g 2 1p r o c e s so fd a t am i n i n g 第一步：数据准备 l 数据集成：将多文件或多数据库运行环境中的数据进行合并处理，解决语义模糊 东北大学硕士学位论文第2 章数据挖掘概述 性，处理数据中的遗漏和清洗脏数据等。 2 数据选择：为知识发现的目标搜索和选择有关的数据，这包括不同模式数据的转换 和数据的统一和汇总。数据选择的目的是辨别出需要分析的数据集合，缩小处理范围， 提高数据挖掘的质量。 3 数据预处理：对数据进行清理和充实等预处理工作。也包括对数据编码，数据库中 字段的不同取值转换成数码形式将有利于搜索。 第二步：数据挖掘 此阶段进行实际的挖掘操作，利用机器学习、统计分析等方法，从数据库中发现有 用的模式或知识。 第三步：结果表达与解释 根据最终用户的决策目的对提取的信息进行分析，把最有价值的信息区分出来，并 且通过决策支持工具提交给决策者。这一步骤的任务不仅是把结果表达出来，还要对信 息进行过滤处理。如果不能令决策者满意，需要重复以上数据挖掘的过程。 2 4 数据挖掘分类方法 从不同的角度看，数据挖掘技术有多种分类方法0 1 ，如根据发现的知识种类分类， 根据挖掘的数据库类型分类，根据挖掘方法分类，根据挖掘的途径分类，根据所使用的 技术分类等等，目前常用的挖掘技术内容包括如下： ( 1 ) 决策树方法 利用信息论中的互信息寻找数据库中具有最大信息量的字段，建立决策树的一个节 点。再根据字段的不同取值建立树的分支，在树的分支子集中重复建立树的下层节点和 分支的过程，即可建立决策树。国际上最有影响和最早的决策树算法r q u i n l a i l 研制的 i d 3 方法，数据库越大它的效果越好。此后又发展了各种决策树方法，如i b l e 方法使 识别率提高了1 0 。 ( 2 ) 神经网络方法 它模拟人工神经元结构，以m p 模型和h e b b 学习规则为基础，用神经网络连接的 权值表示知识，其学习体现在神经网络的逐步计算上。目前主要有3 大类神经网络模型： 1 ) 前馈式网络，它以感知机、反向传播模型、函数型网络为代表，可用于预测、模式识 别等方面；2 ) 反馈式网络，它以h o p 6 e i d 的立三模型和连续模型为代表，分别用于联想 记忆和优化计算；3 ) 自组织网络，它以a r t 模型、k o h o i o n 模型为代表，用于聚类。 r 东北大学硕士学位论文第2 章数据挖掘概述 ( 3 ) 粗糙集方法 它将知识理解为对数据的划分，每个被划分的集合称为概念。主要思想是利用已知 的知识库，将不精确或不确定的知识用已知的知识库中的知识来近似刻画处理。 ( 4 ) 概念树方法 对数据库中记录的属性字段按归类方式进行抽象，建立起来的层次结构称之为概念 树。利用概念树提升的方法可以大大浓缩数据库中的记录，对多个属性字段的概念树进 行提升，将得到高度概括的知识基表，然后再将它转换成规则。 ( 5 ) 遗传算法 这是模拟生物进化过程的算法，是自然遗传学与计算机科学相互结合、相互渗透而 形成的新的计算方法。遗传学习开始时，首先创建一个由随机产生的个体组成的初始群 体，每个个体可以用一个二进制符号串表示。根据适者生存原则，形成由当前群体中最 优的个体组成的新的群体，并生成这些个体的后代。个体的优劣由适应度函数给出，后 代通过选择算子、交叉算子和变异算子生成。整个过程直到群体进化到每个个体都满足 指定的适应度阈值为止。，这种遗传算法可以起到产生优良后代的作用，这些后代需满 足适应度值，经过若干代的遗传，将得到满足要求的后代( 问题的解) ，遗传算法已在 优化计算和分类机器学习方面显示了明显的优势。 ( 6 ) 公式发现 在工程和科学数据库( 由实验数据组成) 中，对若干数据项( 变量) 进行一定的数 学运算，求得相应的数学公式。比较典型的b a c o n 发现系统完成了对物理学中大量定 律的重新发现，其基本思想是：对数据项进行初等数学运算( 加、减、乘、除) ，形成 组合数据项，就得到了组合数据项等于常数的公式。 ( 7 ) 统计分析方法 在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示的确定性关系) 和相关关系( 不能用函数公式表示，但仍是相关确定关系) 。对它们的分析采用如下方 法：回归分析、相关分析、主成分分析。 ( 8 ) 模糊集方法 利用模糊集理论对实际问题进行模糊评判、模糊决策、模糊模式识别、模糊聚类分 析和模糊控制。系统的复杂性越高，精确化能力就越低，即模糊性就越强，这是z a d e h 总结出来的互克性原理。 ( 9 ) 可视化技术 o 东北大学硕士学位论文 第2 章数据挖掘概述 可视化数据分析技术拓宽了传统的图标功能，使用户对数据的剖析更清楚，例如， 把数据库中的多维数据变成多种图形，这对提示数据的状况、内在本质及规律性起了很 大作用。 在这诸多方法中，粗糙集理论与方法对于处理复杂系统是一种较为有效的方法。 2 5 数据挖掘常用工具 按照数据挖掘的应用范围可以将挖掘工具分成专用型挖掘工具和通用型挖掘工具 两类。 专用型挖掘工具只要用于某个特定领域。因此，专用型数据挖掘工具针对性较强， 采用一些特定的算法对特定的数据集进行处理，数据挖掘的效率较高，挖掘出的知识的 可靠性也高，但是应用范围受到限制。 通用型数据挖掘工具一般不考虑所挖掘对象的实际含义，只提供各种通用挖掘算 法，允许用户自己定义数据源进行多模式挖掘。由于这种类型挖掘算法的通用型，在数 据挖掘过程中很难进行优化。因此，数据挖掘的效果往往不能使所有用户满意。 2 6 本章小结 本章对数据挖掘进行了综述，包括数据挖掘的定义、数据挖掘的三个过程，和数据 挖掘的9 种常见的分类方法。并且指出粗糙集方法是数据挖掘的一种较为有效的方法， 该方法将在以下章节进行详细介绍。 i o 东北大学硕士学位论文第3 章粗糙集理论基础 第3 章粗糙集理论基础 粗糙集理论是一种刻画不完整性和不确定性的数学工具，能有效地分析和处理不精 确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律。粗 糙集理论的研究已经经历了2 0 多年的时间，无论是在系统理论，计算模型的建立和应 用系统的研制开发上，都已取得了很多成果，也建立了一套较为完善的粗糙集理论体系。 由于本论文主要是研究基于粗糙集理论的知识约简算法，因此为了便于后面的阐 述，本章将对粗糙集理论的有关的概念和知识作一个简要的介绍。 3 1 粗糙集理论基本概念 定义3 1 1 近似空间( a p p r o x i m a t es p a c e ) 彳s = ( 【，r ) 是一个二元有序组，这里u 为所讨论对象的非空有限集合，称其为论域或全域n i v e r s e ) ；r 为建立在【，上的一个 等价关系的族集。 定义3 1 2 令尺为等价关系族，设p 尺，且尸q ，则n p ( 尸中所有等价关系 的交集) ，称为p 上的不可区分关系( i n d i s c e m i b i l i t yr e l a t i o n ) ，记为i n d ( p ) 。 容易看出i n d ( 尸) 也是一个等价关系，且具有唯一性。在知识库中知识粒度可由不可 区分关系i n d ( p ) 的等价类反映。 定义3 1 3 1 1 2 1 将子集x u 称为论域u 上的概念( c o n c e p t ) ，约定矽也是一个概念； 非空子族集psr 所产生的不可区分关系i n d ( j p ) 的所有等价类关系的集合即u i n d ( 尸) ， 称为u 的尸基本知识( b a s i cl “o w l e d g e ) ，相应的等价类称为知识p 的基本概念( b a s i c c o n c e p t ) 。特别地，若等价关系q r ，则称u q 为【，的q 初等知识( e l e m e n t a r y l o o w l e d g e ) ，相应等价类称为q 初等概念( e l e m e n t a r yc o n c 印t ) 。由于选取尺的不同子集 p ，可得到u 上的不同知识，故可称k = ( u ，尺) 为知识库( 1 “o w l e d g eb a s e ) 。分别称星( x ) 、 尺( x ) 为x 的尺下近似集( l o w e ra p p r o x i m a t i o n ) 和尺上近似集( u p p e ra p p r o x i m a t i o n ) 。并 将x 的尺边界域、x 的尺正域及x 的尺负域分别定义为： b n 异( x ) = 尺( ) 一星( x ) 、p o s r ( ) 2 垦( x ) 、n e g 舟( x ) 2 u 一尺( x ) 。 东北大学硕士学位论文第3 章粗糙集理论基础 由定义3 1 3 可以将星( x ) 和p o s r ( x ) 理解为根据知识尺判断肯定属于x 的u 中的 元素组成的集合，将r ( x ) 看作由知识r 判断可能属于x 的u 中元素组成的集合；那么 b n 置( 彳) 就是依据知识r 无法确定属于x 还是属于x 的u 中元素组成的集合， n e g 置( x ) 是由知识尺判断肯定不属于x 的u 中元素组成的集合。 定理3 1 1 考虑知识的依赖性，令k = ( 【，尺) 是一个知识库，p ，q 互尺，则有： ( 1 ) 知识q 依赖于知识p ( 记作pjq ) 当且仅当i i l d ( 尸) i n d ( q ) 。 ( 2 ) 知识尸与知识q 等价( 记作p 兰q ) 当且仅当pjq 且p 乍q 。 ( 3 ) 知识尸与知识q 独立( 记作尸q ) 当且仅当尸q 与p 乍q 均不成立。 显然，p 兰q 当且仅当i n d ( p ) ：i 1 1 d ( q ) 。当知识q 依赖于知识尸时，也说知识q 是 由知识p 导出的。 定义3 1 4 1 1 4 l 令p 为一族等价关系，尺p ，如果 i 1 1 d ( p ) = i n d ( p 一 尺) ) ， 则称尺为j p 中不必要的；否则称尺为尸中必要的。若每一个尺p 都是p 中必要的，则 称r 为独立的；否则称尺为依赖的。 定义3 1 5 设qs 尸，如果q 是独立的，且 i n d ( 尸) = i n d ( q ) ， 则称q 为尸的一个约简。尸中所有必要关系组成的集合称为p 的核，记作c o r e ( p ) 。p 可 以有多个约简，以刚( p ) 表示p 的所有约简的集合。 定理3 1 2 族集p 的核等于尸的所有约简的交集。即 c o r e ( p ) ：n r e d ( 尸) 。 定义3 1 6 1 1 6 1 设p 和q 为论域u 上的等价关系。q 的j p 正域记作p o s 。( q ) ，定义为： p o s p ( q ) _ ，战旦x ) ， q 的尸正域是u 中所有根据分类u p 的信息可以准确地划分到关系q 的等价类中去的 对象集合。 东北大学硕士学位论丈 第3 章粗糙集理论基础 定义3 1 7 设尸和q 为等价关系族，r 尸，如果 p o s 删p ) ( i n d ( q ) ) = p o s i n d ( p 一( i n d ( q ) ) 则称j r 为尸中q 不必要的；否则尺为尸中q 必要的。 为简单起见，用p o s p ( q ) 代管p o s i i l d ( p ) ( i n d ( q ) ) 。如果p 中的每个尺都为q 必要的， 则称p 为q 独立的。 定义3 1 8 设ss 尸，s 为p 的q 约简当且仅当s 是p 的q 独立子族且 p o s s ( q ) = p o s 尸( q ) ，尸的q 约简简称为相对约简。尸中所有q 必要的原始关系构成的集 合称为p 的q 核，简称为相对核，记为c o r e q ( 尸) 。以r e d q ( 尸) 表示所有p 的q 约简构成 的集合。 定理3 1 3 相对核与相对约简的关系为： c o r e q ( p ) 2 n r e d q ( p ) 。 3 2 信息系统理论基本概念 定义3 2 1 s = ( u ，彳，矿，厂) 是一个信息系统，其中 u = “，恐，- ，却i ) 是有限非空集合，称为论域或对象空间，u 中的元素称为对象； 彳= “，口2 ，印i ) 也是一个有限非空集合，彳中的元素称为属性；对于每个小口么，有一个映射 厂：u 一厂( u ) ， 且 y = 厂( 石) l x u ) 称为属性彳的值域。如果彳= c u d ，c n d = g ，则称信息系统s 为一个决策表，其中c 中 的属性称为条件属性，d 中的属性称为决策属性。 定义3 2 2 1 1 9 设s = ( u ，彳，y ，厂) 是一个信息系统，对于任意口互彳，记 东北大学硕士学位论文第3 章粗糙集理论基础 尺口= ( ，一) l 丘，( ) = z ，( 一) ( q b ) ) ， 则心是u 上的等价关系。记 口= l ( 誓，一) 心) ， 则u = 誓 bl 【，) 是u 上的划分。 定义3 2 3 设s = ( u ，彳，矿，) 是一个信息系统，u 的可辨识矩阵是一个刀九的对 称矩阵m = ( ) ，其元素 ，= 口l 口c ，丘( ) 丘( 一) 且( d d ，以( ) 以( 一) ) ) “，= 1 ，2 ，z ) 。 3 3 本章小结 本章主要介