决策树的基本原理是什么？是怎么构建的？

简化版

决策树 是一种树形结构的分类/回归模型：从根节点开始，每个内部节点是对某个特征的一次判断（如「年龄 < 30？」），按判断结果把样本分到不同分支，一路走到叶子节点得到预测结果。构建过程是递归地贪心选择「最好的分裂特征和分裂点」——每次都挑一个能让子节点「最纯」（同类样本尽量聚在一起）的划分，用信息增益、增益比或基尼指数衡量「纯度提升」。递归到节点足够纯、或满足停止条件为止，最后往往还要剪枝防过拟合。它的最大优点是直观、可解释、不需要特征缩放。

详细版

结构：

          [年龄<30?]          ← 根节点（对特征判断）
         /          \
     是 /            \ 否
   [收入高?]        叶子:不买    ← 内部节点 / 叶子
   /     \
 叶子:买  叶子:不买

内部节点：对一个特征的测试。
分支：测试的每种结果。
叶子节点：最终类别（分类）或数值（回归）。

构建（递归划分，贪心）：

BuildTree(数据集 D):
  1. 若 D 已足够纯 / 满足停止条件 → 变叶子，返回
  2. 遍历所有特征和候选分裂点，选「纯度提升最大」的划分
  3. 按最优划分把 D 分成子集
  4. 对每个子集递归 BuildTree

分裂标准（衡量纯度提升）：

算法	标准
ID3	信息增益
C4.5	信息增益比
CART	基尼指数（分类）/ 平方误差（回归）

停止条件： 节点样本全同类、无可用特征、样本数/深度达阈值等。之后常做剪枝防过拟合。

完整版教学

一、决策树在做什么——一串「if-else」判断

决策树本质是把预测过程组织成一棵「问题树」：从根节点开始问一个关于特征的问题，根据答案往下走一个分支，再问下一个问题，直到走到叶子，叶子上写着答案。

比如判断「要不要给某人放贷」：

有房吗？──否──→ 收入>1万？──否──→ 拒绝
   │                  │
   是                 是──→ 批准
   ↓
  批准

这套流程和人类做决策的方式高度一致，所以决策树极其直观、可解释——你能清楚看到「因为满足了 A 和 B 条件，所以判为某类」。这是它相对于逻辑回归、SVM 等「黑箱式加权」模型最大的特点。

二、核心思想：递归地把数据「分纯」

训练一棵决策树，就是决定「每个节点该问哪个特征、以什么为界分裂」。指导原则只有一个：每次分裂，都要让分出来的子节点尽量「纯」——即每个子集里的样本尽量属于同一类。

想象一个装着红蓝两色球的盒子（不纯，混在一起）。决策树每次分裂就像找一个规则把球倒进两个新盒子，目标是让每个新盒子里尽量只剩一种颜色。一直分到每个盒子基本纯色，就不用再分了——那些纯盒子就是叶子。

「纯不纯」需要量化，这就引出纯度指标（信息熵、基尼指数），而「分裂让纯度提升多少」就是选特征的依据（信息增益等，详见分裂标准专题）。

三、构建流程：贪心 + 递归

决策树用贪心策略递归构建：

BuildTree(数据集 D, 特征集 A):
  1. 如果 D 中样本全属同一类 → 生成叶子，标记为该类，返回
  2. 如果 A 为空 或 D 在 A 上取值都相同 → 生成叶子，标记为 D 中最多的类，返回
  3. 从 A 中选出「分裂后纯度提升最大」的最优特征 a*
  4. 对 a* 的每个取值（或每个分裂点），生成一个分支，把 D 划分成子集 Dv
  5. 对每个子集 Dv，递归 BuildTree(Dv, A - {a*})

两个关键词：

贪心：每一步只选「当前」纯度提升最大的分裂，不考虑全局最优。所以决策树得到的是局部最优的树，不保证全局最优（找全局最优是 NP 难的）。
递归：对每个子集重复同样的过程，自顶向下把树长出来。

四、什么时候停止分裂

不能一直分到底（那会严重过拟合），要有停止条件。常见的：

节点内样本全属同一类（已纯，无需再分）。
没有可用特征了，或所有样本在剩余特征上取值都相同。
节点样本数少于阈值（min_samples_split）。
树深度达到上限（max_depth）。
分裂带来的纯度提升小于阈值（提升太小不值得分）。

这些其实就是预剪枝参数——通过提前停止控制树的复杂度。

