CN113327079A - Path selection potential factor visual analysis method based on network car booking track - Google Patents

Abstract

The invention discloses a route selection potential factor visual analysis method based on a network car booking track, which comprises the following steps: acquiring a track data point set of a network appointment vehicle order, and performing network matching on each track point to obtain the number of a road; for each network car booking order, extracting the road number of the network car booking of the order passing through the selected section, converting the road number of each network car booking order into a road sequence, and calculating a similarity matrix of the road sequence; projecting by taking the obtained similarity matrix as input, extracting track clusters with similar attributes, and extracting frequently-occurring subsequences as key paths; and counting influence factors related to the driver path selection on each path, obtaining the subjective selection of the user on each path related factor through a weight model, and analyzing the importance degree of different factors on ranking results. The invention provides a visual basis for the planning of travel routes between urban areas, network car booking and traffic dispersion.

Description

Path selection potential factor visual analysis method based on network car booking track

Technical Field

The invention relates to the field of transportation, in particular to a route selection potential factor visual analysis method based on a network car booking track.

Background

In the era of rapid development of modern information technology, with the application and popularization of GPS devices, a great deal of information on the movement trajectories of people and vehicles is collected. The data can truly and comprehensively reflect the relevant information of urban traffic and personnel flow. Urban computing combines urban perception, data acquisition, data management, data analysis and service provision into a complete processing flow, assists in understanding the essence of various urban phenomena, and further improves the living standard of people. Traffic is one of the most important application areas in urban computing. Many transportation systems analyze the mobility of people in urban areas by combining multi-source heterogeneous relevant data such as weather and population distribution so as to know travel behaviors and improve travel experience.

However, in the traffic network of the four-way eight-reach, there are usually a plurality of routes from a certain starting point to a certain end point, and it has become a concern in the transportation field to know how a driver selects a route, i.e. the behavior of selecting a route. The intelligent road planning system can help city planners to improve road use conditions and can also help drivers to make intelligent travel decisions. However, the driver may choose a different route depending on different factors, such as the time cost of traveling. Selecting the route with the least time cost is a selection preference for the general tendency in people's daily life. Other factors may also influence route decision making, such as the number of traffic lights, the degree of road traffic clearance, etc. Also, the influence of these factors may change with time. The efficiency of travel is the primary concern during the weekdays, and the balance between efficiency and comfort of travel is used on weekends. When the mutual influence of various factors such as time, style preference of a driver and the like is comprehensively considered, the problem of the path selection behavior is even more complicated, and the difficulty is mainly reflected in the following aspects: firstly, the track data comprises a series of track points containing longitude and latitude and time information, and because the precision of the GPS equipment is insufficient, a large amount of missing and wrong numerical values exist in the collected track data. Secondly, under different travel paths, the lengths of the road track sequences constructed are inconsistent, and the similarity of the original track sequences is difficult to measure. Thirdly, the potential factors influencing the path selection are complex and diverse, and a certain challenge is provided for effectively quantifying the respective influence action and reasonably verifying the influence action.

In recent years, some researchers have collected volunteer trajectories with the help of a global positioning system using a GPS receiver for exploration analysis. It takes less effort and the captured routing behavior is more realistic than traditional preference statement investigations. However, such pilot studies are typically conducted on limited users in a limited spatio-temporal context, such as collecting only morning commuting travel data. In order to improve the defects of the traditional research method, the invention provides a track similarity calculation method based on a real network car booking track data set and combined with the road network data, develops a set of visual analysis system, helps a user to process large-scale track data, compares different route selections and explores potential factors influencing the selection

Disclosure of Invention

The invention aims to overcome the defects of the prior art and provides a path selection potential factor visual analysis method based on a network car booking track, which comprises the following steps:

acquiring a track data point set Tr ═ { Tr of a network taxi appointment order₁,tr₂,...,tr_mGet a group of order track point sequence with length l by track filtration

Carrying out road network matching on each track point p to obtain the serial number of the road;

for each network car booking order, firstly extracting the road number of the network car booking of the order passing through the selected section, and attaching a timestamp; then, the road number of each network car booking order is numberedConversion to road sequence S ═ R₁,R₂,…,R_i,…,R_num]， R_iRepresenting indexes of roads, and constructing a similarity matrix according to a road sequence;

projecting by taking the obtained similarity matrix as input, projecting track data points of all network appointment orders into a two-dimensional space, extracting track clusters with similar attributes, and extracting frequently-appearing subsequences from travel paths in the track clusters by using a VMSP algorithm to serve as key paths;

and counting influence factors related to the driver path selection on each path, obtaining the subjective selection of the user on each path related factor through a weight model, and analyzing the importance degree of different factors on ranking results.

Further, the track data point set Tr ═ Tr for obtaining the network taxi appointment order₁,tr₂,...,tr_mGet a group of order track point sequence with length l by track filtration

After road network matching is carried out on each track point p, the number of the road where the track point p is located is obtained, and the method specifically comprises the following processes:

track data point set Tr ═ Tr for network taxi booking order₁,tr₂,...,tr_mAnd f, wherein m is the order number, and a group of order track point sequences with the length of l is obtained through track filtering

And (3) performing road network matching on each track point P to obtain the number of the road, and when performing road network matching, firstly calculating candidate points and creating a candidate point diagram, wherein the candidate points PⁱSelecting a candidate point each time to calculate the distance from the point to the network; if the distance is less than or equal to the maximum search distance, extracting a candidate point as a point c closest to the observation point on the road network_iAnd adds it to the candidate layer i.

