Cell Phone Location Data for Travel Behavior Analysis (2018)

Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

56 5.1 Roadmap to the Chapter This technical chapter discusses how the noisy and massive cell phone call detail record (CDR) data were analyzed to extract daily trajectories. The discussion starts with the motivation for the approach and then focuses on how the noise from CDR data needs to be removed to arrive at meaningful data for assessing travel patterns. To measure travel in space and through time, some location and activity inferences were made. This chapter describes the need to drop spurious observations in order to parse trajec- tories and identify stay locations. The analysis steps needed to identify activity types at detected stay locations where individuals carrying cell phones conduct their activities are reviewed. Tem- poral activity patterns are examined by analyzing start times and activity duration patterns. The analytical components of this chapter describe how grid-based and point-based algo- rithms analyze traces, locations, and the time spent at each location to identify and extract stay points and stay regions. Data from the student user are used to present examples of stay extrac- tion results. The density of stay locations and the duration of activities for different arrival times are presented at the regional level. The results were aggregated to the zone level to facilitate origin–destination (O-D) comparisons of travel patterns. 5.2 Motivation and Purpose A critical task in urban and transportation planning is the examination and understanding of what people are doing in space and time (Chapin 1974; Lynch 1976; Hägerstrand 1989; Ahmed and Miller 2007; Janelle 2012; Jiang et al. 2012a, 2012b). To answer this question by using bil- lions of cell phone traces in the CDR data, it is crucial to infer the spatial and temporal activities that people engage in and position their travel as reflecting the need to pursue activities that are located elsewhere (Manheim 1979, Pinjari and Bhat 2011). As discussed already, location data gathered from cell phones, while massive, are often noisy across spatial and temporal dimensions. They can also be biased because of differences in usage of the technology and in penetration rates among different segments of the population. More- over, CDR data provide an irregular sampling frequency, as they only include information when a cell phone is connected to cellular networks for a call, a text message, or data usage. CDR data also provide no insights into the mode of transportation used. However, cell phone data provide an opportunity to measure travel more directly because of the sheer volume of data available to analyze. Such data sets are only growing larger and richer each year as the economy and individuals make increasing use of mobile-based systems. C H A P T E R 5 Extraction of Daily Trajectories

Extraction of Daily Trajectories 57 Passively collected cell phone data provide an unparalleled scale of observation. New methods of estimating travel demand need to balance trade-offs between small, but complete, data for a short period as compared with large, but incomplete, data over a longer period (Toole et al. 2015). In both cases, noise and biases must be carefully dealt with to produce valid measurements. To this end, the research team addressed several challenges presented by the cell phone data. Key insights from past research that tackled these problems to extract meaningful locations from massive and passive cell phone data for estimates of travel demand have been integrated into this body of work. 5.2.1 Motivation CDR data include spatiotemporal information on people’s movements relative to cell towers or triangulated locations, depending on the positioning technology used by the mobile service carrier. An initial study by Wang et al. (2012) used CDR data to estimate travel demand. The study generated transient O-D matrices for different time periods by simply counting as a trip a pair of consecutive calls made within the same hour from two different towers. By assigning the converted intersection-to-intersection transient O-D matrices to the road network and using a bipartite network framework, Wang et al. (2012) presented a method for analyzing road usage patterns and pinpointing areas as driver sources contributing to major traffic congestion in Boston, Massachusetts, and the San Francisco Bay area in California. Following a similar approach, Iqbal et al. (2014) used CDR data collected in Dhaka, Bangladesh, over 1 month and combined them with traffic count data to estimate intersection-to-intersection transient O-D matrices. By using an optimization-based approach, they generated expansion factors for node-to-node transient O-D flows and compared the results with the limited traffic count data. While Wang et al. (2012) presented groundbreaking work using CDR data to infer road usage patterns, the method of using transient O-D flows for travel demand estimation could lead to a biased view of movements. Rather than modeling travel flows between activity destinations, transient O-D data capture segments of travel on the basis of the appearance of people in space and time as presented in raw cell phone data. Transient O-D data are particularly problematic for raw data that contain noise caused by tri- angulation of mobile positions such as the oscillation problem described in Chapter 4 and cases in which CDR data have low spatial resolution. For example, if the distance between cell towers is more than a few kilometers, transient O-D matrices can introduce biases, even if the road networks within each tower coverage area are dense. Traffic may be detoured to local roads, although the assigned travel path is not necessarily a direct route from the true origin to the destination. 5.2.2 Purpose To address this issue, the noise from cell phone trajectories must be removed by identifying and dropping spurious points or calls made in the middle of routes rather than at an origin or a destination. It is important to parse the trajectories observed in cell phone data into meaningful locations, termed “stays.” To produce meaningful estimates of travel demand, the goal, in general, is to find suitable algorithms with which to extract meaningful stay locations from noisy cell phone data for further analysis. By applying algorithms to parse passive cell phone trajec- tories into stay locations, researchers can estimate O-D trip tables for an average day or by time period from tower-based or finer-grained triangulated cell phone traces (Alexander 2015, Colak et al. 2015, Toole et al. 2015). This chapter presents two sets of algorithms that are tailored to address the distinct character- istics of cell phone data triangulated at the 200- to 300-meter accuracy level. These algorithms

