决策树算法是解决分类问题的另一种方法。与基于概率推断的朴素贝叶斯分类器和逻辑回归模型不同，决策树算法采用树形结构，使用层层推理来实现最终的分类。与贝叶斯分类器相比，决策树的优势在于构造过程无需使用任何先验条件，因而适用于探索式的知识发现。

决策树的分类方法更接近人类的判断机制，这可以通过买房的实例说明。

面对眼花缭乱的房源，普通人优先考虑的都是每平方米的价格因素，价格不贵就买，价格贵了就不买。在价格合适的前提下，面积就是下一个待确定的问题，面积不小就买，面积小了就不买。如果面积合适，位置也是不容忽视的因素，单身业主会考虑房源离工作地点的远近，离单位近就买，离单位远就不买；为人父母的则要斟酌是不是学区房，是学区房就买，不是学区房就不买。如果位置同样称心，就可以再根据交通是否便捷、物业是否良好、价格是否有优惠等条件进一步筛选，确定最后的购买对象。

前面的例子模拟了一套购房策略。在这套策略中，业主对每个可选房源都要做出“买”与“不买”的决策结果，而“每平米价格”、“房屋面积”、“学区房”等因素共同构成了决策的判断条件，在每个判断条件下的选择表示的是不同情况下的决策路径，而每个“买”或是“不买”的决定背后都包含一系列完整的决策过程。决策树就是将以上过程形式化、并引入量化指标后形成的分类算法。

决策树是一个包含根节点、内部节点和叶节点的树结构，其根节点包含样本全集，内部节点对应特征属性测试，叶节点则代表决策结果。从根节点到每个叶节点的每条路径都对应着一个从数据到决策的判定流程。使用决策树进行决策的过程就是从根节点开始，测试待分类项的特征属性，并按照其值选择输出的内部节点。当选择过程持续到到达某个叶节点时，就将该叶节点存放的类别作为决策结果。

由于决策树是基于特征对实例进行分类的，因而其学习的本质是从训练数据集中归纳出一组用于分类的“如果…… 那么……”规则。在学习的过程中，这组规则集合既要在训练数据上有较高的符合度，也要具备良好的泛化能力。决策树模型的学习过程包括三个步骤：特征选择、决策树生成和决策树剪枝。

特征选择决定了使用哪些特征来划分特征空间。在训练数据集中，每个样本的属性可能有很多个，在分类结果中起到的作用也有大有小。因而特征选择的作用在于筛选出与分类结果相关性较高，也就是分类能力较强的特征。理想的特征选择是在每次划分之后，分支节点所包含的样本都尽可能属于同一个类别。

在特征选择中通常使用的准则是信息增益。机器学习中的信息增益就是通信理论中的互信息，是信息论的核心概念之一。信息增益描述的是在已知特征后对数据分类不确定性的减少程度，因而特征的信息增益越大，得到的分类结果的不确定度越低，特征也就具有越强的分类能力。根据信息增益准则选择特征的过程，就是自顶向下进行划分，在每次划分时计算每个特征的信息增益并选取最大值的过程。信息增益的计算涉及信源熵和条件熵的公式，这在前面的专栏内容中有所涉及，在此就不重复了。

信息增益的作用可以用下面的实例来定性说明。

在银行发放贷款时，会根据申请人的特征决定是否发放。假设在贷款申请的训练数据中，每个样本都包含年龄、是否有工作、是否有房产、信贷情况等特征，并根据这些特征确定是否同意贷款。一种极端的情形是申请人是否有房产的属性取值和是否同意贷款的分类结果完全吻合，即在训练数据中，每个有房的申请人都对应同意贷款，而每个没房的申请人都对应不同意贷款。这种情况下，“是否有房产”这个特征就具有最大的信息增益，它完全消除了分类结果的不确定性。在处理测试实例时，只要根据这个特征就可以确定分类结果，甚至无需考虑其他特征的取值。

相比之下，另一种极端的情形是申请人的年龄和是否同意贷款的分类结果可能完全无关，即在训练数据中，青年 / 中年 / 老年每个年龄段内，同意贷款与不同意贷款的样本数目都大致相等。这相当于分类结果在年龄特征每个取值上都是随机分布的，两者之间没有任何规律可言。这种特征的信息增益很小，也不具备分类能力。一般来说，抛弃这样的特征对决策树学习精度的影响不大。

在最早提出的决策树算法——ID3 算法中，决策树的生成就利用信息增益准则选择特征。ID3 算法构建决策树的具体方法是从根节点出发，对节点计算所有特征的信息增益，选择信息增益最大的特征作为节点特征，根据该特征的不同取值建立子节点；对每个子节点都递归调用以上算法生成新的子节点，直到信息增益都很小或没有特征可以选择为止。

ID3 算法使用的是信息增益的绝对取值，而信息增益的运算特性决定了当属性的可取值数目较多时，其信息增益的绝对值将大于取值较少的属性。这样一来，如果在决策树的初始阶段就进行过于精细的分类，其泛化能力就会受到影响，无法对真实的实例做出有效预测。

为了避免信息增益准则对多值属性的偏好，ID3 算法的提出者在其基础上提出了改进版，也就是 C4.5 算法。C4.5 算法不是直接使用信息增益，而是引入“信息增益比”指标作为最优划分属性选择的依据。信息增益比等于使用属性的特征熵归一化后的信息增益，而每个属性的特征熵等于按属性取值计算出的信息熵。在特征选择时，C4.5 算法先从候选特征中找出信息增益高于平均水平的特征，再从中选择增益率最高的作为节点特征，这就保证了对多值属性和少值属性一视同仁。在决策树的生成上，C4.5 算法与 ID3 算法类似。

无论是 ID3 算法还是 C4.5 算法，都是基于信息论中熵模型的指标实现特征选择，因而涉及大量的对数计算。另一种主要的决策树算法 CART 算法则用基尼系数取代了熵模型。

CART 算法的全称是分类与回归树（Classification and Regression Tree），既可以用于分类也可以用于回归。假设数据中共有 KK