{'fraction_non_alphanumeric': 0.023877327491785325, 'fraction_numerical': 0.006681270536692223, 'mean_word_length': 4.815923566878981, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 1}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
DRFMM: a map-matching algorithm based on distributed random forest multi-classification

In the vehicle navigation system, the vehicle movement trajectory displayed on the electronic map reflects the results of real-time positioning by the GPS measuring device. Map matching is the process of matching a series of GPS coordinates to an electronic map to find the true path of the trajectory. In this study, a distributed random forest map-matching algorithm (DRFMM) is proposed. The point-line matching method is used as the basic feature. The random forest algorithm in the Spark platform is used to train the historical data. The road network data is meshed, and a multi-classification model is trained offline for each grid in the road network to predict the FCD data online. The experimental results show that the DRFMM algorithm proposed in this paper has improved the accuracy of point-line matching by 10%. The multi-classification method keeps the matching accuracy with the increase of data volume. At the same time, with multi-threading and distributed platform, DRFMM's matching speed is nearly 6 times faster than stand-alone matching algorithm.


Introduction
With the accelerating process of urbanization, the number of road vehicles has increased sharply and traffic congestion has become increasingly serious. With the gradual deepening of research on traffic, the Intelligent Transportation System (ITS) emerged as the times require.
Floating Car Data has become an advanced collection method for urban road traffic conditions in ITS. FCD data includes GPS positioning data of floating vehicles, driving direction angle, and time information, which can obtain the speed of the road segment and traffic flow parameters.
Map matching is an important step in FCD processing, which directly affects the accuracy of traffic information acquisition. Due to the default error in positioning device, it often leads to a situation where the vehicle trajectory and the actual road are greatly deviated on the electronic map. Therefore, map matching is needed to avoid errors in vehicle positioning.
The rest of the article is organized as follows: Section 2 discusses the related terms and Section 3 discusses related work. The DRFMM model will be introduced in detail in Section 4. We do some experimental verification and analysis in Section 5. Finally, we conclude the paper in Section 6.

Road Network
The road network is a directed graph ( , ). is a set of vertices, representing the intersection or turning points of the road. E = → , ∈ that is a series of directed edges, representing the road segments in the road network.

GPS trajectory
The GPS trajectory is a series of time series data T: → → ⋯ → that are sequentially transmitted by the same car over a period of time.

Related Work
According to the application environment, the map matching algorithm can be divided into geometric/incremental matching and global matching algorithms.
The geometric/incremental map matching algorithm [4][7] [8] is represented by the geometric map matching method. The point-to-line matching algorithm can find the correct road segment more accurately by calculating the distance from the point to the road segment. This method ensures a certain accuracy and matching speed. The global matching algorithm [1][3] [9] attempts to find a path in the road network to be closest to the floating car trajectory. Yu Zheng et al [2] proposed a new global matching algorithm ST-Matching for low sampling rate GPS trajectories.
In general, the incremental algorithm has better performance than the global algorithm in terms of algorithm running time, and the global algorithm can obtain more accurate matching results.
In order to obtain a faster matching speed, Renchu Song [5] achieved map matching through multicore CPU to greatly speed up the matching speed. Antonio [6] proposed a distributed map matching algorithm using MapReduce computing framework to improve the speed of map matching.

Road Network Mesh
The road network data used in this paper is about Hefei city downloaded from OpenStreetMap. We use the xml.etree library of Python to extract the required the road segment and node information.
In the classification algorithm, the more training categories, the longer the training and predicting cost. And the extracted road network contains 11981 road segments. Therefore, we use meshing to process road network data, and operations within each grid can be processed in parallel.
We assume that the road network is L long and H high. The study divides the entire map into M × N grids of the same size. The coordinates of the lower left corner of the road network map is ( , ). The coordinate of any point in the map is p( , ), then the grid ID to which the point belongs can be calculated by the following formula: The driving data that is not in the range of the road network will be removed, establishing the mapping relationship between the road name in FCD and the road segments in the road data.
For the GPS point of the sample data, we calculate the corresponding grid number using formula (1), and the distance of the point with all the segments in the grid by using formula (2). The distance is used as a feature of the training/test set, using the real road segment ID as the training set label.
Algorithm 1 Data Preprocess Input: original road data hefei.osm and trajectory dataset hefei_taxi.

Random forest multi-classification algorithm.
This paper hopes to improve the matching accuracy and speed up the matching process. The random forest algorithm is more suitable for multiclassification problems. The training and prediction speed is fast and it is easy to achieve parallelization. Therefore, this paper chooses random forest algorithm to train multi-classification model in each grid.

Distributed implementation details
The Spark platform has many ecological environment tools and integrates many machine learning libraries. We choose Spark as the distributed computing platform. The overall flow chart of this article is as follows: Figure 1. Overall architecture of the DRFMM model The offline training phase is model-based parallel processing that multiple nodes simultaneously train some parameters of a single model. After training, we save the corresponding model of the grid in the HDFS distributed file system. The online prediction phase is Data-based parallelism, based on the Python multi-threaded programming and Spark's parallel framework, each sample of the test set is allocated in parallel to its grid, and the offline trained model is used to predict the segment where it is located.

Experimental verification and analysis
The pre-processed test set format example is as follows. The example is the corresponding test set in the NO.74645 grid, and the label of the training set is the real Section ID.

Experimental setup and result
We used eight LENOVO machines to build a Hadoop/Spark cluster. All code is written in Python and runs on a Spark cluster in the Yarn mode. algorithm using 10000,30000,50000 trajectory points, and the average of each set of experiments was taken as the final accuracy. It is found from the experimental results that the accuracy of DRFMM is significantly higher than that of point-line matching, and as the matching trajectory points increase, the accuracy of point-line matching decreases, but the accuracy of DRFMM almost remains stable.
In order to verify that the multi-classification method maintains a stable accuracy when the trajectory points number increase, we add a neural network NN as the matching algorithm of the multi-classification model. It can be seen from the accuracy that when the trajectory increases, the NN method still maintain stable accuracy. We calculate the acceleration ratio of the system, and draw the following line chart in Figure 2.
It can be seen that the 8-node distributed matching algorithm only needs 12.08 seconds to match 51,545 trajectory points, which is nearly 6 times faster than the stand-alone matching speed.

Conclusion
Two main contributions of this paper is the distributed map matching algorithm based on random forest multi-classification model and using Spark paradigm to speed up matching speed.
The experimental results show that the DRFMM algorithm improves the matching accuracy by 10% compared with the traditional point-line matching algorithm. With the help of Python multi-threading and Spark distributed computing framework, the matching speed is improved by nearly 6 times compared with the stand-alone matching algorithm.
We will continue to expand our work in the following two directions. Firstly, the Spark distributed computing paradigm greatly reduces the matching time, but the system's acceleration ratio is still not good enough. It is necessary to explore the Spark parallel mechanism and improve the ratio. Secondly, we use the map data source-OpenStreetMap itself has some errors, and the error of the road network data will directly affect the matching result. We consider updating the road network data from the trajectory data to correct the error of the map data itself.