从轨迹中发现热门路线扁平简洁风论文答辩ppt模板

DiscoveringPopularRoutesfromTrajectories从轨迹中发现热门路线分享人：J-JaSonConferenceICDE2011InternationalConferenceonDataEngineeringSchool&Author2014/15QS43School&AuthorZaibenChenHengTaoShenXiaofangZhouTheaimDiscoveringtheMostPopularRoutebetweentwolocationsbyobservingbehaviorsofmanyprevioususers.通过观察之前用户的行为，找出两地之间最热门的路线WhydothisIsusefulespeciallyforuserswhoaretravelingtounfamiliarareas.对在陌生区域驾驶的人很有帮助。Theshortestorthefastestmaynotbethebest.最短的和最快的不一定是最好的。HowdothisHowdothisThreesteps:1DevelopaCoherenceExpandingalgorithmtoretrieveatransfernetworkfromrawtrajectories提出CoherenceExpandingalgorithm用于从未预处理的轨迹中得到transfernetworkHowdothisThreesteps:2TheAbsorbingMarkovChainmodelisappliedtoderiveareasonabletransferprobabilityforeachtransfernode用AbsorbingMarkovChainmodel推导出每个转换点的transferprobabilityHowdothisThreesteps:3ProposeaMaximumProbabilityProductalgorithmtodiscovertheMPRfromatransfernetwork使用MaximumProbabilityProduct从转换网络中得到MPR(最热门路径)RelatedWorkStep1MiningTransferNetworkIsasetoftransfernodes,whichcanbeanintersectionoftrajectoriesorjusttheendlocationsofatrajectory.N是交换点的集合，交换点可以是轨迹的交叉点也可以是轨迹的终点。Isacollectionoftransferedgesconnectingtransfernodes.E是一系列连接交换点的交换边。MiningTransferNetworkNoticethatifthereisaroadmapavailable,wecanfindoutthetransfernetworkbymap-matchingtrajectories.Tracesofhiking,boating,walking,andmanyout-dooractivitiesarenotconstrainedbyaroadnetwork.爬山，划船，步行等户外运动的不会被路网所限制mostmapsthatpeoplethinkofasfreehavelegalortechnicalrestrictionsontheiruse.很多地图上的路线或有法律或者技术上的限制MiningTransferNetworkDetecttheintersectionsoftrajectoriesIntersectionsoftrajectoriesWithinanintersectionregion,thedensityoftrajectorypointsisnormallyhigher,incomparisonwiththedensityofpointsonanincoming/outgoingroadedge,becauseitistheplacewheretrajectoriesjointogetherordriversslowdowntomakeaturn.Ifweconsideranintersectionasagroupofpoints,thenthesizeofthegroupshouldbegreaterthansomethreshold.IntersectionsoftrajectoriesAnumberoftrajectorieschangemovingdirectionatanintersection,assomepeoplemaketurns.Themovingdirectionsoftrajectorypointsfrom/todifferentroadedgesarelikelytobeorthogonal(i.e.,angleofdifferencetendsto𝜋/2).Withinasmalldistance,pointswhosemovingdirectionsdifferby0or𝜋(i.e.,inthesameoroppositedirection)areprobablyonthesameroad,whilepointswithdirectiondifference0and𝜋arepossiblymovingtodifferentroadbranchesofanintersection.Theclosertheangleofdifferencetendsto𝜋/2,thehigherpossibilitythatanintersectionexists.Intersectionsoftrajectoriesdensity密度条件direction方向条件Definition1Definition1：Coherence𝑑𝑖𝑠𝑡(𝑝,𝑞)istheEuclideandistancebetween𝑝and𝑞𝜃istheangleofdifferencebetween𝑝and𝑞’smovingdirections𝛿isascalingfactor𝛼and𝛽aretuningparametersDefinition2,3Definition2：DirectlyCoherence-ConnectedifthenDefinition3：Coherence-ConnectedIfthereisachainofpointsandthenandObviously,CoherenceConnectedisasymmetricandtransitiverelation.AlgorithmDBSCANDensityCoherenceAlgorithmAlgorithmPracticeInpractice,asGPSdataismoreorlessdirty,wefirstreduceoutlierpointsthatsuddenlyjumpawaybyconsideringphysicallimitsonvehiclespeed,beforerunningtheclusteringalgorithm.Besides,linearinterpolationisconductedforlowsampling-ratetrajectoriestoreducethepossibilitythattheyaremissedatsomeintersectionsthattheydopassthrough.DirectionsmoothingisalsocarriedouttoalleviatetheeffectofpositionfluctuationcausedbyGPSinaccuracy.MiningTransferNetworkAfterdiscoveringalltheclusters(intersections),wetreateachofthemasatransfernodewhoselocationisapproximatedbytheaveragecoordinate,whiletransferedgesareconstructedbycheckingtrajectoriesbetweennodes.Step2DerivingTransferProbabilityTheaim：Theaimistofindoutwhichtransfernodeismorelikelytoleadausertothedestination,andthisprobabilitywillserveasapopularityindicator.根据每个点引导用户驶向终点的可能性，推导出每个交换点的受欢迎程度。DerivingTransferProbabilityWhere𝑑𝑖𝑠𝑡𝑠(𝑡𝑟𝑎𝑗,𝑑)istheshortestEuclidean/networkdistancebetween𝑑andthefrontpartof𝑡𝑟𝑎𝑗thatstartsfrom𝑛𝑖.RandomWalkIfweconductsucharandomwalk,whatistheexactprobabilitythat,startingfromanode𝑛𝑖,wewilleventuallyreachthedestination𝑑within𝑡steps?用t步从ni走到nj的概率在t步之内步从ni走到nj的概率ChooseparametercSet𝑡asthediameterofthetransfernetworkinourexperiments,whichguaranteesatleastoneroutecanbefoundbetweenanytwonodesandalsoavoidsconsideringthoseexcessivelylongroutes.toobig没意义toosmall误认为不可达AMCMAbsorbingMarkovChainModel:Astate(node)𝑛𝑖ofaMarkovchainiscalledabsorbingifit’simpossibletoleaveit.endpointsofTwithoutanyoutgoingedgesthedestinationnodeAMCMAMCMAssumetherearetotally𝑥absorbingstates,and𝑦transientstates(𝑥+𝑦=𝑚).WegroupabsorbingstatesintoABSandtransientstatesintoTR.Transfermatrix：y-by-ymatrixy-by-xmatrixx-by-yzeromatrixx-by-xidentitymatrixHowtocalculateExample：P1P2P3P111/21/3P21/411/2P31/31/51P=1/3+1/4=7/12P1→P1→P31×1/3=1/3P1→P2→P31/2×1/2=1/4WhydothisLemma3:Aroutethatfirstvisitsthedestinationinexactly(𝑡0)steps(transfers),muststartfromatransientstate,andthestateat𝑡=1,2,⋅⋅⋅,𝑡−1stepisalsoatransientstate.一条路径经过t步到达终点，终点是吸收态(absorbingstate)，之前所到达的点都是转移态(transientstate)。Whydothis在t步之内步从ni走到d的概率用t步从ni走到d的概率WhydothisExpressedinmatrixform:Howtocalculate1d1d