精华内容
下载资源
问答
  • 机器学习(六)决策优化-剪枝

    千次阅读 2018-04-03 22:49:35
    来自https://blog.csdn.net/u012328159/article/details/79285214决策树(decision tree)(二)——剪枝*... 决策树系列博客: 1. 决策树(一)——构造决策树 2. 决策树(二)——剪枝 3. 决策树(decision t...

    决策树(decision tree)(二)——剪枝

    **注:本博客为周志华《机器学习》读书笔记,虽然有一些自己的理解,但是其中仍然有大量文字摘自周老师的《机器学习》书。 
    决策树系列博客: 
    1. 决策树(一)——构造决策树 
    2. 决策树(二)——剪枝 
    3. 决策树(decision tree)(三)——连续值处理 
    4. 决策树(四)缺失值处理

    前面在决策树(decision tree)(一)中介绍了几种对结点划分的方法(信息增益、信息增益率、基尼指数),在这篇博客里主要介绍剪枝,即; 
    1. 预剪枝(pre-pruning) 
    2. 后剪枝(post-pruning) 
    首先剪枝(pruning)的目的是为了避免决策树模型的过拟合。因为决策树算法在学习的过程中为了尽可能的正确的分类训练样本,不停地对结点进行划分,因此这会导致整棵树的分支过多,也就导致了过拟合。决策树的剪枝策略最基本的有两种:预剪枝(pre-pruning)和后剪枝(post-pruning):

    • 预剪枝(pre-pruning):预剪枝就是在构造决策树的过程中,先对每个结点在划分前进行估计,若果当前结点的划分不能带来决策树模型泛华性能的提升,则不对当前结点进行划分并且将当前结点标记为叶结点。
    • 后剪枝(post-pruning):后剪枝就是先把整颗决策树构造完毕,然后自底向上的对非叶结点进行考察,若将该结点对应的子树换为叶结点能够带来泛华性能的提升,则把该子树替换为叶结点。

    一、预剪枝(pre-pruning) 
            关于预剪枝(pre-pruning)的基本概念,在前面已经介绍过了,下面就直接举个例子来看看预剪枝(pre-pruning)是怎样操作的。数据集为(图片来自西瓜书): 

    数据集

    这个数据集根据信息增益可以构造出一颗未剪枝的决策树(图片来自西瓜书): 
    未剪枝的决策树

    下面来看下具体的构造过程: 
    前面博客(决策树(一))讲过用信息增益怎么构造决策树,这边还是用信息增益构造决策树,先来计算出所有特征的信息增益值: 
    3

    因为色泽脐部的信息增益值最大,所以从这两个中随机挑选一个,这里选择脐部来对数据集进行划分,这会产生三个分支,如下图所示:
    5

    但是因为是预剪枝,所以要判断是否应该进行这个划分,判断的标准就是看划分前后的泛华性能是否有提升,也就是如果划分后泛华性能有提升,则划分;否则,不划分。 下面来看看是否要用脐部进行划分,划分前:所有样本都在根节点,把该结点标记为叶结点,其类别标记为训练集中样本数量最多的类别,因此标记为好瓜,然后用验证集对其性能评估,可以看出样本{4,5,8}被正确分类,其他被错误分类,因此精度为43.9%。划分后: 划分后的的决策树为: 
    决策树

    则验证集在这颗决策树上的精度为:5/7 = 71.4% > 42.9%。因此,用 脐部 进行划分。 
            接下来,决策树算法对结点 (2) 进行划分,再次使用信息增益挑选出值最大的那个特征,这里我就不算了,计算方法和上面类似,信息增益值最大的那个特征是“色泽”,则使用“色泽”划分后决策树为: 
    7

    但到底该不该划分这个结点,还是要用验证集进行计算,可以看到划分后,精度为:5/7=0.571<0.714,因此,预剪枝策略将禁止划分结点 (2) 。对于结点 (3) 最优的属性为“根蒂”,划分后验证集精度仍为71.4%,因此这个划分不能提升验证集精度,所以预剪枝将禁止结点 (3) 划分。对于结点 (4) ,其所含训练样本已属于同一类,所以不再进行划分。 
            所以基于预剪枝策略生成的最终的决策树为:
    最终的决策树

    总结: 对比未剪枝的决策树和经过预剪枝的决策树可以看出:预剪枝使得决策树的很多分支都没有“展开”,这不仅降低了过拟合的风险,还显著减少了决策树的训练时间开销和测试时间开销。但是,另一方面,因为预剪枝是基于“贪心”的,所以,虽然当前划分不能提升泛华性能,但是基于该划分的后续划分却有可能导致性能提升,因此预剪枝决策树有可能带来欠拟合的风险。

    二、后剪枝(post-pruning) 
            后剪枝就是先构造一颗完整的决策树,然后自底向上的对非叶结点进行考察,若将该结点对应的子树换为叶结点能够带来泛华性能的提升,则把该子树替换为叶结点。前面已经说过了,使用前面给出的训练集会生成一颗(未剪枝)决策树: 

    未剪枝的决策树

            后剪枝算法首先考察上图中的结点 (6),若将以其为根节点的子树删除,即相当于把结点 (6) 替换为叶结点,替换后的叶结点包括编号为{7,15}的训练样本,因此把该叶结点标记为“好瓜”(因为这里正负样本数量相等,所以随便标记一个类别),因此此时的决策树在验证集上的精度为57.1%(为剪枝的决策树为42.9%),所以后剪枝策略决定剪枝,剪枝后的决策树如下图所示: 
    这里写图片描述

            接着考察结点 5,同样的操作,把以其为根节点的子树替换为叶结点,替换后的叶结点包含编号为{6,7,15}的训练样本,根据“多数原则”把该叶结点标记为“好瓜”,测试的决策树精度认仍为57.1%,所以不进行剪枝。 
            考察结点 2 ,和上述操作一样,不多说了,叶结点包含编号为{1,2,3,14}的训练样本,标记为“好瓜”,此时决策树在验证集上的精度为71.4%,因此,后剪枝策略决定剪枝。剪枝后的决策树为: 
    这里写图片描述

            接着考察结点 3 ,同样的操作,剪枝后的决策树在验证集上的精度为71.4%,没有提升,因此不剪枝;对于结点 1 ,剪枝后的决策树的精度为42.9%,精度下降,因此也不剪枝。 
            因此,基于后剪枝策略生成的最终的决策树如上图所示,其在验证集上的精度为71.4%。

    总结:对比预剪枝后剪枝,能够发现,后剪枝决策树通常比预剪枝决策树保留了更多的分支,一般情形下,后剪枝决策树的欠拟合风险小,泛华性能往往也要优于预剪枝决策树。但后剪枝过程是在构建完全决策树之后进行的,并且要自底向上的对树中的所有非叶结点进行逐一考察,因此其训练时间开销要比未剪枝决策树和预剪枝决策树都大得多。

    参考文献 
    [1]: 周志华 《机器学习》 

    展开全文
  • 决策树算法的系统实现与修剪优化

    千次阅读 2007-05-16 14:21:00
    本文以一个决策树算法的程序实现为例,进一步讨论了对树进行修剪优化时可能涉及的问题,目的在于给决策树研究人员提供一深入和清晰的简化技术视图。 引言机器学习领域研究对数据的归纳分类,主要集中在预测精确度...
    决策树是对分类问题进行深入分析的一种方法,在实际问题中,按算法生成的决策树往往复杂而庞大,令用户难以理解。这就告诉我们在重分类精确性的同时,也要加强对树修剪的研究。本文以一个决策树算法的程序实现为例,进一步讨论了对树进行修剪优化时可能涉及的问题,目的在于给决策树研究人员提供一个深入和清晰的简化技术视图。 
    

    引言

    机器学习领域研究对数据的归纳分类,主要集中在预测精确度方面。然而,在许多实际业务中,只有"数据的预测结构更易于理解"的分类规则才易让人接受,就象这个分类规则所解决的决策问题一样让人清楚明白。在机器学习和统计领域,决策树归纳作为一种分类问题的解决方法正在被广泛的研究。由于许多树简化规则正在生成越来越简单和越来越小的决策树,树简化规则已经成为继预测精度之后的第二个研究焦点。总结树简化技术的关键问题在于解决方法的多样性。要驾御这种多样性,可以将这些方法分为五类。类的建立是将树归纳看作是对预想树空间的即席状态搜索。

    一、决策树算法的程序实现

    决策树归纳算法在机器学习、统计和其它解决分类问题的领域有着广泛的应用。决策树可以按如下方式分类一个查询事例,给定要分类的查询Q,树将沿一条路径从根遍历到叶节点,直到将类标签分配给Q。测试通常能够评价描述事例的特征或(如布尔或线形)组合特征集。笔者开发的决策树算法包括四个输入:
    1. C--培训事例集,由特征集和一个类标签定义
    2. R--测试集,用于将培训事例集分成若干子集
    3. E()--评价函数,用于评价分类结果的质量
    4. Stop()--暂停函数,用于确定何时结束决策树
    算法输出的决策树T的每一叶代表一个类,通常有唯一的类标签。决策树由根部向下运用递归分割算法。Make-T函数生成决策树,并完成后期修剪工作,这可能有三种结果:维持原状、修剪或转换成另一种数据结构。Induce-T函数输出树T,它输入C中的子集C'、 测试集R、评价函数E(),以及暂停函数Stop()。Induce-T实施登山式搜索,即只前进不后退,至于达到什么状态由Stop()决定。初始树包括一个节点、根和所有的事例C,状态随树的扩展而变化,表现为树的递归请求。每一个对Induce-T的请求创建一个包含输入子集C'的节点,划分事例C'的"最好"的测试集由Best()函数决定,它借助于E()评价给定测试集和分类结果的质量,并返回最好测试集Best()。再将Best()分类方法P应用于事例子集C',并返回Best()的值V,返回若不能满足Stop(),则树继续扩展。目标状态集由Stop()决定,当返回为真时结束树的扩展。例如,当选定同质规则时,如果所有事例C'有相同的类标签标签,则函数Stop()返回真。同质规则可以被作为缺省的暂停规则,因为它暗含在所有的暂停规则之中。Stop()函数决定将N定义为叶节点还是内部节点。如果是后者,树将继续扩展:节点N被设置为内部节点,子树被标记为V中的测试输出值V'; 如果是前者,节点N被设置为叶节点,叶节点的类标记由其所包含的事例C'决定,通常选择的类标签是事例C'中大多数事例所共有的。
    树归纳算法,如这里提及的生成算法,必须是计算高效的,因为建立决策树是一项复杂的任务,搜索的复杂性会随树的深度(即树根到最低的树叶的距离)呈指数增长。因此,修剪算法应建立于寻找使评价函数E()最大的测试集。如何设计和优化评价函数E()自然成为了系统开发人员关注的问题。

    二、对树进行修剪优化时应考虑的问题

    1、决策树的大小
    决策树变的异常庞大有多种原因。其中之一是特征描述不当,有些树特征描述方式不能精确的建立目标概念模型,当用这种描述方式时,目标模型非常复杂。相反,运用的当的描述将大大降低模型的复杂程度。因此,这个问题很好地提醒我们,树修剪过程中要考虑相应的描述;另一个导致树庞大的原因是噪声。当事例包含大量的特征噪声(即错误标签的特征值)或类噪声(即错误标签的类值)时,归纳运算会因为不相关的事例特征而将树扩展的漫无边际。噪声导致无关的事例掺杂在选定的测试集中,这将引起"无谓建模"的现象,即树将目标概念和内部噪声都作为建模的对象。这是个普遍的问题,因为给定事例中都不同程度地包含噪声。虽然有多种降低噪声的剪树方法,但记住没有一个剪树方法对任何噪声都有效。

    超大的树通常是破碎的--过多的叶,且每叶仅有少数的事例。这样的叶比拥有许多事例的叶更易出现分类错误,更易受噪声影响。这些叶节点(或更准确地说,其相应的树路径)是分散的,发生的可能性都很低。因而,另一种树简化方法是通过剪掉只有少数事例的叶子来消除这种分散性。不管什么原因,复杂树不仅难以理解,而且分类模糊,因为小散点比大散点更易出错。然而,毕竟在培训集中辨别特征的真伪决非易事,在不考虑对树在未知测试事例中运行性能的影响下,修剪树往往会降低对培训集分类的精确度。

    2、权衡精确度与简易性
    修剪方法在于确保精确程度的同时,提高可理解性。这两个目标不一定是矛盾的,可能有种方法能同时提高精确度和可理解性。实际上,最初引入树简化方法的目的是控制培训集中的噪声,而后发现它可以提高许多含噪声的数据集的精确度。

    对简化(或修剪)程度的控制一直是人们争论不朽的问题。通过牺牲精确度修剪的决策树常常灵巧的出奇,然而,保守一点的修剪可能带来精确度的大大提高,这在实际应用中至关重要。故此,许多学者在研究决策树的精确度与简易性的最佳比例,但在随机选择的培训集中很难作做到这一点,因为单凭培训集中的事例,难以区分树的哪部分复杂是由噪声引起的和哪部分是由树本身属性引起的。而且,专门领域的知识不属于培训集之内,就需要在培训集中评价专门领域知识的噪声级别、自身属性的复杂度、以及选择需要简化的程度。对知识稀疏的归纳算法不会涉及这些,因而每个树就假定了模型的复杂程度和培训噪声的级别,这将影响树简化的整个过程。这些算法与描述偏差还有所不同。例如,许多算法假定模型是正规分散的形式,测试对事例特征是单变量的函数,而其它算法假定特征值可以进行线形组合。自然,针对特定的任务,会有一些算法比另一些算法要好。如果无法决断哪个算法对给定的数据库最好,就它们放在一起运行,然后比较结果。

    三、决策树的修剪算法
    修剪树有多种算法,一般人们将其分为五大类方法。最常用的是直接控制树大小的一类方法,通过前期修剪(即在树扩展过程中强行增加一个停止规则),或后期修剪(在树生成后剪掉子树)完成,或逐渐调整树的大小。再一类方法主要是扩展测试集,首先按特征构成是数据驱动还是假设驱动(即借助于以前建立的树预测构件特征)的差别,将建立的特征组合或分割,然后在此基础上引进多变量测试集。这些方法在调整树表达时有效地扩展了树集。第三类,包括选择不同的测试集评价函数,通过改善连续特征的描述,或修改搜索算法本身实现。第四类,数据库约束,即通过削减数据库或事例描述特征集来简化树。第五类,将树转换成另一种数据结构(如决策表或决策图)。这些方法通常可以在同一种算法中相互结合,进而增强各自的功能。例如,经常在搜索测试或搜索空间测试中引入控制树大小的方法。简化决策树的最常用方法是在树建立过程中控制其大小,包括前期修建和后期修剪。

    前期修剪阻止决策树按默认的同质暂停规则生成一个"完全"的树,要作到着一点,需在树生成进程中加入另一个暂停规则。自由限制树的简易修剪形式非常适用,然而,通常暂停规则将评价树继续扩展的效应,如果效用为零(或很小),则停止扩展。或者说此后的处理对树的输出形态影响不大。前期修剪较后期修剪有效,因为它尽可能早的结束了树的生成阶段。约束暂停规则往往同时过滤掉相关和无关测试集,而且,当选择测试集和修剪时使用对某个节点是局部的同一个测试约束时会出现问题,因为约束的绝对值往往因样本的大小不同而变化。前期修剪会引起树在不完全成熟之前停止,即树可能在不应停止的时候而停止扩展,,或称之为horizon效应。即使这样,前期修剪对大规模的实际应用还是值得研究的,因为它相当高效。人们有望在未来的算法中解决horizon效应。

    后期修剪是人们普遍关注的树简化方法,后期修剪算法输入一个未修剪的树T,输出修剪了T中一个或多个子树后获得的树T'。算法并非搜索每个可能的T',而是借助于启发式搜索。修剪将子树转化为叶,进而用叶节点替代内部节点。与前期修剪不同的是,后期修剪没有使用一个消除细节的函数,而是直接采用默认的同质暂停规则。当树相对训练集冗余时(即噪声参与了建模),修剪将非常有效地提高精确度。例如,给定培训集m,假设包含培训集n的叶节点类标签为多数满足n'〈= n,则替代错误率为(n-n')/ m,低层叶节点对替代精确度的影响最小,因而被最先修剪。后期修剪方法借助于多种评价函数,用以确定修剪一个节点是削弱还是增强了事例集的精确度。恰当的修剪可以提高分类的精确度。尤其是当训练集噪声级别比较高时,修剪相当有效。
    有些后期修剪方法将培训集分为两个子集。一个用于生成树,另一个用于后期修剪。不妨成之为生成集和修剪集。生成集常用于生成一个树,然后,按修剪变量生成树集S,修剪集将从S中选择一个最佳的树。例外情况是除错修剪(REP),即修剪集对树进行修剪,而不单单是选择。修剪集方法的优势在于生成树集,而非一个树。尤其是当领域专家算法对选择的树不满意时,可以从树集中进行人为挑选,树集归纳可以提高预测的精确度;将培训集分为两个子集的不足之处在于,设计决策受人为影响,小的培训集可能产生一个很小的树,因为低层部分被剪掉,但这恰恰是应该选择一个尽可能大的培训集的很好的理由,减小培训集的大小相当于增加了修剪预测精确度的不确定性。后期修剪多种算法,如MCCP、REP、MEP、CVP、PEP、EBP等,它们的精确度和简化程度各不相同,感兴趣的读者可以查阅相关资料,在此不予以详述。

    结束语
    在精确度与简易性之间选择权衡值可能是决策树永远逃避不了的主题,但不管怎样,记住这一点是重要的,即即使我们专注的问题是修剪树,但决不能将精确度置之不理。修剪树如果导致精确度的大大降低,那修剪将是毫无意义的。

     
    展开全文
  • 史上最强Tomcat8性能优化

    万次阅读 多人点赞 2019-10-25 15:33:32
    文章目录授人以鱼不如授人以渔目的服务器资源Tomcat配置优化Linux环境安装运行Tomcat8AJP连接执行器(线程池)3种运行模式部署测试用的web项目查看服务器信息部署web应用使用Apache JMeter进行性能测试下载安装修改...

    授人以鱼不如授人以渔

    本博客的目的不在于给出最佳配置,而是带领开发者,能够从实际情况出发,通过不断的调节tomcat和jvm参数,去发现吞吐量,平均响应时间和错误率等信息的变化,同时根据服务器的cpu和内存等信息,结合接口的业务逻辑,最好是测试使用率最高,并发最大,或者是最重要的接口(比如下单支付接口),设置最优的tomcat和jvm配置参数。

    目的

    通过Tomcat性能优化可以提高网站的并发能力。

    Tomcat服务器在JavaEE项目中使用率非常高,所以在生产环境对Tomcat的优化也变得非常重要了。

    对于Tomcat的优化,主要是从2个方面入手,一是Tomcat自身的配置,另一个是Tomcat所运行的jvm虚拟机的调优。

    服务器资源

    服务器所能提供CPU、内存、硬盘的性能对处理能力有决定性影响。硬件我们不说了,这个方面是钱越多越好是吧。

    Tomcat配置优化

    Linux环境安装运行Tomcat8

    具体的安装步骤可以参考Linux(CentOS7)安装Tomcat与设置Tomcat为开机启动项

    如果需要登录系统,必须配置tomcat用户,在安装完Tomcat后,进行如下操作

    /conf/tomcat-users.xml文件中的<tomcat-users>标签里面添加如下内容

    <!-- 修改配置文件,配置tomcat的管理用户 -->
    <role rolename="manager"/>
    <role rolename="manager-gui"/>
    <role rolename="admin"/>
    <role rolename="admin-gui"/>
    <user username="tomcat" password="tomcat" roles="admin-gui,admin,manager-gui,manager"/>
    

    如果是tomcat7,配置了tomcat用户就可以登录系统了,但是tomcat8中不行,还需要修改另一个配置文件,否则访问不了,提示403,打开webapps/manager/META-INF/context.xml文件

    <!-- 将Valve标签的内容注释掉,保存退出即可 -->
    <?xml version="1.0" encoding="UTF-8"?>
    
    <Context antiResourceLocking="false" privileged="true" >
      <!--<Valve className="org.apache.catalina.valves.RemoteAddrValve"
             allow="127\.\d+\.\d+\.\d+|::1|0:0:0:0:0:0:0:1" />-->
      <Manager sessionAttributeValueClassNameFilter="java\.lang\.(?:Boolean|Integer|Long|Number|String)|org\.apache\.catalina\.filters\.CsrfPreventionFilter\$LruCache(?:\$1)?|java\.util\.(?:Linked)?HashMap"/>
    </Context>
    

    打开浏览器进行访问10.172.0.202:8080

    在这里插入图片描述

    点击“Server Status”,输入用户名、密码进行登录,tomcat/tomcat

    在这里插入图片描述

    登录之后可以看到服务器状态等信息,主要包括服务器信息,JVM,ajp和http信息

    在这里插入图片描述

    AJP连接

    在服务状态页面中可以看到,默认状态下会启用AJP服务,并且占用8009端口。

    在这里插入图片描述

    什么是AJP

    AJP(Apache JServer Protocol)
    AJPv13协议是面向包的。WEB服务器和Servlet容器通过TCP连接来交互;为了节省SOCKET创建的昂贵代价,WEB服务器会尝试维护一个永久TCP连接到servlet容器,并且在多个请求和响应周期过程会重用连接。

    在这里插入图片描述

    我们一般是使用Nginx+Tomcat的架构,所以用不着AJP协议,把AJP连接器禁用。

    修改conf下的server.xml文件,将AJP服务禁用掉即可。

    <!-- 禁用AJP连接 -->
    <!-- <Connector port="8009" protocol="AJP/1.3" redirectPort="8443" /> -->
    

    在这里插入图片描述

    重启tomcat,查看效果。可以看到AJP服务已经不存在了。

    在这里插入图片描述

    执行器(线程池)

    在tomcat中每一个用户请求都是一个线程,所以可以使用线程池提高性能。

    修改server.xml文件:

    <!--将注释打开-->
    <Executor name="tomcatThreadPool" namePrefix="catalina-exec-"
            maxThreads="500" minSpareThreads="50" prestartminSpareThreads="true" maxQueueSize="100"/>
    
    <!--
    参数说明:
    maxThreads:最大并发数,默认设置 200,一般建议在 500 ~ 1000,根据硬件设施和业务来判断
    minSpareThreads:Tomcat 初始化时创建的线程数,默认设置 25
    prestartminSpareThreads: 在 Tomcat 初始化的时候就初始化 minSpareThreads 的参数值,如果不等于 true,minSpareThreads 的值就没啥效果了
    maxQueueSize,最大的等待队列数,超过则拒绝请求
    -->
    
    <!--在Connector中设置executor属性指向上面的执行器-->
    <Connector executor="tomcatThreadPool" port="8080" protocol="HTTP/1.1"
                   connectionTimeout="20000"
                   redirectPort="8443" />
    

    保存退出,重启tomcat,查看效果。

    在这里插入图片描述

    在页面中显示最大线程数为-1,这个是正常的,仅仅是显示的问题,实际使用的是指定的值。如果配置了一个Executor,则该属性的任何值将被正确记录,但是它将被显示为-1

    3种运行模式

    tomcat的运行模式有3种:

    bio
    性能非常低下,没有经过任何优化处理和支持

    nio
    nio(new I/O),是Java SE 1.4及后续版本提供的一种新的I/O操作方式(即java.nio包及其子包)。Java nio是一个基于缓冲区、并能提供非阻塞I/O操作的Java API,因此nio也被看成是non-blocking I/O的缩写。它拥有比传统I/O操作(bio)更好的并发运行性能。Tomcat8默认使用nio运行模式

    apr
    安装起来最困难,但是从操作系统级别来解决异步的IO问题,大幅度的提高性能

    对于每种协议,Tomcat都提供了对应的I/O方式的实现,而且Tomcat官方还提供了在每种协议下每种I/O实现方案的差异, HTTP协议下的处理方式如下表,详情可查看Tomcat官网说明

    BIO NIO NIO2 APR
    类名 Http11Protocol Http11NioProtocol Http11Nio2Protocol Http11AprProtocol
    引用版本 ≥3.0 ≥6.0 ≥8.0 ≥5.5
    轮询支持
    轮询队列大小 N/A maxConnections maxConnections maxConnections
    读请求头 阻塞 非阻塞 非阻塞 阻塞
    读请求体 阻塞 阻塞 阻塞 阻塞
    写响应 阻塞 阻塞 阻塞 阻塞
    等待新请求 阻塞 非阻塞 非阻塞 非阻塞
    SSL支持 Java SSL Java SSL Java SSL Open SSL
    SSL握手 阻塞 非阻塞 非阻塞 阻塞
    最大链接数 maxConnections maxConnections maxConnections maxConnections

    推荐使用nio,在tomcat8中有最新的nio2,速度更快,建议使用nio2

    设置nio2:

    <Connector executor="tomcatThreadPool"  port="8080" protocol="org.apache.coyote.http11.Http11Nio2Protocol"
                   connectionTimeout="20000"
                   redirectPort="8443" />
    

    在这里插入图片描述

    可以看到已经设置为nio2了。

    部署测试用的web项目

    为了方便测试性能,我们将部署一个java web项目,这个项目本身和本博客没有什么关系,仅仅用于测试。

    注意:这里在测试时,我们使用一个新的tomcat,进行测试,后面再对其进行优化调整,再测试。

    查看服务器信息

    说明一下我的测试服务器配置,不同的服务器配置对Tomcat的性能会有所影响。

    配置参数 参数值
    Linux版本 CentOS Linux release 7.2.1511 (Core)
    查看逻辑cpu个数 4
    查看物理cpu个数 4
    总内存 8G

    CentOS7服务器环境信息查看命令

    查看Linux版本

    查看Linux版本:cat /etc/centos-release

    查看CPU个数

    查看逻辑cpu个数:cat /proc/cpuinfo | grep “processor” | wc -l

    查看物理cpu个数:cat /proc/cpuinfo | grep “physical id” | sort | uniq | wc -l

    查看每个物理cpu的核数cores:cat /proc/cpuinfo | grep “cpu cores”

    如果所有物理cpu的cores个数加起来小于逻辑cpu的个数,则该cpu使用了超线程技术。查看每个物理cpu中逻辑cpu的个数:cat /proc/cpuinfo | grep “siblings”

    查看内存使用情况

    查看内存占用情况:free -m

    参数说明

    Mem:内存的使用情况总览表。

    total:机器总的物理内存 单位为:M

    used:用掉的内存。

    free:空闲的物理内存。

    [root@localhost ~]# cat /etc/centos-release
    CentOS Linux release 7.2.1511 (Core)
    
    [root@localhost ~]# cat /proc/cpuinfo | grep "processor" | wc -l
    4
    [root@localhost ~]# cat /proc/cpuinfo | grep "physical id" | sort | uniq | wc -l
    4
    
    [root@localhost ~]# cat /proc/cpuinfo | grep "cpu cores"
    cpu cores       : 1
    cpu cores       : 1
    cpu cores       : 1
    cpu cores       : 1
    
    [root@localhost ~]# free -m
                  total        used        free      shared  buff/cache   available
    Mem:           7825         850        6241           9         733        6714
    Swap:          8063           0        8063
    

    部署web应用

    上传war包到linux服务器,然后进行部署

    我的web应用的名字叫tomcat-optimization,主要是提供了一个查询用户列表的接口,该接口会去阿里云数据库查询用户列表,没有任务业务逻辑的处理

    # 删除tomcat的/webapps/ROOT目录的所有文件
    cd /webapps/ROOT
    rm -rf *
    
    # 上传war包到tomcat的/webapps/ROOT,然后解压
    jar -xvf tomcat-optimization.war
    rm -rf tomcat-optimization.war
    
    # 进入tomcat的/bin目录重启tomcat
    cd /bin
    ./shutdown.sh
    ./startup.sh
    

    访问接口地址: http://10.172.0.202:8080/user/listUser

    [{
    	"id": 1,
    	"account": "lilei",
    	"password": "123456",
    	"userName": "李雷",
    	"gender": 1,
    	"age": 15,
    	"birthday": "2001-01-01 01:01:38",
    	"createTime": "2016-03-01 19:09:55"
    }, {
    	"id": 2,
    	"account": "hanmeimei",
    	"password": "123456",
    	"userName": "韩梅梅",
    	"gender": 0,
    	"age": 14,
    	"birthday": "2002-01-01 01:01:38",
    	"createTime": "2016-03-01 19:09:55"
    }, {
    	"id": 3,
    	"account": "lucy",
    	"password": "123456",
    	"userName": "露西",
    	"gender": 0,
    	"age": 13,
    	"birthday": "2003-01-01 01:01:38",
    	"createTime": "2016-03-01 19:09:55"
    }]
    

    使用Apache JMeter进行性能测试

    Apache JMeter是Apache组织开发的基于Java的压力测试工具。 我们借助于此工具进行测试,将测试出tomcat的吞吐量等信息。

    下载安装

    下载地址:http://jmeter.apache.org/download_jmeter.cgi

    在这里插入图片描述

    注意:这里需要先安装好jdk8及其以上版本的环境,可以参考JDK安装与环境变量配置

    直接将下载好的zip压缩包进行解压即可。

    在这里插入图片描述

    进入bin目录,找到jmeter.bat文件,双机打开即可启动。

    在这里插入图片描述

    JMeter启动页面

    在这里插入图片描述

    JMeter主页面

    在这里插入图片描述

    修改语言

    默认的主题是黑色风格的主题并且语言是英语,这样不太方便使用,所以需要修改下语言。

    设置语言为简体中文。

    在这里插入图片描述

    修改语言完成的界面

    在这里插入图片描述

    创建接口的测试用例

    测试接口之前需要调整Windows环境配置,不然会报如下错误

    JMeter java.net.BindException: Address already in use: connect
    

    出现原因
    TCP/IP连接数不够或TIME_WAIT中存在很多链接,导致吞吐量低。

    解决方案
    从问题的原因分析,有两种解决方案,一是增加预留给TCP/IP服务的临时端口的数量,二是加快被占用端口的释放速度。

    解决办法
    1、打开注册表:regedit
    2、HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\ Services\TCPIP\Parameters
    3、新建 DWORD值,name:TCPTimedWaitDelay,value:30(十进制) –> 设置为30秒,默认是240秒
    4、新建 DWORD值,name:MaxUserPort,value:65534(十进制) –> 设置最大连接数65534
    5、重启系统

    第一步:设置测试计划的名称

    在这里插入图片描述

    第二步:添加线程组,使用线程模拟用户的并发

    在这里插入图片描述

    在这里插入图片描述

    1000个线程,每个线程循环10次,也就是tomcat会接收到10000个请求。

    第三步:添加http请求

    在这里插入图片描述

    设置http请求

    在这里插入图片描述

    第四步:添加请求监控

    在这里插入图片描述

    启动与进行接口测试

    在这里插入图片描述

    查看测试报告

    在聚合报告中,重点看吞吐量。

    在这里插入图片描述

    调整Tomcat参数进行优化

    通过上面测试可以看出,tomcat在不做任何调整时,吞吐量为697次/秒。这个吞吐量跟接口的业务逻辑关系很大,如果业务逻辑复杂,需要比较长时间计算的,可能吞吐量只有几十次/秒,我这里测试的时候没有添加任务业务逻辑,才会出现吞吐量为697次/秒的情况。这里的吞吐量最好是经过多次测试取平均值,因为单次测试具有一定的随机性

    禁用AJP连接

    修改conf下的server.xml文件,将AJP服务禁用掉即可。

    <!-- <Connector port="8009" protocol="AJP/1.3" redirectPort="8443" /> -->
    

    在这里插入图片描述

    在这里插入图片描述

    这里经过9次测试,测试结果如下704 730 736 728 730 727 714 708 735 平均是723

    可以看到,禁用AJP服务后,吞吐量会有所提升。

    当然了,测试不一定准确,需要多测试几次才能看出是否有提升。

    设置线程池

    通过设置线程池,调整线程池相关的参数进行测试tomcat的性能。有关线程池更多更详细的配置参考Tomcat官网提供的配置详解

    最大线程数为150,初始为4

    <Executor name="tomcatThreadPool" namePrefix="catalina-exec-"
            maxThreads="150" minSpareThreads="4" prestartminSpareThreads="true"/>
    
    <!--在Connector中设置executor属性指向上面的执行器-->
    <Connector executor="tomcatThreadPool" port="8080" protocol="HTTP/1.1"
                   connectionTimeout="20000"
                   redirectPort="8443" />
    

    在这里插入图片描述

    经过9次测试,测试结果如下705 725 702 729 733 738 735 728 平均是724

    最大线程数为500,初始为50

    <Executor name="tomcatThreadPool" namePrefix="catalina-exec-"
            maxThreads="500" minSpareThreads="50" prestartminSpareThreads="true"/>
    
    <!--在Connector中设置executor属性指向上面的执行器-->
    <Connector executor="tomcatThreadPool" port="8080" protocol="HTTP/1.1"
                   connectionTimeout="20000"
                   redirectPort="8443" />
    

    测试结果:733 724 718 728 734 721 720 723 平均725

    吞吐量为725次/秒,性能有所提升。

    最大线程数为1000,初始为200

    <Executor name="tomcatThreadPool" namePrefix="catalina-exec-"
            maxThreads="1000" minSpareThreads="200" prestartminSpareThreads="true"/>
    
    <!--在Connector中设置executor属性指向上面的执行器-->
    <Connector executor="tomcatThreadPool" port="8080" protocol="HTTP/1.1"
                   connectionTimeout="20000"
                   redirectPort="8443" />
    

    吞吐量为732,性能有所提升。

    测试结果 737 729 730 738 735 726 725 740 平均732

    最大线程数为5000,初始为1000

    是否是线程数最多,速度越快呢? 我们来测试下。

    <Executor name="tomcatThreadPool" namePrefix="catalina-exec-"
            maxThreads="5000" minSpareThreads="1000" prestartminSpareThreads="true"/>
    
    <!--在Connector中设置executor属性指向上面的执行器-->
    <Connector executor="tomcatThreadPool" port="8080" protocol="HTTP/1.1"
                   connectionTimeout="20000"
                   redirectPort="8443" />
    

    测试结果 727 733 728 725 738 729 737 735 739 平均732

    可以看到,虽然最大线程已经设置到5000,但是实际测试效果并不理想,并且平均的响应时间也边长了,所以单纯靠提升线程数量是不能一直得到性能提升的。

    设置最大等待队列数

    默认情况下,请求发送到tomcat,如果tomcat正忙,那么该请求会一直等待。这样虽然可以保证每个请求都能请求到,但是请求时间就会边长。

    有些时候,我们也不一定要求请求一定等待,可以设置最大等待队列大小,如果超过就不等待了。这样虽然有些请求是失败的,但是请求时间会虽短。典型的应用:12306。

    <!--最大等待数为100-->
    <Executor name="tomcatThreadPool" namePrefix="catalina-exec-"
            maxThreads="500" minSpareThreads="100" prestartminSpareThreads="true" maxQueueSize="100"/>
    
    <!--在Connector中设置executor属性指向上面的执行器-->
    <Connector executor="tomcatThreadPool" port="8080" protocol="HTTP/1.1"
                   connectionTimeout="20000"
                   redirectPort="8443" />
    

    在这里插入图片描述

    测试结果:

    • 平均响应时间:0.438秒,响应时间明显缩短
    • 错误率:43.07%,错误率超过40%,也可以理解,最大线程为500,测试的并发为1000
    • 吞吐量:1359次/秒,吞吐量明显提升

    结论:响应时间、吞吐量这2个指标需要找到平衡才能达到更好的性能。

    设置nio2的运行模式

    将最大线程设置为500进行测试:

    <Executor name="tomcatThreadPool" namePrefix="catalina-exec-"
            maxThreads="500" minSpareThreads="100" prestartminSpareThreads="true"/>
    
    <!-- 设置nio2 -->
    <Connector executor="tomcatThreadPool" port="8080" protocol="org.apache.coyote.http11.Http11Nio2Protocol"
                   connectionTimeout="20000"
                   redirectPort="8443" />
    

    从测试结果可以看到,平均响应时间有缩短,吞吐量有提升,可以得出结论:nio2的性能要高于nio。

    参数说明与最佳实践

    具体参数参考官网说明

    执行器参数说明(加粗是重点)

    Attribute Description
    threadPriority (优先级) (int) 执行程序中线程的线程优先级,默认值为 5Thread.NORM_PRIORITY常量的值)
    daemon(守护进程) (布尔) 线程是否应该是守护程序线程,默认值为 true
    namePrefix(名称前缀) (String) 执行程序创建的每个线程的名称前缀。单个线程的线程名称将为namePrefix+threadNumber
    maxThreads(最大线程数) (int) 此池中活动线程的最大数量,默认为 200
    minSpareThreads(最小活跃线程数) (int) 始终保持活动状态的最小线程数(空闲和活动),默认值为 25
    maxIdleTime(空闲线程等待时间) (int) 空闲线程关闭之前的毫秒数,除非活动线程的数目小于或等于minSpareThreads。默认值为60000(1分钟)
    maxQueueSize(最大的等待队里数,超过则请求拒绝) (int) 在我们拒绝执行之前可以排队等待执行的可运行任务的最大数量。默认值为Integer.MAX_VALUE
    prestartminSpareThreads(是否在启动时就生成minSpareThreads个线程) (boolean) 在启动执行程序时是否应启动minSpareThreads,默认值为 false
    threadRenewalDelay(重建线程的时间间隔) (long) 如果配置了ThreadLocalLeakPreventionListener,它将通知该执行程序已停止的上下文。上下文停止后,池中的线程将更新。为避免同时更新所有线程,此选项设置了任意两个线程之间的延迟。该值以毫秒为单位,默认值为1000ms。如果值为负,则不更新线程。

    执行器最佳实践

    此最佳配置仅供参考

    <Executor name="tomcatThreadPool" namePrefix="catalina-exec-"
            maxThreads="800" minSpareThreads="100" maxQueueSize="100"                                 prestartminSpareThreads="true"/>
    

    连接器参数说明

    可以看到除了这几个基本配置外并无特殊功能,所以我们需要对 Connector 进行扩展。

    其中Connector 支持参数属性可以参考Tomcat官方网站,本文就只介绍些常用的。

    通用属性(加粗是重点)
    Attribute Description
    allowTrace 如果需要服务器能够处理用户的HAED/TRACE请求,这个值应该设置为true,默认值是false
    asyncTimeout 默认超不时候以毫秒为单位的异步恳求。若是没有指定,该属性被设置为10000(10秒)
    enableLookups 设置为true是否要调用以 request.getRemoteHost()执行DNS查找以返回远程客户端的实际主机名。设置为false跳过DNS查找并改为以字符串形式返回IP地址(从而提高性能)。默认情况下,DNS查找被禁用。
    maxHeaderCount 容器允许的请求头字段的最大数目。请求中包含比指定的限制更多的头字段将被拒绝。值小于0表示没有限制。如果没有指定,默认设置为100。
    maxParameterCount 将被容器自动解析的最大数量的参数和值对(GET加上POST)。参数值对超出此限制将被忽略。值小于0表示没有限制。如果没有指定,默认为10000。请注意, FailedRequestFilter 过滤器可以用来拒绝达到了极限值的请求。
    maxPostSize 容器FORM URL参数解析将处理的POST的最大大小(以字节为单位)。可以通过将此属性设置为小于零的值来禁用该限制。如果未指定,则此属性设置为2097152(2兆字节)。请注意, FailedRequestFilter 可以使用拒绝超过此限制的请求。
    maxSavePostSize 将被容器在FORM或CLIENT-CERT认证中保存/缓冲的POST的最大尺寸(以字节为单位)。对于这两种类型的身份验证,在用户身份验证之 前,POST将被保存/缓冲。对于POST CLIENT-CERT认证,处理该请求的SSL握手和缓冲清空期间,POST将被缓存。对于Form认证,POST将被保存,同时用户将被重定向到登陆 表单。POST将被一直保留直到用户成功认证或者认证请求关联的会话超时。将此属性设置为-1可以禁用此限制。将此属性设置为0,POST数据在身份验证 过程中将不被保存。如果没有指定,该属性设置为4096(4千字节)。
    parseBodyMethods 以逗号分隔的HTTP方法列表,通过方法列表,等同于POST方法,request 正文将被解析成请求参数。这在RESTful应用程序要支持以POST式的语义解析PUT请求中是非常有用的。需要注意的是设置其他值(不是POST)会导致Tomcat的行为违反servlet规范的目的。在这里为了符合HTTP规范明确禁止HTTP方法TRACE。默认值是POST
    port 连接器 将在其上创建服务器套接字并等待传入连接的TCP端口号。您的操作系统将仅允许一个服务器应用程序侦听特定IP地址上的特定端口号。如果使用特殊值0(零),则Tomcat将随机选择一个空闲端口用于此连接器。这通常仅在嵌入式和测试应用程序中有用。
    protocol 设置协议以处理传入流量。默认值为 HTTP/1.1使用自动切换机制选择基于Java NIO的连接器或基于APR / native的连接器。如果PATH(Windows)或LD_LIBRARY_PATH(在大多数Unix系统上)环境变量包含Tomcat本机库,并且AprLifecycleListener用于初始化APR的库的useAprConnector属性设置为 true,则将使用APR /本机连接器。如果找不到本机库或未配置属性,则将使用基于Java NIO的连接器。请注意,APR /本机连接器的HTTPS设置与Java连接器的设置不同。
    要使用显式协议而不是依赖于上述自动切换机制,可以使用以下值:
    org.apache.coyote.http11.Http11NioProtocol-非阻塞Java NIO连接器
    org.apache.coyote.http11.Http11Nio2Protocol-非阻塞Java NIO2连接器-APR
    org.apache.coyote.http11.Http11AprProtocol/本地连接器。
    也可以使用自定义实现。
    看看我们的连接器比较表。对于Java和Java连接器,http和https的配置相同。
    有关APR连接器和特定于APR的SSL设置的更多信息,请访问APR文档
    proxyName 如果这个连接正在使用的代理服务器配置,配置该属性指定的服务器的名称,可以调用request.getServerName()返回。有关更多信息,请参见代理支持。
    proxyPort 如果这个连接正在使用的代理服务器配置,配置该属性指定服务器端口,可以调用request.getServerPort()返回。有关更多信息,请参见代理支持。
    redirectPort 如果该连接器支持非SSL请求,并且接收到的请求为满足安全约束需要SSL传输, Catalina 将自动将请求重定向到指定的端口号。
    scheme 将该属性设置为你想调用request.getScheme()返回的协议的名称。例如,对于SSL连接器,你会将此属性设置为“HTTPS ”。默认值是“ HTTP ”。
    secure 如果你想调用request.isSecure()收到此连接器的请求返回true,请该该属性设置为true。您希望SSL连接器或非SSL连接器接收数据通过一个SSL加速器,像加密卡,SSL设备,甚至一个web服务器。默认值是假的。
    URIEncoding 解决我们的乱码问题,这将指定使用的字符编码,来解码URI字符。如果没有指定,ISO-8859-1将被使用。
    useBodyEncodingForURI 这指定是否应该用于URI查询参数,而不是使用URIEncoding contentType中指定的编码。此设置兼容性Tomcat 4.1.x版(该版在contentType中指定编码,或者使用request.setCharacterEncoding的方法显式设置(参数为 URL传来的值)。默认值false。
    useIPVHosts 将该属性设置为true会导致Tomcat使用收到请求的IP地址,来确定将请求发送到哪个主机。默认值是假的。
    xpoweredBy 将此属性设置为true会导致Tomcat支持使用Servlet规范的通知,(在规范中推荐使用头字段)。默认值是假的。
    标准实现(加粗是重点)

    除了上面列出的常见的连接器属性,标准的HTTP连接器(BIO,NIO和APR/native)都支持以下属性。

    Attribute Description
    acceptCount 当所有可能的请求处理线程都在使用时,传入连接请求的最大队列长度。当队列满时收到的任何请求将被拒绝。默认值是100。
    acceptorThreadCount 用于接受连接的线程的数量。在一个多CPU的机器上,增加该值,虽然你可能不会真正需要超过2个。此外,有很多非保持活动连接,您可能需要增加这个值。默认值是 1。
    acceptorThreadPriority 接收器线程的优先级。该线程用来接受新的连接。默认值是5(java.lang.Thread.NORM_PRIORITY常量)。更多这个优先级是什么意思的详细信息,请查看java.lang.Thread的类的JavaDoc 。
    address 对于拥有多个IP地址的服务器,该属性指定哪个地址将被用于在指定端口上监听。默认情况下,该端口将被用于与服务器相关联的所有IP地址。
    bindOnInit 控制连接器绑定时套接字的使用。缺省情况,当连接器被启动时套接字被绑定和当连接器被销毁时套接字解除绑定。如果设置为false,连接器启动时套接字被绑定,连接器停止时套接字解除绑定。
    compressableMimeType 该值是一个被用于HTTP压缩的逗号分隔的MIME类型列表。默认值是text / html类型,为text / xml,text / plain。
    compression 通常会在ngnix里面配置压缩 ,开启压缩GZIP 为了节省服务器带宽,连接器可以使用HTTP/1.1 GZIP压缩。可接受的参数的值是“off ”(禁用压缩),“on ”(允许压缩,这会导致文本数据被压缩),“force ”(强制在所有的情况下压缩),或者一个整数值(这是相当于为“on”,但指定了输出之前被压缩的数据最小量)。如果不知道内容长度但被设置为“on”或更积极的压缩,输出的数据也将被压缩。如果没有指定,该属性被设置为“关”。 注意:这是使用压缩(节省您的带宽)和使用sendfile功能(节省你的CPU周期)之间的权衡。如果连接器支持sendfile功能,例如NIO连接,则使用sendfile将优先于压缩。症状是48 KB的静态文件将未压缩就发送。你可以如下文所述通过设置连接器的useSendfile属性来关闭sendfile,或在默认的conf/web.xml或者你的web应用的web.xml中配置DefaultServlet来改变sendfile的使用量阈值。
    compressionMinSize 如果压缩被设置为“on”,那么该属性可以用于指定在输出之前被压缩的数据的最小量。如果未指定,此属性默认为“2048”。
    connectionLinger 连接器的套接字被关闭时的逗留秒数。如果没有指定,将使用默认的JVM。
    connectionTimeout 在将提交的请求URI行呈现之后,连接器将等待接受连接的毫秒数。使用值-1表示没有超时(即无限)。默认值是60000(60秒),但请注意,Tomcat的标准server.xml中,设置为20000(即20秒)。
    connectionUploadTimeout 上传数据过程中,指定的以毫秒为单位超时时间。只有在设置disableUploadTimeout为false有效。
    disableUploadTimeout 此标志允许servlet容器在数据上传时使用不同的连接超时,通常较长。如果没有指定,该属性被设置为true,禁用上传超时。
    executor 指向Executor元素的引用。如果这个属性被设置,并且被命名的executor存在,连接器将使用这个executor,而其他所有线程相关属性将被忽略。请注意共享的executor如果没有指定到一个连接器,则该连接器将使用一个私有的,内部的executor来提供线程池。
    executorTerminationTimeoutMillis The time that the private internal executor will wait for request processing threads to terminate before continuing with the process of stopping the connector. If not set, the default is 0 (zero) for the BIO connector and 5000 (5 seconds) for the NIO and APR/native connectors.
    keepAliveTimeout 此连接器在关闭连接之前将等待另一个HTTP请求的毫秒数。默认值是使用已设置的connectionTimeout属性的值。使用值-1表示没有超时(即无限)。
    maxConnections 在任何给定的时间服务器接受并处理的最大连接数。当这个数字已经达到了,服务器将不会接受任何连接,直到连接的数量降到低于此值。基于acceptCount的设置,操作系统可能仍然接受连接。默认值根据不同的连接器类型而不同。对于BIO,默认的是maxThreads的值,除非使用了Executor,在这种情况下默认值是executor的maxThreads值 。对于NIO的默认值是10000。APR /native的默认值是8192。 需要注意的是Windows系统的APR/native,所配置的值将减少到小于或等于maxConnections的1024的倍数的最大值。这样做是出于性能方面的考虑。如果设置的值-1,maxConnections功能被禁用,而且连接数将不做计算。
    maxExtensionSize 限制HTTP区块请求中区块扩展的总长度。如果值为-1,则不施加任何限制。如果未指定,8192将使用默认值。
    maxHttpHeaderSize 请求和响应的HTTP头的(以字节为单位的)最大尺寸。如果没有指定,该属性被设置为8192(8 KB)。
    maxKeepAliveRequests HTTP请求最大长连接个数。将此属性设置为1,将禁用HTTP/1.0、以及HTTP/1.1的长连接。设置为-1,不禁用。如果没有指定,该属性被设置为100。
    maxSwallowSize Tomcat会为中止的上载而吞下的请求正文字节的最大数量(不包括传输编码开销)。上载中止是指Tomcat知道将忽略请求主体,但客户端仍将其发送。如果Tomcat不吞咽该主体,则客户端不太可能看到响应。如果未指定,将使用默认值2097152(2兆字节)。小于零的值表示不应强制执行任何限制。
    maxThreads 最多同时处理的连接数,Tomcat使用线程来处理接收的每个请求。这个值表示Tomcat可创建的最大的线程数。如果没有指定,该属性被设置为200。如果使用了execute将忽略此连接器的该属性,连接器将使用execute,而不是一个内部线程池来处理请求。
    maxTrailerSize 限制一个分块的HTTP请求中的最后一个块的尾随标头的总长度。如果该值是-1,没有限制的被强加。如果没有指定,默认值是8192。
    minSpareThreads 始终保持运行最小线程数。如果没有指定,则默认为10。
    noCompressionUserAgents 该值是一个正则表达式(使用java.util.regex),匹配不应该使用压缩的HTTP客户端的用户代理标头。因为这些客户端,虽然他们宣称支持压缩功能,但实现不完整。默认值是一个空字符串(正则表达式匹配禁用)。
    processorCache 协议处理器缓存Processor对象以提高性能。此设置规定了这些对象有多少能得到缓存。-1意味着无限制,默认为200。如果不使用Servlet 3.0的异步处理,一个好的默认是使用maxThreads设置。如果使用Servlet 3.0的异步处理,一个好的默认是使用maxThreads和最大预期的并发请求(同步和异步)的最大值中的较大值。
    restrictedUserAgents 该值是一个正则表达式(使用java.util.regex),匹配用户代理头的HTTP浏览器将不能使用HTTP/1.1或HTTP/1.0长连接,即使该浏览器宣称支持这些功能的。默认值是一个空字符串(正则表达式匹配禁用)。
    server 覆盖服务器的HTTP响应头。如果设置了这个属性的值将覆盖Web应用程序设置的Tomcat的默认头和任何服务器头。如果没有设置,应用程序指定的任何值将被使用。如果应用程序没有指定一个值,那么Apache-Coyote/1.1将被使用。除非你是偏执狂,你将不再需要此功能。
    socketBuffer 为套接字输出缓冲而提供的缓冲区的大小(以字节为单位)。-1可以被指定来禁止使用的缓冲区。默认情况下,一个9000个字节的缓冲区将被使用。
    SSLEnabled 在连接器上使用此属性来启用SSL加密传输。如果要打开SSL握手/加密/解密,请设置true。默认值是false。当设置这个值为true时,为了传递正确的request.getScheme()和 request.isSecure()到servlets,你需要设置scheme和secure属性。更多信息请查看SSL支持。
    tcpNoDelay 如果设置为true,TCP_NO_DELAY选项将被设置在服务器上的套接字上,在大多数情况下,这样可以提高性能。默认设置为true。
    threadPriority 在JVM中请求处理线程的优先级。默认值是5(java.lang.Thread.NORM_PRIORITY常量值)。关于优先级的更多详细信息,请查看java.lang.Thread的类的JavaDoc
    upgradeAsyncWriteBufferSize The default size of the buffer to allocate to for asynchronous writes that can not be completed in a single operation. Data that can’t be written immediately will be stored in this buffer until it can be written. If more data needs to be stored than space is available in the buffer than the size of the buffer will be increased for the duration of the write. If not specified the default value of 8192 will be used.

    连接器最佳实践

    此最佳配置仅供参考

    <Connector executor="tomcatThreadPool" port="8080" 						                            protocol="org.apache.coyote.http11.Http11Nio2Protocol" 
               connectionTimeout="20000" redirectPort="8443" 
               enableLookups="false" maxPostSize="10485760" URIEncoding="UTF-8" 	                    acceptCount="100" acceptorThreadCount="2" disableUploadTimeout="true"                    maxConnections="10000" SSLEnabled="false"/>
    

    调整JVM参数进行优化

    接下来,通过设置jvm参数进行优化,为了测试一致性,依然将最大线程数设置为500,启用nio2运行模式

    设置并行垃圾回收器

    在/bin/catalina.sh文件第一行添加如下参数,gc日志输出到/logs/gc.log

    #年轻代、老年代均使用并行收集器,初始堆内存64M,最大堆内存512M
    JAVA_OPTS="-XX:+UseParallelGC -XX:+UseParallelOldGC -Xms64m -Xmx512m -XX:+PrintGCDetails -XX:+PrintGCTimeStamps -XX:+PrintGCDateStamps -XX:+PrintHeapAtGC -Xloggc:../logs/gc.log"
    

    在这里插入图片描述

    测试结果与默认的JVM参数结果接近。

    查看gc日志文件

    将gc.log文件上传到gceasy.io查看gc中是否存在问题。上传文件后需要等待一段时间,需要耐心等待。

    在这里插入图片描述

    问题一:系统所消耗的时间大于用户时间

    在这里插入图片描述

    如果在报告中显示System Time greater than User Time,系统所消耗的时间大于用户时间,这反应出的服务器的性能存在瓶颈,调度CPU等资源所消耗的时间要长一些。

    问题二:线程暂停时间有点长

    在这里插入图片描述

    可以关键指标中可以看出,吞吐量表现不错,但是gc时,线程的暂停时间稍有点长。

    问题三:GC总次数过多

    在这里插入图片描述

    通过GC的统计可以看出:

    • 年轻代的gc有100次,次数有点多,说明年轻代设置的大小不合适,需要调整
    • FullGC有7次,说明堆内存的大小不合适,需要调整

    问题四:年轻代内存不足导致GC

    在这里插入图片描述

    从GC原因的可以看出,年轻代大小设置不合理,导致了多次GC。

    调整年轻代大小

    调整jvm配置参数

    JAVA_OPTS="-XX:+UseParallelGC -XX:+UseParallelOldGC -Xms128m -Xmx1024m -XX:NewSize=64m -XX:MaxNewSize=256m -XX:+PrintGCDetails -XX:+PrintGCTimeStamps -XX:+PrintGCDateStamps -XX:+PrintHeapAtGC -Xloggc:../logs/gc.log"
    

    将初始堆大小设置为128m,最大为1024m,初始年轻代大小64m,年轻代最大256m

    在这里插入图片描述

    从测试结果来看,吞吐量以及响应时间均有提升。

    查看gc日志

    在这里插入图片描述

    可以看到GC次数要明显减少,说明调整是有效的。

    在这里插入图片描述

    GC次数有所减少

    在这里插入图片描述

    设置G1垃圾回收器

    #设置了最大停顿时间100毫秒,初始堆内存128m,最大堆内存1024m
    JAVA_OPTS="-XX:+UseG1GC -XX:MaxGCPauseMillis=100 -Xms128m -Xmx1024m -XX:+PrintGCDetails -XX:+PrintGCTimeStamps -XX:+PrintGCDateStamps -XX:+PrintHeapAtGC -Xloggc:../logs/gc.log"
    

    测试结果

    在这里插入图片描述

    可以看到,吞吐量有所提升,评价响应时间也有所缩短。

    在这里插入图片描述

    G1集合阶段统计

    在这里插入图片描述

    JVM配置最佳实践

    此最佳配置仅供参考

    JAVA_OPTS="-Dfile.encoding=UTF-8-server -Xms1024m -Xmx2048m -XX:NewSize=512m -XX:MaxNewSize=1024m -XX:PermSize=256m -XX:MaxPermSize=256m -XX:MaxTenuringThreshold=10-XX:NewRatio=2 -XX:+DisableExplicitGC"
    

    参数说明

    file.encoding 默认文件编码

    -Xmx1024m 设置JVM最大可用内存为1024MB

    -Xms1024m 设置JVM最小内存为1024m。此值可以设置与-Xmx相同,以避免每次垃圾回收完成后JVM重新分配内存。

    -XX:NewSize 设置年轻代大小

    -XX:MaxNewSize 设置最大的年轻代大小

    -XX:PermSize 设置永久代大小

    -XX:MaxPermSize 设置最大永久代大小

    -XX:NewRatio=4 设置年轻代(包括Eden和两个Survivor区)与终身代的比值(除去永久代)。设置为4,则年轻代与终身代所占比值为1:4,年轻代占整个堆栈的1/5

    -XX:MaxTenuringThreshold=0 设置垃圾最大年龄,默认为:15。如果设置为0的话,则年轻代对象不经过Survivor区,直接进入年老代。对于年老代比较多的应用,可以提高效率。如果将此值设置为一个较大值,则年轻代对象会在Survivor区进行多次复制,这样可以增加对象再年轻代的存活时间,增加在年轻代即被回收的概论。

    -XX:+DisableExplicitGC 这个将会忽略手动调用GC的代码使得System.gc()的调用就会变成一个空调用,完全不会触发任何GC。

    总结

    通过上述的测试,可以总结出,对tomcat性能优化就是需要不断的进行调整参数,然后测试结果,可能会调优也可能会调差,这时就需要借助于gc的可视化工具来看gc的情况。再帮我我们做出决策应该调整哪些参数。

    再次重申本博客的目的不在于给出最佳配置,而是带领开发者,能够从实际情况出发,通过不断的调节tomcat和jvm参数,去发现吞吐量,平均响应时间和错误率等信息的变化,同时根据服务器的cpu和内存等信息,结合接口的业务逻辑,最好是测试使用率最高,并发最大,或者是最重要的接口(比如下单支付接口),设置最优的tomcat和jvm配置参数

    展开全文
  • 结点有两种类型:内部结点和叶结点,其中内部结点表示一特征或属性,叶结点表示一类。 分类树 分类树是一种描述对实例进行分类的树形结构。 用决策树分类,从根结点开始,对实例的某一特征进行测试,...

    分类目录:《深入理解机器学习》总目录
    相关文章:
    基于决策树的模型(一)分类树和回归树
    基于树的模型(二):集成学习之Bagging和Random Forest
    基于树的模型(三):集成学习之GBDT和XGBoost
    基于树的模型(四):随机森林的延伸——深度森林(gcForest)
    基于树的模型(五):从零开始用Python实现ID3决策树
    基于树的模型(六):Python实现CART决策树并利用Tkinter构建GUI对决策树进行调优
    基于树的模型(七):RF/XGBoost等算法实践与决策树Scala实践等(材料准备中)


    决策树(Decision Tree)是一种基本的分类与回归方法,当决策树用于分类时称为分类树,用于回归时称为回归树。本文主要讨论决策树中的分类树与回归树的一些基本理论,后续文章会继续讨论决策树的BoostingBagging相关方法。

    决策树由结点和有向边组成。结点有两种类型:内部结点和叶结点,其中内部结点表示一个特征或属性,叶结点表示一个类。一般的,一棵决策树包含一个根结点、若干个内部结点和若干个叶结点。叶结点对应于决策结果,其他每个结点则对应于一个属性测试。每个结点包含的样本集合根据属性测试的结果被划分到子结点中,根结点包含样本全集,从根结点到每个叶结点的路径对应了一个判定测试序列。在下图中,圆和方框分别表示内部结点和叶结点。决策树学习的目的是为了产生一棵泛化能力强,即处理未见示例能力强的决策树。
    j决策树图示

    分类树

    分类树是一种描述对实例进行分类的树形结构。在使用分类树进行分类时,从根结点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子结点。这时,每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配,直至达到叶结点。最后将实例分到叶结点的类中。

    假设给定训练数据集:
    D={(x1,y1),(x2,y2),...,(xN,yN)}D=\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}其中,xi=(xi(1),xi(2),...,xi(n))T,x_i=(x_i^{(1)}, x_i^{(2)}, ..., x_i^{(n)})^T,为输入实例,即特征向量,nn为特征个数,i=12Ni=1,2…,NNN为样本容量,yi{1,2,...,K}y_i \in \{ 1, 2, ..., K\}为类标。分类树学习的目标是根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类。

    决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个,也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树,同时具有很好的泛化能力。从另一个角度看,决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个,我们选择的条件概率模型应该不仅对训练数据有很好的拟合,而且对未知数据有很好的预测。

    决策树学习用损失函数表示这一目标,其损失函数通常是正则化的极大似然函数,决策树学习的策略是以损失函数为目标函数的最小化。当损失函数确定以后,学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题,所以现实中决策树学习算法通常采用启发式方法,近似求解这一最优化问题。这样得到的决策树是次最优的。

    决策树分类算法
    输入:
    \qquad 训练集:D=(x1,y1),(x2,y2),,(xN,yN)D = {(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)}
    \qquad 属性集:A=a1,a2,,anA = {a_1, a_2, \cdots, a_n}
    过程:
    \qquad 函数TreeGenerate(D,A)TreeGenerate(D, A)
    输出:
    \qquad 以node为根节点的决策树
    算法:
    ( 1 ) 生成结点根node
    ( 2 ) if DD中样本全属于同一类别CkC_k then
    ( 3 ) \quad 将node标记为CkC_k类叶结点
    ( 4 ) \quad return
    ( 5 ) end if
    ( 6 ) if A=A = \varnothing OR DD中样本在AA上取值相同 then
    ( 7 ) \quad 将node标记为叶结点,其类别标记为DD中样本数最多的类
    ( 8 ) \quad return
    ( 9 )end if
    (10)从AA中选择最优划分属性aa_*
    (11)for aa_* 的每一个值ava_*^v do
    (12)\quad 为node生成一个分支:令DvD_v表示DD中在aa_*上取值为ava_*^v的样本子集
    (13)\quad if DvD_v为空 then
    (14)\qquad 将分支结点标记为叶结点,其类别标记为DD中样本最多的类
    (15)\qquad return
    (16)\quad else
    (17)\qquadTreeGenerate(Dv,A{a})TreeGenerate(D_v, A - \{a_*\})为分支结点
    (18)\quad end if
    (19)end for

    决策树学习的算法通常是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分,也对应着决策树的构建。开始,构建根结点,将所有训练数据都放在根结点。选择一个最优特征,按照这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类,那么构建叶结点,并将这些子集分到所对应的叶结点中去,如果还有子集不能被基本正确分类,那么就对这些子集选择新的最优特征,继续对其进行分割,构建相应的结点。如此递归地进行下去,直至所有训练数据子集被基本正确分类,或者没有合适的特征为止。最后每个子集都被分到叶结点上,即都有了明确的类。这就生成了一棵决策树。

    从上述过程中就可以看出,决策树的生成是一个递归过程。在决策树基本算法中,有三种情形会导致递归返回

    1. 当前结点包含的样本全属于同一类别,无需划分
    2. 当前属性集为空,或是所有样本在所有属性上取值相同,无法划分
    3. 当前结点包含的样本集合为空,不能划分

    在第二种情形下,我们把当前结点标记为叶结点,并将其类别设定为该结点所含样本最多的类别。在第三种情形下,同样把当前结点标记为叶结点,但将其类别设定为其父结点所含样本最多的类别。这两种情形的处理实质不同:第二种情况是在利用当前结点的后验分布,而第三种情况则是把父结点的样本分布作为当前结点的先验分布

    以上方法生成的决策树可能对训练数据有很好的分类能力,但对未知的测试数据却未必有很好的分类能力,即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝,将树变得更简单,从而使它具有更好的泛化能力。具体地,就是去掉过于细分的叶结点,使其回退到父结点,甚至更高的结点,然后将父结点或更高的结点改为新的叶结点。如果特征数量很多,也可以在决策树学习开始的时候,对特征进行选择,只留下对训练数据有足够分类能力的特征。

    可以看出,决策树学习算法包含特征选择决策树的生成决策树的剪枝过程。由于决策树表示一个条件概率分布,所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择,决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优,相对地,决策树的剪枝则考虑全局最优。

    决策树模型呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。分类树具有良好的可读性与分类速度快的优点。分类树在学习时,利用训练数据,根据损失函数最小化的原则建立分类树模型,在预测时,对新的数据,利用分类树模型进行分类。决策树学习通常包括3个步骤:特征选择、决策树的生成和决策树的修剪。

    决策树与if-then规则

    可以将决策树看成一个if-then规则的集合:由决策树的根结点到叶结点的每一条路径构建一条规则,路径上内部结点的特征对应着规则的条件,而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质——互斥并且完备。这就是说,每一个实例都被一条路径或一条规则所覆盖,而且只被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

    决策树与条件概率分布

    决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域,并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设XX为表示特征的随机变量,YY为表示类的随机变量,那么这个条件概率分布可以表示为PYXP(Y|X)XX取值于给定划分下单元的集合,YY取值于类的集合。各叶结点(单元)上的条件概率往往偏向某一个类,即属于某一类的概率较大。决策树分类时将该结点的实例强行分到条件概率大的那一类去。

    决策树的优缺点
    • 计算复杂度不高
    • 对中间缺失值不敏感
    • 解释性强,在解释性方面甚至比线性回归更强
    • 与传统的回归和分类方法相比,决策树更接近人的决策模式
    • 可以用图形表示,非专业人士也可以轻松理解
    • 可以直接处理定性的预测变量而不需创建哑变量
    • 决策树的预测准确性一般比回归和分类方法弱,但可以通过用集成学习方法组合大量决策树,显著提升树的预测效果

    特征选择

    特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。比如,我们希望构建一棵决策树来根据不同人的各种属性来预测每个人性别,那么对于属性“头发的长度”可能就要比属性“头发的颜色”所能包含的信息更多。因为一般来说,男生的头发要比女生的头发短,所以我们希望“头发的长度”这个属性处于决策树的上部。随着划分过程不断进行,我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的“纯度”(purity)越来越高。

    信息增益

    为了便于说明信息增益,先给出熵与条件熵的定义。在信息论与概率统计中,熵(entropy)是表示随机变量不确定性的度量。设XX是一个取有限个值的离散随机变量,其概率分布为:
    P(X=xi)=pi,i=1,2,,nP(X = x_i) = p_i, i = 1, 2, \cdots, n
    则随机变量XX的熵定义为:
    H(X)=i=1npilogpiH(X) = -\sum_{i = 1}^n p_i \log p_i
    在上式中,若pi=0p_i = 0,则定义pilogpi=0p_i \log p_i = 0。通常,上式中的对数以22为底或以ee为底(自然对数),这时熵的单位分别称作比特(bit)或纳特(nat).由定义可知,熵只依赖于XX的分布,而与XX的取值无关,所以也可将XX的熵记作H(p)H(p),即:
    H(p)=i=1npilogpiH(p) = -\sum_{i = 1}^n p_i \log p_i
    由此可见,熵越大,随机变量的不确定性就越大。从熵的定义可验证
    0H(p)logn0 \leq H(p) \leq \log n
    当随机变量只取两个值,例如1,0时,即XX的分布为:
    P(X=1)=p,P(X=0)=1p,0p1P(X = 1) = p,\quad P(X = 0) = 1-p, \quad 0≤p≤1
    其熵为:
    H(p)=plog2p(1p)log2(1p)H(p) = -p \log_2 p - (1 - p)\log_2 (1 - p)
    这时,熵H(p)H(p)随概率pp变化的曲线如下图所示(单位为比特):
    熵的变化曲线
    p=0p = 0p=1p = 1H(p)=0H(p) = 0,随机变量完全没有不确定,当p=0.5p = 0.5时,H(p)=1H(p) = 1,熵取值最大,随机变量不确定性最大。

    设有随机变量(X,Y)(X, Y),其联合概率分布为:

    P(X=xi,Y=yi)=pij{i=1,2,,nj=1,2,,m P(X = x_i, Y = y_i) = p_{ij} \quad \begin{cases} i = 1, 2, \cdots, n \\ j = 1, 2, \cdots, m \end{cases}

    条件熵H(YX)H(Y|X)表示在已知随机变量XX的条件下随机变量YY的不确定性。随机变量XX给定的条件下随机变量YY的条件熵(conditional entropy)H(YX)H(Y|X),定义为XX给定条件下YY的条件概率分布的熵对XX的数学期望:
    H(YX)=i=1npiH(YX=xi)H(Y|X) = \sum_{i = 1}^n p_iH(Y|X = x_i)

    其中,pi=P(X=xi),i=1,2,,np_i = P(X = x_i), i = 1, 2, \cdots, n

    当熵和条件熵中的概率由数据估计(如极大似然估计)得到时,所对应的熵与条件熵分别称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)。此时,如果有0概率,令0log0=00\log0 = 0

    信息增益(information gain)表示得知特征XX的信息而使得类YY的信息的不确定性减少的程度。特征aa_*对训练数据集DD的信息增益g(D,a)g(D, a_*),定义为集合DD的经验熵H(D)H(D)与特征aa_*给定条件下DD的经验条件熵H(Da)H(D|a_*)之差,即:
    g(D,a)=H(D)H(Da)g(D, a_*) = H(D) - H(D|a_*)
    一般地,熵H(Y)H(Y)与条件熵H(YX)H(Y|X)之差称为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

    决策树学习应用信息增益准则选择特征。给定训练数据集DD和特征aa_*,经验熵H(D)H(D)表示对数据集DD进行分类的不确定性。而经验条件熵H(Da)H(D|a_*)表示在特征aa_*给定的条件下对数据集DD进行分类的不确定性。那么它们的差,即信息增益,就表示由于特征aa_*而使得对数据集DD的分类的不确定性减少的程度。显然,对于数据集DD而言,信息增益依赖于特征,不同的特征往往具有不同的信息增益,信息增益大的特征具有更强的分类能力。

    根据信息增益准则的特征选择方法:对训练数据集(或子集)DD,计算其每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征。

    设训练数据集为DDD|D|表示其样本容量,即样本个数。设有KK个类CkC_kk=1,2,,Kk=1, 2, \cdots, KCk|C_k|为属于类CkC_k的样本个数,k=1KCk=D\sum_{k=1}^K |C_k| = |D|。设特征aa_*VV个不同的取值{a1,a2,,aV}\{ a_*^1, a_*^2, \cdots, a_*^V\},根据特征aa_*的取值将DD划分为VV个子集D1,D2,,DVD_1, D_2, \cdots, D_VDt|D_t|DtD_t的样本个数,i=1nDt=D\sum_{i=1}^n|D_t|=|D|。记子集DiD_i中属于类CkC_k的样本的集合为DikD_{ik}。即Dik=DiCkD_{ik} = D_i \cap C_kDik|D_{ik}|DikD_{ik}的样本个数。于是计算信息增益的方法如下:

    信息增益
    输入:训练数据集DD和特征aa_*
    输出:特征aa_*对训练数据集DD的信息增益g(D,a)g(D, a_*)
    1.计算数据集DD的经验熵H(D)H(D)H(D)=k=1KCkDlog2CkDH(D) = -\sum_{k=1}^K \frac{C_k}{D}\log_2\frac{C_k}{D}
    2.计算特征AA对数据集DD的经验条件熵H(DA)H(D|A)H(DA)=i=1nDiDH(Di)=i=1nDiDk=1KDikDilog2DikDiH(D|A) = \sum_{i=1}^n\frac{|D_i|}{D}H(D_i)=-\sum_{i=1}^n\frac{|D_i|}{D}\sum_{k=1}^K\frac{D_{ik}}{D_i}\log_2\frac{D_{ik}}{D_i}
    3.计算信息增益:g(D,a)=H(D)H(Da)g(D, a_*) = H(D) - H(D|a_*)

    一般而言,信息增益越大,则意味着使用特征aa_*来进行划分所获得的“纯度提升”越大。因此,我们可用信息增益来进行决策树的划分属性选择,即在上述决策树分类算法第10行使用a=arg maxaAg(D,a)a_* = \text{arg}\ \max_{a \in A}g(D, a)选择最优划分属性。著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性。

    ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征,递归地构建决策树。具体方法是:从根结点开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立子结点。之后,再对子结点递归地调用以上方法,构建决策树,直到所有特征的信息增益均很小或没有特征可以选择为止,最终得到一个决策树。ID3相当于用极大似然法进行概率模型的选择

    ID3算法
    输入:训练数据集DD,特征集AA,阈值ϵ\epsilon
    输出:决策树TT
    1.若DD中所有实例属于同一类CkC_k,则TT为单结点树,并将类CkC_k作为该结点的类标记,返回决策树TT
    2.若A=A = \varnothing,则TT为单结点树,并将DD中实例数最大的类CkC_k,作为该结点的类标记,返回决策树TT
    3.否则,计算AA中各特征对DD的信息增益,选择信息增益最大的特征aa_*
    4.如果aa_*的信息增益小于阈值ϵ\epsilon,则置TT为单结点树,并将DD中实例数最大的类CkC_k作为该结点的类标记,返回决策树TT
    5.否则,对aa_*的每一可能值ava_*^v,依a=ava_* = a_*^vDD分割为若干非空子集DvD_v,将DvD_v中实例数最大的类作为标记,构建子结点,由结点及其子结点构成决策树TT,返回决策树TT
    6.对第vv个子结点,以DvD_v为训练集,以A{a}A - \{a_*\}为特征集,递归地调用第(1)步~第(5)步,得到子树TvT_v,并返回子树TvT_v

    信息增益率

    信息增益值的大小是相对于训练数据集而言的,并没有绝对意义。在训练数据集的经验熵大的时候,信息增益值会偏大。反之,信息增益值会偏小。使用信息增益率(information gain ratio)可以对这一问题进行校正。这是特征选择的另一准则。特征aa_*对训练数据集DD的信息增益率gg(D,a)g_g(D, a_*)定义为其信息增益g(D,a)g(D, a_*)与训练数据集DD的经验熵H(D)H(D)之比:
    gg(D,a)=g(D,a)H(D)g_g(D, a_*) = \frac{g(D, a_*)}{H(D)}

    如前文所说,信息增益准则对可取值数目较多的属性有所偏好,为减少这种偏好可能带来的不利影响,著名的C4.5决策树算法不直接使用信息增益来选择划分属性,而是使用信息增益率来选择最优划分属性。

    C4.5算法
    输入:训练数据集DD,特征集AA,信息增益率阈值ϵ\epsilon,信息增益阈值α\alpha
    输出:决策树TT
    1.若DD中所有实例属于同一类CkC_k,则TT为单结点树,并将类CkC_k作为该结点的类标记,返回决策树TT
    2.若A=A = \varnothing,则TT为单结点树,并将DD中实例数最大的类CkC_k,作为该结点的类标记,返回决策树TT
    3.否则,计算AA中各特征对DD的信息增益和信息增益率,在信息增益大于α\alpha的特征中选择信息增益率最大的特征aa_*
    4.如果aa_*的信息增益率小于阈值ϵ\epsilon,则置TT为单结点树,并将DD中实例数最大的类CkC_k作为该结点的类标记,返回决策树TT
    5.否则,对aa_*的每一可能值ava_*^v,依a=ava_* = a_*^vDD分割为若干非空子集DvD_v,将DvD_v中实例数最大的类作为标记,构建子结点,由结点及其子结点构成决策树TT,返回决策树TT
    6.对第vv个子结点,以DvD_v为训练集,以A{a}A - \{a_*\}为特征集,递归地调用第(1)步~第(5)步,得到子树TvT_v,并返回子树TvT_v

    需注意的是,信息增益率准则对可取值数目较少的属性有所偏好,因此,C4.5算法并不是直接选择增益率最大的候选划分属性,而是使用了一个启发式的方法选择最优划分属性:先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的.。

    连续值处理

    实际的任务中常会遇到连续属性,对于全部为连续属性的样本来说,我们一般使用回归决策树来处理。C4.5算法则采用了二分法对连续属性进行处理。由于连续属性的可取值数目不再有限,因此,不能直接根据连续属性的可取值来对结点进行划分。此时,连续属性离散化技术可派上用场。最简单的策略是采用二分法对连续属性进行处理。

    给定样本集DD和连续属性aa,假定aaDD上出现了nn个不同的取值,将这些值从小到大进行排序,记为{a1,a2,a3,,an}\{a_1, a_2, a_3, \cdots, a_n\}。基于划分点tt可将DD分为子集Dt+D_t^+DtD_t^-,其中Dt+D_t^+包含那些在属性aa上取值大于tt的样本,而DtD_t^-则包含那些在属性aa上取值不大于tt的样本。显然,对相邻的属性取值aia^iai+1a^{i + 1}来说,tt在区间[ai,ai+1)[a^i, a^{i + 1})中取任意值所产生的划分结果相同.因此,对连续属性aa,我们可考察包含n1n-1个元素的候选划分点集合:
    Ta={ai+ai+12  1in1}T_a = \{\frac{a^i + a^{i + 1}}{2} \ | \ 1 \leq i \leq n - 1\}

    即把区间[ai,ai+1)[a^i, a^{i + 1})的中位点ai+ai+12\frac{a^i + a^{i + 1}}{2}作为候选划分点。然后,我们就可像离散属性值一样来考察这些划分点,选取最优的划分点进行样本集合的划分:
    Gain(D,a)=maxtTaGain(D,a,t)=maxtTaEnt(D)λ{,+}DtλDEnt(Dtλ) \begin{aligned} Gain(D, a) &= \max_{t \in T_a} Gain(D, a, t)\\ & = \max_{t \in T_a} Ent(D) - \sum_{\lambda \in \{-, +\}} \frac{D^\lambda _t}{D}Ent(D^\lambda _t) \end{aligned}

    其中Gain(D,a,t)Gain(D, a, t)是样本集DD基于划分点tt二分后的信息增益。于是,我们就可选择使Gain(D,a,t)Gain(D, a, t)最大化的划分点。

    缺失值处理

    现实任务中常会遇到不完整样本,即样本的某些属性值缺失。且在属性数目较多的情况下,有时会有大量样本出现缺失值。如果简单地放弃不完整样本,仅使用无缺失值的样本来进行学习,显然是对数据信息极大的浪费。显然,有必要考虑利用有缺失属性值的训练样例来进行学习。

    划分属性的选择

    给定训练集DD和属性aa,令D~\tilde{D}表示DD中在属性aa上没有缺失值的样本子集。显然,我们仅可根据D~\tilde{D}来判断属性aa的优劣。假定属性aaVV个可取值{a1,a2,a3,,aV}\{a^1, a^2, a^3, \cdots, a^V\},令D~v\tilde{D}^v表示D~\tilde{D}中在属性aa上取值为ava^v的样本子集,D~k\tilde{D}_k表示D~\tilde{D}中属于第kk(k=1,2,3,,K)(k = 1, 2, 3, \cdots, K)的样本子集,则显然有D~=k=1KD~k\tilde{D} = \bigcup^K_{k = 1}\tilde{D}_kD~=v=1VD~v\tilde{D} = \bigcup^V_{v = 1}\tilde{D}^v。假定我们为每个样本xx赋予一个权重ωx\omega_x,并定义:
    ρ=xD~ωxxDωxp~k=xD~kωxxD~ωxr~v=xD~vωxxD~ωx \begin{aligned} \rho & = \frac{\sum_{x \in \tilde{D}}\omega_x}{\sum_{x \in D}\omega_x}\\ \tilde{p}_k & = \frac{\sum_{x \in \tilde{D}_k}\omega_x}{\sum_{x \in \tilde{D}}\omega_x}\\ \tilde{r}_v & = \frac{\sum_{x \in \tilde{D}^v}\omega_x}{\sum_{x \in \tilde{D}}\omega_x} \end{aligned}

    直观地看,对于属性aaρ\rho表示无缺失值样本所占的比例,p~k\tilde{p}_k表示无缺失值样本中第kk类所占的比例,r~v\tilde{r}_v则表示无缺失值样本中在属性aa上取值ava^v的样本所占的比例。基于上述定义,我们可将信息增益的计算式推广为:
    Gain(D,a)=ρ×Gain(D~,a)=ρ×(Ent(D~)x=1Vr~vEnt(D~v)) \begin{aligned} Gain(D, a) &= \rho \times Gain(\tilde{D}, a)\\ & = \rho \times (Ent(\tilde{D}) - \sum_{x = 1}^V \tilde{r}_v Ent(\tilde{D}^v)) \end{aligned}

    对样本进行划分

    根据上面的定义,若样本xx在划分属性aa上的取值已知,则将xx划入与其取值对应的子结点,且样本权值在子结点中保持为ωx\omega_x。若样本xx在划分属性aa上的取值未知,则将xx同时划入所有子结点,且样本权值在与属性值ava^v对应的子结点中调整为r~v×ωx\tilde{r}_v \times \omega_x。直观地看,这就是让同一个样本以不同的概率划入到不同的子结点中去。

    基尼指数

    数据集DD的纯度还可用基尼值来度量:
    Gini(D)=k=1Kpk(1pk)=1k=1Kpk2Gini(D) = \sum^K_{k=1}p_k(1 - p_k) = 1 - \sum^K_{k=1}p_k^2

    其中,KK为类别数,pkp_k为样本点属于第kk类的概率。对于二类分类问题,若样本点属于第1个类的概率是pp,则概率分布的基尼指数为:
    Gini(D)=2p(1p)Gini(D) = 2p(1 - p)

    直观来说,Gini(D)Gini(D)反映了从数据集DD中随机抽取两个样本,其类别标记不一致的概率。因此,Gini(D)Gini(D)越小,则数据集DD的纯度越高。对于属性aa的基尼指数定义为:
    Gini_index(D,a)=v=1VDvDGini(Dv)Gini\_index(D, a) = \sum^V_{v = 1}\frac{D^v}{D}Gini(D^v)

    CART算法中,我们在候选属性集合AA中,选择那个使得划分后基尼指数最小的属性作为最优划分属性,即:a=argminaAGini_index(D,a)a_* = \text{arg}\min_{a \in A}Gini\_index(D, a)

    在二类分类问题中,基尼指数Gini(D)Gini(D)、熵H(p)H(p)的一半,和分类误差率的关系:
    特征选择方法对比
    其中,横坐标表示概率pp,纵坐标表示损失。可以看出基尼指数和熵的一半的曲线很接近,都可以近似地代表分类误差率。

    分类树的剪枝

    剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段。在决策树学习中,为了尽可能正确分类训练样本,结点划分过程将不断重复,有时会造成决策树分支过多,这时就可能因为对训练样本学习得“太好”了,以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此,可通过主动去掉一些分支来降低过拟合的风险。决策树剪枝的基本策略有预剪枝后剪枝

    预剪枝

    预剪枝是指在决策树生成过程中,对每个结点在划分前先进行估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点。停止决策树生长常用方法:

    1. 定义一个高度,当决策树达到该高度时就停止决策树的生长
    2. 达到某个节点的实例具有相同的特征向量,即使这些实例不属于同一类,也可以停止决策树的生长。这个方法对于处理数据的数据冲突问题比较有效。
    3. 定义一个阈值,当达到某个节点的实例个数小于阈值时就可以停止决策树的生长
    4. 定义一个阈值,通过计算每次扩张对系统性能的增益,并比较增益值与该阈值大小来决定是否停止决策树的生长。

    后剪枝

    后剪枝则是先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升,则将该子树替换为叶结点。相比于预剪枝,后剪枝更常用,因为在预剪枝中精确地估计何时停止树增长很困难。

    错误率降低剪枝(REP,Reduced-Error Pruning)

    错误率降低剪枝方法是一种比较简单的后剪枝的方法。在该方法中,可用的数据被分成两个样例集合:首先是训练集,它被用来形成学习到的决策树,另一个是与训练集分离的验证集,它被用来评估这个决策树在后续数据上的精度,确切地说是用来评估修剪这个决策树的影响。学习器可能会被训练集中的随机错误和巧合规律所误导,但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验。

    错误率降低剪枝方法考将树上的每个节点作为修剪的候选对象,再决定是对该节点进行剪枝:

    1. 删除以此结点为根的子树
    2. 使其成为叶子结点
    3. 当修剪后的树对于验证集合的性能不比修剪前的树的性能差时,则确认删除该结点,否则恢复该节点

    因为训练集合的过拟合,使得验证集合数据能够对其进行修正,反复进行上面的操作,从底向上的处理结点,删除那些能够提高验证集合的精度的结点,直到进一步修剪会降低验证集合的精度为止。

    错误率降低剪枝方法是最简单的后剪枝方法之一,不过由于使用独立的测试集,原始决策树相比,修改后的决策树可能偏向于过度修剪。这是因为一些不会再次在测试集中出现的很稀少的训练集实例所对应的分枝在剪枝过程中往往会被剪枝。尽管错误率降低剪枝方法有这个缺点,不过错误率降低剪枝方法仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学习方法的优点和缺点提供了一个很好的学习思路。由于验证集合没有参与决策树的构建,所以用错误率降低剪枝方法剪枝后的决策树对于测试样例的偏差要好很多,能够解决一定程度的过拟合问题。

    悲观错误剪枝(PEP,Pesimistic-Error Pruning)

    悲观错误剪枝方法是根据剪枝前后的错误率来判定子树的修剪。它不需要像错误率降低修剪方法那样,需要使用部分样本作为测试数据,而是完全使用训练数据来生成决策树,并进行剪枝,即决策树生成和剪枝都使用训练集

    该方法引入了统计学中连续修正的概念弥补错误率降低剪枝方法中的缺陷,在评价子树的训练错误公式中添加了一个常数,即假定每个叶子结点都自动对实例的某个部分进行错误的分类。

    把一颗具有多个叶子节点的子树的分类用一个叶子节点来替代的话,在训练集上的误判率肯定是上升的,但是在新数据上不一定。于是我们把子树的误判计算加上一个经验性的惩罚因子来做是否剪枝的考量指标。对于一个叶子节点,它覆盖了NN个样本,其中有EE个错误,那么该叶子节点的错误率为E+0.5N\frac{E + 0.5}{N}。这个0.50.5就是惩罚因子,那么一颗子树,它有LL个叶子节点,那么该子树的误判率估计为:
    Ei+0.5LNi\frac{\sum E_i +0.5 * L}{\sum N_i}

    这样的话,我们可以看到一棵子树虽然具有多个子节点,但由于加上了惩罚因子,所以子树的误判率计算未必占到便宜。剪枝后内部节点变成了叶子节点,其误判个数EE也需要加上一个惩罚因子,变成E+0.5E+0.5,那么子树是否可以被剪枝就取决于剪枝后的错误E+0.5E+0.5在的标准误差内。对于样本的误差率ee,我们可以根据经验把它估计成各种各样的分布模型,比如二项式分布、正态分布等。如果E+0.5<Ei+SE(Ei)E+0.5 < E_i + SE(E_i)则对ii进行剪枝。

    代价复杂度剪枝(CCP,Cost-Complexity Pruning)

    代价复杂度剪枝算法为子树TtT_t定义了代价和复杂度,以及一个可由用户设置的衡量代价与复杂度之间关系的参数αα。其中,代价指在剪枝过程中因子树TtT_t被叶节点替代而增加的错分样本,复杂度表示剪枝后子树TtT_t减少的叶结点数,αα则表示剪枝后树的复杂度降低程度与代价间的关系,定义为:
    α=R(t)R(Tt)Nt1\alpha = \frac{R(t) - R(T_t)}{|N_t| - 1}

    其中,Nt|N_t|是子树TtT_t中的叶节点数,R(t)=r(t)p(t)R(t) = r(t) * p(t)为结点tt的错误代价,r(t)r(t)为结点tt的错分样本率,p(t)p(t)为落入结点tt的样本占所有样本的比例,R(Tt)=R(i)R(T_t) = \sum R(i)是子树TtT_t错误代价,ii为子树TtT_t的叶节点。

    1. 对于完全决策树TT的每个非叶结点计算αα值,循环剪掉具有最小αα值的子树,直到剩下根节点,得到一系列的剪枝树{T0,T1,T2,,Tm}\{ T_0, T_`1, T_2, \cdots, T_m \},其中T0T_0为原有的完全决策树,TmT_m为根结点,Ti+1T_{i +1}为对TiT_i进行剪枝的结果
    2. 从子树序列中,根据真实的误差估计选择最佳决策树
    REP PEP CCP
    剪枝方式 自底向上 自顶向下 自底向上
    计算复杂度 O(n)O(n) O(n)O(n) O(n2)O(n^2)
    误差估计 测试集上误差估计 使用连续纠正 标准误差

    回归树

    建立回归树的过程大致可以分为两步:

    1. 将预测变量空间(X1,X2,X3,,XpX_1, X_2, X_3, \cdots, X_p)的可能取值构成的集合分割成JJ个互不重叠的区域{R1,R2,R3,,RJ}\{ R_1, R_2, R_3, \cdots, R_J\}
    2. 对落入区域RjR_j的每个观测值作同样的预测,预测值等于RjR_j上训练集的各个样本取值的算术平均数。

    比如,在第一步中得到两个区域R1R_1R2R_2R1R_1中训练集的各个样本取值的算术平均数为10,R2R_2中训练集的各个样本取值的算术平均数为20。则对给定的观测值X=xX = x,若xR1x \in R_1,给出的预测值为10,若xR2x \in R_2,则预测值为20。

    所以,类似于上述决策树分类算法的第(10)步,关键在于如何构建区域划分{R1,R2,R3,,RJ}\{ R_1, R_2, R_3, \cdots, R_J\}。事实上,区域的形状是可以为任意形状的,但出于模型简化和增强可解释性的考虑,这里将预测变量空间划分成高维矩形,我们称这些区域为称盒子。划分区域的目标是找到使模型的残差平方和RSSRSS最小的矩形区域{R1,R2,R3,,RJ}\{ R_1, R_2, R_3, \cdots, R_J\}RSSRSS的定义为:
    RSS=j=1JiRj(yiy^Rj)2RSS = \sum^J_{j=1} \sum_{i \in R_j}(y_i - \hat{y}_{R_j})^2

    其中,y^Rj\hat{y}_{R_j}是第jj个矩形区域中训练集中各个样本取值的算术平均数。但是,要想考虑将特征空间划分为JJ个矩形区域的所有可能性,在计算上是不可行的。因此一般采用一种自上而下的贪婪法:递归二又分裂。“自上而下”指的是它从树顶端开始依次分裂预测变量空间,每个分裂点都产生两个新的分支。“贪婪”意指在建立树的每一步中,最优分裂确定仅限于某一步进程,而不是针对全局去选择那些能够在未来进程中构建出更好的树的分裂点。

    在执行递归二又分裂时,先选择预测变量XjX_j和分割点ss,将预测变量空间分为两个区域{XXj<s}\{ X|X_j <s \}{XXjs}\{ X|X_j \geq s \},使RSSRSS尽可能地减小。也就是说,考虑所有预测变量X1,X2,X3,,XpX_1, X_2, X_3, \cdots, X_p和与每个预测变量对应的ss的取值,然后选择预测变量和分割点,使构造出的树具有最小的RSSRSS。更详细地,对jjss,定义一对半平面:
    R1(j,s)={XXj<s}R2(j,s)={XXjs}R_1(j, s) = \{ X|X_j <s \} \quad \text{和} \quad R_2(j, s) = \{ X|X_j \geq s \}

    寻找jjss,使得下式最小:
    xiR1(j,s)(yiy^R1)2+xiR2(j,s)(yiy^R2)2\sum_{x_i \in R_1(j, s)}(y_i - \hat{y}_{R_1})^2 + \sum_{x_i \in R_2(j, s)}(y_i - \hat{y}_{R_2})^2

    重复上述步骤,寻找继续分割数据集的最优预测变量和最优分割点,使随之产生的区域中的RSSRSS达到最小。此时被分割的不再是整个预测变量空间,而是之前确定的两个区域之一。如此一来就能得到3个区域。接着进一步分割3个区域之一以最小化RSSRSS。这一过程不断持续,直到符合某个停止准则,如我们在分类决策树中讨论到的前剪枝中的停止准则。

    区域{R1,R2,R3,,RJ}\{ R_1, R_2, R_3, \cdots, R_J\}产生后,就可以确定某一给定的测试数据所属的区域,并用这一区域训练集的各个样本取值的算术平均数作为与测试进行预测。

    f回归树实例

    回归树的剪枝

    上述方法生成的回归树会在训练集中取得良好的预测效果,却很有可能造成数据的过拟合,导致在测试集上效果不佳。原因在于这种方法产生的树可能过于复杂。一棵分裂点更少、规模更小(区域{R1,R2,R3,,RJ}\{ R_1, R_2, R_3, \cdots, R_J\}的个数更少)的树会有更小的方差和更好的可解释性(以增加微小偏差为代价)。针对上述问题,一种可能的解决办法是:仅当分裂使残差平方和RSSRSS的减小量超过某阈值时,才分裂树结点。这种策略能生成较小的树,但可能产生过于短视的问题,一些起初看来不值得的分裂却可能之后产生非常好的分裂。也就是说在下一步中,RSSRSS会大幅减小。

    因此,更好的策略是生成一棵很大的树T0T_0,然后通过后剪枝得到子树。直观上看,剪枝的目的是选出使测试集预测误差最小的子树。子树的测试误差可以通过交叉验证或验证集来估计。但由于可能的子树数量极其庞大,对每一棵子树都用交叉验证来估计误差太过复杂。因此需要从所有可能的子树中选出一小部分再进行考虑。在回归树中,我们一般使用代价复杂度剪枝(CCP,Cost-Complexity Pruning),也称最弱联系剪枝(Weakest Link Pruning)。这种方法不是考虑每一棵可能的子树,而是考虑以非负调整参数α\alpha标记的一系列子树。每一个α\alpha的取值对应一棵子树TT0T \in T_0,当α\alpha一定时,其对应的子树使下式最小:
    m=1TxiRm(yiy^Rm)2+αT\sum_{m=1}^{|T|} \sum_{x_i \in R_m}(y_i - \hat{y}_{R_m})^2 + \alpha |T|

    这里的T|T|表示树TT的结点数,RmR_m是第mm个终端结点对应的矩形(预测向量空间的一个子集),y^Rm\hat{y}_{R_m}是与RmR_m对应的预测值,也就是RmR_m中训练集的平均值。调整系数α\alpha在子树的复杂性和与训练数据的契合度之间控制权衡。当α=0\alpha = 0时,子树TT等于原树T0T_0,因为此时上式只衡量了训练误差。而当α\alpha增大时,终端结点数多的树将为它的复杂付出代价,所以使上式取到最小值的子树会变得更小。

    α\alpha从0开始逐渐增加时,树枝以一种嵌套的、可预测的模式被修剪,因此获得与α\alpha对应的所有子树序列是很容易的。可以用交又验证或验证集确定α\alpha,然后在整个数据集中找到与之对应的子树:

    回归决策树算法
    1.利用递归二叉分裂在训练集中生成一额大树,只有当终端结点包含的观测值个数低于某个最小值时才停止。
    2.对大树进行代价复杂性剪枝,得到一系列最优子树,子树是α\alpha的函数。
    3.利用KK折交叉验诞选择α\alpha。具体做法是将训练集分为KK折。对所有k=1,2,3,,Kk=1, 2, 3, \cdots, K,对训练集上所有不属于第kk折的数据重复第(1)步~第(2)步得到与α\alpha对应的子树,并求出上述子树在第kk折上的均方预测误差。
    4.每个α\alpha会有相应的KK个均方预测误差,对这KK个值求平均,选出使平均误差最小的α\alpha
    5.找出选定的α\alpha在第(2)步中对应的子树。

    决策树的基础即是上文所述的分类决策树与回归决策树,其预测准确性一般比回归和分类方法弱,但可以通过用集成学习方法组合大量决策树,显著提升树的预测效果,这些方法我将会在接下来的文章中继续阐述,欢迎关注学习讨论!

    展开全文
  • SQL数据库优化方面的经验

    万次阅读 2016-08-29 10:42:51
    1、用PreparedStatement一般来说比用Statement性能高,一sql发给服务器去执行,涉及步骤:语法检查,语义分析,编译,缓存。 2、有外键约束会影响插入和删除性能,如果程序能够保证数据完整性,在设计数据库时就...
  • SQL优化:索引优化

    万次阅读 2017-08-22 08:18:08
     SQL索引在数据库优化中占有一非常大的比例, 一好的索引的设计,可以让你的效率提高几十甚至几百倍,在这里将带你一步步揭开他的神秘面纱。  1.1 什么是索引?  SQL索引有两种,聚集索引和非聚集索引,...
  • 在变化响应中,DMOEA-DVC分别通过保持,预测和分布性引入策略来重新初始化三个决策变量组。 实验结果:在33个基准DMOPs上将DMOEA-DVC与其他六个典型的DMOEAs进行了比较。实验结果表明,DMOEA-DVC的总体性能优于或...
  • 如果你只给出一策略,使用值迭代算法更新至值函数收敛,你将得到了这策略下的最优决策,这样的计算模式只涉及到上式的前两行部分;因为只有一策略,所有的 就是确定的。 上面公式的通俗解释是,我在状态 s ...
  • 数据挖掘十大算法之决策树详解(1)

    万次阅读 多人点赞 2016-11-20 10:51:32
    在2006年12月召开的 IEEE ...本博客已经介绍过的位列十大算法之中的5。本文主要介绍机器学习中的决策树模型。决策树模型是一类算法的集合,在数据挖掘十大算法中,具体的决策树算法占有两席位置,即C4.5和CART算法
  • 决策

    千次阅读 2018-06-14 15:19:53
    理解树,就需要理解几关键词:根节点、父节点、子节点和叶子节点。 父节点和子节点是相对的,说白了子节点由父节点根据某一规则分裂而来,然后子节点作为新的父亲节点继续分裂,直至不能分裂为止。而根节点是没有...
  • 决策树案例分析

    千次阅读 2018-07-11 11:09:24
    通过一个决策树案例,着重从特征选择、剪枝等方面描述决策树的构建,讨论并研究决策树模型评估准则。最后基于 R 语言和 SPSS Modeler这两工具,分别设计与实现了决策树模型的应用实例。1.机器学习概念 机器学...
  • 优化算法】简述灰狼优化算法(GWO)原理

    万次阅读 多人点赞 2019-03-25 21:10:34
    系列优化算法简述: OP_1. 简述遗传算法(GA)原理 OP_2 简述灰狼优化算法(GWO)原理 前言: 灰狼优化算法(Grey Wolf Optimizer,GWO)由澳大利亚格里菲斯大学学者 Mirjalili 等人于2014年提出来的一种群智能...
  • 2018-12-20更新,新增内容 2019-01-14更新,对...一般情况面对的样本通常具有很多特征,对事务的判断不能只从一角度出发,决策树的思想是先从一特征入手,通过这次分类使问题规模缩小,同时分类后的子集相比...
  • 决策树学习谈到贝叶斯分类算法、EM、HMM

    万次阅读 多人点赞 2012-05-17 21:06:53
    第一篇:从决策树学习谈到贝叶斯分类算法、EM、HMM (Machine Learning & Data Mining交流群:8986884)引言 最近在面试中,除了基础 & 算法 & 项目之外,经常被问到或被要求介绍和描述下自己所知道...
  • 一般BI商业智能解决方案都包含财务、销售、客户等分析模块,本文分享的是某大型服装集团通过帆软FineBI建设的BI决策系统。该决策系统主要针对财务、资金、采购、生产、库存、物流、销售、渠道、产品、客户等主题与...
  • SQL 优化推荐书单

    千次阅读 2018-05-26 15:11:39
    它涉及到的内容,有硬件大件,即 CPU, 内存,IO;还有与之交互的软件,SQL 和 内嵌的语言 远古时期的数据库应用,只有少数科学家在上面跑批处理,瓶颈往往都是单个硬件组件,比如 CPU, 内存,IO. 大家都知道的是...
  • 决策树算法原理及案例

    万次阅读 多人点赞 2017-06-12 16:57:30
    通过一个决策树案例,着重从特征选择、剪枝等方面描述决策树的构建,讨论并研究决策树模型评估准则。最后基于 R 语言和 SPSS Modeler这两工具,分别设计与实现了决策树模型的应用实例。 1.机器学习概念
  • C5.0决策树之ID3、C4.5、C5.0算法 一、起源 最早的决策树算法起源于CLS(Concept Learning System)系统,即概念学习系统。它是最早的决策树算法,为今后的许多决策树算法提供了借鉴。[[[] 李旭. 五种决策树算法...
  • 马尔可夫决策过程

    千次阅读 2018-06-22 00:46:50
    马尔可夫决策过程是基于马尔可夫过程理论的随机动态系统的最优决策过程。...中文名马尔可夫决策过程外文名Markov Decision Processes简 称MDP属 于运筹学中数学规划的一分支领 域概率论,统计学人 物安德雷·...
  • 无人机任务决策

    千次阅读 2018-05-14 16:52:18
    存在不确定性的自主决策是一深入研究的问题空间,特别是在陆、空、海的自主系统运行领域。无人机执行任务的复杂性以及环境的不确定性,要求其系统具有更高的决策能力和自主性。现在的自主决策方法一般是基于人工...
  • Hyperopt 参数优化

    万次阅读 多人点赞 2018-08-28 20:02:03
    Hyperopt简介 Hyperopt(Hyper-parameter Optimization...另一方面,一模型会涉及到多参数,要量化评估各种可能性是一很大的工程量。因此hyperopt是一很实用的函数库,可以帮助我们快速选定模型参数,得到...
  • 某公司基于FineBI数据决策平台的试运行分析报告
  • 决策树-离散连续值如何构造决策

    千次阅读 2019-06-26 11:05:51
    决策树的详细说明:https://blog.csdn.net/suipingsp/article/details/41927247 什么是决策树: 决策树是通过一系列规则对数据进行分类的过程。...2, 一棵决策树的生成过程主要分为以下3部分: 特征选...
  • 但是大量重要的ILP和INLP问题,并不存在多项式时间的解法,因此,启发式算法可以这样定义:一基于直观或经验构造的算法,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一实例的一可行解,该...
  • 决策支持系统复习资料

    千次阅读 2016-05-29 20:06:19
    今天的决策比过去更加复杂的四原因 P3 决策是管理的根本和核心所在,但它并不等同于管理 需要计算机实现决策支持的原因:快速计算、克服认知限制、减少费用、技术支持、质量支持、竞争支持 P4 管理信息系统->模型...
  • 支持向量机通俗导论(理解SVM的层境界) 作者:July、pluskid ;致谢:白石、jerrylead 出处:结构之法算法之道blog。 前言 第一层、了解SVM 1.0、什么是支持向量机SVM 1.1.、线性分类 ...
  • 运筹优化(一)--运筹学概述

    万次阅读 多人点赞 2019-01-07 23:27:49
    优化方法的目的在于针对所研究的系统,求得一合理运用人力、物力和财力的最佳方案,发挥和提高系统的效能及效益,最终达到系统的最优目标。 运筹学的具体内容包括:规划论(包括线性规划、非线性规划、整数规划...
  • 多属性决策的理论与方法

    千次阅读 2019-11-24 23:15:25
    推荐两本书《移动云计算-——资源共享技术》 李波著...多属性决策一般包括两部分内容:1、获取决策信息,一般包括属性权重和属性值,其中属性权重的确定是多属性决策的一重要内容;2、通过一定的方式对决策信息进...
  • 出于常用且简单的考虑,选择了C4.5决策树作为第一算法。工程框架鉴于本篇是第一算法实现,应此需要把整个工程框架介绍一下。 出于最优性能考虑,本框架是为C/C++语言设计的。不过即使用其他语言,也可以按这...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 78,831
精华内容 31,532
关键字:

优化决策的三个方面是