决策树是一个树结构(二叉树或非二叉树),每一个非叶子结点表示一个对特征属性的测试,每一个分支代表这个特征属性在某个值域上的输出,每个叶节点存放一个特定的类别。使用决策树进行决策的过程就是从根节点开始,测试待分类样本中对应的特征属性,并按照其值选择输出分支继续往下,直到到达叶子节点,将叶子节点存放的类别作为决策结果。

1. 决策树模型

  决策树模型的构建主要分三大部分,首先我们位于根节点处,需要做的是特征选择,选择出一个特征属性来创造分支,特征选择的依据一般会涉及几类指标(如信息增益,增益率和基尼系数),据此指标选择合适的特征,进而划分子树,迭代此过程完成决策树生成,然后对生成的决策树进行剪枝以提高其泛化能力。决策树的构造过程秉承着分而治之(divide-and-conquer)的原则,决定好划分属性后,将原树分成多个子树,再子树中继续同样的过程,直到遇到结束条件,即可生成决策树。

1.1 特征选择

  首先我们要解决的问题是如何选择哪一个特征的哪一个属性值在一个叶子节点处划分,常规做法就是遍历所有特征以特征中的所有取值,衡量按照这个特征的这个属性值划分子树是否是最佳的,衡量是否最佳的指标有三个:分别是信息增益、增益率和基尼系数。

1.1.1 信息增益 (Information Gain)

  信息熵是度量一个样本集合不纯度最常用的一个指标,假设当前样本集合 $D$ 中第 $k$ 类样本所占比例为 $p_k$($k=1, 2, \dots, |\mathcal { Y }|$),则当前样本集合 $D$ 的信息熵定义为:

信息熵 $Ent(D)$ 越大,说明不纯度越高,或者说不确定性越大。

  假设属性集为 $A$,如果此时我们用有 $V$ 个可能取值 ${a^1, a^2, \dots, a^V}$ 的离散属性 $a$ ($a\in A$) 来划分当前样本集合 $D$,能够得到 $V$ 个分支子树,每个分支子树 $D^v$ 都包含各自在属性 $a$ 上的同一取值 $a^v$(这里只是在 $X$ 方面的一致,label 的取值是不一定一样的)。根据上面信息熵的定义,我们可以计算出划分之后的每一个子树的信息熵 $Ent(D^v)$,然后通过对子树信息熵的加权求和得到划分后所有子树的整体信息熵(即所谓的条件熵):

  然后我们比较划分前后的信息熵变化:

  我们将划分前后的信息熵变化定义为信息增益 (Information Gain),信息增益越大,说明当前的划分越能够降低信息的不纯度,亦即越能够降低系统的不确定性,如此得到的决策树决策效果越好。于是我们就选择能够使得信息增益最大的属性进行划分,著名的 ID3 就是根据信息增益来进行划分属性的。

信息增益的优点:

  • 信息增益看起来比较直观而且计算量相对较少

信息增益的缺点:

  • 信息增益有一个比较严重的缺点是会非常倾向取值多的那一类特征
    • 原因:对于多值特征(极端情况下,unique id)这时候按照信息增益切分出来的各部分都是纯的,即熵最小是 0,$Ent(D, a)$ 也为 0,这种切分没有意义
    • 因为属性取值越多,$Ent(D, a) = -\sum_{v=1}^V { {\mid D^v\mid}\over {\mid D\mid}}\sum_{k=1}^{K} \frac{D_{v k}}{D_{v}} \log \frac{D_{v k}}{D_{v}}$,分数部分接近于零!
    • 举例:如果一个特征是消费者的信用卡号,在 IG 选择特征划分时肯定会选这个特征,因为此时 $Ent(D, a)$ 已经小到零了,即分完的结果纯度非常高(每一个分支只有一个样本),信息增益达到最大。

