{'fraction_non_alphanumeric': 0.027815376285868977, 'fraction_numerical': 0.009102598808879264, 'mean_word_length': 4.744023323615161, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Predicting passenger origin-destination in online taxi-hailing systems

Because of transportation planning, traffic management and dispatch optimization importance, the passenger origin-destination prediction has become one of the most important requirements for intelligent transportation systems management. In this paper, we propose a model to predict the origin and destination of travels which will occur in the next specified time window. In order to extract meaningful travel flows we use K-means clustering in four-dimensional space with maximum cluster size limitation for origin and destination. Because of large number of clusters, we use non-negative matrix factorization to decrease the number of travel clusters. We also use a stacked recurrent neural network model to predict travels count in each cluster. Comparing our results with other existing models show that our proposed model has 5-7% lower mean absolute percentage error (MAPE) for 1-hour time window, and 14% lower MAPE for 30-minute time window.


Introduction
A notable number of online taxi travels data are generated during daily trips. These data include valuable information about time, origin and destination of users travels which can be used to extract people travels pattern to have precise transportation planning and management strategies. Passenger origin-destination (OD) prediction has become one of the most important requirements for intelligent transportation systems management. In particular, it will help real-time ride-sharing systems to have accurate information about the number of travels and their origin and destination for the next time window to offer a fair price to the ride requesters. It is common between ride-sharing applications to offer the travel price before requesting and ride matching.
In this paper, we propose a point of view for travels clustering using K-means algorithm in four-dimensional space. Using a two-dimensional grid-based clustering might split hotspots with high input and output traffic to meaningless pieces and decrease the clusters quality. In other words since two-dimensional clustering pairs origin and destination hotspots after the clustering, it results in a large number of travel flow clusters with low quality. In contrast to the aforementioned techniques, four-dimensional clustering is able to extract meaningful and high-quality clusters of travel flows in fewer number by putting origin and destination points together during the clustering. We work on passenger trip data of Tap30.org, one of the largest taxi hailing companies in Iran. Since the number of extracted clusters is substantial, the model training requires a large amount of processing resources. Thus we use non-negative matrix factorization (NMF) [10,15] to decrease the size of the OD vectors. Methods such as principal component analysis (PCA) cannot perform as well as NMF algorithm, because the negative values in the coefficient matrix disobey the initial physical meaning and further disturb the accuracy of prediction [25]. We also propose a stacked recurrent neural networks model which consists of a non-linear supervised feature extraction part and a linear regression part. Non-linear supervised feature extraction part of this model is able to extract some features with linear relation with OD vectors of the next time interval. Linear regression part of the model uses the extracted features to estimate OD vectors for the next time interval. Besides the OD vectors of previous time intervals, we also add weather and time features to the input vectors in order to increase the prediction accuracy. We investigate the model prediction ability using simple recurrent cell [11], long short term memory (LSTM) [20] and gated recurrent unit (GRU) [8] as three different types of the recurrent neural networks cells for the non-linear supervised feature extraction part. The GRU cell shows powerful prediction ability for short time window. We also compare the proposed model with several existing models including NMF-vector autoregression (NMF-VAR) [25], multi-layered perceptron (MLP), and support vector machine (SVM) [28]. Our evaluation shows that the proposed model achieves a lower MAPE in comparison to existing models.
The rest of the paper is organized as follows. A review of the related work is provided in Section 2. Three types of travels flow clustering are explained in Section 3. Section 4 discusses our approach to OD prediction. Experimental results are detailed and presented in Section 5. And finally Section 6 concludes the main results of the paper.

Related Work
Many of the recent related work proposed models to estimate the OD matrix. Each entry of the OD matrix is the number of travels between pairs of predefined zones for a specified time interval. For example Toque et al. [33] proposed a model for public transportation OD matrix prediction. For public transportation like bus and subway, it is clear where the bus stops and subway stations are located, so there is no need for preprocessing to find out hotspots, but solving this problem for online taxi-hailing systems is more challenging because users can request a taxi from/to any arbitrary point on map. Also for online taxi-hailing systems, the size of the OD matrix is much larger than the public transportation OD matrix, thus model training requires larger processing resources. Toque et al. showed that LSTM neural networks have acceptable prediction power and can predict the number of travels between origin and destination hotspots for 15-minute time intervals with a suitable error rate. Li et al. [25] proposed a hybrid algorithm for estimating OD flows. In the first phase, they use the NMF algorithm to overcome the big size of the OD matrix. In the second phase, the coefficient matrix of the next time window is estimated based on the previous time series coefficient matrices extracted by the NMF algorithm using vector autoregressive (VAR) model. The VAR model is not able to extract non-linear relations between the coefficient matrices. Reddy et al. [27] proposed a flow-dependent assignment algorithm based on fuzzy inference for generating the relative contributions of the OD elements toward the link volumes and a recursive methodology for the OD estimation. Ying et al. [35] proposed a method on the basis of the polynomial trend model and the Kalman filtering theory. They showed that the proposed model outperforms traditional methods. Tanaka et al. [30] proposed a convex quadratic optimization model to estimate OD matrices of a bus line passengers. OD matrix of a bus line is small and because of specific locations of bus stops, there is no need for clustering techniques to find origin and destination hotspots or noticeable traffic flows. Zhang et al. [37] proposed a deep convolution-based neural network model to estimate inflow and outflow of grid-based map segments. They also could increase the estimation power of the model using external features such as weather conditions and events in addition to spatial and temporal features. Grid-based clustering may break meaningful origin and destination hotspots into several zones and result in a large number of travel flows. Also traffic flow between an origin and destination hotspot is converted to a sequence of inflow and outflow of zones which makes it necessary to have information about the routes which makes the model slower and more complex. Another approach for solving such problems is statistical methods. Despite previous models which were trained based on observed OD matrices to estimate next time interval OD matrix, statistical models estimate parameters of OD matrix distribution. Li et al. [24] proposed a Bayesian statistical model to estimate traffic flows on the links between the city zones. A path from an origin to a destination is a sequence of nodes connected by these links. They assumed that the OD matrix has multivariate Poisson distribution and used the expectation maximization (EM) algorithm to estimate the distribution parameters. For this type of map zoning approach, as mentioned earlier, we need travel routes. In some statistical models, it is assumed that each OD flow has a Poisson distribution independent from the other OD flows distribution [17,29,32,34]. Such an assumption may impose some biases on the estimation.
One of the most important phases of solutions to such problems is preprocessing and aggregation. An appropriate aggregation method helps to extract high quality travel patterns, which helps the prediction model to predict travels easily and more accurately. To obtain meaningful patterns, Yue et al. [36] used a clustering approach to group spatiotemporally similar pick-up and drop-off points to extract time-dependent attractive areas and movement patterns from taxi trajectory data. For our problem since the number of travel flows is gigantic, adding time as a 5th dimension results in more clusters with fewer points. Clusters with few members may have random behavior and this hinders the prediction. Jahnke et al. [21] proposed density-based spatial clustering of applications with noise (DBSCAN) [14] algorithm to detect high-intensity gathering of origin and destination zones all over the city to help visual analysis of traveling behavior. Pairing origin and destination zones after two-dimensional clustering enlarges the OD matrix and decreases the meaning and quality of OD flows. But four-dimensional clustering returns fewer travel flow clusters by putting origins and destinations of travels together during the clustering.

Grid-based clustering
As declared before, in online taxi-hailing systems users can request taxis to travel between two arbitrary map points, thus despite the public transportation, it is not clear where the origin and destination hotspots are and it is required to do some preprocessing to find pickup and drop off hotspots and divide the city map to zones based on these hotspots. A simple and easy way to cluster the origin and destination points is used by Zhang et al. [38] in order to semantic mining of taxi flows, and Calabrese et al. [7] for estimating the OD flows using users mobile phone location data. This method divides the city map to equal squares as depicted in Fig. 1. The main problem of this method is that it is possible that a hotspot like a hospital, a subway station or a shopping center gets split between multiple squares as shown in Fig. 2. This problem causes origin and destination hotspots to lose their semantic meaning. Another problem of grid-based clustering is that after clustering you should use Cartesian product of zones to make the OD matrix and the Cartesian product creates many OD matrix entries which have no travel demand.

Two dimensional clustering
The K-means, agglomerative hierarchical clustering, and DBSCAN are other common approaches for detecting hotspots of taxi trips origins and destinations in two-dimensional map space [21]. For example Tang et al. [31] used DBSCAN clustering algorithm to cluster pick-up and drop-off locations to generate OD matrix for traffic distribution estimation. In this paper we use K-means clustering algorithm [2]. K-means is an optimization-based clustering algorithm which tries to increase intra-cluster similarity by reducing Eq. (1) value. In order to reduce the K-means cost value (J ), origins and destinations vectors (x q ) should converge to their cluster center vector (µ i ). According to Eq. (2), by K-means cost reduction, within clusters scatter (S W ) get reduced and consequently between clusters scatter (S B ) get increased, because total scatter (S T ) = (S W ) + (S B ) is constant. In every iteration of the K-means algorithm, points move to nearest clusters.
For our problem, origin and destination hotspots should have a maximum size because prediction large zones is not useful. For this purpose, we ran K-means clustering algorithm with different number of seeds on origin and destination points to find the approximate number of clusters with appropriate maximum intradistance. After we extracted hotspots of origins and destinations points using K-means clustering, we should pair them, but there would be some origin and destination hotspot pairs which have no travel demand, thus the OD matrix could be smaller. Another problem with two-dimensional clustering is that clustering of origin and destination points separately can damage the quality of travel patterns. As shown in Fig. 3 clusters A and B are two origin hotspots, and clusters C and D are destination hotspots. According to this clustering, our OD matrix has 4 entries and 3 of them have non-zero number of travels. Because of separate clustering of origin and destination points, one unique travel pattern has been split into three OD matrix entries. If the clustering had considered points with the thick outline in clusters A, B and C, D respectively as one origin and one destination hotspot, the travel pattern was stated in one entry.

Four dimensional clustering
As declared in the previous subsection it seems that two-dimensional clustering makes the OD matrix large and it causes damages to the travel patterns. Another approach is to move into a four-dimensional space where latitude and longitude of origin and destination points form its dimensions. Each point (Org Lat , Dest Lat , Org Lon , Dest Lon ) in this space means a travel on two-dimensional map. Close points in this space are travels which their origins and destinations are close to each other. We use K-means clustering for travel points in this four-dimensional space and we ran the algorithm with different number of clusters to find the appropriate clustering with low mean clusters intra maximum distance and low number of clusters. In Fig. 4 one of the travel clusters is depicted. To visualize travel points in four-dimensional space, we use color range as the fourth dimension in a three-dimensional space. Coordinates of the points are set based on distance (in meters) from an arbitrary origin. This approach has two advantages. The first is reduction of number of OD matrix entries. In fact in four-dimensional space, since we don't pair origin and destination hotspots and each travel cluster has its own origin and destination hotspots, instead of OD matrix, we use OD vector. The second advantage is the high quality of the clusters which makes them more informative about travel patterns because both origin and destination points have participated in travel clustering simultaneously and the points are divided among fewer entries. We repeat the algorithm with different number of clusters to set the origin and destination hotspot maximum size limit. The travel cluster which is illustrated in Fig. 4, is depicted on the map in Fig. 5.

Travel prediction
There are two possible approaches for building a travel request prediction model: 1) creating a model for all travel clusters, and 2) creating different models for each travel cluster based on their travel patterns. For example, a time series neural network may be applicable for a travel cluster prediction and for another one using a simple statistical model might be enough. Note that we have to handle large amounts of clusters for both approaches. In this paper, we focus on the first approach.

