【统计学习方法】 Adaboost算法 Python实现

我就是我 2022-06-08 12:11 188阅读 0赞

## 前言 ##

代码可在Github上下载:[代码下载][Link 1]  
  俗话说三个臭皮匠，顶个诸葛亮。应用在机器学习里面讲就是多个弱分类器，通过组合可以变成一个强分类器，这也便是集成学习的思想。今天所要讲的Adaboost（自适应提升）算法便是种思想的一种代表算法。Adaboost不同于SVM，是一种实践优先于理论的一种产物，是先发现这种算法有效，后来人们不断研究，用前向加法模型来证明它，为何会这种算法是有效的。

## 算法 ##

首先先来看下P138的算法。

> 引用《统计学习方法》P138 8.1.2算法  
> 输入：训练数据集T =\{  ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) (x\_1, y\_1), (x\_2, y\_2), ..., (x\_N, y\_N) (x1,y1),(x2,y2),...,(xN,yN)\}，其中 x i ∈ X ⊆ R n x\_i\\in X\\subseteq R^n xi∈X⊆Rn， y i ∈ Y = \{ − 1 , + 1 \} y\_i\\in Y= \\\{-1, +1\\\} yi∈Y=\{ −1,\+1\}；弱学习算法。  
> 输出：最终分类器G(x)  
> （1），初始化训练数据的权值分布 D 1 = ( w 11 , . . . , w 1 i , . . . , w 1 N ) ， 其 中 w 1 i = 1 / N ， i = 1 , 2 , . . . , N D1= (w11, ..., w1i, ..., w1N)，其中w1i= 1/N，i=1, 2, ..., N D1=(w11,...,w1i,...,w1N)，其中w1i=1/N，i=1,2,...,N  
> （2）对m=1, 2,…, M  
>  (a)使用具有权值分布Dm的训练数据集学习，得到基本分类器 G m ( x ) : X → \{ − 1 , + 1 \} G\_m(x): X\\rightarrow\\\{-1, +1\\\} Gm(x):X→\{ −1,\+1\}  
>  （b）计算Gm(x)在训练数据集上的分类误差率  
>  （c）计算Gm(x)的系数  
>  a m = 1 2 l o g 1 − e m e m a\_m = \\frac\{1\}\{2\} log\\frac\{1-e\_m\}\{e\_m\} am=21logem1−em  
> 这里的对数是自然对数。  
>  （d）更新训练数据集的权值分布 D m + 1 = ( w m + 1 , 1 , ⋯ &ThinSpace; , w m + 1 , i , ⋯ &ThinSpace; , w m + 1 , N ) D\_\{m+1\} = (w\_\{m+1,1\},\\cdots,w\_\{m+1, i\},\\cdots,w\_\{m+1, N\}) Dm\+1=(wm\+1,1,⋯,wm\+1,i,⋯,wm\+1,N)  
>  w m + 1 , i = w m i Z m e x p ( − a m y i G m ( x i ) ) w\_\{m+1, i\}=\\frac\{w\_\{mi\}\}\{Z\_m\}exp(-a\_m y\_i G\_m(x\_i)) wm\+1,i=Zmwmiexp(−amyiGm(xi))  
> 这里，Zm是规范化因子  
> 它使 D m + 1 D\_\{m+1\} Dm\+1成为一个概率分布。  
> （3）构建基本分类器的线性组合 f ( x ) = ∑ m = 1 M a m G m ( x ) f(x) = \\sum\_\{m=1\}^\{M\}a\_mG\_m(x) f(x)=m=1∑MamGm(x)  
> 得到最终分类器 G ( x ) = s i g n ( f ( x ) ) = s i g n ( ∑ m = 1 M a m G m ( x ) ) G(x)=sign(f(x))=sign(\\sum\_\{m=1\}^Ma\_mG\_m(x)) G(x)=sign(f(x))=sign(m=1∑MamGm(x))

