[Research] Data streams as time series

I borrowed a book from the Library Service: 

Learning from Data Streams: Processing Techniques in Sensor Networks. Joao Gama, M.M. Gaber. Springer, November 2007, 255 pages, ISBN 354073678

This book have interesting chapters about processing of time series and stream mining. I read many of them, but the most interesting are:

Chapter 3, Data Stream Processing. In this chapter the authors present the constrints of considering data streams such as efficient use of memory, limited storage, real time processing and provide tradicional techniques to deal with these problems such as landmark windows, sliding windows, tilted windows, sampling, data summary, hashing, wavelets, histograms

Chapter 9, Clustering techniques in Sensor Networks. This chapter presents some of the open problems in data stream clustering inclusing time series. Incremental versions of clustering techniques by avoiding assuming that we know the time series in all their extent, clustering of entire time series and not only subsequences, discovery of structures in data over time are some of the open problem within clustering of data streams. It is interesting to note that the definition of representatives such as centroids and medoids with the goal of reducing dimensionallity is not always natural. Hence, Random Projection seems a viable alternative for clutering time series.

J. Lin and D. Gunopulos. Dimensionality reduction by random projection and latent semantic indexing. In Proceedings of the Text Mining Workshop, at the 3rd SIAM International Conference on Data Mining, May 2003.

Here Random projection is employed to reduce the dimensionality present a traditional information retrieval task like document classification. This paper was quickly read and only works for understanding the usefulness of Singular Value Decomposition into the random projection technique since both techniques are extensively used to reduce dimensionality in the vector space. It is interesting to note that orthogonal vectors to feed the RM index up are desirable, but they are expensive to achieve. However, since in high-dimensional space contains a larger number of almost orthogonal vectors than orthogonal vectors, the random vectors might be sufficiently close enough to orthogonal to offer a reasonable approximation of the original vectors. I plan to check that assumption in our time series to see if random projection can be used as a clustering method.

[Research] Incremental Clustering of Time Series and Motif Discovery

Iterative Incremental Clustering of Time Series. Jessica Lin, Michail Vlachos, Eamonn J. Keogh, Dimitrios Gunopulos. Advances in Database Technology. 2004

In this paper, the authors present an interesting way to clustering time series. They mention some of the problems I had when dealing with clustering of human motion time series: low convergence, long times, variable clusters. As the authors said: Kmeans has a complexity of O(kNrD), k=number of clusters, N=number of abjetcs, r=number of iterations, and D=number of dimensions. However, all the algorithms (and even this paper) assume that time series have the same length. Reading this paper I understand that several comparisons of length-variable time series makes difficult the convergence and the obtaining of centroids. The approach introduced in this paper is based on the multiresolutions properties de Haar Wavelets and I think they can be more studied to preserve the convergence when clustering time series of different lengths.

Scaling and time warping in time series querying. Fu, A. W., Keogh, E., Lau, L. Y., and Ratanamahatana, C. A. 2005. In Proceedings of the 31st international Conference on Very Large Data Bases (Trondheim, Norway, August 30 - September 02, 2005). Very Large Data Bases. VLDB Endowment, 649-660.

This work studies the properties of DTW with respect to Euclidean distance in the context of time series queries. Since response time is the primary goal, the authors present some lower bound techniques (based on triangular inequality) such as: Sakoe-Chiba band and LB-Keaogh, to reduce the number of time the DTW distance is evaluared. The reduction in the dimensionality of the time series by component analysis is emphasized.

Detecting time series motifs under uniform scaling. Yankov, D., Keogh, E., Medina, J., Chiu, B., and Zordan, V. 2007. In Proceedings of the 13th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining (San Jose, California, USA, August 12 - 15, 2007). KDD '07. ACM, New York, NY, 844-853. 

This paper was recently published and especifically deal with detecting time series motifs with the technique Uniform Scaling. The basic idea is to resample the time series both in amplitude and also in frequency to be able to compare time series of different lengths. The authors do not use Fourier techniques for that purpose but only a sampling of the time series upto obtain a desired length. In this paper they also used random projection to detec motifs. I noticed that the random projection approach is basically a clustering approach that organize range of time series in different buckets by using a hashing function that is based on the random election of elements in the time series segmenet. The main assumption uis that the time series are uniformly distributed and then a random distribution of elements in the time series is obtained. I want to know if this assumption is valid in case of human motion time series from video data since we noticed that we obtain sort of regular shapes over time, but not random time series.

Chiu, B., Keogh, E., and Lonardi, S. 2003. Probabilistic discovery of time series motifs. In Proceedings of the Ninth ACM SIGKDD international Conference on Knowledge Discovery and Data Mining (Washington, D.C., August 24 - 27, 2003). KDD '03. ACM, New York, NY, 493-498. 

In this paper the authors introduce the importance of a random distribution in time series. By assuming that, they use statistical parameters (mean, standart deviation, correlation) to interpret missing or noisy values in the time series. Random projection is also used here, I wonder if other algoritms can be used since this method only works well in [10-20] dimensions since above that interval, a random distribution is not assumed.

[Research] Distribution of spatiotemporal events to describe movement in video

Since I am taking Applied Spatial Statistics, I am starting to consider a statistical approach to model the presence of events in video. Rather than describing the method of Laptev, this approach will be a mechanisim to formally discuss in the paper the existence of gradients in human movement.

