（控制理论与控制工程专业论文）基于多分类器融合的数据挖掘分类算法研究与应用.pdf

重庆大学硕+ 学位论文中文摘要 摘要 数据挖掘分类算法是数据挖掘研究的一个重要课题，已在商业等领域广泛 应用。学生信用分类是典型的分类挖掘问题，属于信用分类的范畴，同时也是 一个新的应用研究课题。如何采用多分类器融合的方法综合不同分类器的信息， 避免单一分类器可能存在的片面性，从而提高分类的性能，已成为数据挖掘分类 算法研究的热点问题。 本论文依托教育部“春晖计划”科研项目“高校学生个人信用评价管理系统研 究”和重庆市自然科学基金计划项目“面向混合数据类型的通用数据挖掘模式研 究”，采用多分类器融合的方法研究数据挖掘分类算法，并将该方法用于学生信 用分类。本文的主要研究工作和成果概括如下： 首先，分析了数据挖掘、数据挖掘的分类器、多分类器融合的基本理论和 方法为研究基于多分类器融合的分类算法，及其在学生信用分类数据挖掘的 应用打下基础 其次，设计了基于a d a b o o s t 的b p 神经网络融合分类算法，着重讨论了算 法的主要组成部分和基本分类器的构造，以及调整样本权重、训练神经网络基 本分类器、确定基本分类器权重这三个算法流程中的关键问题。 最后，将多分类器融合方法与项目实际需求相结合用于学生信用分类。选 择学生信用分类的数据项并进行分类挖掘数据预处理，建立了基于多分类器融 合的学生信用分类模型，通过仿真验证了该算法能有效提高基本分类器的精度 和泛化能力，用于学生信用分类是有效和可行的。在高校学生个人信用评价管 理系统的基础上设计和实现了学生信用分类模块。 本文的研究成果为学生信用分类和助学贷款的发放提供了决策依据，同时 也对信用分类的其他方面具有参考价值。 关键词：数据挖掘分类算法，多分类器融合，a d a b o o s t ，b p 神经网络，学生信用 分类 重庆大学硕士学位论文 英文摘要 a b s t r a c t d a t am i n i n gc l a s s i f i c a t i o na r i t h m e t i ci sf i l li m p o r m tp r o b l e mi nd a t am i n i n g r e s f 札a n di th a sb e e nw i d e l yu s e di nb u s i n e s s 棚。c aa n ds oo n s t u d e n tc r e d i t c l a s s i f i c a t i o ni sat y p i c a ld a t am i n i n gc l a s s i f i c a t i o np r o b l e m , a n dan wr e s e a r c hs a b j e n t i nc r e d i te l a i f i c a t i o n t h er e s e a r c ho ne l a s s i f i e a t i 0 1 1a r i t h m e t i cb a s e do nt h ec l a s s i f i e r b ym u l t i p l ec l a s s i f i e r sf l l s i o n , a v o i d i n q gt h eu n i l a t e r a l i s m f o rs i n g l ec l a s s i f i e ra n d i m p r o v i n gi t sl 删o r m a n c * , i sp o p u l a x t 1 1 i sp a p e rs t e m sf r o mt h em i n i s t r yo fe d u c a t i o nc h u n h u ip r o j e n t , r e s e a r c ha n d a p p l i c a t i o n0 1 1c h o n g q i n gc o l l e g es t u d e n tp e r s o n a lc r e d i ts y s t e m , a n dt h ec h o n g q i n g n s f p r o j - t , r e s e a r c h0 1 1u n i v e r s a ld a t am i n i n gm o d e f o rm i x e dd a t at y p e t h i sp a p e r d o 部r e s e a r c ho nd a t am i n i n gc l a s s i f i c a t i o nb a s e do nm u l n p l ec l a s s i f i e r sf u s i o nm e t h o d a n dt h i sm e t h o di sa p p l i e do nc o l l e g es t u d e n tp e r s o n a lc r e d i tc l a s s i f i c a t i o n 1 1 m a i n w o r ka n da c h i e v e m e n t so f t h i sp a p 口a r es u m m a r i z e d f o l l o w s ： f i r s t l y , i ta n a l y z e st h eb a s i ct h e o r yo fd a t am i n i n g , c l a s s i f i e r a n dm u l 卸i e e l a s s i f i e r sf u s i o n t h i si st h eb a s ef o rr e s e a r c ho nc l a s s i f i c a t i o na r i t h m e t i cb a s e do i l m u l t i p l e c l a s s i f i e r sf u s i o n ，a n di t sa p p l i c a t i o no ns t u d e n tc r e d i tc l a s s i f i c a t i o n s e c o n d l y , t h ec l a s s i f i c a t i o na r i t h m e t i ci sd e s i g n e d , b yb pn e u r a ln e t w o r kf u s i o n b a s e do ua d a b o o s t t h ep r i m a r yp a r t sa n dc o n f o r m a t i o nmd i s c u s s e d t h r o ek e y p r o b l e m ss u c ha sa d j u s t i n gt h ew e i g h to f t h es a m p l e , t r a i n i n gt h en e u r a ln e t w o r kb a s i c c l a s s i f i e ra n ds e t t i n gt h ew r i g h to f t h eb a s i cc l a s s i f i e r , o x ea l s od i s c u s s e d f i n a l l y , b a s e do nt h ef a c to ft h ep r o j e c t , t h ec l a s s i f i c a t i o na r i t h m e t i cb a s e do n m u l t i p l ec l a s s i f i e r sf u s i o ni sa p p l i e dt os t u d e n tc r e d i tc l a s s i f i c a t i o n t h es t u d e n tc r e d i t e l a s s i f i c a t i o nd a t ai t e m sa l es c h * t a do o u c 日1 1w i t hs t u d e n tl o a na n dp r e i x e a t e d 1 1 w s t u d e l l t 口e d i tc l a s s i f i c a t i o nm o d e lb a s e d0 0m u l t i p l ec l a s s i f i e r sf u s i o ni sd e s i g n e d a n d t h i sm o d e li st e s ta n dp r o v e dt h a ti tc mi m p r o v et h ep r v c t s i o na n de x t e n da b i l i t yo f s i n g l ec l a s s i f i e r a n di ti sp r o v e dt ob ea v a i l a b i l i t ya n de f f e c t i v ei ns t u d e n tc r e d i t c l a s s i f i c a t i n n t h es t u d e n tc r e d i tc l a s s i f i c a t i o nm o d u l ei si m p l e m e n t e d t h ea c h i 自c e m e n t so ft h i sp a p e ra r eu s e f u lf o rs t u d e n tc r e d i tc l a s s i f i c a t i o na n d s t u d e n tl o a n j u d g m e n t , a n df o rt h er e f e r e n c e dp a r t so f c r e d i tc l a s s i f i c a t i o n k e y w o r d 。：d a t am i n i n gc l a s s i f i c a t i o na r i t h m 矗c , m u l t i p l ec l a s s i f i e r sf u s i o n ， a d a b o o s t , b pn e u r a ln e t w o r k , s t u d e n tc r e d i tc l a s s i f i e a f i m a 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重麽太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：靳布爪 签字日期： 劢矿7 年牛月b 日 学位论文版权使用授权书 本学位论文作者完全了解重迭太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重麽太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( ) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名： 编狱 导师签名：乞易亿 签字日期：加刁年午月z 矿日 签字日期：刀口7 年午月z 汐日 重庆大学硕士学位论文 1 绪论 1 绪论 本章首先阐明本文所选课题的研究背景及其所具有的研究价值，然后着重 评述数据挖掘分类算法和多分类器融合的研究现状，最后综述本文的主要研究 内容和组织结构。 1 1 研究背景及意义 1 1 1 研究背景 2 0 世纪9 0 年代以来，随着信息技术和数据库技术的迅猛发展，人们可以非 常方便地获取和存储大量的数据，在这大量的数据背后隐藏着许多重要的信息。 面对大规模的海量的数据，传统的数据分析工具( 如管理信息系统) 只能进行 一些表层的处理( 如查询、统计等) ，而不能获得数据之间的内在关系和隐含的 信息。为了摆脱“数据丰富，知识贫乏”的困境，人们迫切需要一种能够智能地 自动地把数据转换成有用信息和知识的技术和工具。这种对强有力的数据分析 工具的迫切需求使得数据挖掘( d a t am i n i n g ，d m ) 技术应运而生。数据挖掘所发 现的知识可以用于信息管理，查询优化，决策支持和过程控制等，还可以用于数 据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层 次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下， 汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视 化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研 究领域，形成新的技术热点。 在数据挖掘中，分类( c l a s s i f i c a t i o n ) 是一种重要的数据分析技术，它可以用 于提取描述重要数据类的模型，可以预测未来的数据趋势。数据挖掘分类算法 的工作方法是通过分析己知分类信息的历史数据总结出一个预测模型。分类问 题在人工智能、机器学习以及模式识别等领域已经得到了广泛的研究，并已产 生了许多的分类方法。但是，对传统的分类算法在可扩展性和高效率性，对大 规模的海量的数据分类等方面还面临大量的问题。因此，近年来分类问题已成 为数据挖掘领域的一项重要研究内容，获得了更加广泛的、深入的研究。现实 中的很多问题都可以转化为分类问题，因而数据挖掘分类技术的潜在应用十分 广泛，从政府管理决策、商业经营、科学研究和工业企业决策支持等各个领域 都应用了分类技术。例如，可以建立一个分类模型，对银行的贷款客户进行分 类，以降低贷款的风险；也可以通过建立分类模型，对工厂的机器运转情况进 行分类，用来预测机器故障的发生。 重庆大学硕士学位论文1 绪论 学生信用分类属于信用分类( c r e x l i tc l a s s i f i c a t i o n ) ，是典型的分类挖掘问题。 信用分类涉及个人信用和企业信用等方面的内容，其中个人信用还包括各种银 行、保险行业的信用分类。个人信用作为一种基本道德准则，是指一个人遵守 约定的程度，此约定可以是个体之间的约定、个体与单位之间的约定，也可以 是社会公有的约定。个人信用代表着社会或他人对一个人的信赖程度。目前在 我国，个人信用建设还刚刚起步，在北京、上海、深圳等几个大城市的少数人 群已经开始关于商业贷款消费等信用分类，但由于技术手段相对落后，并且人 口众多，地域分散，达到全国联网的程度还需要一个较长的时间。这就决定了 个人信用建设必须从试点到全国的发展过程。高校作为一个社会单元，具有学 生个人素质较高、个人信用信息征集和管理比较容易，高校学生管理信息化程 度高等条件，具备了作为试点进一步开展个人信用建设的客观条件。由于重庆 市有高校相对集中、学生规模大的特点，各高校信息化水平高，方便的校园网 为收集学生的信用信息创造了有利条件，有助于在此基础上开展高校学生个人 信用分类的研究。 1 1 2 课题来源及研究对象 本文所选课题来源于教育部“春晖计划”科研项目“高校学生个人信用评 价管理系统研究”( s 2 0 0 5 2 6 3 0 0 2 ) 和重庆市自然科学基金计划项目“面向混合 数据类型的通用数据挖掘模式研究”( c s t c ，2 0 0 6 b b 2 1 9 0 ) 。结合项目的研究内 容，本文主要研究数据挖掘分类算法在学生信用分类的应用。拟采用多分类器 融合的方法研究分类算法，结合数据挖掘的流程将算法用于学生信用分类，建 立基于多分类器融合的学生信用分类模型，并在原有的高校学生个人信用评价 管理系统中设计和实现学生信用分类模块。 1 1 3 研究意义和目标 学生信用分类是社会个人信用建设的重要组成部分，同时也是分类挖掘的一 个新的应用领域。本文研究采用多分类器融合的方法研究数据挖掘分类算法，以 重庆大学为试点，充分利用现有的信息资源和网络资源，将该方法应用于学生信 用分类，具有重要的意义和实际的价值。通过对当前具有代表性的数据挖掘分 类算法进行比较研究，分析和总结各种分类算法的特点，可以为选择和改进分 类算法提供依据；通过多分类器融合的方法可以综合不同分类器的信息，避免 单一分类器可能存在的片面性，从而提高分类的性能；通过将学生信用分类与 助学贷款的还款情况相结合，将多分类器融合方法用于学生信用分类，建立基 于多分类器融合的学生信用分类模型，可以提高传统信用分类方法的性能，同 时也是信用分类方面一个新的尝试；通过设计和实现学生信用分类模块，根据 历史数据的分析，对学生的信用情况进行分类，可以在一定程度上降低学生助 2 重庆大学硕士学位论文 1 绪论 学贷款因为没有抵押而存在风险，为银行和学校发放助学贷款提供决策依据； 通过本文的研究和应用，有助于进一步培养和增强大学生的信用意识，为今后 大学生进入社会个人信用体系打下基础，也作为个人信用建设的一个切入点， 进一步推动整个社会信用建设。 1 2 研究现状 1 2 1 数据挖掘分类算法的研究现状 面临的主要问题 尽管数据挖掘分类算法继承了大量在人工智能、机器学习以及模式识别等 领域的理论与技术，但是它仍然面临着许多问题的挑战。主要有以下几个方面 【1 气 1 ) 分类算法的有效性和可扩放性 现在的数据库包含的数据量往往达到g b 级，甚至t b 级。从巨量的数据中 有效地抽取分类信息要求所用的挖掘算法必须是有效的，而且是可扩放的。也 就是说，算法用于大型数据库时的运行时间必须是可预测、接受的。 2 ) 噪声数据和丢失数据的处理 这个问题在商业等应用领域中尤其突出。可以想象，如果某数据库在建立 时不是面向数据挖掘的，其某些重要数据或属性可能丢失，某些数据的纪录很 可能产生模糊甚至错误。这将干扰分类挖掘过程，降低所挖掘知识的精确性。 3 ) 时序数据和知识更新问题 在各种应用领域中的数据库大多是随时间变化的，这使得早期挖掘到的知 识并不适用于后期的情况。这就要求数据挖掘系统能够具备随时更新所获知识 的功能，通常采用有效的手段来处理时序数据。 4 ) 模式可理解性 数据挖掘的结果能否为人所理解是其能否为人所用的前提条件。简单明了 的表达方式能够提高挖掘结果的可理解性。目前的表达方式主要有：决策树， 规则、图表、自然语言表示、以及数据与知识的可视化等。 5 ) 网络与分布式环境下的分类挖掘 随着i n t e r n e t 的不断发展，网络资源逐渐丰富，面对分布式与网络化的环境， 数据挖掘系统需要增加相关的技术。当前人工智能中关于多a g e n t 系统的研究 为这方面提供了有益的借鉴和帮助。 下一步研究方向 面向分类的数据挖掘研究具有重要的理论意义和实践意义。具体说来，有 以下几个方向值得进一步研究1 2 , 4 ，s 】： 3 重庆大学硕士学位论文 1 绪论 1 ) 现有分类方法的扩展和改进：对传统的分类方法，如神经网络、决策树 等进行改进或优化，使其能够处理大规模的、高维的数据。 2 ) 融合方法的应用：数据挖掘分类是一个复杂的过程，通过多种方法的相 互融合，在保留各个方法自身优点的同时相互弥补各自的缺陷，可以使得挖掘 算法更有效率。 3 ) 不确定性方法的分析和构造：对现有的不确定性方法之间的关系进行深 入分析，针对数据挖掘分类中的各种不确定性构造相应的、合理的不确定性度 量对算法性能的提高具有重要意义。 4 ) 对数据中噪声、空缺等实际问题的处理：面向数据挖掘过程和分类算法， 通过有效的手段对数据进行预处理，以提高算法的鲁棒性。 5 ) 数据挖掘分类过程中各个步骤的紧密结合：如属性离散化与属性约简的 结合、属性约简与规则抽取的结合等，这些步骤的进行应该面向最终的分类性 能，同提高分类挖掘的性能密切相关。 1 2 2 多分类器融合的研究现状 理论研究的主要方面 目前，对多分类器融合( m u l t i p l ec l a s s i f i e r sf u s i o n ) 的理论研究集中于以下三方 面 6 - 9 1 ： 1 ) 对融合工具的研究 这方面的研究是多分类器融合技术的核心内容。目前，常用的融合方法有投 票法、b a y c s 规则、d s 证据理论、基于模糊集的融合方法，k a l m a n 滤波方法、 神经网络等。 2 ) 对多分类器融合的资源结构进行优化 多分类器的融合不仅包括信息的获取、处理、评估和集成，还包括对分类器 的管理与控制。这方面的研究主要是如何协调管理多个分类器，以使融合后获得 最好性能。当分类器较多时，它们之间的交互影响也会非常复杂，而且它们之间 的相关性有可能还会随着处理对象的不同而变化。因此，如何实时地选择合适的 分类器进行融合，既能节省资源又能最大限度地获取有用信息，是提高分类性能 的重要方法。 3 ) 对单个分类器的研究 单个分类器的分类性能会影响到多分类器融合的分类性能，并且将不同的分 类器进行融合得到的效果也不同。一般认为，单个分类器的性能越好，由这些分 类器进行融合取得的分类性能就越好；融合的各分类器之间的相关性越小，越有 利于得到好的融合效果。 4 重庆大学硕士学位论文1 绪论 应用研究现状 近年来，多分类器融合的应用主要在模式识别等领域，如手写字符识别、人 脸识别、遥感图像分类、文本分类和检索、语音识别和理解等，并取得了一定成 果。在商业领域如客户细分、保险业中的风险预测等方面也有一些研究【1 0 l n 。虽然 多分类器融合在信用分类方面的研究并不很多，但也显示出了很大的研究价值和 现实应用前景。目前国内外在信用分类方面主要以线性判别分析、逻辑回归、基 于范例学习、决策树、神经网络等的传统方法为主，采用多分类器融合的方法进 行学生信用分类是新的尝试。 1 3 研究内容和组织结构 结合本文的研究内容，论文的组织结构具体安排如下： 第一章，绪论。阐述本文的研究背景、项目来源和研究意义；综述数据挖掘 分类算法和多分类器融合的研究现状；介绍主要的研究内容和组织结构安排。 第二章，分类挖掘和多分类器融合的理论分析。阐述数据挖掘的定义、过程 和任务；分析和探讨分类的概念，几种常见的分类器构造方法，分类器的评价和 比较方法；分析和探讨多分类器融合的概念，融合的有效性，常见的多分类器融 合方法。 第三章，基于多分类器融合的分类算法研究。阐述a d a b o o s t 算法提出的背景 及其特点，分析a d a b o o s t 算法的原理，训练误差和收敛性，以及泛化误差。选择 b p 神经网络作为基分类器，阐述人工神经网络的神经元的构成，b p 神经网络及 其学习算法。设计基于a d a b o o s t 的神经网络融合分类算法，阐述该算法的设计思 想和算法流程。 第四章，多分类器融合在学生信用分类的应用。选择与学生信用分类主题相 关的数据项，对分类挖掘的数据进行预处理，建立基于多分类器融合的学生信 用分类模型，并通过仿真实验来验证算法的有效性。在高校学生个人信用评价 管理系统的基础上，分析和设计学生信用分类模块，并在j 2 e e 平台上开发学生 信用分类模块。 第五章，总结。最后对本文研究和应用的工作成果进行总结，并展望下一步 的研究工作。 重庆大学硕士学位论文 2 分类挖掘与多分类器融合 2 分类挖掘与多分类器融合 本章分析和探讨分类挖掘和多分类器融合的基本理论，作为全文的理论和应 用研究的基础。首先阐述数据挖掘的定义、过程和任务，着重分析数据挖掘的数 据准备过程；然后分析和探讨分类的概念，常见的分类器的构造方法，并着重分 析分类器的评价和比较方法；最后阐述多分类器融合的概念和拓扑结构，分析融 合的有效性问题，以及常见的多分类器融合方法。 2 1 数据挖掘 2 1 1 数据挖掘的定义 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数 据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的 过程【1 2 1 。这是从技术的角度对数据挖掘的定义，包括下面几层含义：数据源必须 是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接 受、可理解、可运用；并不要求发现在任何地方都适用的知识，仅支持特定的发 现问题。 数据挖掘的定义与另一个常用的术语数据库中的知识发现( k n o w l e d g e d i s c o v e r y i n d a t a b a s e 。k d d ) 密切相关。k d d 的出现很好地满足了数据处理的需要。 关于数据挖掘与k d d 的关系有许多不同的观点，代表了不同的数据挖掘技术定义。 k d d 是数据挖掘的一个特例 这种看法认为既然数据挖掘系统可以在关系数据库、事务数据库、数据仓库、 空间数据库、文本数据以及诸如w e b 等多种数据组织形式中发现知识，那么数据 库中的知识发现k d d 只是数据挖掘的一个方面【1 3 1 。这是早期比较流行的观点，强 调了数据挖掘在数据形式上的多样性。 数据挖掘是k d d 过程的一个步骤 这种观点的核心思想是：k d d 是从数据中发现知识的全部过程，而数据挖掘 则是此全部过程中的一个特定的、关键的步骤【2 1 4 1 。这种观点认为虽然可以从数据 仓库、w e b 等数据中挖掘知识，但是这些数据都是和数据库技术相关的。把数据 挖掘作为k d d 的一个重要步骤看待，可以使我们更容易聚焦研究重点，有效解决 问题。目前，人们在数据挖掘算法的研究上，基本属于这样的范畴。 k d d 与数据挖掘含义相同 有些人认为，k d d 与数据挖掘只是叫法不一样，它们的含义基本相刚3 4 】。事 实上，在许多的文献和场合中，这两个术语仍然不加区分地使用。因此，也有人 6 重庆大学硕士学位论文 2 分类挖掘与多分类器融合 称知识发现为数据挖掘。本文也不加区别地使用两者。 2 1 2 数据挖掘的过程 数据挖掘是从大量数据中抽取未知的，有价值的模式或规律等知识的复杂过 程。简单的说，数据挖掘过程可以粗略分为几个阶段：确定挖掘对象、数据准备、 数据挖掘算法执行、模式的解释和评估【3 ，1 ”6 1 。这几个阶段是不断反馈、循环往复 的过程，直到得到用户满意的模式为止。同时，数据挖掘过程也是是交互的，需 要用户( 特别是领域专家) 的参与。数据挖掘的过程如图2 1 所示： 预 处 图2 1 数据挖掘的过程 f i g 2 1p r o c e s so f d a t am i n i n g 知 识 确定挖掘对象 确定清晰的挖掘对象，认清数据挖掘的目标是数据挖掘整个过程的第一步也 是最重要的一步。因为数据挖掘的最后结果往往是不可预测的，但要探索的问题 应是有预见的、有目标的。为了数据挖掘而挖掘数据带有盲目性，往往不会成功。 在定义挖掘对象时，需要确定如何入手、需要挖掘什么数据、需要用多少数据、 数据挖掘要进行到什么程度等问题。 数据准备 数据准备包括数据选取和数据预处理两个步骤【3 ，1 5 】： 1 ) 数据选取 数据选取的目的是确定发现任务的操作对象，目标数据是根据用户的需要从 原始数据库中抽取的一组数据。在确定数据挖掘的对象后，需要搜索所有与对象 有关的内部和外部数据，从中选出适合于数据挖掘应用的数据。在进行数据选取 时，应根据数据挖掘的需要，分析清楚哪些数据是数据挖掘中比较重要的数据源。 2 ) 数据预处理 因为现实中的数据库极容易受噪声数据、空缺数据和不一致性数据的干扰， 所以存在不完整的、含噪声的和不一致的数据是大型的、现实世界数据库或数据 仓库的共同特点。为了提高数据挖掘过程的效率和结果的质量，在完成了数据选 7 重庆大学硕士学位论文2 分类挖掘与多分类器融合 取步骤之后，还需要对数据进行预处理，对数据进行清洗，解决数据中的空缺值， 冗余、数据值的不一致、数据定义的不一致、过时的数据等问题。常用的预处理 技术有数据的净化、数据的集成、数据的转换等。 a 数据的净化 数据的净化是清除数据源中不正确、不完整等不能达到数据挖掘质量要求的数 据，例如不正确的数据、空值数据、不完整的数据等。数据的净化可以提高数据 的质量，从而得到更正确的数据挖掘结果。数据的净化还可以对不一致性数据进 行处理。 b 数据的集成 数据的集成所应用的数据不一定来源于同一个数据源。如果来自多个数据源， 就需要进行数据的集成。数据集成是从不同的数据源选取所需的数据，并进行统 的存储，而且需要消除其中的不一致性。数据的集成是数据仓库系统非常重要 的一个特征。如果基于数据仓库进行数据挖掘，那么数据的集成工作在数据仓库 系统中已经完成。如果数据挖掘所应用的数据来源于一个数据源，一般不需要进 行数据的集成，只需要进行数据的选取。 c 数据的转换 数据的转换是为了使数据适用于数据挖掘计算的需要而进行的一种转换。这 种变换主要有两个方面的原因：一是现有的数据不能满足分析需要而进行数据变 换；二是应用具体数据挖掘算法的需要。因为不同算法对数据往往也有着不同的 要求，所以为了使计算结果更高效更准确，需要对数据进行相应的变换。 数据挖掘 这里的数据挖掘是指数据挖掘算法的执行。首先根据对问题的定义明确挖掘 的任务和目的，并在确定了挖掘任务后，决定使用什么样的数据挖掘算法。选择 算法有两个考虑因素：一是不同的数据有不同的特点，因此需要用与之相关的算 法来挖掘；二是用户或实际运行系统的要求，有的用户可能希望获取容易理解的 知识，而有的用户只是希望获取预测准确度尽可能高的预测型知识，并不在意获 取的知识是否易于理解。对所得到的经过转化的数据进行挖掘，除了完善与选择 合适的算法需要人工干预外，其余的工作都由挖掘工具自动完成。 模式的解释和评估 当数据挖掘出现模式后，要对挖掘的模式进行解释和评估。数据挖掘阶段挖 掘出来的模式经过评估，可能存在冗余的或无关的模式，这时需要将其剔除；模 式也有可能不满足用户的要求，这时则需要整个发现过程退回到发现阶段之前， 如重新选取数据、采用新的数据变换方法、设定新的数据挖掘参数值，甚至换一 种算法等。另外，数据库知识发现由于最终是面向人类用户的，因此可能要对所 重庆大学硕士学位论文 2 分类挖掘与多分类器融合 发现的模式进行可视化，这样更有利于用户对数据挖掘模式进行分析，或者模式 转换为用户易懂的另一种表示。数据挖掘模式质量的优劣有两个影响要素：一是 所采用的数据挖掘技术的有效性；二是用于挖掘的数据的质量和数量( 数据量的 大小) 。如果选择了错误的数据或不适当的属性，或对数据进行了不适当的转换， 则挖掘的模式可能会不好。 2 1 3 数据挖掘的任务 数据挖掘任务一般可分有两大类：预测型和描述型1 3 , 1 2 嘲。预测型挖掘任务是 指根据数据库的若干已知字段预测或验证其他未知字段值。描述型挖掘任务是对 数据中存在的规则做一种描述，或者刻画出数据的一般特性，或者根据数据的相 似性把数据分组。 运用各种理论技术，数据挖掘可以建立六种模式，即六种主要的数据挖掘任 务：分类、回归、时间序列、聚类、关联及序列发现【3 】。分类与回归主要是用来做 预测，而关联与序列发现主要是用来描述行为。聚类则是二者兼顾。 分类模式 分类模式是一个分类器( 分类函数) ，能够把数据集中的数据项映射到某个给 定的类上。 回归模式 回归模式的函数定义与分类模式相似，它们的差别在于分类模式的预测值是 离散的，回归模式的预测值是连续的。例如，给出某种动物的特征，可以用分类 模式判定这种动物是哺乳动物还是鸟类；给出某个人的教育情况、工作经验，可 以用回归模式判定这个人的年工资在哪个范围内，是在6 0 0 0 元以下，还是在6 0 0 0 元到1 万元之间，还是在l 万元以上。 时间序列模式 时间序列模式根据数据随时间变化的趋势预测将来的值。这里需要考虑到时 间的特殊性质，像一些周期性的时间定义( 如星期、月、季节、年等) ，不同的日 子( 如节假日) 可能造成的影响。日期本身的计算方法，还有一些需要特殊考虑 的地方如时间前后的相关性( 过去的事情对将来有多大的影响力) 等。只有充分 考虑时间因素，利用现有数据随时间变化一系列的值，才能更好地预测将来的值 聚类模式 聚类模式把数据划分到不同的组中，组之间的差别尽可能大，组内的差别尽 可能小。与分类模式不同，进行聚类前并不知道将要划分成几个组和什么样的组， 也不知道根据哪些数据项来定义组。一般来说，业务知识丰富的人应该可以理解 这些组的含义，如果产生的模式无法理解或不能用，则该模式可能是无意义的， 需要回到上阶段重新组织数据。 9 重庆大学硕士学位论文2 分类挖掘与多分类器融合 关联模式 关联模式是数据项之间的关联规则，关联规则是如下形式的一种规则：在无 力偿还贷款的人当中，6 0 的人的月收入在3 0 0 0 元以下。 序列模式 序列模式与关联模式相仿，而把数据之间的关联性与时间联系起来。为了发 现序列模式，不仅需要知道事件是否发生，而且需要确定事件发生的时间。例如， 在购买彩电的人们当中，6 0 的人会在3 个月内购买影碟机。 2 2 数据挖掘的分类器 2 2 1 分类的概念 分类是数据挖掘中一项非常重要的任务，在商业等领域有着广泛的应用。分 类可描述如下p 】：训练集( 或称输入数据) 是一条条的数据库记录组成的。每一条 记录包含若干个属性，组成一个特征向量。训练集的每条记录还有一个特定的类 标签与之对应。该类标签是系统的输入，通常是以往的一些经验数据。一个具体 样本的形式可表示为样本向量“，五，而：) ，) ，在这里五表示字段值，y 表示类 别。数据挖掘分类就是分析输入数据，通过在训练集中的数据表现出来的特性， 为每一个类找到一种准确的描述或者模型。由此生成的描述或者模型来对未来的 测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，但仍可以由此 预测这些新数据所属的类。 分类数据挖掘的过程分为【3 】：分类模型的建立和分类模型的应用两个阶段。第 一阶段，分类模型的建立。在这个阶段，数据的类别是事先己知的，需要做的工 作是建立一个分类模型，用该分类模型来描述这些预先定义好的数据类别或概念。 分类模型的建立是通过分析训练样本数据来完成的。通常情况下，分类模型以分 类规则、决策树或数学公式的形式给出。第二个阶段，分类模型的应用。在对建 立的分类模型进行应用前，需要对建立的分类模型进行评估，在确保分类模型的 准确性和精确度的前提下，运用该模型对未知其类别的数据进行分类处理。 2 2 2 分类器的构造方法 分类器的构造方法主要有统计方法、机器学习方法、神经网络方法等等。对 于不同的数据类型和应用领域，每一种分类器构造方法都有各自的优点。如果某 种算法对某个特定的问题看上去比另一个算法更好，那是因为它可能更适合于这 一特定的模式分类任务，而并没有任何一种分类方法对所有的分类问题都优于其 他方法。下面介绍一些常见的分类器构造方法。 决策树 决策树是一种经典的分类方法，它着眼于从一组无次序、无规则的事例中推 1 0 重庆大学硕士学位论文 2 分类挖掘与多分类器融合 理出决策树表示形式的分类规则。最具代表性的决策树算法包括c a r t 算法，i d 3 算法和c 4 5 算法。在数据挖掘中，用得最多的是i d 3 2 1 1 算法及其后继版本c 4 5 1 2 2 1 算法。它们都采用了自顶向下、分而治之的方式来建造决策树。它利用信息增益 寻找数据库中具有最大信息量属性字段，建立决策树的一个节点，再根据该属性 字段的不同取值建立树的分枝。在每个分枝集中重复建立树的下一个节点和分枝 的过程。树的质量取决于分类精度和树的大小。决策树的构造有两个阶段：建树 和剪枝。第一阶段为建树阶段，选取部分训练数据建立决策树，决策树按广度优 先建立，直到每个叶节点包括相同的类标志为止。第二阶段为剪枝阶段，用测试 数据检验决策树，如果所建的决策树不能正确回答所研究的问题，就要对决策树 进行调整( 剪枝或增加节点) ，直到建立一棵正确的决策树。从根节点到叶节点的 一条路径就对应着一条规则，整棵决策树就对应着一组表达式规则。 神经网络 神经网络【1 7 1 最早是由心理学家和神经生物学家提出的，旨在寻求开发和测试 神经的计算模拟。神经网络是一组相互连接的输入输出单元，每个连接都与一个 权值相连。在学习阶段，通过调整神经网络的权，使网络能够正确预测输入样本 的类标号来学习。神经网络需要较长的训练时间，而且需要较多的参数，这些参 数主要靠经验确定，如网络拓扑或结构。同时，人们很难解释蕴涵在学习权之中 的符号的含义，因此神经网络很难被理解和解释。但是，神经网络也有一些其他 算法所不具备的优点，如对噪声数据的高承受能力，以及它对未经训练的数据分 类模式的优秀表现。由于提出了一些从训练过的神经网络提取规则的算法，这些 因素推动了神经网络在分类方面的应用。 遗传算法 遗传算法刚是一种有效的解决最优化问题的方法。它是模拟达尔文的遗传选 择和自然淘汰的生物进化过程的计算模型，其的思想源于生物遗传学和适者生存 的自然规律，是具有“生存+ 检测”的迭代过程的搜索算法。遗传算法以一种群体中 的所有个体为对象，并利用随机化技术指导，对一个被编码的参数空间进行高效 搜索。遗传算法从一组随机产生的称为钟群”的初始解开始搜索，种群中每个个体 是问题的一个解，称为“染色体，染色体是一串符号，比如一个二进制字符串，这 些染色体在后续迭代中不断进化，称为遗传。每一代中用j 看应度”来测量染色体的 好坏，生成的下一代染色体称为“后代”。后代是由前一代染色体通过交叉或者变异 运算形成的。在新一代形成过程中，根据适应度的大小选择部分后代，淘汰部分 后代，从而保持种群大小是常数。适应度高的染色体被选中的概率较高。这样经 过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。 重庆大学硕士学位论文 2 分类挖掘与多分类器融合 粗糙集理论 粗糙集理论【1 8 】是由波兰华沙理工大学的p a w l a k 教授于2 0 世纪8 0 年代提出的 一种研究不完整、不确定知识和数据的表达、学习、归纳的理论方法。这套方法 与统计学方法处理不确定性问题完全不同，它不是采用概率方法描述数据的不确 定性，而且与这一领域传统的模糊集合论处理不精确数据的方法也不相同。所谓 粗糙集方法，是基于一个机构( 或一组机构) 关于一些现实和它分辨某些特点、 过程、对象等的能力的知识，该方法以观察和测量所得数据进行分类的能力为基 础。粗糙集理论不仅为信息科学和认知科学提供了新的科学逻辑和研究方法，而 且为智能信息处理提供了有效的处理技术。 k 近邻分类器 k 近邻分类器【1 9 】是有较为完善理论又简单的一种不需训练的分类器设计方 法。其基本思想是：把待识别样本和参照集( 即原型集) 中的原型( 原型是指己 知类别的、具有代表性的样本) 相比较，找出参照集和待识别样本最相近( 基于 某种距离，比如欧式距离) 的k 个原型，由k 个原型确定的最具代表性的类作为待 识别样本的决策类，即k 个原型多数所属类。当训练集中样本的个数较少的时候， 可以以简单的把训练集看作参照集；但是当训练集中样本个数很多( 比如几千、 几万个) 的时候，可以采用己有的选取或者计算出参照集中的原型。 2 2 3 分类器的评价和比较 当构造出分类器后，需要了解分类器对给定问题的泛化程度，以便了解它对 未来数据进行分类时的性能表现是否有用。通过评价该分类器的性能，可以知道 它是否足够好，足够适合用于给定的问题。评价分类器的一个基本要求是测试集 当中不能包含用于训练分类器时的训练样本，否则会导致“用训练集进行测试”的方 法论上的错误【2 3 1 。由于分类器对训练它的数据存在着过分特化的现象，所以，如 果用训练数据来评价分类器的话，可能会得到过于乐观的估计。一种可能的解决 方法是，用样本集的一部分作为训练数据，余下的样本用于检测分类器的分类准 确程度。但是如果用于训练的样本太少的话，则增加了过拟合的可能性。下面介 绍几种常用的评价方法。 保持法 这是一种最为简单的分类器评价方法。它的基本思想是：首先将给定的数据 随机划分成两个独立的集合，即训练集和测试集。其中三分之二的数据分配到训 练集，余下的三分之一数据作为测试集；其次，对训练集进行泛化得到一个分类 器，然后用测试集来评估它的准确率。显然，对数据集的不同划分会得到不同的 评价结果。对它的改进方法是随机二次选样，也就是对保持方法重复k 次，然后 求每次迭代得到的准确率的平均值。 重庆大学硕士学位论文2 分类挖掘与多分类器融合 交叉验证法 交叉验证技术由c o v e r 提出，并广泛地与分类方法结合使用。交叉验证法首 先将训练集d 分为k 个大小基本相等且相互不相交的子集。对于任意子集n ，用 训练集d 一口训练分类器，然后用d i 对生成的分类器进行测试，若d f 中的样本数 为 ，分类错误的样本数为0 ，则用( 2 1 ) 式计算得到错误率弓 q = 毫严 ( 2 1 ) v j 如此反复，直至所有的子集都已用于测试为止。最后用( 2 2 ) 式计算整个分类器的错 误率p 。 口= i 1 一- e ， ( 2 2 ) 因此，分类器的准确率a c c u r a c y 可以表示为： a c c u r a c y = 1 - e ( 2 3 ) 当k 的值增大时，生成的分类器个数也随之增加，算法的复杂度会变大。 在实际应用中，通常取置的值为1 0 ，称为1 0 一折交叉验i 正( 1 0 - c v ) 。但是， 只运行一次1 0 一折交叉验证并不足以得到可信的错误估计值。由于对折数的选择 上存在着随机变动的因素，每一次对同一个分类算法在同一个训练集上运行l o 一 折交叉验证也会得到不同的结果，所以，用交叉验证法对分类器进行评估时，有 效的方式是重复运行十次l o 一折交叉验证后再求平均值，这就意味着运行学习算 法1 0 0 次，需要较大的计算开销。