Visual analytics of movement: An overview of methods, tools and procedures <s> Clustering trajectories <s> With widespread availability of low cost GPS devices, it is becoming possible to record data about the movement of people and objects at a large scale. While these data hide important knowledge for the optimization of location and mobility oriented infrastructures and services, by themselves they lack the necessary semantic embedding which would make fully automatic algorithmic analysis possible. At the same time, making the semantic link is easy for humans who however cannot deal well with massive amounts of data. In this paper, we argue that by using the right visual analytics tools for the analysis of massive collections of movement data, it is possible to effectively support human analysts in understanding movement behaviors and mobility patterns. We suggest a framework for analysis combining interactive visual displays, which are essential for supporting human perception, cognition, and reasoning, with database operations and computational methods, which are necessary for handling large amounts of data. We demonstrate the synergistic use of these techniques in case studies of two real datasets. <s> BIB001 </s> Visual analytics of movement: An overview of methods, tools and procedures <s> Clustering trajectories <s> The paper investigates the possibilities of using clustering techniques in visual exploration and analysis of large numbers of trajectories, that is, sequences of time-stamped locations of some moving entities. Trajectories are complex spatio-temporal constructs characterized by diverse non-trivial properties. To assess the degree of (dis)similarity between traiectories, specific methods (distance functions) are required. A single distance function accounting for all properties of trajectories, (1) is difficult to build, (2) would require much time to compute, and (3) might be difficult to understand and to use. We suggest the procedure of progressive clustering where a simple distance function with a clear meaning is applied on each step, which leads to easily interpretable outcomes. Successive application of several different functions enables sophisticated analyses through gradual refinement of earlier obtained results. Besides the advantages from the sense-making perspective, progressive clustering enables a rational work organization where time-consuming computations are applied to relatively small potentially interesting subsets obtained by means of 'cheap' distance functions producing quick results. We introduce the concept of progressive clustering by an example of analyzing a large real data set. We also review the existing clustering methods, describe the method OPTICS suitable for progressive clustering of trajectories, and briefly present several distance functions for trajectories. <s> BIB002 </s> Visual analytics of movement: An overview of methods, tools and procedures <s> Clustering trajectories <s> One of the most common operations in exploration and analysis of various kinds of data is clustering, i.e. discovery and interpretation of groups of objects having similar properties and/or behaviors. In clustering, objects are often treated as points in multi-dimensional space of properties. However, structurally complex objects, such as trajectories of moving entities and other kinds of spatio-temporal data, cannot be adequately represented in this manner. Such data require sophisticated and computationally intensive clustering algorithms, which are very hard to scale effectively to large datasets not fitting in the computer main memory. We propose an approach to extracting meaningful clusters from large databases by combining clustering and classification, which are driven by a human analyst through an interactive visual interface. <s> BIB003
Clustering is a popular technique used in visual analytics for handling a large number of data. Usually existing clustering methods are wrapped in interactive visual interfaces supporting not only visual inspection but often also interactive refinement of clustering results. Trajectories of moving objects are quite complex spatio-temporal constructs. Their potentially relevant characteristics include the geometric shape of the path, its position in space, the life span and the dynamics, that is the way in which the spatial location, speed, direction and other point-related attributes of the movement change over time. Rinzivillo et al. BIB002 argue for the use of diverse distance functions addressing different properties of trajectories and introduce the procedure of progressive clustering that allows analysts to combine these distance functions in the process of analysis. The analysis is done in a sequence of steps. In each step, clustering with a single distance function is applied either to the whole set of trajectories or to one or more of the clusters obtained in the preceding steps. In this way, the user may (1) refine clustering results, (2) combine several distance functions differing in semantics and (3) gradually build comprehensive understanding of different aspects of the trajectories. Several distance functions suitable for clustering of trajectories are suggested by Andrienko et al. BIB001 The procedure of progressive clustering is illustrated in Figure 2 . First, the density-based clustering algorithm OPTICS with the distance function 'common ends' has been applied to the ship trajectories (Figure 2(a) ). Each of the resulting clusters consists of trajectories with spatially close end points. In this way, the user uncovers the major destinations of the ships. Second, one of the clusters, namely trajectories ending at Rotterdam, has been interactively selected, that is all other clusters have been hidden (Figure 2(b) ). Third, the same clustering algorithm with the distance function 'route similarity' has been applied to the members of the selected cluster (Figure 2(c) ). The user can see the typical routes of the ships coming to Rotterdam. In Figure 2 (d), the route-based clusters of trajectories are shown in an STC, which is explained in more detail in the next subsection. The majority of the clustering tools can work only with data loaded in the computer random access memory (RAM) and are therefore not scalable to very large datasets. Andrienko et al. BIB003 suggest a way to overcome the limits of RAM. After defining clusters of trajectories on the basis of a subset (sample) of trajectories, the analyst is supported by interactive visual and computational tools in the process of creating, testing and refining a classification model for assigning trajectories to the clusters. Then the classifier is used to supplement the clusters with new trajectories, which are loaded from a database by portions fitting in the main memory.