MINING HETEROGENEOUS DATA FOR SEMANTIC UNDERSTANDING OF MOBILITY DATA

Abstract

With the prevalence of positioning technology, an increasing amount of human mobility data becomes available nowadays, including geotagged social media data, location records collected by mobile phone applications, and GPS traces collected by navigation services. There have been tremendous interests in mining different mobility patterns for understanding human activities and behaviors. While the mobility data are valuable, they are often numeric or categorical in nature, (e.g., a GPS point with timestamp and geo-coordinates). As a result, the subsequent mined patterns from the data often have limited semantics. At the same time, a massive volume of spatial contexts (e.g., venue databases and geotagged tweets) provides us with rich semantics about urban dynamics. By combining the mobility data with surrounding contexts, we are able to understand the semantics of human mobility. Semantics enriched mobility data can benefit various applications such as automatic human activity space inference and target advertisements.

This dissertation describes several recent attempts in fusing external context data for understanding the human mobility data. I will motivate the problem by presenting one key limitation of conventional mobility pattern mining approaches. A fundamental step in understanding the semantics is the mobility record annotation problem, that is, to associate a raw mobility record with the relevant surrounding context. More specifically, I have proposed to use words from social media as a source of dynamic event information. I have also proposed a framework to model dependencies among annotations for individual and collective movements. As the context data could have duplicates, I have proposed a label propagation method for addressing the annotation problem under noisy contexts. Finally, I will present recent collaboration results on applying the proposed framework to a practical social science study.

Chapter 1 | Semantic Annotation of Mobility Data

1.1 Understand semantics of mobility data

In the past decade, positioning technologies have been embedded into many aspects of our world. Consequently, a huge amount of mobility data have been collected from smartphones carried by mobile users, sensor tags attached to animals, GPS systems on vehicles, and location-based service by social media platforms. In general, such mobility data are represented by a sequence of timestamped geographic coordinates (e.g., GPS coordinates or cell tower ids). The mobility data embed with rich knowledge about moving objects and have high-impact applications:

• Spatiotemporal interactions embedded in the movement of human may reveal relationships among them such as family or colleague relationships. The day-to-day interactions reveal the complex social structure of human society.
• Tracking and monitoring animal movement is important in addressing environmental challenges such as climate changes, vegetation regression, invasive species identification.
• Trajectories of vehicles or vessels may reveal traffic patterns at different regions. Such knowledge can assist detection of suspicious events. In urban planning domain, traffic patterns mined from trajectories can help to improve road arrangement and detect flaws in the design.

With valuable applications in mind, researchers have spent extended efforts in mining interpretable patterns from the mobility data. Specifically, the patterns studied can be categorized into three levels: (i) individual, (ii) pairwise, and (iii) collective patterns. At an individual level, researchers have studied, periodic pattern [1,2] , representative behaviors [3,4] , and frequent movement pattern [5] . At a pairwise level, various distance measures have been proposed, such as Dynamic Time Warping (DTW) [6] , Longest Common Subsequences (LCSS) [7] , Edit Distance on Real sequence (EDR) [8] , and Edit distance with Real Penalty (ERP) [9] . Researchers have also been looking at more explicit relationship patterns, such as attraction/avoidance [10] , and following [11] relationships. At a collective level, moving objects clusters have been extensively studied. Representative methods include moving cluster [12] , flock [13–16] , convoy [17] , and swarm [18] . Gathering pattern [19] has also been explored. While they are useful for understanding the inherent moving behaviors of a mobile user, they do not provide anycontextual semantics required for understanding the intended activities of the user, because they focus on mobility data alone.

Given the location history of a mobile user (or trajectory of a moving object), one of the most fundamental and important questions one may ask is: What is the true destination (or the reason) for this person (object) to visit a certain location at a particular time? In other words, we wish to understand the semantics of the mobility data. Generally, the semantics could be the landmark information (e.g., a museum or a shopping mall) or information about the events attended (e.g., basketball game, movies or exhibition). The semantics provide us with richer and much more interpretable information about a mobile user (a moving object). The semantics of the movements are important. We start this dissertation by motivating the problem of understanding the semantics in the following section.

