CN106408124A - Moving path hybrid forecasting method oriented to data sparse environment - Google Patents

Abstract

A hybrid prediction method for moving paths in a data-sparse environment, including the following steps: obtaining mobile location data information; data processing: performing data preprocessing and data semantic analysis on the data; building a semantic knowledge base: performing rich semantic analysis on the original trajectory data Transformation and fusion processing, constructing semantic knowledge base; building hybrid online prediction model: based on semantic knowledge base, establishing a hybrid online prediction model based on forward pattern similarity matching calculation and high-order Markov model; prediction path output: in hybrid online In the prediction model, input the segment of the trajectory to be predicted for prediction, and output the predicted path. The present invention effectively overcomes the problem of pattern matching failure caused by data sparseness, and at the same time significantly improves the accuracy of path prediction, meeting the requirements of real-time, high efficiency, predictability and other aspects of mobile service applications.

Description

A Hybrid Prediction Method for Moving Path in Data Sparse Environment

technical field

The invention belongs to the technical field of mobile computing, and in particular relates to a mixed prediction method for moving paths in a data-sparse environment.

Background technique

At present, with the rapid development and widespread popularization of mobile positioning and tracking technology, it is possible to use location-aware devices to obtain historical trajectory data of moving objects. It has become a significant trend and inevitable feature in the field of mobile computing to realize the value extraction and knowledge discovery of historical trajectory big data through semantic modeling and calculation of historical trajectory data, thereby supporting related mobile service applications. attention from academia and industry.

Based on the large-scale group sensing historical trajectory data, the universal and regular mobile characteristics and behavior patterns can be efficiently mined and extracted to build a mobile behavior knowledge base; through the mathematical modeling of the mobile trajectory, the maximum probability derivation method can be used. Realize accurate online path prediction for mobile users. This technology can be widely used in many fields such as intelligent scheduling and management of urban traffic, location-based commercial precision advertising marketing, and travel route recommendation. However, in practical applications, the above methods have two problems, specifically as follows: 1) The context and background knowledge data are not easy to obtain, making it difficult to combine Map Matching Technique or Traffic Flow statistical methods to It is difficult to improve the prediction accuracy of moving paths; 2) The data sparsity problem (Data Sparsity Problem) caused by the low value density of perceptual data makes the traditional methods based on approximation calculation or pattern matching difficult to work. The existence of the above problems has brought great challenges to the application services of mobile path prediction. Therefore, in view of the sparse distribution characteristics of massive sensory trajectory data, how to construct a highly applicable and reliable mobile path accurate prediction model and method under the condition of lack of context and background knowledge data has very important practical significance and application value.

Contents of the invention

The invention provides a path prediction method for the sparse distribution of massive mobile trajectory data. The technical solution adopted is:

A mixed prediction method for moving paths in a data-sparse environment, comprising the following steps:

S1: Obtain mobile location data information;

S2: Data processing: data preprocessing and data semantic analysis for data;

S3: Build a semantic knowledge base: perform rich semantic conversion and fusion processing on the original trajectory data, and build a semantic knowledge base;

S4: Build a hybrid online prediction model: Based on the semantic knowledge base, establish a hybrid online prediction model based on forward pattern similarity matching calculation and high-order Markov model;

S5: Prediction path output: Input the trajectory segment to be predicted in the hybrid online prediction model for prediction, and output the prediction path.

Further, a mobile path hybrid prediction method oriented to a data-sparse environment, the mobile location data information in S1 includes trajectory segments to be predicted.

Furthermore, a mixed prediction method for moving paths in a data-sparse environment, the semantic analysis of the data in S2 includes performing a unified semantic coordinate transformation operation on the data, segmenting the data into complete moving track segments, and marking them.

Furthermore, a mixed prediction method for moving paths in a data-sparse environment, the semantic-rich transformation and fusion processing of the original trajectory data in S3 includes: semantic segmentation of hidden maps, simple node extraction of road network skeletons, Mobile Patterns Knowledge Discovery.

Further, a mixed prediction method for moving paths in a data-sparse environment, the semantic-rich conversion and fusion processing of the original trajectory data in S3 also includes a region-level Pair migration matrix, and the region-level Pair migration matrix is calculated based on the semantic segmentation processing of the hidden map.

