Data Mining: The Textbook

14.10. EXERCISES

491

2. 
   For the time series of Exercise 1, construct the rolling average series for a window size of 2 units. Compare the results to those obtained in the previous exercise.
   

2. 
   For the time series of Exercise 1, construct the exponentially smoothed series, with a smoothing parameter α = 0.5. Set the initial smoothed value y₀ to the first point in the series.
   

2. 
   Implement the binning, moving average, and exponential smoothing methods.
   

2. 
   Consider a series, in which consecutive values are related as follows:
   

yi+1 = yi · (1 + Ri)

(14.27)

Here R_i is a random variable drawn from [0.01, 0.05]. What transformation would you apply to make this series stationary?

6. Consider the series in which yi is defined as follows:
yi = 1 + i + i^2 + Ri	(14.28)

Here R_i is a random variable drawn from [0.01, 0.05]. What transformation would you apply to make this series stationary?

7. 
   For a real-valued time series x₀ . . . x_n−1 with Fourier coefficients X₀ . . . X_n−1, show that X_k + X_n−k is real-valued for each k ∈ {1 . . . n − 1}.
   

7. 
   Suppose that you wanted to implement the k-means algorithm for a set of time series, and you were given the same subset of complex Fourier coefficients for each dimensionality-reduced series. How would the implementation be different from that of using k-means on the original time series?
   

7. 
   Use Parseval’s theorem and additivity to show that the dot product of two series is proportional to the sum of the dot products of the real parts and the dot prod-ucts of the imaginary parts of the Fourier coefficients of the two series. What is the proportionality factor?
   

7. 
   Implement a shape-based k-nearest neighbor classifier for time series data.
   

7. 
   Generalize the distance-based motif discovery algorithm, discussed in this chapter to the case where the motifs are allowed to be of any length [a, b], and the Manhattan segmental distance is used for distance comparison. The Manhattan segmental dis-tance between a pair of series is the same as the Manhattan distance, except that it divides the distance with the motif length for normalization.
   

7. 
   Suppose you have a database of N series, and the frequency of motifs are counted, so that their occurrence once in any series is given a credit of one. Discuss the details of an algorithm that can use wavelets to determine motifs at different resolutions.
   

Chapter 15

Mining Discrete Sequences

“I am above the weakness of seeking to establish a sequence of cause and effect.”—Edgar Allan Poe

15.1 Introduction

Discrete sequence data can be considered the categorical analog of timeseries data. As in the case of timeseries data, it contains a single contextual attribute that typically corre-sponds to time. However, the behavioral attribute is categorical. Some examples of relevant applications are as follows:

1.