Estimating Latent People Flow without Tracking Individuals

1 Introduction

With recent advances in wireless and mobile networks, location information of people can be recorded in a variety of spaces such as exhibition halls, shopping malls, amusement parks, and urban cities. It is important to understand people's mobility patterns in these spaces, because it provides useful knowledge for optimizing navigation systems [Huang and Gartner, 2010], travel route recommendation [Kurashima et al., 2010], location-based mobile advertising [Dhar and Varshney, 2011], urban planning [Yuan et al., 2012], and disaster management [Song et al., 2014]. For example, analyzing the routes of people helps to guide them to the locations of interest, and determine which advertisement to serve to the visitors to suit their current locations.

Many statistical methods that analyze trajectory data have been proposed to understand people's mobility patterns [Giannotti et al., 2007; Monreale et al., 2009; Zhuang et al., 2017]. Trajectory data is a set of location points with time stamps for each individual (e.g., pedestrian, car, bike). However, since privacy concerns are increasing, location information of people is often aggregated, making the tracking of individuals impossible [Chow and Mokbel, 2011]. Aggregated data can also be obtained directly from people counting systems that use various sensors such as video cameras [Chan et al., 2008] and inductive-loop traffic detectors [Klein, 2001]. These systems have been recently developed for low-cost and large-scale people count data collection. Giving the preference for data aggregation, existing methods that analyze trajectory data are inapplicable. Therefore, estimating latent people flows, i.e., transition populations between locations, from only aggregated data is of critical importance in understanding people's mobility patterns while protecting privacy.

The aggregated data considered consist of incoming and outgoing counts at each location and each time step as shown in Figure 1. For example, in an exhibition hall, we may be able to obtain only counts of pedestrians entering or leaving each event booth, and we cannot know the history of locations visited by each pedestrian. Other examples include pedestrian data for each attraction in an amusement park [Du et al., 2014], each store in a shopping mall [Senior et al., 2007], and traffic data for intersections [Kumar et al., 2013].

The collective flow diffusion model (CFDM) was proposed to estimate transition populations between locations from aggregated data [Kumar et al., 2013]. CFDM is learned by maximizing a likelihood subject to constraints that represent people flow conservation. The constraint states that all people who leave a location at time step t always arrive at another location at the next time step, t+1. However, this assumption is too restrictive for many real-world applications, mainly because we do not always have a large enough number of sensor devices to cover large-scale spaces: People might be moving through passages where no sensor devices are placed at an observation time step. In that case, the people are not observed in any location, and CFDM fails to estimate transition populations accurately as it assumes that everyone is in one or other of the observed locations at the next time step.

The purpose of this paper is to robustly estimate unobserved transition populations between locations in practical situations, that is, the observation range is limited and some people are not observed in any location in some time periods. In order to achieve our purpose, we propose a new probabilistic model that incorporates people's travel duration between locations. This is, however, quite challenging to implement, because travel duration between locations is not present in the aggregated data, and, moreover, people are heterogeneous so travel duration depends on the individual. For example, in an exhibition hall, some people might directly visit their next location, but others might take a rest before arriving at another location; in an urban city, moving speeds might depend on the means of transport (e.g., walking, bike, car).

With the proposed model, the temporal dynamics of people flows are assumed to be probabilistic diffusion processes over a network, where the nodes are locations (e.g., booths and shops) and the edges are paths between these locations (e.g., passages and roads). People diffuse from node to node according to transition probabilities that depend on their locations. Since the transition populations between locations are not observed, we treat them as latent variables. Our key idea is to treat travel duration as random variable that follows a probability distribution. This enables us to capture the heterogeneity in travel duration among individuals. The distributions of travel duration are incorporated into the constraints that represent flow conservation; they aim to model that people who left one location in one time step and arrived at another location after some delay. We develop an efficient inference algorithm to estimate the transition probabilities, the transition populations, and the travel duration distributions.

We show the effectiveness of our model on real-world datasets, pedestrian location logs from large-scale exhibition halls, and bike trip data and taxi trip data in New York City. First, we show that our model achieves high estimation performance for the transition populations between locations. Second, we show that our model precisely captures the travel duration distributions between locations. Third, by using the estimated transition populations, we show that our model can analyze the routes of pedestrians in exhibition halls that are likely to be chosen by visitors without tracking individuals.

The major contributions of this paper include:

• We propose a probabilistic model that incorporates travel duration distributions for robustly estimating unobserved transition populations between locations from only aggregated data.
• We develop an efficient inference algorithm to learn the transition probabilities, the transition populations, and the travel duration distributions.
• Experiments on multiple real-world datasets show that our proposed model achieves statistically significant improvement over baseline methods.

2 RelatedWork

A number of works have been published recently that use the latest trends (e.g., deep learning) for analyzing aggregated data such as population or inflow and outflow at each location [Hoang et al., 2016; Zhang et al., 2017; Yao et al., 2018]. These works can predict the population or inflow and outflow in the future with consideration of some external factors (e.g., weather). They cannot, however, estimate the transition populations between locations from inflow and outflow, which is the task considered in this paper. The task of estimating the transition populations between locations is important for better understanding people's mobility patterns; for example, it is useful for finding the popular routes of pedestrians in exhibition halls. While the method of [Xu et al., 2017] can recover user trajectories given aggregated data and transition probabilities. The transition probabilities must be manually set by using other information such as distances between locations. In other words, the method cannot estimate the transition populations between locations from only aggregated data. Different from that method, our model can estimate not only the transition populations but also transition probabilities from only aggregated data. What is more, our model also enables us to estimate the travel duration distributions, a function not considered in the previous method.

Collective graphical models (CGMs) [Sheldon and Dietterich, 2011] have been recently developed as a general framework for analyzing aggregated data. The models have been applied for modeling contingency tables [Sheldon and Dietterich, 2011] and bird migration [Sheldon et al., 2008]. Prior works provide efficient inference techniques for CGMs based on maximum a posteriori [Sheldon et al., 2013], MCMC sampler [Sheldon and Dietterich, 2011], message passing [Sun et al., 2015], and variational Bayesian inference [Iwata et al., 2017]. The collective flow diffusion model (CFDM) [Kumar et al., 2013] is the first application of efficient inference techniques developed for CGMs to the transportation domain. By maximizing a likelihood subject to constraints that represent people flow conservation, this model can estimate transition populations between locations from only aggregated data [Kumar et al., 2013; Du et al., 2014]. However, CFDM does not consider people's travel duration between locations, which is important for modeling the temporal dynamics of people flows. The proposed model is an extension of CFDM, and incorporates travel duration distributions into the constraints that represent flow conservation. Our model can estimate the transition populations between locations with consideration of the travel duration. Therefore, our model more precisely estimates transition populations between locations than previous models.

Information diffusion models are related to our work, because their main goal is to estimate latent flows of a piece of information over a network. These models have been used for analyzing the spread of information [Rodriguez et al., 2011; Kurashima et al., 2014] and user influence [Iwata et al., 2013; Tanaka et al., 2016] over social networks. These models incorporate a continuous time distribution to model the temporal dynamics of information flows, with the aim of describing the spread of information from node to node with delays over time. However, in analyzing information flows, it is not necessary to consider flow conservation, a critical factor in modeling the temporal dynamics of people flows based on aggregated data. Our model can infer latent people flows from only aggregated data by considering the flow conservation constraints that incorporate travel duration distributions.

3 ProblemFormulation

In this section, we detail the aggregated data considered here, and define our problem of estimating latent people flows. The notations used in this paper are listed in Table 1.

Aggregated data: We illustrate an example of aggregated data for the three locations in the upper part of Figure 2. The data consist of incoming and outgoing counts at each location and each time step. Let N out t,i be the count of outgoing people from location i at time step t, and N in t,i be the count of incoming people to location i at time step t. Suppose that we are given a set of outgoing counts Nout = {N out t,i |t = 0, . . . , T-1, i ∈ V} and a set of incoming counts Nin = {N in t,i |t = 1, . . . , T, i ∈ V}, where T is the number of observation time steps and V is the set of locations. The aggregated data of individuals (e.g., pedestrians, cars, bikes) can be gathered using various methods such as Wi-Fi [Musa and Eriksson, 2012], Bluetooth [Kotanen et al., 2003], and video-based people counting systems [Chan et al., 2008].

Problem: Our problem of estimating latent people flows, i.e., transition populations between locations, is formulated as follows. Figure 2 illustrates the studied problem for the case of three locations. Suppose that we have a set of incoming and outgoing counts at each location and each time step. We would like to estimate the transition population between locations at each time step, Mtij , which is the number of people who left location i at time step t and whose next location was j. Our goal is to infer a set of transition populations M = {Mtij |t = 0, . . . , T - 1, i ∈ V, j ∈ Ei}, where Ei is the set of locations that are accessible from location i; people in location i can move only to the linked locations j ∈ Ei.

