决策树

决策树

决策树建树的基本流程

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

• 信息增益

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

  $$Ent(D)=-\sum^{|y|}_{k=1}p_klog_2p_k$$

  信息增益为

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

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

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

  $$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$$

  其中

  $$IV(a)=-\sum^V_{v=1}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$$

  称为属性a的固有属性值

• Gini系数

  $$Gini(D)=\sum^{|y|}_{k=1}\sum_{k'\neq k}p_kp_{k'}=1-\sum^{|y|}_{k=1}p_k^2$$

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

  基尼指数(选择最小的)

  $$Gini\_index(D,a)=\sum^V_{v=1}\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)*p(t)$为结点的误差代价，如果该结点被剪枝,r(t)为结点t的误差率；p(t)为结点t上的数据占所有数据的比例

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

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

  • 最小误差剪枝

  • 悲观误差剪枝