Gradients will be considered as random variables that could appear in any pixel of the video. I plan to model those events as a probability function with the goal of finding the maximum likelihood estimates. I am reading the Expectation-maximization algorithm and the book "Interactive Spatial Data Analysis" to classify types of movement based on probability distribution of events.

The idea of using a distribution of probabilities in videos can also be found in [1]. The authors use this approach to synchronize video recordings of the same scene, but with different viewpoints. A weak point in this approach is that the authors only compare 2 distributions (histograms) by directly subtracting each position in the histograms.

I have also defined the "conflictive" spatiotemporal gradients as the ones that fall in the [middle line +- 2*spatial variance]. These events are removed and I am generating them for all the videos.

[1] J. Yan, M. Pollefeys, Video Synchronization via Space-Time Interest Point Distribution, Advanced Concepts for Intelligent Vision Systems, 2004.

[Research] Paper Review on Time Series Indexation

Discovering Characteristic Actions from On-Body Sensor Data. Minnen, D. Starner, T. Essa, I. Isbell, C. College of Computing, Georgia Institute of Technology, Atlanta, GA 30332 USA. dminn@cc.gatech.edu. 10th IEEE International Symposium on Wearable Computers. Oct. 2006

In this paper the authors discuss the discovery of human activity from sensor data. Rather than identifying the type of movement, this work pretend to discover if there are some patterns that appear frequently during stream data. The authors called motifs to this patterns and are practically the unit motions we discover in the paper of time series. Some interesting ideas of this paper are the use of a suffix tree to discover human motion in real time from stream data. Although the authors do not exploit this feature (they prefer to use a HMM), I think suffix tree can help to discover fragments of unit motions.

Finding motifs in time series (2002). Jessica Lin, Eamonn Keogh, Stefano Lonardi, Pranav Patel. In the 2nd workshop on temporal data mining, at the 8th ACM SIGKDD international

This is the former paper of Lin et at. about finding motifs in time series by using the SAX approach. Here, the authors present first a brute force algorithm to find motifs and then a refined version that use a complicated local hashing indexation of time series. Two interesting things I found useful in this paper was the assumption of normal probability for all the normalized time series. I plan to evaluate the normal probability plot of our time series to check if we have a normal distribution indeed. If not, a more general distribution (adaptative to the data) can be used to generate SAX symbols for the time series. In terms of indexation, the authors use ADM algorithm.

Keogh, E., Palpanas, T., Zordan, V. B., Gunopulos, D., and Cardle, M. 2004. Indexing large human-motion databases. In Proceedings of the Thirtieth international Conference on Very Large Data Bases - Volume 30 (Toronto, Canada, August 31 - September 03, 2004). M. A. Nascimento, M. T. Özsu, D. Kossmann, R. J. Miller, J. A. Blakeley, and K. B. Schiefer, Eds. Very Large Data Bases. VLDB Endowment, 780-791.

In this paper, Keogh et al. discuss the advantage of using DTW and not Euclidean distance when dealing with large databases. Here the concept of uniform scaling is presented as a method that is less imprecise than using only DTW. Unfortunately, in this work the all the time series has the same length, which is not common in real problems like human motion detection.
By reading these papers, I can see that we have the problem of motif detection to find unit motions during the time series that represents one video. And, we have the problem of partially identifying time series with a suffix tree. We also face specific problems like unit motions of varying length. I want to know the effect of scaling in amplitude, scaling in length (with Fourier coefficients) in terms of distance.

[Research] Unit motions within time series (adaptative method)

Unit motions are independent segments of the time series that contains motion. And they are separated by intervals of "silence" (no motion). We assumed a fixed value for the length of this separation. That is, if the distance, in terms of frames, between two unit motions is more than 12 frames, we consider these two unit motions as different unit motions. However, this fixed value sometimes gives us incorrect unit motions (unit motions are were considered together or incorrectly split). A employed Statistics to adapt this value to the nature of the time series. First I evaluate the mean u and variance d of the lengths of segments with silence. Then, the minimum distance to consider independent unit motions is t = u + 0.7sqrt(d). I evaluate then the new unit motions for all the time series and make clustering of the unit motions. The new results are slightly better in some movements which seems to indicates the importance of setting values of external parameters with adaptive methods.

The new results are the following:

Hand-based Foot-based
Boxing 94.7369 5.2631
Hand clapping94.7368 5.2632
Hand waving 52.6316 47.3684
Jogging 26.8421 73.1579
Running 21.5790 78.4210
Walking 26.3159 73.6841

And this are the previous one:

Hand-based Foot-based
Boxing 89.5% 10.5%
Hand clapping89.5% 10.5%
Hand waving 78.9% 21.1%
Jogging 28.8% 71.1%
Running 21.1% 78.9%
Walking 22.3% 77.7%

[Research] Obtaining Time Series to characterize human movement in video data

I finished the slides for the presentation on next Tuesday. They are 15 slides.

I read the final version of the HCI book chapter and fix errors made bu the editor during the revision of the paper.

Time series for all the videos were generated again. These time series does not consider the points that fall in the middle of the human body. I also made tests to generate time series with different number of gradients per video. Our previous approach considered the 20 most important gradients in terms of spatiotemporal variation. I made histograms of the gradients for each video and discover that taking the 10% of all the gradients discovered lead us to obtain more estable time series.