AdaBoost算法（AdbBoost Algorithm）—有监督学习方法、非概率模型、判别模型、非线性模型、非参数化模型、批量学习

定义

输入:训练数据集$T=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$,其中， x i ∈ χ ⊆ R n , y i ∈ y = { − 1 , + 1 } x_i \in \chi\subseteq R^n, y_i \in {\tt y}=\{ -1,+1 \} xi​∈χ⊆Rn,yi​∈y={−1,+1};弱学习算法;

输出:最终分类器$G(x)。$

(1)初始化训练数据的权值分布
$$D_1=({\omega }_{11},\cdots ,{\omega }_{1i},\cdots ,{\omega }_{1N}),{\omega }_{1i}=\frac{1}{N},i=1,2,\cdots ,N$$
(2)对$m=1,2,\cdots ,M$
      
(a)使用具有权值分布$D_m$的训练数据集学习，得到基本分类器
G m ( x ) : χ → { − 1 , + 1 } G_m(x): \chi \rightarrow \{ -1,+1 \} Gm​(x):χ→{−1,+1}
      
(b)计算$G_m(x)$在训练数据集上的分类误差率
$$e_m=\sum _{i=1}^{N}P(G_m(x_i)\ne y_i)=\sum _{i=1}^N{\omega }_{mi}I(G_m(x_i)\ne y_i)$$
      
©计算$G_m(x)$的系数
$${\alpha }_m=\frac{1}{2}log\frac{1-e_m}{e_m},此处的对数是自然对数$$
      
(d)更新训练数据集的权值分布
$$D_{m+1}=({\omega }_{m+1,1},\cdots ,{\omega }_{m+1,i},\cdots ,{\omega }_{m+1,N})$$
$${\omega }_{m+1,i}=\frac{{\omega }_{mi}}{Z_m}exp(-{\alpha }_m{y}_i{G}_m(x_i)),i=1,2,\cdots ,N$$
$$其中Z_m是规范化因子,Z_m=\sum _{i=1}^N{\omega }_{mi}exp(-{\alpha }_m{y}_i{G}_m(x_i)),它使D_{m+1}成为一个概率分布$$
(3)构建基本分类器的线性组合
$$f(x)=\sum _{m=1}^M{\alpha }_m{G}_m(x)$$
      得到最终分类器
$$G(x)=sign(f(x))=sign(\sum _{m=1}^M{\alpha }_m{G}_m(x))$$

输入空间

T= { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x N , y N ) } \left\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\right\} {(x1​,y1​),(x2​,y2​),…,(xN​,yN​)}

import time
import numpy as npdef loadData(fileName):'''加载Mnist数据集 下载地址：https://download.csdn.net/download/nanxiaotao/89720991）:param fileName:要加载的文件路径:return: 数据集和标签集'''#存放数据及标记dataArr = []; labelArr = []#读取文件fr = open(fileName)#遍历文件中的每一行for line in fr.readlines():curLine = line.strip().split(',')dataArr.append([int(int(num) > 128) for num in curLine[1:]])if int(curLine[0]) == 0:labelArr.append(1)else:labelArr.append(-1)#返回数据集和标记return dataArr, labelArr

trainDataList, trainLabelList = loadData('../Mnist/mnist_train.csv')

np.shape(trainDataList)

特征空间（Feature Space）

trainDataList[0][0:784]

统计学习方法

模型

$$G(x)=sign(f(x))=sign(\sum _{m=1}^M{\alpha }_m{G}_m(x))$$

策略

$${\omega }_{m+1,i}=\frac{{\omega }_{mi}}{Z_m}exp(-{\alpha }_m{y}_i{G}_m(x_i)),i=1,2,\cdots ,N$$
$$({\alpha }_m,G_m(x))=arg\ast \underset{\alpha ,G}{\min }\sum _{i=1}^{N}exp[-y_i(f_{m-1}(x_i)+\alpha G(x_i))],其中f(x)=\sum _{m=1}^M{\alpha }_m{G}_m(x)$$

算法

trainDataList = trainDataList[:10000]
trainLabelList = trainLabelList[:10000]
treeNum = 40 #树的层数

$$e_m=\sum _{i=1}^{N}P(G_m(x_i)\ne y_i)=\sum _{i=1}^N{\omega }_{mi}I(G_m(x_i)\ne y_i)$$

def calc_e_Gx(trainDataArr, trainLabelArr, n, div, rule, D):'''计算分类错误率:param trainDataArr:训练数据集数字:param trainLabelArr: 训练标签集数组:param n: 要操作的特征:param div:划分点:param rule:正反例标签:param D:权值分布D:return:预测结果， 分类误差率'''#初始化分类误差率为0e = 0x = trainDataArr[:, n]y = trainLabelArrpredict = []if rule == 'LisOne':    L = 1; H = -1else:                   L = -1; H = 1#遍历所有样本的特征mfor i in range(trainDataArr.shape[0]):if x[i] < div:predict.append(L)if y[i] != L: e += D[i]elif x[i] >= div:predict.append(H)if y[i] != H: e += D[i]return np.array(predict), e