4 Model

We propose a probabilistic model that incorporates people's travel duration between locations for estimating unobserved transition populations between locations from only aggregated data. Modeling the travel duration between locations is expected to estimate the transition populations more robustly in practical situations, that is, the observation range is limited and some people are not observed in any location in some time periods.

In the proposed model, the temporal dynamics of people flows are assumed to be probabilistic diffusion processes over a network, where the nodes are locations and the edges are paths between these locations. If the network structure such as road networks or a set of neighbor information is unknown, our model works by assuming a complete graph among locations. We assume that people diffuse from node to node in accordance with location-dependent transition probabilities. Let θij ≥ 0 be the transition probability that people leave location i and move to location j, where ∑j∈Ei θij = 1. Given the outgoing count N out t,i and the transition probabilities θi = {θij |j ∈ Ei}, transition population Mti = {Mtij |j ∈ Ei} is given by the following multinomial distribution,

Since we cannot obtain the tracking information of individuals in our aggregated data setting, Mti is unobserved. Therefore, we treat it as a latent variable. Transition population Mti satisfies the following two relations that represent outgoing and incoming flow conservation:

The outgoing flow conservation (2) indicates that the sum of people leaving location i at time step t equals the observed outgoing count at the same time step. The incoming flow conservation (3) indicates that the weighted sum of people leaving location j before time step t equals the observed incoming count at time step t. Weight F(∆t,τ ; αji) is travel duration probability, which is the probability that people who left location j at time step τ arrive at location i at time step t. Here, ∆t,τ = t - τ is travel duration and αji is a parameter of the probability distribution. Details of F(∆t,τ ; αji) are given in the following paragraphs. The travel duration is treated as a random variable that follows the probability distribution; it is not a point estimate. This enables us to capture the heterogeneity in travel duration among individuals.

To derive the travel duration probability F(∆t,τ ; αji), we first introduce continuous travel duration distribution f(∆; αji) as the probability density function of travel duration ∆ from location j to i given parameter αji, where ∆ > 0 is a continuous random variable. Note that our model does not depend on the particular choice of the travel duration distribution. The travel duration probability F(∆t,τ ; αji) is calculated by the following integral of f(∆; αji) over the interval from ∆t,τ - 1 to ∆t,τ :

Though our model can use any distribution as f(∆; αji), for simplicity we consider the well-known one-parameter distribution, i.e., Rayleigh distribution, which is widely used for assessing the duration time in various fields such as user modeling [Wang et al., 2008] and information diffusion modeling [Rodriguez et al., 2011]. Figure 3 illustrates an example when using the Rayleigh distribution. The travel duration distribution is as follows:

the red line in Figure 3. Here, αji > 0. The travel duration probability is given by

the red area in Figure 3: The probability that people who left location j at time step τ arrive at location i at time step t.

5 Inference

Given outgoing counts Nout and incoming counts Nin , we estimate the latent transition populations M, the transition probabilities Θ = {θi|i ∈ V}, and the parameters of travel duration distributions A = {αji|j ∈ V, i ∈ Ej} by maximizing the likelihood with the flow conservation constraints. The log-likelihood of M is given by

where logNti! is omitted since it does not depend onM, and we employ Stirling's approximation, log n! ≈ n log n-n, in order to calculate logMtij! efficiently [Sheldon et al., 2013]. The parameters are estimated by maximizing the approximate log-likelihood (7) subject to constraints (2) and (3). The constraints might not strictly hold in real-world data, because the observations are noisy. To handle noisy observations, we treat the constraints as soft constraints, where the squared difference between the left- and right-hand sides in each of (2) and (3) are minimized. Then, the objective function to be maximized is described as follows:

Here, λ ≥ 0 is a hyperparameter that controls the penalty for violating the constraints and ∥ · ∥ is the Euclidean norm. We update each parameter M, Θ and A alternately as described in the following paragraphs.

Update of M: Given current estimates ˆΘ and ˆA, we arrive

Algorithm 1: Inference procedure for our model.

