PaperlayerView exact revision on arXiv

Source-linked AI summary

Model-based clustering and segmentation of time series with changes in regime

Allou Samé, Faicel Chamroukhi, Gérard Govaert, Patrice Aknin

arXiv:1312.6967v1stat.MEcs.LGmath.STstat.MLstat.TH

TL;DR

Rail-switch power-consumption series change regime, while conventional regression mixtures use constant cluster dynamics. The paper models each cluster with hidden-process regressions and logistic regime transitions; results report efficient clustering on simulated and railway data.

  • Problem

    Rail-switching power-consumption series undergo regime changes, whereas existing regression-mixture approaches use constant dynamics within each cluster.

    Source: §1 · p. 2

  • Method

    The model represents each cluster with a hidden-process regression whose polynomial coefficients vary by regime and whose transitions are modeled with logistic functions.

    Source: §1 · p. 2, §3.2 · p. 4

  • Results

    The approach is reported as efficient for clustering univariate time series with regime changes in both simulated data and a real-world railway application.

    Source: §5 · p. 16

  • Takeaways & Limitations

    The approach provides both a time-series partition and a segmentation into shared regime changes, with BIC used to select cluster and segment counts and regression order.

    Source: §5 · p. 15

    The model assumes the time series are independently generated from a global mixture.

    Source: §3.1 · p. 4

Abstract

from arXiv · show

Mixture model-based clustering, usually applied to multidimensional data, has become a popular approach in many data analysis problems, both for its good statistical properties and for the simplicity of implementation of the Expectation-Maximization (EM) algorithm. Within the context of a railway application, this paper introduces a novel mixture model for dealing with time series that are subject to changes in regime. The proposed approach consists in modeling each cluster by a regression model in which the polynomial coefficients vary according to a discrete hidden process. In particular, this approach makes use of logistic functions to model the (smooth or abrupt) transitions between regimes. The model parameters are estimated by the maximum likelihood method solved by an Expectation-Maximization algorithm. The proposed approach can also be regarded as a clustering approach which operates by finding groups of time series having common changes in regime. In addition to providing a time series partition, it therefore provides a time series segmentation. The problem of selecting the optimal numbers of clusters and segments is solved by means of the Bayesian Information Criterion (BIC). The proposed approach is shown to be efficient using a variety of simulated time series and real-world time series of electrical power consumption from rail switching operations.

1 Introduction

Rail-switch diagnosis begins by clustering electrical-power time series from switching operations, whose successive mechanical movements produce changes in regime. The paper extends regression-mixture clustering to model those changes within clusters.

1 Introduction

  • Electrical-power time series from rail-switching operations are clustered as a preliminary step toward diagnosing problems in rail switches.The traces come from different switching operations and are also called longitudinal data, signals, or curves in other contexts.Source: §1 · p. 2
  • Existing time-series mixture approaches use a constant dynamic within each cluster, so their regression or autoregression coefficients do not vary over time.The cited approaches include regression mixtures, random-effect regression mixtures, and ARMA methods combined with EM.Source: §1 · p. 2
  • The proposed extension gives each cluster a hidden-process regression model whose polynomial coefficients vary across regimes, with logistic functions modeling smooth or abrupt transitions.It is presented as an extension of a regression model previously proposed for regime changes.Source: §1 · p. 2
  • The paper presents the model and its EM parameter estimation, then evaluates it on simulated and railway time series.The EM algorithm is cited as [6].Source: §1 · p. 2
  • The observed data comprise a sample of time series on a fixed time grid, with an unobserved cluster label for each series.Each series is represented as a vector of real-valued observations.Source: §1 · p. 2

2 Regression mixture model for time series clustering

This section recalls regression-mixture clustering, in which each cluster has a polynomial mean curve, and describes maximum-likelihood fitting and posterior-probability assignment.

2.1 Definition of the regression mixture model

  • Each regression-mixture component represents a series with a polynomial mean curve parameterized by regression coefficients and a noise variance.The model is formulated for time-series clustering.Source: §2.1 · p. 3

2.2 Fitting the model

  • The mixture parameters are estimated by maximizing the conditional log-likelihood with the EM algorithm.The sample is assumed independent; EM is attributed to Dempster, Laird and Rubin.Source: §2.2 · p. 3
  • After fitting, each series is assigned to the cluster with the highest posterior probability.Source: §2.2 · p. 3

3 Clustering time series with changes in regime

The proposed clustering model uses a mixture of cluster-specific regression components to represent series with changing regimes. Within each cluster, hidden component labels and logistic weights describe the time-varying regime assignments.

3.1 The global mixture model

  • Series are assumed to be independently generated from a global mixture whose proportions and component densities define the clusters.The proposed model differs from the regression mixture by how it defines each component density.Source: §3.1 · p. 4

3.2 Definition of the mixture components

  • Within cluster k, a hidden process assigns observations to L polynomial regressions, with logistic time-dependent weights governing regime membership.The component regression parameters include a coefficient vector and noise standard deviation; the logistic weights ensure smooth transitions between regimes.Source: §3.2 · p. 4

3.3 A cluster-segmentation model

The model produces a segmentation of the time series within each cluster, with segments that are contiguous parts of the time grid. Its parameters are estimated by maximizing the conditional log-likelihood with EM.

3.3 A cluster-segmentation model

  • Each cluster’s time series are segmented into contiguous parts of the time grid.The model’s latent structure separates clustering into K clusters from segmentation into L segments within each cluster.Source: §3.3 · p. 5, Figure 1 · p. 5

3.4 Parameter estimation via the EM algorithm

  • The model parameters are estimated by maximizing the conditional log-likelihood with the EM algorithm.EM alternates between steps until convergence, using cluster membership and sub-regression assignments as complete data.Source: §3.4 · p. 6

E-Step (Expectation)

The E-step evaluates expected complete-data log-likelihood using posterior probabilities for cluster and sub-regression assignments. The M-step maximizes that quantity by separately updating model parameter groups.

E-Step (Expectation)

  • The E-step evaluates the expected complete-data log-likelihood conditional on observed data and the current parameters.Its posterior probabilities represent cluster membership and assignment to a cluster’s sub-regression model.Source: E-Step (Expectation) · pp. 6–7

M-Step (Maximization)

  • The M-step maximizes Q by separately optimizing Q1, Q2, and Q3.The mixture proportions are updated by maximizing Q1 under a constraint.Source: M-Step (Maximization) · p. 7
  • The transition parameters αk are estimated by solving K weighted logistic regression problems with IRLS.IRLS is described as equivalent to a Newton–Raphson algorithm.Source: M-Step (Maximization) · pp. 7–8
  • The regression coefficients βkℓ are updated by analytically solving K × L weighted least-squares problems.Source: M-Step (Maximization) · p. 8

Common segmentation for all clusters

The model permits constraints that share segmentation parameters across clusters or share regression variances within or across clusters.

Common segmentation for all clusters

Common variance for regression models from the same cluster

Common variance for all regression models

3.5 Time series clustering, approximation and segmentation

The fitted model yields cluster assignments, cluster mean-series approximations, and within-cluster segmentations. BIC is used to select the number of clusters, segments, and polynomial degree.

3.5 Time series clustering, approximation and segmentation

  • The fitted parameters yield a time-series partition by assigning each series to its most probable cluster.The cluster mean series can also be approximated from the estimated parameters.Source: §3.5 · p. 9
  • Estimated parameters also yield a segmentation for time series originating from each cluster.The segmentation is derived from the estimated parameters using the specified segment definition.Source: §3.5 · p. 9

3.6 Assessing the number of clusters, segments and the regression order

  • BIC assesses candidate values of K, L, and polynomial degree p while accounting for the model’s free parameters.The free parameters include mixture proportions, logistic-function parameters, polynomial coefficients, and variances.Source: §3.6 · pp. 9–10
  • The selected solution is the tested (K, L, p) triplet with the highest BIC.The procedure runs EM over specified ranges of cluster counts, segment counts, and polynomial degrees.Source: §3.6 · p. 10

4 Experimental study

The experiments assess clustering accuracy on simulated series and railway power-consumption data, comparing the proposed EM algorithm with standard regression mixtures. The proposed approach performs better overall in the reported simulated and real-world comparisons.

4 Experimental study

  • The evaluation compares misclassification percentage and intra-cluster inertia on simulated and railway time series.The simulated sets contained 50 series of length 60, arranged into two equally sized clusters with differing mean-curve structures.Source: §4 · p. 10, §4.1.2 · p. 11

4.1.1 Simulation protocol and algorithms tuning

  • BIC most often selected (K, L, p) = (2, 3, 3) for the proposed approach and (K, p) = (2, 10) for regression mixtures.The selection rates were computed across 25 randomly generated sets of 50 series.Source: §4.1.1 · p. 10, §4.1.2 · p. 12

4.1.2 Comparison between the proposed model and the standard regression mixture

  • Across 25 simulated samples, the proposed algorithm's overall performance is better than the standard regression-mixture EM algorithm.The comparison uses the BIC-selected settings; Table 2 reports misclassification percentages and intra-cluster inertia.Source: Table 2 · p. 12, §4.1.2 · p. 12

4.2 Experiments using real world data

  • On railway data, the proposed regression approach has the smallest intra-cluster error and misclassification rate among the compared approaches.The proposed model used L = 5 regression components and polynomial degree p = 3; Table 3 reports the error comparison.Source: §4.2 · p. 14, Table 3 · p. 15

5 Conclusion

The proposed approach efficiently clusters univariate time series with regime changes in simulated and real-world data. It models clusters through time-varying polynomial coefficients and uses BIC to select model orders.

5 Conclusion

  • Each cluster is modeled by a regression whose polynomial coefficients vary over time according to a discrete hidden process, with logistic functions controlling regime transitions.Transitions may be smooth or abrupt.Source: §5 · p. 15
  • A dedicated EM algorithm solves maximum-likelihood estimation of the model parameters.Source: §5 · p. 15
  • BIC determines the numbers of clusters and segments, as well as the regression order.Source: §5 · pp. 15–16
  • The approach groups time series that share common changes in regime, providing both clustering and segmentation.Source: §5 · p. 15
  • The approach is reported as efficient for clustering univariate time series with regime changes in simulated and real-world experiments.The real-world application concerns electrical power consumption from rail switching operations.Source: §5 · p. 16

A Convexity of the set Ekℓ

For each regime label, the set E_kℓ contains times when its probability is maximal among the regime probabilities. The section establishes that this set is convex.

A Convexity of the set Ekℓ

Loading 1312.6967v1…