第29卷第5期控制与决策2014年5月文章编号:1001-0920(2014)05-0815-06DOI: ),男,博士生,从事数据挖掘的研究；赵大哲(1960 ),女,教授,博士生导师,从事数据挖掘、医学影像处理等研究.
816控制与决策第29卷不均衡数据学习的两个不同侧面,它们可能会同时出考虑类内的不均衡性问题.文献[8]发现了类内不均现,都将影响分类器的性能[8].2)现有的采样方法或衡问题的严重性,提出了一种基于K-means的升采样者是简单地通过随机方式进行复制或删除样本,或者算法KOS来解决类内和类间的不均衡性问题,利用是基于某些启发式的规则插入样本或过滤噪音样本,K-means对两类样本分别进行聚类,在每个簇内使用都没有遵循数据本身的分布规律,当所设计的样本生随机升采样,使同类中的所有簇数据以及两类整体数成规则与潜在真实类分布不完全一致时,将不可避免据都达到均衡化.该算法虽然达到了整体和局部的均地向训练样本集内引入噪声,并扭曲数据的空间分布.衡性,但却引入了另外的问题:1)对两类数据都只采鉴于上述问题,本文提出一种基于概率分布估计用了随机升采样技术,造成冗余数据增多,增加了数的混合采样算法(HPS),从全局和局部两个角度对不据处理的时间消耗;2)聚类的数目需要人工设置,而均衡问题进行深入的剖析和处理.该算法使用高斯混且很难找到最佳的簇个数.合模型[9]对两个类分别进行概率分布参数估计和数2基于概率分布的混合采样算法据分解,并根据估计的概率函数对类中的每个子类数为了使采样算法生成的新样本空间D 更加符据进行有效的采样:在保证多数类的空间结构不变的合数据的真实分布,并改善类间与类内的不均衡分布,情况下去除冗余的信息;根据样本的分布规律对少数该算法基于高斯混合模型(GMM)概率分布,分别对类合成更加准确真实的新样本,挖掘和扩展潜在的决多数类和少数类进行采样.即首先通过GMM概率分策区域.通过实验验证,该算法有效改善了不均衡数布对两类样本分布进行模拟和数据分解,再根据学习据分布问题,提升了传统分类器的分类性能.到的概率分布函数进行样本的重采样.GMM可视为1相关工作由L个高斯分布以一定比例混合而成,每个高斯成分数据重采样算法是通过改变原有训练集D,使分用均值 和协方差矩阵 来决定其几何特征,如下式类器在新数据集D 上能够提高性能.采样的目的是所示:找到采样过程S:D!D .采样方法可进一步分为XLXL降采样和升采样.降采样是通过减少多数类样本来提p(x)=p(l)p(xjl)= lN( l; l);(1)l=1l=1高少数类的分类性能,但容易丢失多数类的一些重要信息,使分类器无法进行充分的学习.虽然很多改进其中XL l=1.方法通过一定的规则l=1,有选择地去掉对分类作用不大由于GMM是一种对数据的真实分布进行模拟的多数类样本,如NCL[10]算法,但在复杂的数据分布和逼近的半参数表达模型,可以近似于任意的数据分中很难准确地确定噪音及冗余样本,导致很多重要信布,假定两类样本数据遵从具有某种参数的高斯混合息被删除.分布,从而使用GMM分别对两类的分布进行参数估升采样技术则是通过增加少数类的样本来提高计.对GMM进行参数估计的常用方法是EM,但由于少数类的分类性能,最简单的升采样方法是随机复制其需要人工指定聚类的个数,并且其对初始值点较为少数类样本,缺点是没有给少数类增加任何新的信敏感,本文中使用Figueiredo-Jain(FJ)解法[12]来对参息,会使分类器学到的决策域变小,导致过学习.较高数进行估计.该算法可以自动确定高斯模型的最佳个级的升采样算法则采用一些启发式的技巧,有选择地数,从而更加准确地计算出模型中的参数.HPS算法插入少数类样本,如SMOTE算法[3],对每个少数类样流程如下.本随机选出几个邻近样本,并且在该样本与这些邻近Step1计算两类样本的采样数量.样本的连线上随机取点,生成无重复的新的少数类若数据集D中两类样本数量分别为Mmaj和样本.但SMOTE在插入新样本时未考虑多数类的分Mmin,则混合采样数量N=(Mmaj Mmin)
,
=布,插入了很多噪音,造成过泛化.为了防止合成的新1.升采样的数量为Nmin=N Rhs,降采样的数量为样本侵入到多数类空间中,在SMOTE基础之上BaruaNmaj=N (1 Rhs),Rhs为混合采样的比例系数.等[11]提出了一种基于聚类的升采样算法—–CBSOStep2过滤数据集中的噪音样本.算法,先对少数类样本进行聚类,再划分成若干簇区为了防止噪音样本对概率分布估计造成影响,域,在对少数类进行采样时可保证新样本在同一个簇首先对样本进行预处理.根据最近邻域思想,当样本区域内.数据的M个最近邻域样本中超过4/5为相反的类别以上的升采样算法虽在一定程度上提高了少数(M=5)时,该样本是噪音的可能性较大,应进行过类的识别率,但其采样策略只是针对样本之间的连线滤.过滤后生成新数据集D0,D0= lter(D).进行插入,仍有大量重要的空间未能开采,而且没有
第5期曹鹏等:基于概率分布估计的混合采样算法817Step3对两类样本分别进行高斯混合建模.其中i:sizema为多数类i-th子类的样本数量,Sjmaj为利用FJ解法对D0中的两类样本分别进行概率多数类中子类的个数.密度估计,每个样本被分到概率最大的簇中,完成数对多数类的子类进行降采样.据聚类分割的工作,并获得概率密度函数参数.确定对于多数类的每个子类中,需要在保持子类的空了两类样本的采样数量和数据子类后,对两类样本分间结构信息不被破坏的前提下减少冗余样本.因每个别采样以解决类间和类内的不均衡性问题.子类的高斯分布中,处于中心位置的区域样本分布较Step4对少数类进行升采样.其他区域更为稠密,故应具有更高的降采样几率.计确定少数类各个子类的采样数量.算每个样本xk的高斯概率值并归一化,每个样本被为解决少数类内部各个子类(簇)之间的均衡性,移除的几率与每个样本的归一化高斯概率值成正比,每个子类的升采样数量应与子类中的样本数量成反从而在压缩多数类的同时保留了具有代表性的样本.比.利用下式计算每个子类的升采样数量:通过图1可以直观地了解HPS采样的原理以及 .SXmin1 与SMOTE采样的区别.原数据分布D如图1(a)所示Nimin=1 Nsizeijmin:(2)minj=1sizemin(三角为少数类,圆形为多数类).图1(b)为SMOTE采其中样后的数据分布D :sizeimin为少数类中i-th子类的样本数量,SminSM(矩形为新合成的少数类样本),为少数类中子类的个数可以看到,基于样本连线插值的SMOTE算法没有考.对少数类的子类进行升采样虑多数类的数据分布,生成很多噪音数据.图1(c)为.在每个子类中使用该子类的高斯密度函数进行对两类分别进行GMM建模及分解的结果:多数类有升采样3个簇,样本数量为20,15,10;少数类有2个簇,样本.由于边界数据对少数类的识别作用较大,为了扩展少数类的决策域,需要对少数类样本有选择地数量为10,5.图1(d)为HPS采样分布D HPS.两类样采样本的采样总数量N=Mmaj Mmin=30,若Rhs=0:5,,即重点对位于边界区域的少数类样本进行采样.根据文献则两类的采样数量为Nmaj=Nmin=15.[13]的思想,计算子类中每个样本xk的采样权重rk,即rk=11+;(3)exp( k)其中 k是xk的K1个邻域中多数类的个数. k越大,说明该样本是边界样本的概率越大,所以采样的权重越大(由文献[21]可设为).之后根据下式对rk进行归一化(a)!"#$%&(b)SMOTE'()*#$%&:.siXzeiminr^k=rkrj:(4)j=1再由归一化的采样权重,计算每个样本xk的采样数量gk,有gk=Nimin r^k:(5)因而边界区域的少数类样本采样的数量较其他区域(c)GMM%+,-(d)HPS'()*#$%&更多图1基于概率分布的混合采样算法图示.基于每个样本xk进行升采样时,为了在扩展潜在空间的同时避免引入噪音,限定在其K2最近邻域由式(2)s(6)计算每个子类的采样数量并进行的区域之内合成gk个新样本.重采样,采样后多数类各个子类的数量分别为13,10,Step5对多数类进行降采样.7;少数类的数量均为15,同时缓解了类间和类内的确定多数类各个子类的采样数量.不均衡.另外可以看到:对于多数类,在保证每个子类对于多数类,每个子类的降采样数量应与子类的样本空间结构不发生变化的前提下,减少了冗余数中的样本数量成正比,即样本数量多的子类其降采样据;而对于少数类中的子类区域,增加有效的少数类的数量也多,从而保证了多数类内部各个子类的均信息,扩展了数据空间并避免了插入的样本侵入多数衡.每个子类的降采样数量计算如下:类空间,这与基于全局采样的SMOTE算法的采样原 .SXmaj 理有着本质上的区别.由于本文算法是基于局部的数Nijma=sizeisizejmajma Njmaj:(6)据空间,即以簇区域为单元进行采样的,可以获得更j=1
818控制与决策第29卷加合理的数据分布,文献[14]也证明了从局部数据入集分别执行5次采样操作,并在采样后的训练数据集手进行处理可以达到更好的采样效果.分别构建分类器并测试,最后将5 10次结果计算均3实验评估值作为该算法的无偏结果,实验结果如表2所示.数据集描述表2不同算法的分类性能比较结果为了评估算法的性能,选择9组具有不同不均衡数据集指标比例的UCI数据集进行测试,数据集详细信息如表所示表1实验数据集描述数据集(+)样本数特征数不均衡比例=%(tableware)(Z)(2,3,4,5)54731010SegmentSegment(bricface)(yes)(opel)(1)(positive)(spam)算法的性能验证为了验证HPS算法对不均衡数据学习的有效性,使用几种常用的不均衡数据处理算法进行性能比较Pima,如SMOTE(SM),SMOTE+NCL(SML),KOS,其中:SMOTE的采样率Ros设为200%;KOS算法中聚类个数K设为2;CBSO算法中 设为1,即代表升通过实验对比发现,HPS在多数数据集上均优于采样数量等于两类数量的差额.在HPS算法中,为了其他采样算法.由于HPS算法是基于概率密度函数进避免减少过多的信息,Rhs设置为.参数K1和K2行采样,在少数类样本数量充足的条件下,可准确估是分别用来控制样本采样权重和新样本合成区域大计出真实的概率密度函数,从而发现潜在的数据空间小的.对于高维数据,根据欧氏距离确定的邻域并不并合成准确的新样本.不均衡数据中少数类一般分为能准确描述样本之间的相对位置,所以K1选取过大绝对稀缺和相对稀缺.HPS在少数类样本数量不充足会获得不准确的权重值;而且由于处于决策区域的样的情况下,即绝对稀缺时,将无法准确获得少数类样本周围会有较多的多数类样本,为避免引入噪音K2本的概率分布参数,导致可能插入不准确的样本,无也不宜设置过大.通过多组实验发现,邻域参数K1和法达到最佳的采样效果.如Glass数据集中少数类只K2均设为5时可获得较好且较稳定的采样性能.本实有9个样本,所以HPS算法在该数据集中较其他算法验使用不均衡数据学习最常用的决策树算法作性能有所下降.但不均衡比例同为4%的Letter数据为基分类器.集含有充足的样本,属于相对稀缺,HPS算法可以达分类器评测指标直接影响着分类器的性能,到理想的结果.对于绝对稀缺的数据学习问题一直是传统的准确率对于不均衡数据的评价不再有效,数据挖掘中重点研究的课题之一,目前仍没有有效的这里将采用不均衡分类的评测指标GM(Geometric解决方法[15].mean)和AUC(AreaundertheROCcurve).其中:GM从实验结果还可以看到SMOTE和CBSO在大是综合衡量两类准确率的指标(GM=(ACCmaj 多数数据集下提升了分类性能,但基于样本连线的ACCmin)1=2),只有两类的准确率都较高时才能得到插入机制受到了很多限制,而且只从全局不均衡性较高的GM值;AUC是另一个有效的不均衡数据分的角度处理数据,未能很好地保证不均衡数据采类性能评价手段,由于ROC曲线作为分类器评估的样质量.SML结合了两种采样的优势,要普遍好于可视化技术得到了广泛应用,AUC能以定量的方式SMOTE,但其中的NCL降采样操作在复杂空间下不表示ROC曲线对应的分类器性能.所有算法都使用可避免地删除了多数类的重要信息,导致保留的样本10折交叉验证.由于升采样算法本身具有一定的随机无法反映原始数据的分布.KOS算法虽同时考虑了两性,对于所有升采样算法,在每次交叉验证时,对训练个不均衡性问题,但由于采用随机升采样造成数据过
第5期曹鹏等:基于概率分布估计的混合采样算法819拟合,而且K值的固定设置对于某些数据集并不准由表3可以发现:在多个数据集下,HPS算法的确,影响了采样的效果.优化结果好于SMOTE算法;而对于数据集Pima和采样率Rhs对分类性能的影响及优化Spambase,在AUC指标的指导优化下得到了更好的采样算法中的采样率决定着采样的性能GM结果,说明AUC在某些数据集上,对不均衡数据,从而影响着分类准确性,但是最佳的采样率很难通过经验获具有更好的评估和优化作用,文献[4,16]也同样支持得这一结论..本文选取不均衡度为30%的German数据集进行演示,通过选取HPS算法中不同的采样率比例Rhs来对噪音的鲁棒性测试观察其对分类性能的影响,如图2所示.数据集中不可避免地具有很多噪音数据,噪音数0据是指样本中含有错误的值,包括特征属性的错误和.8类别标签的错误[17].由于决策树分类器本身的训练机制(根据信息增益率进行特征选择和分裂)具有一定的属性噪音的抑制能力,类别标签噪音具有更强的分类器阻碍性,这里重点考虑含有错误类标签的AUC样本噪音.为了系统地验证HPS算法对噪音数据的鲁棒性,实验中人工加入噪音数据,并调整噪音的级别Rhs图2改变采样率Rhs对程度.该实验使用其他文献中相同的实验方法来对原German数据集的分类影响始数据集注入不同程度的噪音数据[18].在给定的噪音通过图2曲线可以看到Rhs直接影响着分类性级别l%下,每个样本以概率为l%的可能性出现相反能:当Rhs=0时,只有降采样对多数类进行处理以的类别,即噪音级别l%越大,样本类别被反转的可能达到类别均衡的目的,但可能漏掉潜在重要的数据;性越大,噪音出现的概率也越大.Rhs=1时只有升采样起作用,合成大量的新样本,随机选取German数据集进行测试,表4列出了造成分类模型的过拟合.HPS算法在Rhs=0:65和在具有不同噪音级别的不均衡数据下的实验比较结Rhs=0:6时分别达到了最高的AUC和GM值,这也果.可以发现HPS相对于其他算法具有更强的抗噪证明了混合采样可以避免单一采样的缺陷.性,特别是在噪音级别较高的情况下,这完全归功于最佳采样率依赖于具体的数据分布,为了使HPSHPS算法在对数据进行分布估计和采样之前进行的算法达到最佳性能,本文对每个数据集在训练数据中过滤操作,同时采样过程中的样本权重设置操作,降进行交叉验证来获取最优采样率Rhs.采样率取值范低了噪音数据对采样和分类学习的影响.围设置为[,1],步长为,对于每一个Rhs值,采用表4调整类别标签噪音级别的实验结果节中介绍的方法进行验证,最终选取交叉验证最好的Rhs值作为该数据集的最佳采样率.同样也对噪音级别=%算法进行升采样率的寻优,采样率选取范围为[50%,2 Rmax],其中Rmax为使两类数据相等时的采样率,步长设置为50%,优化过程同上.对于HPS算法,分别使用GM和AUC作为评价指标来指导采样率的优化,GM分类结果和最佳采样率如表所示.表4结论3优化SM和HPS算法采样率的GM性能比较结果数据集SMHPSGMHPS为了提升不均衡数据的采样性能,本文提出了一AUCGMRos=%GMRhsGMR种基于概率分布的混合采样算法.该算法根据估计的数据分布规律对每个子类进行采样,在保证类间均衡化的同时,也分别对两类数据内部的不均衡性进行改进,从而更好地改进了不均衡数据的采样效果,提升了分类性能.实验结果表明该算法在处理不均衡数据集时具有更高的分类精度.下一步的工作是:1)研究如何结合集成算法来提升不均衡学习的泛化能力;)本实验中对参数
默认为1,未来的实验中将对参数
进行调整优化以获得最佳的参数值.
820控制与决策第29卷参考文献(References)[10][C].ProcofAI[1]HeH,[J].IEEETransonKnowledgeandDataEngineering,2009,21(9):inMedicineinEurope:,2001:63-66.[11]BaruaS,MdI,[2]陶新民,张冬雪,付丹丹,等.基于谱聚类欠取样的不均衡数据SVM分类算法[J].控制与决策,2012,27(12):[C].,2011:735-744.(TaoXM,ZhangDX,FuDD,-basedunder[12]FigueiredoMAT,-finitemixturemodels[J].IEEETransonPatternAnalysissamplingapproaches[J].ControlandDecision,2012,27(12):1761-1768.)andMachineIntelligence,2002,24(3):381-396.[13]ChenS,HeH,:Ranked[3]ChawlaNV,BowyerKW,HallLO,:Syntheticminorityover-samplingtechnique[J].JofminorityoversamplinginBoosting[J].IEEETransonArtificialNeuralNetworks,2010,21(10):,2002,6(1):321-357.[4]CaoP,ZhaoD,-sensitive[14]CieslakDA,,optimizelocally,SVMforimbalanceddatalearning[C].Procofthe17thpredictglobally:ImprovingperformanceonimbalancedPacific-AsiaConfonKnowledgeDiscoveryandDatadata[C].,2008:,2013:-152.[5]陈刚,冯丹.一种新的模糊规则权重方法的非平衡数据[15][C].DataMiningand分类问题的研究[J].控制与决策,2012,27(1)::ACompleteGuidefor(ChenG,:Springer-Verlag,ruleweightsinimbalanceddataclassificationproblem[J].2005:,2012,27(1):104-108.)[16]ChawlaNV,CieslakDA,HallLO,[6][J].AnnalsofInformationSystems,2010,8(1):cost[J].DataMiningandKnowledgeDiscovery,2008,(2):225-252.[7]JoT,[17]ZhuXq,:Adisjuncts[J].ACMSIGKDDExplorationsNewsletter,quantitativestudy[J].ArtificialIntelligenceReview,2004,2004,6(1):(3):177-210.[8]-learninginthepresenceofbetween-[18]AnyfantisD,KaragiannopoulosM,KotsiantisS,-classimbalances[C].,2001:[C].Procofthe4thIFIP[9]TitteringtonDM,SmithAFM,[M].NewYork:JohnInnovations(AIAI’07).Athens,2007:,2001.(责任编辑：李君玲)
