一种基于SVM的多类文本二叉树分类算法

一种基于SVM的多类文本二叉树分类算法AbstractWiththeexponentialgrowthofonlinedata,textclassification,asoneofthemostwidelyappliedtechniquesinnaturallanguageprocessing,playsacrucialroleinvariousapplications.However,traditionaltextclassificationmethodsarenotefficientenoughtodealwiththeincreasinglycomplexclassificationproblems.Therefore,anovelmulti-classtextbinarytreeclassificationalgorithmbasedonsupportvectormachine(SVM)isproposedinthispaper.Theproposedalgorithminvolvesanoptimizedtextfeatureextractionandaclassificationmechanismwithabinarytreestructure.Theexperimentalresultsdemonstratetheeffectivenessoftheproposedalgorithmcomparedtothetraditionalmachinelearningclassifiers.Keywords:textclassification;SVM;binarytreeclassification;featureextractionIntroductionTextclassificationisconsideredasoneofthemostvitaltoolsinmanydomains,especiallyinonlinecontentanalysisandinformationretrieval.Inrecentyears,therapidgrowthofdigitaldatahasledtotheemergenceofcomplexclassificationproblems,whichmaynotbeaddressedefficientlyusingtraditionalalgorithmssuchasNaiveBayes,K-NN,ordecisiontrees.Therefore,morepowerfulalgorithmsthatcanhandleextensivedatasetswithhighaccuracyandlowcomputationaloverheadhaverecentlyreceivedmoreattention.Supportvectormachine(SVM)iswidelyusedintextclassificationduetoitsabilitytohandlehigh-dimensionaldataandclassifynon-linearlyseparabledatasets.Yet,theapplicationofSVMinmulti-classtextclassificationtasksisstillchallenging.AlthoughSVMcanhandlebinaryclassificationquiteefficiently,itisdifficulttoextendthelinearSVMmodeltoamulti-classcasewithhighaccuracyandlowcomputationaloverhead.Tosolvethesechallenges,weproposedanovelmulti-classtextbinarytreeclassificationalgorithmbasedonSVM.Intheproposedalgorithm,weadoptanoptimizedtextfeatureextractionandaclassificationmechanismwithabinarytreestructure.Theproposedapproachenhancestheefficiencyandperformanceofthealgorithmcomparedtotraditionalmachinelearningclassifiers.RelatedWorkTextclassificationhasattractedsignificantattentioninthelastdecades.Recentresearchontextclassificationmainlyfocusesondesigningrobustalgorithmstoovercomethelimitationsoftraditionalclassifiersandhandletheincreasingamountofdigitaldata.Manyalgorithmshavebeenproposedintheliteraturetotackledifferentaspectsofthisproblem.Inthefollowingsections,wediscusssomeofthepreviousresearchthatisrelatedtothiswork.TheNaiveBayesalgorithmhasbeenwidelyusedintextclassification.However,duetoitsassumptionofindependenceamonginputfeatures,itoftenfallsshortindealingwithmorecomplexclassificationproblemsandachievinghighaccuracy.AnotherpopularalgorithmistheK-nearestneighbors(K-NN).Althoughitcanachievehighaccuracy,itsuffersfromhighcomputationaloverheadanddoesnotworkwellwithhigh-dimensionaldata.Decisiontreesarealsowidelyusedintextclassification.Nonetheless,itsuffersfromoverfittingandinstability.Toaddressthesedrawbacks,therandomforestalgorithmhasbeenproposed,whichaggregatesmultipledecisiontreestoachievehighaccuracyandstability.Finally,supportvectormachine(SVM),asapowerfulandwidelyusedclassifier,achievesgoodperformanceinmanyclassificationtasks,butitscomputationaloverheadisrelativelyhighandmorechallengingforittohandlethemulti-classclassificationproblem.MethodologyInthissection,wedescribetheproposedmulti-classtextbinarytreeclassificationalgorithmbasedonSVM.Thealgorithmhastwomaincomponents:anoptimizedtextfeatureextractionmethodandaclassificationmechanismusingabinarytreestructure.OptimizedTextFeatureExtractionIntheproposedmethod,weadoptthetermfrequency-inversedocumentfrequency(TF-IDF)featureextractionmethod.TF-IDFmeasurestherelevanceoftermsinadocumentbycombiningthetermfrequencyandtheinversedocumentfrequency.Ithasbeenshowntobearobustmethodfortextfeatureextractioninmanytextclassificationtasks.Toimprovetheefficiencyofthefeatureextractionprocess,weemployfeatureselectiontechniquestoreducethedimensionalityofthefeaturespace.Specifically,weadopttheChi-squaredmeasureasthefeatureselectioncriterion,whichassessestheindependencebetweeneachfeatureandtheclasslabels.Moreover,weusethemutualinformationcriteriontoassesstherelevanceofeachfeaturetotheclassificationoftextdocuments.ClassificationMechanismUsingBinaryTreeIntheproposedmethod,weuseabinarytreestructuretoclassifymulti-classtextdata.Inthebinarytreeclassificationmethod,thedatasetisrecursivelysplitintotwosubsetsbyrepeatingthenon-leafnodeofthebinarytree.Incontrasttothetraditionalmulti-classclassificationmethods,thebinarytreestructurecanreducethecomputationalcomplexityandimprovetheefficiencyofthealgorithm.Theproposedalgorithmusestheone-vs-allmethodtoconvertthemulti-classclassificationproblemtobinaryclassificationproblem.Abinarydecisiontreemodelisthenconstructedforeachsub-problem,andabinaryclassifierbasedontheSVMisusedtoperformtheclassification.Theexperimentalresultsdemonstratethattheproposedmethodcanachievegoodclassificationaccuracywhilereducingthecomputationalcomplexitycomparedtotraditionalmachinelearningclassifiers.ExperimentalStudyInthissection,weevaluatetheperformanceoftheproposedmulti-classtextbinarytreeclassificationalgorithmbasedonSVM.Wecomparetheproposedalgorithmwithseveraltraditionaltextclassificationalgorithms,includingNaiveBayes,K-NN,decisiontree,andrandomforest.Weconductexperimentsonfourdifferenttextclassificationdatasets,whichincludethe20newsgroups,RCV1,Reuters-2157,andWebKBdatasets.Foreachdataset,werandomlyselectasubsetofdocumentsasatrainingsetandtheremainingdocumentsasatestset.Thedatasets'statisticsaresummarizedinTable1.Fromtheexperimentalresults,wefindthattheproposedalgorithmoutperformstraditionaltextclassificationalgorithmsintermsofclassificationaccuracyandcomputationalcomplexity.Table2showstheclassificationaccuracyandrunningtimeofdifferentclassifiersondifferentdatasets.Aswecansee,th