1.1.2 增益率(Gain Ratio)

  为了克服信息增益的劣势,后人就开始想是不是有这样一种抑制朝着多离散值的属性方向划分呢?我们可以设计一种衡量标准,当我们选怎离散值较多的属性的时候信息增益虽然最多,但是我们设计的这个衡量标准的值也会相应较大,这两个在一定程度上抵消。首先衡量一下划分之后子树划分信息量 (Split Information,也称 Intrinsic Value) 的概念:

  划分信息量可以衡量划分后数据的广度和均匀程度,划分后每个子树的数目越均匀,那么划分信息量就越大。因为信息增益在划分时会偏向类似 ID 型特征的趋势,所以我们如果取划分信息量的倒数,亦即将信息增益除以划分信息量就能起到抑制效果,这就是所谓的增益率 (Gain Ratio):

  那么,现在划分属性的依据是最大化增益率了,这也是 C4.5 采用的方式。

   信息增益比本质: 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时,惩罚参数较小;特征个数较少时,惩罚参数较大。

   要想增益率尽量大,那么划分信息量就得尽量小,亦即尽量选择分裂子树更少的方式。例如,划分方式一是将数据均匀划分成 $n$ 分,可计算得到划分信息量为 $\log_2 n$ ;划分方式二是将数据均匀分成两个部分,则划分信息量为 $1$;那么划分信息量会倾向选择能得到较小值的方案二,即子树数目小的。我们也可以通过对照对数函数在 $(0,1)$ 区间的趋势图,很明显距离 $1$ 的部分(即平均子树样本数较多的部分,也就是说划分子树较少时)函数结果较小,也就是更倾向选划分子树数目较少的方式!所以,增益率的弱点是有一点过分强调了找取值数目较少的属性。

增益率的优点

  • 解决了信息增益偏向类别多的特征做划分的问题

增益率的缺点

  • 信息增益率偏向取值比较少的特征
    • 为了避免仅仅因为划分信息量非常小就选择一个特征来进行划分,C4.5在根据增益率划分属性的时候一般采用一种启发式方法,即先计算每个属性的信息增益,然后仅对增益高过平均值的属性应用增益率进行测试。

1.1.3 基尼系数(Gini Index)

  之前两个衡量不纯度(不确定性)的标准是依赖信息熵,但是信息熵的计算有 $\log$ 运算,相对来说计算量较大,那么有没有一个没有那么复杂计算的衡量不纯度的方式呢?这就促生了基尼系数 (Gini Index)。我们说一个东西的纯度 (Purity) 高,一般指的是其中尽量只包含一种物质,例如纯金的纯度;相对的不纯度 (Impurity) 高说明里面的杂质多,在类别中的说法就是不同类的数目越多。那么,我们假设当前样本集合 $D$ 中第 $k$ 类样本所占比例为 $p_k$($k=1, 2, \dots, \vert\mathcal { Y }\vert$),那么我们连续抽取两个样本,这两个样本不属同一个类的概率如下:

  这就是基尼系数 (Gini Index, Gini Impurity),比较好理解的是,连续选取的两个样本不属于同一个类的概率越大,那么此批样本的不纯度就越高。所以,我们在划分属性的时候,选择能够使得基尼系数最小的属性。这里用数学推导说明了基尼系数和熵的关系。

  如果样本集合 $D$ 根据属性 $a$ 是否取某一可能值 $c$ 被划分成 $D_1$ 和 $D_2$ 两部分,即:

  则在特征 $a$ 的条件下,集合 $D$ 的基尼系数定义为:

基尼系数优点:

  • 基尼系数在计算上会快一些,因为没有求 $\log$ 运算。

  注意下基尼系数和信息熵的关系,信息熵在 x=1 处一阶泰勒展开就是基尼指数。

1.2 决策树的生成

  根据选择的节点分裂标准,从上至下递归地生成子节点,直到某个节点不满足分裂的标准,则停止决策树停止生长。不满足分裂的标准有如下几个:

  1. 当前结点包含的样本全都属于同一个类别,无法继续划分;(同一类了还分啥?)
  2. 当前的属性集为空,没有属性用来划分了;或者即使有属性可划分但是所有样本在所有属性上的衡量结果相同,无法进行划分了;
  3. 除了属性为空,当前结点包含的样本结合为空时,无法进一步划分。

  决策树生成都是贪心的,考虑下一层子树的最优,而不是考虑全局的最优。

