轨迹数据挖掘-介绍ppt课件

.,Chapter1TrajectoryPreprocessing,JohnKrummMicrosoftResearchRedmond,WAUSA,Wang-ChienLeePennsylvaniaStateUniversityUniversityPark,PAUSA,.,Trafficinfo,Navigation,Localweather,Emergencyservice,Logistics,Location-BasedServices,GeographicalInformationSystem(GIS),Tracking,MobileCommerce,.,SystemModelforLBSs,Thelocationsoftrackedmovingobjectsarereportedtothelocationserverviawirelesscommunications.TheLBSapplicationssubmitqueriestotheservertoretrievemovingobjectdataforanalysisorotherapplicationneeds.,.,Trajectories,.,PositioningtechnologiesGlobalpositioningsystem(GPS)Network-based(e.g.,usingcellularorwifiaccesspoints)Dead-Reckoning(forestimation),.,MobileObjectDatabases,ResearchcommunitieshavemadetremendousresearchefforttosupportLBSs.E.g.,Mobileobjectdatabases(MODs)Inadditiontoconventionalsearchfunctionsofmovingobjects,manyLBSapplicationsneedtoanalyzeandminevariousmovingpatternsandphenomenonoftrackedobjects.TrajectoryManagement:trajectoriesofmovingobjects,i.e.,theirgeographical-temporaltraces,areoftentreatedasfirst-classcitizensinMODs.,.,TrajectoryPreprocessing,ProblemstosolvewithtrajectoriesLotsoftrajectorieslotsofdataNoisecomplicatesanalysisandinferenceEmploythedatareductionandfilteringtechniquesSpecializeddatacompressionfortrajectoriesPrincipledfilteringtechniques,.,Part1-Compression,.,PerformanceMetrics,Trajectorydatareductiontechniquesaimstoreducetrajectorysizew/ocompromisingmuchprecision.PerformanceMetricsProcessingtimeCompressionRateErrorMeasureThedistancebetweenalocationontheoriginaltrajectoryandthecorrespondingestimatedlocationontheapproximatedtrajectoryisusedtomeasuretheerrorintroducedbydatareduction.ExamplesarePerpendicularEuclideanDistanceorTimeSynchronizedEuclideanDistance.,.,IllustrationofErrorMeasures,PerpendicularEuclideanDistanceTimeSynchronizedEuclideanDistance,.,TrajectoryDataReduction,ClassificationofDataReductionTechniques.BatchedCompression:Collectfullsetoflocationpointsandthencompressthedatasetfortransmissiontothelocationserver.Applications:contentsharingsitessuchasEverytrailandBikely.TechniquesincludeDouglas-PeuckerAlgorithm,top-downtime-ratio(TD-TR),andBellmansalgorithm.On-lineDataReductionSelectiveon-lineupdatesofthelocationsbasedonspecifiedprecisionrequirements.Applications:trafficmonitoringandfleetmanagement.TechniquesincludeReservoirSampling,SlidingWindow,andOpenWindow.,.,BatchCompression-Douglas-Peucker(DP)Algorithm,PreservedirectionaltrendsintheapproximatedtrajectoryusingtheperpendicularEuclideandistanceastheerrormeasure.Replacetheoriginaltrajectorybyanapproximatelinesegment.Ifthereplacementdoesnotmeetthespecifiederrorrequirement,itrecursivelypartitionstheoriginalproblemintotwosubproblemsbyselectingthelocationpointcontributingthemosterrorsasthesplitpoint.Thisprocesscontinuesuntiltheerrorbetweentheapproximatedtrajectoryandtheoriginaltrajectoryisbelowthespecifiederrorthreshold.,.,IllustrationofDPAlgorithm,Splitatthepointwithmosterror.RepeatuntilalltheerrorsR),randomlydecides,withaprobabilityofR/k,whethertokeepthislocationpointornot.Ifthedecisionispositive,oneoftheRexistinglocationpointsinthereservoirisdiscardedrandomlytomakespaceforthenewlocationpoint.thereservoiralgorithmalwaysmaintainsauniformsampleoftheevolvingtrajectorywithoutevenknowingtheeventualtrajectorysize.,.,On-lineCompressionSlidingWindow,Fitthelocationpointsinagrowingslidingwindowwithavalidlinesegmentandcontinuetogrowtheslidingwindowuntiltheapproximationerrorexceedssomeerrorbound.FirstinitializethefirstlocationpointofatrajectoryastheanchorpointpaandthenstartstogrowtheslidingwindowWhenanewlocationpointpiisaddedtotheslidingwindow,thelinesegmentpapiisusedtofitallthelocationpointswithintheslidingwindow.Aslongasthedistanceerrorsagainstthelinesegmentpapiaresmallerthantheuser-specifiederrorthreshold,theslidingwindowcontinuestogrow.Otherwise,thelinesegmentpapi-1isincludedaspartoftheapproximatedtrajectoryandpiissetasthenewanchorpoint.Thealgorithmcontinuesuntilallthelocationpointsintheoriginaltrajectoryarevisited.,.,SlidingWindow-Illustration,Whiletheslidingwindowgrowsfromp0top0,p1,p2,p3,alltheerrorsbetweenfittinglinesegmentsandtheoriginaltrajectoryarenotgreaterthanthespecifiederrorthreshold.Whenp4isincluded,theerrorforp2exceedsthethreshold,sop0p3isincludedintheapproximatetrajectoryandp3issetastheanchortocontinue.,.,OpenWindow,Differentfromtheslidingwindow,chooselocationpointswiththehighesterrorintheslidingwindowastheclosingpointoftheapproximatinglinesegmentaswellasthenewanchorpoint.Whenp4isincluded,theerrorforp2exceedsthethreshold,sop0p2isincludedintheapproximatetrajectoryandp2issetastheanchortocontinue.,.,Part1Summary,TrajectoryDataCompressionBatchDouglas-Peucker(DP)Top-DownTimeRatio(TDTR)timeincludedBellmandynamicprogrammingOn-lineSlidingwindowOpenwindow(variationofslidingwindow),.,Part2-Filtering,GoalsSmoothnoise&outliersInferhigherlevelvalues(e.g.speed),TechniquesMeanandmedianKalmanfilterParticlefilter,.,RunningExample,Trackamovingpersonin(x,y)1075(x,y)measurements=1secondManuallyaddedoutliers,measurementvector,actuallocation,noise,zeromean,standarddeviation=4meters,Notation,.,MeanFilter,Alsocalled“movingaverage”and“boxcarfilter”Applytoxandymeasurementsseparately,zx,t,Filteredversionofthispointismeanofpointsinsolidbox,“Causal”filterbecauseitdoesntlookintofutureCauseslagwhenvalueschangesharplyHelpfixwithdecayingweights,e.g.Sensitivetooutliers,i.e.onereallybadpointcancausemeantotakeonanyvalueSimpleandeffective(Iwillnotvotetorejectyourpaperifyouusethistechnique),.,MeanFilter,10pointsineachmean,OutlierhasnoticeableimpactIfonlythereweresomeconvenientwaytofixthis,outlier,.,MedianFilter,zx,t,Filteredversionofthispointismeanmedianofpointsinsolidbox,Insensitivetovalueof,e.g.,thispoint,median(1,3,4,7,1x1010)=4mean(1,3,4,7,1x1010)2x109,Medianiswaylesssensitivetooutlinersthanmean,.,MedianFilter,10pointsineachmedian,Outlierhasnoticeablelessimpact,outlier,.,Joke,Theoneaboutthestatisticianswhogohunting,.,KalmanFilter,MyfavoritebookonKalmanfiltering,MeanandmedianfiltersassumesmoothnessKalmanfilteraddsassumptionabouttrajectory,Assumedtrajectoryisparabolic,data,dynamics,Weightdataagainstassumptionsaboutsystemsdynamics,Bigdifference#1:Kalmanfilterincludes(helpful)assumptionsaboutbehaviorofmeasuredprocess,.,KalmanFilter,Bigdifference#2:Kalmanfiltercanincludestatevariablesthatarenotmeasureddirectly,Kalmanfilterseparatesmeasuredvariablesfromstatevariables,Runningexample:measure(x,y)coordinates(noisy),Runningexample:estimatelocationandvelocity(!),Measure:,Inferstate:,.,KalmanFilterMeasurements,Measurementvectorisrelatedtostatevectorbyamatrixmultiplicationplusnoise.,Runningexample:,Inthiscase,measurementsarejustnoisycopiesofactuallocationMakessensornoiseexplicit,e.g.GPShasofaround4meters,.,KalmanFilterDynamics,Insertabiasforhowwethinksystemwillchangethroughtime,locationisstandardstraight-linemotion,velocitychangesrandomly(becausewedonthaveanyideawhatitactuallydoes),.,KalmanFilterIngredients,Hmatrix:givesmeasurementsforgivenstate,Measurementnoise:sensornoise,matrix:givestimedynamicsofstate,Processnoise:uncertaintyindynamicsmodel,.,KalmanFilterRecipe,JustpluginmeasurementsandgoRecursivefiltercurrenttimestepusesstateanderrorestimatesfromprevioustimestep,Bigdifference#3:KalmanfiltergivesuncertaintyestimateintheformofaGaussiancovariancematrix,.,HardtopickprocessnoisesProcessnoisemodelsouruncertaintyinsystemdynamicsHereitaccountsforfactthatmotionisnotastraightline,Velocitymodel:,“Tuning”s(bytryingabunchofvalues)givesbetterresult,.,ParticleFilter,DieterFoxetal.,WiFitrackinginamulti-floorbuilding,Multiple“particles”ashypothesesParticlesmovebasedonprobabilisticmotionmodelParticlesliveordiebasedonhowwelltheymatchsensordata,.,ParticleFilter,DieterFoxetal.,Allowsmulti-modaluncertainty(KalmanisunimodalGaussian)Allowscontinuousanddiscretestatevariables(e.g.3rdfloor)Allowsrichdynamicmodel(e.g.mustfollowfloorplan)Canbeslow,especiallyifstatevectordimensionistoolarge(e.g.(x,y,identity,activity,nextactivity,emotionalstate,),.,ParticleFilterIngredients,z=measurement,x=state,notnecessarilysameProbabilitydistributionofameasurementgivenactualvalueCanbeanything,notjustGaussianlikeKalmanButweuseGaussianforrunningexample,justlikeKalman,Forrunningexample,measurementisnoisyversionofactualvalue,E.g.measuredspeed(inz)willbeslowerifemotionalstate(inx)is“tired”,.,ParticleFilterIngredients,Probabilisticdynamics,howstatechangesthroughtimeCanbeanything,e.g.TendtogosloweruphillsAvoidleftturnsAttractedtoScandinavianpeopleClosedformnotnecessaryJustneedadynamicsimulationwithanoisecomponentButweuseGaussianforrunningexample,justlikeKalman,xi,xi-1,randomvector,.,ParticleFilterAlgorithm,StartwithNinstancesofstatevectorxi(j),i=0