Input : Nin , Nout , V, {Ei}i∈V, T, λ Output: M, Θ, A 1: InitializeM, Θ, A 2: repeat 3: UpdateMby solving (9) 4: for i ∈ V do 5: for j ∈ Ei do 6: Update θij by (10) 7: end for 8: end for 9: Update A by solving (11) 10: until Convergence

at the following optimization problem:

We solve the optimization problem by using the L-BFGS-B method [Byrd et al., 1995].

Update of Θ: The estimates of Θ are obtained in closed form by maximizing (8) given current estimates ˆM as follows:

Update of A: Given current estimates ˆMand ˆΘ, we solve the following optimization problem:

by using the L-BFGS-B method [Byrd et al., 1995]. We iteratively update each parameter until the value of (8) converges. Our inference procedure is shown in Algorithm 1, which always converges and guarantees that the local optima of the respective parameters are obtained by setting λ to a fixed value.

Validation of λ: Hyperparameter λ can be determined by the following validation procedure: (a) learn the model parameters by Algorithm 1 with each candidate value of λ; (b) predict the incoming counts at the next time step; (c) choose the value based on prediction performance in the training data. Given the preceding outgoing counts, the predicted incoming counts in location i at the next time step are given by

6 Experiments

6.1 Data Description

We evaluated the proposed model using real-world pedestrian location logs collected in exhibition halls. The data was collected at an event that attracted large crowds, Niconico Chokaigi 2016 1 , held at Makuhari Messe located near Tokyo, Japan from 10:00 to 18:00 on April 29th. The event site was composed of four exhibition halls, Hall 1, Hall 2, Hall 3 and Hall 4 with sizes of 186.3m × 124.8m, 183.2m × 124.8m, 127.6m × 124.8m, and 190.9m × 108.3m, respectively. The number of event booths, |V |, in Hall 1, Hall 2, Hall 3 and Hall 4 were 38, 27, 10, and 9, respectively. We gathered pedestrian location logs using Bluetooth beacons which were placed at each booth. The technology enables us to observe the times at which each user entered or left the observation range (at most 10 - 15 meters). The data consist of 3,727 mobile users who agreed to provide detailed information of location over time. The original data contains time stamps of arrival and departure at booths for each user; users can be tracked over time. Note that the tracking information of users was used only for evaluating the estimation performance for transition populations and travel duration probabilities; we did not use the tracking information in the inference process. In this experiment, we created aggregated incoming and outgoing pedestrian counts at each booth, where the time interval was 3 minutes. The number of observation time steps was 160. Ei was a set of edges assuming a complete graph for all datasets. The total sum of incoming and outgoing pedestrians at all booths in each hall are shown in Table 2.

To additionally validate the performance of our model, we used two public datasets, bike trip data 2 and taxi trip data 3 in New York City. The data is a set of trip records consisting of: trip id, pickup location, dropoff location, pickup date and time, and dropoff date and time. Note that the data consist of location information only when people started and finished the trips; the trajectories during the trips are not recorded. We used the data from 8:00 to 24:00 on March 1st and June 1st, and created gridded incoming and outgoing count data, where the time interval in both datasets was 10 minutes. The number of observation time steps was 96. The grid sizes in the bike trip data and taxi trip data were 2km × 2km (12 × 12 grid cells) and 3km × 3km (18 × 18 grid cells), respectively. Here, we omitted grid cells if their incoming and outgoing counts were lower than a threshold. Then, bike trip data and taxi trip data held 11 and 14 grid cells, respectively. Ei was a set of edges assuming a complete graph for all datasets. The total sum of incoming and outgoing bikes/taxis at overall grid cells on each date are shown in Table 2.

6.2 Quantitative Evaluation

Transition Population Estimation

We evaluated our model in terms of its performance in estimating the transition populations M. The evaluation metric is the following normalized mean absolute error (NMAE) in transition populations:

1 http://www.chokaigi.jp/2016/en/

2 https://www.citibikenyc.com/system-data

3 http://www.nyc.gov/html/tlc/html/about/trip record data.shtml

where M ⋆ tij is the true transition population leaving location i at time step t and whose next location is j; ˆMtij is its estimate. We compared our proposed model with the collective flow diffusion model (CFDM) [Kumar et al., 2013]. Different from our model, CFDM does not consider travel duration between locations. In addition, we compared our proposed model with the following two baseline methods: Popularity and Uniform methods. Popularity assumes that people move to other locations in proportion to location popularity regardless of current locations; the estimated transition population is given by

