引言

决策树（Decision Tree）是一种有监督学习算法，常用于分类和回归。本文仅讨论分类问题。

决策树.png

一、决策树模型

决策树模型是运用于分类以及回归的一种树结构。决策树由节点和有向边组成，一般一棵决策树包含一个根节点、若干内部节点和若干叶节点。决策树的决策过程需要从决策树的根节点开始，待测数据与决策树中的特征节点进行比较，并按照比较结果选择选择下一比较分支，直到叶子节点作为最终的决策结果。

内部节点：对应于一个属性测试。每个内部节点为一个判断条件，并且包含数据集中满足从根节点到该节点所有条件的数据的集合。根据内部结点的判断条件测试结果，内部节点对应的数据的集合别分到两个或多个子节点中
叶节点：叶节点为最终的类别，被包含在该叶节点的数据属于该类别，即对应于决策结果
根节点包：包含数据集中的所有数据的集合
每个节点包括的样本集合根据属性测试的结果被划分到子节点中；
根节点到每个叶节点的路径对应对应了一个判定测试路径；

简而言之，决策树是一个利用树的模型进行决策的多分类模型

二、决策树学习

1.特征选择

为了找到最优的划分特征，我们需要先了解一些信息论的知识：

纯度
信息熵(information entropy)
信息增益(information gain)
信息增益率(information gain ratio)
基尼指数(Gini index)

纯度：
你可以把决策树的构造过程理解成为寻找纯净划分的过程。数学上，我们可以用纯度来表示，纯度换一种方式来解释就是让目标变量的分歧最小

信息熵：表示信息的不确定度
在信息论中，随机离散事件出现的概率存在着不确定性。为了衡量这种信息的不确定性，信息学之父香农引入了信息熵的概念.
当不确定性越大时，它所包含的信息量也就越大，信息熵也就越高。
信息熵越大，纯度越低。当集合中的所有样本均匀混合时，信息熵最大，纯度最低

信息熵.png

经典的 “不纯度”的指标有三种，分别是信息增益（ID3 算法）、信息增益率（C4.5 算法）以及基尼指数（Cart 算法）
信息增益：
信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。
信息增益率
信息增益率 = 信息增益 / 属性熵
基尼指数
基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。
即基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率
基尼系数的性质与信息熵一样：度量随机变量的不确定度的大小；
G 越大，数据的不确定性越高；
G 越小，数据的不确定性越低；
G = 0，数据集中的所有样本都是同一类别
详细参考：机器学习——基尼指数

2.决策树生成

决策树生成.png

2.1 ID3

ID3 算法是建立在奥卡姆剃刀（用较少的东西，同样可以做好事情）的基础上：越是小型的决策树越优于大的决策树
ID3算法的核心是在决策树各个节点上根据信息增益来选择进行划分的特征，然后递归地构建决策树。算法采用自顶向下的贪婪搜索遍历可能的决策树空间。

具体方法：

1.从根节点开始，初始化特征集合和数据集合
2.计算数据集合信息熵和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点；
3.由该特征的不同取值建立子节点；更新数据集合和特征集合（删除上一步使用的特征，并按照特征值来划分不同分支的数据集合）；
4.重复 2，3 两步，若子集值包含单一特征，则为分支叶子节点，即到所有特征的信息增益都很小或者没有特征可以选择为止，得到最终的决策树

ID3的局限：

没有剪枝，容易过拟合；
采用信息增益作为选择最优划分特征的标准，然而信息增益会偏向那些取值较多的特征，类似“编号”的特征其信息增益接近于 1(这也是C4.5采用信息增益率的原因)；
只能用于处理离散分布的特征；
没有考虑缺失值

2.2 C4.5

C4.5与ID3相似，但大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准。

C4.5的实现基于ID3的改进：

用信息增益率来选择划分特征，克服了用信息增益选择的不足
在构造树的过程中进行剪枝（引入悲观剪枝策略进行后剪枝）；
将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；
缺失值进行处理
1.在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）答：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；
2.选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）答：样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

信息增益率对可取值较少的特征有所偏好（分母越小，整体越大），因此 C4.5 并不是直接用增益率最大的特征进行划分，而是使用一个启发式方法：先从候选划分特征中找到信息增益高于平均值的特征，再从中选择增益率最高的。