五、连续特征和缺失值怎么办（简述）

连续特征：不能像离散特征那样每个取值一个分支，而是找一个阈值 t，按「特征 ≤ t / > t」二分（如「年龄 ≤ 30」）。候选阈值一般取相邻样本值的中点，遍历选最优（详见连续值处理专题）。
缺失值：C4.5 等算法能按比例把缺失样本分到各分支、并在选特征时按缺失比例折算增益（详见缺失值处理专题）。

六、决策树为什么不需要特征缩放

这是高频追问。精确轴对齐树的节点做「特征值与阈值比较」，正比例缩放或严格单调变换保持样本顺序，因此存在产生相同划分的对应阈值，通常不需要为距离或梯度做标准化。但“完全免疫”过于绝对：有限精度、直方图分桶、近似算法、缺失值编码以及非严格单调变换都可能改变候选切分。正确表述是常规树对量纲远不如距离模型敏感，同时必须保证训练和预测预处理一致。

七、优缺点速览与延伸

优点：直观可解释、不需要缩放、能处理数值和类别特征、能捕捉非线性和特征交互、训练/预测快。

缺点：容易过拟合（长得太深就把训练集背下来了，需剪枝）、不稳定（数据小变动可能让树结构大变，高方差）、贪心不保证全局最优、单棵树精度有限。

单棵树在强解释、规则抽取和低延迟场景仍有独立价值；当预测效果优先时，也常把树作为随机森林、GBDT、XGBoost 的基学习器。集成能缓解决策树的高方差或逐步降低偏差，但会增加模型体积、计算量并削弱全局可解释性，因此不是无条件替代单树。

面试回答不能只背优缺点清单，还要把性质连回分裂机制：轴对齐阈值带来非线性表达，也造成阶梯状边界；贪心递归让训练高效，却不保证得到全局最优树。选择单树还是集成，应由解释要求、样本规模、延迟预算与验证集表现共同决定。

八、用六个样本走完一次贪心建树

假设 6 个样本中 3 正 3 负，父节点 Gini 为 0.5。按“是否有房”分裂后，左节点 3 个全正、右节点 3 个全负，加权 Gini 为 0，因此该分裂下降 0.5；如果另一个特征分裂后两边都仍是 2:1，则下降量只有约 0.056。树只选当前节点最优分裂，并不会回溯证明整棵树全局最优。

Gini(parent) = 1 - (3/6)^2 - (3/6)^2 = 0.5
weighted_Gini(best_split) = 3/6*0 + 3/6*0 = 0
gain = 0.5 - 0 = 0.5

对象/方案	核心机制	选择或风险
训练阶段	枚举特征与切分，比较不纯度下降	计算成本集中在找分裂
停止阶段	深度、叶样本数、增益等触发停止	控制模型容量
预测阶段	从根按条件只走一条路径	成本约与路径深度相关

根节点数据 → 选当前最优切分 → 左/右子集递归
                         ├→ 满足停止条件：生成叶子
                         └→ 未满足：继续切分

记忆钩子：决策树训练是局部贪心搜索，预测才是一串确定的 if-else；别把“每步最优”说成“整树最优”。

九、常见误区与追问

误区：训练误差降到 0 就说明树已经学好。 深树可以记住噪声，泛化误差可能同时上升。
误区：决策树只适合分类。 回归树通过最小化叶内平方误差并输出均值预测连续值。
追问：为什么建树通常是贪心的？ 全局搜索所有树结构是组合爆炸问题，局部最优切分更可计算。
追问：叶子输出什么？ 分类树通常输出类别分布或多数类，平方损失回归树输出均值。
追问：预测复杂度怎么估算？ 单样本通常访问一条根到叶路径，近似 O(depth)，不需要遍历全树。

十、加强记忆

决策树 = 一棵「if-else 问题树」：内部节点对特征判断、分支是判断结果、叶子给预测。训练是贪心 + 递归地「把数据分纯」——每次选让子节点纯度提升最大的特征和分裂点（用信息增益/增益比/基尼指数衡量），递归到足够纯或触发停止条件（样本同类、无特征、达深度/样本数阈值）为止，再剪枝防过拟合。连续特征按阈值二分，缺失值可按比例分配。它不需要特征缩放（只比较大小顺序、对单调变换免疫），直观可解释；但单棵树易过拟合、高方差，所以实战靠随机森林（降方差）和 GBDT（降偏差）等集成发挥威力。

简化版

详细版