Further, for each network car booking order, the network of the order is extracted firstlyThe number of the road passed by the car appointment in the selected section is numbered, and a timestamp is attached to the number; then, the road number of each network taxi booking order is converted into a road sequence S ═ R₁,R₂,…,R_i,…,R_num]，R_iThe method comprises the following steps of representing indexes of roads, and constructing a similarity matrix according to a road sequence, wherein the method specifically comprises the following steps:

firstly, extracting road numbers of the order vehicles of the online taxi appointment in a selected section and a timestamp, and then converting the road numbers of each order into a sequence S ═ R₁,R₂,…,R_i,…,R_num]，R_iAn index representing roads, where num is the number of roads in the selected range;

grouping orders according to road sequences passed by different network appointment driving tracks; firstly, constructing a similarity matrix according to a road sequence; will T_kDefined as the set of all possible k-grams in the sequence S: s: t is_k(S)＝{k-gram|k-gram＝ (s_js_j+1...s_j+k-1)，j∈[1，n+1-k]}; suppose that the two sequences are S₁And S₂And given k, first according to T ═ T_k(S₁)∪T_k(S₂) To compute a set of all possible k-grams; converting the two sequences to the same length; then, passing through the array

Calculating a normalized frequency for each k-gram in each sequence l (l ═ 1, 2), wherein

Represents the jth k-gram in the sequence l; finally, the normalized polar distance D (S) between the two sets is calculated by a formula₁，S₂)：

Further, the obtained similarity matrix is used as input to be projected, the track data points of all network car booking orders are projected into a two-dimensional space, track clusters with similar attributes are extracted, a VMSP algorithm is used for extracting frequently-occurring subsequences from travel paths in the track clusters to serve as key paths, and the method comprises the following processes:

further dividing the path of the order track, projecting the calculated difference matrix serving as input by using a projection method and a t-SNE algorithm, and selecting a key path in different clusters according to the projection result for analysis; for two data points x in a high dimensional space_iAnd x_j，x_iSelecting x by conditional probability p (j | i)_jAs its neighboring points, p (j | i) is defined as follows:

wherein sigma_iIs represented by x_iThe conditional probability in the low-dimensional space is represented by q (j | i) as the variance of the Gaussian distribution of the center point, and the variances of all the Gaussian distributions are simultaneously set

In this case, q (j | i) is:

minimizing the difference of two probability distributions in the same event space, using a cost function F of:

the t-SNE considers the neighborhood relationship, so that data points with close distance in a high-dimensional space are closer in a low-dimensional space, and data points with far distance are farther in the low-dimensional space;

and taking the track sequence in the cluster as the input of the VMSP algorithm, and extracting the frequent subsequence meeting the minimum support counting as a key path.

Further, the method includes the steps of counting influence factors related to the driver path selection on each path, obtaining subjective selection of the user on the relevant factors of each path through a weight model, and analyzing importance degrees of different factors on ranking results, and specifically includes the following steps:

counting the number of orders by using a Ranking SVM through different paths selected by a user circle as initial sequencing, and obtaining the weight of a group of influence factors according to the initial sequencing;

using the number of the network appointment orders in each path as an initial sequence to generate sequencing marking data; the Ranking SVM model takes all combinations of paired difference vectors as training examples;

using the number of network appointment vehicle orders as initial sequencing and training a Ranking SVM model, obtaining a weight vector w, sequencing data points according to values of attribute weights, and obtaining Ranking scores of the data points; and obtaining the contribution of the attribute value to the ranking score of the data point according to the contribution value of the data point attribute.

Further, the system comprises a traffic flow overview module, an interactive road sequence extraction and key path extraction module and a path selection factor exploration module;

the traffic flow overview module is used for counting traffic flow according to the driving track, utilizing the whole space-time distribution of the cellular map and the time sequence flow evolution diagram overview flow, exploring the traffic flow evolution condition in the region by combining a clustering algorithm and dividing a time slice;

the interactive road sequence extraction and key path extraction module is used for firstly calculating the similarity of the tracks, then extracting track clusters, analyzing frequent subsequences of the road sequence as key paths by using a VMSP algorithm, and screening order tracks meeting the key paths for statistics;

the exploration module of the path selection factors is used for analyzing potential factors influencing driver selection and relevant factors in different paths.

The invention has the beneficial effects that: the method is based on a network car booking track data set, and interactive exploration is carried out on path selection potential factors to help an analyst comprehensively and efficiently extract a key travel path from large-scale track data, and meanwhile, the potential factors in the path are quantized to enable the analyst to intuitively and deeply know the potential factors influencing the path selection behavior of a driver, so that a visual basis is provided for inter-city-area travel path planning, network car booking scheduling and traffic dispersion.

Drawings

FIG. 1 is a flow chart of a method for visually analyzing path selection latent factors based on a network car booking track;

FIG. 2 is a schematic diagram of a network appointment trajectory based path selection latent factor visual analysis system;

FIG. 3 is a candidate point set in a road network and a created candidate layer;

FIG. 4 is a diagram of network appointment trajectory data matching results;

FIG. 5 is a graph comparing the effect of t-SNE projection and MDS projection;

FIG. 6 is a time series flow chart;

FIG. 7 is a cellular map;

FIG. 8 is a track filtering view;

FIG. 9 is an order trajectory projection view;

FIG. 10 is a schematic diagram of order trace selection and geographic information display;

FIG. 11 is a schematic diagram of road mode display and critical path selection;

FIG. 12 is a path sort view;

FIG. 13 is a correlation factor contribution view and a path ordering view.

Detailed Description

The technical solutions of the present invention are further described in detail below with reference to the accompanying drawings, but the scope of the present invention is not limited to the following.

