A density-based heuristic for household detection in college communities through Big Data analysis

Abstract

In the age of big data, the wealth of information offers unprecedented opportunities to glean valuable insights into human behavior and activities. This study focuses on leveraging data collected from mobile applications used by students at a local college to identify their home locations and other shared points of interest. Through this research, we aim to enhance understanding of mobility patterns within student communities, providing valuable information for decision-making in transportation planning and mobility-related issues in surrounding areas. This paper introduces a heuristic based on density-related clustering to detect home locations from real-time big data collected by a mobile application. The results demonstrate satisfactory precision, with potential for further improvement as additional data is acquired, thus offering insights into potential future applications and services. RESUMEN: En la era del Big Data, la abundancia de datos ofrece oportunidades sin precedentes para obtener información valiosa sobre el comportamiento y las actividades humanas. Este estudio se centra en el aprovechamiento de los datos recogidos de las aplicaciones móviles utilizadas por los estudiantes de una universidad local para identificar la ubicación de sus hogares y otros puntos de interés compartidos. A través de esta investigación, se pretende mejorar la comprensión de los patrones de movilidad dentro de las comunidades de estudiantes, proporcionando información valiosa para la toma de decisiones en la planificación del transporte y las cuestiones relacionadas con la movilidad en las zonas circundantes. Este artículo presenta una heurística a partir de clustering basado en densidades para detectar las ubicaciones de los hogares a partir de grandes volúmenes de datos, recopilados en tiempo real por una aplicación móvil. Los resultados demuestran una precisión satisfactoria, con potencial de mejora a medida que se adquieren datos adicionales, evidenciando un potencial de posibles aplicaciones y servicios futuros.

Headnote

ABSTRACT: In the age of big data, the wealth of information offers unprecedented opportunities to glean valuable insights into human behavior and activities. This study focuses on leveraging data collected from mobile applications used by students at a local college to identify their home locations and other shared points of interest. Through this research, we aim to enhance understanding of mobility patterns within student communities, providing valuable information for decision-making in transportation planning and mobility-related issues in surrounding areas. This paper introduces a heuristic based on density-related clustering to detect home locations from real-time big data collected by a mobile application. The results demonstrate satisfactory precision, with potential for further improvement as additional data is acquired, thus offering insights into potential future applications and services.

RESUMEN: En la era del Big Data, la abundancia de datos ofrece oportunidades sin precedentes para obtener información valiosa sobre el comportamiento y las actividades humanas. Este estudio se centra en el aprovechamiento de los datos recogidos de las aplicaciones móviles utilizadas por los estudiantes de una universidad local para identificar la ubicación de sus hogares y otros puntos de interés compartidos. A través de esta investigación, se pretende mejorar la comprensión de los patrones de movilidad dentro de las comunidades de estudiantes, proporcionando información valiosa para la toma de decisiones en la planificación del transporte y las cuestiones relacionadas con la movilidad en las zonas circundantes. Este artículo presenta una heurística a partir de clustering basado en densidades para detectar las ubicaciones de los hogares a partir de grandes volúmenes de datos, recopilados en tiempo real por una aplicación móvil. Los resultados demuestran una precisión satisfactoria, con potencial de mejora a medida que se adquieren datos adicionales, evidenciando un potencial de posibles aplicaciones y servicios futuros.

KEYWORDS:

Algorithms; data analysis; data visualization; data processing; pattern recognition

Algoritmos; análisis de datos; visualización de datos; procesamiento de datos; reconocimiento de patrones

Declaration of competing interest

We declare that we have no significant competing interests, including financial or non-financial, professional, or personal interests interfering with the full and objective presentation of the work described in this manuscript.

Acknowledgment

This article has been published as part of activities in the Latin American Energy and Vehicle Research Network - RELIEVE.

Funding

This study was financed partially by the National Council for Science and Technology -CONACYT (Mexico) and by the MinCiencias (Colombia).

Author contributions

