8.决策树

1.分类树vs回归树

分类树（Classification Tree）：解决的问题是分类问题，目标类型是分类型。
回归树（Regression Tree）：解决的问题是预测问题，目标类型是数值型。

输入类型无影响，可数值可类别：训练阶段和学习阶段。

1.1. 分类树种类

ID3 -> C4.5 -> C5.0（一脉相承）
CART
CHAID

都是由上至下的树生成算法。

1.2. 分类树的归纳学原理

所有训练数据都放在根节点。
根据所选特征递归式切割样本数据。
选择属性：选择使得分类正确率更高的属性，选择大多数训练样本属于单一类别的切割。
剪枝——Tree Pruning（避免过拟合问题）：训练数据中会包含噪声数据。

1.3. 属性选择

属性选择：

算法

属性选择基准

ID3

Information Gain

C4.5/C5.0

Gain Ratio

CART

Gini Index

CHAID

Chi-Square Statistic

不同分类树算法采用的计算公式会有所不同，上述选择基准可以理解为：最佳函数树切割函数。

2. 分类树

2.1. ID3

信息获利（Information Gain），化学公式Entropy（熵）——用来衡量内部是偏某一类还是平均分布（内部混乱程度），越靠近1表示平均分布，越靠近0表示偏某一类分布，最平均时Entropy得到的值是1，完全偏某一类时Entropy是0。

Information Gain的计算（略），信息获利的结果越高越好，第一次切割后，左右选择属性会使用不同的属性，——ID3算法不采用剪枝的动作，所以Information Gain目的是让树生长。

缺点：

特征数据的值很多，喜欢字段有很多分支。
所有字段都是类别型（数值型需离散化），即它不能处理连续型属性。
它无法处理缺失属性（空值、无值）。
它无法直接处理噪声数据，抗噪能力弱。

2.2. C4.5

信息增益比（Gain Ratio），它可以改进ID3的四个明显缺点。

$Gain Ratio = \frac{Information Gain}{Information Value}$

其中 $IV$ 表示分支度，等于每个分支的Entropy之和，如果分支度太多反而会扣分，导致Gain Ratio下降。C4.5解决：

ID3喜欢字段有很多分支的问题，分支度过多的问题。
可以处理连续型变量（自动离散化），排序后切割，数值型通常只会分两支。

2.2.1. 剪枝法

修剪法/悲观剪枝：Buttom-Up（C4.5/CART）
盆栽法/预剪枝：Top-Down（CHAID）

两种方法图示如：

悲观剪枝：

假设Confidence Level（CF）= 25%，越小的值会导致更多的剪枝，这种意味着75%的概率会预测错误——数据量越多时，错误率会慢慢下降。
如果展开过后错误率更大，则树就不展开了，这种情况会递归往上执行剪枝动作。

C4.5的公式：

$e = (f + \frac{z^2}{2N} + z\sqrt{\frac{f}{N} - \frac{f^2}{N} + \frac{z^2}{4N^2}}) / (1 + \frac{z^2}{N})$

$N$ 是样本数量「训练」
$E$ 是节点上分类错误样本数「训练」
$f = E/N$ 是观测到的错误率「训练」
$z$ 是基于 $c$ 的标准对应的错误量（c = 25%则z = 0.69）。
$e$ 是预测错误率

砍和子树保留？

2.3. CART

全称（Classfication and Regression Tree），分类回归树——它是一种构建二元（Binary）分类回归树算法。

基本逻辑：

字段选择是使用Gini Index作评估指标。
树剪枝是Bottom-Up的方式配合验证数据集（Validation Dataset）来进行。

Gini的公式比Entropy的简单，Gini比Entropy好的地方是不使用log，所以计算速度会快更多。

$Gini(A_i) = 1 - \sum\limits_{j = 1}^n p_j^2$

计算不同切割法的Gini Index的值，一次分两支，没使用Information Gain，不需要去处理分支度的问题，数值型和类别型都不需考虑分支度 $IV$ 的问题。

最终结果：

Gini Index