OD vector decomposition
As mentioned in the previous section after using K-means clustering algorithm on the travel points in four-dimensional space we got much travel clusters with a specific origin and destination maximum intra-distance. When training models such as neural networks, the big size of the input vector results in a large number of trainable variables. There are decomposition algorithms like Principal Component Analysis (PCA) that might be used to reduce the size of the OD vector. PCA reduces the dimension of the OD vector by choosing eigenvectors which have much bigger eigenvalues [22]. There are some work which have used PCA for OD matrix decomposition but the main problem with using PCA in this context is that the physical meaning of the real situation could not be reflected by the negative values returned by PCA, and it disturbs the prediction accuracy [4,13,25]. According to multiple studies on the NMF, this algorithm can guarantee to extract the integrated features of data by non-negative values during the analysis process. The NMF algorithm has been used in many fields such as spectral data analysis, learning parts of faces and semantic features of text [4,12,23], DNA gene expression analysis [6], and clustering of protein interactions [16]. Using the NMF algorithm as described in [10,15], we decompose each OD vector to a coefficient vector and a constant basis matrix, as shown in Eq. (3). Coefficient vector has many fewer dimensions. We predict time series coefficient vector, then we use the basis matrix to inverse transform the predicted coefficient vector to an OD vector. Suppose the overall time length of the data is (T ) and each OD vector has (N ) clusters of travel demand in a time interval. The NMF algorithm returns coefficient vectors in (M ) dimensional space which is much smaller than (N ) dimensional space.

