毕业答辩PPT模板_深蓝学术简约

Discovering Popular Routes from Trajectories 从轨迹中发现热门路线 分享人： School & Author 2014/15 QS 43 School & Author Zaiben Chen Heng Tao Shen Xiaofang Zhou The aim Discovering the Most Popular Route between two locations by observing behaviors of many previous users. 通过观察之前用户的行为，找出两地之间最热门的路线 Why do this Is useful especially for users who are traveling to unfamiliar areas. 对在陌生区域驾驶的人很有帮助。 The shortest or the fastest may not be the best. 最短的和最快的不一定是最好的。 How do this How do this Three steps: 1 Develop a Coherence Expanding algorithm to retrieve a transfer network from raw trajectories 提出Coherence Expanding algorithm 用于从未预处 理的轨迹中得到transfer network How do this Three steps: 2 The Absorbing Markov Chain model is applied to derive a reasonable transfer probability for each transfer node 用Absorbing Markov Chain model 推导出每个转换点 的transfer probability How do this Three steps: 3 Propose a Maximum Probability Product algorithm to discover the MPR from a transfer network 使用Maximum Probability Product 从转换网络中得到 MPR( 最热门路径) Related Work Step 1 Mining Transfer Network Is 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 transfer nodes. E 是一系列连接交换点的交换边。 Mining Transfer Network Notice 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 people think of as free have legal or technical re strictions on their use. 很多地图上 的路线或有法 律 或者技术上的 限制 Mining Transfer Network Detect the intersections of trajectories Intersections of trajectories Within an intersection region, the density of trajectory point s is normally higher, in comparison with the density of point s on an incoming/outgoing road edge, because it is the place where trajectories join together or drivers slow down to ma ke a turn. If we consider an intersection as a group of points, then the size of the group should be greater than some thre shold. Intersections of trajectories A number of trajectories change moving direction at an inte rsection, as some people make turns. The moving directions of trajectory points from/to different road edges are likely t o be orthogonal (i.e., angle of difference tends to /2). Wit 𝜋 hin a small distance, points whose moving directions differ b y 0 or (i.e., in the same or opposite direction) are probabl 𝜋 y on the same road, while points with direction difference>0 and < are possibly moving to different road branches of a 𝜋 n intersection. The closer the angle of difference tends to 𝜋 /2, the higher possibility that an intersection exists. Intersections of trajectories density 密度条件 direction 方向条件 Definition 1 Definition 1 ： Coherence 𝑑𝑖𝑠𝑡( , ) is the Euclidean 𝑝𝑞 distance between and 𝑝 𝑞 𝜃is the angle of differen ce between and ’s m 𝑝 𝑞 oving directions 𝛿is a scaling factor 𝛼and are tuning parameter 𝛽 s Definition 2,3 Definition 2 ：Directly Coherence- Connectedif then Definition 3 ：Coherence-Connected If there is a chain of points and then and Obviously, CoherenceConnected is a symmetric and transitive relation. Algorithm DBSCAN Density Coherence Algorithm Algorithm Practice In practice, as GPS data is more or less dirty, we first reduce outlier points that suddenly j ump away by considering physical limits on v ehicle speed, before running the clustering al gorithm. Besides, linear interpolation is cond ucted for low sampling-rate trajectories to re duce the possibility that they are missed at s ome intersections that they do pass through. Direction smoothing is also carried out to alle i t th ff t f iti fl t ti d Mining Transfer Network After discovering all the clusters (intersecti ons), we treat each of them as a transfer n ode whose location is approximated by th e average coordinate, while transfer edges are constructed by checking trajectories b etween nodes. Step 2 Deriving Transfer Probability The aim ： The aim is to find out which transfer nod e is more likely to lead a user to the desti nation, and this probability will serve as a popularity indicator. 根据每个点引导用户驶向终点的可能性，推导出每个交换点 的受欢迎程度。 Deriving Transfer Probability Where ( , ) is the shortest Euclidean/network 𝑑𝑖𝑠𝑡𝑠𝑡𝑟𝑎𝑗𝑑 distance between and the front part of that 𝑑 𝑡𝑟𝑎𝑗 starts from . 𝑛𝑖 Random Walk If we conduct such a random walk, what is the exact probabi lity that, starting from a node , we will eventually reach th 𝑛𝑖 e destination within steps? 𝑑 𝑡 用t 步从ni 走到nj 的概率 在t 步之内步从ni 走到nj 的概率 Choose parameter c Set as the diameter of the transfer network in our 𝑡 experiments, which guarantees at least one route can be found between any two nodes and also avoids considering those excessively long routes. too big 没意义 too small 误认为不可达 AMCM Absorbing Markov Chain Model: A state (node) of a Markov chain is called ab 𝑛𝑖 sorbing if it’s impossible to leave it. end points of T without any outgoing edges the destination node AMCM AMCM Assume there are totally absorbing states, and transient 𝑥 𝑦 states ( + = ). We group absorbing states into ABS and tr 𝑥𝑦𝑚 ansient states into TR. Transfer matrix ： y-by-y matrix y-by-x matrix x-by-y zero matrix x-by-x identity matrix How to calculate Example ： P1 P2 P3 P1 1 1/2 1/3 P2 1/4 1 1/2 P3 1/3 1/5 1 P = 1/3+1/4 = 7/12 P1→P1→P3 1×1/3 = 1/3 P1→P2→P3 1/2×1/2 = 1/4 Why do this Lemma 3: A route that first visits the destination in exa ctly ( >0) steps (transfers), must start from a 𝑡 transient state, and the state at =1,2, , −1 𝑡 ⋅⋅⋅𝑡 step is also a transient state. 一条路径经过t 步到达终点，终点是吸收态(absorbing st ate) ，之前所到达的点都是转移态(transient state) 。 Why do this 在t 步之内步从ni 走到d 的概率 用t 步从ni 走到d 的概率 Why do this Expressed in matrix form: How to calculate 1 d1 d2 …… dx n1 p(n1, d1) p(n1, d2) …… p(n1, dx) n2 p(n2, d1) p(n2, d2) …… p(n2, dx) n3 p(n3, d1) p(n3, d2) …… p(n3, dx) How to calculate 2 p(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) D = 0 1 0 …… 0 = p(n1, d2) p(n2, d2) p(n3, d2) S D y-by-x x-by-1 y-by-1 How to calculate 3 p(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) D = = Σ(p(n1,ni)×p(ni, d2)) Σ(p(n2,ni)×p(ni, d2)) Σ(p(n3,ni)×p(ni, d2)) Q Q·D y-by-y y-by-1 y-by-1 p(n1, d2) p(n2, d2) p(n3, d2) D Step 3 Searching The MPR 热门程度的另一表达形式: 路线的定义: A route is defined as a consecutive sequence o 𝑅 f transfer nodes 1 →2 → , where ( , +1), 𝑛 𝑛 ⋅⋅⋅𝑛𝑖 𝑛𝑗𝑛𝑗 (1≤< ), is an existed transfer edge. 𝑗𝑖 路线热门程度定义: Algorithm Dijkstra Algorithm 𝐿( ) 𝑛𝑖 Why However, a problem with this alternative option is that the search algorithm just c onsiders the local information of the curr ent node other than steps further, whic 𝑡 h possibly causes an incorrect result. ——author Experiments Contributions We present a new route planning approach that gives anot her option for users other than existing shortest path base d methods. We develop an algorithm to establish the transfer network model of a collection of historical trajectories, and utilize th e Absorbing Markov Chain model to derive the transfer pro bability for transfer nodes. We propose a reasonable popularity function as well as the search algorithm for discovering the most popular route ov er a transfer network. Thank you!