1.2 Motivation

1.2.1         Limitations of Mobility Patterns

While the inherited patterns from mobility data reveal meaningful information about the moving objects, mobility patterns alone do not explicitly consider the context of the movement. As a result, the patterns mined from the mobility data

(a)                                                       (b)

Figure 1.1. An illustrative example depicting the importance of context in adding semantics to the mobility data. The figures show a trivial following pattern mined from two trajectories of two Baboons without (a.) or with (b.) context.

could be trivial and misleading. In general, the context includes information about surrounding environment. The context could be static (e.g., name of the place, or type of the location) or dynamic (e.g., events information, or user comments generated at places). Considering the context information, we are able to understand the mobility in a finer-detail. Here we present two examples to depict the drawbacks of a pattern mining approach.

A case of trivial pattern. We developed a data mining algorithm for mining following patterns from two trajectories [20] . The following pattern is defined as follows. Suppose we are given the trajectories of two moving objects, denoted by

R = r₁r₂ …r_n and S = s₁s₂ …s_n respectively, where r_i and s_i are the locations

(i.e., longitude and latitude) recorded at the same timestamp i, where they are sampled at synchronized timestamps. We note that if R is following S at timestamp i, then r_i must be spatially close to some location s_j, and S arrives at location s_j ahead of R (i.e., j < i). Given thresholds d_max and l_max, a location pair (r_i,s_j) is said to be a following pair if kr_i − s_jk < d_max and 0 < i − j ≤ l_max. A following pattern is defined as a time interval consisting of most following pairs (i.e., significantly more than the number of following pairs appeared by random).

Example 1 We applied the developed algorithm on the trajectories of two Baboons for studying the social structure of Baboons. Figure 1.1(a) illustrates one pattern we found in the Baboons’ trajectories. We can see that the Baboon A (blue) followed

Baboon B (red) during the time. While it seemly interesting, the pattern is actually a

(a)                                                       (b)

Figure 1.2. Another illustrative example depicting the importance of context in adding semantics to the mobility data. The figures show co-location patterns mined from two mobile users’ movements without (a.) or with (b.) context.

trivial case. Figure 1.1(b) further plots the following trajectories with the contextual information (provided by Google Earth). We can now clearly see that the two Baboon moved along a road. Considering the road information, the following pattern is more likely to be a result of Baboon group migration, rather than suggesting social relation between the two animals.

The example depicts the limitation of a pattern only approach, where for a majority of the time, the reasons behind the formation of the patterns are not expressed in the patterns themselves. In this example, a following pattern expressing the social hierarchy in the Baboon group would compare the same as the following pattern appeared as part of the group movements, if we are to only look at the patterns. However, it is to see that by considering the contexts (where the reasons of the formations are often embedded) we can easily differentiate an interesting case with a trivial case.

A case of misleading inference. The mobility patterns are often used as units for inferring characteristics. Patterns deprived of semantics may often lead to incorrect inference results. Here, we present another example in the friendship classification problem, where the goal is to classify whether two mobile users are friends or not based on spatial signals (e.g., GPS trajectories).

Example 2 For the friendship classification problem, it is common to assume that the number of co-locating events positively correlates with the strength of the relationship. Co-locating events are defined as the number of times the two users are spatially close. Again, Figure 1.2(a) shows that two people have co-located at one location for 20 times in a week (without context). However, as Figure 1.2(b) further plots the surrounding environment of the co-location events, we can see that all the co-location events happened at Penn Station, which is a major transportation hub in New York City. It is very likely for the two individual to meet (co-locate) at random when commuting.

