ID3,C4.5和CART三种决策树的区别

[问答题]

查看答案及解析

Dylan2333

具体介绍可参见个人博客关于决策树部分介绍Decision Tree

关于三种生成算法及其对应的剪枝算法的代码实现见个人github

欢迎拍砖

ID3

生成决策树

ID3算法生成决策树时，在每一层选取信息增益最大的特征及其所有可能的取值划分数据集，因此ID3生成不一定是二叉树

剪枝

ID3的剪枝是通过比较某一分支在被剪前后损失函数的变化进行的

C4.5

C4.5在划分数据集时采用的依据为信息增益比，这样可以避免ID3算法中倾向于选取取值可能性较多的特征的现象

CART

生成决策树

CART在生成树时，通过遍历每个特征的所有可能取值，计算出基尼系数(classification)或均方误差(regression)最大或最小的特征及其取值，根据是否等于该值划分数据集，因此CART得出的决策树是二叉树。其中回归树的本质也是分类的思想。

剪枝

CART采用一个非固定的 ‘正则化参数’，通过逐步增加(或减小)该值，得到多个剪枝后的子树，通过交叉验证选取最优子树

发表于 2019-04-23 21:08:43 回复(0)

neekity

https://blog.csdn.net/Neekity/article/details/88091758
决策树（decision tree）是一种基本的分类与回归方法，主要优点时模型具有可读性，分类速度快，学习时利用训练数据根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。决策树学习通常包括三个步骤：特征选择，决策树的生成和决策树的修剪。

决策树学习的损失函数通常是正则化的极大似然函数，决策树学习的策略是以损失函数为目标函数的最小化。确定了损失函数后，学习问题就变为在损失函数意义下选择最优决策树的问题，但这是个NP完全问题，一般采用启发式算法来近似求解这一最优化问题。

1. 信息增益(ID3算法)
特征 $A$ 对训练数据集 $D$ 信息增益 $g(D,A)$ ，定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差，即 $g(D,A)=H(D)-H(D|A)$
假设训练数据集为 $D$ ,容量为 $|D|$ 。有 $K$ 个 $C_{k}$ 类，个数为 $|C_{k}|$ 。特征 $A$ 有n个不同的取值，根据这些取值会把 $D$ 划分为n个子集，样本个数是 $|D_{i}|$ 。 $D_{i}$ 子集中属于 $C_{k}$ 类的样本个数是 $|D_{ik}|$ 。那么通过计算选择出信息增益最大的特征作为切分点。$ $H(D)=-\sum_{k=1}^{K}\frac{|C_{k}|}{|D|}log(\frac{|C_{k}|}{|D|})$ $H(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(\frac{|D_{ik}|}{|D_{i}|})$
2. 信息增益比(C4.5生成算法)

以信息增益作为划分训练数据的特征，存在偏向于选择取值较多的特征的问题，使用信息增益比可以解决这个问题。

$g_{R}(D,A)=\frac{g(D,A)}{H_{A}(D)}\qquad H_{A}(D)=-\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}log(\frac{|D_{i}|}{|D|})$

3. 基尼指数(CART分类与回归树)
分类问题中，假设有K个类，样本点属于第 $k$ 类的概率为 $p_{k}$ ,则概率分布的基尼指数为$ $Gini(p)=\sum_{k=1}^{K}p_{k}(1-p_{k})=1-\sum_{k=1}^{K}p_{k}^{2}$ $对于给定的样本集合$ D $，基尼指数为$ $Gini(D)=1-\sum_{k=1}^{K}(\frac{|C_{k}|}{|D|})^{2}$ $在特征$ A $(是否是A，所以只有两类情况)的条件下，集合$ D $的基尼指数定义为$ $Gini(D,A)=\frac{|D_{1}|}{|D|}Gini(D_{1})+\frac{|D_{2}|}{|D|}Gini(D_{2})$ $