每日算法 — 使用java实现梯度提升树：GBDT与XGBoost原理

梯度提升树（Gradient Boosting Decision Tree，GBDT）是机器学习领域最经典且应用广泛的集成学习算法之一。XGBoost作为其工业级优化实现，在数据竞赛中屡获佳绩。本文用Java从零实现GBDT核心框架，讲解梯度提升原理、二阶泰勒展开近似目标函数以及正则化策略，包含完整可运行的回归与分类代码。

一、算法原理与数学推导

GBDT的核心思想是串行训练多棵决策树，每棵树学习前面所有树预测残差的梯度方向。设训练集有 n 个样本，损失函数为 L(y, F(x))，当前模型的预测为 F_{m-1}(x)，则第 m 棵树拟合的目标为负梯度：

r_i = -[∂L(y_i, F(x_i)) / ∂F(x_i)]  (i=1,...,n)

XGBoost在此基础上引入二阶泰勒展开，将目标函数近似为：

Obj ≈ Σ_i [g_i * f_t(x_i) + 0.5 * h_i * f_t(x_i)^2] + Ω(f_t)

其中 g_i 为一阶梯度，h_i 为二阶梯度（Hessian），Ω(f_t) 为正则化项，包含叶子节点数 T 和叶子权重 w 的L2惩罚：

Ω(f) = γT + 0.5λΣ_j w_j^2

二、树节点与分裂搜索

import java.util.*;

/**
 * 决策树节点
 */
public class TreeNode {
    public int featureIndex = -1;     // 分裂特征索引
    public double splitValue = Double.NaN; // 分裂阈值
    public double leafValue = Double.NaN;  // 叶子节点预测值
    public TreeNode left = null;
    public TreeNode right = null;
    public boolean isLeaf = false;

    public TreeNode() {}
}

/**
 * 分裂候选结果
 */
public class SplitResult {
    public int featureIndex;
    public double splitValue;
    public double gain;  // 分裂增益
    public double leftWeight;
    public double rightWeight;
    public List<Integer> leftIndices;
    public List<Integer> rightIndices;

    public SplitResult(int featureIndex, double splitValue, double gain,
                       double leftWeight, double rightWeight,
                       List<Integer> leftIndices, List<Integer> rightIndices) {
        this.featureIndex = featureIndex;
        this.splitValue = splitValue;
        this.gain = gain;
        this.leftWeight = leftWeight;
        this.rightWeight = rightWeight;
        this.leftIndices = leftIndices;
        this.rightIndices = rightIndices;
    }
}

三、数据集与梯度计算

/**
 * 训练数据集
 */
public class Dataset {
    public double[][] features;  // [样本数][特征数]
    public double[] labels;      // [样本数]

    public Dataset(double[][] features, double[] labels) {
        this.features = features;
        this.labels = labels;
    }

    public int sampleCount() { return labels.length; }
    public int featureCount() { return features[0].length; }
}

/**
 * 梯度与Hessian计算接口
 */
public interface LossFunction {
    /** 一阶梯度 */
    double[] gradient(double[] pred, double[] label);
    /** 二阶梯度 */
    double[] hessian(double[] pred, double[] label);
    /** 初始预测值 */
    double initPred(double[] label);
    /** 转换为最终输出（如sigmoid） */
    default double transform(double raw) { return raw; }
}

/**
 * 平方损失（回归任务）
 */
public class SquaredLoss implements LossFunction {
    @Override
    public double[] gradient(double[] pred, double[] label) {
        double[] g = new double[pred.length];
        for (int i = 0; i < pred.length; i++) g[i] = pred[i] - label[i];
        return g;
    }

    @Override
    public double[] hessian(double[] pred, double[] label) {
        double[] h = new double[pred.length];
        Arrays.fill(h, 1.0);
        return h;
    }

    @Override
    public double initPred(double[] label) {
        double sum = 0;
        for (double v : label) sum += v;
        return sum / label.length;
    }
}

