Solved – How to cluster non-aligned time-series with different length

clusteringtime series

I am trying to cluster dozens of time-series sampled every 30min, and which cover the period mid2016 – mid2020. Most of them have very nice "patterns", others may have missing values for a given period (eg: one whole year, severals months, etc) or be more "chaotic" (sudden variations).

Here I display some of the time-series I am handling:

If we look at a closer level (eg: weekly), it is possible to see some seasonal patterns as the graphs below show (2020/1/1 to 2020/1/8):

Ideally, I would like to make clusters where time-series share similar "shapes in time" (eg: similar shape based on time –> peaks on the morning and evening, almost null values on weekends or holidays, etc) but also, if possible, yearly seasonality when enough data are available.

I tried to apply the commonly used DTW measure + hierarchical clustering (ward linkage), but because of the number of points I have per time-series (even after doing 1hr resampling), it took too much time and I was quite disappointed with the results (though I applied on data with few amount of preprocessing).

So what I am facing is:

I would like to extract the "nicest" part of each time series, but if I do so, they will be misaligned (do not start at the same time point) and they will be of different length.
Thus, I am quite confused to the preprocessing steps I should employ.

I would be glad if you have some advice about preprocessing / distance / clustering algorithm that I should I apply to perform clustering of these time series.

Best Answer

Preprocessing that results in misalignment or different lengths is not necessarily a problem. Have you considered Time Series Clustering - a decade review (Information Systems 53, 2015), in which Aghabozorgi et al review 38 algorithms for clustering whole time-series? See the rightmost column of Table 4 (pages 27-28) for their notes describing attributes of each of the approaches.

Related Solutions

Solved – How to cluster time series

A) Spend a lot of time on preprocessing the data. Preprocessing is 90% of your job.

B) Choose an appropriate similarity measure for the time series. For example, threshold crossing distance may be a good choice here. You probably won't desire dynamic time warping distance, unless you have different time zones. Threshold crossing may be more appropriate to detect temporal patterns, while not paying attention the the actual magnitude (which will likely be very different from company to company).

C) Cluster the resulting dissimlarity matrix using methods such as hierarchical clustering or DBSCAN that can work with arbitrary distance functions.

Solved – Cluster Sequences of data with different length

One way to do it (among many other ways) is to treat the element of your sequence as a word. In other words, if your assume your list is a sentence, then you can extract ngrams.

import nltk
from nltk import ngrams
a = [1, 15, 1, 1, 13, 14]
b = [1, 1, 1, 1, 12, 1, 7, 11, 9, 11, 7, 11, 7, 11, 7, 4, 7, 7, 14, 15, 9, 2]
c = [13, 1, 13, 15, 13, 2, 9, 2, 9, 2, 2, 2, 2, 2, 2, 2]
d = [1, 2, 9, 1, 6, 10, 6, 1, 6, 10, 14, 3, 10]

bb = list()
bb.append(str(','.join(str(e) for e in ['x' + str(e) for e in a])))
bb.append(str(','.join(str(e) for e in ['x' + str(e) for e in b])))
bb.append(str(','.join(str(e) for e in ['x' + str(e) for e in c])))
bb.append(str(','.join(str(e) for e in ['x' + str(e) for e in d])))

I added the x, because seems CountVectorizer neglects single numbers/letters. Lets do word count - alternatively you can go ahead with ngrams (read the sklearn documentation here ) as well

from sklearn.feature_extraction.text import CountVectorizer
vectorizer = CountVectorizer()
X = vectorizer.fit_transform(bb)
X.toarray()

The out put looks like this

array([[3, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0],
       [5, 0, 4, 1, 0, 1, 1, 1, 0, 1, 0, 6, 2],
       [1, 0, 0, 0, 3, 0, 1, 9, 0, 0, 0, 0, 2],
       [3, 3, 0, 0, 0, 1, 0, 1, 1, 0, 3, 0, 1]])

basically columns corresponds to words which are

print(vectorizer.get_feature_names())

['x1', 'x10', 'x11', 'x12', 'x13', 'x14', 'x15', 'x2', 'x3', 'x4', 'x6', 'x7', 'x9']

and rows are your samples.

Now that you have a feature matrix, you can go ahead and do clustering, for example kmeans

from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
kmeans.labels_

which results

array([0, 1, 0, 0], dtype=int32)

Best Answer

Related Solutions

Solved – How to cluster time series

Solved – Cluster Sequences of data with different length

Related Question