每日算法 — 使用java实现AdaBoost：自适应提升算法与弱分类器加权组合

可莉爸爸 AI算法

引言

AdaBoost（Adaptive Boosting，自适应提升）是机器学习领域最具影响力的集成学习算法之一，由Freund和Schapire于1995年提出。AdaBoost通过迭代训练一系列弱分类器，并自适应地调整样本权重，最终将多个弱分类器加权组合成一个强分类器。本文将用Java完整实现AdaBoost算法，深入讲解样本权重更新机制、弱分类器选择和加权投票策略。

算法原理

核心思想

AdaBoost的核心思想是：通过反复训练弱分类器，每次重点关注前一轮分类错误的样本，最终将所有弱分类器的预测结果按权重加权求和，形成强分类器。

算法流程

初始化样本权重：

$$D_1(i) = \frac{1}{n}, \quad i = 1, 2, …, n$$

对于每轮迭代 $t = 1, 2, …, T$：

  1. 训练弱分类器：在当前样本分布 $D_t$ 下训练弱分类器 $h_t$

  2. 计算分类误差：

$$\epsilon_t = \sum_{i=1}^{n} D_t(i) \cdot \mathbb{I}[y_i \neq h_t(x_i)]$$

  1. 计算弱分类器权重：

$$\alpha_t = \frac{1}{2} \ln\left(\frac{1 – \epsilon_t}{\epsilon_t}\right)$$

  1. 更新样本权重：

$$D_{t+1}(i) = \frac{D_t(i) \cdot e^{-\alpha_t y_i h_t(x_i)}}{Z_t}$$

其中 $Z_t$ 为归一化因子。

最终分类器：

$$H(x) = \text{sign}\left(\sum_{t=1}^{T} \alpha_t h_t(x)\right)$$

权重更新解析

  • 当样本被正确分类时（$y_i = h_t(x_i)$），权重乘以 $e^{-\alpha_t} < 1$，权重减小
  • 当样本被错误分类时（$y_i \neq h_t(x_i)$），权重乘以 $e^{\alpha_t} > 1$，权重增大
  • 分类误差越小，该弱分类器的权重 $\alpha_t$ 越大

Java实现

项目结构

src/
├── AdaBoost.java            // AdaBoost核心类
├── WeakClassifier.java      // 弱分类器接口
├── DecisionStump.java       // 决策桩实现
├── DataPoint.java           // 数据点类
├── AdaBoostDemo.java        // 演示入口
└── DatasetGenerator.java    // 数据集生成器

弱分类器接口

/**
 * 弱分类器接口
 * AdaBoost通过组合多个弱分类器构建强分类器
 */
public interface WeakClassifier {
    /**
     * 训练弱分类器
     * @param dataPoints 训练数据
     * @param weights 样本权重
     */
    void train(DataPoint[] dataPoints, double[] weights);

    /**
     * 预测单个样本
     */
    int predict(double[] features);

    /**
     * 计算加权误差
     */
    double computeError(DataPoint[] dataPoints, double[] weights);

    /**
     * 获取分类器描述
     */
    String getDescription();
}

决策桩实现

/**
 * 决策桩（Decision Stump）
 * 最简单的弱分类器：选择一个特征维度和一个阈值进行二分
 */
public class DecisionStump implements WeakClassifier {
    private int featureIndex;    // 选择的特征维度
    private double threshold;    // 分割阈值
    private int polarity;        // 极性（1或-1）
    private double weightedError;

    @Override
    public void train(DataPoint[] dataPoints, double[] weights) {
        int n = dataPoints.length;
        int dim = dataPoints[0].getFeatures().length;

        double minError = Double.MAX_VALUE;

        // 遍历每个特征维度
        for (int feature = 0; feature < dim; feature++) {
            // 找到该维度的取值范围
            double minVal = Double.MAX_VALUE;
            double maxVal = Double.MIN_VALUE;
            for (DataPoint point : dataPoints) {
                double val = point.getFeatures()[feature];
                if (val < minVal) minVal = val;
                if (val > maxVal) maxVal = val;
            }

            // 在该维度上尝试多个阈值
            int nThresholds = 20;
            for (int t = 0; t <= nThresholds; t++) {
                double threshold = minVal + (maxVal - minVal) * t / nThresholds;

                // 尝试两种极性
                for (int pol : new int[]{1, -1}) {
                    double error = computeWeightedError(
                        dataPoints, weights, feature, threshold, pol);

                    if (error < minError) {
                        minError = error;
                        this.featureIndex = feature;
                        this.threshold = threshold;
                        this.polarity = pol;
                        this.weightedError = error;
                    }
                }
            }
        }
    }

