决策树算法

决策树的历史

• 第一个决策树算法：$\mathrm{CLS}$ 算法
• 是决策树受到关注、称为机器学习主流技术的算法：$\mathrm{ID}3$ 算法
• 最常用的决策树算法：$\mathrm{C}4.5$ 算法
• 其他决策树算法：如可以用于回归任务的决策树算法：$\mathrm{CART}$ 算法、基于决策树最强大的算法：$\mathrm{RF}$ 算法

决策树模型

决策树是一个离散属性的、有监督的多分类模型。决策树基于树结构来进行决策。其中每个内部节点对应于某个属性上面的测试，每个分支对应于该测试的一个可能的结果（即一个范围），而每个叶节点对应于一个预测结果。

学习过程：通过对训练样本的分析来确定“划分属性”，即决定每个内部节点上的判定测试。

预测过程：将测试用例从根节点开始，沿着划分属性所构成的“判定测试序列”下行，直到叶节点。

基本流程

决策树的基本策略是分而治之。即自根节点开始，递归地对数据集进行划分，直到达到了停止条件，然后就可以生成决策树。

停止条件主要有以下三种：

• 当前节点包含的样本全属于同一类别，无需划分；
• 当前属性集为空，或者是所有样本在所有属性上取值相同，无法划分；
• 当前节点包含的样本集合为空，不能划分。

因此，我们可以得到决策树生成算法的伪代码：

// 定义节点结构 // 
Node {
    bool isLeaf              // 标记是否为叶子节点
    int label                // 如果是叶子节点，存储类别标签
    int splitAttribute       // 用于划分的属性
    List<int> splitValues    // 属性的划分值（支持多个值）
    List<Node> children      // 子节点列表，每个值对应一个子节点
}

// 决策树构建函数
Node buildDecisionTree(Data[] data, Attribute[] attributes) {
    if (allSamplesHaveSameLabel(data)) {
        return createLeafNode(getLabel(data)) // 第一种停止条件
    }

    if (attributesAreEmpty(attributes)) {
        return createLeafNode(getMostFrequentLabel(data)) // 第二种停止条件
    }

    bestAttribute = selectBestAttribute(data, attributes)
    splitValues = getPossibleValues(bestAttribute)

    Node node = createNode(bestAttribute)

    for each value in splitValues {
        subset = filterDataByAttributeValue(data, bestAttribute, value)
        if (subset is empty) {
            node.children.append(createLeafNode(getMostFrequentLabel(data))) // 第三种停止条件
        } else {
            node.children.append(buildDecisionTree(subset, remainingAttributes)) // 继续划分
        }
    }

    return node
}

// 判断数据是否属于同一类别
bool allSamplesHaveSameLabel(Data[] data) {
    return (所有样本的标签相同)
}

// 选择最佳划分属性
int selectBestAttribute(Data[] data, Attribute[] attributes) {
    return (通过某种度量选择最佳属性，例如信息增益)
}

// 获取属性的所有可能取值
List<int> getPossibleValues(int attribute) {
    return (该属性的所有可能取值)
}

// 根据属性值过滤数据集
Data[] filterDataByAttributeValue(Data[] data, int attribute, int value) {
    return (选择该属性等于特定值的样本)
}

决策树生成的最核心部分就是选择最佳划分属性。不同决策树的算法视角不同，选择的度量也不同，这就产生了归纳偏好。而选择划分属性最核心的思想就是要让划分后的每个类别尽可能“纯”，显然，这样可以减少后面的划分步骤并且提高分类的精度。而至于如何去衡量“纯”这一形容词，我们马上就来介绍。

信息增益

信息增益直接以信息熵为基础，计算划分前后的信息熵差值。因此我们先来介绍信息熵。

信息熵

信息熵是度量样本“纯度”最常用的一种指标。假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k$，则 $D$ 的信息熵定义为：

$$\mathrm{Ent}(D)=-\sum _{k=1}^{|\mathcal{Y}|}{p}_k{\log }_2{p}_k$$

其中，$\mathcal{Y}$ 是类别集合。在计算信息熵时，我们通常规定 $0\log 0=0$。因此，我们不难看出，信息熵的值越小，样本的纯度越高，且 $min\{\mathrm{Ent}(D)\}=0$，$max\{\mathrm{Ent}(D)\}={\log }_2|\mathcal{Y}|$。

例如，我们有两个类别，但所有样本都属于第一个类别，那么信息熵为 $-1{\log }_{2}1-0{\log }_{2}0=0$，即样本的纯度最高；而如果两个类别的样本数量相等，那么信息熵为 $-0.5{\log }_{2}0.5-0.5{\log }_{2}0.5=1$，即样本的纯度最低。

假设离散属性 $a$ 有 $V$ 个可能的取值 $\{a^1,a^2,\dots ,a^V\}$，$D^v$ 表示 $D$ 中在属性 $a$ 上取值为 $a^v$ 的样本集合（其中 $v=1,2,\cdots ,V$），则以属性 $a$ 对样本集合 $D$ 进行划分所得到的信息熵的差为：

$$\mathrm{Gain}(D,a)=\mathrm{Ent}(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}\mathrm{Ent}(D^v)$$