如果初次看这本书的话，可能在这里的时候有一些问题。  
  这里有三个问题。  
  第一个问题：基本分类器是什么？我的理解是基本分类器是决策树桩。决策树我们之前也有学过，但是决策树桩是只有一个根节点的决策树。那可以想象到，一个决策树桩只能对某一维度的数据进行划分。也就是说比如有N个样本，每个样本有身高，体重，年龄等属性，那我们每次迭代要么就只能判断身高超过多少的为1，没超过的为-1，要么就只能判断体重超过多少的为1，没超过的为-1。具体选哪一维度，选多少为阈值，这个要根据计算误差率来判断，哪个维度、阈值的误差率最小就选哪个。  
  第二个问题：Adaboost的权值分布w是干嘛用的？w是权值用来计算 e m e\_m em用的。我们的目标是找出最小的误差率，根据P138的第二段如下。

> 提高那些被前一轮弱分类器错误分类样本的权值，降低那些被正确分类样本的权值。

根据书中公式(8.1)，如果一个样本权重很大，那么如果误分， I ( G m ( x i ) ≠ y i ) I\\left( \{ \{ \{\\rm\{G\}\}\_m\}\\left( \{ \{x\_i\}\} \\right) \\ne \{y\_i\}\} \\right) I(Gm(xi)̸=yi)会为1，会造成误差很大，那基本分类器选的肯定是为误差率最小的分类器，所以一个样本被分的次数越多，权重越大，后面会更倾向于选择能够正确分类这个样本的分类器。  
  第三个问题：Adaboost算法什么时候停止循环？根据P142页“Adaboost算法的训练误差分析”中的分析，Adaboost可以不断减少训练误差，并且是以指数速度下降的。这里我定义了一个误差率小于0.01停止。

class SingleDecisionTree:   #决策树桩
        def __init__(self, axis=0, threshold = 0, flag = True):
            self.axis = axis
            self.threshold = threshold
            self.flag = flag #flag=True, x>=threshold=1, 否则为-1

首先我想介绍的是决策树桩中的init，接受3个参数，一个是axis，表示这个决策树桩是按哪个维度划分，一个是threshold，表示这个决策树桩是按什么阈值划分，还有一个是flag，这个我要稍微说明下，有了阈值还不够成为一个分类器。比如是x>=2.5为1，还是x>=2.5为-1，所以需要这个标志来说明是哪种情况。在这个代码中，当flag=True时, x>=threshold=1, 否则为-1。  
  以下贴个代码，这次的代码，就是对应书上的P140 8.1.3例子。  
  这里有个坑要注意一下，可以看下P141页， G 2 G\_2 G2分类器和 G 3 G\_3 G3分类器， G 2 G\_2 G2是x<8.5预测为1， G 3 G\_3 G3是x>5.5预测为1，这里的flag要注意一下。

class SingleDecisionTree:   #决策树桩
        def preditct(self, x):
            if (self.flag == True):
                return -1 if x[self.axis] >= self.threshold else 1
            else:
                return 1 if x[self.axis] >= self.threshold else -1

接下是预测函数，根据flag的不同，维度和阈值来进行分类。

class SingleDecisionTree:   #决策树桩
        def preditctArr(self, dataSet):
            result = list()
            for x in dataSet:
                if (self.flag == True):
                    result.append(-1 if x[self.axis] >= self.threshold else 1)
                else:
                    result.append(1 if x[self.axis] >= self.threshold else -1)
            return result

这个函数是我为了书中公式(8.4)写的，我直接传一个X向量到分类器，分类器返回一个结果向量回来，这样就不用循环算那个权值分布啦。

