乐趣区

关于机器学习:机器学习-Decision-Tree

jiezi

1 个月未更新了，年底事件比拟多（社畜都懂得~）。上月底报名了百度飞桨的一个常规赛 – MarTech Challenge 点击反欺诈预测，搞了一周（社畜只能上班熬夜搞!），运气比拟好，水到了 Top1。

这个较量是惯例的结构化较量，次要就是依据业务了解进行特色工程 + LGB/XGB 集成模型调参、融模。但如果想对这些 Boosting 算法用起来得心应手的话，还是先要把决策树弄明确。这个十分重要的机器学习模型有很多材料和书籍进行解说，我这纯属班门弄斧。

之前也从未总结过，趁着这个机会总结一下所看的一些材料，重点是讲清楚 决策树中特征选择与切分点。

那就间接进入主题~

决策树的思维是，用节点代表样本汇合，通过某些断定条件来对节点内的样本进行调配，将它们划分到该节点下的子节点，并且要求各个子节点中类别的纯度之和应高于该节点中的类别纯度，从而起到分类成果。

决策树学习的实质是，从训练数据集中演绎出一组分类规定。

结构决策树

递归地抉择最优特色（能将数据集往“纯度”更高的方向划分），顺次直到不能划分为止（所有子集被根本正确分类或者没有适合特色为止）。

这个过程是 部分最优 的，因为 <u> 每个节点的划分都是抉择以后条件下最好的分类 </u>，没有思考前面的节点划分状况，从全局看未必是最优，仅是次优解，并且这种启发式的贪婪算法，容易产生 过拟合，模型泛化能力差。

但，咱们能够从下往上对决策树进行 剪枝 （pruning），剪去过于细分的叶节点，回退到父节点并更改为叶节点，晋升模型的泛化能力，这也是思考 全局最优 的形式。

关键问题：如何抉择适合的特色以及该特色对应的切分地位

切分点查找、评估形式

特征选择的准则：该特色具备很强的 分类能力。

1、信息增益（Information Gain）

也叫熵减，Entropy Decrease，熵是形容信息不确定状态的一种度量，值越大则越不稳固（事件产生的概率越低，所蕴含的信息量越大）。

信息增益 = 父节点信息熵 – 按某特色宰割后子节点 条件熵

其中条件熵指的是，节点决裂之后带来了多少不确定性的升高或纯度的进步：

在每一个小类外面，都计算一个小熵，而后每一个小熵乘以各个类别的概率，而后求和。

所以，信息增益代表随机变量 X 的取值，升高了 Y 的不确定性的均匀缩小量。

举例：

递归抉择信息增益最大的特色作为切分特色。

然而，如果遇到那种 uuid、编号等特色，模型很容易将一个 id 解决成一类，此时条件熵往往等于 0，信息增益必定最大，这里就会陷入特征选择的误区。这并不是咱们想要的分类，容易过拟合。

所以说，信息增益更偏好于抉择取值较多的特色。

2、信息增益比(Gain Ratio)

信息增益比能够很好的校对信息增益的问题。分子还是信息增益，分母为一个惩办项，即特色不同取值下的熵之和。

当决裂数很多的时候（比方一个 id 对应着一个类），惩办项会变大，决裂算法可无效防止抉择这类特色做决裂。

小结

「信息增益」不能齐全反馈一个「决裂」的有效性，通过革新应用「信息增益比」公式，能够无效防止决策树决裂策略应用相似「uuid」、「编号」类的取值量特地大的特色，陷入「最大化信息增益」的误区中。

特色决裂应该应用「二叉树」还是「多叉树」也能够从这个例子中失去启发，二叉树的个性使它自带克制「过拟合」的性能，毕竟二叉树不能一下子间接分完，多叉树是可能一次性间接将样本分完。

决策树生成算法

  1. ID3：信息增益

    • 没有剪枝策略，容易过拟合；
    • 信息增益准则 对可取值数目较多的特色有所偏好，相似“编号”的特色其信息增益靠近于 1；
    • 只能用于解决离散散布的特色;
    • 没有思考缺失值;

  2. C4.5：信息增益比
    间断特色离散化：假如 n 个样本的间断特色 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，别离计算以该划分点作为二元分类点时的信息增益，并抉择信息增益最大的点作为该间断特色的二元离散分类点；

    • C4.5 只能用于分类;
    • C4.5 应用的熵模型领有大量耗时的对数运算，间断值还有排序运算；
    • C4.5 在结构树的过程中，对数值属性值须要依照其大小进行排序，从中抉择一个宰割点，所以只适宜于可能驻留于内存的数据集，当训练集大得无奈在内存包容时，程序无奈运行；
  3. CART
    CART 算法的二分法能够简化决策树的规模，进步生成决策树的效率。

CART

CART,classification and regression tree, 分类回归树，既能够用于分类也能够用于回归。

CART 采纳的二叉树递归，每个非叶子节点都有 2 个分支。

  • 当 CART 是 分类树 的时候，采纳 GINI 值 作为决裂节点的根据；
  • 当 CART 作为 回归树 的时候，应用样本的 最小方差 作为决裂节点的根据。

1、回归树

最小二乘法 回归树生成算法：

抉择某特色，将所有取值分为 2 类（分类有很多种，为 1：n），计算 2 类对应的 y 的均值 c，并计算 2 类取值的均方误差（yi-c)^2，遍历所有的分类状况，抉择误差最小的切分状况。

示例:

2、分类树

分类树是用 基尼指数 抉择最优特色，同时决定该特色的最优二值切分点。<u> 基尼系数越小，不纯度越低，特色越好。</u>

示例：

3、剪枝

CART 采纳后剪枝法，即学生成决策树，而后产生所有剪枝后的 CART 树，而后应用穿插验证测验剪枝的成果，抉择泛化能力最好的剪枝策略。

咱们心愿缩小树的大小来避免过拟合（升高树的复杂度），但又放心去掉节点后预测误差会增大，所以定义一个损失函数来达到这两个变量之间的均衡。

损失函数定义如下：

C(T)为预测误差，|T| 为子树 T 的叶子节点数（代表树的复杂度）

总结

  • 划分规范的差别

    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 是通过代价复杂度剪枝。

参考：

  1. CART 算法的原理以及实现
  2. CART 分类树
  3. 【机器学习】决策树（上）——ID3、C4.5、CART
  4. 艰深了解信息熵
  5. 艰深了解条件熵

  6. 《统计学习办法》

    欢送关注集体公众号：Distinct 数说

退出移动版