决策树

4/14/2021 决策树

# 谈谈你对熵、信息增益和信息增益比的理解?

  • 什么是熵?

首先要理解熵:熵是对不确定性的度量,熵越大,随机变量的不确定性就越大。对同一个随机变量,当他的概率分布为均匀分布时,不确定性最大,熵也最大。对有相同概率分布的不同的随机变量,取值越多的随机变量熵越大。

熵的计算公式: 条件熵的计算公式:

  • 什么是信息增益?

熵H(X)度量了X的不确定性,条件熵H(X|Y)度量了我们在知道Y以后X剩下的不确定性,那么H(X)-H(X|Y)度量了X在知道Y以后不确定性减少程度,在信息论中称为互信息,记为I(X,Y),在决策树ID3算法中叫做信息增益。ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大,则越适合用来分类。

  • 什么是信息增益比?

信息增益比计算公式:

这里是特征熵,特征越多对应的特征熵越大,它作为分母,可以校正信息增益容易偏向取值较多的特征的问题。

# ID3算法的划分标准是什么?

ID3 使用的分类标准是信息增益,它表示得知特征 A 的信息而使得样本集合不确定性减少的程度。

数据集的信息熵:

其中表示集合D中属于第k类样本的样本子集。

针对某个特征A,对于数据集D的条件熵为:

其中表示中特征A取第i个值得的样本子集,表示中属于第k类的样本子集。

信息增益=信息熵-条件熵:

信息增益越大表示使用特征 A 来划分所获得的“纯度提升越大”。

# ID3算法有什么缺陷?C4.5算法是如何解决ID3的缺陷的?ID3和C4.5存在什么缺陷?

ID3的缺陷

  • ID3没有考虑连续特征,比如长度,密度都是连续值,无法在ID3运用。这大大限制了ID3的用途。
  • 信息增益准则对可取值数目较多的特征有所偏好,类似“编号”的特征其信息增益接近于 1;
  • ID3 没有剪枝策略,容易过拟合
  • 没有考虑过拟合的问题

C4.5的解决方案

  • 引入了信息增益比,平衡了信息增益容易偏向于取值较多特征的问题
  • 引入悲观剪枝策略进行后剪枝;
  • 对于连续特征,将连续特征离散化,假设 n 个样本的连续特征 A 有 m 个取值,C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点,分别计算以该划分点作为二元分类点时的信息增益,并选择信息增益最大的点作为该连续特征的二元离散分类点;

ID3和C4.5的缺陷

  • 容易过拟合
  • 生成多叉树,不利于计算机计算
  • 大量对数运算以及排序算法,对cpu不友好

# C4.5是如何处理缺失值的?

C4.5对于缺失值的处理可以分为两个子问题:

  1. 在特征值缺失的情况下进行划分特征的选择?即如何计算特征的信息增益率

对于具有缺失值特征,用没有缺失的样本子集所占比重来折算;

  1. 选定该划分特征,对于缺失该特征值的样本如何处理?即到底把这个样本划分到哪个结点里

将样本同时划分到所有子节点,不过要调整样本的权重值,其实也就是以不同概率划分到不同节点中。

# C4.5的划分标准是什么?

利用信息增益比可以克服信息增益的缺点,其公式为:

这里是特征熵,特征越多对应的特征熵越大,它作为分母,可以校正信息增益容易偏向取值较多的特征的问题。

这里需要注意,信息增益率对可取值较少的特征有所偏好(分母越小,整体越大),因此 C4.5 并不是直接用增益率最大的特征进行划分,而是使用一个启发式方法:先从候选划分特征中找到信息增益高于平均值的特征,再从中选择增益率最高的。

# C4.5算法的缺陷是什么?

  1. C4.5 用的是多叉树,用二叉树效率更高;
  2. C4.5 只能用于分类;
  3. C4.5 使用的熵模型拥有大量耗时的对数运算,连续值还有排序运算;
  4. C4.5 在构造树的过程中,对数值属性值需要按照其大小进行排序,从中选择一个分割点,所以只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时,程序无法运行。

# 基尼系数的的定义及其优势是什么?

熵模型拥有大量耗时的对数运算,基尼指数在简化模型的同时还保留了熵模型的优点。

基尼系数

代表了模型的不纯度,基尼系数越小,不纯度越低,特征越好。这和信息增益(率)正好相反。

基尼系数的优点:在保证准确率的情况下大大减小了计算量。

基尼指数反映了从数据集中随机抽取两个样本,其类别标记不一致的概率。因此基尼指数越小,则数据集纯度越高。基尼指数偏向于特征值较多的特征,类似信息增益。基尼指数可以用来度量任何不均匀分布,是介于 0~1 之间的数,0是完全相等,1是完全不相等,

# CART是如何在特征值缺失的情况下进行划分特征的选择?

CART 一开始严格要求分裂特征评估时只能使用在该特征上没有缺失值的那部分数据,在后续版本中,CART 算法使用了一种惩罚机制来抑制提升值,从而反映出缺失值的影响(例如,如果一个特征在节点的 20% 的记录是缺失的,那么这个特征就会减少 20% 或者其他数值)。

# 选定该划分特征,CART模型对于缺失该特征值的样本该进行怎样处理?

CART 算法的机制是为树的每个节点都找到代理分裂器,无论在训练数据上得到的树是否有缺失值都会这样做。在代理分裂器中,特征的分值必须超过默认规则的性能才有资格作为代理(即代理就是代替缺失值特征作为划分特征的特征),当 CART 树中遇到缺失值时,这个实例划分到左边还是右边是决定于其排名最高的代理,如果这个代理的值也缺失了,那么就使用排名第二的代理,以此类推,如果所有代理值都缺失,那么默认规则就是把样本划分到较大的那个子节点。代理分裂器可以确保无缺失训练数据上得到的树可以用来处理包含确实值的新数据。

# 决策树出现过拟合的原因及其解决办法?

对训练数据预测效果很好,但是测试数据预测效果较差的现象称为过拟合。

原因:

  • 在决策树构建的过程中,对决策树的生长没有进行合理的限制(剪枝);
  • 样本中有一些噪声数据,没有对噪声数据进行有效的剔除;
  • 在构建决策树过程中使用了较多的输出变量,变量较多也容易产生过拟合

解决办法

  • 选择合理的参数进行剪枝,可以分为预剪枝和后剪枝,我们一般采用后剪枝的方法;
  • 利用K−folds交叉验证,将训练集分为K份,然后进行K次交叉验证,每次使用K−1份作为训练样本数据集,另外一份作为测试集;
  • 减少特征,计算每一个特征和响应变量的相关性,常见得为皮尔逊相关系数,将相关性较小的变量剔除;当然还有一些其他的方法来进行特征筛选,比如基于决策树的特征筛选,通过正则化的方式来进行特征选取等(决策的正则化)。

# 决策树剪枝有哪些策略?其优缺点分别是什么?

剪枝是防止决策树过拟合的方法。一棵完全生长的决策树很可能失去泛化能力,因此需要剪枝。

  • 剪枝的策略

剪枝分为预剪枝和后剪枝两种,预剪枝是在构建决策树时抑制它的生长,后剪枝是决策树生长完全后再对叶子节点进行修剪。

  • 预剪枝
  1. 设置一个树的最大高度/深度或者为树设置一个最大节点数,达到这个值即停止生长
  2. 对每个叶子节点的样本数设置最小值,生长时叶子节点样本数不能小于这个值
  3. 节点划分前准确率比划分后准确率高。

预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间,但另一方面它是基于“贪心”策略,会带来欠拟合风险。

  • 后剪枝

后剪枝方法是对一棵已经完全生长的决策树进行剪枝

  1. 错误率降低剪枝(Reduced-Error Pruning)
  2. 悲观剪枝(Pessimistic Error Pruning)
  3. 代价复杂度剪枝(Cost-Complexity Pruning)

后剪枝决策树的欠拟合风险很小,泛化性能往往优于预剪枝决策树。但同时其训练时间会大的多。

  • 预剪枝和后剪枝的优缺点比较

时间成本方面,预剪枝在训练过程中即进行剪枝,后剪枝要在决策树完全生长后自底向上逐一考察。显然,后剪枝训练时间更长。预剪枝更适合解决大规模问题。

剪枝的效果上,预剪枝的常用方法本质上是基于贪心的思想,但贪心法却可能导致欠拟合,后剪枝的欠拟合风险很小,泛化性能更高。

另外,预剪枝的有些方法使用了阈值,如何设置一个合理的阈值也是一项挑战。

# C4.5采用的剪枝方法是什么?

C4.5 采用的悲观剪枝方法,用递归的方式从低往上针对每一个非叶子节点,评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降,则这棵子树就可以被替换掉。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。

# CART是如何处理类别不平衡问题的?