As shown in fig. 1, road network matching is a process of associating longitude and latitude information of a series of ordered travel tracks to an electronic map road network. Its main purpose is to track the driving route of vehicle, analyze traffic flow and find the starting point of driving direction. Map matching corresponds to the decoding problem in a Hidden Markov Model (HMM), which is based on finding a Hidden sequence that produces this observation sequence under a given observation. Where the hidden sequence represents the specific location of the person or object holding the positioning device, and the observation sequence represents a series of coordinates consisting of GPS track points generated by the positioning device. After the hidden Markov model is matched, the road where the GPS track point is actually located can be obtained for subsequent research.

Track data point set Tr-Tr for network appointment orders used in the present invention₁,tr₂,...,tr_mAnd f, wherein m is the order number, and a group of order track point sequences with the length of l is obtained through track filtering

In order to obtain a track sequence and perform the next similarity calculation and the key path extraction, the name of the road where each track point p is located needs to be obtained after road network matching is performed on each track point p. In road network matching, we first calculate candidate points and create a candidate graph. Candidate point PⁱIs the possible position observed on the network, and the distance from the point to the network is calculated every time the candidate point is selected. If the distance is less than or equal to the maximum search distance, the extraction candidate object is taken as the point c closest to the observation point on the road network_iAnd adds it to the candidate layer i.

As shown in fig. 3, the candidate graph is a directed acyclic graph representing all paths that are possible final matches of the GPS track. The graph will be used as a stochastic matrix for the hidden markov model, with n layers, where n is the observed value. Each column contains all candidates with the same or corresponding observations. The computation of candidate points has a large impact on computation time, e.g. a higher search distance may result in more candidates and more likely paths per observation, which will be computed in the next step, so a high subdivision of the network may result in a large number of candidate points per observation.

All probabilities along each path will be efficiently multiplied by using the Viterbi algorithm (Viterbi algorithm), and only the highest probability of reaching a candidate point will be stored and reused, i.e. the path with the highest probability of passing through the candidate graph. For the network appointment vehicle track data set used in the invention, the matching result is shown in fig. 4, and it can be seen from the top right detail view that the cleaned network appointment vehicle track points have a better matching effect in the network data.

The track similarity is an important index for the analysis of the moving objects, and how to measure the track similarity is a central problem. Aiming at the large-scale network car booking track data set, the calculation amount can be reduced and the calculation efficiency can be improved by extracting the similarity of the road sequence passing by the track.

The data set of the invention consists of a series of network appointment car order records, and all track points in each order are recorded according to the time sequence. For each network appointment order, we first extract the road number that the vehicle passes through in the selected section, with an exact timestamp. Then, we convert the road number of each order into the sequence S ═ R₁，R₂，...，R_i，...，R_num]， R_iAn index of links is represented, where num is the number of links in the selected range.

In order to group orders according to road sequences passed by different network appointment driving tracks, a similarity matrix is constructed according to the road sequences. However, because the road sequence is too long and the lengths of the road sequences are different between two tracks, the subsequence is extracted from the original sequence as the feature to compare the similarity, and T is used_kDefined as the set of all possible k-grams (k consecutive elements) in the sequence S. S: t is_k(S)＝{k-gram|k-gram＝(s_js_j+1...s_j+k-1)，j∈[1，n+1-k]To calculate the distance for two different sequences to have the same length, we have calculated the common k-gram in both sequences and its count. Suppose that the two sequences are S₁And S₂And given k, we first turn we from T ═ T_k(S₁)∪T_k(S₂) To compute the set of all possible k-grams. Therefore, we convert both sequences to the same length. Then, we pass through the array

Calculating a normalized frequency for each k-gram in each sequence l (l ═ 1, 2), wherein

Representing the jth k-gram in the sequence l. Finally, we calculate the normalized polar distance D (S) between the two sets by the formula₁，S₂)。

The normalized distance ranges from 0 to 1, with smaller numbers indicating a smaller distance between the two sequences, and a higher similarity. We test different k values from 1 to 5, finally choose the k value to be 3, and when the k value is 3, the clustering effect of the obtained diversity matrix is most obvious. The computational complexity of the algorithm is o (n), where n is the number of road sequences. The method is scalable in terms of computation speed when the sequence is computationally intensive. In addition, speed is also affected by the average length of the sequence and the total number of all possible k-grams, but in a real net appointment trajectory dataset, these two parts are usually of a specific range. Thus, the speed is mainly affected by the number of sequences. After building the similarity matrix, we next project all order trajectories into a two-dimensional space based on their similarities.

In order to further divide the path of the order track, the calculated difference matrix is used as input to be projected through a projection method, and the key path can be selected from different clusters to be analyzed according to the projection result. In the selection of a projection method, a t-distributed stored neighboring embedding (t-SNE) algorithm is used, the method is a machine learning algorithm for reducing dimensions, is commonly used in the dimension reduction process of popular learning, and is very suitable for reducing the dimensions of high-dimensional data into two dimensions or three dimensions, and is convenient for visualization. As it is superior to the prior art in creating a single mapping that is used to exhibit different scale structures. The technique visualizes high-dimensional data by converting the similarity between data points to a joint probability and providing each data point with a location in a two-dimensional space. the t-SNE converts the similarity between data points into probability, the similarity in the original space is represented by Gaussian joint probability, and the similarity in the embedding space is represented by't distribution'.

For two data points x in a high dimensional space_iAnd x_j，x_iSelecting x by conditional probability p (j | i)_jAs its neighbors. At x_iIn a Gaussian distribution with a central point, if x_jCloser to x_iThe larger p (j | i) is. Conversely, if the distance between the two is long, p (j | i) is small. Thus, p (j | i) is defined as follows:

wherein sigma_iIs represented by x_iIs the variance of the gaussian distribution of the center point. Meanwhile, we represent the conditional probability in the low-dimensional space by q (j | i), and set the variance of all Gaussian distributions to be at the same time

In this case, q (j | i) is:

the next goal is to minimize the difference between two probability distributions in the same event space, where we use the cost function F as:

the t-SNE considers the neighborhood relationship, so that data points which are close to each other in a high-dimensional space are closer to each other in a low-dimensional space, data points which are far from each other are further away from each other in the low-dimensional space, the data points which are high in similarity need to be gathered into a cluster as far as possible after dimension reduction when the tracks are grouped, the distance between different clusters is as far as possible, the requirement can be met by using the t-SNE for dimension reduction, and the similarity between the tracks is displayed through a dimension reduction result. In the system design process, experiments are carried out by simultaneously using multi-dimensional Scaling (MDS) projection, and as shown in FIG. 5, compared with the MDS method, the results obtained by the t-SNE method can be seen in a cluster more clearly.

The road sequence segmentation method based on the k-gram and the polar coordinate distance formula can quantitatively calculate the similarity between tracks and extract track clusters with similar attributes. Due to the strong connectivity of the urban road network, even if the tracks of the same cluster are present, the driving routes are not completely consistent, and a phenomenon of partial detour may exist. In general, such detour behavior is relatively rare, belongs to an abnormal behavior in the current cluster, and cannot represent the critical path information in the cluster. Given that the trajectory data is a sequence consisting of a series of trajectory points, we can extract representative travel Patterns in the trajectory cluster using the classical frequent mining of maximum Sequential Patterns (VMSP) algorithm. The VMSP algorithm utilizes a vertical representation method to store frequent candidate item sets, traverses a search space by applying a depth-first strategy in the solving process, and finds all maximum sequence modes by continuously expanding a search range. Compared with other sequence mining algorithms, the method has the advantages that the storage mode adopts a vertical structure, so that a frequent mode can be generated through the expansion of subsequences, the expense of scanning a sequence database is greatly saved, and the sequence database can be traversed once only when a frequent 1-item set is generated in the whole mining process.

And taking the track sequence in the cluster as the input of the VMSP algorithm, and extracting the frequent subsequence meeting the minimum support counting as a key path. The VMSP algorithm comprises two stages, namely a search stage and a mode generation stage, wherein the search stage refers to a candidate sub-item set which generates a certain frequent mode by recursively expanding the mode by taking the mode as a prefix; the mode generation stage extracts the candidate sub-item set with the minimum support count by calculating the support of the candidate sub-item set generated in the search stageA frequent mode. The algorithm has two spreading modes, I-type spreading and S-type spreading, wherein I-type spreading refers to spreading at the last position of the sequence, and S-type spreading refers to spreading after the last position. For example, assume that the sequence is S ═ S<R₁，R₂，...，R_h>Type I is extended to S_i-extension＝<R₁，R₂，...，{R_h，R_x}>The S type is extended to S_s-extension＝<R₁，R₂，...，R_h，R_x>。

And (3) extracting frequently-occurring subsequences from the travel paths in the track cluster by using a VMSP algorithm as a key path. One key point of the VMSP algorithm is the problem of setting the minimum support. Through multiple tests, the minimum support degree is set to be half of the number of the travel paths, so that the coverage range of the key paths finally obtained by the algorithm is wider, and comprehensiveness of an analysis conclusion can be guaranteed.

The Ranking SVM algorithm is one of Pairwise methods, and applies the idea of optimizing a hyperplane to a sorting problem with PairWise constraints. An attribute weight vector, which may be positive or negative, may be derived using a Ranking SVM. The magnitude of the positive and negative weights respectively represents the sequencing of the attribute in the positive and negative factors, and the weight of zero represents that the given attribute does not influence the ranking of the data points. After extraction of the key paths in the region is completed, influence factors related to driver path selection, such as path length, time cost, number of traffic lights and the like, can be counted for each path, then subjective selection of the user on the relevant factors of each path can be known through a model, and importance degrees of different factors on ranking results can be analyzed.

TABLE 3.1 notation for solving the weight model

The method uses a Ranking SVM to count the number of orders selected by different paths of a user circle as initial Ranking, and obtains the weight of a group of influencing factors according to the initial Ranking. The Ranking SVM applies a classical Support Vector Machine (SVM) to the Ranking problem. Standard SVM algorithms provide data points in some m-dimensional space and provide a set of corresponding labels that label the class to which each point belongs. For one data point therein

It is usually represented in the algorithm as a set of tuples (d)_i，y_i) And when dealing with the two-class problem, label y_iE { -1, 1 }. The output model is a hyperplane composed of

Is cut into the space of data and optimized so that y_iThe point being-1 on one side of the hyperplane, and y_iThe point 1 is on the other side and the distance from the point to the hyperplane is sufficiently large.

The Ranking SVM applies the idea of optimizing the hyperplane to a Ranking problem with pairwise constraints. In addition to obtaining a complete set of data points with corresponding labels, we obtain a limited pair of data points d_iAnd d_jAnd a label tells us d_iIs better. The data input to the Ranking SVM model is a difference vector of paired data points, e.g., d_i-d_jAnd then predict which point is better based on the difference between them. We use each pathThe number of network appointment orders in (c) is used as the initial ranking score, and we will assign (d) according to formulas 3-5_i，d_j) And its relative tag converted to a tuple.

