深入理解决策树算法
引言
决策树(Decision Tree)是机器学习中一种经典的分类与回归算法。本文主要讨论用于分类的决策树。决策树模型呈树形结构，在分类问题中，决策树模型可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的剪枝。
基本原理
模型结构
决策树由结点(Node)和有向边(Directed Edge)组成。结点有两种类型：内部结点(Internal Node)和叶结点(Leaf Node)。内部结点表示特征或属性，叶结点表示一个类别，有向边代表了划分规则。
决策树从根结点到子结点的的有向边代表了一条路径。决策树的路径是互斥并且是完备的。
用决策树分类时，对样本的某个特征进行测试，根据测试结果将样本分配到树的子结点上。此时每个子结点对应该特征的一个取值。递归地对样本测试，直到该样本被划分叶结点。最后将样本分配为叶结点所属的类。
条件概率分布
决策树将特征空间划分为互不相交的单元，在每个单元定义一个类的概率分布，这就构成了一个条件概率分布。
通俗来讲，在训练过程中，我们学习构建的决策树（规则）会将训练样本划分在不同的叶子节点中，每个叶子节点所代表的类别就是该叶子节点中数量最多的样本类别，当然在某些场景下，我们会考虑训练样本的权重，来定义叶子节点代表的类别。
学习过程
决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树（即能对训练数据进行正确分类的决策树）可能有多个，也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集己经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。
以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更髙的结点，然后将父结点或更高的结点改为新的叶结点。
如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。
可以看出，决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程。由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。
决策树学习常用的算法有ID3、C4.5与CART，下文结合这些算法分别叙述决策树学习的特征选择、决策树的生成和剪枝过程。
特征选择
特征选择在于选取对训练数据具有分类能力的特征。这样可以提髙决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。
通常特征选择的准则是信息增益或信息增益比。
信息增益
熵越大，随机变量的不确定性就越大。从定义可验证：
当随机变量只取两个值，例如1、0时，即X的分布为：
熵为：
设有随机变量(X, Y)，其联合概率分布为：
条件熵
表示在己知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵(Conditional Entropy)
，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：
这里，
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵(Empirical Entropy)和经验条件熵(Empirical Conditional Entropy)。此时，如果有0概率，令
信息增益(Information Gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
