# A Trajectory Partition Method Based on Combined Movement Features

Authors: Ji Tang; Linfeng Liu; Jiagao Wu
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

Trajectory data mining has become an increasing concern in the location-based applications, and the trajectory partition is taken as the primary procedure of trajectory data mining. The amount of movement trajectories of nodes is typically very large, and the trajectory shapes are extremely diverse, which makes the trajectory partition a vital issue to the trajectory data mining results. In this work, the movement behaviors of nodes are analyzed from the aspects of moving speeds, stop points, and moving directions, and then a novel Trajectory Partition Method based on combined movement Features (TPMF) is proposed to partition the trajectories. In TPMF, we first extract the change points where the movement speeds of nodes are varied significantly; then, we extract the stop points by detecting the speed variations of nodes; finally, the Douglas-Peucker algorithm is applied to partition the subtrajectories according to the extracted feature points (change points and stop points). Simulations are carried out on theGeolife trajectory dataset, and the simulation results indicate that TPMF can achieve a preferable trade-off between the simplification rate and the trajectory partition error, while the running time is shortened as well.


---

## Body

## 1. Introduction

Recently, the mobile communication devices with GPS modules are very popular due to the development of location-aware technology. For example, some people (nodes) carrying communication devices travel along urban roads, and the personal geographical locations can be recorded by the GPS modules at regular intervals. Thus, each movement trajectory consisted of some GPS points arranged in chronological order. Note that we can obtain many valuable information by mining these trajectories, such as the movement behaviors of nodes, which can be exploited and served for the applications of location recommendations [1], destination predictions [2], and personal navigations [3].In general, the personal trajectories are very complicated, since the nodes always move casually. There is a vital issue to be addressed for the trajectory data mining: the trajectory data is generated quickly, and the storage space of nodes is occupied, which brings large computation burdens and storage burdens in trajectory data mining. On the contrary, the reduction of the number of trajectory data leads to the loss of some key information, making the outcome of trajectory prediction inaccurate.The trajectory partition is served for the removals of redundant GPS points and the detections of node behaviors. Especially, it is necessary to simplify the trajectories to avoid the unbearable computation burdens in trajectory data mining phase, while the valuable information regarding the trajectory contours can be reserved as much as possible. In this paper, we partition the trajectories into successive line segments according to the combined movement features (moving speeds, stop points, and moving directions). The main intention of our work is to make a preferable trade-off between the simplification rate and the trajectory partition error while shortening the running time.To reduce the computation burdens in the trajectory mining phase, the existing trajectory partition methods always attempt to find and remove the redundant trajectory points and reserve the valuable trajectory points. However, the results of trajectory partition are not preferable because the movement features are not comprehensively considered in these methods. To this end, we take into account the typical movement features, such as the spatial locations, directions, time, movements, and stops for analyzing the trajectories, and these features are concluded and combined as moving speeds, stop points, and moving directions. The innovations of this paper are given as follows:(1)
The novel idea of partitioning the trajectories based on moving speeds, stop points, and moving directions is proposed to remove the redundant trajectory points while ensuring the trajectory accuracy.(2)
A stop point extraction algorithm based on moving speeds is put forward to extract the stop points more accurately. Especially, we improve the stop point extraction through applying our proposed mechanisms of forward search and backward search based on moving speeds. Our method reduces the unnecessary computations by detecting the speeds, and more accurate results can be obtained from the mechanisms of forward search and backward search.(3)
A Douglas-Peucker algorithm based on perpendicular Euclidean distance and directions is utilized to maintain the overall shapes of trajectories as much as possible through retaining the points where the directions change abruptly; i.e., we combine the indices of perpendicular Euclidean distance and moving directions to identify the points where the directions change abruptly while the overall contours of trajectories are basically maintained.The rest of the paper is organized as follows: Section2 gives some related works. Section 3 introduces the Trajectory Partition Method based on combined movement Features (TPMF). Section 4 reports the simulation results for performance evaluation of TPMF. Finally, Section 5 concludes this paper.


## 2. Related Work

The technique of trajectory partition is derived from that of trajectory compression. In early work, two representative strategies of trajectory compression are proposed in [4], which introduces an offline compression method and an online compression method, respectively. Given a fully generated trajectory, the offline compression generates an approximate trajectory by removing some redundant points from the original trajectory. The well-known offline trajectory compression method is Douglas-Peucker (DP) algorithm [5], and the idea of DP is to replace a subtrajectory with an approximate line segment, as shown in Figure 1(a). DP recursively partitions each trajectory into two subtrajectories by selecting the points can contributing the largest error as the splitting points, until the specified perpendicular Euclidean distance is satisfied. As the perpendicular Euclidean distance is not associated with the time stamps, and thus an improved Top-Down algorithm [6] is proposed to compress the trajectories, where the temporal-distance information of each sample point is defined and considered. In contrast to the offline compression, the online compression does not require complete trajectories, and each trajectory is compressed immediately while it is transmitted. SQUISH [7] works in the streaming environment with a fixed-size buffer. For each point, it maintains a priority which serves as the upper bound of SED distance for the neighboring points. This is because when a point is deleted from buffer, its priority score will be accumulated to its two neighboring points. Since SQUISH is not error-bounded, its subsequent work SQUISH-E [8] is designed to be adaptive to different objectives by introducing two parameters λ (compression ratio bound) and μ (compression error bound). BQS [9] picks at most eight significant points, forming a convex hull to enclose all the points in the buffer. Then, an upper bound and a lower bound are derived, such that a point can be quickly decided to be removed or reserved. Recently, Liu et al. propose an one-pass error bounded trajectory simplification algorithm named OPERB [10]. Based on a local distance checking method, OPERB maintains a directed line segment to approximate the buffered points and guarantees that the distance from the current point to the line segment is bounded.Figure 1
Trajectory compression and partition.
(a)
Douglas-Peucker algorithm (b)
MDL algorithm (c)
Algorithm based on position perturbationIn addition, some other researches aim to reduce the number of trajectory data and maintain the semantic meanings, such as the types of places where the nodes stay for a long period. References [11, 12] attempt to maintain the semantic meanings of original trajectories after trajectory compression process.As a basis of the techniques of trajectory clustering and trajectory classification, we need to partition the original trajectories into several successive line segments for a further process. Lee et al. [13] present a trajectory partition method based on Minimum Description Length (MDL), as shown in Figure 1(b), whereL(H) represents the length sum of all trajectory partitions, andL(D|H) represents the sum of the difference between the trajectory and its trajectory partitions. MDL finds a list of characteristic points to minimize the value ofL(H) +L(D|H). Reference [14] provides a trajectory partition method based on the position perturbation, as shown in Figure 1(c), and this method calculates the perpendicular distance from a point to the previous moving direction. If the perpendicular distance is larger than a preset threshold, then the previous point is reserved. The above steps are repeated until all points have been traversed. Besides, Fu et al. [15] first find the stop points and then apply DP algorithm to simplify the trajectory segments between adjacent stop points. Besides, a corner detection based method is adopted to divide trajectories in [16].Most of aforementioned works always divide trajectories spatially, and it is necessary to take into account the critical movement features such as the moving speeds, stop points, and moving directions. Moreover, a preferable trade-off between the simplification rate and the trajectory partition error is expected to be achieved.


