基于多分类器融合的数据挖掘分类算法研究与应用

《基于多分类器融合的数据挖掘分类算法研究与应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

重庆大学硕士学位论文基于多分类器融合的数据挖掘分类算法研究与应用姓名：梁勇林申请学位级别：硕士专业：控制理论与控制工程指导教师：石为人20070420 重庆大学硕+学位论文中文摘要摘要数据挖掘分类算法是数据挖掘研究的一个重要课题，已在商业等领域广泛应用。学生信用分类是典型的分类挖掘问题，属于信用分类的范畴，同时也是一个新的应用研究课题。如何采用多分类器融合的方法综合不同分类器的信息，避免单一分类器可能存在的片面性，从而提高分类的性能，已成为数据挖掘分类算法研究的热点问题。本论文依托教育部“春晖计划”科研项目“高校学生个人信用评价管理系统研究”和重庆市自然科学基金计划项目“面向混合数据类型的通用数据挖掘模式研究”，采用多分类器融合的方法研究数据挖掘分类算法，并将该方法用于学生信用分类。本文的主要研究工作和成果概括如下：首先，分析了数据挖掘、数据挖掘的分类器、多分类器融合的基本理论和方法．为研究基于多分类器融合的分类算法，及其在学生信用分类数据挖掘的应用打下基础．其次，设计了基于AdaBoost的BP神经网络融合分类算法，着重讨论了算法的主要组成部分和基本分类器的构造，以及调整样本权重、训练神经网络基本分类器、确定基本分类器权重这三个算法流程中的关键问题。最后，将多分类器融合方法与项目实际需求相结合用于学生信用分类。选择学生信用分类的数据项并进行分类挖掘数据预处理，建立了基于多分类器融合的学生信用分类模型，通过仿真验证了该算法能有效提高基本分类器的精度和泛化能力，用于学生信用分类是有效和可行的。在高校学生个人信用评价管理系统的基础上．设计和实现了学生信用分类模块。本文的研究成果为学生信用分类和助学贷款的发放提供了决策依据，同时也对信用分类的其他方面具有参考价值。关键词：数据挖掘分类算法，多分类器融合，AdaBoost，BP神经网络，学生信用分类 重庆大学硕士学位论文英文摘要ABSTRACTDataminingclassificationarithmeticisfillimpormtproblemindataminingres∞f℃札andithasbeenwidelyusedinbusiness棚。caandSOon．Studentcreditclassificationisatypicaldataminingclassificationproblem,andanwresearchsabjentincreditelaⅨification．TheresearchOnelassifieati011arithmeticbasedOntheclassifierbymultipleclassifiersfllsion,avoidinqgtheunilateralismforsingleclassifierandimprovingitsl删ormanc*,ispopulax．T11ispaperstemsfromtheministryofeducationChunhuiprojent,‘'Researchandapplication011Chongqingcollegestudentpersonalcreditsystem",andtheChongqingNSFproj∞-t,‘'Research011universaldataminingmodeformixeddatatype'’．Thispaperdo部researchondataminingclassificationbasedonmulnpleclassifiersfusionmethod．AndthismethodisappliedOncollegestudentpersonalcreditclassification．11"mainworkandachievementsofthispap口aresummarized∞follows：Firstly,itanalyzesthebasictheoryofdatamining,classifierandmul卸Ieelassifiersfusion．ThisisthebaseforresearchonclassificationarithmeticbasedOilmultipleclassifiersfusion，anditsapplicationonstudentcreditclassification．Secondly,theclassificationarithmeticisdesigned,byBPneuralnetworkfusionbasedOUAdaBoost．Theprimarypartsandconformationmdiscussed．Throekeyproblemssuchasadjustingtheweightofthesample,trainingtheneuralnetworkbasicclassifierandsettingthewrightofthebasicclassifier,oxealsodiscussed．Finally,basedonthefactoftheproject,theclassificationarithmeticbasedOnmultipleclassifiersfusionisappliedtostudentcreditclassification．Thestudentcreditelassificationdataitemsalesch*tadOOUC．日11WithstudentloanandpreIxeated．11wstudellt口editclassificationmodelbased00multipleclassifiersfusionisdesigned．Andthismodelistestandprovedthatitcmimprovetheprvctsionandextendabilityofsingleclassifier．Anditisprovedtobeavailabilityandeffectiveinstudentcreditclassificatinn．Thestudentcreditclassificationmoduleisimplemented．Theachi自cementsofthispaperareusefulforstudentcreditclassificationandstudentloanjudgment,andforthereferencedpartsofcreditclassification．Keyword。：DataMiningClassificationArithm矗c,MultipleClassifiersFusion，AdaBoost,BPNeuralNetwork,StudentCreditClassifieafimaⅡ 独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重麽太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：靳布爪签字日期：劢矿7年牛月b日学位论文版权使用授权书本学位论文作者完全了解重迭太堂有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权重麽太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密()，在——年解密后适用本授权书。本学位论文属于不保密(√)。(请只在上述一个括号内打“4”)学位论文作者签名：编狱导师签名：／乞易亿．签字日期：加刁年午月z矿日签字日期：刀口7年午月z汐日 重庆大学硕士学位论文1绪论1绪论本章首先阐明本文所选课题的研究背景及其所具有的研究价值，然后着重评述数据挖掘分类算法和多分类器融合的研究现状，最后综述本文的主要研究内容和组织结构。1．1研究背景及意义1．1．1研究背景20世纪90年代以来，随着信息技术和数据库技术的迅猛发展，人们可以非常方便地获取和存储大量的数据，在这大量的数据背后隐藏着许多重要的信息。面对大规模的海量的数据，传统的数据分析工具(如管理信息系统)只能进行一些表层的处理(如查询、统计等)，而不能获得数据之间的内在关系和隐含的信息。为了摆脱“数据丰富，知识贫乏”的困境，人们迫切需要一种能够智能地自动地把数据转换成有用信息和知识的技术和工具。这种对强有力的数据分析工具的迫切需求使得数据挖掘(DataMining，DM)技术应运而生。数据挖掘所发现的知识可以用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。在数据挖掘中，分类(Classification)是一种重要的数据分析技术，它可以用于提取描述重要数据类的模型，可以预测未来的数据趋势。数据挖掘分类算法的工作方法是通过分析己知分类信息的历史数据总结出一个预测模型。分类问题在人工智能、机器学习以及模式识别等领域已经得到了广泛的研究，并已产生了许多的分类方法。但是，对传统的分类算法在可扩展性和高效率性，对大规模的海量的数据分类等方面还面临大量的问题。因此，近年来分类问题已成为数据挖掘领域的一项重要研究内容，获得了更加广泛的、深入的研究。现实中的很多问题都可以转化为分类问题，因而数据挖掘分类技术的潜在应用十分广泛，从政府管理决策、商业经营、科学研究和工业企业决策支持等各个领域都应用了分类技术。例如，可以建立一个分类模型，对银行的贷款客户进行分类，以降低贷款的风险；也可以通过建立分类模型，对工厂的机器运转情况进行分类，用来预测机器故障的发生。 重庆大学硕士学位论文1绪论学生信用分类属于信用分类(CrexlitClassification)，是典型的分类挖掘问题。信用分类涉及个人信用和企业信用等方面的内容，其中个人信用还包括各种银行、保险行业的信用分类。个人信用作为一种基本道德准则，是指一个人遵守约定的程度，此约定可以是个体之间的约定、个体与单位之间的约定，也可以是社会公有的约定。个人信用代表着社会或他人对一个人的信赖程度。目前在我国，个人信用建设还刚刚起步，在北京、上海、深圳等几个大城市的少数人群已经开始关于商业贷款消费等信用分类，但由于技术手段相对落后，并且人口众多，地域分散，达到全国联网的程度还需要一个较长的时间。这就决定了个人信用建设必须从试点到全国的发展过程。高校作为一个社会单元，具有学生个人素质较高、个人信用信息征集和管理比较容易，高校学生管理信息化程度高等条件，具备了作为试点进一步开展个人信用建设的客观条件。由于重庆市有高校相对集中、学生规模大的特点，各高校信息化水平高，方便的校园网为收集学生的信用信息创造了有利条件，有助于在此基础上开展高校学生个人信用分类的研究。1．1．2课题来源及研究对象本文所选课题来源于教育部“春晖计划”科研项目“高校学生个人信用评价管理系统研究”(s2005．2．63002)和重庆市自然科学基金计划项目“面向混合数据类型的通用数据挖掘模式研究”(CSTC，2006BB2190)。结合项目的研究内容，本文主要研究数据挖掘分类算法在学生信用分类的应用。拟采用多分类器融合的方法研究分类算法，结合数据挖掘的流程将算法用于学生信用分类，建立基于多分类器融合的学生信用分类模型，并在原有的高校学生个人信用评价管理系统中设计和实现学生信用分类模块。1．1．3研究意义和目标学生信用分类是社会个人信用建设的重要组成部分，同时也是分类挖掘的一个新的应用领域。本文研究采用多分类器融合的方法研究数据挖掘分类算法，以重庆大学为试点，充分利用现有的信息资源和网络资源，将该方法应用于学生信用分类，具有重要的意义和实际的价值。通过对当前具有代表性的数据挖掘分类算法进行比较研究，分析和总结各种分类算法的特点，可以为选择和改进分类算法提供依据；通过多分类器融合的方法可以综合不同分类器的信息，避免单一分类器可能存在的片面性，从而提高分类的性能；通过将学生信用分类与助学贷款的还款情况相结合，将多分类器融合方法用于学生信用分类，建立基于多分类器融合的学生信用分类模型，可以提高传统信用分类方法的性能，同时也是信用分类方面一个新的尝试；通过设计和实现学生信用分类模块，根据历史数据的分析，对学生的信用情况进行分类，可以在一定程度上降低学生助2 重庆大学硕士学位论文1绪论学贷款因为没有抵押而存在风险，为银行和学校发放助学贷款提供决策依据；通过本文的研究和应用，有助于进一步培养和增强大学生的信用意识，为今后大学生进入社会个人信用体系打下基础，也作为个人信用建设的一个切入点，进一步推动整个社会信用建设。1．2研究现状1．2．1数据挖掘分类算法的研究现状①面临的主要问题尽管数据挖掘分类算法继承了大量在人工智能、机器学习以及模式识别等领域的理论与技术，但是它仍然面临着许多问题的挑战。主要有以下几个方面【1气1)分类算法的有效性和可扩放性现在的数据库包含的数据量往往达到GB级，甚至TB级。从巨量的数据中有效地抽取分类信息要求所用的挖掘算法必须是有效的，而且是可扩放的。也就是说，算法用于大型数据库时的运行时间必须是可预测、接受的。2)噪声数据和丢失数据的处理这个问题在商业等应用领域中尤其突出。可以想象，如果某数据库在建立时不是面向数据挖掘的，其某些重要数据或属性可能丢失，某些数据的纪录很可能产生模糊甚至错误。这将干扰分类挖掘过程，降低所挖掘知识的精确性。3)时序数据和知识更新问题在各种应用领域中的数据库大多是随时间变化的，这使得早期挖掘到的知识并不适用于后期的情况。这就要求数据挖掘系统能够具备随时更新所获知识的功能，通常采用有效的手段来处理时序数据。4)模式可理解性数据挖掘的结果能否为人所理解是其能否为人所用的前提条件。简单明了的表达方式能够提高挖掘结果的可理解性。目前的表达方式主要有：决策树，规则、图表、自然语言表示、以及数据与知识的可视化等。5)网络与分布式环境下的分类挖掘随着Internet的不断发展，网络资源逐渐丰富，面对分布式与网络化的环境，数据挖掘系统需要增加相关的技术。当前人工智能中关于多Agent系统的研究为这方面提供了有益的借鉴和帮助。②下一步研究方向面向分类的数据挖掘研究具有重要的理论意义和实践意义。具体说来，有以下几个方向值得进一步研究12,4，s】：3 重庆大学硕士学位论文1绪论1)现有分类方法的扩展和改进：对传统的分类方法，如神经网络、决策树等进行改进或优化，使其能够处理大规模的、高维的数据。2)融合方法的应用：数据挖掘分类是一个复杂的过程，通过多种方法的相互融合，在保留各个方法自身优点的同时相互弥补各自的缺陷，可以使得挖掘算法更有效率。3)不确定性方法的分析和构造：对现有的不确定性方法之间的关系进行深入分析，针对数据挖掘分类中的各种不确定性构造相应的、合理的不确定性度量对算法性能的提高具有重要意义。4)对数据中噪声、空缺等实际问题的处理：面向数据挖掘过程和分类算法，通过有效的手段对数据进行预处理，以提高算法的鲁棒性。5)数据挖掘分类过程中各个步骤的紧密结合：如属性离散化与属性约简的结合、属性约简与规则抽取的结合等，这些步骤的进行应该面向最终的分类性能，同提高分类挖掘的性能密切相关。1．2．2多分类器融合的研究现状①理论研究的主要方面目前，对多分类器融合(MultipleClassifiersFusion)的理论研究集中于以下三方面[6-91：1)对融合工具的研究这方面的研究是多分类器融合技术的核心内容。目前，常用的融合方法有投票法、Baycs规则、D—s证据理论、基于模糊集的融合方法，Kalman滤波方法、神经网络等。2)对多分类器融合的资源结构进行优化多分类器的融合不仅包括信息的获取、处理、评估和集成，还包括对分类器的管理与控制。这方面的研究主要是如何协调管理多个分类器，以使融合后获得最好性能。当分类器较多时，它们之间的交互影响也会非常复杂，而且它们之间的相关性有可能还会随着处理对象的不同而变化。因此，如何实时地选择合适的分类器进行融合，既能节省资源又能最大限度地获取有用信息，是提高分类性能的重要方法。3)对单个分类器的研究单个分类器的分类性能会影响到多分类器融合的分类性能，并且将不同的分类器进行融合得到的效果也不同。一般认为，单个分类器的性能越好，由这些分类器进行融合取得的分类性能就越好；融合的各分类器之间的相关性越小，越有利于得到好的融合效果。4 重庆大学硕士学位论文1绪论②应用研究现状近年来，多分类器融合的应用主要在模式识别等领域，如手写字符识别、人脸识别、遥感图像分类、文本分类和检索、语音识别和理解等，并取得了一定成果。在商业领域如客户细分、保险业中的风险预测等方面也有一些研究【10'ln。虽然多分类器融合在信用分类方面的研究并不很多，但也显示出了很大的研究价值和现实应用前景。目前国内外在信用分类方面主要以线性判别分析、逻辑回归、基于范例学习、决策树、神经网络等的传统方法为主，采用多分类器融合的方法进行学生信用分类是新的尝试。1．3研究内容和组织结构结合本文的研究内容，论文的组织结构具体安排如下：第一章，绪论。阐述本文的研究背景、项目来源和研究意义；综述数据挖掘分类算法和多分类器融合的研究现状；介绍主要的研究内容和组织结构安排。第二章，分类挖掘和多分类器融合的理论分析。阐述数据挖掘的定义、过程和任务；分析和探讨分类的概念，几种常见的分类器构造方法，分类器的评价和比较方法；分析和探讨多分类器融合的概念，融合的有效性，常见的多分类器融合方法。第三章，基于多分类器融合的分类算法研究。阐述AdaBoost算法提出的背景及其特点，分析AdaBoost算法的原理，训练误差和收敛性，以及泛化误差。选择BP神经网络作为基分类器，阐述人工神经网络的神经元的构成，BP神经网络及其学习算法。设计基于AdaBoost的神经网络融合分类算法，阐述该算法的设计思想和算法流程。第四章，多分类器融合在学生信用分类的应用。选择与学生信用分类主题相关的数据项，对分类挖掘的数据进行预处理，建立基于多分类器融合的学生信用分类模型，并通过仿真实验来验证算法的有效性。在高校学生个人信用评价管理系统的基础上，分析和设计学生信用分类模块，并在J2EE平台上开发学生信用分类模块。第五章，总结。最后对本文研究和应用的工作成果进行总结，并展望下一步的研究工作。 重庆大学硕士学位论文2分类挖掘与多分类器融合本章分析和探讨分类挖掘和多分类器融合的基本理论，作为全文的理论和应用研究的基础。首先阐述数据挖掘的定义、过程和任务，着重分析数据挖掘的数据准备过程；然后分析和探讨分类的概念，常见的分类器的构造方法，并着重分析分类器的评价和比较方法；最后阐述多分类器融合的概念和拓扑结构，分析融合的有效性问题，以及常见的多分类器融合方法。2．1数据挖掘2．1．1数据挖掘的定义数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程【121。这是从技术的角度对数据挖掘的定义，包括下面几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现在任何地方都适用的知识，仅支持特定的发现问题。数据挖掘的定义与另一个常用的术语数据库中的知识发现(KnowledgeDiscoveryinDatabase。KDD)密切相关。KDD的出现很好地满足了数据处理的需要。关于数据挖掘与KDD的关系有许多不同的观点，代表了不同的数据挖掘技术定义。@KDD是数据挖掘的一个特例．这种看法认为既然数据挖掘系统可以在关系数据库、事务数据库、数据仓库、空间数据库、文本数据以及诸如WEB等多种数据组织形式中发现知识，那么数据库中的知识发现KDD只是数据挖掘的一个方面【131。这是早期比较流行的观点，强调了数据挖掘在数据形式上的多样性。②数据挖掘是KDD过程的一个步骤这种观点的核心思想是：KDD是从数据中发现知识的全部过程，而数据挖掘则是此全部过程中的一个特定的、关键的步骤【2’141。这种观点认为虽然可以从数据仓库、WEB等数据中挖掘知识，但是这些数据都是和数据库技术相关的。把数据挖掘作为KDD的一个重要步骤看待，可以使我们更容易聚焦研究重点，有效解决问题。目前，人们在数据挖掘算法的研究上，基本属于这样的范畴。③KDD与数据挖掘含义相同有些人认为，KDD与数据挖掘只是叫法不一样，它们的含义基本相刚3'4】。事实上，在许多的文献和场合中，这两个术语仍然不加区分地使用。因此，也有人6 重庆大学硕士学位论文2分类挖掘与多分类器融合称知识发现为数据挖掘。本文也不加区别地使用两者。2．1．2数据挖掘的过程数据挖掘是从大量数据中抽取未知的，有价值的模式或规律等知识的复杂过程。简单的说，数据挖掘过程可以粗略分为几个阶段：确定挖掘对象、数据准备、数据挖掘算法执行、模式的解释和评估【3，1”61。这几个阶段是不断反馈、循环往复的过程，直到得到用户满意的模式为止。同时，数据挖掘过程也是是交互的，需要用户(特别是领域专家)的参与。数据挖掘的过程如图2．1所示：预处图2．1数据挖掘的过程Fig．2．1Processofdatamining知识①确定挖掘对象确定清晰的挖掘对象，认清数据挖掘的目标是数据挖掘整个过程的第一步也是最重要的一步。因为数据挖掘的最后结果往往是不可预测的，但要探索的问题应是有预见的、有目标的。为了数据挖掘而挖掘数据带有盲目性，往往不会成功。在定义挖掘对象时，需要确定如何入手、需要挖掘什么数据、需要用多少数据、数据挖掘要进行到什么程度等问题。②数据准备数据准备包括数据选取和数据预处理两个步骤【3，15】：1)数据选取数据选取的目的是确定发现任务的操作对象，目标数据是根据用户的需要从原始数据库中抽取的一组数据。在确定数据挖掘的对象后，需要搜索所有与对象有关的内部和外部数据，从中选出适合于数据挖掘应用的数据。在进行数据选取时，应根据数据挖掘的需要，分析清楚哪些数据是数据挖掘中比较重要的数据源。2)数据预处理因为现实中的数据库极容易受噪声数据、空缺数据和不一致性数据的干扰，所以存在不完整的、含噪声的和不一致的数据是大型的、现实世界数据库或数据仓库的共同特点。为了提高数据挖掘过程的效率和结果的质量，在完成了数据选7 重庆大学硕士学位论文2分类挖掘与多分类器融合取步骤之后，还需要对数据进行预处理，对数据进行清洗，解决数据中的空缺值，冗余、数据值的不一致、数据定义的不一致、过时的数据等问题。常用的预处理技术有数据的净化、数据的集成、数据的转换等。a．数据的净化数据的净化是清除数据源中不正确、不完整等不能达到数据挖掘质量要求的数据，例如不正确的数据、空值数据、不完整的数据等。数据的净化可以提高数据的质量，从而得到更正确的数据挖掘结果。数据的净化还可以对不一致性数据进行处理。b．数据的集成数据的集成所应用的数据不一定来源于同一个数据源。如果来自多个数据源，就需要进行数据的集成。数据集成是从不同的数据源选取所需的数据，并进行统～的存储，而且需要消除其中的不一致性。数据的集成是数据仓库系统非常重要的一个特征。如果基于数据仓库进行数据挖掘，那么数据的集成工作在数据仓库系统中已经完成。如果数据挖掘所应用的数据来源于一个数据源，一般不需要进行数据的集成，只需要进行数据的选取。c．数据的转换数据的转换是为了使数据适用于数据挖掘计算的需要而进行的一种转换。这种变换主要有两个方面的原因：一是现有的数据不能满足分析需要而进行数据变换；二是应用具体数据挖掘算法的需要。因为不同算法对数据往往也有着不同的要求，所以为了使计算结果更高效更准确，需要对数据进行相应的变换。③数据挖掘这里的数据挖掘是指数据挖掘算法的执行。首先根据对问题的定义明确挖掘的任务和目的，并在确定了挖掘任务后，决定使用什么样的数据挖掘算法。选择算法有两个考虑因素：一是不同的数据有不同的特点，因此需要用与之相关的算法来挖掘；二是用户或实际运行系统的要求，有的用户可能希望获取容易理解的知识，而有的用户只是希望获取预测准确度尽可能高的预测型知识，并不在意获取的知识是否易于理解。对所得到的经过转化的数据进行挖掘，除了完善与选择合适的算法需要人工干预外，其余的工作都由挖掘工具自动完成。④模式的解释和评估当数据挖掘出现模式后，要对挖掘的模式进行解释和评估。数据挖掘阶段挖掘出来的模式经过评估，可能存在冗余的或无关的模式，这时需要将其剔除；模式也有可能不满足用户的要求，这时则需要整个发现过程退回到发现阶段之前，如重新选取数据、采用新的数据变换方法、设定新的数据挖掘参数值，甚至换一种算法等。另外，数据库知识发现由于最终是面向人类用户的，因此可能要对所 重庆大学硕士学位论文2分类挖掘与多分类器融合发现的模式进行可视化，这样更有利于用户对数据挖掘模式进行分析，或者模式转换为用户易懂的另一种表示。数据挖掘模式质量的优劣有两个影响要素：一是所采用的数据挖掘技术的有效性；二是用于挖掘的数据的质量和数量(数据量的大小)。如果选择了错误的数据或不适当的属性，或对数据进行了不适当的转换，则挖掘的模式可能会不好。2．1．3数据挖掘的任务数据挖掘任务一般可分有两大类：预测型和描述型13,12．嘲。预测型挖掘任务是指根据数据库的若干已知字段预测或验证其他未知字段值。描述型挖掘任务是对数据中存在的规则做一种描述，或者刻画出数据的一般特性，或者根据数据的相似性把数据分组。运用各种理论技术，数据挖掘可以建立六种模式，即六种主要的数据挖掘任务：分类、回归、时间序列、聚类、关联及序列发现【3】。分类与回归主要是用来做预测，而关联与序列发现主要是用来描述行为。聚类则是二者兼顾。①分类模式分类模式是一个分类器(分类函数)，能够把数据集中的数据项映射到某个给定的类上。②回归模式回归模式的函数定义与分类模式相似，它们的差别在于分类模式的预测值是离散的，回归模式的预测值是连续的。例如，给出某种动物的特征，可以用分类模式判定这种动物是哺乳动物还是鸟类；给出某个人的教育情况、工作经验，可以用回归模式判定这个人的年工资在哪个范围内，是在6000元以下，还是在6000元到1万元之间，还是在l万元以上。③时间序列模式时间序列模式根据数据随时间变化的趋势预测将来的值。这里需要考虑到时间的特殊性质，像一些周期性的时间定义(如星期、月、季节、年等)，不同的日子(如节假日)可能造成的影响。日期本身的计算方法，还有一些需要特殊考虑的地方如时间前后的相关性(过去的事情对将来有多大的影响力)等。只有充分考虑时间因素，利用现有数据随时间变化一系列的值，才能更好地预测将来的值．④聚类模式聚类模式把数据划分到不同的组中，组之间的差别尽可能大，组内的差别尽可能小。与分类模式不同，进行聚类前并不知道将要划分成几个组和什么样的组，也不知道根据哪些数据项来定义组。一般来说，业务知识丰富的人应该可以理解这些组的含义，如果产生的模式无法理解或不能用，则该模式可能是无意义的，需要回到上阶段重新组织数据。9 重庆大学硕士学位论文2分类挖掘与多分类器融合⑤关联模式关联模式是数据项之间的关联规则，关联规则是如下形式的一种规则：在无力偿还贷款的人当中，60％的人的月收入在3000元以下。⑥序列模式序列模式与关联模式相仿，而把数据之间的关联性与时间联系起来。为了发现序列模式，不仅需要知道事件是否发生，而且需要确定事件发生的时间。例如，在购买彩电的人们当中，60％的人会在3个月内购买影碟机。2．2数据挖掘的分类器2．2．1分类的概念分类是数据挖掘中一项非常重要的任务，在商业等领域有着广泛的应用。分类可描述如下p】：训练集(或称输入数据)是一条条的数据库记录组成的。每一条记录包含若干个属性，组成一个特征向量。训练集的每条记录还有一个特定的类标签与之对应。该类标签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可表示为样本向量“，．．．，五，．．．，而：)，)，在这里五表示字段值，y表示类别。数据挖掘分类就是分析输入数据，通过在训练集中的数据表现出来的特性，为每一个类找到一种准确的描述或者模型。由此生成的描述或者模型来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，但仍可以由此预测这些新数据所属的类。分类数据挖掘的过程分为【3】：分类模型的建立和分类模型的应用两个阶段。第一阶段，分类模型的建立。在这个阶段，数据的类别是事先己知的，需要做的工作是建立一个分类模型，用该分类模型来描述这些预先定义好的数据类别或概念。分类模型的建立是通过分析训练样本数据来完成的。通常情况下，分类模型以分类规则、决策树或数学公式的形式给出。第二个阶段，分类模型的应用。在对建立的分类模型进行应用前，需要对建立的分类模型进行评估，在确保分类模型的准确性和精确度的前提下，运用该模型对未知其类别的数据进行分类处理。2．2．2分类器的构造方法分类器的构造方法主要有统计方法、机器学习方法、神经网络方法等等。对于不同的数据类型和应用领域，每一种分类器构造方法都有各自的优点。如果某种算法对某个特定的问题看上去比另一个算法更好，那是因为它可能更适合于这一特定的模式分类任务，而并没有任何一种分类方法对所有的分类问题都优于其他方法。下面介绍一些常见的分类器构造方法。①决策树决策树是一种经典的分类方法，它着眼于从一组无次序、无规则的事例中推10 重庆大学硕士学位论文2分类挖掘与多分类器融合理出决策树表示形式的分类规则。最具代表性的决策树算法包括CART算法，ID3算法和C4．5算法。在数据挖掘中，用得最多的是ID3[211算法及其后继版本C4．51221算法。它们都采用了自顶向下、分而治之的方式来建造决策树。它利用信息增益寻找数据库中具有最大信息量属性字段，建立决策树的一个节点，再根据该属性字段的不同取值建立树的分枝。在每个分枝集中重复建立树的下一个节点和分枝的过程。树的质量取决于分类精度和树的大小。决策树的构造有两个阶段：建树和剪枝。第一阶段为建树阶段，选取部分训练数据建立决策树，决策树按广度优先建立，直到每个叶节点包括相同的类标志为止。第二阶段为剪枝阶段，用测试数据检验决策树，如果所建的决策树不能正确回答所研究的问题，就要对决策树进行调整(剪枝或增加节点)，直到建立一棵正确的决策树。从根节点到叶节点的一条路径就对应着一条规则，整棵决策树就对应着一组表达式规则。②神经网络神经网络【171最早是由心理学家和神经生物学家提出的，旨在寻求开发和测试神经的计算模拟。神经网络是一组相互连接的输入输出单元，每个连接都与一个权值相连。在学习阶段，通过调整神经网络的权，使网络能够正确预测输入样本的类标号来学习。神经网络需要较长的训练时间，而且需要较多的参数，这些参数主要靠经验确定，如网络拓扑或结构。同时，人们很难解释蕴涵在学习权之中的符号的含义，因此神经网络很难被理解和解释。但是，神经网络也有一些其他算法所不具备的优点，如对噪声数据的高承受能力，以及它对未经训练的数据分类模式的优秀表现。由于提出了一些从训练过的神经网络提取规则的算法，这些因素推动了神经网络在分类方面的应用。③遗传算法遗传算法刚是一种有效的解决最优化问题的方法。它是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，其的思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导，对一个被编码的参数空间进行高效搜索。遗传算法从一组随机产生的称为‘钟群”的初始解开始搜索，种群中每个个体是问题的一个解，称为“染色体，染色体是一串符号，比如一个二进制字符串，这些染色体在后续迭代中不断进化，称为遗传。每一代中用‘‘j看应度”来测量染色体的好坏，生成的下一代染色体称为“后代”。后代是由前一代染色体通过交叉或者变异运算形成的。在新一代形成过程中，根据适应度的大小选择部分后代，淘汰部分后代，从而保持种群大小是常数。适应度高的染色体被选中的概率较高。这样经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。 重庆大学硕士学位论文2分类挖掘与多分类器融合④粗糙集理论粗糙集理论【18】是由波兰华沙理工大学的Pawlak教授于20世纪80年代提出的一种研究不完整、不确定知识和数据的表达、学习、归纳的理论方法。这套方法与统计学方法处理不确定性问题完全不同，它不是采用概率方法描述数据的不确定性，而且与这一领域传统的模糊集合论处理不精确数据的方法也不相同。所谓粗糙集方法，是基于一个机构(或一组机构)关于一些现实和它分辨某些特点、过程、对象等的能力的知识，该方法以观察和测量所得数据进行分类的能力为基础。粗糙集理论不仅为信息科学和认知科学提供了新的科学逻辑和研究方法，而且为智能信息处理提供了有效的处理技术。⑤k．近邻分类器k．近邻分类器【19】是有较为完善理论又简单的一种不需训练的分类器设计方法。其基本思想是：把待识别样本和参照集(即原型集)中的原型(原型是指己知类别的、具有代表性的样本)相比较，找出参照集和待识别样本最相近(基于某种距离，比如欧式距离)的k个原型，由k个原型确定的最具代表性的类作为待识别样本的决策类，即k个原型多数所属类。当训练集中样本的个数较少的时候，可以以简单的把训练集看作参照集；但是当训练集中样本个数很多(比如几千、几万个)的时候，可以采用己有的选取或者计算出参照集中的原型。2．2．3分类器的评价和比较当构造出分类器后，需要了解分类器对给定问题的泛化程度，以便了解它对未来数据进行分类时的性能表现是否有用。通过评价该分类器的性能，可以知道它是否足够好，足够适合用于给定的问题。评价分类器的一个基本要求是测试集当中不能包含用于训练分类器时的训练样本，否则会导致“用训练集进行测试”的方法论上的错误【231。由于分类器对训练它的数据存在着过分特化的现象，所以，如果用训练数据来评价分类器的话，可能会得到过于乐观的估计。一种可能的解决方法是，用样本集的一部分作为训练数据，余下的样本用于检测分类器的分类准确程度。但是如果用于训练的样本太少的话，则增加了过拟合的可能性。下面介绍几种常用的评价方法。①保持法这是一种最为简单的分类器评价方法。它的基本思想是：首先将给定的数据随机划分成两个独立的集合，即训练集和测试集。其中三分之二的数据分配到训练集，余下的三分之一数据作为测试集；其次，对训练集进行泛化得到一个分类器，然后用测试集来评估它的准确率。显然，对数据集的不同划分会得到不同的评价结果。对它的改进方法是随机二次选样，也就是对保持方法重复K次，然后求每次迭代得到的准确率的平均值。 重庆大学硕士学位论文2分类挖掘与多分类器融合②交叉验证法交叉验证技术由Cover提出，并广泛地与分类方法结合使用。交叉验证法首先将训练集D分为K个大小基本相等且相互不相交的子集。对于任意子集n，用训练集D一口训练分类器，然后用Di对生成的分类器进行测试，若Df中的样本数为^‘，分类错误的样本数为Ⅳ0，，则用(2．1)式计算得到错误率弓·q=毫严(2．1)』Vj如此反复，直至所有的子集都已用于测试为止。最后用(2．2)式计算整个分类器的错误率P。口=i1‘一-e，(2．2)因此，分类器的准确率Accuracy可以表示为：Accuracy=1-e(2．3)当K的值增大时，生成的分类器个数也随之增加，算法的复杂度会变大。在实际应用中，通常取置的值为10，称为10一折交叉验i正(10-cv)。但是，只运行一次10一折交叉验证并不足以得到可信的错误估计值。由于对折数的选择上存在着随机变动的因素，每一次对同一个分类算法在同一个训练集上运行lO一折交叉验证也会得到不同的结果，所以，用交叉验证法对分类器进行评估时，有效的方式是重复运行十次lO一折交叉验证后再求平均值，这就意味着运行学习算法100次，需要较大的计算开销。但由于这种处理方法能够产生稳定的测量结果，可以用到几乎所有的分类方法中，因此被普遍用来评价分类器的优劣程度。③余一法余一法是交叉验证法的极端情况，其每个q的大小为l。若IDl为栉，则(2．2)式改写为：归I：}萎岛㈤显然，该方法的计算复杂度极高，不过得到的准确度也是最高的。2．3多分类器融合2．3．1多分类器融合概述将多个分类器得到的分类信息进行综合，从而得出最终的分类结果，称为多分类器融合125,261。在不同的领域它有不同的叫法，如多分类器联合(CombinationofMultipleClassifiers)，分类器集成(ClassifierEnsembles)等等[2al。多分类器融合方法的突出优点是可以综合不同分类器得到的分类信息，避免单一分类器可能存在的片面性，从而提高分类的准确性。多分类器融合的方法一般按照拓扑结构分为串行 重庆大学硕士学位论文2分类挖掘与多分类器融合组合、并行组合、层次级联三类。①串行组合在图2．2的串行组合结构中，多个分类器处于一个线性序列中，序列中的每个分类器使用随后的分类器的特征空间，最后一个分类器使用整个特征空间。按照序列的顺序，分类器的结构越来越复杂，分类精度越来越高，但同时分类速度也越来越慢。分类时按顺序先使用结构简单的分类器，当一个分类器的决策结果低于预先设定的可信度水平时被拒绝时，激活下一个分类器。竺斗磊卜寸砷⋯．4磊iP竺I．．．．．．．．．．．．．．．．．．．．．．．．．．．_JI．．．．．．．．．．．．．．．．．．．．．．．．．．．JI．．．．．、．．．．．．．．．．．．．．．．．．．．．．_J图2．2多分类器串行组合Fig．2．2Serialcombinationofmultipleclassifiers②并行组合并行组合根据最终输出结果获得方式的不同分为多分类器融合和多分类器选择两类，其结构如图2．3所示，图中的组合器对应的两类方法分别是融合器和选择器。输图2．3多分类器并行组合Fig．2．3Parallelcombinationofmultipleclassifiers1)融合器按融合器输入及输出信息的抽象程度，融合一般分为三个层次，即数据级融合、特征级融合和决策级融合。其中，决策级融合是对每个分类器执行一个判断得出一个独立的判定，再对来自每个分类器的判定进行融合。本文所说的融合指决策级融合，即多个分类器都在同样的特征空间上进行训练，在整个空间上的性能被认为近似相同，根据各个分类器的整体性能将这些分类器的输出结果按某种14 重庆大学硕士学位论文2分类挖掘与多分类器融合方式结合在一起来达到“共识”，得到最终的分类决策。根据分类器不同的输出结果形式，融合器可以分为三个层次的融合，即抽象层、排序层和度量层。2)选择器虽然各个分类器都在同样的特征空间上进行训练，但是分类器在特征空间中不同区域的性能存在差异。选择器就是要找出在输入样本周围区域中具有最优局部性能的分类器，并以该分类器的输出作为整个系统的输出结果。多分类器选择方法可以分为静态分类器选择和动态分类器选择两类：静态分类器选择方法在训练阶段对特征空间进行划分，为每个区域选择性能最优的分类器或是为每个分类器选择能达到其最优性能的区域，后者可能效率更高，但往往难以实现；动态分类器选择方法在分类操作阶段选择做出最终决策的分类器，通常根据分类器对当前决策的确定性高低进行选择(确定性是对分类器性能的估计)，确定性最高的分类器被选中。图2．4多分类器层次级联Fig．2AHierarchicalconcatenationofmultipleclassifiera③层次级联层次级联也称为混合组合，是串行组合和并行组合相结合的产物，如图2．4所示。分层组合从信息量最少的层次开始，在相应层次上组合各个成员，得到结果属于下一信息层次的中问层分类器，再将中间层分类器与相应层次的成员分类器 重庆大学硕士学位论文2分类挖掘与多分类器融合组合，如此可以使各个分类器的信息得到最大程度的利用。2．3．2融合的有效性问题在研究多分类器融合时，常常会面临着这样一些深层次的问题：即为什么能够建立一个有效的组合?为什么不能找到和融合方法一样好的单个分类器?至少有三个原因可以用来解释这些问题[271。在说明这些原因之前，首先考虑机器学习的本质。机器学习算法通过搜索可能的假设空间日以找到最精确的假设，即能最好地近似或逼近未知函数F的假设。如果假设空间日很大，那么就需要大量的训练数据才可能搜索到比较好的近似函数。需要组合的第一个原因是，训练数据可能并没有提供足够的信息使得学习算法能够从日中泛化出一个最佳分类器。大多数学习算法考虑的是非常大的假设空间，所以即使去掉了错分训练样本的假设以后，仍会有很多假设得以保留，利用保留下来的假设集，可以很容易地建立组合分类器来尽可能地逼近未知函数F。需要组合的第二个原因是，学习算法有可能无法解决人们所提出的困难的搜索问题。因此，多分类器融合被看作是补偿有缺陷探索算法的一种方法。需要组合的第三个原因是，假设空间H也许并不包含真实函数，，但可能会包含几个对何一样好的近似函数。通过这些近似函数的加权组合，就可以表示日之外的分类函数。综上所述，融合提供了克服假设空间表达能力不足的一种方法。2．3．3多分类器融合的方法多分类器融合方法很多，下面介绍几种有代表性的方法：①投票表决法投票表决是一种最简单的组合分类器方法。它的原理是：由基本分类器对样本进行预测(决策)，每一个基本分类器对自己所预测的类投一票，得到票数最多的类就是样本的最终预测结果。无加权的投票表决具有非常强的鲁棒性。简单投票的一个改进是，基本分类器呜，输出一个类概率估计P(厂(x)=kI^)，它表示的是样本x被基本分类器鬼O=1，2，．．．，工)预测为类k(k=1，2，⋯，置)的概率大小。将所有基本分类器的概率估计进行组合，计算下式的值1LP(厂(工)=后)=÷∑P(厂(x)=kth,)(2．5)J。扣l具有最高概率值的类k就是x的类。这种方法也称为分布求和。Kitler对该问题进行了理论分析∞。他根据不同组合规则对错误评估的敏感程度。提出了一个统一组合规则的框架，这些组合规则包括：乘规则、和规则、最小规则、最大规则和中值规则。“一人一票”的表决原则并没有考虑到不同的基本分类器具有不同的分类特征，16 重庆大学硕士学位论文2分类挖掘与多分类器融合因此，投票过程中自然也无法体现性能高的基本分类器的分类优势。于是，便有了另一种改进的投票表决法——加权投票。加权投票的思想主要是根据基本分类器的不同分类性能，使其在投票时拥有的表决权有所不同，精度高的分类器，就具有较大的权重值。蓬)Bagging与Boosting算法这两种方法都是典型地通过改变训练样本的分布或权重值来操纵训练集，使得多个基本分类器进行组合以后，得到一个性能改进的整体分类器。1)Bagging算法Baggmgl2*l算法的基本思想是：从大小为Ⅳ的原始数据集D中，分别独立随机地采用放回采样的方式，抽取Ⅳ’个数据(N’y，并且有误差‘=^-nI吩(t)≠只I。 重庆大学硕士学位论文3基于多分类器融合的分类算法研究令啦：土ln上生。‘2岛更新每个样本的权蛾癣)=掣×{Z矿if毒斟≥其中，互是一个正规因子，用来确保∑。Df+。(i)=1。endfor④最终的预测输出为：日(x)=Ji妒(∑二q曩O)}。3．1．3AdaBoost算法分析①训练误差及收敛性分析AdaBoost算法能有效的降低训练集的误差，这一点Freund和Schapirel331己经证明，且最终预测的训练误差有上界：去I{f：H“)≠z)l≤去车exp(—乃，“))=兀刁(3·1)其中厂(工)=∑q鸟(x)。应用优化理论，从(3．1)式中可以看出，通过选择q，|j|I可以使得弓最小化：磊=∑Df(i)exp(-ct,y,ht(x,))(3．2)也就是说使其训练错误误差降到最低。对于二值分类问题，根据饵：喜ln!兰，2岛可得到：兀弓=兀[2嗣]．兀l一4砰≤expf-2Zg；1(3．3)令以=去一‘，式中‘为吩的训练误差。从(3．3)式可以看出，当弱分类器略好于随机猜测时(--值分类问题￡<0．5)，训练误差按指数函数下降，并最终能下降到零。AdaBoost算法之前的Boosting算法也有相似的性质。然而，Boosting算法在学习前需要得到己知的下界y。实践中关于这样的边界的知识是很难得到的。而AdaBoost算法可以调整单个弱假设的错误率，所以说是自适应的。一个分类训练算法是否可行，首先要从理论上考察其收敛性，否则，如果算法本身就不可行，更谈不上算法的有效性和精度。一般认为，训练算法的收敛性是指随着训练学习次数的增加，训练误差会逐渐下降，最终达到设计者要求的精度，这样的系统才能作为一个学习系统。如果算法在训练过程中会出现振荡或过学习，即随着学习次数的增加训练误差反而上升或者一直处于上下波动状态，则是不可行的。从上面对AdaBoost算法的训练误差分析可以看出当弱学习算法略好于随机猜测时(--值分类问题E<0．5)，训练误差按指数函数下降，并最终能下降到零，这说明AdaBoost算法具有收敛性。21 重庆大学硕士学位论文3基于多分类器融合的分类算法研究②泛化误差分析上面分析了AdaBoost算法的训练误差，而在实际的机器学习应用中，泛化误差是一个更为令人关注的问题。理论上为了产生最好的分类器，期望AdaBoost算法的训练误差降到零。Schapire和singeg”】用基于样本个数、弱学习分类空间的VC维来衡量泛化误差。根据Baum和Hausslcr的理论，Freund和Schapire推导出AdaBoost算法的最大泛化误差为：多，[日(x)≠y]+6(厨而)(3．4)式中P，H表示在训练集上的经验概率。由(3．4)式可以看出，当r变大时，误差也随之增大，也就是当迭代次数过多时，容易产生过学习(过拟合)。但是在早期的大量实验中，没有发生过过学习现象，更有甚者当训练误差降到零后，其泛化误差还在继续下降，这似乎与(3．4)式矛盾。基于这个实验现象，Schapire等人在Bartlett[351的基础上，用边界的概念来分析这种训练误差为零时泛化误差还在下降的现象：～arginf(x,y)=粥=帮。固其中，I∈卜l，+11，当且仅当测试的最终预测正确时J为+l。Sehapiret3司等人认为，在(3．5)式中，较大的正边界表示可信度高的正确的预测，较大的负边界表示可信度较高的错误的预测；同理，较小的边界表示可信度低的预测。当训练误差降低为零后，在训练空间上的边界仍能提高，由以下式子表示：多，[坍argin／(x,y)≤p]+叫捂】(3．6)一3．2神经网络分类器3．2．1神经网络分类器概述人工神经网络(ArtifidalNeuralNetwork，ANN)是由大量的简单处理单元经广泛并行互联形成的一种网络系统。它是对人脑系统的简化、抽象和模拟，具有人脑功能的许多基本特征。它是对人类神经系统的一种模拟。人工神经网络系统的功能实际上是通过大量神经元的广泛互连，以规模宏伟的并行运算来实现的【”朝。人工神经元(简称神经元)是人工神经网络的基本的单元Ds]。每个构造起网络的神经元模型模拟一个生物神经元，其数学模型是在1943年由w．Mcculloch和W．Pitts提出的，简称MP模型，如图3．1所示。 重庆大学硕士学位论文3基于多分类器融合的分类算法研究图3．1人工神经元结构模型Fig．3．1Structm'emodelofneuron图中，‘，厶⋯．，厶为输入，0；为神经元的输出，％为外面神经元与该神经元连接强度(即权)，0为阈值，／(力为该神经元的作用函数。MP模型方程为q=厂(∑％‘一B)i=I，2，⋯，刀(3．7)其中，％是神经元之间的连接强度，％=o，％(f≠_，)是可调实数，由学习过程来调整。只是阈值，厂(力是作用函数。人工神经元的最基本作用函数有如下4种：①[0，1】阶跃函数俐=锯彗(3．s，②[-1，1】阶跃函数㈨={_!。拦@∞③(．1，1)s型函数，(力=丽1--e-x0．10)④(o，1)s型函数八力=_二=(3．11)3．2．2BP神经网络及其学习算法．BP(BaekPropagation)模型是一种用于前向多层神经网络的反向传播学习算法，由D．Rumelhart和Mc．Clelland于1985年提出。在此之前，虽然己有Wcrbos和Park盯分别于1974年及1982年提出过类似的算法，但只有在D．Rumelhart等 重庆大学硕士学位论文3基于多分类器融合的分类算法研究提出后才引起了广泛的重视和应用。目前，BP算法已成为应用最多且最重要的一种训练前向神经网络的学习算法，也是前向网络得以广泛应用的基础。在人工神经网络中，绝大部分的神经网络模型是采用BP网络和它的变化形式，它是前向网络的核心部分，体现了人工神经网络最精华的部分【3驴9】。BP神经网络(Back．PropagationNeuralNetwork)是一种误差反向传播训练的人工神经网络，它由输入神经元节点、输出神经元节点以及一层或多层隐神经元节点组成，各神经元节点单元一般采用Sigmoid型的作用函数进行运算，它主要用于函数逼近、模式识别、分类和数据压缩。BP神经网络的结构如图3．2所示。输入层隐含层输出层一⋯．一图3．2BP神经网络结构图Fig．3．2Shucn盯eofBPneIlralnetworkylY2yIBP学习规则是一种有导师的学习算法，其主要思想是：对于Ⅳ个输入学习样本(日，B，⋯，昂)及己知与其对应的期望输出样本(写，正，⋯，％)，用网络的实际输出与目标矢量之间的误差来修改其权值，使网络的实际输出与期望输出尽可能地接近，即使网络输出层的误差平方和达到最小。它是通过连续不断地在相对于误差函数梯度下降的方向上计算网络权值和偏差的变化逐渐逼近目标的。网络的学习过程由正向和反向传播两部分组成。在正向传播过程中，输入信息从输入层经隐含层逐层计算传向输出层，每一层神经元的状态只影响到下一层神经元。如果输出层不能得到期望输出，即实际输出与期望输出之间有误差，那么转入反向传播过程，将误差信号沿原来的连接通路返回，通过修改各层神经元的权值，逐次地向输入层传播进行计算，再经过正向传播过程，这两个过程反复运用，使得误差信号最小，当误差达到所希望的要求，网络学习过程结束。以下是BP算法的具体步骤：①从训练集中取一个样本，将其输入信息输入到网络中。②由网络分别计算各层神经元节点的输出。⑧计算网络的实际输出与期望输出的误差。④从输出层反向计算到第一个隐层，按一定原则向误差减少的方向调整网络 重庆大学硕士学位论文3基于多分类器融合的分类算法研究的各个连接权值。⑤对训练集中的每一个样本重复以上步骤，直到对整个训练集的误差达到要求为止。在以上步骤中，关键的是第④步。必须确定如何沿着误差减少的方向调整连接权值。在对它说明之前，先对下面要用到的符号约定如下：ol：节点i的输出；删，：节点，的输入：％：从节点f到节点．，的连接权值；儿，耳：分别为输出层上节点．i}的实际输出(即由网络计算机得到的输出)及期望输出。显然对于节点_，有：哟=∑％q，(3．12)其中Ot=f(netj)，节点_，位于书点f的下一层上，且节点i连接到节点J。在BP算法学习过程中，为了使学习以尽可能快的减少误差的方式进行。P=去∑(‘一n)2(3．13)对误差的计算采用了广义的规则，其误差函数为连接权值的修改由下式计算：黟★(f+1)=阡么(f)+△阡▲(3．14)其中，％O)及％(f+1)分别是时刻f及f+1从节点，至节点．i}的连接权值；△％是权值的变化量。现在的问题是如何计算△阡k。为了使连接权值沿着e的梯度变化方向得以改善，网络逐渐收敛，BP算法取：△％卅袭(3．”)其中，，7为学习因子(o<，7<1)，Eh以下计算得到：由于旦：旦一Onet,(3．16)a％Onetka％’故有蓑2袁莩％q2q(3．·7)令所以有。＆吨。瓦(3．18) 重庆大学硕士学位论文3基于多分类器融合的分类算法研究A％2唧老214q下面分两种情况计算矗。①节点k是输出层上的节点。此时，q=Yk，则￡一ae一&却t42丽。两藏由于(3．19)(3．20)．当=-<珞一几)(3．21)叫‘轰_，(Ⅳeta)(3．蚴所以蟊=一乓一以)，(ne‘)(3．23)A％=，7(耳～Yj)f(netk)Oj(3．24)②节点I不是输出层上的节点。这表示连接权值是作用于隐层上的节点的，此时况按如下计算：4：．黑；要．黑：要f(netD(3．25)‘翻ettaota"kaot、其中，去是一个隐函数求导问题，结果为：蠢2莓吒％(3．26)所以疋=，(嗽)∑氏阡■(3．27)这表明，内层节点的J值起通过上一层节点的6值来计算的。这样，就可以先用(3上5)式计算出最高层(即输出层)上各节点的万值，并将它反传到较低层上，然后用(3．27)式计算出各较低层上节点的占值。每个较低层上节点的声值的计算都要用到与它相邻但层次较高的节点的艿值。在实际应用中，学习因子选的太小，收敛太慢；学习因子选得太大，则有可能修正过头，导致振荡甚至发散。因此一般的做法是在权值公式中加入一个态势项，即：％(f+1)；％(f)一，7暖q+d％(f)一％(f一1)](3．28)其中，口为一常数，称为态势因子，它决定上一次学习的权值变化对本次权值更新的影响程度。 重庆大学硕士学位论文3基于多分类器融合的分类算法研究3．3基于AdaBoost的神经网络融合3．3．1设计思想本文设计的基于AdaBoost的BP神经网络融合分类算法的如图3．3所示。其基本设计思想是：利用多个分类能力一般的BP神经网络分类器作为基本分类器，然后通过AdaBoost算法以特定的方法融合起来，构成一个分类能力更强的强分类器。后一个分类器总是试图弥补前一个分类器的缺陷，因此将它们各自的输出融合，可以获得更好的分类效果。DlD2珥图3．3基于AdaBoost的BP神经网络融合分类算法Fig．3．3BPnaⅡalnetworkfusionbasedonAdaBoost①算法的主要部分基于AdaBoost的BP神经网络融合分类算法的设计主要包括下面几个部分：1)输入样本，记为S={(置，咒)}f=1，2,---,m}，其中互∈X为甩维输入向量，Yl∈Y为样本类别。2)迭代次数，记为r，一般开始的时候可以设置较大的值，然后根据AdaBoost算法实际的分类错误率选择合适的迭代次数。3)基本分类器，作为基本分类器的BP神经网络分类器记为h，危代表用于第f轮迭代的BP神经网络分类器，t=l，⋯，T代表迭代的轮数。4)加权样本，包括样本集墨及其权重分布口，墨为第t轮迭代时用于BP神经网络分类器训练的训练样本，口(i)表示在第，轮迭代时赋给样本(t，只)的权值，其中第1轮迭代时所有样本被赋予一样的初始权重。Df(f)反映了样本(xj，咒)被BP神经网络分类器鬼选入训练集的概率，并根据上一轮BP神经网络分类器而I一。的实际输出与期望输出的差异来调整。5)基本分类器的权重，记为啦，它对应第礴套迭代的BP神经网络分类器鱼， 重庆大学硕士学位论文3基于多分类器融合的分类算法研究反映了该BP神经网络分类器的重要性，即权重越大越重要。啦根据啊的分类效果来确定，分类效果越好权重越大。6)输出结果，记为日表示。经过r轮迭代后AdaBoost算法得到一个BP神经网络分类器序列{栩，⋯，％}，以及与之对应的权重序列{％，⋯，断}。算法得到的最终分类函数日是对r个BP神经网络分类器输出结果进行加权投票。②基本分类器的构成设计基于AdaBoost的BP神经网络融合分类算法的另外一个重要部分是确定作为基本分类器的BP神经网络的结构。可以对BP神经网络的结构和参数进行优化和选择：1)输入层与输出层神经元数目的选择BP神经网络分类器的输入层与输出层的神经元个数需要根据具体问题来设计，只是在设计中应该注意减小系统的规模，使学习的时间和系统的复杂性尽量减小。2)隐层数的设计1989年RobertHecht-Nielson证明了对于任何在闭区间内的一个连续函数都可以用具有一个隐层的BP网络来逼近，因而一个三层的BP网络可以完成任意的N维到M维的映射。因此本文采用具有一个隐层的BP网络。3)隐层神经元个数的选择对于隐层神经元个数的选择是一个十分复杂的问题，目前还没有现成的解析式来表示，其数目与问题的要求、输入输出层的神经元数目都有直接的关系。一般来说，网络隐层神经元太少可能不能训练好网络或者网络不强壮，不能识别以前没有学习过的样本，容错性差；但隐层神经元太多又会使学习时间过长，使网络的泛化能力降低。一般可以参照以下几个公式：_Ⅳ／L、七<∑c⋯(3．29)M＼’／式中的k为样本数，h为隐含层神经元个数，Ⅳ为输入层神经元个数。h=0．5(N+M)+口(3．30'其中肘为输出层神经元个数，Ⅳ为输入层神经元个数，口为1至10之间的常数。h=l092N(3．31)Ⅳ为输入层神经元个数。4)神经元作用函数的选择本文BP神经网络分类器的输入、输出和隐含层神经元都采用Sigmoid型的作用函数进行运算。 重庆大学硕士学位论文3基于多分类器融合的分类算法研究3．3．3算法描述①算法流程基于AdaBoost的BP神经网络融合分类算法的流程，大概分为以下几个阶段：1)算法的初始化。主要是AdaBoost算法迭代次数T，BP神经网络基本分类器曩的网络参数，以及样本权重Df(f)的初始化；2)基分类器的训练。根据训练样本的分布口，选取用于训练BP神经网络分类器的样本置，训练结束后得到一个BP神经网络分类器鸟，并可以计算得到该分类器的误差￡。3)基本分类器权重的确定。根据第，轮迭代中BP神经网络分类器啊的误差‘，计算出该分类器的权重口．。4)训练样本权重的调整。根据上轮迭代嘭的结果，调整训练样本的分布D，+．。5)得到最后的分类函数。根据r轮迭代得到的r个BP神经网络分类器{啊，⋯，％}，及其对应的权重{q，⋯，嘶}，加权投票得到最后的分类函数日。上面所提到的基于AdaBoost的BP神经网络融合分类算法有三个非常重要的问题：1)如何调整样本的权重口(i)。2)如何训练BP神经网络基本分类器鬼。3)如何把得到的基本分类器按一定权重口。融合起来。从具体的算法流程图3．4中可以看出第1和第3这两个问题都与系数啦有关。 重庆大学硕士学位论文3基于多分类器融合的分类算法研究图3．4基于AdaBoost的BP神经网络融合的流程图Fig．3．4FlowchartofBPNNfusionbasedonAdaBomt 重庆大学硕士学位论文3基于多分类器融合的分类算法研究②基本分类器的训练流程对于基于AdaBoost的BP神经网络融合分类算法的第2个问题，BP神经网络训练的流程如图3．5所示。图3．5BP神经网络训练流程图Fig．3．5ThetrainingflowchartofBPNN31 重庆大学硕士学位论文3基于多分类器融合的分类算法研究3．4本章小节本章设计了基于AdaBoost的神经网络融合的分类算法。分析了AdaBoost算法提出的背景及其特点，通过对AdaBoost算法进行深入分析，选择弱分类器BP神经网络作为基本分类器，设计了基于AdaBoost的神经网络融合分类算法。着重阐述了该算法的设计思想，包括算法的主要组成部分和基本分类器的构成；阐述了算法的流程，以及调整样本权重、训练BP神经网络基本分类器、确定基本分类器权重三个关键的问题。 重庆大学硕士学位论文4多分类器融合在学生信用分类的应用本章结合项目研究的内容，将多分类器融合方法应用于学生信用分类，是在信用分类一个新是新的尝试。首先根据学生信用分类的主题确定选取相关的数据项，并根据分类挖掘的需要进行数据预处理；然后建立基于多分类器融合的学生信用分类模型，并通过仿真实验对算法进行分析；最后在高校学生个人信用评价管理系统的基础上设计并实现信用分类模块。4．1基于多分类器融合的学生信用分类模型4．1．1学生信用分类及数据选取学生信用分类是社会个人信用建设的重要组成部分，同时也是分类挖掘的一个新的应用领域。我国的国家助学贷款是以帮助学校中经济困难的学生支付在校期间的学费和日常生活费为目的，运用金融手段支持教育，资助经济困难学生完成学业的重要形式。同时，国家助学贷款工作是支持高等教育发展，深化高等教育改革，保证教育机会、平等，维护社会稳定的重要举措。国家助学贷款的风险中关键的是大学生的“信用”意识淡薄，这是助学贷款受阻的关键原因。国家助学贷款属于政策性的信用贷款，由于国家助学贷款市场上存在着非对称性信息现象，我国尚未建立起一个全国性的个人信用体系，因此银行在贷款前就无法有效审查借款人的资信情况。另一方面，助学贷款唯一的偿还资金来源就是借款人的未来收入，随着近年来毕业生就业形势日趋严峻，借款人的未来收入不确定，新政策虽然延长了学生贷款的还款年限并提供了人性化的减免措施，但这只能相对缓和还款人的还款压力，甚至从银行角度来看，还款期限的延长意味着贷款管理成本和不确定性的增加，并不能提高其支付能力。近年来随着高校学生人数的扩张，对国家助学贷款的需求一路攀升，但随着还贷高峰的逐步来临，许多高校助学贷款的还款率却比较低。目前，由于部分学生缺乏诚信所出现的到期不还贷的现象，导致银行对学生的诚信度产生怀疑，并采取减少甚至是停止对学校的助学贷款业务。这直接影响到高校今后新生的贷款问题，同时给学校带来负面的影响。因此，高校应加强对助学贷款的审核及追踪管理。在推行国家助学贷款的过程中，学校事实上成为连接银行和学生的中介媒体，是贷款的组织者。从实际效果看，学校也是国家助学贷款的直接受益者，而且是最大最先的受益者，因为国家助学贷款在很大程度上减少了学生的欠费率。因此，高校要加强对助学贷款的审核，从源头上把好关。因此，有必要结合学生助学贷款的还款情况对学生的信用情况进行分类，为学校贷款中心及银行发放助学贷款提供决策依据，同时也有助于培 重庆大学硕士学位论文4多分类器融合在学生信用分类的应用养学生的诚信意识[39-o]。由于在校大学生是个相对特殊的团体，因此学生信用分类的数据项不但与学生本身的经济状况有关，而且还与学生在校的表现有密切关系。本文以重庆大学为试点，充分利用现有的信息资源和网络资源，从学校的学工部、教务处、财务处、勤工助学中心等各部门采集学生信用相关数据。现阶段可以采集到的信用相关数据项来自公共信息和经济信息两个方面。根据调研的情况，本文从公共信息、经济信息两个方面选择以下数据项用于学生信用分类，所选的数据项如表4．1所示。①信用类别将学生信用分类的类别对应于学生助学贷款的还款情况。助学贷款的还款情况分为“按时’’和“不按时”两种，即信用类别对应为‘好’’和“差”两类。②公共信息的数据项包括：学习成绩，是对学生在校各科成绩计算的结果，来自学校教务处；荣誉嘉奖次数，包括由学校、国家、教育系统颁发的各种荣誉称号和奖励，主要来自学工部的统计数据；违规违纪次数，包括学校对学生提出的警告、记过、留校察看、开除学籍等处分，主要来自各学院的统计数据。③经济信息的数据项包括：奖学金收入一包括学校记录的各种奖学金，来自学工部的统计数据；打工收入，是指学生在校期间参加勤工俭学或其它兼职工作的收入，来自勤工助学中心的记录；拖欠学费，包括是指学生在校期间拖欠的学费的情况，来自财务处的记录。表4．1学生信用分类的数据项Table4．1Dataitemsforstudentcreditclassification数据来源数据项属性值助学贷款信用类别按时(好)，不按时(差)学习成绩《0-1001公共信息荣誉嘉奖次数∈Ⅳ违规违纪次数∈Ⅳ奖学金收入∈置经济信息打工收入∈置拖欠学费∈R 重庆大学硕士学位论文4多分类器融合在学生信用分类的应用4．1．2分类挖掘的数据预处理在确定分类挖掘的对象之后，根据选定的数据项，需要对数据进行必要的预处理，主要包括数据的净化和数据的转换【删。①数据的净化数据的净化可以在数据装载入挖掘数据集之前进行，也可以在装载后进行。数据的净化技术一般有基于规则的方法、可视化方法和统计学方法。基于规则的方法是根据字段定义域的约束和其它字段的关系对该字段的每一项数据进行评估；可视化方法是以图的形式显示数据集的有效轮廓，从而可以辨别脏数据；统计学方法是通过统计技术填补丢失的数据和更正错误的数据。处理空缺值的方法有：忽略元组、人工填写空缺值、使用一个全局常量填充空缺值、使用属性的平均值填充空缺值、使用最可能的值填充空缺值等方法。消除噪声数据的方法有：分箱、计算机和人工检查结合、回归等方法。清理不一致数据可以采用人工的方法来加以更正，有些可以采用知识工程工具来检测违反规则的数据并加以修正。②数据的转换对基于AdaBoost的BP神经网络融合分类算法来说，还需要把数据转化成一种能够被BP神经网络分类器接受的形式。这里主要需要解决输入和输出数据的归一化的问题。根据一般神经元作用函数的不同，大多数神经网络模型只能接受(o，1)或(一l，+1)这个区间的数据值。归一化可以加快神经网络的权值和阀值的修正过程，还可以摆脱数值绝对大小的影响。归一化的方法很多，常用的有最大最小值法，指数函数法等。本文采用最大最小值法，如(4．1)式所示，对学习成绩、荣誉嘉奖次数、违规违纪次数、奖学金收入、打工收入、拖欠学费等量化输入数据项进行归一化。而=兰二竺max—mill’ifrain<五