CN115994313A - Crowd movement modeling method and device based on visiting location clustering - Google Patents

Abstract

The present application discloses a crowd movement modeling method and device based on visiting location clustering, which belongs to the field of trajectory prediction. The method includes: obtaining the visiting locations and visiting location clustering of multiple individuals in the crowd based on historical crowd moving trajectory data; Crowd movement characteristics are extracted by visiting locations, visiting location clusters and historical crowd movement trajectories, and model parameters of the crowd movement model are generated according to the crowd moving characteristics. The conditional probability distribution between them; the set number of simulated individuals and the target duration are input into the crowd movement model to generate the movement trajectories of multiple simulated individuals within the target duration. This application can not only predict the individual's movement trajectory, but also predict the individual's visit patterns between visit location clusters and within visit location clusters, and reproduce the internal relationship between visit locations and visit location clusters, filling the existing model flaws.

Description

Crowd movement modeling method and device based on visiting location clustering

technical field

The present application relates to the technical field of trajectory prediction, in particular to a crowd movement modeling method and device based on clustering of visiting locations.

Background technique

In recent decades, due to the increasing availability of big data on crowd movement trajectories such as call record data, mobile device location data, and social media check-in data, crowd movement trajectory processing methods and crowd movement modeling methods have developed rapidly, and It has achieved more and more applications in solving practical problems such as urban planning, traffic engineering, and disease transmission control. The crowd movement modeling method can simulate the movement trajectories of individuals in the city, and make these movement trajectories conform to the basic laws of crowd movement at the individual and group levels found in empirical data, and then reproduce the key characteristics of urban crowd movement. If it is impossible to accurately predict the law of crowd movement and reproduce the key characteristics of crowd movement, it will be impossible to provide accurate reference for the rational formulation of relevant policies.

A series of fine-grained models of crowd movement have been proposed in existing studies, among which the Exploration and Preference Return (EPR) model and its variants, such as d-EPR model and PEPR model, are the most influential and widely used crowd models. Mobile model. However, in the existing crowd movement models, individuals move between independent locations, and the spatial distribution characteristics of these visited locations and their internal connections are completely ignored. However, in fact, individuals’ visit locations will form clusters in physical space, and these visit location clusters have rich semantic features, which are usually associated with certain types of behaviors of individuals and constitute various activity spaces in individuals’ daily life (such as residential activity space, work activity space, entertainment activity space, etc.), and affects the movement of individuals. Modeling crowd movement from the perspective of visiting location clusters instead of independent visiting locations can accurately reproduce the movement rules of individuals between visiting location clusters and within each visiting location cluster. On the one hand, it can also establish a connection between people's mobile behavior and urban space, which helps to understand the interaction process between people and various urban spaces.

To sum up, how to take into account the impact of visiting location clustering on individual movement in crowd movement modeling is one of the problems to be solved in the current crowd movement modeling method.

Contents of the invention

This application provides a crowd movement modeling method and device based on clustering of visiting locations, which can not only predict the movement trajectory of individuals, but also predict the visiting patterns of individuals between clusters of visiting locations and within clusters of visiting locations. The intrinsic connection between visited places and visited place clusters fills the gaps of existing models.

The embodiment of the first aspect of the present application provides a crowd movement modeling method based on clustering of visiting places, including the following steps: acquiring visiting places and visiting place clusters of multiple individuals in the crowd based on historical crowd movement trajectory data; according to the Extracting crowd movement features from the visiting locations, the clustering of the visiting spots, and the historical crowd movement trajectories, and generating model parameters of the crowd movement model according to the crowd movement features, wherein the crowd movement features include all individual visited places The conditional probability distribution between the visiting frequency sorting and the visiting frequency sorting of the visiting location clusters to which it belongs; input the set number of simulated individuals and the target duration into the crowd movement model, and generate the number of people within the target duration through the crowd movement model The trajectory of a simulated individual.

Optionally, in an embodiment of the present application, the acquiring visit locations and visit location clusters of multiple individuals in the crowd based on historical crowd movement trajectory data includes: a plurality of position recording points, calculate the current speed of the plurality of position recording points, and mark the position recording points whose current speed is less than or equal to the preset speed threshold as staying position recording points; cluster all the staying position recording points, and calculate The single stay time of the individual in each location record point cluster, and determine the individual's visit location according to the single stay time, wherein, the coordinates of the visit place are the center of the corresponding location record point cluster; All the visiting locations are clustered to obtain the visiting location clusters.

Optionally, in an embodiment of the present application, extracting crowd movement features according to the visiting places, the clustering of the visiting places and the historical crowd movement trajectory includes: according to the order of individual visits to various visiting places and each According to the arrival time and departure time of each visit, calculate the stay time of each individual visit, and count the stay time distribution of all individuals; according to the order of visits by individuals to each visit location, calculate the movement of each individual visit Step length, and count the distribution of moving steps of all individuals; According to the historical movement trajectory of the individual, the exploration probability of the individual under different numbers of visited locations is counted; According to the historical movement trajectory of the individual, the random exploration of the individual under different numbers of visited locations is counted Probability: sort all the visit locations of the individual and the visit frequencies of all visit location clusters, and calculate the conditional probability distribution between the visit frequency rankings of all the visit locations of the individual and the visit frequency rankings of the visit location clusters to which they belong.