The model generated using the Ranking SVM can be used to input a pair of points and predict which is better. However, all constraints from user interaction may not be satisfied, so we choose a constraint that models all constraints as soft intervals. In this way, the user's interaction will always produce a set of attribute weights that model the user's constraints as closely as possible by setting penalty factors for violations of the constraints.

To compute the linear segmentation hyperplane for SVMs, the ranking problem must first be converted to a two-class problem. In this regard, the marking data for ranking is generated using the number of network appointment orders in each route as an initial ranking. The rankking SVM model takes as a training example the creation of all combinations of pairs of difference vectors. That is, for each i, j ∈ [1, n ]]And i ≠ j, a tuple of training data can be derived from equations 3-5, where each training instance is a pair-wise path d_iAnd d_jProperty difference between, if d_iRank higher than d_jThen, the classification is that y is 1; or if d_iIs ranked below d_jAnd y is-1. Thus, we now translate the ordering into a two-classification problem, which can classify the training data containing constraints in the Ranking SVM.

The process of calculating the Ranking is modeled according to the working mode of a Ranking SVM model. Using this model, the difference vector of two data points is input into a Ranking SVM classifier (e.g., represented as (d) for points i and j_i-d_j)). In response, the Ranking SVM uses its model to predict which of the two input points is ranked higher. First, the model uses the dot product of a given disparity vector and its internal model weight w. If the dot product w (d)_i-d_j) Positive, the vector difference belongs to the positive class y-1, so d_iRank of d_jBefore. If the dot product is negative, then the vector difference belongs to the negative class y-1, when d is present_jRelatively higher than d in the ranking_i. And finally, inputting the vector into a Ranking SVM model in a vector pair combination mode until a complete data sequence is generated.

By taking its output on any pair of data points as a comparator function in an ordering of time complexity o (nlogn), the Ranking can be derived by using a Ranking SVM model through the function. However, we do not input the difference vectors into the Ranking SVM to obtain the corresponding Ranking, but rather make the computation of the model more flexible by computing the score of each individual point based on the Ranking SVM model and Ranking based on the scores. First, we compute a single dot product from each data point weight w, thus obtaining the ranking score in equations 3-6.

The values of these dot products are then sorted, with the highest value corresponding to the highest ranking. The final result is the same as the result of defining data points directly using the Ranking SVM model, i.e., w (d)_i-d_j)＝w·d_i-w·d_j. If w.d_i＞w· d_jThen w (d)_i-d_j) > 0, thus d_iIs arranged at d_jAbove. On the contrary, if w · d_i＜w·d_jThen d_iIs arranged at d_jThe following is a description. By this method, the system can flexibly use the same sorting algorithm for data, whether the weights used therein are derived from the results of a Ranking SVM model or are modified by the user directly through the interface.

The contribution value of the data point attribute may help the user to learn the ranking score r (d) of the data point_i) (formulae 3 to 6) in which v_ijRepresents the jth attribute a_iiFor data point d_iThe calculation formula is as described in 3-7.

v_ij＝a_ijw_ij (3-7)

In addition, the contribution score

Represents an attribute a_jThe contribution to the weight normalized by the rank calculation is normalized during the t-th time period,

according to w_tjThe ratio to the maximum ranking score is calculated as described in equations 3-8.

The contribution score is calculated as

Where an attribute with a high contribution score value indicates that the attribute contributes more to the ranking score of the data point. Thus, the attribute value will contribute more to the ranking score of the data point when the weight of the attribute is higher. If the weight value of the attribute is small, the attribute value contributes less to the ranking score of the data point. Finally, by visualizing the weight values of the attributes, the user can easily know which attributes have an important role in ranking the data points.

The route selection latent factor visual analysis system based on the network appointment vehicle track consists of eight visual views, the views can be divided into three groups according to functions, the three groups comprise a track filtering group diagram consisting of a time sequence flow diagram and a map view, and the two views can respectively filter network appointment vehicle track data from time and space; a group of key path extraction group diagrams consisting of a track order projection view, a road sequence mode view and a path factor overview view, and analysts can extract key paths from the large-scale network taxi appointment track data through the views and know the relevant factor information of each path; and a factor exploration group diagram which is composed of a related factor contribution view and a path ordering view and influences path selection, wherein the two views provide interactive exploration support for the analysts aiming at the interested time period, path ordering and factor contribution.

In order to assist a user to search for time sequence change of car booking track data of a network, traffic flow is counted according to a driving track, overall space-time distribution of traffic flow is summarized by utilizing a cellular map and a time sequence flow evolution diagram, and a clustering algorithm is combined to search the traffic flow evolution situation in the region in detail from the perspective of space-time union and divide a time slice.

First, we cut in from the time perspective, draw a time-series flow chart, and show the time-series evolution of the flow in minutes. As shown in fig. 6, the radial direction is the time axis, we draw the outer time ring in hours as granularity, and the color of the ring encodes the category to which the time belongs. Furthermore, we plot a light gray bar around the time ring to show the flow situation, with minutes as the granularity, based on the idea of z-glyh, where the height of the bar maps the difference between the flow value at that moment and the mean flow value. As can be seen from fig. 6, the flow rates were less than the mean value during 0:00 to 9:30, 12:10 to 12:50, and 22:25 to 23:59, and the flow rates were greater than the mean value for the remaining time. The flow rate gradually increases from 7, decreases from about 11:30, rapidly increases from about 13, and decreases after 18:30 reaches the peak of the day. Meanwhile, the average speed per minute of all the order tracks is calculated, and the top ten percentile, the top fifty percentile and the top seventy-five percentile of all the data are counted and displayed in the circular ring area in the middle layer of the time sequence flow chart.

