0 学习目标

了解决策树模型，以及决策树学习的三个步骤：特征选择、决策树的生成和决策树的修建
CART算法的学习与应用

1 决策树模型

结构：决策树由结点(node)和有向边(directed edge)组成.结点有两种类型，内部结点(internal node)：表示一个特征或者属性；叶子结点(leaf node)：表示一个类.

用决策树分类，从根结点开始，对实例的某一特征进行判断，根据判读结果，将实例划分到其子结点；因为每个内部结点对应实例的一个特征的取值。此时，再根据子结点的特征进行判断，如此递归地对实例根据特征进行判断和划分，直至达到叶子结点。最后将实例划分到叶子结点的类中。

如此可见，决策树也可以看成是一个if-then规则的集合。还可以表示成给定特征条件下类的条件概率分布。

2 决策树学习

假设给定训练数据集：
$$
D=\{(x_1,y_1),\cdots(x_N,y_N)\}
$$
其中，$x_i=(x_i^{(1)},\cdots,x_i^{(n)})^T$为输入实例（特征向量），$n$为特征个数，$y_i \in \{1,2,\cdots\,K\}$为类标记，$i=1,2,\cdots,N$，$N$为样本容量。
特征学习的目标是根据给定的训练数据集构建一个决策树模型，使之能够对实例进行正确的分类。

能够对训练数据集进行正确分类的决策树可能有不止一个，但是选择哪个呢？选择的标准是什么呢？我们需要的是一个与训练数据矛盾较小的决策树，并且具有很好的泛化能力。
学习策略：决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。

决策树的构建： 开始，构建根结点，将所有训练数据都放在根结点，选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类，如果这些子集已经能够被基本正确分类，那么构建叶子结点，并将这些子集分到所对应的叶子结点中去；如果还有自己不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点，如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶子结点上，即都有了明确的类。这就生成了一课决策树。

特征选择

特征选择的目的是选出对分类有重大影响的特征，舍弃对分类结果影响很小的特征。特征选择的准则通常是信息增益或信息增益比。
为了更好的理解信息增益，先给出熵(entropy)和条件熵(conditional entropy)的定义：
熵：表示随机变量不确定性的度量。随机变量$X$的熵可以定义为：
$$
\begin{equation}
H(X)=- \sum_{i=1}^{n}p_ilogp_i
\end{equation}
$$
其中，$X$是一个取值为有限个值的随机变量，$p_i$为$X$取$x_i$时的概率。若$p_i=0$，则定义$0log0=0$。当对数以2为底时，熵的单位称为比特(bit);当对数以$e$为底时，熵的单位称为纳特(nat)。

由(1)式可知，熵只与$X$的分布有关，而与$X$的取值无关。熵越大，随机变量$X$的不确定性也越大。
条件熵：表示一个随机变量已知的条件下，另一个随机变量的不确定性的度量。
$$
\begin{equation}
H(Y|X)=\sum_{i=1}^{n}p_iH(Y|X=x_i)
\end{equation}
$$
其中，$p_i=P(X=x_i),i=1,2,\cdots,n.$

信息增益(information gain)：表示得知特征$X$的信息而使得类$Y$的信息不确定性减小的程度。特征$A$对训练数据集$D$的信息增益$g(D,A)$,定义为：
$$
\begin{equation}
g(D,A)=H(D)-H(D|A)
\end{equation}
$$
一般地，熵与条件熵的差也称作互信息(mutual information).
根据信息增益准则的特征选择方法是：对训练数据集$D$，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

信息增益的算法
输入：训练数据集$D$和特征$A$;
输出：特征$A$对训练数据集$D$的信息增益$g(D,A)$.
(1)计算数据集$D$的经验熵$H(D)$
$$
H(D)=- \sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}
$$
其中，$|C_k|$为属于$C_k$的样本个数，且$\sum_{k=1}^{K}|C_k|=|D|$
(2)计算特征$A$对数据集$D$的经验条件熵$H(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_i|}log_2\frac{|D_{ik}|}{|D_i|}
$$
(3)计算信息增益
$$
g(D,A)=H(D)-H(D|A)
$$

决策树的生成

决策树的经典生成算法有ID3和C4.5，下面分别介绍之。

ID3算法

ID3算法的核心思想是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。相当于用极大似然法进行概率模型的选择。
算法：
输入：训练数据集$D$，特征集$A$，阈值$\varepsilon$;
输出：决策树$T$.
(1)如果$D$中的所有实例属于同一类$C_k$，则$T$为单结点树，并将类$C_k$作为该结点的类标记，返回$T$;
(2)如果$A=\oslash$，则$T$为单结点树，并将$D$中实例数最大的类作为该结点的类标记，返回$T$;
(3)否则，按照信息增益算法计算$A$中各个特征对$D$的信息增益，选择信息增益最大的特征$A_g$;
(4)如果$A_g$的信息增益小于阈值$\varepsilon$，则置$T$为单结点树，并将$D$中的实例数最大的类作为该结点的类标记，返回$T$;
(5)否则，对$A_g$的每一个特征值$a_i$，依$A_g=a_i$将$D$分割为若干非空子集$D_i$，将$D_i$中实例数最大的类作为类标记，构建子结点，由结点及其子结点构成树$T$，返回$T$;
(6)对第$i$个子结点，以$D_i$为训练集，以$A-\{A_g\}$为特征集，递归地调用(1)-(5)，得到子树$T_i$，返回$T_i$.

ID3算法只有树的生成，所以该算法生成的树容易产生过拟合.

C4.5算法

C4.5算法与ID3算法类似，进行了改进。C4.5算法在生成树的过程中，用信息增益比来选择特征。用信息增益选择特征，倾向于选择取值较多的特征，而采用信息增益比可以较正这一问题。
信息增益比：特征$A$对训练数据集$D$的信息增益$g_R(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_2\frac{|D_i|}{|D|}$,$n$是特征$A$取值的个数。

算法：
输入：训练数据集$D$，特征集$A$，阈值$\varepsilon$;
输出：决策树$T$.
(1)如果$D$中的所有实例属于同一类$C_k$，则$T$为单结点树，并将类$C_k$作为该结点的类标记，返回$T$;
(2)如果$A=\oslash$，则$T$为单结点树，并将$D$中实例数最大的类作为该结点的类标记，返回$T$;
(3)否则，按照信息增益比公示计算$A$中各个特征对$D$的信息增益比，选择信息增益比最大的特征$A_g$;
(4)如果$A_g$的信息增益比小于阈值$\varepsilon$，则置$T$为单结点树，并将$D$中的实例数最大的类作为该结点的类标记，返回$T$;
(5)否则，对$A_g$的每一个特征值$a_i$，依$A_g=a_i$将$D$分割为若干非空子集$D_i$，将$D_i$中实例数最大的类作为类标记，构建子结点，由结点及其子结点构成树$T$，返回$T$;
(6)对第$i$个子结点，以$D_i$为训练集，以$A-\{A_g\}$为特征集，递归地调用(1)-(5)，得到子树$T_i$，返回$T_i$.

决策树的剪枝

决策树生成算法递归地生成的决策树，往往对训练集的数据分类很准确，但是对未知的测试数据分类不是很准确，这就是过拟合问题。过拟合的原因是训练过程中为了提高对训练数据分类的正确率，采用了过于复杂的模型。解决决策树模型过拟合问题的办法是，对生成的决策树进行简化，也称为剪枝。

有空再写

3 CART算法

4 决策树应用

4 参考文献

[1] 李航,《统计学习方法》,清华大学出版社,2012