其中，$\frac{|D^v|}{|D|}$ 表示属性 $a$ 取值为 $a^v$ 的样本在 $D$ 中所占的比例，比重越大，信息熵的影响越大。对于各个可选的属性，我们选择信息增益最大的属性作为划分属性。这样，我们就可以递归地生成决策树了。

可是，直接使用信息增益作为划分属性的标准，会有一个问题：信息增益偏向于选择取值较多的属性。例如，我们如果将“编号“作为属性，那么信息增益就会很大（想象一下，如果我们给定一个编号，那样本的类别就可以直接确定了）。因此，我们引入了信息增益率来消除这种影响。

增益率定义为：

$$\mathrm{Gain}\mathrm{\_}\mathrm{ratio}(D,a)=\frac{\mathrm{Gain}(D,a)}{\mathrm{IV}(a)}$$

其中

$$\mathrm{IV}(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}$$

如果属性 $a$ 的取值较多，那么 $\mathrm{IV}(a)$ 的值就会较大，从而抵消掉信息增益的影响。但这样做也有可能导致决策树对取值较多的属性带有“偏见”，有几率漏掉一些重要的属性。因此，我们有时也采用启发式算法。启发式算法先从候选属性集中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

基尼指数

前文介绍的信息增益和信息增益率都是基于信息熵的，因此需要引入大量的对数运算，在数据集较大时性能较低。因此，我们还可以使用基尼指数来选择划分属性。

基尼指数只需要计算比例。具体地，设 $p_k$ 为样本属于第 $k$ 类的概率，$D^k$ 为样本集合 $D$ 中属于第 $k$ 类的样本子集，则基尼指数定义为：

$$\mathrm{Gini}(D)=\sum _{k=1}^{|\mathcal{Y}|}\sum _{k^{\prime }\ne k}{p}_k{p}_{k^{\prime }}=1-\sum _{k=1}^{|\mathcal{Y}|}{p}_k^2=1-\sum _{k=1}^{|\mathcal{Y}|}{\left(\frac{D^k}{D}\right)}^2$$

基尼指数反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。因此，基尼指数越小，数据集的纯度越高。

决策树的剪枝

研究表明，划分选择的各种准则虽然对决策树的尺寸有很大的影响，但对泛化性能的影响却不大。但是，剪枝方法和程度对决策树的泛化性能有很大的影响，在数据带有噪声的情况下，甚至可以将泛化性能提高 $25\mathrm{\%}$。因为剪枝是决策树对付“过拟合”的重要手段。

决策树的剪枝分为预剪枝和后剪枝两种。预剪枝是指提前终止某些分支的生长，而后剪枝则是先生成完整的决策树，再通过某种准则来剪枝。

预剪枝

利用留出法就可以实现一种最简单的预剪枝。具体地，我们可以将数据集分为训练集和验证集，然后在训练集上生成决策树。对于每个内部节点，我们可以计算在验证集上划分前后的错误率，如果剪掉这个节点（即不进行划分，把这个节点变成叶节点，类别为该节点中样本最多的类别）能够降低错误率，那么就剪掉这个节点。

后剪枝

同样，将数据集分为训练集和验证集，然后在训练集上生成完整的决策树。接着，我们可以自底向上地对决策树进行剪枝。具体地，我们可以计算剪掉某个节点后在验证集上的错误率，如果剪掉这个节点能够降低错误率，那么就剪掉这个节点。

预剪枝和后剪枝的比较

预剪枝的测试时间和训练时间都比后剪枝要短，但是预剪枝的欠拟合风险增加。而泛化性能上，后剪枝的效果经常优于预剪枝。

特殊处理

对于连续值的处理

对于连续值的处理，我们的基本思路是连续属性离散化。常见的做法就是二分法，即对某个属性，如果有 $n$ 个属性值，那么会产生 $n-1$ 个候选划分点。对于这些候选划分点，我们可以计算信息增益或基尼指数，选择最优的划分点即可。

对于缺失值的处理

现实数据集中，经常会有缺失值。如果对于有缺失值的样例，我们都舍弃的话，那么会造成大量数据的浪费。其实，我们只需要在计算信息增益或基尼指数时，乘以一个缺失值样本所占的比例系数即可。而它们在进入下一层划分时，会按照该属性其他样本的比例进行划分。

多变量决策树

前面的决策树都是单变量决策树，即每次只能选择一个属性作为判据，即轴平行决策树，这种决策树的表达能力有限。因此，我们可以引入多变量决策树，即每次可以选择多个属性作为判据，这就是倾斜的决策树。

轴平行是哪个轴？？

如果我们把每个属性视为坐标空间里面的一个轴，那么由 $n$ 个属性构成的样本空间就是一个 $n$ 维空间，其中每个样本就是这个空间里面的一个点。单变量决策树的分类边界总是和坐标轴平行的，因为它每次只能选择一个属性作为判据。（可以想象二维和三维空间中的例子）

多变量决策树的每个节点并不是利用单独一个属性来决定应当划分到哪一个子节点，而是作为一个线性选择器，利用一个属性的线性组合来进行划分。这样，我们就可以更好地处理属性之间的关系，这一模型的表达能力就更加强大。