    /**
     * 计算给定参数下的加权误差
     */
    private double computeWeightedError(DataPoint[] dataPoints, double[] weights,
                                         int feature, double threshold, int polarity) {
        double error = 0;
        for (int i = 0; i < dataPoints.length; i++) {
            int predicted = polarity * (dataPoints[i].getFeatures()[feature] >= threshold ? 1 : -1);
            if (predicted != dataPoints[i].getLabel()) {
                error += weights[i];
            }
        }
        return error;
    }

    @Override
    public int predict(double[] features) {
        return polarity * (features[featureIndex] >= threshold ? 1 : -1);
    }

    @Override
    public double computeError(DataPoint[] dataPoints, double[] weights) {
        return weightedError;
    }

    @Override
    public String getDescription() {
        return String.format("DecisionStump[特征%d, 阈值=%.4f, 极性=%d, 误差=%.4f]",
            featureIndex, threshold, polarity, weightedError);
    }

    public int getFeatureIndex() {
        return featureIndex;
    }

    public double getThreshold() {
        return threshold;
    }

    public int getPolarity() {
        return polarity;
    }
}

数据点类

/**
 * 数据点类
 */
public class DataPoint {
    private final double[] features;
    private final int label; // +1 或 -1

    public DataPoint(double[] features, int label) {
        this.features = features;
        this.label = label;
    }

    public double[] getFeatures() {
        return features;
    }

    public int getLabel() {
        return label;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("(");
        for (int i = 0; i < features.length; i++) {
            sb.append(String.format("%.2f", features[i]));
            if (i < features.length - 1) sb.append(", ");
        }
        sb.append(") -> ").append(label);
        return sb.toString();
    }
}

AdaBoost核心类

import java.util.ArrayList;
import java.util.List;

/**
 * AdaBoost算法实现
 * 通过迭代训练弱分类器并自适应调整样本权重，构建强分类器
 */
public class AdaBoost {
    private List<WeakClassifier> weakClassifiers; // 弱分类器列表
    private List<Double> alphas;                  // 弱分类器权重
    private int nRounds;                          // 迭代轮数
    private double[] finalWeights;                // 最终样本权重分布

    public AdaBoost(int nRounds) {
        this.nRounds = nRounds;
        this.weakClassifiers = new ArrayList<>();
        this.alphas = new ArrayList<>();
    }

    /**
     * 训练AdaBoost模型
     * @param dataPoints 训练数据集
     */
    public void train(DataPoint[] dataPoints) {
        int n = dataPoints.length;

        // 初始化样本权重为均匀分布
        double[] weights = new double[n];
        for (int i = 0; i < n; i++) {
            weights[i] = 1.0 / n;
        }

        System.out.println("=== AdaBoost 训练开始 ===");
        System.out.println("样本数: " + n);
        System.out.println("迭代轮数: " + nRounds);

        for (int round = 0; round < nRounds; round++) {
            System.out.println("\n--- 第 " + (round + 1) + " 轮 ---");

            // 训练弱分类器
            DecisionStump stump = new DecisionStump();
            stump.train(dataPoints, weights);

            double error = stump.computeError(dataPoints, weights);
            System.out.println("弱分类器: " + stump.getDescription());
            System.out.printf("加权误差: %.4f%n", error);

            // 如果误差过大，跳过该轮
            if (error >= 0.5 || error < 1e-10) {
                System.out.println("误差超出有效范围，跳过该轮");
                continue;
            }

            // 计算弱分类器权重 alpha = 0.5 * ln((1-e)/e)
            double alpha = 0.5 * Math.log((1 - error) / error);
            alphas.add(alpha);
            weakClassifiers.add(stump);

            System.out.printf("分类器权重 α: %.4f%n", alpha);

            // 更新样本权重
            double sumWeights = 0;
            for (int i = 0; i < n; i++) {
                int predicted = stump.predict(dataPoints[i].getFeatures());
                int label = dataPoints[i].getLabel();

                // 权重更新公式: D(i) *= exp(-alpha * y_i * h(x_i))
                weights[i] *= Math.exp(-alpha * label * predicted);
                sumWeights += weights[i];
            }

            // 归一化权重
            for (int i = 0; i < n; i++) {
                weights[i] /= sumWeights;
            }

            // 输出权重分布信息
            printWeightDistribution(dataPoints, weights);
        }

        finalWeights = weights.clone();
        System.out.println("\n=== 训练完成 ===");
        System.out.println("弱分类器数量: " + weakClassifiers.size());
    }

