AdaBoost算法（Adaptive Boost）的核心思想是：如果一个弱分类器的分类效果不好，那么就构建多个弱分类器，综合考虑它们的分类结果和权重来决定最终的分类结果。很多人认为AdaBoost是监督学习中最强大的两种算法之一（另一个是支持向量机SVM）。

AdaBoost的训练过程如下：

为每个训练样本初始化相同的权重；

针对训练样本及权重，找到一个弱分类器；

计算出这个弱分类器的错误率ε与权重α；

对正确分类的样本，降低其权重，对错误分类的样本，提升其权重；

返回2不断迭代，直至弱分类器数量足够；

其中错误率ε定义为分错的样本数除以总样本数。权重α定义为：

权重提升与降低的公式如下：

对未知样本分类时，用每个弱分类器进行分类，将结果乘以这个分类器的权重α，累加到一起得到一个猜测值，根据其正负决定最终输出1还是-1。注意AdaBoost只能解决二分类问题，如果多于2个分类，需要做一定变通。

在AdaBoost中，广泛使用单层决策树（Decision Stump）作为弱分类器。之前研究ID3算法的决策树时，样本特征是离散型数据，这回研究连续型数据，因此之前的方法就不可用了，需要基于边界比较来确定分类。另外需要注意要同时考虑权重D来决定最佳切分方式。基本思路如下：

foreach(每一个维度){在此维度最大最小值之间切出N个边界foreach(每一个边界){针对"<="与">"两种情况{获取此条件下的分类结果（满足记为1，不满足记为-1）foreach(每一个结果){if(猜测错误)累加加权错误率}保留最小加权错误率的切分方式}}}

由于只在一个维度上切分一次，可以想像单层决策树的错误率应该相当高，是典型的弱分类器。但是综合考虑它们的结果及权重，最终的分类错误率可以做到大大低于单个单层决策树。上完整C#版AdaBoost的实现代码：

首先是DataVector，之前Label一直是字符串，这回要出现1和-1了，因此改造一下，使Label的类型可定义：

