集成学习-AdaBoost (分类)

作者: To_QT | 来源:发表于2019-08-08 01:40 被阅读6次

1. 概念

1.1 League of Legends 还是 AdaBoost?

LOL打团的思想是这样的:对面开团时,五个英雄各自有各自的作用,坦克要够肉,ADC要足够猥琐输出……所以,类型越全面,对面越容易团灭。
其实AdaBoost模型和LOL打团是一样一样的。面对数据集,每个基学习器(英雄)都有各自关注的部分,覆盖的越全面,学习效果越好。而且,有一定的先后顺序:先控再输出。。。

键盘侠

1.2 真正的AdaBoost

1.2.1 样本空间

假定给定一个二分类的训练数据集T=\{(\boldsymbol{x_1}, y_1),(\boldsymbol{x_2}, y_2),...,(\boldsymbol{x_N}, y_N)\},其中\boldsymbol{x_i}是一个1*d维的向量,标签y_i \in Y=\{-1, 1\}

1.2.2 表达式

\begin{align} F_T(\boldsymbol{x})=\sum_{t=1}^{T} \alpha_tf_t(\boldsymbol{x})\tag{1.1} \end{align}
在公式(1.1)中,f_t(\boldsymbol{x})是弱学习器的计算结果,f_t是弱学习器模型,T是弱学习器的数量。
在每迭代过程中,每次迭代都会选择一个弱学习器,并且给其分配一个权重\alpha_t,这样的话,对于第i个样本而言(i\leq N),整个AdaBoost模型在第t轮时的训练误差E_t可以表达为:
\begin{align} E_t=\sum_{i=1}^{N}E[F_{t-1}(\boldsymbol{x_i})+\alpha_t f_t(\boldsymbol{x_i})]\tag{1.2} \end{align}
在公式(1.4)F_{t-1}(\boldsymbol{x_i})是根据之前t-1次迭代得到的模型,f_t(\boldsymbol{x_i})是本轮学习的弱学习器,在学习完成之后会添加到最终模型中。

1.2.3 AdaBoost的损失函数

函数表达式:
L(y, f(x))=e^{[-yf(x)]} \tag{1.3}

图1.1 函数图像
1.2.4 AdaBoost 的前生今世

假设经过了m-1代之后(m<T),对于第i个样本而言,公示(1.1)可以表示为
\begin{align} F_{m-1}(\boldsymbol{x_i})=&\alpha_1f_1(\boldsymbol{x_i})+\alpha_2f_2(\boldsymbol{x_i})+...+\alpha_{m-1}f_{m-1}(\boldsymbol{x_i}) \tag{1.4} \end{align}
根据公式(1.3)
\begin{align} F_{m}(\boldsymbol{x_i})=F_{m-1}(\boldsymbol{x_i})+\alpha_{m}f_{m}(\boldsymbol{x_i}) \tag{1.5} \end{align}
当损失函数为Exponential loss的时候:
\begin{align} E=&\sum_{i=1}^{N}e^{-y_iF_{m}(\boldsymbol{x_i})}\\ =&\sum_{i=1}^{N}e^{-y_i(F_{m-1}(\boldsymbol{x_i})+\alpha_{m}f_{m}(\boldsymbol{x_i}))}\\ =&\sum_{i=1}^{N}e^{-y_iF_{m-1}(\boldsymbol{x_i})-y_i\alpha_{m}f_{m}(\boldsymbol{x_i})}\\ =&\sum_{i=1}^{N}e^{-y_iF_{m-1}(\boldsymbol{x_i})}e^{-y_i \alpha_{m}f_{m}(\boldsymbol{x_i})}\tag{1.6} \end{align}
公式(1.6)中,由于e^{-y_iF_{m-1}(\boldsymbol{x_i})}是一个定值,记为w_i。所以,假设w_i^{(1)}=1,且当m>1时,有w_i^{(m)}=e^{-y_iF_{m-1}(\boldsymbol{x_i})},则公式(1.6)可以记为:
\begin{align} E=&\sum_{i=1}^{N}w_i^{(m)}e^{-y_i\alpha_{m}f_{m}(\boldsymbol{x_i})}\tag{1.7} \end{align}
如果在样本空间中,AdaBoost模型能够正确分类的情况下,有:y_if_{m}(\boldsymbol{x_i})=1;当分类错误时:y_if_{m}(\boldsymbol{x_i})=-1。因此,公式(1.7)可以写为:
\begin{align} E=&\sum_{y_i=f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)} e^{-\alpha_{m}}+ \sum_{y_i \neq f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)} e^{\alpha_{m}} \\ =& \sum_{y_i = f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)}e^{-\alpha_{m}}+ \sum_{y_i \neq f_{m}(\boldsymbol{x_i})}^{N} w_i^{(m)}e^{\alpha_{m}}- \sum_{y_i \neq f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)}e^{-\alpha_{m}}+ \sum_{y_i \neq f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)}e^{-\alpha_{m}}\\ \\ =&\sum_{i=1}^{N} w_i^{(m)} e^{- \alpha_{m}}+ \sum_{y_i \neq f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)} e^{\alpha_{m}}- \sum_{y_i \neq f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)} e^{-\alpha_{m}} \\ \\ =&\sum_{i=1}^{N}w_i^{(m)} e^{-\alpha_{m}}+ \sum_{y_i \neq f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)}(e^{\alpha_{m}}-e^{-\alpha_{m}})\tag{1.8} \end{align}
在公式(1.8)中,要使AdaBoost模型分类尽可能的正确,即要找到一个\alpha_{m}使得\sum_{y_i \neq f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)}项尽可能的小(假设\alpha_{m}>0),因此对\alpha_{m}求导有:
\begin{align} \partial{E}/\partial{\alpha_{m}}=&-\sum_{i=1}^{N}w_i^{(m)} e^{-\alpha_{m}}+ \sum_{y_i \neq f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)}(e^{\alpha_{m}}+e^{-\alpha_{m}})\tag{1.9} \end{align}
令公式(1.9)0
\begin{align} 0=-\sum_{i=1}^{N}w_i^{(m)} e^{-\alpha_{m}}+ \sum_{y_i \neq f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)}(e^{\alpha_{m}}+e^{-\alpha_{m}})\\ e^{-\alpha_{m}} \sum_{y_i=f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)} = e^{\alpha_{m}} \sum_{y_i\neq f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)}\tag{1.10} \end{align}
由于e^{-\alpha_{m}}i无关,公式(1.10)左右同时取对数:
\begin{align}\\ -\alpha_{m}+In(\sum_{y_i=f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)}) =& \alpha_{m}+In(\sum_{y_i\neq f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)})\\ 2\alpha_{m} =& In(\sum_{y_i=f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)}) - In(\sum_{y_i\neq f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)}) \\ \alpha_{m} =& \frac{1}{2} In(\frac{\sum_{y_i=f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)}}{\sum_{y_i\neq f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)}}) \tag{1.11} \end{align}
又因m次之后,错误率\varepsilon_m为:
\begin{align} \varepsilon_m=\frac{\sum_{y_i \neq f_{m}(\boldsymbol{x_i})}^{N}w_i^{(m)}}{\sum_{i=1}^{N}w_i^{(m)}} \tag{1.12} \end{align}
所以公式(1.11)
\begin{align}\\ \alpha_{m} =& \frac{1}{2} In(\frac{1-\varepsilon_m}{\varepsilon_m}) \tag{1.11} \end{align}
最终,通过更新F_{m-1}F_{m}(\boldsymbol{x_i})=F_{m-1}(\boldsymbol{x_i})+\alpha_mf_m(\boldsymbol{x_i})即可提升AdaBoost模型的性能。

1.2.5 基本流程
西瓜书174

2. AdaBoost的另一种理解

艾瑞博迪嗨起来!

3. 提升树(Boosting Tree)

其实提升树并没有那么高大上,就是采用了决策树作为上述AdaBoost模型中的弱学习器,而且严格意义上来说,是决策树桩,下面通过一个栗子来说明,基于分类的提升树是怎么构建出来的。

3.1 数据

假定我们有数据集如图1所示。目标:用boosting tree去预测是否有心脏病(绿色列),三个特征(Chest Pain, Blocked Arteries, Patient Weight)。


图3.1 数据情况概览
1. 给每一个样本同样的权重,表示他们一开始对于分类器是同等重要的。

w=\frac{1}{data_size} = \frac{1}{8}

2. 计算不同特征值下正确与错误分类的数量,并计算其基尼系数。
图3.2 三个决策树桩的计算结果

由于特征Patient Weight的基尼系数最小,因此,选择该特征所构成的决策树桩作为第一个分类器。

以特征Patient Weight作为决策树桩时,在整个训练集上仅1个错误,即\varepsilon_1=\frac{1}{8}。根据公式(1.11),可以计算出该分类器的权重为:
\begin{align}\\ \alpha_{1} =& \frac{1}{2} In(\frac{1-\varepsilon_1}{\varepsilon_1})\\ =& \frac{1}{2} In(\frac{1-\frac{1}{8}}{\frac{1}{8}}) \\ =& 0.97 \end{align}

3. 通过权重重新调整数据分布。
  • 对于错误的样本,增加权重。

    图3.3 第一个分类器错误的样本
    w_3 = \frac{1}{8} * e^{-0.97*(1*-1)}=0.33
  • 对于分类正确的样本,减少权重。

    图3.4 第一个分类器正确的样本
    w_0=w_1=w_2=\frac{1}{8} * e^{-0.97*(1*1)}=0.05
    w_4=w_5=w_6=w_7=\frac{1}{8} * e^{-0.97*(-1*-1)}=0.05
  • 正则化权重.
    w_i=\frac{w_i}{\sum_{j=0}^{7}w_j}=\frac{w_i}{0.68}

    图3.5 具有新权重的数据集
4. 创建新的数据分布(要与原数据具有同样的shape)

此时,将图3.5中的数据当成概率分布。随机选择一个(0,1)内的数字n:

  • n_1 \in (0, 0.07],则将第0条数据(Yes, Yes, 205, Yes)添加进新数据集
  • n \in (0.07, 0.14],则将第2条数据(No, Yes, 180, Yes)添加进新数据集
  • n \in (0.21, 0.7],则将第2条数据(Yes, Yes, 167, Yes)添加进新数据集
    ... 以此类推

很明显,被第一个分类器分错的数据很入选新数据集的概率极大,可能有多条。假设新数据集是这样的:


图3.6 第一轮结束后新的数据集

跳转步骤1 。直到模型中有指定数量的分类器后结束。


4. 代码

源代码

class AdaBoost(object):
    def __init__(self, n_estimator, weaker_learner, column_type):
        '''
        AdaBoost 模型初始化
        :param n_estimator: 选取n_estimator个弱学习器
        '''
        # 弱学习器的数量
        self.n_estimator = n_estimator
        # 每一列数据的类型(连续/离散)
        self.column_type = column_type
        # 初始化每个学习器权重
        self.alpha = [1] * n_estimator
        # 初始弱学习器数组
        self.weaker_learners = []

        # 初始化样本数据集大小以及特征数量
        self.data_size, self.feature_size = 0, 0

        # 特征的索引值
        self.feature_indices = []

        # 初始化弱学习器
        self.weaker_learner = weaker_learner
        # 初始化训练集的权值分布
        self.w = None

    def __initArgs__(self, _X, _Y):
        '''
        相关参数初始化
        :param _X: 训练集特征值
        :param _Y: 训练集标签值
        :return:
        '''
        self.train_x = _X
        self.train_y = _Y
        self.data_size, self.feature_size = _X.shape
        self.feature_indices = [_ for _ in range(self.feature_size)]

    def getErrorRate(self, true_y, fake_y):
        '''
        计算第ith_estimator个弱学习器的误差
        :param fake_y: 弱学习器的编号
        :return: 弱学习器的错误率
        '''
        aggErrors = np.multiply(np.mat(true_y) != np.mat(fake_y), np.ones(fake_y.shape))
        return aggErrors.sum() / true_y.shape[0]

    def getAlpha(self, error_rate):
        '''
        计算第ith_estimator个弱学习器的权重
        :param error_rate: 错误率
        :return: 弱学习器对应的权重
        '''

        return 0.5 * np.log((1-error_rate)/error_rate)

    def fit(self, _X, _Y):
        '''
        AdaBoost 模型训练
        :param _X: 特征值
        :param _Y: 标签值
        :return:
        '''
        self.__initArgs__(_X, _Y)
        for ith_estimator in range(self.n_estimator):
            print('%d\'s estimator:' % ith_estimator)

            # 初始化分布
            self.w = 1 / self.data_size * np.ones((self.data_size, 1))

            # 新建一个弱学习器
            # 寻找最优的划分节点
            weaker_learner = self.weaker_learner(ith_estimator, self.column_type)

            weaker_learner.fit(_X, _Y)

            weaker_learner_result = weaker_learner.predict(_X)

            self.weaker_learners.append((weaker_learner.__root__.feature_index, weaker_learner))

            # 计算错误率
            error_rate = self.getErrorRate(self.train_y, weaker_learner_result)
            print('error_rate:', error_rate)

            # 计算该弱学习器的权重
            ith_alpha = self.getAlpha(error_rate)
            print('alpha:', ith_alpha)
            self.alpha[ith_estimator] = ith_alpha

            print(self.train_y)
            print(weaker_learner_result)

            # 更新w
            w_tmp = - ith_alpha * np.multiply(self.train_y, weaker_learner_result)
            self.w = np.multiply(self.w, np.exp(w_tmp))
            print('update weights:', self.w)
            # 规范化w
            self.w /= self.w.sum()
            print('normal weights:', self.w)

            # 如果错误率比随机猜还差,那就停止
            if error_rate > 0.5:
                break
            else:
                _X, _Y = self.resampleData()
                print('resample data')
                print(_X)
                print(_Y)

        print('train done')

    def resampleData(self):
        '''
        数据重采样,先计算每个样本需要被抽取的次数,
        然后列索引按照抽取次数从大到小排序(注意是列)
        :return:
        '''
        # 确定每个样本需要抽取的次数

        nums = list(np.multiply(self.w.T[0], self.data_size))

        # 将权重的索引按 权重的大小排序(从大到小)
        idx = list(np.argsort(self.w.T[0]))
        idx.reverse()


        new_index = []
        for id in idx:
            num_arr = (int(nums[id]) + 1) * [id]
            new_index.extend(num_arr)
            if len(new_index) == self.data_size:
                break
        return self.train_x[new_index], self.train_y[new_index]

    def predict(self, X):
        '''
        预测
        :param x: 1*d 维的特征值
        :return: 预测结果
        '''
        print('predict')
        result = []
        for x in X:
            res = 0
            for index, weaker_learner in enumerate(self.weaker_learners):
                res += self.alpha[index] * weaker_learner[1].predict(
                    np.array([x])
                )
            result.append(1 if res > 0 else -1)
        return np.array([result]).T

5. 小结

机器学习中最大的问题在于要面临数据集中维度灾难的问题,一般来说,减少了特征数量之后,虽然计算速度有所提升,但是鬼知道你去掉特征之后模型拟合优度有没有下降。AdaBoost模型不同于SVM和神经网络这两大算法,在AdaBoost模型中,你只要选择你认为有用的特征就好了,只要够小弟(基学习器)够多,啥样的模型都能画出来(当然这种过拟合的模型不要也罢)。

PS:用惯了pandas的行列索引之后,再使用Numpy简直就是个坑。


6. 参考文献

相关文章

  • 2019年上半年收集到的人工智能集成学习干货文章

    2019年上半年收集到的人工智能集成学习干货文章 机器学习-集成学习 集成学习——Adaboost分类 2019-...

  • 集成学习-AdaBoost (分类)

    1. 概念 1.1 League of Legends 还是 AdaBoost? LOL打团的思想是这样的:对面开...

  • 集成学习——Adaboost分类

    上一期分享了集成学习之Bagging分类的方法,这一期分享它的另外一种方法,Adaboost分类方。 Adaboo...

  • Adaboost算法简介

    Adaboost算法 Adaboost算法是一种有监督的学习方法,是基于Adaboost算法的分类器把若干个分类器...

  • Adaboost算法理解

    1、Adaboost作为一种集成学习方法,核心思想是经过多轮迭代,对分类器的权重参数每次迭代进行修正,然后集成得到...

  • 集成学习之AdaBoost

    一. AdaBoost介绍 我们在机器学习(八)-集成学习(Ensemble learning)中介绍了集成学习的...

  • 04 集成学习 - Boosting - AdaBoost算法构

    03 集成学习 - Boosting - AdaBoost算法原理 十、AdaBoost算法构建 上一章最后说明了...

  • GBDT集成算法(梯度提升树)

    一、算法思想 GBDT是集成学习Boosting算法中的一种,它与Adaboost相比,Adaboost算法利用...

  • 集成学习——AdaBoost

    集成学习 简单来说,集成学习就是将一组个体学习器结合起来,通过某种策略,将其结合成一个总学习器来完成相应任务;集成...

  • Boost-GBDT

    GBDT也是集成学习Boosting家族的成员,但是却和传统的Adaboost有很大的不同。回顾下Adaboost...

网友评论

    本文标题:集成学习-AdaBoost (分类)

    本文链接:https://www.haomeiwen.com/subject/wvbpdctx.html