AdaBoost元算法
1.1、基于数据集多重抽样的分类器将不同的分类器组合起来， 而这种组合的结果被称为集成方法（ensemble method）或元算法（meta-algorithm）。集成方法的多种形式：不同算法的集成；统一算法不同设置的集成；数据集不同部分分配给不同分类型的集成。 接下来，我们将介绍基于同一种分类器多个不同实例的两种计算方式。在这些方法中，数据集也会不断的变化，而后应用于不同的实例分类器上。
1.1.1、bagging,基于数据随机抽样的分类器构建方法自举汇聚法( bootstrap aggregating), 也称为bagging方法,是在从原始数据集选择S次后得到S个新数据集的一种技术。新数据集和原数据集的大小相等。每个数据集都是通过在原始数据集中随机选择一个样本来进行替换而得到的。这里的替换就意味着可以多次地选择同一样本。这一性质就允许新数据集中可以有重复的值，而原始数据集的某些值在新集合中则不再出现。 在S个数据集建好之后,将某个学习算法分别作用于每个数据集就得到了S个分类器。当我们要对新数据进行分类时，就可以应用这S个分类器进行分类。与此同时，选择分类器投票结果中最多的类别作为最后的分类结果。 当然，还有一些更先进的bagging方法，比如随机森林( random forest )。
1.1.2 boostingboosting是一种与bagging很类似的技术。不论是在boosting还是bagging当中，所使用的多个分类器的类型都是一致的。但是在前者当中，不同的分类器是通过串行训练而获得的，每个新分类器都根据已训练出的分类器的性能来进行训练。boosting是通过集中关注被已有分类器错分的那些数据来获得新的分类器。 由于boosting分类的结果是基于所有分类器的加权求和结果的,因此boosting与bagging不太一样。bagging中的分类器权重是相等的，而boosting中的分类 器权重并不相等，每个权重代表的是其对应分类器在上一轮迭代中的成功度。 boosting方法拥有多个版本，本章将只关注其中一个最流行的版本AdaBoost。
1.2、训练算法:基于错误提升分类器的性能 能否使用弱分类器和多个实例来构建一个强分类器?这是一个非常有趣的理论问题。这里的“弱”意味着分类器的性能比随机猜测要略好，但是也不会好太多。这就是说，在二分类情况下弱分类器的错误率会高于50%，而“强”分类器的错误率将会低很多。AdaBoost算法即脱胎于上述理论问题。 AdaBoost是adaptive boosting (自适应boosting)的缩写，其运行过程如下:训练数据中的每个样本，并赋予其一个权重,这些权重构成了向量D。一开始,这些权重都初始化成相等值。首先在训练数据上训练出一个弱分类器并计算该分类器的错误率,然后在同一数据集上再次训练弱分类器。在分类器的第二次训练当中,将会重新调整每个样本的权重,其中第一次分对的样本的权重将会降低，而第一次分错的样本的权重将会提高。为了从所有弱分类器中得到最终的分类结果，AdaBoost为每个分类器都分配了一个权重值alpha，这些alpha值是基于每个弱分类器的 错误率
ε
\varepsilon
ε 进行计算的。其中，错误率ε的定义为: 
alpha计算公式如下： 
AdaBoost算法流程图如下： 
计算出alpha值之后，可以对权重向量D进行更新,以使得那些正确分类的样本的权重降低而错分样本的权重升高。D的计算方法如下。 如果某个样本被正确分类，那么该样本的权重更改为:
D
i
(
i
+
1
)
=
D
i
(
i
)
e
−
α
S
u
m
(
D
)
D_i^{\left(i+1\right)}=\frac{D_i^{\left(i\right)}e^{-\alpha}}{Sum\left(D\right)}
Di(i+1)=Sum(D)Di(i)e−α 而如果某个样本被错分,那么该样本的权重更改为:
D
i
(
i
+
1
)
=
D
i
(
i
)
e
α
S
u
m
(
D
)
D_i^{\left(i+1\right)}=\frac{D_i^{\left(i\right)}e^\alpha}{Sum\left(D\right)}
Di(i+1)=Sum(D)Di(i)eα 在计算出D之后, AdaBoost又开始进入下- ~轮迭代。AdaBoost算法 会不断地重复训练和调整权重的过程，直到训练错误率为0或者弱分类器的数目达到用户的指定值为止。 接下来，我们将建立完整的AdaBoost算法。在这之前，我们首先必须通过一些代码来建立弱分类器及保存数据集的权重。
单层决策树( decision stump,也称决策树桩)是一种简单的决策树。前面我们已经介绍了决策树的工作原理，接下来将构建一个单层决策树,而它仅基于单个特征来做决策。由于这棵树只有一次分裂过程，因此它实际上就是一个树桩
如下图数据，如果想要试着从某个坐标轴上选择一个值(即选择一条与坐标轴平行的直线)来将所有的圆形点和方形点分开,这显然是不可能的。这就是单层决策树难以处理的一个著名问题。通过使用多棵单层决策树，我们就可以构建出一个能够对该数据集完全正确分类的分类器。 
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#just classify the data
'''
用于测试是否有某个值小于或者大于我们正在测试的阈值
:param dataMatrix: 数据集
:param dimen: 某个特征
:param threshVal: 阈值
:param threshIneq:
:return:
'''
retArray = ones((shape(dataMatrix)[0], 1))
if threshIneq == 'lt':
retArray[dataMatrix[:,dimen] threshVal] = -1.0
return retArray
# 将最小错误率minError设为+∞
# 对数据集中的每一个特征(第一层循环):
# 对每个步长(第二层循环):
# 对每个不等号(第三层循环):
# 建立一棵单层决策树并利用加权数据集对它进行测试
# 如果错误率低于minError,则将当前单层决策树设为最佳单层决策树
# 返回最佳单层决策树
def buildStump(dataArr,classLabels,D):
'''
生成单层决策树
在一个加权数据中循环，并找到具有最低错误率的单层决策树
:param dataArr: 训练数据集
:param classLabels: 类别标签列表
:param D: 权重矩阵，初始化是一个权重值相等的列矩阵，与数据集行相同
:return:
'''
dataMatrix = mat(dataArr); labelMat = mat(classLabels).T
m,n = shape(dataMatrix)
numSteps = 10.0;
bestStump = {};
bestClasEst = mat(zeros((m,1)))
minError = inf #init error sum, to +infinity
for i in range(n): # 对数据集中的每一个特征(第一层循环)
# 通过最大、最小值确定步长
rangeMin = dataMatrix[:,i].min();
rangeMax = dataMatrix[:,i].max();
stepSize = (rangeMax - rangeMin) / numSteps
# 对每个步长(第二层循环)
for j in range(-1,int(numSteps)+1):#loop over all range in current dimension
# 对每个不等号(第三层循环)
for inequal in ['lt', 'gt']: #go over less than and greater than
threshVal = (rangeMin + float(j) * stepSize) #阈值
# 分类预测值
predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)#call stump classify with i, j, lessThan
errArr = mat(ones((m,1))) # 初始错误
errArr[predictedVals == labelMat] = 0 # 将分类正确的特征，对应的errArr设置为0， 也就是分类错误的设置1， 因为我们要求的是错误率
weightedError = D.T*errArr #calc total error multiplied by D
if weightedError < minError:
print("split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f" % (i, threshVal, inequal, weightedError))
minError = weightedError
bestClasEst = predictedVals.copy()
bestStump['dim'] = i
bestStump['thresh'] = threshVal
bestStump['ineq'] = inequal
return bestStump,minError,bestClasEst
aggClassEst += alpha * classEst
1.4.2、aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T, ones((m, 1)))
#对每次迭代:
# 利用buildStump()函数找到最佳的单层决策树
# 将最佳单层决策树加入到单层决策树数组
# 计算alpha
# 计算新的权重向量D
# 更新累计类别估计值
# 如果错误率等于0.0，则退出循环
def adaBoostTrainDS(dataArr,classLabels,numIt=40):
weakClassArr = []
m = shape(dataArr)[0]
# 初始权重
D = mat(ones((m,1))/m) #init D to all equal
aggClassEst = mat(zeros((m,1)))
for i in range(numIt):
# 构建单层决策树， 错误率， 分类结果
bestStump, error, classEst = buildStump(dataArr, classLabels, D) # build Stump
# 计算alpha, max(error, 1e-16)是确保在没有错误的情况下， 不会出现除0溢出
alpha = float(0.5*log((1.0-error)/max(error,1e-16)))#calc alpha, throw in max(error,eps) to account for error=0
bestStump['alpha'] = alpha
# 将最佳单层决策树加入到单层决策树数组
weakClassArr.append(bestStump) #store Stump Params in Array
# 对权重D 进行更新： 正确分类的样本权重降低， 错误分类的样本提升
# 如何判断分类正确， 通过预测矩阵与标签矩阵相乘
expon = multiply(-1 * alpha * mat(classLabels).T, classEst) # exponent for D calc, getting messy
D = multiply(D, exp(expon)) # Calc New D for next iteration
D = D / D.sum()
#calc training error of all classifiers, if this is 0 quit for loop early (use break)
aggClassEst += alpha * classEst
print("aggClassEst: ",aggClassEst.T)
# 错误率累加计算
aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T, ones((m, 1)))
errorRate = aggErrors.sum() / m
print("total error: ", errorRate, "aggErrors:", sign(aggClassEst) != mat(classLabels).T)
if errorRate == 0.0: break
return weakClassArr, aggClassEst
