决策树是十大数据挖掘算法之一，在很多工程实践中都取得了很好的效果。其分类决策过程与20问游戏类似，专家系统中经常适用决策树，而且决策树给出结果往往可以匹敌在当前领域具有几十年工作经验的人类专家。

本文对决策树的基本原理，优缺点，应用场景等进行了简要的概述。此外将会陆续实现常用的机器学习和数据挖掘算法，有简单直观的notebook形式，也有python易用重用的代码。代码实践部分参考[4]，数据也来源于课本附带的小的数据集，方便使用。
代码链接：https://github.com/hfl15/MLinAction

概述

优点：

• 计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据[4]。
• 不需要领域知识和参数设置，可以处理高维数据，树型表示直观容易理解，学习和分类步骤简单、快速，一般有较好的准确率[3]

缺点：

• 可能产生过拟合[4]

适用数据类型：

• 标称型、数值型（需要离散化）[4]

关键字：

• 决策树归纳，分裂属性选择，剪枝

算法步骤

Input:
    D: data set, contain value and class label
    attribute_list : candidate attribute list
    Attribute_selection_method: a process to select best split attribute in candidate attribute list
Return:
    a decision tree
    
DecisionTree(D, attribute_list, Attribute_selection_method):
    create a new node TNode;
    if all instance in D have the same class label C:
        return TNode as a leaf node and label with class C;
    endif
    if attribute_list is NULL:
        return TNode as a leaf node and label with voting class (for instance majority voting);
    endif
    
    best_split_attribute = Attribute_selection_method(D, attribute_list);
    label TNode with best_split_attribute;
    attribute_list = attribute_list - best_split_attribute;
    for each unique value j in best_split_attribute:
        set Dj is a subset of D, which correspond the output j;
        if Dj is NULL:
            add a leaf node to TNode and label with voting class with D
        else:
            add a child for TNode and let it point to the output of DecisionTree(Dj, attribute_list, Attribute_selection_method)
        endif
    endfor

几种决策树

• ID3 ： 基础版本，信息增益，先剪枝
• C4.5 ： 信息增益率，先剪枝（悲观剪枝，只考虑误差，泛化能力差） (disadvantage: CPU time and memory [1])
• CART ： 基尼系数，在所有可能的特征A以及它们所有可能的切分点a中，选择基尼系数最小的作为切分点。后剪枝（考虑误差和树的结构复杂度）

属性选择

• 信息增益：偏向于多值属性（极端例子，record的id）
• 信息增益率：矫正信息增益不足。但倾向于产生不平衡的划分，其中一个分区比其他分区小得多。
• 基尼系数：CART树。（1）偏向于多值属性，并且当类的数量很大时会很困难；（2）倾向于导致相等大小的分区和纯度。
• 其他：CHAID, C-SEP, G-统计量....

Note: 所有度量都是有偏的，目前没有发现哪一种度量显著优于其他度量，需结合具体实践。

信息熵、信息增益、信息增益率

信息熵：

如果一个随机变量X可能有多个取值，则符号\(x_{i}\)的信息定义为：\(I(x_{i}) = -logp(x_{i})\)，其中\(p(x_{i})\)是随机变量取\(x_{i}\)的概率。
信息熵是信息混乱程度的度量，越高说明信息越混乱，表明数据越混乱，其定义为随机变量X所有可能的信息（所有可能的取值）的期望，即：
\(H(X) = -\sum_{i=1}^{n} x_{i}*log(p(x_{i}))\)
\(x_{i}, i = 1, .., n\) 对应X的一个划分。信息熵只与随机变量的分布有关，与随机变量的取值无关

信息增益(ID3)：

对于分类问题，假设训练集为\(D = (x^{i}, y^{i})\)，\(y^{i}\)表示类标，总共有K类\(C_{k}(k=1,...,K)\), \(|D|\)操作表示取集合的个数。现计算以属性A作为划分变量的信息增益，其中A有n个不同的取值，一个取值对应一个划分\(D_{i}\)：
(1) 计算原数据集的信息熵（经验熵）
\(H(D) = -\sum_{k=1}^{K}\frac{|C_{k}|}{|D|}log(\frac{|C_{k}|}{|D|})\)
(2) 计算划分后的信息熵（条件熵）
\(H(D|A) = \sum_{i=1}^{n}\frac{|D_{i}|}{|D|}H(D_{i}) = -\sum_{i=1}^{n}\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_{i}|}log(\frac{|D_{ik}|}{|D_{i}|})\)
(3) 计算信息增益
\(Gain(D,A) = H(D) - H(D|A)\)

对所有候选属性重复(1)(2)(3)，最后取信息增益最大的属性作为划分属性。对于所有属性来说H(D)的值是一样的，不同在于划分之后的条件熵，因此信息增益越大，说明条件熵越小，也就说明了划分之后的数据集混乱程度更小。

信息增益率( C4.5 )（越大越好）：

在信息增益的基础上除以“分裂信息（split information）”，将信息增益规范化。分裂信息定义如下：
\(SplitInfo(D,A) = - \sum_{j=1}^{v}\frac{|D_{j}|}{|D|}log(\frac{|D_{j}|}{|D|})\)
\(v\)为分裂属性A可能的取值数，\(D_{j}\)对应其中一个取之的数据集划分。
那么信息增益率定义为：
\(GainRate(D,A) = \frac{Gain(D,A)}{SplitInfo(D,A)}\)

