每天一个ml模型——决策树

该系列的宗旨为：少公式，简洁化，掌握核心思想，面向对机器学习感兴趣的朋友。

ps：为了微信阅读方便，不过多介绍详细的算法，主要源自李航《统计学习方法》以及周志华《机器学习》，水平所限，望大牛们批评指正。

决策树：多类分类、回归

模型特点：分类树、回归树

学习策略：以损失函数为目标函数的最小化

学习的损失函数：正则化的极大似然函数

学习算法：特征选择，决策树的生成，决策树的剪枝

基本思想：决策树可以转换成一个if-then规则的集合，也可以看做是定义在特征空间划分上的类的条件概率分布

1、决策树模型与学习

1.1决策树模型

用决策树分类，从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点；

这时，每一个子节点对应着该特征的一个取值，如此递归地对实例进行测试并分配，直至达到叶结点

上图为一个决策树模型，圆代表内部结点，表示一个特征或者属性；方框代表叶结点，表示一个类

1.2决策树与if-then规则

由决策树的根节点到叶节点的每一条路径构成一条规则；

路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论

1.3决策树学习

决策树学习目标：构建一个与训练数据拟合很好，并且复杂度小的决策树，从可能的决策树中直接选取最优决策树。

2、特征选择

2.1特征选择问题

特征选择在于选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率。

通常特征选择的准则是信息增益或信息增益比

2.2信息增益

其中H(D)是数据集D的熵，H(D|A)表示数据集D对特征A的条件熵

2.3信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择特征较多的问题，故可以使用信息增益比校正这个问题

3、决策树的生成

决策树的生成算法介绍ID3和C4.5

3.1 ID3算法

核心思想：在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树

具体做法：

从根结点（root node）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；

再对子结点递归调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止

3.2 C4.5生成算法

C4.5和ID3算法相似，只不过使用了信息增益比选择特征

4.决策树的剪枝

防止决策树出现过拟合现象。

决策树的剪枝，往往从已生成的树上剪掉一些叶结点或叶结点以上的子树，并将其父结点或根结点作为新的叶结点，从而简化生成的决策树。

决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。

5.CART算法

分类与回归树（classification and regression tree,CART），是应用广泛的决策树学习方法，是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。

CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。

CART算法由以下两步组成

(1)决策树的生成：基于训练数据集生成决策树，生成的决策树要尽量大

(2)决策树的剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准