（计算机应用技术专业论文）基于粗集理论的增量式属性约简研究.pdf

摘要 粗糙集理论是一个有效的数据挖掘方法，正越来越被人们所重视。 其主要思想是保持分类能力不变的情况下，利用等价类，通过约简，达 到发掘知识并简化知识的目的。 首先，本文介绍了数据挖掘和粗糙集的基本理论和主要方法。然后 研究了粗糙集理论的属性约简方法，并针对属性约简存在的问题提出了 一种基于信息熵的属性约简算法，算法中引入了信息熵准则作为属性选 择的标准。为满足数据库动态更新的需要，对该方法进行修改提出了一 种基于信息熵的增量式属性约简。最后，给出了扩充特征矩阵的定义， 提出了基于扩充特征矩阵的增量式规则提取方法。 关键词：数据挖掘粗糙集约简增量式算法特征矩阵 a b s t r a c t r o u 曲s e tt h e o r yi s a 1 1e f f e c t i v em e t l l o do fd a t am i l l i n g hi s b e i n g r e c o g n i z e d 罂翟d u a i l yn sb a s i ct h e o r yi su t i l i z i n ge q u i v a l e n c ef e l a t i o n c l a s s ，恤o u 曲r e d u c t i o n ，o b t a 证证gk n o w l e d g ea n dr c d u c t i o no fk n o w l e d g e 、v i mt h cs 锄ea b i l i t yo fc l a s s i 矗c a t i o n a tf i r s t ，t h i sp 印e rd e s c r i b e st h eb a s i cp r i n c i p l e sa n dt h em a i nm e t h o d s o fd a t am i n i n ga i l dr o u g hs e tm e o r y t h e n “s t u d i e se s s e m i a lm e t h o d sa i l d a k o r i m m so fa t 晡b u t er e d u c t i o n a n dan e w 砌b u t e sr e d u c t i o na 1 2 0 r i 恤m b 船e do ni 1 1 f 0 n n a t i o ne n 仃o p yi sp r o p o s e dt ot a c k l et l l ep r o b l e m si n v o l v e di n r o u g hs e t t h en e wa i g o r i m ma d o p t si n f o m l a t i o ne n t m p ya sa t 缸b u t e s e l e c t i n gc r i t e r i o n i no r d e rt om c c td ”a m i cd a t a b a s e ，m i sp 印e rp m p o s e sa n e wi n c r e m e n t a la t 研b u t e sr e d u c t i o na l g o r i 血mb a s c do ni 1 1 f 0 册a t i o n e n 仃i ) p yb ym o d i 母i n gt h i sm e m o d a “a s t 也ed e f i m t i o no ff 音a t u r em a 啊xi s e x t c n d e d ，b a s e do nw h i c ha ni n c r e m e n t a lm l ee x t m c t i o n a l g o r i t h mi s p r o p o s e d k e yw o r d s ：d a t am i n i n gr o u g hs e tt h e o i 了 r e d u c t i o n i n c 代m e n t a la l g o r i t h mf e a t u nm a t r i i 第一章绪论 1 1 研究的目的和意义 当今，社会已经进入了网络信息时代，计算机与网络信息技术的飞 速发展使得各个领域的信息急剧增加( 信息爆炸) ，并且由于人类的参 与使数据与信息系统中的不确定 生更加显著( 复杂系统) 。如何从大量 的、杂乱无章的、强干扰的数据( 海量数据) 中挖掘潜在的、有利用价 值的信息( 有用知识) ，这给人类的智能信息处理能力提出了前所未有 的挑战。由此产生了一个崭新领域一一数据挖掘( d m ) 。7 j 和数据库知 识发现( k d d ) 【8 】o 数据挖据是从大量的，不完全的、有噪声的，模糊的、随机的数据 集中识别有效的、新颖的、潜在有用的，以及最终可理解的模式的非平 凡过程。它是一门涉及面很广的交叉学科，包括机器学习、数理统计、 神经网络、数据库、模式识别、粗糙集、模糊数学等相关技术。数据挖 掘技术是信息技术自然演化的结果，它从一开始就是面向应用的。它不 仅是面向特定数据库的简单检索和查询调用，而且要对这些数据进行微 观、中观乃至宏观的统计、分析、综合和推理，以指导实际问题的求解， 发现事件间的相互关联，甚至利用已有的数据对未来的活动进行预测。 如数据挖掘在零售业中的应用，能够识别顾客的购买行为，发现顾客的 购买模式和趋势，改进服务质量，取得更好的顾客保持力和满意程度， 提高货品销量，减少商业成本。数据挖掘在电信业中的应用有助于理解 商业行为，确定电信模式，捕捉盗用行为，更好地利用资源和提高服务 质量。此外，数据挖掘在金融系统和生物医学等方面的研究与应用也已 获得极大成功，并促进了这些行业的发展。需要指出的是，数据挖掘所 发现的知识都是相对的，具有特定前提和约束条件，面向特定领域，同 时还要易于理解，最好能用自然语言表达发现结果。数据挖掘和知识发 现的研究成果是很讲求实际的。 进行数据挖掘的方法有很多，粗糙集方法便是其中的主要方法之 一。粗糙集理论是波兰数学家z p a w l a k 教授为开发自动规则生成系统 及研究软计算问题于1 9 8 2 年提出的，用于研究不完整数据和不精确知 识的表达、学习、归纳的数学分析理论【9j 其特点是算法简单，无需提 供问题所需处理的数据之外的任何先验信息，就可以直接从给定问题的 描述集合出发，通过不可分辨关系和等价类确定给定问题的近似域，从 而找出该问题的规律。属性约简是粗集理论中一个重要课题| l 。由于大 型数据库中常常包含许多对发现规则来讲是冗余的、不必要的属性，研 究人员发现，如果能将冗余属性删除，将大大提高系统潜在知识的清晰 度，降低发现规则的时间复杂性，提高发现效率。当然，由于粗糙集理 论未能包含处理不精确或不确定原始数据的机制，所以与其它处理不确 定性问题的理论有很强的互补性。所谓粗糙集方法，是基于一个结构( 或 一组结构) 关于一些现实的大量数据信息，以对观察和测量所得数据进 行分类的能力为基础，从中发现推理知识扣分辨系统的某些特点、过程、 对象等。粗糙集理论不仅为信息科学和认知科学提供了新的科学逻辑和 研究方法，而且为智能信息处理提供了有效的处理技术。 粗糙集理论对于人工智能和认知科学是十分重要的，自从提出以来 一直得到模糊数学创始人z a d e h 的重视，并给与很高的评价，将之列 入他新提倡的软计算( s o rc o m p m i n g ) 的基础理论之一。将粗糙集应 用于数据挖掘领域，能提高对大型数据库中的不完整数据进行分析和学 习的能力，具有广泛的应用前景和应用价值。 1 2 国内外研究现状 八十年代初，波兰数学家z p a w l a k 教授提出了用粗糙集理论来研 究不完整数船、不精确知识的表达、学习、归纳等方法。它把那些无法 确认的个体都归于边界线区域，这个区域定义为上近似集和下近似集之 差集，由于上近似集和下近似集都可以通过等价关系给出确定的数学描 述，所以含糊元素数目可以被计算出来，从而真假二值之问的含糊程度 可以计算。这套方法是与用统计方法处理不确定问题完全不同的，它不 是采用概率方法描述数据的不确定性；与这一领域传统的模糊集合论处 理不精确数据的方法也不相同。最初关于粗糙集理论的研究主要集中在 波兰，当时并没有引起国际计算机界和数学界的重视。直到1 9 9 0 年前 后，由于该理论在数据的决策与分析、模式识别、机器学习与知识发现 等方面的成功应用，才逐渐引起了世界各国学者的广泛关注。1 9 9 1 年 z p a w l a k 的专著粗糙集一关于数据推理的理论的问世标志着粗糙集 理论及其应用的研究进入了活跃时期。1 9 9 2 年在波兰召开了关于粗糙集 理论的第一届国际学术会议，这次会议着重讨论了集合近似定义的基本 思想及应用。其中粗糙集环境下的机器学习基础研究是这次会议的4 个 专题之一。1 9 9 3 年在加拿大召开第二届国际粗糙集理论与知识发现研讨 会，这次会议积极推动了国际上对粗糙集理论与应用的研究，由于当时 正值数据库知识发现( k d d ) 成为研究的热门话题，一些著名k d d 学 者参加了这次会议，并且介绍了许多应用扩展粗糙集理论的知识方法与 系统。1 9 9 5 年a c mc o m m 吼i c a t i o n 将粗糙集列为新浮现的计算机科学 的研究课题。1 9 9 8 年，国际信息科学杂志为粗糙集理论的研究出版了一 期专辑。1 9 9 9 年在日本召开第七届粗糙集、模糊集、数据挖掘和粒度、 软计算国际会议，主要阐述了当前粗糙集、模糊集的研究现状和发展趋 势。2 0 0 0 年在加拿大召开了第二届粗糙集和计算的当前趋势学术会议。 目前粗糙集理论已成为信包科学最为活跃的研究领域之一，在许多应用 领域已得到发展，如医疗数据分析、水泥窑生产控制算法、地理学、振 动分析、飞行员技能评定、开关电路综合、语言识别、近似分类、故障 诊断、成本预测等 i ”。粗糙集理论自提出以来直得到模糊数学的创始 人z a d e h 的重视，并给与很高的评价，把它列为他新提倡的软计算的基 础理论之一。 与国外相比，国内研究稍晚，没有形成整体力量。国内对粗糙集理 论的研究始于9 0 年代中期，1 9 9 3 年国家自然科学基金首次对数据库中 知识发现领域的研究项目给予资助。目前，许多科研单位和高等院校竞 相开展相关领域的基础理论及应用研究，取得了令人鼓舞的成果。2 0 0 1 年5 月在重庆邮电学院举办了首届中国粗糙集和软计算学术研讨会 ( c r s s c 2 0 0 1 ) ，2 0 0 2 年1 0 月在苏州大学举办了第二届中国粗糙集 和软计算学术研讨会，2 0 0 3 年5 月在重庆邮电学院同时举办第三届中国 粗糙集和软计算学术研讨会和第九届粗糙集、模糊集、数据挖掘与粒度 计算国际学术会议( r s f d g 坨2 0 0 3 ) ，这些会议的举办表明我国粗糙 集理论和数据挖掘研究的队伍正在不断壮大，已经得到国际同行的重视 和认可。粗糙集理论逐渐应用于数据挖掘( d m ) 领域中，并在对大型 数据库中不完整数据进行分析和学习方面取得了显著的成果，使得粗糙 集理论及数据挖掘的研究成为热点领域。 1 3 数据挖掘 近些年来，随着电子商务和电子政务的迅速普及产生了大量的数 据，同时日益增长的科学计算扣大规模的工业生产过程也提供了大规模 的数据源。而日益成熟的数据库系统和数据库管理系统都为这些海量数 据的存储和管理提供了技术保证。同时，计算机技术的另一个技术领域 人工智能自1 9 5 6 年诞生之后取得了重大的进展，经历了博奕时期、自 然语言理解、知识工程等阶段，目前的研究热点是机器学习。用数据库 管理技术来存储数据，用机器学习的方法来分析数据，挖掘大量数据背 后的知识，这两者的结合促成了数据库中的知识发现的产生。本章介绍 数据挖掘的基本概念和主要过程，作为以后工作的基础。 1 3 1 数据挖掘的定义及其特点 数据挖掘( d a t am i i l i n g 简称d m ) 是指从大量的原始数据中发现 隐式的、未知的、有用的知识的非平凡过程【1 2 1 。简单的说，就是从数 据到知识的过程。数据挖掘的对象一数据，既可以是集中在主机上的数 据库，也可以是分布存放在互联网上的各种数据。这些数据可能有千兆 字节或更多，故数据挖掘一般需要一些领域知识。 由于数据挖掘所使用的数据直接来自数据库，数据的组织形式、规 模都具有依赖数据库的特点，特别地，数据挖掘处理的数据量非常巨大， 数据的完整性、一致性都难以保证。所以，数据挖掘算法的效率、有效 性和可扩充性都显得至关重要。 与传统的数据库查询系统比较，数据挖掘技术存在显著的不同u “。 首先，传统的数据库查询一般都具有严格的查询表达式，可以用s o l 语句描述。而数据挖掘则常常表现出即时、随机的特点，查询要求不确 定，整个挖掘过程无法用s q l 语言就能完整表达。其次，传统的数据 库查询一般生成严格的结果集，但数据挖掘过程往往基于统计规律，产 生的规则并不要求对所有的数据项总是成立，而是达到事先约定的闽值 就可以了。最后，通常情况下，数据库查询只对数据库的原始字段进行， 而数据挖掘可能在数据库的不同层次上发掘知识规则。 在数据挖掘系统中被用来抽取知识的数据集称为训练集【l 。通过训 练这个数据库中的数据，系统试图创建一般规则、模式的描述以及数据 库中的关系，获得的知识不仅对所考虑的数据库是有效的，而且还要适 合其他类型的数据。 另一个数据集用来测试已获得的知识，它即为测试集f l 引。如果在训 练集中发现的模式对其他数据也是有效的，此模式是清晰的；如果所获 得知识是一般知识，将对测试集的大部分数据是合适的。 一般情况下，数据库被分为两部分，一部分是训练集，一部分是测 试集。数据库中7 0 用作训练集，且被数据挖掘系统训练。原始数据库 的剩余部分则作测试集，测试从训练集中获取的知识是否合适。 数据挖掘的基础是来自机器学习和统计领域的技术。通过使用数据 库( 训练集) ，进行一个学习过程且获得数据库的模式。由此可以考虑 学习的两种不同的方法：推理和归纳。推理学习结合数据库中已有的信 息去提出实际已存在于数据库中的新的信息。一个推理系统通过使用之 前定义了的规则集推理数据，这些规则制约着被给出推理系统的信息是 怎样被使用得出结论和推断信息。归纳学习【i6 j 是发现存在于不同数据中 的隐藏模式，该模式将导致更多的有意义的一般知识。归纳学习是数据 挖掘的一个重要手段1 1 ”。就数据挖掘来讲，归纳学习是最适合的，也是 4 最好用的。这是由于用这种方法产生的知识不仅对所用的数据库对象适 用，也对类似数据适用，而且对不可见对象亦可行。 1 3 2 数据挖掘的功能 数据挖掘的功能用于指定数据挖掘任务中要找的模式类型。数据挖 掘的任务一般可分为两类一一描述和预测i l 。 数据挖掘得到的知识可以分为六大类： 特征( c h 盯a c t c r i s t i c ) ：对数据集概括总体的特征，即对共性的描 述。例如，盒装鲜牛奶的保质期一般为十天。 关联规则( a s s o c i a t i o n ) ：相关数据在不同属性之间或同一属性的 不同值之间的关联关系。例如，规则b u y ( x ，m i l k ) b u y ( x ，b r e a d ) 。 聚类( c 1 u s t e r i n 2 ) ：按一定距离或相似性测试度把数据分成一系列 相互区分的组。例如，帮助市场分析人员从客户数据库中发现不同的客 户群，并且用购买模式来刻画不同客户群的特征。 分类( c l a s s i f i c 砒i o n ) ：利用已知训练数据集的预定义类建立模型， 用模型对数据库中的数据进行分类。例如，按每公里的油耗把汽车分类。 趋势分析( t r e n da n dd e r i v a t i o na n a l v s i s ) ：构造和使用模型以评估 给定样本可能具有的属性值或值区间。例如，股票走势分析。 直接模式分析( p a t t e m d i r e c t e da n a l y s i s ) ：在数据中发现用户指定 的模式，并标识其特征。 数据挖掘的功能以及它们可以发现的模式类型介绍如下： 概念类描述。 特征化和区分：数据可以与类或概念相关联。 关联分析：发现关联规则i l 。 分类和预测：通过分类找出描述并区分数据或概念的模型，以便能 够使用模型预测类标未知的对象类。 聚类分析。 孤点分析。 1 3 3 数据挖掘的方法 数据挖掘中采用的方法综合了数据库、人工智能、统计学、模式识 别、机器学习、数据分析等领域的研究成果。现有的数据挖掘方法主要 有以下几种： 一、决策树方法 利用信息论中的互信息( 信息增益) 寻找出数据集中具有最大信息 的字段，建立决策树中的每一个结点，再根据字段的不同取值建立树的 分支的过程，即建立决策树。国际上最有影响的决策树方法是q u i n l a n 研究的i d 3 方法。 二、神经网络方法 它模拟人脑神经元结构，以m p 模型和h e b b 学习规则为基础， 建立了三大类神经网络模型。 1 ) 前馈式网络，以反向传播模型、函数型网络为代表，用于预测、 模式识别等方面。 2 ) 反馈式网络，以h o p f i e l d 离散模型和连续模型为代表，分别用于 联想记忆和优化计算。 3 ) 自组织网络，以a p t 模型，k o h 0 1 0 n 模型为代表，用于聚类。 三、模糊论方法 利用模糊集合理论对实际问题进行模糊评判、模糊决篡，模糊模式 识别和模糊聚类分析。模糊性是客观存在的，系统的复杂性越高，模糊 性越强，这是z a d e h 总结出的互克性原理。 四、遗传算法 这是模拟生物进化过程的算法，由三个基本算子组成： 1 ) 选择，是指从一个旧种群( 父代) 中选出生命力强的个体，产生 新种群( 后代) 的过程。 2 ) 杂交，是选择两个不同的个体的部分进行交换，形成新的个体。 3 ) 变异，对某些个体的某些基因进行变异。 遗传算法已在优化计算和分类机器学习等方面发挥了显著的作用。 五、粗糙集方法 粗糙集理论是八十年代初z p a w l a k 针对gf i r e g e 的边界域思想提 出的，基于给定训练数据内部的等价类的建立，用一对上下近似集合来 逼近数据库中的不精确概念。用于分类，可以发现不准确数据或噪声数 据内在的结构联系；用于特征归约，可以识别和删除无助于给定训练数 据分类的属性；用于相关分析，可以根据分类任务评估每个属性的贡献 或意义。其主要思想是在保持分类能力不变的前提下，通过知识约简， 导出问题的决策或分类规则。 1 3 4 数据挖掘的步骤 数据挖掘的实施大体可分为以下三步： 一、数据准备( d a t a p r e p a r a t i o n ) ，本阶段分为两步： 1 ) 数据集成：从操作型环境中提取数据并加以集成，解决语义的二 义性问题，消除脏数据。 2 ) 数据选择和预分析：进一步缩小数据范围，提高数据挖掘的质量。 二、数据挖掘( d a t a m i n j n g ) 这个阶段实际的挖掘工作，包括： 1 ) 先决定如何产生假设，是让数据挖掘系统为用户产生假设，还是 对于数据库中可能包含的知识提出假设。前一种称为发现型的数 据挖掘，后一种称为验证型的数据挖掘； 2 ) 选择合适的工具： 3 ) 利用前面提到的数据挖掘方法挖掘数据库中的知识； 4 ) 证实发现的知识。 三、规则表述( p r e s e n t a t i o n ) 数据挖掘将获得的信惑以方便用户理解和观察的方式反映给用户， 这时可利用可视化工具。这些基于不同数据集合的分析结果除了通过可 视化工具提供给用户外，还可以存储在知识库中，供日后进一步分析和 比较。 1 3 5 数据挖掘系统 典型的数据挖掘系统如图1 1 所示，其中，数据挖掘模块包括针对 各种应用而开发的挖掘子模块，如关联规则挖掘模块、聚类分析模块、 特征规则模块等。 图1 1 数据挖掘系统图 1 4 粗糙集理论的产生和发展 1 4 1 粗糙集理论研究对象 粗糙集的研究对象是由一个多值属性( 特征、症状、特性等) 集合 描述的一个对象( 观察、病历等) 集合，对于每个对象及其属性都有一 个值作为其描述符号，对象、属性和描述符是表达决策问题的3 个基本 要素。这种表达形式也可以看成一个二维表格，表格的行与对象相对应， 列对应于对象的属性；各行包含了表示相应对象信息的描述符，还有关 于各个对象的类别成员的信息。通常，关于对象的可得到的信息不一定 足以划分其成员类别。换句话说，这种不精确性导致了对象的不可分辨 性。给定对象间的一个等价关系，即导致由等价关系构成的近似空间的 不分明关系，粗糙集就用不分明对象类形成的上近似和下近似来描述。 这些近似分别对应了确定属于给定类的最大的对象集合和可能属于给 定类的最小的对象集合。下近似和上近似的差是一个边界集合，它包含 了所有不能确切判定是否属于给定类的对象。这种处理可以定义近似的 精度和质量。粗糙集方法可以解决重要的分类问题，所有冗余对象和属 性的约简包含属性的最小子集，能够很好地近似分类，得到可以接受质 量的分类。而且，它还可以用决策规则集合的形式表示最重要属性和特 定分类之间的所有重要关系。 1 4 2 粗糙集理论的特点 1 ) 粗糙集不需要先验知识模糊集和概率统计方法是处理不确定信息 的常用方法，但这些方法需要一些数据的附加信息或先验信息，如模糊 隶属函数和概率分布等，这些信息有并不容易得到。粗糙集分析方法仅 利用数据本身提供的信息，无须任何先验知识。 2 ) 粗糙集是一个强大的数据分析工具它能表达和处理不完备信息；能 在保留关键信息的前提下对数据进行化简并求得知识的最小表达式；能 识别并评估数据之间的依赖关系，揭示出概念简单的模式；能从经验数 据中获取易于证实的规则知识，特别适于智能控制。 3 ) 粗糙集与模糊集分别刻画了不完备信息的两个方面粗糙集以不可 分辨关系为基础，侧重分类，模糊集基于元素对集合隶属程度的不同， 强调集合本身的含混。从粗糙集的观点看，粗糙集合不能清晰定义的原 因是缺乏足够的论域知识，但可以用一对清晰集合逼近。虽然粗糙集和 模糊集特点不同，但它们之间有着密切的关系，有很强的互补性；粗糙 集和证据理论也有一些相互交叠之处，在实际应用中可以相互补充。 1 4 3 粗糙集理论应用的现状 粗糙集理论是一种处理含糊和不精确性问题的新型数学工具，其 基本思想是在保持分类能力不变的前提下，通过知识约简，导出概念 的分类规则。它自问世以来，无论是在理论或应用上都是一种新的、 最重要的并且是迅速发展的一门既有理论又有应用的研究领域。 1 ) 股票数据分析。文【2 0 1 应用r s 方法分析了十年间股票的历史数据， 研究了股票价格与经济指数之问的依赖关系，获得的预测规则得到了 华尔街证券交易专家的认可。 2 ) 模式识别。文 2 1 应用粗糙集方法研究了手写字符识别问题，提取出 特征属性。 3 ) 地震预报。文 2 2 】研究了地震前的地质牵口气象数据与里氏地震级别 的依赖关系。 4 ) 冲突分析。丈【2 3 】应用粗糙集方法建立了反映以色列、巴勒斯坦、 约旦、叙利亚和沙特阿拉伯等六国关于中东和平问题各自立场的谈判 模型。 5 ) 从数据库中知识发现( k n o w l e d g ed i s c o v e r vi nd a 协a s e ) 耳。j ，k d d 又称数据挖掘( d a t a m i n i n g ) ，是当前人工智能和数据库技术交叉学科 的研究热点之一。粗糙集方法现已成为k d d 的一种重要方法，其导 出的知识精炼且更便于存储和使用。 6 ) 粗糙控制。粗糙集根据观测数据获得控制策略的方法被称为从范例 中学习( 1 e a m i n g 舶me x a m p l e s ) ，属于智能控制范畴。基本步骤是： 把控制过程中的一些有代表性的状态以及操作人员在这些状态下所 采取的控制策略都记录下来，形成决策袁，然后对其分析化简，总结 出控制规则，形式为：i f c o n d i t i o n = n 满足t h e n 采取d e c i s i o n ：m 。 粗糙集方法是一类符号化分析方法，需要将连续的控制变量离散化， 为此z p a w l a l ( 提出了粗糙函数的概念，为粗糙控制打下了理论基础。 文f 2 6 ，2 7 】应用粗糙控制研究了“小车一倒立摆系统”这一经典控制问 题，取得了较好的结果。在过程控制领域，文【2 8 】应用粗糙集方法成 功地提取出了水泥窑炉的控制规则。粗糙控制的优点是简单迅速、实 现容易、不需要象f u z z y 控制那样进行模糊化和去模糊化。因此在特 别要求控制器结构与算法简单的场合，采取粗糙控制较为合适。另外， 由于控制算法完全来自观测数据本身，其决策和推理过程可以很容易 被检验和证实。一种新的有吸引力的控制策略“模糊一粗糙控制 ( 矗j z z y - r o u 曲c o n 廿0 1 ) ”正悄然兴起，其主要思路是利用粗糙集获取 模糊控制规则。 7 ) 医疗诊断。粗糙集方法根据以往的病例归纳出诊断规则，用来指 导新的病例。现有的人工预测早产的准确率只有1 7 v 3 8 ，应用粗糙 集理论则可提高到6 8 一9 0 。 8 ) 专家系统( e s ) 。粗糙集抽取规则的特点，为构造e s 知识库提供了 一条崭新的途径。 9 ) 人工神经网络( a n n ) 。训练时间过于漫长的固有缺点是制约a n n 实用化的因素之一。文【3 0 】应用粗糙集化简神经网络训练样本数据集， 在保留重要信息的前提下消去了多余的数据，使训练速度提高了4 7 2 倍，获得了较好的效果。 1 0 ) 决策分析【3 ”。r s 的决策规则是在分析以往经验数据的基础上得到 的。r s 允许决策对象中存在一些不太明确、不太完整的属性，弥补了 常规决策方法的不足。希腊工业发展银行e t e v a 应用r s 理论协助制 定信贷政策，是r s 多准则决蓑方法的一个成功范例。 这种理论在许多重要的实际生活中都有应用，利用粗糙集理论处 理的主要问题包括数据库中的数据约简、数据相关性的发现、数据意 义的评估、由数据产生决策控制算法、数据的近似分类、数据中的相 似性或差异性的发现、数据中范式的发现以及因果关系的发现。特别 地，粗糙集方法在医学、药学、银行、商业、金融、市场研究、工程 设计、气象学、振动分析、开关函数、冲突分析、图像处理、声音识 别、并发系统分析、决策分析、字符识别及其他领域都有重要的应用。 1 5 本文的主要研究工作与内容安排 本文首先对数据挖掘做了概述，介绍了数据挖掘的主要概念和挖掘 过程；然后对粗糙集理论做了简要介绍；并研究了粗糙集理论的核心问 题之一：属性约简，比较了几种主要的属性约简算法；最后研究大型数 据库的增量式地更新规则，总结了增量式规则提取方法的一般设计原 则，给出了扩充特征矩阵的定义，在此基础上提出了基于扩充特征矩阵 的增量式规则提取方法。本文的主要工作包括： 1 1 介绍了经典粗糙集的基本理论。经典粗糙集是建立在等价关系基础 之上的，用一对上下近似集合来表示一个不精确的概念，其等价关系条 件较强。 2 1 属性约简问题是粗糙集理论的核心问题之一，已被证明是一个 n 卜h a r d 问题i j ”j 。讨论了知识约简与知识依赖关系，知识表达系统 和决策表的关系，探讨和比较了多种属性约筒方法。 3 ) 增量式算法是知识发现领域的一个热点问题。一般地，对粗糙集方 法来说，就是指当新对象加入决策表时，以增量式的方式接受新对象。 本文的内容安排如下： 本章给出了数据挖掘和粗糙集理论的研究目的、发展状况和前景以 及数据挖掘的主要过程和步骤；在接下来的第二章，介绍了粗糙集的基 本理论和相关概念；第三章研究了粗糙集的核心问题之一：属性约简及 几种主要的属性约简算法；第四章总结了增量式规则提取方法的一般设 计原则，扩展了特征矩阵的定义，并在此基础上提出了一种增量式规则 提取算法，该规则能够以增量的方式从样本数据中提取确定性和可能性 规则：最后总结全文。 第二章粗糙集基本理论 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其主 要思想就是在保持分类能力不变的前提下，通过知识约简导出问题的决 震或分类规则。下面将阐述粗糙集理论的基础及其思想，作为后面章节 的理论准备。 2 1 信息系统 一个信息系统包含一个对象集，每个对象有一些属性，并且这些属 性有对应的属性值。对于所有对象属性是相同的，但属性值可能不同， 因而一个信息系统多少与一个关系数据库类似。 一个信息系统( i s ) 可用一个四元素表示：i s = ( u ，a ，v 。，f a ) ， 其中u 是一个非空的有限对象集u = x l ，x 2 ，x 。 一论域，a 是一个 非空的有限属性集a = a 1 ，a 2 ，如。v 。为属性a 的值域，例如属 性a 是表示对象大中小这一属性，那么可取值为f 大，中，小) ；对每个 属性a a 定义信息函数f a ：u v 。信息系统可用二维信息表加以描述， 表中的每一行表示u 中的一个对象，每一列表示a 中的一个属性，表 中的每个元素表示该对象的多种属性的取值，即信息函数f a 的值。一个 信息系统可简化定义为i s = ( u a l 。 一个决策系统是一个信息系统，i s = ( u ，a ) ，其中a 中的属性被进一 步划分为不相交的属性集c 和d 的并集，其中c 为条件属性集，d 为 决策属性集。( a = c u d 且cn d = 币) 表2 1 给出一个决策系统的例子，是一个决策表。表中a ，b ，c ，d 属性 分别表示s t u d i e s ，e d u c a t i o n ，w o r k s ，m c o m e 性。 表2 1 收入决策表 这个信息系统中有5 个人( 对象) ，每个对象均有其生活状况的属 假设想从中发现规则，且这一规则能根据一个人的描述属性预测他 或她的收入多少。收入属性即d 被当作决策属性( 或依赖属性) ，其余的 属性：学习a 、教育b 、工作c 被作为条件属性。这种只有一个决策属性 的情形是最普遍的。 2 2 粗集的基本概念 令x cu ，且r 为一等价关系，当x 能用r 属性集确切地描述时， 它可用某些r 基本集合的并来表示，称x 是r 可定义的，否则x 为r 不可定义的。r 可定义集是论域的子集，它可在知识库k = ( u ，r ) 中被 精确地定义；而r 不可定义集不能在这个知识库中被定义。r 不可定义 集也可称为r 非精确集或r 粗集。 当存在一个等价关系r i n d ( k ) 且x 为r 精确集，集合x u 称 为k 中的精确集；当对于任何r i n d ( k ) 且x 为r 粗集，则x 称为k 中的粗集m j 。 下面首先定义不可分辨关系。如果在两对象中存在这样的关系，则 意味着被考虑属性的属性值对于两者来说是相同的，因此，这些属性不 能被区分或识别。 不可分辨关系：对于信息系统i s = ( u ，a ) 的每个属 生子集b a ， 可定义等价关系i n d ( b ) ，称为不可分辨关系【3 6 ，”】，定义为： i n d ( b ) = ( x ，y ) u + u ：x ) = a ( y ) ，对每个a b ) ( 2 1 ) 对于前面给出的决策系统的例子，计算u n d ( c ) 有如下结果 u d ( a ，b ，c ) 2 “l ，2 ) ，( 3 ) ， 4 ，5 从中可以看出对象被统一划分，并且组成一个划分的对象在使用选 定属性进行分辨时是不可区分的。 一个等价关系就是一个划分。表2 2 是使用表格形式表示的划分： 类e l 来自对象1 和2 ，类e 2 来自对象3 ，类e 3 来自对象4 和5 ，注意 e 3 的两个对象有不同的决策值。 表2 2 收入决策表的等价划分结果 abc e in o9 0 0 dy e s e 2y e sg o o dy e s 里i呈旦旦竺旦!呈旦 一、上、下近似集 3 8 4 0 1 下面给出的定义是粗集的基本概念，它说明了这一方法的中心点 一模糊类。 上、下近似集：信息系统i s = ( u ，a ) ，下近似集b ( x 1 和上近似集 b ( ) ( ) ，其中对象x u ，属性集b a ( 定义u 上的一个等价关系) ，根 据等价关系中的类可被定义为： b 一( 工) = u x u 月v d ( 日) i ，= ；量。r ( 2 2 ) b 一( x ) = u 矸 ，毋v d ( b ) i k n x 庐) ( 2 3 ) 分别称为x 的b 下近似集和b 上近似集。集合 6 ( x ) = 日一( x ) 一罡( z ) 称为x 的b 边界。p 0 ( x ) = 厦( j ) 称为x 的b 正域；把聆锯。( z ) = u b 一( j ) 称为x 的b 负域，b n b ( ) 。称为x 的 b 边界域。 下近似b ( x ) 是根据知识b ，u 中所有一定能归入x 的元素的集 合，即所有包含于x 的y 的并，上近似b 。仪) 是根据知识b ，u 中一定 能和可能能归入x 的元素的集合，即所有与x 的交不为零的y i 的并。 b n b ( x ) 是根据知识b ，u 中既不能肯定归入x ，也不能肯定归入x 的元 素的集合。 二、分辨矩阵 在这种矩阵中，( 条件) 属性被插入，这些属性能被用来区分相关 列行之间的类。 分辨矩阵：信息系统i s = ( u ，a ) ，对于属性集b 爿，分辨矩阵定义如 下： 彳( b ) = ( 州。) 。，1 j ，”= i u 肋( b ) l ，那儿 棚。= 口b i 口( 丑，) 日( 工，) ) ，f ，= 1 ，2 ，n ( 2 4 ) 分辨矩阵中的元素m ，i 是b 中能区分对象类x 。，x ，u i n d ( b ) 的属性 集 4 ”。 从上一个例子中，能够观察到e l ，e 2 之间仅有一个属性的属性值 不同，即为a ，这个属性因而被放在矩阵中的相应的位置。如表2 - 3 所 示。可见它是一个对称矩阵，且对角线为矿。 表2 3 收入决策表的分辨矩阵 如果一些分类具有相同的决策值，则不需要在这些类之间区分，这 样的话，对于决策值相同的类就不需加入属性。如果任何类都有同样的 决策值的话，那么就能得到更简单的规则。之前的例子不是这样，它的 所有的类均有不同决策值。因而，对于一个决策系统i s = ( u ，c u d ) ，分 辨矩阵可定义为h ： ，( c ，d ) = ( 彳d ( f ，) ) 。，1 f ，_ ，盯= iu 月v d ( c ) ， 4 u 胁r d ( c ) = x l ，2 ，x 。) m 舻吲篇；，= d ( 巍 三、分辨函数【4 3 j 分辨函数：属性集合b 量爿，分辨函数苁b ) 是： 厂( b ) = 。 瓢 vm n ( x 一，x ，) ( 2 5 ) ( 2 6 ) 其中n = l u i n d ( b ) i ，u i n d ( b ) = x l ，x 2 ，x 。 ，v m d ( z ，x ，) 是对应分辨 矩阵元素m d ( x 。，x i ) 的布尔型变量“m 。( ，x ，) ”的并集i “。 一个对象类x 的相对分辨函数艇，b ) 是： ，( x ，b ) = 0 、vm d ( x ，x ) ( 2 7 ) j 1 1 ，l j 这表明分辨函数戊b ) 用来计算最小属性集，这些属性要求能从其它所有 类中分辨出任何等价类。类似地，相对分辨函数，( x ，b ) 计算最小属性集， 这些属性要求能从其它类中分辨出给定等价类x 。 对于上面的例子可计算下面的相对分辨函数： ，( 巨，c ) = 口 ( 6 v c ) ( 易，c t ) = d ( d v 6 v c ) 厂( e ，c ) = ( 6 vc ) v 6 vc ) 四、属性的约简和核 在信息系统中，数据仅能在一定程度上区分类。然而，为了能够达 到这一目的，不是所有的属性都可能被需要。为此，介绍下面的一些知 识。 数据约简即对某个不可分辨关系，如果某个条件属性被去除后仍有 相同的等价关系的话，那么这个条件属性便是可省的【4 5 j 。 首先，看一下独立性，对于属性日b 彳，如果i n d ( b ) = i n d ( b - a ) 则属性a 是冗余的；否则称a 是独立的或必要的。当对任意a b ，如 果a 是独立的，则b 是独立的；当a 是独立的，且b 爿，则b 也是 独立的。 核和约简是粗集理论的两个基本概念。 约简：对于属性集b b ，若对于所有属性口曰一b 。是不必的， 且上 ，d ( 占) = n ，d ( b ) ，即b 。为最小子集，则b + 称为b 的约简，用r e d ( b ) 表示。 一个属性集合b 可能有多种约简。分辨函数苁b ) 的基本集决定了b 的约简。 核：b 的所有属性集中都包含的不可省略关系的集合，即所有约简 关系簇r e d ( b ) 的交称为b 的核，记作c 0 r e ( b ) 。它是表达知识必不可 少的重要属性集。属性集合的核和约简的关系表达为： c o r e ( b ) = nr e d ( b ) ( 2 8 ) 其中r e d ( b 1 是b 的所有约简关系簇【4 6 l 。核主要有两个作用：( 1 ) 它可作为所有约简的计算基础，因为核包含在所有约简之中，并且计算 可以直接进行；( 2 ) 它是信息系统中必需的属性，即在知识约简时，它 是不能消去的知识特性部分的集合。 下面介绍另一个相关的概念一一相对约简1 4 ”。 首先看一个分类相对另一个分类的正域，p 和s 为u 中的等价关系， s 的p 正域记为p o s p ( s ) ：p o s p ( s ) = u p ( x )x u s 对于u 伊的分类， u s 的正域是论域中所有通过分类u ，p 表达的知识能够确定地划入u s 类的对象的集合。当j p d s m ( 肼d ( s ) ) = p 0 s m ( h 川( ，d ( s ) ) 时，称a p 为p 中s 可省略的；否则a 为p 中s 不可省略的。当p 中每个a 都 是s 不可省略的，则称p 是对于s 独立的。 相对约简：如果q 是p 的s 独立的子集，且p o s o ( s ) = p o s p ( s ) ，则 称子集qcp 为p 的s 约简，p 中所有s 不可省略的属性称为p 的s 核。 相对核和相对约简关系如下： c o r e s ( p ) = nr e d s ( p ) 其中r e d s ( p ) 是p 中所有的s 约简关系簇。 相对分辨函数，b ) 的基本集决定了b 的相对约简。r e d x ( b ) 是代 表对于类x ，b 的相对约简。 由此可见在信息系统中，相对约简包含足够的信息把一个类中的对 象同其他类区分开来。 对于上面的例子，为了发现相对约简，分辨函数被计算，下面将看到， 每个函数被最小化成如下形式： ，( e l ，c ) = d a ( 6 v c ) = ( 口 6 ) v ( 以 c ) 厂( 易，c ) = 日 0 v 6 v c ) = 口 厂( 毛，c ) = ( 6 v c ) 0 v 6 v c ) = 6 vc 这给出所需的相对约简。例如，r e d d ( c ) = “a ，b ) ， a ，c ) ，相对约简 是最小的，因为每个分辨函数是被最小( 相对) 的约简是一个约简，在 约简中属性不可能被去掉，而同时不失掉约简的性质。 五、知识依赖性的量度及粗集的粗糙度 1 、知识的依赖性量度【4 8 - 5 0 j 从知识的相对约简，知道从一给定的知识能导出另一知识时，则两 种知识间存在依赖性。令k = ( u ，r ) 为一个知识库，且p ，q r ，若 i n d ( p ) i n d ( q ) ，则称知识q 依赖于知识p 或者称知识q 可由知识p 完全推导出来，记为pjq 。而且等价于p o s p ( q ) = u 。 在很多时候，知识并非是完全可推导的。有一些知识( q ) 是可由知 识( p ) 部分导出的，部分可导性可用知识的部分依赖性表达。为此给出 知识的依赖性量度 七= o ( q ) = c 口r d ( p ( 姆p ( q ) ) c r d ( u ) ( 2 9 ) 其中c a r d ( ) 表示集合的基数，则称知识q 是p 的k 度可导的( o k 1 ) ，记作p j i q 。这里c a r d ( p 0 s p ( q ) ) 是表示根据p ，u 中所有一定能 归入o 的元素的集合。 2 、属性的重要性 在进行分类时，去掉某些属性会改变分类，则说明该属性强度大， 即重要性高；反之，说明属性的强度小，即重要性低。对于属 生集d 导出的分类子集b 。b 的重要性，用两者的依赖程度的差来度量，即 ( d ) 一厶、。( d ) ( 2 1 0 ) 这表示当从集合b 中去掉某些属性集b 后对对象进行分类时，分 类的正域将会受到怎样的影响。根据属性重要性来进行约简，将很轻 松地得到该知识表申的核的构成，但核不是该原始知识表的约简。如 果可省略的属性不唯一时，通常存在多种约简形式。 3 、粗集的粗糙度 r 为u 上的等价关系，x 是r 可定义的，当且仅当r 一( z ) = 尺一( x ) ； x 是r 不可定义的，当且仅当足一( x ) r 一( 1 ，因此，对于u 中的任意 元素x ，其关于r 的精确可定义度a r ( x ) 和粗糙度p r ( ) ( ) 定义如下： ( x ) = c 甜d ( 月一( z ) ) c d 坩( r 一( x ) ) p r ( x ) = l a 。( x ) 2 3 规则的产生 ( 2 1 1 ) ( 2 1 2 ) 在数据库中规则代表依赖性，它也代表抽取知识【5 l 】。当不在原始信 息系统中划分新的对象时，规则可以被利用。当约简被找到