注意：log以2为底

基尼系数 (CART)(越小越好):

\(Gini(D) = 1 - \sum_{k=1}^{K}p_{i}^{2}\)
其中\(p_{i}\)表D中元组属于类\(C_{k}(k=1,...,K)\)的概率，可以使用\(\frac{|C_{k}|}{|D|}\)估计。可以这么理解：进行K次试验，每次同时抽取2个实例，这两个实例都属于同一类的概率为\(p_{i}^{2}\)，如果数据集越纯，那么这一值就越大，相应的基尼系数就越小，也就表明了数据集更纯。
对于二元划分，划分属性A：
\(Gini(D|A) = \frac{|D_{1}|}{|D|}Gini(D_{1}) + \frac{|D_{2}|}{|D|}Gini(D_{2})\)
划分不纯度降低：
\(Gini(D) = Gini(D) - Gini(D|A)\)

基尼系数越大，不确定性程度越高，与信息熵对应

剪枝

解决过拟合，使用统计量剪掉最不可靠的分枝。

决策树的剪枝往往通过极小化决策树整体的损失函数货代价函数来实现。
\(C_{\alpha}(T) = \sum_{t=1}^{|T|} |N_{t}|H_{t}(T) + \alpha|T|\)
\(H_{t}(T) = -\sum_{k=1}^{K}\frac{N_{tk}}{N_{t}}log(\frac{N_{tk}}{N_{t}})\)
\(C = \sum_{t=1}^{|T|}N_{t}H_{t}(T) = \sum_{t=1}^{|T|} \sum_{k=1}^{K}N_{t}\frac{N_{tk}}{N_{t}}log(\frac{N_{tk}}{N_{t}}) = \sum_{t=1}^{|T|} \sum_{k=1}^{K}N_{tk}log(\frac{N_{tk}}{N_{t}})\)

其中T表示树的叶节点集合，每个叶结点对应数据集\(N_{t}\)，类别用k表示。
\(\alpha\) 权衡预测误差和树的复杂度。

(1)先剪枝（prepruning）：当信息增益（或信息增益率）小于某个阈值时停止划分

• 不足：基于‘贪心’的思想禁止分枝继续展开，泛化能力差，具有欠拟合的风险
• 优点：由于分枝没有展开，降低过拟合风险，减小计算开销

(2)后剪枝（postpruning）：对于训练好的树，依次将子树替换成新的叶子结点，对于前后两个棵树分别计算上面定义的决策树损失函数，若果修改后的树具有更小的误差值，则修改生效

• 缺点：自底向上搜索剪枝，空间和时间开销大
• 优点：相比于先剪枝，保留更多分枝，泛化能力相对更好，欠拟合风险小，

一些关键点：

• CART使用后剪枝，同时考虑经验误差和结构误差
• C4.5悲观剪枝，仅考虑经验误差，一般会加入一个惩罚值来调节从训练集得到的误差率，以抵消出现的偏倚。
• 可以使用二进制对决策树进行编码，最佳的决策树是最小化编码二进制位位数的树
• 组合方法，先剪枝和后剪枝组合使用
• 目前没有发现有一种剪枝方法显著优于其他所有的方法
• 尽管剪枝后，一般树会更紧凑简单，但还是难免有重复(repeittion)和复制(replication)，使得树难以解释。解决方法(1)使用多元划分（基于组合属性的划分）；（2）使用不同形式的知识表示（如规则）。

可伸缩性与决策归纳

已有的决策树算法，比如ID3,C4.5,CART都是为相对较小的数据集设计的，都限制训练元组驻留在内存种。对于无法全部导入内存的大数据挖掘，效率效率低下！！！
解决办法：

• 雨林(RainForest)适应可用的内存量，每个树结点维护AVC-集（结构："属性-值，类标号"），即保存了每个结点种属性的分布情况，大大减小了所需的存储空间，使得实际数据集能够放入内存种。
• 树构造的自助乐观算法(Bootstrapped Optimistic Algorithm for Tree Construction, BOAT)。对原数据集合进行采用构成多个小的采样数据集，每个采样数据集都用于一颗树的训练，将得到的多棵树进行组合得到基于所有实际数据训练得到的树的近似。BOAT使用度量下限，以便检测树对实际树的近似程度。BOAT只需要扫描D两次，传统的决策树每一层都需要扫描一次！BOAT比RainForest快2到3倍。 另一个优点，BOAT支持增量更新。

可视化挖掘

• 基于感知的分类(Perception-based Classification, PBC)，一种基于多维可视化技术的交互方法，允许用户在构建树的同时加上关于数据的背景知识。[3]

research issues [1]

• stable tree: the resubstitution error rate should approximate the leave-one-out-validated error rate, suggesting that the tree is of the 'right' size.
• decomposing complex trees: such as the ensemble classifier, we can use simpler tree as the week classifier to construct a powerful classifier.

reference：
[1] Wu X, Kumar V, Quinlan J R, et al. Top 10 algorithms in data mining[J]. Knowledge and information systems, 2008, 14(1): 1-37.
[2] 统计学习方法：李航
[3] 数据挖掘概念与技术（Jiawei Han）
[4] 机器学习实战（Peter Harrington）
[5] 机器学习-周华志