决策树模型

概述

决策树：分类决策树是一种描述描述对实例进行分类的树形结构

  1. 决策时的学习旨在构建一个与训练数据拟合很好，并且复杂度小的决策树。因为从可能的决策树选择最优决策树是NP完全问题，现实中采用启发式算法。

  2. 决策树的学习包括：特征选择，树的生成，树的剪枝。常用的算法有ID3, C4.5,CART。

  3. 特征选择的准则是信息增益或信息增益比或基尼指数

  4. 决策树的生成通常选用信息增益最大，信息增益比最大或基尼系数最小的作为特征选择的准则，从根节点开始递归的产生决策树。

  5. 熵

    H(X)=−∑i=1npilogpiH(X)=-\sum_{i=1}^np_ilogp_i

    条件熵，可以理解为在不同特征取值下的熵的加权和

    H(Y∣X)=∑i=1npiH(Y∣X=xi)pi=P(X=xi)H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)\\ p_i=P(X=x_i)

    信息增益

    g(D,A)=H(D)−H(D∣A)g(D,A)=H(D)-H(D|A)

    信息增益比

    gR(D,A)=g(D,A)HA(D)HA(D)=−∑i=1n∣Di∣∣D∣log∣Di∣∣D∣g_R(D,A)=\frac{g(D,A)}{H_A(D)}\\ H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}log\frac{|D_i|}{|D|}

决策树的生成

算法停止计算的条通常是节点中的样本点个数小于设定阈值，或样本集合的基尼不纯度(信息增益)小于设定阈值，亦或是没有更多特征

1.CART分类树的生成

image-20221009155718575

决策树的剪枝

  1. 简单决策树的剪枝

    损失函数

    Cα(T)=∑t=1∣T∣NtHt(T)+α∣T∣=C(T)+α∣T∣Ht(T)是经验熵C_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T| = C(T) +\alpha|T| \\ H_t(T)是经验熵

  2. CART剪枝

    对所有的内部节点t计算：

    g(t)=C(T)−C(Tt)∣Tt∣−1α=min(α,g(t))g(t)=\frac{C(T)-C(T_t)}{|T_t|-1}\\ \alpha = min(\alpha, g(t))

    image-20221009155534265