Understanding crowd dynamics is critical for public safety, transportation optimization, and disease control. Federated learning, a privacy-preserving machine-learning approach, suggests to train models on the devices where data is generated. This maintains server independence for latency-sensitive applications and ensures data privacy as data never leaves the device. Additionally, federated learning facilitates load balancing among participants. Unlike traditional machine learning solutions, federated learning aggregates model parameters of all participating entity. Thus, aggregation in federated learning is challenging. In this paper, we propose Tidal Crowds, a federated crowd flow prediction algorithm, leveraging the benefits of federated learning. Tidal Crowds comes in three parts, data acquisition and processing, machine learning algorithm, and aggregation algorithm. The machine learning algorithm is based on DeepSTN+ that is capable of handling long-range spatial dependencies. Aggregation algorithms include FedAvg and FedProxy. Tidal Crowds aims to examine and enhance prediction accuracy while providing server independence and preserving privacy using federated learning. In our experiments, Tidal Crowds outperforms the original DeepSTN+ in various settings.
1 Introduction
The movement of people in a specific area is referred to as crowd flow. Understanding the underlying causes and patterns of crowd flow helps authorities to provide better services, such as maintaining public safety, preventing the spread of disease, planning public transportation, and more. The crowd-counting approach is performed to detect and count people in a specific area at a specific time. Using this approach, the crowd density of the area can be measured and compared to other areas and to other time slots. Based on the crowd counting approach, inflow and outflow approaches are used to understand how crowds in areas affect each other [4]. Inflow refers to the number of people entering an area, while outflow is the number of people leaving an area.
Crowd flow prediction solutions aim to predict future crowd flows using past crowd flow data. In the case of inflow and outflow approaches, the solution can predict both future inflow and future outflow of an area using past inflow and past outflow. For instance, in two neighboring cities, say A and B, the future inflow of city B may depend on the past outflow of city A. In this paper, we use inflow and outflow approaches on a real-life trajectory data set to predict future crowd flows.
Crowd flow prediction can be improved by adding point-of-interest (POI) information capturing what attracts people to a location, such as entertainment venues, restaurants, and shops.
Crowd flow prediction is often considered a latency-sensitive application, in the sense that users of such applications may require an immediate or near-immediate response from the centralized decision mechanism. For example, if the centralized decision mechanism is inaccessible or saturated in the case of heavy traffic, a user device may have to resort to its local model to find a way out for its user. In general, three types of data are used in crowd-counting solutions: images, videos, and trajectories [10, 11]. The data used in the crowd flow prediction is sensitive data, for example, trajectory data captures the exact locations of users.
1.1 Federated Learning
Federated learning was introduced as a privacy-preserving machine learning approach that decentralizes data, i.e., brings code to data, and distributes the load unlike traditional machine learning approaches [1]. This approach has three important characteristics: it guarantees independence from a central decision mechanism, it guarantees privacy, and it balances the computational load. Each user device has a local copy of the machine-learning model, i.e., user devices do not need to communicate with a central decision mechanism. This eliminates the dependence on a single point of failure for learning, a key feature for latency-sensitive applications. Machine learning is thus performed locally, allowing the load to be shared among all devices. Moreover, user devices do not share local data but, only local parameters. Restricting data sharing inherently ensures the user data privacy by preventing data centralization, which can lead to massive data breaches.
Federated learning solutions often rely on a central server to operate federated learning rounds as follows:
•
user devices perform machine learning locally on their private local data, then send their locally computed model parameters to the central server;
•
the central server aggregates these model parameters and sends the resulting aggregated model parameters back to the user devices;
•
user devices update their local model parameters with the aggregated model parameters.
Central Server performs an aggregation algorithm based on averaging approaches such as FedAvg [7] and FedProxy [8]. In general, at the end of a federated learning round, user devices and the central server have exactly the same machine-learning model. The machine-learning model on user device is referred to as the local model, and the global model on a central server. Model parameters can be the weights of a neural network [1], or the best features of a decision tree [9].
1.2 Federated Crowd Flow Prediction
While there is a growing body of research on federated learning in mobility applications, such as traffic flow prediction [6], POI recommendation [3], and next location prediction [2], federated crowd flow prediction solutions have not been explored extensively. There is a need for more research on federated crowd flow prediction in order to better understand its applicability.
Federated crowd flow prediction can be implemented by having user devices locally train the crowd flow prediction model, using their own trajectory data, and then send their model parameters to a central server. Federated crowd flow prediction performs machine learning locally, which can result in faster response time by distributing the load across user devices. It also improves user privacy by preventing the trajectory data from leaving user devices. This research provides valuable insights into the use of federated learning in crowd flow prediction, which leads to the development of new and more efficient solutions for federated crowd flow prediction.
1.3 Contributions and Roadmap
In this paper, we propose a federated crowd flow prediction solution, Tidal Crowds, and compare it to a traditional machine learning approach. We also test different federated aggregation algorithms, namely FedAvg and FedProxy. More specifically, the contributions of this paper are as follows:
•
we propose a federated crowd flow prediction solution, Tidal Crowds;
•
Tidal Crowds comes in support for POI and two federated aggregation algorihms, FedAvg and FedProxy;
•
Tidal Crowds, thanks to federated learning, ensures independence from a central decision mechanism, guarantees user privacy, and balances the load;
•
we conduct experiments and compare the crowd flow prediction approaches in two settings, traditional machine learning and federated learning, on a real-world data set BikeNYC;
•
we also experiment with various Tidal Crowds settings, such as with or without POI.
The rest of the paper is organized as follows. In Section 2, we first introduce our system model and specify the problem addressed in this paper, followed by a description of our solution, Tidal Crowds. We then evaluate the proposed solution on a real-life data set in Section 3. Related work is discussed in Section 4, while our contribution and potential future research are presented in Section 5.
2 Tidal Crowds
We consider an asynchronous system consisting of a finite set of devices that communicate by message passing over reliable channels. In addition, each device keeps track of its successive locations, which are stored in its local data set as its trajectories. Given this system, the Tidal Crowds algorithm aims to use these individual data sets to predict crowd flow in a reliable and privacy-preserving manner.
The core of Tidal Crowds consists of all devices running the same machine learning algorithm, namely DeepSTN+ [5], on their local data set. Intuitively, the idea is to aggregate the individual learning gained of each device and share it with other devices.
Figure 1:
Figure 1: Tidal Crowds overview.
Tidal Crowds comes in three parts, data acquisition and processing, machine learning algorithm, and aggregation algorithm as shown in Fig. 1. In this section, we explain each parts in detail.
In Tidal Crowds, we use the client-server architecture.1 The server manages the federated learning rounds and aggregates all the model parameters in one place. The Tidal Crowds protocol is as follows.
(1)
Each client gathers and processes trajectory data.
(2)
Each client trains their DeepSTN+ models on those trajectories.
(3)
Each clients sends locally computed DeepSTN+ model parameters to the server.
(4)
The server aggregates the clients’ locally computed DeepSTN+ model parameters using an aggregation algorithm.
(5)
The server updates its global DeepSTN+ model.
(6)
The server sends the new DeepSTN+ model parameters back to the clients.
2.1 Data Preparation
DeepSTN+ takes a time-series data of a grid map, where each cell has an inflow and an outflow value. Then, it predicts future inflow and outflow values of a cell on the grid map using past inflow and outflow values. Therefore, we start by selecting an area to work on and dividing that area into X × Y cells to create a grid map, our grid map is set to 21 × 12.
The inflow and outflow, introduced by Hoang et al., refer to the number of people entering a cell and leaving a cell, respectively [4]. Let \(\mathbb {P}\) be trajectories in a data set, \(Tr_t \in \mathbb {P}\) be a set of trajectories at tth time, and | · | denotes the cardinality of a set. For each cell gx, y, t ∈ inputData at tth time, the inflow and outflow values are calculated using Formula 1 and Formula 2, respectively.
We then prepare a four-dimensional array with the following structure: inputData[t][f][r][c] where t is the time interval, f is flow (0 for inflow, 1 for outflow), r is the row, and c is the column. For instance, inputData[2][0][5][3] contains the inflow value at the third time interval for the cell [5, 3] on the grid map, and inputData[2][1][5][3] represents the outflow of the same cell.
2.2 DeepSTN+
As the core machine learning algorithm of Tidal Crowds, we use the DeepSTN+ model introduced by Lin et al. [5]. DeepSTN+ is a novel and promising solution for crowd flow prediction because it takes into account long-range spatial dependencies. That is, even if two locations are distant but connected, the model understands how the crowd flow is correlated in both locations.
Distant regions in large cities are typically connected by various transportation modes such as subway, bus, and train. The long-range spatial dependence in big cities is an important factor in understanding crowd flow. Lin et al. state that previous crowd flow prediction solutions do not encapsulate long-range spatial dependencies [5]. Therefore, they design DeepSTN+ for crowd flow prediction to address this problem.
In a different setting, DeepSTN+ combines POI and time information to understand their effect on the flow of crowds. In addition to separate channels, average pooling is used to reduce the number of parameters. For example, streets with educational institutions can be expected to be more crowded at the beginning and end of the school day, when students are arriving for or leaving school.
2.3 Aggregation Algorithms
The distribution of data in federated learning brings in distribution of data, balancing the load. However, each client’s learning must be aggregated to complete collaboration.
FedAvg. Together with federated learning, McMahan et al. introduce the FedAvg algorithm that performs averaging on the learnings of clients as follows, K represents number of clients [7].
FedProxy. Sahu et al. proposed the FedProxy algorithm to introduce and adjust the balance between local and global updates [8]. For this, a λ is introduced to FedAvg algorithm as a multiplier as in Eq. 4.
In this section, we present the data set and metrics we used. We measure and compare the error rates for the traditional machine learning and Tidal Crowds. We also compare the performances of variants of Tidal Crowds with two aggregation algorithms and use of POI. Figures 2 show the results for the traditional machine learning approach with and without POI up to ten epochs. We find that Tidal Crowds converges faster than the traditional machine learning solution.
Figure 2:
Figure 2: Traditional machine learning approach on BikeNYC data set with and without POI.
3.1 BikeNYC Data set
BikeNYC2 is a bike rental data set that was collected in New York City. We use the bike trajectory data collected between April 1 and September 30, 2014. The data set includes start and end timestamps and start and end trajectory points for each bike.
The POI information is taken from OpenStreetMap3. We chose the following amenity tags as POI; sustenance, education, transportation, financial, healthcare, entertainment-arts-culture, public service, facilities, and waste management.
3.2 Experiment Setup
For the traditional machine learning experiment, we split the last 14 days from the BikeNYC data set as a test set. For the Tidal Crowds experiments, we split the BikeNYC data set into ten groups using bike id information. In FedProxy experiment, we chose to give more weight to the global model because it is the collaboration results. Thus, the lambda is set to 0.4, that is, we multiply the global model weights are multiplied by 0.6 and clients model weights are multiplied by 0.4.
We measure error rates using two metrics: Root mean square percentage error(RMSPE) and Mean absolute percentage error (MAPE), Equations 5 and 6 respectively. Where n is the number of samples, yi is the actual value of the ith sample, and \(\hat{y}_i\) is the predicted value of the ith sample.
In the traditional DeepSTN+ solution, we set the number of epochs to ten. To compare the performance of Tidal Crowds to DeepSTN+, we trained each client model for one epoch and performed ten rounds of federated learning.
3.3 Performance of Tidal Crowds
In Tidal Crowds, we assume that there are ten clients and that all devices participate in each federated learning round.
Figure 3:
Figure 3: Tidal Crowds’ performance using different settings. Performance of Client 6 is given as an example.
Figure 4:
Figure 4: Comparison of traditional machine learning approach and Tidal Crowds to the ground truth without POI. Time intervals are shown next to the approach name.
Figure 5:
Figure 5: Comparison of traditional machine learning approach and Tidal Crowds to the ground truth with POI. Time intervals are shown next to the approach name.
The error rates of Client 6 are shown in Figure 3 in all settings of Tidal Crowds. A few rounds of Tidal Crowds is not as effective as the baseline approach, but increasing the number of rounds allows the model to converge. We found that it takes about five rounds for Tidal Crowds to improve considerably, and performing additional rounds converges the model. We notice similar patterns for each setting of Tidal Crowds. However, Tidal Crowds with the FedProxy setting convergences faster than the FedAvg algorithm. Thus, FedProxy can be more suitable in cases where faster convergence is needed. In addition to the aggregation algorithm, the use of POI improves the performance by including the semantic knowledge in the prediction.
We also take a look at the quality of the predictions to better understand the performance of Tidal Crowds. In Figures 4 and 5, we present inflow predictions of the baseline on the leftmost column, ground truth on the second column, Tidal Crowds with FedAvg on the third column, and Tidal Crowds with FedProxy on the rightmost column. The first rows are for the 57st time interval and the second rows are for the 58th time interval for Figure 4. In Figure 5, the time intervals are 16th and 17th in the same order.
We observe that both the baseline approach does not predict good and might be over fitting as we only train the models for ten epochs. However, after ten federated rounds, we observe good predictions with both settings of Tidal Crowds. For example, in Figure 4, the cell (4, 13), the most crowded area, is detected in all settings. Moreover, we observe the crowd around the top area between the 4th and 8th columns in the 57th time slot has started to disappear in the 58th time slot. We observe similar patterns in Figure 5, the crowds on line 16 and 17 are detected in all Tidal Crowds solutions and followed through the next time slot. Even though the crowded areas are captured, the predictions of Tidal Crowds with POI is a bit higher than the ground truth. This can be examined further, e.g., increasing the number of federated rounds.
Tidal Crowds is a promising approach to crowd flow prediction, and with POI information, it outperforms the baseline approach. At the same time, it ensures server independence from a central decision mechanism, ensures user privacy, and balances the load. The FedAvg and FedProxy aggregation algorithms produce promising results and can be experimented further.
4 Related Work
Neural network-based solutions are powerful and promising for interpreting complicated mobility patterns. This growing trend affects crowd flow prediction applications, as shown by the introduction of a neural network-based crowd flow prediction model called DeepST by Zhang et al. [12]. Later, crowd flow prediction models are improved by using recurrent neural network (RNN) solutions [13]. The three temporal windows (closeness, period, and trend) and inflow and outflow are also introduced as they are essential for understanding crowd dynamics. Since RNNs often take a long time to train, Lin et al. introduce a convolutional neural network-based crowd flow prediction model [5]. However, Lin et al.’s crowd flow prediction model assumes that the data is centralized, i.e., they use a traditional machine learning approach, and do not consider the privacy of user data [5, 11].
Federated learning has been applied to human mobility applications such as traffic flow prediction [6], POI recommendation [3], and next location prediction [2]. The authors observe an increase in performance and achieve promising results by adding federated learning to their solution.
Federated learning can bring benefits to crowd flow prediction solutions because such solutions are latency sensitive and rely on private data.
5 Conclusion
In this paper, we present Tidal Crowds, a crowd flow prediction algorithm that ensures server independence from a central decision mechanism, ensures user privacy, and load balancing.
Tidal Crowds consists of three parts, data acquisition and processing, machine learning algorithm, and aggregation algorithm. The data acquisition and processing part deals with preparing the inflow and outflow data. The core of Tidal Crowds is the DeepSTN+ algorithm, which is good at capturing long-range spatial dependencies and allows use of POI in a different setting. Tidal Crowds allows two aggregation algorithms, FedAvg and FedProxy.
We evaluate Tidal Crowds on a real-life data set and compare its all settings to a traditional machine learning approach. We find that Tidal Crowds improves the performance of crowd flow prediction and converges the model faster than the traditional machine learning approach.
In the future, we plan to use different data sets to test Tidal Crowds and various additional information such as weather information to improve the quality of Tidal Crowds. We also plan to evaluate other federated learning algorithms such as client selection and federated averaging algorithms.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. 2016. Practical Secure Aggregation for Federated Learning on User-Held Data.
Minh X. Hoang, Yu Zheng, and Ambuj K. Singh. 2016. FCCF: Forecasting Citywide Crowd Flows Based on Big Data. In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (Burlingame, California) (SIGSPACIAL ’16). Association for Computing Machinery, New York, NY, USA, Article 6, 10 pages.
Yi Liu, James J. Q. Yu, Jiawen Kang, Dusit Niyato, and Shuyu Zhang. 2020. Privacy-Preserving Traffic Flow Prediction: A Federated Learning Approach. IEEE Internet of Things Journal 7, 8 (2020), 7751–7763.
Anit Kumar Sahu, Tian Li, Maziar Sanjabi, Manzil Zaheer, Ameet Talwalkar, and Virginia Smith. 2018. On the Convergence of Federated Optimization in Heterogeneous Networks. CoRR abs/1812.06127 (2018). arXiv:https://arXiv.org/abs/1812.06127http://arxiv.org/abs/1812.06127
Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and Yi Zhou. 2019. A Hybrid Approach to Privacy-Preserving Federated Learning. In Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security (London, United Kingdom) (AISec’19). Association for Computing Machinery, New York, NY, USA, 1–11.
Bo Zhang, Rui Zhang, Niccolo Bisagno, Nicola Conci, Francesco G. B. De Natale, and Hongbo Liu. 2021. Where Are They Going? Predicting Human Behaviors in Crowded Scenes. ACM Trans. Multimedia Comput. Commun. Appl. 17, 4, Article 123 (nov 2021), 19 pages.
Junbo Zhang, Yu Zheng, and Dekang Qi. 2017. Deep Spatio-Temporal Residual Networks for Citywide Crowd Flows Prediction. Proceedings of the AAAI Conference on Artificial Intelligence 31, 1.
Junbo Zhang, Yu Zheng, Dekang Qi, Ruiyuan Li, and Xiuwen Yi. 2016. DNN-Based Prediction Model for Spatio-Temporal Data. In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (Burlingame, California) (SIGSPACIAL ’16). Association for Computing Machinery, New York, NY, USA, Article 92, 4 pages.
Ali Zonoozi, Jung-Jae Kim, Xiaoli Li, and Gao Cong. 2018. Periodic-CRN: A Convolutional Recurrent Model for Crowd Density Prediction with Recurring Periodic Patterns. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (Stockholm, Sweden) (IJCAI’18). AAAI Press, 3732–3738.
The increasing concern for privacy and the use of machine learning on personal data has led researchers to introduce new approaches to machine learning. Federated learning is one such a novel privacy-preserving machine learning approach that “brings code ...
Multimodal learning mines and analyzes multimodal data in reality to better understand and appreciate the world around people. However, how to exploit this rich multimodal data without violating user privacy is a key issue. Federated learning is ...
Highlights
The three different modes in the multimodal federated learning model are summarized.
Multimodal fusion based on the federated learning framework is also specified.
The difficulties and some ideas of multimodal federated learning ...
Federated learning is an emerging machine learning paradigm that enables multiple devices to train models locally and formulate a global model, without sharing the clients’ local data. A federated learning system can be viewed as a large-scale ...
