Clustering Dynamic Spatio-Temporal Patterns in The Presence of Noise and Missing Data

Xi C. Chen, James H. Faghmous, Ankush Khandelwal, Vipin KumarIJCAI 2015

Tracking objects that change shape and size over time is a fundamental challenge in fields ranging from Earth science to medical imaging. Traditional clustering methods often fail when sensors are noisy or data is frequently missing—for instance, when satellite views of a lake are blocked by persistent cloud cover. This paper, originally presented at IJCAI 2015, introduces a novel spatio-temporal clustering paradigm designed to handle these real-world complexities by identifying "stable cores" to anchor dynamic clusters.

The Challenge of Dynamic Data

Most existing clustering algorithms, such as K-Means or Normalized Cuts, are designed for static datasets. However, spatio-temporal data is inherently dynamic; clusters move, expand, and contract over time.

Spatio-temporal clusters change shape and size over time (T to T+4).

As shown in the sequence above, a single object (like a pulsing brain region or a seasonal lake) does not maintain a constant footprint. Snapshot-based analysis often fails to capture this continuity, especially when individual frames are degraded.

Data Quality and Real-World Constraints

Beyond dynamics, real-world sensors produce "messy" data. Satellite imagery, for example, is plagued by two primary issues: missing values due to cloud cover and noise artifacts from sensor heat or atmospheric interference.

Visualizing the impact of noise and missing values on satellite imagery.

When data quality drops, traditional methods that rely on spatial proximity in a single time step often collapse. The authors argue that a "temporal-first" approach is required to distinguish true object boundaries from transient noise.

Proposed Methodology: The Stable Core Paradigm

The researchers propose a four-step process that leverages long-term temporal signatures to provide robustness:

  1. Identify Core Points: The algorithm first identifies locations that remain consistently within the same cluster over a significant temporal window.
  2. Discover Stable Clusters (ST-DBSCAN): The popular DBSCAN algorithm is extended into the spatio-temporal domain. It uses a specialized distance metric where two points are considered neighbors only if they are physically close and their time-series signatures are statistically similar.
  3. Grow and Refine (Layered Classifier): Once stable cores are established, the algorithm "grows" the clusters to include uncertain points at the boundaries using a local Bayesian classifier. This ensures spatial consistency while adapting to local statistical variations.
  4. Post-processing: A final pass ensures label consistency across the entire dataset.

The "secret sauce" is the use of temporal redundancy. By assuming that noise is random (white noise), the method proves that the difference between signals of two pixels in the same object should average to zero over time, effectively using time to "cure" noise.

Evaluation and Results

The method was validated using global in-land water monitoring data (TCWETNESS from MODIS satellites) across 166 lake regions. The results were compared against K-Means, Expectation-Maximization (EM), and Normalized Cuts (NCUT).

  • Robustness: The proposed method maintained high F1 scores even when up to 60% of the data was missing, a point where NCUT and K-Means performance plummeted.
  • Scalability: The approach proved effective across diverse geographies, from arid reservoirs to tropical lakes, by using local classifiers that adapt to different environments.

Conclusion

By anchoring dynamic clusters to their most stable temporal features, this paradigm offers a robust solution for analyzing messy, real-world spatio-temporal data. While the current work requires manual selection of a temporal window size, future research aims to automate this process, allowing the system to adaptively determine the necessary historical context for accurate classification.

Summary updated

BibTeX
@inproceedings{chen2015clustering,
  author = {Xi C. Chen and James H. Faghmous and Ankush Khandelwal and Vipin Kumar},
  title = {{Clustering Dynamic Spatio-Temporal Patterns in The Presence of Noise and Missing Data}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure