（信号与信息处理专业论文）神经网络在数据挖掘中的应用.pdf

神经网络在数据挖掘中的应用 摘要 本文首先介绍数据挖掘的研究背景、定义、数据挖掘的过程及任务，然后对 数据挖掘的常用技术进行了较为详细的讨论。在此基础上，对神经网络在数据挖 掘中的应用进行了深入的研究。 神经网络用于数据挖掘的两个主要问题是训练时间过长和获得的知。纵难以 理解和表示。通过采用收敛速度快的训练算法及规则抽取算法可以克服这两个 问题。因此本文对常用的b p 神经网络的各种快速训练算法进行了详细的分析， 并对已有的各种规则抽取算法进行了介绍。 ，针对具有离散属性的w b c d 数据库，本文利用b p 神经网络进行分类规则 的挖掘。首先利用收敛速度快而且准确率高的l e v e n b e r g m a r q u a r d 算法训练神 经网络，利用提出神经网络动态剪枝算法在不低于预定准确率的前提下去除不 必要的隐层单元及连接权重；然后通过聚类算法在准确率不降低的情况下将隐 层单元的激活值离散化：在分类规则的挖掘阶段，首先网络的输出根据隐层单 元的离散激活值被描述为一定的规则集；然后产生由输入属性描述离散激活值 的规则集；通过合并这两个规则集，可以产生由输入属性描述网络输出的最终 分类规则集。实验结果表明得到的规则集比由决策树方法得到的c 4 5 规则集的 预测准确率要高，且在一定的程度上理解性也要好于c 4 5 规则集。与其他规则 抽取算法相比，本实验得到的规则集准确率更高，而理解性与其他算法差不多。 同时对此w b c d 问题通过属性选择及去除部分属性值缺少的样本进行数据预 处理，实验结表明经预处理后训练时间大大缩短而且分类的准确率也没有降低 甚至有所提高。由于对连续属性的处理是神经网络规则的难点，因此对于连续 属性的i r i s 植物分类数据库。本文利用基于f 统计的方法进行连续属性离散化， 通过离散化还达到了特征选择的目的，对于i r i s 问题的规则挖掘采用与w b c d 问题相同的方法，同样得到了预测率高于c 4 5 规则且更易于理解的规则。而且 比其他规则抽取算法的准确率都要高，理解性也等于或好于其他算法。 在本文的第四章介绍数据挖掘的应用及对目前的已有的典型的数据挖掘系 统，总结了数据挖掘的发展方向及面临的技术挑战，同时对于神经网络用于数 据挖掘中仍存在的问题进行了探讨万 f 关键词：数据挖掘；神经网络；分类规则：数据预处理 t h e a p p l i c a t i o n o fn e u r a ln e t w o r k si nd a t am i n i n g a b s t r a c t i nt h i st h e s i st h er e s e a r c hb a c k g r o u n d ，d e f i n i t i o n ，p r o c e s sa n d t a s k so fd a t am i n i n g a r ef l r s ti n t r o d u c e d s e c o n d ，t h ec o m m o n l yu s e dt e c h n o l o g i e s o fd a t am i n i n ga r e d i s c u s s e di nd e t a i l o nt h i sb a s i s ，t h ea p p l i c a t i o no f n e u r a ln e t w o r k si nd a t am i n i n gi s i n v e s t i g a t e dt h o r o u g h l y t h et w op r o b l e m so fd a t am i n i n gu s i n gn e u r a ln e t w o r k sa r et h el o n gt r a i n i n gt i m e a n db e i n gu n d e r s t o o da n de x p l i c i tr e p r e s e n t a t i o no f t h ea c q u i r e dk n o w l e d g e t os o l v e t h e s e p r o b l e m s ，t h et r a i n i n ga l g o r i t h mw i t h f a s t c o n v e r g e n c es p e e da n d t h er u l e e x t r a c t i o n a l g o r i t h m s h o u l db eu s e d s o t h ef a s t t r a i n i n ga l g o r i t h m s o f b a c k p r o p a g a t i o nn e u r a ln e t w o r k sa n dt h er u l e e x t r a c t i o na l g o r i t h m sa r ei n t r o d u c e d a n dd i s c u s s e d t h ed a t a b a s ef o rt h ew i s c o n s i nb r e a s tc a n c e rd i a g n o s i s ( w b c d ) p r o b l e mw i t h d i s c r e t ea t t r i b u t e si su s e df o rm i n i n gc l a s s i f i c a t i o n r u l e su s i n gb a c k p r o p a g a t i o n n e u r a ln e t w o r k s f i r s tt h el e v e n b e r g m a r q u a r d ta l g o r i t h m ，w h i c hh a sh i g hs p e e do f c o n v e r g e n c ea n da c c u r a c y , i s u s e di n t r a i n i n g n e u r a in e t w o r k s an e wn e u r a l n e t w o r kd y n a m i cp r u n i n ga l g o r i t h mn a m e dn d pi sp r e s e n t e da n d i su s e di n r e m o v i n gu n n e c e s s a r y h i d d e nu n i t sa n dw e i g h tc o n n e c t i o n sw h e n t h ea c c u r a c yi sn o t b e l o wt h e p r e s c r i b e d l e v e l t h e n c l u s t e r i n ga l g o r i t h m i su s e dt od i s c r e t et h e a c t i v a t i o nv a l u e sa th i d d e nu n i t s d u r i n gt h ep r o c e s so fm i n i n gc l a s s i f i c a t i o nr u l e s ， t h er u l es e tt h a te x p l a i n st h en e t w o r ko u t p u t si nt e r m so f d i s c r e t ea c t i v a t i o nv a l u e sa t h i d d e nu n i t si sg e n e r a t e d t h e nt h er u l es e tt h a te x p l a i n se a c hd i s c r e t ev a l u ei nt e r m s o ft h eo r i g i n a la t t r i b u t e so ft h ei n p u td a t ai sg e n e r a t e d b ym e r g i n gt h et w os e t so f r u l e sas e to fr u l e st h a te x p l a i nt h en e t w o r ko u t p u t si nt e r m so f t h eo r i g i n a la t t r i b u t e s o ft h ei n p u td a t aa r eg e n e r a t e d e x p e r i m e n t a lr e s u l t ss h o w t h a to u rr u l es e t sn o to n l y h a v eah i g h e rp r e d i c t i v ea c c u r a c yb u ta l s oa r ee a s i e rt ou n d e r s t a n dt os o m e e x t e n t t h a nc 4 5r u l es e t c o m p a r e dw i t ho t h e rr u l ee x t r a c t i o na l g o r i t h m s ，t h er u l e s e t o b t a i n e di no u re x p e r i m e n t si sm o r ea c c u r a t et h a nt h e i r sa n dh a sa b o u tt h es a m e u n d e r s t a n d a b i l i t yw i t ht h e m f u r t h e r , t h ed a t ap r e p r o c e s s i n gi n v o l v i n gs e l e c t i n g a t t r i b u t e sa n d r e m o v i n gs a m p l e sw i t hm i s s i n g a t t r i b u t ev a l u e si su s e d a f t e r p r e p r o c e s s i n gt h ec o m p u t a t i o n a lt i m e u s e di n t r a i n i n ga n dp r u n i n gi s r e d u c e d g r e a t l ya n dt h ec l a s s i f i c a t i o na c c u r a c yi s n o tr e d u c e db u ti n c r e a s e d b e c a u s ei t i s d i f f i c u l tf o rn e u r a ln e t w o r k st od e a lw i t ha t t r i b u t e s ，w h i c hh a v ec o n t i n u o u sn u m e r i c v a l u e s ，s oi nt h i st h e s i st h em e t h o db a s e do n 矿s t a t i s t i cm e t h o di s u s e dt od i s c r e t e t h ec o n t i n u o u sn n n l e r i cv a l u e so nt h ei r i s p l a n t c l a s s i f i c a t i o n p r o b l e m a f t e r d i s c r e t i o nt h ef e a t u r es e l e c t i o ni sa c h i e v e dw h i c hc a l lr e d u c et h et r a i n i n gt i m eo f n e u r a ln e t w o r k sg r e a t l y s i m i l a r l y , t h es a m er u l e sm i n i n gm e t h o dt h a ti su s e di n w b c d p r o b l e mi sa l s ou s e df o rm i n i n gc l a s s i f i c a t i o nr u l e s t h er u l e s e to b t a i n e d n o to n l yh a sah i g h e rp r e d i c t i v ea c c u r a c yb u ta l s oa r ee a s i e rt ou n d e r s t a n dt h a nc 4 5 r u l es e ta n dr u l es e t so b t a i n e db yo t h e rr u l ee x t r a c t i o na l g o r i t h m s i nc h a p t e rf o u r , t h ea p p l i c a t i o no fd a t am i n i n ga n dt h er e p r e s e n t a t i v ed a t am i n i n g s y s t e ma tp r e s e n ta r ei n t r o d u c e d a l s ot h ed e v e l o p m e n td i r e c t i o n so f d a t am i n i n g a n dt e c h n i c a lc h a l l e n g e sa r es u m m a r i z e d i na d d i t i o n ，t h ee x i s t e n tp r o b l e m so ft h e a p p l i c a t i o n so f n e u r a ln e t w o r k si nd a t am i n i n ga r ed i s c u s s e d k e y w o r d s ：d a t am i n i n g ，n e u r a ln e t w o r k s ，c l a s s i f i c a t i o nr u l e s ， d a t a p r e p r o c e s s i n g 第1 章概论 在当今这样一个信息时代，各个领域的数据量急剧增加，据估计全世界的信 息总量每几个月就要翻番，同时随着i n t e n d e r 的发展，我们得到的数据越来越 多，这些数据对我们来说是一个宝贵的财富。在这些海量的数据中蕴藏着非常有 价值的信息，如何从中获得对于人们有益的信息就显得十分急迫面重要。传统的 技术对于数据收集方便有效，能对数据产生一定的检索、汇总和统计，但还谈不 上对数据进行理解、概括，对于海量数据的分析效率非常低。甚至不可能，导致 了“数据爆炸但知识贫乏”的现象。因此当前迫切需要某种工具和手段来从大量 的数据中挖掘出某些重要的信息，而数据挖掘技术使得上述问题的实现成为可 能。数据挖掘是一个新兴的研究领域，涉及到诸如机器学习、模式识别、统计学、 人工智能、数据可视化、高性能与分布计算和数据库等众多学科，它的研究内容 是自动的去处理大量的原始数据，从中挖掘出具有必然性的、具有意义的模式， 不仅具有广泛的应用背景而且具有深远的理论意义。数据挖掘技已经被应用到商 业、医疗天文学、生物学等众多的领域，可以这样说只要存在大量数据的地方 就必然会有数据挖掘技术的存在。基于大规模的数据采集，功能强大的多处理器 计算机和数据挖掘算法的有利支持，数据挖掘技术正不断的完善并显示其强大的 数据处理与数据分析能力。 1 1 研究背景 当前我们正处在个“数据爆炸但知识贫乏”的时代。在各种企业、商业 领域中的交易记录与财务报表，科研领域所收集的数据，其数据规模经常在数 十兆字节，甚至成百上千兆字节。现代计算机技术和数据库技术，已可以支持 存储并快速检索这样规模的数据库。这意味着，我们已具有将这样的“数据洪 流”转换为“整齐有序”但却“堆积如山”数据集合的能力。但是，面对“堆 积如山”的数据集合，无论在时间意义上还是在空间意义上，传统的数据分析 手段还是难以应付，人们无法理解并有效使用这些数据，由此导致越来越严重 的“数据灾难”。另外，传统的数据分析方法只能获得这些数据的表层信息， 而不能获得数据的内在关系和隐含的信息，即不能获得重要的知识。这样，快 速的数据产生与搜集技术和拙劣的数据分析方法之间形成了鲜明的对照，这需 要新的技术来“智能地”和“自动地”分析这些原始数据，以使消耗大量财力 与物力所收集与整理的宝贵资源一数据得以利用。这就是数据挖掘( d a t a m i n i n g ) 技术产生的背景。 神经网络在数据挖掘中的应用 1 2 数据挖掘的定义 数据库中的知识发现k d d ( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ) ，是指从数据 库中识别出有效的、新颖的、潜在有用的乃至最终可理解的非平凡过程川。数 据挖掘( d a t am i n i n g ) 是指从数据库的大量数据中揭示出隐含的、以前未知的并 具有潜在价值的信息的非平凡过程【2 】【3 1 。可见这两个术语的内涵基本相同，更 严格的讲k d d 应当是指数据库中发现知识的全过程，而d a t am i n i n g 是k d d 全过程中的一个特定的、关键步骤，即利用特定的算法从数据中抽取模式川， 这种定义实际上是把数据挖掘的对象定义为数据库。数据挖掘更为广义的定义 为：数据挖掘意味着在一些事实或观察数据的集合中寻找模式的决策支持过程 【4 1 。实际上，数据挖掘的对象不仅是数据库，也可以是文件系统或其他任何组 织在一起的数据集合。数据库中的知识发现和数据挖掘两个术语在大多数场合 中仍然不加区分地使用着，在本文中大多数的研究集中于数据挖掘这一环节， 所以采用数据挖掘这一术语。数据挖掘还可以被称为知识抽取、信息发现、知 识发现、智能数据处理、数据考古等。 1 3 数据挖掘的过程 图l ：k d d 过程的基本流程图 f i g u r e1 ：t h eb a s i cf l o wo f s t e p sc o m p r i s i n gt h ek d dp r o c e s s 从数据库中的知识发现和数据挖掘的定义可以看出，数据挖掘强调它是一 个包含多个步骤的过程，文献川认为数据挖掘有以下九步组成： ( i ) 理解应用领域和先验知识，从用户的角度确定k d d 的目标； ( 2 ) 创建目标数据集：选择一个数据集或者集中在变量或者数据样本的子集上， 使之能反映待发现的对象； f 3 ) 数据的清理和预处理：如排除噪声、确定对缺损属性的处理方法等i ( 4 ) 数据缩减和映射：根据作业目标寻找表示数据的有用特征。用降维或者变 换的方法以减少变量数或者找到对数据的恒定的表示； ( 5 ) 使k d d 目标符合特定的数据挖掘方法；也就是确定k d d 的目标是分类、回 归、还是聚类等： ( 6 ) 选择数据挖掘的算法：选择用于寻找数据中模式的方法，这包括恰当的模 型和参数的选择及使特定的数据挖掘方法符合k d d 的总体标准： ( 7 ) 进行数据挖掘：在一定的或一系列的表示形式下寻找有趣的模式，例如分 类规则、决策树、回归模型和聚类等： ( 8 ) 解释所挖掘的模式，可能的话返回i - 7 步作进一步的反复。这步可能涉 及到抽取模式或模型的可视化或给定抽取模型数据的可视化； ( 9 ) 整理已发现的知识：将获得的知识合并进另一系统进行进一步的工作或将 知识汇报给相关方： k d d 过程会多次迭代并可能在任何两步间不断循环，即如果发现不一致或 者不适合可以返回前面的步骤进行修改，直到符合要求为止，k d d 基本的流程 图如图l 所示。文献博9 j 将k d d 的( 1 ) 一( 4 ) 步合并称为数据挖掘的前处理，将 ( 5 ) 一( 8 ) 看作广义上的数据挖掘，而将( 8 ) 一( 9 ) 看作数据挖掘的后处理。这样有 利于以数据挖掘为核心来看待整个的数据挖掘过程。个更为简单的数据挖掘 流程图如图2 所示。 e 一 原始数据知识 图2 ：数据挖掘流程图 f i g u r e2 ：t h ef l o wo f s t e p sc o m p r i s i n gt h ed a t am i n i n gp r o c e s s 以上的数据挖掘流程【9 0 l 有以下四个主要的阶段组成：采集选择、数据预处 理、数据挖掘和解释评价。采集选择的目的是辨别出需要分析的数据集合，缩 小处理范围：然而实际系统今收集列的原始数据通常是“脏”的，即数据存在 杂乱性、重复性及不完整性：数据预处理可以处理数据中的遗漏及清洗脏数据， 从而提高数据挖掘的质量，数据预处理应该包括数据集成、数据清理、数据变 换和数据简化等几方面的功能；数据挖掘阶段进行实际的挖掘操作，它要先决 定数据挖掘的任务，然后选择合适的工具，进行发现知识的操作及证实发现的 知识：解释评价这一步骤的任务不仅是把结果表达出来，还要对信息进行过讧g 处理，如果不能令决策者满意，需要重复以上数据挖掘的过程。图2 所示的数 据挖掘过程的实质与图1 一致，只不过更为简洁。 1 4 数据挖掘的任务 根据发现知识的不同，我们可以将数据挖掘任务归纳为以下几类： ( 1 ) 特征规则【8 l 【9 】 从与学习任务相关的一组数据中提取出关于这些数据的特征式，这些特征 式表达了该数据集的总体特征。 ( 2 ) 分类1 1 0 j 【1 9 1 1 6 9 】【7 0 1 数据分类是发现每一数据与既定类别间映像函数的过程，或者说是挖掘出 关于该类数据的描述或模型。数据分类方法有决策树分类方法、统计方法、 神经网络方法、粗集方法等，已用于医学诊断、市场调查等领域。 f 3 ) 关联性川【7 2 】【7 3 l 【7 4 l 关联性问题是数据挖掘中研究比较成熟的问题。它是用来发现一组项目之 间的关联关系和相关关系。它们经常被表达为规则形式。关联性分析广泛 应用于交易数据分析，通过分析结果来指导销售、目录设计及其它市场决 策的制定。 f 4 ) 聚类【7 5 】1 7 6 】 聚类是一种常见的描述工作，搜索并识别一个有限的种类集合或簇集合， 从而描述数据。简单地说，就是识别出一组聚类规则，将数据分成若干类。 些种类可能相互排斥而且是穷举的( 无遗漏的) ，或者包含了更丰富的表达 形式例如层次的种类或重叠的种类。经过分类后的数据，在各类之间其 相似程度很小，而在某一类内部，其数据的相似性则很大。聚集分析在统 计、机器学习、空间数据库、数据开采等领域已有不同侧重的研究，它主 要是基于可能性分析。 ( 5 ) 预测【7 7 l 【7 8 l 通过对数据的分析处理，估计一组数据中的某些丢失数据的可能值或一个 数据集合中某种属性值的分布情况。一般是利用数理统计的方法。找出与 所要预测的属性并根据相似数据的分析估算属性值的分布情况。 4 神经网络在数据挖掘中的应用 ( 6 ) 变化和偏差分析【7 9 l f 8 0 】 变化和偏差分析是探测数据现状、历史记录或标准之间的显著变化和偏离。 偏差包括很大一类潜在的有趣知识，如观测结果与期望的偏离、分类中的 反常实例、模式的例外等。 ( 7 ) 模式发现【8 1 l s 2 j 模式发现是根据所选择的相似方面和进行比较的区域，以及匹配中是否允 许任意长的子序列和比例伸缩等进行的，对相似模式的开采有不同的方法。 ( 8 ) 路径发现 s 3 l 在分布信息环境中，文档和对象通过连接便于用户存取。理解用户存取模 式有助于改进系统设计，而且有助于作出更好的市场决策。捕捉用户的存 取模式称为路径模式开采，即路径发现。 此外还包括搜索性分析，回归等。当然，数据挖掘的任务还可以从用户的 角度分为验证和发现。验证就是证实用户的假设，发现就是系统自动的发现新 的模式。发现任务还可以细分为预测和描述【l 】。 第2 章数据挖掘的常用技术 数据挖掘和知识发现发展到今天，出现了许多的技术分支，有多种分类的 方法2 2 1 。例如数据挖掘按照所操纵的数据库可以分为关系型、事务型、时川型、 文本型等；按照所挖掘的知识的种类可以分为关联规则挖掘、分类规则挖掘、 聚类规则挖掘趋势分析等。但到目前为止，对数据挖掘的研究更集中在具体挖 掘技术的研究【1 1 。因此下面我们将介绍数据挖掘的几种常用的技术。 2 1 关联规则 关联规则挖掘是数据挖掘领域最成熟、最活跃的研究课题，是商业销售、 股票价格、银行交易等许多领域进行数据挖掘的常用手段。 2 1 1 问题描述 关联规则最初由a g r a w a l 提出【7 1 1 ，问题可以描述如下： 设，= f i ，i 3 i 。 是由胛个不同的项目组成的集合。给定一个事物数据库d ，其 中每一个事物7 1 是，中一组项目的集合即r ，7 1 是一个惟一的标示符t 1 d 。 如果项集x ，且x e t 则事物丁包含项集x 。一条关联规则就是形如x jy 的蕴含式，其中x ，y i ，x n y = 。关联规则x y 成立的条件是： 它具有支持度以即事物数据库d 中至少有s 的事物包含x u y 。它具有 置信度c ，即在事物数据库d 中包含膏的事物至少有c 同时包含y 。关联规则 挖掘问题实质上就是在事物数据库d 中找出满足最小支持度m i n s u p p o a 及最小 置信度m i n c o n f i d e n c e 的关联规则。 关联规则挖掘问题可以分解为以下两个子问题： 1 找出存在于事物数据库中的所有大项集。项集x 的支持度s u p p o a ( x ) 不小于 用户给定的最小支持度m i n s u p p o r t ，则称为大项集。 2 利用大项集生成关联规则。这些规则必须满足最小支持度和最小置信度 上述两个问题中第2 个比较容易，目前大多数的研究也集中在第1 个问题 上，挖掘关联规则的总体性能由第l 步决定。 2 1 2 关联规则挖掘步骤 所有的采掘算法不论它是采用什么数据结构，其复杂程度、效率如何，它 们都可以分为如下几个步骤： 6 1 预处理与挖掘任务有关的数据。根据具体问题的要求对数据库进行相应的 操作，从而构成规格化的数据库d ； 2 针对d ，求出所有大项集。由于一般情况下我们所面临的数据库都比较大， 所以此步是算法的核心： 3 生成满足最小置信度的规则，形成规则集r ； 4 解释并输出r ； 2 1 3 关联规则的主要研究方向 自从a g r a w a l 等人在文献中首先提出了关联规则的挖掘问题并给出解决 此问题最原始的算法a i s 之后，该问题被广泛深入的进行了研究，目前主要的 研究方向包括： 1 多循环方式的挖掘算法 此类算法中最有效和有影响的算法为a p r i o r i l 9 “，d h p 9 2 】和p a r t i t i o n 9 3 i 。 2 增量式更新算法 关联规则的增量式更新问题主要有两个：( 1 ) 在给定的最小支持度和最小置 信度下，当一个新的事物数据集d b 添加到旧的事物数据库d b 中时，如何生成 d b u d b 中的关联规则，文献叫1 给出了解决此问题的一种算法。给定事物数 据库d b ，在最小支持度和最小置信度发生变化时，如何生成数据库d b 中的 关联规则，文献1 9 5 提出了一种算法解决此类问题。 3 并行发现算法 目前已经提出的并行挖掘关联规则的算法有：c d 、c a d 和d d 算法【9 6 j 及 d m a 9 7 l 算法等。 4 挖掘一般或多层关联规则 基于要挖掘的数据库中的概念层次和发现单一概念层次中的关联规则的算 法，学者们提出了许多高效发现一般或多层关联规则的算法【9 8 1 1 9 9 1 。 5 采掘多值属性关联规则 关联规则可分为布尔型关联规则和多值属性关联规则。多值属性又可分为 数量属性和类别属性。多值属性关联规则采掘问题首先在文献【3 l 中提出。目前 提出的挖掘多值属性关联规则的算法大多是将多值属性关联规则挖掘问题转化 为布尔型关联规则采掘问题，即将多值属性的值划分为多个区间，每个区间算 作一个属性，将类别属性的每一个类别当作一个属性。这方面的研究还包括7 3 i o o l 。 6 基于约束的关联规则挖掘 基于约束的关联规则挖掘的主要目的是发现更有趣的、更实用的和更特别 的关联规则，这方面的研究主要有【1 0 1 】【1 0 2 1 。 当然，除了上述主要的研究方向外，还有挖掘相关性和因果关系、比例规 则、多维关联规则等。 2 2 决策树 决策树是一个类似于流程图的树结构，其中每个内部节点表示在一个属性 上的测试，每个分枝代表一个测试输出，而每个叶子代表类别或类分布。样本 的属性通过在决策树上测试，而达到对未知类别的样本分类，是解决分类问题 的一种有效手段。决策树已经在医疗、博弈论和商务等领域得到了广泛的应用。 决策树方法的起源是概念学习系统c l s ，发展到i d 3 方法达到高潮。决策 树是利用信息论中的互信息( 信息增益) 寻找数据库中具有最大信息量的字段， 建立决策树的一个节点，再根据字段的不同取值建立树的分支；在每个分支子 集中重复建树的下层节点和分支过程，即可建立决策树。一般来说，决策树的 构造主要由两个阶段组成：( 1 ) 生长阶段：由训练数据生成一棵决策树( 2 ) 剪 枝阶段：用剩余数据检验决策树，剪去影响预测精度的分支。这样在决策树每 个内部节点处进行属性值的比较，在叶节点得到结论。从根节点到叶节点的一 条路径就对应着一条规则，整棵决策树就对应着一组析取表达式规则。 2 2 1i d 3 方法 国际上最有影响和最早的决策树方法是由q u i u l a n 研制的i d 3 方法i l ，i d 3 的算法核心是在决策树中各级结点上用信息增益作为属性选择标准，使得在每 一非叶结点进行测试时，能获得关于被测试例子最大的类别信息，使用该属性 将例子集分成子集后，系统的熵最小。i d 3 的基本原理如下： 设e = f i f 2 r 是疗维有穷向量空间，其中e 是有穷离散符号 集，e 中的元素e = ( ”i ，v 2 ，h ) ，叫作例子，其中v ，巧，- ，= l ，2 ，胛。 设p e 和 ，e 是的两个例子集，分别叫作正例集和反例集。 假设向量空间e 中的正例集雎和反例集n e 的大小分别为p 和，l 。i d 3 方 法基于下列两个假设： f 1 ) 在向量空间e 上的一棵正确决策树对任意例子的分类概率同e 中正反 例的概率一致； f 2 ) 一棵决策树能对一例子作出正确类别判断所需的信息量为： 仰，加一焘l o g2 焘一寿l 0 9 2 忐 ( 2 1 ) 如果以属性a 作为决策树的根，a 具有v 个值 v l ，”，v ，) ，它将分 为v 个子集 ，毋，b ) ，假设e i 中含有p ，个正例和n i 个反例，子集e 。的信 息熵为，p 。胛，) ，以属性a 为根分类后的信息熵为： ( 4 ) ：窆旦盟坳，_ ) ( 2 2 ) ip 十n 以a 为根的信息增益是： g a i n ( a ) = l ( p ，”) 一e ( a ) ( 2 - 3 ) i d 3 选择使朋f ) 最大的属性a 作为根结点。对4 + 的不同取值对应的e 的v 个子集e ，递归调用上述过程生成a + 的子结点b ，b ，鼠。 i d 3 决策树生成过程如下： 算法：g e n e r a t ed e c i s i o nt r e e 由给定的训练数据产生一棵决策树。 输入：训练样本s a m p l e s 由离散值属性表示：候选属性的集合a t t r i b u t e 一，。 输出：一棵决策树。 方法： ( 1 ) 创建节点： f 2 ) i f s a m p l e s 都在同一个类c t h e n 返回作为叶节点，以类c 标记： ( 3 ) i f a t t r i b u tf f s f 为空t h e n 返回v 作为叶节点，标记为s a m p l e s 中最普通的类； ( 4 ) 选择a t t r i b u t e l i s t 中具有最高信息增益的属性t e s t _ a t t r i b u t e ； ( 5 ) 标记节点为t e s t a t t r i b u t e ： ( 6 ) f o re a c ht e s ta t t r i b u t e 中的已知值珥： ( 7 1 由节点长出一个条件为t e s ta t t r i b u t e = a 的分枝； ( 8 ) 设s ，是s a m p l e s 中t e s t _ a t t r i b u t e = a ，的样本的集合： ( 9 ) i f 岛为空t h e n 加上一个树叶，标记为s a m p l e s 中最普通的类： ( 1 0 ) e l s e 加上一个由g e n e r a t e _ d e c i s i o n _ t r e e ( s ，a t t r i b u t e 一，括，f 船l 口，f ，曲“，p ) 返回的 节点： i d 3 是一个典型的决策树学习系统，它以信息熵作为分离目标评价函数， 9 塑丝旦垒垄墼塑丝塑主盟查旦 一 采用自顶向下不可返回的策略，搜出全部空间的一部分它确保决策树建立最 简单，每次所做的测试数据最少。i d 3 算法构造的决策树平均深度较小。分类 速度较快。 典型的决策树方法还包括c a r t l l7 1 、c h a i d 1 8 】和c 4 5 t 1 9 ) 及i d 3 的增量版 本i d 4 1 2 0 1 5 1 2i d 51 2 1 1 等。 2 2 2 决策树的研究方向 自从i d 3 出现以后，许多的研究工作针对此方法进行了有效的优化和改进 i 1 1 2 ) 1 1 3 】1 i 5 1 【1 6 ，主要集中在以下几个方面： 1 扩充决策树属性的取值范围及改进选择分离属性的选择； 2 提高决策树构造效率，削减数据库遍历次数，减少i o 操作； 3 优化决策树，简化决策树输出； 4 扩充决策树，形成决策图； 5 将遗传算法、神经网络技术引入决策树算法。 2 3 贝叶斯方法 贝叶斯方法基于贝叶斯定理，它是一种统计学的分类方法。根据属性间是 否独立，可以分为朴素贝叶斯( n a f v e b a y e s ) 和贝叶斯网络( b a y e s i a n n e t w o r k s ) 。 朴素贝叶斯分类假定一个属性值对于给定类的影响独立于其他属性的值，而贝 叶斯信念网络可以表示属性间的依赖关系。 2 3 1 朴素贝叶斯 假定事例x 是类标号未知的样本，共有矗类，每类的先验概率( p r i o r p r o b a b i l i t y ) 为j d ( g ) ，j = l 足。事例x 可以用一个r t 维向量j ，_ 扛f ，x 小x n 表示， 描述对样本的疗个属性爿，爿小爿 ，的度量。j d 矽表示事例出现的概率| p c g ) 表示事例属于类别g 时，出现事例x 的条件概率。p ( 0 m 表示事例为时， 该事例属于g 类的后验概率( p o s t e r i o r p r o b i l i t y ) 。朴素贝叶斯分类就是根据贝叶 斯定理： 删耻警 ( 2 - 4 ) 将未知的样本划分到具有最大后验概率的g 类即满足下列条件 p ( c ，j x ) j d ( c ，f ) ，l s i s r ，- ，i( 2 5 ) 0 由于p 对于所有的类为常数，每类的先验概率p 矧可以由p 矧= s 扫计算得 到，其中s ，是类属于c ，的样本数s 是样本总数。 由于在朴素贝叶斯分类中假定属性间不存在依赖关系即属性间相互独立所以 p ( x i c ，) = 丌p ( x l c ，) ( 2 6 ) i l 其中p 阢l q 可以由训练样本集估计，p ( x k l 吲= 母由，其中s j k 是属性a k 上具有 值x t 且属于c ，类的训练样本数，町是属于q 类的训练样本数。 朴素贝叶斯方法具有快速、准确的特点，而且算法实现也比较简单，只需 对数据库扫描一边，同时抗干扰的能力也较强。我们将此方法曾用于分子标记 的特征带识别中【1 0 6 1 ，取得了理想的效果，此方法在w e b 页识【8 6 i 别中也取得了 理想的效果。 理论上讲贝叶斯分类是基于最小错误概率的，最小错误概率在o 1 损失【5 1 的情况下与与最小风险判别准则是等价的。然而由于类条件独立性和概率估计 的不准确性在实践中并非如此。针对朴素贝叶斯方法的不足，有人提出了改进 的n a f v eb a y e s 方法”o ，此方法通过考察各属性在给定类中取值的相关程度， 合并相关程度高的属性以提高朴素贝叶斯分类的精确度。a d a b o o s t 方法【1 是 一种增强的朴素贝叶斯学习方法，此方法被用于联合几个朴素贝叶斯分类器时 具有很好的概括能力。 2 3 2 贝叶斯网络 朴素方法假定类条件独立，然而在现实中属性间常常存在一定的依赖关系， 即不满足在给定样本的类条件下的属性间的相互独立。贝叶斯网络可以描述数 据变量间的依赖关系，它是一种图形模型，有两部分组成。第一部分是有向无 环图，每个节点代表一个随机变量，每条弧代表一个概率依赖。第二部分是每 个属性的一个条件概率表或者是概率分布。贝叶斯网络是图形表示方式与概率 知识的有机结合，它提供了一种自然地表示因果信息的方法是复杂联合概率 分布的紧凑表示方式。它的特点是使用概率去表示所有的不确定性，学习或其 他形式的推理都用概率规则实现，学习的结果表示为随即变量的概率分布它 可以解释为我们对不同可能性的信任程度1 。 贝叶斯网络用于数据挖掘的主要优点是o j ： 1 由于贝叶斯网络能够描述所有变量间的依赖关系，可以处理不完整的数据； 2 贝叶斯网络可以用来学习因果关系： 3 由于贝叶斯网络具有因果和概念语义，所以有助于与先验知识和数据相结 合： 4 贝叶斯网络与贝叶斯统计相结合是避免数据过适应的一种有效方法： 2 4 遗传算法 遗传算法是建立在自然选择和自然遗传学机理基础上的迭代自适应概率 性搜索算法3 1 ，主要包括选择、交叉、变异等操作。它在优化计算、预测以 及寻优方面具有一定的优势。用遗传算法进行数据挖掘可以按照以下几步进 行： ( 1 ) 编码和群体的初始化，通过编码将原始数据表示成遗传空间的位串，即染 色体； ( 2 ) 确定适应度函数，是适应度函数应该反映专家经验知识的可信度： ( 3 ) 遗传操作，由遗传概率计算出每个个体进行遗传操作的次数： ( 4 ) 适应度定标，为防止早熟及随机漫游现象，应采用缩小或放大的方法进行适 应度的定标； ( j ) 交叉操作，通过选择交叉概率进行交叉操作，这样可以充分发掘个体的多样 性，提高全局的搜索能力： ( 6 ) 变异，按照一定的变异概率随机的把某一个体的某些位进行变异： ( 7 ) 知识发现，即寻找到最优的个体； 由于遗传算法具有简单、有效、全局最优及不需要领域知识等优点，基于 此方法的数据挖掘也得到了广泛的研究及应用 5 j 【6 1 【7 】4 5 i 。 2 5 粗糙集 粗糙集理论的特点是不需要预先给定某些特征或者属性的数量描述，而是 直接从给定问题的描述集合出发，通过不可分辨的关系和不可分辨的类确定给 定问题的近似域，找出问题的内在规律。粗糙集理论的出发点是根据目前已有 的对于给定问题的知识将问题的论域进行划分，然后对划分后的每一个组成部 分确定其对某一概念的支持程度，即肯定支持此概念、肯定不支持此概念和可 能支持此概念。在粗糙集理论中以上三种情况分别用三个近似的集合来表示为 正域、负域和边界。基于粗糙集理论的数据挖掘算法能够使得在每种信息不完 备的情况下根据给定目标的置信度尽可能的给出问题的最大可能的解，这非常 具有实际的意义。假定有n 个条件属性，首先计算出在所有条件属性完备情况 下的一组规则，然后去除某一个条件属性根据剩下的n 1 个属性计算出在这组 不完备属性下的另一组规则，简化下去得到系统在各种信息不完备的情况下f 门 规则集合，在此基础上进行推理决策，得到我们感兴趣的信息。粗糙集理论 于其特殊的优点即能够使得在每种信息不完备的情况下根据给定目标的置信度 尽可能的给出问题的最大可能的解，而在数据挖掘中越来越得到关注【1 0 3 l 【l 0 4 j 。 2 6 人工神经网络 基于人工神经网络的方法是通过学习在分析数据中的模式来构造符合我们 需要的模型，知识与信息的存储表现为网络元件互连间分布式的联系，网络的 学习和识别决定于各神经元连接权重的动态演化过程，在数据聚类、事务数据 库的建模和分析等方面具有广泛的应用。例如由神经网络进行分类规则的挖掘 可以分为网络的构造和训练、+ 规则提取两步。网络的构造和训练是根据数据集 中的属性数目和数据特征，选择合适的编码方式构成神经网络( 例如可采用最 常用的多层b p 网络) ，但根据问题的不同可以采用其他类型的神经网络，例如 径向基神经网络、自组织特征映射神经网络等等) ，通过由监督的训练方式或者 无监督的训练来对神经网络训练。规则提取就是从网络中提取分类规则，规则 的形式为i f ( x 10 1a t ) a n d ( x 2 0 2a z ) a i l d