Optionally, in one embodiment of the present application, generating the movement trajectories of multiple simulated individuals within the target duration through the crowd movement model includes: selecting the initial position of each simulated individual, and setting the initial time is 0; the residence time of the simulated individual is extracted according to the movement characteristics of the crowd, and the exploration behavior or return behavior is performed according to the exploration probability of the simulated individual; when the simulated individual is an exploration behavior, according to the simulated individual’s Random exploration probability to perform random exploration behavior or cluster exploration behavior; when the simulated individual performs random exploration behavior, extract the moving step according to the movement characteristics of the crowd, and determine the simulation within the range of the moving step The individual explores and visits any location other than the cluster of visited locations; when the simulated individual performs the exploration behavior within the cluster, the cluster of locations to be visited by the simulated individual is determined according to the order of visit frequency of the cluster of visited locations. class, extract the moving step size according to the movement characteristics of the crowd, and within the range of the moving step size, determine and visit any exploration place of the simulated individual in the cluster of places to be visited; When the simulated individual is in the returning behavior, the cluster of places to be visited by the simulated individual is determined according to the visit frequency of the clustered places to be visited, and the cluster of places to be visited by the simulated individual is determined according to the visit frequency of the places to be visited within the cluster of places to be visited. Visit the location and conduct the visit; calculate whether the total stay time of the simulated individual at multiple visit locations is greater than or equal to the target duration, if the total stay time is greater than or equal to the target duration, then according to the multiple visit locations The location and visit sequence generate the movement track of the simulated individual, if the total stay time is less than the target duration, continue to explore or return according to the exploration probability of the simulated individual until the total stay time is greater than or equal to The target duration.

The embodiment of the second aspect of the present application provides a crowd movement modeling device based on clustering of visiting places, including: an acquisition module, configured to acquire visiting places and visiting place clusters of multiple individuals in the crowd based on historical crowd movement trajectory data; A parameter generating module, configured to extract crowd movement characteristics according to the visited locations, clusters of the visited locations, and the historical crowd movement trajectories, and generate model parameters of a crowd movement model according to the crowd movement characteristics, wherein the crowd The movement characteristics include the conditional probability distribution between the visit frequency rankings of all the visiting places of the individual and the visiting frequency rankings of the visiting place clusters to which they belong; the trajectory generation module is used to input the set number of simulated individuals and target duration into the crowd movement model, using the crowd movement model to generate movement trajectories of multiple simulated individuals within the target duration.

Optionally, in an embodiment of the present application, the acquisition module includes: an identification unit, configured to determine a plurality of position recording points in the individual trajectory according to the historical crowd movement trajectory data, and calculate the plurality of position record points Record the current speed of the point, and mark the position record point whose current speed is less than or equal to the preset speed threshold as the stay position record point; the first clustering unit is used to cluster all the stay position record points, and calculate the individual’s time at each position A single stay time in the record point cluster, according to the single stay time to determine the individual's visit location, wherein the coordinates of the visit place is the center of the corresponding position record point cluster; the second clustering unit is used for All the visit places of the individual are clustered to obtain the visit place clusters.

Optionally, in one embodiment of the present application, the parameter generation module includes: a first extraction unit, configured to calculate the time of each visit according to the individual's visit sequence to each visit location and the arrival time and departure time of each visit. The residence time of each individual visit, and count the distribution of the residence time of all individuals; the second extraction unit is used to calculate the moving step size between each visit of each individual according to the order of visits by individuals to each visit location, and The distribution of moving steps of all individuals is counted; the third extraction unit is used to count the exploration probability of individuals under different numbers of visited locations according to the historical moving trajectory of the individual; the fourth extraction unit is used to calculate the statistical The random exploration probability of individuals under different numbers of visiting locations; the fifth extraction unit is used to sort all the visiting locations of the individual and the visiting frequencies of all visiting locations clustered, and calculate the ranking of the visiting frequencies of all visiting locations of the individual and their belonging Conditional probability distribution among visit frequency orderings for clusters of visit locations.

Optionally, in one embodiment of the present application, the trajectory generation module includes: an initial unit, configured to select the initial position of each simulated individual, and set the initial moment to 0; an exploration unit, configured to The crowd movement feature extracts the residence time of the simulated individual, and performs exploration behavior or return behavior according to the exploration probability of the simulated individual; the exploration unit is also used to The random exploration probability of the simulated individual performs random exploration behavior or cluster exploration behavior; the exploration unit is also used to extract the moving step according to the movement characteristics of the crowd when the simulated individual performs random exploration behavior, and Within the range of the moving step, it is determined that the simulated individual is at any exploration location outside the cluster of the visited locations and visits; the exploration unit is also used for when the simulated individual performs an exploration behavior within the cluster , determine the location clusters to be visited by the simulated individuals according to the visit frequency ranking of the visited location clusters, extract the moving step size according to the movement characteristics of the crowd, and determine the simulated individual within the range of the moving step size Explore and visit any location within the cluster of locations to be visited; the exploration unit is further configured to determine the simulated individual's visit frequency according to the visit frequency of the visited location cluster when the simulated individual is returning. Clustering of places to be visited, determining and visiting places to be visited by the simulated individual according to the visit frequency of the places to be visited in the cluster of places to be visited; an output unit for calculating the number of places to be visited by the simulated individual in multiple places to visit Whether the total stay time is greater than or equal to the target duration, if the total stay time is greater than or equal to the target duration, then generate the movement trajectory of the simulated individual according to the positions and visit sequences of the multiple visit locations, if the total stay time is greater than or equal to the target duration If the stay time is less than the target duration, continue to perform exploration or return behavior according to the exploration probability of the simulated individual until the total stay time is greater than or equal to the target duration.

