基于Python随机森林算法分析与研究计算机科学与技术专业.docx

摘要1Abstract2第一章引言31.1 背景介绍31.2 Python31.2.1 当代环境下的Python41.2.2 Python的演变41.2.3 Python的特点介绍41.2.4 Python的功能与应用51.3 本文结构和框架6第二章随机森林算法研究与分析72.1 决策树72.1.1 决策树的概念72.1.2 节点分裂72.1.3 决策树分类存在的问题92.2 随机森林分析92.2.1 训练集的随机性92.2.2 特征变量的随机性112.3 随机森林理论概述112.4 随机森林性能指标122.4.1 分类效果性能指标122.4.2 泛化误差和OoB估计142.4.3 随机森林运行效率指标14第三章随机森林算法的实现163.1 决策树的实现163.2 随机森林的构建过程183.2.1 训练集的生成193.2.2 决策树的构成203.2.3 森林的形成203.3 随机森林的构成21第四章随机森林应用与实例分析224.1 随机森林算法应用场合224.1.1 预测能力224.1.2 分类能力224.2 莺尾花分类实例分析234.2.1 数据处理与算法模型23422莺尾花分类实例分析24第五章总结与展望27参考文献28致谢30附录31摘要本文主要讲述如何使用python程序设计语言来实现随机森林算法，以及实现该算法有哪些意义和优点，从而了解到可以解决现实生活中的哪些问题。分类和回归几乎涵盖了我们现实生活中绝大多数问题，而回归问题又可离散化转化为分类，所以本文主要研究分类问题。传统分类算法比如单决策树，都是单个分类器，而将多个分类器集成来进行预测，便是集成学习算法。而集成学习算法代表之一随机森林算法便是本文的一个核心重点，它是以决策树为基础，集成多棵决策树以投票方式输出的结果，应用于很多场合，并在这些场合取得巨大成就。当然，其算法本身还尚未成熟，有很多不足的地方需要改进，尤其是一些特殊情况下，无法实现该算法。本文将针对决策树以及随机森林算法将着重介绍，讲述其演绎过程及这种思想的来源和思想构成原理，以及分析其特点和优势，并且用PythOn将该算法实现，探讨算法改进方法，推动理论性质方面的研究进展。关键字：python；分类回归；决策树；节点分裂；随机森林算法AbstractThisarticledescribeshowtousethePythonprogramminglanguagetoimplementarandomforestalgorithm,andwhataretheadvantagesandadvantagesofimplementingthealgorithm,soastounderstandwhatproblemscanbesolvedinreallife.Classificationandregressionalmostcovermostoftheproblemsinourlife,andregressionproblemsaretransformedintoclassifications.Therefore,thispaperfocusesonclassificationissues.Traditionalclassificationalgorithmssuchassingledecisiontreesaresingleclassifiers,andintegrationofmultipleclassifiersforpredictionisanensemblelearningalgorithm.Theensemblelearningalgorithmrepresentsarandomforestalgorithmisacorefocusofthisarticle,itisbasedonthedecisiontree,theintegrationofmultipledecisiontreestovoteouttheresults,appliedtomanyoccasions,andintheseoccasionsmadegreatachievements.Ofcourse,thealgorithmitselfisnotyetmature,therearemanydeficienciesneedtobeimproved,especiallyinsomespecialcircumstances,thealgorithmcannotbeachieved.Thisarticlewillfocusonthedecisiontreeandtherandomforestalgorithmwillfocusonthedescriptionofthedeductiveprocessandthesourceofthisideaandtheideaoftheideology,aswellastheanalysisofitscharacteristicsandadvantages,andtheimplementationofthealgorithminPython,toexplorethealgorithmtoimprovethemethod,topromotethetheoryNatureresearchprogress.keyword：Python;ClassificationandRegression;DecisionTree;NodeSplit;RandomForest第一章引言1.1 背景介绍在如今大数据、大信息的环境下，到处都存在“信息”和"数据”，并且我们也很容易地就能获取到信息和数据，但对这么庞大的信息和数据量我们该如何有效快捷处理和分析，是我们长久以来的热点话题。因此，如何利用现有的科学统计方法和统计工具来处理和分析这些大量的数据信息，成为当代该领域研究数据的热门话题之一，我们希望有一种又快捷又有效处理数据的方式来分析这些信息。在数据处理环节中，有很多方法，但应用最广泛最有效的便是分类方法。它通过训练集产生适合的分类器，用户只要将要分析分类的数据通过这个分类器就能得到该分类器预测的分类结果。分类技术有单分类器和多分类器技术之分，这是由分类器的个数决定的。单分类器虽然推动了分类技术的发展，甚至达到一时巅峰，但是因为其自身的缺陷而遇到了瓶颈。于是，多分类器组合思想便由然而生。简单来说，很多个单分类器按一定规则组合形成了一个群体，这就是多分类器，既继承了单分类器的优势又解决了之前的瓶颈，将多个单分类器的分类预测结果汇总，按一定规则分析从而得到最终结果，本文所要介绍的随机森林算法便是这种多分类器组合的分类方法之一。随机森林这种思想最早产生于1995年，2001年，LeOBreiman做了系统介绍，从此，随机森林成为了人们进行数据挖掘与分析的重要手段。在这些年里，随机森林充分展示其优势和特点，逐渐被人们所喜爱，并被广泛使用，成为数据处理和挖掘的重要手段，也成为各个领域研究人员的热门话题。本文将实现随机森林算法，分析其特点和优势，结合PythOn语言本身的快捷易懂的特点，更加快速地解决数据分析与处理问题。Python程序设计语言这些年来也因为其快捷性被人们所热爱，成为当下越来越热门的流行程序语言，它的特点同样是快捷有效，结合随机森林算法在处理大数据、大信息的问题上有着得天独厚的优势，这也是本文想要着重叙述的地方。1.2 PythonPythOn一种解释型程序设计语言，在1989年问世，1991年发行，其数量庞大的库，使其有另一个外号，胶水语言L顾名思义，它可以把其他语言设计的模块组合起来，实现用户所要的功能，所以它的特点简单来说就是简洁清晰、通俗易懂，方便学者学习和探讨。1.2.1 当代环境下的Python当今社会，庞大的信息量、数据量使得如今的关键不在于获取信息，而在于如何处理和分析信息，PythOn有着得天独厚的优势站在历史的舞台。它的简便、易懂、快捷的特点最终受到人们的青睐，并且在各个领域中得到广泛的应用，其使用人数也是逐年成线性增长。1.2.2 Python的演变20世纪90年代，PythOn问世，直到现在，它已被逐渐广泛应用于Web编程和系统管理任务的处理。1989年12月，GUidOVanROSSUm过圣诞节的时候因为无所事事，闲着无聊便找些事做，于是他开始写一些脚本语言，后来他把这些脚本程序命名为ABC语言。后来GUidO发现他无意间开发的语言竟然如此优美，功能如此强大。但ABC因为其自身的弊端无法弥补，最终不被人们所认可，但GUidO并没有放弃，他吸取ABC语言失败的教训，重新研发程序，这便是后来的Python程序设计语言。现如今，Python越来越受到人们关注和认可，Python的使用率也是呈线性上升的状态。PythOn语言因为其特点和优势，国外很多科研机构都使用该语言，而且有很多大学课程都开始选择PythOn教学，轻松容易。Python有很多扩展库，这些扩展库专用于科学计算，这些扩展库构成的开发环境十分适合工程和技术人员处理实验数据、制图，甚至在科学计算应用程序方面也有很多应用成果。1.2.3 Python的特点介绍Python作为一种高级计算机程序设计语言当然和其他高级语言有相似的地方,但Python自身也有区别于其他语言的地方。说到可比性，可能首先想到的是MATLAB语言，Python因其具有强大的库，所以可以找到替代MATLAB大部分常用功能的扩展库，其次，PythOn相比于MATLAB的昂贵费用，优势显而易见，用户可以不用付任何费用去安装Python和它的大多数扩展库；并且，于MATLAB相比，Python是一种更容易学习、容易理解的语言；最后，PythOn因为有丰富的库的存在，所以可以实现文件管理、网络通信等多种高级任务。PythOn的设计整体风格是清新划一，这也使其成为容易学习、容易使用的计算机语言，从而被大众认可。PythOn具有以下几个优点：（1）简单：其语言本身体现简单主义，编写程序就如同写一个故事，通俗易懂，不用刻意弄清语言本身含义，重在解决实际问题。（2）易上手：对于编程新手来说是最容易上手的一门程序语言，它有专门的说明包，里面语句用法一一详尽。（3）速度快：PythOn是从库中调用程序，这些程序还是由C/C+等语言写的，所以运行速度上还算比较快。（4）免费：使用者可以随意使用、开发，没有费用收取。（5）可移植性：PythOn可在很多不同平台上进行工作。（6）可扩展性：有一些算法和公式是开发者希望保密的，可以将其用其他语言编译出来，在运用的时候只需调用即可。（7）可嵌入性:在C或者C+语言编译中可以夹杂一些Pylhon语句，充当一个脚本，方便用户使用。（8）独特的语法：Python有自己独特的语法规则区别于其他语言，使其更加灵活简便。1.2.4 Python的功能与应用Python既然有这么多优点，那这种语言都有哪些功能，可以完成那些任务呢？前文已经说了，它有很强大的库，这些库的种类十分丰富，具体可以完成以下工作任务：（1）系统编程：有API,能够有效管理和维护系统，具有系统管理员想要的理想编程工具Linux标志性语言。（2）图形处理：具有PIL、Tkinter等图形库，从而能方便地处理图形。（3）数学处理：提供NUmPy扩展，这些扩展有大量接口，而这些接口都是直接连接到标准数学库中。（4）文本处理：提供re模块，利用re模块进行判断，可以预算正则表达式，从而分析数据模块。（5）数据库编程：提供PythOnDB-API模块可以加快程序员与数据库的联系。(6)网络编程：能方便快速地进行分布式应用程序的开发。(7)Web编程：是一种应用型的开发语言。(8)多媒体应用：Python提供PyoPenGL模块可以分析图像，这些图像可以是平面或立体的。PyGame模块也可用于来编写游戏软件。1.3本文结构和框架之前已经介绍了Python的相关背景知识，接下来大数据环境下的一种数据处理和分析的算法随机森林算法。将在下一章节介绍该算法的思想构成和实现方法,对其特点和优势进行研究和总结，探讨其可行性，总结其缺陷，并给出改进方案和以后学习研究的方向。然后，再结合PythOn语言将其实现，完成随机森林的构建，分析其算法特性和实验过程，引用生活中实际例子的应用，完成整个算法的构建过程,在本文最后附录给与全部代码展示。最后针对这些特性对实验结果经行分析和总结，展现该算法的优势和可行性。第二章随机森林算法研究与分析2.1 决策树决策树是一种简单的单分类器，也是随机森林的基本单元，随机森林单个分类器就是一棵决策树，且无剪枝，研究随机森林就必须从单个决策树开始。2.1.1 决策树的概念决策树是一种简单、典型的单分类器，它通过一定规则对数据信息进行分类或者预测，其生成过程分为三步：第一，通过对训练集进行递归分析，生成一棵形如倒立的树，由根节点出发，进行一层一层判断筛选；其次，每当从一个节点通往下一个节点时是通过一系列规则和规律进行的，研究分析路径，得到产生这些路径所需要的一定规则和规律；最后通过这些对数据分类或预测然后得出结果。总的来说，单个决策树实质上就是通过样本产生一定的规则，利用这些规则分析得出分类和预测结论，以此来对数据进行挖掘和研究。决策树是一种树状模型，形如倒立的树，其中节点分为三类，分别为根节点、中间节点以及叶子结点，每个节点代表的研究对象的属性，而节点之间的通道则是之前节点属性的值或值的范围，每个非叶子节点都会在下面产生二叉路径，生成两棵子树，以此类推，一直到生成的节点是叶子结点为止。在根节点分裂时，需要根据选择结果优劣，选择最优属性产生左右子树，这就是节点分裂，而节点分裂比较规则有不同算法，接下来本文会有所介绍。2.1.2 节点分裂【1。】决策树一般采用程序递归方式生成,从根节点开始一分为二，形成左右两棵子树,再以左右两个子节点分成左右两棵子树，以此类推，形成树状模型。而节点分裂是根节点在分裂时对属性的选择方面，如何选择最佳属性，这里有多个分裂算法，下面以CLSlw和CARTl为例进行阐述。(1)CLS算法决策树的思想是从根节点开始分裂，一层层进行，形成树状，每条路径形成一个规则，在CLS算法中，根节点的分裂，对属性的选择方面是随机的，即每个属性被选到的概率是等可能的，然后就从该属性分裂，有多少属性值域，就会产生多少树的分支，每个节点都和之前规则一样进行分裂，即数据集已空或数据集中所有样本为同一类别，这就是CLS算法思想。下面以人员是否经常使用互联网预测为例详细介绍，数据集如表2-1所示：表2-1人员特征样本信息表人员编号年龄阶段职业类型是否常用互联网1青年学生不常用2中年公务员常用3老年公务员常用4中年服务行业职员常用5老年服务行业职员常用6青年公务员不用7老年无业不用8中年无业不用根节点属性CLS算法没有明确给出，是由程序随机选取，加入根节点属性选择年龄阶段，那么有三个属性取值，则有青年、中年、老年三条路径生成：图2-1以年龄阶段为根节点属性分类效果图该属性将样本分类三个子集，分别为：左：青年样本1、样本6；中：中年样本2、样本4、样本8；右:老年（样本3、样本5、样本7）。分析每个子集，目标取值都不同，并且数据集不为空或不属同类，所以继续分裂产生新子树，最终得到一棵决策树如图2-2所示:图2-2生成最终决策树图CLS算法步骤如下：第一步:设置决策树根节点（X,Q）,X为训练集，Q为属性集。第二步:生成子叶点时，若训练集为空或属同一类别，则算法结束，该节点为叶子节点，否则进行第三步。第三步:从Q中选取属性，该属性取值有多少种，就产生多少种分支。第四部:对每个分支设置根节点，然后转向第二步。从CLS算法步骤来看，可以生成很多种决策树，因为第一个根节点属性是随机选取的，没有统一的规则，这就带来一定的弊端，限制其应用范围，但这种算法是一切之后优秀分裂算法的起源，之后的算法都是该算法的优化和发展。（2）CART算法CART算法在继承了CLS算法的递归思想基础上，形成以信息墉【为基础的优化思想。根节点分裂遵循Gini系数最小选择规律。CART算法将根节点属性分裂的两组取值组合的子集进行Gini指标计算，将当前训练集按二分递归规则分成两子集，从而形成左右子树，而在节点分裂时，使用Gini指标来决定数据划分，Gini指标计算如下：首先进行样本Gini系数计算如式（2-1）所示：Gini（三）=I-Pi2（2-1）Pi为G在样本S中出现的概率。然后对每个划分计算其Gini系数(假设S被分为两个子集Sl和S2)如式(2-2)所示：Ginisplit(三)=FGini(SI)+Gini(S2')(2-2)CART算法对于离散属性数据有较好的处理，但对连续属性数据处理存在问题,需要先将其离散化，将连续变量转化为离散变量。变成离散变量，就按照Gini系数最小原则进行分裂，通过递归形成决策树，从生成分类规则。CART算法分裂过程中，若出现下列四种情况：当前数据集样本小于给定值、当前数据集样本为空、当前数据集样本同类、决策树深度超过用户给定额度，则分裂产生叶子结点，同时算法结束。CART算法虽说是CLS算法升级，但仍有很多不足之处，需要改进和优化。2.1.3决策树分类存在的问题决策树只是最简单的但分类器，一次其本身有不可避免的缺陷：1.分类规则过于复杂。决策树算法分裂采用贪婪方式，每次只选用一个属性进行分支构造决策树，分类方式甚多，因此产生的分类规则也复杂苛刻，需要大量的分析和运算过程。解决这类问题一般采用剪枝的方法，关于剪枝的方法也是决策树一个重要的研究方向，这里就不继续深入了。2 .生成结果只是局部最优解。决策树分类结果不能得到全局最优结果，只是局部最优,分裂选取过的属性不再考虑分析,很容易忽略其他影响,造成结果非全局最优。3 .欠拟合和过拟合。在决策树分类过程中，特征选取过少，导致不能得到分类或预测结果；相反，特征选取过多，则导致分类或预测结果超出目标属性范围而出错。两者相比后者更为棘手，是对于决策树和其他分类算法来说都是一个难题。2.2 随机性分析随机森林构建思想解决了原先单决策树存在的过拟合和非全局最优解四的缺陷，主要在于其思想处处体现随机性，下面将会分析该算法训练集和特征变量的随机性。2.2.1 训练集的随机性随机森林采用Bagging方法生成决策树时，选取特征是遵循有放回随机抽样的方法。新的数据并不是简单复制，而是多次重复自身达到空间重构，新的数据源于原始数据，但彼此之间也存在差异，这也体现出决策树生长时的随机性。这一点使得各个决策树区别度很高，丰富性提高，避免了之前所说的局部最优解的问题。Bagging方法一方面提高了精度，另一方面可以通过没有选取到的数据集预估泛化误差、强度和相关系数。2.2.2 随机特征变量的随机性之前生成随机森林时选取特征变量来进行进一步选择时，特征本身是由随机选出的。在节点选取属性时，不是所有属性都参与选择，而是从其中随机选出若干个进行选择。这是为了提高分类精度，减少树之间相关性。从M个属性中随机选取若干个在进行选择，这里就体现了随机性，这使得最终生成的决策树都和其他决策树有所区别，再从这若干个属性再次随机选择作为节点属性，这又是另一个随机性的体现，同样提到了树的精度，同时区别于其余决策树。2.3 随机森林理论概述随机森林在数学上的定义，比如现有由hl(x),h2(X),hk(X)构成的随机森林。边际函数定义：mg(X,Y)=avkl(hk(X)=;)-maxavkl(k(X)=;)(2-3)边际函数表示的意思是，在正确分类的情况下得到的票数比在不正确分类的情况下得到得票数多的程度，显然，函数越大，说明原分类器分类效果越可靠。泛化误差定义：PE*=Px(mg(XfY)<0)(2-4)X,Y代表概率定义空间。随机森林边缘函数：mr(X,Y)=P(九X)=丫)-maxP(c(X)=力(2-5)jy,j=i,P(X)=丫)是正确判断的概率，maxP(X)=/)为错误判断的概率最大值。=i每棵决策树生成随机森林时，总是有一个初始数据集和没有被抽取的数据集Ok(x)。Qk(X，”)表示X在。式%)中方的比例。即：S = E(mr(X, Y) = E P(M(X) = Y)-(2-8)(2-9)(2-10)(2-11)(2-12)kihk(')=yj,(%，y)0c(%)Qa,y.)=77;jI力'("M),(>y)0c()QkG,%）为正确分类的概率估计，由此可对对随机森林强度和相关性进行分析。随机森林强度定义：maxP(hk(X)=/)(2-7)j*y,j=i/将式(2-6)代入式(27)得：s=；Zki(Q(%y)maxQ6,力)n件丫，j=i)随机森林相关度定义：,、*以Qgy)-maxQs,j)-s2_vr(mr)_njy.；=/P""""22Sd(M*)(i!i=1Jp“+瓦+(PlG)匕为P(k式勺)=y)的OBB估计，凡为PolZ8)=刃的C)BB估计。匕和冗计算公式如下：P=%iy)-J(38)=y)u£-OJ(M阳)5-y)(38)=万)U2将式(2-10)和式(2-11)带人式(2-9)得:yj=argmaxQ(X,”)随机森林的性能体现在其收敛程度、强度和相关程度。收敛性在于决策树的泛化误差都收敛，出差会有上限，这说明随机森林对未知事物具有良好的适应性，不会造成很大的误差，也不易造成过拟合。由上述可见，随机森林的泛化性良好，所以应放大但棵决策树的决策能力，减小树与树之间的相互影响和联系，降低相关度。从另一个角度说，随机森林既然是由多棵决策树构成，其分类强度自然是由每棵决策树的强度决定，因此我们应尽量提高单棵决策树的分类能力，从而提高整个森林的强度和精度。总而言之，树的强度越高，树与树之间相关程度越低，整个随机森林的性能就越好，反之，若树的强度越低，树和树之间的相关程度越高,这说明每棵树的异化程度过低，分类出的结果可信度不高,导致随机森林性能越差。2.4随机森林的性能指标随机森林性能指标从内外两方面分析的话，从外部看来，主要是训练样本的情况，与样本正负情况、规模有关，从内部看来，由树的强度和树与树之间相关度决定。所以由此得出随机森林的三大指标，即分类效果指标、泛化误差和运行效率。这三个指标可用来综合评价森林的性能。2.4.1 分类效果系列指标众所周知，森林算法主要用来进行分类预测，那么分类预测效果自然有对应指标进行衡量。这里介绍一下二分类混淆矩阵。如表22所示：表2-2混淆矩阵ClassifiedpositiveClassifiednegativePositiveTPFNNegativeFPTN上表为二分类混淆矩阵。假设有正分类和负分类两种分类，如上表列向显示，TP、TN表示正确分类的正负类样本数，FN、FP表示错误分类的正负类样本数。分类精度Accuracy：Accuracy =TP+TNTP+TN+FP+FN(2-13)表示随机森林分类精度。灵敏度Sensitivity：TPSensitivity=(2-14)JTP+FN表示模型文寸正类的分类精度。特异度Specificity：TNSpecificity=(2-15)1.jfp+tn',表示模型对负类的分类精度。几何均值G-mean：G mean =TP TN×TP+FN FP+TNG.均值为灵敏度和特异度的几何平均，为了保持正负两类精度平衡且总体精度最大。只有灵敏度和特异度都比较高，G-均值才会较高，这也是比较常用的性能评价指标。负类查全率Recall：Recall =TPTP+FN(2-17)表示被正确分类的负样本占所有负类样本比例。负类查准率Precision：TPPrecision=(2-18)TP+FP表示负类中，正确分类在预测中的比例。负类检验值F-Value：(2-19)Fvalue(1+历)XreCa-xprec"i°n2×recall+precision其表示负类查全率和查准率的组合。泛化误差与OOB估计1.泛化能力与泛化误差机器学习试分析研究数据背后的规律，依照这些规律得出分类预测结果，对数据集以外但有着同样规律的数据进行分析，也能得出一定的输出结果，这种举一反三的能力即为泛化能力。简单来说，泛化能力就是通过已有数据集中数据规律，来推测数据集以为数据规律的能力，也是算法对新鲜样本的学习能力。而泛化误差是泛化能力的一个衡量指标，误差越小，自然学习分析能力越好，反之，学习效果会产生很大偏差。上文己经讲述误差可以计算，但实际中，样本输出分布都未知，这就导致很难通过已有样本有效获得误差估计。目前解决办法是对这种推广所带来的误差进行估计，估计的方法大致有分析模型和交叉验证两种。分析模型常用于简单线性问题的误差估计，而交叉验证是把样本划分，分成训练集和验证集，而验证集输出已经给出，所以可以计算其分化误差。2.00B估计【另一种误差估计的方法为OoB方法。据前文介绍，随机森林采用bagging方法训练，这种训练方式，会有一部分数据不被抽取，这些不被抽取的数据个数约为(1-1M)mo若M很大，其值约为le,即0.368,这些数据即为OBB数据没有被抽取的数据,利用这些数据估计的方法称为OOB估计。交叉验证与OoB估计类似，但因其要对数据进行划分和合并所以运算量巨大，成本较高。OoB数据在生成决策树的同时产生，决策树构建完成的时候就可以得到OOB估计，所以比较方便省时省力，而OoB估计效果和交叉验证一样好，所以OoB估计成为常用估计泛化误差的方法。算法性能与OOB估计成反比。同时，Breiman早通过实验证明OoB估计是泛化误差的无偏估计，而且他也通过大量实验证明估计效果的可靠性、准确性以及可行性，且发现OoB数据不仅能估计误差，还能计算强度与相关系数，从而有利于分类结果更加准确。2.4.3随机森林算法运行效率指标任何算法的可行性都要考虑其运行效率，即要考虑算法运行时的执行量和工作量,需要占用多少计算机资源,因此时间复杂度【网和空间复杂度是我们要考虑的影响算法运行效率的两大因素。1 .时间复杂度时间复杂度，简单的来说就是计算机执行指令所需要的工作量和时间，若直接计算算法执行多长时间是很困难的，所以我们引入时间复杂度的概念，来描述算法执行快慢。时间复杂度通过代码中指令条数，循环次数，以及语句重复次数计算得出，从理论上说，指令越多，重复执行的次数越多，需要的运行时间越长。2 .空间复杂度空间复杂度，简单的来说就是该算法占用计算机内存空间的大小。通过指标，可以估计算法在运行过程中，需要占用计算机内存多大的空间来执行算法，处理程序本身的变量，还需要CPU与主存之间产生一些虚拟存储空间，来提供算法所需变量的存储空间。现在计算机飞速发展，一般空间占用无需考虑，算法所需内存空间，计算机硬件方面基本可以支持，所以随机森林的时间复杂度是我们主要考虑的因素，不断优化算法，降低时间复杂度，一直是我们努力的方向。第三章随机森林算法的实现3.1决策树的实现例：通过头发长短和声音来判断性别数据集如表3/所示：表3.1人员样本头发、声音、性别信息表头发声音性别1长粗男2短粗男3短粗男4长细女5短细女6短粗女7长粗女8长粗女经分析，因为根节点分裂有不同方法，会生成不同的决策树，可有以下两种决策图3-1以头发为根节点属性生成的决策树图如图3.1所示，该决策树以头发为根节点属性进行分裂，生成最终决策树，最终四个叶子节点。头发长声音粗的或头发短声音粗的视为男生，头发长声音细的或头发短声音细的视为女生。J头发J女1,女2长/短男2,男3,女3男1,女4,女5图3-2以声音为根节点属性生成的决策树图如图3-2所示，该决策树以声音为根节点属性进行分裂，生成最终决策树，最终三个叶子节点。声音粗头发长的视为女生，声音粗头发短的视为男生，声音细的视为女生。那么这两种决策树哪一种更好？面对多个特征，计算机如何选择哪个属性作为最佳属性选择？数据划分是将无序数据变得有序，我们有很多方法，每种方法各有千秋，我们可以测量数据复杂度，选择复杂度最低的属性，该属性即为最佳特征。ClaudeShannon定义了墉（entropy,简称E）和信息增益（informationgain,简称IG）,用来描述信息复杂度，信息复杂程度与E成正比。公式为：H=-ilP（%t）log2P（X1）（3-1）而IG是两个E的差。首先计算未分类的E：E（all）=-×log2-log2=0.9544（3-2）接着分别计算第一种和第二种决策树分类后信息Eo第一种首先按头发分类，分类后的结果为：长头发中有1男3女。短头发中有2男2女。E（长发I）=-（XIog2i-2Iog2=0.8113（3-3）E（短发1）二一"Iog2J-Jlog2J=1（3-4）由式（3-3）和式（3-4）可得:E(I)=-×0.8113+-×1=0.9057(3-5)'，88IG(I)=E(all)-E(I)=0.9544-0.9057=0.0487(3-6)同理，按第二种的方法，首先按声音特征来分，分类后的结果为：声音粗中有3男3女。声音细中有0男2女。E(声音粗2)=-×log2-×log2(3-7)E(声音细2)=-|XIog21=0(3-8)由式(3-7)和式(3-8)可得：E(2)=×1+×0=0.75(3-9)IG(2)=E(all)-E(2)=0.9544-0.75=0.2087(3-10)计算E代码如下：defcalentropy(data):#计算数据的峭(entropy)numlines=len(data)#数据条数labels=forfeatVecindata:curkind=featVec-l#每行数据的最后一个字(类别)ifcurkindnotinlabels.keys():labelscurkind=0labelscurkind+=l#统计有多少个类和每个类的数量ShannonEnt=Oforkeyinlabels:prob=float(labelskey)numlines#计算单个类的端值shannonEnt-=prob*log(prob,2)#累加每个类的端值returnShannonEnt由此可知,第二种信息增益更大,样本分辨能力强,所以采用第二种方法用Python实现决策树构建，代码见附录。3.2随机森林的构建过程随机森林的构建简单来说就是多个决策树的组合，再由多个决策树产生的结果投票选出最终结果。每棵决策树都一个自己的训练集，构建N棵决策树，那就对应N个训练集，从原始训练集到N个子训练集可以采用抽样的方法，其方法包括不放回抽样和有放回抽样。(1)不放回抽样不放回抽样意思是从多个个体容量为M中不放回的抽取一定数量为m的作为样本，而简单随机抽样表示在每次不放回抽样时，每个个体被抽取的概率是等可能的。而产生随机数的方式有两种，一是抽签，二是随机数。抽签是将总体中的个体编号，每个个体都有一个特有的标签，装进一个容器里，随机打乱，随机一个个抽取号签m次，就得到上述所说的m容量的样本，此方法若总体个数不多就显得简单易行。当数据总量过于庞大时，抽签法就比较困难。而随机数法是通过特定器具所产生的数来抽样。不放回抽样方式特点是抽样时数据集不断减少，此时样本不会重复。(2)有放回抽样有放回抽样，顾名思义，在每次抽取完样本时，将样本再放回训练集，这样每次抽样不会减少数据集，且生成的样本可能有重复°bagging抽样是简单随机选取特征，没有设置每个特征的权重，这种方式简称无权重抽样，与之相对的是有权重抽样。Bagging方法本身是有放回抽样，数据集中总是有一部分被抽取，而相对的另一部分不会被选取，假设样本训练集总量为M,则每个样本不被选取的概率约为(1-1M)%另一种方法就是BooSting方法，是指在生成一个样本容量为m的训练集之后，初始设定每个样本的权重是lm,设定权值之后，进行测试，然后提高分类性能差的训练集的权重，重复多次进行测试，得出最后权值列，一个训练集对应一个权值列，这些权值将对最后投票结果产生影响，从而影响最终结果。Bagging和BoOSting虽都是有放回抽样，但是也有很大区别：1.Bagging每次训练测试相互之间是独立的，没有关联，而BoOSting每次训练测试是在前一次训练基础之上的，训练之间有串行关联，所以Bagging可以并行处理，处理较快，而BooSting总是要等待上一个训练结果，所以处理较慢。2.Bagging训练对每个样本都是平等待遇，而BOoSting对每个样本都设置权重，所以两种方法对待样本的待遇不同。而大多数随机森林都采用Boosting的方法,生成训练集样本数量约为原始训练集样本数量的2/3,且样本有重复，避免了单决策树非全局最优解的问题，从而提高整体性能水平。3.2.2决策树的构成每个训练集训练生成一个决策树，多棵决策树组合生成随机森林，每棵决策树无需剪枝，任其生长。1 .节点分裂在生成决策树的时候最关键的一步为节点分裂，根据上一小节中的介绍，一个完整的决策树便是通过节点分裂，一层层直到叶子结点而形成的，节点属性也是根据分裂规则确定。不同的规则生成不同决策树，因为不同规则会导致节点属性选择不一致，自然生成结果不一致，主要分裂算法也在上一节有所介绍，主要是CLS算法和CART算法。2 .特征变量的随机选取特征是指节点分裂的属性。一个树的生成，不是所有属性都能参与比较和决策，只有其中一部分参与，参与的个数便是随机特征变量。随机特征变量不仅减少相关树之间的关系，同时提升树的精度，从而提高整个随机森林的准确率。属性选取是在节点分裂时，所有属性按某一概率分布进行随机选取。随机特征变量选取主要有随机选择输入变量（FOreSt-RD和随机组合输入变量（ForeSt-RC）两种方法，这两种方法有联系又有区别。ForeSt-Rl是通过随机分组的方法完成的，每组有F个变量，F为某一定值，对每一组进行CART算法