决策树

1 基本流程

一颗决策树要包括一个根结点，若干个内部结点和若干个叶结点。

• 叶结点对应决策结果，其他每个结点对应于一个属性测试
• 每个结点包含的样本集合根据属性测试的结果被划分到子结点中
• 根结点包含样本全集。
• 从根结点到每个叶结点之间的路径对应了一个判定测试序列。

决策树的目的：产生一颗泛化能力强，即处理未见示例能力强的决策树。

基本流程：分而治之的思想

• 数据集D={(x1,y1),…,(xn,yn)}D=\{(x_1,y_1),…,(x_n,y_n)\}D={(x1​,y1​),…,(xn​,yn​)}，其中$x_i$表示一个n维的变量（自变量），$y_i$表示标签（多类别分类问题中，某一个类别）

• 属性集A={a1,a2,…,an}A=\{a_1,a_2,…,a_n\}A={a1​,a2​,…,an​}，一个n维的向量，表示n个决策变量，与$x$的维度一致

• 过程：函数TreeGenerate(D, A)

  生成结点Node;
  if D中的样本全属于同一个类别C:     //D中的样本，不管x是多少，其y值（标签）均为C
  	node标记为C类叶结点
  	return   (1)
  if A==None or D中的样本在A上的取值相同:
  	node标记为叶结点，其类别标记为D中样本数最多的类别   //指D中所有样本呢在属性上均一致，比如“都是已婚”，“都是18岁”
  												 //则将node标记为D中所有数据的y值，频数最大的，比如大部分数据											 		 //都是E类，则将node标记为E类
  	return   (2)
  
  从A中选取最优划分属性a*,遍历a*中的每个值
  for a*的每一个值a*':
  	为node生成一个分支node*；令Dv表示D中在a*上取值为a*'的样本子集
  	if Dv == None:  //即不需要为a*'再开辟新的子结点了,没有这类数据
  		将分支结点node*标记为叶结点,其类别为D中样本数最多的类别
  		return  (3)
  	else:
  		TreeGenerate(Dv, A\{a*})   //开辟新的分支结点
  

  注意：三个return表示：

  （1）：当前接待你包含的样本属于同一个类别，无需再划分

  （2）：当前属性集为空，或者所有样本在属性上取值相同，无法划分。利用当前结点的后验分布

  （3）：当前结点包含的样本集合为空，不能划分。利用父节点的先验分布

2 划分选择

决策树的关键在于：选取最优划分属性a*。一般而言，我们希望随着决策树的划分过程，决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度越来越高。

2.1 信息增益

信息熵（information entropy）：度量样本纯度。假定当前样本集合D中第$k$类样本的比例为$p_k$，一共有$Y$个类别，则信息熵定义为：
$$Ent(D)=-\sum _{k=1}^{|Y|}{p}_{k}lo{g}_2{p}_k$$
信息熵$\mathbf{E}\mathbf{n}\mathbf{t}(\mathbf{D})$的值越小，D的纯度越高。个人理解，可以把信息熵理解成信息的混乱程度，混乱程度越大，说明纯度低；反之，纯度高我们希望得到混乱程度越来越小的决策树。例如，(0.1,0.9)的分布比(0.2,0.8)的分布纯度更高，反映在信息熵中前者的信息熵更小

信息增益：假设离散属性$a$有$V$个可能的取值{a1,a2,…,aV}\{a^1,a^2,…,a^V\}{a1,a2,…,aV}。若使用$a$来对样本集D进行划分，得到$V$个分支结点，第$v$个分支中包含D中所有在$a=a^v$的样本$D^v$，其信息熵为$Ent(D^v)$。考虑到不同分支结点的样本数不同，给分支结点权重$|D^v|/|D|$，即该结点样本数占总样本数的比例。信息增益（information gain）为：
$$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$
可以将信息增益理解为分支前和分支后的混乱程度的差值，差值越大，可以说明选用属性$a$对划分的”纯度提升“越大，分支效果越好。

ID-3决策树算法采用信息增益为准则来划分属性。选用属性准则：
$$a_{\ast }={\mathrm{argmax}}_{a\in A}Gain(D,a)$$

2.2 增益率

实际上，信息增益准则对可取值数目较多的属性有所偏好，为了减少这种偏好可能带来的不利影响，C4.5算法采用”增益率“来选择最优划分属性：
$$\begin{gathered} Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)} \\ IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}lo{g}_2\frac{|D^v|}{|D|} \end{gathered}$$
$IV(a)$为属性的固有值，表示属性的可能取值越多，其$IV(a)$值越大。增益率准则可以对可取值数目较少的属性有所偏好。C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用启发式：先从候选划分属性中找出信息增益高出平均水平的属性，再从中选择增益率最高的。

