1. 概念

1.1 League of Legends 还是 AdaBoost？

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

键盘侠

1.2 真正的AdaBoost

1.2.1 样本空间

假定给定一个二分类的训练数据集，其中是一个维的向量，标签。

1.2.2 表达式

在公式中，是弱学习器的计算结果，是弱学习器模型，是弱学习器的数量。
在每迭代过程中，每次迭代都会选择一个弱学习器，并且给其分配一个权重，这样的话，对于第个样本而言，整个AdaBoost模型在第轮时的训练误差可以表达为：

在公式中是根据之前次迭代得到的模型，是本轮学习的弱学习器，在学习完成之后会添加到最终模型中。

1.2.3 AdaBoost的损失函数

函数表达式：

图1.1 函数图像

1.2.4 AdaBoost 的前生今世

假设经过了代之后（），对于第个样本而言，公示可以表示为

根据公式有

当损失函数为Exponential loss的时候：

公式中，由于是一个定值，记为。所以，假设，且当时，有，则公式可以记为：

如果在样本空间中，AdaBoost模型能够正确分类的情况下，有：；当分类错误时：。因此，公式可以写为：

在公式中，要使AdaBoost模型分类尽可能的正确，即要找到一个使得项尽可能的小（假设），因此对求导有：

令公式为：

由于与无关，公式左右同时取对数：

又因次之后，错误率为：

所以公式为

最终，通过更新为即可提升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. 给每一个样本同样的权重，表示他们一开始对于分类器是同等重要的。

2. 计算不同特征值下正确与错误分类的数量，并计算其基尼系数。

图3.2 三个决策树桩的计算结果

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

以特征Patient Weight作为决策树桩时，在整个训练集上仅个错误，即。根据公式，可以计算出该分类器的权重为：

3. 通过权重重新调整数据分布。

• 对于错误的样本，增加权重。
  

  图3.3 第一个分类器错误的样本
  
  

• 对于分类正确的样本，减少权重。
  

  图3.4 第一个分类器正确的样本
  
  
  

• 正则化权重.
  
  

  图3.5 具有新权重的数据集

4. 创建新的数据分布（要与原数据具有同样的shape）

此时，将图3.5中的数据当成概率分布。随机选择一个内的数字:

• 若，则将第0条数据（Yes, Yes, 205, Yes）添加进新数据集；
• 若，则将第2条数据（No, Yes, 180, Yes）添加进新数据集；
• 若，则将第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. 参考文献

• 维基百科比大多数博主讲的要好！
• 一文读懂机器学习常用损失函数(Loss Function)
• 西瓜书
• 统计学习方法