Time Series Clustering via Community Detection in Networks

Leonardo N. Ferreira; Liang Zhao

Source-linked AI summary

Time Series Clustering via Community Detection in Networks

Leonardo N. Ferreira, Liang Zhao

arXiv:1508.04757v1Aug 19, 2015stat.MLcs.LGcs.SI

TL;DR

Time-series clustering needs to capture global relationships that are generally unknown in the original series representation. This paper transforms series into a network and applies community detection; experiments report better results than other clustering algorithms in most tested datasets, alongside the ability to detect shape patterns despite shifts or amplitude variations.

Problem
In original time-series form, neighboring-sample relationships are visible, but long-distance global relationships generally remain unknown.
Source: §1 · p. 2
Method
The method normalizes series, calculates pairwise distances, connects each series to its most similar ones in a network, and uses community detection to form clusters.
Source: §1 · p. 2
Results
The network-based method outperformed other clustering algorithms in most tested datasets, and ε-NN with DTW and multilevel community detection achieved the best results among the combinations studied.
Source: §5 · p. 20
Takeaways & Limitations
The method detects shape patterns that other studied techniques miss and groups similar patterns despite time shifts or amplitude variations.
Source: §1 · p. 3
The evaluation used Rand index, and searching over k and ε can be too time-consuming for many real datasets.
Source: §5 · p. 20

Abstract

from arXiv · show

In this paper, we propose a technique for time series clustering using community detection in complex networks. Firstly, we present a method to transform a set of time series into a network using different distance functions, where each time series is represented by a vertex and the most similar ones are connected. Then, we apply community detection algorithms to identify groups of strongly connected vertices (called a community) and, consequently, identify time series clusters. Still in this paper, we make a comprehensive analysis on the influence of various combinations of time series distance functions, network generation methods and community detection techniques on clustering results. Experimental study shows that the proposed network-based approach achieves better results than various classic or up-to-date clustering techniques under consideration. Statistical tests confirm that the proposed method outperforms some classic clustering algorithms, such as $k$-medoids, diana, median-linkage and centroid-linkage in various data sets. Interestingly, the proposed method can effectively detect shape patterns presented in time series due to the topological structure of the underlying network constructed in the clustering process. At the same time, other techniques fail to identify such patterns. Moreover, the proposed method is robust enough to group time series presenting similar pattern but with time shifts and/or amplitude variations. In summary, the main point of the proposed method is the transformation of time series from time-space domain to topological domain. Therefore, we hope that our approach contributes not only for time series clustering, but also for general time series analysis tasks.

1. Introduction

The paper proposes clustering time series by representing them as networks and detecting communities, addressing the need to capture relationships beyond neighboring samples. Its experiments report better results than other clustering algorithms under study, while the network structure also detects shape patterns and groups similar patterns despite time shifts or amplitude variations.

1. Introduction

Time-series clustering seeks both effectiveness and efficiency, and community detection identifies groups of densely connected vertices with sparse connections between groups.The paper situates its approach among methods that either adapt data representations or modify clustering algorithms for time series.Source: §1 · p. 2
Time-series representations make neighboring-sample relationships visible but generally leave long-distance global relationships unknown, while networks can characterize relationships among data samples.The introduction contrasts distance-based clustering, which produces clusters of shapes determined by its distance function, with network-based methods that can capture arbitrary cluster shapes.Source: §1 · p. 2
The proposed four-step approach normalizes series, calculates pairwise distances, connects each series to its most similar neighbors in a network, and treats detected communities as clusters.The paper frames this as transforming time series from the time-space domain to the topological domain, with potential use beyond clustering.Source: §1 · pp. 2–3
Experimental results and statistical tests show that the network-based approach achieves better results than other time-series clustering algorithms.The introduction also reports that it can detect shape patterns that other studied techniques fail to identify.Source: §1 · p. 3
The method detects shape patterns through the network's topological structure and groups similar patterns despite time shifts or amplitude variations.Other techniques studied in the paper fail to identify the described shape patterns.Source: §1 · p. 3