C4.5的局限：

剪枝策略可以再优化；
C4.5 用的是多叉树，用二叉树效率更高；
C4.5 只能用于分类；
C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

2.3 CART

ID3 和 C4.5 生成的决策树分支、规模都比较大，CART 算法的二分法可以简化决策树的规模，提高生成决策树的效率。
CART(classificationandregressiontree),分类回归树算法，既可用于分类也可用于回归，在这一部分我们先主要将其分类树的生成。区别于ID3和C4.5,CART假设决策树是二叉树，内部节点特征的取值为“是”和“否”，左分支为取值为“是”的分支，右分支为取值为”否“的分支。这样的决策树等价于递归地二分每个特征，将输入空间(即特征空间)划分为有限个单元。
CART的分类树用基尼指数来选择最优特征的最优划分点，具体过程如下

1.从根节点开始，对节点计算现有特征的基尼指数，对每一个特征，例如A，再对其每个可能的取值如a,根据样本点对A=a的结果的”是“与”否“划分为两个部分，利用Gini(D,A=a)进行计算；
2.在所有可能的特征A以及该特征所有的可能取值a中，选择基尼指数最小的特征及其对应的取值作为最优特征和最优切分点。然后根据最优特征和最优切分点，将本节点的数据集二分，生成两个子节点
3.对两个字节点递归地调用上述步骤，直至节点中的样本个数小于阈值，或者样本集的基尼指数小于阈值，或者没有更多特征后停止；
4.生成CART分类树；

3.决策树剪枝

剪枝就是给决策树瘦身，这一步想实现的目标就是，不需要太多的判断，同样可以得到不错的结果。之所以这么做，是为了防止“过拟合”（Overfitting）现象的发生。
过拟合：指的是模型的训练结果“太好了”，以至于在实际应用的过程中，会存在“死板”的情况，导致分类错误。
欠拟合：指的是模型的训练结果不理想.
剪枝的方法：

预剪枝：在决策树构造时就进行剪枝。方法是，在构造的过程中对节点进行评估，如果对某个节点进行划分，在验证集中不能带来准确性的提升，那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。那么怎么测量泛化精度，就是留出一部分训练数据当做测试集，每次划分前比较划分前后的测试集预测精度。
- 优点：降低了过拟合风险，降低了训练所需的时间。
- 缺点：预剪枝是一种贪心操作，可能有些划分暂时无法提升精度，但是后续划分可以提升精度。故产生了欠拟合的风险。
后剪枝：在生成决策树之后再进行剪枝。通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。方法是：用这个节点子树的叶子节点来替代该节点，类标记为这个节点子树中最频繁的那个类。
- 优先：降低过拟合风险，降低欠拟合风险，决策树效果提升比预剪枝强
- 缺点：时间开销大得多

ID3、C4.5、CART对比

参考：【机器学习】决策树（上）——ID3、C4.5、CART（非常详细）

划分标准的差异：ID3 使用信息增益偏向特征值多的特征，C4.5 使用信息增益率克服信息增益的缺点，偏向于特征值小的特征，CART 使用基尼指数克服 C4.5 需要求 log 的巨大计算量，偏向于特征值较多的特征。
使用场景的差异：ID3 和 C4.5 都只能用于分类问题，CART 可以用于分类和回归问题；ID3 和 C4.5 是多叉树，速度较慢，CART 是二叉树，计算速度很快；
样本数据的差异：ID3 只能处理离散数据且缺失值敏感，C4.5 和 CART 可以处理连续性数据且有多种方式处理缺失值；从样本量考虑的话，小样本建议 C4.5、大样本建议 CART。C4.5 处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而 CART 本身是一种大样本的统计方法，小样本处理下泛化误差较大；
样本特征的差异：ID3 和 C4.5 层级之间只使用一次特征，CART 可多次重复使用特征；
剪枝策略的差异：ID3 没有剪枝策略，C4.5 是通过悲观剪枝策略来修正树的准确性，而 CART 是通过代价复杂度剪枝。

更多模型不断更新中。。。。

决策树是什么东东？