1.3 剪枝处理(Pruning)

  生成好的决策树比较大的问题是容易过拟合,为了在一定程度上抑制这样的现象就提出了剪枝 (Pruning) 的操作,剪枝分为预剪枝和后剪枝两种。值得注意的是,不管是预剪枝还是后剪枝,都是在考虑泛化性能的提升与否,而不是信息熵。

  • ⁉️ 这里的泛化性能怎么验证?在一定的验证集上做验证?
  • ⁉️ 如果在损失函数那儿加上正则化呢?

1.3.1 预剪枝 (Pre-Pruning)

  在决策树的生成过程中,对每个结点在划分前先进行估计,若当前结点的划分不能带来泛化性能上的提升,则停止划分并将当前结点标记为叶节点。

  对比未剪枝的决策树和经过预剪枝的决策树可以看出:预剪枝使得决策树的很多分支都没有“展开”,这不仅降低了过拟合的风险,还显著减少了决策树的训练时间开销和测试时间开销。但是,另一方面,因为预剪枝是基于“贪心”的,所以,虽然当前划分不能提升泛化性能,但是基于该划分的后续划分却有可能导致性能提升,因此预剪枝决策树有可能带来欠拟合的风险。

  预剪枝方法:

  1. 当决策树达到一定的高度就停止决策树的生长;
  2. 到达此节点的实例具有相同的特征向量,而不必一定属于同一类,也可以停止生长;
  3. 到达此节点的实例个数小于某个阈值的时候也可以停止树的生长,不足之处是不能处理那些数据量比较小的特殊情况;
  4. 计算每次扩展对系统性能的增益,如果小于某个阈值就可以让它停止生长。

预剪枝优点

  • 在一定程度上降低了过拟合的风险
  • 显著减少了决策树训练时间开销和测试时间开销

预剪枝缺点

  • 当前划分可能没有提升,后续的划分有可能提升较大,预剪枝没有办法改善这样的情况,所以预剪枝可能会过早停止决策树的生长,致使有欠拟合的风险。

1.3.2 后剪枝 (Post-Pruning)

  先从训练集生成完整的决策树,然后自底向上地对每一个非叶子结点进行考察,如果将该结点的子树改成叶结点能够提高决策树的性能,那么就将当前结点的子树改成对应的叶结点。

  后剪枝决策树通常比预剪枝决策树保留了更多的分支,一般情形下,后剪枝决策树的欠拟合风险小,泛化性能往往也要优于预剪枝决策树。但后剪枝过程是在构建完全决策树之后进行的,并且要自底向上的对树中的所有非叶结点进行逐一考察,因此其训练时间开销要比未剪枝决策树和预剪枝决策树都大得多。

  后剪枝方法又分为两种,一类是把训练数据集分成树的生长集和剪枝集;另一类算法则是使用同一数据集进行决策树生长和剪枝。后剪枝算法有很多种:

前剪枝和后剪枝的比较:

  1. 前剪枝阈值的设定很敏感,一点点的变动,会引起整颗树非常大的变动,不好设定。
  2. 前剪枝生成比后剪枝简洁的树
  3. 一般用后剪得到的结果比较好

2. 决策树实践

  在决策树实践时需要考虑两个大问题,一是在划分子树时离散的特征比较好处理,对于连续值特征的处理需要做一番思考,第二个是对于数据缺失的情况做什么样的处理。

2.1 连续值处理

  对于离散的标称型数据来说,特征值是离散有限的,但是对于连续特征来说,其连续值就不一定是有限的了,我们需要进行连续属性离散化。最简单的而且也正是 C4.5 中采用的方法叫做二分法(bi-partition)。

  假设给定样本集 $D$ 和连续属性 $a$,$a$ 在样本 $D$ 上有 $n$ 个不同的取值,将这 $n$ 个不同的值按照从小到大的顺序排好,记为 ${a^1, a^2, \dots, a^n}$。那么,基于一个划分点 $t$,我们可以将样本分成 $D^-$ 和 $D^+$ 的两个部分。在相邻的两个取值 ${a^i, a^{i+1}}$ 上,我们知道 $t$ 无论取区间 $[a^i, a^{i+1})$ 的任何一个值,划分结果都不变,因为虽然属性是连续型属性,但是其在训练样本中所有的取值目前是已知的了。可能在测试集中会有取值有不一样的情况,但是也是始终逃不出大小关系的,所以不用担心像标称型属性那样测试集出现训练集中没有的属性取值的苦恼了。

  对于连续属性 $a$,我们采取两个相邻取值的中位数 ${a^i+a^{i+1}}\over 2$ 来做一个划分点,这样可以得到 $n-1$ 个候选划分点集合:

  然后遍历 $T_a$ 找到能够使得在评判标准下得到最好效果的那个划分点:

2.2 缺失值处理

  对于输出出现缺失值的情况,一般来说有两个问题需要考虑:

  1. 如何在划分属性值缺失的情况下进行划分属性选择?(比如”色泽”这个属性作为划分属性时,有的样本在其上面取值缺失时,要该如何计算信息增益?)
  2. 已经选好划分属性,但某样本在该属性上值缺失,该如何对样本进行划分?(该将这个样本划分到哪个类?)

  当然,我们要明确一点,缺失值是针对样本的某个属性值来说的。简单处理方法有:

  • 舍弃缺失值
  • 填充缺失值

  接下来分别对几个缺失值的问题展开讨论。

2.2.1 问题一:有属性值缺失,如何选哪个做划分属性?

  这个是在选择划分属性时需要面临的问题,我们要判断是否将这个属性作为划分属性,按照之前的流程我们需要计算其信息增益,但是有的样本在这个属性上取值是缺失的,那么我在计算信息增益时该如何处理这些样本的缺失值呢?这里我们看一种只考虑无缺失值的方法。

  像 CART 算法就采用一种基于无缺失值样本来计算信息增益的方式,首先给定训练集 $D$ 和属性 $a$,然后定义在属性 $a$ 上无缺失值的样本子集为 $\tilde { D }$。$\tilde { D } ^ { v }$ 表示 $\tilde { D }$ 中在属性 $a$ 上取值为 $a ^ { v }$ 的样本子集;$\tilde { D } _ { k }$ 表示 $\tilde { D }$ 中属于第 $k$ 类($ k=1, 2, \dots,\mid\mathcal{Y} \mid $)的样本子集。

  我们需要知道信息增益,那么将其分成两个部分,第一个是对已知值(即无缺失值的部分)所带来的信息增益;第二部分是对未知值(即缺失值)带来的信息增益,通过加权平均的方式综合起来。而一个明显的事实是,对于未知值而言我们的能获得的信息量是零,于是我们有下面的式子:

  假定我们为每个样本 $x$ 赋予一个权重 $w_x$,那么上面的式子中 $\rho$ 表示无缺失值样本占所有样本的比例:

  $\tilde { r } _ { v }$ 表示无缺失值的样本在属性 $a$ 上取值为 $a^v$ 的样本占无缺失值样本子集的比例:

  据此可以计算出无缺失值样本子集的信息熵为:

  其中 $\tilde { p } _ { k }$ 表示无缺失值样本中第 $k$ 类样本所占的百分比:

  所以,当样本在划分属性上缺失时,我们就用上面的 $\operatorname { gain } ( D, a )$ 来计算信息增益,进而选择对应的划分属性。值得注意的是,这里在处理缺失值的时候假设了每个样本都有一个权值,在学习开始初期这些权重初始化为 1。设置每个样本都有权重的好处或许是使得算法更灵活一些,对 imbalance 问题处理得更好,但是一个问题是要如何去更新每个参数的权重?⁉️

2.2.2 问题二:样本在划分属性上缺失,如何划分该样本?

  若样本 $x$ 在划分属性 $a$ 上的取值未知,则将 $x$ 同时划入所有子结点,且样本的权值在属性值为 $a^v$ 对应的子结点上调整为 $\tilde{r} \cdot w_x$。我们知道 $\sum _ { k = 1 } ^ { | \mathcal { Y } | } \tilde { p } _ { k } = 1$,$\sum _ { v = 1 } ^ { V } \tilde { r } _ { v } = 1$,可见这里是将原来这单个样本的权值按照不同的概率分拆成了多份划分到对应的子结点中去了。这样很好理解,因为没有足够多的信息,我们不知道要如何划分该样本,每个子结点都有可能接收这个样本,但是子结点接收的概率是不同的,那么我们就将该单个样本的信息按照相应的概率分给各个子结点。

