Unsupervised Abnormal Stop Detection for Long Distance Coaches with Low-Frequency GPS

How to determine the stop spots from the low-frequency GPS: In practice, there exists large amount of low-sampling-rate (e.g., one point every 2 minutes) GPS trajectories for a coach. They are generated in the scenarios where saving of energy cost and communication cost are desired. Low-frequency GPS typically refers to send a GPS coordinate per $30$ seconds in China (see Table I for more details). In order to capture the abnormal stop spots, we have to first obtain the possible stop spots during the travel service of a coach. However, a $30$ seconds interval is too long to directly judge whether a coach has stopped or not.

Discover the abnormal stop spots: A coach would have various stop behaviors due to the changes of road conditions and different driving behaviors [6]. The abnormal stop spots are the candidate spots where the coach drivers would like to pick up passengers. Therefore, the key challenge of this research is to effectively discover the abnormal stop spots in an unsupervised approach under the complex traffic conditions [7].

In this paper, we propose a method that aims to resolve the above challenges in an unsupervised approach. Rather than seeking the stop spots by manually screening the physical constraints that conventionally pick up passengers, we instead of directly discover the abnormal stop spots by assuming that the complex traffic system follows the low rank constraints [8]. That is, we cast our quest for “abnormal” stops as the matrix decomposition problem, in which the low rank models the normal stops, while a sparsity residual term represents the abnormal ones.

This paper makes several significant contributions to the field of the long range coach industry management, as outlined below:

Introduction to the IPPs Problem. This study is pioneering in exploring the discovery of the spots of the IPPs activity for long range coaches, only relying on the low-frequency GPS. We approach this challenge as an unsupervised problem, achieving the effective solutions for identifying the candidate spots where the IPPs activities tend to occur.

Discovery of the possible stop spots from the low-frequency GPS: This paper addresses the problem of the low-frequency GPS in particular. We propose a method to identify the possible stop spots by simply assuming that the speed of a coach changes linearly. These candidate stop spots are instrumental in characterizing the stop spots from diverse coach drivers.

Determining anomalous stop spots: We assume that the abnormal stop spots are sparse, compared with the normal ones. Besides, it is impossible for long range coaches to illegally stop at some special spots (e.g., main road). Therefore, we introduced the structured sparsity [9] and the low rank constraint [10] for detecting abnormal stop spots. Our findings reveal the proposed method as the superior method for detecting the spots for the IPPs activities.

The varying natural environments and traffic conditions [11] [12] [13] leverages GPS to address multiple issues related to traffic safety and efficiency. For instance, by monitoring the movement patterns and speed variations of buses, abnormal driving behaviors can be detected, e.g., abnormal driving behaviors [14] [15], over speeding [16], the deviation from the predetermined route [17] [18] [19], and black spots identification [20]. In a summary, discovering the stop spots for the IPPs activities barely been investigated.

Besides, both the video and audio play a pivotal role  [21] to identify abnormality in human behaviors. Compared with GPS, either video or audio directly reflects the human behaviors, e.g., fighting in surveillance scenes [22]. However, to our best knowledge, how to leverage video or audio to detect the IPPs activity is still an open problem.

Low frequency GPS are application-logged data from GPS embedded equipments on diverse vehicles, e.g., trucks, buses. Different applications enforce diverse priors to handle the information loss caused by the low frequency. For instance, either the connection between the shortest path and the vehicle trajectory [23] or the spatial and the temporal information [24] [25] is used as a prior to tackle the low-frequency GPS for the map matching problem. As a comparison, we assume that a vehicle would follow a linearly changed velocity as a prior to discover the possible stop behavior.

Although transportation in a city is a mixture of the multiple factors, (e.g., the influence of the road conditions, traffic conditions, and climate and environment), recent research has discovered that the spatio-temporal data from the transportation problem has the low-rank structure [7] [26]. Consequently, [27] [28] proposed a non-convex low-rank model to address missing data problem. Non-negative matrix (and tensor) factorization has been widely used for network traffic analysis [29]. [30] proposed a method based on sparse non-negative matrix factorization to identify the periodic patterns in traffic behavior. In this paper, we strip the abnormal stop spots from the abnormal ones by the low rank and the sparse decomposition.

