一、什么是决策树？

1、定义

决策树是一种解决分类问题的算法，由下面几种元素组成：

• 根节点：包含样本的全集
• 内部节点：对应特征属性测试
• 叶节点：代表决策的结果

2、步骤

Step1. 特征选择

筛选出跟分类结果相关性较高的特征（通常利用【信息增益】进行筛选）

Step2. 决策树生成

从根结点出发，选择信息增益最大的特征作为节点特征，根据该特征的不同取值建立子节点；对每个子节点采用相同的方式生成新的子节点，直到信息增益很小或者没有新的特征可以选择为止。

Step3. 决策树剪枝

剪枝的主要目的是对抗“过拟合”，通过主动去掉部分分支来降低过拟合的风险。

二、理论基础

1、信息熵模型

（1）信息熵

• 随机变量 X 的信息熵度量了 X 的不确定性。

• 公式： $H(X)=−\sum_{i=1}^np_i\log p_i$

其中 n 是 X 不同取值的数目。

（2）联合熵

• 两个随机变量 X 和 Y 的联合熵公式： $H(X,Y)=-\sum_{i=1}^np(x_i,y_i)\log p(x_i,y_i)$

（3）条件熵

• 随机变量 X 在 Y 下的条件熵度量了知道 Y 以后 X 剩下的不确定性。

• 公式： $H(X|Y)=-\sum_{i=1}^np(x_i,y_i)\log p(x_i|y_i)=\sum_{j=1}^np(y_j)H(X|y_j)$

（4）信息增益

• 信息增益度量了 X 在知道 Y 以后的不确定性减少程度。

• 公式： $I(X,Y)=H(X)-H(X|Y)$

（5）信息增益比

• 信息增益比是信息增益和特征熵的比值。

• 公式： $I_R(X,Y)=\frac{I(X,Y)}{H(Y)}$

2、基尼系数

• 基尼系数代表了模型的不纯度，基尼系数越小，不纯度越低。

• 公式： $\text{Gini} = \sum_{i=1}^Kp_i(1-p_i)=1-\sum_{i=1}^Kp_I^2$

三、决策树算法

1、ID3算法

• 利用信息增益选择特征。
• 信息增益准则对可取数目较多的属性有所偏好。

2、C4.5算法

• 引入信息增益比选择特征。
• 信息增益比对可取数目较少的属性有所偏好。

3、CART算法

• 既可以用于分类，也可以用于回归问题。
• 使用基尼系数取代信息熵。

参考资料：

ID3算法和C4.5算法

CART算法