Further, a mixed prediction method for moving paths in a data-sparse environment, the semantic-rich conversion and fusion processing of the original trajectory data in S3 also includes a multi-continuous state transition probability model, and the multi-continuous state transition probability The model is used to transform semantic data for sequence of segmented trajectories.

Furthermore, a mixed prediction method for moving paths in a data-sparse environment, the forward pattern matching in S4 includes element matching and distance calculation.

Furthermore, a mixed prediction method for moving paths in a data-sparse environment prioritizes the forward pattern matching prediction process, and outputs the prediction path when there is a solution in the matching process; The current moving state is used as the reference, and the probability distribution of the continuous state transition of the corresponding order is recursively forward, and the one with the maximum probability is used as the predicted path with a step size of 1. Through the recursive cycle process, the predicted destination location information is used as Termination condition, output prediction path.

Further, a method for moving path hybrid prediction in a data-sparse environment, in which the corresponding data processing in S2 is performed before the segment of the trajectory to be predicted in S5 is input.

Furthermore, a hybrid prediction method for moving paths in a data-sparse environment is designed, and the corresponding dynamic monitoring management and message generation process control are designed for the data preprocessing and semantic analysis steps in S2.

The present invention provides a path prediction method oriented to the sparse distribution of mobile trajectory data, constructs a city map semantic model through historical trajectory data to realize rich semantic conversion and fusion of original trajectory data, and establishes Pattern Matching Computing (Pattern Matching Computing) ) and Higher Order Markov Model (Higher Order MarkovModel) hybrid forecasting method, the essence of which is to build a hybrid and replaceable collaborative forecasting model. In order to improve the accuracy of path prediction; on the other hand, a replaceable high-order Markov model is used to construct a segmented trajectory movement state transition probability matrix model under strict time series relationship, so as to effectively overcome the pattern matching failure (No Pattern Matching) problem, while significantly improving the accuracy of path prediction, meeting the needs of mobile service applications for real-time, high efficiency, and predictability.

Description of drawings

Fig. 1 is a schematic diagram of the steps of a method for moving path hybrid prediction in a data-sparse environment according to the present invention;

Fig. 2 is a schematic diagram of the forward mode similarity matching result of a moving path hybrid prediction method in a data sparse environment according to the present invention;

Fig. 3 is a path prediction result under different known lengths of online prediction trajectories of a mobile path hybrid prediction method oriented to a data-sparse environment in the present invention;

FIG. 4 is a schematic diagram of a prediction result of a moving path hybrid prediction method in a data-sparse environment according to the present invention.

detailed description

A mixed prediction method for moving paths in a data-sparse environment, comprising the following steps:

S1: Obtain mobile location data information;

The information receives and stores data from multiple location-aware sources (vehicle GPS, mobile smartphone, PDA, etc.). In this embodiment, the mobile location data information includes the trajectory segments to be predicted.

S2: Data processing: perform data preprocessing and data semantic analysis on the data;

As shown in Figure 1: the preprocessing of the data is: the preprocessing operation of the collected historical trajectory data, specifically including: 1) the noise introduced by the signal strength change of the positioning device and the channel change in the data transmission process data, the module performs noise detection and filtering; 2) due to the instability of the link connection during the rapid movement of the moving object and the data loss phenomenon caused by the packet loss phenomenon in the data transmission process, the module performs equal time interval Data interpolation operation;

The data semantic analysis includes a unified semantic coordinate conversion operation on the data, which is divided into complete movement trajectory segments and marked: 1) Due to the automatic process of the movement trajectory collection process and the lack of labeling attributes, this module is not suitable for continuous collection of movement trajectory Perform the semantic segmentation operation of the Complete trajectory segment based on the time interval threshold and the space interval distance threshold; 2) Due to the differences in the selection of spatial coordinate systems of multi-source mobile positioning devices (WGS84 coordinate system, GGRS87 coordinate system, GSM coordinate system etc.), this module performs a unified semantic coordinate transformation operation.

In this embodiment, the corresponding dynamic monitoring management and message generation process control are designed for the step S2 data processing step, that is, in the process of receiving and analyzing the moving track data, the flow controller controls the flow operation of the data receiving and semantic analysis process .

S3: Build a semantic knowledge base: perform semantic-rich transformation and fusion processing on the original trajectory data, and build a semantic knowledge base; the semantic-rich transformation and fusion processing of the original trajectory data in S3 includes:

As shown in Figure 3, the specific implementation process of the semantic segmentation of the hidden map is: calculate the two-dimensional density function based on the spatial distribution characteristics of the large-scale historical offline trajectory position points, and combine the two-dimensional density function and the boundary approximation value set to realize the hidden Reconstruction of semantic topological relationship with map geospatial and secondary division process of regional spatial area;

Simple node extraction of road network skeleton: similar to the hidden map semantic segmentation module, based on the spatial distribution density characteristics of large-scale mobile trajectory data, the hidden position points of the restricted movement trajectory data under the constraints of the belt network are extracted to form a road network skeleton Minimalistic node collection.

The process of extracting the simplified nodes of the road network skeleton is based on the calculation of the movement angles of k adjacent sequences in the historical moving trajectory, and the key road network nodes are extracted through the density-based clustering method.

Mobility pattern knowledge discovery is based on the semantic segmentation of the hidden map and the simplified node output set of the road network skeleton, the process of semantically rich transformation of the original collected movement trajectory data, and the efficient extraction of potential mobility behavior patterns based on the sequential pattern mining algorithm The collection provides knowledge support for subsequent mobile path prediction.

The semantic-rich conversion and fusion processing of the original trajectory data in S3 also includes a region-level Pair migration matrix, and the region-level Pair migration matrix is calculated based on the semantic segmentation of the hidden map. The specific implementation is as follows: The complete set of complete trajectory segments in the mobile trajectory data semantic analysis module is used as input data, and the pair point set is extracted, and then the semantic-rich conversion process of the corresponding pair point set is realized based on the regional spatial area division with hidden map semantics. The corresponding Pair migration probability matrix block under conditional probability is constructed using Bayesian network. Among them, a pair refers to a pair from one location to another location, including the starting point and end point of the response; a region-level pair refers to starting from one region and ending at another region.

The semantic-rich conversion and fusion processing of the original trajectory data in S3 also includes a multi-continuous state transition probability model, which is used to transform the semantic data of the segmented trajectory sequence.

Among them, the semantic knowledge base refers to storing the set of mobile behavior patterns discovered by the knowledge discovery module of mobile patterns, the association rules of mobile behavior, and the high-order state movement transition matrix knowledge based on the Markov probability process output by the multi-continuous state transition probability.

S4: Build a hybrid online prediction model: Based on the semantic knowledge base, establish a hybrid online prediction model based on forward pattern similarity matching calculation and high-order Markov model;

The forward pattern matching includes element matching and distance calculation, which is used to realize the approximation calculation process based on the matching direction and distance between the Partial trajectory to be predicted and the excavated movement pattern, and at the same time output the movement path prediction result through the similarity threshold comparison .

Among them, the Markov probability prediction model: used to realize the probability calculation and prediction process between the Partial trajectory to be predicted and the multi-continuous state transition probability matrix based on the current moving state and the high-order Markov order as the step size, and at the same time Output the prediction result of the moving path with a step size of 1.

In this embodiment, the forward pattern matching prediction process is prioritized to maximize the use of historical movement information in Partial to effectively improve the accuracy of the output prediction path, wherein the forward pattern matching process uses the Partial trajectory segment and the excavated movement pattern Match the same element between them, and calculate the forward distance of the same matching element to compare the similarity between the movement pattern and the Partial fragment one by one, and return the corresponding suffix sequence as the output prediction path if there is a solution in the matching process; In the case of a solution, execute the Markov probabilistic inference model, take the current moving state as the benchmark, recursively forward the corresponding order continuous state transition probability distribution, take the one with the maximum probability as the output prediction path with a step size of 1, and pass recursion The loop process uses the derived Partial destination location information as the termination condition to generate the final output prediction path.

In the hybrid prediction model, the calculation method of forward mode similarity matching is as follows:

In the above formula (1), degree represents the similarity value between the historical movement pattern and the online segment movement track, cov is the pattern matching length of the two, and dis represents the composite distance between the current position of the online query track and the historical pattern , sup is the support degree of the historical pattern. In formula (2), e _k is all the elements that match the online query track in the historical pattern, and e _end represents the current position of the online query track.

A brief description of the similarity matching process of the above-mentioned forward pattern, as shown in Figure 2, the circular sequence is the segment of the online query movement track, and there are three matchable patterns in the historical movement pattern, in which the triangle represents the matching element, and the square represents the short-term Prediction paths, where candidate mode 1 has value 2, is 1.