## 3. Trajectory Partition Method

In real-world scenes, we note the three significant characteristics regarding the node movements: (i) the moving speeds of nodes changes greatly due to the switches of different travel modes or some special events (e.g., sudden braking or abrupt deceleration in driving) [17]; (ii) the nodes are prone to visit some locations intentionally or unintentionally, and the locations visited frequently or stayed for a long period can be marked as stop points; (iii) the moving directions of nodes are varied frequently when some travel modes (such as the walking mode) are adopted [17].To this end, we propose a trajectory partition method based on combined movement features (moving speeds, stop points and moving directions). Several definitions are first given as follows.Definition 1 (a GPS point).
A GPS pointpi=(lati,lngi,ti) is expressed as a quadruple, which is composed of the latitude, longitude and timestamp of the i-th point, where i=1,2,…,n, n denoting the number of GPS points in a trajectory.Definition 2 (a trajectory).
A trajectory is composed of the GPS points arranged in the chronological order and is denoted byTR=p1,p2,…,pn.Definition 3 (a stop point).
A stop pointSPi=(lati,lngi,tstarti,tendi) denotes a location where a node arrives at the time tstarti and departs at the time tendi.


### 3.1. Moving Speeds

Usually, the moving speed of a node is changed largely when its travel mode is switched [17]. The common travel modes include walking, riding bicycles, taking buses, driving cars, or taking the subway. As shown in Figure 2, suppose the node travels from the locationA to the locationB and the change point is the position where the node switches the travel mode from walking to taking the bus.Figure 2
Travel mode transition.To detect the change point caused by the switch among different travel modes, we define the moving speed difference as△i+1=vi,i+1-vi+1,i+2, where vi,i+1 represents the average speed on the line segment pipi+1. If △i+1 is larger than a given threshold, then pi+1 will be retained as a change point.Considering the fact that the speed changes are usually caused by the switches among different travel modes (Figure3), we take the standard deviation of moving speeds as the speed threshold, since the standard deviation can reflect the speed fluctuations. The speed threshold vth is expressed as(1)vth=∑i=1n-1vi,i+1-v¯2n-1,where v¯=∑i=1n-1vi,i+1/n-1; i.e., v¯ denotes the average speed in a trajectory.Figure 3
Speed change.


### 3.2. Stop Points

Another fact is that the nodes are possible to stay around some locations for a long period, e.g., waiting for the bus, having a dinner at a restaurant, resting in a leisure area, or shopping at a mall, and these locations can be taken as stop points. There are two types of stop points [18–20]: (a) the position-invariant stop points: such as theSP1 in Figure 4, which is determined according to the preset staying period; (b) the position-offset stop points: the node moves around a position for a preset period, such as theSP2 in Figure 4.Figure 4
Two types of stop points.In previous works, the stay points are detected according to the distance threshold and the time threshold, i.e., the distance between an anchor point and its successors is judged whether it is larger than the distance threshold, and then the time span between the anchor point and the last successor is measured. If the time span is larger than the time threshold, a stay point is determined.Notice that the stop point cannot be extracted when there is a round-trip path. As illustrated in Figure5, a customer (node) visits a convenience store from pi and then walks along the direction pipj→. Assume the distance dij between pi and pj is larger than the distance threshold, while the time duration of the node traveling from pi to pj-1 is also larger than the time threshold, and hence the average coordinate of all points from pi to pj-1 can be denoted by the stop point, which actually leads to the extraction of a false stop point.Figure 5
A false stop point.In addition, this process may fail to accurately detect the stop points due to the false position of the start point; as shown in Figure6, if p1 is taken as a start point mistakenly, then a false stop point is extracted.Figure 6
A false stop point.Actually, the setting of the distance threshold will affect the detection accuracy of stop points. If a smaller distance threshold is set (e.g., 10m), a smaller portion of points located within the ranges of stay points is not detected, as shown in Figure7(a), and p6 and p7 are not detected. If a large distance threshold is set (e.g., 100m), the points not falling into within range of stay point are also detected, as shown in Figure 7(b); p6, p7, and p8 can be detected.Figure 7
Two cases of distance threshold settings: (a) a smaller distance threshold and (b) a larger distance threshold.
(a) (b)Furthermore, the time threshold is related to the number of stay points, and a smaller time threshold will result in more stop points; on the contrary, less stop points are detected if a larger time threshold is set.To address the issues mentioned above, we observe that the speed of a node always becomes slow when it visits a location, and thus we propose a Stop Points Extraction Method based on the moving Speeds of nodes (SPEMS). In SPEMS, the stop points can be extracted through the following steps.Step 1.
Each pair of adjacent GPS pointspi, pi+1 is traversed, and the moving speed vi,i+1 is calculated.Step 2.
Ifvi,i+1 is equal to 0 or vi,i+1≤λv (λv denotes a speed threshold), then a backward search with the center pi+1 is performed to extract a point pL, such that the inequalities dist(pi+1,pk)≤r and dist(pi+1,pL-1)>r are satisfied, where r denotes a search radius threshold and k=i,i-1,…,L.Step 3.
A forward search is performed to extract a pointpR, such that the inequalities dist(pi+1,pk)≤r and dist(pi+1,pR+1)>r are satisfied, where k=i+2,i+3,…,R.Step 4.
If the time interval△t(pL,pR)≥δt (δt denotes the time threshold), then we take the intermediate point p⌊(L+R)/2⌋ as a stop point. Obviously, we remove the points from pL to pR except p⌊(L+R)/2⌋, and this mechanism can avoid these points being repeatedly detected.Figure8 gives an example of forward search and backward search, where pL is found by a backward search with the center pi+1 and pR is found by a forward search.Figure 8
Forward search and backward search.An example is given in Figure9, where we assume v5,6≥vth and hence we can find the points p2 and p10 with the center p6 through the backward search and the forward search, respectively. If △t(p2,p10)≥δt, we set p⌊(2+10)/2⌋ as the stop point; i.e., p6 is a stop point.Figure 9
Stop point extraction.The pseudocode of SPEMS is depicted in Algorithm1.Algorithm 1:SPEMS pseudocode.
Input: T R = p 1 , p 2 , … , p n , r , λ v , δ t. Output: SP. 1:i=1. 2:whilei<ndo 3:   j=i+1. 4:   Calculatevi,j. 5:ifvij==0 or vi,j≤δvthen 6:L=Backward-Search(TR,j,r). 7:R=Forward-Search(TR,j,r). 8:△t=pR.t-pL.t. 9:if△t≥δtthen 10:mid=(L+R)/2. 11:     AddTR[mid] to SP. 12:     Remove points frompL to pR except pmid. 13:i=L. 14:else 15:i=i+1. 16:end if 17:else 18:i=i+1. 19:end if 20:end while