M. D. Giraldo-Galindo, L. F. Quirama-Londoño and J. I. Huertas-Cardozo: Conceived and designed the analysis. M. D. Giraldo-Galindo and L. F. Quirama-Londoño: Collected the data. M. D. Giraldo-Galindo and L. F. Quirama-Londoño: Contributed data or analysis tools. M. D. Giraldo-Galindo and |. F. Quirama-Londofio: Performed the analysis.M. D. Giraldo-Galindo, |. F. Quirama-Londoño and J. I. Huertas-Cardozo: Wrote the paper.

Data availability statement

The data associated with this study (Appendix 5) were extracted from some projects developed in Toluca and Mexico City, Mexico, in 2014 using a PEMS Semtech EcoStar, OBD II and GPS Garmin 16x. The authors confirm that the data supporting the findings of this study are available within the article.

1. Introduction

Home location detection plays a pivotal role in various domains, from urban planning to personalized services, and is essential for understanding human mobility patterns and informing policy decisions [1-3]. Social media platforms, particularly Twitter, have emerged as valuable sources of data for inferring travel patterns and home-work travel matrices [4]. Meanwhile, mobile phone data analytics offer insights into population geography and mobility patterns, aiding in the development of real-time monitoring tools and urban planning strategies [5, 6].

Studies have underscored the importance of selecting appropriate methodologies for home location detection, considering the characteristics of the dataset, and addressing inherent biases [7, 8]. Various techniques have been proposed for inferring home locations, including clustering algorithms, trajectory analysis, and machine learning models [9, 10]. Ensemble approaches that combine multiple algorithms have shown promise in enhancing detection accuracy [11, 12]. However, privacy concerns related to location data persist, necessitating the implementation of robust privacy protection measures, especially in the context of location-based services [13, 14]. Furthermore, recent research has focused on the development of novel methodologies for home location detection [15, 16]. These advancements highlight the interdisciplinary nature of home location detection research, drawing insights from fields such as computer science, geography, and social sciences.

In fact, accurate home location detection is crucial for various applications, including urban planning, personalized services, and ensuring user privacy. Addressing the methodological challenges and privacy concerns associated with home location detection requires ongoing research and collaboration across disciplines. The proposed approach was evaluated using real-life logs from a representative group of students over a five-month period. The results showed that this approach is effective in obtaining average demand data, which can be utilized in planning mobility strategies, as long as continuous tracking of mobility data is feasible through mobile devices. The methodology proposed in the following section employs a density-based approach, a type of agglomerative clustering, to address the unique challenges presented by spatiotemporal data, which often form large clusters around user points of interest. This approach 15 particularly effective for detecting these hotspots while simultaneously discarding outliers, such as occasional stops during a trip. In our case study, the parameters of the heuristic approach were calibrated using home data provided by volunteers. Unlike previous studies, which broadly address various populations, our research focuses specifically on the residential patterns of college students. Our study offers a more targeted analysis by incorporating characteristics such as the last-day trip destination identified through a data mining process on raw data. Additionally, home locations identified by our methodology were validated against a set of known student data, ensuring the accuracy and relevance of our findings.

2. Methodology

In order to obtain locations of the student homes, data have to be mined from a typical tracking dataset, which contains primarily coordinates and timestamps by following a multi-step procedure described in Figure 1. In summary, the methodology follows this sequence:

Data are collected by a mobile app that uses the location services of the mobile device, so that they can be temporarily kept in the local storage; then, data are securely stored in a remote server via an Application Programming Interface (API). In the second stage, these unprocessed data are filtered to detect outliers and possible errors and then transformed to a suitable format for further processing. Finally, data are aggregated into origins and destinations (OD) by a segmentation algorithm and classified as the inferred home locations of students. These locations are validated for a selected sample of known locations. To complete the flow, some potential transport services and strategies, including routes among these locations are planned out. The steps followed in the methodology are described below.

2.1 Mobile Data Collection

The first step is storing mobility data together with temporal and user's identity information in a remote database. Each observation i (a labeled spatiotemporal data point) will have the following structure in Equation 1. The simplest form consists of the locations coordinates (x, у) of the tracked user at a specific time, t.

pi = Ca Yi ti) (1)

A more complete version of the observation is shown in Equation 2.1.

