Weka AdaBoost.docx

Weka算法Classifier-meta-AdaBoostM1源码分析（一）多分类器组合算法简单的来讲常用的有voting,bagging和boosting，其中就效果来说Boosting略占优势，而AdaBoostM1算法又相当于Boosting算法的“经典款”。Voting思想是使用多分类器进行投票组合，并按照少数服从多数（大多数情况）来决定最终的分类，缺点是少数服从多数的规则往往只能避免达到最差的情况却也很难达到最少的情况。Bagging思想是有放回的随机抽样来训练多个分类器，最后使用voting来进行投票决策，经典算法如RandomForest（之前也有博客分析过），缺点是要求各基分类器同构，并且从精度上来讲Bagging并不是一个明显提高精度的算法，而是一个防止过拟合的算法。Boosting是使用级联训练分类器，使得“下一级”分类器更加重视“上一级”分错的数据，最后把各分类器结果加权组合来进行决策，缺点是需要级联训练因此算法难于并行化。比较经典的算法如AdaBoostM1、GBDT。一、算法算法部分简单说一下，并不做详细的形式化描述及相关理论正确性的证明，参考资料来自于wiki/wiki/AdaBoost算法过程：（1）初始化训练集各实例权重为1/k（假设总共k个用例）（2）for i=1;i 0.5，所以w1），对于分类错误的实例，原训练集中的权重乘以w（即调高权重）。（9）归一化训练集权重（缩小一定倍数使和为1）（10）回到2可以看到，根据这个算法，第四步训练得到了基分类器，每个基分类器都会在第七部得到一个权重，最后进行分类预测的时候就根据每个基分类器的结果进行加权投票得到最终的结果。二、实现在分析每个分类器的时候，我们都从buildClassifier入手，这次也不例外。javaview plaincopy1. publicvoidbuildClassifier(Instancesdata)throwsException2. 3. super.buildClassifier(data);/weka里面有个工具是可以从一个分类器以深度拷贝的方式新建一个分类器，而adaboostm1作为一个多分类器的combine，这个深度拷贝必须要拷贝每一个基分类器，这个就是在super类中实现的。4. 5. /看看这个数据能否用adaboost来分类，从代码来看，只能处理枚举类型，但我认为这个应该是由基分类器能力决定的。6. getCapabilities().testWithFail(data);7. 8. /预处理9. data=newInstances(data);10. data.deleteWithMissingClass();11. 12. /如果只有一个属性列，当然也就是分类本身的属性，这时没法使用任何复杂分类方法，就只是用mZero模型，mZero模型简单的返回枚举值中出现最多的值。13. if(data.numAttributes()=1)14. System.err.println(15. Cannotbuildmodel(onlyclassattributepresentindata!),16. +usingZeroRmodelinstead!);17. m_ZeroR=newweka.classifiers.rules.ZeroR();18. m_ZeroR.buildClassifier(data);19. return;20. 21. else22. m_ZeroR=null;23. 24. 25. m_NumClasses=data.numClasses();26. if(!m_UseResampling)&27. (m_ClassifierinstanceofWeightedInstancesHandler)28. buildClassifierWithWeights(data);/如果基分类器本身就是一个权重敏感的分类器，那么就不需要使用重抽样，否则使用重采样方法，常见的权重敏感的分类器的实现有很多，比如之前介绍过的J48,RandomTree，RandomForest,Bagging等。29. else30. buildClassifierUsingResampling(data);/否则使用重抽样的方法。31. 32. 三、基分类器AdaBoostM1使用的默认基分类器是weka.classifiers.trees.DecisionStump，名字直译过来就是决策桩（这什么名字？！），其分类方法类似于ID3算法的节点分裂算法，如果是枚举型的，遍历所有属性，选出其中一个属性，使使用该属性进行分类后的熵增益最大，如果是数值型的，选择一个节点做二分，使分类后方差最小。但和决策树不同的是，并不做递归的树生长，只做一次节点选择并分裂（所以叫桩而不是树）。这个基分类器大体思路就是这样，代码较简单并且没有什么巧妙的算法思想，故不做具体分析。四、buildClassifierWithWeight上篇文章分析主流程的时候，可以看到最后主流程最后把训练过程委派给了buildClassifierWithWeight和buildClassifierUsingResampling，先来分析一下buildClassifierWithWeightview sourceprint?01.protectedvoidbuildClassifierWithWeights(Instances data)02.throwsException 03.04.Instances trainData, training;05.doubleepsilon, reweight;06.Evaluation evaluation;07.intnumInstances = data.numInstances();08.Random randomInstance =newRandom(m_Seed);09.10./ /初始化11.m_Betas =newdoublem_Classifiers.length;12.m_NumIterationsPerformed =0;13.14./ 从直观认识上讲，算法训练模型的时候，不应该改变训练数据或者把训练集弄脏，因此需要做一个Instances的深度拷贝。15.training =newInstances(data,0, numInstances);16.17./ 主循环，boosting使用的基分类器数量就是m_Classifiers数组长度。18.for(m_NumIterationsPerformed =0; m_NumIterationsPerformed m_Classifiers.length;19.m_NumIterationsPerformed+) 20.if(m_Debug) 21.System.err.println(Training classifier + (m_NumIterationsPerformed +1);22.23./ 这里可以设置一个百分数，代表权重分位数，低于该分位数的实例会被过滤掉，这里是体现了boosting的“每次迭代着重考虑之前分错的实例”这种思想。24.if(m_WeightThreshold 100) 25.trainData = selectWeightQuantile(training,26.(double)m_WeightThreshold /100);27.else28.trainData =newInstances(training,0, numInstances);29.30.31./训练基分类器，如果是一个不稳定的随机分类器，先设置一个种子。32.if(m_Classifiersm_NumIterationsPerformedinstanceofRandomizable)33.(Randomizable) m_Classifiersm_NumIterationsPerformed).setSeed(randomInstance.nextInt();34.m_Classifiersm_NumIterationsPerformed.buildClassifier(trainData);35.36./ 进行模型准确度的估计，枚举型返回准确率，数值型返回方差，但因为AdaBoostM1不支持数值型，所以这里可以认为返回准确率。需要注意的是这里的估计方法就是把training里的每一个Instance放到基分类器里进行预测，相当于训练集和测试集是同一个集合，因此对于AdaBoostM1，必须选择弱分类器，可以预见到，如果是一个强分类器（如REPTree和不剪枝的J48），导致数据过拟合，这里得到的errorRate就为0，进而直接退出迭代。37.evaluation =newEvaluation(data);38.evaluation.evaluateModel(m_Classifiersm_NumIterationsPerformed, training);39.epsilon = evaluation.errorRate();40.41./ 如果错误率大于0.5（那还分个毛。），或者错误率是0（完全分类），就退出。42.if(Utils.grOrEq(epsilon,0.5) | Utils.eq(epsilon,0) 43.if(m_NumIterationsPerformed =0) 44.m_NumIterationsPerformed =1;/ If were the first we have to to use it45.46.break;47.48./ 设置此基分类器的权重，并且重新设置整个训练集中各用例的权重49.m_Betasm_NumIterationsPerformed = Math.log(1- epsilon) / epsilon);50.reweight = (1- epsilon) / epsilon;51.if(m_Debug) 52.System.err.println( error rate = + epsilon53.+ beta = + m_Betasm_NumIterationsPerformed);54.55.56./ 下面这个函数做了两个事：1、对于training里分错的对象，让其权重乘以reweight，即提高了权重 2、du对训练集所有权重进行归一化，使之和为1（即稍微同比缩小一点）57.setWeights(training, reweight);58.59.可以看到，此函数并没有对训练集根据权重进行重抽样，因为基分类器自身就是权重敏感的分类器。但是从设计的角度来吐个槽的话，个人认为这并不是一个非常好的设计，AdaBoostM1类作为一个基分类器的wrapper，必须对整个训练及分类结果负责，并不能因为基分类器“仅仅实现了权重敏感接口”就完全信任其权重敏感的操作，再从算法本身的角度来讲，实现“权重敏感”的逻辑本身就是AdaBoostM1算法的一部分，不应委派给基分类器去做。五、buildClassifierUsingResamplingview sourceprint?01.protectedvoidbuildClassifierUsingResampling(Instances data)02.throwsException 03.04.Instances trainData, sample, training;05.doubleepsilon, reweight, sumProbs;06.Evaluation evaluation;07.intnumInstances = data.numInstances();08.Random randomInstance =newRandom(m_Seed);09.intresamplingIterations =0;10.11./ 初始化所有基分类器的权重数组，迭代次数等。12.m_Betas =newdoublem_Classifiers.length;13.m_NumIterationsPerformed =0;14./ 深度拷贝训练集15.training =newInstances(data,0, numInstances);16.sumProbs = training.sumOfWeights();17.for(inti =0; i training.numInstances(); i+) 18.training.instance(i).setWeight(training.instance(i).19.weight() / sumProbs);/初始化权重为均值。20.21.22./ 主循环23.for(m_NumIterationsPerformed =0; m_NumIterationsPerformed m_Classifiers.length;24.m_NumIterationsPerformed+) 25.if(m_Debug) 26.System.err.println(Training classifier + (m_NumIterationsPerformed +1);27.28.29./ 低权重过滤30.if(m_WeightThreshold 100) 31.trainData = selectWeightQuantile(training,32.(double)m_WeightThreshold /100);33.else34.trainData =newInstances(training);35.36.37./ 重采样38.resamplingIterations =0;39.double weights =newdoubletrainData.numInstances();40.for(inti =0; i weights.length; i+) 41.weightsi = trainData.instance(i).weight();42.43.do44.sample = trainData.resampleWithWeights(randomInstance, weights);/根据权重重采样，算法是Walkers method, see pp. 232 of Stochastic Simulation by B.D. Ripley，我完全找不到出处，并且原代码可读性比较差，如果有知道该算法的读者望留个言，谢谢了。45.46./ 训练基分类器47.m_Classifiersm_NumIterationsPerformed.buildClassifier(sample);48.evaluation =newEvaluation(data);49.evaluation.evaluateModel(m_Classifiersm_NumIterationsPerformed,50.training);51.epsilon = evaluation.errorRate();52.resamplingIterations+;53.while(Utils.eq(epsilon,0) &54.(resamplingIterations MAX_NUM_RESAMPLING_ITERATIONS);/因为重采样的不稳定性，所以这里会训练多次，MAX