Time Series Data Clustering Based on Differential Evolution Algorithm and Discrete Cosine Transform

Time series is a type of data with complex structure. Analysis of time series is used in sciences such as meteorology, economics, geology, marine science, medicine and engineering widely. So, Because of time series applications in various sciences, the interest to analyze these data has been increased.On the other hand by developing information gathering technologies such as mobile, GPS and sensors, and Access to large volumes of time series data, we always require methods to extract useful information from large datasets. Thus, data mining is an important method for solving this problem. Clustering analysis as the most commonly used function of data mining, has attracted many researchers in computer science. Clustering is a strong instrument for knowledge discovery and it provides useful information about existing patterns in datasets. In general, the purpose of clustering is representing large datasets by a fewer number of cluster centers. It simplifies large datasets and thus is an important step in the process of knowledge discovery and data mining. Fuzzy C-means (FCM) clustering is one of the most important classic clustering methods that have been used in many researches. The main disadvantage of this method is the high probability of getting trapped in local optima especially in facing high-dimensional data such as time series. Furthermore Euclidean distance is the most commonly used similarity measure in Fuzzy C-means but sometimes, its necessary to use another similarity/dissimilarity measures instead of Euclidean distance. In this paper in order to compensate the shortcomings of Fuzzy C-means algorithm, we used one of the existing evolutionary algorithms. Evolutionary algorithms has gained huge popularity in the field of pattern recognition and clustering recently. Among the existing evolutionary algorithms, the differential evolution algorithm as a strong, fast and efficient global search method has been attracted the attention of researchers. In this paper, we proposed a technique for clustering time series data using a combination of Fuzzy C-means and differential evolution (DE) approach and we considered dynamic time warping (DTW) as distance measures between time series. Also, in this method we used Discrete Cosine Transform (DCT) to time series dimension reduction. Finding all elements of cluster centers using differential evolution is time consuming and the large number of unknown parameters related to the cluster centers will reduce the efficiency and the speed of differential evolution algorithm.So, for reducing the search space,the most important Discrete Cosine Transform coefficients of the cluster centers were recognized as the main unknown clustering problem in the proposed method and differential evolution algorithm tries to determine the near optimal Discrete Cosine Transform coefficients of cluster centers by minimizing the Fuzzy C-means objective function. Experimental results over two popular data sets indicate the superiority of the proposed technique compared to fuzzy C-means and a clustering algorithm based on differential evolution without using dimension reduction techniques.Comparing the run time of the methods, the proposed method is slower than the Fuzzy C-means clustering algorithm, but due to the use of discrete cosine transform method to reduce unknowns, it operates faster than differential evolution without using dimension reduction techniques.