TimeCluster: Dimension Reduction Applied to Temporal Data For Visual Analytics

This article is about proposing an advanced algorithm for forecasting time series and reducing high dimensionality. The researchers used auto-encoder architecture with convolutional operators to deal with the complexity of sequential data and amazingly they were successful.

Photo by Drew Beamer on Unsplash

About two years ago, I had to cope with time-series data and work on them. It was quite difficult for me at that time, because I hadn’t known anything about how to work on sequential data. Thus, I have started to read a large number of papers and finally, I have gained experience on time series data and done two projects that I applied most conventional algorithms. This encouraged me to write about the most interesting research that I am into them. This article is about one of those researches that I did like to use in my scientific paper but did not. By the way, it is worthy to discuss and it is probable to obtain this architecture in my future project.

The second project that I worked on was quite high dimensional (I think it had about 50 features); thus, I had to read about reducing dimensionality. Yes, you are right; this article is about capturing long dependencies by monitoring their variations over time, finding repetitive patterns, recognizing outliers, and effectively labeling data instances. These tasks are usually done individually; but, in this research, a single model architecture is proposed to do all of them simultaneously. Some other techniques for reducing dimensionality are used for comparison. Because of the power of capturing features, we use deep learning for multivariate time-series data.

Owing to the importance of understanding time-series data, a number of techniques have been developed. In most cases, automated techniques have not accomplished acceptance results, thus researchers rely on visual analytics tools to do their works. What do visual analytics tools do? These tools blend the strengths of machine abilities with human abilities to simplify exploration, analysis, understanding, and providing insights. The goal of this visual process is to tightly couple automatic analysis methods and interactive visualization, to analyze, explore and understand data.

For small time-series datasets, we use time-series graphs, which are usually useful. However, graphs cannot be effective and become challenging for some other tasks such as anomaly detection, classifying time-series subsequences into clusters of similar patterns, etc. We can find some other alternatives for visual encoding like color-fields, horizon graphs, etc.

The summary of this research can be written as below:

1. Illustrate a visual analytics system that can be used for identifying patterns, repeated patterns (cluster), outliers (anomalies), and transitions between states in large time-series data.
2. Use a deep convolutional auto-encoder (DCAE)
3. Provide visual comparisons for various methods
4. Evaluating with two different datasets

Overview of the methodology

Figure 1. An overview of our proposed visual analytics approach. It starts from raw time-series data and ends allowing users to interact with the system and changing the parameters which help to improve and fit the users tasks. Transforming time-series data into a 2D space (points) passing through a multi-step process including preprocessing (the time-series data are in high-dimensional space after this step), dimensionality reduction techniques are used to project each sliding window into a 2D space (if the number of time-dependent variables is univariate PCA, t-SNE, or UMAP are applied directly on the sliding window matrix, but if it is multivariate, DCAE is applied to extract important features which are then projected into a 2D space using PCA, t-SNE, or UMAP), visualizing the data into a 2D space, assisting users to detect outliers and frequent patterns in large time-series data, and allowing users to interact with the system and customize views. [source]

Data Preprocessing

Normalization

Normalizing is a simple transformation of the scale of the data into a limited domain (usually [0,1] or [-1,+1]). In this research, all values of datasets normalized into the range of [0,1]. The formula is demonstrated below:

Eq. 1

Sliding window approach

This approach is prevalent for multivariate time-series data D of dimension d with n time-steps.

D = X₁, X₂, X₃, …, Xₙ

• w: window width
• s: stride
• t: the start time of a sliding window

We’d define a new matrix Zₖ which can be seen as below:

In this research, the values of w and s are equal to 60 and 1 respectively. These values are changeable, and you can set another value to have different resolutions to impact your results.

• The overlapping among windows is good because it can help you to prevent lost data and simplify the smooth transition between time-steps(s) after decreasing the dimension of the features.

The results of the sliding window are considered as points in high-dimensional space. Each point shows the phenomena that are happened at various time intervals.

Dimensionality Reduction (DR)

