决策树模型时一种描述对实例进行分类的树形结构。决策树可以分成ID3、C4.5和CART。

1、基于信息增益（用于ID3和ID4.5）

只能用于离散的特征集，用做分类。
$P(x = x_i)=p_i, i=1,2,...,n$
熵 $H(X) = -\sum_{i=1}^np_i\log{p_i}$ （注：熵越大，随机变量的不确定性越大）
条件熵 $H(Y|x) = -\sum_{i=1}^np_iH(Y|x = x_i)$
信息熵增益 $g(D,A) = H(D) - H(D|A)$ （特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差)
信息增益比: $g_R(D,A) = \frac{g(D,A)}{H_A(D)}$ （特征A的信息增益g(D,A)与训练数据集D关于特征A的值的熵 $H_A(D)$ 之比）

基于信息增益算法的算法

当前数据的熵，D表示数据总数， $C_k$ 表示数据集的k分类：
$H(D) = - \sum_{k=1}^K\frac{|C_k|}{D}\log\frac{|C_k|}{|D|}$
对于特征A的条件熵是：
$H(D|A) = -\sum_{i=1}^{N}\frac{|D_i|}{|D|}H(D_i) = -\sum_{i=1}^{N}\frac{|D_i|}{|D|}\sum_{k=1}^K\frac{|D_{ik}|}{D}\log\frac{|D_i|}{|D|}$ （其中 $D_{i}$ 表示特征A中的特征取值i， $D_{ik}$ 表示特征取值i下的分类情况）
于是特征A的信息增益比是： $g(D,A) = H(D) - H(D|A)$

（1）ID3算法

选择信息增益最大的特征作为结点的特征。

（2）ID4.5算法

选择信息增益比最大特征作为结点的特征。

决策树剪枝

剪枝类型：预剪枝、后剪枝

预剪枝：在构造决策树的同时进行剪枝。所有决策树的构建方法，都是在无法进一步降低熵的情况下才会停止创建分支的过程，为了避免过拟合，可以设定一个阈值，熵减小的数量小于这个阈值，即使还可以继续降低熵，也停止继续创建分支。但是这种方法实际中的效果并不好。
后剪枝：是在决策树生长完成之后，对树进行剪枝，得到简化版的决策树。剪枝的过程是对拥有同样父节点的一组节点进行检查，判断如果将其合并，熵的增加量是否小于某一阈值。如果确实小，则这一组节点可以合并一个节点，其中包含了所有可能的结果。后剪枝是目前最普遍的做法。
后剪枝的剪枝过程是删除一些子树，然后用其叶子节点代替，这个叶子节点所标识的类别通过大多数原则(majority class criterion)确定。所谓大多数原则，是指剪枝过程中, 将一些子树删除而用叶节点代替,这个叶节点所标识的类别用这棵子树中大多数训练样本所属的类别来标识,所标识的类称为majority class ，（majority class 在很多英文文献中也多次出现）。

2、CART算法

用于回归和分类。创建的是二叉决策树。

1、回归树的生成

X与Y分别为输入和输出变量，并且Y为连续变量，给定数据集 $D=\{(x_i, y_1), (x_2, y_2), ..., (x_n,y_n)\}$
(1).选择最优切分j与切分点S（j为特征，s为特征的且分点，即二叉树的分类点）使得：
$\min_\limits{j,s}[\min_\limits{c_1}\sum_{x_i\in R_1(j,s)}(y_i -c_1)^2+\min_\limits{c_2}\sum_{x_i\in R_2(j,s)}(y_i -c_2)^2]$
其中c1表示集合 $x_i\in R_1(j,s)$ 的平均值，c2表示集合 $x_i\in R_2(j,s)$ 的平均值，即：
$R_1(j,s) = \{x| x^j \leq s\}, R_2(j,s) = \{x| x^j \geq s\}$
$\hat{c_i} = \frac{1}{N_m}\sum_{x_i \in R_m(j,s)}y_i, x\in R_m, m=1,2$
(2).这样就找到了一个最优切分点，然后调用步骤(1)
(3).最后生成决策树: $f(x) = \sum_{m=1}^{M}\hat{c_m}I(x\in R_m)$

2、分类树的生成

基尼系数： $Gini(p) = \sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{k=1}^Kp_{k}^2$
二分类的基尼系数： $Gini(p) = 2p(1-p)$
样本集合D： $Gini(D)=1-\sum_{k=1}^K(\frac{|C_k|}{D})^2$
特征A条件下，集合D的基尼系数： $Gini(D, A) = \frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$
基尼指数越大，不确定性越大，选择基尼系数最小的特征点。
算法的过程和回归树的生成相似，也是遍历特征和特征值的可能的二分点。

决策树笔记整理