The crowd movement modeling method and device based on clustering of visited places in the embodiment of the present application, by identifying visiting place clusters from individual movement trajectories, using individual movement behaviors at the visiting place clustering level to obtain crowd movement characteristics, except for stay time , moving step size, the variation of the individual’s exploration probability with the number of visited locations, and the variation of the individual’s random exploration probability with the number of visited locations, this application also innovatively considers the ordering of the individual’s visit frequencies of all visited locations and their The conditional probability distribution among the visit frequency rankings of the visiting place clusters, by considering the conditional probability distribution, this application reflects the internal connection between the visiting places and the visiting place clusters; it describes two important characteristics of individual movement: belonging to Visiting locations clustered with high-frequency visiting locations have a higher probability of being visited by individuals, and visiting locations with higher visiting frequencies are more likely to appear in high-frequency visiting location clusters; There are obvious deficiencies in the association relationship of visiting location clustering. It further introduces a two-stage decision-making process of individual movement from the perspective of visiting location clusters, which can not only predict the individual's movement trajectory, but also predict the individual's access patterns between visiting location clusters and within visiting location clusters, recurring visits Intrinsically linking clusters of places and visited places fills the gaps of existing models.

Additional aspects and advantages of the application will be set forth in part in the description which follows, and in part will be obvious from the description, or may be learned by practice of the application.

Description of drawings

The above and/or additional aspects and advantages of the present application will become apparent and easy to understand from the following description of the embodiments in conjunction with the accompanying drawings, wherein:

FIG. 1 is a flow chart of a crowd movement modeling method based on visiting location clustering provided according to an embodiment of the present application;

FIG. 2 is a flow chart of obtaining visiting locations and visiting location clusters of multiple individuals in a crowd according to an embodiment of the present application;

FIG. 3 is a flow chart of extracting crowd movement features according to an embodiment of the present application;

FIG. 4 is a flow chart of a method for simulating individual movement trajectories according to an embodiment of the present application;

FIG. 5 is a schematic diagram of a crowd movement model provided according to an embodiment of the present application;

Fig. 6 is an example diagram of a crowd movement modeling device based on visiting place clustering according to an embodiment of the present application.

Detailed ways

Embodiments of the present application are described in detail below, examples of which are shown in the drawings, wherein the same or similar reference numerals denote the same or similar elements or elements having the same or similar functions throughout. The embodiments described below by referring to the figures are exemplary, and are intended to explain the present application, and should not be construed as limiting the present application.

Fig. 1 is a flow chart of a crowd movement modeling method based on visiting place clustering according to an embodiment of the present application.

As shown in Figure 1, the crowd movement modeling method based on visiting location clustering includes the following steps:

In step S101 , based on historical crowd movement track data, the visiting locations and visiting location clusters of multiple individuals in the crowd are obtained.

The historical crowd movement trajectory data can be the crowd movement data of a specific city in the past period of time. The crowd movement trajectory data includes the places where individuals go and the time of arrival and departure. According to the movement track data of the crowd, the visiting locations of multiple individuals in the crowd can be obtained therefrom.

In one embodiment of the present application, as shown in FIG. 2 , as a way of obtaining the visiting locations and visiting location clusters of multiple individuals in the crowd, it includes:

S1011. Determine multiple position record points in the individual trajectory according to the historical crowd movement track data, calculate the current speed of the multiple position record points, and mark the position record points whose current speed is less than or equal to the preset speed threshold as stay position record points.

Specifically, the embodiments of the present application can extract the trajectory of each individual in the historical crowd movement trajectory data, and identify the position record points in the individual's trajectory that are in the stay state, wherein the individual's trajectory is recorded by multiple locations with time stamps Composed of points, the state of the location record point includes the stay state and the moving state.

Define the trajectory of an individual as ,definition is a timestamped location record. The state of the location record can be divided into the stay state and the moving state. The location records belonging to the stay state in , the identification method is as follows:

set a speed threshold (The recommended value is 1.3m/s), scan backward from the first position record point, when the position record point satisfy , the state of the location record point is the stay state, otherwise it is the moving state.

S1012, cluster all the stay location record points, calculate the single stay time of the individual in each location record point cluster, and determine the individual visit location according to the single stay time, wherein the coordinates of the visit location are the corresponding location records Center of point clustering.

Specifically, the embodiment of the present application can use the first clustering algorithm to cluster all location record points in the stay state, count the single maximum stay time of individuals in each location record point cluster, and divide the single maximum stay The location record points whose time is longer than the preset duration are clustered as individual visit locations, and the coordinates of the visit locations are the centers of the corresponding location record point clusters.

The first clustering algorithm can use the DBSCAN (Density-Based Spatial Clustering of Applications with Noise) algorithm, which is a density-based clustering algorithm.

Given a maximum scanning radius and a minimum number of samples (recommended values are 50 m and 2 samples, respectively), the first clustering algorithm is used to cluster all location records belonging to the stay state for a given individual. According to the clustering results, the single maximum stay time of a given individual in each location record point cluster is counted. Keep all location record point clusters with a single maximum stay time greater than the preset duration (can be set to 5 minutes), and each remaining location record point cluster represents a visit location of a given individual, and the coordinates of the visit location are corresponding The center of the location record point cluster.

According to individual trajectories and clustering results, individual trajectories can be expressed as a series of time-stamped visit location records, and further, the arrival time, departure time and visit order of a series of visit locations for a given individual can be determined.

S1013. Cluster all the visit locations of the individual to obtain the visit location clusters.

In the embodiment of the present application, the second clustering algorithm may be used to cluster all the visited places of the individual to obtain the visited place clusters.

The second clustering algorithm can be the HDBSCAN (Hierarchical Density-Based Spatial Clustering of Applications with Noise) algorithm, which is a hierarchical clustering algorithm based on the DBSCAN algorithm.