Gini Gain

越小越好

越大越好

最终使用验证数据来决定剪枝相关信息，节点真正错误率使用验证数据代替原始的训练数据（训练数据正确率会是100%）。

$Gini = 2 \times AUC - 1$

2.4. CHAID分类树

统计方式的分类算法：字段选择使用卡方统计量，自动将数值型字段离散化，主要使用 $\chi^2$ 来做字段选择。 $\chi^2$ 的值越大（p value值越小），代表该条件字段和目标字段的关系越密切，越是重要条件字段。(p value必须小于0.05，它们之间关系才明显)，CHAID把字段离散化，然后计算每个字段的卡方统计量，根据p value决定树是否继续往下增长，属于Top-Down的剪枝方法，如果 $p < 0.05$ 则树继续增长。

3. 回归树

CART回归树的不同点：在叶节点的时候不是一个类别，而是一个值，使用方差来作为不纯度衡量标准——改进版（M5-Quinlan）。

均值做回归和众数做分类一样，效果不是很好，只能作为一个基模型，所以选择方差。

改进：使用多元线性回归，名称改成模型树（Model Tree），最差时会蜕化成线性回归（不展开），模型树可以做非线性预测。回归树的字段选择：

每个字段尝试分堆，降低对应的方差信息（左右子树方差计算），考虑总方差的降低数。
数值型：排序过后每个切点都会切一刀并计算相关方差信息，然后找到最低方差代表该字段对应的方差计算。

如下图，最低的是Location

方差做不纯度评估标准，M5使用标准差。

4. 决策规则

PRISM决策规则算法

4.1. 分类规则

分类树，分类预测
- 直接
  - 对新进样本测试字段值
  - 根节点一直跑到叶节点（找一个路径），最终叶节点会有Yes/No标签
- 间接
  - 将分类树转换成分类规则
  - 分类规则中找到适合做预测的分类规则

分类规则可以直接精简、产生、优化。

4.2. PRISM

全称：A Simple Bottom-up Covering Algorithm for Creating Rules。

假设数据总共有8笔，先根据每个字段计算：

4.2.1. Generation Rule for C1

4.2.2. Calculate p

$P(C1|Hair = blond)$

上述表格计算了Hair = blond的计算方式。

4.2.3. Output Rule 1

得到规则一：Hair = red -> C1

4.2.4. 重复查找规则2

最终PRISM可能会生成更少的决策规则，这是决策规则比决策树更好的地方，它的可解读性更强。

最后更新于3年前

这有帮助吗？

8.决策树

1.分类树vs回归树

分类树（Classification Tree）：解决的问题是分类问题，目标类型是分类型。
回归树（Regression Tree）：解决的问题是预测问题，目标类型是数值型。

输入类型无影响，可数值可类别：训练阶段和学习阶段。

1.1. 分类树种类

ID3 -> C4.5 -> C5.0（一脉相承）
CART
CHAID

都是由上至下的树生成算法。

1.2. 分类树的归纳学原理

所有训练数据都放在根节点。
根据所选特征递归式切割样本数据。
选择属性：选择使得分类正确率更高的属性，选择大多数训练样本属于单一类别的切割。
剪枝——Tree Pruning（避免过拟合问题）：训练数据中会包含噪声数据。

1.3. 属性选择

属性选择：

算法

属性选择基准

ID3

Information Gain

C4.5/C5.0

Gain Ratio

CART

Gini Index

CHAID

Chi-Square Statistic

不同分类树算法采用的计算公式会有所不同，上述选择基准可以理解为：最佳函数树切割函数。

2. 分类树

2.1. ID3

缺点：

特征数据的值很多，喜欢字段有很多分支。
所有字段都是类别型（数值型需离散化），即它不能处理连续型属性。
它无法处理缺失属性（空值、无值）。
它无法直接处理噪声数据，抗噪能力弱。

2.2. C4.5

信息增益比（Gain Ratio），它可以改进ID3的四个明显缺点。

$Gain Ratio = \frac{Information Gain}{Information Value}$