### 3.3. Moving Directions

The changes of moving directions are concerned with the current travel modes; e.g., the moving direction will be changed more frequently when the nodes adopt the walking mode rather than taking vehicles.Besides, the traditional DP algorithm cannot maintain the shapes of the original trajectories very well in some special cases, such as the case shown in Figure10, where the point of the street corner is not taken as a feature point. The reason is that DP algorithm divides the trajectories on the basis of perpendicular Euclidean distance, and thus the points with large direction changes are easy to be ignored.Figure 10
An ignored point in DP algorithm.Therefore, we propose a DP algorithm based on Direction changes and Perpendicular Euclidean Distance (DPDPED). In DPDPED, the error measure is defined as(2)φ=θmax·distpk,pk′,i<k<j,where θmax=max⁡{θ1,θ2} and 0≤θmax≤π. θ1 represents the angle between pipj→ and pipk→, θ2 represents the angle between pipj→ and pkpj→, where pi and pj are two adjacent feature points. pk is a point on the line segment pipj→, and pk′ is the projection on pipj→. Essentially, DPDPED combines the maximum angle and the perpendicular Euclidean distance into the index of error measure, and the points ignored by DP can be found through detecting the direction changes of nodes. In this mechanism, since the value of φ is very sensitive to the direction changes, and hence the points with large direction changes can be found easily. As illustrated in Figure 11, a split point p6 divides the trajectory into two subtrajectories.Figure 11
Illustration of DPDPED algorithm.Algorithm2 gives the pseudocode of DPDPED.Algorithm 2:DPDPED pseudocode.
Input: T R = p 1 , p 2 , ⋯ , p n , F P , φ t h. Output: FP. 1:sindex=0. 2:eindex=len(TR)-1. 3:ifsindex<eindexthen 4:cindex=sindex+1. 5:φmax=0. 6:kindex=0. 7:whilecindex<eindexdo 8:φ=θmax⋅dist(pindex,pindex′). 9:ifφ≥φmaxthen 10:φmax=φ. 11:kindex=cindex. 12:end if 13:cindex=cindex+1. 14:end while 15:ifφmax≥φththen 16:FP.append(TR[kindex]). 17:DBDP(TR[sindex:kindex],FP,φth). 18:DBDP(TR[kindex:eindex],FP,φth). 19:end if 20:end if


### 3.4. Trajectory Partition Algorithm

In TPMF, the change points are first extracted based on the speed changes, and then SPEMS algorithm is applied to extract the stop points. The extracted change points and stop points are treated as feature points. Finally, DPDPED is executed to simplify the subtrajectories between the adjacent feature points. Figure12 illustrates our trajectory partition process, where two change points are found by the detection of speed changes in Figure 12(a), and then two stops points are extracted by our SPEMS in Figure 12(b), finally, a point with direction change largely is found by DPDPED in Figure 12(c). The pseudocode of TPMF is depicted in Algorithm 3.Algorithm 3:TPMF pseudocode.
Input: T R = p 1 , p 2 , … , p n , r , δ t , λ v, the maximum angle thresholdθth, the distance threshold dth. Output:Feature Point Set FP. 1:i=1,k=0,FP=Φ. 2:FP←(FP∪p1), FP←(FP∪pn). 3:vth← Calculate standard deviation of speed in TR. 4:whilei≤n-2do 5:ifvi,i+1-vi+1,i+2≥vththen 6:FP←(FP∪pi+1). 7:end if 8:i=i+1. 9:end while 10:SP=SPEMS(TR,r,δv,δt). 11:FP←(FP∪SP). 12:  Sort the points ofFP in a chronological order. 13:FP1←(FP). 14:Index← find the indexes of feature points in FP1 inTR. 15:φth=θth⋅dth. 16:whilek<len(Index)-1do 17:DPDPED(TR[Index[k]:Index[k+1]],FP,φth).  18:k=k+1. 19:end while 20:  Remove duplicate points fromFP. 21:  Sort points inFP in a chronological order.Figure 12
Trajectory partition process.
(a)
Discover change points (b)
Discover stop points (c)
Discover points with direction change largelyAccording to the steps of TPMF, the time complexity is calculated as follows:(3)n+n+FP1-1n-Np-FP1FP1+122=2n+FP1-14FP12×2n-2Np-FP12,where Np is the number of removed points within the ranges of stop points and the expression of Np is given by(4)Np=∑i=1SPNumSPi,SPi∈SP,where SPi denotes the i-th stop point in SP and Num(SPi) denotes the number of points around the stay point SPi. ⌊n-Np-|FP1|/|FP1|+1/2⌋ denotes the average number of points between adjacent feature points. Therefore, the time complexity of TPMF is written as O⌊|FP1|-1/4|FP1|2×(2n-2Np-|FP1|)2⌋. When n is large enough, we have (5)n<FP1-14FP12×2n-2Np-FP12<n2