Given the cluster extraction parameters and the minimum number of samples (recommended values are 1 km and 2), use the second clustering algorithm to cluster all the visit locations of a given individual, and obtain several visit locations of a given individual Clustering, according to the clustering results of visiting places, the affiliation relationship between each visiting place and each visiting cluster of a given individual can be determined.

In step S102, crowd movement characteristics are extracted according to the visiting locations, visiting location clusters, and historical crowd movement trajectories, and model parameters of the crowd movement model are generated according to the crowd movement characteristics, wherein the crowd movement characteristics include the visit frequencies of all the individual visiting locations The conditional probability distribution between the ranks and the visit frequency ranks of the visited place clusters to which they belong.

A series of individual visit locations and visit location clusters are obtained based on the crowd movement trajectory data of a specific city. According to the visit locations, visit location clusters and crowd movement trajectory data, the crowd movement characteristics can be extracted, and then the crowd movement model can be determined according to the characteristics. multiple parameters. Among them, the crowd movement characteristics can include stay time, moving step length, the change of exploration probability with the number of visited places, the change of the ratio of random exploration probability to explored probability with the number of visited places, the order of visit frequency of visited places and the visited places to which they belong. Clustering access frequency sorting relationship, etc.

In one embodiment of the present application, as a method of extracting crowd movement features, as shown in Figure 3, crowd movement features are extracted according to visiting locations, visiting location clusters, and historical crowd movement trajectories, including:

S1021. Calculate the stay time of each individual for each visit according to the visit order of the individual to each visit location and the arrival time and departure time of each visit, and count the stay time distribution of all individuals.

S1022. According to the individual's visit sequence to each visit location, calculate the movement step size between each visit of each individual, and count the movement step length distribution of all individuals.

S1023, according to the historical movement trajectory of the individual, calculate the exploration probability of the individual under different numbers of visited locations.

explore probability With the change of the number of visited places S, the statistical method is as follows: each visit behavior of an individual is defined as an exploration behavior and a return behavior. When an individual visits a place that has never been visited before, the visit behavior is called an exploration behavior; , when an individual visits a previously visited location, the visit behavior is called return behavior.

When the number of places visited by the individual is S, define the probability that the individual will perform exploration behavior in the next visit as the exploration probability of the individual when the number of places visited is S .

For each individual, according to its historical movement trajectory, the exploration probability of the individual given the number S of different visited places is counted value of .

S1024, according to the individual's historical movement trajectory, calculate the random exploration probability of the individual under different numbers of visited locations.

Random Exploration Probability The ratio of the ratio to the exploration probability varies with the number of visited locations S. The statistical method is as follows: each individual exploration behavior is defined as random exploration behavior and cluster exploration behavior. When it does not belong to any of the current visiting place clusters, the exploration behavior is called random exploring behavior; on the contrary, when the visiting place visited by the individual during the exploring behavior belongs to a certain current visiting place cluster, it is called the exploring behavior Behavior for exploring within clusters.

When the number of places visited by the individual is S, define the probability that the individual chooses random exploration behavior in the next visit to explore behavior as the random exploration probability of the individual when the number of visited places is S .

For each individual, according to its historical movement trajectory, the random exploration probability of the individual given the number S of different visiting places is counted value of .

S1025. Sorting all the visit locations of the individual and the visit frequencies of all the visit location clusters, and calculating the conditional probability distribution between the visit frequency rankings of all the visit locations of the individual and the visit frequency rankings of the visit location clusters to which they belong.

The relationship between the visit frequency ranking of a visit location and the visit frequency ranking of the visit location cluster to which it belongs, the statistical method is as follows: Define the number of visits an individual makes to a visit location as the visit frequency of the visit location ;Sort all the visiting places according to their visiting frequency from high to low, define the sorting of a certain visiting place as the visiting frequency sorting of the visiting place .

Define the sum of visit times of individuals to all visit places in a visit place cluster as the visit frequency of the visit place cluster ;Sort all the visit location clusters according to their visit frequency from high to low, define the sort of a visit location cluster as the visit frequency sort of the visit location cluster .

Count the visit frequency sorting of all visit places for each individual and the visit frequency ranking of the cluster of visit places to which it belongs , computing the conditional probability distribution .

The crowd movement feature in the embodiment of the present application innovatively considers the conditional probability distribution between the visit frequency rankings of all the visiting places of an individual and the visiting frequency rankings of the visiting place clusters to which they belong. This distribution can reflect the visiting places and the visiting place clusters Two important characteristics that characterize the movement of individuals: Visiting places that belong to the cluster of high-frequency visiting places have a higher probability of being visited by individuals, and visiting places with higher visiting frequency are more likely to have clusters of high-frequency visiting places. class; and it is proved that the existing models have obvious deficiencies in describing the association relationship between the visiting places and the visiting place clusters to which they belong.

Based on the features extracted above, the model parameters are determined according to the following method value of:

based on dwell time distribution, fitting the distribution middle value;

based on dwell time distribution, fitting the distribution middle number of

Based on the number of visited locations S and the exploration probability relationship, fitting equation middle and value;

Based on the number of visited locations S and random exploration probability relationship, fitting equation middle value;

Sort by visit frequency based on visit location and the visit frequency ranking of the cluster of visit places to which it belongs The conditional probability distribution of ,parameter and The numerical fitting method of is as follows:

Ranking of frequency of visits for a given place visited The value is , to calculate the probability distribution ;

Fitting the exponential distribution given different r _l The value of m in;

based on and m relationship, fitting equation middle and value.