N >> M
NMF is an optimization-based algorithm, and in order to decompose matrix (V ) to matrices (C, B) (4) such that C ≥ 0 , B ≥ 0 (5), we have to minimize the NMF cost (6). For data dimension reduction, usually (M ) is chosen such that T M + M N << T N [15].
d β (x|y) (7) is a scalar cost function which is called β-divergence with a single minimum for x = y [3]. The β-divergence is a family of cost functions parametrized by a shape parameter β that takes the Euclidean distance, the Kullback-Leibler divergence and the Itakura-Saito divergence as special cases for different values of β [15]. For β = 0 and β = 1, β-divergence responds like IS and KL divergences, respectively.
The heuristic update rules for basis and coefficient matrices are as follows: (More details are available in [15].)

Prediction model
After using NMF algorithm to reduce the time series OD vectors dimensions, we use stacked recurrent neural networks for feature extraction and a feed-forward fully connected layer for linear regression to predict the coefficient vector of the next time interval (t ′ ) as shown in Fig. 6. To get the OD vector of next time interval, the estimated coefficient vector should be multiplied by basis matrix which we have obtained from the NMF algorithm. To increase the prediction accuracy of the model, some weather condition features such as temperature, pressure, humidity, wind speed, wind direction, dew point temperature, and visibility were added to travel clusters data. In addition to weather condition features, time features such as the hour of the day, the day of the week, part of the hour (for time windows of less than an hour), and is-holiday are used for travel prediction. Supervised feature extraction part of the model helps to extract most influential features on the output by sequentially nonlinear mappings. Our model input is a sequence of the features of the last (t) time intervals which as mentioned earlier, includes the coefficient vectors of the last (t) time intervals, the time and the weather condition features. We tested three types of recurrent neural networks cell: 1) Simple Recurrent, 2) LSTM, and 3) GRU. As shown in Fig. 6 we used three recurrent cells in the prediction model. An unfolded simple recurrent cell for input sequence (x) with length (t) is depicted in Fig. 7. According to Eq. (10), for each sequence entry, we have a nonlinear mapping modeled by sigmoid activation function (12) which helps to reveal nonlinear relations of input features. The problem with this type of recurrent cell is that it forgets the first entries of a long input sequence [20].  Cho et al. [8] proposed a gating mechanism in recurrent neural networks which is like LSTM but only has update Eq. (19) and reset Eq. (20) gates and has fewer trainable variables. Chung et al. [9] have shown that GRU outperforms LSTM on smaller datasets where it is harder to extract patterns. For the VAR model [26] as declared in Eq. (23), the estimated value is a linear function of its previous values in the last (t) time intervals plus a constant vector (c) and an unobservable zero-mean white noise vector (e t ′ ). For our proposed model according to Fig. 6 and Eq. (25), we use multiple nonlinear mappings on the features of the last (t) time intervals (f ), then extract important features (ef ), and finally use linear regression 26 to estimate the next time interval coefficient vector. The recurrent cells in feature extraction part of the model could be each of those recurrent cells which described earlier. Sending input features to each recurrent cell concatenated to previous cell output helps to avoid the problem of vanishing gradients and speeds learning. [18] Our proposed model is trained considering Mean Squared Error (MSE) Eq. (27) cost function for (T ) time intervals. Here we encounter another optimization problem. To minimize the cost function, we use Root Mean Square Propagation (RM-SProp) optimizer [19] Eqs. (28,29). The momentum is denoted by (β), trainable variables by (w) and the learning rate by (α).

