Recent Techniques of Clustering of Time Series Data: A Survey
---
paper_title: Data Mining Concepts and Techniques

paper_content:

Understand the need for analyses of large, complex, information-rich data sets. Identify the goals and primary tasks of the data-mining process. Describe the roots of data-mining technology. Recognize the iterative character of a data-mining process and specify its basic steps. Explain the influence of data quality on a data-mining process. Establish the relation between data warehousing and data mining. Data mining is an iterative process within which progress is defined by discovery, through either automatic or manual methods. Data mining is most useful in an exploratory analysis scenario in which there are no predetermined notions about what will constitute an "interesting" outcome. Data mining is the search for new, valuable, and nontrivial information in large volumes of data. It is a cooperative effort of humans and computers. Best results are achieved by balancing the knowledge of human experts in describing problems and goals with the search capabilities of computers. In practice, the two primary goals of data mining tend to be prediction and description. Prediction involves using some variables or fields in the data set to predict unknown or future values of other variables of interest. Description, on the other hand, focuses on finding patterns describing the data that can be interpreted by humans. Therefore, it is possible to put data-mining activities into one of two categories: Predictive data mining, which produces the model of the system described by the given data set, or Descriptive data mining, which produces new, nontrivial information based on the available data set.
---
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: Time-frequency clustering and discriminant analysis

paper_content:

We consider the use of time-varying spectra for classification and clustering of non-stationary time series. In particular, recent developments using local stationarity and Kullback-Leibler discrimination measures of distance are exploited for classifying earthquakes and mining explosions at regional distances.
---
paper_title: Detecting Climate Change in Multivariate Time Series Data by Novel Clustering and Cluster Tracing Techniques

paper_content:

Climate change can be detected in several scientific domains including hydrology, meteorology, and oceanography. In this paper we describe our on-going work for detecting change in multivariate time series data from these domains. For the detection, we extract climate patterns from the data, represented by clusters of time series, and trace the clusters over time. A climate pattern is categorized as a changing pattern if it shows a similar tendency over a significant amount of time, e.g. several years. Since existing clustering and cluster tracing approaches are not suitable for time series data, we are working on novel clustering and tracing approaches specifically for this purpose.
---
paper_title: On Clustering Multimedia Time Series Data Using K-Means and Dynamic Time Warping

paper_content:

After the generation of multimedia data turned digital, an explosion of interest in their data storage, retrieval, and processing has drastically increased. This includes videos, images, and audios, where we now have higher expectations in exploiting these data at hands. Typical manipulations are in some forms of video/image/audio processing, including automatic speech recognition, which require fairly large amount of storage and are computationally intensive. In our recent work, we have demonstrated the utility of time series representation in the task of clustering multimedia data using k-medoids method, which allows considerable amount of reduction in computational effort and storage space. However, k- means is a much more generic clustering method when Euclidean distance is used. In this work, we will demonstrate that unfortunately, k-means clustering will sometimes fail to give correct results, an unaware fact that may be overlooked by many researchers. This is especially the case when Dynamic Time Warping (DTW) is used as the distance measure in averaging the shape of time series. We also will demonstrate that the current averaging algorithm may not produce the real average of the time series, thus generates incorrect k-means clustering results, and then show potential causes why DTW averaging methods may not achieve meaningful clustering results. Lastly, we conclude with a suggestion of a method to potentially find the shape-based time series average that satisfies the required properties.
---
paper_title: A density based method for multivariate time series clustering in kernel feature space

paper_content:

Time series clustering finds applications in diverse fields of science and technology. Kernel based clustering methods like kernel K-means method need number of clusters as input and cannot handle outliers or noise. In this paper, we propose a density based clustering method in kernel feature space for clustering multivariate time series data of varying length. This method can also be used for clustering any type of structured data, provided a kernel which can handle that kind of data is used. We present heuristic methods to find the initial values of the parameters used in our proposed algorithm. To show the effectiveness of this method, this method is applied to two different online handwritten character data sets which are multivariate time series data of varying length, as a real world application. The performance of the proposed method is compared with the spectral clustering and kernel k-means clustering methods. Besides handling outliers, the proposed method performs as well as the spectral clustering method and outperforms the kernel k-means clustering method.
---
paper_title: A Novel Unascertained C-Means Clustering with Application

paper_content:

Using the theory and method of unascertained measure, a novel unascertained C-means clustering model and the clustering weight are established. The basic knowledge of the unascertained sets and concept of unascertained clustering was introduced briefly. Then, the unascertained measure was defined and clustering weight were set up. Experimental results show that the presented algorithm performs more robust to noise than the fuzzy C-means clustering (FCM) algorithm do. Furthermore, the results of stock market board analysis using proposed method that indicates the unascertained C-means clustering model provides a quantitative objective and efficient method of stock market board analysis, and hence is suitable to stock market board analysis.
---
paper_title: Fuzzy Clustering of Short Time-Series and Unevenly Distributed Sampling Points

paper_content:

This paper proposes a new algorithm in the fuzzy-c-means family, which is designed to cluster time-series and is particularly suited for short time-series and those with unevenly spaced sampling points. Short time-series, which do not allow a conventional statistical model, and unevenly sampled time-series appear in many practical situations. The algorithm developed here is motivated by common experiments in molecular biology. Conventional clustering algorithms based on the Euclidean distance or the Pearson correlation coefficient are not able to include the temporal information in the distance metric. The temporal order of the data and the varying length of sampling intervals are important and should be considered in clustering time-series. The proposed short time-series (STS) distance is able to measure similarity of shapes which are formed by the relative change of amplitude and the corresponding temporal information. We develop a fuzzy time-series (FSTS) clustering algorithm by incorporating the STS distance into the standard fuzzy clustering scheme. An example is provided to demonstrate the performance of the proposed algorithm.
---
paper_title: Clustering seasonality patterns in the presence of errors

paper_content:

Clustering is a very well studied problem that attempts to group similar data points. Most traditional clustering algorithms assume that the data is provided without measurement error. Often, however, real world data sets have such errors and one can obtain estimates of these errors. We present a clustering method that incorporates information contained in these error estimates. We present a new distance function that is based on the distribution of errors in data. Using a Gaussian model for errors, the distance function follows a Chi-Square distribution and is easy to compute. This distance function is used in hierarchical clustering to discover meaningful clusters. The distance function is scale-invariant so that clustering results are independent of units of measuring data. In the special case when the error distribution is the same for each attribute of data points, the rank order of pair-wise distances is the same for our distance function and the Euclidean distance function. The clustering method is applied to the seasonality estimation problem and experimental results are presented for the retail industry data as well as for simulated data, where it outperforms classical clustering methods.
---
paper_title: Activation detection in event-related fMRI through clustering ofwavelet distributions

paper_content:

We propose a new method for the detection of activated voxels in event-related BOLD fMRI data. We model the statistics of the wavelet histograms derived from each voxel time series independently through a generalized Gaussian distribution (GGD). We perform k-means clustering of the GGDs characterizing the voxel data in a synthetic data set, using the symmetrized Kullback-Leibler divergence (KLD) as a similarity measure. We compare our technique with GLM modeling and with another clustering method for activation detection that directly uses the wavelet coefficients as features. Our method is shown to be considerably more stable against realistic hemodynamic variability.
---
paper_title: Pattern Discovery from Stock Time Series Using Self-Organizing Maps †

paper_content:

† This work was supported by the RGC CERG project PolyU 5065/98E and the Departmental Grant H-ZJ84 ‡ Corresponding author ABSTRACT Pattern discovery from time series is of fundamental importance. Particularly when the domain expert derived patterns do not exist or are not complete, an algorithm to discover specific patterns or shapes automatically from the time series data is necessary. Such an algorithm is noteworthy in that it does not assume prior knowledge of the number of interesting structures, nor does it require an exhaustive explanation of the patterns being described. In this paper, a clustering approach is proposed for pattern discovery from time series. In view of its popularity and superior clustering performance, the self-organizing map (SOM) was adopted for pattern discovery in temporal data sequences. It is a special type of clustering algorithm that imposes a topological structure on the data. To prepare for the SOM algorithm, data sequences are segmented from the numerical time series using a continuous sliding window. Similar temporal patterns are then grouped together using SOM into clusters, which may subsequently be used to represent different structures of the data or temporal patterns. Attempts have been made to tackle the problem of representing patterns in a multi-resolution manner. With the increase in the number of data points in the patterns (the length of patterns), the time needed for the discovery process increases exponentially. To address this problem, we propose to compress the input patterns by a perceptually important point (PIP) identification algorithm. The idea is to replace the original data segment by its PIP’s so that the dimensionality of the input pattern can be reduced. Encouraging results are observed and reported for the application of the proposed methods to the time series collected from the Hong Kong stock market.
---
paper_title: A Wavelet-Based Anytime Algorithm for K-Means Clustering of Time Series

