Decision Tree part2

blairchen

data-science

Publish：Jun 27, 2018

views

1. 决策树模型

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）

关于 ID3 与 C4.5 的具体计算流程示例，请参见 desicion tree (part1)

1.1. 定义

分类决策树模型是一种描述对实例进行分类的树形结构，其中包含两种类型的节点

1. 内部节点: 表示一个 feature（属性）
2. 叶节点: 表示一个 class

一般决策树可以根据以下四个方面划分归类 :

1. 分支数
2. 划分策略
3. 终止策略
4. 基分类器

1.2. if-then规则集合

1. 一条由根节点到叶节点的路径 –> 一条规则
2. 路径上内部节点的特征 –> 规则的条件
3. 叶节点的类 –> 规则的结论 class
4. 性质：互斥且完备

1.3. 条件概率分布

给定 feature 条件下 class 的条件概率分布

2. 决策树的学习

决策树学习本质是从 train datasets 中归纳出一组分类规则，另一个角度，学习是由 train datasets 估计条件概率模型

2.1 目的

得到一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力

2.2 策略

以损失函数（通常为正则化的极大似然函数）为目标函数的最小化，并在损失函数确定后，选择最优决策树

2.3 学习算法

1. 理论上：从所有可能的决策树中选取最优决策树，NP完全问题
2. 实际中：采用启发式方法，近似求解（得到次最优决策树）–> 递归的选择最优特征，并根据该最优特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。
3. 主要步骤： (1). 特征选择 (2). 决策树的生成 (3). 决策树的剪枝

Notes: 决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。

3. 特征选择

• 实质 ： 选取对于训练数据具有分类能力的特征（决定用哪个 feature 来划分 feature space）

• 常用准则

Algorithm	Feature 选择方法	Author
ID3	Information gain	Quinlan. 1986
C4.5	Gain ratio	Quinlan. 1993.

CART | 回归树： 最小二乘
分类树： 基尼指数 Gini index | Breiman. 1984
(Classification and Regression Tree 分类与回归树)

3.1 信息增益 Information gain

$g(D, A)=H(D)-H(D|A)$

$g(D, A)$即信息增益，表示得知特征$A$的信息而使得类$D$的信息的不确定性减少的程度

$H(D)$ 为集合 $D$ 的信息熵

• 其中假设 $D$ 是一个取有限个值的离散随机变量，概率分布为 $P(X=x_i)=p_i, i=1, 2,…,n$

• 熵是表示随机变量不确定性的度量，定义 $H(D)=- \sum_{i=1}^n p_ilogp_i$，熵越大，随机变量的不确定性就越大，$0 \leq H(D) \leq logn$

• $H(D|A)$ 经验条件熵在已知随机变量$A$（特征）的条件下随机变量 $D$ 的不确定性$H(D|A)= \sum_{i=1}^{n}p_iH(D|A=a_i)$

• 一般将熵 $H(D)$ 与条件熵 $H(D|A)$ 之差称为互信息，决策树学习中的信息增益等价于类与特征的互信息

小结:

• 给定训练数据集 $D$ 和特征 $A$，经验熵 $H(D)$ 表示对数据集 $D$ 进行分类的不确定性，而经验条件熵 $H(D|A)$ 表示在特征 $A$ 给定的条件下对数据集进行分类的不确定性，因此两者之差即信息增益表示由于特征 $A$ 而使得数据集 $D$ 的分类的不确定性减少的程度.

• 对于数据集 $D$ 而言，信息增益依赖于特征，不同特征具有不同的信息增益，信息增益大的特征具有更强的分类能力（也就是我们需要挑选的目标）

3.2 信息增益比 Gain ratio

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，使用信息增益比可以对这问题进行校正.

特征$A$对训练数据集$D$的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集$D$关于特征$A$的值的熵$H_A(D)$之比：

$g_R(D,A)= \frac{g(D,A)}{H_A(D)}$

其中

$H\_A(D)=- \sum\_{i=1}^{n} \frac{|D\_{i}|}{|D|}log\_2 \frac{|D\_{i}|}{|D|}$

$n$ 为特征 $A$ 的取值个数，$D_i$ 表示据特征 $A$ 的取值将 $D$ 分成的子集

4. 决策树的生成

4.1 ID3

核心思想:

• 在决策树的各个结点上应用信息增益准则选择特征，递归地构建决策树。
• 递归终止条件：所有特征的信息增益（设置信息增益的阈值来判断是否进一步划分）均很小或没特征可选为止.

（每选一个特征则后期划分子树不再使用前面用过的特征，因为子树已经是在该特征下属于同一取值的实例集合）

决策树的生成:

输入：训练数据集 $D$ 和特征集 $A$，阈值 $ε$；
输出：决策树 $T$

(1) （叶子结点）若 $D$ 中所有实例属于同一类 $C\_k$, 则 $T$ 为单节点树，并将类$C\_k$ 作为该结点的类标记，返回 $T$
(2) （终止条件之没有特征可供选择） 若 $A=∅$, 则 $T$为单节点树，并将 $D$ 中实例数最大的类 $C\_k$ 作为该结点的 class 标记（多数表决规则），返回 $T$

(3) （计算 $A$ 中各特征对 $D$ 的信息增益，选择信息增益最大的特征 $A\_g$
(4) （终止条件之阈值) 若 $A\_g$ 的信息增益小于阈值 $ε$，则置 $T$ 为单节点树，并将 $D$ 中实例数最大的类 $C\_k$ 作为该结点的类标记，返回 $T$

(5) 否则，对 $A\_g$ 的每一可能值 $a\_i$，依 $A\_g=a\_i$ 将 $D$ 划分为若干非空子集 $D\_i$，并将 $D\_i$ 中实例数最大的类作为标记构建子节点，返回 $T\_i$
(6) 对第 $i$ 个子节点，以 $D\_i$ 为训练集，$A − {A\_g}$ 为特征集，递归地调用(1)~(5)得到子树 $T\_i$ 并返回.

4.2 C4.5

C4.5算法与ID3算法类似，不同之处在于，C4.5在生成的过程中，用Gain ratio来选择特征。

Notes: 上述决策树的生成算法只有树的生成，而且是针对训练集构造的树，容易产生过拟合。

5. CART(classification and regression tree)

• CART 假设决策树是二叉树，而 ID3,C4.5 生成的过程中并无此假设，这也导致了两者的根本不同，ID3,C4.5 每次选择出最佳特征之后，是按照该特征的每一个取值划分子树；
• CART 则是对每一个特征、每一个特征的每一个取值计算基尼指数（分类树）然后从所有特征对应的取值计算所得的基尼指数中最小的特征及特征值作为切分点来划分子树，并在这些子空间上确定预测的概率分布，也就是在输入给定的条件下输出对应的条件概率分布.

5.1 CART 纯度度量

CART 中用于选择变量的不纯性度量是 Gini index；如果目标变量是标称的，并且是具有两个以上的类别，则 CART 可能考虑将目标类别合并成两个超类别（双化）；如果目标变量是连续的，则 CART 找出一组基于树的回归方程来预测目标变量。

5.2 CART 步骤

build decision tree时通常采用自上而下的方法，在每一步选择一个最好的属性来分裂。 “最好” 的定义是使得子节点中的训练集尽量的纯。不同的算法使用不同的指标来定义"最好"。

CART 是在给定输入随机变量 $X$ 条件下求得输出随机变量 $Y$ 的条件概率分布的学习方法。

可以看出CART算法在叶节点表示上不同于ID3、C4.5方法，后二者叶节点对应数据子集通过“多数表决”的方式来确定一个类别（固定一个值）；而CART算法的叶节点对应类别的概率分布。如此看来，我们可以很容易地用 CART 来学习一个 multi-label 的分类任务。

CART 算法也主要由两步组成:

• 决策树的生成：基于训练数据集生成一棵二分决策树；
• 决策树的剪枝：用验证集对已生成的二叉决策树进行剪枝，剪枝的标准为损失函数最小化。

由于分类树与回归树在递归地构建二叉决策树的过程中，选择特征划分的准则不同。

• 二叉分类树构建过程中采用基尼指数（Gini Index）为特征选择标准；
• 二叉回归树采用平方误差最小化作为特征选择标准。

5.3 树的构建

5.3.1 二叉回归树

设 $X$, $Y$ 分别为输入和输出变量，其中 $Y$ 为连续变量，给定训练数据集 $D= \lbrace (x\_1, y\_1), (x\_2, y\_2),…,(x\_N, y\_N) \rbrace$

决策树的生成就是递归地构建二叉决策树的过程，对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树

一个回归树对应着输入空间（即特征空间）的一个划分以及在划分的单元上的输出值，所以我们的主要目的是要构建回归树，也就是如何划分输入空间，因为一旦划分好输入空间，如将输入空间划分为 $M$ 个单元, $R\_1, R\_2, … , R\_M$ , 并且在每个单元 $R\_m$ 上有一个固定的输出值 $c\_m$，那么回归树的模型就可以表示为

$f(x)=\sum\_{m=1}^Mc\_mI(x \in R\_m)$

概念强调

首先要强调的是 CART假设决策树是二叉树，内部结点特征的取值只有“是”和“否”，左分支是取值为“是”的分支，有分支则相反。这样的决策树等价于递归地二分每个特征.

最小二叉回归树生成算法

输入：训练数据集$D$；
输出：回归树 $f(x)$

算法：在训练集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上输出值，构建二叉决策树

(1). 择最优切分变量$j$与切分点$s$，求解

$\min\_{j,s}[\min\_{c\_1} \sum\_{x\_i\in R\_1(j,s)}(y\_i-c\_1)^2 + \min\_{c\_2} \sum\_{x\_i\in R\_2(j,s)}(y\_i-c\_2)^2]$

遍历变量$j$，对固定的切分变量$j$扫描切分点$s$，选择使上式最小值的对$(j,s)$。其中$R\_m$是被划分的输入空间，$c\_m$是空间$R\_m$对应的固定输出值。

(2). 用选定的对$(j,s)$划分区域并决定相应的输出值：

$R_1(j,s)=\lbrace x\mid x^{(j)} \le s \rbrace , \quad R_2(j,s)=\lbrace x \mid x^{(j)} \gt s \rbrace$

$\hat c\_m = {1\over N\_m}\sum\_{x\_i\in R\_m(j,s)}y\_i , \quad x\in R\_m , m=1,2$

(3). 继续对两个子区域调用步骤（1），（2），直至满足停止条件。

(4). 将输入空间划分为$M$个区域$R\_1$,$R\_2$ , … , $R\_M$，生成决策树：

$f(x) = \sum\_{m=1}^M\hat c\_m I(x\in R)$

举个🌰🌰🌰:

训练数据见下表，$x$ 的取值范围为区间 $[0.5,10.5]$, $y$ 的取值范围为区间$[5.0,10.0]$ ,学习这个回归问题的最小二叉回归树。

$x\_i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---- | — | — | — | — | — | — | — | — | —
$y\_i$ | 5.56 | 5.70 | 5.91 | 6.40 | 6.80 | 7.05 | 8.90 | 8.70 | 9.00 | 9.05

首先来看这个优化问题

$\min\_{j,s}[\min\_{c\_1} \sum\_{x\_i\in R\_1(j,s)}(y\_i-c\_1)^2 + \min\_{c\_2} \sum\_{x\_i\in R\_2(j,s)}(y\_i-c\_2)^2]$

求解训练数据的切分点s:

$R_1(j,s)=\lbrace x\mid x^{(j)} \le s \rbrace , \quad R_2(j,s)=\lbrace x \mid x^{(j)} \gt s \rbrace$

