硕士毕业论文-机器学习算法在生物信息学中的应用.doc

上海大学博士学位论文 2008年4月中图分类号： 单位代号：10280密 级： 学 号：05720159 硕士学位论文SHANGHAI UNIVERSITYMASTER DISSERTATION题目机器学习算法在生物信息学中的应用作 者 金雨欢学科专业 物理化学导 师 陆文聪 教授完成日期 二零零八年五月XI上海大学硕士学位论文2008年5月A Dissertation Submitted to Shanghai University for the Masters Degree in ScienceUsing Machine Learning MethodsIn BioinformaticsM. D. Candidate：Jin YuhuanSupervisor：Prof. Lu WencongMajor：Physical ChemistryScience College, Shanghai UniversityMay, 2008摘 要20世纪后期，人类和其他生物物种基因组学的研究飞速发展，生物信息的增长惊人，生物科学技术极大地丰富了生物科学的数据资源。数据资源的急剧膨胀迫使人们寻求一种强有力的工具，运用新的技术手段对复杂的海量生物信息进行储存、管理、分析和研究，组织这些数据，以利于储存、加工和进一步利用，有效管理、准确解读、充分使用这些信息。本文的工作就是应用机器学习方法来对生物信息数据进行分析，处理。本文的主体工作分为三个部分：1. 用集成学习算法研究蛋白质亚细胞定位预测。蛋白质的亚细胞位置，是蛋白质的一个重要性质，能够表明蛋白质在细胞中的功能。预报蛋白质亚细胞位置，在基因注释和药物设计工作中，都扮演了很重要的角色。本文用基于序列氨基酸组成成分进行蛋白质序列特征编码，选用了AdaBoost与Bagging这两种最重要的集成学习算法来对训练数据集进行建模。在建模过程中，分别尝试了用4种不同的弱分类器来训练样本，并用基于交叉验证法的建模结果来对建模参数进行优化。结果表明：用AdaBoost随机森林算法作为弱分类器时有最好的建模结果，交叉验证预报正确率为76.51%；Bagging用最近邻算法作为弱分类器时有最好的建模结果74.21%。用独立测试样本集对训练好的预报模型进行验证，AdaBoost与Bagging的最大预报正确率分别为80.75%和80.90%，优于SVM方法所得结果（SVM的训练模型交叉验证预报正确率为76.46%，独立测试样本集预报正确率为76.98%）。2. 用支持向量机回归算法（SVR）对1-苯基-2氢-四氢三嗪-3-酮同系物进行QSAR研究。1-苯基-2氢-四氢三嗪-3-酮同系物可用作5-脂抗氧化酶抑制剂。本工作中用来自文献的12个拓扑指数与Hyperchem计算得到的17个物理化学参数作为初始分子描述符，然后用基于SVR留一交叉验证法进行变量筛选，最终得到8个分子描述符用于建立预报模型。该模型的留一交叉验证法的RMSE（最小残差平方和）为0.2834，作为对比，多元线性回归算法（MLR）、偏最小二乘法（PLS）、人工神经网络（ANN）的RMSE分别为0.4301、0.4379 、0.4039；SVM与MLR、PLS、ANN的独立测试集验证结果的RMSE分别为0.2834、0.3316、0.3470和0.3581。3. 提出了一种基于MVC架构的服务器设计途径，建立了基于已得模型的在线预报服务器。建立生物信息学预报模型的目的是为了提供对生物信息中的未知对象进行预报的工具，使得预测结果能够为他人所用。为了更好的达到这个目的，将研究得到的预报模型提供给所有相关领域的研究人员，建立在线预报服务器是一条有效途径。关键词：生物信息学，定量构效关系（QSAR），机器学习，集成学习，支持向量机（SVM），支持向量回归算法（SVR），AdaBoost，Bagging，亚细胞位置定位，5-脂抗氧化酶抑制剂，在线预报服务器AbstractIn the late 20th century, genomics research in human and other living species had been developed rapidly, and the information of biology increased by surprised speed. The information source of bioscience was great enriched by bioscience techniques. The rapidly expanding of information source force people to search for a powerful and effective tool, which uses new techniques to the storage, management, analysis and research of the mass of complex biological information, then organize these data to be better in storage, processing and utility.Machine learning methods were used to analyse and process the data of biological information in this work. The main work of the paper contains three parts:1. Using integrated learning algorithm to study the prediction of protein subcellular localization. Protein subcellular localization, which tells where a protein resides in a cell, is an important characteristic of a protein, and relates closely to the function of proteins. The prediction of their subcellular localization plays an important role in the prediction of protein function, genome annotation and drug design. In this work, the sequences were coded based on the sequence amino acid composition, and the models were built using AdaBoost and Bagging, which were the most important algorithm of the integrated learning algorithm. During the modeling process, four different weak classifiers were used in training data, and the modeling parameters were optimized based on the result of cross-validation of the models. As a result, AdaBoost got the best model with a correct rate of 76.51% in cross-validation prediction, when random forest algorithm was selected as the weak classifier; Bagging got the best model with a correct rate of 74.21% in cross-validation prediction, when KNN was selected as the weak classifer. Then, independent dataset test was used to validate the trained model, the result of AdaBoost and Bagging were 80.75% and 80.90% of prediction correct rate. As comparison, SVM was used, and the result of training cross-validation was 76.46% of correct rate, and the independent dataset test was 76.98% of correct rate.2. Using support vector machine regression algorithm to take QSAR study in 1-phenyl 2H-tetrahydro-triazine-3-one analogues. 1-phenyl 2H-tetrahydro-triazine-3-one analogues could be used as 5-lipoxygenase inhibitors. In this work, 12 topological indexes and 17 physical chemical parameters caculated by Hyperchem were used as the original molecular descriptors. Then, the descriptors were filtered based on SVR leave-one-out cross validation. As a result, 8 descriptors were selected to build the predicting model. The RMSE of this model using leave-one-out cross validation was 0.2834. As comparison, the RMSE value of multiple linear regression (MLR), partial least squares (PLS) and artificial neural network (ANN) were 0.4301, 0.4379 and 0.4039, respectively. The independent data sets of SVR, MLR, PLS, and ANN were tested to demonstrate the generalization alility of these models, and the results in RMSE values were 0.2834, 0.3316, 0.3470, and 0.3581, respectively.3. Building online predicting server based on the gained model. The aim of building the bioinformatics predicting model is to supply a tool to predict unknowns in the biological information, and make the information to benefit human. Building online predicting server is an effective way. The predicting models available online can be used by experimental researchers. In this work, a design of server based on MVC construction was brought out, which could increase the efficiency of building a series of online predicting server.Keywords: bioinformatics, quantitative structure activity relationship(QSAR), machine learning, integrated studying, support vector machine(SVM), support vector machine regression alogrithm(SVR), AdaBoost, Bagging, subcellular localization, 5-lip inhibitors, online prediction server.目录摘要VIAbstractVIII目录X绪论11.1生物信息学简介11.2 机器学习算法在生物信息学中的应用21.3 QSAR简介41.4 论文的主要内容5第一章机器学习算法62.1 决策树算法62.1.1 C4.5算法72.1.2 随机决策树算法92.1.3 随机森林算法102.2. 集成学习算法112.2.1 集成学习算法概述112.2.2 AdaBoost算法142.2.2.1 Boosting算法介绍142.2.2.2 Adaboost算法描述152.2.3 Bagging算法172.2.3.1 Bagging 算法的提出172.2.3.2 Bagging算法描述182.3 SVM算法192.3.1 统计学习理论192.3.2 支持向量分类算法212.3.2.1 最优分类面212.3.2.2线性可分的情况212.3.2.3非线性可分情况232.3.3 支持向量回归算法232.3.3.1 -不敏感损失函数232.3.3.2 线性回归情况242.3.3.3 非线性回归情况252.3.4 支持向量机核函数262.4 本章小结28第二章用集成学习算法预测亚细胞定位293.1 蛋白质亚细胞定位的生物学基础303.2 亚细胞定位预测方法现状333.3 数据集以及特征参数的提取363.4 实验与分析373.4.1 预报模型参数的选择373.4.2 预报模型393.4.3 预报模型验证393.4.4 分析与讨论403.5 本章小结41第三章5-脂氧化酶抑制剂的QSAR研究424.1 引言424.2 材料和方法434.2.1 数据集434.2.2 计算机硬件与软件434.2.3 分子描述符434.2.4 基于支持向量回归算法的特征选择444.3 结果和讨论444.3.1 建模变量的选择444.3.2 SVR模型参数的选择444.3.3 SVR模型484.3.4 SVR模型验证484.3.5 讨论494.3.5.1SVR参数的讨论494.3.5.2 敏感性分析494.4 本章小结51第四章在线web预报服务器的建立535.1 J2EE技术与MVC模式535.1.1 J2EE概述535.1.2 J2EE分布式多层应用模型544.1.3 MVC模式565.1.4 基于J2EE的MVC模式575.2 系统的总体设计595.2.1 系统的结构设计595.2.1 系统环境与开发工具605.3 系统的详细设计615.4 已完成的在线web预报服务器635.5 本章小结64第五章总结与展望656.1 全文总结656.2 工作展望66参考文献67附录一. 1-苯基-2氢-四氢三嗪-3-酮同系物结构及活性值数据76攻读硕士期间发表及已录用论文78致谢7983第一章 绪论1.1生物信息学简介20世纪后期，人类和其他生物物种基因组学的研究飞速发展，生物信息的增长惊人，生物科学技术极大地丰富了生物科学的数据资源。数据资源的急剧膨胀迫使人们寻求一种强有力的工具，运用新的技术手段对复杂的海量生物信息进行储存、管理、分析和研究，并组织好这些数据，以利于储存、加工和利用，进而达到有效管理、准确解读、充分使用这些信息的目的。生物信息学便是在急速上涨的生物信息数据海洋中应运而生。美国人类基因组计划实施五年后的总结报告中,对生物信息学作了以下的定义：生物信息学是一门交叉学科,它包含了生物信息的获取、处理、储存、分发、分析和解释等在内的所有方面,它综合运用数学、计算机科学和生物学的各种工具,来阐明和理解大量数据所包含的生物学意义。1目前生物信息学的主要任务是研究生物分子数据的获取、存储和查询，发展数据分析方法，研究内容主要包括三个方面：第一， 收集和管理生物分子数据，将各种数据以一定的表示形式存放在计算机中，建立数据库系统并提供数据查询和数据通讯工具，使得生物学研究人员能够方便地使用这些数据，并为信息分析和数据挖掘打下基础。目前国际上已建立起许多公共生物分子数据库，包括基因图谱数据库、核酸序列数据库、蛋白质序列数据库、生物大分子结构数据库等，由专门的机构建立和维护负责收集、组织、管理和发布生物分子数据，并提供数据检索和分析工具，向生物学研究人员提供大量有用的信息，最大限度地满足他们的研究和应用需要，为生物信息学研究服务。迄今为止,生物学数据库总数已达500个以上。在DNA序列方面有GenBank、EMBL和DDBJ等。在蛋白质一级结构方面有SWISS-PROT、PIR和MIPS等。在蛋白质和其它生物大分子的结构方面有PDB等。在蛋白质结构分类方面有SCOP和CATH等。1第二， 进行数据处理和分析，通过信息分析发现数据之间的关系提取本质规律，进而上升为生物学知识。在此基础上解释与生物分子信息复制、传递、表达有关的生物过程，并解释生物过程中出现的故障与疾病的关系，帮助发现新药物作用目标，设计新药物分子，为进一步的研究和应用打下基础。目前生物信息学的主要研究对象是基因和蛋白质。在蛋白质分析方面，着重分析蛋白质序列与蛋白质结构及功能之间的关系，预测蛋白质的功能，研究蛋白质家族关系开展进化分析。面对大量蛋白质序列数据，传统的计算方法越来越显示出不足，借助机器学习模式识别的方法弥补传统试验方法的不足，是目前生物信息学领域普遍使用的方法2。本论文研究基于机器学习理论和算法，通过对蛋白质序列分析，进而实现亚细胞位置预测的工作。第三， 开发分析工具和实用软件解决具体问题，为生物信息学的应用服务，如生物分子序列比较工具、基因识别工具、生物分子结构预测工具、基因表达数据分析工具等。到目前为止，各国研究人员开发了许多有应用价值的软件产品，如用于生物信息数据库检索的SRS和Entrez，用于序列同源性分析的BLAST3,4和FASTA5,6，以及用于多序列比对的Clustw7等。为方便同行使用，本论文的部分研究工作已经通过Internet向全世界生物学家提供开放性服务。1.2 机器学习算法在生物信息学中的应用机器学习的研究主旨是使用计算机模拟人类的学习活动,它是研究计算机识别现有知识、获取新知识、不断改善性能和实现自身完善的方法。这里的学习意味着从数据中学习,它包括有指导学习(Supervised Learning)、无指导学习(UnsupervisedLearning)和半指导学习(Semi-Supervised Learning)三种类别。常见的有指导学习包括:决策树、Boosting与Bagging算法、人工神经网络和支持向量机等。8机器学习算法在生物信息学中的应用主要包括四个方面：9第一， 在序列比对分析中的应用。序列比对是生物信息学的基础。基本问题是比较两个或两个以上符号序列的相似性。从20世纪80年代以来,人们发展了半经验的直观算法。它们可以很快地给出较好的结果,但不能保证所得结果是最优的。另外,还有动态规划算法、神经网络和隐马尔科夫算法。目前已用于序列对比分析的方法主要有:NeedlimanWunsch动态规划算法, Smith Waterman算法及Blast Fasta等相似性比较程序。通过它们可进行两序列、多序列、局部序列乃至完整基因组的比较。目前,基因的比较研究也必须从基因的比较上升到对不同进化水平的生物在整个基因层面上的比较研究。第二， 在人类基因组研究中的应用。随着人类基因组研究的发展,利用机器学习方法进行基因识别被广泛使用。这些方法包括神经网络算法、基于规则的方法、决策树和概率推理等。此外,基于隐马尔科夫模型EM训练算法、Viterbi序列分析算法以及FDR(False DiscoveryRate)方法都有成功的应用成果。发现新基因和单核苷酸多态是当前国际上基因组研究的热点。生物信息学的方法是发现新基因的重要手段。第三， 在蛋白质组研究中的应用。这里包含两个方面，蛋白质功能预测和蛋白质结构预测：a， 蛋白质功能预测主要是分析目标蛋白质是否和具有功能信息的已知蛋白质的相似性。一般步骤为先通过蛋白质序列数据库比较来确定其功能。利用Blast和Fasta工具与蛋白质序列库中的序列进行同源性比较。然后通过组成蛋白质的20种氨基酸的物理和化学性质,分析已知或未知蛋白质的性质,如等电点/分子量、疏水性、跨膜螺旋、卷曲螺旋及信号肽等。最后与保守的基序和图形数据库比较判断功能。b， 蛋白质结构预测的目的是利用已知的一级序列来构建出蛋白质的立体结构模型,对蛋白质进行结构预测需要具体问题具体分析,在不同的已知条件下对于不同的蛋白质采取不同的策略。目前利用机器学习方法预测蛋白质空间结构的方法主要有折叠识别以及神经网络、隐马尔科夫、支持向量机、AdaBoost等方法。如Cai等人10使用支持向量机网络模型对蛋白质二级结构分类。第四， 在生物芯片研究中的应用。生物芯片技术检测及分析技术是生物信息学中目前实用性较强的研究领域。生物芯片主要包括基因芯片(GeneChip)或称DNA芯片(DNAChip)、蛋白芯片(ProteinChip)和芯片实验室(Lab-on-a Chip)等。基因芯片是生物芯片中研究最早、最先形成商品化产品,并已取得广泛应用。机器学习的许多方法都可以直接应用于基因芯片分析,如序列比较方法、贝叶斯神经网络方法和聚类方法等。1.3 QSAR简介化合物的性质/活性是化学的基本研究内容之一，徐光宪先生将物质结构与性能的定量关系称为化学的第二根本规律，并将其列为二十一世纪化学的四大难题（中长期）之一10。化学家们普遍认为，化合物所表现出来的各种性质/活性与化合物的结构密不可分，即性质/活性是结构的函数。这也是结构性质/活性关系（Structure Property/Activity Relationship, SPR/SAR）的基本假设。早在1868年，Crum-Brown和Fraser提出了化合物的分子结构C和生物活性可由方程表示：，这是QSAR方面的第一个方程11。后来人们发现，化合物拓扑结构是决定其化学性质的重要因素。当时只研究了少部分的化合物结构参数与其活性关系，如取代基的电子效应(Hammett的常数)，立体参数(Taft参数)以及疏水性参数(Hansch的分配常数)。到二十世纪30年代，Hammett在其经典著作Physical Organic Chemistry中提出了线性自由能关系LFER(Linear Free Energy Relationship)，推动了化合物构效关系研究的深入发展。20世纪40年代起，化学家开始发现分子和其它化学物质可以很方便地用多种不同的矩阵表示12,13，化学图的概念及拓扑指数（图论指数）14,15的引入使表征分子结构并进行化合物的构效关系研究有了一个基本工具。而后在二十世纪60年代，Hansch16,17和Free、Wilson18,19的研究开始建立在定量的基础之上。他们用统计方法对实验数据进行归纳总结并建立结构-活性关系表达式，探讨结构变化与生化活性之间的关系，标志着QSAR时代的开始。二十世纪70年代以后，随着生物化学、分子生物学、统计学和计算机科学的快速发展，SPR/SAR研究提高到了一个新的水平。一方面，表征分子的结构参数不断丰富，在传统物理化学参数以外，更多地使用拓扑参数15,20-23、电子参数24-26来表征基团结构；另一方面，一些新的建模方法也被引入到SPR/SAR的研究中，除了传统的多元线性回归、偏最小二乘回归和主成分分析等算法以外，遗传算法27,28、人工神经网络29,30和支持向量机方法31,32等逐步引入了定量构效关系研究。二十世纪80年代后，考虑分子三维构象的3D-QSAR也逐步引起了研究者的关注。1979年Crippen提出的距离几何学方法33、1980年Hopfinger等人提出的分子形状分析方法34、1988年Cramer等人提出的比较分子场方法(CoMFA) 35是3D-QSAR中最常用的手段。但在化学领域，由于研究体系与数据量的差异，2D-SPR/SAR仍占主导地位。1.4 论文的主要内容本文运用机器学习技术对蛋白质序列的亚细胞定位数据集以及一类有机同系物进行研究，建立起了用于蛋白质序列亚细胞定位的预测模型和用于5-脂氧化酶抑制活性预测的QSAR模型。并运用J2EE技术，实现基于上述模型的在线预报功能。本文的主要内容分为三个部分，第一部分介绍了常用的机器学习算法，以及它们的原理。第二部分介绍了预测模型的具体构建方法与构建过程。第三部分介绍了在线预报系统的实现原理与具体实现方法。本文的主要工作成果在于：1.建立起了用于蛋白质序列亚细胞定位预报模型和5-脂氧化酶抑制活性预测模型；2.通过构建基于上述模型的在线预报服务器，使预报模型能够为领域专家，特别是实验工作者所用。第二章 机器学习算法机器学习是人工智能研究较为年轻的分支,它的发展过程大体上分为四个时期。第一阶段是20世纪50年代中叶到60年代中叶,属于热烈时期。在这个时期,所研究的是“没有知识”的学习,即“无知”学习。其研究目标是各类自组织系统和自适应系统,其主要研究方法是不断修改系统的控制参数和改进系统的执行能力,不涉及与具体任务有关的知识。本阶段的代表性工作是:塞缪尔(Samuel)的下棋程序。但这种学习的结果远不能满足人们对机器学习系统的期望。第二阶段是在60年代中叶到70年代中叶,被称为机器学习的冷静时期。本阶段的研究目标是模拟人类的概念学习过程,并采用逻辑结构或图结构作为机器内部描述。本阶段的代表性工作有温斯顿(Winston)的结构学习系统和海斯罗思(Hayes-Roth)等的基本逻辑的归纳学习系统。第三阶段从20世纪70年代中叶到80年代中叶,称为复兴时期。在此期间,人们从学习单个概念扩展到学习多个概念,探索不同的学习策略和方法,且在本阶段已开始把学习系统与各种应用结合起来,并取得很大的成功,促进机器学习的发展。1980年,在美国的卡内基梅隆(CMU)召开了第一届机器学习国际研讨会,标志着机器学习研究已在全世界兴起。82.1 决策树算法决策树学习是一种逼近离散值函数的算法，对噪声数据有很好的健壮性，且能够学习析取表达式，是最流行的归纳推理算法之一，已经成功应用到医疗诊断、评估贷款申请的信用风险、雷达目标识别、字符识别、医学诊断和语音识别等广阔领域36,37。决策树分类算法使用训练样本集合构造出一棵决策树，从而实现了对样本空间的划分。当使用决策树对未知样本进行分类时，由根结点开始对该样本的属性逐渐测试其值，并且顺着分枝向下走，直到到达某个叶结点，此叶结点代表的类即为该样本的类。例如，图2.1即为一棵决策树，它将整个样本空间分为三类。如果一个样本属性A的取值为a2,属性B的取值为b2，属性C的取值为c1那么它属于类138。图2.1 一颗决策树实例为了避免过度拟和现象的出现，在决策树的生成阶段要对决策树进行必要修剪。常用的修剪技术有预修剪(pre-pruning)和后修剪(post-pruning)两种。决策树的质量更加依靠好的停止规则而不是划分规则。39获取大小合适的树常用的方法是后剪枝。后剪枝法主要有训练和验证集法，使用统计的方法，最小描述长度准则。其它的剪枝方法有：限制最小结点规模，两阶段研究，不纯度的阀值，将树转变为规则，Tree reduction。没有一种剪枝方法明显优于其它方法。寻找一棵最优决策树主要解决以下三个最优化问题:生成最少数目的叶子，生成的每个叶子的深度最小，生成的决策树叶子最少且每个叶子的深度最小。以上三个问题均已被证明为NP难题，所以,决策树算法一般只能找到一棵近似最优决策树40。常用的决策树算法由CART，ID3，C4.5算法，随机树算法，在下面，对本文中用到的决策树算法进行了详细介绍。2.1.1 C4.5算法41设S为训练集样本总数，共有m类样本，Si为类Ci中的样本数，计算公式为：(2.1.1.1)其中，其中pi是任意样本属于Ci的概率，可用Si/S来估计。设属性X具有v个值，它将S分成v个子集，其中Sj包含S中这样的一些样本，它们在属性X上具有值。以属性X为分类所需的期望熵（条件熵）是：(2.1.1.2)其中sij是子集Sj中属于类Ci的样本数，是sj中的样本属于Ci的概率。属性X的信息增益函数为：(2.1.1.3)信息增益函数对于那些可能产生多分枝的测试倾向于生产大的函数值，但是输出分枝多，并不表示该测试对末知的对象具有更好的预测效果，信息增益率函数可以弥补这个缺陷“信息增益率”是为了去除多分枝属性的影响而对信息增益的一种改进。使用“信息增益率函数”，它同时考虑了每一次划分所产生的子结点的个数和每个子结点的大小（包含的数据实例的个数），考虑的对象主要是一个个地划分，而不再考虑分类所蕴涵的信息量，属性X的信息增益函数为：(2.1.1.4)其中v为该节点的分枝数，si为第i个分枝下的记录个数。依次计算每个属性的信息增益Gain(X)以及信息增益率A(X)，选取信息增益率最大的，但同时获取的信息增益又不低于所有属性平均值的属性作为测试属性，以该属性作为结点，属性的每一个分布引出一个分枝，据此划分样本。要是节点中所有样本都在同一个类，则该节点成为树叶，以该客户类别标记该树叶。如此类推，直到子集中的数据记录在主属性上取值都相同，或没有属性可再供划分使用，递归地形成初始决策树。另外，在节点处记下符合条件的统计数据：该分枝总数、有效数、中止数和失效数。之所以选取信息增益率大而信息增益不低于平均值的属性，是因为高信息增益率保证了高分枝属性不会被选取，从而决策树的树型不会因某节点分枝太多而过于松散。过多的分枝会使得决策树过分地依赖某一属性，而信息增益不低于平均值保证了该属性的信息量，使得有利于分类的属性更早地出现。得到了完全生长的初始决策树后，为了除去噪声数据和孤立点引起的分枝异常，可采用后剪枝算法对生成的初始决策树进行剪枝，并在剪枝过程中使用一种悲观估计来补偿树生成时的乐观偏差。对决策树上的每个非叶子结点，计算该分枝节点上的子树被剪枝可能出现的期望错误率。然后，使用每个分枝的错误率，结合沿每个分枝观察的权重评估，计算不对该节点剪枝的期望错误率。如果剪去该节点导致较高的期望错误率，则保留该子树；否则剪去该子树，最后得到具有最小期望错误率的决策树。2.1.2 随机决策树算法42设属性集为建树提供结构，其中是非决策属性，决策属性是一列有效的类别。表示记录x的属性Fi的值,具体结构描述如下：树中的每个结点表示一个问题;每个分支对应结点分裂属性Fi的可能取值。随机决策树的构造过程:对根结点和分支结点随机的从属性集合中选择分裂属性,在一条分支路径上离散属性仅出现一次,连续属性可以出现多次。且在以下3种情况下停止树的构造：树的高度满足预先设定的阈值;分支结点的事例数太小以至于不能给出一个有统计意义的测试;其它任何一个属性测试都不能更好地分类。在后2种情况下,分类结果标记为训练数据集中最普通的类,或是出现概率最高的类。当对事例X进行分类时,以各随机树输出的后验概率均值最大的类为预测类。下面详细介绍随机决策树的深度选择和数目的选择及其分类。(1)选择树的深度。使用多个随机树的主要特色是多样性导致较高的分类准确率,多样性不与深度成正比关系。研究表明,当i=k/2时得到最大路径数,随机决策树有最佳的效果。(2)选择随机决策树的个数。树的个数N=10时有较低的分类错误率,且可信度大于99.7%。(3)叶子结点的更新。在树的结构建好后对树结点更新,其中叶子结点记录事例被分类为某一预定类别的个数;非叶子结点不记录经过分支的事例数目,叶子中信息形式如:。其中,si表示预测为di类的事例数, 表示决策属性类别。表示某一叶子结点记录的总事例数。(4)分类。当对事例进行分类时,预测为预定类别di的概率。其中,N表示随机决策树的数目;为每棵随机决策树输出的后验概率;S为从根结点开始搜索到合适叶子结点处的事例个数;Si为该叶子结点处训练数据集中标记为di类的数目。在后验概率Pi中找出最大的一个,其所对应的预定类别即为随机决策树最终的输出结果。由于完全随机的选择属性,因而可能会出现某些属性在整个决策树构造过程中没有或很少被选取为分裂属性,特别是当该属性对分类结果有较大贡献时,这种缺少将导致分类正确率的不稳定,当属性数较少时,这种不稳定性将更为明显。2.1.3 随机森林算法43在决策树算法中,一般用选择分裂属性和剪枝来控制树的生成,但是当数据中噪声或分裂属性过多时,它们也解决不了树不平衡。最新的研究表明6,构造多分类器的集成,这样可以提高分类精度.随机森林就是许多决策树的集成.为了构造k棵树,我们得先产生k个随机向量，这些随机向量是相互独立并且是同分布。随机向量可构造决策分类树，简化为。给定k个分类器和随机向量x、y,定义边缘函数(2.1.1.5)其中是示性函数。该边缘函数刻画了对向量X正确分类y的平均得票数超过其它任何类平均得票数的程度。可以看出,边际越大分类的置信度就越高。于是，分类器的泛化误差(2.1.1.6)其中下标X,Y代表的是该误差是在X,Y空间下的。将上面的结论推广到随机森林,。如果森林中的树的数目较大，随着树的数目增加,对所有随机向量趋向于(2.1.1.7)这是随机森林的一个重要特点，并且随着树的增加，泛化误差将趋向一上界，这表明随机森林对未知的实例有很好的扩展。随机森林的泛化误差上界的定义为(2.1.1.8)其中是相关系数的均值,s是树的分类强度。随机森林的泛化误差上界可以根据两个参数推导出来：森林中每棵决策树的分类精度即树的强度S,和这些树之间的相互依赖程度。当随机森林中各个分类器的相关程度增大时，泛化误差上界就增大；当各个分类器的分类强度增大时，泛化误差上界就增大。正确理解这两者之间的相互影响是我们理解随机森林工作原理的基础.2.2. 集成学习算法集成学习(Ensemble Learning)是一种新的机器学习范式，它使用多个(通常是同质的)学习器来解决同一个问题。由于集成学习可以有效地提高学习系统的泛化能力，因此它成为国际机器学习界的研究热点。2.2.1 集成学习算法概述在机器学习领域，最早的集成学习方法是Bayesian Averaging。在此之后，集成学习的研究才逐渐引起了人们的关注。L.K.Hansen和P.Salamon44使用一组神经网络来解决问题，除了按常规的做法选择出最好的神经网络之外，他们还尝试通过投票法将所有的神经网络结合起来求解。他们的实验结果表明，这一组神经网络形成的集成，比最好的个体神经网络的性能还好。正是这一超乎人们直觉的结果，使得集成学习引起了很多学者的重视。1990年，Schapire45通过一个构造性方法对弱学习算法与强学习算法是否等价的问题作了肯定的证明，证明多个弱分类器可以集成为一个强分类器，他的工作奠定了集成学习的理论基础。这个构造性方法就是Boosting算法的雏形。但是这个算法存在着一个重大的缺陷，就是必须知道学习算法正确率的下限，这在实际中很难做到。在1995年，Freund和Schapire46做了进一步工作，提出了AdBaoost算法，该算法不再要求事先知道泛化下界，可以非常容易的应用到实际的问题中去。1996年，Breiman46提出了与Boosting相似的技术Bagging，进一步促进了集成学习的发展。狭义地说，集成学习是指利用多个同质的学习器来对同一个问题进行学习，这里的“同质”是指所使用的学习器属于同一种类型，例如所有的学习器都是决策树、都是神经网络等等。广义地来说，只要是使用多个学习器来解决问题，就是集成学习47,48。在集成学习的早期研究中，狭义定义采用得比较多，而随着该领域的发展，越来越多的学者倾向于接受广义定义。所以在广义的情况下，集成学习已经成为了一个包含内容相当多的、比较大的研究领域。大致上来说，集成学习的构成方法可以分为四种:1. 输入变量集重构法。这种构成方法，用于集成的每个算法的输入变量是原变量集的一个子集。这种方法比较适用于输入变量集高度冗余的时候，否则的话，选取一个属性子集，会影响单个算法的性能，最终影响集成的结果。2. 输出变量集重构法。这种构成方法，主要是通过改变输出变量集，将多分类问题转换为二分类问题来解决。3. 样本集重新抽样法。在这种构成方法中，用于集成的每个算法所对应的训练数据都是原来训练数据的一个子集。目前的大部分研究主要集中在使用这种构成方法来集成学习，如Bagging，Boosting等等。样本集重新抽样法对于不稳定的算法来说，能够取得很好的效果。不稳定的算法指的是当训练数据发生很小变化的时候，结果就能产生很大变化的算法。如神经网络、决策树。但是对于稳定的算法来说，效果不是很好。4. 参数选择法。对于许多算法如神经网络、遗传算法来说，在算法应用的开始首先要解决的就是要选择算法参数。而且，由于这些算法操作过程的解释性很差，对于算法参数的选择没有确定的规则可依。在实际应用中，就需要操作者根据自己的经验进行选择。在这样的情况下，不同的参数选择，最终的结果可能会有很大的区别，具有很大的不稳定性。集成算法的作用主要体现在如下四个方面：1. 提高预测结果的准确性。机器学习的一个重要目标就是对新的测试样本尽可能给出最精确的估计。构造单个高精度的学习器是一件相当困难的事情，然而产生若干个只比随机猜想略好的学匀器却很容易。研究者们在应用研究中发现，将多个学习器进行集成后得到的预测精度明显高于单个学习器的精度，甚至比单个最好的学习器的精度更高。2. 提高预测结果的稳定性。有些学习算法单一的预测结果时好时坏，不具有稳定性，不能一直保持高精度的预测。通过模型的集成，可以在多种数据集中以较高的概率普遍取得很好的结果。3. 解决过拟合问题。在对己知的数据集合进行学习的时候，我们常常选择拟合度值最好的一个模型作为最后的结果。也许我们选择的模型能够很好的解释训练数据集合，但是却不能很好的解释测试数据或者其它数据，也就是说这个模型过于精细的刻画了训练数据，对于测试数据或者其它新的数据泛化能力不强，这种现象就称为过拟合。为了解决过拟合问题，按照集成学习的思想，可以选择多个模型作为结果，对于每个模型赋予相应的权重，从而集合生成合适的结果，提高预测精度。4. 改进参数选择。对于一些算法而言，如神经网络、遗传算法，在解决实际问题的时候，需要选择操作参数。但是这些操作参数的选取没有确定性的规则可以依据，只能凭借经验来选取，对于非专业的一般操作人员会有一定的难度。而且参数选择不同，结果会有很大的差异。通过建立多个不同操作参数的模型，可以解决选取参数的难题，同时将不同模型的结果按照一定的方式集成就可以生成我们想要的结果。集成学习经过了十几年的不断发展，各种不同的集成学习算法不断被提了出来，其中以Boosting和Bagging的影响最大。这两种算法也是被研究得最多的，它们都是通过改造训练样本集来构造集成学习算法。在下面的章节中对这两种算法进行了详细的介绍。2.2.2 AdaBoost算法Kearns和Valiant指出48，在PCA学习模型中，若存在一个多项式级学习算法来识别一组概念，并且识别正确率很高，那么这组概念是强可学习的；而如果学习算法识别一组概念的正确率仅比随机猜测略好，那么这组概念是弱可学习的。Kaerns和valiant提出了弱学习算法与强学习算法的等价性问题，即是否可以将弱学习算法提升成强学习算法的问题。如果两者等价，那么在学习概念时，只要找到一个比随机猜测略好的弱学习算法，就可以将其提升为强学习算法，而不必直接去找通常情况下很难获得的强学习算法。1990年，schapire49 通过一个构造性方法对该问题做出了肯定的证明，其构造过程称为Boosting。1995年Freund50对其进行了改进。在Freund的方法中通过Boosting产生一系列神经网络，各网络的训练集决定于在其之前产生的网络的表现，被已有网络错误判断的示例将以较大的概率出现在新网络的训练集中。这样，