In step S103, the set number of simulated individuals and the target duration are input into the crowd movement model, and the movement trajectories of multiple simulated individuals within the target duration are generated through the crowd movement model.

Optionally, in one embodiment of the present application, the movement trajectories of multiple simulated individuals within the target duration are generated through the crowd movement model, including:

Select the initial position of each simulated individual, and set the initial moment to 0;

Extract the residence time of the simulated individual according to the movement characteristics of the crowd, and perform exploration behavior or return behavior according to the exploration probability of the simulated individual;

When the simulated individual is exploring behavior, perform random exploration behavior or cluster exploration behavior according to the random exploration probability of the simulated individual;

When simulating an individual’s random exploration behavior, extract the moving step according to the movement characteristics of the crowd, and within the range of the moving step, determine the simulated individual’s visit to any exploration location outside the cluster of visiting locations;

When simulating the individual’s exploration behavior within the cluster, determine the location cluster to be visited by the simulating individual according to the visit frequency ranking of the visiting location cluster, extract the moving step according to the movement characteristics of the crowd, and determine the simulating individual within the range of the moving step Explore and visit any place within the cluster of places to visit;

When the simulated individual is in the return behavior, determine the location to be visited cluster of the simulated individual according to the visit frequency of the visited location cluster, and determine and visit the location to be visited by the simulated individual according to the visit frequency of the visited locations within the cluster of places to be visited;

Calculate whether the total stay time of the simulated individual in multiple visit locations is greater than or equal to the target duration, if the total stay time is greater than or equal to the target duration, then generate the movement trajectory of the simulated individual according to the positions and visit sequences of multiple visit locations, if the total stay time is less than Target duration, then continue to explore or return according to the exploration probability of the simulated individual until the total stay time is greater than or equal to the target duration.

As shown in FIG. 4 , the flow of the method for generating the moving trajectories of a certain number of virtual individuals within a period of time is shown. The specific operation steps are as follows:

Set the number of individuals and the target duration of the movement trajectory to be generated:

For each virtual individual, randomly select a location point in the selected city as the initial location of the individual;

Set the initial time to 0, repeat the following steps until the total stay time of the individual exceeds the target time;

Step A: From the distribution extraction dwell time ;

Step B: Individuals take Probability to perform exploration behavior (go to step C), otherwise, perform return behavior (go to step F);

Step C: When the individual performs exploratory behavior, the Probability to perform random exploration (go to step D); otherwise, perform intra-cluster exploration (go to step E);

Step D: When the individual performs random exploration behavior, first from the distribution Extract the move step size ; Then, let the individual start from the current position as the center of the circle, Randomly select a location on the arc of the radius that does not belong to any existing cluster of visited locations to visit; if there is no location on the arc that meets the above requirements, regenerate the moving step and repeat step D;

Step E: When the individual performs the exploration behavior in the cluster, the probability Choose to explore access frequency sorting cluster i for the visiting locations; after determining the visiting location clusters to be explored, from the distribution Extract the move step size ; Then, let the individual start from the current position as the center of the circle, Randomly select a location on an arc of radius that belongs to the selected cluster to visit. If there is no place on the arc that satisfies the above requirements, regenerate the move step and repeat step E;

Step F: When the individual performs the return behavior, first select the visiting location cluster to be returned according to the visiting frequency of all visiting location clusters, and the return probability is proportional to the visiting frequency of each visiting location cluster; then, according to the visiting location clustering The visit frequencies of all visit locations determine the visit locations to be returned, and the return probability is proportional to the visit frequency of each visit location.

This application introduces a two-stage decision-making process for individual movement from the perspective of visiting location clustering, that is, individuals first make a movement decision at the cluster level to decide which visiting location cluster to visit, and then make a moving decision at the visiting location level to decide which one to visit Specific places to visit. As shown in Figure 5, in the crowd mobility model, the influence of visit location clustering on individual mobility exists in both the preference return phase and the exploration phase. In the preference return stage, the individual first decides which visit location cluster to visit according to the visit frequency of all visit place clusters, and then decides which specific visit place to visit according to the visit frequency of all visit place clusters in this cluster: this mechanism reflects The attractiveness of the visiting locations that make up the visiting location cluster affects the return probability of the visiting location cluster. In addition, the individual’s visit frequency to a visiting location is not only affected by its own attractiveness, but also by the visiting location cluster to which it belongs. In other words, the influence of the attractiveness of other nearby visited places; similarly, in the exploration process, the individual first decides which cluster to explore in (or chooses to stay outside all existing clusters explore), and then decide new places to explore within the selected cluster according to the moving step size: this mechanism means that the individual's choice of new places to explore is not completely random as assumed in the EPR model, Rather, it is affected by the existing clustering of visited locations.