pi = (uid; lat, lon; alt; date; ti, dowi, асс, timestamp)

e uid, is a unique identifier of the user, normally a MD5 hash string which guarantees data is collected anonymously, but it still makes it possible to know the user in the database

e lat. lon, alt, the points of latitude, longitude, and altitude coordinates

e date, a day-month-year string

e t a 24-hour local time format for a continuous variable after applying the formula shown in Equation 2

e dow, the day of the week the observation was captured, where 1 is Sunday

e acc, accuracy in meters of the measurement as reported by the sensor API, lower values produce more accurate measurements

e timestamp, a Unix-based timestamp, allowing to treat dates as continuous variables

The set Pa of data point observations collected in real-time by a user's mobile device, is stored in this format in a remote server for further offline treatment. However, this format is not yet suitable for most calculations, so that further processing is required as described in the following steps.

2.2 Data Processing

In order to avoid bias in the calculation of travel destinations, outliers are removed, considering the position accuracy and temporal constraints. A subset Pa consists of more refined "valid" observations, selected through the following criteria shown in Equation 3.

where a is a parameter that denotes the maximum allowed accuracy error in meters. Moreover, users can travel to destinations found in other regions, countries, and even continents. For the purpose of this research, home locations must be found inside a study region at a medium-sized city level, so a bounding box defined by [lonmin, lonmax, latmin, latmax] constraints the valid observation previously found; this is shown in Equation 2.2. Pes {pi Е Р, |

(latmin < lat; < latmax)

A (lonmin < Toni < loNmax) }

Because this research is intended to provide insights into transport services for students in a College Community, a time period when users are expected to regularly visit the campus must be selected. Then, a cutoff date defined by [datemin, datemax] is used to select the final subset P, shown in Equation 4.

Lastly, since OD detection requires the computation of distances, a Cartesian projection is a better approach. For the selected study region, the UTM-17S is chosen, so that longitude, latitude, and altitude measures are transformed to Euclidean space coordinates (x, y, z). Since dates and accuracies are not needed anymore, each observation pi in the resulting processed set P is shown in Equation 5.

Computing new attributes

Additional features must be incorporated into the existing dataset to comprehensively evaluate travel behavior.

Let pi be the ith observation in a spatiotemporal dataset P . Then, the cumulative distance Dan for a trajectory starting at point a and consisting of the following n observations is defined in Equation 6.

where di; is the Euclidean distance between two observations, defined in Equation 7.

that is, the sum of distances between proximate points; then, the instant speed at observation it is computed by Equation 8.

The resulting extended dataset has the following structure shown in Table 1, after making the mentioned computations, and then filtering out consecutive measures taken at the same time stamp (possibly duplicates); also, the very first observation has to be removed in order to avoid division by zero in the speed calculation. Distances have been transformed to km so that the speed unit is km/h. The field "dt" in Table 1 corresponds to the difference in hours between consecutive points.

Finally, a last filtering procedure removes observations With extreme speeds, as values beyond 130 km/h are very improbable (by checking speed limits within the studied region). These data are often related to extreme distances between proximate points, which can occur due to bad GPS measures.

2.3 Data Mining

A heuristic is proposed to segment the data traces of each user into individual travels (geometries) and OD pairs at the start and end points. This heuristic focuses on identifying low-speed hot spots as potential destinations to aggregate the data into trajectories.

Low-Speed Detection: Data are traversed to look for stay hot spots, by comparing instant speeds with a threshold parameter e so that data points are segmented into a sequence of displacements.

False positives filtering: An acceptable displacement by a set of known travel modes should involve a minimum stay time ¿min in location, as well as minimum time and travel distance. After this process, the dataset size will be reduced (approximately up to a 0.5 factor).

GPS Traces Clustering: Finally, the first (FP) and last (LP) point in each cluster allow extracting coordinates of the origin and destination, as well as the departure and arrival times (from the time stamps of these points). The travel time is simply the difference between the arrival and departure times; also, the cumulative distance of all points in a cluster indicates the trip travel distance.

Home Detection: After detecting destinations, additional heuristics must be applied to find out a user's place of residence. It is, therefore, essential to define certain concepts beforehand. Let Тк be a trip displacement identified by &, the following characteristics are known in Equation 9.

e oi the origin data point with its own coordinates and timestamp

e di, the destination data point with its own coordinates and timestamp

e dti, the departure time (time at origin data point)

e ati, the arrival time (time at destination data point)

e sti, stay time at destination of this trip is defined in Equation 10

That is, the stay time is the time spent on the destination before the next trip starts. Some points of interest will be found with this process, including, for sure, the college campus and the expected home location. The heuristic assumes that the most frequent last trip destination of the day must be a student's home.

It must be noted that every new visit to this place will yield a slightly different pair of coordinates. To find their centroid, a density-based clustering such as DBSCAN [? ] must be carried out on these points. The dissimilarity measure is the Euclidean distance and a set of points or destinations of interest is found.

In the following section, the results after applying this methodology to the collected data set are presented and discussed; an approach to validate these results is also provided.

3. Tests and results

3.1 Dataset Description

The dataset used in this study comprises spatiotemporal data collected through a specialized tracking mobile application designed for a university community over five months. It encompasses data from 728 users, chosen over a one-month period, specifically from May 20 to June 20, 2023, with data totaling about five million monthly records. Subsequent analysis results have shown that 30 days of mobility data per user is sufficient to identify household locations domicile. The number of observations after the data cleaning process is above 11 million, so that good infrastructure for cloud storage is required to handle this volume of big data. The bounding box for the region of Cuenca, Ecuador, contains longitudes between -79,084789233 and -78,933588295, and latitudes between -2,938030323 and -2,865347073.

A picture of the sample of collected points on a map at scale 1:50000 is given in Figure 2, showing that complete travel trajectories can be retrieved from data. The sampling frequency of the GPS, that is, the time difference between measures was not fixed, but it was around 2 seconds on average.

3.2 Heuristic Results

Taken a single day displacements for a single user, the speeds and distances between proximate points variations that take place when traveling, staying on destination, and changing to a different travel mode may allow a trip's endpoints to be detected. The speed and distance distributions are shown in Figure 3.

As seen in the previous figure, most of the speeds and distances are closer to zero, probably because users spend most of their time walking or staying in one destination before starting the next trip. The changes in speed during the day can be seen in Figure 4.

This means that data points can be segmented into individual travels by detecting those locations when moving at very low speeds (staying still), with respect to a given speed tolerance e.

It can be assumed that actual destinations are found in intervals where users are not moving for a minimum amount of time ¿min, that is, in the "valleys" shown in the last figure; in contrast to traffic lights that will also produce zero speeds but will last only a few seconds. Figure 5 shows the points merged into trips (clusters) for e=2km/h and fmin= 10 minutes. Increasing fmin Will merge nearby trips into larger ones.

Following the steps mentioned in the methodology, the data points have been clustered into trips that fit the time and distance constraints. The statistical data for the extreme (border) points of each cluster are given in Table 2.

A glimpse of the aggregate data on individual travels (one per cluster) is presented in Table 3.

The resulting segmentation allows ODs to be detected. Their coordinates are given in the table as attributes "dx" and "ау" for destination locations, and "ох" and "оу" for the origins. Figure 6 presents on a map at scale 1:25000 the resulting user's destinations (as red spots). It can be noticed that as locations are repeatedly visited, some points could be merged into a single destination as they are possibly short displacements around the same location; this can be done by density-based clustering techniques; however, this is not necessary for the upcoming analysis. By applying the algorithm to the full dataset of tracked users, segmented trajectories exhibit the statistics shown in Figure 7.

Then, according to this report, the majority of trips occur on weekdays. Moreover, they are "short trips" below 30 minutes and 10 km.

Home Detection

A first exploratory data analysis must be carried out with 31 users who have voluntarily provided an approximation of the location of their residence. Some statistics of these trips are presented in Figures 8 and 9, where it can be noticed that arrival times of home trips occur mostly in the evening, in contrast to no-home trips that do not exhibit a clear pattern, as seen in Figure 9 .

Taking the locations of those destinations found in each last trip of each day (avoiding trips between days), the results for the same one-user of the sample used in previous analysis, but now for multiple days, is shown in Figure 10. By using a clustering radius of 50 meters with a minimum

cluster size of 5 points (which means at least 5 home trips are required to detect it), 5 different possible candidates were found, but only the most frequent (the biggest cluster) has been assumed to be home, as can be seen in the same Figure 10, where this location has been highlighted as a green spot, and in Figure 11, the assumed home locations for a sample of users are shown.

Data Validation

The last stage intends to test the approach's accuracy, and for that, a set of 30 volunteers who provided actual home locations is used. In Figure 12, a map with these actual locations and the detected ones by the algorithm is presented.

In Table 4, the corresponding coordinates are shown together with the measured distance. A histogram of these errors can be seen in Figure 13, suggesting an approximated normal distribution, with a mean of 27.9 meters and a margin of 5.62 meters for a 95% confidence interval.

4. Conclusions

This paper presents an approach to detecting home locations through density-based clustering, exploratory data analysis and data segmentation. Home locations have been validated by users who have voluntarily provided an approximation of the location of their residence. The heuristic considers the last known destination per day, so the more data collected, the more plausible it is that the algorithm will pick up the correct location.

This approach creates clusters of recurrent destinations, after mobility data is aggregated into trips by segmentation techniques. It has been shown that one month of data is sufficient for users to exhibit patterns, which are required to identify those regions of interest.

5. Discussion and Future Works

Some key aspects must be considered in order to increase the chance of success of this approach. For instance, the segmentation of data points must be done per user, since OD detection expects instant speeds to decrease below a reference value per trip, so that stay time when "not moving" reaches a minimum time threshold. The calibration of the max speed threshold makes trips longer or shorter, and it could increase the chances to find locations of interest where the user stays for long periods. As the dataset contains all tracking data from users, constraining a trip's arrival time to a given interval (morning, evening) and detecting its travel mode helps discriminate destinations among college campuses, home locations, and other relevant places a student visits. In the following section, some examples of use cases are provided.

5.1 Transport Service Applications

When considering the home location of several users Within the studied area, a list of insights for different applications to provide transport services arise. A sample of assumed home locations is shown in Figure 11 for our region of interest.

Some possible applications are:

Sidebar

CITE THIS ARTICLE AS:

I. Mendoza, A. Baquero-Larriva and G. A. Álvarez-Coello "A Density-based heuristic for household detection in college communities through big data analysis", Revista Facultad de Ingeniería, Universidad de Antioquia, no. 114, pp. 51-62, Jan-Mar 2025. [Online].

ARTICLE INFO:

Received: January 29, 2024

Accepted: August 30, 2024

Available online: September 02, 2024

Footnote

* Corresponding author: Iván Mendoza

E-mail: imendoza Quazuay.edu.ec

ISSN 0120-6230

e-ISSN 2422-2844

References

References

[1] J. Huertas, M. Giraldo, L. Quirama, and J. Díaz, "Driving cycles based on fuel consumption," Energies, vol. 11, no. 11, Nov. 2018. [Online]. Available: https://doi.org/10.3390/en11113064

[2] E. Ericsson, "Independent driving pattern factors and their influence on fuel use and exhaust emission factors," Transportation Research Part D: Transport and Environment, vol. 6, no. 5, Sep. 2001. [Online]. Available: https://doi.org/10.1016/S1361-9209(01)00003-7

[3] J. 1. Huertas, L. F. Quirama, М. D. Giraldo, and J. Diaz, "Comparison of driving cycles obtained by the micro-trips, markov-chains and mwd-cp methods," International Journal of Sustainable Energy Planning and Management, vol. 22, Jun. 2019. [Online]. Available: https://doi.org/10.5278/ijsepm.2554

[4] W. T. Hung, H. Y. Tong, C. P. Lee, K. Ha, and L. Y. Pao, "Development of a practical driving cycle construction methodology: A case study in hong kong," Transportation Research Part D: Transport and Environment, vol. 12, Mar. 2007. [Online]. Available: https://doi.org/10.1016/j.trd.2007.01.002

[5] H. Y. Tong and W. T. Hung, "A framework for developing driving cycles with on-road driving data," Transportation Reviews, vol. 30, no. 5, Aug. 2010. [Online]. Available: https://doi.org/10.1080/ 01441640903286134

[6] J. I. Huertas, L. F. Quirama, M. Giraldo, and J. Diaz, "Comparison of three methods for constructing real driving cycles," Energies, vol. 12, no. 4, Feb. 2019. [Online]. Available: https://doi.org/10.3390/ еп12040665

[7] 3. Lin and D. A. Niemeier, "An exploratory analysis comparing a stochastic driving cycle to california's regulatory cycle," Atmospheric Environment, vol. 36, no. 38, Dec. 2002. [Online]. Available: https://doi.org/10.1016/S1352-2310(02)00695-7

[8] L. F. Quirama, M. Giraldo, J. I. Huertas, J. E. Tibaquirá, and D. Cordero-Moreno, "Main characteristic parameters to describe driving patterns and construct driving cycles," Transportation Research Part D: Transport and Environment, vol. 97, Aug. 2021. [Online]. Available: https://doi.org/10.1016/j.trd.2021.102959

[9] M. Giraldo, L. F. Quirama, J. I. Huertas, and J. E. Tibaquirá, "The effect of driving cycle duration on its representativeness," World Electric Vehicle Journal, vol. 12, no. 4, Oct. 2021. [Online]. Available: https://doi.org/10.3390/wevj12040212

[10] M. Giraldo and J. I. Huertas, "Real emissions, driving patterns and fuel consumption of in-use diesel buses operating at high altitude," Transportation Research Part D: Transport and Environment, vol. 77, Dec. 2019. [Online]. Available: https://doi.org/10.1016/j.trd.2019.10. 004

[11] EEA, Explaining road transport emissions. A non-technical guide, 1st ed. Copenhagen, Denmark: Publications Office of the European Union, 2016. [Online]. Available: https://doi.org/10.2800/71804

[12] USEPA, MOVES2014a User Interface Reference Manual, Washington D.C., United States, 2016. [Online]. Available: https://tinyurl.com/ 3rkyzpn4

[13] Q. Yu, T. Li, and H. Li, "Improving urban bus emission and fuel consumption modeling by incorporating passenger load factor for real world driving," Applied Energy, vol. 161, Jan. 2016. [Online]. Available: https://doi.org/10.1016/j.apenergy.2015.09.096

[14] 3. D. К. Bishop, С. J. Axon, and М. D. Mcculloch, "A robust, data-driven methodology for real-world driving cycle development," Transportation Research Part D: Transport and Environment, vol. 17, no. 5, Jul. 2012. [Online]. Available: https://doi.org/10.1016/j.trd. 2012.03.003

[15] Q. Gong, S. Midlam-Mohler, V. Marano, and G. Rizzoni, "An iterative markov chain approach for generating vehicle driving cycles," SAE International Journal of Engines, vol. 4, no. 1, 2011. [Online]. Available: https://www.jstor.org/stable/26278204

[16] Z. Xiao, Z. Dui-jia, and S. Jun-min, "A synthesis of methodologies and practices for developing driving cycles," Energy Procedia, vol. 16, Mar. 2012. [Online]. Available: https://doi.org/10.1016/j. egypro.2012.01.286

[17] N. H. Arun, S. Mahesh, G. Ramadurai, and S. M. S. Nagendra, "Development of driving cycles for passenger cars and motorcycles in chennai, india," Sustainable Cities and Society, vol. 32, Jul. 2017. [Online]. Available: https://doi.org/10.1016/j.scs.2017.05.001

[18] L. Е. Quirama, M. Giraldo, 3. I. Huertas, and M. Jaller, "Driving cycles that reproduce driving patterns, energy consumptions and tailpipe emissions," Transportation Research Part D: Transport and Environment, vol. 82, May. 2020. [Online]. Available: https: //doi.org/10.1016/j.trd.2020.102294