Brandon Zhang
March 22, 2021
Decision Tree
原理
决策树模型与学习
决策树的内部节点表示一个特征或属性，叶节点表示一个类。
- if-then规则：互斥且完备
- 本质： 从训练数据集中归纳出一组分类规则（估计出条件概率模型）
- 损失函数：正则化的极大似然函数
- 学习算法：启发式方法，得到(sub-optimal)的决策树
一、特征选择
准则：信息增益
熵： 设$X$是一个取有限个值的离散随机变量，定义为： $$H(X) = -\sum_{i=1}^n p_i\log p_i$$
条件熵： 随机变量$X$给定的条件下随机变量$Y$的条件熵$H(Y|X)$，定义为： $$H(Y|X) = \sum_{i=1}^np_iH(Y|X=x_i)$$ 当熵和条件熵中的概率由极大似然估计得到时，分别成为经验熵和经验条件熵
信息增益：表示得知特征$X$的信息使得类$Y$的信息不确定性减少的程度。这种差值也称为互信息 $$g(D,A)=H(D)-H(D|A)$$
特征选择方法：对训练数据集D，计算每一个特征的信息增益，选取信息增益最大的特征。
- 信息增益比 上述的特征选择存在偏向选择取值较多的特征的问题，使用information gain ratio可以解决这个问题。 定义为： $$g_R(D, A) = \frac{g(D,A)}{H_A(D)}$$ 其中，$H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{D}\log_2\frac{|D_i|}{D} $，n是特征A的取值个数。
二、决策树的生成
- ID3算法 C4.5算法的基础般，只用信息增益来选取特征。
- C4.5算法
三、决策树的剪枝
决策树的生成很容易出现过拟合现象，所以需要利用剪枝(pruning)来简化决策树。 决策树的剪枝往往通过极小化决策树整体的损失函数(loss function)来实现： $$C_{\alpha}(T)=\sum_{i=1}^{|T|}N_tH_t(T) + \alpha|T|=C(T)+\alpha|T|$$ 其中$|T|$表示树T的叶结点个数，t是树T的叶结点，该叶结点上有$N_t$个样本点，$\alpha \geq 0$为参数。
通过式子可以看出$C(T)$代表了模型对训练数据的预测误差，即拟合程度；而$\alpha|T|$代表了模型的复杂度，可以理解为正则化的方式来增强模型的泛化能力。
而树的剪枝算法分为：
- 预剪枝：不足是基于贪心策略，带来欠拟合的风险
- 后剪枝
后剪枝与动态规划类似，生成一棵完整的决策树以后，自底向上地对非叶节点进行考察，若剪完后损失函数变小，则进行剪枝。
四、CART决策树
回归树的生成
分类树的生成
- 基尼系数：假设有$K$个类，样本点属于第$k$类的概率为$p_k$，则
$$Gini(p)=\sum_{k=1}^Kp_k(1-p_k)$$
若样本集合$D$根据特征$A$是否取值$\alpha$被分割为$D_1$和$D_2$两部分，则在特征$A$下，集合$D$的基尼指数为：
$$Gini(D, A)=\frac{|D_1|}{D}Gini(D_1)+\frac{|D_2|}{D}Gini(D_2)$$
- 基尼系数：假设有$K$个类，样本点属于第$k$类的概率为$p_k$，则
$$Gini(p)=\sum_{k=1}^Kp_k(1-p_k)$$
若样本集合$D$根据特征$A$是否取值$\alpha$被分割为$D_1$和$D_2$两部分，则在特征$A$下，集合$D$的基尼指数为：
$$Gini(D, A)=\frac{|D_1|}{D}Gini(D_1)+\frac{|D_2|}{D}Gini(D_2)$$
剪枝 后剪枝法，从生成的决策树$T_0$开始不断剪枝，一直到根节点，形成一个子树序列${T_0, T_1, \dots, T_n}$，然后通过交叉验证法在独立的验证数据集上对子树序列进行测试。