### 3.5. Trajectory Partition Error

Two metrics have been applied to measure the performance of trajectories partition methods: (a) simplification rate refers to the ratio of removed points to original points and (b) running time represents the execution time of trajectory partition method to measure the time complexity. Besides, the error between the simplified trajectories and the original trajectories should also be measured, and we define the metric of trajectory partition error, as shown in Figure 13, pi and pj are two adjacent feature points, and the average perpendicular Euclidean distance and the average angle are used to evaluate the error of trajectory partition results.Figure 13
Trajectory partition error.The expression of average perpendicular Euclidean distance is given by(6)avgp=∑i=FIα,j=FIα+1∑k=i+1j-1distpk,pk′n-s,α=0,1,…,FI-1,where FI denotes the subscript set of feature points, dist(pk,pk′) represents the perpendicular Euclidean distance between pk and pk′, ands denotes the number of points in FP.The expression of average angle is written as(7)avga=∑i=FIα,j=FIα+1max⁡θi,j+max⁡θj,i/2s-1α=0,1,…,FI-1,where θi,j=θi,i+1,θi,i+2,…,θi,k,…,θi,j-1 represents the set of angles between pipk→ and pipj→ and θj,i=θj,j-1,θj,j-2,…,θj,k,…,θj,i+1 represents the set of angles between pjpk→ and pjpi→.Furthermore, the Min-Max standardization is used to standardizeavgp and avga, respectively. Finally, we define the trajectory partition error ε=w1·avgp∗+w2·avga∗, where w1 and w2 are the weights reflecting the impacts of average perpendicular Euclidean distance and average angle on the trajectory partition. Then, the expressions of avgp∗ are written as(8)avgp∗=avgp-minpmaxp-minp,where minp denotes the minimum value of all the perpendicular Euclidean distances from the points between adjacent feature points to the simplified line segment. Likewise, maxp represents the maximum value.The expressions ofavga∗ are written as(9)avga∗=avga-minamaxa-mina,where mina denotes the minimum value of all average angles between adjacent feature points and maxa denotes the maximum value.


## 3.1. Moving Speeds

Usually, the moving speed of a node is changed largely when its travel mode is switched [17]. The common travel modes include walking, riding bicycles, taking buses, driving cars, or taking the subway. As shown in Figure 2, suppose the node travels from the locationA to the locationB and the change point is the position where the node switches the travel mode from walking to taking the bus.Figure 2
Travel mode transition.To detect the change point caused by the switch among different travel modes, we define the moving speed difference as△i+1=vi,i+1-vi+1,i+2, where vi,i+1 represents the average speed on the line segment pipi+1. If △i+1 is larger than a given threshold, then pi+1 will be retained as a change point.Considering the fact that the speed changes are usually caused by the switches among different travel modes (Figure3), we take the standard deviation of moving speeds as the speed threshold, since the standard deviation can reflect the speed fluctuations. The speed threshold vth is expressed as(1)vth=∑i=1n-1vi,i+1-v¯2n-1,where v¯=∑i=1n-1vi,i+1/n-1; i.e., v¯ denotes the average speed in a trajectory.Figure 3
Speed change.


## 3.2. Stop Points

Another fact is that the nodes are possible to stay around some locations for a long period, e.g., waiting for the bus, having a dinner at a restaurant, resting in a leisure area, or shopping at a mall, and these locations can be taken as stop points. There are two types of stop points [18–20]: (a) the position-invariant stop points: such as theSP1 in Figure 4, which is determined according to the preset staying period; (b) the position-offset stop points: the node moves around a position for a preset period, such as theSP2 in Figure 4.Figure 4
Two types of stop points.In previous works, the stay points are detected according to the distance threshold and the time threshold, i.e., the distance between an anchor point and its successors is judged whether it is larger than the distance threshold, and then the time span between the anchor point and the last successor is measured. If the time span is larger than the time threshold, a stay point is determined.Notice that the stop point cannot be extracted when there is a round-trip path. As illustrated in Figure5, a customer (node) visits a convenience store from pi and then walks along the direction pipj→. Assume the distance dij between pi and pj is larger than the distance threshold, while the time duration of the node traveling from pi to pj-1 is also larger than the time threshold, and hence the average coordinate of all points from pi to pj-1 can be denoted by the stop point, which actually leads to the extraction of a false stop point.Figure 5
A false stop point.In addition, this process may fail to accurately detect the stop points due to the false position of the start point; as shown in Figure6, if p1 is taken as a start point mistakenly, then a false stop point is extracted.Figure 6
A false stop point.Actually, the setting of the distance threshold will affect the detection accuracy of stop points. If a smaller distance threshold is set (e.g., 10m), a smaller portion of points located within the ranges of stay points is not detected, as shown in Figure7(a), and p6 and p7 are not detected. If a large distance threshold is set (e.g., 100m), the points not falling into within range of stay point are also detected, as shown in Figure 7(b); p6, p7, and p8 can be detected.Figure 7
Two cases of distance threshold settings: (a) a smaller distance threshold and (b) a larger distance threshold.
(a) (b)Furthermore, the time threshold is related to the number of stay points, and a smaller time threshold will result in more stop points; on the contrary, less stop points are detected if a larger time threshold is set.To address the issues mentioned above, we observe that the speed of a node always becomes slow when it visits a location, and thus we propose a Stop Points Extraction Method based on the moving Speeds of nodes (SPEMS). In SPEMS, the stop points can be extracted through the following steps.Step 1.
Each pair of adjacent GPS pointspi, pi+1 is traversed, and the moving speed vi,i+1 is calculated.Step 2.
Ifvi,i+1 is equal to 0 or vi,i+1≤λv (λv denotes a speed threshold), then a backward search with the center pi+1 is performed to extract a point pL, such that the inequalities dist(pi+1,pk)≤r and dist(pi+1,pL-1)>r are satisfied, where r denotes a search radius threshold and k=i,i-1,…,L.Step 3.
A forward search is performed to extract a pointpR, such that the inequalities dist(pi+1,pk)≤r and dist(pi+1,pR+1)>r are satisfied, where k=i+2,i+3,…,R.Step 4.
If the time interval△t(pL,pR)≥δt (δt denotes the time threshold), then we take the intermediate point p⌊(L+R)/2⌋ as a stop point. Obviously, we remove the points from pL to pR except p⌊(L+R)/2⌋, and this mechanism can avoid these points being repeatedly detected.Figure8 gives an example of forward search and backward search, where pL is found by a backward search with the center pi+1 and pR is found by a forward search.Figure 8
Forward search and backward search.An example is given in Figure9, where we assume v5,6≥vth and hence we can find the points p2 and p10 with the center p6 through the backward search and the forward search, respectively. If △t(p2,p10)≥δt, we set p⌊(2+10)/2⌋ as the stop point; i.e., p6 is a stop point.Figure 9
Stop point extraction.The pseudocode of SPEMS is depicted in Algorithm1.Algorithm 1:SPEMS pseudocode.
Input: T R = p 1 , p 2 , … , p n , r , λ v , δ t. Output: SP. 1:i=1. 2:whilei<ndo 3:   j=i+1. 4:   Calculatevi,j. 5:ifvij==0 or vi,j≤δvthen 6:L=Backward-Search(TR,j,r). 7:R=Forward-Search(TR,j,r). 8:△t=pR.t-pL.t. 9:if△t≥δtthen 10:mid=(L+R)/2. 11:     AddTR[mid] to SP. 12:     Remove points frompL to pR except pmid. 13:i=L. 14:else 15:i=i+1. 16:end if 17:else 18:i=i+1. 19:end if 20:end while