2.2.3 问题三:模型训练好,但测试时出现缺失值?

  这时候,就不能按比例分配了,因为你必须给该样本一个确定的 label,而不是薛定谔的 label。若此样本的属性 $A$ 的值未知,这时候可以采用以下两种方式:

  1. 待分类样本在到达属性 $A$ 的分支结点时即可结束分类过程,此样本所属类别为属性 $A$ 的子树中概率最大的类别 (看子树对应的叶子节点的类别,计算概率);
  2. 或者把待分类样本的属性 $A$ 赋予一个最常见的值,然后继续分类过程。

2.3 测试遇到没有见过的类别

  有见到类似的讨论,一般工程实现上看自己意愿,可以像处理缺失值那样操作,但像 SKLearn 这样的包是直接报错的;从机器学习或者数据角度上来看这个问题,如果没有特定假设,这个问题是无解的。如果我们假设没有见过的或者未知的值是平均值的,那么就可以在划分时,两个子树都走,然后就看那个子树样本多就归到那一类。

总结

  决策树是分类和回归模型中非常常用的模型,在此基础上发展出来的 XGBoost 等甚至是竞赛实战中的必备。

决策树优点

  1. 简单直观,输出的结果易于理解。
  2. 对于数据基本上不需要预处理、归一化和缺失值处理(对缺失值不敏感)。
  3. 计算复杂度不高,决策树预测的代价是 $O(\log_2m)$。 $m$ 为样本数。
  4. 既可以处理离散值,也可以处理连续值。
  5. 可以处理多维度输出的分类问题。
  6. 可以交叉验证的剪枝来选择模型,从而提高泛化能力。
  7. 对于异常点的容错能力好,健壮性高。
  8. 可以处理不相关特征数据。

决策树缺点

  1. 决策树算法非常容易过拟合,导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
  2. 对异常值(Outlier)过于敏感,决策树会因为样本发生一点点的改动,就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
  3. 寻找最优的决策树是一个 NP 难的问题,我们一般是通过启发式方法,容易陷入局部最优。可以通过集成学习之类的方法来改善。
  4. 在处理特征关联性比较强的数据时表现得不是太好。有些比较复杂的关系,决策树很难学习,比如异或。这个就没有办法了,一般这种关系可以换神经网络分类方法来解决。
  5. 如果某些特征的样本比例过大,生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。
  6. 对连续性的字段比较难预测,需要特殊处理。

待解决问题

  代码实现算法的时候,首先第一步需要将每一步要做什么细节的用伪代码的形式写下来才能比较好的进行 Code。

  1. 模型的起点,如何更新,结束条件有哪些
  2. 如何预测
    • 如何计算
  3. 返回什么东西??

⁉️ 自己实现的 Decision Tree 为什么不稳定?

  • 可以对照着参考的算法,一步一步调试找问题……

代码实现

# Check if expansion of y is needed
        if len(np.shape(y)) == 1:
            y = np.expand_dims(y, axis=1)

为什么要拓展y的维度?因为有的 y 是 onehot 编码过的。

设定 min_samples_split(最小的划分样本),即如果还剩下大于等于这个数字的样本数,那么继续划分。类似的,设定max_depth,防止决策树划分太深;还要设定min_impurity(最小的不纯度),要超过这个最小不纯度,就继续划分。

代码实现问题 1、按照开源的代码实现的结果是,准确率一直不太稳定,偏差太大。

预测的做法

  也是要遍历地从根节点一直往下延伸到具体的叶节点上,返回的值是叶节点的value。

⁉️ 预测样本出现了,有的类在训练数据集的特征中不存在的情况要怎么处理?

  • 那就预测不出来啊

决策树的参数是什么?在实现的时候以什么形式存下来?

References

  1. Complete Guide to Parameter Tuning in XGBoost (with codes in Python)
  2. Page 11 - BASIC CONCEPTS IN INFORMATION THEORY
  3. Intuitive explanation of entropy
  4. 决策树算法原理
  5. A Complete Tutorial on Tree Based Modeling from Scratch (in R & Python)
  6. 决策树—回归
  7. SKlearn Decision Tree
  8. efficient-decision-tree-notes