决策树模型

概述

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

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

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

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

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

5. 熵

   $$H(X)=-\sum_{i=1}^np_ilogp_i$$

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

   $$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_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分类树的生成

决策树的剪枝

1. 简单决策树的剪枝

   损失函数

   $$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)=\frac{C(T)-C(T_t)}{|T_t|-1}\\ \alpha = min(\alpha, g(t))$$