（计算机应用技术专业论文）基于神经网络的数据挖掘方法研究.pdf

摘要 从大量的数据中提取和挖掘未知的、有效的和可操作的知识就是数据挖掘， 它是知识发现过程中的重要步骤。数据挖掘能够发现未知的知识，区别于那些 先提出假设再进行验证的数据处理方法。挖掘结果的有效性是指数据挖掘的结 果是正确、合理的；挖掘结果的可操作性是指挖掘的知识能够为决策提供支持。 数据挖掘越来越多地受到各界的重视并被广泛应用于各个领域。 分类技术是数据挖掘中最有应用价值的技术之一。数据分类就是在大量数 据中找出一组对象的共同特征，并将数据按照分类模型划分成不同的类的过程。 该模型能够把数据库中的元组映射到给定类别集中的某一个。数据分类一般分 两步，建立数据模型与使用模型进行分类。在使用模型进行分类前应首先评估 该模型即分类器的预测准确率；如果准确率可以接受，就可以使用类标号对未 知的数据元组或对象进行分类。 人工神经网络是在现代神经生物学研究成果的基础上发展起来的一种模拟 人脑信息处理机制的网络系统，它不但具有处理数值数据的一般计算能力，而 且还具有处理知识的思维、学习、记忆能力。基于神经网络的数据挖掘过程由 数据准备、规则提取和规则评估三个阶段组成。本文研究了教学型和分解型规 则抽取算法，在分析了r x 分解型算法后，利用关联法对输入输出神经元进行关 联计算，按关联度排完序之后，用r b f 神经网络进行结点选择，这样可以大大 减少神经网络的输入结点个数，简化网络结构，减少子网的递归分裂次数，提 高计算效率。最后，通过两个u c i 数据集中数据的验证，表明了该方法的有效 性。由于目前还没有任何一种分类方法对所有的分类问题都优于其他方法，因 此对于各种分类方法的改进与优化是一个非常有意义的研究方向。 关键词：数据挖掘，分类，规则抽取，神经网络，分解型算法， a b s t r a c t d a t am i n i n gt e c h n i q u er e p r e s e n t se x t r a c t i n gas e q u e n c eo fu n k n o w n , v a l i da n d o p e r a b l ek n o w l e d g ef r o mag r e a td e a lo fd a t u m ；i ti sa ni m p o r t a n ts t e pi nk n o w l e d g e d i s c o v e r i n gp r o c e d u r e t h ep r i n c i p l eo fd i s c o v e r i n gu n k n o w nk n o w l e d g eb yd a t a m i n i n gt e c h n i q u ei s d i f f e r e n tf r o ms u c hd a t ap r o c e s s i n gm e t h o d sl i k ep r o v i n g v a l i d a t i o na f t e rp r o p o s i n gh y p o t h e s i s t h ea v a i l a b i f i t yo fm i n i n gr e s u l t sl i e s i ni t s c o r r e c t n e s sa n dr e a s o n i n g ；t h eo p e r a b i l i t yt i e si ni t su s a g ei nd e c i s i o ns u p p o r t i n g d a t am i n i n gt e c h n i q u ei sw i d e l yu s e di ne v e r ys c i e n t i f i ca s p e c ti no u r s o c i e t y c l a s s i f y i n gt e c h n i q u ei so n eo ft h eu t m o s tv a l u a b l eo n e si na p p l i c a t i o nf i e l d s d a t u mc l a s s i f i c a t i o nr e p r e s e n t se x t r a c t i n gt h et o g e t h e rc h a r a c t e r sf r o mag r o u po f o b j e c t s , a n dc l a s s i f y i n gt h e mi n t od i f f e r e n tc l a s sa c c o r d i n gt ot h er e s u l tm o d e l t h i s m o d e lc a nm a par e c o r di nac e r t a i nd a t a b a s ei n t oo n eo ft h eg i v e nc l a s s t h e p r o c e d u r eo fd a t u mc l a s s i f i c a t i o nc o n s i s t so ft w os t e p s ：b u i l d i n gu pt h ed a t u m m o d e l a n dc l a s s i f y i n gd a t u mb yi t b u tb e f o r ec l a s s i f y i n g , t h ec o r r e c tr a t es h o u l db e e v a l u a t e d , o n c ea c c e p t a b l e ，u n k n o w nd a t ar e c o r da n do b j e c t 啪b ec l a s s i f i e di n t o d i f f e r e n tc l a s s a r t i f i c i a ln e u r a ln e t w o r ki sas i m u l a t i n gb r a i np r o c e s s i n gn e ts y s t e mb a s e do n m o d e mn e u r a lb i o l o g i cr e s e a r c h i n g , i tc a nn o to n l yp r o c e s s i n go r d i n a r yn u m e r i c d a t u m , b u ta l s oh a st h ea b i l i t yo fp r o c e s s i n gk n o w l e d g e ，l e a r n i n ga n dm e m o r i z i n g , p r o c e d u r eo fd a t am i n i n gb a s e do nn e u r a ln e t w o r k sc o n s i s t so ft h r e es t e p s ：d a t u m p r e p a r a t i o n , m l e se x t r a c t i o na n dr o l e se v a l u a t i o n t h i sp a p e rw a sd i s c u s s i n gt w o k i n d so fr u l ee x t r a c t i n ga l g o r i t h m s , p e d a g o g i c a la n dd e c o m p o s i t i o n a la l g o r i t h m s a f t e rp r e s e n t i n gd e c o m p o s i t i o n a la l g o r i t h mr x , c o m p u t i n gt h ea s s o c i a t er a t eo fi n p u t a n do u t p u td a t u m , t h e nr b fn e u r a ln e t w o r kb a s e do nj o o n ef r a m e w o r kw a su s e d f o rs e l e c t i n gp r o c e d u r e t h i sp r o c e d u r ew a st os i m p l i f yt h es t r u c t u r eo ft h en e t w o r k , r e d u c et h en u m b e ro f i n p u tn o d e s a tl a s t ，b yt w ou c i d a t a s e t s ，t h i sp a p e rh a sp r o v e d t h ea v a i l a b i l i t yo ft h i sm e t h o d b u tt h e r ei sn o o n ec l a s s i f i c a t i o nm e t h o dw a st h eb e s t o n ef o ra l lt h ep r o b l e m s m o r ee f f o r t sa r ct ob es p a r e di ns u c hf i e l d s k e y w o r d s ：d a t am i n i n g , c l a s s i f i c a t i o n , r u l ee x t r a c t i n g , n e u r a ln e t w o r k , d e c o m p o s i t i o u a la l g o r i t h m 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意 研究生签名：谭闩期：丛 ：篁 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保留、 送交论文的复印件，允许论文被查阅和借阕：经作者同意学校可以公靠论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名：谭导师签名： 武汉理工大学硕士学位论文 1 1 引言 第1 章绪论 信息技术的发展使人类收集、存储数据的能力迅速增长。数据管理技术的 进步促进了商业和政府事务的信息化，产生了大量的数据，特别是i n t e r n e t 兴起 后，互联网上的信息更是按指数速度增长。为了管理这些数据，大型数据库正 在被广泛应用于商业和科学工程领域。虽然数据库技术的进步使数据的收集和 存储变得越来越容易，但是数据规模的爆炸性增长，远远超出了人们的理解能 力，使用传统的数据库管理系统和以往的分析方法己经不能发现这些数据中所 隐藏的信息。 数据挖掘是知识发现过程中的重要步骤，是从大量的数据中提取和挖掘知 识的过程。数据挖掘被定义为从大型数据库中提取未知的、有效的和可操作的 知识，并为企业提供决策支持【1 1 。数据挖掘能够发现未知的知识，区别于那些先 提出假设再进行验证的数据处理方法。挖掘结果的有效性是指数据挖掘的结果 是正确、合理的；挖掘结果的可操作性是指挖掘的知识能够为决策提供支持。 数据挖掘越来越多地受到各界的重视并被广泛应用于各个领域，包括生物医学 和d n a 分析、金融数据的分析、零售业和客户关系管理等。 从认识论角度，知识是对事物运动状态及其变化规律的概括性描述；但基 于人工智能和信息系统，这个定义需要更精确的表达，知识源于人类的分类( 广 义) 能力，关于环境的知识从生存观点就是感觉信号的复杂分类，更抽象层次 上的分类则是推理、学习、决策的关键，是一种基础知识。因而数据挖掘中的 数据分类技术可以认为是数据挖掘中的基础和核心技术，几乎凡是有数据的地 方就有对数据进行分类的需求。如：根据金融和商业交易记录对客户按照各种 规则的分类；医院挂号处根据病人看病记录以及其它数据对病人应当去的科室 进行自动选择等等。随着数学和计算机技术的不断发展，数据量日益增大，对 于数据分类技术的研究就越发显得必要。 本文在阐述了数据挖掘的各项任务及相关技术之后，重点对几种用于提取 分类规则的神经网络挖掘算法做出了研究，给出了具体算法流程，并针对其不 足做出了改进。通过对具体数据集进行实验，证明了改进的有效性与可行性。 武汉理工大学硕士学位论文 1 2 相关文献综述 商业、教育、科学研究和工程中数据库的日益广泛应用和频繁使用，使得 人们长期以来积累了浩瀚的数据，并拥有了大量的数据资源，但是面对如此海 量的数据，传统的数据技术所能做的基本上是一些存取和标记工作，从而形成 了数据丰富而知识贫乏的局面。人们当然不会仅仅满足对这些数据的简单查询。 从信息处理的角度，人们更希望计算机帮助我们分析数据、理解数据，帮助我 们基于丰富的数据做出决策，做人力所不能及的事情。于是，数据挖掘从 大量数据中用非平凡的方法发现有用的知识就成了一种自然的需求。正是这种 需求引起了人们的广泛关注，导致了数据挖掘研究的蓬勃开展。数据挖掘和知 识发现( k d d ) 正是在这样的应用需求背景下产生并迅速发展起来的，并且成 为当前一个重要的发展领域【2 j 。 数据挖掘是从数据集中提取有用的、新颖的关系、模式和趋势的过程。国 际上第一次关于数据挖掘与知识发现的研讨会是于1 9 9 8 年6 月在美国的底特律 召开，会后激发了多个领域的交叉和渗透，吸引了众多研究领域学者的关注和 参与，大量先进技术被应用于数据挖掘研究中，由此提出和建立了许多知识发 现的方法和系统【3 l ，在世界上逐渐形成了k d d 研究的热点和高潮。 知识发现与数据挖掘是应用需求推动下多种学科融合的结果。 首先是数据库技术。随着数据库技术的不断发展及数据库管理系统的广泛 应用，大型数据库系统已经在各行各业普及，数据库中存储的数据量急剧增大 在大量的数据背后隐藏着许多重要信息，而这些重要信息可以很好地支持人们 的决策，可是目前由于对这些数据进行分析处理的工具都很少，人们用到的主 要是数据库的存储功能，而隐藏在这些数据之后的更重要的信息则没有参考价 值。数据库技术的日益成熟和数据仓库的发展为数据挖掘提供了发挥的平台。 其次，在数据库技术飞速发展的同时，人工智能领域的一个分支机器 学习的研究也取得了很大的进展。自5 0 年代开展机器学习的研究以来，先后经 历了神经模型的决策理论、概念符号获取及知识加强和论域专用学习三个阶段。 根据人类学习的不同模式，人们提出了许多种机器学习方法。如实例学习、观 察和发现学习，神经网络和遗传算法【4 2 】等。其中某些常用且较成熟的算法已被 人们运用于实际的应用系统及智能计算机的设计与实现中。数据挖掘中的许多 方法就来源于机器学习。 2 武汉理工大学硕士学位论文 最后，是应用领域的推动。由于数据存储技术的日渐成熟，数据库和联机 事务处理已经被广泛应用于金融、证券、保险、销售以及天气预报、工业生产、 分子生物学、基因工程等各行业。在工业领域，关键设备的在线监测系统和定 期巡检系统日益普及，这些都积累了大量的数据，而且在产生更多的数据。对 于这些数据，人们已经不满足于传统的统计分析手段，而需要发现更深层次的 规律，提供更有效的决策支持。 知识发现与数据挖掘研究融人工智能技术、数据库技术、数理统计技术、 可视化技术、哲学、逻辑等学科为一体，是一个多学科相互交叉融合所形成的 具有广泛应用前景的研究领域。知识发现与数据挖掘的应用范围非常广泛，数 据来源可以是经济、工业、农业、军事、社会、商业、科学的数据或用卫星观 测得到的数据。数据的形态有数字、符号、图像，声音等。数据挖掘发现的知 识可以表示成各种形式，包括规则、法则、科学规律、方程或概念网。 近年来，基于k d d 研究的有关报道不断涌现：基于决策树分类、统计分类、 贝叶斯分类等数据挖掘方法均能有效解决小规模数据库的数据挖掘问题。关联 规则是1 9 9 3 年由a g r a w a l r 等人f 4 】提出，近年来已不仅局限于在交易数据库中 挖掘关联规则，而扩展到从关系数据库、空间数据库和多媒体数据库中挖掘关 联规则，并且随着技术和应用的发展，对挖掘关联规则技术提出了更新的要求， 如在线挖掘、提高挖掘大型数据库的计算效率、减小w i 开销、挖掘定量型关 联规则等同。从神经网络对噪声的鲁棒性以及非线性函数逼近的特性出发，提出 了r b f 神经网络在一定条件下与模糊规则【3 3 】系统等价的论述嗍，及规则提取的 神经网络方法 6 ) 1 7 1 。p e d r y c z 提出了模糊径向基函数神经网络，通过所定义的d a t a m i n i n gw i n d o w s 提取产生式模糊规则【们。s c t i o n o 等通过对在神经网络中加入惩 罚项和结构调整进行属性特征提取，从而实现对属性的约简，减少了数据挖掘 的计算复杂度1 1 0 j 。 k d d 研究从九十年代初至今已取得了许多进展，但是同时还存在许多有待 人们去探索和解决的课题。同时由于知识发现方法还仅局限于几种，需要发展 新的更加有效的理论、方法和技术。 神经网络自诞生半个多世纪以来，取得了很大的成功。神经网络是根据对 象的输入输出数据直接建模的，无需对象的先验知识。神经网络理论是巨量信 息并行处理和大规模并行计算的基础，既是高度非线性动力学系统，又是自适 应组织系统，可用来描述认知、决策及控制的智能行为。神经网络具有许多优 武汉理工大学硕士学位论文 异的性能：它的可塑性、自适应性和自组织性使它具有很强的学习能力；它的 并行处理机制使它求解问题的时间很短，具有满足实时性要求的潜力；它的分 布存储方式使它的鲁棒性和容错能力都相当良好。 规则表达了输入输出之间的因果关系，就像人们常用的语言表示“如果， 那么”一样。从数值数据中抽取规则有多种方法。这些年来，人们提出了许 多神经网络模型，许多文献探讨了从神经元网络中提取规则的方法【1 3 】【1 4 】，多层 前向网络是其中最常用的一种。它把神经元按层排列，每一层的神经元只与上 一层和下一层的神经元相连。它的一个突出特点是：它是一个通用的近似器， 也就是说，它可以按任何期望精度拟合任意连续型函数。近年来，随着k d d 研 究的兴起与飞速发展，基于k d d 的神经网络研究成为热点研究方向之一。 目前，国外数据挖掘的发展趋势及其研究方向主要体现在：对知识发现方 法的研究进一步发展，如近年来注重对贝叶斯方法以及b o o s t i n g 方法的研究和 提高；传统的统计学回归法在k d d 中的应用；k d d 与数据库的紧密结合。 在应用方面包括：k d d 商业软件工具不断产生和完善，注重建立解决问题 的整体系统，而不是孤立的过程。用户主要集中在大型银行、保险公司、电信 公司和销售业【1 l 】。国外很多计算机公司非常重视数据挖掘的开发应用，i b m 和 微软都成立了相应的研究中心进行这方面的工作。此外，一些公司的相关软件 也开始在国内销售。 1 3 论文的内容和组织 本文主要内容是研究用于神经网络分类规则抽取的数据挖掘算法，以及如 何对该算法进行优化，使得网络结构尽量简化，减少该规则抽取过程的时间开 销，并对优化后的分类正确率是否提高进行了验证。本文的结构将按照如下方 式组织： 第1 章介绍了数据挖掘技术与知识发现过程的产生、发展、研究现状及未 来发展的趋势，提出了本文研究的主要内容。 第2 章概述了数据挖掘技术的基本理论、相关概念以及数据挖掘的任务。 并列举了数据挖掘的应用领域。 第3 章着重介绍了数据挖掘技术中的分类技术，并对几种分类器的构造方 法进行了研究，给出了算法流程。 第4 章对本文算法研究的基础神经网络技术做出了综述性的概括，并 4 武汉理工大学硕士学位论文 对b p 算法流程和针对其不足做出的改进做了详细的说明。本文用r b f 网络对 r x 算法的输入前件进行了优化，因此本章对r b f 网络进行了简单介绍。 第5 章针对四种基于前馈型网络的数据挖掘算法做了较深入研究，并重点 研究了r x 算法的基本原理和思想，给出了算法流程，针对其结构复杂的特点对 输入端做出了优化，并通过u c i 数据集进行了验证。 第6 章对全文的工作做了总结，提出一些不足并对今后的工作做出了展望。 1 4 本章小结 本章介绍了数据挖掘技术与知识发现过程的产生、发展、研究现状及未来 发展的趋势，对本文的内容组织做出了说明，阐述了本文研究的主要内容。 5 武汉理工大学硕士学位论文 第2 章数据挖掘技术概述 2 1 数据挖掘的提出 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又潜在有 用的信息和知识的过程。 数据挖掘从狭义上是指从数据库中提取知识。具体的说就是在数据库中， 对数据进行一定的处理，从而获得其中隐含的、事先未知的而又可能极为有用 的信息。数据挖掘包括以下几个步骤：从大规模数据库中( 或其它来源) 取得 数据；选择合适的特征属性；挑选合适的样本；剔除数据中不正常的数据并补 足不够的部分；用适当的变换使数据挖掘过程与数据模型相适应或相匹配；辨 别所得到的知识，将得到的结果信息化或可视化，然后与现有的知识相结合、 比较。这些步骤是从数据到知识的必由之路。每一步骤都可能是成功的关键或 失败的开始。在一般的定义中数据挖掘是知识获取的部分。 2 2 数据挖掘与传统分析方法的区别 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别 是数据挖掘是在没有明确假设的前提下去挖掘信息并发现知识。数据挖掘所得 到的信息应具有先前未知、有效性和可用性三个特征。 先前未知的信息是指该信息是预先未曾预料的，即数据挖掘是要发现那些 不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息 越是出乎意料，就可能越有价值。 2 3 相关概念 2 3 1 知识发现 数据库中的知识发现( k d d ) 是从数据集中识别出有效的、新颖的、潜在 有用的，以及最终可理解的模式的高级处理过程f 3 2 j 。数据挖掘( d m ) 是指从大 型数据库的数据中提取出人们感兴趣的知识，这些知识是隐含的、事先未知的、 潜在的有用信息。k d d 代表从低层次数据中提取高层次知识的全过程，包括数 6 武汉理工大学硕士学位论文 据信息收集，数据原型确定，相关函数的分析，知识的抽取和数据模式分析。 而d m 则是指从数据中自动抽取模型。在首届k d d 国际学术会议上，f a y y a d 等人提出了k d d 处理模型【2 】。共分五个关键阶段： 1 数据准备 一般可以分为四个子步骤：数据清洗；数据选择；数据预处理；数据表示。 2 数据挖掘 数据挖掘是k d d 的核心，也是技术难点所在。它的任务是从数据集中搜索 出用户可能感兴趣的或对用户可能有用的模式。数据挖掘的工作量一般占整个 k d d 过程工作量的2 5 左右。 3 评价、解释模式模型 确定有意义的、有效的、有用的模式，提供易于理解的方式或可视化工具。 4 巩固知识 进行知识的一致性、动态更新和维护。 5 运用知识 运用知识是k d d 的最终目的，但从系统的角度看这又是知识评价的广义延 伸，是在实践中进一步评价所挖掘的知识，并把结论反馈到整个k d d 系统中去。 k d d 过程可能需要多次的循环反复，每一个步骤一旦与预期目标不符，都要回 溯到前面的步骤，重新调整，重新执行，形成一种螺旋式的上升。如图2 1 所 示，是k d d 的全部过程。 7 武汉理工大学硕士学位论文 原始数据 图2 1f a y y a d 知识发现过程模型 在知识发现过程中，数据被存储在数据库中，根据数据挖掘算法的要求从 数据库中选取数据挖掘所需要的数据，在数据预处理阶段对噪音数据和错误数 据进行处理，然后对数据进行变换满足数据挖掘算法的要求，选择合适的数据 挖掘算法进行数据挖掘，以发现知识模式，这就是知识发现的核心阶段，最后 对发现的模式进行解释和评估，删除冗余和无关的模式，并对发现的模式进行 可视化，把结果转换成用户易懂的表示方式。 2 3 2 数据仓库 为了划清数据处理的分析型环境与操作型环境之间的界限，由原来的以单 一数据库为中心的数据环境发展为一种新的体系化环境，即数据仓库1 1 5 l 。数据 仓库不是为了存储数据，而是为了更好地组织企业内所有可能收集到的数据。 建立数据仓库不是目的，只是进行决策支持的中间环节，保证数据的一致性、 准确性、综合性、易用性，为各种决策支持方案提供统一的数据源。例如，以 8 武汉理工大学硕士学位论文 客户为中心的数据仓库是根据客户管理的需求，对企业所有可能和客户相关的 数据进行重组，使得企业对自己的客户具有统一的认识【l q 。一般情况下，数据 挖掘都要先把数据从数据仓库中拿到数据集市中( 如图2 - 2 所示) 。从数据仓库 中直接得到要进行数据挖掘的数据有许多好处，因为数据仓库的数据清理和数 据挖掘的数据清洗差不多，如果数据在导入数据仓库时已经清理过，那很可能 在做数据挖掘时就没有必要再清洗一次了，而且所有的数据不一致问题都已经 被解决了。 另外，数据挖掘库可能是源数据仓库的一个逻辑上的子集，而不一定非得 是物理上单独的数据库。 图2 2 数据仓库与数据挖掘的关系图 2 4 数据挖掘的任务 2 4 1 关联规则挖掘 数据关联是数据库中存在的一类重要的可被发现的知识【1 7 】。若两个或多个 变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关 联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。从而为某些决 策提供必要支持，如购买了某一商品对购买其他商品的影响，发现这样的规则 可以应用于商品货架设计、存货的安排以及根据购买模式对用户进行分类。我 们将关联规则按不同的情况进行分类： 1 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型 9 一一一一 武汉理工大学硕士学位论文 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间 的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来。对数值 型字段进行处理，可以将其进行动态的分割，或者直接对原始的数据进行处理， 数值型关联规则中也可以包含种类变量。 2 基于规则中数据的抽象层次，可以分为单层和多层关联规则 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不 同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 3 基于规则中涉及到的数据的维数，关联规则可以分为单维和多维关联规则 在单维的关联规则中，只涉及到数据的一个维，如用户购买的商品；而在 多维的关联规则中，要处理的数据将会涉及多个维。也就是说，单维关联规则 是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的关系。 2 4 2 分类与预测 分类与预测要解决的问题是为一个事件或者对象归类和预测，是两种数据 分析形式，它是可用于抽取能够描述重要数据集合或预测未来数据趋势的模型。 分类方法用于预测数据对象的离散类别；而预测则用于预测数据对象的连续取 值。如：可以构造一个分类模型来对银行贷款进行风险评估；也可建立一个预 测模型，利用客户收入与职业来预测其可能用于购买计算机设备的支出大小。 机器学习、专家系统、统计学和神经生物学等领域的研究人员已经提出了许多 具体的分类预测方法。 数据挖掘用于预测的工作原理是通过分析已知分类信息的历史数据总结出 一个预测模型。这里用于建立模型的数据称为训练集，通常是已经掌握的历史 数据。训练集也可以是通过实际的实验得到的数据。比如从包含公司所有顾客 的数据库中取出一部分数据做实验，向他们发送介绍新产品的推销信，然后收 集对此做出回应的客户名单，然后就可以用这些推销回应记录建立一个预测哪 些用户会对新产品感兴趣的模型，最后把这个模型应用到公司的所有客户上。 数据挖掘用于分类的工作原理是根据分类过程首先建立一个描述数据集类 别或概念的模型。该模型是通过对数据库中各数据记录内容的分析而获得的。 每一条数据记录都可认为是属于一个确定的数据类别。其类别值是由属性描述 的。分类学习又可称为有教师监督学习，它是在已知训练样本类别的情况下， 通过学习建立相应模型；而无教师监督学习则是训练样本的类别未知的情况下 1 0 武汉理工大学硕士学位论文 进行的。通常分类学习所获得的模型可以表示为分类规则形式、决策树形式或 数学公式形式。 如果一个学习模型的准确率经测试被认为是可以接受的，那么就可以使用 这一模型对未来数据记录或对象进行分类。与分类学习方法相比，预测方法可 以认为是对未知类别的数据记录或对象的类别取值，利用学习所获得的模型进 行预测。从这一角度出发，分类与回归是两种主要预测形式。前者用于预测离 散的目标变量，后者用于预测连续的目标变量。在进行分类或预测挖掘之前， 首先必须准备好挖掘数据。一般需要对数据进行清洗、选择、预处理、表示， 以便提高分类或预测的准确性，效率和可扩展性。 2 4 3 概念描述 概念描述是指类别特征的概括性描述知识。根据数据的微观特性发现其表 征的、带有普遍性的、较高层次概念的、宏观的知识，以此来反映同类事物的 共同性质，是对数据的概括、精炼和抽象。 概念描述的发现方法和实现技术有很多，如数据立方体、属性归约等。数 据立方体也称做多维数据库、实现视图、o l a p 。该方法的基本思想是实现某些 常用的代价较高的聚类函数的计算，如计数、求和、平均、最大值等，并将这 些实现视图储存在多维数据库中。既然很多聚类函数需经常重复计算，那么在 多维数据立方体中存放预先计算好的结果将能保证快速响应，并可灵活地提供 不同角度和不同抽象层次上的数据视图。另一种概念描述发现方法是加拿大 s i m o nf r a s e r 大学提出的面向属性的归约方法。这种方法以类s q l 语言表示数 据挖掘查询，收集数据库中的相关数据集，然后在相关数据集上应用一系列数 据推广技术进行数据推广，包括属性删除、概念树提升、属性阈值控制、计数 及其他聚类函数传播等。 2 4 4 聚类 聚类就是把整个数据库分成不同的群组。它的目的是使得群与群之间的差 别很明显，而同一个群之间的数据尽量相似。与分类不同，在开始对数据进行 聚类之前并不知道要把数据分成几组，也不知道怎么分即依照哪几个主要变量。 因此在聚类之后要有一个对专业领域知识很熟悉的人来解释这样分群的意义。 很多情况下，一次聚类后所得到的分群对可能并不理想，这时就需要删除或增 加变量以影响分群的方式，经过几次反复之后才能最终得到一个理想的结果。 1 1 武汉理工大学硕士学位论文 神经网络和k 一均值是比较常用的聚类算法。 聚类与分类是两个不同的概念。在分类之前，已经知道要把数据分成哪几 类，每个类的性质是什么，而聚类则恰恰相反。 2 4 5 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致 1 6 1 ， 这些数据对象称做孤立点。大部分数据挖掘方法将孤立点视为噪声或异常数据 并丢弃。然而，在一些应用中，罕见的事件可能比正常出现的事件更有实际价 值，因此发展起来的孤立点数据分析被称作孤立点挖掘。 孤立点可以使用统计试验检测。它假定一个数据分布或概率模型，并使用 距离度量，到其他聚类的距离很大的对象被视为孤立点。基于偏差的方法通过 考察一组对象主要特征上的差别识别孤立点，而不是使用统计或距离度量。 2 5 数据挖掘的应用 由于数据挖掘能够自动发现以前未知的模式，自动预测未来趋势和行为【堋， 因此，数据挖掘技术广泛用于以下一些领域： 零售市场营销 这是数据挖掘技术应用最早也是最重要的领域，主要功能是：市场定位， 消费者分析，预测销售趋势，优化营销策略，分析库存需求，选择零售点，价 格分析等。在民航系统中，还可以帮助优化组合航线航班，发现提高航线效益 的机票预订方式。 金融 预测存贷款趋势，优化存贷款策略；抽取预测模式；监督交易活动， 发现交易规则。 信用保险 分析保险客户的要求和信誉， 过程控制质量监督 鉴别产品制造过程中的缺陷； 化工医药 保险风险行为模式以及欺诈行为。 管理由异常行为引起的通信网络数据。 从各种文献资料中自动提取有关化学反应的信息，发现新的、有用的化学 成分，分析和解释有利于提高产品质量、改进产品功能、增加公司利润的重要 武汉理工大学硕士学位论文 信息和数据。 工程与科学数据分析 分析科学数据；数据库模式集成；传感数据分析和处理。 司法 帮助调查案件，诈骗监测，洗钱认证，犯罪组织分析等。 军事 信息系统中的目标特征提取、关联规则挖掘等。 2 6 本章小结 本章概要介绍了数据挖掘技术的基本理论、相关概念以及数据挖掘的任务。 并列举了数据挖掘的应用领域。数据挖掘是从大量数据中发现有用的模式，这 些数据可以存放在数据库、数据仓库或其他信息存储介质中。这是一个新兴的 跨学科领域，源于诸如数据库系统、数据仓库、统计学、机器学习、数据可视 化、信息检索和高性能计算等。 武汉理工大学硕士学位论文 第3 章分类分析 分类技术是数据挖掘中的主要技术方法之一，本章重点叙述了分类技术的 原理、一般步骤框架及四种常用方法，并给出了几种核心方法的算法描述。 3 1 分类及分类器 分类在数据挖掘中是一个非常重要的课题，数据分类就是在大量数据中找 出一组对象的共同特征，并将数据按照分类模型划分成不同的类的过程。该分 类模型即分类器。它代表了这类数据的整体信息，即该类的内涵描述。该模式 能够把某个数据元组映射到给定类别集中的某一个类。 数据分类的过程可以大致分为两步： 首先是建立一个数据模型，描述预定的数据类集或概念集。假定每个元素 属于一个预定的类，由一个类标签属性表示。对于分类，数据元组也称为样本、 实例或对象。为建立分类模型而被分析的数据元组构成训练数据集。训练数据 集中的单个元组称为训练样本。通过分析由属性描述的数据元组来构造模型。 由于提供了每个训练样本的类标号，这一步也称作有监督的学习。它不同于无 监督的学习( 聚类) ，后者的训练样本的类标号是未知的，要学习的类集合或数 量也可能事先不知道。通常，学习模型以分类规则、决策树或数学公式等形式 显示。 其次，使用模型进行分类。首先评估该模型即分类器的预测准确率。模型 在给定测试集上的准确率是被模型正确分类的测试样本的百分比。对于每个测 试样本，将己知的类标号与该样本的学习模型预测类比较。如果模型的准确率 可以接受，就可以使用类标号对未知的数据元组或对象进行分类。 3 2 分类分析的主要步骤 分类分析是一种根据输入数据集建立分类模型的系统方法。包括决策树分类 法、基于规则的分类法、最近邻分类法和神经网络分类法等。这些技术都使用 一种学习算法确定分类模型，该模型能够很好地拟合输入数据中类标号和输入 属性之间的联系。学习算法得到的模型不仅要很好地拟合输入数据，还要能够 正确地预测未知样本的类标号。因此，该算法的主要目标就是建立具有很好的 泛化能力模型，即建立能够准确地预测未知样本类标号的模型。 1 4 武汉理工大学硕士学位论文 构造分类器的过程一般分为以下几个主要步骤： ( 1 ) 将现有的己经类别的数据划分为训练数据和测试数据两部分； ( 2 ) 通过构造数据分类算法对训练集进行学习。最终得到一个符合学习要 求的分类模型，它可以以分类规则、决策树或数据公式等形式显示。 ( 3 ) 使用分类模型对测试数据进行检测，如果符合测试要求( 如分类精度) ， 则进行( 4 ) ，否则，返回( 2 ) 。 c 4 ) 应用得到的分类模型对未知数据进行分类。 其中，步骤( 1 ) 目前主要有两种划分方法：保持方法和k 倍交叉验证方法。 保持方法将己知数据随机地划分为训练数据和测试数据两部分，一般做法是三 分之二为训练数据，其余三分之一为测试数据，使用训练模型导出分类模型， 其在测试数据上的分类精度作为最终的分类精度。 保持方法的局限性体现在三个方面： 用于训练的样本较少，因为要保留一部分数据用于检验，因此，建立的 模型不如使用所有样本建立的模型； 模型可能高度依赖于训练集和检验集的构成。一方面，训练集越小，模 型的方差就越大；另一方面，如果训练集太大，用较小的检验集估计的准确率 又不太可靠； 训练集和检验集不再是相互独立的，因为训练集和检验集来源于同一个 数据集，在一个子集中超出比例的类在另一个子集就低于比例，反之亦然。 k 倍交叉验证将己知数据随机划分为k 个互不相交的个数大致相等的数据 子集墨，是，是，& ，训练和测试迭代进行k 次。在第1 次迭代时，s 作为测试 数据，其余的子集用于训练分类法。最终分类器的分类精度取k 次测试数据上 的分类精度的平均值i ”。 3 3 分类分析的主要方法 3 3 1 决策树 决策树，又称判定树，是一种类似二叉树或多叉树的树结构。树中的每个 非叶子结点( 包括根结点) 对应于训练样本集中一个非类别属性的测试，非叶 子结点的每一个分枝对应属性的一个测试结果，每个叶子结点则代表一个类或 类分布。从根结点到叶子结点的一条路径形成一条分类规则。 武汉理工大学硕士学位论文 决策树可以很方便地转化为分类规则，是一种非常直观的分类模式表示形 式。决策树是基于归纳学习理论而形成的一种树结构，基于决策树方法学习的 一个最大的优点就是它在学习过程中不需要了解许多领域知识，只要训练例子 能够用属性结论的方式表达出来，就可用决策树来学习。 一棵决策树的内部结点是属性或属性的集合，叶结点是需要划分的类。决 策树易于转换为i f - t h e n 型的分类规则。 总的来说，决策树的构建是一种白上而下、分而治之的归纳过程，本质是 贪心算法。从根结点开始，对每个非叶子结点，找出其对应样本集中的一个属 性对样本集进行测试，根据不同的测试结果将训练样本集划分成若干个子样本 集，每个子样本集构成一个新叶子结点，对新叶子结点再重复上述划分过程， 这样不断循环，直至达到给定的终止条件。其中，测试属性的选择和如何划分 样本集是构建决策树的关键环节。不同的决策树算法在此使用的技术不尽相同。 算法3 1 给出了决策树归纳算法的框架。该算法的输入是训练样本集e 和属 性f ，算法递归地选择最优的属性来划分数据，并扩展树的叶子结点，直到满足 条件为止。具体描述如下： 算法3 1 决策树归纳算法的框架 d e c i s i o n t r e e ( e ，f ) 1i fs t o p p i n g _ c o n d i t i o n ( e ，f ) - - t m et h e n 2 l e a f = c r e a t e n o d e 0 3 l e a f 1 a b e l = c l a s s i f y ( e ) 4r e t u r nl e a f 5e l s e 6 r o o t = c r e a t e n o d e 0 7 r o o t t e s t _ c o n d i t i o n = f m d _ b e s t _ s p l i t ( e ，f ) i 是择最优属性划分数据 8令v = v l v 是r o o t t e s t _ c o n d i t i o n 的一个可能输出) 9f o r 每个v e vd o 1 0 e = e lr o o t t e s t _ c o n d i t i o n ( c ) = 、，并且e e e ) 1 1c h i l d = d e c i s i o n t r e e ( e ，f ) 肭展叶子结点 1 2 将c h i l d 作为r o o t 的派生结点添加到树中，并将边( r o o t c h i l d ) 标记为v 1 3 e n d f o r 1 6 武汉理工大学硕士学位论文 1 4e n d i f 1 5r e t u r nr o o t 在构造决策树时，许多分枝可能反映的是训练数据中的异常，如噪声或孤 立点。树的剪枝方法用于处理这种过分适应数据的问题，通常采用的是统计度 量的方法，剪去最不可靠的分枝，试图通过检测和剪枝，导致较快的分类，提 高该树独立于测试数据的正确分类率，保证未知数据上分类的准确性。常用的 两种剪枝方法是先剪枝和后剪枝。 一般地，后剪枝所需的计算较先剪枝多，但产生的树更可靠。 决策树算法中的著名算法是i d 3 ，以后又有了对i d 3 算法的增强算法，c 4 5 就是i d 3 算法的后继算法，c 5 又是继c a 5 之后的算法。 i d 3 算法和c a 5 算法，适用于相对小的数据集。当这两种算法用于大型数 据库的数据挖掘时，有效性和可伸缩性就是一个需要关注的问题。大部分决策 树的方法往往限制训练样本驻留内存。在数据挖掘应用中，大型数据库中包含 数以百万计的数据是极为平常的。所以，算法的限制制约了可伸缩性，频繁的 内、外存交换也导致算法的效率低下。 在大型数据库中利用决策树进行分类，早期的策略是连续属性离散化，用 每个结点对数据进行选样。选样前，将样本集划分成多个子集，各子集放在内 存中，分别为各子集构造决策树。最终的分类将由各子集得到的分类进行组合 而得到。一般地，通过子集分割得到的分类准确性不及一次性分类的准确性高。 决策树算法还可以与数据仓库技术集成，用于数据挖掘。比如将数据立方 体方法与决策树方法集成，可以提供交互的决策树的多层挖掘，数据立方体和 存放在概念分层中的知识可以用于不同的抽象层归纳决策树。一旦得到决策树， 概念分层可以用来概化或特化树的结点，并对新的特定抽象层的数据重新分类。 决策树分类算法的优点： ( 1 ) 产生的分类规则易于理解。决策树的每个分枝都对应一个分类规则， 因此决策树分类算法最终可以输出一个容易理解的规则集； ( 2 ) 速度相对较快； ( 3 ) 准确率相对较高。 缺点是，首先，在构造树的过程中，需要对数据集进行多次的顺序扫描和 排序，因而