其中 $IV$ 表示分支度，等于每个分支的Entropy之和，如果分支度太多反而会扣分，导致Gain Ratio下降。C4.5解决：

ID3喜欢字段有很多分支的问题，分支度过多的问题。
可以处理连续型变量（自动离散化），排序后切割，数值型通常只会分两支。

2.2.1. 剪枝法

修剪法/悲观剪枝：Buttom-Up（C4.5/CART）
盆栽法/预剪枝：Top-Down（CHAID）

两种方法图示如：

悲观剪枝：

假设Confidence Level（CF）= 25%，越小的值会导致更多的剪枝，这种意味着75%的概率会预测错误——数据量越多时，错误率会慢慢下降。
如果展开过后错误率更大，则树就不展开了，这种情况会递归往上执行剪枝动作。

C4.5的公式：

$e = (f + \frac{z^2}{2N} + z\sqrt{\frac{f}{N} - \frac{f^2}{N} + \frac{z^2}{4N^2}}) / (1 + \frac{z^2}{N})$

$N$ 是样本数量「训练」
$E$ 是节点上分类错误样本数「训练」
$f = E/N$ 是观测到的错误率「训练」
$z$ 是基于 $c$ 的标准对应的错误量（c = 25%则z = 0.69）。
$e$ 是预测错误率

砍和子树保留？

2.3. CART

全称（Classfication and Regression Tree），分类回归树——它是一种构建二元（Binary）分类回归树算法。

基本逻辑：

字段选择是使用Gini Index作评估指标。
树剪枝是Bottom-Up的方式配合验证数据集（Validation Dataset）来进行。

Gini的公式比Entropy的简单，Gini比Entropy好的地方是不使用log，所以计算速度会快更多。

$Gini(A_i) = 1 - \sum\limits_{j = 1}^n p_j^2$

计算不同切割法的Gini Index的值，一次分两支，没使用Information Gain，不需要去处理分支度的问题，数值型和类别型都不需考虑分支度 $IV$ 的问题。

最终结果：

Gini Index

Gini Gain

越小越好

越大越好

最终使用验证数据来决定剪枝相关信息，节点真正错误率使用验证数据代替原始的训练数据（训练数据正确率会是100%）。

$Gini = 2 \times AUC - 1$

2.4. CHAID分类树

3. 回归树

CART回归树的不同点：在叶节点的时候不是一个类别，而是一个值，使用方差来作为不纯度衡量标准——改进版（M5-Quinlan）。

均值做回归和众数做分类一样，效果不是很好，只能作为一个基模型，所以选择方差。

改进：使用多元线性回归，名称改成模型树（Model Tree），最差时会蜕化成线性回归（不展开），模型树可以做非线性预测。回归树的字段选择：

每个字段尝试分堆，降低对应的方差信息（左右子树方差计算），考虑总方差的降低数。
数值型：排序过后每个切点都会切一刀并计算相关方差信息，然后找到最低方差代表该字段对应的方差计算。

如下图，最低的是Location

方差做不纯度评估标准，M5使用标准差。

4. 决策规则

PRISM决策规则算法

4.1. 分类规则

分类树，分类预测
- 直接
  - 对新进样本测试字段值
  - 根节点一直跑到叶节点（找一个路径），最终叶节点会有Yes/No标签
- 间接
  - 将分类树转换成分类规则
  - 分类规则中找到适合做预测的分类规则

分类规则可以直接精简、产生、优化。

4.2. PRISM

全称：A Simple Bottom-up Covering Algorithm for Creating Rules。

假设数据总共有8笔，先根据每个字段计算：

4.2.1. Generation Rule for C1

4.2.2. Calculate p

$P(C1|Hair = blond)$

上述表格计算了Hair = blond的计算方式。

4.2.3. Output Rule 1

得到规则一：Hair = red -> C1

4.2.4. 重复查找规则2

最终PRISM可能会生成更少的决策规则，这是决策规则比决策树更好的地方，它的可解读性更强。

最后更新于3年前

这有帮助吗？