Scalable and privacy-respectful interactive discovery of place semantics from human mobility traces

Abstract

Mobility diaries of a large number of people are needed for assessing transportation infrastructure and spatial development planning. Acquisition of personal mobility diaries through population surveys is a costly and error-prone endeavour. We examine an alternative approach to obtaining similar information from episodic digital traces of people’s presence in various locations, which appear when people use their mobile devices for making phone calls, accessing the Internet or posting georeferenced contents (texts, photos or videos) in social media. Having episodic traces of a person over a long time period, it is possible to detect significant (repeatedly visited) personal places and identify them as home, work or place of social activities based on temporal patterns of a person’s presence in these places. Such analysis, however, can lead to compromising personal privacy. We have investigated the feasibility of deriving place meanings and reconstructing personal mobility diaries while preserving the privacy of individuals whose data are analysed. We have devised a visual analytics approach and a set of supporting tools making such privacy-preserving analysis possible. The approach was tested in two case studies with publicly available data: simulated tracks from the VAST Challenge 2014 and real traces built from georeferenced Twitter posts.

Keywords

Visual analytics episodic movement data personal mobility behaviour location type classification mobility

Introduction

Information about human daily mobility, that is, where people travel, when and why, is necessary for transportation management, urban planning and public health studies. This kind of information can be obtained from daily mobility diaries of a large sample of people. The way of using mobility diaries is briefly described.

Use of daily mobility diaries

In planning any changes in transportation infrastructure, public transportation or land use (LU) in populated areas, it is necessary to obtain realistic predictions of how the changes may affect the daily lives of the population, in particular, their daily mobility behaviours, and how well the changed environment will suit the daily needs of the people. For this purpose, it is necessary to estimate how many people at different times of the day need to get to the places of their work or study; to schools or kindergartens of their children; to places for shopping, health care, services, entertainment and recreation and back to their home places. This is done in the following way.

A large set of personal mobility diaries from a sample of the population is obtained through a survey campaign. In the diaries, the responders describe at what times of the day they typically go to what kinds of places and for what purposes. A planner generates a so-called synthetic population where each virtual individual represents one person from the real population currently living or expected to live in the area to be affected by the planned changes. The collected diaries are randomly distributed among the virtual individuals and treated as their personal plans for a day. The place types referred to in the diaries are substituted by concrete locations in the area based on the current or planned LU distribution. Then agent-based simulation methods¹ are used to simulate movements of the virtual individuals through the planned environment for implementing their personal plans. The individual movements are aggregated into collective flows. The simulation may uncover bottlenecks in the transportation infrastructure, show where people’s time may be lost, reveal unused facilities and so on. Based on such findings, the planner can understand what needs to be improved and in what way. Similar studies are undertaken to forecast the impacts of possible changes in the population number or structure.

Data acquisition problem

Personal mobility diaries are traditionally acquired through population surveys, which is a costly and error-prone endeavour. Therefore, researchers have been seeking alternative ways to obtain similar information, preferably, from already existing data containing traces of people’s presence and activities in different places at different times, such as mobile phone use records. Given that mobile phones are actively used throughout a day, the daily mobility can be reasonably well reflected in the data. Since the mobile phone data are not widely accessible, other publicly available data with similar properties, in particular, georeferenced posts in Twitter and other social media, have also been investigated. Such posts are most often sent from mobile devices; hence, their coordinates and timestamps can be used to trace the users’ mobility.

There is a large content gap between daily mobility diaries and automatically collected data with time-stamped positions of people. The latter lack semantics, which makes it difficult to ascertain whether a phone call or Twitter post has been made from home, work place, public transport, grocery store or other type of location. Hence, to be able to reconstruct diary-like information from mobility data, it is necessary to extract significant locations and determine their person-specific meaning or purpose, such as home, work, shopping, sports and social activities.

An earlier work² demonstrated a possibility of extracting frequently visited places from raw position data of a person (specifically, GPS tracks) covering a long time period and identifying the meanings of these places by analysing temporal patterns of the person’s presence. However, what is easy to do with data from a few people becomes very problematic for hundreds or thousands of people. Moreover, analysing such data at the individual level can reveal sensitive personal information, thus compromising personal privacy. Hence, the challenge is to find approaches to deriving place semantics for a large number of people by analysing entire population and groups (overall and intermediate levels³) instead of individuals.

A further difficulty is posed by the episodic character of mobile phone use records, georeferenced tweets and similar data.^4,5 Persons’ positions are recorded only when specific events occur: starting a call, sending an SMS, accessing a web page or sending a tweet. For the times between the events, the whereabouts of the people are unknown. This means, in particular, that the timestamps of entering and leaving places and the duration of staying are not known and cannot be used in the analysis, which is different from analysing GPS tracks with fine temporal resolution.² With such episodic mobility data, the place semantics need to be derived from temporal distributions of events recorded at those places. The feasibility of this concept has been demonstrated on the example of a few individuals considered separately.⁶ The challenge is to extend it to many individuals analysed simultaneously.

To summarize, there is a need for methods and tools for extracting repeatedly visited personal places and deriving the place semantics (i.e. meanings or purposes) from episodic mobility data of a large number of people. To fulfil this need, several problems must be solved as follows:

Work effectively with massive, long-term data from a large number of people.

Be able to deal with the episodic character of the data.

Respect personal privacy using only aggregated data for the whole population or large groups of people and avoiding access to individual data, in particular, people’s locations.

