ML算法(一)——决策树算法

在机器学习领域中有这样一类算法，它核心思想并不是非常复杂的数学公式而是简单的逻辑if-then分支，这也就造成了它较为容易理解但又不那么容易理解透的特性，它和它的一些tricks是一些大厂必问必推的重点，也是后续像随机森林，GBDT等算法的基础所在，它就是决策树算法。

它一般可以解决分类问题(离散情况)也可以解决回归问题(连续情况)，是对样本进行处理的树形结构，由节点和有向边组成。因为思想较为简单所以它的可解释性性比较强，分类速度比较快，但过拟合现象也十分严重，所以会有后续的剪枝操作。

本文主要讨论决策树用于分类的情况

一般决策树算法有几个步骤：

• 1、特征属性划分(节点分裂)
• 2、递归构建决策树
• 3、消除过拟合进行剪枝

一些前提和约定

• 决策树的每一个叶子节点代表了一个分类，而内部的有孩子的节点表示特定属性或特征的判断，有向边代表了满足某个属性范围的划分规则
• 树从根节点到叶子节点的有向边集合称为路径，所以每条路径都是互斥的即不存在交叉
• 在数据结构中谈到树就应该有递归的定性思维，所以决策树的层级节点划分也是依靠的递归

原理

一般决策树属于有监督学习(即训练集因变量已经标记好了属于哪些类或哪些可能取值)，我们要做的就是训练出一个模型使得这个模型能在已知训练集数据上损失最小即正确分类的样本数最多，在未知训练数据上泛化最好(这也是有监督学习模型的生成思想或者叫套路，泛化是指过拟合程度小，模型相对不复杂，对未知数据或测试集数据的拟合性好)

• 树模型是if-then的形式，需要先针对数据选定判断标准(或者是特征节点分裂，分裂成两组)，所以需要选好节点分裂的方式，以确保能使各个子数据集有一个最好的分类(即选最优划分特征)
• 判断某一样本属于哪个类是根据条件概率大小来确定的，因为决策树有多条路径多个叶子结点，所以将分类空间划分为互斥的多个，所以某一个样本属于哪个类是由一个概率值衡量的，即

,这里的

指的是每个分类，所以此时节点对应的分类是

• 之前提到的损失是由损失函数量化的，一般是正则化的极大似然函数，一般在剪枝中用

过程

• 1、将所有训练数据放在根节点，训练数据有n个样本，m个特征
• 2、根据选定的节点分裂规则划分为两个数据子集，每个子集都是当前条件下的最好的分类
• 3、对比训练数据的已知的标签Y，如果已经基本被正确分类，则这时的子集构成叶子节点，若不能被基本正确分类，则继续对自己选择最优的特征，对子集进行分割，构建新的子节点
• 4、递归第三步，直到所有训练子集被正确分类或节点纯度已经很纯(无法再进行特征划分)为止
• 5、前四步得到的模型对训练数据通常有非常好的分类能力(毕竟模型越复杂会分的越细，可以想象给你一堆散点图让你拟合，一定可以选择更高次数的多项式使得所有散点都在曲线上，但此时模型效果对未知数据反而非常差，违背初衷)，所以此时会进行提高泛化能力的操作，即剪枝，剪去过于细分的叶子结点，使得叶子结点的子集回退到父节点或祖先结点上并替换成子叶节点

剪枝的本质是容忍某些分类误差，决策树过程是模型的局部最优即训练集最优，而剪枝则是为了全局最优

有些场景决策树是有超参数的，比如树高，叶子节点的数量等

核心处理方法

节点分裂(特征选择)

目的是为了选出让训练数据具有很强分类能力的特征(可以和随机划分类比，如果选出的特征的结果和随机划分的特征结果没什么区别则说明这个特征不具备分类能力)，这里先引入信息学中熵的思想：

所以如果一个特征的增益越大表示训练数据基于这个特征的有序性有规律性越大，所以这个特征能更好的将数据集节点的分裂。

生成树

和过程所描述的一致

1、根节点开始，计算所有特征的信息增益，选择信息增益(ID3树)/信息增益比(C4.5树)最大的特征作为节点分裂的特征，划分出两个子数据集节点

2、判断是否满足树的超参数限制和信息增益的阈值，比如树高，叶子节点数等，没达到则递归步骤1

如果没有参数限制，则决策树很有可能每个叶子都只有一个样本，出现分的太细的情况

剪枝

感觉大厂经常问，笔者被问到至少两次

之前所述，剪枝是为了缓解过拟合现象或者提高泛化能力，它主要是从已经生成的树上裁剪掉一些分的太细的子节点，并将此时的父节点或其他辈分更高的节点作为新的子节点，剪枝的依据是极小化决策树的整体损失函数。

一些常见树的区别

• ID3和C4.5树的区别在于节点分裂依据是信息增益还是信息增益比
• CART树与ID3和C4.5树的区别是 前者只是二叉树(要么满足条件要么不满足)，而后两者可以n叉树(取决于特征的可能值数量)，CART的特征可以离散也可以连续(需要划范围进行分桶操作)，后两者是离散，选取的节点分裂方法也不一定相同

GBDT，xgboost，rf后续再讨论