    /**
     * 打印权重分布信息
     */
    private void printWeightDistribution(DataPoint[] dataPoints, double[] weights) {
        double maxWeight = 0;
        int maxIndex = -1;
        double minWeight = Double.MAX_VALUE;
        int minIndex = -1;

        for (int i = 0; i < weights.length; i++) {
            if (weights[i] > maxWeight) {
                maxWeight = weights[i];
                maxIndex = i;
            }
            if (weights[i] < minWeight) {
                minWeight = weights[i];
                minIndex = i;
            }
        }

        System.out.printf("权重范围: [%.4f, %.4f]%n", minWeight, maxWeight);
        System.out.printf("最大权重样本: %s (权重=%.4f)%n",
            dataPoints[maxIndex], maxWeight);
    }

    /**
     * 预测单个样本
     * H(x) = sign(sum(alpha_t * h_t(x)))
     */
    public int predict(double[] features) {
        double sum = 0;
        for (int t = 0; t < weakClassifiers.size(); t++) {
            int prediction = weakClassifiers.get(t).predict(features);
            sum += alphas.get(t) * prediction;
        }
        return sum >= 0 ? 1 : -1;
    }

    /**
     * 在数据集上评估模型
     */
    public double evaluate(DataPoint[] dataPoints) {
        int correct = 0;
        for (DataPoint point : dataPoints) {
            if (predict(point.getFeatures()) == point.getLabel()) {
                correct++;
            }
        }
        return (double) correct / dataPoints.length;
    }

    /**
     * 打印每个弱分类器的详细信息
     */
    public void printClassifierDetails() {
        System.out.println("\n=== 弱分类器详情 ===");
        for (int t = 0; t < weakClassifiers.size(); t++) {
            System.out.printf("分类器 %d: %s, α=%.4f%n",
                t + 1, weakClassifiers.get(t).getDescription(), alphas.get(t));
        }
    }

    public List<WeakClassifier> getWeakClassifiers() {
        return weakClassifiers;
    }

    public List<Double> getAlphas() {
        return alphas;
    }
}

数据集生成器

import java.util.Random;

/**
 * 生成用于AdaBoost演示的数据集
 */
public class DatasetGenerator {
    private Random random;

    public DatasetGenerator(long seed) {
        this.random = new Random(seed);
    }

    /**
     * 生成二维线性不可分数据集（适合AdaBoost展示）
     * 创建一个XOR-like的分布，单个决策桩无法完美分类
     */
    public DataPoint[] generateNonLinearDataset(int n) {
        DataPoint[] data = new DataPoint[n];

        for (int i = 0; i < n; i++) {
            double x = random.nextDouble() * 4 - 2; // [-2, 2]
            double y = random.nextDouble() * 4 - 2; // [-2, 2]

            // XOR-like 分布：第一、三象限为正，第二、四象限为负
            int label;
            if ((x >= 0 && y >= 0) || (x < 0 && y < 0)) {
                label = 1;
            } else {
                label = -1;
            }

            // 添加一些噪声
            if (random.nextDouble() < 0.1) {
                label = -label;
            }

            data[i] = new DataPoint(new double[]{x, y}, label);
        }

        return data;
    }

    /**
     * 生成带冗余特征的高维数据集
     */
    public DataPoint[] generateHighDimDataset(int n, int dim) {
        DataPoint[] data = new DataPoint[n];

        for (int i = 0; i < n; i++) {
            double[] features = new double[dim];
            for (int j = 0; j < dim; j++) {
                features[j] = random.nextGaussian();
            }

            // 标签由前两个特征的XOR决定
            int label = (features[0] >= 0 && features[1] >= 0) ||
                        (features[0] < 0 && features[1] < 0) ? 1 : -1;

            data[i] = new DataPoint(features, label);
        }

        return data;
    }
}

演示入口

/**
 * AdaBoost算法演示
 */
public class AdaBoostDemo {
    public static void main(String[] args) {
        demoXORClassification();
        System.out.println("\n" + "=".repeat(60) + "\n");
        demoComparisonWithSingleStump();
    }

    /**
     * 演示1：XOR-like分布分类
     */
    private static void demoXORClassification() {
        System.out.println("=== 演示1：XOR-like分布分类 ===\n");

        DatasetGenerator generator = new DatasetGenerator(42);
        DataPoint[] trainData = generator.generateNonLinearDataset(200);
        DataPoint[] testData = generator.generateNonLinearDataset(100);

        AdaBoost adaBoost = new AdaBoost(10);
        adaBoost.train(trainData);
        adaBoost.printClassifierDetails();

        double trainAccuracy = adaBoost.evaluate(trainData);
        double testAccuracy = adaBoost.evaluate(testData);

        System.out.printf("\n训练集准确率: %.1f%%%n", trainAccuracy * 100);
        System.out.printf("测试集准确率: %.1f%%%n", testAccuracy * 100);
    }

    /**
     * 演示2：与单个决策桩的对比
     */
    private static void demoComparisonWithSingleStump() {
        System.out.println("=== 演示2：AdaBoost vs 单决策桩 ===\n");

        DatasetGenerator generator = new DatasetGenerator(123);
        DataPoint[] data = generator.generateNonLinearDataset(300);

        // 划分训练集和测试集
        int trainSize = 200;
        DataPoint[] trainData = new DataPoint[trainSize];
        DataPoint[] testData = new DataPoint[data.length - trainSize];
        System.arraycopy(data, 0, trainData, 0, trainSize);
        System.arraycopy(data, trainSize, testData, 0, data.length - trainSize);

        // 单决策桩
        double[] uniformWeights = new double[trainSize];
        for (int i = 0; i < trainSize; i++) {
            uniformWeights[i] = 1.0 / trainSize;
        }
        DecisionStump singleStump = new DecisionStump();
        singleStump.train(trainData, uniformWeights);

        int correctSingle = 0;
        for (DataPoint point : testData) {
            if (singleStump.predict(point.getFeatures()) == point.getLabel()) {
                correctSingle++;
            }
        }
        double singleAccuracy = (double) correctSingle / testData.length;

        // AdaBoost
        AdaBoost adaBoost = new AdaBoost(15);
        adaBoost.train(trainData);
        double adaBoostAccuracy = adaBoost.evaluate(testData);

        System.out.println("对比结果：");
        System.out.printf("  单决策桩准确率: %.1f%%%n", singleAccuracy * 100);
        System.out.printf("  AdaBoost准确率: %.1f%%%n", adaBoostAccuracy * 100);
        System.out.printf("  提升幅度: %.1f%%%n", (adaBoostAccuracy - singleAccuracy) * 100);
    }
}

复杂度分析

指标 复杂度 说明
每轮训练 $O(n \cdot d \cdot m)$ $n$为样本数，$d$为维度，$m$为阈值搜索数
总训练时间 $O(T \cdot n \cdot d \cdot m)$ $T$为迭代轮数
预测时间 $O(T \cdot d)$ 需要评估T个弱分类器
空间复杂度 $O(T \cdot d)$ 存储T个弱分类器的参数

算法特性

优点

  • 不易过拟合：通过关注难分类样本，提升泛化能力
  • 实现简单：弱分类器只需要比随机猜测稍好
  • 可解释性强：每个弱分类器的权重反映了其重要性

缺点

  • 对噪声敏感：异常样本权重会不断增大
  • 依赖弱分类器：弱分类器不能太弱（误差需小于0.5）

算法扩展

多分类AdaBoost

  • AdaBoost.M1：直接扩展到多分类，要求弱分类器准确率大于随机猜测
  • AdaBoost.M2：使用伪损失函数处理多分类
  • SAMME：基于多类指数损失函数的AdaBoost

回归AdaBoost

AdaBoost.R2通过将回归问题转化为分类问题，实现了回归任务的提升学习。

总结

AdaBoost通过巧妙的权重调整机制，将多个弱分类器组合成强分类器，是集成学习的经典之作。本文的Java实现完整展示了样本权重初始化、弱分类器训练、加权误差计算和权重更新的全过程。理解AdaBoost后，读者可以深入学习梯度提升树（GBDT）、XGBoost等更强大的集成学习方法。

Tagged with: