精华内容
下载资源
问答
  • 决策树知识点总结

    千次阅读 2018-09-20 21:25:24
    本章介绍关于决策树知识,理论部分来自周老师的西瓜书,代码部分来自《机器学习实战》,有位作者对代码实现已经做了很好的介绍,有兴趣的朋友可以看一下,感谢作者。...

    本章介绍关于决策树的知识,理论部分来自周老师的西瓜书,代码部分来自《机器学习实战》,有位作者对代码实现已经做了很好的介绍,有兴趣的朋友可以看一下,感谢作者。(https://www.cnblogs.com/dennis-liucd/p/7905793.html)。

    一、基本流程

    顾名思义,决策树是基于树结构来进行决策的,这也是人类在面临决策问题时一种很自然的处理机制。决策过程中提出的每一个问题都是对某个属性的“测试”,每个测试或是导出最终结论(分类结果),或是导出进一步需要判定的问题,其考虑范围是在上次决策结果的限定范围内进行的。

    一般地,一棵决策树包含一个根结点、若干内部结点和若干叶结点;叶结点对应决策结果(样本最终的分类),其他每个结点则对应一个属性测试;每个结点包含的样本集合依据所选属性的取值被划分到相应的叶结点中去;根结点包含全部的样本。从根结点到每个叶结点的路径对应了一个判定测试序列。决策树的学习算法是一个递归算法:

    在决策树算法中,有三中情况会导致递归返回:(1)当前结点包含的样本全属于一个类别,无需划分;(2)当前属性集为空,或者所有样本在所选属性上的取值都相同,无法划分(解决思路:把当前结点标记为叶结点,将其类别设定为所含样本类别最多的类别);(3)当前结点包含的样本集合为空(解决思路:把当前结点标记为叶结点,将其类别设置为其父结点中所含样本数目最多的类别)。

    二、划分选择

    由上面的决策树算法知,决策树学习的关键是第8行,即如何选取最优的划分属性。一般而言,随着划分过程不断进行,我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的“纯度”越来越高。

    2.1信息增益

    “信息熵”是度量样本集合纯度最常用的一种指标。假定当前集合D中第k类样本所占的比例为{p_{k}}^{}(k=1,2,...,|y|)(k =1,2,...,n),则D的信息熵定义为:

                                                                                     Ent(D)=-\sum_{k=1}^{n}p_{k} log_{2}p_{k}

    Ent(D)的值越小,则D的纯度越高。

    假定离散属性aV个可能的取值{{ a^{1},a^{2},...,a^{V}}},若使用a来对集合进行划分,则会产生V个分支结点,其中第v个分支结点包含了集合D中所有属性a上取值为a^{v}的样本,记为D^{v }。我们有上面的公式可以计算出该集合的信息熵,再考虑到不同的分支结点所包含的样本数目不同,给每个分支结点赋予权重|D^{v }|/|D|,即样本数越大,对分支结点的影响也就越大,于是可以计算出用属性a对样本集D进行划分所获得的“信息增益”:

                                                                      Gain(D,a)=Ent(D)-\sum_{v=1}^{V}|D^{v}/D|Ent(D^{v})

    一般而言,信息增益越大,则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此,我们在进行划分时,依次计算每个属性的信息增益,选取增益最大的特征作为最优划分属性。(著名的ID3算法就是如此)

    2.2增益率

    当决策树产生的分支结点太多时,就出现了过拟合问题,这样的决策树不具有泛化能力。实际上,信息增益准则对可取值数目较多的属性有所偏好,为了减少这种偏好可能带来的不利影响,著名的C4.5决策树算法不直接使用信息增益,而是使用“增益率”来选择最优划分属性。信息增益率定义为:

                                                              

    其中,属性a的可能取值的数目越多,IV(a)的取值就越大。

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

    2.3基尼指数

    CART决策树(分类回归树,可用于分类和回归)使用“基尼指数”来选择划分属性。同样是基于决策树的生成是希望分支结点的纯度越高越好这样一个原则,我们还可以通过基尼系数这一指标来衡量样本集合的纯度,基尼系数定义为:

                                                                               

    从概率论来看,Gini(D)反应了从数据集D中抽取两个样本,其类别不一致的概率。因此基尼系数越大,则表示样本集合的纯度越低。属性a的基尼指数定义为:

                                                         。

    于是,我们在属性候选集合A中选择那个使得划分后基尼指数最小的属性作为最优划分属性。

    三、剪枝处理

    现在来考虑一个问题:决策树是不是形态越丰富,分支越多,越复杂,分类越准确呢?显然是否定的。学习算法中存在着一个需要特别注意的问题:“过拟合”。换句话说就是学习过程中过度的学习了训练集的特点,把训练集自身的一些特点当作所有样本数据都具有的一般性质,也就是学的太过了,有一些不应该继续分支的结点继续进行划分了,导致分支过多过冗余。这样子反而会降低学习算法的泛化能力。剪枝对于决策树的泛化性能的提升是显著的,有实验研究表明[Mingers,1989a],在数据带有噪声时,通过剪枝甚至可以将决策树的泛化性能提高25%。

    所以剪枝这一名词也因此得来,因为剪枝的目的就是剪去过多的分支!决策树剪枝的基本策略有“预剪枝”和“后剪枝”,两者的界定就是一个发生在决策树生成过程中,一个是发生在决策树生成后。

    3.1预剪枝

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

    我们可以通过留出法来对泛化性能进行评估。将样本集合分为训练集和验证集。在基于前面提到的几种属性划分选择的基础上,对比划分前后的验证集的准确率来进行泛化性能的评估。如果经过划分后,验证集的准确率提高了,则认为当前结点的划分对于泛化性能的提升是有意义的,否则不计划分。

    通过预剪枝,不仅可以降低过拟合的风险,同时因为限制了无意义的结点划分,在训练和测试的计算成本上也有所优化。由以上论述,我们可以认识到预剪枝是判断当前结点对于泛化性能的影响,并没有考虑当前结点的后续结点是否有机会能够提升泛化性能,这是一种“贪心”的本质。这个策略带来的问题就是有可能会丢失那些在后续确实能提高泛化性能的结点,因此预剪枝带来欠拟合的风险。

    3.2后剪枝

    后剪枝是发生于决策树生成完成以后,从由底至上考虑每个非叶节点,若将该结点替换为叶节点能够给决策树带来泛化性能的提升的话,则将该结点替换为叶节点。因为后剪枝是在一棵完整的决策树的基础上从底至上考虑每个非叶节点,相对于预剪枝来说欠拟合风险很小,不过训练时间开销是比较大的。

    四、连续与缺失值

    4.1连续值处理

    由于连续属性的可取值的数目不再有限,所以需要新的方法来对该属性进行划分。最简单的策略是采用二分法对连续属性进行处理,C4.5决策树就是采用这种方法。

    划分的基本思路是选取一个划分点 t,将数据集  划分成D_{t}^{-} 和D_{t}^{+}两个子集(也就是划分后的子结点),其中D_{t}^{-}包含属性a的取值不大于t的那些样本,D_{t}^{+}包含了属性 a 不小于 t 的那些样本。那么,如何选择划分点 t 呢?

    首先,将  中样本的属性a的所有取值按从小到大的顺序排列,记为{a1,a2,...,an};

    然后,选取每个子区间[a_i{} ,a_i+1{})的中点作为备选的划分点集合,即

                                                                            

    最后,基于使划分后的信息增益最大的原则,在备选集合 Ta 中选出最优的划分点 

                                                                   

     

    在这里有一点需要注意的是:

    离散属性的划分中,作为当前结点划分依据的属性,再其分支结点将不再作为划分考虑。例如在判别西瓜的好坏分类中,我们第一个结点通过色泽分出了亮和暗,得出了亮和暗两个分支结点。那么接下来这两个分支结点将不再考虑西瓜的色泽属性了,因为在第一个结点已经明确划分出了哪些瓜是“亮”属性,哪些瓜是“暗“属性,离散属性的划分重点是判别”是什么“,所以不存在多次重复判别。

    而连续属性不同,连续属性例如通过二分法来离散化,划分重点不是”是什么“,而是”区间内属性值的大小关系“,这是可以多次划分多次比较的。例如在区间0到1,第一个结点是以t=0.5进行划分,得出两个分支结点v1,v2。 在v1中0到0.5,我们可以再次选定一个划分点t=0.25,再次划分出分支结点。

    这是连续属性与离散数学在划分时的一个区别。

    4.2缺失值处理

    在前面的讨论中,我们都是假定样本属性的值都不是缺失的,但现实情况下还是存在一些样本是缺失的。例如由于测试成本,隐私保护等等。

    如果缺失属性样本较多的话,并且不做任何处理,简单的放弃不完整样本的话,显然对数据信息是极其浪费的。样本不能放弃,但是属性缺失我们不得不放弃,因为本身就缺失,我们不可能凭空随便插入一个值,所以我们只能在划分过程中进行处理,减小划分误差。总的来说需要我们考虑的问题有两个:

    (1)如何在属性值缺失的情况下进行划分属性选择?

    (2)给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分?

    先讨论问题(1):

    我们给定训练集D和属性a,令表示D中在属性a上没有缺失值的样本集合,显然我们只能通过来判断属性a的优劣。假定属性a有V个可取值,令表示在属性a上取值为的样本子集,表示中属于第k类(k=1,2,...,|y|)的样本子集。假定我们为每个样本x赋予一个权重Wx,初值为1。同时定义:

    ,表示对于属性a,无缺失的样本比例;

    ,表示无缺失样本中,第k类所占比例;

    ,表示无缺失样本在属性a上取值为的样本的比例;

    基于上述推论,我们可以将信息增益的计算时推广为:

                                                              

    其中Ent(\widetilde{D})=-\sum_{k=1}^{|y|} \widetilde{p_{k}}log_2{}\widetilde{p_{k}}

    对于问题(2):

    出于缺失值的样本终归还是不是理想样本,估我们还是希望这样的非理想样本对于决策树的贡献减小,因此我们有如下策略:

    若样本 x 在划分属性a上的取值已知,则将x划入与其对应的分支结点,并保持样本权重Wx不变。若样本x在划分属性a上的取值未知,则将样本x划入所有分支结点,且样本权重调整为\widetilde{r_{v}}\cdot w_{x}

     

    五、多变量决策树

    想象一下,若我们把样本的每个属性都视为坐标空间中的一个坐标轴,则由d个属性描述的样本就对应了d维空间中的一个数据点。对样本的分类就意味着在这个坐标空间中寻找不同类样本之间的分类边界。而我们前面提到的决策树在d维空间中形成的分类边界有一个特点:轴平行,如图4.11所示,这个样本集的属性只包括两个连续属性(密度,含糖率),它的分类边界由若干个与坐标轴平行的分段组成的。

                                                            

                                                            

    如图4.10以及4.11所示,在图4.10的决策树上有几个分支结点,对应图4.11则有几段关于轴平行的分类边界。这样的分类边界的确取得了很好的解释性,但是这仅仅是二维小样本容量上的应用。如果样本很复杂,是多维的大样本,那么必须通过很多很多段的划分才能取得较好的近似,例如图4.10中的决策树需要4段分类边界。通过多段的分类边界去划分,显然时间开销是很大的,因此假如我们不局限于平行与轴的分类边界,考虑使用斜的划分边界,如图4.12所示,此时就引入了“多变量决策树”。

                                                         

    “多变量决策树”与“普通决策树”相比,关键在于分支结点的属性测试的区别。“多变量决策树”的属性测试不再是单一的属性测试,而是对多个属性的线性组合进行测试。换句话说,对于分支结点的属性测试,我们不再是为每个结点寻找一个最优划分属性了,而是对每个分支结点建立一个合适的线性分类器(\sum_{i=1}^{d}w_{i}a_{i}\leqslant t),例如图4.10中的数据集,我们通过多变量决策树生成如图4.13所示的决策树,并且其分类边界如图4.14所示。

                                                      

                                                        

     

    六.常见的决策树分类方法

    (1)、CLS算法:是最原始的决策树分类算法,基本流程是,从一棵空数出发,不断的从决策表选取属性加入数的生长过程中,直到决策树可以满足分类要求为止。CLS算法存在的主要问题是在新增属性选取时有很大的随机性。

    (2)、ID3算法:对CLS算法的最大改进是摒弃了属性选择的随机性,利用信息熵的下降速度作为属性选择的度量。ID3是一种基于信息熵的决策树分类学习算法,以信息增益和信息熵,作为对象分类的衡量标准。ID3算法结构简单、学习能力强、分类速度快适合大规模数据分类。但同时由于信息增益的不稳定性,容易倾向于众数属性导致过度拟合,算法抗干扰能力差。

    ID3算法的核心思想:根据样本子集属性取值的信息增益值的大小来选择决策属性(即决策树的非叶子结点),并根据该属性的不同取值生成决策树的分支,再对子集进行递归调用该方法,当所有子集的数据都只包含于同一个类别时结束。最后,根据生成的决策树模型,对新的、未知类别的数据对象进行分类。

    ID3算法优点:方法简单、计算量小、理论清晰、学习能力较强、比较适用于处理规模较大的学习问题。

    ID3算法缺点:倾向于选择那些属性取值比较多的属性,在实际的应用中往往取值比较多的属性对分类没有太大价值、不能对连续属性进行处理、对噪声数据比较敏感、需计算每一个属性的信息增益值、计算代价较高。

    (3)、C4.5算法:基于ID3算法的改进,主要包括:使用信息增益率替换了信息增益下降度作为属性选择的标准;在决策树构造的同时进行剪枝操作;避免了树的过度拟合情况;可以对不完整属性和连续型数据进行处理;使用k交叉验证降低了计算复杂度;针对数据构成形式,提升了算法的普适性。

    (4)、SLIQ算法:该算法具有高可扩展性和高可伸缩性特质,适合对大型数据集进行处理。

    (5)、CART(Classification and RegressionTrees, CART)算法:是一种二分递归分割技术,把当前样本划分为两个子样本,使得生成的每个非叶子节点都有两个分支,因此,CART算法生成的决策树是结构简洁的二叉树。

    分类回归树算法(Classification and Regression Trees,简称CART算法)是一种基于二分递归分割技术的算法。该算法是将当前的样本集,分为两个样本子集,这样做就使得每一个非叶子节点最多只有两个分支。因此,使用CART算法所建立的决策树是一棵二叉树,树的结构简单,与其它决策树算法相比,由该算法生成的决策树模型分类规则较少。

    CART分类算法的基本思想是:对训练样本集进行递归划分自变量空间,并依次建立决策树模型,然后采用验证数据的方法进行树枝修剪,从而得到一颗符合要求的决策树分类模型。

    CART分类算法和C4.5算法一样既可以处理离散型数据,也可以处理连续型数据。CART分类算法是根据基尼(gini)系数来选择测试属性,gini系数的值越小,划分效果越好。设样本集合为T,则T的gini系数值可由下式计算:

                                                                          

    其中,pj是指类别j在样本集T中出现的概率。若我们将T划分为T1、T2两个子集,则此次划分的gini系数的值可由下式计算:

                                                   

    其中,s为样本集T中总样本的个数,s1为属于子集T1的样本个数,s2为属于子集T2的样本个数。

    CART算法优点:除了具有一般决策树的高准确性、高效性、模式简单等特点外,还具有一些自身的特点。如,CART算法对目标变量和预测变量在概率分布上没有要求,这样就避免了因目标变量与预测变量概率分布的不同造成的结果;CART算法能够处理空缺值,这样就避免了因空缺值造成的偏差;CART算法能够处理孤立的叶子结点,这样可以避免因为数据集中与其它数据集具有不同的属性的数据对进一步分支产生影响;CART算法使用的是二元分支,能够充分地运用数据集中的全部数据,进而发现全部树的结构;比其它模型更容易理解,从模型中得到的规则能获得非常直观的解释。

    CART算法缺点:CART算法是一种大容量样本集挖掘算法,当样本集比较小时不够稳定;要求被选择的属性只能产生两个子结点,当类别过多时,错误可能增加得比较快。

    展开全文
  • 个人对于机器学习中决策树的理解和总结
    一、决策树阐述、特性、优缺点:
    1.阐述、特性:
    决策树是一种基本的分类和回归算法,主要包含三个部分:特征选择、决策树的生成和剪枝。
    首先,决策树的构成是由和边,结点包括内部结点和外部结点,内部结点表示特征,外部结点表示类别。
    其次,决策树学习本质是从训练数据中归纳出一组分类规则,使它与训练数据矛盾较小的同时具有较强的泛化能力。另一个数学角度:由训练数据集估计条件概率,是一种判别式模型。
    损失函数是正则化的极大似然函数。学习的策略是损失函数最小化。(NP难问题,通常采用启发式算法,SMO就是一个启发式算法,包括特、生、剪三个步骤)
    最后,决策树算法思想是递归的选择最有特征,根据最优特征对数据进行分割,这一过程对应着决策树的构建和特征空间的划分。
    决策树有可能产生过拟合,所以需要剪枝,减去过于细分的结点。
    2、优缺点
    优点:构造简单、判别速度快; 对数据不需要任何加工; 对于unbalance 的数据效果好。
    缺点:泛化能力差,容易过拟合; 对新增的样本,需要调整整棵树的结构。

    二、特征选择:
    特征选择的准则是:信息增益或信息增益比,选择使信息增益最大的特征分割。
    1、信息增益:
    熵:数据的不一致性,(随机变量的不确定性)。
    条件熵:在特征集合给定的条件下,数据集合非一致性。
    信息增益:熵 — 条件熵 表示:在得知特征的条件下,使得数据分类的不确定性减少的程度。所以,信息增益越大表示特征的划分能力越强。
    2、信息增益比:
    因为用信息增益作为划分数据集的特征,可能会偏向于:选择取值较多的特征,用信息增益比可以矫正。
    信息增益比:信息增益 / 关于当前特征取值的熵。
    三、决策树的生成:
    1) ID3:
    选择信息增益最大的特征。
    核心:在决策树的各个节点上利用信息增益准则选择特征,递归的构建决策树。
    具体方法:从根节点开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为当前结点的特征,由该特征的不同取值建立子节点(划分数据),再对子节点递归的调用以上方法,构建决策树。直到所有特征的信息增益都很小或没有特征可以选择为止。
    相当于用极大似然估计进行概率模型的选择。
    缺点:只有树的生成,容易过拟合;
    偏向于选择 取值较多的特征。
    2)C4.5:
    用信息增益比来选择特征。
    对ID3的一个改进。
    3)CART(classification and regression tree )算法:
    用基尼指数选择特征。
    优点:不用提前确定权衡银子a,而是在剪枝的同时找到最优的a值。
    步骤:1、 决策树生成:基于训练数据集生成决策树,决策树要越大越好。(就是递归的生成二叉决策树的过程, 回归用平方误差最小 的准则,对 分类用基尼指数最小 的准则。)
    2、 决策树剪枝:用验证数据集对已生成的决策树进行剪枝,并生成最优子树。用最小损失函 数作为剪枝的标准。
    1、cart 决策树生成:
    (1)最小二乘回归树生成算法:(在训练数据集所在的输入空间中,递归的对每个区域划分为两个子区域,并决定每个子区域的输出值,构建决策二叉树)
    输入:训练数据集D; 输出:回归树;
    1)根据平方误差最小化准则寻找当前数据集的最优切分变量和切分点;
    2)用选定的切分变量和切分点对数据进行划分,并决定每个划分区域相应的输出值c_m;
    3)继续对两个划分的区域进行上面的步骤,直到满足条件;
    4)将输入空间划分为M的区域,生成决策树:f(x)=求和(c_m * I)
    (2)分类树的生成:
    输入:训练数据集D,终止条件; 输出:分类决策树;
    1)对给定的训练数据集,计算现有特征对数据集的基尼指数,对每个特征属性值都将数据划分两部分;2)在所有可能的特征和划分点中,选择基尼指数最小的作为最优特征和最优切分点。
    将数据切分为两个子节点。3)对两个子节点递归的调用上面方法,直到满足停止条件;4)生成。
    2、cart剪枝:
    (从生成算法产生的决策树底端开始不断剪枝,直到根节点。生成了一个子树序列;利用交叉验证法在独立的验证数据集上岁子树进行测试,找出最优子树(损失函数最小的))
    四、决策树的剪枝:
    提出:决策树的生成算法递归的产生决策树,直到不能继续下去为止,这样的算法往往对训练数据的分类很准确,但是对未知的测试数据分类却没有那么准确,容易产生过拟合。
    目的:解决过拟合,方法:考虑决策树的复杂度,对已经生成决策树进行简化。(过拟合的原因:建立决策树的过程中,过多的考虑如何选择特征,能对训练数据分类的更加准确,从而构建出过于复杂的决策树。)
    实现原理:通过极小化决策树整体的损失函数或代价函数。(决策树生成只考虑了通过提高信息增益对训练数据进行更好的拟合,而决策树剪枝通过优化损失函数还考虑了减少模型复杂度。
    决策树生成学习局部的模型,而决策树剪枝学习整体的模型。
    代价函数 : Ca(T)=C(T)+a|T| =模型与训练数据的预测误差 + a*模型复杂度(较大的a促使选择较简单的模型) (C(T)一般有两种衡量方法,一种是熵,一种是基尼指数。)
    算法步骤:输入:生成算法生成的整棵树、参数a。 输出:修剪后的子树。
    1)计算每个节点的经验熵;2)递归的从树的叶节点向上回缩;
    3)计算叶节点回缩到父节点的树的损失函数,和没回缩时的树的损失函数。如果回缩后更小,则进行剪枝,将父节点作为新的叶子结点。4)重复,直到不能继续,得到损失函数最小的子树
    五、随机森林:
    通过两个随机、构建多个次优树:
    1)样本随机:随机选择样本,通过有放回的抽样,重复的选择部分样本来构建树;
    2)特征随机:构建树的过程中,每次考察部分特征,不对树进行剪枝;
    优点:训练速度快,不易过拟合;提高了泛化性能。
    缺点:新增样本数据,需要调整整棵树。
    展开全文
  • 【机器学习】决策树知识点小结

    千次阅读 2018-08-20 13:22:03
    决策树原理简述 决策树是一类常见的机器学习方法,它是基于树的结构进行决策的。每次做决策时选择最优划分属性,一般而言,随着划分过程不断进行,我们希望决策树的分支节点所包含的样本尽可能属于同一个类别,即...

    决策树原理简述

    决策树是一类常见的机器学习方法,它是基于树的结构进行决策的。每次做决策时选择最优划分属性,一般而言,随着划分过程不断进行,我们希望决策树的分支节点所包含的样本尽可能属于同一个类别,即节点的“纯度”(purity)越来越高。

    决策树学习算法包含特征选择、决策树的生成与剪枝过程。决策树的学习算法通常是递归地选择最优特征,并用最优特征对数据集进行分割。开始时,构建根节点,选择最优特征,该特征有几种值就分割为几个子集,每个子集分别递归调用此方法,返回节点,返回的节点就是上一层的子节点。直到达到终止条件。(预剪枝条件等)

    关于各种熵的介绍见各类熵总结

    常用的决策树算法有ID3,C4.5和CART。(还有一个C5.0不过是商用版本,在C4.5的基础上做了很多改进。)

    • ID3:以信息增益为准则来选择划分属性。
    • C4.5:使用信息增益率来进行属性的选择。
    • CART:使用基尼系数来选择划分属性。

    各类决策树的具体的算法流程见ID3,C4.5,CART决策树

    信息增益率的优缺点

    优点:ID3使用信息增益去对决策树进行划分,经常偏向于分支较多的特征分裂,因为具有较多属性值的特征,分裂后其信息增益通常较大。此时就会有较大的概率出现每个分支节点只包含一个样本这种情况,此时分支节点的纯度达到最大,但显然这种决策树是不具备泛化能力的,无法对新样本进行有效的预测。总结一下:信息增益对可取属性数目较多的特征有所偏好,而信息增益率减少了这种偏好可能带来的不利影响。

    缺点:信息增益率偏向取值较少的特征,当特征取值较少时信息增益率求解公式分母较小,因而信息增益率比较大。所以它偏向取值较少的特征。

    综合其优缺点:我们在使用信息增益率时,通常也并不是直接使用。而是先在候选特征中找出信息增益高于平均水平的特征,然后在这些特征中再选择信息增益率最高的特征。

    决策树的剪枝策略

    树的剪枝策略分为两种,一种为在树生成过程中的预剪枝策略,另一种为树在生成之后的后剪枝策略。具体参见之前写的文章树的剪枝策略

    树的剪枝主要是为了防止树的过拟合,提高树模型的泛化能力。(剪枝之后的分类误差不能相差太大。)

    C4.5对ID3做了哪些改进

    ID3算法是采用信息增益作为评价标准进行分支的决策树算法。

    ID3的缺点

    1. 对于具有很多值的属性它是非常敏感的,例如,如果我们数据集中的某个属性值对不同的样本基本上是不相同的,甚至更极端点,对于每个样本都是唯一的,如果我们用这个属性来划分数据集,它会得到很大的信息增益,但是,这样的结果并不是我们想要的。
    2. ID3算法不能处理具有连续值的属性。
    3. ID3算法不能处理属性具有缺失值的样本。
    4. 由于按照上面的算法会生成很深的树,所以容易产生过拟合现象。

    C4.5算法主要对ID3作出了以下方面的改进:

    1. 用信息增益率来选择属性,克服了用信息增益来选择属性时偏向选择值多的属性的不足。
    2. 可以处理连续数值型属性。
    3. 使用了PEP的后剪枝策略。
    4. 缺失值的处理。处理的方式通常有三种:
      1. 赋上该属性最常见的值或者取均值;
      2. 丢弃有缺失值的样本;
      3. 根据节点的样例上该属性值出现的情况赋一个概率,比如该节点上有10个样本,其中属性A的取值有6个为“高”,4个为“低”。那么对该节点上缺失的属性A,以0.6的概率设为“高”,0.4的概率设为“低”。

    C4.5的缺点:

    1. 算法低效,在构造树的过程中,需要对数据集进行多次的顺序扫描和排序(主要在于对连续特征的处理上),因而导致算法的低效。
    2. 内存受限,适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。

    无论是ID3还是C4.5最好在小数据集上使用,决策树分类一般只适用于小数据。当属性取值很多时最好选择C4.5算法,ID3得出的效果会非常差。

     

    C4.5如何处理连续数值型特征

    C4.5既可以处理离散型特征,也可以处理连续型特征。对于连续分布的特征,其处理方法是:先把连续特征转换为离散特征再进行处理。虽然本质上特征的取值是连续的,但对于有限的采样数据它是离散的,如果有N个样本,那么我们就有N-1种离散化的方法。(离散属性的离散化通常是分两类,小于等于某一个分割点的为一类,大于某一个分割点的为一类。)具体分割点的选择是根据计算信息增益,选择有最大信息增益的分割点。另外,在分割之前,我们还需要对连续属性进行排序(升序),这样可以大大减少运算量。经证明,在决定连续特征的分界点时采用信息增益这个指标,而选择属性的时候才使用信息增益率这个指标能选择出最佳分类特征。

    具体步骤如下:

    1. 对特征的取值进行升序排序
    2. 两个特征取值之间的中点作为可能的分裂点,将数据集分成两部分,计算每个可能的分裂点的信息增益。优化算法就是只计算分类属性发生改变(对于升序排序的特征取值而言,对每一个分裂点都进行计算未免太过耗时,实践证明,取那些夹在相同分类属性之间的分裂点必不会时全局最小。)的那些特征取值。
    3. 选择修正后信息增益最大的分裂点作为该特征的最佳分裂点。
    4. 计算最佳分裂点的信息增益率作为特征的信息增益率。

    分裂点的信息增益修正方法:

    将信息增益减去\log_2(N-1)/\left | D \right |得到修正后的信息增益。其中N是连续特征的取值个数,D是训练数据数目。此修正的原因在于:当离散特征与连续特征并存时,C4.5算法倾向于选择连续特征做最佳树分裂点。

    C4.5与CART的区别

    两者都是决策树,但CART既可以做分类,又可以做回归,而C4.5只是用于分类。

    C4.5是构造决策树来发现数据中蕴含的分类规则,是一种通过划分特征空间逼近离散函数值的方法。C4.5是基于ID3的改进算法。使用信息增益率作为划分依据。分类规则是互斥并且完备的。所谓互斥即每一条样本记录不会同时匹配上两条分类规则,所谓完备即每条样本记录都在决策树中都能匹配上一条规则。

    CART本质是对特征空间进行二元划分(即CART生成的决策树是一颗二叉树),并能够对标量特征与连续特征进行分裂。在对标量特征进行划分时,分为等于某个特征属性和不等于;对连续特征进行划分时,分为大于和小于等于。并且在分类的时候是采用GINI系数作为衡量标准,而不是信息增益了;在回归时,是使用最小均方误差作为评价。

    CART对于特征的利用是可以重复的,而作为分类的C4.5则是不能重复利用特征。

    分类树和回归树联系区别

    分类树

    以C4.5分类树为例,C4.5分类树在每次分枝时,是穷举每一个feature的每一个阈值,找到使得按照feature<=阈值,和feature>阈值分成的两个分枝的集合信息熵最小的阈值,按照该标准分枝得到两个新节点,用同样方法继续分枝直到得到类别唯一的叶子节点,或达到预设的终止条件,若最终叶子节点中的性别不唯一,则以占有最多数的类别作为该叶子节点的最终分类类别。

    回归树

    回归树总体流程也是类似,区别在于,回归树的每个节点(不一定是叶子节点)都会得一个预测值,以年龄为例,该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点,但衡量最好的标准不再是信息熵(信息增益),而是最小化均方误差即(每个人的年龄-预测年龄)^2 的总和 / N。也就是被预测出错的人数越多,错的越离谱,均方差就越大,通过最小化均方差能够找到最可靠的分枝依据。分枝直到每个叶子节点上人的年龄都唯一或者达到预设的终止条件(如叶子个数上限),若最终叶子节点上人的年龄不唯一,则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

    总结

    1. 分类树使用信息增益或增益比率来划分节点;每个节点样本的类别情况投票决定测试样本的类别。
    2. 回归树使用最小均方误差划分节点;每个节点样本的均值作为测试样本的回归预测值。

    CART树对离散特征取值数目>=3对特征如何处理

    因为CART树是二叉树,所以对于样本离散特征有N>=3个取值时的处理也只能有两个分支,这就要通过人为组合创建二取值序列并取GiniGain最小者作为树分叉的决策点。如某特征值具有[‘young’,’middle’,’old’]三个取值,那么二分序列会有如下3种可能性(空集和满集在CART分类中没有意义): [((‘young’,), (‘middle’, ‘old’)), ((‘middle’,), (‘young’, ‘old’)), ((‘old’,), (‘young’, ‘middle’))]。

    采用CART算法,就需要分别计算按照上述List中的二分序列做分叉时的Gini系数,然后选取产生最小的GINIGain的二分序列做该特征的分叉二值序列参与树构建的递归。如果某特征取值有4个,那么二分序列组合就有7种,5个取值就有15种组合。

    因此CART不适用于离散特征有过多取值可能的场景。此时,若一定要使用CART,则最好预先人为的将离散特征的取值缩减。 

    那么对于二分后的左右分支,如果特征取值tuple中元素多于2个,该特征一般还是需要继续参与到子数据集的分割中去。这在一定程度上有助于提升模型的精度(一定意义上改进了C4.5完全的贪心算法,使得模型有一定的全局(局部)特征考量的性质)。

    决策树对缺失值的处理方法

    缺失值问题可以从四个方面来考虑

    1.在进入模型开始训练之前,我们可以对缺失值做上一定的处理。

    1. 为缺失值赋上该属性最常见的值或者取均值;
    2. 丢弃有缺失值的样本;
    3. 根据节点的样例上该属性值出现的情况赋一个概率,比如该节点上有10个样本,其中属性A的取值有6个为“高”,4个为“低”。那么对该节点上缺失的属性A,以0.6的概率设为“高”,0.4的概率设为“低”。

    2. 在选择分裂属性的时候,训练样本存在缺失值,如何处理?(计算分裂损失减少值时,忽略特征缺失的样本,最终计算的值乘以比例(实际参与计算的样本数除以总的样本数))

    假如你使用ID3算法,那么选择分类特征时,就要计算所有特征的熵减(信息增益,Gain)。假设10个样本,特征是a,b,c。在计算a特征熵时发现,第10个样本的a特征缺失,那么就把第10个样本去掉,前9个样本组成新的样本集,在新样本集上按正常方法计算a特征的熵减。然后结果乘0.9(未缺失样本的比例),就是a特征分裂最终的熵。

    3. 分类特征选择完成,对训练样本分类,发现样本特征缺失怎么办?(将该样本分配到所有子节点中,权重由1变为具有特征a的样本被划分成的子集样本个数的相对比率,计算错误率的时候,需要考虑到样本权重)

    1. 单独为属性缺失的样本划分一个分支子集。
    2. 比如该节点是根据a特征划分,但是待分类样本a特征缺失,怎么办呢?假设a特征离散,有1,2两种取值,那么就把该样本分配到两个子节点中去,但是权重由1变为相应离散值个数占样本的比例。然后计算错误率的时候,注意,不是每个样本都是权重为1,存在分数。

    4. 训练完成,给测试集样本分类,有缺失值怎么办?(分类时,如果待分类样本有缺失变量,而决策树决策过程中没有用到这些变量,则决策过程和没有缺失的数据一样;否则,如果决策要用到缺失变量,决策树也可以在当前节点做多数投票来决定(选择样本数最多的特征值方向)。)

    1. 如果有单独的缺失分支,使用此分支。
    2. 把待分类的样本的特征a值分配一个最常出现的a的属性值,然后进行分支预测。
    3. 根据其他特征为该待分类样本填充一个特征a值,然后进行分支处理。
    4. 在决策树中特征a节点的分支上,遍历特征a节点的所有分支,探索可能所有的分类结果,然后把这些分类结果结合起来一起考虑,按照概率决定一个分类。
    5. 待分类样本在到达特征a节点时就终止分类,然后根据此时a节点所覆盖的叶子节点类别状况为其分配一个发生概率最高的类。

    如果决策树属性用完了仍未对决策树完成划分应该怎么办

    当训练集很大以及特征数量并不是很多的情况下,这种状况很容易发生。此时的解决方法一般有两种:

    1. 一种即退出模型,做特征组合、交叉等操作扩充特征。当有了足够多的特征后,便可以有效改善这种情况。但在一般情况下,树模型如果特征过多,相当容易过拟合。
    2. 另一种方法便是直接对叶子节点采用“多数表决”,即使用节点中出现最多的类别作为该节点的标签。

    决策树需要进行归一化处理吗?

    在之前的文章中有讲过类似的问题,这里再重复一遍。决策树是概率模型,为什么是概率模型呢,不要以为那些有贝叶斯公式、类条件概率、后验概率的模型才是概率模型。决策树其实是一种简单高效并且具有强解释性的概率模型,是给定特征条件下类的条件概率分布的一种退化表示(并不求解概率密度函数但依据训练样本可以得到类频率代替概率)。

    概率模型是不需要归一化的,因为它们不关心变量的值,而是关心变量的分布和变量之间的条件概率。数值缩放不会影响决策树的分裂点位置。

    二叉决策树与多叉决策树相比各有什么特点

    二叉决策树不像多叉树那样会形成过多的数据碎片,而二叉决策树可能会得到更深的最终决策树。

    决策树构建过程中较为耗时的步骤

    确定最佳分割点,在该步骤中需要对特征值进行排序,计算信息增益等,非常耗时。

    决策树算法主要应用于非线性模型,若已知数据集是满足线性假设的,那么我们可以直接用一个线性模型取得比较好的预测结果

    决策树特征的重复选择

    决策树中一个特征被选择过后依然是有可能被选择为分裂特征的。

    • 若特征为离散特征,如果决策树为二叉树,则可以在分类的子区间继续划分,如果决策树为多叉树,通常进行一次划分。
    • 若特征为连续特征,则可能在决策树中多次被选择。

    决策树模型的优缺点

    优点

    1. 易于理解,决策树易于理解和实现。人们在通过解释后都有能力去理解决策树所表达的意义。
    2. 数据处理简单,对缺失值不敏感。对于决策树,数据的准备往往是简单或者不必要的。其他的算法模型往往要求先把数据一般化,比如去掉多余的或者空白的属性。
    3. 能够同时处理数据型变量和类别变量。其他的技术往往要求特征是单一类型的。
    4. 是一个白盒模型,如果给定一个观察的模型,那么根据所产生的决策树很容易推出相应的逻辑表达式。
    5. 易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。
    6. 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
    7. 如果有不相关的 feature,没什么干扰,如果数据中有不相关的 feature,顶多这个 feature 不出现在树的节点里。逻辑回归和 SVM 没有这样的天然特性(但是有相应的补救措施,比如逻辑回归里的 L1 正则化)。

    缺点

    1. 很容易在训练数据中生成复杂的树结构,造成过拟合。剪枝可以缓解过拟合。
    2. 不适合处理高维数据,当属性数量过大的时候,部分决策树就不太适用了。
    3. 对异常值(Outlier)过于敏感,很容易导致树的结构巨大的变换。
    4. 模型的更新比较复杂,每当有新的样本进来时,树的结构很有可能会发生大的改变。
    5. 采用的贪心策略无法考虑到全局的特性。

    树模型的应用场景

    模型应用场景可参考如下:

    • 如果不强调模型的解释度,尽量避免单棵决策树,用集成树模型
    • 在集成树模型中,优先推荐使用xgboost
    • 在中小数据集上,优先选择集成树模型。大数据集上推荐神经网络
    • 在需要模型解释度的项目上,优先使用树模型
    • 在项目时间较短的项目上,如果数据质量低(大量缺失值、噪音等),优先使用集成树模型
    • 在硬件条件有限及机器学习知识有限的前提下,优先选择树模型

     

    https://www.cnblogs.com/end/p/3328379.html

     

     

    展开全文
  • 决策树的完整知识点总结

    万次阅读 多人点赞 2016-11-26 16:29:32
    决策树的目的是构造一种模型,使之能够从样本数据的特征属性中,通过学习简单的决策规则——IF THEN规则,从而预测目标变量的值。 图1 决策树 例如,在某医院内,对因心脏病发作而入院治疗的患者,在住院的...

    一、原理

     

    决策树是一种非参数的监督学习方法,它主要用于分类和回归。决策树的目的是构造一种模型,使之能够从样本数据的特征属性中,通过学习简单的决策规则——IF THEN规则,从而预测目标变量的值。


    图1 决策树

    例如,在某医院内,对因心脏病发作而入院治疗的患者,在住院的前24小时内,观测记录下来他们的19个特征属性——血压、年龄、以及其他17项可以综合判断病人状况的重要指标,用图1所示的决策树判断病人是否属于高危患者。在图1中,圆形为中间节点,也就是树的分支,它代表IF THEN规则的条件;方形为终端节点(叶节点),也就是树的叶,它代表IF THEN规则的结果。我们也把第一个节点称为根节点。

    决策树往往采用的是自上而下的设计方法,每迭代循环一次,就会选择一个特征属性进行分叉,直到不能再分叉为止。因此在构建决策树的过程中,选择最佳(既能够快速分类,又能使决策树的深度小)的分叉特征属性是关键所在。这种“最佳性”可以用非纯度(impurity)进行衡量。如果一个数据集合中只有一种分类结果,则该集合最纯,即一致性好;反之有许多分类,则不纯,即一致性不好。有许多指标可以定量的度量这种非纯度,最常用的有熵,基尼指数(Gini Index)和分类误差,它们的公式分别为:

    (1)

    (2)

    (3)

    上述所有公式中,值越大,表示越不纯,这三个度量之间并不存在显著的差别。式中D表示样本数据的分类集合,并且该集合共有J种分类,pj表示第j种分类的样本率:

    (4)

    式中NNj分别表示集合D中样本数据的总数和第j个分类的样本数量。把式4带入式2中,得到:

    (5)

    目前常用的决策树的算法包括ID3(Iterative Dichotomiser 3,第3代迭戈二叉树)、C4.5和CART(ClassificationAnd Regression Tree,分类和回归树)。前两种算法主要应用的是基于熵的方法,而第三种应用的是基尼指数的方法。下面我们就逐一介绍这些方法。

    ID3是由Ross Quinlan首先提出,它是基于所谓“Occam'srazor”(奥卡姆剃刀),即越简单越好,也就是越是小型的决策树越优于大型的决策树。如前所述,我们已经有了熵作为衡量样本集合纯度的标准,熵越大,越不纯,因此我们希望在分类以后能够降低熵的大小,使之变纯一些。这种分类后熵变小的判定标准可以用信息增益(Information Gain)来衡量,它的定义为:

    (6)

    该式表示在样本集合D下特征属性A的信息增益,n表示针对特征属性A,样本集合被划分为n个不同部分,即A中包含着n个不同的值,Ni表示第i个部分的样本数量,E(Di)表示特征属性A下第i个部分的分类集合的熵。信息增益越大,分类后熵下降得越快,则分类效果越好。因此我们在D内遍历所有属性,选择信息增益最大的那个特征属性进行分类。在下次迭代循环中,我们只需对上次分类剩下的样本集合计算信息增益,如此循环,直至不能再分类为止。

    C4.5算法也是由Quinlan提出,它是ID3算法的扩展。ID3应用的是信息增益的方法,但这种方法存在一个问题,那就是它会更愿意选择那些包括很多种类的特征属性,即哪个A中的n多,那么这个A的信息增益就可能更大。为此,C4.5使用信息增益率这一准则来衡量非纯度,即:

    (7)

    式中,SI(DA)表示分裂信息值,它的定义为:

    (8)

    该式中的符号含义与式6相同。同样的,我们选择信息增益率最大的那个特征属性作为分类属性。

    CART算法是由Breiman等人首先提出,它包括分类树和回归树两种。我们先来讨论分类树,针对特征属性A,分类后的基尼指数为:

    (9)

    该式中的符号含义与式6相同。与ID3和C4.5不同,我们选择分类基尼指数最小的那个特征属性作为分类属性。当我们每次只想把样本集合分为两类时,即每个中间节点只产生两个分支,但如果特征属性A中有多于2个的值,即n> 2,这时我们就需要一个阈值β,它把D分割成了D1D2两个部分,不同的β得到不同的D1D2,我们重新设D1的样本数为LD2的样本数为R,因此有LN,则式9可简写为:

    (10)

    我们把式5带入上式中,得到:

    (11)

    式中,∑LL,∑RR。式11只是通过不同特征属性A的不同阈值β来得到样本集D的不纯度,由于D内的样本数量N是一定的,因此对式11求最小值问题就转换为求式12的最大值问题:

    (12)

    以上给出的是分类树的计算方法,下面介绍回归树。两者的不同之处是,分类树的样本输出(即响应值)是类的形式,如判断蘑菇是有毒还是无毒,周末去看电影还是不去。而回归树的样本输出是数值的形式,比如给某人发放房屋贷款的数额就是具体的数值,可以是0到120万元之间的任意值。为了得到回归树,我们就需要把适合分类的非纯度度量用适合回归的非纯度度量取代。因此我们将熵计算用均方误差替代:

    (13)

    式中N表示D集合的样本数量,yiri分别为第i个样本的输出值和预测值。如果我们把样本的预测值用样本输出值的平均来替代,则式13改写为:

    (14)

    上式表示了集合D的最小均方误差,如果针对于某种特征属性A,我们把集合D划分为s个部分,则划分后的均方误差为:

    (15)

    式中Ni表示被划分的第i个集合Di的样本数量。式15与式14的差值为划分为s个部分后的误差减小:

    (16)

    与式6所表示的信息增益相似,我们寻求的是最大化的误差减小,此时就得到了最佳的s个部分的划分。

    同样的,当我们仅考虑二叉树的情况时,即每个中间节点只有两个分支,此时s= 2,基于特征属性A的值,集合D被阈值β划分为D1D2两个集合,每个集合的样本数分别为LR,则:

    (17)

    把式14带入上式,得:

    (18)

    式中,yi是属于集合D的样本响应值,liri分别是属于集合D1D2的样本响应值。对于某个节点来说,它的样本数量以及样本响应值的和是一个定值,因此式18的结果完全取决于方括号内的部分,即:

    (19)

    因此求式18的最大值问题就转变为求式19的最大值问题。

    我们按照样本响应值是类的形式,还是数值的形式,把决策树分成了分类树和回归树,它们对应不同的计算公式。那么表示特征属性的形式也会有这两种形式,即类的形式和数值的形式,比如决定是否出去踢球,取决于两个条件:风力和气温。风力的表示形式是:无风、小风、中风、大风,气温的表示形式就是具体的摄氏度,如-10℃~40℃之间。风力这个特征属性就是类的形式,而气温就是数值的形式。又比如决定发放房屋贷款,其金额取决于两个条件:是否有车有房和年薪。有车有房的表示形式是:无车无房、有车无房、无车有房、有车有房,而年薪的表示形式就是具体的钱数,如0~20万。有车有房这个特征属性就是类的形式,年薪就是数值的形式。因此在分析样本的特征属性时,我们要把决策树分为四种情况:特征为类的分类树(如决定是否踢球的风力)、特征为数值的分类树(如决定是否踢球的温度)、特征为类的回归树(如发放贷款的有车有房)和特征为数值的回归树(如发放贷款的年薪)。由于特征形式不同,所以计算方法上有所不同:

    Ⅰ、特征为类的分类树:对于两类问题,即样本的分类(响应值)只有两种情况:响应值为0和1,按照特征属性的类别的样本响应值为1的数量的多少进行排序。例如我们采集20个样本来构建是否踢球分类树,设出去踢球的响应值为1,不踢球的响应值为0,针对风力这个特征属性,响应值为1的样本有14个,无风有6个样本,小风有5个,中风2个,大风1个,则排序的结果为:大风<中风<小风<无风。然后我们按照这个顺序依次按照二叉树的分叉方式把样本分为左分支和右分支,并带入式12求使该式为最大值的那个分叉方式,即先把是大风的样本放入左分支,其余的放入右分支,带入式12,得到A,再把大风和中风放入左分支,其余的放入右分支,带入式12,得到B,再把大风、中风和小风放入左分支,无风的放入右分支,计算得到C,比较A、B、C,如果最大值为C,则按照C的分叉方式划分左右分支,其中阈值β可以设为3。对于非两类问题,采用的是聚类的方法。

    Ⅱ、特征为数值的分类树:由于特征属性是用数值进行表示,我们就按照数值的大小顺序依次带入式12,计算最大值。如一共有14个样本,按照由小至大的顺序为:abcdefghijklmn,第一次分叉为:a|bcdefghijklmn,竖线“|”的左侧被划分到左分支,右侧被划分到右分支,带入式12计算其值,然后第二次分叉:ab|cdefghijklmn,同理带入式12计算其值,以此类推,得到这13次分叉的最大值,该种分叉方式即为最佳的分叉方式,其中阈值β为分叉的次数。

    Ⅲ、特征为类的回归树:计算每种特征属性各个种类的平均样本响应值,按照该值的大小进行排序,然后依次带入式19,计算其最大值。

    Ⅳ、特征为数值的回归树:该种情况与特征为数值的分类树相同,就按照数值的大小顺序依次带入式19,计算最大值。

    在训练决策树时,还有三个技术问题需要解决。第一个问题是,对于分类树,我们还需要考虑一种情况,当用户想要检测一些非常罕见的异常现象的时候,这是非常难办到的,这是因为训练可能包含了比异常多得多的正常情况,那么很可能分类结果就是认为每一个情况都是正常的。为了避免这种情况的出现,我们需要设置先验概率,这样异常情况发生的概率就被人为的增加(可以增加到0.5甚至更高),这样被误分类的异常情况的权重就会变大,决策树也能够得到适当的调整。先验概率需要根据各自情况人为设置,但还需要考虑各个分类的样本率,因此这个先验值还不能直接应用,还需要处理。设Qj为我们设置的第j个分类的先验概率,Nj为该分类的样本数,则考虑了样本率并进行归一化处理的先验概率qj为:

    (20)

    把先验概率带入式12中,则得到:

    (21)

    第二个需要解决的问题是,某些样本缺失了某个特征属性,但该特征属性又是最佳分叉属性,那么如何对该样本进行分叉呢?目前有几种方法可以解决该问题,一种是直接把该样本删除掉;另一种方法是用各种算法估计该样本的缺失属性值。还有一种方法就是用另一个特征属性来替代最佳分叉属性,该特征属性被称为替代分叉属性。因此在计算最佳分叉属性的同时,还要计算该特征属性的替代分叉属性,以防止最佳分叉属性缺失的情况。CART算法就是采用的该方法,下面我们就来介绍该方法。

    寻找替代分叉属性总的原则就是使其分叉的效果与最佳分叉属性相似,即分叉的误差最小。我们仍然根据特征属性是类还是数值的形式,也把替代分叉属性的计算分为两种情况。

    当特征属性是类的形式的时候,当最佳分叉属性不是该特征属性时,会把该特征属性的每个种类分叉为不同的分支,例如当最佳分叉属性不是风力时,极有可能把5个无风的样本分叉为不同的分支(如3个属于左分支,2个属于右分支),但当最佳分叉属性是风力时,这种情况就不会发生,也就是5个无风的样本要么属于左分支,要么属于右分支。因此我们把被最佳分叉属性分叉的特征属性种类的分支最大样本数量作为该种类的分叉值,计算该特征属性所有种类的这些分叉值,最终这些分叉值之和就作为该替代分叉属性的分叉值。我们还看前面的例子,无风的分叉值为3,再计算小风、中风、大风的分叉值,假如它们的值分别为4、4、3,则把风力作为替代分叉属性的分叉值为14。按照该方法再计算其他特征属性是类形式的替代分叉值,则替代性由替代分叉值按从大到小进行排序。在用替代分叉属性分叉时那些左分支大于右分支样本数的种类被分叉为左分支,反之为右分支,如上面的例子,无风的样本被分叉为左分支。

    当特征属性是数值的形式的时候,样本被分割成了四个部分:LL、LR、RL和RR,前一个字母表示被最佳分叉属性分叉为左右分支,后一个字母表示被替代分叉属性分叉为左右分支,如LR表示被最佳分叉属性分叉为左分支,但被替代分叉属性分叉为右分支的样本,因此LL和RR表示的是被替代分叉属性分叉正确的样本,而LR和RL是被替代分叉属性分叉错误的样本,在该特征属性下,选取阈值对样本进行分割,使LL+RR或LR+RL达到最大值,则最终max{LL+RR,LR+RL}作为该特征属性的替代分叉属性的分叉值。按照该方法再计算其他特征属性是数值形式的替代分叉值,则替代性也由替代分叉值按从大到小进行排序。最终我们选取替代分叉值最大的那个特征属性作为该最佳分叉属性的替代分叉属性。

    为了让替代分叉属性与最佳分叉属性相比较,我们还需要对替代分叉值进行规范化处理,如果替代分叉属性是类的形式,则替代分叉值需要乘以式12再除以最佳分叉属性中的种类数量,如果替代分叉属性是数值的形式,则替代分叉值需要乘以式19再除以所有样本的数量。规范化后的替代分叉属性如果就是最佳分叉属性时,两者的值是相等的。

    第三个问题就是过拟合。由于决策树的建立完全是依赖于训练样本,因此该决策树对该样本能够产生完全一致的拟合效果。但这样的决策树对于预测样本来说过于复杂,对预测样本的分类效果也不够精确。这种现象就称为过拟合。

    将复杂的决策树进行简化的过程称为剪枝,它的目的是去掉一些节点,包括叶节点和中间节点。剪枝常用的方法有预剪枝和后剪枝两种。预剪枝是在构建决策树的过程中,提前终止决策树的生长,从而避免过多的节点的产生。该方法虽然简单但实用性不强,因为我们很难精确的判断何时终止树的生长。后剪枝就是在决策树构建完后再去掉一些节点。常见后剪枝方法有四种:悲观错误剪枝(PEP)、最小错误剪枝(MEP)、代价复杂度剪枝(CCP)和基于错误的剪枝(EBP)。CCP算法能够应用于CART算法中,它的本质是度量每减少一个叶节点所得到的平均错误,在这里我们重点介绍CCP算法。

    CCP算法会产生一系列树的序列{T0,T1,…,Tm},其中T0是由训练得到的最初的决策树,而Tm只含有一个根节点。序列中的树是嵌套的,也就是序列中的Ti+1是由Ti通过剪枝得到的,即实现用Ti+1中一个叶节点来替代Ti中以该节点为根的子树。这种被替代的原则就是使误差的增加率α最小,即

    (22)

    式中,R(n)表示Ti中节点n的预测误差,R(nt)表示Ti中以节点n为根节点的子树的所有叶节点的预测误差之和,|nt|为该子树叶节点的数量,|nt|也被称为复杂度,因为叶节点越多,复杂性当然就越强。因此α的含义就是用一个节点n来替代以n为根节点的所有|nt|个节点的误差增加的规范化程度。在Ti中,我们选择最小的α值的节点进行替代,最终得到Ti+1。以此类推,每需要得到一棵决策树,都需要计算其前一棵决策树的α值,根据α值来对前一棵决策树进行剪枝,直到最终剪枝到只剩下含有一个根节点的Tm为止。

    根据决策树是分类树还是回归树,节点的预测误差的计算也分为两种情况。在分类树下,我们可以应用上面介绍过的式1~式3中的任意一个,如果我们应用式3来表示节点n的预测误差,则:

    (23)

    式中,Nj表示节点n下第j个分类的样本数,N为该节点的所有样本数,max{Nj}表示在m个分类中,拥有样本数最多的那个分类的样本数量。在回归树下,我们可以应用式14来表示节点n的预测误差:

    (24)

    式中,yi表示第i个样本的响应值,N为该节点的样本数量。我们把式23和式24的分子部分称为节点的风险值。

    我们用全部样本得到的决策树序列为{T0,T1,…,Tm},其所对应的α值为α0<α1<…<αm。下一步就是如何从这个序列中最优的选择一颗决策树Ti。而与其说找到最优的Ti,不如说找到其所对应的αi。这一步骤通常采用的方法是交叉验证(Cross-Validation)。

    我们把L个样本随机划分为数量相等的V个子集Lvv=1,…,V。第v个训练样本集为:

    (25)

    Lv被用来做L(v)测试样本集。对每个训练样本集L(v)按照CCP算法得到决策树的序列{T0(v),T1(v),…,Tm(v) },其对应的α值为α0(v)<α1(v)<…<αm(v)α值的计算仍然采用式22。对于分类树来说,第v个子集的节点n的预测误差为:

    (26)

    式中,Nj(v)表示训练样本集L(v)中节点n的第j个分类的样本数,N(v)L(v)中节点n的所有样本数,max{Nj(v)}表示在m个分类中,L(v)中节点n拥有样本数最多的那个分类的样本数量。对于回归树来说,第v个子集的节点n的预测误差为:

    (27)

    式中,yj(v)表示训练样本集L(v)中节点n的第i个样本的响应值。我们仍然把式26和式27的分子部分称交叉验证子集中的节点风险值。

    我们由训练样本集得到了树序列,然后应用这些树对测试样本集进行测试,测试的结果用错误率来衡量,即被错误分类的样本数量。对于分类树来说,节点n的错误率为:

    (28)

    式中,Nv表示测试样本集Lv中节点n的所有样本数,Nv,j表示Lv中第j个分类的样本数,这个j是式26中max{|Lj(v)|}所对应的j。对于回归树来说,节点n的错误率为:

    (29)

    式中,yv,i表示Lv的第i个样本响应值。决策树的总错误率E(v)等于该树所有叶节点的错误率之和。

    虽然交叉验证子集决策树序列T(v)的数量要与由全体样本得到的决策树序列T的数量相同,但两者构建的形式不同,它需要比较两者的α值后再来构建。而为了比较由全体样本训练得到α值与交叉验证子集的α(v)值之间的大小,我们还需要对α值进行处理,即

    (30)

    其中α’= 0,而α’m为无穷大。

    我们设按照式22得到的初始训练子集L(v)决策树序列为{T0(v),T1(v),…,Tm(v)},其所对应的α(v)值为{α0(v), α1(v),…,αm(v)}。最终的树序列也是由这些T(v)组成,并且也是嵌套的形式,但可以重复,而且必须满足:

    (31)

    该式的含义是T(v)中第k个子树的α(v)值要小于α’k的最大的α(v)所对应的子树,因此最终的树序列有可能是这种形式:T0(v),T0(v),T1(v),T1(v),T2(v),T2(v),T2(v),T2(v),…,直到序列中树的数量为m为止。

    子集的决策树序列构建好了,下面我们就可以计算V个子集中树序列相同的总错误率之和,即

    (32)

    则最佳的子树索引J为:

    (33)

    最终我们选择决策树序列{T0,T1,…,Tm}中第J棵树为最佳决策树,该树的总错误率最小。

    如果我们在选择决策树时使用1-SE(1 Standard Error of Minimum Error)规则的话,那么有可能最终的决策树不是错误率最小的子树,而是错误率略大,但树的结构更简单的那颗决策树。我们首先计算误差范围SE

    (34)

    式中,EJ表示最佳子树的总错误率,N为总的样本数。则最终被选中的决策树的总错误率EK要满足:

    (35)

    并且决策树的结构最简单。

    以上我们完整并详细的介绍了构建决策树,也就是训练决策树的过程,在这个过程中我们没有放过每个技术细节。而预测样本很简单,只要把样本按照最佳分叉属性(或替代分叉属性)一次一次分叉,直到到达决策树的叶节点,该叶节点的值就是该预测样本的响应值。

     

    代码实现在blog中有,我就不copy了,http://blog.csdn.net/zhaocj/article/details/50503450在里面可以看到完整的代码

    展开全文
  • 本章节内容主要介绍决策树,包括决策树简介、生成规则、信息增益、决策树分类条件选择、决策树预剪枝和后剪枝、决策树参数说明并附上部分代码、决策树优缺点。 一、决策树简介 决策树是一种树形结构,树内部每个...
  • 决策树算法学习总结

    2018-11-25 16:14:20
    在大二第一学期因为兴趣原因,自己学习了一些数据分析的算法,这里面便包含决策树,总的来说,学习的情况还是比较良好的,有那个意愿自己去学习.现在想想,那时的学习过程还是挺艰辛的,因为其实几种决策树,ID3,C4.5,CART...
  • 第四讲 决策决策方法 管理的核心是决策。正确的决策决胜千里,错误的决策南辕北辙。 一、 决策的重要性、概念及内涵 (一) 决策的重要性 决策是管理者从事管理工作的基础。在管理过程中,管理者会面临各种各样的...
  • 决策树面试知识点最全总结(二)

    千次阅读 2018-09-14 14:11:22
    决策树面试知识点最全总结(二) 决策树的生成 ID3和C4.5 1 .ID3算法: ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征,递归的构建决策树。 具体的方法是:从根节点开始,对结点计算所有可能的...
  • 决策树算法原理详解

    2018-07-03 19:23:10
    本文是自己整理的一些重点知识点,也是面试中会被问到的知识点 【文档结构】 决策树 信息熵(Entropy) 什么是决策树 决策树的构建过程 决策树分割属性选择 决策树量化纯度 决策树量化纯度 信息增益率计算...
  • 决策树面试知识点最全总结(三)

    千次阅读 2018-09-17 15:30:13
    决策树面试知识点最全总结(三)决策树的剪枝 一 为什么需要减枝: 无论是在ID3还是C4.5决策树的生成算法中,都是递归的生成决策树,直到不能继续下去为止。这样产生的决策树存在一些问题:过拟合即对训练数据的...
  • 本文讲解了经典的决策树:ID3决策树,并给出了西瓜书上的例题。最后给出了ID3的不足。
  • 决策树基本知识,以及三种决策树算法ID3,C4.5,CART之间的比较。利用python实现一个简单的决策树分类模型。
  • 文章目录1 决策树算法简介2 决策树算法2.1 引例例1例22.2 算法分类(1) 信息熵(2) 信息增益(3) 增益率(4) 基尼指数3 决策树算法优缺点4 实验参考资料 1 决策树算法简介 决策树(Decision Tree) 是在已知各种情况发生...
  • 机器学习之决策树——学习总结

    万次阅读 2017-01-22 17:16:37
    决策树学习总结 机器学习的应用越来越广泛,特别是在数据分析领域。本文是我学习决策树算法的一些总结。 机器学习简介机器学习 (Machine Learning) 是近 20 多年兴起的一门多领域交叉学科,涉及概率论、统计学、...
  • 决策树系列(一)——基础知识回顾与总结 1.决策树的定义 &nbsp; &nbsp; &nbsp; 树想必大家都会比较熟悉,是由节点和边两种元素组成的结构。理解树,就需要理解几个关键词:根节点、父节点、子...
  • 它是一种典型的分类方法,首先对数据进行处理,利用归纳算法生成可读的规则和决策树,然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树方法最早产生于上世纪60年代,到70...
  • 数据挖掘基础知识点总结

    千次阅读 2019-08-10 16:34:55
    本文总结了数据仓库和数据挖掘的基础知识
  • 决策树从原理简述到面试详细总结

    千次阅读 2019-04-23 12:01:44
    本人近期有过一些面试,因此针对性地复习了一下,这里就总结一下决策树的一些原理和面试中遇到的相关问题。 1、基础知识 1.1 熵 熵其实是物理里的一个概念,代表一个系统的混乱程度,在信息论里表示一个随机变量不...
  • 在上一篇文章中我们已经详细介绍基于ID3算法进行改良的C4.5算法以及决策树拟合度的优化问题,那这篇文章呢,则是介绍如何使用sklearn实现决策树。 当然,如果只是简单实现决策树的话,我是不可能单独拿出来写成一篇...
  • 1、决策树 首先,决策树是一个有监督的分类模型,其本质是选择一个能带来最大信息增益的特征值进行树的分割,直到到达结束条件或者叶子结点纯度到达一定阈值。按照分割指标和分割方法,决策树的经典模型可以分为ID3...
  • 机器学习知识点相关总结(二)——决策树相关 机器学习知识点相关总结(三)——LR相关 机器学习知识点相关总结(四)——SVM相关 机器学习知识点相关总结(五)——CNN相关 机器学习知识点相关总结(六)——...
  • 一、决策树概念 二、决策树启发函数 1. ID3——最大信息增益 2. C4.5——最大信息增益比 3. CART——最小基尼系数 4. 启发函数区别 三、决策树剪枝策略 1. 预剪枝 2. 后剪枝 四、常见问题 1. C4.5 如何...
  • 在机器习算学法中,如果留意的话会...基本概念:Decision Tree:决策树Random Forest:中文称随机森林GBDT:Gradient Boosting Decision Tree(梯度提升决策树)。三者关系: 提到森林,我们就会联想到是一棵棵的树构
  • CART回归 如果样本的标签和样本的特征存在非线性关系时,则普通的线性回归、岭回归和Lasso回归都不再使用。 局部加权回归也可以对非线性数据进行较好的拟合,但是它是非参数模型,每次预测都要重新训练模型参数...
  • 机器学习算法总结--决策树

    千次阅读 2017-02-13 21:49:42
    简介定义:分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型:内部结点和叶结点。内部结点表示一个特征或属性,叶结点表示一个类。决策树学习通常包括3个步骤:特征...
  • 决策树(decision tree)(一)——构造决策树方法

    万次阅读 多人点赞 2017-04-18 16:44:56
    决策树(decision tree) 说明:这篇博客是看周志华老师的《机器学习》(西瓜书)的笔记总结,博客中有大段文字摘自周老师的《机器学习》书,仅供学习交流使用。转载博客务必注明出处和作者,谢谢。 决策树算法起源...
  • 数据挖掘算法之决策树算法总结

    千次阅读 2014-09-20 09:26:32
    机器学习中,决策树是一个预测模型;它代表的是对象属性值与对象值之间的一种映射关系。树中每个节点表示某个对象,每个分叉路径则代表的某个可能的属性值,而每个叶结点则对应具有上述属性值的子对象。决策树仅有...
  • 决策树算法原理及应用(详细版)

    千次阅读 2020-09-18 12:22:00
    决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点代表一种类别。决策树是一种十分常用的分类方法,本文主要内容:C4.5算法简介算法描述属性选...
  • 关于决策树的一些可能需要了解的知识点,在个人总结决策树中有所涉猎。 谈到随机森林,就需要了解bagging,而谈到bagging,就需要了解集成学习。 集成学习:构建并租个多个学习器来完成任务。获得比单一学习器更...
  • 第6-2课:决策树、博弈树和行为树

    千次阅读 2020-09-22 12:17:12
    在以各种“XX学习”为代表的人工智能...从本质上来说,这些都还不算是真正的 AI,但也能够给游戏的体验增加很多乐趣,这一课我们就来介绍三种常见的给角色预设行为逻辑的方法,分别是决策树、博弈树和行为树。 决策...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,438
精华内容 7,775
关键字:

决策树知识点总结