CN110505583A - A Trajectory Matching Algorithm Based on Bayonet Data and Signaling Data - Google Patents

Abstract

The invention provides a trajectory matching algorithm based on bayonet data and signaling data. The algorithm includes data preprocessing, space-time trajectory matching algorithm, data enhancement algorithm and a classification model for judging whether the vehicle trajectory matches the mobile phone trajectory. Firstly, the invalid data in different data sets are removed, and the vehicles and mobile phones with frequent activities are screened out by calculating the information entropy; then the potential matching data sets of vehicles and mobile phones are obtained according to a spatio-temporal trajectory matching algorithm, and then according to the vehicle and mobile phone trajectories Long-term tracking to obtain the definite match between the vehicle and the mobile phone; then use the data enhancement algorithm to expand the definite matching trajectory; finally use the trajectory matching result to select reasonable model features and establish a trajectory classification model. The invention is applied to the matching of massive vehicle trajectories and mobile phone signaling trajectories, and solves the problems of poor calculation efficiency of trajectory matching, single measurement index and the like.

Description

A Trajectory Matching Algorithm Based on Bayonet Data and Signaling Data

technical field

The invention relates to the field of trajectory matching algorithms, and more specifically, to a trajectory matching algorithm based on bayonet data and signaling data.

Background technique

In recent years, with the development of positioning technology, a large amount of individual trajectory data has emerged. Vehicle trajectories can be recorded by fixed position sensors, such as automatic number plate recognition systems on road monitoring checkpoints. It recognizes a vehicle's license plate number from images captured by color, black and white, or infrared cameras. Vehicle trajectories can be reconstructed based on the data recorded by the bayonet. In addition to fixed position sensors, mobile traffic sensors can move with the vehicle, they include rovers, GPS devices and cell phones. When a mobile phone makes a call or surfs the Internet, it will contact a nearby base station, and the base station will record data such as the current time, location, and device number. Through these data, the detailed movement track of the mobile device or individual can be restored.

Based on the trajectory data of millions of vehicles and mobile phones in the city, finding the most similar trajectory pair from two heterogeneous data sets is equivalent to pairing the driver with the vehicle in the city, which will have a considerable impact. The application value can provide a theoretical reference for residents' travel pattern recognition, impact analysis of urban vehicle restriction policies, privacy data release and other research fields.

At present, many trajectory similarity calculation methods have been proposed at home and abroad, which can be mainly divided into two categories: spatial similarity and spatiotemporal similarity. Spatial similarity is mainly to find trajectories with similar geometric shapes while ignoring the temporal dimension, while spatio-temporal similarity considers both temporal and spatial characteristics of trajectories. However, these algorithms need to calculate the similarity of every two trajectories, which is too computationally expensive for millions of trajectories in the city, and often only uses one indicator to evaluate the similarity of trajectories, which cannot be fully described Trajectory similarity.

Contents of the invention

The invention provides a track matching algorithm based on bayonet data and signaling data, which provides a more reasonable calculation method with less computational complexity and more evaluation indicators for the matching of massive heterogeneous trajectories.

In order to achieve the above-mentioned technical effect, the technical scheme of the present invention is as follows:

A trajectory matching algorithm based on bayonet data and signaling data, comprising the following steps:

S1: Obtain the road checkpoint monitoring data set and mobile phone signaling data set in the research area and research time period;

S2: Preprocessing the bayonet data set and signaling data set, including invalid data cleaning, time span screening, and frequent moving trajectory screening;

S3: Obtain the potential matching data set between the vehicle and the mobile phone through the spatio-temporal trajectory matching algorithm;

S4: Match the trajectories of vehicles and mobile phones in different time periods in the potential matching data set. If the vehicle and mobile phone trajectories maintain the same matching relationship within the time range, it means that the vehicle and the mobile phone are definitely matched;

S5: Use the data enhancement algorithm to sample the determined matching trajectories to obtain more positive cases of vehicle and mobile phone matching; randomly select vehicle and mobile phone trajectories from the bayonet and signaling data sets, and select wrongly matched vehicle and mobile phone trajectories as A counterexample of matching a vehicle with a mobile phone;

