决策树（上） ID3, C4.5, CART https://blog.csdn.net/Datawhale/article/details/102878758?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_baidulandingword~default-1.pc_relevant_paycolumn_v2&spm=1001.2101.3001.4242.2 https://zhuanlan.zhihu.com/p/404072623

简单介绍决策树算法

决策树主要包括三个部分：内部节点、叶节点和边。内部节点是划分的属性，边代表划分的条件，叶节点表示类别。构建决策树 就是一个递归的选择内部节点，计算划分条件的边，最后到达叶子节点的过程。

CART回归算法

CART生成算法

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

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

ID3, C4.5, CART的最优划分选择标准？

• ID3：信息增益

样本集合D，类别数K，数据集D的经验熵为
某个特征A对D的经验条件熵H(D|A)为
信息增益为
选择标准：信息增益大的特征分类能力更强

• C4.5：信息增益比

特征A对于数据集D的信息增益比为 ， 其中
选择标准：信息增益比对可取值较少的特征有所偏好，因此使用一个启发式算法：先从候选划分属性中找出信息增益率高于平均水平的属性，再从中选择增益率最高的

• CART：基尼指数

Gini描述的是数据的纯度
特征A的Gini指数为
选择标准：Gini(D)反映了从数据集D的纯度，越小，数据越纯
信息熵的优点：没有对数运算，计算量小

为什么选择信息增益？

因为信息增益表示由于某特征而使得数据集D的分类的不确定性减少的程度，信息增益大的特征具有更强的分类能力。

信息增益比相对信息增益有什么好处？

• 信息增益：模型偏向于选择取值较多的特征。信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益越大。但是这样泛化能力很差。
• 信息增益比：对取值多的特征加上的惩罚，避免过拟合，提升决策树的泛化能力

ID3算法—>C4.5算法—> CART算法

• 从样本类型的角度，ID3只能处理离散型变量，而C4.5 和CART都可以处理连续型变量。C4.5处理连续型变量时，通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把连续属性转换为布尔型，从而将连续型变量转换多个取值区间的离散型变量。而对于CART，由于其构建时每次都会对特征进行二值划分，因此可以很好地适用于连续性变量。
• 应用角度，ID3 和C4.5只能用于分类任务，而CART不仅可以用于分类，也可以应用于回归任务(回归树使用最小平方误差准则)。
• 从实现细节、优化过程等角度，这三种决策树还有一些不同。
  • ID3 对样本特征缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理（如何处理？；
  • ID3 和C4.5可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而CART每个结点只会产生两个分支，因此最后会形成一颗二叉树，且每个特征可以被重复使用；
  • ID3和C4.5通过剪枝来权衡树的准确性与泛化能力，而CART直接利用全部数据发现所有可能的树结构进行对比。
• ID3 和 C4.5 是多叉树，速度较慢，CART 是二叉树，计算速度很快；
• 从样本量考虑的话，小样本建议 C4.5、大样本建议 CART。C4.5 处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而 CART 本身是一种大样本的统计方法，小样本处理下泛化误差较大 ；
• 剪枝策略的差异：ID3 没有剪枝策略，C4.5 是通过悲观剪枝策略来修正树的准确性，而 CART 是通过代价复杂度剪枝。

决策树的目标函数是什么？

%3D%5Csum%7Bt%3D1%7D%5E%7B%7CT%7C%7D%20N%7Bt%7D%20H%7Bt%7D(T)%2Ba%7CT%7C%0A#card=math&code=C%7B%5Calpha%7D%28T%29%3D%5Csum%7Bt%3D1%7D%5E%7B%7CT%7C%7D%20N%7Bt%7D%20H%7Bt%7D%28T%29%2Ba%7CT%7C%0A&id=cFAMr)
%3D-%5Csum%7Bk%7D%20%5Cfrac%7BN%7Bt%20k%7D%7D%7BN%7Bt%7D%7D%20%5Clog%20%5Cfrac%7BN%7Bt%20k%7D%7D%7BN%7Bt%7D%7D%0A#card=math&code=H%7Bt%7D%28T%29%3D-%5Csum%7Bk%7D%20%5Cfrac%7BN%7Bt%20k%7D%7D%7BN%7Bt%7D%7D%20%5Clog%20%5Cfrac%7BN%7Bt%20k%7D%7D%7BN%7Bt%7D%7D%0A&id=cyDEC)
其中代表叶节点个数，表示具体某个叶节点的样本数，#card=math&code=H_t%28T%29&id=OE9vO) 表示叶节点上的经验熵，为正则项，为参数
代表模型对训练数据的预测误差，即模型与训练数据的拟合程度，代表模型复杂度，参数控制两者之间的影响。

当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优的选择策略是NP完全问题，所以在现实中决策树学习算法通常采用启发方法，近似求解这一最优化问题，这样得到的决策树是次最优的。

