让我联想到博弈论中的决策树。根据多种可能地情况路径，利用概率和已知知识，进行决策判断。
基本问题
Q1：如果建立一颗树，使得经过路径判断，走到叶子时候，能够得到最终样本归属的label(类别)或者y(连续值)？
- 分析这棵树需要满足的基本性质
互斥、完备。即通过各条到叶子的不同路径，能够最终覆盖绝多数的样本。
生成这棵树的过程
1、要得到中间节点(特征)。分类能力越强的特征，越靠近根。
2、要找到当前特征的切分点，而进行分叉。
即涉及到特征选择(特征间重要性比较以及当前特征的切分点)。
而构建的过程，则是递归地选择特征的过程。
直到，没有特征可选、或者样本点已经完全覆盖(特征选择的标准达到阈值，不再分叉)。分析回归树
1、回归树对特征选择和切分点选择的标准，肯定是区别于分类树的。
2、回归树的y如何生成？
分类树的label来自于多数投票。回归树则来自于，落入叶子的样本的均值。
综上，
1、特征选择只在当前考虑选择最优，属于贪心策略，为局部最优。
2、本质上，是将样本空间进行直线(线性棱的空间体)切割。是概率中的条件概率。多个特征规则组合的条件下，样本所属类别的判定。
3、由于1，生成的树易产生过拟合。
4、回归树的回归结果，相比于lr等回归预测模型，结果数量是少的。
Q2：如何进行特征选择？
对于分类树：
1、例如性别、年龄，如果已知性别能够比已知年龄，是更好的信息–即可以更大概率地判断出所属类别，那么就是更重要的特征。
2、其中，更大概率地判断出所属类别 – 即降低经验条件熵。
3、而经验条件熵的缺点是，对于取值比较多的特征，具有偏向性。其公式导致，取值多则经验条件熵值会小。可以考虑极端情况，当每个样本的该特征都取值不同，则经验条件熵为0。就有了C4.5，通过信息增益比来选择特征。
4、CART的gini系数本质和熵类似。越小，熵越小，确定性越高，特征越重要。对于回归树：
1、cart回归树是二叉，要么是要么否。
2、回归树的切分选择不以熵入手考虑，而以均方误差作为判断标准。
3、对于当前特征，找到这样的切分点 – 使得此切分下的两个叶子样本集中，均方误差和最小。误差为：y-所有样本y的均值。
4、生成树过程和分类树一样。为什么不用相关性？
余弦相似度是特征向量在label向量方向上的投影长度。一定程度也是特征重要的体现。
但是，在树模型中，由于本质是条件概率模型，熵就更能反映出概率模型的好坏。
Q3：过拟合处理？
剪枝
1、ID3,C4.5的剪枝是一个动态规划算法。对于某个非叶节点，计算剪去子树后的树的loss和不剪的loss。根据loss小的选择相应动作。而loss大小的比较，可以进行局部计算。因此可用动规实现。
2、loss为，每棵树的所有叶子上样本的熵之和，加上惩罚项(叶子数量或者节点数量)。
3、本质为，正则化的极大似然函数，来选择概率模型。CART剪枝
1、区别于ID3&C4.5，利用了递归思想，对所生成的树进行剪枝。
2、对于某个中间节点，找到进行剪枝动作的阈值–a的大小，a大于阈值则剪枝。即对于每一个中间节点，都有这样的阈值thre所决定的区间[thre,正无穷），剪枝后的树优于生成树。
3、对于所有的最优字数，交叉验证得到最终的最优树，并得到响应的a的thre。
扩展问题
Q4：信息增益比的缺点？
偏好取值少的特征。
C4.5不是直接选择增益比最大的特征，而是之前先把信息增益低于均值的属性剔除，然后在剩下的特征中选择而信息增益比最大的。得到兼顾。
Q5：预剪枝？
1、对当前节点在划分时，进行估计，如果不能够提升泛化能力则不进行划分。
2、本质是基于贪心，对当前节点进行判断是否划分。
3、坏处：当前虽然不能提升泛化能力，但可能划分后子树能够提升泛化能力。导致模型欠拟合。
Q6：对比LR和决策树？
1、y的结果上，决策树是固定的几个值。
2、LR比决策树慢，时间复杂度高。
3、LR无法处理缺失值，需要赋值。并且对极端值更敏感
4、LR对线性关系、全局拟合较好。决策树则是局部最优、局部数据探查更细致，不能更好地对多个特征同时考量。
Q7：CART做了哪些简化？
1、log函数的计算量大，而gini由图形可知，是对熵模型的很好的近似。
2、CART是二叉树，对每个特征进行二分而非多分，减少了特征选择时的计算。
Q8：测试集上缺失值的处理？
1、赋平均值或出现频次最高的值
2、走特征的常用分支
3、特征值专门处理的分支
C4.5的方式是，探查所有的分支，然后得到每个类别的概率，取最大的赋给该样本。
Q9：CART对于离散特征处理、连续特征处理的不同之处？
1、ID3&C4.5都是多叉，特征只出现在一个中间节点；CART是对离散特征不断地二分。
2、连续特征：遍历每个特征，对某特征找到最小化均方误差(loss)的thre点，该点作为该特征的切分点。在所有特征中找到最小的loss，得到最优的(特征，特征切分点)作为中间节点。二分后，对每个孩子继续进行最优的(特征，特征切分点)的查找。同离散特征一样，连续特征可以重复出现，作为中间节点。直到达到停止条件。
3、CART连续特征：换种表述：对于任意划分特征A，对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小所对应的特征和特征值划分点。
4、ID3不支持连续特征划分。C4.5的做法是，将连续值进行排序，取两个值的中间值作为划分点，然后算信息增益比，(连续和离散的)最大的信息增益比为该中间节点。当连续值较多时，计算量的大。并且和CART一样，该连续特征同样可以继续作为中间节点，而非和离线一样一次性地生成多个孩子分叉。
Q10：缺点或者优化？
1、分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1。
2、如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。
其他–都可以在上述问题中找到答案：
如何找到切分点？
本文链接： https://satyrswang.github.io/2021/02/21/决策树/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
