决策树与集成

Decision Tree · Random Forest · Gradient Boosting

问题定义

决策树是一种基于树结构的监督学习算法，通过递归地将特征空间划分为子空间来构建预测模型。集成学习通过组合多个弱学习器来提高预测性能，核心问题包括：如何构建高质量的决策树、如何避免过拟合、如何有效地组合多个模型。

核心算法

决策树算法

ID3 算法

基于信息增益选择最佳分裂特征，适用于分类问题，使用熵来度量信息不确定性。

信息熵：H(S) = -Σ p(i) log₂ p(i)
信息增益：IG(S, A) = H(S) - Σ (|S_v|/|S|) H(S_v)

C4.5 算法

ID3 的改进版本，使用信息增益比来选择特征，避免偏向取值较多的特征，支持连续值和缺失值处理。

CART 算法

使用基尼指数作为分裂准则，生成二叉树，同时支持分类和回归问题。

基尼指数：Gini(S) = 1 - Σ p(i)²

集成学习方法

Bagging（自助聚合）

通过 bootstrap 采样创建多个训练集，训练多个模型后投票或平均。随机森林是 Bagging 的典型应用。

随机森林

在 Bagging 基础上，每次分裂时随机选择特征子集，进一步降低模型方差，提高泛化能力。

Boosting（提升）

通过序列训练弱学习器，每次关注前一轮错误分类的样本，逐步提高模型性能。

梯度提升树 (GBT)

使用梯度下降优化损失函数，每次添加一个新的决策树来拟合当前模型的残差。

XGBoost

梯度提升的优化实现，支持正则化、缺失值处理、并行计算，在竞赛中表现优异。

LightGBM

基于直方图算法和叶子节点分裂策略，训练速度快，内存占用低，适用于大规模数据集。

CatBoost

处理类别特征的能力强，避免过拟合，支持自动特征组合，适用于包含大量类别特征的场景。

开源实现

scikit-learn Decision Trees

提供 DecisionTreeClassifier、DecisionTreeRegressor、RandomForestClassifier、GradientBoostingClassifier 等实现。

XGBoost

优化的梯度提升框架，支持正则化、并行计算、缺失值处理，在 Kaggle 竞赛中广泛使用。

LightGBM

微软开发的高效梯度提升框架，基于直方图算法，训练速度快，内存占用低。

CatBoost

Yandex 开发的梯度提升库，处理类别特征能力强，支持自动特征组合。

应用场景

参考文献