CART 的一大优势在于:无论训练数据集有多失衡,它都可以将其自动消除,而不需要建模人员采取其他操作。

CART 使用了一种先验机制,其作用相当于对类别进行加权。这种先验机制嵌入于 CART 算法判断分裂优劣的运算里,在 CART 默认的分类模式中,总是要计算每个节点关于根节点的类别频率的比值,这就相当于对数据自动重加权,对类别进行均衡。

对于一个二分类问题,节点 node 被分成类别 1 当且仅当:

比如二分类,根节点属于 1 类和 0 类的分别有 20 和 80 个。在子节点上有 30 个样本,其中属于 1 类和 0 类的分别是 10 和 20 个。如果 10/20>20/80,该节点就属于 1 类。

通过这种计算方式就无需管理数据真实的类别分布。假设有 K 个目标类别,就可以确保根节点中每个类别的概率都是 1/K。这种默认的模式被称为“先验相等”。先验设置和加权不同之处在于先验不影响每个节点中的各类别样本的数量或者份额。先验影响的是每个节点的类别赋值和树生长过程中分裂的选择。

# CART是如何对连续值处理的?

对于连续值的处理,CART分类树采用基尼系数的大小来度量特征的各个划分点。在回归模型中,我们使用常见的和方差度量方式,对于任意划分特征 A,对应的任意划分点 s 两边划分成的数据集,求出使各自集合的均方差最小,同时的均方差之和最小所对应的特征和特征值划分点。表达式为:

其中,数据集得到样本输出均值,数据集的样本输出均值。

# 请你说一下ID3、C4.5和CART三者之间的差异。

  • 划分标准的差异:ID3 使用信息增益偏向特征值多的特征,C4.5 使用信息增益率克服信息增益的缺点,偏向于特征值小的特征,CART 使用基尼指数克服 C4.5 需要求 log 的巨大计算量,偏向于特征值较多的特征。
  • 使用场景的差异:ID3 和 C4.5 都只能用于分类问题,CART 可以用于分类和回归问题;ID3 和 C4.5 是多叉树,速度较慢,CART 是二叉树,计算速度很快;
  • 样本数据的差异:ID3 只能处理离散数据且缺失值敏感,C4.5 和 CART 可以处理连续性数据且有多种方式处理缺失值;从样本量考虑的话,小样本建议 C4.5、大样本建议 CART。C4.5 处理过程中需对数据集进行多次扫描排序,处理成本耗时较高,而 CART 本身是一种大样本的统计方法,小样本处理下泛化误差较大 ;
  • 样本特征的差异:ID3 和 C4.5 层级之间只使用一次特征,CART 可多次重复使用特征;
  • 剪枝策略的差异:ID3 没有剪枝策略,C4.5 是通过悲观剪枝策略来修正树的准确性,而 CART 是通过代价复杂度剪枝。

# CART算法为什么选用gini指数?

处进行一阶泰勒展开为

所以:

基尼系数可以理解为熵的一阶泰勒展开,如下所示:

# C4.5算法是如何处理连续值的?

对于连续特征,将连续特征离散化,假设 n 个样本的连续特征 A 有 m 个取值,C4.5将其排序并取相邻两样本值的平均数共 m-1 个划分点,分别计算以该划分点作为二元分类点时的信息增益,并选择信息增益最大的点作为该连续特征的二元离散分类点;

有一点需要注意的是:与离散属性不同,若当前结点划分属性为连续属性,该属性还可作为其后代结点的划分属性。

# 决策树是如何处理缺失值的?

缺失值问题可以从三个方面来考虑

  • 在选择分裂属性的时候,训练样本存在缺失值,如何处理?

假如你使用ID3算法,那么选择分类属性时,就要计算所有属性的熵增(信息增益,Gain)。假设10个样本,属性是a,b,c。在计算a属性熵时发现,第10个样本的a属性缺失,那么就把第10个样本去掉,前9个样本组成新的样本集,在新样本集上按正常方法计算a属性的熵增。然后结果乘0.9(新样本占raw样本的比例),就是a属性最终的熵。

  • 分类属性选择完成,对训练样本分类,发现属性缺失怎么办?

比如该节点是根据a属性划分,但是待分类样本a属性缺失,怎么办呢?假设a属性离散,有1,2两种取值,那么就把该样本分配到两个子节点中去,但是权重由1变为相应离散值个数占样本的比例。然后计算错误率的时候,注意,不是每个样本都是权重为1,存在分数。

  • 训练完成,给测试集样本分类,有缺失值怎么办?

这时候不能按比例分配,必须给该样本一个确定的label,而不是薛定谔的label。这时候根据投票来确定,或者填充缺失值。

# 如何计算决策树的各特征重要程度?

feature importance 一般有两种计算方法:主要思想就是对决策树构建的参与程度

  • 该feature作为分裂特征的次数,也就是参与构建树的参与次数
  • 该feature作为分裂节点时的信息增益的累加值
  • 自己DIY:比如越早参与决策树的节点分裂的特征往往重要程度越高,可以采用加权的方式计算累加和

至于每一次单独的决策过程,只会有一个特征参与(信息增益最大的特征),将节点分裂成子树

# 如果特征很多,决策树中最后没有用到的特征一定是无用吗?

不是无用的,从两个角度考虑:

一是特征替代性,如果可以已经使用的特征A和特征B可以提点特征C,特征C可能就没有被使用,但是如果把特征C单独拿出来进行训练,依然有效.

其二,决策树的每一条路径就是计算条件概率的条件,前面的条件如果包含了后面的条件,只是这个条件在这棵树中是无用的,如果把这个条件拿出来也是可以帮助分析数据.

# 决策树需要进行归一化处理吗?

概率模型不需要归一化,因为他们不关心变量的值,而是关心变量的分布和变量之间的条件概率。决策树是一种概率模型,数值缩放,不影响分裂点位置,对树模型的结构不造成影响。所以一般不对其进行归一化处理。

按照特征值进行排序的,排序的顺序不变,那么所属的分支以及分裂点就不会有不同。

树模型是不能进行梯度下降的,因为构建树模型(回归树)寻找最优点时是通过寻找最优分裂点完成的,因此树模型是阶跃的,阶跃点是不可导的,并且求导没意义,也就不需要归一化。

# 既然使用神经网络也可以解决分类问题,那SVM、决策树这些算法还有什么意义呢?

在机器学习中,数据大概可以分成四大类:图像 (Image),序列(Sequence),图(Graph) 和表格(Tabular) 数据。其中,前3类数据有比较明显的模式,比如图像和图的空间局部性,序列的上下文关系和时序依赖等。而表格数据常见于各种工业界的任务,如广告点击率预测,推荐系统等。在表格数据中,每个特征表示一个属性,如性别,价格等等,特征之间一般没有明显且通用的模式。

神经网络适合的是前三类数据,也就是有明显模式的数据。因为我们可以根据数据的模式,设计对应的网络结构,从而高效地自动抽取“高级”的特征表达。如常见的 CNN (卷积神经网络) 就是针对图像而设计的,RNN (循环神经网络) 是为序列数据而设计的。而表格数据,因没有明显的模式,非要用神经网络的话,就只能用低效的全连接网络,一般效果都不太好。在实践中,对于表格数据,除了专门对特定任务设计的网络结构如DeepFM等,更多时候还是用传统机器学习模型。尤其是 GBDT (梯度提升树),因其自动的特征选择能力及动态的模型复杂度,算得上是一个万金油模型,在各种类型的表格数据上都表现很好。但对于表格数据而言,其实特征工程才是更关键的。在给定数据的情况下,模型决定了下限,特征决定了上限。特征工程类似于神经网络的结构设计,目的是把先验知识融入数据,并且让模型更好地理解数据,让模型可以学得更好。

另外,神经网络实质上不算是一个模型,而是一类可以自由“搭积木”的模型。结构不同的神经网络可以认为是不同的模型了。

总结下,no free lunch,没有一个万能的模型,可以直接用于各种数据。有多少人工就有多少智能:用神经网络的话,你需要结构设计;而用传统模型的话,你需要特征工程。

# 决策树和条件概率分布的关系?

决策树可以表示成给定条件下类的条件概率分布. 决策树中的每一条路径都对应是划分的一个条件概率分布. 每一个叶子节点都是通过多个条件之后的划分空间,在叶子节点中计算每个类的条件概率,必然会倾向于某一个类,即这个类的概率最大.

# CART的剪枝策略是什么?

代价复杂度剪枝算法,具体如下:

# 如果由异常值或者数据分布不均匀,会对决策树有什么影响?

# 决策树和其他模型相比有什么优点?

# 决策树与逻辑回归的区别?

# 分类树和回归树的区别是什么?

# 如何理解决策树的损失函数?

# sklearn中的决策树是否应该用one-hot编码?

https://www.zhihu.com/question/266195966/answer/306104444