$${\alpha }_m=\frac{1}{2}log\frac{1-e_m}{e_m}$$
$${\omega }_{m+1,i}=\frac{{\omega }_{mi}}{Z_m}exp(-{\alpha }_m{y}_i{G}_m(x_i)),i=1,2,\cdots ,N$$
$$D_{m+1}=({\omega }_{m+1,1},\cdots ,{\omega }_{m+1,i},\cdots ,{\omega }_{m+1,N})$$

def createSigleBoostingTree(trainDataArr, trainLabelArr, D):'''创建单层提升树:param trainDataArr:训练数据集数组:param trainLabelArr: 训练标签集数组:param D: :return: 创建的单层提升树'''#获得样本数目及特征数量m, n = np.shape(trainDataArr)sigleBoostTree = {}#误差率最高也只能100%，因此初始化为1sigleBoostTree['e'] = 1#对每一个特征进行遍历，寻找用于划分的最合适的特征for i in range(n):#因为特征已经经过二值化，只能为0和1，因此分切分时分为-0.5， 0.5， 1.5三挡进行切割for div in [-0.5, 0.5, 1.5]:for rule in ['LisOne', 'HisOne']:#按照第i个特征，以值div进行切割，进行当前设置得到的预测和分类错误率Gx, e = calc_e_Gx(trainDataArr, trainLabelArr, i, div, rule, D)#如果分类错误率e小于当前最小的e，那么将它作为最小的分类错误率保存if e < sigleBoostTree['e']:sigleBoostTree['e'] = e#同时也需要存储最优划分点、划分规则、预测结果、特征索引#以便进行D更新和后续预测使用sigleBoostTree['div'] = divsigleBoostTree['rule'] = rulesigleBoostTree['Gx'] = GxsigleBoostTree['feature'] = i#返回单层的提升树return sigleBoostTree

def createBosstingTree(trainDataList, trainLabelList, treeNum = 50):'''创建提升树:param trainDataList:训练数据集:param trainLabelList: 训练测试集:param treeNum: 树的层数:return: 提升树'''#将数据和标签转化为数组形式trainDataArr = np.array(trainDataList)trainLabelArr = np.array(trainLabelList)#没增加一层数后，当前最终预测结果列表finallpredict = [0] * len(trainLabelArr)#获得训练集数量以及特征个数m, n = np.shape(trainDataArr)D = [1 / m] * m#初始化提升树列表，每个位置为一层tree = []#循环创建提升树for i in range(treeNum):curTree = createSigleBoostingTree(trainDataArr, trainLabelArr, D)alpha = 1/2 * np.log((1 - curTree['e']) / curTree['e'])Gx = curTree['Gx']D = np.multiply(D, np.exp(-1 * alpha * np.multiply(trainLabelArr, Gx))) / sum(D)curTree['alpha'] = alphatree.append(curTree)finallpredict += alpha * Gxerror = sum([1 for i in range(len(trainDataList)) if np.sign(finallpredict[i]) != trainLabelArr[i]])finallError = error / len(trainDataList)if finallError == 0:    return treeprint('iter:%d:%d, sigle error:%.4f, finall error:%.4f'%(i, treeNum, curTree['e'], finallError ))#返回整个提升树return tree

tree = createBosstingTree(trainDataList,trainLabelList,treeNum)

假设空间（Hypothesis Space）

$$\left\{f|f(x)=sign(\sum _{m=1}^M{\alpha }_m{G}_m(x))\right\}$$

输出空间

Y ∈ { − 1 , 1 } Y \in \{ -1,1 \} Y∈{−1,1}

模型评估

训练误差

testDataList, testLabelList = loadData('../Mnist/mnist_test.csv')
testDataList = testDataList[:1000]
testLabelList = testLabelList[:1000]

def predict(x, div, rule, feature):'''输出单独层预测结果:param x: 预测样本:param div: 划分点:param rule: 划分规则:param feature: 进行操作的特征:return:'''#依据划分规则定义小于及大于划分点的标签if rule == 'LisOne':    L = 1; H = -1else:                   L = -1; H = 1#判断预测结果if x[feature] < div: return Lelse:   return H

def model_test(testDataList, testLabelList, tree):'''测试:param testDataList:测试数据集:param testLabelList: 测试标签集:param tree: 提升树:return: 准确率'''#错误率计数值errorCnt = 0#遍历每一个测试样本for i in range(len(testDataList)):#预测结果值，初始为0result = 0#遍历每层的树for curTree in tree:#获取该层参数div = curTree['div']rule = curTree['rule']feature = curTree['feature']alpha = curTree['alpha']#将当前层结果加入预测中result += alpha * predict(testDataList[i], div, rule, feature)#预测结果取sign值，如果大于0 sign为1，反之为0if np.sign(result) != testLabelList[i]: errorCnt += 1#返回准确率return 1 - errorCnt / len(testDataList)

accuracy = model_test(testDataList[:1000], testLabelList[:1000], tree)
print('the accuracy is:%d' % (accuracy * 100), '%')

测试误差

模型选择

正则化

过拟合

泛化能力