In the test, this model was tested on two crowd movement trajectory datasets in Guangzhou and Houston, USA. When testing on the Guangzhou dataset, refer to the time length and sample size covered by the Guangzhou dataset. The number of individuals to generate movement trajectories is set to 17,000, and the target duration is set to 5 months. Based on the parameter fitting results of the Guangzhou data set, the relevant parameters in this model are set as follows: β=0.618, ρ=0.697, γ=0.199, α=0.615, τ=0.595, ω=-2.848, ε=0.578; When testing on the Houston dataset, referring to the time length and sample size covered by the Houston dataset, the number of individuals to generate movement trajectories is set to 17,000, and the target duration is set to 50 weeks. Based on the parameter fitting results of the Houston data set, the relevant parameters in this model are set as follows: β=0.800, ρ=0.647, γ=0.273, α=0.416, τ=0.606, ω=-3.572, ε=0.819. Based on the above tests, the relationship between the visiting locations and the visiting frequency rankings of the clusters they belong to in the human movement trajectories of the two cities can be obtained respectively. By comparing the data sets and the human movement trajectories generated by this model, the visiting locations and the clusters they belong to It can be found that the relationship between the visiting locations generated by this model and the visiting frequency rankings of the clusters they belong to is consistent with the characteristics presented by the data set: that is, the visits belonging to the clusters of high-frequency visiting locations Places have higher visit frequency, and visit places with higher visit frequency are more likely to appear in clusters of high-frequency visit places. However, the existing EPR model has obvious deficiencies in describing the relationship between visiting locations and the ranking of visiting frequencies of the clusters they belong to. In the results generated by the EPR model, the composition of visiting locations of clusters with different visiting frequencies is almost the same, and Visit places with higher visit frequencies have a higher probability of appearing in the low-frequency visit place cluster. The above results prove that this model can successfully reproduce the intrinsic relationship between visiting locations and visiting location clusters in crowd movement, which is significantly improved compared with the existing EPR model. Secondly, by introducing clustering of visiting locations into the model, this model establishes a connection between individual movement and the physical space in the city. It is helpful to further simulate the interaction process between urban residents and various urban spaces.

According to the crowd movement modeling method based on visiting place clustering proposed in the embodiment of the present application, by identifying the visiting place clusters from the individual movement trajectories, the movement behavior of the individual at the visiting place clustering level is used to obtain the crowd movement characteristics, except for the stay time , moving step size, the variation of the individual’s exploration probability with the number of visited locations, and the variation of the individual’s random exploration probability with the number of visited locations, this application also innovatively considers the ordering of the individual’s visit frequencies of all visited locations and their The conditional probability distribution between the visit frequency rankings of the visiting place clusters, by considering the conditional probability distribution, this application can successfully reproduce the internal relationship between the visiting places and visiting place clusters in the crowd movement, and describe the important characteristics of individual movement , to fill in the gaps of existing models. It further introduces a two-stage decision-making process of individual movement from the perspective of visiting location clusters, which can not only predict the individual's movement trajectory, but also predict the individual's access patterns between visiting location clusters and within visiting location clusters, recurring visits Intrinsically linking clusters of places and visited places fills the gaps of existing models.

Next, the apparatus for modeling crowd movement based on clustering of visiting locations proposed according to the embodiments of the present application will be described with reference to the accompanying drawings.

Fig. 6 is an example diagram of a crowd movement modeling device based on visiting place clustering according to an embodiment of the present application.

As shown in FIG. 6 , the apparatus 10 for modeling crowd movement based on clustering of visited locations includes: an acquisition module 100 , a parameter generation module 200 and a trajectory generation module 300 .

Wherein, the acquisition module 100 is configured to acquire the visit locations and visit location clusters of multiple individuals in the crowd based on historical crowd movement trajectory data.

The parameter generation module 200 is used to extract crowd movement features according to the visiting locations, clustering of visiting spots, and historical crowd movement trajectories, and generate model parameters of the crowd movement model according to the crowd movement features, wherein the crowd movement features include all visit locations of individuals The conditional probability distribution between the visit frequency rankings and the visit frequency rankings of the visit location clusters to which they belong.

The trajectory generation module 300 is configured to input the set number of simulated individuals and the target duration into the crowd movement model, and generate movement trajectories of multiple simulated individuals within the target duration through the crowd movement model.

Optionally, in one embodiment of the present application, the acquisition module 100 includes: an identification unit, configured to determine multiple position record points in the individual trajectory according to historical crowd movement track data, and calculate the current speed of the multiple position record points, Mark the position record points whose current speed is less than or equal to the preset speed threshold as the stay position record points; the first clustering unit is used to cluster all the stay position record points, and calculate the individual's position in each position record point cluster A single stay time, according to a single stay time to determine the individual's visit location, where the coordinates of the visit location is the center of the clustering of the corresponding location record points; the second clustering unit is used to cluster all the visit locations of the individual, Get clustering of visiting locations.

Optionally, in one embodiment of the present application, the parameter generation module 200 includes: a first extraction unit, configured to calculate the The residence time of each visit, and count the distribution of the residence time of all individuals; the second extraction unit is used to calculate the moving step size between each visit of each individual according to the order of visits by individuals to each visit location, and count all The individual’s movement step distribution; the third extraction unit is used to count the exploration probability of the individual under different numbers of visited locations according to the individual’s historical movement trajectory; the fourth extraction unit is used to calculate the individual’s historical movement trajectory in different locations. The random exploration probability of the individual under the number of visiting locations; the fifth extraction unit is used to sort all the visiting locations of the individual and the visiting frequencies of all the visiting locations clustered, and calculate the visiting frequency ranking of all the visiting locations of the individual and the visiting locations to which they belong The conditional probability distribution among the visit frequency orderings of the clusters.