For a large taxi GPS trajectory, the system provides a set of graphical selectors and supports intuitive track query under space and time constraints. The main method is to utilize the brushed tracks and provide a road sequence segmentation method based on k-gram to calculate the similarity between the tracks.

From a temporal perspective, two levels of time selectors are provided: date and time. The date range is set in the date selector. The time of day range may be set in the time filter. Using these two different granularities of time selectors allows the user to query the trajectory in a periodic pattern.

From a spatial perspective, the selector we have designed is similar to a TransjectoryLenses. The selector covers a circular area and filters the trajectory with spatial constraints as in fig. 8. The correlation constraint is defined in terms of the spatial relationship between the trajectory and the circular region. For example, the selector would filter out tracks starting from a light-colored (top right of FIG. 8) circular area and going to a dark-colored (bottom left of FIG. 8) circular area. In addition to the spatial constraints, there are other geometrical constraints, such as the center position and radius of the circular area, where the radius defaults to 500 meters. In the aspect of interaction, when a mouse is hovered in a certain area, corresponding operations can be displayed. For example, hovering the mouse over a circle center will invoke a move function. In this way, complex queries can be constructed that combine different filters in an intersecting manner. Further, for two or more filters, the direction may be divided among the filters to select a trajectory that follows certain flow directions.

The filtered tracks are shown in a map view of the system, wherein two circles are track filters, colors filled in the circles are used for distinguishing the moving directions of the tracks, the tracks from light areas to dark areas can be obtained through filtering, and the positions of the tracks in the geographic space are shown by gray line segments. In order to visually show the distribution of the tracks, the opacity is used for mapping the number of the tracks, and the darker the color represents the greater the number of the tracks in the road section. In addition, white dots are added in the track to dynamically show the detailed moving process of the track, so that the user is helped to analyze the phenomena of turning around and detouring the vehicle in running.

The control panel on the left side of fig. 8 provides a fine-grained analysis tool for the system. The method comprises the steps of checking specific track information, switching between track and path layer display, displaying path related information, switching control of a track thermodynamic diagram, and configuring parameters for influencing factors in a weighted model generation process. The distribution situation of the network appointment track in the late peak time period of the area is checked by switching the control panel to a track thermodynamic diagram, and the number of the tracks corresponding to the thermodynamic diagram from shallow to deep is from low to high.

By utilizing the network appointment track selected by the track selector, a road sequence segmentation method based on k-gram is adopted to calculate the similarity between the tracks. The basic idea is to extract the track point set Tr ═ Tr of all the network appointment orders in the selected date₁,tr₂,...,tr_nN is the order quantity. Then obtaining a group of order track point sequences with the length of l in the area through track filtering

And each track point p contains the name of the road after being matched by the road network, and the name of the road is replaced by the processed number. Since the sampling time interval of each track point is 3-5 seconds, the road sequence of all orders in the area can be obtained after the duplication

Through the track filtering, the tracks of all network appointment orders in the area and the road sequence passed by the tracks can be obtained. In order to spatially divide similar order tracks, a track similarity calculation method is used to obtain a difference matrix of all tracks, wherein parameters such as k values in k-grams can be adjusted through a control panel, and then the matrix is used as input of a t-SNE algorithm to project the tracks of all orders into a two-dimensional space in a track projection view. Each point in the projection view represents a track of a network appointment order. The position of each point has no specific meaning and its distribution represents the similarity between different trajectories. When a mouse is hovered on the coordinate point, the size of the point is enlarged, the corresponding order track is highlighted by clicking the map view of the coordinate point, the user is allowed to view the geographical position information of the track, and the order number and the passing road sequence number of the network appointment track are displayed in the table view. Meanwhile, the projection view supports the brushing selection operation, and a user can conveniently divide the taxi appointment order track in the area.

The network appointment orders are grouped into different clusters according to the track similarity from the projection view, and a user can select the different clusters by using the lasso tool and view the moving positions of the network appointment tracks in the clusters in the map view. Due to the fact that the similarity of the tracks is calculated by the road sequence segmentation method based on the k-gram, partial detour phenomena exist in the tracks in the same cluster. The track of the part belongs to an abnormal phenomenon and cannot represent the information of the critical path in the current cluster, so that a VMSP algorithm is used for analyzing frequent subsequences of the road sequence in the cluster as the critical path and screening order tracks meeting the critical path for statistics.

In order to extract the tracks in the same cluster from the clustering result shown in the projection view, interactive operation of track brushing is designed, and a user circles a cluster of order track points in the projection view by using a lasso tool, wherein the tracks of all orders in the cluster are shown in a map view.

The phenomenon of detour of partial tracks can be seen through a map view, the partial tracks cannot represent the information of the key path in the current cluster, frequent subsequences of the road sequences in the cluster are required to be analyzed to serve as the key path, order tracks meeting the key path are screened for statistics, and parameters are adjusted through a control panel. In order to clearly show the road sequence mode and the key path, in the functional module, a road sequence mode view is designed to complete the analysis task of the key path extraction part.

In a road sequence mode view, road mode information in each cluster of order tracks is dynamically displayed by using a table, wherein a column of a road sequence lists all frequent sub-sequences of roads meeting the support degree in the cluster, the sub-sequences are sorted according to the sequence length and the support degree, and the colors of the sub-sequences are mapped to road types and sequentially correspond to a main road, a downtown road, a secondary road, a tertiary road, an expressway, a pedestrian road and a nameless road section from deep to light. In order to facilitate the user to view the geographical location information of the roads and tracks in each mode, the view provides a "view" function in the right "operations" column, and track information satisfying the mode can be viewed in the map view. The user clicks the "select" button to analyze the road sequence pattern as a critical path.