class Adaboost:
        def train(self, dataSet, labels):
            N = np.array(dataSet).shape[0]    #样本总数
            M = np.array(dataSet).shape[1] #样本维度
            self.funList = list()  # 存储alpha和决策树桩
            D = np.ones((N, 1)) / float(N) #(1)数据权值分布
            #得到基本分类器 开始
            L = 0.5
            minError = np.inf    #初始化误差大小为最大值（因为要找最小值）
            minTree = None  #误差最小的分类器
            while minError > 0.01:
                for axis in range(M):
                    min = np.min(np.array(dataSet)[:, axis]) #需要确定阈值的最小值
                    max = np.max(np.array(dataSet)[:, axis]) #需要确定阈值的最大值
                    for threshold in np.arange(min, max, L):    #左开右闭
                        tree = SingleDecisionTree(axis=axis, threshold = threshold, flag=True)  #决策树桩
                        em = self.calcEm(D, tree, dataSet, labels)  #误差率
                        if (minError > em): #选出最小的误差，以及对应的分类器
                            minError = em
                            minTree = tree
                        tree = SingleDecisionTree(axis=axis, threshold = threshold, flag=False) #同上，不过flag的作用要知道
                        em = self.calcEm(D, tree, dataSet, labels)
                        if (minError > em):
                            minError = em
                            minTree = tree
                alpha = (0.5) * np.log((1 - minError) / float(minError))    #p139(8.2)
                self.funList.append((alpha, minTree))   #把alpha和分类器写到列表
                D = np.multiply(D, np.exp(np.multiply(-alpha * np.array(labels).reshape((-1, 1)), np.array(minTree.preditctArr(dataSet)).reshape((-1, 1))))) / np.sum(np.multiply(D, np.exp(np.multiply(-alpha * np.array(labels).reshape((-1, 1)), np.array(minTree.preditctArr(dataSet)).reshape((-1, 1)))))) #对应p139的公式(8.4)

接下来要开始介绍Adaboost了，首先是重头戏Adaboost的训练函数，首先看下注释，然后重点来看下while循环，while循环就是在重复算法8.1的(2)这部分，这部分到误差小于0.1的时候停止。首先先根据轴来遍历数据集，然后是阈值，然后不同的flag，根据这三者来选出误差率最小的分类器。其次是计算alpha，然后要将alpha和分类器（决策树桩）写到一个列表，以便构造出强分类器。最后是数据集的权值分布的更新，这里我是根据向量的形式进行更新的。

np.multiply(D, np.exp(np.multiply(-alpha * np.array(labels).reshape((-1, 1)), np.array(minTree.preditctArr(dataSet)).reshape((-1, 1)))))

minTree.preditctArr(dataSet)我刚才介绍过，可以得出 G m ( x i ) \{G\_m\}\\left( \{ \{x\_i\}\} \\right) Gm(xi)的结果，但是我是将数据集传参进去，得到的一个以向量形式的结果，然后跟标签向量相乘，再跟alpha相乘，最终以上这段代码得到了一个 N × 1 N \\times 1 N×1的一个向量。那么 Z m \{Z\_m\} Zm（书中式子8.5）就是这个向量的相加，用个np.sum即可得到。

class Adaboost:
        def calcEm(self, D, Gm, dataSet, labels):    #计算误差
            # value = list()
            value = [0 if Gm.preditct(row) == labels[i] else 1 for (i, row) in enumerate(dataSet)]
            return np.sum(np.multiply(D, np.array(value).reshape((-1, 1))))

这里的是计算误差的，其中value对应着 I ( G m ( x i ) ≠ y i ) I\\left( \{ \{ \{\\rm\{G\}\}\_m\}\\left( \{ \{x\_i\}\} \\right) \\ne \{y\_i\}\} \\right) I(Gm(xi)̸=yi)的一个向量表示，与D相乘还是一个向量，然后用np.sum来进行结果相加，这段代码对应着书中代码(8.1)。

class Adaboost:
        def predict(self, x):   #预测方法
            sum = 0
            for fun in self.funList:    #书上最终分类器的代码
                alpha = fun[0]
                tree = fun[1]
                sum += alpha * tree.preditct(x)
            return 1 if sum > 0 else -1

这段代码就是取出alpha和分类器然后用书中公式（8.7）实现。  
  至此，Adaboost的代码实现完毕。下面贴出全部代码。