2. Background and related works

The background reviews time-series distance measures, clustering approaches, and network community detection as foundations for the proposed clustering study.

2. Background and related works

The background identifies distance measures, clustering algorithms, and network community detection as the three components reviewed for this study.Source: §2 · p. 3

2.1. Time series distance measures

Time-series distances are grouped into shape-based, edit-based, feature-based, and structure-based categories.The review assumes discrete time and defines a series as an ordered sequence of real values.Source: §2.1 · p. 3

2.1.1. Shaped based distance measures

Lp norms compare raw series values using fixed pairs; they are intuitive, parameter-free, and linear-time, but sensitive to noise and misalignment.DTW aligns series by a shortest warping path; STS and DISSIM address different sampling rates, while CID adjusts Euclidean distance for series complexity. Figure 1 contrasts fixed one-to-one comparisons with elastic one-to-many alignment.Source: §2.1.1 · p. 4, Figure 1 · p. 4

2.1.2. Edit Based distance measures

Edit-based distances count the minimum insertions, deletions, and substitutions needed to transform one series into another.LCSS permits time warping and gaps, using ε for point matching and δ for warping.Source: §2.1.2 · p. 4

2.1.3. Feature based distance measures

Feature-based distances compare extracted features rather than raw series values.Examples include wavelet coefficients and INTPER, which uses integrated periodograms followed by Pearson correlation.Source: §2.1.3 · p. 5

2.1.4. Structure based distance measures

Structure-based measures represent higher-level series structure using models such as HMM or ARMA, or by comparing compression ratios.Model-based similarity can use the probability of one series under another series’ model.Source: §2.1.4 · p. 5

2.2. Time series clustering

Prior clustering methods either extract features before conventional clustering or adapt clustering algorithms to time series; prior network clustering uses DTW and high-degree candidate vertices.The paper presents community detection as a network-based approach and reports that simulations show it can identify arbitrary-shaped clusters.Source: §2.2 · pp. 5–6

2.3. Community detection in networks

k-NN and ε-NN networks connect samples by similarity, while communities are dense vertex groups with sparse links between groups.The review describes modularity-based Fast Greedy and Multilevel methods, random-walk-based Walktrap, and label-propagation and Infomap strategies.Source: §2.3 · p. 7

3. Description of the proposed method

The method turns normalized time series into a similarity network and uses community detection to produce clusters. Its stated complexity is O(n^2t), with a nearest-neighbor construction improvement described as reducing it to O(nt).

3. Description of the proposed method

The four-stage workflow normalizes series, calculates distances, connects similar series in a network, and detects communities as clusters.Each time series is a vertex; distance-based links connect similar series, and community detection groups densely connected vertices.Source: §3 · p. 8, Figure 2 · p. 8
Normalization scales the dataset, pairwise distances form matrix D, and k-NN or ε-NN construction converts D into a network before community detection.The authors note that distance choice, network construction, and community-detection choice affect clustering results.Source: §3 · p. 8
O(n^2t) is the stated overall complexity for n series of length t, with pairwise distance calculation as the dominant cost.Z-score normalization takes O(nt), and the cited community-detection algorithms are usually below quadratic or can be linear.Source: §3 · pp. 8–9
A divide-and-conquer k-NN graph construction from Ref. is described as reducing the method’s complexity to O(nt).Source: §3 · p. 9

4. Experimental evaluation

Experiments compare network-based clustering across datasets, distance measures, network constructions, and community detectors. The method outperforms several rival algorithms, while tests on time-shifted and shape-pattern series illustrate its performance on those cases.

4.1. Experiment settings

Across 45 UCR time-series datasets, experiments assess combinations of distance measures, ε-NN or k-NN network construction, and community-detection algorithms, comparing results with Rand Index, measuring percentage of correct algorithm decisions.For k-NN, best RI is found by varying k from 1 to n −1; for ε-NN, ε ranges from min(D) to max(D) in 100 steps of (max(D) − min(D))/100, with the same procedure for rival methods.Source: §4.1 · pp. 9–10

