决策树

记录总结一下决策树的相关内容，主要包括决策树的构建，决策树的评估，ID3,C4.5,CART算法及剪枝策略，缺失值处理及多变量决策树等。主要参考西瓜书，北风网课件，总结过程中绝大多内容是直接摘录，实属惭愧，并未内化为自己的知识，后续继续努力（因此如有侵犯，实属不好意思，私信立刻修改）。

一、决策树是什么？

决策树是一种监督学习方法，通过对属性的选取决策，将数据集划分成不同的部分，循环该过程，在每部分数据集上选取最优的属性进行划分，最终确定这部分数据集的类别。

决策树是一种预测模型，代表的是对象属性与对象值之间的映射关系；决策树是一种树形结构，其中每个内部节点表示一个属性的测试，每个分支表示一个测试输出，每个叶节点代表一种类别；

决策树分为两类：分类树和回归树，前者用于分类，后者用于预测连续值，常用的决策树算法有ID3，C4.5，CART等。

决策树算法的重点：决策树的构造，就是进行属性选择度量，确定各个特征属性之间的树结构。

构建决策树的关键：就是分裂属性，分裂属性是指在某个节点按照某一类特征属性的不同划分构建不同的分支，其目标就是让各个分裂子集尽可能的“纯”。（即让一个分裂子类中待分类的项尽可能的属于同一个类别）

二、决策树

1.决策树构建步骤

1. 将所有的特征看作一个一个的结点；
2. 遍历每个特征的每一种分割方式，找到最好的分割点；将数据划分为不同的子节点，计算划分之后所有子节点的“纯度”信息；
3. 对第二步产生的分割，选择出最优的特征以及最优的划分方式；得出最终的子节点；
4. 对子节点分别继续执行2-3步,直到每个最终的子节点都足够“纯”。

决策树学习基本算法

在决策树基本算法中，有三种情况会导致递归返回：1)当前结点包含的样本全部属于同一类别，无需划分；2）当前属性集为空，或是所有样本在属性上取值相同，无法划分；3）当前结点的样本集合为空，不能划分。

还有一种停止条件是当前节点中记录数小于某个阈值，同时迭代次数达到给定值时，此时使用max(p(i))作为节点的对应类别。（常用）

2.决策树量化纯度

决策树的构建是基于样本概率和纯度进行构建操作的，判断数据集是否“纯”了可以通过三个公式判断，Gini系数，熵，错误率，这三个公式值越大，表示数据越不纯。

3.决策树的评估

决策树的效果评估和一般分类算法一样，采用混淆矩阵来进行计算准确率，召回率，精确率等指标。也可以采用叶子节点的纯度值总和来评估算法的效果，值越小，效果越好。

三、ID3算法

ID3算法内部使用信息熵以及信息增益来进行构建，每次迭代选择信息增益最大的特征属性作为分割属性。

信息熵是度量样本集合纯度最常用的一种指标，信息熵的值越小，则数据集的纯度越高。

属性a对样本集D进行划分所获得的信息增益：

还有一种表示（ ）

条件熵：给定条件X的情况下，所有不同x值情况下Y的信息熵的平均值叫做条件熵。

信息增益越大，意味着使用该属性来进行划分所获得的“纯度提升”越大。

ID3算法优缺点：

优点：构建速度快，实现简单。

缺点：计算依赖于特征数目较多的特征，而属性值最多的属性并不一定最优。（信息增益准则对可能取值数目较多的属性有所偏好，故带来一定的影响）;

ID3算法不是递增算法；

ID3算法是单变量决策树，对于特征属性之间的关系不会考虑；

抗噪性差；

只适合小规模数据集，需要将数据放到内存中。

四、C4.5算法

在ID3算法的基础上，使用信息增益率来取代ID3算法中的信息增益，在树的构造过程中会进行剪枝操作进行优化；能够自动完成对连续属性的离散化处理；C4.5算法在选择中分割属性的时候选择信息增益率最大的属性。

（使用信息增益率划分，会对可能取值数目较少的属性有所偏好，故采用启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的）

 C4.5算法优缺点

优点：产生的规则易于理解；准确率较高；实现简单。

缺点：对数据集需要进行多次扫描和排序，所以效率较低；

