决策树（Decision Tree）是机器学习中非常经典的算法之一，但其核心思想通俗易懂，与人类日常的决策逻辑高度相似。在分类与回归任务中，决策树均能有效应用：处理分类问题时称为分类树，处理回归问题时则称为回归树。
一、决策树的结构详解
顾名思义，决策树在逻辑结构上呈现为树形，由节点和分支组成。一棵标准的决策树包含一个根节点、多个内部节点以及多个叶节点。
根节点包含全部训练样本，从根节点到每个叶节点的路径代表一条完整的判定测试序列。内部节点对应一个特征或属性，每个内部节点设有一个判断条件，同时存储从根节点经过逐层筛选后满足所有条件的数据子集。根据属性的测试结果，数据被划分到两个或多个子节点中。叶节点则代表最终的决策结果，即类别。若某个样本落入某个叶节点，则被判定为该类别。
下图里，圆和方框分别代表内部节点和叶节点。
简而言之，决策树是利用树形结构进行预测的模型，本质上构建了对象属性与对象值之间的映射关系，结构直观，易于理解。
构建决策树的核心目标是生成一棵泛化能力强的树，即能够高效、准确地处理未见样本的预测任务。
二、决策树的优缺点分析
决策树的优点不少，整理一下：
- 对背景知识要求较低，计算复杂度不高，能够自动学习出决策规则；
- 属于有监督学习算法，依赖带有标签的训练样本；
- 对中间缺失值不敏感，能容忍一定程度的样本缺失；
- 可解释性强，有时甚至比线性回归更易于理解；
- 与传统的回归和分类方法相比，决策树更贴近人类决策的思维习惯；
- 能够通过图形直观展示，非专业人士也能轻松理解；
- 可以直接处理定性预测变量，无需创建哑变量；
- 单棵决策树的预测准确性相对较弱，但借助集成学习方法（如随机森林）组合多棵决策树，可以显著提升预测性能。
三、决策树的生成过程
决策树的生成是一个自顶向下的递归过程。其基本思路是：以信息熵作为度量，构建一棵使熵值下降最快的树，直至叶节点处的熵降为零。
在决策树算法中，有三种情况会导致递归返回：
- 当前节点包含的样本全部属于同一类别，无需继续划分。
- 当前属性集为空，无法进一步划分。此时将当前节点标记为叶节点，其类别设定为所含样本最多的类别。这本质上属于“有样本但无属性可用”的情形，利用了当前节点的后验分布。
- 当前节点包含的样本集合为空，无法继续划分。同样需要将当前节点标记为叶节点，但类别应设置为其父节点中样本最多的类别。这属于“有属性但无样本”的情形，利用了父节点的先验分布。