In this example, given that the frequency of co-location is quite significant, we may infer that the two mobile users are friends. However, once again, if we further account for the contexts where the events took place, our inference could conclude otherwise. It is easy to see here again the importance of considering the spatial contexts where the mobility patterns took place. The inference would be more reliable with the contexts.

1.2.2          An Autonomous Social Sensing Framework

This dissertation is also motivated by the autonomous social sensing paradigm for social studies, where human behaviors are inferred from sensory data rather than self-reporting survey for scaling. More specifically, we consider an application of the mobility annotation in the human activity space study that could be made fully automatic with annotation methods.

With the advent of GIS and GPS technologies interest in activity space has grown. The ideas behind activity space research span several decades of work by behavioral geographers, sociologists, and environmental psychologists [21,22] . This literature suggests that one’s home anchors an activity space whose contours are shaped by daily routes and destinations. Indeed, the contemporary literature on activity spaces, confirms that tasks such as working, attending school, shopping, socializing, or going to a place of worship link people to multiple neighborhoods beyond their residential location [23] . By collecting new types of mobility data using GPS will enable better quantification of residential and non-residential exposure to both risks and access to resources and thereby push research on ’health and place’ [23,24] . The newly raised challenges in dealing with the new types of mobility data call from collaborations across social science and computational domains.

To accurately measure the activity space of human subjects, the conventional survey approaches require tremendous resources and time to scale up. Here we start with example scenarios depicting the drawbacks of this conventional approach.

Example 3 A group of social scientists is interested in how an adult’s accessibility to good-quality food relates to the person’s health condition and economic status. They conduct a survey that gathers data on food-related behaviors. The survey includes about a hundred questions, asking details on where the food-related behaviors take place. The social scientists gather responses from 20 qualified participants to the hour-long survey over the period of a month. When examining the responses to surveys, the scientists notice that the participants often struggled to recall the names and addresses of many of the places they visited (e.g., grocery stores, and local shops), especially places further from home and or visited less frequently. The social scientists are also interested in the energy balance and the role of accessibility to physical exercises. They would like to ask similar questions but on physical exercises

related activities.

The example depicts the drawbacks of the conventional approach: (1) require tremendous effort and time to scale up for both conductor and participants, (2) measurement errors in participants’ responses, and (3) limited re-usability for different studies. Meanwhile, ubiquitous positioning technologies and mobile phones provide us a unique way of recording human behaviors in the sensory (e.g., GPS) data. The technological advancement gives birth to social sensing approaches, where instead of responding to questionnaires, subjects contribute their sensory data (e.g., GPS traces) via mobile phones or GPS sensors [3,4,25] . Answers to research questions regarding human behavior are inferred from the data via computational models.

Here we consider an ideal case example:

Example 4 Inspired by the new concept, the social scientists teamed up with computer scientists for a new study. They develop a mobile phone application that records the GPS signals running in the background. The participants who consent to the study download the application and the data are remotely uploaded to a server. The GPS data cover most positioning information about the participants. Given the data, the social scientist can now use various inference methods for different types of environmental exposure studies.

It is easy to see that in the second example, the algorithmic empowered approach can be made easily scalable, as it has limited, even one-time, development cost, small distribution costs, and minimal burdens on the participants. It is also ideal for exploratory studies, as inferences can be done at anytime post-collection. While seemly advantageous, the scenario is built upon accurate and reliable computational methods, where human activities can be accurately inferred: if a person is observed at some location at a specific time, which venue is the intended destination of this

person?

1.3 Problem Definition

Figure 1.3. Mobility data annotation framework.

In this section, we present a formalism of the problem being addressed, and give an outline of this dissertation. For the semantic annotation problem, our goal is to understand the semantics behind the observed movement data. It is easy to see that the mobility data alone is not sufficient, as the data contain only numerical values (e.g., timestamps, and geographic locations). Therefore, it is necessary to harness external context data.

Figure 1.3 illustrates the overall framework. We consider the mobility data as a set of spatio-temporal points, i.e., R = {r₁,r₂,…,r_n}, where each reading r_i is consists of the raw geographic coordinates, timestamp and additional features, i.e., r_i = (loc_i,t_i). Various types of mobility data can be considered here, such as, densely sampled movement trajectories, cell tower identifications, or check-in locations.

Generally, the context data are set of object associated with locations, C = {c₁,c₂,…,c_m}, where each context c ∈ C is tuple of its geographic coordinates loc_j and a set of features f describing the venue, i.e., c_j = (loc_j,f). Various spatial information can be considered as context, such as, venue or event databases, or land type information. Given the data from two channels, we now define the semantic annotation problem as:

Problem 1 (Semantic Annotation Problem) With the mobility data of a user (or multiple users), R = {r₁,r₂,…,r_n}, and the context dataset, C = {c₁,c₂,…,c_m}, our goal is to find the sequence of most relevant assignment Y ,…,y_n^∗ > where y_i^∗ ∈ C denoting the context assignment for each movement point r_i ∈ R.

We have formally the following:

Y ^∗ = arg       min        f(R;C),                                         (1.1)

<y_i:1≤i≤n>

where f(·) is a relevance measure of the annotations to the given mobility data. The essence of the problem is how to measure the relevance of surrounding contexts with the trajectory data from a user. The relevance measure f(·) takes different forms (which also depends on the applications). In this dissertation, we will introduce several recent advancements.

1.4 Literature in Mobility Data Mining and Annotation

In literature, numerous methods have been proposed to extract patterns from the mobility data. Representative studies include stop and move detection [26–28] , activity recognition (e.g., biking and walking) [29–33] , significant place extraction [28,34–36] , and frequent regular pattern discovery [1,5,37,38] for individual movement. Researchers have also looked at patterns for pairs of moving object, such as co-location events [39] , following [11] , and attraction and avoidance [10] , and patterns for collective movements, such as gathering patterns [40] , moving cluster [12] , flock [13–16] , convoy [17] , and swarm [18] . These works mainly focus

Figure 1.4. Ambiguity in annotating the location records with contexts.

on the inherent trajectory patterns. In other words, the patterns are mined or inferred by considering the mobility data alone.

Web 2.0 has gradually built us a rich data warehouse. There is an enormous amount of spatial context data, such as POI (point of interest) databases, gazetteers, digital maps for the road network, social media sites (e.g., Twitter, Foursquare, and Facebook). With increasing amount of spatial context, there has been an emerging trend in the data mining community for considering the contextual information in mobility data research. Representatively, spatial contexts, such as road network, venue database, have demonstrated their unique utility in solving urban computing problems [41] . Location-based recommendation systems have also been utilizing various contexts, such as venue reviews, user profiles, for more accurate prediction and recommendations [42] .

However, little has been done in solving the problem of the mobility data annotation problem, where we aim to associate the correct context with mobility records of users to understand the movement semantics. The distinct challenge in solving the mobility data annotation lies in the ambiguity of surrounding contexts. Because of the data collection mechanism and GPS errors, we may not observe a person locating at the actual location where he was visiting. Take Figure 1.4 as an example. Given a GPS location of the user, how can we know whether he is visiting the clothing store American Apparel or eating at Five Guys restaurant? And even if we have accurate GPS locations, a geographical location could be associated with many venues at the same time. For example, the largest transition center of New York City, Penn Station, sits right beneath Madison Square Garden, a multi-purpose indoor arena. As another example, a multi-function building at Times Square could have restaurants, stores, and offices, all of which share the same location. How can we know which venue is the true destination in these cases? As a result, the assumption adopted by urban computing applications that all nearby contexts are relevant no longer holds for understanding fine-grained semantic of each movement record. Furthermore, the fact that only the movement data are used as input makes the problem more challenging, as supervised approaches (such as methods used in recommendation system) have limited utilized due to sparse labels. In rest of the section, we survey studies that tackling the annotation problem and position this dissertation respectively.

Point-wise annotation. A line of research focuses on how to measure the relevance between a context and a GPS point. Along with this line, methods have been using various types of static information including landmarks [26,43] , landscape and environment [31] , and land-use categories [44,45] . In these papers, a location (i.e., a point, a region, or a road segment) is associated with a set ofpredefined and fixed attributes, such as a landmark (e.g., “Eiffel tower”) or a land type (e.g., residential area or business center). A location on the trajectory is then annotated using the attributes of nearby locations [26,31] . Yan et al. [44,45] extend the point-based annotation to three kinds of objects: points, lines, and regions based on spatial join, using direction, distance, and topological spatial relations such as intersections.

While the contextual semantics used in these studies are static, Wu et al. [46]

(Chapter 2) propose to utilize words from social media data (e.g., geo-tagged tweets) for event annotation. Compared with static contexts represented by spatial shapes, words in social media are complex as they occur over the space. To address the problem, Wu et al. [46] . propose to use density estimated by Kernel density estimation (KDE) for considering both distance and popularity factors.

Dependency-based annotation. The point-wise annotation method has a clear drawback: two different users at the same place at the same time will be annotated the same, regardless of their own varying reasons for or interests in being at the location/venue, as the annotation is independently considered. More recently, several studies start to consider dependencies among records for improving a point-wise measure.

Based on a point-wise measure, Yan et al. [44,45] propose a hidden Markov model (Hidden Markov Model) to consider the transition dependency in individual movement. However, the HMM requires prior knowledge of a user level transition matrix for personalized annotations. Wu and Li [47] (Chapter 3) propose to model the implicit user interests as consistency among the annotations based on observations from human movements, i.e., human movements express strong regularity in time and space. Correspondingly, a Markov Random Field framework is proposed for personalization annotation, where no prior knowledge needed. A similar method extends [48] to densely sampled trajectory data has also been studied in a human activity space study in this dissertation. In another study, Su et al. [49] propose to use conditional random fields (CRF) for summarizing statistics vehicle trajectories into textual templates as semantics.

The mobility data may not come from each individual but collectively, e.g., taxi trips (Origin-Destination pairs). Wu et al. [48] (Chapter 4) consider the annotation problem on taxi drop-offs. To model the collective interests, a label propagation method is developed utilizing the observation that similar records (i.e., same time of the day, and spatially close records) tend to visit similar places.

Table 1.1. Categorization of the literature solving the mobility data annotation problem by data used.

Categorization by the use of data. While aiming to understand the semantics of movement in general, annotation methods proposed have been developed under diverse application scenarios. Table 1.1 categorizes aforementioned annotation studies by the data used. Su et al. [49] propose to annotate vehicle moving statistics (along with road information) for a semantic summarization. Yan et al. [44,45,50] broadly consider various context data of different geometries for densely sampled trajectory. Wu et al. [46] show that social media (i.e., geo-tagged tweets) can be used a source of event information for check-in like movements. Wu and Li [47] and Wu et al. [48] (Chapter 4) consider the venue annotation problem on check-in like movement data and taxi drop-offs for understanding mobile user intentions. Most recently, Wu et al. [51] (Chapter 5) argue that human movement data in the form of check-ins are highly biased and do not cover a full spectrum of human activities. Therefore, densely sampled trajectories of 89 consent participants are used for understanding the human activities space by annotating them with venues. The variety of the data used also signals one of the challenges in studying annotation problem, where what can be done is largely constrained by the type of accessible data.

In this dissertation, we present various recent attempts in tackling the semantic annotation problem. More specifically, we introduce methodologies for using social media (Chapter 2), and venue databases as the context (Chapter 3 and Chapter 4). At last in Chapter 5, we summarize this dissertation by applying proposed methodologies in a social science application for studying human activity

space.

MINING HETEROGENEOUS DATA FOR SEMANTIC UNDERSTANDING OF MOBILITY DATA