（管理科学与工程专业论文）基于遗传算法的分类规则挖掘研究.pdf

摘要 数据挖掘是近年来兴起的一个新的研究领域。它涉及多学科技术的集成，包括 数据库和数据仓库技术、统计学、机器学习、人工智能等，目标是从大量的数据资 料中发现隐藏的有价值的信息和知识，以便为科学决策提供支持。分类规则挖掘则 是通过对训练样本数据集的学习，构造分类规则的过程，是数据挖掘、知识发现的 一个重要方面，其实质是希望得到准确性高、易于理解的和有趣的分类规则。 论文介绍了数据挖掘的基本理论以及遗传算法的基本原理，在此基础上，重点 研究了遗传算法在分类规则挖掘中的应用问题。为了克服简单遗传算法“早熟”收敛 的问题，引入了“非随机初始种群 和“均匀算子思想，提出基于非随机初始种 群遗传算法的分类规则挖掘算法，并利用乳腺癌和皮肤病数据集对其进行了算法测 试。根据实际应用的需要，用多目标遗传算法改进基本遗传算法在分类规则挖掘中 的应用，提出基于多目标遗传算法的分类规则挖掘算法，并利用a d u l t 数据集和z o o 数据集对其进行了算法测试。试验结果表明，所用算法能消除遗传算法在分类挖掘 任务中收敛于局部最优的局限性，且能快速挖掘出易于理解的分类规则，提高对知 识的理解力。 关键词：数据挖掘；遗传算法；分类规则；均匀算子；多目标遗传算法 a b s t r a c t d a t am i n i n gi san e wr e s e a r c hf i e l d r i s i n gi n r e c e n ty e a r s ，a n di n v o l v e sa l l i n t e g r a t i o no ft e c h n i q u e ss u c ha sd a t a b a s ea n dw a r e h o u s et e c h n o l o g y , s t a t i s t i c s ，m a c h i n e l e a r n i n g ，a r t i f i c i a li n t e l l i g e n c ee t c i t sg o a l i st od i s c o v e rv a l u a b l ei n f o r m a t i o na n d k n o w l e d g eh i d d e nb e h i n dd a t af r o mn u m e r o u sd a t a i no r d e rf o rp r o v i d i n gd e c i s i o n s u p p o r t m i n i n gc l a s s i f i c a t i o n r u l e si sap r o c e d u r et oc o n s t r u c tac l a s s i f i e rt h r o u g h s t u d y i n gt r a i n i n gd a t a s e t ，a n di sav e r yi m p o r t a n tp a r to fd a t am i n i n ga n dk n o w l e d g e d i s c o v e r y i ne s s e n c e ，i t sg o a l i st od i s c o v e rc l a s s i f i c a t i o nr u l e sw h i c ha r eh i g h l y p r e d i c t i v ea c c u r a t e ，c o m p r e h e n s i b l ea n di n t e r e s t i n g i nt h i sp a p e r , w eg i v ea ni n t r o d u c t i o nt ot h eb a s i ct h e o r i e so fd a t am i n i n ga n dg e n e t i c a l g o r i t h m t h e n ，w el a ye m p h a s i so ns t u d y i n gt h ea p p l i c a t i o no fg e n e t i ca l g o r i t h mi n c l a s s i f i c a t i o nr u l em i n i n g i no r d e rt oo v e r c o m et h ep r e m a t u r ep h e n o m e n a ，b a s e do nt h e s g a , t h i st h e s i si n t r o d u c e st h ei d e ao f ”n o n r a n d o mi n i t i a lp o p u l a t i o n ”a n d ”u n i f o r m o p e r a t o ri f , a n dp u t sf o r w a r d sm i n i n gc l a s s i f i c a t i o nr u l e sb a s e do ng e n e t i ca l g o r i t h m s w i t hn o n r a n d o mi n i t i a l p o p u l a t i o n ，a n da p p l i e s t h en e wa l g o r i t h mi n t o m i n i n g c l a s s i f i c a t i o nr u l e so nb r e a s tc a n c e rd a t aa n dd e r m a t o l o g yd a t a a tt h es a m et i m e ，t h i s t h e s i si m p r o v e ss i m p l eg e n e t i ca l g o r i t h mb ym u l t i - o b j e c t i v eg e n e t i ca l g o r i t h mb a s e do n r e a l i s t i cd e m a n d ，p r o p o s e sc l a s s i f i c a t i o nr u l em i n i n gb a s e do nm u l t i - o b j e c t i v eg e n e t i c a l g o r i t h ma n dt e s t s t h e a l g o r i t h mo na d u l td a t a b a s e a n dz o od a t a b a s e f r o mt h e e x p e r i m e n t a lr e s u l t s ，i tw a so b s e r v e dt h a t ，t h e s em e t h o d sc a ng u a r a n t e et og e tr i do fa n y l o c a ls o l u t i o nw h e nh a n d l e dt h ep r o b l e m so fg a si nt h et a s ko fc l a s s i f i c a t i o n i tc a na l s o m o s t l yi m p r o v e t h ec o m p r e h e n s i b i l i t yo ft h ed i s c o v e r e dk n o w l e d g e k e yw o r d s ：d a t am i n i n g ；g e n e t i ca l g o r i t h m ；c l a s s i f i c a t i o nr u l e s ；u n i f o r m o p e r a t o r ；m u l t i o b j e c t i v eg e n e t i ca l g o r i t h m 青岛大学硕士学位论文 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人己用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：下i 钐驴 日期： 年6 月，歹日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密 ( 请在以上方框内打“”) 论文作者签名： 弘钐形 铷一晚 ( 本声明的版权归青岛大学所有， 日期：砷6 月，夕日 同期：乃妒年月厶阳 未经许可，任何单位及任何个人不得擅自使用) 第一章绪论 1 1 课题背景 第一章绪论 近年来，随着数据库技术和计算机网络的广泛应用和发展，人类使用先进的自 动数据生成和采集工具，拥有的数据量急剧增大。在这些大量的数据背后隐藏着许 多重要的信息，不同领域的人们都期待着从这些数据中得到自己想要的答案，将信 息变为有用的知识，从杂乱无章的数据“矿山”中找到蕴藏的知识“金块”。但是，传 统的方法很难对数据进行深层次的分析和处理，它不仅费时费力，而且效果往往很 难令人满意。因此，出现了一门新的技术：数据挖掘技术1 1 】。数据挖掘( d a t am i n i n g ) 是计算机科学中的一个重要研究领域，其目标是从数据中抽取知识1 2 j 。目前，该技术 被越来越多的领域所采用并取得了一定的成效，达到了在一定程度上为人们的正确 决策提供辅助的目的。 分类规则是数据挖掘的主要研究内容之一，通过分析训练集数据，产生关于类别 的精确描述1 3 1 。这种类别描述常由分类规则组成，可以用来对未来的数据进行分类预 测，有着广泛的应用前景。实际上，分类是一个两步的过程。第一步，通过分析训练 集建立一个模型，描述指定的数据类集或概念集；第二步，评估模型的预测准确率， 如果模型的准确率可以接受，就可以使用模型进行分类了。对于分类规则的挖掘， 目前主要有以下方法：决策树方法、贝叶斯方法、人工神经网络方法、遗传算法以及 粗糙集方法等，不同的算法适合于不同特征的数据集。 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 是模仿自然界生物遗传进化过程中“物竞天 泽、适者生存”原理的一种全局优化随机搜索算法，是由美国j h o l l a n d 教授于1 9 7 5 年在其论文“自然系统和人工系统的适配”中提出的、具有应用广泛、使用简单、鲁 棒性强等特点的方法【4 】【5 1 。它借用了生物遗传学的观点，通过自然选择、交叉、变异 等遗传操作，一代代不断繁殖进化，最后收敛到一批最适应环境的个体上，从而求得最 优分类规则剿6 。但是，传统遗传算法存在着易于陷入局部最优而达不到全局最优， 致使得到的分类规则概括性不强的问题。 为了提高分类规则挖掘效率、准确性和易理解性，许多研究人员将简单遗传算 法运用到分类规则挖掘中去，并取得了一些成果。但是，总存在“早熟”收敛和局部 最优等问题。本论文提出的基于非随机初始种群遗传算法的分类规则挖掘算法能够 有效地解决上述问题，提高分类规则挖掘的效率和准确性。 1 2 研究现状 分类挖掘有多种方法，常用的有决策树归纳分类、贝叶斯分类、神经网络分类、 1 青岛大学硕士学位论文 基于遗传算法的分类、粗糙集方法分类和模糊集方法分类等。 决策树( d e c i s i o nt r e e ) 归纳是从具有类标号的训练元组学习决策树。决策树是一 种类似于流程图的树结构，其中，每个内部节点表示在一个属性上的测试，每个分 支代表一个测试输出，而每个叶节点存放一个类标号，树的最顶层节点为根节点。 有些决策树算法只能产生二叉树，而另外一些决策树算法可以产生非二叉树。在2 0 世纪7 0 年代后期和8 0 年代初期，机器学习研究者j r o s sq u i n l a n 开发了决策树算法， 称作i d 3 ( i t e r a t i v ed i c h o t o m i s c r ，迭代的二分器) 。这项工作扩展了e b h u n t ，j m a r i n 和p t s t o n c 的概念学习系统。1 9 8 4 年几位统计学家( lb r c i m a n ，j f r i e d m a n ，r o l s h e n 和c s t o n e ) 出版了分类与回归树一书( c a r t , c l a s s f i c a t i o na n dr e g r e s s i o nt r e e s ) ，介绍 了二叉决策树的产生。i d 3 和c a r t 大约同时分别发明，但是从训练元组学习决策 树却采用了类似的方法。这两个基础算法激发了决策树归纳研究的热潮。1 9 9 3 年 j r o s sq u i n l a n 又提出了作为i d 3 后继的c 4 5 。c 4 5 不仅能处理离散值属性同时能 处理连续值属性，成为了新的监督学习算法的性能比较基准。至此，决策树归纳算 法已经发展得相对比较成熟【7 】【8 j 。 后来又出现了i d 3 算法的增量版本，包括i d 4 算法和i d 5 算法。但这此算法对 于相对小的数据集上是有效的，对于现实中数据量很大的数据进行挖掘时，有效性 和伸缩性就成了关注的问题。为此有人提出了一些新的决策树算法，如s l i q 算、法i 引。 其在决策树的构造过程中采用了预排序与广度优先增长策略。使得该算法能够处理 更大的训练集，因此在一定程度上具有良好的随记录个数和属性个数增长的可扩展 性。但是它仍然存在着一些不足：由于需要将类别列表存放于内存，在一定程度 上限制了可以处理的数据集的大小：由于采用了预排序技术，而排序算法的复杂 度本身并不是与记录个数成线性关系。因此使得s l i q 算法不可能达到随记录数目 增长的线性可扩展性。除此之外，为了减少驻留于内存的数据量，还有人提出过 s p r i n t 算法【1 0 】，其优点是在寻找每个结点的最优分裂标准时变得更简单，其缺点 是对非分裂属性的属性列表进行分裂时变得很困难。 为什么决策树分类器如此流行，因为决策树的构造不需要任何领域知识或参数 设置，适合于探测式知识发现，同时决策树可以处理高维数据且获取的知识用树的 形式表示是直观的，容易为人们所理解。决策树分类采用的是贪心算法，以自顶向 下的分治方式构造，大多数决策树归纳算法都沿用了这种自顶向下方法，从训练元 组集和它们相关的类标号开始，随着树的构建，训练集递归地划分成较小的子集。 这样不断循环下去，直至达到特定的终止条件。 贝叶斯分类法( b a y e s i a nc l a s s i f i e r s ) 是统计学分类方法的一种，可以预测类成员 关系的概率，如给定元组属于一个特定类的概率。贝叶斯分类基于贝叶斯定理( b a y e s t h e o r e m ) ，它是一种可以把类的先验知识和从数据中收集的新证据相结合的统计原 2 第一章绪论 理。朴素贝叶斯分类法与决策树和神经网络分类法的各种比较试验表明，在某些领 域，朴素贝叶斯分类法足以与他们相媲美。理论上讲，与其他所有分类算法相比， 贝叶斯分类具有最小的错误率。然而，实践中并非总是如此。这是由于现实中贝叶 斯分类所使用的假定( 类的条件独立性) 的不正确性，以及缺乏可用的概率数据造成 的。贝叶斯分类法还可以用来为不直接使用贝叶斯定理的其他分类法提供理论判定。 例如，在某些假定下，可以证明，与朴素贝叶斯分类法一样，许多神经网络和曲线 拟合算法输出最大的后验假定。 神经网络方法试图模拟人脑神经元结构，是以m p f 由美国m ec u l l o c h 和p i t t s 提出的最早神经元模型之一) 和h e b b 学习规则为基础的分类方法。神经网络是一组 连接的输入输入单元，其中每个连接都与一个权重相关联。在学习阶段，通过调整 这些权重，能够预测输入元组的正确类标号。由于单元之间的连接，神经网络学习 又称连接者学习( c o n n e c t i o n l i s tl e a r n i n g ) 。神经网路需要很长的训练时间，需要确定 大量的参数( 如网络拓扑结构) 。同时，神经网络常常因其可解释性差而受到批评， 人们难以从训练过的网络中抽取规则【1 ，很难解释网络中学习的权重和“隐藏单元” 的符号含义。对于数据挖掘，这些特点使得神经网络最初的使用并不理想。然而， 神经网络的优点包括其对噪声数据的高承受能力，以及对未经训练的数据模式的分 类能力。在缺乏属性与类之间的联系知识时可以使用神经网络算法。此外，神经网 络算法是固有并行的，方便使用并行技术来加快计算过程。最近已经开发了一些从 训练过的神经网络提取规则的技术，这些因素推动了神经网络在数据挖掘分类和预 测方面的应用。当前有许多不同类型的神经网络算法，最流行的神经网络算法是后 向传播。 遗传算法试图利用自然进化的思想。一般，遗传学习开始如下：创建由随机产 生的规则组成的初始群体，每个规则用一个二进位串表示。然后，根据适者生存的 原则，通过选择、交叉、变异等操作，形成由当前群体中的最优规则以及这些规则 的后代组成的新的群体。通常情况下，规则的适应度用它在训练样本集的分类准确 率评估。接着，由先前的规则群体再产生新的规则群体，这样循环下去，直到群体 p 中每个规则都满足预先指定的适应度阈值或者达到指定的进化代数算法终止。遗 传算法易于并行，且具有很好的鲁棒性。在数据挖掘中，还可以用来评估其他算法 的适应度。 粗糙集理论也可以用于分类，发现不准确数据或噪声数据的结构联系。它用于 离散值属性。因此，连续值属性必须在使用前离散化。 模糊集理论也称可能性理论( p o s s i b i l i t yt h e o r y ) 。它是l o t f iz a d e h 于1 9 6 5 年提出 的，作为传统的二值逻辑和概率论的一种替代，它允许我们处理高层抽象的数据， 并且提供了一种处理数据的不精确测量的手段。对于基于规则的分类数据挖掘系统 3 青岛大学硕+ 学位论文 来说，模糊集理论非常有用。它提供了结合模糊度量的操作。当前，模糊逻辑系统 已用于许多分类领域，包括市场调查、财经、环境工程等。 此外，近年来又出现了一些新的用于数据挖掘的分类算法。c b a ( c l a s s i f i c a t i o n b 弱c do na s s o c i a t i o n ) 是基于关联规则的分类算法，该算法分两个步骤构造分类器1 1 2 1 。 发现所有形如墨，ax ；，jc 的关联规则，即右部为类别属性值的类别关联规则。 从己发现的c a r 中选择高优先度的规则来覆盖训练集，也就是说，如果有多条关 联规则的左部相同，而右部为不同的类，则选择具有最高置信度的规则作为可能规 则。c b a 算法的优点是其分类准确度较高，在许多数据集上比决策树更精确，但是 上述两步都具有线性可伸缩性。此外，u u ，h s u 和m a 提出关联分类法和使用显露模 式分类的c r e p 算法1 1 3 l ，使用跳跃显露模式的j e p 算、法1 1 4 l 。 这些分类挖掘算法都有各自的优缺点，没有任何一种分类方法对于所有数据类 型和领域都优于其他方法【1 5 l 。例如，决策树方法对噪声的容错性能较差；另外找到 最佳的决策树是n p 难题；贝叶斯分类中要求的类的条件独立性在现实中难以满足； 神经网络方法对训练数据中的噪声非常敏感，同时训练神经网络是一个很耗时的过 程，特别是隐藏节点数量很大时；遗传算法在把现实分类问题转化为遗传群体的迭 代过程时常会遇到麻烦。尽管神经网络方法和遗传算法都存在着一些缺点，由于神 经网络较强的容错性和遗传算法快速高效的全局搜索能力，使得这两种方法备受关 注，研究也越来越多。 1 3 主要研究内容及研究方法 1 3 1 研究内容 通过大量搜集和阅读国内外相关文献资料，理解数据挖掘的产生、发展、概念、 特点、任务模式和应用，掌握数据挖掘技术的应用步骤。讨论了使用遗传算法进行 数据挖掘的基本思想和关键要解决的问题，为克服简单遗传算法关于“早熟”收敛和 局部最优的缺陷，提出了一种基于非随机初始种群遗传算法的分类规则挖掘算法和 一种基于多目标遗传算法的分类规则挖掘算法，并结合具体的实例给出了分类规则 的提取算法。试验表明本文给出的算法是可行的和有效的，既可提高算法的收敛速 度，又能抑制“早熟”收敛现象的发生。 具体说来，本论文主要做了如下研究： ( 1 ) 基于非随机初始种群的遗传算法分类规则挖掘 在前面分析的基础上，为了防止“早熟”现象的发生，提出了一种基于非随机初 始种群的遗传算法分类规则挖掘算法。利用均匀种群方法生成非随机的初始种群，通 过均匀算子确保连续迭代过程中种群的多样性并防止遗传算法的早熟，挖掘易于理 一一 4 第一章绪论 解的分类规则，提高规则的简单性和对知识的理解力。 ( 2 ) 基于多目标遗传算法的分类规则挖掘 首先介绍了引入多目标遗传算法的背景及该算法内容，在此基础上提出了改进。 之后，利用实验数据集对该改进算法进行了测试。 1 3 2 研究方法 采用比较高效的启发式算法遗传算法作为文章的研究方法。具体步骤包 括：问题描述、算法设计、仿真试验、结果分析。选择m a t l a b 作为仿真试验和结果 分析的工具。 1 3 3 论文结构 本文共分六章。 第一章绪论，主要论述了本文研究工作的背景和本文研究的主要内容。 第二章数据挖掘与分类规则挖掘概述。对数据挖掘的基本知识进行了阐述，主 要包括数据挖掘的产生和发展、数据挖掘的概念、过程、特点、分类和任务模式。 重点探讨了分类规则挖掘的步骤。 第三章遗传算法基本原理及其应用。对简单遗传算法s g a ( s i m p l eg e n e t i c a l g o r i t h m ) 进行了阐述，包括遗传算法的生物由来、特点、理论基础、简单遗传算法 的基本算法流程、三大遗传算子和四大关键问题。之后，就面向数据挖掘的遗传算 法存在的问题做了分析，并详细讨论了“早熟”收敛现象发生的原因和一般解决方法。 第四章基于非随机初始种群的遗传算法分类规则挖掘。为防止“早熟”现象，提 出了基于非随机初始种群的遗传算法并应用于分类规则挖掘中。 第五章基于多目标遗传算法的分类规则挖掘。改善了遗传算法应用于分类规则 挖掘的实际效率。 第六章结论与展望。总结了全文，并提出了将来的进一步工作。 5 青岛大学硕士学位论文 第二章数据挖掘与分类规则挖掘 我们产生和收集数据的能力正在迅速提高，我们被数据科学数据、医疗数 据、人口统计数据、金融数据、和销售数据所淹没。我们必须找到有效的方法， 能自动地分析数据、自动地对数据分类、自动地对数据汇总、自动地发现和描述数 据中的趋势，这正是数据挖掘技术产生的现实需要。数据挖掘技术能够以智能的方 式将海量的数据转换成有用的信息和知识。 2 1 数据挖掘的历史与发展 数据挖掘( d a t am i n i n g ，简称为d m ) - - 诟- 是在1 9 8 9 年8 月于美国底特律市召开 的第十一届国际联合人工智能学术会议上正式提出的【1 6 j 。其目的是从数据库中发现 不为人们所知的隐藏知识和有用的信息。随后，该学科引起了国际人工智能和数据 库等领域专家的广泛关注。1 9 9 5 年，第一届知识发现k d d ( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，数据库知识发现、) 和数据挖掘国际学术会议在加拿大蒙特利尔召开【r 刀。此 后，k d d 国际学术会议每年举办一次，将k d d 和d m 方面的研究推向了高潮。和 国外相比，国内对数据挖掘研究起步较晚。1 9 9 3 年，国家自然科学基金首次支持该 领域的研究项目1 1 8 】。目前，国内很多的科研机构、研究所和高校等都竞相开展数据 挖掘的基础理论及其应用研究。 进入2 l 世纪后，数据挖掘技术向纵深发展，与多种学科交叉、多种技术结合的 数据挖掘理论及技术开始涌现，并行计算、计算机网络和信息工程等其它领域的国 际学会、期刊把数据挖掘和知识发现列为专题和专刊讨论。在g a r t n e rg r o u p 的一次 高级技术调查将数据挖掘和人工智能列为“未来三到五年内将对工业产生深远影响 的五大关键技术”之首，并且还将并行处理体系和数据挖掘列为未来五年内投资焦点 的十大新兴技术前两位。根据g a r t n e r 的h p c 研究表明，随着数据捕获、传输和存 储技术的快速发展，大型系统用户将更多地需要采用新技术来挖掘市场以外的价值， 采用更为广阔的并行处理系统来创建新的商业增长点。今后对数据挖掘研究的焦点 将会集中在以下几个方面： ( 1 ) 改进传统的数据挖掘方法，提高数据挖掘算法的有效性、可伸缩性和并行处 理。 ( 2 ) 并行、分布和增量挖掘算法以及知识的更新维护。 ( 3 ) 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户理解，也 便于在知识发现的过程中进行人机交互。 ( 4 ) 研究在网络环境下的数据挖掘技术，特别是在互联网上建立d m k d 服务器， 并且与数据库服务器配合，实现w 曲m i n i n g 。 6 第二章数据挖掘与分类规则挖掘 ( 5 ) 加强对各种非结构化数据的开采，如对文本数据、图形数据、视频图像数据、 声音数据乃至综合多媒体数据的挖掘开采。 ( 6 ) 数据挖掘语言的形式化描述，即研究专门用于知识发现的数据挖掘语言，也 许会像s o l 语言一样走向形式化和标准化。 ( 7 ) 复杂工程过程中的数据挖掘。 2 2 数据挖掘的基本知识 2 2 1 数据挖掘的概念 数据挖掘的发展历史虽然较短，但从2 0 世纪9 0 年代以来，它的发展速度很快， 加之它是多学科综合的产物，目前还没有一个完整的定义，人们提出了多重数据挖 掘的定义【1 9 】，如s a s 研究生( 1 9 9 7 ) ：“在大量相关数据基础上进行数据探索和建立相 关模型的先进方法”；b h a v a n i ( 1 9 9 9 ) ：“使用模式识别技术、统计和数学技术，在大 量的数据中发现有意义的新关系、模式和趋势的过程”；h a n de ta l ( 2 0 0 0 ) ：“数据挖 掘就是在大型数据库中寻找有意义、有价值信息的过程”。 当前，广泛接受的数据挖掘定义为：数据挖掘就是从大量的、不完全的、有噪 声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们预先不知道的、 但又是潜在有用的信息和知识的过程【1 9 】。数据挖掘要解决的问题就是在庞大的数据 库中寻找有价值的隐藏信息，加以分析，并将这些有意义的信息归纳成结构模式， 提供给有关部门在进行决策时参考。 其含义有： ( 1 ) 数据源必须是真实的、大量的、含噪声的； ( 2 ) 发现的知识是用户感兴趣的、易于被理解的，最好能用自然语言表达发现的 结果； ( 3 ) 这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发 现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际上，所有发 现的知识都是相对的，是有特定前提和约束条件，面向特定领域的。规则的发现主 要基于大量样本的统计规律，发现的规则不必满足所有数据，只要该规律能达到某一 限定值便可认为有此规律。 2 2 2 数据挖掘基本过程 数据挖掘( 或知识发现) 的基本过程如图2 1 所示。大致分为五步： ( 1 ) 定义所要挖掘的问题 ( 2 ) 挖掘前的数据准备 7 青岛大学硕士学位论文 ( 3 ) 数据挖掘 ( 4 ) 模式的解释评估 ( 5 ) 挖出的知识的应用 ( 1 ) 定义所要挖掘的问题 必须清晰地定义出业务问题，明确数据挖掘的目的。 ( 2 ) 挖掘前的数据准备 选择数据( d a t as e l e c t i o n ) - - - 在目标大型数据库或数据仓库中提取数据挖掘的目标 数据集； 数据预处理( d a t ap r e p r o c e s s i n 酚现实世界中的数据库极易受噪声数据、空缺数 据和不一致性数据的侵扰，为了提高数据挖掘模式的质量，降低实际挖掘所需要的 时间和成本，在数据挖掘之前采用数据预处理技术对数据进行预处理是极其必要的 1 2 0 1 2 1 1 。通常，这一过程主要包括以下3 个步骤：数据清理、属性选择和数据变换。 数据清理：是旨在消除和减少数据噪声( 使用光滑技术) 和处理空缺值( 用该属 性最常出现的值，或据统计，用最可能的值来替换空缺值) 。该步骤有助于减少学习 时的混乱。 相关分析：数据中的许多属性可能是冗余的，可以使用相关分析来识别任意 两个给定的属性是否是统计相关的。此外，数据库中还可能包含不相关的属性，在 这种情况下，可是使用属性子集选择找出属性的归约子集，使得数据类的结果概率 分布与使用所有属性得到的原分布尽可能接近。同时也减少了出现在发现模式上属 性的数目，使得模式更易于理解。 数据变换：数据变换的目的是将数据转换成适合当前任务挖掘的形式，例如， 8 第二章数据挖掘与分类规则挖掘 可以通过规范化对数据进行变换，也可以通过对数据泛化到较高层概念进行变换， 或是把连续值型( 离散型) 属性的数据转换成离散型( 连续值型) 属性的数据等。 ( 3 ) 数据挖掘 数据挖掘阶段首先要确定挖掘的任务或目的是什么。确定了挖掘任务以后，下 一步要决定使用什么样的挖掘算法。同一个任务可以用不同的算法来实现，选择实 现算法时必须考虑两个重要因素：一是不同的数据有不同特点，因此需要与之相关的 算法来开采；二是用户或实际运行系统的潜在要求。 ( 4 ) 模式的解释评价 在数据挖掘阶段得到发现的模式之后，要对结果进行解释和评价。把发现的模 式转换成为用户满意的、易懂的、无冗余的模式。如果模式不满足用户要求，则需 要将整个发现过程退回到发现阶段之前，如对数据重新选取、采用新的数据预处理 方法、设定新的数据挖掘参数值，甚至换另外一种挖掘算法。用户通常想得到形式 简单的、准确的、易理解的和有趣的知识和信息。这是一个多目标的优化求解问题， 现实中我们常将其转换为单目标问题来求解。实际上，解决仅提供给用户其感兴趣 的知识就是当前数据挖掘面临的一个难题，关于规则有趣性度量的一些客观的评价 标准可参看文献【2 2 】【2 3 】。 ( 5 ) 知识的运用 将分析所得到的知识集成或融合到业务信息系统中去，发挥这部分知识的作用。 2 2 3 数据挖掘的对象 数据挖掘是从现实中的海量数据源中发现知识，数据挖掘的对象可以根据数据 源的种类相应的分为以下几种主要形式： ( 1 ) 对象关系数据库 对象关系数据库基于对象关系数据模型构造。这种模型通过提供处理复杂对 象的丰富数据类型和对象定位，扩充关系模型。因为大部分复杂的数据库应用需要 处理复杂的对象和结构，对象关系数据库在业界和应用中日趋流行。 ( 2 ) 时间数据库、序列数据库、空间数据库 时间数据库( t e m p o r a ld a t a b a s e ) 通常存放包含时间相关属性的关系数据。这些属 性可能涉及若干时间标签，每个都具有不同的语义。序列数据库( s e q u e n c ed a t a b a s e ) 存放具有或不具有时间概念的有序事件的序列。如顾客购物序列、w e b 点击流和生 物学序列。空间数据库( s p a t i a ld a t a b a s e ) 包含涉及空间的信息。例子包括地理数据库、 计算机辅助设计数据库以及医疗和卫星图像数据库。 ( 3 ) 文本数据库和多媒体数据库 文本数据库是包含对象的词描述的数据库。通常，这种词描述不是简单的关键 9 青岛大学硕士学位论文 词，而是长句或短文，如产品介绍、故障报告、警告信息、笔记或其他文档。多媒 体数据库存放图像、音频和视频数据。应用于基于内容的图片检索、声音传递系统、 视频点播系统、万维网和识别口语命令的基于语音的用户界面等方面。 ( 4 ) 数据流 数据流是指数据动态地从观测平台或窗口流进和流出。这种数据流具有如下独 特的性质：海量甚至可能无限，动态变化，以固定的次序流进和流出，只允许一遍 或少数几遍扫描，要求快速甚至是实时的响应时间。数据流的典型例子包括各种类 型的科学和工程数据，时间序列数据和产生于其他动态环境下的数据，如电力供应、 网络通信、股票交易、w e b 点击流、视频监视和气象或环境监控数据。 ( 5 ) 万维网 万维网和与之关联的分布式信息服务提供了丰富的、世界范围的联机信息服务， 其中数据对象链接在一起便于交互访问。用户通过链接，从一个对象到另一个对象， 寻找感兴趣的信息。这种系统对数据挖掘提供了大量机会和挑战。在这种分布式信 息环境下，捕获用户访问模式称作w e b 日志挖掘。 2 2 4 数据挖掘的分类 数据挖掘系统可根据所挖掘的数据库类型、所挖掘的知识类型、所使用的技术 或应用加以分类【1 0 l 。 ( 1 ) 根据挖掘的数据库类型分类 数据库系统本身可以根据不同的标准( 如数据模型、数据类型或所涉及的应用) 分类，每一类可能需要自己的数据挖掘技术。这样数据挖掘系统就可以相应分类。 例如，根据数据模型分类，可以有关系的、事务的、对象关系的或数据仓库的挖掘 系统。如果根据所处理数据的特点类型分类，可以有空间的、时间序列的、文本的、 数据流的、多媒体的数据挖掘系统，或力维网挖掘系统。 ( 2 ) 根据发现知识的种类分类 根据挖掘的知识类型可分为关联规则、特征规则、分类规则、偏差规则、聚类 规则、判别式规则及时序规则等。 ( 3 ) 根据采用的技术类型分类 根据挖掘方法分为人工神经网络、决策树、贝叶斯方法、遗传算法、最近邻技 术、规则归纳、可视化等。 ( 4 ) 根据挖掘应用分类 数据挖掘系统也可以根据其具体应用分类。例如，可能有些数据挖掘系统特别 适合金融、电信、d n a 、股票市场、e m a i l 等。泛化的全能的数据挖掘系统可能并 不适合这些特定领域的挖掘任务。 1 0 第二章数据挖掘与分类规则挖掘 2 3 分类数据挖掘 2 3 1 分类数据挖掘概述 分类是根据数据集的特点构造一个分类器，利用分类器对未知类别的样本赋予 类别的一种技术。分类可以分为设计和实现两个阶段【冽。设计就是用一定数量的样 本( 亦称训练集或学习集) 进行分类器的设计；实现是指用所设计的分类器对待识别 的样本进行分类决策。而设计阶段又分为训练和测试两个步骤【12 1 。在训练这一步中， 分析训练数据集的特点，为每个类别产生一个相对应的模型；在测试这一步中，利 用类别的模型对测试样本集进行分类，评估其分类准确率。 一般而言，分类器构造过程中最重要的是训练阶段，因为测试代价远远低于训 练代价。通常，模型可以用分类规则、判定树、数学公式或神经网络来表示。在这 几种常用方法中，使用分类规则表示o f t h e n 规则形式) 具有相对优势：每条规则能 够相互独立地表示所发现的知识；新规则的加入并不影响已存在的规则集，而且易 于理解。 2 3 2 分类数据挖掘步骤 数据分类是一个两步过程： 第一步，建立一个描述预先定义的数据类或概念集的分类器。这是学习步或者 说训练阶段，其中分类算法通过分析或从训练集“学习”来构造分类器。训练集由数 据库元组和它们的相关联的类标号组成。元组x 用i i 维属性向量x = ( x 1 , x 2 ，x n ) 表 示，分别描述元组在n 个数据库属性a 1 ，a 2 ，上的n 个度量。假定每个元组 x 都属于一个预先定义的类，由称作类标号属性( c l a s sl a b e la t t r i b u t e ) 的数据库属性确 定。由于提供了每个训练元组的类标号，这一步也称作监督学( s u p e r v i s e dl e a r n i n g ) ， 即分类器的学习是在被告知每个训练元组属于那个特定类的“监督”下进行的。 第二步，使用模型进行分类。首先评估分类器的预测准确率。如果我们使用训 练集来测量分类器的准确率，则评估很可能是乐观的，因为分类器趋向于过分拟合 该数据集( 在学习期间，它可能并入了训练数据中的某些特殊的异常点，这些异常不 在一般的数据集中出现) 。因此，需要使用独立于训练集的检验集来验证分类器的准 确率。如果认为分类器的准确率可以接受，就可以用它对类标号未知的未来数据元 组进行分类。 通常，实例测试中常使用保持方法。保持( h o l d o u t ) 方法是一种简单的较为直接 的估计分类规则准确率的方法。在保持方法中，将给定数据集随机地划分成两个不 想交的集合：训练集和检验集。训练集和检验集的划分比例通常根据分析者的判断( 例 如，各占5 0 ，或者三分之二作为训练集、三分之一作为检验集) 。使用训练集导出 】1 青岛大学硕士学位论文 分类法，然后其准确率用测试集评估。评估可采用适应度函数分别在训练集和检验 集上得到的适应度值来进行。分类规则在训练集和测试集中的适应度值越接近，则 说明分类的精度相对越高。其它的分类器准确率度量常用方法还有k 折交叉确认 ( k f o l dc r o s s - v a l i d a t i o n ) 和自助法( b o o t s t r a pm e t h o d ) 。 例如，通过分析某商店顾客的购买记录得到分类规则，预测什么属性的顾客购 买电脑的可能性比较大。如图2 2 所示。特征属性a g e 的取值域为 y o u t h ，m i d d l e _ a g e d ， s e n i o r ，i n c o m e 的取值域为 l o w , m e d i u m ，h i g h ，s t u d e n t 的取值域为 y e s ，n o ， c r e d i t _ r a t i n g 的取值域为 f a i r , e x c e l l e n t 类别属性为b u y s _ c o m p u t e r 的取值域为 y e s ， n o 。 c l a s s ： r l a g e i n c o m es t u d e n tc r e d i tr a t i b u y s _ c o d n gm p u t e r 1 y o u t hh i 曲 n oe x c e l l e n tn 0训 2 m i d d l e _ a g e dh i g l l n 0f a i f y e s 练 3s e n l o rm e d i u mn of a i r y e s 集 4s e n l o fl o w y e s f a i r y e s i fa g e ( = y o u t h ) a n di n c o m e ( = h i g h ) a n ds t u d e n t ( = n o ) a n dc r e d i t _ r a t i n g ( = e x c e l l e n t ) t h e nb u y s _ c o m p u t e r ( = y e s ) a ) 学习：在训练集上使用分类算法，得到分类规则 由分类算法得 到分类规则 测试数据 c l a s s ： r i a g e i n c o m es t u d e n t c r e d i t _ r a t i n gb u y s _ c o d m p u t e r 测 5 0 0s e n l o rl o w y e s e x c e l l e n tn o试 5 0 1 m i d d l e _ a g e d l o w y e s e x c e l l e n t y e s 集 5 0 2 y o u t h m e d i u mn 0f a i rn o 5 0 3 y o u t h l o w y e s f a i r y e s b ) 分类：在测试数据上评估分类规则的准确率，如果准确率可以接受，则分类规则可 以应用于分类新的数据元组 图2 2 分类挖掘示例图 1 2 第三章遗传算法的基本原理及其应用 第三章遗传算法的基本原理及其应用 生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其 启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统 的设计和开发提供了广阔的前景。遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 就是这种 生物行为的计算机模拟中令人瞩目的重要成果。遗传算法是美国m i c h i g a n 大学的 h o l l a n d 2 5 】教授等于2 0 世纪7 0 年代创立的。遗传算法的基本思想是基于达尔文进化 论和孟德尔的遗传学说，是一类借鉴生物界自然选择和自然遗传机制的随机搜索算 法。通过仿效生物的进化与遗传，根据“生存竞争”和“优胜劣汰”的原则，借助选择、 交叉、变异等操作，使所要解决的问题从随机初始解一步步逼近最优解。 3 1 遗传算法概述 3 1 1 遗传算法的产生及发展 遗传算法起源于对生物系统所进行的计算机模拟研究。早在上世纪4 0 年代，就 有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了 生物的进化过程模拟、遗传过程模拟等研究工作。进入6 0 年代后，美国密执安大学 的h o l l a n d 教授及其学生们受到这种生物模拟技术的启发，创造出了一种基于生物 遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术一遗传算法。下 面是在遗传算法的发展进程中一些关键人物所做出的一些主要贡献。 2 0 世纪6 0 年代，h o l l a n d 认识到了生物的遗传和自然进化现象与人工自适应系 统的相似关系，提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制， 以群体的方法进行自适应搜