4.2. Network construction influence

ε-NN achieves larger Rand indices than k-NN (p-value ≤.0001), while intermediate k or ε values usually avoid fragmented or fully connected networks.In the coffee example, k = 7 gives RI=1, versus RI=0.64 at k = 1 and RI=0.48 at k = 27.Source: §4.2 · pp. 11–12, Figure 4 · p. 11, Table 3 · p. 12

4.3. Time series distance function influence

DTW has the best results for both network constructions, but is not statistically distinguishable as better; L∞, STS, and INTPER perform worse.Distance measures differ significantly for both constructions (Friedman test, p-value ≤.0001).Source: Figure 5 · p. 12, §4.3 · pp. 12–13

4.4. Community detection algorithm influence

Walktrap performs best with k-NN, while Fast Greedy and multilevel are statistically similar and outperform the other tested algorithms with ε-NN.The five algorithms differ significantly for both network constructions (Friedman test, p-value ≤.0001).Source: Figure 6 · p. 13, §4.4 · p. 13

4.5. Comparison to rival Methods

Statistical tests favor community detection over k-medoids (PAM), diana, median-linkage, centroid-linkage, Zhang’s method, Maharaj’s method, and PDC (p-values ≤.02).The tests do not establish statistical superiority over complete-linkage, single-linkage, or average-linkage (p-values ≤.32); the selected configuration uses multilevel detection, ε-NN, and DTW.Source: §4.5 · pp. 14–15, Figure 7 · p. 15

4.6. Detecting time series clusters with time-shifts

For the CBF data, ε-NN (ε = 58.87) with DTW and multilevel community detection gives RI = 0.96, versus RI = 0.91 for complete linkage with DTW.It forms 3 communities and correctly finds all clusters except the time series labeled “3”.Source: §4.6 · p. 16, Figure 9 · p. 18

4.7. Efficiency to detect shape patterns

On the two-pattern dataset, ε-NN with DTW and multilevel detection correctly clusters all 1000 series (RI = 1), versus RI = 0.97 for single linkage with DTW.The four communities correspond to the four groups defined by the order of upward and downward steps.Source: Figure 11 · p. 19, Figure 10 · p. 19, §4.7 · p. 20

5. Conclusion

The method outperformed rival algorithms on most tested datasets and grouped series with time shifts and amplitude variations. The authors identify ε-NN with DTW and multilevel community detection as the best combination among those studied, while noting scope and evaluation constraints.

Among tested combinations, ε-NN with DTW and multilevel community detection achieved the best results; intermediate k and ε values also performed better.Source: §5 · p. 20
The method outperformed rival algorithms on most tested datasets and grouped series with time shifts and amplitude variations.Source: §5 · p. 20
The approach can be adapted by changing network construction, distance, or community detection, and general improvements to these subroutines also apply.Source: §5 · p. 20
The method was developed for univariate series, while multivariate clustering would require a suitable distance function or a clustering method for multiple variables.One proposed route is to cluster each variable separately and merge the results using criteria.Source: §5 · p. 20
Accuracy comparisons used the rand index, and searching k and ε for the best values may be too time-consuming for many real datasets.The authors propose evaluating other indexes and developing automatic parameter-selection and faster network-construction strategies.Source: §5 · p. 20

Appendix A. Data Set Description

The experiments used 45 time-series datasets from the UCR repository and retained only their training sets. Because dataset authors supplied the labels, the experiments assume those labels are correct.

The experiments used 45 real and synthetic time-series datasets from the UCR repository, retaining training sets and discarding test sets.Source: Appendix A · p. 22
Dataset labels were defined by the contributing authors rather than UCR, so the experiments assume those labels are correct.Source: Appendix A · p. 22
Table A.8 describes the UCR time-series datasets used in the experiments.Source: Table A.8 · p. 23