58 Cell Phone Location Data for Travel Behavior Analysis are designed to filter the cell phone data to infer human activities and travel in space and time. Parsing passive cell phone data to extract “stay locations” identifies activity anchor points in an individual’s daily travels. This approach allows differentiation of destinations from pass-by points and helps identify an individual’s mobility pattern. Similar research is also key in analyz- ing GPS data from commercial vehicles. The wide adoption of smartphones and location-based mobile apps has led to a vast body of computer science literature on the topic of trajectory mining. Jiang et al. (2013) provide a review of these techniques. A detailed review on trajectory mining methods can also be found in Zheng’s (2015) research. 5.3 Stay Extraction Algorithms 5.3.1 Grid-Based Algorithm In the preprocessing of the CDR data, the first step is to identify stays, which represent phone records that are registered when users engage in activities. These stays are distinct from pass-by points, which represent records made while traveling along each user’s trajectory. As illustrated in Figure 5-1, a stay point is identified by a sequence of consecutive cell phone records bounded by both temporal and spatial constraints. The spatial constraint is defined by the roaming distance when a user is staying at a location, which should be related to the accuracy of the technology collecting location data. In this study, the spatial accuracy for triangulated CDR data, also known as the roaming distance, was set as 300 meters. This distance was estab- lished to approximate the area that might likely be traversed on foot as part of an urban activity. The temporal constraint is the minimum duration spent at a location, which is measured as the time difference between the first and the last record in a stay location. In this study, records satisfying the spatial constraint (300 meters) and temporal constraint (duration of 10 minutes or more) were counted as stays. Once a stay point was identified, the geographic location was set as the centroid of all records belonging to that stay. In Figure 5-1, Point s1 is the centroid of Record Locations p3, p4, and p5. Both constraints may be adjusted on the basis of the data availability and the researchers’ understanding of the quality of the data. The second step is to distinguish stay regions from stay points. Different stay points identi- fied in a user’s several different trajectories may refer to a same location, but the coordinates of these stay points are unlikely to be exactly the same. A grid-based clustering method was used to cluster stay points and get stay regions. Source: Jiang et al. 2013. Figure 5-1. Illustration of the stay extraction process [green dots = raw triangulated CDR data points (p); red dots = stay points (s); blue dot = grid- based stay region (r) from the cluster of stay points].

Extraction of Daily Trajectories 59 As shown by Zheng et al. (2010), the advantage of the grid-based clustering method over the k-means algorithm and the density-based ordering points to identify the clustering structure (OPTICS) algorithm is that it can constrain the output cluster sizes. This property is desirable when each location should have a bounded size and the accuracy of the records is within a certain range. The procedure for performing grid-based clustering follows these steps: • The entire region is divided into rectangular cells of about 100 meters (one-third of the roam- ing distance of 300 meters). • All the stay points are mapped to the appropriate cell. • The unlabeled cell is iteratively merged with the maximum stay points and its unlabeled neighbors to create a new stay region. • Once a cell is assigned to a stay region, it is marked as labeled.1 In Figure 5-1, the three stay points are clustered to one stay region (r1). 5.3.2 Point-Based Algorithm In contrast to the grid-based algorithm, the point-based stay region extraction is designed to exploit the maximum spatial accuracy possible. To extract individuals’ whereabouts [including their stationary stay locations (to infer activity types) and their moving pass-by locations (to infer travel path and road usage)] from phone records, Jiang et al. (2013) employed a method inspired by Hariharan and Toyama (2004) that was originally designed for processing GPS traces. GPS data are recorded with a high frequency so that they can be treated as continuous tra- jectories. Unlike GPS data, cell phone data are perceived with indefinite gaps in space and time. Furthermore, the locational accuracy of cell phone data is lower than that of pinpointed GPS traces, depending on the technology (Renso et al. 2008). On the basis of these differences, Jiang et al. (2013) tailored the algorithms for the CDR data by using the spatial and temporal approach described in Sections 5.3.2.1 and 5.3.2.2. 5.3.2.1 Spatial Dimension Let sequence Di = (di(1), di(2), di(3), . . . , di(ni)) be the observed data for a given anonymous user i, where di(k) = (t(k), x(k), y(k))1 for k = 1, . . . , ni; t(k) = time observation; x(k) = longitude; and y(k) = latitude of the kth observation of user i. First, points di(k) that are spatially within the roaming distance of 300 meters to their subse- quent observations are extracted, say, di(k + 1), di(k + 2), . . . , di(k + m). To reduce the jumps in the location sequence of the cell phone data, it is assumed that di(k), . . . , di(k + m) are observed when user i is at a specific location. That location corresponds to the medoid (Med) of the set of locations (xi(k), yi(k))1, . . . , (xi(k + m), yi(k + m))1, and it is denoted by Med((xi(k), yi(k))1, . . . , (xi(k + m), yi(k + m))1). This treatment respects the time order, at first, to ignore noisy jumps in the estimated loca- tion. At the next step, the treatment disregards time ordering to apply Hariharan and Toyama’s (2004) agglomerative clustering algorithm, which consolidates points that are close in space but may be far apart in time. The points to be consolidated together form a cluster whose diameter is 1For more details about the algorithm, readers are referred to Zheng et al. (2010).

60 Cell Phone Location Data for Travel Behavior Analysis required to be no more than a certain threshold. Again, the observation is moved to the location of the new medoid of the clusters, as shown in Figure 5-2. 5.3.2.2 Temporal Dimension The top part of Figure 5-3 presents the frequency distribution and the bottom part the cumu- lative distribution function of stay duration for the extracted filtered locations identified in Figure 5-2. The stay duration criterion is imposed on the filtered data, and the stay locations whose duration exceeds a certain temporal threshold are extracted. The temporal threshold was set at 10 minutes. The cyan vertical bars in Figure 5-3 show the positions of the 10-minute stay duration in these two distributions. In the example discussed, 31 distinct stay locations were extracted from the 1,776 phone records in the 2-month period of an anonymous user represented by the red points in Figure 5-4. The points represented by black circles in Figure 5-4 are pass-by points at which lengthy stays were not observed. It is possible that the user stayed in some of these pass-by locations as well as in other locations that were not observed. In these cases, information about time and location is totally or partially latent, as they are not observed in the cell phone records. However, all the stay locations frequently visited by the user ought to be extracted from the cell phone data, especially if the observation period is long enough, as was the case with this example. Therefore, the pass-by locations were filtered out and the stays were assumed to be true trip origins or destinations, between which trips were made. 5.4 Stay Extraction Results 5.4.1 Individual Example This section discusses the results of applying the algorithms to the data from the anonymous student user. As discussed earlier, the value of the student user data set was that it functioned as a validation step. The detailed trace data were combined with prompted recall information not avail- able in the CDR data. Therefore, this step provided information critical to understanding whether or not the algorithms performed a reasonable job in measuring stays and pass-by locations. Figure 5-5 presents the stay extraction results obtained using the grid-based algorithm presented in Section 5.3.1. Figure 5-6 presents the extracted stay results obtained using the Source: Jiang et al. 2013. Figure 5-2. Filtered locations from phone records with a 300-meter threshold: (a) raw phone records and (b) filtered locations. Two months of data from an anonymous user were used in the filtering.

Extraction of Daily Trajectories 61 Figure 5-3. Pattern of stay durations: (top) frequency distribution of stay durations and (bottom) cumulative distribution of stay durations. Data represent stay durations for all filtered locations in 2 months of data from Boston. Source: Jiang et al. 2013. Figure 5-4. Inference of stays and pass-by areas by using a 10-minute threshold: (a) filtered locations and (b) stays and pass-by areas. Two months of data from an anonymous user were filtered with a 10-minute threshold.

62 Cell Phone Location Data for Travel Behavior Analysis Figure 5-5. Stay locations extracted by using grid-based algorithm (blue points = user’s raw cell phone data; red bulbs = stays extracted by using grid algorithm and anonymous user data. Grid-based algorithm used 18 months of data from an anonymous user.

Extraction of Daily Trajectories 63 Figure 5-6. Effect of grid- and point-based algorithms on stay locations (blue points = raw phone records; circles = filtered locations). Eighteen months of data from an anonymous user were used in the filtering.

64 Cell Phone Location Data for Travel Behavior Analysis point-based algorithm presented in Section 5.3.2 and compares the results with those derived using the grid-based algorithm. In both cases, the noise in the raw cell phone data was removed and locations were reduced to a few anchor points where the individual was estimated to have conducted activities. • The comparison in Figure 5-6 of the stay extraction results from the grid-based algorithm and the point-based algorithm suggests that the two algorithms have different advantages. In most cases, the stays extracted by these two algorithms were close to each other. • However, the stays extracted from the point-based algorithm are always on top of existing raw cell phone records, and thus more sensitive and relevant when referring to local spatial context. In contrast, the stay results from the grid-based algorithm are regionalized into loca- tions that are not necessarily near the exact locations the user visited. • One of the advantages of the grid-based algorithm is that it is faster. However, when infor- mation with high spatial resolution is aggregated into a coarser resolution, some local details are lost. • The grid-based algorithm also has advantages in terms of privacy protection when compared with the point-based algorithm. Given that the point-based algorithm uses the agglomerative clustering method to preserve much of the spatial information in the raw data, it keeps the original spatial resolution of the data but is costly in terms of computing speed. • For purposes of travel demand estimation, grid-based stay extraction may be good enough, given that data from the extracted stay points are aggregated into zones such as Census tracts or traffic analysis zones (TAZs). • For other studies, such as inferring population density at the building or block level, a point-based stay extraction algorithm that will provide higher spatial accuracy may be more appropriate. 5.4.2 Regional Perspective This section uses data from the same sample day presented in Figure 5-4 to demonstrate the results of extracted pass-by locations and stays in the Boston region. Figure 5-7 shows the spatial distribution of the kernel density estimation of pass-by filtered locations with a temporal threshold of less than 10 minutes, as discussed in Section 5.3.1. The major roads in the region are presented in blue to show their spatial relationship to the pass-by locations extracted from the CDR data. As the road network in the downtown area is denser, it is harder to see a clear relationship, other than the high pass-by density in the downtown area as compared with the suburbs. How- ever, Figure 5-7 shows a clearer spatial correlation of the major roads and the pass-by locations along major transportation corridors, especially in the outer areas of the metropolitan region. Presumably, those cell phone traces correspond to cell phones that were being used along those roads. Figure 5-8 presents the spatial distribution of the kernel density estimation of the stays, which represent filtered anchor locations with a duration of 10 minutes or more in the CDR data for the same sample day. It shows a higher density of stays in the center of the region, while it also highlights several subcenters in the suburbs. 5.4.3 Stay Duration by Arrival Time To validate the extracted stays in terms of the temporal dimension, the research team looked further at stay duration by arrival time observed both in the travel survey data and the synthe- sized CDR data for the Boston region.

Extraction of Daily Trajectories 65 Figure 5-9, which was presented in an earlier published study of the authors’ research group (Widhalm et al. 2015), demonstrates the validity of the stays extracted from the CDR data in the temporal dimension. Figure 5-9a shows the stay duration by arrival time derived from the 2011 Massachusetts Travel Survey (MTS) data, while Figure 5-9b shows the distribution derived from the 2-month CDR data. In the aggregate, the two figures show similar temporal patterns for activity start and activity duration. There is a concentration of 6- to 8-hour stays that start around 8 a.m. and most likely Source: Jiang et al. (2013) Figure 5-7. Pass-by locations and their spatial distribution in the region. CDR data for a 2-month sample period in Boston (same as in Figure 4-7) were used to show the kernel density estimation of the pass-by locations.

66 Cell Phone Location Data for Travel Behavior Analysis Legend Source: Jiang et al. (2013) Figure 5-8. Stay locations and their spatial distribution in the region. CDR data for a 2-month sample period in Boston (same as in Figure 4-7) were used to show the kernel density estimation of the pass-by locations.

Extraction of Daily Trajectories 67 correspond to work activities. There is also a concentration of 10- to 16-hour stays starting between 4 p.m. and midnight that probably reflect home stay activities. These patterns suggest that the methods of extracting stays presented earlier are reliable and can give robust estimates of stay duration. These duration estimates are important for further categorizing activity types as “home,” “work,” and “other” and analyzing O-D matrices to pro- vide estimates of travel demand. 5.5 Mapping Stay Locations to Zones 5.5.1 Creating and Storing Geographic Data To estimate zone-to-zone O-D matrices, it is necessary to assign extracted stay locations to Census tracts or another type of zone that is defined. A relational database was used to store Census information for the study area in a standard format. A Postgres program along with an open-source spatial extension PostGIS was used to store and manipulate Census data and other geographic data, such as road network data. Given the current cost of computing resources, these systems provide adequate performance for storing static GIS and Census data. They have convenient, mature interfaces for easy access. In addition, this database was also used to store aggregated results from the various analyses so that they could be made available to interactive web application programming interfaces (APIs) and visualization platforms. 5.5.2 Aggregating Stay Points to Zones Polygons of Census tracts or TAZs and demographic information associated with them were stored in a relational database. However, it is computationally inefficient to perform point-in- polygon calculations for each user or call record in a CDR data set. To dramatically speed up these computations, the research team rasterized polygons into small pixel grids in which each pixel value is a unique identifier for the Census tract covering that pixel. This raster was then used as a look-up table for converting the latitude and longitude of CDR data into Census tract IDs. The rasterization introduced some error along the borders of tracts, but these errors were minimized by making pixel sizes much smaller than the resolution of the location estimates Source: Widhalm et al. 2015. (a) Boston survey (b) Boston CDR Figure 5-9. Stay duration (hours) in (a) MTS and (b) CDR data.

68 Cell Phone Location Data for Travel Behavior Analysis of calls between 10 meters and 100 meters. By using this method, the stay points were easily converted into zones such as Census tracts. The method is critical, given that it supports further in-depth analyses of cell phone data for providing estimates of travel demand. 5.6 Summary This technical chapter discusses the details of how daily trajectories are extracted from noisy and massive cell phone CDR data. The discussion starts with the motivation for this approach and focuses on how the noise from these CDR data is removed to arrive at meaningful data for transportation analysis. The value of the CDR data lies in their analysis to make key inferences regarding the locations and the activities of the respondent carrying a cell phone device through- out the day. The chapter first reviews the steps needed to identify activity types at detected stay locations where individuals spend time to conduct their activities. The temporal patterns related to each activity, including the start times and the duration of individual activities, are also examined. The chapter describes how grid-based and point-based algorithms are used to identify and extract stay points and stay regions by analyzing traces, locations, and the time spent at each location. Examples of stay extraction results are presented with data from an individual user. The density of stay locations and the duration of activities by time of arrival are presented. Finally, the results are aggregated to the zone level to facilitate O-D comparisons.