## 3.3. Moving Directions

The changes of moving directions are concerned with the current travel modes; e.g., the moving direction will be changed more frequently when the nodes adopt the walking mode rather than taking vehicles.Besides, the traditional DP algorithm cannot maintain the shapes of the original trajectories very well in some special cases, such as the case shown in Figure10, where the point of the street corner is not taken as a feature point. The reason is that DP algorithm divides the trajectories on the basis of perpendicular Euclidean distance, and thus the points with large direction changes are easy to be ignored.Figure 10
An ignored point in DP algorithm.Therefore, we propose a DP algorithm based on Direction changes and Perpendicular Euclidean Distance (DPDPED). In DPDPED, the error measure is defined as(2)φ=θmax·distpk,pk′,i<k<j,where θmax=max⁡{θ1,θ2} and 0≤θmax≤π. θ1 represents the angle between pipj→ and pipk→, θ2 represents the angle between pipj→ and pkpj→, where pi and pj are two adjacent feature points. pk is a point on the line segment pipj→, and pk′ is the projection on pipj→. Essentially, DPDPED combines the maximum angle and the perpendicular Euclidean distance into the index of error measure, and the points ignored by DP can be found through detecting the direction changes of nodes. In this mechanism, since the value of φ is very sensitive to the direction changes, and hence the points with large direction changes can be found easily. As illustrated in Figure 11, a split point p6 divides the trajectory into two subtrajectories.Figure 11
Illustration of DPDPED algorithm.Algorithm2 gives the pseudocode of DPDPED.Algorithm 2:DPDPED pseudocode.
Input: T R = p 1 , p 2 , ⋯ , p n , F P , φ t h. Output: FP. 1:sindex=0. 2:eindex=len(TR)-1. 3:ifsindex<eindexthen 4:cindex=sindex+1. 5:φmax=0. 6:kindex=0. 7:whilecindex<eindexdo 8:φ=θmax⋅dist(pindex,pindex′). 9:ifφ≥φmaxthen 10:φmax=φ. 11:kindex=cindex. 12:end if 13:cindex=cindex+1. 14:end while 15:ifφmax≥φththen 16:FP.append(TR[kindex]). 17:DBDP(TR[sindex:kindex],FP,φth). 18:DBDP(TR[kindex:eindex],FP,φth). 19:end if 20:end if


## 3.4. Trajectory Partition Algorithm

In TPMF, the change points are first extracted based on the speed changes, and then SPEMS algorithm is applied to extract the stop points. The extracted change points and stop points are treated as feature points. Finally, DPDPED is executed to simplify the subtrajectories between the adjacent feature points. Figure12 illustrates our trajectory partition process, where two change points are found by the detection of speed changes in Figure 12(a), and then two stops points are extracted by our SPEMS in Figure 12(b), finally, a point with direction change largely is found by DPDPED in Figure 12(c). The pseudocode of TPMF is depicted in Algorithm 3.Algorithm 3:TPMF pseudocode.
Input: T R = p 1 , p 2 , … , p n , r , δ t , λ v, the maximum angle thresholdθth, the distance threshold dth. Output:Feature Point Set FP. 1:i=1,k=0,FP=Φ. 2:FP←(FP∪p1), FP←(FP∪pn). 3:vth← Calculate standard deviation of speed in TR. 4:whilei≤n-2do 5:ifvi,i+1-vi+1,i+2≥vththen 6:FP←(FP∪pi+1). 7:end if 8:i=i+1. 9:end while 10:SP=SPEMS(TR,r,δv,δt). 11:FP←(FP∪SP). 12:  Sort the points ofFP in a chronological order. 13:FP1←(FP). 14:Index← find the indexes of feature points in FP1 inTR. 15:φth=θth⋅dth. 16:whilek<len(Index)-1do 17:DPDPED(TR[Index[k]:Index[k+1]],FP,φth).  18:k=k+1. 19:end while 20:  Remove duplicate points fromFP. 21:  Sort points inFP in a chronological order.Figure 12
Trajectory partition process.
(a)
Discover change points (b)
Discover stop points (c)
Discover points with direction change largelyAccording to the steps of TPMF, the time complexity is calculated as follows:(3)n+n+FP1-1n-Np-FP1FP1+122=2n+FP1-14FP12×2n-2Np-FP12,where Np is the number of removed points within the ranges of stop points and the expression of Np is given by(4)Np=∑i=1SPNumSPi,SPi∈SP,where SPi denotes the i-th stop point in SP and Num(SPi) denotes the number of points around the stay point SPi. ⌊n-Np-|FP1|/|FP1|+1/2⌋ denotes the average number of points between adjacent feature points. Therefore, the time complexity of TPMF is written as O⌊|FP1|-1/4|FP1|2×(2n-2Np-|FP1|)2⌋. When n is large enough, we have (5)n<FP1-14FP12×2n-2Np-FP12<n2