In the high-order Markov calculation model, the calculation formula of the next potential position Rank with a step size of 1 is:

arg Max:score(loc)

Among them, score(loc) represents the Rank value of the candidate position loc, d _orig represents the distance between the position loc and the starting position of the fragment trajectory, d _dest represents the distance between the position loc and the inference destination of the fragment trajectory, and pro(loc) represents the position loc at The transition probability value in the trained high-order Markov model. By calculating the Rank value of m candidate positions loc, the one with the largest Rank value is the next predicted position of the online query segment trajectory.

S5: Prediction path output: Input the trajectory segment to be predicted in the hybrid online prediction model for prediction, and output the prediction path.

According to the sparse distribution characteristics of the mobile trajectory data, the above hybrid and complementary prediction mode is used to realize the purpose of predicting the future movement path of the online query trajectory segment. For 5000 test track fragments, the predicted path results are compared and verified under the five conditions of known lengths of 10%, 20%, 30%, 40% and 50%, respectively, with the first-order Markov model method and the second-order Markov model method For comparison, the hybrid prediction model (Hybrid Moving Route Prediction, HMRP) constructed by the present invention has significant advantages, as shown in Fig. 3 and Fig. 4 .

Claims (10)

1. A method for moving path mixing prediction method under data sparse environment, it is characterized in that: described method comprises the following steps: S1: Obtain mobile location data information; S2: Data processing: Perform data preprocessing and data semantic analysis for data; S3: Build a semantic knowledge base: Perform rich semantic conversion and fusion processing on the original trajectory data to build a semantic knowledge base; S4: Build a hybrid online prediction model: Based on the semantic knowledge base, a hybrid online prediction model based on forward pattern similarity matching calculation and high-order Markov model is established; S5: Prediction path output: In the hybrid online prediction model, input the trajectory segment to be predicted for prediction, and output the predicted path. 2 . The hybrid prediction method for moving paths in a data-sparse environment according to claim 1 , wherein the moving position data information in S1 includes trajectory segments to be predicted. 3 . 3. The mixed prediction method for moving paths in a data-sparse environment according to claim 1, characterized in that: the semantic analysis of data in the S2 includes a unified semantic coordinate conversion operation for the data, which is divided into complete Move the track segment and label it. 4. A mixed prediction method for moving paths in a data-sparse environment according to claim 1, characterized in that: the semantic-rich conversion and fusion processing of the original trajectory data in the S3 includes: implicit map semantics Segmentation, simple node extraction of road network skeleton, knowledge discovery of mobility patterns. 5. A mixed prediction method for moving paths in a data-sparse environment according to claim 4, characterized in that: the semantic-rich conversion and fusion processing of the original trajectory data in the S3 also includes regional-level Pair migration matrix, the region-level Pair migration matrix is calculated based on the hidden map semantic segmentation processing. 6. A mixed prediction method for moving paths in a data-sparse environment according to claim 4, characterized in that: the semantic-rich conversion and fusion processing of the original trajectory data in the S3 also includes multi-continuous state transitions A probability model, the multi-continuous state transition probability model is used to transform semantic data for segmented trajectory sequences. 7. A method for moving path hybrid prediction in a data-sparse environment according to claim 6, characterized in that: said forward pattern matching in S4 includes element matching and distance calculation. 8. The mixed prediction method for moving paths in a data-sparse environment according to claim 1, characterized in that: the forward pattern matching prediction process is performed preferentially, and the prediction path is output when the matching process has a solution; When solving, execute the Markov probabilistic inference model, take the current moving state as the benchmark, recursively forward the corresponding order continuous state transition probability distribution, take the one with the maximum probability as the output prediction path with a step size of 1, and pass the recursive cycle process , output the predicted route with the predicted destination location information as the termination condition. 9 . The method for moving path hybrid prediction in a data-sparse environment according to claim 1 , wherein the corresponding data processing steps in S2 are executed before the segment of the trajectory to be predicted is input in S5 . 10. According to any one of claims 1-9, a mobile path hybrid prediction method oriented to a data-sparse environment is characterized in that: corresponding dynamic monitoring management and message are designed for the steps of data preprocessing and semantic analysis in S2 Generate flow control.