Optionally, in one embodiment of the present application, the trajectory generation module 300 includes: an initial unit, used to select the initial position of each simulated individual, and set the initial time to 0; an exploration unit, used to move according to the crowd Feature extraction simulates the individual's stay time, and performs exploration behavior or return behavior according to the exploration probability of the simulated individual; the exploration unit is also used to perform random exploration behavior or clustering according to the random exploration probability of the simulated individual when the simulated individual is an exploration behavior Inner exploration behavior; the exploration unit is also used to extract the moving step according to the movement characteristics of the crowd when the simulated individual performs random exploration behavior, and within the range of the moving step, determine any exploration location of the simulated individual outside the cluster of visiting locations and conduct visits; the exploration unit is also used to determine the location clusters to be visited of the simulated individuals according to the visit frequency ranking of the visited location clusters when the simulated individuals perform cluster exploration behavior, and extract the moving step size according to the movement characteristics of the crowd, and Within the range of the moving step, determine and visit any exploration site within the cluster of locations to be visited by the simulated individual; the exploration unit is also used to cluster the visit frequency according to the visited site when the simulated individual is returning behavior Determine the cluster of places to be visited by the simulated individual, determine and visit the places to be visited by the simulated individual according to the visit frequency of the places to be visited in the cluster of places to be visited; the output unit is used to calculate the total stay of the simulated individual at multiple visited places Whether the time is greater than or equal to the target duration. If the total stay time is greater than or equal to the target duration, the movement trajectory of the simulated individual will be generated according to the location and visit sequence of multiple visit locations. If the total stay time is less than the target duration, continue to be based on the exploration probability of the simulated individual. Perform exploration behavior or return behavior until the total stay time is greater than or equal to the target duration.

It should be noted that, the foregoing explanations on the embodiment of the method for modeling crowd movement based on clustering of visited places are also applicable to the apparatus for modeling crowd movement based on clustering of visited places in this embodiment, and details are not repeated here.

According to the crowd movement modeling device based on visiting place clustering proposed in the embodiment of the present application, by identifying visiting place clusters from individual movement trajectories, the movement behavior of individuals at the visiting place clustering level is used to obtain crowd movement characteristics, except for the stay time , moving step size, the variation of the individual’s exploration probability with the number of visited locations, and the variation of the individual’s random exploration probability with the number of visited locations, this application also innovatively considers the ordering of the individual’s visit frequencies of all visited locations and their The conditional probability distribution between the visit frequency rankings of the visiting place clusters, by considering the conditional probability distribution, this application can successfully reproduce the internal relationship between the visiting places and visiting place clusters in the crowd movement, and describe the important characteristics of individual movement , to fill in the gaps of existing models. It further introduces a two-stage decision-making process of individual movement from the perspective of visiting location clusters, which can not only predict the individual's movement trajectory, but also predict the individual's access patterns between visiting location clusters and within visiting location clusters, recurring visits Intrinsically linking clusters of places and visited places fills the gaps of existing models.

In the description of this specification, descriptions referring to the terms "one embodiment", "some embodiments", "example", "specific examples", or "some examples" mean that specific features described in connection with the embodiment or example , structure, material or characteristic is included in at least one embodiment or example of the present application. In this specification, the schematic representations of the above terms are not necessarily directed to the same embodiment or example. Moreover, the described specific features, structures, materials or characteristics may be combined in any one or N embodiments or examples in an appropriate manner. In addition, those skilled in the art can combine and combine different embodiments or examples and features of different embodiments or examples described in this specification without conflicting with each other.

In addition, the terms "first" and "second" are used for descriptive purposes only, and cannot be interpreted as indicating or implying relative importance or implicitly specifying the quantity of indicated technical features. Thus, the features defined as "first" and "second" may explicitly or implicitly include at least one of these features. In the description of the present application, "N" means at least two, such as two, three, etc., unless otherwise specifically defined.

Any process or method description in a flowchart or otherwise described herein may be understood to represent a module, segment or portion of code comprising one or more executable instructions for implementing a custom logical function or step of a process , and the scope of preferred embodiments of the present application includes additional implementations in which functions may be performed out of the order shown or discussed, including in substantially simultaneous fashion or in reverse order depending on the functions involved, which shall It should be understood by those skilled in the art to which the embodiments of the present application belong.

Claims (8)

1. The crowd movement modeling method based on the access place clustering is characterized by comprising the following steps of:

acquiring access sites and access site clusters of a plurality of individuals in a crowd based on historical crowd movement track data;

extracting crowd movement features according to the access places, the access place clusters and the historical crowd movement tracks, and generating model parameters of a crowd movement model according to the crowd movement features, wherein the crowd movement features comprise access frequency sequences of all access places of individuals and conditional probability distribution among access frequency sequences of the access place clusters to which the individuals belong;

Inputting the set number of simulated individuals and the target duration into the crowd movement model, and generating movement tracks of a plurality of simulated individuals in the target duration through the crowd movement model.

2. The method of claim 1, wherein the obtaining access locations and access location clusters for a plurality of individuals in the crowd based on the historical crowd movement trajectory data comprises:

determining a plurality of position record points in an individual track according to the historical crowd movement track data, calculating the current speeds of the position record points, and marking the position record points with the current speeds less than or equal to a preset speed threshold as stay position record points;

clustering all the stay position record points, calculating single stay time of an individual in each position record point cluster, and determining access places of the individual according to the single stay time, wherein coordinates of the access places are centers of the corresponding position record point clusters;

clustering all access places of the individuals to obtain the access place clusters.

3. The method of claim 1, wherein extracting crowd movement features from the visit location, the visit location cluster, and the historical crowd movement trajectories comprises:

Calculating the residence time of each individual visit according to the visit sequence of each individual visit to each visit place, the arrival time and the departure time of each visit, and counting the residence time distribution of all individuals;

calculating the moving step length between each visit of each individual according to the visit sequence of each individual to each visit place, and counting the moving step length distribution of all the individuals;

counting the exploration probability of the individual under different access places according to the historical movement track of the individual;

according to the historical movement track of the individual, counting random exploration probabilities of the individual under different access places;

sorting all access places of the individual and the access frequencies of all access place clusters, and calculating the access frequency sorting of all access places of the individual and the conditional probability distribution among the access frequency sorting of the access place clusters to which the access places belong.

4. A method according to any one of claims 1-3, wherein generating movement trajectories for a plurality of simulated individuals within the target time period from the crowd movement model comprises:

selecting an initial position of each simulation individual, and setting the initial time to be 0;

extracting the residence time of the simulated individuals according to the crowd movement characteristics, and carrying out exploration behaviors or return behaviors according to the exploration probability of the simulated individuals;

When the simulated individual is the exploration behavior, carrying out random exploration behavior or intra-cluster exploration behavior according to the random exploration probability of the simulated individual;

when the simulated individuals conduct random exploration behaviors, extracting movement step length according to the crowd movement characteristics, and determining any exploration place of the simulated individuals outside the visit place cluster in the movement step length range for visit;

when the simulated individuals perform intra-cluster exploration behaviors, determining a to-be-visited place cluster of the simulated individuals according to the visit frequency sequence of the visit place cluster, extracting the moving step length according to the crowd moving characteristics, and determining any exploration place of the simulated individuals in the to-be-visited place cluster and visiting the exploration place within the moving step length range;

when the simulated individual is in a return behavior, determining a to-be-accessed place cluster of the simulated individual according to the access frequency of the access place cluster, and determining and accessing the to-be-accessed place of the simulated individual according to the access frequency of the access place in the to-be-accessed place cluster;

calculating whether the total residence time of the simulation individual in a plurality of access places is larger than or equal to the target duration, if the total residence time is larger than or equal to the target duration, generating a moving track of the simulation individual according to the positions and the access sequence of the plurality of access places, and if the total residence time is smaller than the target duration, continuing to search or return according to the exploration probability of the simulation individual until the total residence time is larger than or equal to the target duration.

5. A crowd movement modeling apparatus based on access location clustering, comprising:

the acquisition module is used for acquiring access sites and access site clusters of a plurality of individuals in the crowd based on the historical crowd movement track data;

the parameter generation module is used for extracting crowd movement characteristics according to the access places, the access place clusters and the historical crowd movement tracks, and generating model parameters of a crowd movement model according to the crowd movement characteristics, wherein the crowd movement characteristics comprise access frequency sequences of all access places of individuals and conditional probability distribution among the access frequency sequences of the access place clusters to which the individual access places belong;

the track generation module is used for inputting the set number of the simulated individuals and the target time length into the crowd movement model, and generating movement tracks of the plurality of the simulated individuals in the target time length through the crowd movement model.

6. The apparatus of claim 5, wherein the acquisition module comprises:

the identification unit is used for determining a plurality of position record points in the individual track according to the historical crowd moving track data, calculating the current speed of the position record points, and marking the position record points with the current speed less than or equal to a preset speed threshold as stay position record points;

The first clustering unit is used for clustering all the stay position record points, calculating single stay time of an individual in each position record point cluster, and determining access places of the individual according to the single stay time, wherein the coordinates of the access places are the centers of the corresponding position record point clusters;

and the second clustering unit is used for clustering all the access places of the individuals to obtain the access place clusters.

7. The apparatus of claim 5, wherein the parameter generation module comprises:

the first extraction unit is used for calculating the stay time of each access of each individual according to the access sequence of the individual to each access place, the arrival time and the departure time of each access, and counting the stay time distribution of all the individuals;

the second extraction unit is used for calculating the moving step length between each visit of each individual according to the visit sequence of the individual to each visit place and counting the moving step length distribution of all the individuals;

the third extraction unit is used for counting the exploration probability of the individuals under different access places according to the historical movement track of the individuals;

a fourth extraction unit, configured to count random exploration probabilities of individuals under different access location numbers according to historical movement tracks of the individuals;

And a fifth extraction unit, configured to rank all access sites of the individual and access frequencies of all access site clusters, and calculate a conditional probability distribution between the access frequency ranks of all access sites of the individual and the access frequency ranks of the access site clusters to which the access sites belong.

8. The apparatus of any of claims 5-7, wherein the trajectory generation module comprises:

the initial unit is used for selecting the initial position of each simulation individual and setting the initial time to be 0;

the exploration unit is used for extracting the residence time of the analog individuals according to the crowd movement characteristics and carrying out exploration behaviors or return behaviors according to the exploration probability of the analog individuals;

the exploration unit is further used for conducting random exploration behaviors or intra-cluster exploration behaviors according to random exploration probabilities of the simulated individuals when the simulated individuals are exploration behaviors;

the exploration unit is further used for extracting a moving step length according to the crowd moving characteristics when the simulated individuals conduct random exploration behaviors, and determining any exploration place of the simulated individuals outside the visit place cluster and visiting the exploration place within the moving step length range;

The exploration unit is further used for determining a to-be-visited place cluster of the analog individual according to the visit frequency sequence of the visit place cluster when the analog individual performs intra-cluster exploration behaviors, extracting the moving step length according to the crowd moving characteristics, and determining any exploration place of the analog individual in the to-be-visited place cluster and visiting the exploration place within the moving step length range;

the exploration unit is further used for determining a to-be-accessed place cluster of the simulated individual according to the access frequency of the access place cluster when the simulated individual is in return behavior, and determining and accessing the to-be-accessed place of the simulated individual according to the access frequency of the access place in the to-be-accessed place cluster;

the output unit is used for calculating whether the total residence time of the simulation individual at a plurality of access places is greater than or equal to the target duration, if the total residence time is greater than or equal to the target duration, generating a moving track of the simulation individual according to the positions and the access sequence of the plurality of access places, and if the total residence time is less than the target duration, continuing to perform exploration or return according to the exploration probability of the simulation individual until the total residence time is greater than or equal to the target duration.

Images