所属模块：
M2 · 经典机器学习 (Classical Machine Learning)| 专题分类：决策树 (Decision Trees)| 难度等级：Hard
一、核心一句话结论 (One-Sentence Summary)
缺失值可用代理分裂（CART）、按缺失率分流、或缺失指示变量；类别特征可用 one-hot、目标编码、或原生类别分裂（LightGBM/CatBoost）。
Modern tree models (LightGBM, XGBoost) handle missing values natively by routing them to whichever child branch maximizes impurity gain, and handle categoricals natively via histogram integer binning and optimal Fisher splits.
二、核心考点要义 (Key Insights)
- 📌 目标编码需交叉拟合防泄漏
- 📌 高基数类别 → 哈希/嵌入/计数编码
English Insights:
– Missing Values in XGBoost/LightGBM: Treats missingness as a valid signal; during training, tests routing all missing values to left vs right branch, setting the default path to maximum gain.
– Categorical Handling – One-Hot Encoding: Inefficient for high cardinality (sparse splits, unbalanced deep trees).
– Categorical Handling – Target Encoding: Encodes categories as mean target values with Bayesian smoothing; risks severe target leakage if not out-of-fold.
– Native Categorical Splits (LightGBM): Sorts categories by target mean and evaluates optimal subset partition in $O(K log K)$ time via Fisher’s exact theorem.
三、核心数学原理与机理推导 (Mathematical Principles & Derivation)
$$text{surrogate split}: text{用最相似特征替代}$$
缺失值处理：① 代理分裂（CART）——对每个主分裂，额外学若干’代理分裂’（用与主特征最相关的其他特征），当主特征缺失时用代理分裂决定走向；优点是保留样本且利用特征相关性，缺点是计算复杂。② 默认方向（XGBoost/LightGBM）——训练时为每个分裂学习’缺失样本走左还是走右’（按哪边损失更小），推理时缺失样本按该默认方向走；实现简单且效果常优于简单填充。③ 填充 + 指示变量——用均值/中位数/模型预测填充，并额外加一个’是否缺失’的二值特征（当缺失有信息时有效）。④ 按缺失分流——把缺失作为一个独立的类别分支。
📖 查看英文严格数学推导 (English Mathematical Derivation)
LightGBM optimal categorical split derivation: For binary classification with $K$ categories, finding the optimal subset split among $2^{K-1}-1$ possible partitions is an NP-hard combinatorial problem. Fisher (1958) proved that if categories are sorted by the ratio of positive targets: $frac{sum_{y in c_k} y}{N_{c_k}}$, the optimal split threshold on this 1D sorted sequence is mathematically guaranteed to be the optimal subset split in the original categorical space! LightGBM sorts the histogram bins in $O(Klog K)$ time, turning an exponential $2^K$ search into a simple linear scan over $K$ thresholds.
四、工业级落地权衡与工程考量 (Industrial Trade-offs)
类别特征处理：① one-hot——适合低基数（<10–20 类），高基数会导致维度爆炸与稀疏，且树在每个 one-hot 列上只能做’是/否’分裂（效率低）。② 目标编码（target/mean encoding）——用类别对应的目标均值替代，需交叉拟合（在 K 折内用其他折的均值编码本折，防止标签泄漏）+ 平滑（向全局均值收缩，尤其对低频类别）。③ 原生类别分裂（LightGBM/CatBoost）——LightGBM 用’按类别目标均值排序后分裂’（many-vs-many 分裂），CatBoost 用 ordered target statistics（按时间/随机顺序只用’过去’样本统计）从原理上避免泄漏，且用对称树加速。④ 嵌入——深度模型中对高基数类别学嵌入向量（如推荐系统中的 item embedding）。⑤ 计数/频率编码——用类别出现频次作为特征，简单且不泄漏，但信息量有限。
⚙️ 查看英文落地权衡分析 (English Systems & Trade-offs)
Missing value strategies: (1) Mean/Median Imputation: Destroys missingness information and distorts feature variance. (2) Missingness Indicator Flag: Adds binary column $mathbb{I}(x text{ is null})$; effective for linear models. (3) Native Tree Routing: Superior in XGBoost/LightGBM because it captures informative missingness (e.g. Failure to provide annual income correlates with credit risk).
五、常见面试避坑陷阱 (Common Pitfalls & Traps)
- ⚠️ 对高基数类别用 one-hot（维度爆炸 + 分裂低效）
- ⚠️ 目标编码不做交叉拟合（严重标签泄漏）
English Pitfalls:
– One-hot encoding high-cardinality features (e.g. ZIP_Code with 5,000 levels), which creates extremely sparse, deep, unbalanced trees.
– Computing Target Encoding globally without K-fold out-of-fold splitting (causes catastrophic label leakage).
六、高频深度面试追问与预测 (Follow-Up Questions)
- 目标编码如何防止泄漏？
- How does Fisher’s 1958 theorem prove that sorting categories by target mean guarantees the globally optimal binary partition?
- 为什么 LightGBM 能直接处理类别特征？
- How does CatBoost prevent target leakage in categorical encoding using online target statistics ordered by time?
七、知识图谱对齐 (Knowledge Graph Anchor)
- 🔗 关联底层卡片：
CART 决策树、Gini 指数、信息增益比与剪枝策略(CART Decision Trees, Gini Impurity & Pruning) - 🗺️ 知识图谱模块：
经典机器学习思维导图
🔬 算法科学家与机器学习深度考察全量题库 (Science Depth)
本题收录于 TalentMe 算法科学家深度考察真题库 (Science Depth)。全库共 856 道硬核考点，深度覆盖数学统计、经典ML、深度学习、Transformer、大语言模型、多模态、推荐系统与 MLOps。支持 Jev 面经智能匹配、一键离线单文件 HTML 手册导出并直连 Obsidian 本地记忆。