## 3.5. Trajectory Partition Error

Two metrics have been applied to measure the performance of trajectories partition methods: (a) simplification rate refers to the ratio of removed points to original points and (b) running time represents the execution time of trajectory partition method to measure the time complexity. Besides, the error between the simplified trajectories and the original trajectories should also be measured, and we define the metric of trajectory partition error, as shown in Figure 13, pi and pj are two adjacent feature points, and the average perpendicular Euclidean distance and the average angle are used to evaluate the error of trajectory partition results.Figure 13
Trajectory partition error.The expression of average perpendicular Euclidean distance is given by(6)avgp=∑i=FIα,j=FIα+1∑k=i+1j-1distpk,pk′n-s,α=0,1,…,FI-1,where FI denotes the subscript set of feature points, dist(pk,pk′) represents the perpendicular Euclidean distance between pk and pk′, ands denotes the number of points in FP.The expression of average angle is written as(7)avga=∑i=FIα,j=FIα+1max⁡θi,j+max⁡θj,i/2s-1α=0,1,…,FI-1,where θi,j=θi,i+1,θi,i+2,…,θi,k,…,θi,j-1 represents the set of angles between pipk→ and pipj→ and θj,i=θj,j-1,θj,j-2,…,θj,k,…,θj,i+1 represents the set of angles between pjpk→ and pjpi→.Furthermore, the Min-Max standardization is used to standardizeavgp and avga, respectively. Finally, we define the trajectory partition error ε=w1·avgp∗+w2·avga∗, where w1 and w2 are the weights reflecting the impacts of average perpendicular Euclidean distance and average angle on the trajectory partition. Then, the expressions of avgp∗ are written as(8)avgp∗=avgp-minpmaxp-minp,where minp denotes the minimum value of all the perpendicular Euclidean distances from the points between adjacent feature points to the simplified line segment. Likewise, maxp represents the maximum value.The expressions ofavga∗ are written as(9)avga∗=avga-minamaxa-mina,where mina denotes the minimum value of all average angles between adjacent feature points and maxa denotes the maximum value.


## 4. Simulations

In this section, we present an extensive simulation study of our TPMF. We conduct several simulations to evaluate TPMF on theGeolife dataset. All simulations are run on a PC equipped with Windows 7, 3.20GHz CPU and 4 GB memory. The trajectory partition methods are realized by Python language.


### 4.1. Dataset

GPS trajectory dataset is cited from (Microsoft Research Asia)Geolife [21] project, which collects the trajectories of 182 users (nodes) during five years (from April 2007 to August 2012). These trajectories are recorded by different GPS loggers and GPS phones and have a variety of sampling rates. 91.5 percents of the trajectories are logged in a dense representation, e.g., every 1~5 seconds or every 5~10 meters per point.


### 4.2. Parameter Settings

The trajectory data used in our simulations includes 171 trajectories, each of which contains tracks of one node every day. Firstly, we select six trajectories from the 171 trajectories to determine the parameter values. The details of each trajectory are shown in Table1.Table 1
Trajectory details.
TraID Date Start End Raw Points 1 2008-10-23 02:53:04 11:11:12 908 5 2008-10-28 00:38:26 05:03:42 1477 9 2008-11-03 23:21:53 03:31:08 2231 11 2008-11-11 00:17:04 02:35:54 681 49 2009-04-05 05:19:38 14:00:18 4004 161 2009-06-28 00:52:29 13:45:56 5848To observe the impacts ofδt and r on the number of stop points, four trajectories are selected for this simulation. Figure 14 shows the number of stop points under different search radius and time threshold.Figure 14
Number of stop points vs. time threshold and search radius threshold.
(a)
♯tra1 (b)
♯tra5 (c)
♯tra9 (d)
♯tra49From Figures14(a)–14(d), we can observe that the curves decrease rapidly when δt increases from 60 s to 120 s, which is attributed to the fact in TPMF more points are treated as the stop points when a smaller time threshold δt is set. When δt≥120 s, the curves descend slowly, especially when 180 s≤δt≤300 s the curves remain almost stable, which indicates that the fluctuation of the number of stop points is very slight, and the reason is that the range of 180 s≤δt≤300 s is close to the duration that the node stays at the stop points, and thus the value of δt should be selected from the interval [180,300] s. In addition, when r=10 m or r=15 m, the number of extracted stop points is not large enough, compared with the number of original points, and thus we set r=20 m. In Figures 14(a) and 14(d), the number of stop points does not change obviously when 180 s≤δt≤240 s. Similarly, Figures 14(b) and 14(c) also illustrate that the number of stop points is not changed when 240 s≤δt≤300 s, and thus we set δt=240 s.As shown in Figure15, the number of stop points remains unchanged when 0.6 m/s≤λv≤0.7 m/s, which is attributed to the fact that the speed falling into the interval of 0.6 m/s≤λv≤0.7 m/s is very close to the moving speed of the node, and we can set λv=0.6 m/s. Since the trajectory partition error increases (or decreases) as dth or θth increases (or decreases), there are no suitable values can be obtained. Thus, we set dth and θth smaller in our simulations. Without loss of generality, we assume the impacts of average perpendicular Euclidean distance and average angle be equivalent, and each of w1 and w2 is set to 0.5. Actually, w1 and w2 are adjustable weights, and the values of w1 and w2 can be easily adjusted for different applications or different trajectory datasets. The main simulation parameters are provided in Table 2.Table 2
Simulation parameters.
Parameters Description Values δt Time threshold 240s r Search radius threshold 20m λv Speed threshold 0.6m/s dth Distance threshold 10m θth Maximum angle threshold π/6 w1 Weight ofavgp∗ 1/2 w2 Weight ofavga∗ 1/2Figure 15
Number of stop points vs. moving speed threshold.