The dataset comprising coach GPS records were sourced from the Beijing transportation information center. Specifically, each coach is equipped with a GPS enabled device that transmits real-time but low frequent data including longitude, latitude, time stamps, instantaneous velocity, and engine state (see Table I). All items are relayed to a data center via telecommunication networks.

Adherence to local coach regulations is mandatory, requiring: 1) connectivity of GPS signals; and 2) accurate GPS time stamps. Non-compliance, indicated by erroneous data transmission, prompts law enforcement to notify coach companies for corrective actions.

Obviously, LF GPS makes the location uncertainty increase as the sampling rate reduces. Consequently, judging whether a coach has stopped or not from LF GPS is very difficult due to the long time intervals. If a coach is assumed to linearly change speed, we have two cases which indicate that a coach has been stopped in 30 seconds as in Fig. 2.

Concretely, given two consecutive GPS points with the velocity $v_{i}$ and $v_{i+1}$, the time interval $30(\text{seconds})$ between the consecutive GPS points, and $v_{m}$ is the minimum velocity between the two consecutive GPS points, a coach would have a stop behavior as follows:

Case 1: when both the minimal velocity $v_{m}$ is equal to 0 and the stop duration $\Delta t=0$, we have:

where $t$ is the time a coach reaches to the minimum speed $v_{m}$, and $d$ the distance between the two GPS points (see Fig. 2(a)). If the minimal velocity in Eq. (1), $v_{m}$ is equal to 0, (i.e., $v_{m}=0$), we have the following equation:

Therefore, by applying the constrains $t>0$, we have the following inequality as follows:

Case 2: when the minimal velocity $v_{m}=0$ and the stop duration $\Delta t>0$, we could assume that a coach has stopped at the time $t$ as follows (see Fig. 2 (b), (c) ):

The key problem to judging whether a coach has stopped or not is: find the conditions that satisfy the non-negativity, i.e., $t>0$ and $\Delta t>0$.

Therefore, (4) is re-written as follows:

To remove the variable $t$, we have the following sub-cases:

Sub-case 2.1: $v_{i+1}>v_{i}$: Given $v_{i+1}>v_{i}$, we have $\frac{v_{i}}{v_{i+1}}<1$.Consequently, (6) is re-written as follows:

Eq. (7) give the low bound of the stop duration $\Delta t$. That is, if the low bound in Eq. (7) is greater than 0, a stop has occurred between the two GPS points.

Sub-case 2.2: $v_{i+1}\leq v_{i}$: Given $v_{i+1}\leq v_{i}$, we have $\frac{v_{i}\times t}{v_{i+1}}-t\geq 0$. Consequently, we simplify drop the term $\frac{v_{i}\times t}{v_{i+1}}-t$ in  (4) as follows:

Ideally, we expect to precisely discover where a IPP activity occurs. Based on the first Markov assumption in traffic [31] [32], we adaptively segment the route into fine-grained road segments which help law enforcers precisely locate the IPP spots.

In this paper, we uniformly segment a travel line of a coach into the road segments the fixed length $D$. The estimated stop time $\Delta t$ in Alg. 1 were assigned to the corresponding road segments. Concretely, if there is are $N$ stop time $\Delta t_{i,s}$, $(s=1,2,...,S)$ of a coach in the $i$-th road segment during one day, we summarize the stop duration of a coach in the $i$-th segment during one day as follows:

where $\bm{R}\in\mathbb{R}^{M\times N}$ is the stop duration matrix, $M$ is the number of the road segments, $i=1,2,...,M$. $N$ is the total number of stop durations of each bus in each day after combining the stop durations of the same coach on the same day according to Eq. (9), $j=1,2,...,N$.

Dealing with location inaccuracy: In many cases, the location information may be miss-located due to the blocked signal transmission. Therefore, a smooth mechanism is preferred over the stop duration $\Delta t_{i,j}$ between the $i$-th interval and $t+1$-th one. As shown in Fig.3, a simple and yet reasonable approach uses linear interpolation to smooth the stop duration $\Delta t_{i,j}$ as follows:

where $D_{i,j}$ is the distance from the stop spot of a trajectory to the end point of the $i$-th road segment.

In order to strip the Abnormal Stop Spots (ASSs) from the matrix $\bm{R}$, we introduce the stop type matrix $\bm{I}\in\mathbb{R}^{M\times N}$, where $\bm{I}_{ij}\in\{0,1\}$, in which $0$ means the abnormal stop, and $1$ indicates the normal stop. Consequently, striping the abnormal stops from the normal ones is modeled as follows:

where the operation $\odot$ is the element-wise multiplication between two matrices, $\|\cdot\|_{1}$ is the $L_{1}$ norm, $\|\cdot\|_{2,1}$ is the group sparsity, $\|\cdot\|_{*}$ is the nuclear norm, $\lambda(\lambda>0)$ and $\beta(\beta>0)$ are the hyper-parameters. In Eq. (11), we relaxes the 0-1 programming of $\bm{I}$.

Eq. (11) assumes that the stop duration matrix $\bm{R}$ is decomposed into a low rank matrix $\bm{\Theta}=\bm{R}\odot\bm{I}$, and a mixture of the sparse matrix $\bm{E}$ and column-sparse matrix $\bm{W}$. Motivated by [7], the matrix $\bm{\Theta}$ in Eq. (11) represents the normal stop spots, and the sparse matrix $\bm{E}$ indicates the abnormal stop spots. Therefore, the column-sparse $\|\cdot\|_{2,1}$ models that some road segments are impossible to be ASSs, while the sparse $\|\cdot\|_{1}$ follows that the ASSs should be sparse compared to the normal stop behaviors of coaches. In summary, Eq. (11) assumes that the ASSs are sparely occurred in some special road segments. Therefore, a larger value of $\bm{E}_{ij}$ indicates a higher ASS for the $i$-th road segment.

We use the Alternating Direction Method of Multipliers (ADMM) to solve Eq. (11) as follows:

where $\bm{Y}_{1}\in\mathbb{R}^{M\times N}$, $\bm{Y}_{2}\in\mathbb{R}^{M\times N}$, and $\bm{Y}_{3}\in\mathbb{R}^{M\times N}$ are the Lagrange multiplier matrices, and $\rho$ ($\rho>0$) is the penalty factor. The iterative alternating direction method is used to solve the Lagrangian function in Eq. (12).

Update the matrix $\bm{E}$: When other variables are fixed, the subproblem w.r.t. $\bm{E}$ is as follows:

which can be solved by the shrinkage method as follows:

in which the shrinkage factor ${S}_{\alpha}(Z)$ is defined as follows:

Update the matrix $\bm{\Theta}$: When other variables are fixed, the subproblem w.r.t. $\bm{\Theta}$ is as follows:

which can be solved by the singular value threshold method. More specially, let $\bm{C}=\bm{U}\bm{\Sigma}\bm{V}^{\top}$ be the Singular Value Decomposition (SVD) of $\bm{C}$. Then, for ${T_{\lambda}}(\bm{C})=\bm{U}{\bm{\Sigma}_{\lambda}}{\bm{V}^{T}}$, we have:

where ${\bm{\Sigma}_{\lambda}}$ is diagonal with ${({\bm{\Sigma}_{\lambda}})_{ii}}=\max(0,{\bm{\Sigma}_{ii}}-\lambda)$. By the SVD threshold method [33], the solution for the $\bm{\Theta}$ is as fallows:

Update the matrix $\bm{I}$: When other variables are fixed, the subproblem w.r.t. $\bm{I}$ is as follows:

Then $\bm{I}$ is solved as follows:

where the operation $/$ represents the element-wise division between two matrices.

Update the matrix $\bm{W}$: When other variables are fixed, the subproblem w.r.t. $\bm{W}$ is as follows:

where $\|\bm{W}\|_{2,1}=\sum\limits_{i=1}^{n}{\sqrt{\sum\limits_{j=1}^{m}{\bm{W}_{ij}^{2}}}}=\sum\limits_{i=1}^{n}{{{\left\|{{\bm{W}_{i}}}\right\|}_{2}}}$. We can update the $i$-th column of the $\bm{W}$ matrix as follows:

where $\alpha=\beta/\rho$, $\mathbf{Q}=\bm{E}-\frac{{\bm{Y}}_{3}}{\rho}$, $\mathbf{Q}_{i}$ is the $i$-th column of the matrix $\bm{Q}$.

Update the matrix $\bm{Y}$: Update the Lagrange multipliers ${\bm{Y}}_{1}$, ${\bm{Y}}_{2}$ and ${\bm{Y}}_{3}$ are as follows:

During training, we update $\rho\leftarrow\rho\cdot\mu$, where $\mu>1$. In this paper, we initialized $\rho$ to 1 and set $\mu$ to 1.2. The ADMM process is summarized in Alg. 2.

Table III compared the SOTA method in Section IV-B2 with our method. Table III shows that proposed method achieved the best AUC and AP values. The results indicate that our proposed method can effectively improve the accuracy of capturing abnormal stop spots. Besides, the superior performances of our method uncovered three observations as follows:

• •

  Group sparsity is very necessary to the ASS task. Our method significantly outperforms WST by 4.76% and 2.39% in terms of AUC and AP, respectively. This indicates that the group sparsity in Eq. (11) is very important to discover ASSs. The group sparsity empowers the model to remove the impossible stop spots.

• •

  Stripping abnormal stop duration from the stop duration is necessary. Our method significantly outperforms WSA, for instance, AUC and AP of the WSA are 23.81% and 18.62% lower than that of the proposed method, respectively. This means that there are many normal stop duration are mixed in the $\bm{R}$ matrix builded from strategy in WSA. Moreover, the significant performance gap also verifies that the low rank decomposition efficiently strip the abnormal stop duration form these normal ones.

• •

  Many abnormal stop behaviors barely been discovered by the instantaneous speed. Our method significantly outperforms UIS, for instance, AUC and AP of UIS are 23.07% and 28.78% lower than that of the proposed method, respectively. Because some abnormal stop would happen in 30 seconds. The comparisons between UIS and our method verify the effectiveness of the necessary and effectiveness of extracting candidate stop spots from low-frequency GPS in Section III-B.

Intuitively, the limited number of law enforcers should be dynamically allocated to the spots where coaches frequently stop for the IPPs activity. In terms of our approach, the AST of the $\bm{E}$ matrix reflects the possibility and the duration of the IPPs activity in a road segment. Except these well-understood spots (i.e., intercity bus stations, railway station, airports, and centralized business areas), the proposed method could effectively discover some spots which have the high probability to occur the IPPs activity. For instance, Fig. 8 illustrated three street-view of the road segments (i.e.,#156, #157, #38 in Fig. 5(a)) with the top-3 largest AST value. Note that #38, #157 road segments are the ground truth; while # 156 road segment is the IPPs spot discovered by our method. Specially, Figs. 8(a) and 8(b) shown that the stop spot is located near a highway toll station, facilitating coaches pick up passengers who have the long range travel demand. Besides, there is a bus stop which makes it convenient for shuffling passengers by buses. Moreover, several intersections provide a space for coaches to pick up passengers. For Fig. 8(c), the street-view images show that the stop spot is near an bus stop, subway station and the train station, which help coach drivers to pick up passengers. Because this area has a high probability to pick up the passengers with the long range travel demand. Additionally, there is a long side road which supplies a convenience for coaches to pull over.