Clustering Time Series Data Stream - A Literature Survey
---
paper_title: Application of Fuzzy Grade-of-Membership Clustering to Analysis of Remote Sensing Data

paper_content:

Abstract A fuzzy grade-of-membership (GoM) clustering algorithm is applied to analysis of remote sensing data, in particular, the type of data used in climatic classification. The methodology is applied to a cloud product data subset derived from NASA’s International Satellite Cloud Climatology Project, which includes remotely sensed global monthly average surface temperature and precipitation data for land and coastal regions for the year 1984. GoM partitions for this case are similar to those of vector quantization and fuzzy c-means clustering algorithms, which is significant given the striking differences between the algorithms. The GoM clustering approach is shown to provide an alternative means of interpreting large heterogeneous datasets for exploratory analysis, which broadens the application base by admitting categorical data.
---
paper_title: Combining conceptual clustering and principal component analysis for state space based process monitoring

paper_content:

Multivariate statistics and unsupervised machine learning have recently been studied by many researchers for process monitoring and fault diagnosis. These approaches often depend on calculating a similarity or distance measure to group data sets into clusters. Apart from giving predictions, they are not able to give causal explanations on why a specific set of data is assigned to a particular cluster. In this work, a conceptual clustering approach is presented for designing state space based monitoring systems, which is able to generate conceptual knowledge on the major variables which are responsible for clustering, as well as projecting the operation to a specific operational state. A critical issue in this approach is how to conceptually represent dynamic trend signals. For this purpose, principal component analysis is used for concept extraction from real-time dynamic trend signals. The method is introduced using a continuous stirred tank reactor as a case study. Application of the approach to a refinery methyl tert-butyl ether process is also presented.
---
paper_title: Querying and mining of time series data: experimental comparison of representations and distance measures

paper_content:

The last decade has witnessed a tremendous growths of interests in applications that deal with querying and mining of time series data. Numerous representation methods for dimensionality reduction and similarity measures geared towards time series have been introduced. Each individual work introducing a particular method has made specific claims and, aside from the occasional theoretical justifications, provided quantitative experimental observations. However, for the most part, the comparative aspects of these experiments were too narrowly focused on demonstrating the benefits of the proposed methods over some of the previously introduced ones. In order to provide a comprehensive validation, we conducted an extensive set of time series experiments re-implementing 8 different representation methods and 9 similarity measures and their variants, and testing their effectiveness on 38 time series data sets from a wide variety of application domains. In this paper, we give an overview of these different techniques and present our comparative experimental findings regarding their effectiveness. Our experiments have provided both a unified validation of some of the existing achievements, and in some cases, suggested that certain claims in the literature may be unduly optimistic.
---
paper_title: Online clustering of parallel data streams

paper_content:

In recent years, the management and processing of so-called data streams has become a topic of active research in several fields of computer science such as, e.g., distributed systems, database systems, and data mining. A data stream can roughly be thought of as a transient, continuously increasing sequence of time-stamped data. In this paper, we consider the problem of clustering parallel streams of real-valued data, that is to say, continuously evolving time series. In other words, we are interested in grouping data streams the evolution over time of which is similar in a specific sense. In order to maintain an up-to-date clustering structure, it is necessary to analyze the incoming data in an online manner, tolerating not more than a constant time delay. For this purpose, we develop an efficient online version of the classical K-means clustering algorithm. Our method's efficiency is mainly due to a scalable online transformation of the original data which allows for a fast computation of approximate distances between streams.
---
paper_title: Efficient Similarity Search over Future Stream Time Series

paper_content:

With the advance of hardware and communication technologies, stream time series is gaining ever-increasing attention due to its importance in many applications such as financial data processing, network monitoring, Web click-stream analysis, sensor data mining, and anomaly detection. For all of these applications, an efficient and effective similarity search over stream data is essential. Because of the unique characteristics of the stream, for example, data are frequently updated and real-time response is required, the previous approaches proposed for searching through archived data may not work in the stream scenarios. Especially, in the cases where data often arrive periodically for various reasons (for example, the communication congestion or batch processing), queries on such incomplete time series or even future time series may result in inaccuracy using traditional approaches. Therefore, in this paper, we propose three approaches, polynomial, Discrete Fourier Transform (DFT), and probabilistic, to predict the unknown values that have not arrived at the system and answer similarity queries based on the predicted data. We also apply efficient indexes, that is, a multidimensional hash index and a B+-tree, to facilitate the prediction and similarity search on future time series, respectively. Extensive experiments demonstrate the efficiency and effectiveness of our methods for prediction and answering queries.
---
paper_title: Cluster Analysis of Time-Series Medical Data Based on the Trajectory Representation and Multiscale Comparison Techniques

paper_content:

This paper presents a cluster analysis method for multidimensional time-series data on clinical laboratory examinations. Our method represents the time series of test results as trajectories in multidimensional space, and compares their structural similarity by using the multiscale comparison technique. It enables us to find the part-to-part correspondences between two trajectories, taking into account the relationships between different tests. The resultant dissimilarity can be further used with clustering algorithms for finding the groups of similar cases. The method was applied to the cluster analysis of Albumin-Platelet data in the chronic hepatitis dataset. The results denonstrated that it could form interesting groups of cases that have high correspondence to the fibrotic stages.
---
paper_title: Clustering Short Time Series Gene Expression Data

paper_content:

Motivation: Time series expression experiments are used to study a wide range of biological systems. More than 80% of all time series expression datasets are short (8 time points or fewer). These datasets present unique challenges. On account of the large number of genes profiled (often tens of thousands) and the small number of time points many patterns are expected to arise at random. Most clustering algorithms are unable to distinguish between real and random patterns. ::: ::: Results: We present an algorithm specifically designed for clustering short time series expression data. Our algorithm works by assigning genes to a predefined set of model profiles that capture the potential distinct patterns that can be expected from the experiment. We discuss how to obtain such a set of profiles and how to determine the significance of each of these profiles. Significant profiles are retained for further analysis and can be combined to form clusters. We tested our method on both simulated and real biological data. Using immune response data we show that our algorithm can correctly detect the temporal profile of relevant functional categories. Using Gene Ontology analysis we show that our algorithm outperforms both general clustering algorithms and algorithms designed specifically for clustering time series gene expression data. ::: ::: Availability: Information on obtaining a Java implementation with a graphical user interface (GUI) is available from http://www.cs.cmu.edu/~jernst/st/ ::: ::: Contact: jernst@cs.cmu.edu ::: ::: Supplementary information: Available at http://www.cs.cmu.edu/~jernst/st/
---
paper_title: Clustering Time-Series Gene Expression Data Using Smoothing Spline Derivatives

paper_content:

Microarray data acquired during time-course experiments allow the temporal variations in gene expression to be monitored. An original postprandial fasting experiment was conducted in the mouse and the expression of 200 genes was monitored with a dedicated macroarray at 11 time points between 0 and 72 hours of fasting. The aim of this study was to provide a relevant clustering of gene expression temporal profiles. This was achieved by focusing on the shapes of the curves rather than on the absolute level of expression. Actually, we combined spline smoothing and first derivative computation with hierarchical and partitioning clustering. A heuristic approach was proposed to tune the spline smoothing parameter using both statistical and biological considerations. Clusters are illustrated a posteriori through principal component analysis and heatmap visualization. Most results were found to be in agreement with the literature on the effects of fasting on the mouse liver and provide promising directions for future biological investigations.
---
paper_title: Unsupervised Feature Extraction for Time Series Clustering Using Orthogonal Wavelet Transform

paper_content:

Unsupervised Feature Extraction for Time Series Clustering Using Orthogonal Wavelet Transform
---
paper_title: Clustering Streaming Time Series Using CBC

paper_content:

Clustering streaming time series is a difficult problem. Most traditional algorithms are too inefficient for large amounts of data and outliers in them. In this paper, we propose a new clustering method, which clusters Bi-clipped (CBC) stream data. It contains three phrases, namely, dimensionality reduction through piecewise aggregate approximation (PAA), Bi-clipped process that clipped the real valued series through bisecting the value field, and clustering. Through related experiments, we find that CBC gains higher quality solutions in less time compared with M-clipped method that clipped the real value series through the mean of them, and unclipped methods. This situation is especially distinct when streaming time series contain outliers.
---
paper_title: Clustering Data Streams: Theory and Practice

paper_content:

The data stream model has recently attracted attention for its applicability to numerous types of data, including telephone records, Web documents, and clickstreams. For analysis of such data, the ability to process the data in a single pass, or a small number of passes, while using little memory, is crucial. We describe such a streaming algorithm that effectively clusters large data streams. We also provide empirical evidence of the algorithm's performance on synthetic and real data streams.
---
paper_title: Characteristic-Based Clustering for Time Series Data

paper_content:

With the growing importance of time series clustering research, particularly for similarity searches amongst long time series such as those arising in medicine or finance, it is critical for us to find a way to resolve the outstanding problems that make most clustering methods impractical under certain circumstances. When the time series is very long, some clustering algorithms may fail because the very notation of similarity is dubious in high dimension space; many methods cannot handle missing data when the clustering is based on a distance metric. ::: ::: This paper proposes a method for clustering of time series based on their structural characteristics. Unlike other alternatives, this method does not cluster point values using a distance metric, rather it clusters based on global features extracted from the time series. The feature measures are obtained from each individual series and can be fed into arbitrary clustering algorithms, including an unsupervised neural network algorithm, self-organizing map, or hierarchal clustering algorithm. ::: ::: Global measures describing the time series are obtained by applying statistical operations that best capture the underlying characteristics: trend, seasonality, periodicity, serial correlation, skewness, kurtosis, chaos, nonlinearity, and self-similarity. Since the method clusters using extracted global measures, it reduces the dimensionality of the time series and is much less sensitive to missing or noisy data. We further provide a search mechanism to find the best selection from the feature set that should be used as the clustering inputs. ::: ::: The proposed technique has been tested using benchmark time series datasets previously reported for time series clustering and a set of time series datasets with known characteristics. The empirical results show that our approach is able to yield meaningful clusters. The resulting clusters are similar to those produced by other methods, but with some promising and interesting variations that can be intuitively explained with knowledge of the global characteristics of the time series.
---
paper_title: Clustering Time Series with Clipped Data