Experiments
To train and test our proposed model we use passenger travel data of Tap30.org, an online taxi-hailing company in Iran. Travel data are gathered in city of Tehran, from September 13th to October 27th, 2018. We use the data of the first 38 days for clustering and model training and the next 7 days as test data for classification and model validation. Test data classification and model validation is based on the clusters extracted by the K-means algorithm on train data in four-dimensional space as declared before.

Four dimensional K-means clustering
At first, we use the K-means clustering algorithm in four-dimensional space to get significant OD flows. To apply maximum intra-distance limitation in origin and destination zones, we repeat the K-means algorithm for different number of clusters. It should be noted that as clusters size increase, the confidence interval of our prediction also increases, but the results may not be informative. For small travel cluster size, prediction becomes more difficult, in other words the travel clusters will be less predictable and more random. 10000 travel clusters with 2900 meters average of clusters' maximum intra-distance for origin and destination zones is an acceptable confidence interval to the domain experts of the data provider company. We have ignored insignificant clusters, i.e. clusters with less than 10 travels in 5 weeks. As illustrated in Fig. 10 and Fig. 11 by increasing the maximum intradistance of origin and destination zones in each cluster, travel data quality or count of travels increases and vice versa. It is possible for a small origin or destination zones with high travel rate to include a hotspot like a shopping center, a university, etc.  The results of our three aforementioned clustering methods are shown in Table  1. Clusters with fewer than 10 travels do not hold important information about the travels pattern. Four-dimensional K-means clustering can extract meaningful travel patterns because of putting origin and destination points of travels together. According to the clustering results on our data, this method has made fewer clusters of travel than the other existing techniques.  Table 2, the NMF algorithm has a significant impact on the number of trainable variables for the three proposed recurrent models. To find the best input time length, we tried 9 different input time length for the proposed model. We use the mean absolute percentage error metric (MAPE@1 31) to evaluate the models performance on predicting non-zero demand. MAE and MSE don't show the performance differences of the models for this test. We use the three introduced recurrent cells in this test. Also MSE, MAE and MAPE@1 metrics in all tests are calculated on denormalized data. According to Fig. 12, we consider a 3-hour length for the time series sequence, in other words the proposed model forecasts based on the last three hours coefficient vectors, time features, and weather conditions. It seems that longer sequences do not help the prediction and only cause longer processing of data. As declared before our proposed model has a supervised feature selection part which makes it unnecessary to do feature selection manually. To check the time and weather features impact on the proposed models prediction, we train and test the proposed models with and without the extra features. As shown in Fig. 13, weather features decrease the MAPE@1 metric more than time features and thus it is the more effective feature.  To compare our models prediction accuracy with existing models we implemented some of them. The simplest one is called calendar model, which has three types: 1) Hourly calendar model which returns mean of the number of travels in the last 3 hours, 2) Daily calendar model which returns mean of the number of travels in the past 7 days for the specified hour, and 3) Weekly calendar model which returns the mean of travel count in the past 5 weeks for the specified hour and day. The second model is MLP, which has the same structure as the proposed model with the difference that the recurrent part is replaced with a simple layer of neurons. The input data of the MLP model is similar to our proposed model with the exception of the time series axis and thus all the last 3 hours features come in a vector. We also use NMF algorithm on models input which 'NMF' is written at the beginning of their name. The other models that use input data similar to the MLP model are SVM [28] with Radial Basis Function (RBF) kernel, K-Nearest Neighbors (KNN) [1] with uniform distance weight, and Random Forest [5]. We also use NMF-VAR [25] which is explained earlier and its input data structure is like our proposed model. Except weekly and daily calendar models, the other ones use the past 3 hours features to predict next hour travel.
According to the bar chart shown in Fig. 15, it seems that MLPs prediction accuracy is better than the other models but based on the bar charts of Fig. 16 and Fig. 14, MLP cannot predict nonzero travel count well. In other words it seems that considering all the bar charts, the three proposed models outperform the existing techniques. As mentioned earlier the stacked recurrent model can represent the non-linear relations among the past 3 hours features (weather conditions, time and travels counts) vectors and the next hour coefficient vector but NMF-VAR only finds the coefficient of a linear model which is based on the past 3 hours travel count. The three proposed stacked recurrent models have similar predictability but according to Fig. 14, it seems that NMF-Stacked LSTM's higher complexity results in more useful features in the feature extraction part of the linear regression  phase and it causes more accurate prediction for non-zero values. The predicted coefficient vectors were converted to travel vectors by multiplying the basis matrix. As shown in Fig. 17 four out of 10000 travel clusters are randomly selected to compare the NMF-Stacked LSTM model travel prediction and the exact values. We repeat the comparisons for NMF-VAR, NMF-Stacked RNN, NMF-Stacked GRU and NMF-Stacked LSTM with 30 minutes time intervals. Decreasing the confidence intervals size, hinders the prediction but the results are more useful. We train the models based on the past 180 minutes features to predict the next 30 minutes travel count.   As illustrated in Fig. 19 and Fig. 20 MSE and MAE values are decreased comparing to values in Fig. 15 and Fig. 16. It is because of the travel count decrement in tighter time intervals. According to Fig. 18 MAPE@1 is increased because as declared earlier prediction for the tighter intervals is harder. This shows that NMF-Stacked GRU can predict nonzero travel count with much better accuracy than the other three models but based on MAE and MSE metrics, proposed recurrent models predictability are close to each other.

Conclusion
Based on an online taxi-hailing passenger travel data, we proposed a prediction model. At first, using the K-means clustering algorithm in four-dimensional space, meaningful travel flows were grouped into 10000 clusters. We showed that these clusters have better quality than Grid-based and 2D K-means clustering results. After clustering travel data, we aggregated the demand values for each travel cluster in hourly time intervals. To increase prediction accuracy, weather condition and time features were added to the input vector. These extra features caused about 5% improvement on mean absolute percentage error for non-zero travel count prediction. We also proposed a neural network model which has a stacked recurrent part for supervised feature extraction and a linear regression part. The feature extraction part has the ability to find non-linear relations between the features. According to our experiments, it was shown that the proposed model outperforms the other popular models with about 5-7% MAPE@1, 0.19 MSE, and 0.13 MAE improvement. Simple-RNN, LSTM, and GRU as recurrent cell of feature extraction part of the model had close results but for 30 minutes time interval prediction, the proposed model with GRU recurrent cell had about 14%, 10%, 7% better MAPE@1 comparing to NMF-VAR, NMF-Stacked RNN, and NMF-Stacked LSTM models, respectively.