S6: Using reasonable model features and a classification algorithm with high accuracy, a trajectory classification model is established based on the positive and negative trajectory data obtained in the above steps.

Further, in the step S1, the mobile phone signaling data includes: (1) user number isdn: the unique identification of the mobile phone user; (2) longitude lng: the longitude of the user's location; (3) latitude lat: the user's location Latitude; (4) time time: the time when the signaling record was generated. The bayonet monitoring data includes: (1) bayonet number kdbh: the unique identification of the monitoring bayonet; (2) longitude kkjd: the longitude of the monitoring bayonet; (3) latitude kkwd: the latitude of the monitoring bayonet; (4) )Vehicle license plate hphm: the license plate number of the vehicle passing through the checkpoint; (5) passing time gcsj: the time for the vehicle to pass through the checkpoint.

Further, in the step S2, the invalid data includes abnormal position data, that is, the latitude and longitude of the bayonet or signaling data is not within the research scope; field missing data, that is, data with missing fields such as time, latitude and longitude, and vehicle license plate; and Incorrect identification data, specifically the incorrect data of the vehicle number plate identified by the bayonet.

Further, in the step S2, the time span screening is specifically to select signaling and bayonet data from 6:00 to 24:00 every day for calculation, and to exclude data outside this time period.

Further, in the step S2, the moving frequency of the trajectory is measured by calculating the information entropy value of each trajectory, and only the trajectory whose information entropy value is greater than the threshold is selected for trajectory matching calculation, and the information entropy threshold is 2. The specific calculation method of the trajectory information entropy value is:

Among them, D is the moving track of a vehicle or mobile phone, Ent(D) is the information entropy value of the track, p _k is the proportion of the kth position point in the track, and m is the number of different position points in the track.

Further, in the step S3, the specific process of the spatio-temporal trajectory matching algorithm is:

a) Extract the moving trajectory of a vehicle from the bayonet data set according to the license plate number and passing time, and the trajectory points are arranged in chronological order;

b) Take a vehicle trajectory point as the research object in sequence, and search whether there is data centered on the vehicle trajectory point in the signaling data set that satisfies the spatiotemporal constraints formed by the time threshold τ and the distance threshold ε;

c) If it exists, record all mobile phone devices that meet the space-time constraints as the potential mobile phone matching data set of the vehicle;

d) Take the next vehicle track point and search whether there is a mobile phone device that satisfies the space-time constraints of the track point. If it exists, the mobile phone device corresponding to the two track points will be intersected. If it does not exist or the intersection is empty, the vehicle Matching failed;

e) If the potential mobile phone matching data set is not empty at the last track point, the vehicle matching is successful.

The time threshold τ in the algorithm is 600 seconds, and the distance threshold ε is 2000 meters.

Further, in the step S4, the time range is one week or more, and it is determined that the matching refers to that the mobile phone is the mobile phone device carried by the driver of the corresponding vehicle.

Further, in the step S5, the specific process of the data enhancement algorithm is:

a) Select the trajectory of the vehicle and the mobile phone that are determined to be matched, and randomly select several points from the vehicle trajectory points to form a new vehicle trajectory;

b) For the new vehicle trajectory, select signaling data points that satisfy the space-time constraints of the new vehicle trajectory from the corresponding mobile phone trajectory to form a new mobile phone signaling trajectory;

c) The sampled vehicle trajectory and signaling trajectory can be used as a new determined matching trajectory pair.

Further, in the step S6, the model features are shortest distance (CPD), Hausdorff distance (HD), dynamic time warping distance (DTW), maximum common substring (LCSS) and edit distance (EDR).

Further, in the step S6, the classification algorithm is the LightGBM algorithm, which is a fast, distributed, high-performance gradient boosting algorithm based on the decision tree algorithm.

Compared with the prior art, the beneficial effects of the technical solution of the present invention are:

1. The traditional similarity calculation method is to enumerate any two trajectories to calculate their similarity. For millions of mobile phone users and vehicles in the city, a large amount of computing resources will be required to complete the matching calculation. The method of the present invention improves the matching calculation efficiency of massive heterogeneous trajectories. Firstly, the trajectories with infrequent movement are eliminated through the trajectory information entropy value, and secondly, the spatiotemporal constraints are also used in the spatiotemporal trajectory matching algorithm to quickly exclude a large number of dissimilar trajectories. It can reduce a lot of calculation overhead and reduce calculation time.