容易求得在 $R\_1$,$R\_2$ 内部使得平方损失误差达到最小值的 $c\_1$,$c\_2$ 为：

$c\_1={1\over N\_1}\sum\_{x\_i \in R\_1}y\_i , \quad c\_2={1\over N\_2}\sum\_{x\_i \in R\_2}y\_i$

这里 $N\_1$,$N\_2$ 是 $R\_1$,$R\_2$的样本点数。

求训练数据的切分点，根据所给数据，考虑如下切分点：

$1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5$

对各切分点，不难求出相应的 $R\_1$ , $R\_2$ , $c\_1$ , $c\_2$ 及

$m(s)=\min\_{j,s}[\min\_{c\_1} \sum\_{x\_i\in R\_1(j,s)}(y\_i-c\_1)^2 + \min\_{c\_2} \sum\_{x\_i\in R\_2(j,s)}(y\_i-c\_2)^2]$

例如，当 $s=1.5$ 时，$R\_1 = \lbrace 1\rbrace$, $R\_2 = \lbrace 2, 3 , \ldots , 10\rbrace$, $c\_1 = 5.56$, $c\_2 = 7.50$,

$m(s)=\min\_{j,s}[\min\_{c\_1} \sum\_{x\_i\in R\_1(j,s)}(y\_i-c\_1)^2 + \min\_{c\_2} \sum\_{x\_i\in R\_2(j,s)}(y\_i-c\_2)^2] = 0+15.72 = 15.72$

现将$s$及$m(s)$的计算结果列表如下：

由上表可知，当$x=6.5$的时候达到最小值，此时 $R\_1 = \lbrace 1 ,2 , \ldots , 6\rbrace$, $R\_2 ={7 ,8 ,9 , 10}$, $c\_1 = 6.24$, $c\_2 = 8.9$

所以回归树 $T\_1(x)$ 为：

$T\_1(x) = \begin{cases} 6.24, & x\lt 6.5 \\\\ 8.91, & x \ge 6.5 \\\\ \end{cases}$

$f\_1(x) = T\_1(x)$

用 $f\_1(x)$ 拟合训练数据的残差见下表，表中 $r\_{2i} = y\_i - f\_1(x\_i),i=1,2,\ldots , 10$

$x\_i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---- | — | — | — | — | — | — | — | — | —
$y\_i$ | -0.68 | -0.54 | -0.33 | 0.16 | 0.56 | 0.81 | -0.01 | -0.21 | 0.09 | 0.14

用$f\_1(x)$拟合训练数据的平方误差：

$L(y,f\_1(x)) = \sum\_{i=1}^{10}(y\_i-f\_1(x\_i))^2 = 1.93$

第2步求 $T\_2(x)$.方法与求 $T\_1(x)$ 一样，只是拟合的数据是上表的残差，可以得到：

$T\_2(x) = \begin{cases} -0.52, & x\lt 3.5 \\\\ 0.22, & x \ge 3.5 \\\\ \end{cases}$

$f\_2(x) = f\_1(x) + T\_2(x)= \begin{cases} 5.72, & x\lt 3.5 \\\\ 6.46, & 3.5\le x \lt 6.5 \\\\ 9.13, & x\ge 6.5 \\\\ \end{cases}$

用$f\_2(x)$拟合训练数据的平方误差是：

$L(y,f\_2(x)) = \sum\_{i=1}^{10}(y\_i-f\_2(x\_i))^2 = 0.79$

继续求得

$T\_3(x) = \begin{cases} 0.15, & x\lt 6.5 \\\\ -0.22, & x \ge 6.5 \\\\ \end{cases} \quad L(y,f\_3(x)) = 0.47 ,$

$T\_4(x) = \begin{cases} -0.16, & x\lt 4.5 \\\\ 0.11, & x \ge 4.5 \\\\ \end{cases} \quad L(y,f\_3(x)) = 0.30 ,$

