机器学习基础(8)-决策树
决策树模型
决策树是一种基本的分类与回归问题，它模拟人类进行决策的过程，经过一系列的if-then过程达到最后的决策结果。决策树整体是一个树形结构，结点则分为两种类型：内部结点以及叶子结点。内部结点表示根据某个属性（特征）进行划分，决定进入哪一个子结点中；而叶子结点则是最终的输出结果，在分类问题中就是一个类别，在回归问题中就是一个数值。决策树的决策过程就是从根结点到叶子结点的一条路径，路径中的内部结点决定下一步的走向，叶子结点决定最终的输出。
决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树可能有多个，也可能一个都没有。我们希望得到的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。同其他机器学习算法类似，我们也希望用损失函数来表征决策树的效果。确定损失函数之后，决策树学习就变为了在损失函数意义下选择最优决策树的问题。
但是，在所有可能的决策树中选取最优决策树是一个NP完全问题，所以在现实中决策树学习算法通常是采用启发式学习，近似求解这一最优化问题。简单来说，我们使用贪婪的思想，在每次进行内部结点划分的时候，都采用最优的划分方式，递归地选择最优特征。这样得到的决策树是次最优的。
按照递归的方式进行决策树的构建，我们很容易得到一个完全长成的树。可以预见的是，这棵树可能比较复杂，它在训练集上有很好的分类能力，很容易达到训练误差\(E_{in}=0\)（极端情况下，完全长成的树上每个叶子结点都只有一个训练样本，相当于对每个训练样本都特殊处理）。这样的树对未知的数据通常有较差的效果，即发生了过拟合现象。因此我们需要对已生成的树自下而上地进行剪枝，降低树的复杂度，从而使它具有更好的泛化能力。
总结来说，决策树学习算法包含特征选择、决策树的生成以及决策树的剪枝。决策树的生成对应模型的局部选择，考虑局部最优；而决策树的剪枝对应于模型的全局选择，考虑全局最优。
决策树的优点是模型直观，便于理解并且应用广泛，同时它算法简单，容易实现，在训练和预测的时候有较高的效率。不过决策树也有相应的缺点，它缺少足够的理论支持，虽然能够达到好的效果，但是如何选择合适的树结构也是困难所在。
决策树学习
决策树的学习通常包括三个步骤：特征选择、决策树的生成以及决策树的修剪（剪枝）。
特征选择
特征选择是在每一个内部结点中进行的过程。考虑在目前的内部结点上，训练数据集为\(D = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}\)，其中\(x_i\)为一个多维向量\(x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(m)})\)，每个维度代表一个特征取值；\(y_i\)表示对应的类别取值，代表一个类别。内部结点需要做的事情就是选择一个特征\(A\)，根据特征\(A\)的取值可以将训练数据集划分为n个子集\(D_1,D_2,...,D_n\)，对应生成的\(n\)个子结点。选择的依据则有信息增益、信息增益比以及基尼系数。
信息增益
首先需要给出熵和条件熵的概念。在信息论中，熵（entropy）用来度量随机变量的不确定性。假设\(X\)是一个取有限个值的离散随机变量，它的概率分布如下： \[ P(X = x_i) = p_i,\quad i=1,2,...,n \] 则随机变量\(X\)的熵定义为： \[ H(X) = -\sum_{i=1}^np_i\log p_i \] 其中如果\(p_i=0\)，则定义\(0\log 0 = 0\)。其中的对数项，底数通常取2或者自然对数\(e\)，此时熵的单位分别为比特（bit）或纳特（nat）。从定义中我们可以看到，熵只依赖于\(X\)的分布，而不依赖于具体的随机变量取值，因此也可以将\(X\)的熵记作\(H(p) = H(X)\)。当熵\(H(p) =0\)时，则表示随机变量完全没有不确定性。
条件熵则涉及到多个随机变量。设有随机变量\((X,Y)\)，它的联合概率分布为： \[ P(X=x_i,Y=y_i) = p_{ij},\quad i=1,2,...,n,\quad j=1,2,...,m \] 条件熵\(H(Y|X)\)表示在已知随机变量\(X\)的条件下，随机变量\(Y\)的不确定性，定义为在\(X\)给定的条件下，\(Y\)的条件概率分布的熵对\(X\)的数学期望： \[ H(Y|X) = \sum_{i=1}^np_iH(Y|X= x_i) \] 其中，\(p_i = P(X=x_i),i=1,2,...,n\)。
当熵和条件熵中的概率是由数据估计得到的，所对应的熵和条件熵通常也分别被称为经验熵和经验条件熵。
信息增益（information gain）的概念需要借助熵以及条件熵，它表示的是在得知特征\(X\)的信息之后，使得类\(Y\)信息的不确定性减少的程度。信息增益是针对某个特征\(A\)以及某个训练数据集\(D\)来说的，信息增益\(g(D,A)\)定义为集合\(D\)的熵\(H(D)\)与在特征\(A\)给定条件下\(D\)的条件熵\(H(D|A)\)之差，即： \[ g(D,A) = H(D) - H(D|A) \]
一般地，熵\(H(Y)\)与条件熵\(H(Y|X)\)之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
信息增益依赖于某个特征\(A\)。熵\(H(D)\)表示直接对训练数据集\(D\)进行分类的不确定性，而条件熵\(H(D|A)\)表示在特征\(A\)给定的条件下对数据集\(D\)分类的不确定性。显然在给定某个特征后，不确定性应该有所下降，否则就是这个特征对于分类基本没有用。而不同的特征往往具有不同的信息增益，信息增益大的特征具有更强的分类能力，我们在内部结点进行特征选择的时候，也是选择信息增益最大的特征进行划分。
总结来说，根据信息增益进行划分的时候，我们会依次计算每个特征的信息增益。假设此时选择了特征\(A\)。对于数据集\(D\)，基于它的分类结果可以得到一个随机变量，从而得到熵\(H(D)\)。而根据\(A\)的取值，我们可以将数据集\(D\)划分为n个子集\(D_1,D_2,...,D_n\)。对于每个子集\(D_i\)，基于分类结果，我们可以得到熵\(H(D_i)\)，而条件熵\(H(D|A)\)就是熵\(H(D_i)\)的期望，\(D_i\)对应的概率就是\(|D_i|/|D|\)。
信息增益比
以信息增益作为依据进行特征选择，可能会出现某种偏向，偏向于选择取值较多的特征。而信息增益比（information gain ratio）可以对这一问题进行校正。信息增益比定义如下： \[ g_R(D,A) = \frac{g(D,A)}{H_A(D)} = \frac{H(D)-H(D|A)}{H_A(D)} \] 其中，\(H_A(D)\)表示数据集\(D\)基于特征\(A\)取值的熵，\(n\)表示特征\(A\)有\(n\)个取值： \[ H_A(D) = -\sum_{i=1}^{n} \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|} \] 在特征选择时，会依次计算所有特征的信息增益比，然后选择最大的那个特征作为划分依据。
基尼系数
同样假设\(X\)是一个取有限个值的离散变量，有如下的概率分布： \[ P(X = x_i) = p_i,\quad i=1,2,...,n \] 则随机变量\(X\)的基尼系数定义为： \[ Gini(X) = \sum_{i=1}^n p_i(1-p_i) = 1 - \sum_{i=1}^n p_i^2 \] 对于训练数据集\(D\)，针对特征\(A\)可以将其划分为若干个子集\(D_1,D_2,...,D_n\)。对于每个子集\(D_i\)，我们可以计算出它基于分类结果的基尼系数\(Gini(D_i)\)，而整体基于特征\(A\)的基尼系数则是子集基尼系数\(Gini(D_i)\)的期望，\(D_i\)对应的概率就是\(|D_i|/|D|\)。 \[ Gini(D,A) = \sum_{i=1}^n\frac{|D_i|}{|D|}Gini(D_i) \] 基尼系数\(Gini(D)\)表示集合\(D\)的不确定性，而\(Gini(D,A)\)表示经过\(A\)划分之后集合\(D\)的不确定性。基尼系数越大，集合的不确定性也就越大，这点与熵是相似的。基于基尼系数进行特征选择时，我们会选择对应基尼系数最小的那个特征，它对应得到的集合不确定性也最小。
决策树剪枝
有了特征选择的依据，我们就可以递归地进行决策树生成。完成生成的树通常会发生过拟合的现象，因此我们需要考虑决策树的复杂度，进行决策树剪枝，对已生成的决策树进行简化。剪枝（pruning）从已经生成的树上裁掉一些子树或者叶子结点，并将其根结点或者父结点作为新的叶子结点，从而简化树模型。
极小化决策树整体的损失函数是一种剪枝的方式。假设生成的决策树为\(T\)，它的叶子结点的个数为\(|T|\)，并且\(t\)是树\(T\)的叶子结点，该叶子结点中有\(N_t\)个样本点，则决策树学习的损失函数可以定义如下： \[ \begin{aligned} C_{\alpha}(T) &= C(T) + \alpha |T| \\ &= \sum_{t=1}^{|T|}N_t H_t(T) + \alpha|T| \end{aligned} \] 其中\(H_t(T)\)表示在叶子结点\(t\)上基于分类结果得到的经验熵；\(C(T)\)表示模型对训练数据的预测误差，它是所有叶子结点上经验熵的加权\(N_t\)和；\(|T|\)是叶子结点的个数，一定程度上表示模型的复杂度；\(\alpha \ge 0\)控制训练误差与模型复杂度之间的影响。
剪枝就是在\(\alpha\)确定的情况下，选择损失函数最小的模型。实际上，这里定义的损失函数极小化等价于正则化的极大似然估计。
剪枝算法整体是一个自下而上的过程。对一棵完全生成的树\(T\)以及给定的参数\(\alpha\)，我们首先计算每个结点的经验熵，之后递归地从树的叶子结点向上回缩。当然回缩是有条件的，假设叶子结点回缩前后整体树分别为\(T_B\)和\(T_A\)，则当\(C_{\alpha}(T_A) \le C_{\alpha}(T_B)\)时，才进行叶结点回缩。递归进行直到无法回缩，我们就可以得到损失函数最小的树模型。
学习算法
常见的决策树学习算法包括ID3、C4.5以及CART。
ID3
ID3算法的核心是在决策树的各个结点上应用信息增益准则进行特征选择，递归地构建决策树。从根结点开始进行特征选择，递归进行决策树构建，直到所有特征的信息增益均很小或者没有特征可以选择为止。我们一般会给定一个阈值$$，如果当前结点上经过选择后特征对应的信息增益都小于这个阈值，则不再进行递归划分，而它将成为一个单结点树，返回的结果则是对应实例中出现次数最多的类别。
ID3算法中只有树的生成，所以该算法生成的树容易产生过拟合。
C4.5
C4.5算法与ID3算法相似，差别在于C4.5在特征选择的时候使用了信息增益比（也存在阈值$$的使用）。
CART
CART全称为分类与回归树（Classification And Regression Tree），是一种应用广泛的决策树学习方法。CART同样包括特征选择、决策树生成以及决策树剪枝。它既可以用于分类也可以用于回归。
CART中假设决策树都是二叉树，即每次特征选择后将数据集划分成两份，递归地二分每个特征。
- CART决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大
- CART决策树剪枝：用验证数据集对已生成的树进行剪枝，并选择最优子树，此时用损失函数最小作为剪枝的标准
CART生成
CART决策树的生成指的是递归地构建二叉决策树的过程。其中又可以分为回归树和分类树，对回归树使用平方误差最小化准则，对分类树用基尼系数最小化准则。
一棵回归树对应输入空间的一个划分以及在划分单元上的输出值。类比于分类树，回归树的叶子结点上输出的是一个固定的值，而分类树则是类别标签。当输入空间的划分确定之后，可以使用平方误差来表示回归树对训练数据的预测误差，同时通过最小化预测误差来决定当前结点输出什么样的值。因此对于CART回归树来说，接下来需要确定的就是如何进行空间划分。
对于CART回归树来说，内部结点得到的训练资料是\(D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}\)，其中\(y_i\)是连续变量，\(x_i\)是一个多维向量\((x_i^{(1)},x_i^{(2)},...,x_i^{(n)})\)。CART每次的选择都是进行二分。对于第\(i\)个输入的第\(j\)个维度分量\(x_i^{(j)}\)，假设取值为\(x_i^{(j)} = s\)，那么根据这个值，就可以将输入空间划分为两个部分： \[ R_1(j,s) = \{x|x^{(j)} \le s\},\quad R_2(j,s) = \{x|x^{(j)} > s\} \] 对于固定的\(i\)，我们可以找到最优切分点\(s\)，就是说对于给定的输入\(x_i\)，确定以它的第几个维度分量进行划分能够做到预测误差最小化，以即完成最优化： \[ \min_{j,s} [\min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2] \] 也就是对于给定的输入变量\(x_i\)，我们能够得到一个最优的划分\((j,s)\)。之后遍历所有的输入变量，找到全局的最优划分，以最优化分作为当前内部结点的划分。递归进行上述的划分操作，这样就生成一棵回归树。这样的回归树通常被称为最小二乘回归树。
CART分类树，内部结点的特征选择则是基于基尼系数的。不过需要注意的是，由于CART都是二分决策的，因此对于选定的特征\(A\)，每次按照特征\(A\)的某个取值\(a\)进行划分，得到两个子集\(D_1,D_2\)，基尼系数的计算如下，每次选择能够使得基尼系数最小的特征以及取值。 \[ Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|} Gini(D_2) \] 算法停止计算的条件有三种：
- 结点中的样本个数小于预定阈值
- 结点中最优基尼系数小于预定阈值
- 没有更多的特征或类别
CART剪枝
CART剪枝算法通过从完全长成的决策树底端剪去一些子树，降低模型的复杂度。具体来说，CART剪枝算法由两步组成：
- 从完全生成的决策树\(T_0\)的底端开始不断剪枝直到\(T_0\)的根结点，形成一个子树序列\(\{T_0,T_1,...,T_n\}\)
- 利用交叉验证的方法在独立的验证数据集上对子树序列进行测试，从中选择最优的子树
在生成子树序列的过程中，我们需要使用到树的损失函数： \[ C_{\alpha}(T) = C(T) + \alpha|T| \] 对于固定的\(\alpha\)，我们一定能够找到使得损失函数\(C_{\alpha}(T)\)最小的子树，将其记为\(T_{\alpha}\)。当\(\alpha\)偏大的时候，最优子树偏小；反之最优子树偏大。
生成子树序列的过程同样伴随着\(\alpha\)的增大。具体来说，我们将\(\alpha\)从小增大，得到\(0=\alpha_0 < \alpha_1<...<\alpha_n <+\infty\)，如此产生了一系列区间\([\alpha_i,\alpha_{i+1}),i=0,1,...,n\)。我们剪枝得到的子树序列恰好对应于这些区间，更具体地说，子树\(T_i\)对应区间\([\alpha_i,\alpha_{i+1})\)，它表示在\(\alpha \in [\alpha_i,\alpha_{i+1})\)的情况下，我们能够得到的最优子树。
假设我们从\(T_0\)开始剪枝，对于\(T_0\)的任意内部结点\(t\)，以\(t\)为单结点树，损失函数为： \[ C_{\alpha}(t) = C(t) + \alpha \] 而以\(t\)为根结点的子树，损失函数为： \[ C_{\alpha}(T_t) = C(T_t) + \alpha|T_t| \] 当\(\alpha=0\)以及充分小的时候，有： \[ C_{\alpha}(T_t) < C_{\alpha}(t) \] 随着\(\alpha\)的增大，会存在某个\(\alpha\)，有： \[ C_{\alpha}(T_t) = C_{\alpha}(t) \] 此时有： \[ \alpha = \frac{C(t) - C(T_t)}{|T_t| - 1} \] 于是，我们需要做的就是对\(T_0\)的每个内部结点\(t\)，计算： \[ g(t) = \frac{C(t) - C(T_t)}{|T_t| - 1} \] 这表示剪枝后整体损失函数减少的程度。在\(T_0\)中减去\(g(t)\)最小的子树\(T_{t}\)，将得到的树作为\(T_1\)，同时更新\(\alpha\)，将最小的\(g(t)\)设置为\(\alpha_1\)。重复这个过程，不断增加\(\alpha\)的值，得到一系列区间，得到一系列子树，直到得到根结点。如此就得到了子树序列。整个过程相当于每次对树进行一次修剪，得到子树构成子树序列，然后通过交叉验证选择表现最好的子树作为最终的输出。