决策树

· · 算法·理论

  1. 决策树简而言之就是一个二叉树，它按每一个节点的特征分类向下，直到底端给你一个分类结果。

  2. 那么我们现在就可以考虑分类特征的选择问题，这里我们介绍信息增益这个概念。 首先给出熵与条件熵的定义。 在概率统计中，熵表示随机变量不确定性的度量

    P(X=x_i)=p_i,i=1,2,\ldots,n

    随机变量X的熵定义为

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

    熵越大，不确定性也就越大。(此处规定0log0=0) 设有随机变量P(x,y)，其联合概率分布为

    P(X=x_i,Y=y_j)=p_{ij},i=1,2,\ldots,n;j=1,2,\ldots,n

    条件熵H(Y|X)表示在X的条件下随机变量Y的不确定性,条件熵定义如下

    H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)

    即X给定时Y的条件概率分布的熵对X的数学期望 信息增益则表示得知特征X的信息而使Y的信息不确定度减少的程度。用函数g(D,A)来表示特征A对数据集D的信息增益，我们定义其为两个熵的差值

    g(D,A)=H(D)-H(D|A)

    我们可以发现g(D,A)是会随着数据集的大小二人变化的，无绝对意义。由此，我们引入信息增益g_R(D,A)比来解决这一问题。

    g_R(D,A)=g(D,A)/H(D)

  3. 决策树生成算法

    • ID3算法(生成决策树T)

      (1)若D中所有实例属于同一类C_k,则T为单节点树,并将类C_k作为该节点的类标记，返回T

      (2)若A=\varnothing,则T为单节点树，并将D中实例数最大的类C_k作为该节点的类标记，返回T

      (3)否则，计算A中各特征对D的信息增益，选择最大者A_g

      (4)如果A_g小于阈值(增益太小，没有意义,)则T为单节点树，并将D中实例数最大的类C_k作为该节点的类标记，返回T

      (5)否则，按A_g特征的每一个可能值a_i划分相应的非空子集D_i,将D_i中实例数最大的类作为标记，构建子节点，由节点及子节点构成树T，返回T

      (6)对第i个子节点，以D_i为训练集，以A-{A_g}为特征集，重复(1)~(5),得到子树T_i,返回T_i

    • C4.5算法与ID3类似(将信息增益替换为信息增益比)

  4. 剪枝

    显然，上述算法是为了尽力提高对训练数据集的预测准确度的原理而运行，容易构建过于复杂的决策树,这样往往会导致过拟合的现象，对测试数据的分类不一定准确。

    因此，我们需要对决策树进行简化，即“剪枝”。

    剪枝往往通过极小化决策树整体的损失函数来实现。

    设树T的叶节点个数为|T|,t是树T的叶节点，该叶节点上有N_t个样本点，其中k类的样本点有N_{tk}个，H_t(T)为叶节点t上的经验熵,\alpha\ge0为参数，则决策树学习的损失函数可以定义为

    C_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|

    其中经验熵为

    H_t(T)=-\sum_k\dfrac{N_{tk}}{N_t}log\dfrac{N_{tk}}{N_t}

    此处将\sum_{t=1}^{|T|}N_tH_t(T)记作C(T)

    此时有

    C_\alpha(T)=C(T)+\alpha|T|

    我们来解释一下这个公式,C(T)表示的是模型对训练数据的预测误差,T作为树的大小-1，表示了树的复杂度，参数\alpha控制两者之间的影响。

    剪枝就是\alpha确定时，选择损失函数最小的模型。

    • 剪枝算法

      现在已知树T,\alpha，返回修剪后的树

      (1)计算每个节点的经验熵

      (2)递归地从树的叶节点向上回缩

      设一组叶节点回缩到父节点前后的整体树分别为T_B与T_A,如果

      C_\alpha(T_A)\le C_\alpha(T_B)

      则进行剪枝，将父节点作为新的叶节点。

      (3)继续(2),直到不能再继续为止，得到目标T_\alpha

  5. CART算法

    简单来说CART算法是通过不停的二分训练数据集来实现构造一个二叉决策树，当然，它也可以剪枝。它可以生成回归树和分类树。