paper_content:

The emergence of the field of data mining in the last decade has sparked an increasing interest in clustering of time series. Although there has been much research on clustering in general, most classic machine learning and data mining algorithms do not work well for time series due to their unique structure. In particular, the high dimensionality, very high feature correlation, and the (typically) large amount of noise that characterize time series data present a difficult challenge. In this work we address these challenges by introducing a novel anytime version of k-Means clustering algorithm for time series. The algorithm works by leveraging off the multi-resolution property of wavelets. In particular, an initial clustering is performed with a very coarse resolution representation of the data. The results obtained from this “quick and dirty” clustering are used to initialize a clustering at a slightly finer level of approximation. This process is repeated until the clustering results stabilize or until the “approximation” is the raw data. In addition to casting k-Means as an anytime algorithm, our approach has two other very unintuitive properties. The quality of the clustering is often better than the batch algorithm, and even if the algorithm is run to completion, the time taken is typically much less than the time taken by the original algorithm. We explain, and empirically demonstrate these surprising and desirable properties with comprehensive experiments on several publicly available real data sets.
---
paper_title: Data Mining of Time Series Based on Wave Cluster

paper_content:

Considering the researching background, this paper discussed the associated research of data mining technology, time series and financial time series data mining, separately. As following, the basic theory and methods of phase space reconstruction were analyzed in details. All of these provided the theoretical basis and technical feasibility to time series data mining based on phase space reconstruction.After contrasting the different means of time series pattern mining, we pointed out the problem of time series data mining framework TSDM, and presented the temporal patterns mining method based Wave Cluster systematically.
---
paper_title: Combining ICA with SVR for prediction of finance time series

paper_content:

Due to the complexity of real task for learning, the learning algorithms based on ERM (empirical risk minimization) principle always have good fit for the training samples, but bad prediction for future samples. SVM(support vector machine) as a new kernel learning algorithm has embodied Vapnik's SRM (structure risk minimization) principle. It overcomes the problem for ERM posing by optimizing the object consisting of the learning error on the training samples and the capacity of hypothesis space. We'll use nonlinear support vector regression (SVR) in the prediction of finance time series. This may be illumined by the success of BP neural network and RBF neural network applied in finance time series. Before applying SVR, we use another new hot tool called ICA(independent component analysis)for feature extraction. Traditional PCA only takes into account the uncorrelated between features, however ICA considers the independence which is a more strict condition than PCA. Experiments have shown that our method based on ICA+SVR are superior to other methods, i.e. PCA+SVR, KPCA+SVR.
---
paper_title: Research on predicting agricultural drought based on fuzzy set and R/S analysis model

paper_content:

This paper uses fuzzy clustering iteration method to cluster the data of many years rainfall, and then considers sensitiveness coefficient as the foundation of calculating weight, which affects the crop output by valid rainfall in each growth stage. On this base, by means of the principle and method of R/S analysis, this paper establishes the predicting model to research on time series data mining of rainfall, then predicting the years of occurrence of agricultural drought. The result of application in Puyang irrigation area which is in Henan Province shows that the model is convenient and current, and is authentically feasible in the application of forecasting the years of occurrence of agricultural drought, which makes a guidance effect in agricultural production.
---
paper_title: Distance measures for effective clustering of ARIMA time-series

paper_content:

Much environmental and socioeconomic time-series data can be adequately modeled using autoregressive integrated moving average (ARIMA) models. We call such time series "ARIMA time series". We propose the use of the linear predictive coding (LPC) cepstrum for clustering ARIMA time series, by using the Euclidean distance between the LPC cepstra of two time series as their dissimilarity measure. We demonstrate that LPC cepstral coefficients have the desired features for accurate clustering and efficient indexing of ARIMA time series. For example, just a few LPC cepstral coefficients are sufficient in order to discriminate between time series that are modeled by different ARIMA models. In fact, this approach requires fewer coefficients than traditional approaches, such as DFT (discrete Fourier transform) and DWT (discrete wavelet transform). The proposed distance measure can be used for measuring the similarity between different ARIMA models as well. We cluster ARIMA time series using the "partition around medoids" method with various similarity measures. We present experimental results demonstrating that, using the proposed measure, we achieve significantly better clusterings of ARIMA time series data as compared to clusterings obtained by using other traditional similarity measures, such as DFT, DWT, PCA (principal component analysis), etc. Experiments were performed both on simulated and real data.
---
paper_title: A simulation study on clustering time series with metaheuristic methods

paper_content:

Given a set of time series, let be the cross-correlation matrix function which may be computed from prewhitened residual series. Then, a dissimilarity index is assumed between each pair of time series which accounts for the crosscorrelations but does not necessarily fulfills the Euclidean distance requirements. Metaheuristic methods are proposed to partition the set of time series into clusters in such a way that ( ) the cross-correlation maximum absolute value between each pair of time series that belong to the same cluster is greater than some given threshold, and ( ) the -min cluster criterion is minimized. The simulation experiment shows that suitably designed metaheuristic methods, and especially the tabu search algorithm, are able to solve this problem successfully, and produce results better than both the single linkage method, and, on the other hand, a pure random search algorithm.
---
paper_title: Stock markets forecasting based on fuzzy time series model

paper_content:

This paper is aimed at improving the forecasting accuracy with correcting two deficiencies, subintervals failing to well represent the data distribution structures and a single antecedent factor in the fuzzy relationships in current fuzzy time series models. First, the universe of discourse is partitioned into subintervals with the midpoints of two adjacent cluster centers generated by the fuzzy clustering method as their endpoints. And the sub-intervals are employed to fuzzify the time series into fuzzy time series. Then, the fuzzy time series model with multi-factors high-order fuzzy relationships is built up to forecast the stock markets. Finally, the model we produced is used to forecast the daily Shanghai Stock Exchange Composite index and Shenzhen Stock Exchange Component index, respectively. The results show that the model do improve the prediction accuracy compared with the benchmark model.
---
paper_title: Mixtures of ARMA models for model-based time series clustering

paper_content:

Clustering problems are central to many knowledge discovery and data mining tasks. However, most existing clustering methods can only work with fixed-dimensional representations of data patterns. In this paper we study the clustering of data patterns that are represented as sequences or time series possibly of different lengths. We propose a model-based approach to this problem using mixtures of autoregressive moving average (ARMA) models. We derive an expectation-maximization (EM) algorithm for learning the mixing coefficients as well as the parameters of component models. Experiments were conducted on simulated and real datasets. Results show that our method compares favorably with another method recently proposed by others for similar time series clustering problems.
---
paper_title: Time Series Clustering Via RPCL Network Ensemble With Different Representations

paper_content:

Time series clustering provides underpinning techniques for discovering the intrinsic structure and condensing/summarizing information conveyed in time series, which is demanded in various fields ranging from bioinformatics to video content understanding. In this paper, we present an unsupervised ensemble learning approach to time series clustering by combining rival-penalized competitive learning (RPCL) networks with different representations of time series. In our approach, the RPCL network ensemble is employed for clustering analyses based on different representations of time series whenever available, and an optimal selection function is applied to find out a final consensus partition from multiple partition candidates yielded by applying various consensus functions for the combination of competitive learning results. As a result, our approach first exploits its capability of the RPCL rule in clustering analysis of automatic model selection on individual representations and subsequently applies ensemble learning for the synergy of reconciling diverse partitions resulted from the use of different representations and augmenting RPCL networks in automatic model selection and overcoming its inherent limitation. Our approach has been evaluated on 16 benchmark time series data mining tasks with comparison to state-of-the-art time series clustering techniques. Simulation results demonstrate that our approach yields favorite results in clustering analysis of automatic model selection.
---

Title: Recent Techniques of Clustering of Time Series Data: A Survey
Section 1: INTRODUCTION
Description 1: This section provides an overview of time series clustering, discussing different types and the challenges associated with high dimensionality, temporal order, and noise.

Section 2: MAJOR TIME SERIES CLUSTERING APPROACHES
Description 2: This section divides time series clustering methods into three major categories based on whether they work directly with raw data, indirectly with features extracted from raw data, or indirectly with models built from raw data.

Section 3: Literature Survey of TemporalProximity-Based Clustering Approach
Description 3: This section surveys various temporal-proximity-based clustering methods that work directly with raw time series data, detailing important contributions and experiments in the field.

Section 4: Literature Survey of RepresentationBased Clustering Approach
Description 4: This section discusses representation-based clustering methods that first convert raw time series data into feature vectors of lower dimension before applying clustering algorithms.

Section 5: Literature Survey of Model-Based Clustering Approach
Description 5: This section explores model-based clustering methods that consider each time series as being generated by some kind of model or probability distribution, focusing on methodologies and experiments.

Section 6: CONCLUSIONS
Description 6: This section summarizes the recent techniques in clustering of time series, discusses the uniqueness and limitations of previous research, and identifies potential topics for future research.