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

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

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

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

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

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

一些前提和约定

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

原理

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

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

p = p(y | vec{x})

,这里的

vec{x}

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

arg max p(y| vec{x})

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

过程

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