2.3 基尼指数

CART决策树采用”基尼指数“衡量数据集D的纯度：
$$Gini(D)=\sum _{k=1}^{|Y|}\sum _{k^{\prime }\ne k}{p}_k{p}_{k^{\prime }}=1-\sum _{k=1}^Y{p}_k^2$$
基尼指数表示从数据集D中随机抽取两个样本，其类别标记不一致的的概率。因此，概率越小，即基尼指数越小，D纯度越高。

属性$a$的基尼指数定义为：
$$Gini\_index(D,a)=\sum _{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$$
选用准则：
$$a_{\ast }={\mathrm{argmin}}_{a\in A}Gini\_index(D,a)$$

3 剪枝处理

剪枝（Pruning）是决策树学习算法应对”过拟合“的手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时造成决策树分支过多（学的太好了），以致于把训练集自身的一些特点作为所有数据都具有的一般性质而导致过拟合。

剪枝的基本策略包括：预剪枝(prepruning)和后剪枝(post-pruning)。

• 预剪枝：在决策树生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将该节点标记为叶结点
• 后剪枝：先从训练集生成一颗完整的决策树，然后自底向上对非叶节点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。

通过对预剪枝和后剪枝的概念进行解释，我们可以发现，剪枝的关键在于如何判断决策树的泛化性能是否提升？

3.1 预剪枝

流程：

• 将数据集划分为训练集和测试集。

• 用训练集训练出一颗决策树，如下：

• 以根节点为例展开：

  • 如果不划分，则以所有数据集中类别数量最多的作为该结点分类结果，即”好瓜“（其实坏瓜也行，因为好瓜坏瓜各5个）

    在测试集中，{4，5，8}成功分类至好瓜，其他的个未能分类成功，所有准确率为42.9%

  • 如果划分，则按照图中结果，测试集{4，5，8，11，12}成功分类，准确率为71.4%，有所提升，所以要选取”脐部“划分。

• 以②为例：根据信息增益准则选取属性”色泽“，发现准确率下降，因此禁止划分。其他同理。

评价：

• 优点：使得决策树的很多分支都没有展开，不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。
• 缺点：有些分支的当前划分虽然不能提升泛化性能，甚至导致泛化性能下降，但在其基础上进行的后续划分可能导致性能显著提升。预剪枝基于贪心的思想，本质上禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险

3.2 后剪枝

流程：

• 先根据训练集训练出一个完整的决策树，可以求得该决策树的验证集精度为42.9%

• 自底向上，首先考虑结点⑥：将⑥领先的分支剪除，即把⑥换为叶结点，其类别对应包含的其数据集{7，15}样本中类别占比最大的类别，这里可以选为”好瓜“，决策树在测试集上的精度提高到57.1%。所以决定剪枝。

• 继续考虑结点⑤，精度不变，可以不剪枝。

• 继续考虑结点②，精度提升到71.4%，决定剪枝

• 考虑③和①，精度均未提升，因此保留，不进行剪枝

• 最终得到后剪枝决策树：

评价：

• 优点：可以看出，后剪枝决策树比预剪枝决策树保留了更多的分支。一般情况中，后剪枝决策树欠拟合的风险比较小，泛化性能也往往优于预剪枝决策树。
• 缺点：后剪枝过程是完整生成决策树之后再进行的，并且要自底向上，对所有非叶节点注意观察，训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

4 连续和缺失值

4.1 连续值处理

由于连续属性的可取值数目不再是有限的，因此可以采用连续属性离散化技术。

C4.5决策树中采用二分法：

• 给定样本集$D$和连续属性$a$，假定$a$在$D$上出现了$n$个不同的取值，将这些值从小到大进行排序{a1,a2,…,an}\{a_1,a_2,…,a_n\}{a1​,a2​,…,an​}

• 基于划分点$t$，将$D$分成$D_t^{-}$和$D_t^{+}$。$t$的集合（相当于依次在$a^i$和$a^{i+1}$直接取中值）：
  Ta={ai+ai+12∣i≤i≤n−1} T_a=\{\frac{a^i+a^{i+1}}{2}|i\le i \le n-1\} Ta​={2ai+ai+1​∣i≤i≤n−1}

• 信息增益公式改为：
  Gain(D,a,t)=max⁡t∈Ta Ent(D)−∑λ∈{−,+}∣Dtλ∣∣D∣Ent(Dtλ) Gain(D,a,t)=\mathop{\max}_{t\in T_a}\space Ent(D)-\sum_{\lambda \in \{-,+\}}\frac{|D^\lambda_t|}{|D|}Ent(D^\lambda_t) Gain(D,a,t)=maxt∈Ta​​ Ent(D)−λ∈{−,+}∑​∣D∣∣Dtλ​∣​Ent(Dtλ​)

• 算出各个属性$a$的信息增益以及对应的划分点$t$，分支按照$\le t$和$\ge t$，划分为两类。

4.2 缺失值处理

现实当中，我们面对的数据集往往出现一些缺失值属性（出于隐私保护等原因）。如果简单地放弃不完整样本，仅使用无缺失值的样本进行学习，显然是对数据信息极大的浪费。

对缺失值的处理，我们需要先考虑两个问题：

（1）如何在属性值缺失的情况下进行划分属性选择？

（2）给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

问题一解决方法：

• 给定的数据集$D$和属性$a$，令$\tilde{D}$表示$D$在属性$a$上没有缺失值的样本子集，用$\tilde{D}$来衡量问题一中的属性选择。

• 假定$a$有$V$个可选取值，令${\tilde{D}}^v$表示$\tilde{D}$中在属性$a$上取值为$a^v$的样本子集，是${\tilde{D}}^k$表示$\tilde{D}$中属于第$k$类的样本子集

  显然有$\tilde{D}={\bigcup }_{k=1}^Y{\tilde{D}}_k,\tilde{D}={\bigcup }_{v=1}^V{\tilde{D}}^v$

• 假定我们为每一个样本$x$赋予一个权重$w_x$，并定义
  $$\begin{gathered} \rho =\frac{{\sum }_{x\in \tilde{D}}{w}_x}{{\sum }_{x\in D}{w}_x}, \\ {\tilde{p}}_k=\frac{{\sum }_{x\in {\tilde{D}}_k}{w}_x}{{\sum }_{x\in \tilde{D}}{w}_x}(1\le k\le |Y|), \\ {\tilde{r}}_v=\frac{{\sum }_{x\in {\tilde{D}}^v}{w}_x}{{\sum }_{x\in \tilde{D}}{w}_x}(1\le v\le V) \end{gathered}$$
  可以看出，$\rho$是无缺失样本的比例；${\tilde{p}}_k$表示无缺失样本中第$k$类的比例，${\tilde{r}}_v$表示无缺失样本中在属性$a$上取值为$a^v$的比例

• 将信息增益的公式推广至：
  $$\begin{gathered} Gain(D,a)=\rho \times Gain(\tilde{D},a)=\rho \times (Ent(\tilde{D})-\sum _{v=1}^V{\tilde{r}}_{v}Ent({\tilde{D}}^v)) \\ Ent(\tilde{D})=-\sum _{k=1}^{|Y|}{\tilde{p}}_{k}lo{g}_2{\tilde{\rho }}_k \end{gathered}$$

问题二解决方法：

• 若样本在属性$a$中的取值已知，则划入到对应的子节点，权重$w_x$不变
• 若样本在属性$a$中的取值未知，则划入到所有子结点，在每个子结点处权重调整为${\tilde{r}}_v\times w_x$。可以理解成，将样本以不同的概率划入到不同的子结点。

5 多变量决策树

若我们把每个属性视为坐标空间中的一个坐标轴，则$d$个属性描述的样本就对应了$d$维空间中的一个数据点。对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。
决策树所形成的分类边界有一个明显的特点：轴平行(axis-parallel)，即它的分类边界由若千个与坐标轴平行的分段组成。如下图

多变量决策树：能实现”斜划分“甚至更复杂划分的决策树，如下图

• 斜划分：非叶节点不再只对单个属性进行划分，而是对属性的线性组合进行测试${\sum }_{i=1}^d{w}_i{a}_i=t$，其中$w_i$和$t$可以再样本集和属性集上学习到。这个方法与传统的决策树不同，不再为每个非叶结点找到一个最优划分属性，而是试图建立一个合适的线性分类器。
• 代表决策树：OC1决策树

4.6 增量学习

部分决策树算法可以进行”增量学习“，如ID4、ID5R、ITI等。增量学习即在接收到新样本后可以对已学习的模型进行调整，不用完全重新学习，主要机制是调整分支路径上的划分属性次序来对树进行部分重构。