Unsupervised clustering of series using dynamic programming and neural processes

Karthigan Sinnathamby, Chang-Yu Hou, Lalitha Venkataramanan, Vasileios-Marios Gkortsas, François FleuretarXiv 2021 · OpenReview

TL;DR

This paper introduces a novel unsupervised clustering method for time-series data by integrating dynamic programming with neural processes. This approach allows for more flexible and data-driven modeling of cluster characteristics, outperforming previous methods that relied on fixed physics models, especially in complex scenarios.

What Problem Does This Paper Address?

Clustering time-series data is crucial for identifying patterns and grouping similar sequences. Traditional methods often rely on predefined models (like physics-based equations) to define what makes data points "coherent" within a cluster. However, this has limitations: multiple models might fit the same data, or the underlying model might be unknown. This paper addresses the challenge of creating a more general and data-driven framework for unsupervised clustering that can adapt to these uncertainties by learning an approximate model of cluster characteristics.

Methods

The core of this work is the integration of Neural Processes (NPs), specifically Attentive Neural Processes (ANPs), with an existing dynamic programming clustering algorithm.

  • Dynamic Programming Clustering: The foundation is an algorithm that segments and clusters time-series data based on predefined constraints (number of clusters, transitions, minimum block size). It assumes that each cluster can be characterized by a specific model and that a function exists to measure a point's affiliation to a cluster.
  • Neural Processes (NPs): NPs are a type of deep learning model capable of learning a distribution over functions. They can predict the distribution of an arbitrary target point given a set of "context" points. This makes them ideal for modeling stochastic processes.
  • Integration: The key innovation is using NPs to learn the cluster characterization and affiliation functions. Instead of relying on explicit, predefined physics models, the NPs learn an approximate model from the data. The context points (data points within a cluster) serve as the signature for cluster characterization, and the likelihood of predicting target points from these context points is used for cluster affiliation. This allows the framework to handle situations where the underlying model is unknown or ambiguous.

Datasets

The paper uses simulated datasets generated from three known physics models for petrophysical measurements:

  • Waxman-Smits (WS) equation
  • Sen-Goode-Sibbit (SGS) equation
  • Archie's equation

These models are used to create multi-variate time-series data with multiple blocks belonging to different clusters. The data is generated with realistic noise levels, mimicking measurement and interpretation precision. The paper does not introduce new benchmark datasets but rather uses simulated data based on established physical models to test the proposed method.

Key Insights and Ideas

  • Data-Driven Cluster Characterization: NPs enable a shift from rigid, predefined models to flexible, learned representations of cluster characteristics. This is crucial when the true underlying physics is unknown or complex.
  • Handling Model Ambiguity: By learning an approximate model, the method can effectively deal with scenarios where multiple models might describe the data, or where no explicit model is readily available.
  • Improved Clustering Performance: The ANP-enhanced clustering algorithm demonstrates superior or comparable performance (measured by Adjusted Rand Index - ARI) compared to using a fixed WS equation, especially in complex datasets.
  • NLL as a More Informative Metric: Using the Negative Log-Likelihood (NLL) from NPs for cluster affiliation provides a more nuanced measure than traditional L2 loss, as it accounts for both the mean and variance of predictions. This can lead to more heterogeneous cost scatter plots but potentially more robust clustering.

Key Results

The paper presents results on seven testing examples, including variations of WS and SGS equations.

  • For datasets WS-1, WS-2, WS-3, WS-3-smooth, and SGS-2, the "lowest cost" ANP prediction achieved a better ARI than the WS-based method.
  • The "most common" ANP pattern also provided comparable results to the WS-based clustering.
  • In several cases (e.g., WS-1, SGS-2), the "lowest cost" ANP prediction resulted in near-perfect ARI scores, indicating highly accurate clustering.
  • The ANP-based method generally achieved lower costs (NLL) compared to the WS-based method's MSE, reflecting the richer probabilistic modeling.

Limitations and Future Work

  • Heterogeneity in Cost Scatter Plots: The authors note that the cost scatter plots for the NP method are more heterogeneous than those using a fixed WS equation. This is attributed to the NLL metric incorporating variance, which can increase with smaller blocks and higher N/C values.
  • Local Minima: The algorithm might get stuck in local minima, yielding low NLL but not necessarily the globally lowest achievable NLL.
  • Best Prediction Not Guaranteed: While the "lowest cost" ANP prediction often yields the best results, the authors acknowledge they haven't proven this is always the case. They suggest considering both the "most common" and "lowest cost" predictions, along with external information, for final decisions.
  • Future Work: The paper suggests that for pairs (N,C) with small values, the behavior of the NP method might be similar to the WS method. However, for higher N and C, the NP method's behavior becomes more disparate, opening avenues for further investigation into these regimes. The authors also propose that the NP method offers a way to represent equations in an aggregated manner, which could be further explored.

Summary updated

Abstract

Following the work of arXiv:2101.09512, we are interested in clustering a given multi-variate series in an unsupervised manner. We would like to segment and cluster the series such that the resulting blocks present in each cluster are coherent with respect to a predefined model structure (e.g. a physics model with a functional form defined by a number of parameters). However, such approach might have its limitation, partly because there may exist multiple models that describe the same data, and partly because the exact model behind the data may not immediately known. Hence, it is useful to establish a general framework that enables the integration of plausible models and also accommodates data-driven approach into one approximated model to assist the clustering task. Hence, in this work, we investigate the use of neural processes to build the approximated model while yielding the same assumptions required by the algorithm presented in arXiv:2101.09512.
BibTeX
@misc{sinnathamby2021unsupervised,
  author = {Karthigan Sinnathamby and Chang-Yu Hou and Lalitha Venkataramanan and Vasileios-Marios Gkortsas and François Fleuret},
  title = {{Unsupervised clustering of series using dynamic programming and neural processes}},
  year = {2021},
  eprint = {2101.10983},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.10983},
}

Loading related content...

Figure