Decison Tree

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

伪代码

# 输入：训练集：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}); # 递归生成决策树

划分选择

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$的基尼指数。基尼指数越小，集合纯度越高。

剪枝

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