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}_{k}lo{g}_2{p}_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 决策树算法）
   $$Gai{n}_{r}atio(D,a)=\frac{Gain(D,a)}{-\sum _{v=1}^V\frac{\left|D^v\right|}{\left|D\right|}lo{g}_2\frac{\left|D^v\right|}{\left|D\right|}}$$
   $IV(a)=-\sum _{v=1}^V\frac{\left|D^v\right|}{\left|D\right|}lo{g}_2\frac{\left|D^v\right|}{\left|D\right|}$ 称为 $a$ 的固有值，$a$ 的取值数目越多，$IV(a)$ 越大。$Gai{n}_{r}atio(D,a)$ 表示增益率，增益率越大，集合纯度越高。

   缺点：增益率对可取值数目较少的属性有所偏好。（C4.5 算法没有直接使用增益率，而是先从候选属性中找出信息增益大于平均值的属性，再从中找出增益率最高的作为最优化分属性，这是一种折中）

3. 基尼指数（CART 决策树算法）

   $$Gini(D)=1-\sum _{k=1}^{\left|\gamma \right|}{p}_k^2$$

   $$Gin{i}_{i}ndex(D,a)=\sum _{v=1}^V\frac{\left|D^v\right|}{\left|D\right|}Gini(D^v)$$

   $Gini(D)$ 表示基尼指数，$Gin{i}_{i}ndex(D,a)$ 表示属性 $a$ 的基尼指数。基尼指数越小，集合纯度越高。

剪枝

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