您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

AdaBoost C++ 完整實現與核心原理深度解析

編輯：關於C++

AdaBoost 演算法核心原理

AdaBoost（Adaptive Boosting）是一種經典的集成學習演算法，其核心思想是將多個「弱分類器」組合成一個「強分類器」。每個弱分類器通常是一個簡單的決策樹樁（Decision Stump，即單層決策樹）。最終的分類結果由所有弱分類器的加權投票決定：

H(x) = sign(Σ αₘ · hₘ(x))

其中 hₘ(x) 是第 m 個弱分類器的預測結果（-1 或 1），αₘ 是該分類器的權重，計算公式為：

α = 0.5 × ln((1 - errorRate) / errorRate)

錯誤率越低的分類器，獲得的權重 α 越大，在最終決策中話語權越重。

權重更新機制

AdaBoost 的關鍵在於樣本權重 D 的動態調整。初始時所有樣本權重相等（1/N）。每輪迭代後，被誤分類樣本的權重會增大，正確分類樣本的權重減小：

Dᵢ ← Dᵢ × exp(-α × yᵢ × h(xᵢ)) / Z

其中 Z 為歸一化因子，使所有權重總和為 1。這迫使下一輪弱分類器更關注前一輪難以分類的樣本。

訓練流程

初始化樣本權重向量 D
對 m = 1 到 M 輪迭代：
- 使用當前權重 D 訓練弱分類器 hₘ
- 計算加權錯誤率 errorRate
- 計算分類器權重 αₘ
- 更新樣本權重 D
- 若錯誤率極低或達到最大迭代次數，提前終止
輸出最終強分類器 H(x)

C++ 完整實現代碼

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>

using namespace std;

const double EPS = 1e-6;

// 單層決策樹分類函數
vector<double> stumpClassify(const vector<vector<double>>& data, int dimen, double threshVal, int threshIneq) {
    int N = data.size();
    vector<double> retLabel(N);
    if (threshIneq == 0) { // 小於閾值分為 -1
        for (int i = 0; i < N; ++i)
            retLabel[i] = (data[i][dimen] <= threshVal) ? -1.0 : 1.0;
    } else { // 大於閾值分為 -1
        for (int i = 0; i < N; ++i)
            retLabel[i] = (data[i][dimen] > threshVal) ? -1.0 : 1.0;
    }
    return retLabel;
}

// 構建最佳單層決策樹
vector<double> buildStump(const vector<vector<double>>& data,
                          const vector<double>& D,
                          double& minError,
                          vector<double>& bestClassEst) {
    int N = data.size();
    int M = data[0].size();
    const int numSteps = 10;
    vector<double> bestStump(3); // {特徵索引, 閾值, 不等式方向}
    minError = numeric_limits<double>::max();

    for (int i = 0; i < M; ++i) {
        double rangeMin = data[0][i], rangeMax = data[0][i];
        for (int j = 1; j < N; ++j) {
            rangeMin = min(rangeMin, data[j][i]);
            rangeMax = max(rangeMax, data[j][i]);
        }
        double stepSize = (rangeMax - rangeMin) / numSteps;

        for (int j = -1; j <= numSteps; ++j) {
            double threshVal = rangeMin + j * stepSize;
            for (int inequal = 0; inequal < 2; ++inequal) {
                vector<double> predictVals = stumpClassify(data, i, threshVal, inequal);
                double weightedError = 0.0;
                for (int k = 0; k < N; ++k)
                    if (predictVals[k] != data[k][M]) // 假設最後一列為標籤
                        weightedError += D[k];

                if (weightedError < minError) {
                    minError = weightedError;
                    bestClassEst = predictVals;
                    bestStump[0] = i;
                    bestStump[1] = threshVal;
                    bestStump[2] = inequal;
                }
            }
        }
    }
    return bestStump;
}

// AdaBoost 訓練主流程
vector<vector<double>> adaBoostTrainDS(vector<vector<double>>& data, int numIt) {
    int N = data.size();
    int M = data[0].size() - 1; // 最後一列為標籤
    vector<vector<double>> weakClassArr;
    vector<double> D(N, 1.0 / N);
    vector<double> aggClassEst(N, 0.0);

    for (int iter = 0; iter < numIt; ++iter) {
        double error;
        vector<double> classEst(N);
        vector<double> bestStump = buildStump(data, D, error, classEst);

        if (error > 0.5) break; // 弱分類器表現太差，提前停止

        double alpha = 0.5 * log((1.0 - error) / max(error, EPS));
        bestStump.push_back(alpha);
        weakClassArr.push_back(bestStump);

        // 更新樣本權重
        double Dsum = 0.0;
        for (int j = 0; j < N; ++j) {
            double expon = -1.0 * alpha * data[j][M] * classEst[j];
            D[j] *= exp(expon);
            Dsum += D[j];
        }
        for (int j = 0; j < N; ++j) D[j] /= Dsum;

        // 累加分類估計
        for (int j = 0; j < N; ++j)
            aggClassEst[j] += alpha * classEst[j];

        // 計算整體錯誤率
        double aggError = 0.0;
        for (int j = 0; j < N; ++j)
            if (sign(aggClassEst[j]) != data[j][M]) aggError += 1.0;
        aggError /= N;

        if (aggError == 0.0) break; // 完美分類，提前終止
    }
    return weakClassArr;
}

// 分類預測函數
vector<double> adaClassify(const vector<vector<double>>& test,
                           const vector<vector<double>>& classifierArr) {
    int N = test.size();
    vector<double> aggClassEst(N, 0.0);
    for (const auto& clf : classifierArr) {
        int dimen = (int)clf[0];
        double thresh = clf[1];
        int inequal = (int)clf[2];
        double alpha = clf[3];
        vector<double> classEst = stumpClassify(test, dimen, thresh, inequal);
        for (int j = 0; j < N; ++j)
            aggClassEst[j] += alpha * classEst[j];
    }
    for (int j = 0; j < N; ++j)
        aggClassEst[j] = (aggClassEst[j] > 0) ? 1.0 : -1.0;
    return aggClassEst;
}

double sign(double x) { return (x > 0) ? 1.0 : -1.0; }

int main() {
    // 示例數據：{特徵1, 特徵2, 標籤}
    vector<vector<double>> data = {
        {1.0, 2.1, 1.0}, {2.0, 1.1, 1.0}, {1.3, 1.0, -1.0},
        {1.0, 1.0, -1.0}, {2.0, 1.0, 1.0}
    };

    vector<vector<double>> classifierArr = adaBoostTrainDS(data, 30);

    // 測試數據
    vector<vector<double>> test = {
        {0.0, 0.0, 0.0}, {5.0, 5.0, 0.0}
    };
    vector<double> result = adaClassify(test, classifierArr);

    cout << "預測結果：" << endl;
    for (double r : result) cout << r << " ";
    cout << endl;
    return 0;
}