$T\_5(x) = \begin{cases} 0.07, & x\lt 6.5 \\\\ -0.11, & x \ge 6.5 \\\\ \end{cases} \quad L(y,f\_3(x)) = 0.23 ,$

$T\_6(x) = \begin{cases} -0.15, & x\lt 2.5 \\ 0.04, & x \ge 2.5 \\ \end{cases}$

$f\_6(x) = f\_5(x)+T\_6(x) =T\_1(x)+ \ldots + T\_5(x) + T\_6(x)= \begin{cases} 5.63, & x\lt 2.5 \\\\ 5.82, & 2.5 \le x\lt 3.5 \\\\ 6.56, & 3.5 \le x\lt 4.5 \\\\ 6.83, & 4.5 \le x\lt 6.5 \\\\ 8.95, & x\ge 6.5 \\\\ \end{cases}$

用$f\_6(x)$拟合训练数据的平方损失误差是

$L(y,f\_6(x)) = \sum\_{i=1}^{10}(y\_i-f\_6(x\_i))^2 = 0.71$

假设此时已经满足误差要求，那么 $f(x) = f\_6(x)$ 即为所求的回归树。

5.3.2 二叉分类树

二叉分类树中用基尼指数（Gini Index）作为最优特征选择的度量标准。基尼指数定义如下：

Gini Index :

1. 是一种不等性度量；
2. 通常用来度量收入不平衡，可以用来度量任何不均匀分布；
3. 是介于0~1之间的数，0-完全相等，1-完全不相等；
4. 总体内包含的类别越杂乱，GINI指数就越大（跟熵的概念很相似）

Gini Index :

同样以分类系统为例，数据集 $D$ 中类别 $C$ 可能的取值为$c\_1, c\_2, \cdots, c\_k$ （$k$是类别数），一个样本属于类别 $c\_i$ 的概率为$p(i)$。那么概率分布的 Gini index 公式表示为：

$Gini(D) = 1 - \sum_{i=1}^{k} {p\_i}^2 \qquad(fmt.2.1.1)$

其中$p\_i = \frac{类别属于c\_i的样本数}{总样本数}$。如果所有的样本 Category 相同，则 $p_1 = 1, p_2 = p_3 = \cdots = p_k = 0$，则有$p_1 = 1, p_2 = p_3 = \cdots = p_k = 0$，此时数据不纯度最低。$Gini(D)$ 的物理含义是表示数据集 $D$ 的不确定性。数值越大，表明其不确定性越大（这一点与 Info Entropy 相似）。
如果 $k=2$（二分类问题，类别命名为正类和负类），若样本属于正类的概率是 $p$，那么对应基尼指数为：

\begin{align} Gini(D) & = 1 - [p^2 + {(1-p)}^2] \\\ & = \underline {2p (1-p)} \qquad\qquad (fmt.2.1.2) \end{align}

如果数据集 $D$ 根据特征 $f$ 是否取某一可能值 $f\_∗$，将 $D$ 划分为 $D\_1=\{(x, y) \in D | f(x) = f\_{\ast}\}, D\_2=D-D\_1$。那么特征 $f$ 在数据集 $D$ 上的 Gini index 定义为：

$Gini(D, f=f\_{\ast}) = \frac{\vert D_1 \vert}{\vert D \vert} Gini(D\_1) + \frac{\vert D\_2 \vert}{\vert D \vert} Gini(D_2) \qquad\qquad (fmt.2.1.3)$

代表性的例子说明 :

下图是 IG 的决策树，并不是 二分分类树 ${Gini}$ ${index}$ 决策树, 放这里仅仅是为了感知一下

<img src="/images/ml/decision-tree/decision-tree-2.png" width=“530” /img>

在实际操作中，通过遍历所有特征（如果是连续值，需做离散化）及其取值，选择 $Min_{gini-index}$ 所对应的特征和特征值。

这里仍然以天气数据为例，给出特征阴晴的 Gini index 计算过程。