只适合小规模数据集，需要将数据放到内存中。

五、CART算法

使用基尼系数作为特征数据纯度的量化指标，选择Gini系数增益最大的作为当前数据集的分割属性；可用于分类和回归两类问题。CART构建的是二叉树（特征可重复使用）

六、算法总结

1.  ID3, C4.5, CART分类算法总结

• ID3和C4.5算法均只适合再小规模数据集上使用
• ID3和C4.5算法都是单变量决策树
• 当属性值取值较多的时候，最好考虑C4.5算法，ID3得出的效果较差
• 决策树分类一般情况只适合小数据量的情况
• CART算法是三种算法中最常用的一种决策树构建算法
• 三种算法的区别仅仅只是对于当前树的评价标准不同而已，ID3使用信息增益，C4.5使用信息增益率，CART使用基尼系数。
• CART算法构建的一定是二叉树，ID3和C4.5构建的不一定是二叉树.

2.  分类树和回归树的区别：

分类树采用信息增益，信息增益率，基尼系数来评价树的效果，都是基于概率值进行判断的；而分类树的叶子节点的预测值一啊不能为叶子节点中概率最大的类别作为当前叶子的预测值。

在回归树中，叶子节点的预测值一般为叶子节点中所有值的均值来作为当前叶子节点的预测值。所以在回归树中一搬采用MSE作为树的评价指标即均方差。

一般情况下，只会使用CART算法构建回归树。

七、决策树优化

过拟合解决策略：剪枝：预剪枝(prepruning)和后剪枝(postpruning)。

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

后剪枝则是先从训练集生成一棵完整的决策树，然后自低向上地对非叶子结点进行考察，若将该节点对应的字树替换为叶节点能带来决策树泛化性能的提升，则将该子树替换为叶节点。

（使用验证集，比较剪枝前后验证集精度的大小，从而判断决策树泛化性能是否提升）

决策树剪枝过程：

对于给定的决策树 ：

     计算所有内部非叶子结点的剪枝系数

     查找最小剪枝系数的结点，将其子节点进行删除操作，进行剪枝得到决策树 ；如果存在多个最小剪枝系数结点，选择包含数据项最多的结点进行剪枝操作。

      重复上述操作，直到产生的剪枝决策树 只有一个结点； 

      得到决策树 .

       使用验证样本集选择最优子树 .

使用验证集选择最优子树的标准，可以使用原始损失函数来考虑：

叶节点越多，决策树越复杂，损失越大；修正添加剪枝系数，修改后的损失函数为：

八 、连续与缺失值

1.连续值

对于连续属性，不能直接根据连续属性的可取值来对结点进行划分，需要把连续属性离散化，最简单的策略是采用二分法对连续属性进行处理，这也是C4.5决策树算法采用的机制。

二分法：

给定样本集D和连续属性α，假定α在D上出现了n个不同的取值，将这些值从小到大进行排序，记为{al , a2,.. . , a"}．基于划分点t可将D分为子集和 ，其中包含那些在属性α上取值不大于t的样本, 而 则包含那些在属性a上取值大于t的样本。 

对于连续属性a，我们可考察包含n-1个元素的候选划分结点集合为：

然后就可像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分。

2.缺失值处理

需要解决两个问题：

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

2）给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

给定数据即D和属性a，令 示在属性a上没有缺失值的样本子集。

对问题1），我们可根据 来判断属性a的优劣。 

对问题2），若样本x在划分属性a上的取值已知，则将x划入与其取值对应的子节点，且样本权值在子节点中保持为 ，若样本x在划分属性a上的取值未知，则将x同时划入所有子节点，且样本权值在与属性值 对应的子节点中调整为 ；

西瓜书案例：

九 、多变量决策树

若我们把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界，决策树所形成的分类边界有一个明显的特点：轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。

总结

以上就是在理论层面对决策树的总结，还存在很多欠缺，也并未设计代码方面，后续继续丰富。

最后

以上就是单身猫咪为你收集整理的机器学习记录总结——决策树决策树一、决策树是什么？二、决策树总结的全部内容，希望文章能够帮你解决机器学习记录总结——决策树决策树一、决策树是什么？二、决策树总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。