/**
 * 对数损失（二分类）
 */
public class LogLoss implements LossFunction {
    @Override
    public double[] gradient(double[] pred, double[] label) {
        double[] g = new double[pred.length];
        for (int i = 0; i < pred.length; i++) {
            double p = sigmoid(pred[i]);
            g[i] = p - label[i];
        }
        return g;
    }

    @Override
    public double[] hessian(double[] pred, double[] label) {
        double[] h = new double[pred.length];
        for (int i = 0; i < pred.length; i++) {
            double p = sigmoid(pred[i]);
            h[i] = p * (1 - p);
        }
        return h;
    }

    @Override
    public double initPred(double[] label) {
        double sum = 0;
        for (double v : label) sum += v;
        double p = sum / label.length;
        return Math.log(p / (1 - p));
    }

    private double sigmoid(double x) {
        return 1.0 / (1.0 + Math.exp(-Math.max(-500, Math.min(500, x))));
    }
}

四、单棵树的构建（贪心分裂）

/**
 * 单棵决策树（CART回归树）
 */
public class DecisionTree {
    private final double lambda;    // L2正则化系数
    private final double gamma;     // 叶子数惩罚
    private final int maxDepth;     // 最大深度
    private final double minSplitGain; // 最小分裂增益
    private TreeNode root;

    public DecisionTree(double lambda, double gamma, int maxDepth, double minSplitGain) {
        this.lambda = lambda;
        this.gamma = gamma;
        this.maxDepth = maxDepth;
        this.minSplitGain = minSplitGain;
    }

    /**
     * 训练单棵树
     * @param data 数据集
     * @param indices 当前节点包含的样本索引
     * @param gradients 一阶梯度
     * @param hessians 二阶梯度
     */
    public void fit(Dataset data, List<Integer> indices, double[] gradients, double[] hessians) {
        root = buildTree(data, indices, gradients, hessians, 0);
    }

    private TreeNode buildTree(Dataset data, List<Integer> indices,
                               double[] gradients, double[] hessians, int depth) {
        TreeNode node = new TreeNode();

        // 计算当前节点的梯度和与Hessian和
        double sumG = 0, sumH = 0;
        for (int idx : indices) {
            sumG += gradients[idx];
            sumH += hessians[idx];
        }

        // 叶子权重（最优解）
        double bestWeight = -sumG / (sumH + lambda);

        // 终止条件
        if (depth >= maxDepth || indices.size() < 2 || sumH < 1e-6) {
            node.isLeaf = true;
            node.leafValue = bestWeight;
            return node;
        }

        // 贪心搜索最优分裂
        SplitResult bestSplit = findBestSplit(data, indices, gradients, hessians);

        // 分裂增益不足则停止
        if (bestSplit == null || bestSplit.gain < minSplitGain) {
            node.isLeaf = true;
            node.leafValue = bestWeight;
            return node;
        }

        // 执行分裂
        node.featureIndex = bestSplit.featureIndex;
        node.splitValue = bestSplit.splitValue;
        node.left = buildTree(data, bestSplit.leftIndices, gradients, hessians, depth + 1);
        node.right = buildTree(data, bestSplit.rightIndices, gradients, hessians, depth + 1);
        return node;
    }

