XGBoost

引言：从二十个问题到机器学习 想象你在玩一个经典游戏——“二十个问题”。你需要通过最多二十个 yes/no 问题，猜出对手心中想的一个物体。聪明的玩家会问这样的问题： “它是活的吗？” “如果活着，它是动物吗？” “如果是动物，它会飞吗？” 每一个问题都将可能的答案空间一分为二，逐步缩小范围，直到锁定目标。这种分而治之的策略，正是决策树算法的核心思想。 决策树是机器学习中最直观、最易于解释的算法之一。从医学诊断到信用评估，从游戏 AI 到推荐系统，决策树及其衍生算法无处不在。它的魅力在于： 可解释性强：决策路径清晰，非技术人员也能理解 非参数化：不需要假设数据的分布形式 处理混合数据：能同时处理数值和类别特征 捕捉非线性关系：通过分层划分，自动学习复杂的决策边界 从1986年 Ross Quinlan 提出 ID3 算法，到今天 XGBoost、LightGBM 在 Kaggle 竞赛中称霸，决策树算法已经走过了近四十年的演进历程。本文将带你从最基本的树结构出发，逐步深入到现代梯度提升框架的数学原理，揭示这一算法的优雅与力量。 第一章：决策树基础 1.1 什么是决策树？ 决策树（Decision Tree）是一种树形结构的预测模型，其中： 内部节点表示对某个特征的测试或判断 分支表示测试的结果 叶节点表示最终的预测结果（类别或数值） 图 1：决策树的基本结构。从根节点开始，根据特征值进行判断，沿着分支走到叶节点得到预测结果。 决策树既可以用于分类（预测离散类别），也可以用于回归（预测连续数值）。前者的代表是 ID3、C4.5、CART（分类树），后者的代表是 CART（回归树）。 1.2 决策树的学习过程 构建决策树的核心问题是：*如何选择每个节点的分裂特征和分裂点？ 这涉及三个关键决策： *1. 特征选择准则 我们需要一个指标来度量分裂的"好坏"。常用的准则包括： 信息增益（Information Gain）：基于信息熵的减少 基尼指数（Gini Index）：基于概率分布的纯度 均方误差（MSE）：用于回归问题 *2. 分裂点选择 对于数值特征，需要确定最优的分裂阈值。通常采用贪婪搜索：遍历所有可能的分裂点，选择使准则最优化的那个。 *3. 停止条件 递归分裂何时停止？常见的停止条件： 节点中样本数少于阈值 节点纯度达到阈值 树深度达到上限 分裂带来的增益小于阈值 1.3 决策树的预测过程 预测一个新样本时，从根节点开始： 检查当前节点的分裂特征 根据样本在该特征上的取值，选择对应的分支 移动到子节点 重复直到到达叶节点 叶节点的标签（分类）或平均值（回归）即为预测结果 时间复杂度为 $O(\log n)$，其中 $n$ 是树的高度。这意味着即使对于大规模数据集，预测速度也非常快。 ...