### 4.3. Comparisons of Trajectory Partition Methods

Seven algorithms are compared in this simulation. Our proposed algorithm TPMF is compared with other six algorithms (DP, MDL, SQUISH, SQUISH-E, BQS, and OPERB) in terms of simplification rate, running time, and trajectory partition error. The parameter settings of other algorithms as given in Table3, where PED represents the Perpendicular Euclidean Distance and SED represents the Synchronized Euclidean Distance. The table term “yes/no” indicates whether the algorithm uses PED or SED. We first partition all the trajectories of one node, and the simulation results are reported in Figure 16.Table 3
Parameter settings of other algorithms.
Algorithms PED SED λ μ DP yes no - 10m MDL no no - - SQUISH no yes 5 - SQUISH-E no yes 5 10m BQS yes no - 10m OPERB yes no - 10mFigure 16
Comparisons of Different Trajectory Partition Algorithms (one node).
(a)
Simplification rate (b)
Running time (c)
Trajectory partition errorAs shown in Figure16(a), with regard to the simplification rate, OPERB outperforms other algorithms and the curves of TPMF and BQS higher than those of DP, MDL, SQUISH, and SQUISH-E. Particularly, MDL always achieves the lowest simplification rates. As illustrated in Figure 16(b), the running time of MDL is much longer than other algorithms. In Figure 16(c), MDL outperforms other algorithms in terms of trajectory partition error.To observe the impacts of the number of trajectories, we select 10 nodes from the dataset, and the trajectory details are shown in Table4. The simulation results are given in Figure 17.Table 4
Trajectory detail of nodes.
Node ID Original trajectories Original points Time periods 1 171 173870 2008-10-23~2009-07-05 2 71 108607 2008-10-23~2008-12-14 3 175 248215 2008-10-23~2009-03-22 4 322 485226 2008-10-23~2009-07-05 5 395 439397 2008-10-23~2009-07-29 6 86 109046 2008-10-24~2009-03-19 7 28 31830 2008-10-23~2008-12-11 8 54 85531 2008-10-25~2008-12-15 9 34 77908 2008-10-24~2008-12-12 10 49 84615 2008-10-23~2008-12-14Figure 17
Comparisons of Different Trajectory Partition Algorithms (ten nodes).
(a)
Simplification rate (b)
Running time (c)
Trajectory partition errorIn Figure17(a), with regard to the average simplification rate, OPERB is generally higher than other algorithms, and the simplification rate of OPERB is about 90%. the plots of TPMF and BQS are close to each other, and their simplification rates fall into the interval from 85% to 90%. The plot of DP is slightly lower than those of TPMF and BQS. Especially, SQUISH and SQUISH-E remain stable due to the constraint of a target simplification rate 80%, and MDL obtains the lowest simplification rates among all algorithms.Figure17(b) illustrates that OPERB executes faster than other algorithms due to its one-pass scanning mechanism, while the running time of MDL is much longer than others. Besides, TPMF consumes less running time than those of DP, MDL, SQUISH, SQUISH-E, and BQS. This is attributed to the fact that TPMF partitions the trajectories according to the extracted feature points (change points and stop points), and hence the number of computations is significantly reduced.In Figure17(c), the average error of TPMF is always smaller than those of DP, BQS, SQUISH-E and OPERB and is close to that of SQUISH. MDL achieves the lowest average error, and this is because MDL partitions the trajectories approximately, and it retains the most points and preserves the trajectory shapes as much as possible, which produces a smaller trajectory partition error along with a lower simplification rate. Notice that OPERB obtains the largest average error along with the highest simplification rate as depicted in Figure 17(a).Therefore, TPMF makes a preferable tradeoff between the simplification rate and the trajectory partition error. TPMF can reserve the most valuable feature points, which makes the redundant points be removed.


## 4.1. Dataset

GPS trajectory dataset is cited from (Microsoft Research Asia)Geolife [21] project, which collects the trajectories of 182 users (nodes) during five years (from April 2007 to August 2012). These trajectories are recorded by different GPS loggers and GPS phones and have a variety of sampling rates. 91.5 percents of the trajectories are logged in a dense representation, e.g., every 1~5 seconds or every 5~10 meters per point.


## 4.2. Parameter Settings

