claude tadonki and jean-philippe vialnew

《claude tadonki and jean-philippe vialnew》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、TheLinearSeparationProblemRevisitedwithACCPMClaudeTADONKIandJean-PhilippeVIALHEC/LOGILAB,40BdduPontd'Arve,CH-1211Geneva,SwitzerlandEmail:{claude.tadonki,jean-philippe.vial}@hec.unige.chMay21,2002AbstractWeinvestigatetheuseofaccpm(analyticcentercuttingplanemetho

2、d)forsolvingthelinearseparationproblem,whichisanimportantinstanceofthegeneraldataminingconcept.Giventwodisjointsubsetsofpoints,theproblemistondahyperplanewhichseparatesthesetwosubsetsaswellaspossible.Ourmethodconsistsofminimizingthetotalsumofmisclassicationgap

3、s.Foralargeamountofdata,thenumberofglobaliterationsintheaccpmprocesscanbereducedbysplittingtheobjectiveintoseveralparts.Hence,wereducethetotaltimecostinvolvedbytheevaluationsoftheobjectiveanditssubgradients.However,asthenumberofcutsincreaseswiththenumberofsubfun

4、ctions,thetimecostassociatedwithbecomesconsiderable.Therefore,wehavetoachieveacertainbalancebetweenthegainintheobjectiveevaluationsandthepricewepayfortheadditionalcutsgenerated.Afterprovidinganalgorithmtocomputeagoodstartingpointwhichyieldsafasterconvergence,wep

5、erformsomeexperimentswithfoursampledatabasesovervariousdisaggregatedforms.Wehaveuseda500MhzSUNUltrasparcwith256MBofRAM.Thereportofmeasuredexecutiontimesshowsthatthemethodisquiteecient,andthecompromisepreviouslyexplainediswellillustrated.Anasymptotictimeanalysis

6、isprovidedandfromthis,wederiveanexpressionapproximatingthevalueoftheoptimalpartitionsize.Keywords:Optimization,convexprogramming,linearseparation,heuristic,complexity.1IntroductionTheseparationproblemisaninstanceofthemoregeneralcaseofthedataminingconcept[14],awi

7、delystudiedtopic.Peoplewithvariedinterestsandbackgrounds(statisticians,economists,physicians,chemists,biologists,mathematicians,computerscientists,...)havedevotedasubstantialpartoftheiractivitiesonthisdataclassicationapproach.Successfulapplicationsarereportedin

8、manydierentareas,e.g.cancerdiagnosis[21],humangenome[15],gamestrategies[19],patternrecognition[22],decision/selectionmaking[30],andmore.FNRSPosdoctoralposition12Cla