2. The currently commonly used algorithms for finding similar trajectories only consider a single similarity index. The method of the present invention combines multiple classic similarity indexes to construct a classification model based on the LightGBM algorithm. The model can describe the space-time of the trajectory more completely characteristics, and effectively judge whether there is a matching relationship between the given two heterogeneous trajectories.

Description of drawings

Fig. 1 is a schematic flow chart of the present invention.

Detailed ways

The accompanying drawings are for illustrative purposes only and cannot be construed as limiting the patent;

In order to better illustrate this embodiment, some parts in the drawings will be omitted, enlarged or reduced, and do not represent the size of the actual product;

For those skilled in the art, it is understandable that some well-known structures and descriptions thereof may be omitted in the drawings.

The technical solutions of the present invention will be further described below in conjunction with the accompanying drawings and embodiments.

Example 1

As shown in Figure 1, a trajectory matching algorithm based on bayonet data and signaling data includes the following steps:

S1: Obtain the road checkpoint monitoring data set and mobile phone signaling data set in the research area and research time period;

S2: Preprocessing the bayonet data set and signaling data set, including invalid data cleaning, time span screening, and frequent moving track screening;

S3: Obtain the potential matching data set between the vehicle and the mobile phone through the spatio-temporal trajectory matching algorithm;

S4: Match the trajectories of vehicles and mobile phones in different time periods in the potential matching data set. If the vehicle and mobile phone trajectories maintain the same matching relationship within the time range, it means that the vehicle and the mobile phone are definitely matched;

S5: Use the data enhancement algorithm to sample the determined matching trajectories to obtain more positive cases of vehicle and mobile phone matching; randomly select vehicle and mobile phone trajectories from the bayonet and signaling data sets, and select wrongly matched vehicle and mobile phone trajectories as A counterexample of matching a vehicle with a mobile phone;

S6: Use reasonable model features and a classification algorithm with high accuracy to establish a trajectory classification model based on the positive and negative trajectory data obtained in the above steps.

The above steps will be described in detail below.

First of all, it is necessary to obtain more than one week's record data of all road checkpoints and mobile phone base stations in the research area, such as prefecture-level administrative regions or county-level administrative regions.

Secondly, preprocess the vehicle bayonet data and mobile phone signaling data:

a) Delete the data whose latitude and longitude coordinates are not in the research area; delete the data whose field information is null or invalid; Delete the data of the wrong number plate in the bayonet data set.

b) Eliminate the data from 0:00-6:00 every day in the vehicle bayonet data set and mobile phone signaling data set, and do not participate in the trajectory matching calculation.

c) Filter out the daily trajectory of each vehicle and each mobile phone through the license plate number, mobile phone device number and recording time, and calculate its information entropy value according to the geographic location of the trajectory points in each trajectory. The calculation formula is as follows:

Among them, D is the moving track of a vehicle or mobile phone, Ent(D) is the information entropy value of the track, p _k is the proportion of the kth position point in the track, and m is the number of different position points in the track.

If the information entropy value of the trajectory is less than 2, it will be deleted from the corresponding data set and will not participate in the trajectory matching calculation.

Next, take the bayonet data set and signaling data set of a certain day within the research range to perform the spatio-temporal trajectory matching algorithm operation.

a) From the bayonet data set, extract the moving track c of a car according to the license plate number and passing time, and the track points are arranged in chronological order;

b) Take a vehicle trajectory point lc ₁ as the research object in order, and search whether there is data centered on the vehicle trajectory point in the signaling data set that satisfies the spatiotemporal constraints formed by the time threshold τ and the distance threshold ε. The spatiotemporal constraints are as follows Show:

(lc.x-ε, lc.y-ε, lc.t-τ) ≤ (ls.x, ls.y, ls.t) ≤ (lc.x+ε, lc.y+ε, lc.t +τ)

c) If there is signaling data ls that satisfies the space-time constraints, the mobile phone devices corresponding to these trajectories are recorded as the potential mobile phone matching data set cs1 _of the vehicle;

