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方法中计算了错误率,可以把它同时也输出出来,另外改变不同的迭代次数,可以对比一下训练错误率与测试错误率:

弱分类器数量(迭代次数)训练错误率测试错误率54.8%4.0%104.7%2.0%503.0%1.0%1002.5%2.0%2002.0%2.0%5000.8%2.0%10000.0%2.0%


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