8.决策树

1.分类树vs回归树

• 分类树（Classification Tree）：解决的问题是分类问题，目标类型是分类型。

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

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

1.1. 分类树种类

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

• CART

• CHAID

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

1.2. 分类树的归纳学原理

1. 所有训练数据都放在根节点。

2. 根据所选特征递归式切割样本数据。

3. 选择属性：选择使得分类正确率更高的属性，选择大多数训练样本属于单一类别的切割。

4. 剪枝——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. 剪枝法

1. 修剪法/悲观剪枝：Buttom-Up（C4.5/CART）

2. 盆栽法/预剪枝：Top-Down（CHAID）

    两种方法图示如：

    悲观剪枝：

1. 假设Confidence Level（CF）= 25%，越小的值会导致更多的剪枝，这种意味着75%的概率会预测错误——数据量越多时，错误率会慢慢下降。

2. 如果展开过后错误率更大，则树就不展开了，这种情况会递归往上执行剪枝动作。

    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可能会生成更少的决策规则，这是决策规则比决策树更好的地方，它的可解读性更强。