模式识别-第11章 独立于算法的机器学习

模式识别–独立于算法的机器学习第十一章独立于算法的机器学习模式识别–独立于算法的机器学习11.1模式识别中的哲学这里讨论的是一些独立于具体识别算法的一般性原理，但可以适用于任何一个特定的识别方法：1.没有免费午餐定理；2.丑小鸭定理；3.Occam剃刀原理。模式识别–独立于算法的机器学习没有免费的午餐定理（NFL,NoFreeLunchTheorem）不存在一个与具体应用无关的，普遍适用的“最优分类器”；学习算法必须要作出一个与问题领域有关的“假设”，分类器必须与问题域相适应。模式识别–独立于算法的机器学习丑小鸭定理（UglyDuckling）不存在与问题无关的“最优”的特征集合或属性集合；也同样不存在与问题无关的模式之间的“相似性度量”。模式识别–独立于算法的机器学习Occam剃刀原理设计者不应该选用比“必要”更加复杂的分类器，“必要”是由训练数据的拟合情况决定的；在对训练数据分类效果相同时，“简单的”分类器往往优于“复杂的”分类器；根据“没有免费午餐定理”，不能说“简单的”分类器对“复杂的”分类器具有天生的优越性，但在现实世界中遇到的各种问题，这种优越性往往是存在。模式识别–独立于算法的机器学习11.2分类性能评价方法使用什么样本测试分类器的性能？如何划分样本集?两分法：随机地将样本集D划分为不相交的两个集合Dl和Dt，分别用于学习分类器和测试分类器性能。训练样本集(Dl)测试样本集(Dt)模式识别–独立于算法的机器学习分类性能评价方法交叉验证：将样本集D随机地划分为互不相交的k个子集：1.使用k-1个子集的样本训练一个分类器；2.测试没有参与训练子集的样本；3.重复k次取平均。留一法（刀切法）：k=nD1…D2Dk-1DkDlDt模式识别–独立于算法的机器学习分类性能评价方法Bootstrap方法（自助法）:1.从样本集D中有放回地抽取n个样本用于训练；2.从样本集D中有放回地抽取n个样本用于测试；3.重复k次取平均。样本集D样本集Dl样本集Dt模式识别–独立于算法的机器学习11.3分类设计的重采样技术分类器设计的重采样技术也被称为“自适应的权值重置和组合（arcing,adaptivereweightingandcombining）；这类方法的主要思想是利用同一个训练样本集合构造多个分类器，然后以某种方式将这些分类器组合成一个分类器；主要方法包括：bagging算法和boosting算法模式识别–独立于算法的机器学习bagging算法1.从大小为n的原始数据集D中独立随机地抽取n’个数据(n’n)，形成一个自助数据集；2.重复上述过程，产生出多个独立的自助数据集；3.利用每个自助数据集训练出一个“分量分类器”；4.最终的分类结果由这些“分量分类器”各自的判别结果投票决定。模式识别–独立于算法的机器学习boosting算法boosting算法同样是利用训练样本集合构造多个分量分类器，它只要求这个分量分类器是一个弱分类器—准确率比平均性能好即可。2类问题，3个分量分类器的训练算法：1.在数量为n的原始样本集D中随机选取n1个样本构成D1，利用D1训练出一个分类器C1；2.在样本集D-D1中选择被C1正确分类和错误分类的样本各一半组成样本集D2，用D2训练出一个分类器C2；3.将样本集D-D1-D2中所有C1和C2分类结果不同的样本组成样本集D3，训练出一个分类器C3；模式识别–独立于算法的机器学习boosting的分类算法对新的样本x进行分类，如果C1和C2判别结果相同，则将x判别为此类别，否则以C3的结果作为x的类别；原始样本集分量分类器组合分类器模式识别–独立于算法的机器学习AdaBoost方法AdaBoost(adaptiveboosting)是boosting方法的一个重要变形，一般所说的boosting方法均是指AdaBoost；AdaBoost方法中，设计者可以不断地增加分量分类器，直到达到足够小的错误率为止；总体分类结果是由各分量分类器加权平均得到，权重由分量分类器的错误率确定。模式识别–独立于算法的机器学习AdaBoost方法1.begininitializeD,kmax,W1(i)1/n,i=1,…,n；2.k0;3.dokk+14.训练使用按照Wk(i)采样D的弱分类器Ck；5.Ek用Wk(i)采样D的样本集测量Ck的训练误差；6.7.8.untilk=kmax；9.end1ln12kkkEE1,,kkkkkWieWiZe正确分类错误分类模式识别–独立于算法的机器学习AdaBoost方法算法中Wk(i)为每一步迭代中对每个样本的加权，Zk是归一化因子，Ck为第k个分量分类器，αk为对Ck的加权；总体的判别函数由各分量分类器的加权平均得到：其中为Ck分类器给出的判别结果。max1kkkkghxxkhx模式识别–独立于算法的机器学习AdaBoost方法的推广能力AdaBoost方法实际上是增加了分类器的复杂程度，但实践表明此方法出现“过拟合”的现象极少，这是此方法最吸引人的地方。模式识别–独立于算法的机器学习针对特征的Boosting算法特征选择：就是从一组数量为n的特征中选择出数量为m的最优特征；1.最优特征组合的评价标准；2.选择出最优特征组合的算法；Boosting可以作为特征选择的方法。模式识别–独立于算法的机器学习AdaBoost特征选择算法Givenexamples(x1,y1),…,(xn,yn),whereyi=0,1fornegativeandpositiveexamplesrespectively;Initializeweightsw1,i=1/2m,1/2lforyi=0,1respectively,wheremandlarethenumberofnegativesandpositivesrespectively;Fort=1,…,T:1.Normalizetheweights:sothatwtisaprobabilitydistribution.,,,1ntititjj模式识别–独立于算法的机器学习AdaBoost特征选择算法2.Foreachfeature,j,trainaclassifierhjwhichisrestrictedtousingasinglefeature.Theerrorisevaluatedwithrespecttowt,3.Choosetheclassifierht,withthelowesterror4.Updatetheweights:whereei=0ifexamplexiisclassifiedcorrectly,ei=1otherwise,andThefinalclassifieris:jijiiiwhxyt11,,ietititww1ttt1111,20,TTttttthxhxotherwise1logtt