大學(xué)課件：決策樹1

Classificationtreesfortimeseries指導(dǎo)老師：褚挺進(jìn)、李揚、張拔群組員：王肖南、呂志鵬、胡小寧、鄭冰IntroductionTimeseriesclassificationhasbeenthesubjectofextensiveresearchinthelastseveralyears.1、Afirstcategoryofproposalconsistsofmappingthetimeseriestoanewdescriptionspacewhereconventionalclassifierscanbeapplied.2、Asecondclassofworksproposesnewheuristics,generallystartingwiththetimeseriessegmentationtoextractprototypesthatbestcharacterizethetimeseriesclasses.3、AthirdcategorymaybedistinguishedthatconsistsofthehiddenMarkovmodels,whichisfrequentlyusedforspeechrecognitionandsignalprocessing.TheworkofYamadaetal.Yamadaetal.proposestwosplittests.Thefirsttest,calledthestandard-examplesplittest,usesanexhaustivesearchtoselectoneexistingtimeseries(calledthestandardtimeseries)Thesecondproposedsplittest,whichiscalledthecluster-examplesplittest,performsanexhaustivesearchfortwostandardtimeseries.TheworkofBalakrishnanandMadigan

BalakrishnanandMadiganlookforapairofreferencetimeseriesthatbestbisectsthesetoftimeseriesaccordingtoaclustering-goodnesscriterion.Forthetimeseriesproximities,boththeEuclideandistanceandthedynamictimewarpingareusedtocomparetheefficiencyoftheobtainedclassificationtrees.SomeremarksFirst,asformanydistance-basedapproaches,theEuclideandistanceandthedynamictimewarpingareconsideredforthetimeseriespromimities.Thestandardmeasuresarevalues-basedmetricsandignorethebehaviorsofthetimeseries.Second,theproposedsplitsusethesamemetrictodivideallthenodes,butthepeculiaritiesofthetimeseriesmaychangefromonenodetoanother.Finally,thetimeseriesdistancesarecalculatedusingthewholetimeseriesvalues,eventhoughthediscriminationisdeterminedbyparticularsubsequences.ThestudyofthispaperThispaperfocusesonadistance-basedapproachtoextendingclassificationtreestotemporaldata.Anewsplitcriterionbasedontimeseriesproximitiesisintroduced.1、Thecriterionreliesonanadaptivetimeseriesmetrictocoverbothbehaviorsandvaluesproximities.2、Thecriterioninvolvestheautomaticextractionofthemostdiscriminatingsubsequences.3、Throughtheexperimentsperformedinthisstudy,Weshowthatthepropsedtreeoutperformstemporaltreesusingstandardtimeseriesdistancesandperformswellcomparaedtoothercompetitivetimeseriesclassifiers.TherestofpaperisorganizedasfollowsSection3,themajormetricsfortimeseriesarepresentinanovelunifiedformalism.Section4presentsthenewtimeseriesclassificationtree,providesthemainalgorithmsanddiscussestheircomplexity.Section5,theproposedclassificationtreeisperformedonsixpublicandthreenewsimulatesdatasets.Section6,theinducedtreesarecomparedtotemporaltreeusingstandarddistancesandcomparedtoothercompetitivetimeseriesclassifier.3.Timeseriesmetrics3.1Values-basedmetrics3.2Behavior-basedmetrics3.3Valuesandbehaviorbasedmetrics3.1Values-basedmetrics時間序列長度不一致：dynamictimewarping時間序列長度一致：Euclideandistance

Euclideandistance:dynamictimewarping:

dynamictimewarping:

兩者比較：

dynamictimewarping:Euclideandistance:

3.2Behavior-basedmetricsUntilrecently,manyapplicationsindifferentdomains(e.g.,speechrecognition,systemdesigncontrol,functionalMRI,microarraysandgeneexpressionanalysis)haveusedthePearsoncorrelationcoefficientasabehaviorproximitymeasurebetweensignals.

時間序列長度一致：

時間序列長度不一致：3.3Valuesandbehaviorbasedmetrics

C(r):Co(r):k的取值：[0:6]4.Timeseriesclassificationtrees*theuseofanadaptivemetric.*theinvolvementoftheautomaticextractionofthemostdiscriminatingsubsequences.*theinvolvementoftheautomaticextractionofthemo