决策树模型

决策树的目标是从一组样本数据中，根据不同的特征和属性，建立一棵树形的分类结构。
决策树的学习本质上是从训练集中归纳出一组分类规则，得到与数据集矛盾较小的决策树，同时具有很好的泛化能力。决策树学习的损失函数通常是正则化的极大似然函数，通常采用启发式方法，近似求解这一最优化问题。

算法原理

ID3-最大信息增益

对于样本集合D，类别数为K，数据集D的经验熵表示为:
$$
H(D)=-\sum_{k=1}^K\frac{|C_k |}{|D|} \log_2{\frac{|C_k |}{|D|}}
$$
其中$C_k$是样本集合$D$中属于第$k$类的样本子集，$|C_k|$表示该子集的元素个数，$|D|$表示元素集合的元素个数。
某个特征$A$对于数据集$D$的经验条件熵$H(D|A)$为
$$
H(D|A)=\sum_{i=1}^N\frac{|D_i|}{|D|}H(D_i)
$$
其中$D_i$表示$D$中特征$A$取第$i$个值的样本子集。
信息增益$g(D,A)$为：
$$
g(D,A)=H(D)-H(D|A)
$$

C4.5-最大信息增益比

信息增益比为：
$$
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|}}
$$

CART-最小基尼指数（Gini）

Gini描述的是数据的纯度，与信息熵含义类似
$$
Gini(D)=1-\sum_{k=1}^N{(\frac{|C_k|}{|D|})}^2
$$
CART树在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类。与ID3、C4.5不同的是，CART时一颗二叉树，采用二元切割法，每一步将数据按特征A的取值切成两份，分别进入左右子树。特征A的Gini指数定义为：
$$
Gini(D|A)=1-\sum_{i=1}^N\frac{|D_i|}{|D|}Gini(D_i )
$$

联系与比较

ID3倾向于取值较多的特征，因为信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益越大。
从样本类型的角度，ID3只能处理离散型变量，而C4.5和CART都可以处理连续型变量。从应用的角度，ID3和C4.5只能用于分类任务，而CART也可以用于回归任务（使用最小平方误差准则）。

剪枝方法

预剪枝：通过提前停止构建而对树“剪枝”，一旦停止，节点就成为树叶。（停止生长的方法：定义高度、达到某个节点实例具有相同的特征向量、定义阈值）。
预剪枝方法相对简单，效率高，而且不需要生成整个决策树，适合解决大规模问题。但是何时停止不好确定，阈值不好确定，高阈值可能导致过分简化的树，而低阈值可能使得树的简化太少。
后剪枝：它首先构造完整的决策树，允许过树过度拟合训练数据，然后对那些置信度不够的节点子树用叶子节点来代替。
相比于预剪枝，后剪枝方法通常可以得到泛化能力更强的决策树，但时间开销会更大。

分类树与回归树

分类树
以C4.5分类树为例，C4.5分类树在每次分枝时，是穷举每一个feature的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的熵最大的阈值(熵最大的概念可理解成尽可能每个分枝的男女比例都远离1:1)，按照该标准分枝得到两个新节点，用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。
总结：分类树使用信息增益或增益比率来划分节点；每个节点样本的类别情况投票决定测试样本的类别。
回归树
回归树总体流程也是类似，区别在于，回归树的每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差即(每个人的年龄-预测年龄)^2 的总和 / N。也就是被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最可靠的分枝依据。分枝直到每个叶子节点上人的年龄都唯一或者达到预设的终止条件(如叶子个数上限)，若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。
总结：回归树使用最大均方差划分节点；每个节点样本的均值作为测试样本的回归预测值。

决策树损失函数

决策树的损失函数通常是正则化的极大似然函数。
为了避免出现过拟合的现象，我们要对决策树进行剪枝。
决策树损失函数为：
$$
C_α (T)=\sum_{t=1}N_t H_t (T)+α|T|
$$
右边第一项表示误差大小，第二项表示模型的复杂度，也就是用叶节点表示，防止过拟化。其中$|T|$代表叶节点个数，$N_t$表示具体某个叶节点的样例数，$H_t (T)$表示叶节点经验熵。
其中，叶节点经验熵为
$$
H_t (T)=-\sum_{k=1}^K\frac{N_{tk}}{N_t}\log⁡{\frac{N_{tk}}{N_t}}
$$
其中，$N_t$表示该叶节点有$N_t$个样本，其中$k$类的样本有$N_{tk}$个。
正则化的损失函数中前一项代表经验误差，而在概率模型中(决策树模型是一种概率模型)，经验误差函数的获得往往通过将极大似然函数取反，即将求极大化为求极小而获得。因此，在概率模型中，极大似然函数与经验误差函数可以认为是相同的概念，那么必然就可以通过经验误差函数来推导出极大似然函数，以此来加深对决策树损失函数的理解。
$$
\begin{aligned}
\sum_{t=1}N_t H_t (T)=&
-\sum_{t=1}\sum_{k=1}^K\frac{N_{tk}}{N_t}\log⁡{\frac{N_{tk}}{N_t}}*N_t \\
=&-\sum_{t=1}\sum_{k=1}^K{N_{tk}}\log⁡{\frac{N_{tk}}{N_t}} \\
=&-\log\prod_{t=1}^{|T|}\prod_{k=1}^{K}{(\frac{N_{tk}}{N_t})}^{N_{tk}} \\
\end{aligned}
$$
至此，损失函数被化简如上，可以看到它与我们所要求的极大似然函数仅一步之遥：将求极小转为求极大，即去掉上式的负号，我们得到对数极大似然函数：
$$
L(T) = \log\prod_{t=1}^{|T|}\prod_{k=1}^{K}{(\frac{N_{tk}}{N_t})}^{N_{tk}}
$$
其对应的极大似然函数是
$$
L(T) = \prod_{t=1}^{|T|}\prod_{k=1}^{K}{(\frac{N_{tk}}{N_t})}^{N_{tk}}
$$
至此，决策树模型的极大似然函数推导完毕。
其意义个人理解为：先对各叶节点之间进行极大似然估计，再对各叶节点内部进行极大似然估计，由此得到决策树模型中的极大似然函数。