usingSystem;namespaceMachineLearning{///<summary>///数据向量///</summary>///<typeparamname="TData">特征类型</typeparam>///<typeparamname="TLabel">标签数据</typeparam>publicclassDataVector<TData,TLabel>{///<summary>///N维数据///</summary>publicTData[]Data{get;privateset;}///<summary>///分类标签///</summary>publicTLabelLabel{get;set;}///<summary>///构造///</summary>///<paramname="dimension">数据维度</param>publicDataVector(intdimension){Data=newTData[dimension];}///<summary>///维度数量///</summary>publicintDimension{get{returnthis.Data.Length;}}}}

然后是一个存储单层决策树的结构：

usingSystem;usingSystem.Collections.Generic;namespaceMachineLearning{///<summary>///单层决策树///</summary>publicclassDecisionStump{///<summary>///分类器权重///</summary>publicdoubleAlpha{get;set;}///<summary>///加权错误率///</summary>publicdoubleError{get;set;}///<summary>///在哪个维度上切分///</summary>publicintDimension{get;set;}///<summary>///切分边界///</summary>publicdoubleBoundary{get;set;}///<summary>///是否按大于来切分///</summary>publicboolGreaterThan{get;set;}///<summary>///此分类器在训练数据集上的分类结果///</summary>publicList<int>Results{get;set;}}}

最后是AdaBoost：

usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;namespaceMachineLearning{///<summary>///AdaBoost(基于单层决策树)///</summary>publicclassAdaBoost{///<summary>///弱分类器列表///</summary>privateList<DecisionStump>m_WeakClassifiers;///<summary>///训练///</summary>///<paramname="trainingSet">训练数据集</param>///<paramname="iterateCount">迭代次数，即弱分类器数量</param>publicvoidTrain(List<DataVector<double,int>>trainingSet,intiterateCount=50){m_WeakClassifiers=newList<DecisionStump>();varD=newList<double>();vargue***esults=newList<double>();for(inti=0;i<trainingSet.Count;++i){//权重初始化为1/nD.Add(1.0/trainingSet.Count);//猜测结果初始化为0，后面累加要用gue***esults.Add(0.0);}//迭代指定次数for(inti=0;i<iterateCount;++i){//在当前权重下生成一棵错误率最低的单层决策树varstump=CreateDecisionStump(trainingSet,D);//计算Alpha（注意stump.Error有可能为0，要防止除0错误）stump.Alpha=0.5*Math.Log((1-stump.Error)/Math.Max(stump.Error,1e-16));//保存这个决策树到弱分类器m_WeakClassifiers.Add(stump);//根据猜测结果，重新计算下一轮的权重向量D(暂时未除以Sum(D)，下一步再处理)for(intj=0;j<trainingSet.Count;++j){if(stump.Results[j]==trainingSet[j].Label)D[j]=D[j]*Math.Exp(-1.0*stump.Alpha);elseD[j]=D[j]*Math.Exp(stump.Alpha);}//保证Sum(D)==1doublesum=D.Sum();for(intj=0;j<trainingSet.Count;++j){D[j]=D[j]/sum;gue***esults[j]+=stump.Alpha*stump.Results[j];}//计算总错误率interrors=0;for(intj=0;j<trainingSet.Count;++j){if(Math.Sign(gue***esults[j])!=trainingSet[j].Label)++errors;}//如果没有错误，可以提前退出循环，但一般很难达到if(errors==0)break;}}///<summary>///分类///</summary>///<paramname="vector">待测数据</param>///<returns>分类结果，1或-1</returns>publicintClassify(DataVector<double,int>vector){doubleresult=0.0;vardataSet=newList<DataVector<double,int>>();dataSet.Add(vector);//用每一个弱分类器的结果乘以相应的alpha，累加得到最终的猜测结果foreach(varcinm_WeakClassifiers){varstumpResults=ClassifyByDecisionStump(dataSet,c.Dimension,c.Boundary,c.GreaterThan);result+=stumpResults[0]*c.Alpha;}//根据正负决定输出1还是-1returnMath.Sign(result);}///<summary>///根据单层决策树进行一次分类///</summary>///<paramname="dataSet">数据集</param>///<paramname="dimension">在哪个维度上分类</param>///<paramname="boundary">分类边界</param>///<paramname="greaterThan">是否按大于来划分数据</param>///<returns>结果</returns>privateList<int>ClassifyByDecisionStump(List<DataVector<double,int>>dataSet,intdimension,doubleboundary,boolgreaterThan){varresult=newList<int>();foreach(varitemindataSet){if(greaterThan)result.Add(item.Data[dimension]>boundary?1:-1);elseresult.Add(item.Data[dimension]<=boundary?1:-1);}returnresult;}///<summary>///构建一个单层决策树///</summary>///<paramname="dataSet">数据集</param>///<paramname="D">权重</param>///<returns>此权重下的最佳单层决策树</returns>privateDecisionStumpCreateDecisionStump(List<DataVector<double,int>>dataSet,List<double>D){varstump=newDecisionStump();doubleminError=double.PositiveInfinity;//遍历每一个维度for(inti=0;i<dataSet[0].Dimension;++i){//找此维度的最大最小值doublemaxValue=double.NegativeInfinity;doubleminValue=double.PositiveInfinity;foreach(varitemindataSet){if(item.Data[i]>maxValue)maxValue=item.Data[i];if(item.Data[i]<minValue)minValue=item.Data[i];}//做10次切分，计算步长doublestepSize=(maxValue-minValue)/10.0;for(intj=0;j<10;++j){//边界doubleboundary=minValue+stepSize*j;//分别计算边界两边的情况for(intk=0;k<2;++k){varresults=ClassifyByDecisionStump(dataSet,i,boundary,k==0);//计算错误，注意是加权的错误doubleweightError=0.0;for(intidx=0;idx<results.Count;++idx){if(results[idx]!=dataSet[idx].Label)weightError+=D[idx];}//保留最小错误的分类器if(weightError<minError){minError=weightError;stump.Error=Math.Min(weightError,1.0);//此分类器的错误比例stump.Boundary=boundary;//分类边界stump.Dimension=i;//在哪个维度上分类stump.GreaterThan=false;//大于还是小于stump.Results=results;//用此分类器得出的结果}}}}returnstump;}}}

最后上测试，还是使用上次的breast-cancer-wisconsin.txt做测试，顺便也和kNN对比一下。上测试代码：

publicvoidTestAdaBoost(){vartrainingSet=newList<DataVector<double,int>>();vartestSet=newList<DataVector<double,int>>();//读取数据varfile=newStreamReader(@"breast-cancer-wisconsin.txt",Encoding.Default);for(inti=0;i<699;++i){stringline=file.ReadLine();varparts=line.Split(',');varp=newDataVector<double,int>(9);for(intj=0;j<p.Dimension;++j){if(parts[j+1]=="?")parts[j+1]="0";p.Data[j]=Convert.ToDouble(parts[j+1]);}p.Label=Convert.ToInt32(parts[10])==2?1:-1;//和上次一样，600个做训练，99个做测试if(i<600)trainingSet.Add(p);elsetestSet.Add(p);}file.Close();//检验varboost=newAdaBoost();boost.Train(trainingSet);//默认50次迭代interror=0;foreach(varpintestSet){varlabel=boost.Classify(p);if(label!=p.Label)error++;}Console.WriteLine("Error={0}/{1},{2}%",error,testSet.Count,(error*100.0/testSet.Count));}

最终结果是99个测试样本猜错1个，错误率1.01%，相当不错。

在Train方法中计算了错误率，可以把它同时也输出出来，另外改变不同的迭代次数，可以对比一下训练错误率与测试错误率：

可以看到，随着弱分类器越来越多，AdaBoost的训练错误率不断下降，最终收敛到0，但测试错误率在下降到最低点后又有所上升。