决策树是一颗依托决策而建立起来的树。

ID3

首先，针对当前的集合，计算每个特征的信息增益；

然后，选择信息增益最大的特征作为当前节点的决策特征；

根据特征不同的类别划分到不同的子节点（比如年龄特征有青年，中年，老年，则划分到3颗子树），然后继续对子节点进行递归，直到所有特征都被划分。

C4.5

它是ID3的一个改进算法，使用信息增益比来进行属性的选择。

优缺点：准确率高，但是子构造树的过程中需要进行多次的扫描和排序，所以它的运算效率较低。

CART

分类回归树(Classification And Regression Tree，CART)是一个决策二叉树，在通过递归的方式建立，每个节点在分裂的时候都是希望通过最好的方式将剩余的样本划分成两类，分类指标：

  1. 分类树：基尼指数最小化。

基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。其中，Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。

  1. 回归树：平方误差最小化

优缺点

优点：计算量简单，可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征；

缺点：单颗决策树分类能力弱，并且对连续值变量难以处理；容易过拟合（后续出现了随机森林，减小了过拟合现象）。

停止条件

  1. 直到每个叶子节点都只有一种类型的记录时停止（这种方式很容易过拟合）

  2. 另一种时当叶子节点的记录树小于一定的阈值或者节点的信息增益小于一定的阈值时停止

决策树的分类与回归

1） 分类树：输出叶子节点中所属类别最多的那一类

2）回归树：输出叶子节点中各个样本值的平均值

ID3、C4.5和CART的应用

  1. ID3只适用于处理离散变量，而C4.5和CART可以处理连续型变量；

  2. ID3和C4.5只适用于分类任务，而CART可以应用于回归类任务；

  3. ID3对缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理；

  4. CART只有2个分支，是一颗二叉树；

  5. ID3和C4.5通过剪枝来衡量模型的准确率与泛化能力，而CART直接利用全部数据发现所有可能的树结构进行对比。

如何对决策树进行剪枝？

  1. 剪枝前置剪枝：在分裂节点的时候设计比较苛刻的条件，如不满足则直接停止分裂（这样干决策树无法到最优，也无法得到比较好的效果）

  2. 后置剪枝：在树建立完之后，用单个节点代替子树，节点的分类采用子树中主要的分类（这种方法比较浪费前面的建立过程）

信息增益，信息增益比和基尼系数的公式


应用：在决策树算法中，ID3使用信息增益、C4.5使用信息增益比、CART算法使用基尼系数。