Decision Tree

决策树是一种用于分类/回归的机器学习算法,基于树结构来进行决策。一棵决策树包含根结点、内部结点和叶结点。根结点包含样本全集,内部结点对应属性,叶结点对应决策结果。

1. 伪代码

# 输入:训练集:D={(x_1,y_1),(x_2,y_2),...,(x_m,y_m)} ,属性集:A={a_1,a_2,...,a_d}
# 输出:以node为根结点的决策树
def TreeGenerate(D,A):
    生成结点node;
    if D中样本属于同类C:
        将node标记为类别C; #属于同类,无需划分
    if A为空 or D中样本在A上取值相同:
         将node标记为叶结点,类别标记为D中样本最多的类; #无法划分,类别设定为当前结点最多的类
    从A中选取最优划分属性a; # 不同选取策略产生不同决策树算法
    for i in a['value']:
        为node生成一个分支; # 属性的取值
        D_v = {a['value']:a['value']=a_v} # 划分子集
        if D_v为空:
            将分支结点标记为叶结点,类别标记为D中样本最多的类; # 无法划分,类别设定为父结点最多的类
        else:
            TreeGenerate(D_v,A\{a}); # 递归生成决策树

2. 划分选择

  1. 信息增益(ID3决策树算法)
    $$Ent(D)=-\sum_{k=1}^{\left | \gamma \right |}p_klog_2p_k$$ $$Gain(D,a) = Ent(D)-\sum_{v=1}^{V}\frac{\left | D^v \right |}{\left | D \right |}Ent(D^v)$$
    $Ent(V)$  表示信息熵,是度量样本集合纯度最常用的一种指标。信息熵越小,集合纯度越高。$Gain(D,a)$ 表示信息增益。信息增益越大,意味着使用属性$a$来进行划分所获得的集合纯度越高。 缺点:信息增益对可取值数目较多的属性有所偏好。
  2. 增益率(C4.5决策树算法)
    $$Gain_ratio(D,a) = \frac{Gain(D,a)}{-\sum_{v=1}^{V}\frac{\left | D^v \right |}{\left | D \right |}log_2\frac{\left | D^v \right |}{\left | D \right |}}$$
    $IV(a)={-\sum_{v=1}^{V}\frac{\left | D^v \right |}{\left | D \right |}log_2\frac{\left | D^v \right |}{\left | D \right |}}$称为$a$的固有值,$a$的取值数目越多,$IV(a)$越大。$Gain_ratio(D,a)$表示增益率,增益率越大,集合纯度越高。 缺点:增益率对可取值数目较少的属性有所偏好。(C4.5算法没有直接使用增益率,而是先从候选属性中找出信息增益大于平均值的属性,再从中找出增益率最高的作为最优化分属性,这是一种折中)
  3. 基尼指数(CART决策树算法)
    $$Gini(D) = 1 – \sum_{k=1}^{\left | \gamma \right |}p_k^2$$ $$Gini_index(D,a) = \sum_{v=1}^{V}\frac{\left | D^v \right |}{\left | D \right |}Gini(D^v)$$
    $Gini(D)$表示基尼指数,$Gini_index(D,a)$表示属性$a$的基尼指数。基尼指数越小,集合纯度越高。

3. 剪枝

剪枝是决策树算法处理过拟合问题的主要手段。分为预剪枝和后剪枝,预剪枝是在树的生成过程中进行剪枝,后剪枝是生成决策树之后再进行剪枝。剪枝的方法是判断剪枝前后模型的泛化能力是否有提升,泛化能力的度量即为性能评估方法,如准确率等。