大学毕业答辩PPT模板报告 (428).pptx

《大学毕业答辩PPT模板报告 (428).pptx》由会员分享，可在线阅读，更多相关《大学毕业答辩PPT模板报告 (428).pptx（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Discovering Popular Routesfrom Trajectories 从轨迹中发现热门路线分享人：School&Author2014/15 QS43School&AuthorZaiben ChenHeng Tao ShenXiaofang ZhouThe aimDiscovering the Most Popular Route between two locations by observing behaviors of many previous users.通过观察之前用户的行为，找出两地之间最热门的路线Why do thisIs useful especially f

2、or users who are traveling to unfamiliar areas.对在陌生区域驾驶的人很有帮助。The shortest or the fastest may not be the best.最短的和最快的不一定是最好的。How do thisHow do thisThree steps:1Develop a Coherence Expanding algorithm to retrieve a transfer network from raw trajectories提出Coherence Expanding algorithm 用于从未预处理的轨迹中得到tra

3、nsfer networkHow do thisThree steps:2The Absorbing Markov Chain model is applied to derive a reasonable transfer probability for each transfer node用Absorbing Markov Chain model推导出每个转换点 的transfer probabilityHow do thisThree steps:3Propose a Maximum ProbabilityProduct algorithm to discover the MPR fro

4、m a transfer network使用Maximum Probability Product从转换网络中得到MPR(最热门路径)Related WorkStep 1Mining Transfer NetworkIs a set of transfer nodes,which can be an intersection of trajectories or just the end locations of a trajectory.N是交换点的集合，交换点可以是轨迹的交叉点也可以是轨迹的终点。Is a collection oftransfer edges connecting tra

5、nsfer nodes.E是一系列连接交换点的交换边。Mining Transfer NetworkNotice that if there is a road map available,we can find out the transfer network by map-matching trajectories.Traces of hiking,boating,walking,and many out-door activities are not constrained by a road network.爬山，划船，步行等户外运动的不会被路网所限制most maps that pe

6、ople think of as free have legal or technical restrictions on their use.很多地图上的路线或有法律或者技术上的限制Mining Transfer NetworkDetect the intersections of trajectoriesIntersections of trajectoriesWithin an intersection region,the density of trajectory points is normally higher,in comparison with the density of

7、points on an incoming/outgoing road edge,because it is the place where trajectories join together or drivers slow down to make a turn.If we consider an intersection as a group of points,then the size of the group should be greater than some threshold.Intersections of trajectoriesA number of trajecto

8、ries change moving direction at an intersection,as some people make turns.The moving directions of trajectory points from/to different road edges are likely to be orthogonal(i.e.,angle of difference tends to /2).Within a small distance,points whose moving directions differ by 0 or (i.e.,in the same

9、or opposite direction)are probably on the same road,while points with direction difference0 and 0)steps(transfers),must start from a transient state,and the state at=1,2,1 step is also a transient state.一条路径经过t步到达终点，终点是吸收态(absorbing state)，之前所到达的点都是转移态(transient state)。Why do this在t步之内步从ni走到d的概率用t步从

10、ni走到d的概率Why do thisExpressed in matrix form:How to calculate 1d1d2dxn1p(n1,d1)p(n1,d2)p(n1,dx)n2p(n2,d1)p(n2,d2)p(n2,dx)n3p(n3,d1)p(n3,d2)p(n3,dx)nyp(ny,d1)p(ny,d2)p(ny,dx)How to calculate 2p(n1,d1)p(n1,d2)p(n1,dx)p(n2,d1)p(n2,d2)p(n2,dx)p(n3,d1)p(n3,d2)p(n3,dx)p(ny,d1)p(ny,d2)p(ny,dx)D=0100=p(n1,d2

11、)p(n2,d2)p(n3,d2)p(ny,d2)SDy-by-xx-by-1y-by-1How to calculate 3p(n1,n1)p(n1,n2)p(n1,ny)p(n2,n1)p(n2,n2)p(n2,ny)p(n3,n1)p(n3,n2)p(n3,ny)p(ny,n1)p(ny,n2)p(ny,ny)D=(p(n1,ni)p(ni,d2)(p(n2,ni)p(ni,d2)(p(n3,ni)p(ni,d2)(p(ny,ni)p(ni,d2)QQDy-by-yy-by-1y-by-1p(n1,d2)p(n2,d2)p(n3,d2)p(ny,d2)DStep 3Searching T

12、he MPR热门程度的另一表达形式:路线的定义:A route is defined as a consecutive sequence of transfer nodes 1 2 ,where(,+1),(1),is an existed transfer edge.路线热门程度定义:AlgorithmDijkstraAlgorithm()WhyHowever,a problem with this alternative option is that the search algorithm just considers the local information of the curre

13、nt node other than steps further,which possibly causes an incorrect result.authorExperimentsContributionsWe present a new route planning approach that gives another option for users other than existing shortest path based methods.We develop an algorithm to establish the transfer network model of a collection of historical trajectories,and utilize the Absorbing Markov Chain model to derive the transfer probability for transfer nodes.We propose a reasonable popularity function as well as the search algorithm for discovering the most popular route over a transfer network.Thank you!