Through screening of a road sequence mode view, each extracted key path can be visualized as a line segment in a map view, different paths are distinguished through colors, and the number of tracks passing through the paths is coded through opacity.

And obtaining a set of related paths in the region according to the similarity calculation of the successive pairs of tracks and the extraction of the key paths. In order to clearly show potential factors influencing driver selection in different paths and reasonably analyze related factors, in the functional module, a path selection factor view and a potential factor analysis view are designed to complete analysis tasks.

Unlike the preset subjective factors in the preference statement survey method, the influencing factors in the invention are directly from the network appointment trajectory data set. For this, we can count and analyze potential factors influencing the driver to select the path from two aspects, including factors related to the path and factors related to the track. For each route, certain intrinsic properties may play a decisive role in route decision, such as the length of the route, the number of traffic lights in the route and the level of roads in the route. The road grade is distinguished by road types, such as urban main roads, surrounding roads or residential roads, and the type can be obtained by tags corresponding to the roads in the OSM road network data. In addition to those route attributes, the cost of time spent by passing vehicles on the route may be considered another route-related factor, the mean and variance of which may have an impact on route selection.

In addition, the trajectory of each order may also have varying degrees of impact on routing, including the departure time of day, the date of departure, and the length of the trajectory. For example, drivers traveling during peak and off-peak hours may make different route decisions. The factors selected to influence driver routing are shown in table 4.1:

TABLE 4.1 description of Path selection related factors

After statistics of relevant factors of the paths is completed, all paths in the area are analyzed, and statistics affecting relevant factors of driver path selection are emphatically displayed and compared, so that a table-based sorting visual path sorting view is added into a path analysis view, and multi-dimensional analysis of the paths is facilitated. Each row in the path sorting view corresponds to a path-related factor in table 4.1, and each row is a path and can be sorted by selecting any column. In order to facilitate the user to intuitively distinguish between different paths and view corresponding geographical location information, the paths are coded by icon colors on the left side, while corresponding to the path colors in the map view. The time cost in the view is shown by using a box line graph, the value of the attribute is shown from left to right from low to high, and the distribution of the time taken by the vehicle to pass through the path can be observed more intuitively by using the box line graph.

Factors in the path are of great significance in explaining the behavior of driver routing. To demonstrate the model results and assist the user in further exploration, we use a matrix to visualize the contribution of relevant factors on different time slices, as shown in fig. 13, where the horizontal axis at the top of the view is a time slice, and the 24 hours of the day are divided according to the clustering results, where the discontinuous time points in the same class are divided into two time slices. The vertical axis on the left side is the name of the relevant factor, each cell in the matrix corresponds to the contribution value of the relevant factor in different time slices, the background of the cell is gray, and the area of an internal rectangle is the contribution score

The different colors are used for distinguishing the positive weight and the negative weight of the weight in the model, the dark color codes the positive weight, and the light color codes the negative weight. The numbers at the bottom of the cells correspond to the weight values. The cells in the rightmost column of the view are the contribution values calculated by all factors in a selected time range, the width of the bar graph in each cell corresponds to the size of the contribution value, and the color also encodes positive and negative weights.

The view supports interactive adjustment of the weight, when a user clicks a cell, the system pops up a weight adjustment panel to change the weight value, then the system sorts the paths according to the new weight value, and the user can interactively explore various factors in the mode.

In addition, the system supports analysis of relevant factors of each path in different time slices, as shown in fig. 13, after a time period of 23 points is selected, contribution values of each attribute in a key path are displayed through a table and a bar graph, information of one factor is displayed in a row, the width of the bar graph encodes the contribution value, in order to visually display the influence of the factor on ranking scores, a black vertical line is set to be the position with the contribution value of 0, a dark bar graph on the right side of the vertical line represents that the weight of the factor is positive, a light bar graph on the left side represents that the weight of the factor is negative, and each factor also supports manual adjustment of the weight value by a user. The buttons in the top dotted line position are used for switching different paths, the path buttons correspondingly rank from high to low from left to right, and meanwhile the last row shows the specific ranking scores of the paths. The dark buttons are represented as the currently viewed path and support scrolling viewing through arrows on two sides, so that the number of different key paths in different areas is met, and the related factors among the different key paths are compared and analyzed.

The foregoing is illustrative of the preferred embodiments of this invention, and it is to be understood that the invention is not limited to the precise form disclosed herein and that various other combinations, modifications, and environments may be resorted to, falling within the scope of the concept as disclosed herein, either as described above or as apparent to those skilled in the relevant art. And that modifications and variations may be effected by those skilled in the art without departing from the spirit and scope of the invention as defined by the appended claims.

Claims (6)

1. A path selection potential factor visual analysis method based on a network car booking track is characterized by comprising the following steps:

acquiring a track data point set Tr ═ { Tr of a network taxi appointment order₁，tr₂，...，tr_mIs traced by a trackFiltering to obtain a group of order track point sequences with length l

Carrying out road network matching on each track point p to obtain the serial number of the road;

for each network car booking order, firstly extracting the road number of the network car booking of the order passing through the selected section, and attaching a timestamp; then, the road number of each network taxi booking order is converted into a road sequence S ═ R₁，R₂，...，R_i，...，R_num]，R_iRepresenting indexes of roads, and constructing a similarity matrix according to a road sequence;

projecting by taking the obtained similarity matrix as input, projecting track data points of all network appointment orders into a two-dimensional space, extracting track clusters with similar attributes, and extracting frequently-appearing subsequences from travel paths in the track clusters by using a VMSP algorithm to serve as key paths;