The trajectory data used in our simulations includes 171 trajectories, each of which contains tracks of one node every day. Firstly, we select six trajectories from the 171 trajectories to determine the parameter values. The details of each trajectory are shown in Table1.Table 1
Trajectory details.
TraID Date Start End Raw Points 1 2008-10-23 02:53:04 11:11:12 908 5 2008-10-28 00:38:26 05:03:42 1477 9 2008-11-03 23:21:53 03:31:08 2231 11 2008-11-11 00:17:04 02:35:54 681 49 2009-04-05 05:19:38 14:00:18 4004 161 2009-06-28 00:52:29 13:45:56 5848To observe the impacts ofδt and r on the number of stop points, four trajectories are selected for this simulation. Figure 14 shows the number of stop points under different search radius and time threshold.Figure 14
Number of stop points vs. time threshold and search radius threshold.
(a)
♯tra1 (b)
♯tra5 (c)
♯tra9 (d)
♯tra49From Figures14(a)–14(d), we can observe that the curves decrease rapidly when δt increases from 60 s to 120 s, which is attributed to the fact in TPMF more points are treated as the stop points when a smaller time threshold δt is set. When δt≥120 s, the curves descend slowly, especially when 180 s≤δt≤300 s the curves remain almost stable, which indicates that the fluctuation of the number of stop points is very slight, and the reason is that the range of 180 s≤δt≤300 s is close to the duration that the node stays at the stop points, and thus the value of δt should be selected from the interval [180,300] s. In addition, when r=10 m or r=15 m, the number of extracted stop points is not large enough, compared with the number of original points, and thus we set r=20 m. In Figures 14(a) and 14(d), the number of stop points does not change obviously when 180 s≤δt≤240 s. Similarly, Figures 14(b) and 14(c) also illustrate that the number of stop points is not changed when 240 s≤δt≤300 s, and thus we set δt=240 s.As shown in Figure15, the number of stop points remains unchanged when 0.6 m/s≤λv≤0.7 m/s, which is attributed to the fact that the speed falling into the interval of 0.6 m/s≤λv≤0.7 m/s is very close to the moving speed of the node, and we can set λv=0.6 m/s. Since the trajectory partition error increases (or decreases) as dth or θth increases (or decreases), there are no suitable values can be obtained. Thus, we set dth and θth smaller in our simulations. Without loss of generality, we assume the impacts of average perpendicular Euclidean distance and average angle be equivalent, and each of w1 and w2 is set to 0.5. Actually, w1 and w2 are adjustable weights, and the values of w1 and w2 can be easily adjusted for different applications or different trajectory datasets. The main simulation parameters are provided in Table 2.Table 2
Simulation parameters.
Parameters Description Values δt Time threshold 240s r Search radius threshold 20m λv Speed threshold 0.6m/s dth Distance threshold 10m θth Maximum angle threshold π/6 w1 Weight ofavgp∗ 1/2 w2 Weight ofavga∗ 1/2Figure 15
Number of stop points vs. moving speed threshold.


## 4.3. Comparisons of Trajectory Partition Methods

Seven algorithms are compared in this simulation. Our proposed algorithm TPMF is compared with other six algorithms (DP, MDL, SQUISH, SQUISH-E, BQS, and OPERB) in terms of simplification rate, running time, and trajectory partition error. The parameter settings of other algorithms as given in Table3, where PED represents the Perpendicular Euclidean Distance and SED represents the Synchronized Euclidean Distance. The table term “yes/no” indicates whether the algorithm uses PED or SED. We first partition all the trajectories of one node, and the simulation results are reported in Figure 16.Table 3
Parameter settings of other algorithms.
Algorithms PED SED λ μ DP yes no - 10m MDL no no - - SQUISH no yes 5 - SQUISH-E no yes 5 10m BQS yes no - 10m OPERB yes no - 10mFigure 16
Comparisons of Different Trajectory Partition Algorithms (one node).
(a)
Simplification rate (b)
Running time (c)
Trajectory partition errorAs shown in Figure16(a), with regard to the simplification rate, OPERB outperforms other algorithms and the curves of TPMF and BQS higher than those of DP, MDL, SQUISH, and SQUISH-E. Particularly, MDL always achieves the lowest simplification rates. As illustrated in Figure 16(b), the running time of MDL is much longer than other algorithms. In Figure 16(c), MDL outperforms other algorithms in terms of trajectory partition error.To observe the impacts of the number of trajectories, we select 10 nodes from the dataset, and the trajectory details are shown in Table4. The simulation results are given in Figure 17.Table 4
Trajectory detail of nodes.
Node ID Original trajectories Original points Time periods 1 171 173870 2008-10-23~2009-07-05 2 71 108607 2008-10-23~2008-12-14 3 175 248215 2008-10-23~2009-03-22 4 322 485226 2008-10-23~2009-07-05 5 395 439397 2008-10-23~2009-07-29 6 86 109046 2008-10-24~2009-03-19 7 28 31830 2008-10-23~2008-12-11 8 54 85531 2008-10-25~2008-12-15 9 34 77908 2008-10-24~2008-12-12 10 49 84615 2008-10-23~2008-12-14Figure 17
Comparisons of Different Trajectory Partition Algorithms (ten nodes).
(a)
Simplification rate (b)
Running time (c)
Trajectory partition errorIn Figure17(a), with regard to the average simplification rate, OPERB is generally higher than other algorithms, and the simplification rate of OPERB is about 90%. the plots of TPMF and BQS are close to each other, and their simplification rates fall into the interval from 85% to 90%. The plot of DP is slightly lower than those of TPMF and BQS. Especially, SQUISH and SQUISH-E remain stable due to the constraint of a target simplification rate 80%, and MDL obtains the lowest simplification rates among all algorithms.Figure17(b) illustrates that OPERB executes faster than other algorithms due to its one-pass scanning mechanism, while the running time of MDL is much longer than others. Besides, TPMF consumes less running time than those of DP, MDL, SQUISH, SQUISH-E, and BQS. This is attributed to the fact that TPMF partitions the trajectories according to the extracted feature points (change points and stop points), and hence the number of computations is significantly reduced.In Figure17(c), the average error of TPMF is always smaller than those of DP, BQS, SQUISH-E and OPERB and is close to that of SQUISH. MDL achieves the lowest average error, and this is because MDL partitions the trajectories approximately, and it retains the most points and preserves the trajectory shapes as much as possible, which produces a smaller trajectory partition error along with a lower simplification rate. Notice that OPERB obtains the largest average error along with the highest simplification rate as depicted in Figure 17(a).Therefore, TPMF makes a preferable tradeoff between the simplification rate and the trajectory partition error. TPMF can reserve the most valuable feature points, which makes the redundant points be removed.


## 5. Conclusions

The trajectory partition is a primary procedure of trajectory data mining. The amount of movement trajectories is typically large, and the shapes of trajectories appear diversely in different applications. In this paper, a trajectory partition method based on combined movement features (moving speeds, stop points, and moving directions) is proposed. The outstanding advantage of our proposed method is that it takes into account the movement behaviors of nodes comprehensively, which can maintain the shape skeletons and movement features while massive redundant points are removed.Future research will focus on investigating a self-adaptive solution of setting the method parameters in TPMF, e.g., the values of parametersr, δt, and λv. In addition, a trajectory mining algorithm based on TPMF will be investigated to obtain the movement modes of nodes as well.



---

*Source: 7803293-2019-07-24.xml*