In this paper, we propose the class-boundaryalignment algorithm to augment SVMs to deal with imbalanced training-data problems posed by many emerging applications (e.g., image retrieval, video surveillance, and gene profiling). Through a simple example, we
Class-BoundaryAlignmentforImbalancedDatasetLearning
GangWuGWU@ENGINEERING.UCSB.EDUEdwardY.ChangECHANG@ECE.UCSB.EDUDepartmentofElectrical&ComputerEngineering,UniversityofCalifornia,SantaBarbara
Abstract
Inthispaper,weproposetheclass-boundary-alignmentalgorithmtoaugmentSVMstodealwithimbalancedtraining-dataproblemsposedbymanyemergingapplications(e.g.,imagere-trieval,videosurveillance,andgenepro ling).Throughasimpleexample,we rstshowthatSVMscanbeineffectiveindeterminingtheclassboundarywhenthetraininginstancesofthetar-getclassareheavilyoutnumberedbythenon-targettraininginstances.Toremedythisprob-lem,weproposetoadjusttheclassboundaryei-therbytransformingthekernelfunctionwhenthetrainingdatacanberepresentedinavectorspace,orbymodifyingthekernelmatrixwhenthedatadonothaveavector-spacerepresentation(e.g.,sequencedata).Throughtheoreticalanaly-sisandempiricalstudy,weshowthattheclass-boundary-alignmentalgorithmworkseffectivelywithimages(datathathaveavector-spacerepre-sentation)andvideosequences(datathatdonothaveavector-spacerepresentation).
Veropoulosetal.,1999;Linetal.,2002;Crammeretal.,2003;Ongetal.,2003).Giventheclasspredictionfunc-tionofSVMs, n
sgn
f(x)=
yiαiK(x,xi)+b
,
i=1
(1)
threeparameterscanaffectthedecisionoutcome:b,αi,andK.OurempiricalstudyshowsthattheonlyeffectivemethodforimprovingSVMs,however,isthroughadap-tivelymodifyingKbasedonthetrainingdatadistribu-tion.Asindicatedby(Amari&Wu,1999),byconfor-mallyspreadingtheareaaroundtheclass-boundaryout-wardontheRiemannianmanifoldSwhereallmappeddataarelocatedinfeaturespaceF,wecanadaptKlocallytodatadistributiontoimproveclass-predictionaccuracy.Inthispaper,weproposetheclass-boundary-alignmentalgo-rithm,whichimprovesuponAmariandWu’smethodfortacklingtheimbalancedtraining-dataprobleminthreere-spects.
1.WeconductthetransformationbasedonthespatialdistributionofthesupportvectorsinfeaturespaceF,in-steadofininputspaceI(Wu&Amari,2002).Usingfeature-spacedistancetoconductconformationtransfor-mationtakesadvantageofthenewinformationlearnedbySVMsineveryiteration,whereasinput-spacedistanceremainsunchanged.
2.Weadaptivelycontrolthetransformationbasedontheskewoftheclass-boundary.Thistransformationgivestheneighborhoodofminoritysupportvectorsahigherspatialresolution,andhenceachievesbetterseparationbetweentheclasses.
3.Weshowthatincaseswheretheinputspacemaynotphysicallyexist(e.g.,sequencedatamaynothaveavec-torspacerepresentation),theclass-boundary-alignmentalgorithmcanbeapplieddirectlytoadjustthepair-wiseobject-distanceinthekernelmatrix1K.
OurexperimentalresultsonbothUCIandreal-worldim-age/videodatasetsshowtheclass-boundary-alignmental-gorithmtobeeffectiveincorrectingtheskewedboundary.
GivenakernelfunctionKandasetofinstancesXtrain={xi,yi}ni=1,thekernelmatrix(Grammatrix)isthematrixofallpossibleinner-productsofpairsfromXtrain,K=(kij)=K(xi,xj).
1
1.Introduction
SupportVectorMachines(SVMs)areacoremachinelearningtechnology.Theyhavestrongtheoreticalfoun-dationsandexcellentempiricalsuccessesinmanypat-ternrecognitionapplicationssuchashandwritingrecogni-tion(Vapnik,1995),imageretrieval(Tong&Chang,2001),andtextclassi cation(Joachims,1998).However,formanyemergingapplications,suchasimageunderstanding,securitysurveillance,andgenepro ling,wherethetraininginstancesofthetargetclassaresigni cantlyoutnumberedbytheothertraininginstances,theclass-boundarylearnedbySVMscanbeseverelyskewedtowardsthetargetclass.Asaresult,thefalse-negativeratecanbeexcessivelyhighinidentifyingimportanttargetobjects(e.g.,asuspiciouseventoragenedisease),andhencecanrendertheclassi erineffective.(WewillpresentanddiscussthedetailsofthisprobleminSection3.)
Severalattemptshavebeenmadetoimproveclass-predictionaccuracyofSVMs(Amari&Wu,1999;
WorkshoponLearningfromImbalancedDatasetsII,ICML,WashingtonDC,2003.
Learning Classi£ers fro... 暂无评价 6页 免费 Evaluating the Accuracy ....In an imbalanced dataset, the majority class has a large percent of all ...
Abstract. Learning classifiers from imbalanced or ...techniques for handling imbalance dataset problems. ...A number of solutions to the class-imbalance ...
ers generally favor natural class distribution although it might be imbalanced...Experimental Data Sets Dataset Size #Att #Class Target #Maj/#Min allbp-op...
热门文档