Ensemble

• boosting

• bagging

• stacking

1. boosting

• 代表算法：AdaBoost

只能分类？

弱分类器：比较粗糙的分类规则

强分类器：精确的分类规则

提升方法就是组合弱分类器，构成一个强分类器

大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习

对于提升方法来说有两个问题需要回答：

1. 每一轮如何改变训练数据的权值或概率分布

2. 如何将弱分类器组合成一个强分类器

1.1 AdaBoost

AdaBoost的做法：

针对问题1，提高被前一轮弱分类器错误分类的样本的权值，降低分类正确的样本的权值

针对问题2，组合采用加权多数表决的方法

算法8.1 (AdaBoost)

输入：训练数据集 $T$ ；弱学习算法

输出：最终的分类器 $G(x)$

1. 初始化训练数据权值分布
   $$
   D_1 = (w_{11}, \cdots, w_{1i}, \cdots, w_{1N}),\quad w_{1i} = \frac{1}{N}, \quad i = 1,2,…,N
   $$

2. 对 $m = 1,2,…, M$

   a. 使用具有权值分布的 $D_m$ 的训练数据集学习得到基本分类器(学习的依据就是分类误差率最小，分类错误的权重和)
   $$
   G_m(x) : \mathcal{X} \rightarrow \lbrace c_1,c_2,\cdots, c_k \rbrace
   $$
   b.计算 $G_m(x)$ 在训练数据集上的分类误差率
   $$
   e_{m}=\sum_{i=1}^{N} P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)=\sum_{i=1}^{N} w_{mi} I\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)
   $$
   c. 计算 $G_m(x)$ 的系数
   $$
   \alpha_m = \frac{1}{2} \log(\frac{1-e_m}{e_m})
   $$
   这里的对数是自然对数

   d. 更新训练数据集的权值分布
   $$
   D_{m+1} = (w_{m+1,1}, …, w_{m+1, i}, …, w_{m+1, N}) \\
   w_{m+1, i} = \frac{w_{mi}}{Z_m} \exp(-\alpha_m I\left(G_{m}\left(x_{i}\right) = y_{i}\right)), \quad i =1,2,…,N
   $$
   这里， $Z_m$规范因子
   $$
   Z_m = \sum_{i = 1}^{N}w_{mi}\exp(-\alpha_m I\left(G_{m}\left(x_{i}\right) = y_{i}\right))
   $$
   $I\left(G_{m}\left(x_{i}\right) = y_{i}\right)$，当分类正确的时候取1，分类错误取0。二分类时可以 $y_iG_m(x_i)$ 代替

   它使 $D_{m+1}$ 称为一个概率分布

3. 构建基本分类器的线性组合
   $$
   f(x) = \sum_{m=1}^{M}\alpha_mG_m(x)
   $$
   最终得到分类器
   $$
   G(x) = \text{sign}(f(x))
   $$

注： $e_m$ 大的，$\alpha_m$ 小，这个时候观察权值的更新公式，对于分子来说，正确率高的，分子小，正确率低的，分子大， 这样就达到了提高被前一轮弱分类器错误分类的样本的权值，降低分类正确的样本的权值的目的

Q：Adaboost终止条件是什么？为什么不容易过拟合？

有些代码将终止条件设置为一个超参数，即弱分类器的个数。

为什么不容易过拟合？

知乎: 俞扬的回答

Adaboost在实验中表现出更加不容易过拟合（相对于别的boosting方法）的现象，尤其是在实验中发现，迭代中经验误差都已经不变化了的情况下，测试误差居然还能下降一段时间。

对于二分类问题，AdaBoost的训练误差以指数速率下降就很具有吸引力

1.2 AdaBoost算法解释

AdaBoost = 加法模型 + 损失函数(指数函数) + 学习算法(前向分步算法)

• 加法模型

$$
f(x) = \sum_{m=1}^{M} \beta_m b(x;\gamma_m)
$$

• 损失函数


$$
L(y,f(x)) = \exp(-yf(x))\\
(\alpha_m, G_m(x)) = \arg \min_{\alpha,G}\sum_{i = 1}^{N}\exp[-y_i(f_{m-1}(x_i) +\alpha G(x_i))]
$$

1.3 Adaboost代码实现

# 解决的问题：二分类，Y_label = {-1, 1} 这里简化特征X Xi = {0,1} (二值化处理)

# 算法实现思路
## 计算分类错误率，输入应该是：数据集和训练好的模弱分类器参数，返回预测结果和分类误差率
## 单层提升树： 输入：数据，权值分布 输出：创建的单层提升树
## 生成提升树：输入：数据， 输出：提升树
## 预测结果

def calc_e_Gx(X_trainArr, Y_trainArr, n, div, D):
    '''
    计算分类误差率
    n，要操作的特征
    div，划分的点
    D, 权值分布
    return 预测结果, 分类误差率
    '''
    # 初始化误差率
    e = 0 
    # 单独提取X, Y
    X_n = X_trainArr[:, n]
    Y_n = Y_trainArr
    predict = []
    
    for i in range(len(X_n)):
        if X_n[i] < div:
            predict[i] = -1
            if predict[i] != Y_train[i]: e += D[i]
        else:
            predict[i] = 1
            if predict[i] != Y_train[i]: e += D[i]
                
    return np.array(predict), e
    
def creatSingleTree(X_trainArr, Y_trainArr, D):
    # 该函数可以用其他弱分类器代替
    # 获得样本数目及特征数量
    m, n = np.shape(X_trainArr)
    
    # 单层树字典，用于存放当前提升树的参数，包括：分割点，预测结果，误差率(由预测结果计算)，
    # 该单层树所处理的特征 
    singleBoostTree = {} 
    # 初始化误差率，最大为100%
    singleBoostTree['e'] = 1
    
    # 遍历每一个特征，寻找用于划分的最合适的特征
    for i in range(n):
        # 由于特征进行了二值化处理，只能为0、1，因此切分点为 -0.5， 0.5，1.5
        for div in [-0.5, 0.5, 1.5]:
            Gx, e = calc_e_Gx(X_trainArr, Y_trainArr, i, div, D)
            if e < singleBoostTree['e']:
                singleBoostTree['e'] = e
                singleBoostTree['div'] = div
                singleBoostTree['Gx'] = Gx
                singleBoostTree['feature'] = i
    return singleBoostTree

def creatBoostingTree(X_trainArr, Y_trainArr, treeNum = 50):
    '''
    treeNum: 弱分类器的数目作为一个超参数，可以通过交叉验证挑选一个最好的
    return: 提升树
    '''
    m, n = np.shape(X_trainArr)
    
    # 初始化权值分布
    D = np.array([1 / m] * m)
    # 初始化树列表
    iterationNum = 0
    tree = []
    
    for i in range(treeNum):
        # 创建当层的提升树
        iterationNum += 1
        curTree = singleBoostTree(X_trainArr, Y_trainArr, D)
        # 计算alpha
        alpha = 1 / 2 * np.log((1 - curTree['e']) / curTree['e'])
        Gx = curTree['Gx']
        D = np.multiply(D, np.exp( -alpha * np.multiply(Y_trainArr, Gx))) / \
            sum(np.multiply(D, np.exp( -alpha * np.multiply(Y_trainArr, Gx))))
        curTree['alpha'] = alpha
        tree.append(curTree)
        
        # 当前训练集预测结果
        finalpredict += alpha * Gx
        # 当前预测误差数目
        error_count = 0
        for i in range(len(Y_trainArr)):
            if np.sign(finalpredict)[i] != Y_trainArr[i]:
                error_count +=  1
        
        error_rate = error_count / len(Y_trainArr)
        
        # 如果误差已经为0了，那么就可以停止了不用再计算了
        if error_rate == 0: return tree
    print('Numbers of iteration: {}, \n error rate: {}'.format(iterationNum, error_rate))
    return tree

def Gx_predict(x, div, feature):
    if x[feature] < div:
        return -1
    else:
        return 1

def model_predict(X_testArr, tree):
    prediction = []
    # 每一层的tree 有div，alpha，feature
    for i in range(len(X_testArr)):
        result = 0
        for curTree in tree:
            div = curTree['div']
            alpha = curTree['alpha']
            feature = curTree['feature']
            result += alpha * Gx_predict(X_testArr[i], div, feature)
        prediction.append(result)
    
    return prediction

def model_score(X_testArr, Y_testArr, tree):
    prediction = model_predict(X_testArr, tree)
    error_count = 0
    for i in range(len(Y_testArr)):
        if prediction[i] != Y_testArr[i]:
            error_count += 1
    score = 1 - (error_count / len(Y_testArr))
    
    return score

1.3 boosting tree

以决策树为基函数的提升方法称为提升树。可以是二叉分类树，或二叉回归树。

• 模型

$$
f_M(x) = \sum_{m = 1}^M T(x;\Theta_m)
$$

其中， $T(x;\Theta_m)$ 表示决策树， $\Theta_m$ 为决策树的参数， $M$ 为树的个数

• 参数确定(经验风险极小化)

$$
\hat{\Theta_m}=\arg \min_{\Theta_m} \sum_{i=1}^{N} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+T\left(x_{i}; \Theta_{m}\right)\right)
$$

• 损失函数
  • 平方误差损失函数的回归问题
  • 指数损失函数的分类问题
  • 一般损失函数的决策问题

当分类问题是二分类，AdaBoost算法的弱分类器限制为二分类即可，就是boosting tree

• 回归问题的提升树
  $$
  T(x;\Theta)=\sum_{j=1}^{J}c_j I(x \in R_j)
  $$
  其中，参数 $\Theta = \lbrace (R_1, c_1), (R_2, c_2),…,(R_J, c_J) \rbrace$ 表示树的区域划分和各区域上的常数， $J$ 是回归树的复杂度即叶结点的个数。

  • 采用平方误差损失函数
    $$
    \begin{align*}
    L(y,f_{m-1}(x) + T(x; \Theta_m)) &= [y - f_{m-1}(x) - T(x;\Theta_m)]^2\\
    &=[r-T(x;\Theta_m)]^2
    \end{align*}
    $$
    所以从损失函数可以看出，当前层树的确定，是通过拟合上一层模型的残差。所以算法可以通过将该层的训练数据给改为残差即可递归得到每一层的tree

• 参数更新(梯度下降)

$$
-[\frac{\partial L(y, f(x_i))}{\partial f(x_i)}]{f(x)=f{m-1}(x)}
$$

2. Bagging[Beriman, 1996a]

采用自主抽样法(bootstrap sampling)

• 确定样本集个数 $m$
• 又放回的抽取 $m$ 个样本
• 采样出 $T$ 个含 $m$ 样本的采样集
• 然后基于每个样本集训练一个基学习器
• 预测可以使用简单投票法

可以记录一下使用的数据，未被使用的数据可以用来对泛化性能进行“包外估计”

代码难度不大

使用random.sample()或者np.random.choice()就可以实现重抽样

random.sample()默认不重复抽样，可以抽取多维数据

np.random.choice() 默认重复抽样 replace=True, 不可以抽取多维数据，所以可以用这个函数产生下标。

3. Random Forest(RF)

Bagging 的变体，RF在基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。具体来说， 传统决策树在选择划分属性时是在当前结点的属性集合(假定有d个属性)中选择一个最优属性； 而在RF中， 对基决策树的每个结点， 先从该结点的属性集合中随机选择一个包含k个属性的子集， 然后再从这个子集中选择一个最优属性用于划分。若令$k=d$,则基决策树的构建与传统决策树相同；若令$k = 1$,则是随机选择一个属性用于划分； 一般情况下， 推荐值$k = log_2d$

算法：

输入：训练数据 $T$ ，基决策树(CART)，重抽样参数 $m$，属性集合参数 $k$

输出：最终分类器

for 1,2,…T

​ 重抽样数据(m个)，记录未被抽取的数据

​ 随机抽取k个属性

​ 根据重抽样的数据和确定的属性，学习基分类器 (如：CART)

end for

输出：最终分类器

4. Stacking

• 介绍

假设是五折的stacking，我们有一个train数据集和一个test数据集，那么一个基本的stacking框架会进行如下几个操作：

1、选择基模型。我们可以有xgboost，lightGBM，RandomForest，SVM，ANN，KNN，LR等等你能想到的各种基本算法模型。

2、把训练集分为不交叉的五份。我们标记为train1到train5。

3、从train1开始作为预测集，使用train2到train5建模(model1)，然后预测train1，并保留结果；然后，以train2作为预测集，使用train1，train3到train5建模，预测train2，并保留结果(model2)；如此进行下去…….直到把train1到train5各预测一遍；

4、把预测的结果按照train1到trian5的位置对应填补上，得到对train整个数据集在第一个基模型的一个stacking转换。

5、在上述建立的五个模型过程中，每个模型分别对test数据集进行预测，并最终保留这五列结果，然后对这五列取平均，作为第一个基模型对test数据的一个stacking转换。

6、然后进入第二层，将新特征作为第二层的train data，第一层的预测结果作为test data

7、一般使用LR(逻辑回归)作为第二层的模型进行建模预测。

但使用stacking会比较耗时，所以真正比赛的时候可以改为3折或4折

• Stacking的输出层为什么用逻辑回归？

stacking的有效性主要来自于特征抽取。而表示学习中，如影随形的问题就是过拟合，试回想深度学习中的过拟合问题。

在[5]中，周志华教授也重申了stacking在使用中的过拟合问题。因为第二层的特征来自于对于第一层数据的学习，那么第二层数据中的特征中不该包括原始特征，以降低过拟合的风险。举例：

• 第二层数据特征：仅包含学习到的特征
• 第二层数据特征：包含学习到的特征 + 原始特征

另一个例子是，stacking中一般都用交叉验证来避免过拟合，足可见这个问题的严重性。

为了降低过拟合的问题，第二层分类器应该是较为简单的分类器，广义线性如逻辑回归是一个不错的选择。在特征提取的过程中，我们已经使用了复杂的非线性变换，因此在输出层不需要复杂的分类器。这一点可以对比神经网络的激活函数或者输出层，都是很简单的函数，一点原因就是不需要复杂函数并能控制复杂度。

因此，stacking的输出层不需要过分复杂的函数，用逻辑回归还有额外的好处：

• 配合L1正则化还可以进一步防止过拟合
• 配合L1正则化还可以选择有效特征，从第一层的学习器中删除不必要的分类器，节省运算开销。
• 逻辑回归的输出结果还可被理解为概率

Reference

[1]. https://github.com/Dod-o/

[2]. 《统计学习方法》 – 李航

[3]. 《机器学习》 – 周志华

[4]. 【SPA大赛】腾讯广告点击大赛：对stacking的一些基本介绍

[5]. Zhou, Z.H., 2012. Ensemble methods: foundations and algorithms. CRC press.