工具：PythonCharm 书中的代码是python2的，而我用的python3，结合实践过程，这里会标注实践时遇到的问题和针对python3的修改。
实践代码和训练测试数据可以参考这里
https://github.com/stonycat/ML-in-Action
（原书作者也提供了源码，但是存在一些问题，且在python3中有部分修改）
————————卖萌=￣ω￣=分割线———————————————————
一、几点概念
1、元算法：对其他算法进行组合的一种方式，这种组合结果也可以叫做集成方法。
2、bagging方法：也叫自举汇聚法（bootstrap aggregating），从原始数据集选择S次，得到S个新数据集的技术。新数据集与原数据集大小相等，每个数据集都是从原始数据中随机选择一个样本，然后再随机选择一个样本来代替这个样本而得到的。（如果感觉拗口，大概就理解成抽出样本之后又用其他的代替好了——抽样后放回）然后用这S个不同的数据集分别训练就得到S个不同的分类器，然后应用S个分类器进行分类，选择分类器投票结果最高的作为最后的分类结果（投票：各个分类器权值相等）
更先进的bagging方法就比如random forest。为什么讲到bagging呢？因为boosting就是一种与bagging很相似的技术。
二、boosting介绍
首先，boosting集成了多个分类器，和bagging一样，不同的分类器类型都是一致的，不过这些分类器是通过串行训练得到的（即每个新的分类器是通过原来已训练出的分类器训练得到的，所以说后面的分类器性能会越来越好~）
然后，boosting的分类结果是基于所有分类器加权求和得到的，这也是和bagging 不同的地方，bagging中的分类器权值都相等。boosting拥有多个版本，这里介绍其中最流行的Adaboost方法。很多人认为boosting和SVM是监督机器学习中最强大的两种方法，但是这它们之间也有很多相似之处，这里我还没有参透，就先不介绍了。。
三、Adaboost原理推导
这里参考了July大神的博客的一部分，数学好的同学可以查看原文。Adaboost算法的原理与推导。
AdaBoost，是英文”Adaptive Boosting”（自适应增强）的缩写，由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。
具体说来，整个Adaboost 迭代算法就3步：
第一步：初始化训练数据的权值分布。如果有N个样本，则每一个训练样本最开始时都被赋予相同的权值：1/N。（初始化的时权值相等）
假设数据集为D，各个样本权值为
其中i= 1,2,3,4,5……N，1表示第一次迭代（也可以说第0次，算初始化）
第二步：进行多轮迭代，训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
首先，计算Gm(x)在训练数据集上的分类误差率：
上面的公式就是计算分类后的误差率
然后计算alpha的值，由上述式子可知，
yi为标签（-1，1），Zm为规范化因子，使得Dm+1成为一个概率分布。上面的公式使得被基本分类器Gm(x)误分类样本的权值增大，而被正确分类样本的权值减小。就这样，通过这样的方式， AdaBoost方法能“重点关注”或“聚焦于”那些较难分的样本上。
第三步：将各个训练得到的弱分类器组合成强分类器。
从而得到最终分类器，如下：
三 、Adaboost代码实现
#coding=utf-8
from numpy import *
def loadSimpData():
datMat = matrix([[ 1. , 2.1],
[ 2. , 1.1],
[ 1.3, 1. ],
[ 1. , 1. ],
[ 2. , 1. ]])
classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]
return datMat,classLabels
#对数据进行分类
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#just classify the data
retArray = ones((shape(dataMatrix)[0],1))
if threshIneq == 'lt':
retArray[dataMatrix[:,dimen] <= threshVal] = -1.0
else:
retArray[dataMatrix[:,dimen] > threshVal] = -1.0
return retArray
#找到最佳决策树
def buildStump(dataArr,classLabels,D):
dataMatrix = mat(dataArr); labelMat = mat(classLabels).T
m,n = shape(dataMatrix)
numSteps = 10.0; bestStump = {}; bestClasEst = mat(zeros((m,1)))
minError = inf #最小错误率，开始初始化为无穷大
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): #遍历不同步长时的情况
for inequal in ['lt', 'gt']: #大于/小于阈值 切换遍历
threshVal = (rangeMin + float(j) * stepSize) #设置阈值
predictedVals = stumpClassify(dataMatrix, i, threshVal,inequal) #分类预测
errArr = mat(ones((m, 1)))#初始化全部为1（初始化为全部不相等）
errArr[predictedVals == labelMat] = 0#预测与label相等则为0，否则为1
# 分类器与adaBoost交互
# 权重向量×错误向量=计算权重误差（加权错误率）
weightedError = D.T * errArr
if weightedError < minError:
minError = weightedError #保存当前最小的错误率
bestClasEst = predictedVals.copy() #预测类别
#保存该单层决策树
bestStump['dim'] = i
bestStump['thresh'] = threshVal
bestStump['ineq'] = inequal
return bestStump, minError, bestClasEst #返回字典，错误率和类别估计
#完整adaboost算法
def adaBoostTrainDS(dataArr,classLabels,numIt=40): #numIt 用户设置的迭代次数
weakClassArr = []
m = shape(dataArr)[0]#m表示数组行数
D = mat(ones((m,1))/m) #初始化每个数据点的权重为1/m
aggClassEst = mat(zeros((m,1)))#记录每个数据点的类别估计累计值
for i in range(numIt):
# 建立一个单层决策树，输入初始权重D
bestStump,error,classEst = buildStump(dataArr,classLabels,D)
print ("D:",D.T)
# alpha表示本次输出结果权重
alpha = float(0.5*log((1.0-error)/max(error,1e-16)))#1e-16防止零溢出
bestStump['alpha'] = alpha #alpha加入字典
weakClassArr.append(bestStump) #字典加入列表
print ("classEst: ",classEst.T)
# 计算下次迭代的新权重D
expon = multiply(-1*alpha*mat(classLabels).T,classEst)
D = multiply(D,exp(expon))
D = D/D.sum()
# 计算累加错误率
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)
if errorRate == 0.0: break#错误率为0时 停止迭代
return weakClassArr,aggClassEst
#测试adaboost
def adaClassify(datToClass,classifierArr):
dataMatrix = mat(datToClass)#待分类样例 转换成numpy矩阵
m = shape(dataMatrix)[0]
aggClassEst = mat(zeros((m,1)))
for i in range(len(classifierArr)):#遍历所有弱分类器
classEst = stumpClassify(dataMatrix,\
classifierArr[0][i]['dim'],\
classifierArr[0][i]['thresh'],\
classifierArr[0][i]['ineq'])
aggClassEst += classifierArr[0][i]['alpha']*classEst
print (aggClassEst) #输出每次迭代侯变化的结果
return sign(aggClassEst) #返回符号，大于0返回1，小于0返回-1
#在难数据集上应用
#自适应数据加载函数
def loadDataSet(fileName):
numFeat = len(open(fileName).readline().split('\t')) #get number of fields
dataMat = []; labelMat = []
fr = open(fileName)
for line in fr.readlines():
lineArr =[]
curLine = line.strip().split('\t')
for i in range(numFeat-1):
lineArr.append(float(curLine[i]))
dataMat.append(lineArr)
labelMat.append(float(curLine[-1]))
return dataMat,labelMat其中，原书代码有一处报错：TypeError：list indices must be integers or slices，not str。
原因在于adaClassify函数中
**classEst = stumpClassify(dataMatrix, classifierArr[i][‘dim’],classifierArr[i][‘thresh’],classifierArr[i][‘ineq’])
aggClassEst += classifierArr[i][‘alpha’]classEst*出错了，要修改为：
classEst = stumpClassify(dataMatrix, classifierArr[0][i][‘dim’],classifierArr[0][i][‘thresh’],classifierArr[0][i][‘ineq’])
aggClassEst += classifierArr[0][i][‘alpha’]*classEst
即每个classifier后面需要添加[0],因为这里是根据字符串来索引，而list形式并不支持key，在测试时可以用输入classifier[0]，测试看看输出什么就明白了，我就是这么发现并修改这个bug的。。运行后结果如下图： 
下面是在给出的预测病马的案例，测试结果：
训练结果： 
测试结果： 