Finding efficient and privacy-preserving approaches to deriving information equivalent to daily mobility diaries from semantically poor episodic movement data was one of the objectives of a European Union (EU)-funded research project DataSim (http://www.uhasselt.be/UH/About-DATASIM/Problems-addressed.html). Our research on determining place semantics with the help of visual analytics techniques was a part of this project. The goal was not to develop ready-to-use tools for city planners and transportation managers but to devise a suitable methodology and test its feasibility.

This article describes the methodology we have devised and demonstrates its feasibility using two case studies with simulated tracks from the VAST Challenge 2014, for which ground truth is available, and real traces built from georeferenced tweets posted during 1 year within a metropolitan area encompassing San Diego (USA) and the surrounding communities.

The website http://geoanalytics.net/and/papers/placeSemantics/ contains supplementary materials, which include texts providing additional details and explanations concerning the analytical procedure, a video demonstrating the process of inferring place semantics and the interactive visual techniques employed and a link to the data we used in this article.

Related works

Obtaining significant places from movement data

The term ‘significant places’ is henceforth used to refer to places repeatedly and purposefully visited by individuals and therefore having certain meanings (semantics) for the individuals, such as home, work, place for shopping, recreation and social activities.

Potentially interesting places have been extracted from mobility data using different variants of clustering.^7–9 Semantic information can be attached to these places by matching them with locations of predefined places of interest (POIs).^10,11 This approach, however, does not uncover personal POIs such as home, work, child’s school and place of regular shopping. Mobile phone data have been used for inferring LU categories based on an observation that residential, commercial, industrial and green areas significantly differ in temporal profiles of mobile phone activities.¹² A few works describe ad hoc approaches to finding and interpreting personal places. Ahas et al.¹³ use mobile phone data to identify home and work places based on the frequency of the person’s calls from each place, their average time of the day and the standard deviation of the time of the day using a set of classification rules that are based on the researchers’ background knowledge. Isaacman et al.¹⁴ derived place classification rules by analysing labelled data of volunteers. The distinguishing attributes were the visit frequency, duration and the counts of phone use events during work hours (13:00–17:00) and during home hours (19:00–07:00). So far, no systematic approaches to identification of different types of personal POI have been reported.

Mobile phone data have also been used for analysing personal daily mobility behaviours without trying to establish place meanings. Daily sequences of persons’ positions can be transformed into graphs with nodes corresponding to visited places and directed links representing trips between the places. Surprisingly, out of millions of possible graph structures, only 17 are of statistical significance. These 17 graphs are called human mobility motifs.¹⁵ Based on this work, it was shown that daily travel behaviours are strikingly similar for different cities and countries while there are also differences explainable by demographic differences between cities.¹⁶

Twitter data, specifically, Foursquare check-in posts extracted from Twitter, were also analysed for deriving location types. It was found that different types of public places (coffee shops, sub shops, book stores, etc.) have characteristic daily and weekly temporal patterns of visits, which can be used for place-type classification.^17,18 Better results can be achieved through additional analysis of term occurrences in the text content of the check-in tweets.¹⁹

Related works in visual analytics

In visual analytics, no specific methods for extraction of semantic information from mobility data have been proposed so far. There are works in which semantic information is derived from contents of georeferenced Twitter or Twitter-like messages and used in spatio-temporal analysis. In VAST Challenge 2011,²⁰ synthetic Twitter-like data were analysed for understanding the cause, character and spatio-temporal evolution of a simulated epidemic outbreak; however, these works were not related to place semantics.

Scatterblogs 2²¹ is a real-time monitoring visual analysis tool for Twitter streams using visual composition of content filters to detect and visualize the spatio-temporal distributions of thematic events but not their association with specific places.

Krüger et al.²² propose to semantically enrich vehicle GPS trajectories with data about public POI obtained from Foursquare by associating POI categories with spatial clusters of trajectory endpoints, that is, frequent destinations. Their work focuses on visual exploration of trip purposes while accounting for POI categorization uncertainties at multiple spatial scales in space and time.

Protection of personal privacy

Application of visual analytics methods to data including people’s geographic positions is associated with privacy issues.^23–25 Aggregation of mobility data of multiple individuals based on spatial and spatio-temporal generalization helps protect personal privacy,²⁶ but this approach is suited for analysis of mass movements rather than personal mobility. Another approach is obfuscation of individuals’ real positions, that is, replacing points by regions; however, obfuscation-based techniques fail to hide repeatedly visited locations and regularly followed routes.²³ The inherent problems of location privacy disappear when mobility data are transformed from geographic space to abstract spaces⁵ (section 9.6). There is an example of applying such a transformation to data with previously attached semantic labels,²⁷ but it is not discussed how the required semantic information can be obtained without compromising personal privacy.

Dasgupta and Kosara²⁸ discuss privacy issues associated with non-geographic data and propose privacy-preserving visualization with parallel coordinates incorporating the formal concepts of k-anonymity and l-diversity developed in the field of data mining. Our work does not aim at developing a mechanism that formally guarantees chosen levels of privacy protection. The goal is to investigate the principal possibility of extracting personal places and attaching semantic labels to them without accessing geographical positions of individuals.

Input data, problem statement and methodology overview

Format and general characteristics of input data

Our methodology is intended for analysis of episodic human mobility traces, such as records about the use of mobile phones or other mobile devices at various locations. The main components of such data are person’s (user’s) identifier, location specification and timestamp. The location specification may be available in the form of geographic coordinates (longitude and latitude) or as a reference to some spatial object with known coordinates, such as mobile network antennas. An example of episodic mobility data we deal with is given in Figure 1, which demonstrates the typical temporal sparseness and irregularity of such data.

Mobility data may also have other components, for example, the type of activity, such as phone calling, sending SMS and accessing a website. Geolocated social media posts include some content (text, photo or video), which may be supplied with a title and/or hashtags, and media-specific attributes. Although some of the components may contain useful location-related information, such as venue types in Foursquare check-in records,^17–19,22 we intentionally limit the core of our methodology to using only the main components (i.e. person identifier, location and time), which are present in all kinds of mobility data. This means that the approach does not require any additional components to be present in the data, but it also does not prohibit the use of additional components when available.

The extraction of significant personal places and derivation of the place meanings require the data to cover a sufficiently long time period and include a sufficient number of presence records for these places. We estimate the shortest meaningful time period to be at least 1 week for identifying the home and work places and at least 2 weeks for identifying other types of places, which are not expected to be visited every day. However, this only applies to data with high temporal frequency, which can come from active mobile phone users or active bloggers. When data are temporally sparse, it is necessary to have records from a much longer time period.

Besides mobility data, the methodology requires additional data that can be used for validating the plausibility of the assignment of semantic labels to places. One possibility is land use data. For example, when a set of places is going to be labelled as ‘home’, it should be checked whether most of them are in residential areas. Another possibility is to utilize data about relevant geographical objects, such as public transportation stops, schools, shops and restaurants. Such objects are commonly called ‘points of interest’ (POI). POI data can be obtained from map feature services, such as OpenStreetMap (www.openstreetmap.org), or retrieved from geographic databases. It is then possible to derive counts of different types of POIs inside places or within a specified distance threshold. Before assigning some meaning to a set of places, the compatibility of this meaning with the POI types occurring in these places should be checked.

Hence, the proposed methodology for acquisition of place semantics requires two datasets: (1) time-stamped positions of people and (2) LU or POI data that can be used for validation of the place meaning assignments.

Data examples

One of the types of mobility data addressed by our approach is mobile phone use records; however, we have no possibility of using a dataset of this type for published work due to privacy restrictions. Instead, we demonstrate our approach using two openly accessible examples of mobility data, which have properties similar to those of mobile phone use data.

VAST Challenge 2014 Mini-Challenge 2

The original dataset provided for the VAST Challenge 2014 Mini-Challenge 2²⁹ consists of simulated tracks of cars with duration of 2 weeks. The records include timestamps, car identifiers and coordinates. We used the tracks of 35 personal cars and ignored the tracks of five remaining vehicles utilized only for business purposes. The full tracks cannot be classified as episodic mobility data because of high temporal resolution (1 s), which allows determining the exact times of arriving at each visited place and leaving it. To have a suitable example of episodic data, we extracted a subset of the car position records by selecting the positions of stops and taking a 25% sample of these positions. This gave us 1469 records imitating the properties of episodic mobility data, as depicted in Figure 1.

No data similar to LU or POI data were provided for the challenge. As the underlying territory for the car tacks is fictitious, existing databases or map feature services cannot give us suitable information about places. To create a substitute for POI data, we utilized simulated credit card transaction records, also available for the challenge. The details of pre-processing the VAST Challenge data are given in Appendix 1. We would like to stress that although the conditions of the challenge did not require it, we analysed the data in a privacy-preserving way, that is, without looking at any personal data.

San Diego tweets

Georeferenced Twitter messages posted in the metropolitan area of San Diego were collected over a period of 302 days from the end of September 2012 until the end of July 2013. In the context of our task, we are only interested in data from residents of the area. To separate residents from visitors, we used a simple filter: there must be at least 100 tweets from a person, and the time span between the first and the last tweets must be at least 100 days. This rather arbitrary filter was nevertheless adequate for obtaining a test dataset; it was not our goal to precisely determine all residents of the area. The selected subset consists of about 2.5 million records of 4286 individuals. The geographical extent of the area is 112 × 103 km. To validate place meaning assignments, we obtained LU data for the San Diego area in the form of polygons with labels specifying the LU classes within the polygon boundaries.

Please note that the texts of the tweets were not used as sources of place-related semantic information in this case study. We intentionally used only the minimum subset of fields shared by all kinds of mobility data, that is, person’s identifier, geographic coordinates and time, to ensure the general applicability of the methodology. Still, our approach as such does not preclude the use of information derived from Twitter texts. In our earlier work,³⁰ we analysed the temporal and spatial distributions of occurrences of different topics (subjects) people tweeted about, such as ‘family’, home, ‘work’, ‘education’, ‘friends’ and ‘food’. High frequencies of certain topic(s) in a place may be related to the place meaning; however, it should be taken into account that people may tweet about any topic from any kind of place. For example, one may tweet about work-related topics while being at home or at a beach and tweet about food and drinks while being at work. Hence, the topics occurring in a place cannot be used as absolute indicators of the place meanings but rather as supporting evidence. Our methodology allows the analyst to utilize topic frequencies extracted from message texts in a way similar to the utilization of LU or POI information. In particular, the multi-attribute bar chart display described in section ‘Attaching LU or POI information to places’ can be used to visualize and analyse aggregated topic frequencies for sets of places.

Problem statement

Having episodic mobility data as shown in Figure 1, we aim at obtaining so-called semantic trajectories, which may look as shown in Figure 2. In semantic trajectories, the geographic locations are substituted by semantic labels denoting the meanings of the visited places or types of activities performed. The transformation of the original mobility data into semantic trajectories needs to be done for a large set of individuals in such a way that the geographic positions of the individuals are hidden from the analyst. Please note that the resulting semantic trajectories are devoid of geographic positions and thus can be viewed and further analysed without compromising individual’s location privacy.

To obtain semantic trajectories from mobility data, the following tasks need to be fulfilled:

Extract personal places repeatedly visited by each individual.

Identify the most likely individual-specific meanings of the extracted personal places and attach semantic labels denoting these meanings to the places.

For the entire set of individuals, extract public places visited by multiple individuals.

Identify the most likely meanings of the public places and attach corresponding semantic labels to the places.

For each point in the original data, find a personal or public place containing it and replace the geographic reference of the point by the semantic label of the place.

The resulting semantic trajectories do not yet adequately approximate personal mobility diaries because they are episodic, like the original mobility data. That is, the trajectories include only a subset of places that were actually visited on each day. For example, trip 1 in Figure 2 begins with ‘shopping’ at 11:43, although the person was, most probably, at home in the morning and could have also visited other places before appearing in the shopping place. It can also be guessed that the person returned home after ‘outdoor recreation’, but this is not reflected in the data. Hence, in the next stage of analysis, more complete daily semantic trajectories should be reconstructed from partial semantic trajectories. This next stage is, however, beyond the scope of this article.

Methodology overview

To support tasks 1–5 and the following analysis of semantic trajectories, we have devised an analytical workflow shown schematically in Figure 3. On the left, the workflow is represented by a flow chart. In the centre, there are brief comments to the steps of the procedure. On the right, there are references to the article sections and Appendix 2 where these steps are described.

For extracting personal and public places, we developed an automated tool involving clustering of points from episodic mobility data by spatial proximity. To extract personal places, the points of each individual are clustered separately; to extract public places, the points of all people are clustered together. Places are defined by constructing boundaries (spatial convex hulls or buffers) around the point clusters. The tool works automatically. It takes input data from the database, processes them and puts the resulting place boundaries back in the database. Personal places are associated with the identifiers of the individuals they belong to; however, the places and the identifiers of their owners are not shown to the analyst. The place extraction algorithm is described in detail in section ‘Extraction of personal and public places’.

A suite of interactive visual techniques supports the process of determining place meanings. To avoid disclosing possibly sensitive personal information, we have chosen such visualization methods that only show data aggregated over the whole set or groups (clusters) of places and allow no access to individual data:

multi-attribute summary bar chart showing value summaries of multiple numeric attributes (section ‘Attaching LU or POI information to places’);

qualitative histogram showing aggregated counts of qualitative values (section ‘Attaching LU or POI information to places’);

two-dimensional (2D) time histogram showing aggregated 2D time series of place visits (section ‘Exploration of time patterns of place visits’).

Identifying the most probable home and work places is supported by a place ranking tool described in section ‘Multi-criteria evaluation and ranking’. The places of each person are ranked based on several relevant attributes, such as the total number of visit-days and the proportions of visits in the typical work and home hours. The places with the best ranks are considered as candidates for receiving the target meaning, that is, ‘home’ or ‘work’. To check whether these places are sufficiently good candidates, the analyst looks at the associated LU or POI classes, as described in section ‘Validation of place scores and ranks’. The analyst investigates how modifications of the criteria weights affect the selection of the candidate places and the corresponding statistics of the LU or POI classes. Finally, the analyst selects the best set of candidates and assigns the target meaning to them. For target meanings other than ‘home’ and ‘work’, candidate places are selected by means of interactive filtering based on relevant temporal attributes and LU or POI classes. A detailed illustrated example of inferring place meanings from the VAST Challenge data is given in Appendix 3 and in an accompanying video, and section ‘General guidelines for inferring place semantics’ contains general guidelines for place semantics acquisition.

After assigning semantic labels to personal and public places, the derivation of semantic trajectories is performed in a straightforward way (see section ‘Problem statement’, task 5). The resulting semantic trajectories can be explored using a map of an abstract semantic space, as described in section ‘Analysis of semantic trajectories’. In particular, the plausibility of the place meaning assignments can be checked by analysing the emerging patterns of flows (aggregate movements) in the semantic space.

Extraction of personal and public places

In mobility data, the positions of moving objects are often specified as points in the geographic space. Starting from these points, it is necessary to find and delineate repeatedly visited places of each person. POI can be obtained from point data by clustering points in space and building spatial buffers or convex hulls around the clusters.³¹ In our case, clustering of points and place delineation needed to be done separately for each person. Density-based clustering used in previous research³¹ is not fully suitable for the task of extracting personal places. A property of density-based clustering algorithms is that they can build clusters of arbitrary shapes and sizes; thus, they can easily construct a huge cluster covering the whole city centre if the point density is sufficiently high throughout the area. Such a cluster would represent not a single place but multiple places, which is not desirable. Smaller density-based clusters can be obtained by increasing the density threshold. The problem is that the same threshold is applied throughout the whole study space. Since point concentrations are usually not equally dense in different parts of the study area, clustering with high density threshold will miss many point concentrations with lower densities while clustering with low-density threshold will merge together multiple point concentrations located close to one another. Moreover, the density of point concentrations varies not only across space but also across the population: it depends on how actively a person tweets or uses a mobile phone. It is both infeasible and violating personal privacy to look at the point distribution of each person in order to select an individual-based density threshold. The clustering and place delineation must be done in batch mode for all persons; hence, the same parameters have to be used.

We have established thus far that the task of personal place extraction requires a point clustering algorithm that is insensitive to the density variation and allows limiting the spatial extents of the resulting clusters. A spatially bounded point clustering algorithm, used earlier for generating space tessellations,³² can be adapted for this purpose. In short, the algorithm places points in circles with a user-specified maximal radius R_max. When a point is added to a circle, the circle centre is re-computed by averaging the x- and y-coordinates of all its points. When there is no suitable circle for a point, a new circle with the centre at this point is created. After processing all points, the circles containing fewer points than the user-chosen minimal number are discarded, and spatial clusters are formed from the points of the remaining circles. The algorithm allows different point densities in different circles and does not allow the clusters to grow beyond the specified limit R_max. Please note that the resulting clusters only consist of the points and do not include the enclosing circles; hence, the clusters may have smaller radii than R_max and may have arbitrary shapes.

The same algorithm may be used for extracting public places, that is, places visited by many individuals. The difference from extracting personal places is that the algorithm is applied to points representing locations of all persons at once. After the algorithm finishes, only clusters containing points of at least a given minimum number of different persons are retained as the result.

A drawback of this algorithm is that some point groupings may not look like ‘true’ spatial clusters. Thus, two or three spatially compact concentrations of points may be grouped together if they fit in one circle, or a concentration of points may be united with one or a few isolated points scattered around. An illustration of this case is given in Figure 4, left. In such artificial groupings, the maximal point density is not attained at the geometric cluster centre but close to the periphery. This can be used as an indication of poor grouping. Unnatural groupings may be not a problem for generating spatial tessellations, which has been the original goal of the algorithm. However, for the purpose of extracting significant personal or public places, such groupings should be avoided. To alleviate this problem, we have modified the algorithm in the following way:

Input: set of points P = {(x, y)}.

Parameters: maximal and minimal radii R_max and R_min; minimal number of points in a group N_min.

Algorithm:

Apply the base point clustering algorithm to P with the parameter value R_max. Let Γ be the list of resulting groups of points.

Go through Γ. For each group of points G ∈ Γ do the following:

2.1. Let R be the group radius. If R < R_min, go to the next group.

2.2. Else, build a bounding box containing G and divide it into nine equal rectangles by two horizontal and two vertical lines (Figure 1 left). Check if the central rectangle contains fewer points than any other rectangle (this means that the maximal point density is not attained near the geometric centre of the cluster). If not, go to the next group.

2.3. Else, subdivide G into smaller groups (Figure 4 right) by applying the base algorithm to G with the parameter value R/2. Add the resulting groups to Γ and remove G from Γ.

2.4. Redistribute points from the neighbouring groups: if a point is closer to the centre of one of the new groups than to the centre of its current group, move it to the new group.

Remove from Γ the groups where the number of points is less than N_min. Return Γ as the result.

For extracting personal places from the San Diego data, we used the following parameters: R_max = 150 m, R_min = 75 m and N_min = 5. The rationale for choosing the radius range 75–150 m is as follows. We want to avoid combining points related to several semantically different places into one cluster; hence, the radius limit should be small. But then, we should account for possible position errors in the data. Particularly, mobile devices often determine positions using WiFi, which is less accurate than GPS. Empirical studies^33,34 have shown that WiFi positioning errors may be much larger than the 20–40 m officially reported. In the experiments, 70%–90% of the errors were within the range of 0–150 m, and the median error was about 74 m. Hence, using a value smaller than 150 m as the maximal cluster radius is not advisable.

The VAST Challenge data are supposed to imitate GPS data, which are usually quite accurate; however, the data providers intentionally introduced noise in some tracks. We have taken R_max = 100 m, R_min = 75 m and N_min = 2. The latter value is small because the time span of the data is only 2 weeks; even a place that was visited only twice in 2 weeks may be one of the regularly visited personal places.

Another problem to deal with in place extraction is that some places may be quite large. For example, a person may work or study on the campus of University of California, San Diego, the extent of which is 3 × 2 km. The person’s points located on the campus may form multiple small clusters (Figure 5(a); points are represented by pink semi-transparent circles), which will be undesirably interpreted as separate personal places. When the person’s visits are aggregated into such small places, the resulting temporal patterns for these places might not resemble a typical temporal pattern of attending a place of work or study. Please note that points of one person are shown in Figure 5 for illustration purpose only. Analysing data of individuals is not a part of the suggested methodology.

Hence, it is desirable to unite neighbouring small clusters into larger clusters while avoiding the weaknesses of density-based algorithms discussed earlier. To do this, we further extend the space-bounded point clustering algorithm on the basis of the following observation: when two clusters are very close in space, there are points in each of them that could also be the members of the other cluster, that is, their distances to the centre of the other cluster are below the maximal circle radius. We call such points ‘connecting points’. The idea is to unite clusters sharing at least a chosen minimal number of connecting points C_min. To avoid extreme growth of the resulting clusters, the user may set an upper limit $R_{\max}^{+}$ on the radius of merged clusters. Two clusters are not merged if this would result in exceeding $R_{\max}^{+}$ . The following algorithm extension is proposed:

For each pair of neighbouring clusters, find the number of connecting points. Neighbouring clusters are found using the spatial index, which is a part of the base algorithm.³² Make a list of cluster pairs having at least C_min connecting points.

Sort the list of connected cluster pairs in the order of decreasing number of connecting points.

Go through the sorted list. For each pair do the following steps:

3.1. If the radius of the circle enclosing the two clusters exceeds $R_{\max}^{+}$ , skip this pair and go to the next one.

3.2. Else, merge the two clusters. Replace the occurrences of the identifiers of the original clusters in the sorted list by the identifier of the merged cluster. Go to the next pair.

According to this algorithm, strongly connected clusters get higher probability of being merged than more loosely connected clusters. The impact of the parameter $R_{\max}^{+}$ is illustrated in Figure 5. In Figure 5(b), the blue polygons are the convex hulls of the clusters obtained through merging original clusters connected by at least three points without limiting the extents of the resulting clusters. In Figure 5(c), the green polygons are the convex hulls of the clusters obtained with $R_{\max}^{+}$ = 600 m.

For assessing the appropriateness of the clustering results, the analyst looks at the statistics of the resulting cluster radii. The presence of too large values may require the analyst to look at the outlines of the largest clusters, which are drawn on a map without showing the identifiers of the place owners. The results are acceptable when the largest clusters correspond to large geographic objects, such as university campuses, visible on the background map. The spatial convex hulls of the clusters are taken as the place boundaries.

For the San Diego data, clustering without setting $R_{\max}^{+}$ results in obtaining personal places with radii up to 1.5 km and public places with radii up to 4 km, which we judged as too large. We have empirically found that the upper limit of 600 m works well enough. We extracted 38,225 personal and 9301 public places. For the artificial data from the VAST Challenge, there is no possibility to check the largest places against a real geographical background. We set $R_{\max}^{+}$ to 250 m, to avoid obtaining too big places. We obtained 202 personal and 41 public places.

Attaching LU or POI information to places

To be able to validate place meaning assignments and resolve ambiguities, LU or POI information needs to be attached to the extracted places. For this purpose, our tools derive a frequency distribution of distinct LU or POI classes for each place. This is done differently for LU and POI data. For LU data, which are usually available in the form of polygons labelled by LU classes, the frequency distributions are obtained in the following way. First, for each point in the original data, the containing LU polygon is found, and the class label of this polygon is attached to the point. Second, for each extracted place, the frequencies of occurrence of distinct LU classes among the points contained in this place are counted. For POI data, which consist of place coordinates and labels signifying the POI classes, the procedure is as follows. For each extracted place, all POIs contained within the place boundaries are found, and the frequencies of distinct POI classes are counted.

Depending on the total number N of distinct LU or POI classes occurring on the studied territory, the class frequency information may be stored in two different ways. If N is not large, the information can be represented by N numeric attributes, one for each class. The values of the attributes for each place are the frequencies of the N classes. We used this approach in the VAST Challenge case study, where we had eight distinct POI classes. In case of large N, the class frequency information can be represented by k qualitative (nominal) attributes, where k is a number chosen by the analyst, such that 1 ≤ k < N. The attributes can be named ‘most frequent class’, ‘second frequent class’,…, ‘kth frequent class’. Their values are the first, second,…, kth class labels in the label arrangement by the decreasing frequencies. We used this approach in the San Diego case study, where N = 103. It would be difficult to deal with 103 numeric attributes representing all possible LU classes. We found it sufficient to use instead three qualitative attributes, that is, we took k = 3.

For viewing LU or POI information and using it in the analysis, we have developed two types of aggregated data displays. For dealing with a set of numeric attributes representing frequencies (in particular, frequencies of different LU or POI classes), we use a multi-attribute summary bar chart display. The examples in Figures 6 and 7 show aggregated frequencies of different POI classes by proportional lengths of horizontal bars. There are interactive controls for selecting the aggregation operation (sum, average, minimum, maximum or count) and setting the value filtering condition. The display in Figure 6 applies the operation ‘average’ and shows the average percentages of different POI classes per place. The value filtering condition is ‘>0’. The display in Figure 7 applies the operation ‘count’ and the value filtering condition ‘> = 5’, that is, it shows, for each POI class, the counts of places where at least 5% of the points have this POI class.

To compare LU or POI class frequencies in two or more groups of places, a colour propagation mechanism is used. When places are divided into groups in any way, such as clustering or classification according to the likelihood of having a certain meaning, distinct colours are assigned to the groups. Information about the group colours and the group membership of each place can be propagated to all currently existing displays. A multi-attribute bar chart reacts to the colour propagation by multiplying the bars: it creates as many groups of bars as there are groups of places. Each group of bars represents aggregated information for one group of places; the bars are painted in the colour of this group. This is illustrated in Figure 7. Where the deviations of the group aggregates from the whole set aggregates are statistically significant, the bars are enclosed in black or white frames indicating significantly higher or significantly lower values, respectively. The significance of the deviations is determined using the chi-square test.

For dealing with qualitative attributes, such as the first, second,…, kth most frequent LU/POI class, we designed a qualitative histogram display. When an attribute has a large number of distinct values, the values can be organized in a hierarchy. For the San Diego case study, where there are 103 different LU classes, we created a hierarchy that can be utilized by the display. Figure 8 demonstrates a hierarchical qualitative histogram for the attribute ‘Land use: most frequent value’ of the personal places extracted from the San Diego data. The bar lengths are proportional to the counts of the classes and generalized categories of LU. The upmost bar corresponds to all LU classes taken together. The display reacts to the propagation of place groups and their colours in the same way as shown in Figure 7.

Exploration of time patterns of place visits

The place extraction tool described in section ‘Extraction of personal and public places’ computes for each place the total number of visit-days and a 2D time series of place visits by days of the week and hours of the day. For personal places, only the visits of the place owners are counted. Counts of visits are not the same as counts of points. If two consecutive points of a person fit in the same place and the same hour, they are treated as representing the same visit.

For looking at the place visit time series and using them in the analysis, we have designed a 2D time histogram display illustrated in Figure 9. A time histogram is a matrix with rows corresponding to days of the week and columns to hours of the day. Inside the cells, there are symbols with sizes proportional to aggregated visits in the corresponding days and hours for the set of places currently considered. The interface (UI) allows the user to select the aggregation operation (sum, minimum, maximum, average or count), the condition for including attribute values in the aggregates (all, positive, negative, zero or within a user-specified interval) and the way of representing the aggregates in the matrix cells (squares, circles, vertical bars or horizontal bars). The display reacts to propagation of place groups and their colours (as explained in section ‘Attaching LU or POI information to places’) by multiplying the time histogram, so that one histogram represents the whole set of places and the remaining histograms show aggregated counts for different groups of places. The symbols in the cells of the matrices have the colours of the clusters. When all histograms do not fit in the window, the display can be scrolled.

Figure 9 illustrates the main idea of our approach to identifying place meanings based on the time patterns of the place visits. Here, time series of visits to two different places are depicted. Based on the observed temporal patterns and our background knowledge concerning the typical times of various activities of people, we can assign the meaning ‘home’ to one place and the meaning ‘work’ to the other place.

Since we need to attach meanings (semantic labels) to a large number of places, we cannot do this by separately looking at the temporal visit pattern of each place. A more scalable approach is to filter and rank the places based on relevant summary attributes derived from the time series. An example of such a derived attribute is the number or proportion of place visits fitting in the work times, that is, in the hours from 05 to 18 during the work days. We have implemented interactive tools for derivation of relevant attributes, which are described in Appendix 2.

However, before deriving attributes that can appropriately distinguish possible place meanings, it is useful to perform an initial exploration of the set of the existing time patterns of place visits. The initial exploration can be done by means of clustering of the place visit time series by similarity and analysing the clusters with the use of 2D time histograms. To standardize the time series across the places and people, the absolute counts are converted to percentages of the total number of the place visits. The clustering can be done using any existing clustering algorithm. The illustration in Figure 10 represents selected clusters obtained with the k-means clustering method for the San Diego example. The appearances of some patterns suggest the likely meanings of the places in the respective clusters. Thus, patterns ‘a’ and ‘b’ in Figure 10 suggest the meaning ‘home’, patterns ‘c’ and ‘d’ evoke the meaning ‘work or study’, ‘e’ could be a shopping pattern and ‘f’ may be attributed to social activities, that is, visiting or meeting friends or relatives. Such observations may give an idea about the possible activities and their typical times for the territory and population under study.

Inferring place meanings

Multi-criteria evaluation and ranking

From the literature and communication with other researchers, we have discerned several criteria used for identifying home and work places of individuals: place visit frequency, average time of the day when visits happen, counts of visits in the night time and in the work time and counts of daily trip starts and ends. All these criteria seem relevant, but it has not been known, which one(s) of them works the best. It seems appropriate to combine these criteria, but so far this has only been done in specific studies through ad hoc rules.^13,14

We have developed a generic interactive technique for combining multiple criteria based on approaches from decision support science³⁵ where multiple attributes of decision options are integrated into scores representing the degree of suitability or utility of the options. The attributes may be given different weights according to their relative importance. Two types of criteria are distinguished: benefit criteria with higher values being preferred and cost criteria with lower values being preferred. The most common criteria integration method in multi-criteria decision making (MCDM) is the weighted linear combination.³⁶ The attribute values are normalized to the range [0, 1] depending on their relative positions between the minimal and maximal values. For a benefit criterion, 0 corresponds to the minimum and 1 to the maximum; for a cost criterion, it is the other way around. The integrated score is computed as the sum of the products of the normalized values multiplied by the attribute weights and divided by the sum of the weights. The result is a number ranging from 0 to 1, where 0 is the worst and 1 is the best.

Previously suggested interactive techniques for MCDM^37,38 allow the user to select relevant criteria and set their directionality (cost or benefit) and weights. The evaluation results, that is, the scores and ranks of the options, are immediately shown on visual displays, such as parallel coordinates plot and map. The user can test how changes in the criteria weights affect the results.

The criteria integration approach from MCDM can be adapted to the task of identifying the most likely home or work place among the personal places of an individual. By nature of the task, the evaluation must be done separately for places of each individual. However, the size of the data and the privacy constraints do not allow separate consideration of the places of each individual by analysts. Analysts can only choose relevant criteria and set a common set of weights to be used for all individuals. A prototypical UI is shown in Figure 11. A computational tool calculates integrated scores separately for the places of each individual and ranks the places according to their scores. The target meaning (home, work, etc.) can be assigned to the set of the top ranking places of all individuals. We stress that the meaning is assigned to multiple places simultaneously without looking at any particular place, that is, without accessing personal data.

We have developed two multi-criteria ranking tools for personal and public places. The former applies ranking separately to personal places of each individual, whereas the latter applies ranking to all public places at once. The tools have similar UIs and functionalities.

Validation of place scores and ranks

As a part of multi-criteria evaluation, two problems need to be solved: how to assess the quality of the evaluation outputs and how to test the impact of choosing different criteria and modifying their weights. The usual MCDM support tools involve visualization of characteristics and scores of individual options, for example, on a parallel coordinates plot.^37,38 This allows the user to check the suitability of one or a few best scoring options by comparing their characteristics with those of the other options. The sensitivity of the evaluation results to the settings can be investigated by interactively changing the settings and observing the consequent changes in the display.

This approach is not applicable to the task of personal place evaluation because it would require separate consideration and comparison of places for each person, which is both infeasible and violates individual privacy. One solution we propose involves LU data. Among the LU classes, there are classes associated with the meaning ‘home’ (various residential LUs), classes related to work or study (industry, education, office, construction, military LU) and classes related to other activities (shopping, recreation, health care, etc.). The quality of place ranking results can be judged from the proportion of the places in LU categories relevant to the target meaning among the best scoring places.

Let us consider the example of ranking the personal places extracted from the San Diego data with regard to the target meaning ‘work or study’. We have chosen the attributes shown in Figure 11 as the ranking criteria, set their directionality (benefit or cost) and obtained initial ranks with all criteria having equal weights. The ranking tool creates an attribute ‘best scored’ and attaches values ‘y’ (yes) and ‘n’ (no) to the places. By means of interactive filtering, we select the subset of places that have the value ‘y’ and examine the LU classes occurring in this subset using a qualitative histogram (Figure 12). We observe that the subset includes a number of places with LU classes relevant to the target meaning ‘work or study’, but there are also many occurrences of irrelevant LU classes. We are going to modify the criteria weights and check whether this improves the proportions of the relevant LU classes.

To support the comparison between outputs of two consecutive rankings, the evaluation tool creates a special attribute representing the place rank changes. The possible values of the attribute are ‘yy’ (the highest rank in both outputs), ‘nn’ (lower ranks in both outputs), ‘yn’ (the highest rank changed to a lower rank) and ‘ny’ (a lower rank changed to the highest rank). These values define classes of the places, which can be propagated to the LU histogram. The tool remembers the previously used criteria weights, so that the analyst can restore these weights and the corresponding place scores and ranks if the result of the changes is not satisfactory.

Continuing our example, we modify the criteria weights as shown in Figure 11, re-compute the place ranks and propagate the place classes expressing the rank changes to the LU histogram. By means of interactive filtering, we focus only on those places that have changed their ranks, that is, the classes ‘ny’ and ‘yn’. In the histogram (Figure 13), these classes are represented by the green and orange bars, respectively. We see that the change in the weight values has increased the number of the top ranked places located in the relevant categories ‘Education’ and ‘Office’: the respective green bars are longer than the orange ones. The number of the top ranked places located in the irrelevant LU category ‘Lodging’ has decreased. Hence, the change in the weight values has improved the place evaluation result in terms of the relevance of the LU classes. Still, it is also necessary to assess the changes with regard to the temporal patterns of the place visits. We do this using a 2D time histogram display. It shows us (Figure 14) that the visit patterns of the places that improved their ranks match much better the target meaning ‘work or study’ than the patterns of the places with lowered ranks. Hence, the results of the weight modification can be approved.

Information about the relevance of the LU classes can be transformed into a binary attribute with values 1 and 0 showing whether the list of LU classes attached to a place includes any target-relevant class. This is facilitated by a generic tool creating binary attributes based on object filtering. Binary attributes can be used for a direct investigation of the relationship between the place scores and the LU relevance by means of a 2D cross-histogram display (Figure 15). Its two dimensions correspond to two attributes. In Figure 15, the dimensions are the evaluation score (horizontal dimension) and LU relevance (vertical dimension). The bins correspond to values or value intervals of the attributes. The bars in the bins represent the frequencies of the corresponding value pairs. The cross-histogram can be displayed in a cumulative mode, in which the frequencies are accumulated along the rows or along the columns from the minimal to the maximal value of the respective attribute or in the opposite direction. In Figure 15, the frequencies are accumulated along the rows in the direction from the maximal score to the minimal; hence, a bar in a score bin (x_i, x_i+1] represents the number of places with the scores greater than x_i. In the lower row, it is the number of places with target-irrelevant LU classes, and in the upper row, it is the number of places with target-relevant LUs.

In Figure 15(a), the cross-histogram represents the whole range of the attribute ‘score’. At the left end of the histogram, the cumulative number of places with relevant LUs (upper row) is much smaller than the number of places with irrelevant LUs (lower row). At about 40% of the score range, the number of places with irrelevant LUs starts to steeply decrease as the score increases while the decline in the upper row is much gentler. At some point, the number of places with relevant LUs starts to exceed the number of places with irrelevant LUs. However, it is hard to compare the bar heights in two rows. In order to support the comparison, the display UI allows superimposing a user-selected reference row or column on all other rows or columns. The superimposed histogram is shown in semi-transparent red. In Figure 15(b), where we have focused on the score interval [0.6, 1], the lower row is superimposed on the upper row. By moving the mouse cursor along the x-axis, we can see that starting from the score of about 0.68, the number of places with relevant LUs exceeds the number of places with irrelevant LUs, and the ratio between these numbers increases with increasing the score. This kind of dependency indicates that the place evaluation scores represent quite well the place’s likelihood of having the target meaning.

There is a technical possibility of implementing a computational tool that could search for the best combination of criteria weights maximizing the absolute number and proportion of the top ranked places with target-relevant LUs (i.e. with value 1 of the relevance attribute). However, the process of finding corresponding places for a given target meaning cannot be fully automated. The analyst would need to check, first, if the automatically selected weights corresponded to the analyst’s understanding of the relative importance of the criteria; second, if the distribution of the LU classes was good enough and, third, if the temporal patterns of the visits to the top ranked places were plausible for the target meaning. For these tasks, the analyst needs interactive visual tools. After the inspection, the analyst may decide to try adding new criteria. Such decisions and subsequent choices including a possibility of incorporating additional relevant criteria cannot be done automatically.

Despite being important for the validation of place evaluation and ranking, LU data need to be treated with caution. Due to spatial positioning errors, the LU classes of the original data points obtained by calculating their containment in LU polygons may be erroneous. Besides, LU data can be outdated. Hence, LU information may be utilized as supporting evidence but not as a decisive criterion for determining place meanings.

Another approach to place ranking validation and parameter sensitivity testing involves POI data. The difference with regard to LU data is that there may be no specific POI types related to the target meaning ‘home’. In this situation, places can be considered as good candidates for the target meaning ‘home’ when they contain none or very few public POIs. An example of inferring place meanings with the use of POI data is provided in Appendix 3 and in the accompanying video available at geoanalytics.net/and/papers/placeSemantics.

Place meaning assignment

An interactive interface for place meaning assignment includes controls for assigning meanings to places based on (a) their ranks, (b) their scores or (c) current filter. The analyst provides an arbitrary textual label representing a meaning, for instance, ‘home’, ‘work or study’, ‘shopping’ and so on. When option (a) is chosen, the meaning is attached to the top ranking places. With option (b), the meaning is attached to the places with the scores above a user-provided threshold. A suitable threshold can be chosen using a 2D cross-histogram display as shown in Figure 15. Using option (c), the meaning is attached to the places satisfying currently operating filter, irrespective of the place scores or ranks. Options (b) and (c) are mostly used for public places and for personal places when the target meaning is not ‘home’ or ‘work’, that is, when the number of personal places that may be expected to have this target meaning is not limited. For example, there may be multiple shops or restaurants repeatedly visited by an individual.

Interactive filtering

The analyst can interactively create filters to select subsets of individuals and subsets of places. Various types of interactive filters are described in book⁵ (section 4.2). Several filters of diverse types can be combined. For the task of place meaning discovery, the most important are the attribute-based filter, the class/cluster-based filter and the related set filter. The attribute-based filter selects objects based on the values of one or more attributes. The class/cluster-based filter selects classes or clusters of objects. The related set filter propagates filtering from object set A to another object set B or in the opposite direction when the objects in set A have references to objects of set B, that is, the values of some attribute of the objects in A are identifiers of objects from B. Filter propagation means that the analyst selects a subset of one of the sets by any filter, and the related set filter selects only those objects from the other set that are related to the selected objects of the former set.

In the context of our task, there is a set of personal places and a set of place owners; the places have references to their owners. The analyst can select, for instance, the individuals who have yet been assigned a place with meaning ‘home’ and use the related set filter to select only the places of these individuals for further analysis. Conversely, the analyst can select the places with the meaning ‘work or study’ and then select the owners of these places to see how many of them already have places with the meaning ‘home’. Please note that filtering results are always represented in an aggregated form, to preclude any access to possibly sensitive individual data.

General guidelines for inferring place semantics

As it can be seen from the examples discussed above, determining place meanings is an explorative activity strongly relying on analyst’s reasoning, surmises and insights and often involving trials and errors. It is hardly possible to describe it in the form of an algorithm. Still, based on our experience, we can propose several general guidelines, which refer to the box ‘Identify place meanings’ of the flow chart in Figure 3.

For each target meaning (‘home’, ‘work’, ‘shopping’, etc.), determine relevant attributes, by which places with this meaning can be distinguished from places with other meanings. If needed, derive attributes that are not initially available (see Appendix 2).

Apply filtering based on the relevant attributes to select a subset of places that are eligible to receive a target meaning.

To find the most likely places for the target meaning, apply multi-criteria evaluation (section ‘Multi-criteria evaluation and ranking’) to the eligible places. For personal places, apply it separately to the set of places of each person; for public places, apply to all places together. Select the top scoring places as candidates for receiving the target meaning. Depending on the target meaning, do this in one of the following two ways:

3.1. If the evaluation is applied to personal places, and a person typically has a single place with the target meaning (e.g. ‘home’), select the places with the highest scores (note that there may be several such places for a person).

3.2. If the evaluation is applied to public places, or if a person may have several places with the target meaning, choose a score threshold and select the places with the scores not less than the threshold.

Examine the temporal distribution of the visits to the best scoring places and check its correspondence to the expected pattern for the target meaning. If the correspondence is not good enough, try to improve it by changing the attribute weights and/or including additional relevant attributes and/or changing the score threshold.

If there are LU classes or POI types relevant and/or irrelevant to the target meaning, watch the proportions of LU classes or frequencies of POI types (section ‘Validation of place scores and ranks’). Test the impact of different attributes and modifications of the attribute weights on these proportions. The goal is to increase the proportions or frequencies of the relevant LU or POI types and decrease those of the irrelevant types. If good results cannot be reached with the current eligibility filter and evaluation criteria, change the filter or include additional criteria.

After gaining confidence in the validity of the candidate place selection, assign the target meaning to the selected places (section ‘Place meaning assignment’).

The following remarks provide further details and show possible modifications to the procedure.

Clustering of time patterns of place visits

Clustering of time patterns of place visits (section ‘Exploration of time patterns of place visits’) can produce, among others, clusters of time patterns that correspond quite well to certain target meanings. The clustering result can thus be used as a relevant attribute for selecting eligible places for these target meanings. The analyst can select appropriate clusters using a cluster-based filter. Clustering can also reveal temporal patterns that have not been anticipated by the analyst. By observing such a pattern, the analyst may arrive at one of expected target meanings, or find new plausible meanings. The guesses about the plausible meanings can be checked against the LU or POI data.

Filter-based meaning assignment

As described in section ‘Place meaning assignment’, a meaning can be assigned to a subset of places based on filtering and not on scores or ranks, which means that step 3 of the procedure may be skipped. This is done in the following cases:

There are individuals having unique eligible places for the target meaning. Multi-criteria evaluation is not applicable in this case. The eligible places belonging to these individuals can be selected through the related set filter (section ‘Interactive filtering’).

Existence of multiple places with the target meaning is usual and expected.

Multiple home and work places

While it is not very typical that people have more than one home or work place, such cases do exist. However, it is reasonable to distinguish true cases of multiple home or work places from cases of splitting large places into smaller ones when using the place extraction algorithm (section ‘Extraction of personal and public places’). In the latter case, several places will be close in space, and this can be used as a distinguishing criterion. Based on the above argument, we propose the following way to deal with multiple eligible places for the same target meaning. First, multi-criteria evaluation (step 3) is applied and the topmost ranking places are selected. After validating the selection in steps 4 and 5, the target meaning is assigned to these places. Then the distances of the remaining places to the selected places are computed separately for each individual. Eligible places located closely to the selected places (i.e. within a chosen distance threshold, such as for example 1 km) can be treated as parts of the same places and can be assigned the same target meaning. The places that have received meanings are excluded from further consideration through filtering. The remaining eligible places may receive target meaning ‘second home’ or ‘second work’ after validation in steps 4 and 5.

Analysis of semantic trajectories

After assigning semantic labels to personal and public places, the original mobility data (section ‘Format and general characteristics of input data’) are transformed into semantic trajectories (section ‘Problem statement’) in the following way. The sequence of records of each individual is divided into daily trajectories taking 04:00 as the beginning hour of a day. From our experiences with many mobility datasets, we know that the total number of recorded activities is usually minimal at this hour; still, another hour can also be chosen. For each trajectory point, the tool tries to find a place containing it. The personal places of the individual are checked first. If no place is found, or a place found has no assigned meaning, the tool checks the public places. If neither personal nor public place is found, the point is skipped (i.e. treated as occasional). If the tool has found a personal or public place with an assigned meaning, the semantic label is attached to the trajectory point. Otherwise, if the point is contained in one of k most frequently visited personal places of the individual (where k is a parameter; in our San Diego experiment, we used k = 5), the frequency rank of this place (i.e. 1, 2,…, k) is attached to the point, to allow subsequent checking for relatively frequently visited places that could not be interpreted. Otherwise, the point receives the label ‘n/a’.

After this step, the semantic labels attached to the trajectory points are treated as references to semantic places ‘home’, ‘work’, ‘shop’ and so on, located in an abstract semantic space.²⁷ The set of trajectories can be aggregated by semantic places analogously to aggregation by geographic places.^4,5 Hence, the trajectories are aggregated spatially by the abstract semantic places and temporally by hourly intervals. When the time span covering the dataset is not too long, like in the VAST Challenge example, it may be divided into intervals based on the linear time model. Thus, a period of 2 weeks will be divided into 336 (=2 × 7 × 24) hourly intervals. A longer time span, as in the San Diego example, can be partitioned based on the cyclic time model. Specifically, the weekly cycle (7 days) is divided into hourly intervals, resulting in 168 (=7 × 24) intervals. The result of the aggregation is two sets of time series: hourly visits to semantic places and hourly flows (i.e. aggregated moves) between the places. A move between two places is counted if the time interval between the points in these two places does not exceed 1 h. The time series of visits and flows are explored to see whether the daily and weekly temporal patterns are realistic.

To visualize the transformed data, we generate a semantic space,²⁷ that is, a 2D layout of the set of semantic places. This can be done in various ways. In Figure 16, the layout has been obtained by applying Sammon’s³⁹ mapping to the set of places based on the strength of the links between them, that is, the counts of the moves. The layout in Figure 17 has been produced by the graph visualization software Gephi (http://gephi.org/).

Figures 16 and 17 show semantic space maps for the VAST Challenge and San Diego examples, respectively. The place visit time series are represented by mosaic diagrams.⁴⁰ The rows correspond to 14 consecutive days in Figure 16 and to 7 days of the weekly cycle in Figure 17; the columns correspond to 24 h of the day. The pixels are coloured according to the hourly visit counts. We observe in Figure 17 that ‘shopping’ in the San Diego example has the highest attendance after ‘home’. This does not necessarily mean that San Diego residents spend more time shopping than doing any other activity. It may just mean that people tweet more often from shopping places than from other types of places. Apart from that, the temporal patterns of the visits to semantically interpreted places observed in both maps correspond to the expected patterns for these types of places or activities.

The flows between the semantic places are shown in Figures 16 and 17 by curved lines with the curvature increasing towards the destination. The line widths and opacity are proportional to the total number of moves between the origins and destinations. As there is no suitable way to represent flow time series in a single map, and it would be daunting to view and compare hundreds of maps of the hourly flows, we apply clustering to the hourly flow situations.^4,5 The results of k-means clustering with k = 8 for the VAST Challenge and k = 7 for San Diego are shown in Figures 18 and 19, respectively. With the selected values of k, we could obtain the simplest yet informative temporal patterns. The mosaic diagrams (at the bottom right and at the top left of the images, respectively) have the same structure as in Figures 16 and 17, but the pixel colours correspond to the time clusters of similar flow situations. The distributions of the cluster colours prominently adhere to the daily and weekly time cycles. The multiple maps in both images represent the averaged flow patterns for the clusters. In Figure 19, we have excluded cluster 1 (blue), in which the flow magnitudes are very low. The line widths and opacity are proportional to the mean hourly move counts.

In Figure 18, we observe quite regular daily routines of the people represented in the VAST Challenge data: during hours 07–08, they usually have coffee and then go to work; at noon, they go for lunch and return back to work in the next 1 or 2 h; then they go home in hour 17 and often go to eat out in the evening. This fully agrees with the available ground truth information.

In Figure 19, the mean move counts have been transformed to z-scores, that is, standardized deviations from the clusters’ means. This transformation supports disregarding purely numeric differences between the clusters, which are mainly caused by the fact that people tweet less in the morning than in the second half of the day, and reveals differences in the major flow directions. In the morning (cluster 2, cyan), most movements originate from home. Flows to work and to shopping accompanied by the use of transport and parking places are prominent. In the middle of the working days (cluster 3, green), flows from different places to home increase as well as move between work places (‘work’ and ‘work 2’); the home–work flow decreases as well as the use of transport and parking places. In the afternoon hours (clusters 4 and 6), people mostly return from work to home or go shopping. Cluster 6 (red) occurring on Thursday and Friday differs from cluster 4 (yellow) by smaller flows from work and work 2 to home and bigger flows to places for eating out and social life. In the evenings and on weekends (cluster 5, orange), most of the movements occur between home and shopping but flows to eating establishments and social life are also prominent. Cluster 7 (dark blue) occurring in hour 23 is mostly characterized by returns to home from different places. All these patterns correspond to our background knowledge about typical human mobility behaviours.

Please note that although we did not use any information about place visit sequences in our analysis, realistic temporal patterns of movements between places have emerged. This confirms the validity of our methods, in addition to the consistency of the results obtained for the VAST Challenge data with the available ground truth information.

Discussion and conclusion

The problem of deriving significant places from mobility data (i.e. time-stamped geographic positions) that lack semantics is ill-defined; therefore, it cannot be solved algorithmically but instead requires human reasoning. Additional challenges are the necessity to deal with large amounts of data from many individuals and the requirement to respect personal privacy of the individuals. By exploring diverse examples of mobility data, we were able to determine which visual analytics techniques can support solving the problem at hand. We designed and developed a set of tools meeting the demands of the analytical tasks at hand and tested the effectiveness of these tools in practice, successfully solving the problem for two different datasets. Hence, we can conclude that the problem is solvable and the techniques that we developed work and can be recommended to others. However, due to the ill-defined character of the problem, it is hardly possible to formulate a rigorous procedure. We convey our experience as an informally defined general procedure accompanied by remarks concerning possible particulars and variations (section ‘General guidelines for inferring place semantics’). These guidelines complement our research contribution.

We are aware of the limitations affecting the mobility data that we have used for our research. One of the experiments was done with data from Twitter. It is known that Twitter users are a specific and quite particular group of people, that is, they cannot be considered as a representative sample of the population. However, this was not a major obstacle for our research, the main goal of which was to develop a methodology for place semantics discovery. Twitter data served as a suitable test dataset, but the methodology can also be applied to other data, in particular, to mobile phone use data, which can represent larger and more diverse section of the population. Second, by example of shopping locations (Figures 17 and 19), we saw that certain types of places and activities may be over-represented in the data and others may be under-represented. This is a consequence of the episodic character of the original data, where the recorded positions correspond to events that tend to occur more often in some types of places than in others. Mobile phone data can also be affected by such problems. Third, there is a time bias: people tend to tweet more in the afternoons and evenings than in the mornings. Again, the same problem may also exist in mobile phone data. It is necessary to find ways to diminish the place and time biases in analysing population mobility based on episodic movement data. We are conducting further research to address these data-specific issues.

Regarding the location privacy of data containing people’s geographic positions, our goal has been to test the possibility of determining place meanings in a privacy-respecting way, that is, so that analysts only deal with aggregated data and do not access personal data, in particular, individuals’ geographic positions. Our research demonstrated that this is practically possible. In two experiments, we used only displays of aggregated data and did not use geographic representations, apart from checking the largest places for choosing right parameters for place extraction (section ‘Extraction of personal and public places’).

To conclude, we have presented a visual analytics approach to the problem of scalable and personal privacy-friendly extraction and semantic interpretation of personal and public places from episodic movement data reflecting human mobility and activities. Our contribution consists of a set of computational and visual techniques and guidelines for solving the problem with the use of these techniques. We have also proposed methods for evaluation and validation of the results. The approach has been successfully tested on an artificial dataset with known ground truth and on a large real-world dataset. The extraction of significant places and their meanings is a necessary step towards reconstruction of mobility diaries, which is the topic of our ongoing research. It can also provide valuable information to researchers of human mobility, who may be interested in studying the variety of individual mobility behaviours. Our research shows that such studies can be done without compromising personal location privacy.

Footnotes

Appendix 1

Appendix 2

Appendix 3 Funding

This research received no specific grant from any funding agency in the public, commercial or not-for-profit sectors.

References

Bonabeau

. Agent-based modelling: methods and techniques for simulating human systems. PNAS P Natl Acad Sci USA 2002; 99(Suppl. 3): 7280–7287.

Andrienko

Wrobel

. Visual analytics tools for analysis of movement data. ACM SIGKDD: Explor 2007; 9(2): 38–46.

Bertin

. Semiology of graphics: diagrams, networks, maps. Madison, WI: University of Wisconsin Press, 1983.

Andrienko

Stange

. Visual analytics for understanding spatial situations from episodic movement data. Künstl Intell 2012; 26(3): 241–251.

Andrienko

Bak

. Visual analytics of movement. Berlin: Springer, 2013.

Andrienko

Fuchs

. Extracting semantics of individual places from movement data by analyzing temporal patterns of visits. In: Proceedings of the ACM SIGSPATIAL workshop computational models of place, Orlando, FL, 5–8 November 2013.

Palma

Bogorny

Kuijpers

. A clustering-based approach for discovering interesting places in trajectories. In: Proceedings of the 23rd annual ACM symposium on applied computing (ACM SAC), Fortaleza, Brazil, 16–20 March 2008, pp. 863–868. New York: ACM Press.

Zimmermann

Kirste

Spiliopoulou

. Finding stops in error-prone trajectories of moving objects with time-based clustering. In: Tavangarian

Kirste

Timmermann

. (eds) Intelligent interactive assistance and mobile multimedia computing. Berlin: Springer, 2009, pp. 275–286.

Rocha

Oliveira

Alvares

. DB-SMoT: a direction-based spatio-temporal clustering method. In: Proceedings of the 5th IEEE international conference on intelligent systems, University of Westminster, London, 7–9 July 2010, pp. 114–119. New York: IEEE.

10.

Parent

Spaccapietra

Renso

. Semantic trajectories modeling and analysis. ACM Comput Surv 2013; 45(4): 42.

11.

Phithakkitnukoon

Horanont

Di Lorenzo

. Activity-aware map: identifying human daily activity pattern using mobile phone data. In: Proceedings of the international conference on pattern recognition, workshop on human behavior understanding, Istanbul, 22 August 2010, pp. 14–25. Heidelberg: Springer.

12.

Toole

Ulm

González

. Inferring land use from mobile phone activity. In: Proceedings of the ACM SIGKDD international workshop Urban computing (UrbComp’12), Beijing, China, 12–16 August 2012, pp. 1–8. New York: ACM Press.

13.

Ahas

Silm

Järv

. Using mobile positioning data to model locations meaningful to users of mobile phones. J Urban Technol 2010; 17(1): 3–27.

14.

Isaacman

Becker

Cáceres

. Identifying important places in people’s lives from cellular network data. In: Lyons

Hightower

Huang

(eds) Pervasive computing. Berlin: Springer, 2011, pp. 133–151.

15.

Schneider

Belik

Couronné

. Unraveling daily human mobility motifs. J R Soc Interface 2013; 10: 20130246.

16.

Schneider

Rudloff

Bauer

. Daily travel behavior: lessons from a week-long survey for the extraction of human mobility motifs related information. In: Proceedings of the 2nd ACM SIGKDD international workshop Urban computing (UrbComp’13), Chicago, IL, 11–14 August 2013, Article no. 3. New York: ACM.

17.

Cheng

Caverlee

Kamath

. Toward traffic-driven location-based web search. In: Proceedings of the 20th ACM conference on information and knowledge management (CIKM 2011), Glasgow, 24–28 October 2011.

18.

Janowicz

Lee

W-C

. What you are is when you are: the temporal dimension of feature types in location-based social networks. In: Proceedings of the 19th ACM SIGSPATIAL international conference on advances in geographic information systems, Chicago, IL, 1–4 November 2011.

19.

Liu

Luo

Lee

. Location type classification using tweet content. In: Proceedings of the 11th international conference on machine learning and applications (ICMLA 2012), Boca Raton, FL, 12–15 December 2012, vol. 1, pp. 232–237. New York: IEEE.

20.

VAST Challenge 2011, http://hcil2.cs.umd.edu/newvarepository/benchmarks.php#VAST2011

21.

Bosch

Thom

Heimerl

. ScatterBlogs2: real-time monitoring of microblog messages through user-guided filtering. In: IEEE conference on visual analytics science and technology (VAST), Atlanta, GA, 13–18 October 2013.

22.

Krüger

Thom

Ertl

. Visual analysis of movement behavior using web data for context enrichment. In: IEEE Pacific visualization symposium (PacificVis), Yokohama, Japan, 4–7 March 2014.

23.

Cuellar

Ochoa

Rios

. Indistinguishable regions in geographic privacy. In: Proceedings of the 27th annual ACM symposium applied computing (SAC 2012) (ed Ossowski

Lecca

), Riva del Garda, 26–30 March 2012, pp. 1463–1469. New York: ACM.

24.

Andrienko

Keim

. Challenging problems of geospatial visual analytics. J Visual Lang Comput 2011; 22(4): 251–256.

25.

Andrienko

. Privacy issues in geospatial visual analytics. In: Gartner

Ortag

(eds) Advances in location-based services. Berlin: Springer, 2012, pp. 239–246.

26.

Monreale

Andrienko

. Movement data anonymity through generalization. Trans Data Priv 2010; 3(3): 91–121.

27.

Andrienko

Fuchs

. Towards privacy-preserving semantic mobility analysis. In: Proceedings of EuroVA, international workshop on visual analytics 2013, EuroGraphics, Leipzig, 17–18 June 2013.

28.

Dasgupta

Kosara

. Adaptive privacy-preserving visualization using parallel coordinates. IEEE T Vis Comput Gr 2011; 17(12): 2241–2248.

29.

VAST Challenge 2014: Mini-Challenge 2, http://www.vacommunity.org/VAST+Challenge+2014%3A+Mini-Challenge+2

30.

Andrienko

Bosch

. Discovering thematic patterns in geo-referenced tweets through space-time visual analytics. Comput Sci Eng 2013; 15(3): 72–82.

31.

Andrienko

Hurter

. Scalable analysis of movement data for extracting and exploring significant places. IEEE T Vis Comput Gr 2013; 19(7): 1078–1094.

32.

Andrienko

. Spatial generalization and aggregation of massive movement data. IEEE T Vis Comput Gr 2011; 17(2): 205–219.

33.

Tsuda

Kong

Maekawa

. Detecting and correcting WiFi positioning errors. In: Proceedings of the ACM international joint conference pervasive and ubiquitous computing (UbiComp ‘13), Zurich, 8–12 September 2013, pp. 777–786. New York: ACM.

34.

Zandbergen

. Accuracy of iPhone locations: a comparison of assisted GPS, WiFi and cellular positioning. Trans GIS 2009; 13(s1): 5–26.

35.

Greco

(ed.). Multiple criteria decision analysis: state of the art surveys. Berlin: Springer, 2005.

36.

Malczewski

. GIS and multicriteria decision analysis. New York: John Wiley & Sons, 1999.

37.

Jankowski

Andrienko

. Map-centered exploratory approach to multiple criteria spatial decision making. Int J Geogr Inf Sci 2001; 15(2): 101–127.

38.

Andrienko

. Informed spatial decisions through coordinated views. Inform Visual 2003; 2(4): 270–285.

39.

Sammon

. A nonlinear mapping for data structure analysis. IEEE T Comput 1969; 18: 401–409.

40.

Andrienko

. Spatio-temporal aggregation for visual analysis of movements. In: Proceedings of the IEEE visual analytics science and technology (VAST 2008), Columbus, OH, 19–24 October 2008, pp. 205–206. New York: IEEE Computer Society Press.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB