决策树

决策树

决策树建树的基本流程

划分选择（为使”纯度”越来越高）

• 信息增益

  信息熵为(越小则纯度越高)

  $$Ent(D)=-\sum _{k=1}^{|y|}{p}_{k}lo{g}_2{p}_k$$

  信息增益为

  $$Gain(D)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$

  缺点：对于可以取值数目较多的属性有所偏好。

• 信息增益率（克服上述所述缺点）

  $$Gain\mathrm{\_}ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$$

  其中

  $$IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}lo{g}_2\frac{|D^v|}{|D|}$$

  称为属性a的固有属性值

• Gini系数

  $$Gini(D)=\sum _{k=1}^{|y|}\sum _{k^{\prime }\ne k}{p}_k{p}_{k^{\prime }}=1-\sum _{k=1}^{|y|}{p}_k^2$$

  反应了从数据集D中随机抽取两个样本，其类别标记不一致的概率

  基尼指数(选择最小的)

  $$Gini\mathrm{\_}index(D,a)=\sum _{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$$

剪枝处理

• 预剪枝

  • 若当前划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶结点

• 后剪枝

  • 自底向上对非叶子节点进行考察，若将该节点对应的子树替换为叶结点能带来泛化能力的提升，则将该子树替换为叶结点

  • 代价复杂性剪枝：对于每个非叶子节点计算它的表面误差率增益值$\alpha$。

    $$\alpha =\frac{R(t)-R(T_t)}{|N_{T_t}|-1}$$

    $|N_{T_t}|$为子树中包含的叶子结点的个数

    $R(t)=r(t)\ast p(t)$为结点的误差代价，如果该结点被剪枝,r(t)为结点t的误差率；p(t)为结点t上的数据占所有数据的比例

    $R(T_t)$是子树Tt的误差代价，如果该节点不被剪枝。它等于子树Tt上所有叶子节点的误差代价之和。

    找到$\alpha$值最小的非叶子节点，令其左右孩子为NULL

  • 最小误差剪枝

  • 悲观误差剪枝