《老饼讲解机器学习》http://ml.bbbdata.com/teach#92

目录

一.决策树种类简介

(一) 第一支线：CART(classification and regression tree)分类与回归树

(二) 第二支线：ID3算法和C4.5算法

二.常见概念

(一) 决策树中的熵，信息增益，信息增益比，GINI系数是什么？

(二)  剪枝是什么？

---

人们常说的决策树有两支线，共四种 ：
(1) CART：分类与回归树
(2) ID3系列： ID3算法，C4.5算法（ID3加强版）

ID3发展更早，CART现在应用更广泛。实际中，基本都用CART.现在人们说决策树，基本都是指CART (pythn,matlab中也只有CART算法包)

一.决策树种类简介

(一) 第一支线：CART(classification and regression tree)分类与回归树

它是一棵二叉树：

分类树和回归树的输入输出都是数值形（枚举型我们会先作问题转化）
对于分类树，它输出(叶子节点)的是类别。
对于回归树，它输出(叶子节点)的是数值。

(二) 第二支线：ID3算法和C4.5算法

1.  ID3算法决策树：

它不是二叉树，

每一层会选一个变量来作全分裂（可以知道，树的层数上限就是变量个数。）。
它的输入和输出都是枚举值。

2 .  C4.5算法决策树：

C4.5算法是ID3作者昆兰重新修强ID3后发布的一个算法（即C4.5算法决策树是ID3的改进版。）

ID3算法有如下缺点：
(1)变量偏好多枚举值：
(2) ID3容易过拟合。
(3) ID3不支持连续变量。
(4) 不支持数据有缺失值。

修改后，因为要兼容连续变量，就让连续变量每次作二分裂（且可以多次分裂），所以树的层数上限有可能超出变量个数。
其它方面与ID3大同小异，仅是修正了ID3上述的四个缺陷。

二.常见概念

(一) 决策树中的熵，信息增益，信息增益比，GINI系数是什么？

熵，熵增益，GINI系数都是在构建树过程中，用来引导树选择哪个变量分裂，连续变量在何处分裂的函数。

(1) 信息增益     ：供ID3算法使用（ID3算法用各个变量的信息增益决定决策树用哪个变量分裂）。
(2) 信息增益比 ：供C4.5算法使用（C4.5算法用各个变量的信息增益决定决策树用哪个变量分裂）。
(3) GINI系数    ：供CART算法使用（C4.5算法用各个变量不同切处的GINI系数决定决策树用哪个变量，切哪里）
(4) 熵              ：信息增益，信息增益比的理论意义背景。

(二)  剪枝是什么？

1.概念：
树分裂时是一裂到底，但往往一些节点裂与不裂没区别，另一方面，裂得太细致，往往出现过拟合。
因此，剪掉一些不必要的未端枝节，使模型更简单（更简单的模型也意味着更不易过拟合）。

2.剪枝方式：
剪枝一般是自下往上剪，主流是这样，也有一些骚操作，但不是主流。

3.剪枝的凭据：
(1) 如果用父节点分类更准确，剪掉枝叶.
(2) 设立一个损失函数（也是在信息增益，信息增益比，GINI系数的基础上设立的一个引导函数），如果剪掉该枝，损失函数下降，则剪掉。

4.预剪枝：
上面所说的剪枝都是指后剪枝（先把树构建到极致，再剪枝），
预剪枝则指建枝过程中，达到一定条件就不剪了，例如，深度到一定程度，或者节点样本过少等等。
预剪枝实际就是给树设立一个生长条件。

实现例子： 《一个简单的决策树例子》 

《老饼讲解机器学习》http://ml.bbbdata.com/teach#92