一种通用的集成学习算法

一种通用的集成学习算法

在机械学习领域，schapire等人提出的adaboost算法无疑是最受关注和研究的算法之一。该算法是一种基于valint提出的pac（可执行微锁）的学习模型。根据keean提出的模型学习和valint提出的弱学习概念，具体实现弱学习算法向强学习算法的转变的可操作算法。adaboost算法、realadaboost算法和gentreavobst算法已在许多领域得到应用。这是目前检测面部特征的最佳方法之一。基于adaboost算法的技术和思想，许多研究人员在制定该算法方面解决了多分类、价格复杂分类、不平衡分类、模糊分类等问题。然而，在推广这项算法时，几乎需要不同的处理方法，尤其是弱学习算法的结构。弱学习算法的泛化能力决定了集成学习算法的泛化能力。在实现训练错误（或错分）最小化的模式评价功能时，为了确保不出现学习，现有的许多集成学习算法都存在相应的分析不足。如果能对二分类、多分类、代价敏感分类、不平衡分类、多标签分类等众多分类预测问题的集成学习算法进行统一,包括对弱分类器的构造的统一必然是一件好事.集成学习算法的构造一般要求体现弱学习定理的思想,即算法能将弱学习算法提升为强学习算法,这并非易事.首先,弱学习定理成立的条件是弱学习算法要比随机猜测略好,这在二分类问题中容易实现,如果错误率大于0.5时,互换分类结果即可.但在多分类、代价敏感分类、不平衡分类等问题中,构造满足该条件的弱分类器是困难的,如果还要求统一的构造方法就更难.其次,算法需确保组合预测函数比单个简单预测函数的预测效果更好,这就要求算法不仅有低的训练错误率,还应该有好的泛化能力.泛化能力不仅涉及到简单预测函数的组合方式,还涉及到简单预测函数的构造方法.最理想的集成学习算法应该是既可以很好拟合样本(训练错误率可以趋于0)又不易出现过学习的算法.本文围绕boosting集成学习算法的统一和泛化能力的保证进行了较深入的研究,得到了一种通用的集成学习算法,其可以衍生出一系列具体的集成学习算法,包括经典的RealAdaBoost算法、多分类AdaBoost算法、GentleAdaBoost算法,多标签分类集成学习算法、代价敏感分类集成学习算法等,理论上这些算法还能实现学习错误任意小.为了算法的统一和好的泛化能力,本文指出简单预测函数可以统一基于单个特征来构造,对其不易出现过学习重要特性进行了分析与实验验证.1根据lx,l所作的1/3.设有预测函数f:X→RK,X为示例空间,f为X到K维空间RK的映射,所有X到RK的映射函数集记为Φ.示例x∈X的标识为K维空间RK中的向量Y=(y1,…,yK),并假设yk≥0(k=1,…,K),预测函数f(x)输出值为(f(x,1),…,f(x,K)).考虑如下的预测问题:如果(f(x,1),…,f(x,K))与(y1,…,yK)各分量的大小顺序一样,则称f(x)正确预测了x.对于这种只关注分量大小顺序的预测问题,首先需要定义其学习错误,以便基于该学习错误的最小化来构造集成学习算法.对f(x)输出值按式(1)进行乘积归一化处理后记为F(x):F(x,k)=exp(f(x,k)-ˉf(x))‚(1)其中ˉf(x)=1ΚΚ∑k=1f(x,k),并且Κ∏l=1F(x,l)=1,且(F(x,1),…,F(x,K))与(f(x,1),…,f(x,K))各分量的大小顺序完全一致.如果(F(x,1),…,F(x,K))与x在K维空间RK中的标识向量(y1,…,yK)的对应分量成比例,即∀l∈{1,…,K}有yl=cF(x,l),c>0,则f(x)就正确预测了x.于是定义如下的学习错误:ε=Ex∈X[Κ∑l=1(yl×(F(x,l))-1)].(2)因为Κ∑l=1(yl(F(x,l))-1)≥ΚΚ∏l=1(yl(F(x,l))-1)1/Κ=ΚΚ∏l=1(yl)1/Κ‚注意到该式的右边与f(x)无关,并当且仅当yl×(F(x,l))-1=c(常数),即yl=cF(x,l)时,Κ∑l=1(yl×(F(x,l))-1)取到极小值.集成学习算法可基于最小化ε来构造,即minf∈Φε=minf∈ΦEx∈X[Κ∑l=1(yl×(F(x,l))-1)].先不用关心示例x∈X的标识向量Y=(y1,…,yK)究竟是什么,后面的分析会指出,不同的赋值可得不同的学习算法.至于为何不直接采用(f(x,1),…,f(x,K))而用(F(x,1),…,F(x,K))来拟合(y1,…,yK),由前面的分析已经看出,如果没有乘积归一化条件,式(2)的极小值点无法保证yl=cF(x,l).后面的分析还会发现,采用指数函数对预测函数进行处理是为了在集成学习算法中形成递推公式.设训练样本集S={x1,…,xm},xi∈X的标识为K维空间RK中的向量Yi=(yi,1,…,yi,K),仍假设yi,k≥0(k=1,…,K),则上述预测函数的学习问题便转变成寻找f(x),使得式(3)取到极小值:ε=m∑i=1(ωiΚ∑l=1yi,l×(F(xi,l))-1)‚(3)其中{ωi}i=1,…,m为样本的概率分布,在没有其他先验条件下一般令ωi=1/m.考虑f(x)为多个简单预测函数ht(x)的组合,即f(x,l)=Τ∑t=1ht(x,l)‚ht(x)输出值为(ht(x,1),…,ht(x,K)),t=1,…,T.令¯ht(x)=1ΚΚ∑k=1ht(x,k),则ˉf(x)=Τ∑t=1¯ht(x),此时式(3)变为ε=m∑i=1(ωiΚ∑l=1yi,lexp(-f(xi,l)+ˉf(xi)))=Ζ0m∑i=1Κ∑l=1(ω1i,lΤ∏t=1exp(-ht(xi,l)+¯ht(xi)))‚(4)其中,ω1i,l=ωiyi,l/Z0,Z0为归一化因子:Ζ0=m∑i=1Κ∑l=1ωiyi,l.根据式(4)就可以形成递推公式,比如提取出包含h1(x)的项,令:Ζ1=m∑i=1Κ∑l=1(ω1i,lexp(-h1(xi,l)+¯h1(xi))),(5)ω2i,l=ω1i,lΖ1exp(-h1(xi,l)+¯h1(xi))‚(6)则式(4)变为ε=Ζ0Ζ1m∑i=1Κ∑l=1(ω2i,lΤ∏t=2exp(-ht(xi,l)+¯ht(xi))).(7)式(7)和式(4)类似,式(7)中t=2,…,T,而式(4)中t=1,…,T,容易形成递推公式.可见采用指数函数对预测函数进行处理是为了形成递推公式.我们可以先基于最小化Z1来构造h1(x),得到h1(x)后根据式(6)计算ω2i,l,式(7)与式(4)类似,可以采用类似的方法构造h2(x),h3(x),…,于是可得到如下的通用集成学习算法.算法1.通用集成学习算法.Step1.初始化权值:ω1i,l=ωiyi,l/Z0,i=1,…,m,l=1,…,K,Z0为归一化因子;Step2.DoFort=1,…,T.1)在权值为ωti,l的S上训练预测函数ht(x):基于最小化Zt来构造ht(x),其中:Ζt=m∑i=1Κ∑l=1(ωti,lexp(-ht(xi,l)+1ΚΚ∑k=1ht(xi,k)))；2)调整权值:ωt+1i,l=ωti,lΖtexp(-ht(xi,l)+1ΚΚ∑k=1ht(xi,k));Step3.组合预测函数f(x)输出(f(x,1),…,f(x,K)),其中:f(x,l)=∑t=1Τht(x,l).在算法1中,最小化Zt时采用不同的方法来构造ht(x)就能得到不同的集成学习算法,给(yi,1,…,yi,K)不同的赋值,可得到能解决不同问题的集成学习算法.由算法的构造过程可得到如下定理:定理1.对算法1得到的组合预测函数f(x),由式(3)定义的ε满足:ε=∏t=0ΤΖt.根据定理1,只要满足Zt≤1(Z0除外)并且一般情况下Zt<1,则算法1就具有如下性质:ε将随着预测函数个数T逐渐增加而逐渐减小.组合预测函数比单个简单预测函数更有效时称算法是有效的,于是,当算法满足条件:Zt≤1且一般情况下Zt<1,则算法是有效的.由于Z0不涉及到预测函数的构造,因此以下谈及Zt时一般不包括Z0.2简单预测函数算法1是非常通用的集成学习算法,其指出了简单预测函数的组合方式和一种可自适应的权值调整策略,许多具体集成学习算法可基于算法1来构造.为此,先对简单预测函数的构造进行说明.从分类的角度,ht(x)无外乎是可对示例空间X实现某种分割的一种划分,对位于不同划分段内的示例输出不同的值,位于同一划分段内的示例输出相同值.下面的集成学习算法的简单预测函数主要考虑能对X实现某种划分的预测函数.具体如何构造这种预测函数也有多种方法,其中最简单的方法便是基于样本的单个特征来划分X,如果特征是数字的则可以采用阈值法来划分.一个阈值可对X实现两段划分,n个阈值可对X实现n+1段划分.2.1基于htx的学习算法设ht(x)对X实现nt段划分,该划分对样本集S也有一个分割S=S1t∪…∪Sntt,当i≠j时,Sit∩Stj=∅.当xi∈Sjt时,ht(xi)输出值为(ht(xi,1),…,ht(xi,K)),其显然与j有关,可记为(αtj,1,…,αtj,Κ),j=1,…,nt.由于同一划分段内ht(x)输出值一样,合并Zt中相同项,并记ptj,l=∑i:(xi∈Sjt)ωi,lt,l=1,…,K,j=1,…,nt,可得:Ζt=∑i=1m∑l=1Κ(ωi,ltexp(-ht(xi,l)+ht¯(xi)))=∑j=1nt∑l=1Κ(ptj,lexp(-αtj,l+1Κ∑k=1Καtj,k))≥Κ∑j=1nt(∏l=1Κ(ptj,l)1/Κ).(8)根据算术平均大于等于几何平均及等号成立条件,当αtj,l=ln(ptj,l),Zt取到极小值:Ζt=Κ∑j=1nt(∏l=1Κ(ptj,l)1/Κ)‚训练ht(x)就转变成寻找可使Zt取到极小值的某个划分S=S1t∪…∪Sntt,在该划分上,ht(x)输出定义为x∈Sjt时,ht(x,l)=ln(ptj,l).于是由算法1可得如下的系列化集成学习算法.算法2.RealAdaBoost系列算法.Step1.初始化权值:ωi,l1=ωiyi,l/Z0,i=1,…,m,l=1,…,K,Z0为归一化因子;Step2.DoFort=1,…,T1)在权值为ωi,lt的S上训练预测函数ht(x):①对划分S=S1t∪…∪Sntt,计算ptj,l=∑i:(xi∈Sjt)ωi,lt；②定义ht(x):x∈Sjt时,ht(x,l)=ln(ptj,l),j=1,…,nt;③选取ht(x):最小化Ζt=Κ∑j=1nt(∏l=1Κ(ptj,l)1/Κ)‚选取ht(x).2)调整权值:ωi,lt+1=ωi,ltΖtexp(-ht(xi,l)+1Κ∑k=1Κht(xi,k));Step3.组合预测函数f(x),输出(f(x,1),…,f(x,K)),其中f(x,l)=∑t=1Τht(x,l).因为Ζt=Κ∑j=1nt(∏l=1Κ(ptj,l)1/Κ)≤∑j=1nt∑l=1Κptj,l=∑i=1m∑l=1Κωi,lt=1,并且仅当ptj,k=ptj,l对所有k,l=1,…,K,j=1,…,nt都成立才会有Zt=1,算法2满足条件:Zt≤1,并且一般情况下Zt<1,因此算法2是有效的.之所以称算法2是系列化集成学习算法,是因为算法2仍然具有通用性,xi的标识(yi,1,…,yi,K)仍然是可变的,对其进行不同赋值可得到不同算法.如采用下述方式赋值,便得到一种K分类集成学习算法.对K分类问题,设xi的类别标签为li∈{1,…,K},用K维向量(yi,1,…,yi,K)来标识xi,令yi,li=1,其余yi,l=0(l≠li),即xi的类别标签对应分量为1其余分量为0的向量来标识xi.得到f(x)后输出(f(x,1),…,f(x,K))中最大分量对应标签Η(x)=argmaxlf(x,l),则算法2便是已有的多分类RealAdaBoost算法.特别地,当K=2,H(x)≠l与-f(x,l)+f¯(x)>0等价,此时式(3)定义的学习错误ε正是训练错误率εtri的一个上界:εtri=1m∑i=1m〖Η(xi)≠li〗≤1m∑i=1m∑l=12yi,l(F(xi,l))-1.(9)由定理1可得:εtri≤∏t=1Τ(2∑j=1ntptj,1ptj,22).(10)当所有nt=2,即ht(x)采取二段划分时,式(10)与文献的结论完全一致,但此处的算法2可以是多段划分,并且可以直接处理多分类问题.2.2训练预测函数的性质算法2是通过求式(8)的极小值点来得到ht(x)的输出值αtj,l=ln(ptj,l).前面的分析已经指出,只要能保证Zt≤1,并且一般情况下Zt<1,便能保证集成学习算法的有效性.分析发现(随后证明),αtj,l=ptj,l/∑k=1Κptj,k也能满足条件,于是可得到如下的系列化集成学习算法.算法3.GentleAdaBoost系列算法.Step1.初始化权值:ωi,l1=ωiyi,l/Z0,i=1,…,m,l=1,…,K,Z0为归一化因子;Step2.DoFort=1,…,T1)在权值为ωi,lt的S上训练预测函数ht(x):①对划分S=S1t∪…∪Sntt,计算ptj,l=∑i:(xi∈Sjt)ωi,lt；②定义ht(x):x∈Sjt时,ht(x,l)=ptj,l/∑k=1Κptj,k‚j=1,⋯,nt；③选取ht(x):最小化Zt选取ht(x),其中Ζt=∑j=1nt∑l=1Κ(ptj,lexp(-ptj,l/∑k=1Κptj,k))exp(1/Κ).2)调整权值:ωi,lt+1=ωi,ltΖtexp(-ht(xi,l)+1Κ∑k=1Κht(xi,k)).Step3.组合预测函数f(x),输出(f(x,1),…,f(x,K)),其中f(x,l)=∑t=1Τht(x,l).类似地,对示例的标识采取不同的赋值方法可以得到不同的集成学习算法.针对K分类问题,用(yi,1,…,yi,K)来标识xi,令yi,li=1,其余yi,l=0(l≠li),li是xi的类标签.得到f(x)后输出标签Η(x)=argmaxlf(x,l),则算法3就是一种多分类GentleAdaBoost算法.算法3的有效性可证明如下:考察∑l=1Κ(αtj,lexp(-αtj,l)),注意到∑l=1Καtj,l=1.当x∈,函数g(x)=xexp(-x)的一阶导数g′(x)>0,且二阶导数g″(x)<0,这表明g(x)是一个上凸函数,于是:∑l=1Κ1Κ(αtj,lexp(-αtj,l))≤(∑l=1Κ1Καtj,l)exp(-∑l=1Κ1Καtj,l)=1Κexp(-1Κ).(11)由此可得Zt≤∑j=1nt∑l=1Κ(ptj,l)=∑i=1m∑l=1Κωi,lt=1.由g(x)的严格凸函数性质,一般情况下Zt<1,故算法3是有效的.2.3结构化集成学习算法正如不少文献分析指出:AdaBoost和RealAdaBoost(见算法2)的权值调整,将使调整后的各类样本的权值一样(均匀分布),即使已知类的先验分布,RealAdaBoost算法也只有在训练h1(x)时利用到该分布,即训练h1(x)时是针对不平衡的样本空间,而后的训练皆是基于分布均匀的样本空间进行的.对不平衡分类问题(类分布极度不平衡)应该有不一样的学习算法.根据前面的分析,在整个训练过程中,如果可以保持类分布不变,并且还能保证Zt≤1,并且一般情况下Zt<1就可以构造出不平衡分类问题的集成学习算法.设初始类分布为{P1,…,PK},分析发现(随后证明),取αtj,l=ln(ptj,l/Pl)时也满足条件,于是可得如下的不平衡分类问题的系列化集成学习算法.算法4.不平衡分类问题的系列集成学习算法.Step1.初始化权值:ωi,l1=ωiyi,l/Z0,i=1,…,m,l=1,…,K,Z0为归一化因子;Step2.DoFort=1,…,T1)在权值为ωi,lt的S上训练预测函数ht(x):①对划分S=S1t∪…∪Sntt,计算pj,lt=∑i:(xi∈Sjt)ωi,lt;②定义ht(x):x∈Sjt,ht(x,l)=ln(ptj,l/Pl),j=1,…,nt;③选取ht(x):最小化Ζt=∑j=1nt(∏l=1Κ(ptj,l/Ρl)1/Κ)‚选取ht(x).2)调整权值:ωi,lt+1=ωi,ltΖtexp(-ht(xi,l)+1Κ∑k=1Κht(xi,k)).Step3.组合预测函数f(x)输出,(f(x,1),…,f(x,K)),其中f(x,l)=∑t=1Τht(x,l).该算法与文献中的算法不同.类似地,对K分类问题,用(yi,1,…,yi,K)来标识xi,令yi,li=1,其余yi,l=0(l≠li),li是xi的类标签.得到f(x)后输出标签Η(x)=argmaxlf(x,l),就得到一种具体的适用于不平衡分类问题的集成学习算法.当然,既然考虑了类分布,一种更合理的标识向量可以是:令yi,li=Pli,其余yi,l=0(l≠li).容易验证,每一轮权值调整后l类样本的权值之和为PlZt,即算法始终保持了类分布不变.算法4的有效性可证明如下:Ζt=∑j=1nt(∏l=1Κ(ptj,l/Ρl)1/Κ)≤1Κ∑j=1nt(∑l=1Κptj,l/Ρl)=1Κ∑l=1Κ(∑j=1ntptj,l)1Ρl.(12)注意到∑j=1ntptj,l=Pl,因此有Zt≤1,并且只有当ptj,k/Pk=ptj,l/Pl对所有k,l=1,…,K,j=1,…,nt都成立才有Zt=1,一般情况Zt<1,因此算法4是有效的.上面根据不同的简单预测函数构造策略,得到了不同的集成学习算法,其中一些正是已有的一些经典算法.算法2～4本身仍然具有一定的通用性,故也称它们为系列化集成学习算法.xi的标识(yi,1,…,yi,K)给不同的赋值,将得到不同的具体算法.前面只针对最常用的K分类问题指出了对示例标识的赋值方法,针对不同的问题如何给示例标识赋值,本文后面还会专门介绍.2.4有条件下,2有2.上述集成学习算法对简单预测函数的构造并没有要求“比随机猜测略好”这一限制条件,是否这一限制条件被转换成“Zt≤1,并且一般情况下Zt<1”呢?答案是否定的.以算法2得到的RealAdaBoost算法的二分类问题(K=2),并采取二段划分(nt=2)为例,分析如下:记εt为ht(x)的训练错误率,则εt=pt1,1+pt2,2或者εt=pt1,2+pt2,1(注意pt1,2+pt2,1+pt1,1+pt2,2=1).ht(x)比随机猜测略好表示正确率1-εt要大于错误率εt,至少不能出现1-εt=εt,即(pt1,1+pt2,2)=(pt1,2+pt2,1).Ζt=2pt1,1pt1,2+2pt2,1pt2,2,当且仅当pt1,1=pt1,2,并且pt2,1=pt2,2时,Zt=1.显然,如果Zt=1,则(pt1,1+pt2,2)=(pt1,2+pt2,1),而(pt1,1+pt2,2)=(pt1,2+pt2,1)不能得出Zt=1.所以算法2的有效性条件限制比“比随机猜测略好”条件更容易满足.更进一步,在算法2中,还允许部分Zt=1,只要一般情况下Zt<1即可,太多的Zt=1无外乎是训练错误率逐渐减小的速度慢一些而已.因此,通用集成学习算法1并不严格受制于弱学习定理中的“弱学习算法比随机猜测略好”限制条件.算法1的时间复杂度与简单预测函数的构造方法有关,如果构造简单预测函数的时间复杂度为O(D),则算法1的时间复杂度为O(mTD),因此,只要构造简单预测函数的时间复杂度不高,本文算法就是一种较快的算法.比如基于单个特征采用阈值法来构造简单预测函数时,算法时间复杂度就为O(mdT),其中m为训练样本数,d为样本特征个数,T为弱分类器的个数.上述时间复杂度为学习阶段的时间复杂度,而测试(预测)阶段的时间复杂性显然也直接依赖于简单预测函数.同样,当基于单个特征采用阈值法来构造简单预测函数时,预测时间复杂度就为O(T).3示例标识赋值方法前面提到,对x∈X的标识Y=(y1,…,yK)给不同的赋值可得不同的学习算法.针对不同的实际需求,下面来分析如何给示例标识赋值.在构造算法2～4时,针对K分类问题,指出了一种标识赋值方法,并由算法2得到K分类RealAdaBoost,由算法3得到K分类GentleAdaBoost,由算法4得到不平衡分类问题的集成学习算法.要清楚怎样给示例的标识赋值,首先需要明白通用集成学习算法1的学习目的.算法1的学习目的是:希望学习所得f(x)输出值(f(x,1),…,f(x,K))与x的标识向量(y1,…,yK)各分量大小顺序一致.理解该学习目的就容易给示例标识赋值.下面介绍一些针对不同问题要求的示例标识赋值方法.3.1反拟合k分类算法设xi的类标签为li∈{1,…,K},与前面RealAdaBoost算法相反,用(yi,1,…,yi,K)来标识xi,令yi,li=0,其余yi,l=1(l≠li).得到f(x)后输出标签由Η(x)=argmaxlf(x,l)改为Η(x)=argminlf(x,l),便得到一种反拟合K分类连续AdaBoost算法.由于此时H(x)≠l,当且仅当存在k∈{1,…,K}(k≠l)满足-f(x,k)+f¯(x)>0,于是训练错误εtri满足:εtri=1m∑i=1m〖Η(xi)≠li〗≤1m∑i=1m∑l=1Κyi,l(F(xi,l))-1.(13)根据定理1,算法2～4都可得到相应的训练错误率估计.比如对应算法2的训练错误率估计为εtri≤Ζ0∏t=1Τ(Κ∑j=1nt(∏k=1Κ(ptj,k)1/Κ))‚(14)其中Z0=(K-1).不难验证,K=2时,式(14)与式(10)一样.3.2输出标签算子hx对K类多标签分类问题,设xi的类别为一个标签子集Yi⊂{1,…,K},定义xi的标识向量(yi,1,…,yi,K),仅当l∈Yi时,yi,l=1,而其余yi,l=0(l∉Yi),得到f(x)后输出标签子集H(x)={l:f(x,l)≥f¯(x)}.也可反过来,仅当l∈Yi时yi,l=0,而其余yi,l=1(l∉Yi),得到f(x)后输出标签子集H(x)={l:f(x,l)≤f¯(x)}.对前者其相当于最小化训练错误:εtri=1m∑i=1m|Yi-Η(xi)|≤1m∑i=1m∑l=1Κyi,l(F(xi,l))-1‚(15)此时的学习算法把本该有但没有预测到的一个标签算一个错误,可以称之为“欠预测最小化的多标签分类算法”.对后者,其相当于最小化训练错误:εtri=1m∑i=1m|Η(xi)-Yi|≤1m∑i=1m∑l=1Κyi,l(F(xi,l))-1‚(16)此时的学习算法把过多预测的每个标签算一个错误,可以称之为“过预测最小化的多标签分类算法”.两种算法都可根据定理1得到训练错误率估计公式.3.3平均错分代价估计对K类代价敏感分类问题,xi的实际标签为li,设c(i,j)为i类被错误分为j类的代价损失,c(i,j)≥0,c(i,i)=0.定义xi的标识向量(yi,1,…,yi,K),其中yi,l=c(li,l),得到f(x)后输出标签Η(x)=argminlf(x,l).则一种平均错分代价ccs满足:ccs=1m∑i=1m(∑l=1Κyi,l〖Η(xi)=l〗)≤1m∑i=1m(∑l=1Κyi,l(Η(xi,l))-1).(17)根据定理1,算法2～4都可以得到相应的平均错分代价估计.比如算法2对应的平均错分代价估计为εcs≤Ζ0∏t=1Τ(Κ∑j=1nt(∏k=1Κ(ptj,k)1/Κ))‚(18)其中,Ζ0=1m∑i=1Κ∑j=1Κc(i,j).根据前面的分析有如下结论:平均错分代价εcs将随ht(x)个数增加而减小.上述代价敏感集成学习算法属于真正意义上的平均错分代价最小化集成学习算法.目前已有的代价敏感集成学习算法通常把多分类问题转换成二分类问题来处理,或者考虑其被错分的总代价,两者都无法区分被错分成不同类别的代价,而真正的平均错分代价最小化算法应具有如下性质:即使被错误分类,也需分为错分代价较小的类,即当H(xi)≠li时,希望输出类H(xi)满足c(li,H(xi))较小.3.4k维向量zx,1,1此处的模糊分类问题是指所有示例(包含样本自身)具有模糊性的分类问题.xi属于类标签l的置信度为yi,l,则直接用K维向量(yi,1,…,yi,K)来标识xi,得到f(x)后的输出仍然是模糊的,输出为(f(x,1),…,f(x,K))或归一化的(f′(x,1),…,f′(x,K)),其中f′(x,l)=f(x,l)/(Κf¯(x))‚l=1,⋯,Κ.4基于单特征阈值法构造简单预测函数算法1对简单预测函数的构造没有特殊限制,在构造算法2～4时,对能实现示例空间某种划分的预测函数,算法给出了简单预测函数的输出公式.下面分析这种简单预测函数的构造方法.由于组合预测函数的泛化能力与简单预测函数密切相关,只要满足“Zt≤1,并且一般情况下Zt<1”条件,简单预测函数应该是越简单越好.设x∈X有d个特征,当特征为数字型,可采用阈值法来划分示例空间,单阈值可实现两段划分,n个阈值可实现n+1段划分.于是,构造简单预测函数就变为构造划分阈值,而“基于最小化Zt选取ht(x)”就变为在d个特征中,选择可以使Zt取到最小值的特征对应的划分.因每一轮训练后样本权值都会作调整,在计算划分阈值时一般需引入权值.于是,有如下的简单预测函数构造方法(对K分类问题):计算K类样本的均值(以样本的权值为加权系数的加权均值),以两两相邻均值之平均值作为分段阈值(共有K-1个)对示例实现K段划分,在满足“Zt≤1并且一般情况下Zt<1”条件下定义简单预测函数的输出值.上述方法突破了简单预测函数个数限制,如果不引入权值,d个特征只能得到d个简单预测函数.计算K类样本的均值方法:以样本标识向量的第K个分量为加权系数进行加权平均.需注意划分段数可以是任意的,K分类问题的划分段数可不等于K.组合函数f(x,l)=∑t=1Τht(x,l),ht(x)按照上述方法来构造时,本文算法与支持向量机(supportvectormachine,SVM)在形式上非常相似.对训练样本为xi(i=1,…,m)、标签为yi∈{1,-1}的分类问题,SVM得到的分类函数为sgn(yi(wxi+b)),这相当于先通过学习得到特征的组合系数w=(w1,…,wd)和分类阈值b,然后构造分类函数sgn(yi(wxi+b)).而本文算法则是先学习单个特征的分类阈值得到预测函数ht(x),然后再进行组合.显然,当示例的特征是非数字型的,SVM的先进行特征组合后构造分类器将无法操作,而本文的先构造分类器后进行组合则是可行的,因为对非数字型特征,依据单个特征可容易实现示例空间的划分.基于单特征阈值法构造的简单预测函数,其组合预测函数不易出现过学习,具体分析如下:首先来分析组合预测函数对示例空间是如何分割的.考虑d=2、示例为二维空间的点.单特征阈值法构造简单预测函数相当于将示例向各个坐标轴进行投影,基于投影后的示例计算阈值来构造简单预测函数.因此,简单预测函数将用垂直于坐标的一条直线(2段划分)或多条直线(多段划分)分割整个二维空间,而组合预测函数将把二维空间划分为一些不重叠的矩形区域(边界矩形区域的长或宽可为无穷大),并且矩形边平行于坐标轴.组合预测函数对同一矩形区域内的示例输出相同值,对分类问题,相当于对各矩形区域进行分类.d>2的高维空间的划分就对应为高维空间的“矩形区域”.先从预测函数的稳定性来分析.组合预测函数对示例空间的划分是边平行于坐标的矩形区域,当示例的某些特征值发生变化时,只要这种变化不会导致其落入另一矩形区域,则组合预测函数输出值都是不变的.除正好位于矩形区域边界上的示例外(相对整个空间非常少),几乎所有示例的特征值发生小的变化都不会影响组合预测函数的输出,而且矩形区域特性决定了允许多个特征同时有小的变化而不改变输出结果,这表明组合预测函数的输出是很稳定的,输出稳定的预测函数是不易出现过学习的.还可以从VC维来分析.考虑二分类问题,简单预测函数采取二段划分,则每个简单预测函数将把示例空间分割成两部分,简单预测函数最多能打散2个样本.如果基于每个特征最多构造一个简单预测函数,组合分类器f(x)最多能打散d+1个样本,按照VC维的定义,f(x)的VC维将小于d+1.我们知道,d维实数空间的线性分类器的VC维为d+1,因此,基于单特征阈值法构造简单预测函数时,f(x)的VC维数一般情况下并不比线性分类器的VC维数大.SVM具有较强的泛化能力,属于一种线性分类器,因此单特征阈值法构造简单预测函数时,其组合预测函数应该有较强泛化能力,即不易出现过学习.需要指出的是,算法1对简单预测函数的构造并无特殊限制,可以基于SVM方法、神经网络方法、特征组合方法等.从使用简单和好的泛化能力考虑,可统一基于单个特征的简单划分法来构造简单预测函数,而通过增加简单预测函数个数来降低训练错误率,这样就又不必耽心出现过学习现象.5实验与分析5.1实验数据与结果分析本文提出的算法更多地体现在对一大类AdaBoost系列算法进行统一,而AdaBoost系列算法早已得到成功应用,因此,实验主要集中在对以下问题进行验证:1)不平衡分类问题集成学习算法是否更有效;2)提出的集成学习算法是否不易出现过学习;3)反拟合K分类连续AdaBoost算法是否有效,K分类GentleAdaBoost算法是否有效.实验数据一般应来自于公共实验数据集,因每个实验数据都具有其特定的数据规律,不管基于多少数据实验,都只能得到一种统计意义上的结论.基于此,本文实验除采用公共UCI的Ionosphere(2类)和Wine(3类)数据外,采用了一种随机数据集,随机数据一般具有更强的代表性.实验数据如表1所示:Ionosphere:采取减少前n个样本(1类和2类同时被减少)来调整类分布以模拟不平衡分类.Wine:采取减少第3类样本(第1类和第2类始终不变)来调整类分布以模拟不平衡分类.Random1:由取值于的随机函数生成,随机赋予类标签,调整类比率来模拟不平衡分类.Random2:类似Random1随机生成,但对1～3类样本各分量分别乘以1,2,3.同比例(60:40)对实验数据集进行随机划分得到训练集和测试集,基于训练集训练得到组合预测函数后对测试集进行测试并统计错误率.为验证算法的适应性,采取多次实验(20次)统计平均错误率.二分类问题的弱分类器采用2段划分,三分类问题的弱分类器采取5段划分:第4节介绍的方法得到2个划分阈值和3个类均值后,统计其两两相邻值之平均得4个值,以此为阈值可实现5段划分.对RealAdaBoost系列算法的边界处理方式见文献,即对Zt用1+ptj,l代替ptj,l.对二分类问题还采用xi的类别标签对应分量为其初始类分布概率(比率),其余分量为0的向量来标识xi.实验结果如表2～6所示:5.2不平衡分类问题的集成学习算法更有效先分析表2数据.看第1个实验数据,P1=0.641,P2=0.359,T=30,A1,A2的测试错误率分别为0.1893,0.1825