（系统分析与集成专业论文）基于粗糙集的数据挖掘算法的研究与应用.pdf

中文摘要 摘要：数据挖掘是致力于数据分析和理解、揭示数据内部蕴藏知识的技术，是当 前人工智能研究中非常活跃的领域。粗糙集理论是一种有效地处理模糊性和不确 定性问题的数学工具，为数据挖掘的研究提供了新的思路和基础。 本文主要围绕基于粗糙集的数据挖掘，针对传统数据挖掘处理噪声数据不力的 问题，从理论和应用两个方面对挖掘方法进行了深入的研究。本文的主要工作包 括： ( 1 ) 在可变精度粗糙集理论下对经典粗糙集的概念进行了重新的诠释；分析 了粗糙集理论在数据挖掘应用中的理论根据和基本原理，并点出了研究的方向。 ( 2 ) 结合信息论，提出了基于信息熵的属性约简算法。该算法以属性的核作 为计算约简的出发点，以过滤分辨矩阵作为选择候选属性的依据，以条件属性和决 策属性的信息熵作为启发信息，来寻找决策信息系统的最小约简。实验证明，该 算法和经典的启发式算法相比，能够降低当噪声数据存在时漏失有效属性的风险， 加快属性约简的速度。 ( 3 ) 提出基于变精度粗糙集的决策树改进算法。该算法采用一边界域作为 选择分类属性的标准，因此解决了不能对噪声数据进行分类的问题。另外，该方 法还对规则置信度进行了重新定义，从而提高了决策树的可理解性。实验结果表 明，该方法更加实用、易于理解且能明显地提高分类的效率。 ( 4 ) 在研究、分析了车站建设施工数据和施工安全风险的基础上，提出了对 轨道建设施工安全风险进行预测的一系列数据挖掘方法。首先，对数据进行清洗、 转换和离散化，并给出数据的集成方法；然后，运用改进的属性约简算法，对3 1 个属性进行约简得到1 3 个条件属性。最后，在完成预处理的基础上，采用基于变 精度粗糙集的决策树改进算法对1 0 2 1 条施工安全数据进行了分类分析，建立起轨 道建设施工安全风险评估模型，并在此基础上初步开发了一个基于粗糙集的数据 挖掘系统。 本文实验结果表明，本文改进的基于粗糙集的算法对噪声数据的处理可行、有 效。 关键词：数据挖掘；粗糙集；属性约简；决策树；风险评估 分类号：t p 3 1 1 a b s t r a c t a b s t r a c t ：d a t am i n i n gi sat e c h n i q u et h a ta i m st oa n a l y z ea n du n d e r s t a n dl a r g e s o u r c ed a t aa n dr e v e a l sk n o w l e d g eh i d d e ni nt h ed a t aa n di sa na c t i v er e s e a r c hf i e l do f a ir e s e a r c h i n g a sa l le f f i c i e n tm a t h e m a t i ct o o lt od e a lw i t 】 1t h ev a g u e n e s sa n d u n c e r t a i n t y , r o u g hs e tt h e o r yp r o v i d e san e wa p p r o a c ho fd a t am i n i n g i nt h i st h e s i s ，d a t am i n i n gb a s e do nr o u g hs e ti ss t u d i e di nt h et h e o r ya n d a p p l i c a t i o nw i t l lr e s p e c tt ot h ep r o b l e mt h a tt h et r a d i t i o n a ld a t am i n i n gm e t h o dc a nn o t h a n d l en o i s yd a t ae f f e c t i v e l y m a i nt o p i c so ft h i sd i s s e r t a t i o na r ea sf o l l o w s ： ( 1 ) i nt h i sp a p e r , w er e - i n t e r p r e t e dt h eb a s i cc o n c e p to fc l a s s i c a lr o u g hs e tt h e o r y b a s e do nv p r s ，w ea l s oa n a l y s et h ef e a t u r e sa n dp r o c e s so ft h ea p p l i c a t i o no fr o u g hs e t t h e o r yi nd a t am i n i n ga n dp o i n t e do u tt h ed i r e c t i o no ft h er e s e a r c h ( 2 ) t of i n d i n go u tm i n i m a lr e d u c t ，a l la t t r i b u t er e d u c ta l g o r i t h r nb a s e do ne n t r o p yi s p r o p o s e di nt h i sd i s s e r t a t i o n t h i sa l g o r i t h me m p l o y sc o r eo fa t t r i b u t ea st h es t a r to f r e d u c t i o na n dt h et i l t e dm a t r i xa st h es e l e c t i o nc r i t e r i ao fc a n d i d a t ea t t r i b u t e sa n d e m p l o y se n t r o yo fa t t r i b u t i o na sh e u r i s t i ci n f o r m a t i o n e x p e r i m e n ts h o w st h a t t h i s a l g o r i t h m ，c o m p a r e dt oo t h e ra l g o r i t h m ，c 锄r e d u c et h er i s ko f o fu s e f u la t t r i b u t e sl o s s a n da c c e l e r a t et h ep a c eo fa t t r i b u t er e d u c t i o n ( 3 ) an e w m e t h o do fd e c i s i o nt r e eb a s e do nv p r si sp r o p o s e di nt h i st h e s i s i no r d e r t os e t t l et h ep r o b l e mt h a tt r a d i t i o n a lm e t h o d sc a nn o tc l a s s i f yn o i s yd a t a , t h ea l g o r i t h mc - h o o s e st h eb o u n d a r yr e g i o no f r o u g hs e t sa st h ec r i t e r i ao fs e l e c t i n gp a r t i t i o n a la t t r i b u t e e s i na d d i t i o n ，t h ec o n c e p t i o no f c o n f i d e n c eo f l e a f n o d e si sr e d e f i n e d ，w h i c hm a k e s t h em e t h o dm o r eu n d e r s t a n d a b l e e x p e r i m e n ts h o w st h a t ，d e c i s i o nt r e eb u i l ti nt h i s w a y i sm o r ee f f e c t i v ea n dc o m p r e h e n s i b l e ( 4 ) a f t e rs t u d ya n da n a l y s e so nc o n s t r u c t i o nd a t ao fs t a t i o n sa n ds e c u r i t yr i s k so f s t a t i o n sc o n s t r u c t i o n , t h i sp a p e re m p l o y st e c h n i q u e so fd a t am i n i n gt op r e d i c tt h e s e c u r i t yr i s k s t h ef i r s ts t e pi s d a t ac l e a n i n g , i n t e g r a t i o na n dt r a n s f o r m a t i o na n d a p p r o a c h e so ns i m i l a r i t yc o m p u t i n go fc o n s t r u c t i o nd a t a t i t lei n t r o d u c e d s e c o n d ，13 a t t r i b u t i o na r eo b t a i n e df r o m31u s i n gt h ei m p r o v e da l g o r i t h mo fa t t r i b u t i o nr e d u e t a t l a s t , w ee m p l o yt h ei m p r o v e dm e t h o do fd e c i s i o nt r e eb a s e do nv p r st h e o r yt oc l a s s i f y 10 21d a t ao fe o n s t r u c t i o nd a t aa n de s t a b l i s ham o d e lo fr i s ka s s e s s m e n t t h e nad a t a - m i n i n gs o f t w a r eb a s e do nr o u g hs e ti sd e v e l o p e d i na d d i t i o n ，e x p e r i m e n ts h o w e dt h a ti m p r o v e da l g o r i t h m so ft h i sp a p e ra r ef e a s i b l e a n de f f e c t i v ei nd e a l i n gw i t hn o i s yd a t a k e y w o r d s ：d a t a m i n i n g ；r o u g hs e t ；a t t r i b u t er e d u c t ；d e c i s i o nt r e e ； r i s ka s s e s s m e n t c l a s s n o ：t p 31 1 v 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：渺、孛酲 签字日期：砂书年f 月乃日 导师签名： 签字日期：洲年歹月2 加 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：澎雪盔签字日期睁r 月枷 6 7 致谢 本论文是在导师徐维祥教授的悉心指导和耐心鼓励下完成的。在此谨向恩师 致以最诚挚的感谢。两年来，徐老师不仅在实际的科研中给予我严格、具体而又 悉心的教导，而且在日常学习、生活中给我无微不至的关心和照顾。徐老师严谨 的治学态度、孜孜不倦的敬业精神和为人师表的高尚风范将使我受益终身。 感谢李华华师姐以及孙凌燕、张生润同学。在撰写论文期间，她们为我论文 的完成提供了无私帮助。 感谢我的家人对我求学生涯的支持和生活中的无限关怀，他们是我坚强的后 盾。 感谢各位专家学者在论文评审过程中所提出的批评和指正。 对所有帮助和关心过我的人，再次致以最诚挚的谢意。 1 1论文写作目的和意义 1 引言 数据挖掘( d a t am i n i n gd m ) 致力于从海量数据中探寻有益的知识用于决策辅 助，目前已成为国际上信息决策领域最前沿研究方向之一i l 】。数据挖掘技术在很多 领域都得到了较为广泛的应用，如金融、医疗保险、市场业、零售业、制造业、 甚至司法系统等。它既可以检验各行业内长期形成的知识模型，也能够发现隐藏 的新规律。 粗糙集理论是研究不确定性和不精确性知识的数学工具，可以在缺少关于数 据先验知识的情况下，仅仅以对观测数据的分类能力为基础，解决模糊或不确定 性数据的分析和处型2 1 。粗糙集理论以其在处理大数据量，消除冗余信息等方面的 优良性能，近年来在分类数据挖掘领域得到了广泛的应用。在数据挖掘预处理阶 段，利用粗糙集算法可以在不改变不可分辨关系的前提下实现数据离散化；在中 期阶段，运用粗糙集属性约简理论在对属性重要性分析研究的基础上去掉冗余、 不相关属性，生成可用于下一步数据挖掘的数据集合；在后期建模阶段，在化简 得到的数据集上，利用粗糙集生成的算法产生有价值的确定规则或可能规则。基 于粗糙集的数据挖掘研究和应用是目前分类数据挖掘领域中最新的研究热点。 数据挖掘广泛应用于各行业，其处理数据往往具有以下特点：数据量大，冗： 余多且存在大量的不一致和错误数据。我们把这些不一致和错误的数据称之为噪 声数据。噪声数据的存在往往会严重影响数据挖掘的挖掘效果，导致错误的决策 支持。目前基于粗糙集的数据挖掘对噪声数据处理还没有有效的方法。粗糙集由 于其本身的一些特点，在处理噪声数据上有先天的优势。因此研究基于粗糙集的 数据挖掘如何对噪声数据进行处理具有很重要的意义。 属性约简是基于粗糙集的数据挖掘的一个重要环节。到目前为止，已经存在 的一些约简算法往往完全无视不一致数据存在。比如启发式约简算法大多针对下 近似不变的情况，只考虑了属性对j 下区域部分实例分类的影响。在不一致信息系 统中往往会导致上近似区域变大，从而丢失信息。因此寻求可以处理噪声数据的 约简算法是研究方向之一。 分类规则是基于粗糙集的数据挖掘的另一个重要环节。相较于传统的i d 3 算 法，现在许多学者提出的决策树改进算法都具有了更好的泛化能力，但在建树过 程中，对噪声数据却都没有做到有效地分类。而考虑到可变精度的粗糙集理论允 许划入正域的实例类别存在不一致性这一特点，如何将它应用到决策树算法中将 是另一个重要研究方向。 目前我国进入城市轨道交通建设高峰期，但城市轨道交通建设施工期间具有 很多潜在的安全风险，其中车站施工安全风险是其中的主要因素【3 】。这些风险一旦 产生将对城市的社会、环境、交通和经济产生巨大负面影响。这迫切需要我们对 车站建设施工存在的安全风险进行系统的研究和评估。施工风险产生的因素十分 复杂，其相关数据又具有不一致性，存在噪声，传统的分类模型很难对其进行深 入的挖掘。本文提出基于粗糙集的数据挖掘改进方法是处理噪声数据的有力工具， 因此如何将这些方法引入到城市轨道交通建设施工安全风险的评估中，挖掘出风 险产生的相关因素，预测车站施工可能存在的安全风险，具有重要的现实意义。 1 2 数据挖掘概述 数据挖掘是信息技术自然演化的结果。自2 0 世纪6 0 年代以来，数据管理已 经从处理原始的文件系统演化到处理复杂的、功能强大的数据库系统。而在过去 的3 0 年里，计算机硬件技术稳定而令人吃惊的进步以及功能强大的计算机、数据 收集设备和存储介质的大量需求极大地促进了数据库的发展和应用，并在各个行 业积累了十分丰富的数据。但是这些海量的数据绝大多数都没有提炼，“数据丰 富，知识贫乏 【4 】的现象普遍存在。j o h nn a i s b e t t 在大趋势一书中就曾这样感 叹：”w ea l ed r o w n i n gi ni n f o r m a t i o n ，b u ts t a r v i n gf o rk n o w l e d g e ”p j 。人们急需要有一 个强有力的工具来理解，并从数据中提取有用的知识用以帮助决策。“谁最先从外 部世界获得有用的信息并加以利用，谁就可能成为赢家【4 】。正是在这种背景下， 数据挖掘技术应运而生。而如何对信息进行快速有效的分析、加工、提取潜在有 用的信息，也就成为计算机以及信息技术领域的重要研究课题。 数据挖掘是从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的 复杂过程，又被称为数据库知识发现【5 】。它是数据库技术深层次的应用，把人们对 数据的处理，从低层次的联机查询操作，提高到决策支持、分析预测等高级应用 上，通过对数据进行微观、宏观的统计、分析、综合和推理，发现数据间的关联 性、未来趋势以及一般性的概括知识并指导现实。此外，数据挖掘是一门典型的 交叉学科，其理论和应用受统计学、集合论、逻辑学、信息论、认知论、机器学 习、模糊集理论、证据理论、神经网络、进化计算、模式识别和粗糙集理论等诸 多学科影响【6 j 。 1 2 1数据挖掘的基本流程 2 一般而言，广义的数据挖掘涉及到以下一些步骤，如下图1 1 所示： 图1 1 数据挖掘的基本过程 f i g u r e i lt h ep r o c e s so f d m 下面简述各个步骤的基本内容： 1 数据选择 分析应用领域，了解相关背景知识，根据需求从数据库中提取相关的数据， k d d 将主要从这些数据中进行知识挖掘。 2 数据预处理 数据预处理包括数据清洗、数据集成、数据转换和数据消减。 数据清洗是指消除数据中所存在的噪声以及纠正其不一致的错误，清除与挖 掘主题明显无关的数据，对丢失的数据进行填充。 数据集成是指将多个数据源中的数据组合到一起。可能涉及到的问题包括实 体识别和消除描述相同的概念但在不同数据库中取不同名字的属性。 数据转换是将数据转换或统一成适合挖掘的形式，如通过汇总或聚集操作。 数据消减的目的是在不影响或基本不影响挖掘结果的条件下缩小所挖掘数据 的规模。使用技术包括离散化、属性约简以及概念层次生成等方法。 以上所提及的各种数据预处理方式是相互关联的，每个处理阶段都可以返回 到前面的阶段进行再处理。 3 数据挖掘 数据挖掘是知识发现的一个基本步骤，其作用是选择合适算法来挖掘数据模 式或规律知识。 4 模式评估及表示 对发现的模型进行兴趣度评估，然后将知识表示为用户可以理解的形式。 1 2 2数据挖掘的基本功能 3 数据挖掘功能用于在指定的数据挖掘任务中找到用户需要的模式类型。然而 用户的需求是多样的，因此数据挖掘系统也应当能够挖掘多种类型的模式，以适 应不同的需求或应用。下面将数据挖掘基本功能以及它们可以挖掘的模式类型介 绍如下1 7 - 9 ： 1 概念类描述 描述性数据挖掘的最简单类型是概念描述，由特征化和比较两类组成。前者 对目标类的数据集进行汇总和描述，后者汇总并将目标类数据集与其他对比类的 数据集相区别。概念特征化又分为两种方法：基于数据立方体o l a p 的方法和面 向属性归纳的方法。概念比较可以用类似于概念特征化的方式，使用面向属性的 归纳或数据立方体方法进行，可以量化地比较从目标类和对比类概化的元组。面 向属性归纳方法包含以下技术：数据聚集、通过属性删除或属性概化数据、计数 和聚集值累计、属性概化控制和概化数据可视性。 2 关联分析 关联分析的目的是发现特征之间或数据之间的相互依赖关系。数据相关性关 系代表一类重要的可发现的知识。一个依赖关系存在于两个因素之间，当两个或 多个因素的取值之间重复出现且概率很高时，它就存在某种关联，就可以建立起 这些数据项的关联规则。一条形如彳专b 的关联规则可以解释为：满足么的数据 项也很可能会满足b 。关联可分为简单关联( 例如，购买面包的顾客中有9 0 的人 同时购买牛奶) 、时序关联( 例如，若a t & t 股票连续上涨两天且d e c 股票不下跌， 则第三天b i m 股票上涨的可能性为7 5 ) 和因果关联。常用技术有回归分析、机器 学习、信念网络等。 3 分类与预测 分类在数据挖掘中是非常重要的一项，目前在商业上应用最多。其目的是通 过学习产生一个分类函数或分类模型( 分类器) ，该分类器能按照事先定义的规则， 把数据库中的数据项映射到一个特定类别中，即对数据进行归类。一般用分类表 示对有限离散属性值的预测，而预测表示对连续数值的预测。分类的核心是分类 器的构造，目前常用方法有统计方法、机器学习方法、仿生学方法等。 4 聚类分析 聚类分析与分类预测方法明显不同之处在于，聚类分析所处理的数据均是无 事先确定的类别归属，属于无教师监督学习。聚类分析的目的是根据一定的规则， 把类别未知的样本按照相似性归成若干类别，使得属于同一类别的样本之间的距 离尽可能的小，不同类中的样本距离尽可能的大。数据聚类正在蓬勃发展，有贡 献的研究领域包括统计学、机器学习、空间数据库技术和生物学。 目前，数据挖掘已广泛应用到零售市场营销、金融、信用保险、过程控制质 4 量监督、化q - 医药、工程与科学数据分析、司法、军事等各个信息系统。然而每 个具体领域都有各自不同的特点，因此在实践应用中需要科学选择数据挖掘方法。 1 2 3分类数据挖掘 分类( c l a s s i f i c a t i o n ) 是数据挖掘中一类重要方法，应用广泛。分类是一个从现 有的带有类别标签的数据集中寻找同一类别数据的共同特性，并以此将它们进行 区分的过程。其核心步骤是构造一个分类函数或分类器，这个分类器将能够把数 据源中的数据映射到给定类别中的某一项中。目前，分类数据挖掘存在多种分类 算法，但基本上可以分为两大类：符号主义方法和连接主义方法【l o 】。符号主义方 法包括决策树、粗糙集理论等技术，其得到的分类知识以分类规则的形式出现； 连接主义方法则以神经网络为代表，其知识蕴含在结构中，相对来说不易为人所 理解。 1 分类的主要步骤 分类的主要步骤如图1 2 所示： 图1 - 2 分类的基本过程 f i g u r e l - 2t h ep r o c e s so fc l a s s i f i c a t i o n ( 1 ) 划分数据集 将现有的已知类别的数据划分为训练数据和测试数据两部分。目前主要有两 种划分方法【1 1 ：保持( h o l d o u t ) 方法和k 倍交叉验证( k - f o l dc r o s sv a l i d a t i o n ) 方法。保 持方法将已知数据随机划为训练数据和测试数据两部分，一般是三分之二作为训 练数据，另外三分一作为测试数据。它使用训练数据导出分类模型，把在测试数 据上的分类精度作为最终的分类精度。k 倍交叉验证则将已知数据随机划分为k 个 大致相等的数据子集墨，s ：，a a o9 鼠，训练和测试重复进行k 次。在第f 次过程 中，s 作为测试数据，其余的子集则作为训练数据。最终分类器的分类精度取k 5 次测试分类精度的平均值。这种方法适用于原始数据量较小的情况，这时不适合 直接应用保持方法。 ( 2 ) 学习 用分类算法分析训练数据，得到一个分类模型，它可以以分类规则、决策树 或数学公式等形式给出。 ( 3 ) 评估分类模型 使用得到的分类模型对测试数据进行检测，如果符合测试要求( 如分类精 度) ，则进行步骤( 4 ) ；否则，返回到步骤( 2 ) 。 在该步骤中，需要对分类模型的有效性进行评价，目前比较常见的有三种比 较尺度：预测准确度；计算复杂度；模型描述的简洁度。其中预测准确度 用的最多。另外，由于数据挖掘中所操作对象往往是巨量的数据库，因此空间或 者时间的复杂度也都将是非常重要的指标。 ( 4 ) 分类 应用得到的分类模型对未知类别的数据进行分类，得到分类规则。 2 常用的分类算法【m 1 6 1 ( 1 ) 基于决策树的分类算法 决策树算法是一种常用的分类数据挖掘算法，也是在实践中应用最广泛的分 类算法。经典决策树算法有著名的决策树归纳算法i d 3 版本f 1 2 】以及在此基础上出 现的c 4 5 、s l i q 等。 i d 3 算法选择具有最高信息增益的属性作为当前结点的测试属性，它所产生的 决策树最为简单，工作量最小，产生的分类规则也易于理解。但也存在着许多不 足，比如不能够处理连续值属性、计算信息增益时偏向于选择取值较多的属性等。 i d 3 的改进算法有c 4 5 ，c 4 5 用信息增益率来选择属性，克服了用信息增益选择 属性时偏向选择属性值多的属性的不足。此外，在树构造过程中或构造完成后进 行剪枝，提高了抗噪声能力。常用的决策树算法还有s l i q 算法，s l i o 算法对c 4 5 分类算法的实现方法进行了改进，在决策树的构造过程中采用了预排序与广度优 先增长策略，使得该算法能够处理更大的训练集。 ( 2 ) 粗糙集( r o u g hs e t ) 粗糙集理论和各种分类技术相结合建立起能够对不完备数据进行分类的算 法。约简算法是粗糙集理论在分类中的主要应用。 约简主要借助于信息表这样一种有效的知识表达形式，在保持信息表中决策 属性和条件属性依赖关系不变时进行的信息表约简，具体包括属性约简和值约简。 属性约简在一定程度上对信息表中的非必要的冗余信息进行约简，但对每一个实 例而言仍可能存在不必要的属性，因此在不引起冲突的条件下可将每一个实例的 6 不必要属性删除，即为值约简。值约简的最终结果就是分类所需要的规则，常见 的值约简算法包括归纳值约简、启发式值约简、基于决策矩阵的值约简算法等。 ( 3 ) 神经网络 神经网络分类过程可以分为训练和分类两个阶段。在训练阶段，首先定义网 络的拓扑结构，再对训练样本中的每个属性的值进行规范化预处理，然后用神经 网络对已预处理的输入进行学习。训练完毕后，用训练好的神经网络对标识样本 进行分类。目前的神经网络模型很多，而反向传播模型( b p 模型) 是使用最多的 典型神经网络。 神经网络法的优点是有较强的抗噪能力，对未经训练的数据也具有较好的预 测分类能力。神经网络的主要缺点是它的知识表示问题，也就是说用加权链连结 单元的网络所表示的知识很难被人理解。此外，神经网络法的学习时间较长，仅 适用于时间容许的应用场合；对于如网络结构等关键参数，通常需要经验方能有 效确定。 ( 4 ) 贝叶斯分类算法 贝叶斯分类是统计学分类方法，它是一类利用概率统计进行分类的算法，此 算法利用b a y e s 定理来预测一个未知类别的样本的可能属性，可选择其可能性最 大的类别作为该样本的类别。在许多场合，朴素贝叶斯( n a i v eb a y e s ) 分类算法可以 与决策树和神经网络分类算法相媲美。由于贝叶斯方法可以综合先验信息和后验 信息，既可以避免只使用先验信息可能带来的主观偏见以及缺乏样本信息时的大 量盲目搜索与计算，也可以避免只使用后验信息带来的噪声影响，因此，适用于 具有概率统计特征的数据采掘和知识发现问题。但贝叶斯定理假设一个属性对给 定类的影响独立于其他属性，但此假设在实际情况中经常不成立，因此影响了其 分类的准确率。为此，也出现了许多降低独立性假设的贝叶斯改进分类算法，如 t a n ( t r e ea u g m e n t e db a y e sn e t w o r k ) 算法、贝叶斯信念网络、半朴素贝叶斯算法、 b a n 算法等多种改进算法。 1 3粗糙集理论的发展及研究现状 1 3 1粗糙集理论的产生与发展 自然界中大部分事物所呈现的信息都是不完整和含糊的。但在经典逻辑中， 只有真假二值之分，因而无法对此类问题进行准确的描述。长期以来许多逻辑学 家和哲学家都致力于研究含糊概念。在1 9 0 4 年谓词逻辑的创始人g f r g e e 就提出 了含糊( v a g u e ) - - 词，将含糊性归结到边界线上，即在全域上存在一些个体，它既 7 不能被分类到某一个子集上，也不能被分类到该子集的补集上。2 0 世纪6 0 年代初， l a z a d e h 提出模糊集【1 7 j ，试图通过这一概念解决含糊概念，但遗憾的是模糊集 不可计算，往往采用隶属度函数来处理模糊性，而基本上隶属度是凭经验或者由 领域专家给出，所以具有相当的主观性【1 8 】。到2 0 世纪8 0 年代初，p a w l a k z 提出 了粗糙集，把边界线区域定义为上、下近似集之差集f 1 9 】。由于上下近似可以通过 等价关系给出确定的数学公式描述，所以可以计算含糊元素数目，即在真假二值 之间的含糊程度可以计算，从而真正实现了g f r e g e 的边界线思想。 1 9 9 1 年，p a w l a k z 出版专著，较系统地阐述了粗糙集理论思想，奠定了粗糙 集的数据基础【l 引。s l o w i n s k i r 在1 9 9 2 年出版粗糙集理论应用专集，较好的概括该 时期粗糙集理论与实践的研究成果，促进了它的近一步发展。1 9 9 2 年，在波兰召 开了第一届国际粗糙集研讨会，会议着重讨论了集合近似的基本思想及其应用， 其中粗糙环境下的机器学习的基础研究成为这次会议的四个专题之一。1 9 9 3 年在 加拿大召开了第二届国际粗糙集与知识发现研讨会，这次会议积极推动了国际上 对粗糙集应用的研究。值得强调的是，由于这次会议正值知识发现成为热门研究 话题之际，一些著名的知识发现学者参加了这次会议，并且介绍了许多应用扩展 粗糙集理论的数据挖掘的方法与系统。1 9 9 6 年在日本东京召开了第五届国际粗糙 集研讨会，这也是第一次在亚洲召开的较有影响的粗糙集研讨会，该次会议极大 地推动了亚洲地区对粗糙集理论与应用的研究。现在，美国、加拿大、波兰、日 本都有粗糙集研究的专门机构。我国从1 9 9 4 年开始对粗糙集的研究，并在2 0 0 1 年5 月在重庆召开了第一届中国粗糙集理论与软计算学术研讨会。 1 3 2粗糙集理论的研究与应用 过去二十多年来，粗糙集以其独特的优势赢得越来越多的关注。许多研究者 从不同角度对粗糙集理论进行了探索，取得了大量的研究成果，粗糙集理论也因 此得到了不断的发展和完善。目前，粗糙集已成为信息科学最活跃的研究领域之 一，该理论在医学、化学、材料学、地理学、管理科学和金融等其他学科都得到 成功的应用。而随着k d d 和d m 的兴起，可以预言，粗糙集方法也将在数据挖掘 和软计算，特别是处理大型数据库和复杂问题等方面，显示出“英雄有用武之地 的气魄。 尽管粗糙集已有了很好的发展和运用，但它仍是一个极其年轻并在高速发展 的学科，需要进行大量理论研究。这些研究主要集中在数学性质、模型拓展、有 效算法以及其他智能分析方法的融合等方面，本文具体归纳如下： 1 数学性质 随着对粗糙集的研究不断深入，它与其他数学分支的联系也就显得更加紧密。 近年来，许多学者发表了大量关于粗糙集代数、粗糙集拓扑及其性质、粗糙逻辑 及处理近似推理的逻辑工具的论文，这些论文充分阐述粗糙集与模糊集、证据理 论之间的关系，并建立了粗糙集与概率逻辑、模态逻辑等统一框架【2 睨。粗糙集 理论研究需要以这些理论为基础，同时也相应的带动这些理论的发展。 2 粗糙集模型拓展 模型拓展方面的研究包括可变精度模型、相似模型以及对这些模型的改进。 由于经典粗糙集在面对数据集中的噪声干扰时，会由于对数据的过度拟合而使对 新对象的预测能力大大降低，z i a r k o 提出可变精度粗糙集模型v p r s ，该模型通过 引入一个精度，允许粗糙集存在一定误分类率，从而使粗糙集模型具有一定的容 错性瞄】。v p r s 和经典粗糙集是兼容的，因为只要令系统误分类率为0 ，v p r s 就 退化为经典粗糙集模型，所以它能够保持绝大数经典模型的良好性质。a n e t a l 对可 变精度粗糙集模型包含度概念作了适当调整，并通过可变精度粗糙集模型产生概 率规则，实现了水资源预测。k a t z b e r g 和z i a r k o 提出了不对称边界的v p r s 模型， 使此模型更加一般化，从而拓宽了v p r s 的应用范围【2 3 1 。不可分辨关系是粗糙集 理论的基础，它是一个等价关系，但在很多情况下，等价要求过于苛刻，为了加 强粗糙集的性能，m a r z e n a k 提出用相似关系来代替不可分辨关系，s l o w i s k i r 进 一步阐述相似关系模型的定义和性质【2 4 】。相似关系代替粗糙集合中的不可分辨关 系后，最主要的变化就是相似类不再形成对原集合的划分，它们之间相互重叠类 似于等价类，可以定义相似集。王国胤把相似关系以及非对称相似关系用于处理 信息系统中的不完备知识，取得很好的效梨1 6 1 。 3 算法研究 粗糙集理论中算法的研究主要集中在约简的启发式算法、规则获取的增量式 算法以及粗糙集并行算法等方面。s k o w r o n 最早提出了可分辨矩阵的概念，可方便 的计算系统的核和约简，在其基础上构造可分辨函数，利用逻辑运算转换可求得 所有约简，但只适合非常小的数据剿2 5 1 。s t a r z y k 和n e l s o n 提出一种新的概念：强 等价，若两个属性在可分辨矩阵所有项中同时出现或同时不出现，它们就可以用 一个属性代替，从而简化可分辨函数，可大幅度提高求取约简的速度，因而能处 理较大的数据集【2 6 】。h u x 提出启发式的约简算法，算法用核作为约简计算的基础， 以属性重要性作为启发信息，按属性重要性的大小逐个将属性加入约简集合 2 7 1 。 以不同属性重要性作为启发式信息，衍生了不同的启发式算法，包括基于正域知 识的【2 8 1 、条件信息熵2 、属性频率【2 明等。然而在面对海量数据时，上述约简得出 的规则容易受噪声干扰，往往具有不稳定性，j a ng b a z o n 在粗糙集基本理论的基 础上提出了动态约简的基本思想，该理论通过从给定决策信息系统中随机抽样形 9 成的子表中获取最常出现的约简，在某种意义上是给定决策信息系统中最稳定的 约简，能够有效的增强约简的抗噪声能力，同时具有很好的“增量特性 3 0 1 。但 是粗糙集在数据挖掘中具有较大的计算复杂度，反复抽样实际上进一步恶化了该 问题。 4 多方法融合 j e l o n e k 等研究了将粗糙集用于神经网络训练数据的预处理，有利于提高学习 效率，并且保持了较低的稳定的近似分类误分率和差错率【2 4 j 。受关联规则挖掘算 法的启发，有些作者提出将关联规则挖掘技巧应用于粗糙集的确定和可能规则的 生成中【2 5 1 。多方法的融合可能可以进一步提高分类效能，因而多方法的融合也是 粗糙集发展的重要方向。 5 应用研究 粗糙集自诞生到现在虽然只有2 0 几年，但已经在很多领域取得了令人鼓舞的 成果。 股票数据分析：g o l a n 和z i a r k o 应用粗糙集方法分析了十年间股票的历史数 据，研究了股票价格与经济指数之间的依赖关系，获得的预测规则得到了华尔街 证券交易专家的认可【3 2 】。 模式识别：n e j m a n 应用粗糙集方法研究了手写字符识别问题，提取出了特征 属性3 3 1 。 决策分析：在决策分析方面，粗糙集理论的决策规则是在分析以往经验数据 的基础上得到的，它允许决策对象存在一些不太明确的属性。希腊发展银行e t e v a 应用粗糙集理论协助制定信贷政策，是粗糙集理论多准则决策方法的一个成功范 例【蚓。 医疗诊断：粗糙集方法根据以往的病例归纳出诊断规则，用来指导新的病例 诊断。现有的人工预测早产的准确率只有1 7 3 8 ，应用粗糙集理论则可提高到 6 8 9 0 【3 5 1 。 除此之外，粗糙集在工业、经济和社会等诸如专家系统控制、人工神经网络、 电力系统、软件工程、过程控制、图像处理、信息融合、企业、商业、金融分析、 医疗诊断、决策支持和投票分析领域也获得广泛的应用。 1 4 论文的结构框架 本文主要工作是研究粗糙集理论在数据挖掘中的应用，并重点从理论和实际 应用两个方面展开。本文将通过6 章内容对该研究工作进行具体论述，论文结构 框架图见图1 1 。 1 0 第一章，简要叙述了数据挖掘技术和粗糙集理论的发展状况及应用特点，对 国内外研究现状作了全面介绍，点明本文研究工作的主要内容和意义。 第二章，介绍粗糙集的理论基础。详细叙述信息系统、集合的上下近似、知 识化简与核、不可分辨关系、分类精度等重要概念，并在可变精度粗糙集理论下 对这些概念进行了重新定义。 第三章，介绍了粗糙集在数据挖掘中的应用状况，同时分析了基于粗糙集理 论的数据挖掘的基本原理和特点。给出了基于粗糙集的数据挖掘的基本流程并指 出其研究的方向及重点。 第四章，重点介绍了属性简约和规则处理阶段目前存在的一些经典算法，阐 述了它们各自的原理及其特征，并在此基础上分别提出两个新的改进算法。实验 证明这两个算法较于经典算法，不仅在时间、空间复杂度上存在优越性，而且能 够有效地处理数据挖掘过程存在的噪声数据。 第五章，以车站建设施工数据和安全验收数据为挖掘目标，完成了从预处理 到建模的一系列过程，最终建立了基于改进的属性约简算法和决策树算法的分类 模型。最后通过比较和分析2 0 0 8 年北京地铁四号线西单站施工数据的分类挖掘结 果，对挖掘模型和改进算法的有效性和实用性进行了实证研究。 第六章，回顾了本文所做的一些工作，并对未来继续研究的方向进行了展望。 图卜1 论文的结构框架 f i g u r ei - 1f r a m e w o r ko f t h ep a p e r 2 粗糙集理论 粗糙集是研究不完整和不精确信息的有效方法【博】。与其它处理模糊性和不确 定性问题的数学工具相比，该理论的最大特点是无需提供任何预备的或额外的先 验信息。其基本思想是利用定义在数据集合上的等价关系作为知识，知识的不确 定度则是在数据整体处理之后自然获得吲3 6 1 。粗糙集理论无需对数据的局部给予 主观评价，从这个角度上讲，粗糙集理论对不确定性的描述相对比较客观。 本章从知识分类、信息表和不可分辨关系出发，介绍粗糙集理论的有关概念， 并在可变精度粗糙集理论下对这些基本概念进行了重新定义。 2 1知识表达系统 粗糙集认为知识是人类对对象进行的分类能力，而分类是按照某种特征属性 将具有相同属性值的“对象 分别归纳在各自的集合中的方法，或者是按照某种 等价关系进行归类的方法。而通常在分类对信息系统进行处理时，我们还会将讨 论的“对象 限制在某一个特定的区域范围之内，这个区域内的所有个体就组成 了问题的论域。于是分类还可以进一步理解为是利用等价关系对论域进行划分的 过程。分类、等价关系、论域和信息系统都是粗糙集中最基本的概念【3 8 1 。 定义2 1信息系统( i n f o r m a t i o ns y s t e m ) 可以表示为元组s = 似4 k 厂) ，其 中u 表示对象的非空有限集合，称为论域。a 称为属性集，形表示属性，c a 的取 值范围，厂表示u x a 专v 是一个信息函数( i n f o r m a t i o nf u n c t i o n ) ，它指定了u 中每一个对象的属性值。 信息系统也可以表示为s = 似cu 皿v , j 9 的形式，其中u 和厂的意义不变，c 称 为条件属性集，d 称为决策属性集，c u d = a ，且cnd = 。这种具有条件属性 集合和决策属性集合的信息系统被称为决策信息系统【3 9 1 。 决策信息系统通常都以表格的形式来表达，称为决策表。 表2 1 给出一个汽车销售的决策信息系统。 在表中，信息表的列表示属性，行表示对象，每个单元格表示对象的属性值。 u = e l ，e 2 ，e 3 ，e 4 ，e 5 ，e 6 ， 燃料消耗，外观质量，销售价格) 是条件属性集合， 市场状况) 则是决策属性集。 定义2 2 设r 为等价关系集合，r 对论域u 的划分：u r = 五，五，置l 称 为知识；( u ，r ) 为近似空间；【x 】露表示包含元素x 的尺等价类，工u ；r 对u 划 分得到的任何子集x ；u ，可称为u 上的一个概念或范畴。 1 2 表2 1 决策信息系统 t a b l e2 - 1ad e c i s i o ns y s t e m 个体编号燃料消耗c l外观质量c 2销售价格c 3市场状况c 4 e l 多差适当不乐观 e 2较多好 适当不乐观 e 3中差 适当乐观 e 4 较多差低不乐观 e 5 多好低乐观 e 6多好高 不乐观 定义2 3 不可分辨关系( i n d i s c e r n i b i l i t yr e l a t i o n ) ：给定一个信息系统 s = ( u , 4 v , j o ，且有尺s a ，x , y u 。当且仅当f ( q ，力= 厂( g ，力，v q e r ，我们称x ，y 在s 中无法根据属性集合尺相互区分。对于每一个尺互彳可以定义一个不可分辨二 元关系( 不可分明关系) 1 n d ( r ) ，i n d ( r ) = ( x ，y ) u 2 , v q 尺，厂g ) = f ( y ，g ) 。 显然，1 n d ( r ) 是一个等价关系，也是u 的一个划分，记为u