paper_content:

Clustering time series is a problem that has applications in a wide variety of fields, and has recently attracted a large amount of research. Time series data are often large and may contain outliers. We show that the simple procedure of clipping the time series (discretising to above or below the median) reduces memory requirements and significantly speeds up clustering without decreasing clustering accuracy. We also demonstrate that clipping increases clustering accuracy when there are outliers in the data, thus serving as a means of outlier detection and a method of identifying model misspecification. We consider simulated data from polynomial, autoregressive moving average and hidden Markov models and show that the estimated parameters of the clipped data used in clustering tend, asymptotically, to those of the unclipped data. We also demonstrate experimentally that, if the series are long enough, the accuracy on clipped data is not significantly less than the accuracy on unclipped data, and if the series contain outliers then clipping results in significantly better clusterings. We then illustrate how using clipped series can be of practical benefit in detecting model misspecification and outliers on two real world data sets: an electricity generation bid data set and an ECG data set.
---
paper_title: A Clustering Algorithm for Time Series Data

paper_content:

In the Intelligent Traffic System, the research about the analysis of time series of traffic flow is important and meaningful. Using clustering methods to analyze time series not only can find some typical patterns of traffic flow, but also can group the sections of highway by their different flow characteristics. In this paper, we propose an Encoded-Bitmap-approach-based swap method to improve the classic hierarchical method. Experiments show that the proposed method has a better performance on the change trend of time series than classic algorithm.
---
paper_title: Clustering time series from ARMA models with clipped data

paper_content:

Clustering time series is a problem that has applications in a wide variety of fields, and has recently attracted a large amount of research. In this paper we focus on clustering data derived from Autoregressive Moving Average (ARMA) models using k-means and k-medoids algorithms with the Euclidean distance between estimated model parameters. We justify our choice of clustering technique and distance metric by reproducing results obtained in related research. Our research aim is to assess the affects of discretising data into binary sequences of above and below the median, a process known as clipping, on the clustering of time series. It is known that the fitted AR parameters of clipped data tend asymptotically to the parameters for unclipped data. We exploit this result to demonstrate that for long series the clustering accuracy when using clipped data from the class of ARMA models is not significantly different to that achieved with unclipped data. Next we show that if the data contains outliers then using clipped data produces significantly better clusterings. We then demonstrate that using clipped series requires much less memory and operations such as distance calculations can be much faster. Finally, we demonstrate these advantages on three real world data sets.
---
paper_title: Hierarchical Clustering of Time-Series Data Streams

paper_content:

This paper presents and analyzes an incremental system for clustering streaming time series. The Online Divisive-Agglomerative Clustering (ODAC) system continuously maintains a tree-like hierarchy of clusters that evolves with data, using a top-down strategy. The splitting criterion is a correlation-based dissimilarity measure among time series, splitting each node by the farthest pair of streams. The system also uses a merge operator that reaggregates a previously split node in order to react to changes in the correlation structure between time series. The split and merge operators are triggered in response to changes in the diameters of existing clusters, assuming that in stationary environments, expanding the structure leads to a decrease in the diameters of the clusters. The system is designed to process thousands of data streams that flow at a high rate. The main features of the system include update time and memory consumption that do not depend on the number of examples in the stream. Moreover, the time and memory required to process an example decreases whenever the cluster structure expands. Experimental results on artificial and real data assess the processing qualities of the system, suggesting a competitive performance on clustering streaming time series, exploring also its ability to deal with concept drift.
---
paper_title: Time-series clustering by approximate prototypes

paper_content:

Clustering time-series data poses problems, which do not exist in traditional clustering in Euclidean space. Specifically, cluster prototype needs to be calculated, where common solution is to use cluster medoid. In this work, we define an optimal prototype as an optimization problem and propose a local search solution to it. We experimentally compare different time-series clustering methods and find out that the proposed prototype with agglomerative clustering followed by k-means algorithm provides best clustering accuracy.
---

Title: Clustering Time Series Data Stream - A Literature Survey

Section 1: INTRODUCTION
Description 1: This section introduces the topic of time series data management and clustering, explaining the constraints of traditional methods and the necessity of new algorithms for high-speed, real-time data processing. It also provides an overview of the applications and categories of clustering techniques.

Section 2: RELATED WORK
Description 2: This section discusses the various clustering techniques that have been proposed for time series data streams, summarizing the methods and highlighting their strengths and limitations through various studies.

Section 3: FUTURE WORK
Description 3: This section suggests potential directions for future research, focusing on improving clustering methods for high-dimensional data, increasing computational efficiency, predicting future values, and handling the storage and processing challenges of raw time series data.

Section 4: CONCLUSION
Description 4: This section summarizes the importance of clustering time series data streams, reviews the surveyed algorithms, discusses their categories, and mentions the potential areas for further study to improve clustering methods.