    /**
     * 遍历所有特征和分裂点，寻找最优分裂
     */
    private SplitResult findBestSplit(Dataset data, List<Integer> indices,
                                      double[] gradients, double[] hessians) {
        SplitResult best = null;
        double bestGain = gamma; // 增益必须大于gamma才值得分裂

        int featureCount = data.featureCount();

        for (int f = 0; f < featureCount; f++) {
            // 收集该特征在当前节点的所有取值并排序
            List<ValueIndex> values = new ArrayList<>();
            for (int idx : indices) {
                values.add(new ValueIndex(data.features[idx][f], idx));
            }
            values.sort(Comparator.comparingDouble(a -> a.value));

            // 前缀和优化：从左到右扫描
            double leftG = 0, leftH = 0;
            double totalG = 0, totalH = 0;
            for (int idx : indices) {
                totalG += gradients[idx];
                totalH += hessians[idx];
            }

            for (int i = 0; i < values.size() - 1; i++) {
                int idx = values.get(i).index;
                leftG += gradients[idx];
                leftH += hessians[idx];

                // 相同值不分裂
                if (values.get(i).value == values.get(i + 1).value) continue;

                double rightG = totalG - leftG;
                double rightH = totalH - leftH;

                if (leftH < 1e-6 || rightH < 1e-6) continue;

                // 分裂增益 = 分裂后Obj减少量 - gamma
                double leftScore = leftG * leftG / (leftH + lambda);
                double rightScore = rightG * rightG / (rightH + lambda);
                double parentScore = totalG * totalG / (totalH + lambda);
                double gain = 0.5 * (leftScore + rightScore - parentScore) - gamma;

                if (gain > bestGain) {
                    bestGain = gain;
                    double leftWeight = -leftG / (leftH + lambda);
                    double rightWeight = -rightG / (rightH + lambda);

                    List<Integer> leftIdx = new ArrayList<>();
                    List<Integer> rightIdx = new ArrayList<>();
                    for (int j = 0; j <= i; j++) leftIdx.add(values.get(j).index);
                    for (int j = i + 1; j < values.size(); j++) rightIdx.add(values.get(j).index);

                    best = new SplitResult(f, values.get(i).value, gain,
                                           leftWeight, rightWeight, leftIdx, rightIdx);
                }
            }
        }
        return best;
    }

    /** 预测单条样本 */
    public double predict(double[] features) {
        TreeNode node = root;
        while (!node.isLeaf) {
            if (features[node.featureIndex] <= node.splitValue) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        return node.leafValue;
    }

    private static class ValueIndex {
        double value;
        int index;
        ValueIndex(double value, int index) { this.value = value; this.index = index; }
    }
}

五、GBDT集成模型

/**
 * GBDT主模型
 */
public class GBDTModel {
    private final int nTrees;           // 树的数量
    private final double learningRate;  // 学习率（收缩系数）
    private final double lambda;        // L2正则化
    private final double gamma;         // 叶子惩罚
    private final int maxDepth;         // 树最大深度
    private final double minSplitGain;
    private final LossFunction loss;

    private List<DecisionTree> trees = new ArrayList<>();
    private double baseScore;           // 初始预测值
    private double[] currentPred;       // 当前模型预测值

    public GBDTModel(int nTrees, double learningRate, double lambda,
                     double gamma, int maxDepth, double minSplitGain, LossFunction loss) {
        this.nTrees = nTrees;
        this.learningRate = learningRate;
        this.lambda = lambda;
        this.gamma = gamma;
        this.maxDepth = maxDepth;
        this.minSplitGain = minSplitGain;
        this.loss = loss;
    }

    /**
     * 训练模型
     */
    public void fit(Dataset data) {
        int n = data.sampleCount();
        currentPred = new double[n];

        // 初始预测
        baseScore = loss.initPred(data.labels);
        Arrays.fill(currentPred, baseScore);

        // 串行训练每棵树
        for (int m = 0; m < nTrees; m++) {
            double[] g = loss.gradient(currentPred, data.labels);
            double[] h = loss.hessian(currentPred, data.labels);

            List<Integer> allIndices = new ArrayList<>();
            for (int i = 0; i < n; i++) allIndices.add(i);

            DecisionTree tree = new DecisionTree(lambda, gamma, maxDepth, minSplitGain);
            tree.fit(data, allIndices, g, h);
            trees.add(tree);

            // 更新当前预测
            for (int i = 0; i < n; i++) {
                currentPred[i] += learningRate * tree.predict(data.features[i]);
            }
        }
    }

    /** 单条样本预测（回归返回原始值，分类返回概率） */
    public double predict(double[] features) {
        double raw = baseScore;
        for (DecisionTree tree : trees) {
            raw += learningRate * tree.predict(features);
        }
        return loss.transform(raw);
    }

