决策树的本质是由多个判断节点组成的树形函数，以一个样本的特征向量X=(X1,X2,X3...Xd) 作为输入，返回一个“决策”，例如判断具有该特征的样本属于哪个类别。

简单地说，从一个树根节点开始，每次生出几个分叉节点（成为子节点），再将子节点当成新的根节点，继续往下生出新的子节点，如此重复，直到满足某些停止条件停止决策树的生长。

决策树属于有监督学习，由根节点、决策节点、叶子节点构成，可按目标类型不同分为分类树和回归树。

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之”策略。

构造树的基本想法是随着树深度的增加，节点的熵迅速降低。熵降低的速度越快越好，这样就有望得到一棵高度最矮的决策树，

一、决策树是什么

决策树（decision tree）：决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试，每个叶节点代表一种类别。

决策树是基于树状结构来进行决策的，一般的，一棵决策树包含一个根节点、若干个内部节点和若干个叶节点。

·每个内部节点表示一个属性上的判断

·每个分支代表一个判断结果的输出

·每个叶节点代表一种分类结果

·根节点包含样本全集

决策树算法，属于有监督学习，分为分类树和回归树。

—分类树：预测样本的分类，最终输出的目标变量是离散的。（比如是或否）

—回归树：预测样本特征的具体数值，最终输出的目标变量是连续的，比如预测概率值。

决策树的效果使用评价函数：

H（t）表示当前节点的熵值或基尼系数值，希望它越小越好，类似损失函数了。

预剪枝：在构建决策树的过程时，提前停止

后剪枝：决策树构建好后，然后才开始裁剪

（二）决策树的生成

决策树的生成主要解决三个问题：

①决策节点的特征选择

②节点分裂的切分点或阈值

③什么时候停止生长分裂

①②关系到决策树的生长，需要设定一个合适的划分依据；③即剪枝（预剪枝和后剪枝）

确定风险决策的目的：如何识别违约概率高的客户，并拒绝。

(一）ID3决策树

因为决策树模型的构建和评估都与信息熵密切相关。而信息熵(information entropy)是用来度量样本纯度的指标。

特征选择的概念：特征选择也即选择最优划分属性，从当前数据的特征中选择一个特征作为当前节点的划分标准。随着划分过程不断进行，希望决策树的分支节点所包含的样本可能属于同一类别，即节点的“纯度”越来越高。

熵（entropy）的概念：一条信息的信息量大小与它的不确定性有直接关系，而熵就是用来度量这件事不确定性的大小。一般来说信息量大，就是指这个时候背后的不确定因素太多。

1、假定样本集合D中第i类样本所占的比例为p_i (i=1,2,3...|n|)，需要先求信息熵

信息熵公式： 

   （ 信息熵的值越小，样本D纯度越高）

其中

就是分类 出现的概率，n是分类的数目。可以看出，熵的大小只和变量的概率分布有关。

对于在X的条件下Y的条件熵，是指在X的信息之后，Y这个变量的信息量（不确定性）的大小，计算公式如下：

例如，当只有A类和B类的时候，

熵的大小为：

当只有A类或只有B类时

所以当Etropy最大为1的时候，是分类效果最差的状态，当它最小为0的时候，是完全分类的状态。因为熵等于零是理想状态，一般情况下，熵介于0-1之间。

熵的不断最小化，实际上就是提高分类正确率的过程。

2、求离散特征a对数据集D的条件信息熵，

条件信息熵公式：

3、计算信息增益(Information Gain)

信息增益的概念：在划分数据集之前之后信息发生的变化，计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

定义属性A对数据集D的信息增益为infoGain（D|A），它等于D本身的熵，减去给定A条件下D的条件熵。

信息增益公式：

其中

信息增益的意义：引入属性A之后，原来数据集D的不确定性减少了很多。

计算每个属性引入后的信息增益，选择给D带来的信息增益最大的属性，即为最优划分属性。一般，信息增益越大，则意味着使用属性A来进行划分所得到的纯度提升越大。

4、递归构建决策树步骤

·从根节点开始，计算所有可能的特征的信息增益（注意：是针对特征计算数值，而且每一种取值都要计算到），选择信息增益最大的特征作为节点的划分特征；

·由该特征的不同取值建立子节点；

·再对子节点递归，构建决策树，直到没有特征可以选择或类别完全相同为止。

总结：

ID3算法适用离散型数据，主要根据信息增益来选择进行划分的特征，然后递归地构建决策树。

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。

(二）C4.5决策树

ID3存在的缺点：如果某个特征的分类很多，也就是分叉超多，那么该特征下的样本就很少，此时的信息增益就非常高，ID3就会认为这个属性适合用作划分。

取值较多的特征用作划分依据时，它的泛化能力弱，没法对新样本有效预测，所以C4.5不依靠信息增益划分样本，而是依靠信息增益率。

改进点：

·用信息增益率进行划分特征，克服了用信息增益选择的不足，但信息增益率对可取值数目较少的属性有所偏好；

·能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理；

·能够处理具有缺失属性值的训练数据；

·在构造树的过程中进行剪枝。

特征a的固有值：当特征a的可取值数量越大，也就是v越大，那么IV（a）的值就越大。

缺点：没有剪枝，可能会产生过度匹配问题，需要进行剪枝；采用信息增益作为选择最优划分特征的标准，然而信息增益会偏向哪些取值较多的特征。

C4.5的计算步骤：

1、 根据ID3的信息熵和条件信息熵 求信息增益

信息增益公式：

2、计算特征a的固有值IV(a)

固有值计算公式：

3、根据信息增益和固有值求信息增益率

信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，C4.5算法采用信息增益率来选择最优划分属性。

信息增益率计算公式：

信息增益率准则对可取值数目较少的属性有所偏好，所以C4.5算法不是直接选择信息增益率最大的候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益率最高的。

4、对连续特征的处理

当属性类型为离散型，无须对数据进行离散化处理；当属性类型为连续型，则需要对数据进行离散化处理，具体思路如下：

m个样本的连续特征A有m个值，从小到大排列a1，a2，，，am，取相邻两样本值的平均数做划分点，一共有m-1个，其中第i个划分点

分别计算以这m-1个点作为二元切分点时的信息增益率。选择信息增益率最大的点为该连续特征的最佳切分点。比如渠道的信息增益率最大的点at，则小于at的值为类别1，大于at的值为类别2，这样就做到了连续特征的离散化。

5、对缺失值的处理

ID3算法不能处理缺失值，而C4.5算法可以处理缺失值，主要有三种情况，具体如下：

·在有缺失值的特征上如何计算信息增益率？根据确实比例，折算信息增益（无缺失值样本所占的比例乘以无缺失值样本自己的信息增益）和信息增益率。

·选定划分属性，若样本在该属性上的值是缺失的，那么如何对这个样本进行划分？将样本以不同概率同时划分到不同节点中，概率是根据其他非缺失属性的比例来得到的。

·对新的样本进行分类时，如果测试样本特性有缺失值如何判断其类别？走所有分支，计算每个类别的概率，取概率最大的类别赋值给该样本。

6、剪枝

为什么要剪枝？因为过拟合的树在泛化能力的表现非常差。剪枝又分为前剪枝和后剪枝，前剪枝是指在构造树的过程中就知道哪些节点可以剪掉。后剪枝是指构造出完整的决策树之后再来考察哪些子树可以剪掉。

（1）前剪枝：在节点划分前确定是否继续增长，及早停止增长的主要方法有：

·节点内数据样本数小于切分最小样本数阈值

·所有节点特征都已分裂

·节点划分前准确率比划分后准确率最高

（2）后剪枝：在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。

总结：

优点：产生的分类规则易于理解，准确率较高。

缺点：只能用于分类；属于多叉树，用二叉树效率会提高；在构造树的过程中，需要对数据集进行多次的顺序扫描和排序（尤其是对连续特征），因而导致算法的低效；在选择分裂属性时没有考虑到条件属性间的相关性，只计算数据集中每一个条件属性与决策属性之间的期望信息，有可能影响到属性选择的正确性；只适合于能够驻留于内存的数据集，当训练大得无法在内存容纳时程序无法运行。

（三）GART决策树

分类树与回归树的区别在样本的输出，如果样本输出是离散值，这是分类树；样本输出是连续值，这是回归树。分类树的输出是样本的类别，回归树的输出是一个实数。

分类模型：采用基尼系数的大小度量特征各个划分点的优劣。

回归模型：采用误差平方和度量。

C4.5生成算法基于较为复杂的熵来度量，使用的是多叉树（由该节点特征的取值种类而定），但只能处理分类不能处理回归。

ID3中基于信息增益选择特征，选择增益大的特征作为当前树的根节点。C4.5采用信息增益率选择特征，减少因特征值多导致信息增益大的问题。

GART决策树既可以处理分类，也可以处理回归，分类效果一般要优于其他决策树。

GART分类树：使用基尼系数来代替信息增益率，基尼系数代表了模型的不纯度，基尼系数越小，纯度越高，无序性越低，特征越好。

GART算法步骤：特征选择、递归建立决策树、决策树剪枝

1、计算基尼指数

基尼系数最小为0，最大为1。GART假设决策树为二叉树，内部结点特征取是和否。这样的决策树等价于递归二分每一个特征，将输入空间划分为有限单元，并在这些单元上预测概率分布。

2、对于属性a计算条件基尼指数

（在属性集合A中，一般选基尼指数最小的属性，即

3、GART决策树构造的算法

（1）对每个属性a的每个可能取值v，将数据集D划分为a=v和a≠v两部分来计算基尼指数：

（2）选择基尼系数最小的属性及其对应取值作为最优划分属性和最优划分点（注意：基尼系数是针对“特征+取值”计算的，这跟信息增益不同

（3）重复(1)(2)

4、树剪枝

当决策树划分得太细时，会对数据产生过拟合，因此要通过剪枝来解决，降低决策树得复杂度来避免过拟合。剪枝分为预剪枝和后剪枝，预剪枝是指在构造树的过程中就知道哪些节点可以剪掉。后剪枝是指构造出完整的决策树之后再来考察哪些子树可以剪掉。使用后剪枝需要将数据氛围测试集和训练集。首先指定参数，使得构建出的树足够复杂，便于剪枝；然后从上而下找到叶节点，用测试机来判断这些叶节点合并是否能够降低测试误差，如果是的话就合并

总结：

数据集中会包含一些复杂的相互关系，使输入数据和目标变量之间存在非线性的关系。对于这种复杂关系的建模，一种可行的方式是使用树来对预测值分段，包括分段常数（回归树）和分段直线（模型树）

CART算法可以用于构建二元树并处理离散型或连续型数据的切分。若使用不同的误差准则，就可以通过CART算法构建模型树和回归树。

    以上就是本篇文章【第三篇：系统入门决策树】的全部内容了，欢迎阅览 ！ 文章地址：http://nhjcxspj.xhstdz.com/news/2138.html 
     资讯      企业新闻      行情      企业黄页      同类资讯      首页      网站地图      返回首页 物流园资讯移动站 http://yishengsujiao.xhstdz.com/ , 查看更多