(1). 当特征“阴晴”取值为”sunny”时，$D\_1 = \{1,2,8,9,11\}, |D\_1|=5$；$D\_2=\{3,4,5,6,7,10,12,13,14\}, |D\_2|=9$. 数据自己对应的类别数分别为 $(+2,-3)、(+7,-2)$。因此 $Gini(D\_1) = 2 \cdot \frac{3}{5} \cdot \frac{2}{5} = \frac{12}{25}$；$Gini(D_2) = 2 \cdot \frac{7}{9} \cdot \frac{2}{9} = \frac{28}{81}$. 对应的基尼指数为：

$Gini(C, “阴晴”=”sunny”) = \frac{5}{14} Gini(D_1) + \frac{9}{14} Gini(D_2) = \frac{5}{14} \frac{12}{25} + \frac{9}{14} \frac{28}{81} = 0.394 \quad(exp.2.2.1)$

(2). 当特征“阴晴”取值为”overcast”时，$D\_1 = \{2,7,12,13\}, |D\_1|=4$；$D\_2=\{1,2,4,5,6,8,9,10,11,14\}, |D\_2|=10$。$D\_1$、$D\_2$ 数据自己对应的类别数分别为 $(+4,-0)、(+5,-5)$。因此 $Gini(D\_1) = 2 \cdot 1 \cdot 0 = 0；Gini(D\_2) = 2 \cdot \frac{5}{10} \cdot \frac{5}{10} = \frac{1}{2}$ 对应的基尼指数为：

$Gini(C, “阴晴”=”overcast”) = \frac{4}{14} Gini(D_1) + \frac{10}{14} Gini(D_2) = 0 + \frac{10}{14} \cdot \frac{1}{2} = \frac{5}{14} = 0.357 \quad(exp.2.2.2)$

(3). 当特征“阴晴”取值为”rainy”时，$D\_1 = \{4,5,6,10,14\}, |D\_1|=5$; $D_2=\{1,2,3,7,8,9,11,12,13\}, |D_2|=9$。 $D\_1$、$D\_2$ 数据自己对应的类别数分别为 $(+3,−2)、(+6,−3)$。因此 $Gini(D\_1) = 2 \cdot \frac{3}{5} \cdot \frac{2}{5} = \frac{12}{25}$；$Gini(D\_2) = 2 \cdot \frac{6}{9} \cdot \frac{3}{9} = \frac{4}{9}$。 对应的基尼指数为：

$Gini(C, “阴晴”=”rainy”) = \frac{5}{14} Gini(D_1) + \frac{9}{14} Gini(D_2) = \frac{5}{14} \frac{12}{25} + \frac{9}{14} \frac{4}{9} = \frac{4}{7} = 0.457 \quad(exp.2.2.3)$

如果特征”阴晴”是最优特征的话，那么特征取值为”overcast”应作为划分节点。

6. 决策树模型的优缺点

6.1 优点

• 可解释性–模拟人类决策过程
• 训练、预测效率较高–关于其切分方式，每次是在一个条件下的局部空间划分样本，而类似Adaboost则是每次在整个空间划分样本，所以就决策树而言相对高效
• 适用于类别类型数据–decision set(穷举类别特征值然后按照特征值的子集集合来划分样本)
• 能够很方便的由二分类模型转换为多分类模型–主要修改不纯度计算以及返回值的设置
• 能够处理缺失特征值–用其他的特征值来替代进行划分(一般要求替代特征划分结果接近缺失特征值)
• 易于实现

6.2 缺点

• 经验多于理论，大多数决策树模型是根据经验来判断的，效果好坏尚无较好的理论支撑

Reference article

• 逗比算法工程师、算法杂货铺
• 52caml、懒死骆驼
• 决策树ID3、C4.5、CART算法：信息熵，区别，剪枝理论总结
• Markdown 学习好教材、CART之回归树构建
• 《机器学习导论》《统计学习方法》

updated on：May 2, 2022

decision-tree