Uniform estimates transition populations using a discrete uniform distribution; it assumes that people move to neighbor locations with equal probability 1/|Ei|. For our model, hyperparameter λ was set to the best value based on the validation procedure described in Section 5; λ was chosen from 0.1, 0.2, 0.5, 1, 2, and 5. We used a Rayleigh distribution for modeling travel duration distribution as shown in Section 4.

Table 3 shows NMAE L1 of the proposed model, CFDM, Popularity and Uniform. For all datasets, the proposed model performed better than the other methods, and the differences between our model and CFDM were significant (t-test, p < 0.01). We found similar results using other evaluation metrics (e.g., MAE, RMSE). The upper parts of Figure 4(a) and 4(b) provide a heatmap visualization of the transition matrix for the bike trip data (Jun.1) and taxi trip data (Jun.1), respectively. The transition matrix is the total number of bikes/taxis that moved between each pair of origin and destination locations; its elements were calculated as follows: Mij = ∑T-1 t=0 Mtij. The true matrix is shown on the left and the estimate of our model is shown on the right. As shown, our model accurately estimated the transition populations between locations. Qualitative comparisons of the estimated transition populations in pedestrian data are described at length in Section 6.3.

Travel Duration Probability Estimation

We evaluated the performance of estimating travel duration probabilities. We used the mean Kullback-Leibler (KL) divergence between the true and estimated travel duration probabilities over all pairs of locations as the evaluation metric:

where P ⋆ (∆) and F (∆; ˆαji) are the true travel duration probability and the estimate of our model, respectively.

Table 4 shows the mean KL divergence L2 of the proposed model and CFDM. In CFDM, the travel duration probability equals 1 if ∆ = 1 and 0 otherwise. As shown in Table 4, the proposed model achieved lower mean KL divergence values for all datasets. The results show that our model precisely estimated the travel duration probabilities. The lower parts of Figure 4(a) and 4(b) show visualization examples of travel duration probability, F(∆; αji), specified by white asterisk (∗) in the corresponding upper heatmap. Red line represents the travel duration distribution, f(∆; αji), estimated by our model. As shown, our model well estimated the travel duration distributions and so allows us to capture the heterogeneity in travel duration among individuals.

As shown in Table 3 and 4, our model achieved better performance in estimating both transition populations and travel duration probabilities. These results indicate that incorporating the people's travel duration into the model is important in estimating latent people flows.

6.3 Qualitative Evaluation

Figure 5 visualizes the estimated pedestrian flows in Hall 1 and Hall 2 from the pedestrian data. We illustrate the true pedestrian flow on the left in Figure 5, and the estimates of the proposed model, CFDM, Popularity and Uniform on the right in Figure 5. Here, the red dots represent the locations of booths, and the directed edges represent the pedestrian flows between locations. The edge widths are proportional to the total numbers of pedestrians that moved between each pair of booths. Note that we omitted those edges whose transition populations were lower than a threshold, and bidirectional edge widths are proportional to the average of the transition populations between the pair of locations. As shown in Figure 5, the proposed model better discerned the pedestrian flows than the other methods. CFDM tends to output some false flows. This is reasonable because, as was explained earlier, CFDM is based on the unreal assumption that all pedestrians who left a location at one time step should arrive at another location at the next time step. In other words, CFDM fails to estimate the pedestrian flows between locations when travel duration is significant. Our model, on the other hand, could more precisely estimate the pedestrian flows because it considers travel duration. The visualization results are useful for optimizing navigation systems and strategies of locationbased advertising. For example, discovering popular routes of pedestrians yields better route recommendations.

7 Conclusion

This paper proposed a probabilistic model that incorporates people's travel duration between locations for estimating latent people flows, i.e., transition populations between locations, from only aggregated data. Incorporating the travel duration into the model enables us to robustly estimate transition populations in practical situations, that is, the observation range is limited and some people are not observed in any location in some time periods. Since travel duration is treated as a random variable that follows a probability distribution, our model can capture the heterogeneity in travel duration among individuals. The inference algorithm presented herein allows us to infer transition probabilities, transition populations, and travel duration distributions. We used three real-world datasets, pedestrian data, bike trip data, and taxi trip data, to confirm that our model can precisely estimate the transition populations between locations. Our future work is to conduct extended experiments considering temporal factors (e.g., time-of-day) and external factors (e.g., weather).