d) Take the next vehicle track point lc ₂ , and search whether there is a mobile phone device cs ₂ that satisfies the space-time constraints of the track point. If it exists, calculate the intersection of the mobile phone devices corresponding to the two track points. If it does not exist or the intersection is empty ,Right now or Then the vehicle matching fails;

e) If the potential mobile phone matching data set is not empty at the last track point, the vehicle matching is successful.

Then, for a certain vehicle, if within seven days a week, a certain mobile phone appears in its potential mobile phone matching data set, it is considered that the vehicle and the mobile phone are definitely matched, that is, the mobile phone is carried by the driver of the vehicle. Mobile devices.

Next, for a certain vehicle trajectory c=(lc ₁ , lc ₂ , lc ₃ , lc ₄ , lc ₅ , lc ₆ ) and a certain mobile phone signaling trajectory s=(ls ₁ , ls ₂ , ls ₃ , ls ₄ , ls ₅ , ls ₆ ), randomly select 3 points from the vehicle trajectory to get a new vehicle trajectory Then according to the space-time constraint relationship, the corresponding new mobile phone signaling trajectory is obtained In this way, a new positive example of vehicle-to-mobile matching can be obtained; then the trajectories of vehicles and mobile phones are randomly selected from the bayonet and signaling data sets, and the trajectories of incorrectly matched vehicles and mobile phones are selected as negative examples of vehicle-to-mobile matching.

Finally, different eigenvalues of matching positive examples and matching negative examples are calculated respectively, including shortest distance (CPD), Hausdorff distance (HD), dynamic time warping distance (DTW), maximum common substring (LCSS) and edit distance ( EDR), forming the data set shown in Table 1.

Table 1 Schematic diagram of the data set

ID hphm isdn CPD SPD DTW LCSS EDR label 1 @#$E8 5ea3bd 38.80 2354 397.66 5 46 1 2 $%#91 2fb9df 42.48 3812 266.43 3 47 0 3 ! #$@19 ed2e83. 19.16 227 237.84 7 51 1

Randomly select 70% of the data from the data set as the training set, input the LightGBM model for training, and predict the remaining 30% of the data.

The same or similar reference numerals correspond to the same or similar components;

The positional relationship described in the drawings is only for illustrative purposes and cannot be construed as a limitation to this patent;

Apparently, the above-mentioned embodiments of the present invention are only examples for clearly illustrating the present invention, rather than limiting the implementation of the present invention. For those of ordinary skill in the art, other changes or changes in different forms can be made on the basis of the above description. It is not necessary and impossible to exhaustively list all the implementation manners here. All modifications, equivalent replacements and improvements made within the spirit and principles of the present invention shall be included within the protection scope of the claims of the present invention.

Claims (10)

1. A track matching algorithm based on bayonet data and signaling data, is characterized in that, comprises the following steps: S1: Obtain the road checkpoint monitoring data set and mobile phone signaling data set in the research area and research time period; S2: Preprocessing the bayonet data set and signaling data set, including invalid data cleaning, time span screening, and frequent moving track screening; S3: Obtain the potential matching data set between the vehicle and the mobile phone through the spatio-temporal trajectory matching algorithm; S4: Match the trajectories of vehicles and mobile phones in different time periods in the potential matching data set. If the vehicle and mobile phone trajectories maintain the same matching relationship within the time range, it means that the vehicle and the mobile phone are definitely matched; S5: Use the data enhancement algorithm to sample the determined matching trajectories to obtain more positive cases of vehicle and mobile phone matching; randomly select vehicle and mobile phone trajectories from the bayonet and signaling data sets, and select wrongly matched vehicle and mobile phone trajectories as A counterexample of matching a vehicle with a mobile phone; S6: Using reasonable model features and a classification algorithm with high accuracy, a trajectory classification model is established based on the positive and negative trajectory data obtained in the above steps. 2. the track matching algorithm based on bayonet data and signaling data according to claim 1, is characterized in that, the mobile phone signaling data in the described step S1 comprises: (1) user number isdn: the unique identification of mobile phone user ; (2) longitude lng: the longitude of the user's location; (3) latitude lat: the latitude of the user's location; (4) time time: the time when the signaling record was generated. The bayonet monitoring data includes: (1) bayonet number kdbh: the unique identification of the monitoring bayonet; (2) longitude kkjd: the longitude of the monitoring bayonet; (3) latitude kkwd: the latitude of the monitoring bayonet; (4) ) Vehicle license plate hphm: the license plate number of the vehicle passing through the checkpoint; (5) passing time gcsj: the time for the vehicle to pass through the checkpoint. 3. The trajectory matching algorithm based on bayonet data and signaling data according to claim 2, characterized in that, in the step S2, the invalid data includes abnormal position data, that is, the latitude and longitude of the bayonet or signaling data is not under study Within the range; missing data in fields, that is, missing data in fields such as time, latitude and longitude, and vehicle license plate; and incorrect identification data, specifically, incorrect data in the vehicle license plate for bayonet recognition. 4. The trajectory matching algorithm based on bayonet data and signaling data according to claim 3, characterized in that, in the step S2, the time span screening is specifically to select the signaling from 6:00 to 24:00 every day Calculate with bayonet data, and exclude data outside the time period. 5. The trajectory matching algorithm based on bayonet data and signaling data according to claim 4, characterized in that, in the step S2, the frequency of movement of the trajectory is measured by calculating the information entropy value of each trajectory, Only the trajectory whose information entropy value is greater than the threshold is selected for trajectory matching calculation, and the information entropy threshold is 2. The specific calculation method of the trajectory information entropy value is: Among them, D is the moving track of a vehicle or mobile phone, Ent(D) is the information entropy value of the track, p _k is the proportion of the kth position point in the track, and m is the number of different position points in the track. 6. The trajectory matching algorithm based on bayonet data and signaling data according to claim 5, characterized in that, in the step S3, the specific process of the spatiotemporal trajectory matching algorithm is: a) Extract the moving trajectory of a vehicle from the bayonet data set according to the license plate number and passing time, and the trajectory points are arranged in chronological order; b) Take a vehicle trajectory point as the research object in sequence, and search whether there is data centered on the vehicle trajectory point in the signaling data set that satisfies the spatiotemporal constraints formed by the time threshold τ and the distance threshold ε; c) If it exists, record all mobile phone devices that meet the space-time constraints as the potential mobile phone matching data set of the vehicle; d) Take the next vehicle track point and search whether there is a mobile phone device that satisfies the space-time constraints of the track point. If it exists, the mobile phone device corresponding to the two track points will be intersected. If it does not exist or the intersection is empty, the vehicle Matching failed; e) If the potential mobile phone matching data set is not empty at the last track point, the vehicle matching is successful. The time threshold τ in the algorithm is 600 seconds, and the distance threshold ε is 2000 meters. 7. The trajectory matching algorithm based on bayonet data and signaling data according to claim 6, characterized in that, in the step S4, the time range is one week or more, and determining the matching means that the mobile phone is the corresponding vehicle The mobile phone device carried by the driver. 8. The trajectory matching algorithm based on bayonet data and signaling data according to claim 7, characterized in that, in the step S5, the specific process of the data enhancement algorithm is: a) Select the trajectory of the vehicle and the mobile phone that are determined to be matched, and randomly select several points from the vehicle trajectory points to form a new vehicle trajectory; b) For the new vehicle trajectory, select signaling data points that satisfy the space-time constraints of the new vehicle trajectory from the corresponding mobile phone trajectory to form a new mobile phone signaling trajectory; c) The sampled vehicle trajectory and signaling trajectory can be used as a new determined matching trajectory pair. 9. The track matching algorithm based on bayonet data and signaling data according to claim 8, characterized in that, in the step S6, the model features are shortest distance (CPD), Hausdorff distance (HD), Dynamic Time Warping Distance (DTW), Maximum Common Substring (LCSS) and Edit Distance (EDR). 10. The trajectory matching algorithm based on bayonet data and signaling data according to claim 9, characterized in that, in the step S6, the classification algorithm is the LightGBM algorithm, which is a fast, distributed, high-performance Gradient boosting algorithm based on decision tree algorithm.