（计算机应用技术专业论文）粗糙集和计算智能相结合的数据挖掘算法研究.pdf

摘要 海量数据与知识贫乏导致了数据挖掘技术的出现，它的主要目标是采用自动 的、智能化的新技术来分析海量数据，以获得有效的、隐含的、以前未知的、有 潜在使用价值的有用信息。它是当今众多学科领域特别是数据库领域最前沿的研 究课题之一。粗糙集理论是一种新的处理模糊和不确定性知识的数学工具，其主 要思想是在保持分类能力不变的情况下，通过知识约简，导出问题的决策或者分 类规则。计算智能技术以神经网络、模糊逻辑以及进化计算等为核心，模仿人类 的思维方式及演化规律，已经在工业控制、模式识别等领域得到了广泛的应用。 目前，在数据挖掘领域粗糙集和计算智能方法相结合还主要用于数据预处理阶 段，基于他们的分类、聚类和关联规则挖掘算法还很少。 本文介绍了数据挖掘、粗糙集理论和计算智能理论的基本概念以及应用，分 析了粗糙集理论和计算智能理论在数据挖掘方面的应用以及它们之间的互补性。 针对粗糙集在处理符号属性方面的优势，设计了一种新的聚类算法，将基于共享 机制的小生境遗传算法运用到分裂式层次聚类算法中，并用粗糙集的思想来定义 遗传算法的适应度函数，实验表明该算法在面向符号属性进行聚类时具有较高的 聚类准确率。此外，提出了一种新型分类算法，将粗糙集与组织协同进化分类算 法相结合，利用支持子集的思想来决定组织的适应度，利用支持子集得到的启发 信息来加快进化速度，增强种群之间的相互协同，实验表明，当数据集中的属性 全部为符号属性时，该算法具有较高的分类准确率并且时间代价较小。 关键词：粗糙集；数据挖掘；计算智能；遗传算法；组织协同进化；分类；聚类 a b s t r a c t m a s s i v ed a t aa n dl a c k i n go fk n o w l e d g el e dt ot h ea p p e a r a n c eo fd a t am i n i n g t e c h n o l o g yw h i c hm a i ng o a li st oo b t a i ne f f e c t i v e ，i m p l i e d ，p r e v i o u su n k n o w na n d v a l u a b l ei n f o r m a t i o n t o d a yd a t am i n i n gi si nt h ef o r e f r o n to fr e s e a r c ht o p i c so f d a t a b a s ef i e l d s t h er o u g hs e tt h e o r yi sau s e f u lt o o lt od e a l 、析t l lv a g u e n e s sa n d u n c e r t a i n t y i tc a ni n d u c ed e c i s i o no rc l a s s i f i c a t i o nr u l et h r o u g hk n o w l e d g er e d u c t i o n w h i l et h ec l a s s i f ya b i l i t yw a sn o td e c r e a s e d t h et e c h n o l o g yo fc o m p u t a t i o n a l i n t e l l i g e n c e w h i c hi n c l u d e sn e u r a ln e t w o r k s ，f u z z yl o g i ca n de v o l u t i o n a r y c o m p u t a t i o ni m i t a t eh u m a nw a y o ft h i n k i n ga n de v o l u t i o na n dh a sb e e nw i d e l yu s e d i nt h ei n d u s t r i a lc o n t r o l ，p a t t e r nr e c o g n i t i o n ，a n do t h e rf i e l d s c u r r e n t l y , i nt h ea r e ao f d a t am i n i n gt h ec o m b i n a t i o no fr o u g hs e ta n dc o m p u t a t i o n a li n t e l l i g e n c ei sm a i n l y u s e di nt h es t a g eo fd a t ap r e p r o c e s s i n ga n dr a r e l yu s e di nc l a s s i f i c a t i o n ，c l u s t e r i n ga n d t h em i n i n go fa s s o c i a t i o nr u l ea l g o r i t h m t h eb a s i cc o n c e p ta n da p p l i c a t i o no fd a t am i n i n g ，t h et h e o r yo fr o u g hs e ta n dt h e t h e o r yo fc o m p u t a t i o n a li n t e l l i g e n c ea r ei n t r o d u c e d t h ea p p l i c a t i o na n dm u t u a l c o m p l e m e n ti nd a t am i n i n go fr o u g hs e tt h e o r ya n dc o m p u t a t i o n a li n t e l l i g e n c e a r e a n a l y z e d i nv i e wo ft h ep r e d o m i n a n c eo fr o u g hs e tt h e o r yi nd e a l i n gw i t hs y m b o l i c a t t r i b u t e s ，an e wc l u s t e r i n ga l g o r i t h mi sp r o p o s e dw h i c hu s en i c h eg e n e t i ca l g o r i t h m b a s e do ns h a r i n gm e c h a n i s mt od i v i s i v eh i e r a r c h i c a lc l u s t e r i n ga n du s et h et h e o r yo f r o u g hs e tt od e f i n ef i t n e s sf u n c t i o no fg a t h ee x p e r i m e n t ss h o wt h a tt h ec l u s t e r i n g a c c u r a t er a t eo ft h i sa l g o r i t h mi sh i g h e rt h a na n o t h e rt w oa l g o r i t h m sf o rs y m b o l i c a t t r i b u t e s i na d d i t i o n ，an e wc l a s s i f i c a t i o na l g o r i t h mi sp r o p o s e dw h i c hc o m b i n e s r o u g hs e tt h e o r ya n do r g a n i z a t i o n a lc o e v o l u t i o n a r ya l g o r i t h mf o rc l a s s i f i c a t i o na n d u s et h ei d e ao fs u p p o r ts u b s e tt od e t e r m i n et h ef i t n e s so fo r g a n i z a t i o n sa n du s et h e s u g g e s t i o no ft h es u p p o r ts u b s e tt oa c c e l e r a t et h ee v o l u t i o na n de n h a n c et h es y n e r g i e s b e t w e e nt h eg r o u p s e x p e r i m e n t ss h o wt h a tw h e na l la t t r i b u t e so fd a t as e ta r e s y m b o l i ca t t r i b u t e st h i sa l g o r i t h mh a sh i g h e rc l a s s i f i c a t i o na c c u r a t er a t ea n d c o s t sl e s s t i m et h a na n o t h e ra l g o r i t h m k e yw o r d s ：r o u g hs e t ；d a t am i n i n g ；c o m p u t a t i o n a li n t e l l i g e n c e ；g a ； o r g a n i z a t i o n a lc o e v o l u t i o n a r ya l g o r i t h m ；c l a s s i f i c a t i o n ；c l u s t e r i n g i l 学位论文原创性声明与版权使用授权书 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：存吾i 也 日期：知。睥5 月7 e t 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名：廖善i 记 导师签名：零可 日期：工p 扩年石月7 日 日期：p 亨年5 月夕日 第一章绪论帚一早珀t 匕 数据挖掘是数据库领域一个有希望的、欣欣向荣的学科。数据挖掘通常又称 为数据库中的知识发现，是自动的或者方便的模式提取，这些模式代表隐藏在大 型数据库、数据仓库或者其他大量信息存储中的知识。粗糙集理论是一种新的 处理模糊和不确定性知识的数学工具，其主要思想是在保持分类能力不变的情况 下，通过知识约简，导出问题的决策或者分类规则堙1 ，目前在数据挖掘领域主要 用于数据预处理以及分类规则的生成。计算智能技术以神经网络、模糊逻辑以及 进化计算等为核心，模仿人类的思维方式及演化规律，已经在数据挖掘领域得到 了广泛的应用。 由于计算智能的各种方法在很大程度上具有互补性，因此将计算智能的各种 方法相结合可以设计性能更高的数据挖掘算法已成为许多学者的共识，这方面的 研究已经进行了很长时间，技术已经比较成熟1 驯。而将粗糙集与计算智能方法 相结合尚处于开始阶段，许多学者也进行了一些尝试并取得了不错的效果，但研 究工作还有待于进一步展开。目前，在数据挖掘领域中粗糙集和计算智能方法相 结合还主要用于数据预处理阶段，基于他们的分类、聚类和关联规则挖掘算法还 很少。本文主要研究将粗糙集和计算智能算法相结合构造性能更高的分类和聚类 算法。 1 1 研究背景和意义 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数 据越来越多，激增的数据背后隐藏着许多重要的信息，人们希望能够对数据进行 分析，以便挖掘出其中存在的关系和规则，并希望能够对其进行更高层次的分析， 以便更好地利用数据并根据现有的数据预测未来的发展趋势。目前的数据库系统 可以高效地实现数据的录入、查询、统计等功能，但无法发现规则和预测趋势， 导致了“数据爆炸但知识贫乏的现象。数据挖掘( d m ：d a t am i n i n g ) 是近年 来随着数据库和人工智能的发展而出现的一门新兴技术，目的是从大量的、不完 全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的、 但又是潜在有用的知识和规则n 1 引。 计算智能已经被大量的应用到数据挖掘技术中，计算智能所涉及到的方法主 要包括人工神经网络、模糊集和以遗传算法为代表的进化计算。 模糊集有很强的搜索能力，利用模糊集理论可对实际问题进行模糊评判、模 糊决策、模糊模式识别和模糊聚类分析，模糊集在数据挖掘中的应用相对比较成 熟，但利用模糊集进行数据挖掘需要数据之外的先验知识，使得挖掘结果缺少客 观性。 神经网络由于本身良好的鲁棒性、自组织自适应性、并行处理、分布存储和 高度容错等特性，非常适合解决数据挖掘的问题，因此近年来越来越受到人们的 关注。神经网络方法的缺点是“黑箱性，人们难以理解网络的学习和决策过程， 当数据集大且不规则时，神经网络的建立和训练时间太长，而且由于神经网络可 变参数太多，很容易产生过度学习。 遗传算法是一种基于生物自然选择与遗传机理的可调节的、鲁棒的、高效率 的随机搜索算法，它具有的并行性、易于和其它模型结合等性质，适用于数据挖 掘，但遗传算法较复杂，收敛于局部极小的早熟问题尚未解决。 粗糙集方法是数据挖掘中一种相对较新的技术口j 5 q 引，它具有以下优点：不 需要给出数据之外的额外信息；可以简化输入信息的表达空间；算法简单，易于 操作；粗糙集处理的对象是类似二维关系表的信息表，目前成熟的关系数据库管 理系统和新发展起来的数据仓库管理系统，为基于粗糙集的数据挖掘奠定了坚实 的基础。 由于计算智能的各种方法在很大程度上具有互补性，因此将计算智能的各种 方法相结合可以设计性能更高的算法己成为许多学者的共识，这方面的研究已经 进行了很长时间，技术已经比较成熟口q 引，例如，将模糊集与神经网络相结合而 成的模糊神经网络，利用遗传算法优化神经网络的权值和结构等等。而将粗糙集 与计算智能方法相结合尚处于开始阶段，许多学者也进行了一些尝试并取得了不 错的效果，但研究工作还有待于进一步展开。 1 2 国内外的研究发展现状 国内外的许多学者对于计算智能和粗糙集相结合都做了一些初步的工作，下 2 面分别介绍。 1 2 1 粗糙集和模糊集的结合 粗糙集和模糊集理论虽然都研究信息系统中的知识不完善、不准确问题，但 二者有明显的区别，模糊集所处理的是内涵明确而界限不清晰( 相互交叠) 的集 合，粗糙集处理的是在现有知识下内涵不明确( 粗糙) 而界限清晰的集合。由此 可见它们分别是对不确定环境中两种不同的不确定性的描述，因此二者具有极强 互补性，将二者结合可以产生比单独使用任何一种更好的效果渺矧。 将粗糙集理论和模糊集理论相结合构成粗糙模糊集，是用粗糙集概念来研究 模糊集的粗近似问题，将粗糙集理论和模糊集理论结合构成模糊粗糙集，是用模 糊集概念来研究粗糙集的模糊相似性问题。模糊粗糙集和粗糙模糊集丰富了信息 系统中对于不完善、不准确知识的描述和处理方法。 d u b o is 等人给出了模糊粗糙集和粗糙模糊集的定义，吴伟志等人用构造 性方法和公理化研究了粗糙模糊集乜，j e s e n 等人将模糊粗糙集用于属性约简 2 2 - 2 3 ，k a s e m s i r i 等人将模糊粗糙集用于泰文字识别1 。 1 2 2 粗糙集和神经网络相结合 粗糙集理论存在容错能力与推广能力差，且只能处理离散数据等问题。而人 工神经网络具有较强的自组织能力、容错能力与推广能力，但不能优选条件属性 组合等特点。因此将粗糙集与人工神经网络相结合将具有理论与应用价值一3 。 舒兰等人利用粗糙集神经网络对m i t b i h 心电数据库中的三类心电信号进行识 别取得了预期的效果乜钔；王玮等人将经典的神经网络和粗糙集理论有机的结合， 给出了另一种基于粗糙集理论的神经网络，并应用神经网络的粗糙模式建立了预 测模型。 1 2 3 粗糙集、模糊集和神经网络三者相结合 这三者相结合主要体现在如下两个方面： ( 1 ) 模糊粗糙集和神经网络相结合。王志勇等人证明了将模糊粗糙集和神经 网络相结合对电力系统的短期负荷进行预测是有效可行的1 ：张东波等人基于模 3 糊粗糙集构建了一种新型的模糊一粗神经网络，并用其进行5 个元音字母的语音 识别取得了较好的效果啪1 。 ( 2 ) 粗糙集和模糊神经网络相结合。於东军等人利用粗糙集从数据库中发现 规则的能力，确定模糊神经网络的初始拓扑结构口；王堵等人利用粗糙集理论来 获取模糊神经网络的初始隶属函数羽。 1 2 4 粗糙集与遗传算法相结合 这两方面的结合主要体现在利用遗传算法的全局搜索能力进行粗糙集的属 性约简。属性约简一直是粗糙集理论研究的重点，无论是研究问题域的关键还是 求出刻划问题的最小规则集，都必须在决策表的最小约简求出的前提下才能得到 解决。但是最小约简的求解是一个n p 难问题由于遗传算法所具有的全局搜索能 力，利用遗传算法进行粗糙集属性约简就成为一个不错的选择。目前，许多基于 遗传算法的粗糙集属性约简算法已经被提出口3 。 就目前来看，将粗糙集和计算智能方法相结合的研究已经取得了初步的成 果，但在许多的领域还有待于进一步的研究。 1 3 主要工作 在阅读了大量相关文献的基础上，分析了粗糙集和计算智能相结合的数据挖 掘算法的研究现状，并深入研究了文献中提出的各种相关算法，包括粗糙集与模 糊集相结合的数据挖掘算法、粗糙集与神经网络相结合的数据挖掘算法、粗糙集 与进化计算相结合的数据挖掘算法以及粗糙集与模糊集、神经网络三者相结合的 数据挖掘算法等，但由于时间的关系，仅取得了如下两项成果。 ( 1 ) 针对粗糙集在处理符号属性方面的优势，提出了一种基于粗糙集和小 生境遗传算法的层次聚类算法，这种算法将基于共享机制的小生境遗传算法运用 到分裂式层次聚类算法中，并用粗糙集的思想来定义遗传算法的适应度函数。通 过实验将该算法与其它算法进行了比较，实验结果表明该算法在面向符号属性进 行聚类时具有较高的聚类准确率。 ( 2 ) 提出了一种基于粗糙集和组织协同进化的分类算法，利用粗糙集思想 对组织协同进化分类算法进行了改进，利用支持子集的思想来决定组织的适应 4 度，利用支持子集得到的启发信息对所有种群中的组织进行优化重构，从而加快 了进化速度，增强了种群之间的相互协同。通过实验将该算法与其它算法进行了 比较，实验结果表明，当数据集中的属性全部为符号属性时，该算法具有较高的 分类准确率和较小的时间代价。 1 4 论文的组成结构 第一章是绪论，介绍了本文的研究意义和背景，并对国内外将粗糙集与计算 智能算法相结合用于数据挖掘的研究现状进行了分析，最后对本文所做的主要工 作进行了介绍。 第二章介绍了数据挖掘、粗糙集以及计算智能的一些基本概念、方法和应用。 首先回顾了数据挖掘的发展历程，接着介绍了数据挖掘的用途、常用方法以及数 据挖掘的流程，并就数据挖掘的研究方向和热点问题进行了探讨；然后介绍了粗 糙集理论的发展与特点，粗糙集理论中的基本概念，以及粗糙集在数据挖掘中的 应用等；最后对计算智能理论进行了概述，并介绍了计算智能的三个主要组成部 分：模糊集、神经网络和进化计算。 第三章将粗糙集与小生境遗传算法相结合，提出了一种基于粗糙集和小生境 遗传算法的分裂式层次聚类算法，并通过实验将该算法与文献 4 6 所提出的算法 r s h c 以及文献 4 6 中所比较的算法a 进行了比较，实验结果表明该算法在面向 符号属性进行聚类时具有较高的聚类准确率。 第四章利用粗糙集中支持子集的思想对组织协同进化分类算法进行了改进， 提出了一种基于粗糙集和组织协同进化的分类算法，并通过实验将该算法与文献 5 7 所提出的算法进行了比较，实验结果表明，当数据集中的属性全部为符号属 性时，该算法具有较高的分类准确率和较小的时间代价。 第二章预备知识 本章将对数据挖掘、粗糙集以及计算智能的基本概念与方法进行介绍和分 析。 2 1 数据挖掘的发展 2 1 1 发展概述 2 0 世纪6 0 年代，数据库及信息技术就逐步从基本的文件处理系统发展为更 复杂、功能更强大的数据库系统；2 0 世纪7 0 年代的数据库系统的研究与发展， 最终导致了关系数据库系统、数据建模工具、索引与数据组织技术的迅速发展， 这时用户获得了更方便灵活的数据存取语言和界面；此外，联机事务处理( o l a p ) 的出现也极大地推动了关系数据库技术的应用普及，尤其是在大数据量存储、检 索和管理的实际应用领域。 2 0 世纪8 0 年代中期开始，关系数据库技术被普遍采用，并提出了许多先进 的数据模型和应用数据库系统，特别是异构数据库系统和基于互联网的全球信息 系统的飞速发展，最终导致了快速增长的庞大数据，这些数据远远超过人类的处 理和分析理解能力。数据与信息知识之间的巨大差距导致数据挖掘技术应运而 生，数据挖掘能从大量数据中发现所存在的特定模式规律，来帮助实现将海量数 据集中的数据转化为知识，从而为商业活动、科学探索和医学研究等诸多领域提 供所必需的信息知识。 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果，它不仅能对 过去的数据进行查询和遍历，而且能找出过去数据之间的潜在联系，从而促进信 息的传递。总的来说，是以下技术的发展激发了数据挖掘的开发、应用和研究侧： ( 1 ) 超大规模数据库的出现，例如商业数据仓库和计算机自动收集的数据记 录； ( 2 ) 先进的计算机技术，例如更快和更大的计算能力和并行体系结构； ( 3 ) 对海量数据的快速访问； 6 ( 4 ) 对这些数据应用精深的统计方法计算的能力。 2 1 2 研究热点 就目前来看，将来的几个热点包括网站的数据挖掘( w e bs i t ed a t am i n i n g ) 、 生物信息或基因( b i o i n f o r m a t i c s g e n o m i c s ) 的数据挖掘及其文本的数据挖掘 ( t e x t u a lm i n i n g ) 。 ( 1 ) 网站的数据挖掘 随着w e b 技术的发展，各类电子商务网站风起云涌，如何让电子商务网站有 效益是一个关键问题。电子商务网站每天都生成大量的记录文件和登记表，如果 能对这些数据进行分析和挖掘，充分了解客户的喜好、购买模式，并设计出满足 于不同客户群体需要的个性化网站，必能增加商家的竞争力。在对网站进行数据 挖掘时，所需要的数据主要来自于两个方面：一方面是客户的背景信息，主要来 自于客户的登记表；另外一部分数据主要来自浏览者的点击流，主要用于考察客 户的行为表现。就分析和建立模型的技术和算法而言，网站的数据挖掘和原来的 数据挖掘差别不大，很多方法和分析思想都可以运用。所不同的是网站的数据格 式有很大一部分来自于点击流，和传统的数据库格式有区别。因而对电子商务网 站进行数据挖掘所做的主要工作是数据准备。目前，有很多厂商正在致力于开发 专门用于网站挖掘的软件。 ( 2 ) 生物信息或基因的数据挖掘 生物信息或基因数据挖掘在商业上很难讲有多大的价值，但对于人类却受益 非浅。由于数据复杂、数据量大，生物信息或基因的数据挖掘比通常的数据挖掘 要复杂得多，因此更需要一些新的和好的算法。现在很多厂商正在致力于这方面 的研究，但就技术和软件而言，还远没有达到成熟的地步。 ( 3 ) 文本的数据挖掘 无论是在数据结构还是在分析处理方法方面，文本数据挖掘与数据库中的数 据挖掘相差很大。文本数据挖掘并不是一件容易的事情，尤其是在分析方法方面， 还有很多需要研究的专题。目前市场上有一些类似的软件，但大部分方法只是把 文本移来移去，或简单地计算一下某些词汇的出现频率，并没有真正的分析功能。 随着计算机计算能力的发展和业务复杂性的提高，数据的类型会越来越多、 7 越来越复杂，数据挖掘将发挥出越来越大的作用。 2 1 3 未来研究方向 当前，数据挖掘研究与开发的总体水平相当于数据库技术在2 0 世纪7 0 年代 所处的地位，迫切需要类似于关系模式、d b m s 系统和s o l 查询语言等理论和方 法的指导，才能使其应用得以普遍推广。预计在本世纪，数据挖掘的研究焦点可 能会集中到以下几个方面： ( 1 ) 发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言，也 许会像s o l 语言一样走向形式化和标准化； ( 2 ) 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户理解， 也便于在知识发现的过程中进行人机交互； ( 3 ) 研究在网络环境下的数据挖掘技术( w e bm i n i n g ) ，特别是在因特网上建 立数据挖掘服务器，并且与数据库服务器配合，实现w e bm i n i n g ； ( 4 ) 加强对各种非结构化数据的挖掘( d a t am i n i n gf o ra u d i o v i d e o ) ， 如对文本数据、图形数据、视频图像数据、声音数据乃至综合多媒体数据的挖掘： ( 5 ) 处理的数据将会涉及到更多的数据类型，这些数据类型或者比较复杂， 或者是结构比较独特。为了处理这些复杂的数据，就需要一些新的和更好的分析 和建立模型的方法，同时还会涉及到为处理这些复杂或独特数据所做的费时和复 杂数据准备的一些工具和软件。 2 2 数据挖掘的任务和方法 2 2 1 数据挖掘的任务 数据挖掘所发现的知识最常见的有以下六类： 1 总结型知识 总结型知识( c o n c l u s i o n ) 是对数据进行浓缩后给出的对数据的紧凑描述。与 传统的数据统计方法不同，数据挖掘主要从数据泛化的角度来讨论数据总结。数 据泛化是一种把数据库中的有关数据从低层次抽象到高层次上的过程。由于数据 库上的数据或对象所包含的信息总是最原始、基本的信息，人们有时希望能从较 8 高层次的视图上处理或浏览数据，因此需要对数据进行不同层次上的泛化以适应 各种查询要求。 2 关联知识 关联知识( a s s o c i a t i o n ) 是反映一个事件和其他事件之间依赖或关联的知 识。如果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他 属性值进行预测。最为著名的关联规则发现方法是a g r a w a lr 提出的a p r i o r i 算 法。关联规则的发现可分为两步。第一步是迭代识别所有的频繁项目集，要求频 繁项目集的支持度不低于用户设定的最低值；第二步是从频繁项目集中构造可信 度不低于用户设定的最低值的规则。识别或发现所有频繁项目集是关联规则发现 算法的核心，也是计算量最大的部分。 3 分类知识 分类知识是( c l a s s i f i c a t i o n ) 反映了同类事物的共性和不同事物之间的差 异。分类需要一个分类函数或分类模型( 分类器) ，该函数或模型能把数据库中的 数据项映射到给定类别中的某一个。分类所要做的是在已知训练数据的特征和分 类结果的基础上，为每一种类别找到一个合理的描述或模型，然后再用这些描述 或模型来对不可知的新数据进行分类。分类的效果一般和数据的特点有关，有的 数据噪声大，有的有缺省值，有的分布稀疏，有的字段或属性间相关性强，有的 属性是离散的而有的是连续值或混合式的。目前普遍认为不存在某种方法能适合 于各种特点的数据。 4 聚类知识 聚类( c l u s t e r i n g ) 是把一组个体按照相似性归成若干类别，即物以类聚。 它的目的是使得属于同一类别的个体之间的距离尽可能的小，而不同类别上的个 体间的距离尽可能的大。聚类方法包括统计方法、机器学习方法、神经网络方法 和面向数据库的方法。 5 预测型知识 预测型知识( p r e d i c t i o n ) 根据时间序列型数据，由历史的和当前的数据去 推测未来的数据，也可以认为是以时间为关键属性的关联知识，也被称为趋势分 析。目前，时间序列预测方法有经典的统计方法、神经网络和机器学习等。 6 偏差型知识 9 偏差型知识( d e v i a t i o n ) 又称为比较分析，它是对差异和极端特例的描述， 揭示事物偏离常规的异常现象，如标准类外的特例，数据聚类外的离群值等。所 有这些知识都可以在不同的概念层次上被发现，并随着概念层次的提升，从微观 到中观、到宏观，以满足不同用户不同层次决策的需要。 2 2 2 常用的方法 数据挖掘中常用的方法主要有神经网络技术、决策树、遗传算法、覆盖正例 排斥反例方法、糊糊集、粗糙集，以及规则推导等。 2 3 数据挖掘的过程与应用 2 3 1 数据挖掘的过程 数据挖掘是一个完整的过程，该过程从大型数据库中挖掘先前未知的，有效 的，可实用的信息，并使用这些信息做出决策或丰富知识。图2 1 描述了数据挖 掘的基本过程和主要步骤。 i ii i- l- 清理与集成 选择与变换数据挖掘评估与表示 图2 1 数据挖掘的基本流程 1 确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘 的最后结果是不可预测的，但要探索的问题应是有预见的，不能盲目地进行数据 挖掘，必须确定业务对象。 2 数据准备 ( 1 ) 数据的选择。搜索所有与业务对象有关的内部和外部数据信息，并从中 选择出适用于数据挖掘应用的数据。 l o ( 2 ) 数据的预处理。研究数据的质量，为进一步的分析做准备。并确定将要 进行的挖掘操作的类型。 ( 3 ) 数据的转换。将数据转换成一个分析模型。这个分析模型是针对挖掘算 法建立的。建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 3 数据挖掘 对经过转换的数据进行挖掘。除了选择合适的挖掘算法外，其余一切工作都 能自动地完成。 4 结果分析 解释并评估结果。其使用的分析方法一般应视数据挖掘操作而定，通常会用 到可视化技术。 5 知识的表示 将分析所得到的知识集成到业务信息系统的组织结构中。 数据挖掘是一个多专家合作的过程，也是一个在资金上和技术上高投入的过 程。这一过程要反复进行，在反复过程中，不断地趋近事物的本质，不断地优化 问题的解决方案。 2 3 2 数据挖掘的应用 目前国际上数据挖掘技术在许多行业已得到广泛应用：国内在数据挖掘方面 也有成功的应用，例如宝钢己应用数据挖掘系统辅助生产决策，每年能节省近千 万元资金。现在我国的研究人员正在加紧研制有关领域的数据挖掘工具，并且数 据挖掘技术的应用领域正不断扩大，目前主要的应用领域有h 叭： ( 1 ) 科学研究。在信息量极为庞大的天文、气象、生物技术等领域中，由于 所获得的大量实验和观测数据靠传统的数据分析工具已难以对付，因此对功能强 大的智能化自动分析工具要求迫切，这种需求推动了数据挖掘技术在科学研究领 域的应用，并且己获得一些重要的应用成果。 ( 2 ) 金融投资。由于金融投资的风险很大，因此在进行投资决策时，需要对 各种投资方向的有关数据进行分析，以选择最佳的投资方向。数据挖掘可以通过 对已有数据进行处理，并利用学习得到的模式进行市场预测。 ( 3 ) 市场营销。在市场营销领域中，数据挖掘可以辅助制定市场策略，分析 购物模式，还可以用来预测销售行情。 ( 4 ) 保险业。保险是一项风险业务。保险公司的一个重要工作就是进行风险 评估。通过研究证明，可以利用数据挖掘技术进行风险分析，在保险公司建立的 保单及索赔信息数据库的基础上，寻找保单中风险较大的领域，从而得出一些实 用的控制风险的规则，以指导保险公司的工作。 ( 5 ) 制造业。制造业应用数据挖掘技术来进行零件故障诊断、资源优化和生 产过程分析等。 ( 6 ) 通信网络管理。在通信网络运行过程中可能产生一系列警告，哪些警告 可以不予理睬，哪些警告必须迅速处理，这往往很难判断，一般需要由人工根据 经验来进行处理，因此效率不高。数据挖掘则可以通过分析己有的警告信息的正 确处理方法以及警告之间的前后关系获得警告之间的关联规则。这些有价值的信 息可用于网络故障的定位检测和严重故障的预测。 2 4 粗糙集理论概述 2 4 1 粗糙集理论的发展 粗糙集理论是由波兰华沙理工大学p a w l a k 教授于2 0 世纪8 0 年代初提出的 一种研究不完整、不确定知识和数据的表达、学习、归纳的理论方法，其主要思 想是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。 粗糙集理论是一种处理含糊和不精确性问题的新型数学工具，比起模糊集，对于 当今现代计算机的应用来说，这种理论无疑是最具有挑战性的领域之一。它自问 世以来，无论是在理论或应用上都是一种新的、最重要的并且是迅速发展的研究 领域。对于人工智能和认知科学也是十分重要的，尤其在机器学习、知识获取、 决策分析、过程控制、模式识别与数据挖掘等方面的应用，粗糙集理论都为之提 供了一种有效的数学方法。当前许多国际重要学术会议和学术研讨班都把粗糙集 理论和研究作为会议和讨论班的主要内容之一。自粗糙集理论提出以来，大致从 两个方面研究了其理论及其应用。一方面是粗糙集的理论研究，有粗糙集代数、 粗糙集拓扑及其性质、粗糙逻辑及处理近似推理的逻辑工具等。另一方面，粗糙 集理论的研究者们也很重视逻辑研究，并发表了一系列的粗糙逻辑方面的文章。 1 2 2 4 2 粗糙集理论的特点 粗糙集理论主要优点之一在于它恰好反映了人们用粗糙集方法处理不分明 问题的常规性，即以不完全信息或知识去处理一些不分明现象的能力，或依据观 察、度量到的某些不精确的结果而进行分类数据的能力。粗糙集理论具有一些独 特的观点。这些观点使得粗糙集特别适合于数据分析。如：知识的粒度性。粗糙 集理论认为知识的粒度性是造成使用已有知识不能精确地表示某些概念的原因。 粗糙集理论引入不可区分关系作为基础，并在此基础上定义了上下近似等概念。 粗糙集理论能够有效地逼近这些概念。 采用粗糙集理论作为知识发现的工具具有许多优点： ( 1 ) 粗糙集不需要先验知识。模糊集和概率统计方法需要一些数据的附加信 息或先验信息，如模糊隶属函数和概率分布等，这些信息有时并不容易得到。粗 糙集无须任何先验知识，其分析方法仅利用数据本身提供的信息，只和已知数据 有关，从而避免了主观因素的影响。 ( 2 ) 粗糙集是一个强大的数据分析工具。它能表达和处理不完备信息；能在 保留关键信息的前提下对数据进行化简并求得知识的最小表达式；能识别并评估 数据之间的依赖关系，揭示出概念简单的模式；能从经验数据中获取易于证实的 规则知识，特别适于智能控制。 ( 3 ) 粗糙集以不可分辨关系为基础，侧重分类。粗糙集可以用一对清晰集合 逼近一个粗糙的论域。粗糙集和模糊集、证据理论有一些相互交叠之处，在实际 应用中可以相互补充。 2 4 3 应用 目前粗糙集理论已经在许多领域得到了成功应用，文献 4 1 介绍了粗糙集理 论在股票数据分析，模式识别，地震预报，冲突分析，知识发现，粗糙控制，医 疗诊断，专家系统，人工神经元网络，决策分析等中的具体应用。目前，关于粗 糙集理论的最新应用主要包括以下几个方面h 射： ( 1 ) 数据挖掘与规则生成 数据挖掘与规则生成是粗糙集理论在实际中最主要的应用。由于粗糙集理论 能够搜索数据的最小集合，可以使用定性与定量的数据并从数据中产生决策规则 集合等优点而在这方面得到了广泛的应用。介绍这方面应用的文章很多，主要包 括网络应用、管理科学领域的应用、医疗诊断等等。 ( 2 ) 决策评价 基于粗糙集理论的决策评价方法可以提高评价的客观性，也可以将复杂的、 模糊的、主观的推理评价过程转换为一连串客观的、量化的、程式化的问题求解 活动，实现科学的评价和正确的选择。利用粗糙集理论可以进行决策评价，以给 决策者提供正确的决策依据。 ( 3 ) 故障诊断 故障诊断是一个涉及到有效决策制定的复杂而困难的问题。基于粗糙集理论 的故障诊断方法很多，一些新的方法有积聚诊断知识和自我学习的能力。 ( 4 ) 模式识别 模式识别是粗糙集理论的一个主要应用方面，可以用于特征选择、特征表示、 分类和聚类。基于粗糙集方法的特征选择新技术可以避免信息丢失并解决数据集 的维度问题。 粗糙集对于人工智能和认知科学是十分重要的，它自提出以来一直得到模糊 数学的创始人z a d e h 的重视，并给予很高的评价，被列入他新提倡的软计算的 基础理论之一，粗糙集理论及其广泛应用越来越受到重视。 2 4 4 目前的研究热点 围绕着其逻辑特点和处理知识的基本原理，粗糙集理论目前的主要研究热点 有以下几个方面。 ( 1 ) 数学理论的系统化和形式化。尽管粗糙集理论产生于真正的数学基础， 但许多理论问题仍有待于真正澄清。对原始粗糙集模型的推广是粗糙集理论研究 的一个主流方向，目前主要有构造性方法和公理化方法； ( 2 ) 算法的研究。粗糙集理论中有效算法研究是粗糙集在智能学习中的一个 主要方向，目前，粗糙集理论中有效算法研究主要集中在导出的增量式算法、约 简算法、粗糙集基本并行算法以及与粗糙集有关的神经网络与遗传算法等。这些 研究有些已经有了成功的商业应用。 1 4 ( 3 ) 与其它软计算理论的联系。由于粗糙集理论在处理不确定性知识和模糊 知识上所具有的优势，将粗糙集理论与其它人工智能方法相结合能提高对数据处 理的能力：与模糊数学相结合能更好地处理不完全知识；与遗传算法相结合可以 降低优化的复杂度；与支持向量机结合进行数据预处理可提高预测精度；与神经 网络的结合可提高神经网络分类器的分类精度和分类能力。粗糙集理论与其它方 法的结合是其在数据挖掘中当前和今后研究的热点。 ( 4 ) 面向粗糙对象的专家系统和智能系统，以及粗糙集在工程技术方面的应 用。 2 5 粗糙集基本概念 本节内容来自参考文献 2 ，4 3 。 2 5 1 信息系统与决策表 定义2 1 一个信息系统( i n f o r m a t i o ns y s t e m ) 是一个四元组s = ( u ，么，y ，厂) ， 其中： u ：对象的非空有限集合，称为论域； a ：属性的非空有限集合； v = u 圪，圪是属性口的值域； 口e 以 f ：u 彳专v ，是一个信息函数，它为每个对象的每个属性赋予一个信息值，即 v a 么，x u ，f ( x ，g i ) 圪。 信息系统也称为知识表示系统，通常也用s = ( u ，彳) 来代替s = ( u ，彳，y ，f ) 。 定义2 2 设s = ( u ，彳，v ，f ) 是一个信息系统，彳= c u d ，c n d = a ，c 称 为条件属性集，d 称为决策属性集。具有条件属性和决策属性的信息系统称为决 策表。 2 5 2 近似空间 在信息系统中，对象由一组属性集表示。如果某些对象在考虑的属性集上取 值完全相同，则这些对象在这一组属性上不能相互区分。每一个属性子集尸彳 决定了一个一元不可区分关系，记为i n d ( p ) 。 定义2 3 令p 为u 上的二元关系，x ，y 均为u 中的任一对象，尸( x ) 为所 有与x 具有关系尸的y 的集合，若p 同时具有自反性、对称性和传递性时，p 被 称为是u 上的一种二元等价关系，也是一种不可区分关系。因此，令任一子集 尸彳，则不可区分关系表示为： i n d ( p ) = ( x ，y ) u u ：v a p ，f ( x ，口) = f ( y ，口) ) 。 不可区分关系( i n d i s c e r n i b i l i t yr e l a t i o n ) 的概念是粗糙集理论的基石， 它揭示出论域知识的颗粒状结构。 关系i n d ( p ) ，p 互a ，决定了u 的一个划分，我们用u i n d ( p ) 来表示。 u i n d ( p ) 中的任何元素称为一个等价类或信息粒度，用x i n d ( p ) 表示包含元 素x 的关系i n d ( p ) 的等价类。 对任意一个概念( 或集合) x ，当集合x 能表示成基本等价类组成的并集时， 称集合x 是可以精确定义的；否则，集合x 只能通过近似的方法来定义。 定义2 4 集合x 关于r 的下近似( l o w e ra p p r o x i m a t i o n ) 定义为： 一r x = u y u r i 】，x ) 。 定义2 5 由根据已有知识判断肯定属于x 的对象所组成的最大集合，称 为x 的正区域( p o s i t i v er e g i o n ) ，记作p o s r ( x ) = _ r x 。 定义2 6 集合x 关于足的上近似( u p p e ra p p r o x i m a t i o n ) 定义为： r x = u y u r i 】，n x g ) ，是由那些根据己有知识判断可能属于x 的对象所 组成的最小集合。 定义2 7 集合x 关于r 的边界区域( b o u n d a r yr e g i o n ) 定义为； b n r ( x ) = r x 一些。 如果6 ( x ) = a ，则称x 关于r 是精确的；反之，如果6 ( x ) a ，则称x 为关于尺的粗糙集。 定义2 8 由那些根据已有知识判断肯定不属于x 的对象所组成的集合，也 称为x 的负区域( n e g a t i v er e g i o n ) ，记作n e g r ( x ) = u 一肷。 显然，在粗糙集理论中，集合的不精确性是由于边界区域的存在而引起的。 集合的边界区域越大，其精确性则越低