AdaBoost

基本流程

自适应提升（Adaptive Boosting，AdaBoost）算法，可作为一种从一系列弱分类器中产生一个强分类器的通用方法。

• 弱分类器的分类效果比强分类器差。

假设有一个集合 $\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\ldots,(\mathbf{x}_N,y_N)\}$，$\mathbf{x}_i$ 表示特征矢量；$y_i$ 表示对应分类为 $\{-1,1\}$ 的标签。

AdaBoost 算法通过 $M$ 次迭代得到若干个弱分类器 $\{k_1,k_2,\ldots,k_M\}$，对于每个样本，弱分类器都会给出分类结果 $k_m(\mathbf{x}_i)\in\{-1,1\}$。

将 $M$ 个弱分类器进行某种线性组合，得到一个强分类器 $C_m$。

进行第 $m-1$ 次迭代后，线性组合得到的强分类器为：

$C_{m-1}(\mathbf{x}_i)=\alpha_1k_1(\mathbf{x}_i)+\alpha_2k_2(\mathbf{x}_i)+\cdots+\alpha_{m-1}k_{m-1}(\mathbf{x}_i)\tag{1}$

• $\alpha_i$ 为权值，$m>1$。

进行第 $m$ 次迭代时，AdaBoost通过增加一个弱分类器的方式扩展成一个强分类器：

$C_m{\mathbf{x}_i}=C_{m-1}(\mathbf{x}_i)+\alpha_mk_m(\mathbf{x}_i)\tag{2}$

定义误差 $E$，判断 $C_m$ 和 $C_{m-1}$ 的性能，当 $C_m$ 比 $C_{m-1}$ 的效果强才有意义。误差用所有样本 $\mathbf{x}_i$ 的指数损失的总和定义：

$\mathbf{E}=\sum_{i=1}^Ne^{-y_iC_m(\mathbf{x}_i)}=\sum_{i=1}^Ne^{-y_i(C_{m-1}(\mathbf{x}_i)+\alpha_mk_m(\mathbf{x}_i))}\tag{3}$

令 $w_i^{(m)}$ 表示在第 $m-1$ 次迭代后，对训练样本 $\mathbf{x}_i$ 所分配的权重。

• $w_i^{(1)}=1$，$w_i^{(m)}=e^{-y_iC_{m-1}(\mathbf{x}_i)}$

$\mathbf{E}=\sum_{i=1}^Nw_i^{(m)}e^{-y_i\alpha_mk_m(\mathbf{x}_i)}\tag{4}$

将上式拆成：

$\mathbf{E}=\sum_{y_i=k_m(\mathbf{x}_i)}w_i^{(m)}e^{-\alpha_m}+\sum_{y_i\neq k_m(\mathbf{x}_i)}w_i^{(m)}e^{\alpha_m}\tag{5}$

• 若 $y_i=k_m(\mathbf{x}_i)$，则分类结果与实际相符，无论都为 $-1$ 还是 $1$，乘积为 $1$。
• 若 $y_i\neq k_m(\mathbf{x}_i)$，则分类结果与实际不符，乘积为 $-1$。

根据对所有 $y_i=k_m(\mathbf{x}_i)$ 的数据项 $\mathbf{x}_i$ 的误差求和，对所有 $y_i\neq k_m(\mathbf{x}_i)$ 的数据项 $\mathbf{x}_i$ 的误差求和，再改写成：

$\mathbf{E}=\sum_{y_i=k_m(\mathbf{x}_i)}w_i^{(m)}e^{-\alpha_m}+\sum_{y_i\neq k_m(\mathbf{x}_i)}w_i^{(m)}e^{\alpha_m}=\sum_{i=1}^Nw_i^{(m)}e^{-\alpha_m}+\sum_{y_i\neq k_m(\mathbf{x}_i)}w_i^{(m)}(e^{\alpha_m}-e^{-\alpha_m})\tag{6}$

可以看出，如果 $\alpha_m$ 一定，强分类器 $C_m$ 的误差大小完全取决于第二项中 $\sum_{y_i\neq k_m(\mathbf{x}_i)}w_i^{(m)}$ 的大小，即取决于这次迭代中被错分类的权值 $w_i^{(m)}$ 的大小。

对式5进行求导：

