如何构建决策树

宏方法——Hunt算法

之所以叫做宏方法是因为很多决策树的算法都是在此基础上发展过来的，包括接下来介绍的ID3、C4.5、CART算法。

算法的思想很简单，可以分为两步：
1.如果该节点下的样本都属于同一类，将该节点设为叶节点
2.如果该节点下的样本不属于同一类，则选择一个属性测试条件，按照该条件将数据依次分到该节点的子女节点上，对子女节点上递归的调用该算法
终止条件是所有的节点上的样本都是同一类或者属性值相同（不能再继续分割下去）

下面列出这个过程中会出现的两个异常并给出该类别的判断：
1.某节点下面的样本属性值相同，设为叶节点。类别：这些样本中的多数类
2.某个分支下样本为空，设为叶节点。类别：父节点中的样本多数类

那么接下来介绍的算法是如何以该宏方法为基础进行改进的呢？其实只是对该宏方法上的细节进行处理，比如Hunt算法中的属性测试条件？

Impurity Function

首先介绍几个常用的选择属性测试条件时的度量标准——Impurity Function。

熵
$Entropy = -\sum_i p_i log_2 p_i$
基尼指标
$GiniIndex = 1- \sum_i p_i^2$
误分类率
$MisclassificationError = 1 - max p_i$

ID3

ID3算法使用的是增益进行节点分割：
$\Delta = I(parent) - \sum \frac{N(node)}{N} I(node)$
$I(node)$ 是某个节点的Impurity Function的值，这个Impurity Function可以是上述介绍的任意一个，比较常用的是熵和基尼指标。用每个节点的样本数为权重对该节点计算出的Impurity Function进行加权。

异常：

如果该节点计算各属性分割得到的 $\Delta$ 是一样的，设为叶节点。类别：该节点下样本的多数类。

缺点：

不能处理缺失值
不能处理连续的属性值
易过拟合

C4.5

为了改进ID3的缺点，C4.5就出现了。它不再选用增益来分割节点，而是用增益比率，这是因为节点分支越多，增益往往也越大，但在实际中我们并不希望这样的情况出现，易过拟合。
$GainRatio = \frac{Gain}{SplitInfo}$
其中 $SplitInfo = I(nodes)$ ，如果 $I$ 选择熵，则 $SplitInfo = -\frac{N(node)}{N} log_2 \frac{N(node)}{N}$

处理连续值：
-- 离散化
1.连续属性( $x_1, \dots, x_n$ )
2.排序( $x_{(1)}, \dots, x_{(n)}$ )
3.以每个值作为分割点 $( <x_{(1)}\ \ \geq x_{(1)}), \dots, (<x_{(n)}\ \ \geq x_{(n)})$
4.计算每次分割后的增益比率，选一个最大的即可
处理缺失值
-- 原来每个节点下的样本占的比重都为1，这里，属性如果缺失了，那么以 $< 1$ 的概率向下分配样本。
在分割节点的时候，对增益比率进行了一小部分改进：
$Gain$ ：在计算时可以先删掉带有缺失值的样本，对剩下的样本计算Impurity Function，在计算完之后乘上一个 $F = N_{没有缺失值的样本} / N$
$SplitInfo$ ：将带有缺失值的样本代入计算，带有缺失值的样本可以单独看为一个节点
处理过拟合
-- PEP剪枝（悲观错误剪枝）