The reason for reducing dimensionality is to provide another view for us to analyze visually and explore the time-series data. Here, the goal is to reduce the number of features to 2 (two dimensions) by obtaining DR techniques. In a nutshell, selecting which technique to be obtained is crucial because the visualization phase relies on it.

There are several non-linear and linear methods to reduce dimensionality, and three of those popular ones that have been widely used are PCA, t-SNE, and UMAP. (if you are aware of these techniques, feel free to skip 🙂)

PCA (Principal Component Analysis)

Principal Component Analysis(PCA) is one of the most popular linear dimension reduction. Sometimes, it is used alone and sometimes as a starting solution for other dimension reduction methods. PCA is a projection-based method that transforms the data by projecting it onto a set of orthogonal axes. [source]

t-SNE (t-Stochastic Neighbor Embedding)

t-SNE is a new award-winning technique for dimension reduction and data visualization. t-SNE not only captures the local structure of the higher dimension but also preserves the global structures of the data like clusters. It has a stunning ability to produce well-defined segregated clusters. t-SNE is based on stochastic neighbor embedding(SNE). t-SNE was developed to address some of the problems in SNE. [source]

UMAP (Uniform Manifold Approximation and Projection)

Uniform Manifold Approximation and Projection (UMAP) is a dimension reduction technique that can be used for visualization similarly to t-SNE, but also for general non-linear dimension reduction. [source]

In this research, these three and the proposed deep convolutional auto-encoder (will be discussed in the next section) are used for dimensionality reduction. The aim is to differentiate and visualize high-dimensional data by having a location in a two-dimension space for each point. Also, the high-dimensional data has its own complexity therefore to deal with that researchers used DCAE and then used DR techniques to reach 2D visualization; whereas, univariate time-series are less complicated and straightway reduced to a 2D using those three earlier mentioned DR techniques.

Figure 2. Top: (all) a selected part of the time-series graph which contains 12000 flow data points of breathing (exhalation and inhalation for one person). Bottom: connected scatter plot of the data after applying our methodology, a PCA, b t-SNE, and c UMAP. The yellow highlight in the time-series graph with the corresponding yellow points are shown in the connected scatter plot indicates the breathing at that moment was completely distinct which is clearly obvious once it is labeled in the time-series graph [source]

Deep Convolutional Auto-Encoder (DCAE)

We can use the Auto-Encoder structure for reducing dimensionality. Also, in recent years, Convolutional operators have shown great potential for various complex tasks. Consequently, when it comes to being deep; I mean deep convolutional auto-encoder, we have a potent model architecture that is able to reduce nonlinear dimensionality.

In regard to being supervised or unsupervised learning, DCAE is an unsupervised algorithm that consists of an encoder and decoder parts, the encoder encodes the data to project the data into a set of feature spaces and the decoder decodes the output of the encoder to rebuild the output data. The locality feature of convolutions puts DCAE in a better position with less time consumption in comparison with usual auto-encoders in rebuilding.

I will demonstrate all concepts that I think will be useful; so, if you are aware of these you can skip these sections.😉

Auto-Encoder

In brief, auto-encoders are unsupervised learning architecture that at the first half of its structure compress and encodes the data and then reconstruct the data in the latter part. In other words, by encoding the data, the model reduces the dimensions of the data by denying the noise of the data.

Figure 3. [source]

For a thorough understanding of auto-encoders, I highly recommend reading this Stanford tutorial. Also, you can read this blog that is complete to me. Also, this is a good introduction to implementing auto-encoders in TensorFlow.

Convolutional Neural Networks

First-time CNNs used was around the 1980s to recognize handwritten digits. CNNs are a class of networks and mostly applied on images, but have shown great potential on time-series datasets. The role of CNNs in image processing is to transform images to a form that makes the process simpler. Well, here images are not the case.

CNNs can be used to obtain feature maps by filtering the input in which each convolutional layer includes kernels and bias. The process of convolution can be described as below:

Eq 2.

DCAE Architecture

Table 1. The architecture of the deep convolutional auto-encoder with the dense layer highlighted in bold [source]