$\frac{d\mathbf{E}}{d\alpha_m}=\sum_{y_i\neq k_m(\mathbf{x}_i)}w_i^{(m)}e^{\alpha_m}-\sum_{y_i=k_m(\mathbf{x}_i)}w_i^{(m)}e^{-\alpha_m}\tag{7}$

令导数为0，得到权值 $\alpha_m$：

$\alpha_m=\frac{1}{2}\ln\left(\frac{\sum_{y_i=k_m(\mathbf{x}_i)}w_i^{(m)}}{\sum_{y_i\neq k_m(\mathbf{x}_i)}w_i^{(m)}}\right)\tag{8}$

令 $\epsilon_m$ 表示误差率：

$\epsilon_m=\frac{\sum_{y_i\neq k_m(\mathbf{x}_i)}w_i^{(m)}}{\sum_{i=1}^Nw_i^{(m)}}\tag{9}$

则 $\alpha_m$ 写成：

$\alpha_m=\frac{1}{2}\ln\left(\frac{1-\epsilon}{\epsilon_m}\right)\tag{10}$

得到 AdaBoost 算法：每次迭代中，选择使 $\sum_{y_i\neq k_m(\mathbf{x}_i)}w_i^{(m)}$ 最小的分类器 $k_m$，得到误差率 $\epsilon_m$，从而计算权值 $\alpha_m$，则最终强分类器由 $C_{m-1}$ 逐渐提升为 $C_m=C_{m-1}+\alpha_mk_m$。

每次迭代后，得到每个训练样本数据权值 $w_i^{(m+1)}$ 为：

$w_i^{(m+1)}=w_i^{(m)}e^{-y_i\alpha_mk_m(\mathbf{x}_i)}=w_i^{(m)}\times\begin{cases}e^{-\alpha_m},&分类正确\\e^{\alpha_m},&分类错误\end{cases}\tag{11}$

AdaBoost的计算步骤：

1. 设有 $n$ 个样本 $\mathbf{x}_1,\ldots,\mathbf{x}_n$，分类为 $y_1,\ldots,y_n,y_i\in\{-1,1\}$。
2. 初始化每个样本的权值 $w_1^{(1)},\ldots,w_n^{(1)}$，都为 $\frac{1}{n}$。
3. 进行迭代：$m=1,\ldots,M$。
   • 找到使得错误率 $\epsilon_m$ 最小的弱分类器 $k_m(\mathbf{x})$，并得到 $\epsilon_m$（见式9）。
   • 计算 $k_m(\mathbf{x})$ 的权值 $\alpha_m$（见式10）。
   • 得到新的强分类器 $C_m(\mathbf{x})$（见式2）。
   • 更新每个样本的权值 $w_i^{(m+1)}$（见式11）。
   • 对权值 $w_i^{(m+1)}$ 进行归一化，使 $\sum_iw_i^{(m+1)}=1$。
4. 得到最终的强分类器：

$C(\mathbf{x})=\mathbf{sign}(C_M(\mathbf{x}))=\mathbf{sign}(\sum_{i=1}^M\alpha_mk_m(\mathbf{x}))\tag{12}$

AdaBoost 算法可分为 Discrete AdaBoost、Real AdaBoost、LogitBoost 和 Gentle AdaBoost。

• Discrete AdaBoost 的弱分类输出结果是 1 或 -1，组成强分类器时是离散的形式。
• Real AdaBoost的弱分类器输出结果是该样本属于某一类的概率。

上述讨论即为 Discrete AdaBoost 的迭代过程。

Real AdaBoost 的迭代过程：

1. 基于每个样本的权值 $w_i^{(m)}$，拟合一个分类概率估计 $p_m(\mathbf{x})=P(y=1|x)\in[0,1]$，表示样本属于分类结果为1的概率。
2. 得到这次迭代的弱分类器：$k_m(\mathbf{x})=\frac{1}{2}\ln\left(\frac{p_m(\mathbf{x})}{1-p_m(\mathbf{x})}\right)$。
3. 更新权值：$w_i^{(m+1)}=w_i^{(m)}e^{-y_ik_m(\mathbf{x})}$。
4. 归一化权值。

最终强分类器 $C$ 为：

$C(\mathbf{x})=\mathbf{sign}(\sum_{i=1}^Mk_m(\mathbf{x}))\tag{13}$

LogitBoost 是逻辑回归技术在 AdaBoost 的应用。弱分类器的选取基于加权最小二乘法。

