Data Mining: The Textbook

16.3. TRAJECTORY MINING

545

2. 
   The only contextual attribute in trajectory data is time. Therefore, trajectory data can be considered spatiotemporal data. While the scenarios discussed in previous sections may also be generalized further by including time among the contextual attributes, the spatial attributes are not behavioral in those cases. For example, when sea sur-face temperatures are tracked over time, both spatial and temporal attributes are contextual.
   

Trajectory analysis is typically performed in one of two different ways:

1. 
   Online analysis: In online analysis, the trajectories are analyzed in real time, and the patterns in the trajectories at a given time are most relevant to the analysis.
   

2. 
   Shape-based analysis: In shape-based analysis, the time variable has already been removed from the analysis. For example, two similar trajectories, formed at different periods, can be meaningfully compared to one another. For example, a cluster of trajectories is based on their shape, rather than the simultaneity in their movement.
   

The two kinds of analysis in trajectory data are similar to time series data. This is not particularly surprising because trajectory data is a form of time series data.

16.3.1 Equivalence of Trajectories and Multivariate Time Series

Trajectory data is a form of multivariate time series data. For a trajectory in two dimen-sions, the X -coordinate and Y -coordinate of the trajectory form two components of the multivariate series. A 3-dimensional trajectory will result in a trivariate series.

Because of the equivalence between multivariate time series and trajectory data, the transformation can be performed in either direction to facilitate the use of the methods designed for each domain. For example, trajectory mining methods can be utilized for appli-cations that are nonspatial. In particular, any n-dimensional multivariate time series can be converted into trajectory data. In multivariate temporal data, the different behavioral attributes are typically measured with the use of multiple sensors simultaneously. Consider the example of the Intel Research Berkeley Sensor data [556 ] that measures different behav-ioral attributes, such as temperature, pressure, and voltage, in the Intel Berkeley laboratory over time. For example, the behavior of the temperature and voltage sensors in the same segment of time are illustrated in Figs. 16.7a, b, respectively.

It is possible to visualize the variation of the two behaviorial attributes by eliminating the common time attribute, or by creating a 3-dimensional trajectory containing the time and the other two behaviorial attributes. Examples of such trajectories are illustrated in Fig. 16.7c, d, respectively. The most generic of these trajectories is illustrated in Fig. 16.7d. This figure shows the simultaneous variation of all three attributes. In general, a multi-variate time series with n behavioral attributes can be mapped to an (n + 1)-dimensional trajectory. Most of the trajectory analysis methods are designed under the assumption of 2 or 3 dimensions, though they can be generalized to n dimensions where needed.

16.3.2 Converting Trajectories to Multidimensional Data

Because of the equivalence between trajectories and multivariate time series, trajectories can also be converted to multidimensional data. This is achieved by using the wavelet trans-formation on the time series representation of the trajectory. The wavelet transformation for time series is described in detail in Sect. 2.4.4.1 of Chap. 2. In this case, the time series is multivariate, and therefore has two behavioral attributes. The wavelet representation for

546 CHAPTER 16. MINING SPATIAL DATA

	25
	24
	23
TEMPERATURE	22
	21
	20
	19	2020	2040	2060	2080	2100	2120	2140	2160	2180	2200
	2000
						TIME STAMP

(a) Temperature

	2.69
	2.68
	2.67
	2.66
VOLTAGE	2.65
	2.64
	2.63
	2.62
	2.61
	2.619	20	21	22	23	24	25
				TEMPERATURE

3. 
   Temperature-Voltage Trajectory
   

	2.69
	2.68
	2.67
	2.66
VOLTAGE	2.65
	2.64
	2.63
	2.62
	2.61
	2.6	2020	2040	2060	2080	2100	2120	2140	2160	2180	2200
	2000
						TIME STAMP

(b) Voltage

	2.69
	2.68
	2.67
VOLTAGE	2.66
	2.65
	2.64

2.63

2.62

2.61

2.6

25
24

2200
23

22	2150

21. 
    2100
    

202050

TEMPERATURE	19	2000
		TIME STAMP

4. 
   Time-Temperature-Voltage Trajectory
   

Figure 16.7: Multivariate time series can be mapped to trajectory data

each of these behavioral attributes is extracted independently. In other words, the time series on the X-coordinate is converted into a wavelet representation, and so is the time series on the Y -coordinate. This yields two multidimensional representations, one of which is for the X-coordinate, and the other is for the Y -coordinate. The dimensions in these two representations are combined to create a single higher- dimensional representation for the trajectory. If desired, only the larger wavelet coefficients may be retained to reduce the dimensionality. The conversion of trajectory data to multidimensional data is an effective way to use the vast array of multidimensional methods for trajectory analysis.

16.3.3 Trajectory Pattern Mining

There are many different ways in which the problem of trajectory pattern mining may be formulated. This is because of the natural complexity of trajectory data that allows for multiple ways of defining patterns. In the following sections, some of the common definitions of trajectory pattern mining will be explored. These definitions are by no means exhaustive, although they do illustrate some of the most important scenarios in trajectory analysis.

16.3.3.1 Frequent Trajectory Paths

A key problem is that of determining frequent sequential paths in trajectory data. To determine the frequent sequential paths from a set of trajectories, the first step is to convert the multidimensional trajectory (with numeric coordinates) to a 1-dimensional discrete