and counting influence factors related to the driver path selection on each path, obtaining the subjective selection of the user on each path related factor through a weight model, and analyzing the importance degree of different factors on ranking results.

2. The method of claim 1, wherein the trace data point set Tr-Tr for obtaining the network appointment order is set as { Tr ═ Tr } of the network appointment track₁，tr₂，...，tr_mGet a group of order track point sequence with length l by track filtration

After road network matching is carried out on each track point p, the number of the road where the track point p is located is obtained, and the method specifically comprises the following processes:

track data point set Tr ═ Tr for network taxi booking order₁，tr₂，...，tr_mAnd f, wherein m is the order number, and a group of order track point sequences with the length of l is obtained through track filtering

And (3) performing road network matching on each track point P to obtain the number of the road, and when performing road network matching, firstly calculating candidate points and creating a candidate point diagram, wherein the candidate points PⁱSelecting a candidate point each time to calculate the distance from the point to the network; if the distance is less than or equal to the maximum search distance, extracting a candidate point as a point c closest to the observation point on the road network_iAnd adds it to the candidate layer layeri.

3. The network car-booking track-based path selection latent factor visual analysis method according to claim 1, wherein for each network car-booking order, firstly extracting a road number which a network car-booking of the order passes through in a selected section, and attaching a time stamp; then, the road number of each network taxi booking order is converted into a road sequence S ═ R₁，R₂，...，R_i，...，R_num]，R_iThe method comprises the following steps of representing indexes of roads, and constructing a similarity matrix according to a road sequence, wherein the method specifically comprises the following steps:

firstly, extracting road numbers of the order vehicles of the online taxi appointment in a selected section and a timestamp, and then converting the road numbers of each order into a sequence S ═ R₁，R₂，...，R_i，...，R_num]，R_iAn index representing roads, where num is the number of roads in the selected range;

grouping orders according to road sequences passed by different network appointment driving tracks; firstly, constructing a similarity matrix according to a road sequence; will T_kDefined as the set of all possible k-grams in the sequence S: s: t is_k(S)＝{k-gram|k-gram＝(s_js_j+1…s_j+k-1)，j∈[1，n+1-k]}; suppose that the two sequences are S₁And S₂And given k, first according to T ═ T_k(S₁)∪T_k(S₂) To compute a set of all possible k-grams; will be provided withConverting the two sequences into the same length; then, passing through the array

Calculating a normalized frequency for each k-gram in each sequence l (l ═ 1, 2), wherein

Represents the jth k-gram in the sequence l; finally, the normalized polar distance D (S) between the two sets is calculated by a formula₁，S₂)：

4. The method according to claim 3, wherein the obtained similarity matrix is used as input for projection, the track data points of all orders of the networked car appointment are projected into a two-dimensional space, track clusters with similar attributes are extracted, and a VMSP algorithm is used for extracting frequently-occurring subsequences of travel paths in the track clusters as key paths, and the method comprises the following steps:

further dividing the path of the order track, projecting the calculated difference matrix serving as input by using a projection method and a t-SNE algorithm, and selecting a key path in different clusters according to the projection result for analysis; for two data points x in a high dimensional space_iAnd x_j，x_iSelecting x by conditional probability p (j | i)_jAs its neighboring points, p (j | i) is defined as follows:

wherein sigma_iIs represented by x_iGeneralizing the conditions in the low dimensional space for the variance of the Gaussian distribution of the center pointsThe rate is represented by q (j | i), and the variance of all Gaussian distributions is set simultaneously

In this case, q (j | i) is:

minimizing the difference of two probability distributions in the same event space, using a cost function F of:

the t-SNE considers the neighborhood relationship, so that data points with close distance in a high-dimensional space are closer in a low-dimensional space, and data points with far distance are farther in the low-dimensional space;

and taking the track sequence in the cluster as the input of the VMSP algorithm, and extracting the frequent subsequence meeting the minimum support counting as a key path.

5. The method according to claim 1, wherein the influence factors related to the driver path selection are counted for each path, the subjective selection of the user on each path related factor is obtained through a weight model, and the importance degree of different factors on ranking results is analyzed, specifically comprising the following processes:

counting the number of orders by using a Ranking SVM through different paths selected by a user circle as initial sequencing, and obtaining the weight of a group of influence factors according to the initial sequencing;

using the number of the network appointment orders in each path as an initial sequence to generate sequencing marking data; the Ranking SVM model takes all combinations of paired difference vectors as training examples;

using the number of network appointment vehicle orders as initial sequencing and training a Ranking SVM model, obtaining a weight vector w, sequencing data points according to values of attribute weights, and obtaining Ranking scores of the data points; and obtaining the contribution of the attribute value to the ranking score of the data point according to the contribution value of the data point attribute.

6. An interactive path selection potential factor visual analysis system is characterized by comprising a traffic flow overview module, an interactive road sequence extraction and key path extraction module and a path selection factor exploration module;

the traffic flow overview module is used for counting traffic flow according to the driving track, utilizing the whole space-time distribution of the cellular map and the time sequence flow evolution diagram overview flow, exploring the traffic flow evolution condition in the region by combining a clustering algorithm and dividing a time slice;

the interactive road sequence extraction and key path extraction module is used for firstly calculating the similarity of tracks, then extracting track clusters, analyzing frequent subsequences of the road sequence as key paths by using a VMSP algorithm, and screening order tracks meeting the key paths for statistics;

the exploration module of the path selection factors is used for analyzing potential factors influencing driver selection and relevant factors in different paths.

Images