设迭代前强分类器 $C_0(\mathbf{x})=0$，每个训练样本数据的概率估计 $p_0(\mathbf{x}_i)=0.5$，迭代过程如下：

1. 计算工作响应 $z_i^{(m)}$：

$z_i^{(m)}=\frac{y_i^*-p_{m-1}(x_i)}{p_{m-1}(x_i)[1-p_{m-1}(x_i)]}\tag{14}$

$y_i^*=\frac{y_i-1}{2}\tag{15}$

2. 计算权值：

$w_i^{(m)}=p_{m-1}(\mathbf{x}_i)[1-p_{m-1}(\mathbf{x}_i)]\tag{16}$

3. 应用权值 $w_i^{(m)}$，基于 $z_i^{(m)}$ 到 $\mathbf{x}_i$ 的加权最小二乘回归法，拟合弱分类器 $k_m(\mathbf{x}_i)$。

4. 更新 $p_m(\mathbf{x}_i)$

$p_m(x_i)=\frac{e^{C_{m-1}(\mathbf{x}_i)}}{e^{C_{m-1}(\mathbf{x}_i)}+e^{-C_{m-1}(\mathbf{x}_i)}}=\frac{1}{1+e^{-2C_{m-1}(\mathbf{x}_i)}}\tag{17}$

5. 更新强分类器。

$C_m(\mathbf{x}_i)=C_{m-1}(\mathbf{x}_i)+\frac{1}{2}k_m(\mathbf{x}_i)\tag{18}$

最终强分类器为式13。

Gentle AdaBoost 算法与 LogitBoost 算法相似，但参数选择更简单。弱分类器 $k_m(\mathbf{x})$ 由基于权值 $w_i^{(m)}$ 的从 $y_i$ 到 $\mathbf{x}_i$ 的加权最小二乘法回归拟合得到。

每次迭代得到的强分类器 $C_m(\mathbf{x})$ 和 权值：

$C_m(\mathbf{x}_i)=C_{m-1}(\mathbf{x}_i)+k_m(\mathbf{x}_i)\tag{19}$

$w_i^{(m+1)}=w_i^{(m)}e^{-y_ik_m(\mathbf{x}_i)}\tag{20}$

OpenCV提供的AdaBoost

OpenCV 实现了上述4种 AdaBoost，且弱分类器都采用 CART 决策树的方法。

使用决策树时：

$\alpha_m=\ln\left(\frac{1-\epsilon}{\epsilon_m}\right)\tag{21}$

$w_i^{(m+1)}=w_i^{(m)}\times\begin{cases}1,&分类正确\\e^{\alpha_m},&分类错误\end{cases}\tag{22}$

OpenCV 的 ml 中提供了Boost 类，继承自 DTree 类。

类中有部分参数：

• BoostType：Boosting 算法的类型。

1
2
3
4
5
6
7
8
9
10

enum Types 
{
    DISCRETE=0, // Discrete AdaBoost.
    REAL=1,     // Real AdaBoost.
    LOGIT=2,    // LogitBoost. 
    GENTLE=3    // Gentle AdaBoost. 
};
// 访问函数：
int getBoostType(); // 默认是 REAL
void setBoostType(int val);

• WeakCount：弱分类器的数量，也是迭代次数。访问函数：

1
2

int getWeakCount(); // 默认是 100
void setWeakCount(int val);

• WeightTrimRate：裁剪率，0～1，在迭代过程中，那些归一化后的样本权值 wi(m) 小于该裁剪率的样本将不进入下次迭代。访问函数：

1
2

double getWeightTrimRate(); // 默认是 0.95
void setWeightTrimRate(double val);

例子-用户贷款违约预测

数据集地址：https://aistudio.baidu.com/datasetdetail/112664

数据集的属性如下：

• income：用户收入，较大数
• age：用户年龄
• experience_years：用户从业年限
• is_1：是否单身
• city：居住城市，抽象代号
• region：居住地区，抽象代号
• current_job_years：现任职位工作年数
• current_house_years：现居房屋居住年数
• house_ownership：房屋所有权，租用（1）、自有（2）、未有（0）
• car_ownership：是否拥有汽车
• profession：职业，抽象代号
• label：是否存在违约，即响应值

AdaBoost 分类效果如下：

1
2
3
4
5

Train Data imported: 168000
Test Data imported: 84000
AdaBoost算法(基于OpenCV实现)：
计算花费时长：31247ms
准确率：0.890024

代码地址：Gitee - AdaBoost