为什么说决策树的目标函数是正则化的极大似然？

决策树的剪枝算法有哪些？优缺点是？

输入:生成算法产生的整个树T,参数a;
输出:修剪后的子树Ty。
(1)计算每个结点的经验熵。
(2)递归地从树的叶结点向上回缩。
设一组叶结点回缩到其父结点之前与之后的整体树分别为TB与TA,其对应的
损失函数值分别是Ca(TB)与Ca(TA),如果
Ca(TA)≤Ca(Tp)
则进行剪枝，即将父结点变为新的叶结点。
(3)返回(2),直至不能继续为止，得到损失函数最小的子树Ta。

如何判断决策树泛化性能是否提升呢？本节假定采用留出法，即预留一部分数据用作“验证集”以进行性能评估。

• 预剪枝
  • 预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点;
  • 问题：预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险,还显著减少了决策树的训练时间开销和测试时间开销.但另一方面,有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。
• 后剪枝
  • 后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
  • 后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

CART的剪枝，参考李航的《统计学习方法》

决策树的缺失值是怎么处理的？

决策树怎么处理连续性特征？

因为连续特征的可取值数目不再有限，因此不能像前面处理离散特征枚举离散特征取值来对结点进行划分。因此需要连续特征离散化，常用的离散化策略是二分法，这个技术也是中采用的策略。下面来具体介绍下，如何采用二分法对连续特征离散化：

• 训练集D，连续特征，其中A有n个取值
• 对的取值进行从小到大排序得到：
• 寻找划分点，将D分为子集与
  • ：特征上取值不大于的样本
  • ：特征上取值大于的样本
• 对相邻的特征取值与，t再区间#card=math&code=%5Bai%2Ca%7Bi%2B1%7D%29&id=cpWaP)中取值所产生的划分结果相同，因此对于连续特征,包含有个元素的后选划分点集合

• 把区间#card=math&code=%5Bai%2Ca%7Bi%2B1%7D%29&id=dFhaO)的中位点作为候选划分点
• 按照处理离散值那样来选择最优的划分点,使用公式： %20%3D%5Cunderbrace%7Bmax%7D%7Bt%5Cin%20T_a%7DGain(D%2Ca%2Ct)%20%3D%20%5Cunderbrace%7Bmax%7D%7Bt%5Cin%20Ta%7D%5C%20(Ent(D)%20-%20%5Csum%7B%5Clambda%20%5Cin%20%5C%7B-%2C%2B%20%5C%7D%7D%5Cfrac%7B%7CDt%5E%7B%5Clambda%7D%7C%7D%7B%7CD%7C%7DEnt(D_t%5E%7B%5Clambda%7D))%0A#card=math&code=Gain%28D%2Ca%29%20%3D%5Cunderbrace%7Bmax%7D%7Bt%5Cin%20Ta%7DGain%28D%2Ca%2Ct%29%20%3D%20%5Cunderbrace%7Bmax%7D%7Bt%5Cin%20Ta%7D%5C%20%28Ent%28D%29%20-%20%5Csum%7B%5Clambda%20%5Cin%20%5C%7B-%2C%2B%20%5C%7D%7D%5Cfrac%7B%7CD_t%5E%7B%5Clambda%7D%7C%7D%7B%7CD%7C%7DEnt%28D_t%5E%7B%5Clambda%7D%29%29%0A&id=KhGha)
  其中#card=math&code=Gain%28D%2Ca%2Ct%29&id=spaaI)是样本集基于划分点二分之后的信息增益。划分点时候选择使用#card=math&code=Gain%28D%2Ca%2Ct%29&id=vngp5)最大的划分点。

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

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

不是无用的，从两个角度考虑：

• 特征替代性，如果可以已经使用的特征和特征可以提点特征，特征可能就没有被使用，但是如果把特征单独拿出来进行训练，依然有效
• 决策树的每一条路径就是计算条件概率的条件，前面的条件如果包含了后面的条件，只是这个条件在这棵树中是无用的，如果把这个条件拿出来也是可以帮助分析数据.

  树形结构为什么不需要归一化?

概率模型不需要归一化，因为他们不关心变量的值，而是关心变量的分布和变量之间的条件概率。决策树是一种概率模型，数值缩放，不影响分裂点位置，对树模型的结构不造成影响。所以一般不对其进行归一化处理。
按照特征值进行排序的，排序的顺序不变，那么所属的分支以及分裂点就不会有不同。
树模型是不能进行梯度下降的，因为构建树模型（回归树）寻找最优点时是通过寻找最优分裂点完成的，因此树模型是阶跃的，阶跃点是不可导的，并且求导没意义，也就不需要归一化。

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

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

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

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

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

• 对异常值不敏感

Decision trees are also not sensitive to outliers since the partitioning happens based on the proportion of samples within the split ranges and not on absolute values.

CART为什么用二叉？

二叉的好处是不会遇到ID3使用信息增益的那种问题。

决策树怎么防止过拟合？

• 对于决策树进行约束：根据情况来选择或组合
  • 设置每个叶子节点的最小样本数，可以避免某个特征类别只适用于极少数的样本。
  • 设置每个节点的最小样本数，从根节点开始避免过度拟合。
  • 设置树的最大深度，避免无限往下划分。
  • 设置叶子节点的最大数量，避免出现无限多次划分类别。
  • 设置评估分割数据的最大特征数量，避免每次都考虑所有特征为求“最佳”，而采取随机选择的方式避免过度拟合。
• 预剪枝(提前停止)：控制深度、当前的节点数、分裂对测试集的准确度提升大小
• 后剪枝(自底而上)：生成决策树、交叉验证剪枝：子树删除，节点代替子树、测试集准确率判断决定剪枝

  为什么C4.5能处理连续特征，ID3不能？

  https://www.zhihu.com/question/425720956
  为什么ID3不考虑连续特征？这是因为任何研究都是循循渐进的，每一个研究只会将精力放在当前最重要的研究点之上。ID3与C4.5都是Quinlan 的作品，而ID3的研究重点是如何设计高效的节点分裂方法来生长决策树，因此它并不太在意如何去处理连续特征。
  而C4.5的重点则是将ID3的成果工程化，让决策树能真正解决实际中的复杂问题，所以C4.5设计了详细的连续特征处理方法和剪枝算法。
  以现在的眼光来看，只要你愿意，可以很容易地将ID3改造为有能力处理连续特征的决策树。

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

ID3的缺陷

• ID3没有考虑连续特征
• 信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
• ID3 没有剪枝策略，容易过拟合

C4.5的解决方案

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

ID3和C4.5的缺陷

• 容易过拟合
• 生成多叉树，不利于计算机计算
• 大量对数运算，对cpu不友好。连续属性还要排序，从中选择分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

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

在机器学习中，数据大概可以分成四大类：图像 (Image)，序列(Sequence)，图(Graph) 和表格(Tabular) 数据。其中，前3类数据有比较明显的模式，比如图像和图的空间局部性，序列的上下文关系和时序依赖等。而表格数据常见于各种工业界的任务，如广告点击率预测，推荐系统等。在表格数据中，每个特征表示一个属性，如性别，价格等等，特征之间一般没有明显且通用的模式。
神经网络适合的是前三类数据，也就是有明显模式的数据。因为我们可以根据数据的模式，设计对应的网络结构，从而高效地自动抽取“高级”的特征表达。如常见的 CNN (卷积神经网络) 就是针对图像而设计的，RNN (循环神经网络) 是为序列数据而设计的。而表格数据，因没有明显的模式，非要用神经网络的话，就只能用低效的全连接网络，一般效果都不太好。在实践中，对于表格数据，除了专门对特定任务设计的网络结构如DeepFM等，更多时候还是用传统机器学习模型。尤其是 GBDT (梯度提升树)，因其自动的特征选择能力及动态的模型复杂度，算得上是一个万金油模型，在各种类型的表格数据上都表现很好。但对于表格数据而言，其实特征工程才是更关键的。在给定数据的情况下，模型决定了下限，特征决定了上限。特征工程类似于神经网络的结构设计，目的是把先验知识融入数据，并且让模型更好地理解数据，让模型可以学得更好。
另外，神经网络实质上不算是一个模型，而是一类可以自由“搭积木”的模型。结构不同的神经网络可以认为是不同的模型了。
总结下，no free lunch，没有一个万能的模型，可以直接用于各种数据。有多少人工就有多少智能：用神经网络的话，你需要结构设计；而用传统模型的话，你需要特征工程。

决策树相比其他模型有什么优点？

决策树的优缺点？

• 优点:
  • 基本不需要预处理，不需要提前归一化，处理缺失值。
  • 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
  • 可以处理多维度输出的分类问题。
  • 相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释
  • 可以交叉验证的剪枝来选择模型，从而提高泛化能力。
  • 对于异常点的容错能力好，健壮性高。
  • 用白盒模型，可清洗观察每个步骤，对大数据量的处理性能较好，更贴近人类思维。
  • 速度快: 计算量相对较小, 且容易转化成分类规则. 只要沿着树根向下一直走到叶, 沿途的分裂条件就能够唯一确定一条分类的谓词.
• 缺点:
  • 决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
  • 寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
  • 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

    CART

    CART怎么处理连续特征？

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

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

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

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

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的剪枝策略？

参考资料

c4.5为什么使用信息增益比来选择特征？