A novel framework for joint sparse clustering and alignment of functional data

Valeria VitelliJournal of Nonparametric Statistics 2019

TL;DR

This paper introduces a novel framework for analyzing functional data (data that evolves over time or another continuous variable) by simultaneously clustering curves, aligning them to account for phase shifts, and identifying the most relevant parts of their domains for clustering. This unified approach addresses limitations of existing methods that often handle these aspects separately, leading to more robust and interpretable results, especially when differences between groups are subtle or localized.

What Problem Does This Paper Address?

Functional data analysis (FDA) deals with data that are functions themselves, like time series or growth curves. A common challenge in FDA is functional clustering, where we want to group similar curves together. However, two major issues complicate this:

  1. Misalignment: Curves might be shifted in time or phase, meaning the same event occurs at different points along the x-axis for different curves. If not accounted for, this misalignment can obscure true similarities and lead to incorrect clustering.
  2. Sparsity/Domain Selection: Often, the important differences between functional groups are not spread across the entire domain but are localized to specific regions. Traditional clustering methods might struggle to identify these localized differences, especially if they are subtle.

Existing methods often address these issues in isolation. For instance, some methods first align curves and then cluster them, or vice-versa. This paper argues that jointly addressing clustering, alignment, and domain selection within a single framework is more effective, particularly when dealing with subtle, localized differences.

Methods

The core of the paper is a novel variational framework that unifies three tasks:

  • Joint Clustering and Alignment: The authors propose a method that simultaneously determines cluster assignments and finds optimal "warping functions" for each curve. These warping functions essentially shift and stretch the x-axis of each curve to align them, effectively decoupling phase variability from amplitude variability. This is framed as an optimization problem to maximize a measure of between-cluster similarity.
  • Sparse Domain Selection: To address the issue of localized differences, they introduce a weighting function w(x). This function assigns importance to different parts of the domain. The optimization problem is modified to maximize the weighted between-cluster similarity. Crucially, a sparsity constraint is imposed on w(x), forcing it to be zero in regions where the curves do not differ significantly between clusters. This effectively "selects" the most informative parts of the domain for clustering.
  • Unified Variational Problem: The paper formulates a single optimization problem that jointly solves for the cluster assignments, the warping functions, and the weighting function. An iterative algorithm, inspired by K-means, is proposed to solve this complex problem. This algorithm alternates between updating the warping functions, updating the cluster assignments, and updating the weighting function.

The authors also discuss how this framework can be adapted to different functional spaces (e.g., L² or H¹) and different similarity/distance measures, making it flexible for various data types.

Datasets

The paper evaluates the proposed method on:

  • Simulated Data: Two simulation studies are presented to test the method's performance under controlled conditions, varying levels of misalignment, and different cluster structures.
  • Berkeley Growth Study Data: A well-known dataset of 93 children's growth curves, used to investigate gender-related patterns and growth spurts.
  • AneuRisk65 Dataset: A dataset of three-dimensional curves representing internal carotid artery centerlines from 65 subjects, used to study potential grouping structures related to cerebral morphology and aneurysm position.

Key Insights and Ideas

  • Joint Optimization is Key: The paper strongly advocates for a unified approach. Separating alignment and clustering can lead to suboptimal results, especially when differences are localized.
  • Sparsity as a Feature Selector: The weighting function w(x) acts as an automatic feature selector, highlighting the specific regions of the functional domain that are most discriminative for clustering.
  • Decoupling Phase and Amplitude: The framework effectively separates variations due to shifts in timing (phase) from variations in the actual shape or magnitude (amplitude), leading to clearer insights into the underlying data structure.
  • Flexibility in Functional Measures: The ability to use different similarity metrics (beyond standard L² distance) is crucial for handling diverse functional data types, such as the AneuRisk65 data where derivative-based measures are more appropriate.

Key Results

  • Improved Clustering Accuracy: In simulations, the proposed sparse KMA method demonstrated better performance in selecting the correct number of clusters and achieving lower misclassification rates compared to standard K-means alignment (KMA), especially when cluster differences were localized.
  • Meaningful Domain Selection: The estimated weighting functions w(x) consistently highlighted biologically or morphologically relevant regions in the real-world datasets (e.g., mid-spurt in growth, specific regions of the carotid artery).
  • Validation of Previous Findings: The application to the Berkeley Growth Study and AneuRisk65 datasets confirmed and extended previous findings, providing a more unified and interpretable understanding of the data. For instance, it confirmed gender stratification in phase variability for growth curves and identified relevant regions for clustering in ICA centerlines.
  • Computational Efficiency: The iterative algorithm showed good convergence properties and reasonable computation times.

Limitations and Future Work

  • Parameter Tuning: The method still requires manual tuning of the sparsity parameter m. The authors suggest future work on developing automatic strategies for this, potentially adapting GAP statistics or using sufficient statistics.
  • Trade-off between Alignment and Sparsity: There appears to be a trade-off where methods more focused on alignment might achieve better phase variability capture but at the cost of template estimation, while sparse methods excel at template estimation but might leave some phase variation. Further research is needed to understand this relationship.
  • Generalization to K=1: The current framework does not explicitly handle the case of K=1 group. Future work could explore how sparse clustering and alignment might degenerate into pure alignment in this scenario.
  • Clustering in Phase: The paper focuses on amplitude sparsity. Future research could explore extending the framework to also handle sparse clustering in the phase variability itself.
  • Algorithmic Improvements: Investigating global convergence of the algorithm, developing probabilistic approaches, and exploring model-based clustering are suggested future directions.

Summary updated

Abstract

A novel framework for sparse functional clustering that also embeds an alignment step is here proposed. Sparse functional clustering entails estimating the parts of the curves' domains where their grouping structure shows the most. Misalignment is a well-known issue in functional data analysis, that can heavily affect functional clustering results if not properly handled. Therefore, we develop a sparse functional clustering procedure that accounts for the possible curve misalignment: the coherence of the functional measure used in the clustering step to the class where the warping functions are chosen is ensured, and the well-posedness of the sparse clustering problem is proved. A possible implementing algorithm is also proposed, that jointly performs all these tasks: clustering, alignment, and domain selection. The method is tested on simulated data in various realistic situations, and its application to the Berkeley Growth Study data and to the AneuRisk65 dataset is discussed.
BibTeX
@article{vitelli2019novel,
  author = {Valeria Vitelli},
  title = {{A novel framework for joint sparse clustering and alignment of functional data}},
  journal = {Journal of Nonparametric Statistics},
  year = {2019},
}
Figure