As it can be seen, the activation function for all layers is ReLu (ReLu(x) = max(0,x))except the last layer for output. The model includes three main parts (encoder, decoder, and bottleneck (compressed representation)).

In the encoder, we have three convolutional layers and each follows by a pooling layer. The max-pooling is used which is a down-sampling operation on feature maps. and likewise the decoder part. First decreasing the size of layers to reach the bottleneck and then, increasing. The model works by repeating each temporal step n times along the time axis.

The Python code for the model in TensorFlow can be coded as below:

The run summary (statistically) can be summarized as below:

Run Summary of DCAE

The chosen optimizer is Adam optimizer and the batch_size is 100 random shuffled windows. The researchers trained DCAE for the feature extraction process. Then, they projected the features in the latent space (bottleneck) to 2D space by use of DR techniques. This can be seen from figure 4.:

Figure 4. DCAE followed by a PCA, b t-SNE, and c UMAP to create the 2D visualization. This figure also shows the Auto-Labeling process. From the time-series graph (top), the user chooses a portion of the data. Based on Euclidean distance, all windows that match below a threshold are labeled with the same color in both graphs. In this example, the selected cluster is corresponding to the Descent Phase of Dive. [source]

Visualization and Interaction Techniques

It is not absurd if I say one of the most important parts of developing machine learning algorithms is to visualize it. Whenever you develop or propose a model for a certain aim in any industry, you need to show that your model is working and provides good results; Not just provide some metrics/numbers such as MSE (Mean-Squared-Error) or etc. So, let’s see how it is in this case:

Figure 5. The overview of the system (A) Time-series graph for raw data (multivariate time-series). (B) Connected scatter plot for the time-series data after applying the proposed approach which reveals six clusters and transitions between them. The DCAE following by a dimension reduction technique (UMAP) is applied on the data that is collected from a Cormorant bird using a sensor. Various colors reveals various clusters were: cluster A, B, C, D, E, and F are respectively, Descent Phase of Dive, Bottom Phase of Dive, Surface Swimming, Ascent Phase of Dive, Flight, and the beginning and the end of the dataset. (C) Zooming in an area of interest (cluster A), (D) Drawing time-series graph for the selected point in connected scatter plot, (E) Zooming of the transitions (connected lines) from cluster C to cluster A, and (F) X, Y, and Z acceleration during a single cormorant dive where the changing in posture during descent, swimming, and ascent are obvious as shifts in the time-series graph. [source]

Figure 5 is in fact widespread mantra ‘overview first, zoom and filter, and then details-on-demand’ by Professor Ben Shneiderman in his paper. So, let’s dive into each section of this overview.

Figure 5A

This is just a display of the original data provided on the time axis.

Figure 5B

Figure 5B is used to make navigation techniques simpler on time series data. This figure shows the transformed data points after reducing dimension by any of the mentioned methods.

In this section, before we label data points one by one, they are clustered and have the same colors and concentrated in certain areas. Each data point links to the previous point (inner) and the next point (outer) as a mark for the flow of time.

Figure 5C,D

Section C is showing the connected scatter data points which seems simple at first look but it has very specific functions in this approach that can see in section D. Here, we can select and zoom to facilitate fast and interactive exploration in large datasets.

Figure 5E

In addition to what we saw in section B that each cluster is colored by some colors, there are some data that can be displayed as in Figure 5E. These data are not included in clusters but are helpful in tracking the transition between data points and clusters.

There are two case study that discussed in this research, but I think demonstrating them make this article long. So, I invite you to see this youtube video by Prof. Mark W. Jones.

Reference

1. Ali, M., et al., TimeCluster: dimension reduction applied to temporal data for visual analytics. The Visual Computer, 2019. 35(6): p. 1013–1026.

Please note that this post is for my research in the future to look back and review the materials on this topic.

If you found any errors, please let me know. Meanwhile, you can contact me in Twitter here or LinkedIn here. Finally, if you have found this article interesting and useful, you can follow me on medium to reach more articles from me