import numpy as np
    
    class SingleDecisionTree:
        def __init__(self, axis=0, threshold = 0, flag = True):
            self.axis = axis
            self.threshold = threshold
            self.flag = flag #flag=True, x>=threshold=1, 否则为-1
    
        def preditct(self, x):
            if (self.flag == True):
                return -1 if x[self.axis] >= self.threshold else 1
            else:
                return 1 if x[self.axis] >= self.threshold else -1
    
        def preditctArr(self, dataSet):
            result = list()
            for x in dataSet:
                if (self.flag == True):
                    result.append(-1 if x[self.axis] >= self.threshold else 1)
                else:
                    result.append(1 if x[self.axis] >= self.threshold else -1)
            return result
    
    class Adaboost:
        def train(self, dataSet, labels):
            N = np.array(dataSet).shape[0]    #样本总数
            M = np.array(dataSet).shape[1] #样本维度
            self.funList = list()  # 存储alpha和决策树桩
            D = np.ones((N, 1)) / float(N) #(1)数据权值分布
            #得到基本分类器 开始
            L = 0.5
            minError = np.inf    #初始化误差大小为最大值（因为要找最小值）
            minTree = None  #误差最小的分类器
            while minError > 0.01:
                for axis in range(M):
                    min = np.min(np.array(dataSet)[:, axis]) #需要确定阈值的最小值
                    max = np.max(np.array(dataSet)[:, axis]) #需要确定阈值的最大值
                    for threshold in np.arange(min, max, L):    #左开右闭
                        tree = SingleDecisionTree(axis=axis, threshold = threshold, flag=True)  #决策树桩
                        em = self.calcEm(D, tree, dataSet, labels)  #误差率
                        if (minError > em): #选出最小的误差，以及对应的分类器
                            minError = em
                            minTree = tree
                        tree = SingleDecisionTree(axis=axis, threshold = threshold, flag=False) #同上，不过flag的作用要知道
                        em = self.calcEm(D, tree, dataSet, labels)
                        if (minError > em):
                            minError = em
                            minTree = tree
                alpha = (0.5) * np.log((1 - minError) / float(minError))    #p139(8.2)
                self.funList.append((alpha, minTree))   #把alpha和分类器写到列表
                D = np.multiply(D, np.exp(np.multiply(-alpha * np.array(labels).reshape((-1, 1)), np.array(minTree.preditctArr(dataSet)).reshape((-1, 1))))) / np.sum(np.multiply(D, np.exp(np.multiply(-alpha * np.array(labels).reshape((-1, 1)), np.array(minTree.preditctArr(dataSet)).reshape((-1, 1)))))) #对应p139的公式(8.4)
    
        def predict(self, x):   #预测方法
            sum = 0
            for fun in self.funList:    #书上最终分类器的代码
                alpha = fun[0]
                tree = fun[1]
                sum += alpha * tree.preditct(x)
            return 1 if sum > 0 else -1
    
        def calcEm(self, D, Gm, dataSet, labels):    #计算误差
            # value = list()
            value = [0 if Gm.preditct(row) == labels[i] else 1 for (i, row) in enumerate(dataSet)]
            return np.sum(np.multiply(D, np.array(value).reshape((-1, 1))))
    
    if __name__ == '__main__':
        # dataSet = [[0], [1], [2], [3], [4], [5], [6], [7], [8], [9]]  #例8.1的数据集
        # labels = [1, 1, 1, -1, -1, -1, 1, 1, 1, -1]
        dataSet = [[0, 1, 3], [0, 3, 1], [1, 2, 2], [1, 1, 3], [1, 2, 3], [0, 1, 2], [1, 1, 2], [1, 1, 1], [1, 3, 1], [0, 2, 1]]    #p153的例子
        labels = [-1, -1, -1, -1, -1, -1, 1, 1, -1, -1]
        adaboost = Adaboost()
        adaboost.train(dataSet, labels)
        # for x in dataSet:
        #     print(adaboost.predict(x))
        print(adaboost.predict([1, 3, 2]))

## 分析 ##

前面提到Adaboost是实践先于理论，

[Link 1]: https://github.com/FlameCharmander/MachineLearning