    /** 批量预测 */
    public double[] predictBatch(double[][] features) {
        double[] result = new double[features.length];
        for (int i = 0; i < features.length; i++) {
            result[i] = predict(features[i]);
        }
        return result;
    }
}

六、完整使用示例

public class GBDTDemo {
    public static void main(String[] args) {
        // 构造简单回归数据集：y = x1 * 2 + x2 * 3 + noise
        Random rand = new Random(42);
        int nTrain = 800;
        double[][] trainX = new double[nTrain][2];
        double[] trainY = new double[nTrain];
        for (int i = 0; i < nTrain; i++) {
            trainX[i][0] = rand.nextDouble() * 10;
            trainX[i][1] = rand.nextDouble() * 10;
            trainY[i] = trainX[i][0] * 2 + trainX[i][1] * 3 + rand.nextGaussian();
        }

        Dataset trainData = new Dataset(trainX, trainY);

        // 训练GBDT回归模型
        GBDTModel model = new GBDTModel(
            50,     // 50棵树
            0.1,    // 学习率
            1.0,    // lambda
            0.0,    // gamma
            4,      // 最大深度
            0.0,    // 最小分裂增益
            new SquaredLoss()
        );

        long start = System.currentTimeMillis();
        model.fit(trainData);
        System.out.println("Training time: " + (System.currentTimeMillis() - start) + "ms");

        // 测试
        int nTest = 200;
        double mse = 0;
        for (int i = 0; i < nTest; i++) {
            double x1 = rand.nextDouble() * 10;
            double x2 = rand.nextDouble() * 10;
            double trueY = x1 * 2 + x2 * 3;
            double pred = model.predict(new double[]{x1, x2});
            mse += (pred - trueY) * (pred - trueY);
        }
        System.out.println("Test MSE: " + (mse / nTest));

        // 二分类示例
        System.out.println("\n--- Classification Demo ---");
        double[][] clfX = new double[nTrain][2];
        double[] clfY = new double[nTrain];
        for (int i = 0; i < nTrain; i++) {
            clfX[i][0] = rand.nextDouble() * 10;
            clfX[i][1] = rand.nextDouble() * 10;
            clfY[i] = (clfX[i][0] + clfX[i][1] > 10) ? 1.0 : 0.0;
        }

        GBDTModel clfModel = new GBDTModel(
            50, 0.1, 1.0, 0.0, 4, 0.0, new LogLoss()
        );
        clfModel.fit(new Dataset(clfX, clfY));

        int correct = 0;
        for (int i = 0; i < 200; i++) {
            double x1 = rand.nextDouble() * 10;
            double x2 = rand.nextDouble() * 10;
            double trueLabel = (x1 + x2 > 10) ? 1.0 : 0.0;
            double prob = clfModel.predict(new double[]{x1, x2});
            int predLabel = (prob > 0.5) ? 1 : 0;
            if (predLabel == (int) trueLabel) correct++;
        }
        System.out.println("Classification accuracy: " + (correct / 200.0));
    }
}

七、XGBoost核心优化点对比

八、复杂度分析

其中 n 为样本数，d 为特征数，L 为叶子数上限，M 为树的数量。

九、总结

本文从零实现了GBDT核心框架，关键要点如下：

• 梯度提升框架：每棵树拟合当前模型的负梯度残差，串行迭代降低损失
• 二阶近似目标：XGBoost引入Hessian矩阵，使分裂点选择更加精确
• 正则化机制：通过 γ 控制模型复杂度，λ 约束叶子权重防止过拟合
• 贪心分裂算法：枚举所有特征与分裂点，利用前缀和优化计算分裂增益

该实现虽为教学版本，但完整覆盖了GBDT/XGBoost的数学原理与核心数据结构。工业部署时可进一步引入直方图近似、列采样、并行训练等优化手段。