决策树学习是一种监督学习方法，通过递归地将训练数据划分为若干子集来构建预测模型。生成的树包含用于检验输入特征的内部节点、表示检验结果的分支，以及给出预测结果的叶节点。它既支持预测类别的分类任务，也支持预测数值的回归任务。在机器学习中，决策树是一种非参数方法：它不要求输入与输出之间具有预先设定的线性关系。(scikit-learn.org)
表示与预测
决策树表示一系列条件判断。数值型检验通常将某个特征与阈值进行比较，例如判断测量值是否超过指定数值。类别型检验可以区分单个类别或若干类别组成的组。预测从根节点开始，沿着相应的分支前进，直到到达叶节点。因此，每条从根节点到叶节点的路径都可以表示为一条“若……则……”规则，其中的各项条件须同时满足。(storm.cis.fordham.edu)
对于分类任务，叶节点通常将到达该节点的训练样本中出现频率最高的类别作为预测结果。它也可以根据这些样本中各类别所占的比例来估计类别概率，必要时还会考虑样本权重。对于采用均方误差的回归任务，叶节点预测目标值的均值；若采用绝对误差损失，则预测中位数。因此，预测规则取决于所选的损失函数。(sklearn.org)
学习过程与划分准则
大多数成熟的决策树构建方法采用递归的贪心划分。在每个节点，算法评估候选检验，选择局部效果较好的划分，然后在划分得到的子集中重复这一过程。这种局部搜索通常无法得到全局最优的树。当满足某项停止条件时，构建过程便会结束，例如达到深度上限、样本不足，或目标值已足够一致。(scikit-learn.org)
分类任务中的划分通常使用不纯度指标来评估。对于各类别所占比例为 (p_1,\ldots,p_K) 的节点，常用指标为：
[ G=1-\sum_{k=1}^{K}p_k^2, \qquad H=-\sum_{k=1}^{K}p_k\log_2 p_k. ]
其中，(G) 为基尼不纯度，(H) 为信息熵，并约定 (0\log 0) 为零。当节点中只有一个类别时，两者均为零。评估候选划分时，会将父节点的不纯度与各子节点按样本权重加权后的不纯度进行比较。熵的减少量称为信息增益。(scikit-learn.org)
回归树则评估划分在多大程度上减少了数值预测误差。在平方误差损失下，选择能够减小节点内目标值方差的划分，等价于减少目标值相对于各自子节点均值的平方偏差。其他准则可以支持不同的优化目标，包括绝对误差和泊松偏差。(scikit-learn.org)
主要算法类别
与 J. 罗斯·昆兰密切相关的 ID3 使用信息增益选择类别型属性，并可生成多路分支。昆兰于 1986 年发表的论文《决策树归纳》（Induction of Decision Trees）详细介绍了 ID3，并探讨了用于处理含噪声和不完整信息的扩展方法。该论文还讨论了信息增益倾向于偏好具有较多可能结果的检验这一问题。(doi.org)
C4.5 对 ID3 方法进行了扩展，其中一项重要改进是通过阈值检验支持连续值属性。分类与回归树（CART）既支持类别型目标，也支持数值型目标，并构建二叉树。这些算法类别在候选划分的处理方式、目标类型和简化过程上有所不同；因此，“决策树”指的是一类模型，而不是某一种具有唯一明确规定的学习算法。(scikit-learn.org)
复杂度控制与评估
在限制较少的情况下生长出的决策树可能会拟合训练样本中的噪声和细微的不规则变化，从而造成过拟合。预剪枝通过最大深度、叶节点最小样本数或最小不纯度减少量等限制来约束树的生长。后剪枝则在构建出较大的树之后移除分支。这两种方法都通过限制模型复杂度起到正则化作用。(scikit-learn.org)
代价复杂度剪枝通过以下形式的目标函数，在拟合程度与树的规模之间进行权衡：
[ R_\alpha(T)=R(T)+\alpha L(T), ]
其中，(R(T)) 衡量训练误差或加权的叶节点不纯度，(L(T)) 表示叶节点数量，(\alpha\geq0) 控制复杂度惩罚的强度。惩罚越大，就越倾向于选择较小的树。剪枝会产生一组候选子树，可以根据它们在留出数据上的表现进行比较，而不只是依据训练数据上的拟合程度。(scikit-learn.org)
深度、叶节点样本数限制和剪枝强度都属于超参数。通常使用验证集或交叉验证来选择这些参数，并在模型选择完成后，用独立的测试集估计性能。这一区分十分重要，因为反复根据测试结果选择配置，会使评估数据中的信息影响模型。如果在划分评估数据之前，就利用全部数据拟合预处理步骤或执行特征选择，而不是仅在训练部分中进行，也可能引入数据泄漏（机器学习）。(scikit-learn.org)
优势、局限与集成方法
小型决策树可以直接查看，并转换为规则。对数值特征进行检验的决策树通常不需要特征缩放，因为其检验依赖于特征值的顺序，而非距离。不过，大型决策树较难解释，训练样本的微小变化也可能导致树的结构出现显著差异。传统回归树给出分段常数预测，无法自然地将连续变化趋势外推到已观测目标值的范围之外。(scikit-learn.org)
决策树的不稳定性推动了集成方法的应用。自助聚合将多个在重采样数据集上训练的模型组合起来。随机森林还会在构建决策树时考虑随机选取的特征子集，从而降低树之间的相关性，并往往能降低预测方差。梯度提升依次构建决策树，依据损失函数改进加性模型。这些方法仍以决策树作为组成学习器，但其组合预测结果难以直接用一条易于理解的规则路径来表示。(scikit-learn.org)