Time-series clustering – A decade review

Clustering is a solution for classifying enormous data when there is not any early knowledge about classes. With emerging new concepts like cloud computing and big data and their vast applications in recent years, research works have been increased on unsupervised solutions like clustering algorithms to extract knowledge from this avalanche of data. Clustering time-series data has been used in diverse scientific areas to discover patterns which empower data analysts to extract valuable information from complex and massive datasets. In case of huge datasets, using supervised classification solutions is almost impossible, while clustering can solve this problem using un-supervised approaches. In this research work, the focus is on time-series data, which is one of the popular data types in clustering problems and is broadly used from gene expression data in biology to stock market analysis in finance. This review will expose four main components of time-series clustering and is aimed to represent an updated investigation on the trend of improvements in efficiency, quality and complexity of clustering time-series approaches during the last decade and enlighten new paths for future works.     

An Effective Software Pipelining Algorithm for Clustered Embedded VLIW Processors

This paper proposes a software pipelining framework, CALiBeR (ClusterAware Load Balancing Retiming Algorithm), suitable for compilers targetingclustered embedded VLIW processors. CALiBeR can be used by embedded systemdesigners to explore different code optimization alternatives, that is, high-qualitycustomized retiming solutions for desired throughput and program memory sizerequirements, while minimizing register pressure. An extensive set of experimentalresults is presented, demonstrating that our algorithm compares favorablywith one of the best state-of-the-art algorithms, achieving up to 50% improvementin performance and up to 47% improvement in register requirements. In orderto empirically assess the effectiveness of clustering for high ILP applications,additional experiments are presented contrasting the performance achievedby software pipelined kernels executing on clustered and on centralized machines.     

FindOut: Finding Outliers in Very Large Datasets

Finding the rare instances or the outliers is important in many KDD (knowledge discovery and data-mining) applications, such as detecting credit card fraud or finding irregularities in gene expressions. Signal-processing techniques have been introduced to transform images for enhancement, filtering, restoration, analysis, and reconstruction. In this paper, we present a new method in which we apply signal-processing techniques to solve important problems in data mining. In particular, we introduce a novel deviation (or outlier) detection approach, termed FindOut, based on wavelet transform. The main idea in FindOut is to remove the clusters from the original data and then identify the outliers. Although previous research showed that such techniques may not be effective because of the nature of the clustering, FindOut can successfully identify outliers from large datasets. Experimental results on very large datasets are presented which show the efficiency and effectiveness of the proposed approach. Received 7 September 2000 / Revised 2 February 2001 / Accepted in revised form 31 May 2001 Correspondence and offprint requests to: A. Zhang, Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA. Email: azhang@cse.buffalo.eduau     

An efficient clustering scheme using support vector methods

Support vector clustering involves three steps—solving an optimization problem, identification of clusters and tuning of hyper-parameters. In this paper, we introduce a pre-processing step that eliminates data points from the training data that are not crucial for clustering. Pre-processing is efficiently implemented using the R*-tree data structure. Experiments on real-world and synthetic datasets show that pre-processing drastically decreases the run-time of the clustering algorithm. Also, in many cases reduction in the number of support vectors is achieved. Further, we suggest an improvement for the step of identification of clusters.     

探讨在版面分析中的聚类稳定性问题

版面分析过程可以理解为同模式类对象间聚类(合并)的过程,而这种聚类存在的风险(hazard)是伴随整个聚类过程中的。而且越是在后期,该风险值越高,即一旦出现聚类错误则将导致前期正确的聚类结果付诸东流。该文将就此问题展开关于版面分析中的聚类稳定性问题的探讨,并提出相应的逻辑规则——逻辑判别函数(logic differentiation function)用来指导聚类和其在聚类算法中的应用;实验结果表明,建立在定性分析基础上的该规则能解决聚类过程的稳定性问题,同时该规则可以应用在存在若干模式类对象聚类的场合中。     

A novel fuzzy clustering algorithm for the analysis of axillary lymph node tissue sections

Recently Fourier Transform Infrared (FTIR) spectroscopic imaging has been used as a tool to detect the changes in cellular composition that may reflect the onset of a disease. This approach has been investigated as a mean of monitoring the change of the biochemical composition of cells and providing a diagnostic tool for various human cancers and other diseases. The discrimination between different types of tissue based upon spectroscopic data is often achieved using various multivariate clustering techniques. However, the number of clusters is a common unknown feature for the clustering methods, such as hierarchical cluster analysis, k-means and fuzzy c-means. In this study, we apply a FCM based clustering algorithm to obtain the best number of clusters as given by the minimum validity index value. This often results in an excessive number of clusters being created due to the complexity of this biochemical system. A novel method to automatically merge clusters was developed to try to address this problem. Three lymph node tissue sections were examined to evaluate our new method. These results showed that this approach can merge the clusters which have similar biochemistry. Consequently, the overall algorithm automatically identifies clusters that accurately match the main tissue types that are independently determined by the clinician.     

A clustering method to distribute a database on a grid

Clusters and grids of workstations provide available resources for data mining processes. To exploit these resources, new distributed algorithms are necessary, particularly concerning the way to distribute data and to use this partition. We present a clustering algorithm dubbed Progressive Clustering that provides an “intelligent” distribution of data on grids. The usefulness of this algorithm is shown for several distributed datamining tasks.     

On principal component analysis, cosine and Euclidean measures in information retrieval

Clustering groups document objects represented as vectors. An extensive vector space may cause obstacles to applying these methods. Therefore, the vector space was reduced with principal component analysis (PCA). The conventional cosine measure is not the only choice with PCA, which involves the mean-correction of data. Since mean-correction changes the location of the origin, the angles between the document vectors also change. To avoid this, we used a connection between the cosine measure and the Euclidean distance in association with PCA, and grounded searching on the latter. We applied the single and complete linkage and Ward clustering to Finnish documents utilizing their relevance assessment as a new feature. After the normalization of the data PCA was run and relevant documents were clustered.     

Information cut for clustering using a gradient descent approach

We introduce a new graph cut for clustering which we call the Information Cut. It is derived using Parzen windowing to estimate an information theoretic distance measure between probability density functions. We propose to optimize the Information Cut using a gradient descent-based approach. Our algorithm has several advantages compared to many other graph-based methods in terms of determining an appropriate affinity measure, computational complexity, memory requirements and coping with different data scales. We show that our method may produce clustering and image segmentation results comparable or better than the state-of-the art graph-based methods.     

A clustering method for automatic biometric template selection

The problem addressed in this paper is the template selection and update in biometrics based on clustering. Template selection is a reliable method to reduce the number of templates used in a biometric system to account for variations observed in a person's biometric data. An efficient method based on clustering with automatic selection of the number of clusters is proposed in this work for finding subgroups of similar templates which are used for prototype selection.Experimental results confirm the advantage of the new method and the importance of adopting a procedure to perform template selection.