Online Clustering of Processes

Azadeh Khaleghi, Daniil Ryabko, Jérémie Mary, Philippe PreuxAISTATS 2012 · OpenReview

Abstract

The problem of online clustering is considered in the case where each data point is a sequence generated by a stationary ergodic process. Data arrive in an online fashion so that the sample received from each process increases with time, and the number of processes to be clustered may also increase. The goal is to provide a non-parametric algorithm that is asymptotically consistent, meaning it correctly identifies clusters as more data is observed.

Introduction

Clustering is a fundamental task in machine learning, typically applied to static vectors. However, in many real-world applications—such as financial monitoring, sensor networks, or video analysis—data arrives as continuous streams or "processes." Clustering these streams in real-time presents a unique challenge: the algorithm must handle data that is constantly evolving and expanding.

The Online Clustering Challenge

The core difficulty in online time-series clustering is the "bad sequence" problem. In a batch (offline) setting, the algorithm has access to the entire dataset at once. In an online setting, new sequences are initially very short. These short sequences lack sufficient statistical information to be categorized accurately. If a standard batch algorithm is applied every time new data arrives, these "noisy" short sequences can pollute the results, causing the algorithm to miscluster even the long, well-established sequences it had previously identified correctly.

Figure 3: Comparison of error rates between the proposed online algorithm and a standard offline approach. The offline method's error rate increases as it is confused by new, short sequences, while the online method continues to improve.

Methodology

The researchers propose a two-step approach to achieve robust online clustering without assuming specific parametric models like Markov Chains.

1. Distributional Distance

Instead of comparing raw data values, the algorithm compares the underlying distributions of the sequences. It uses a distance metric based on the frequency of finite-length "blocks" (patterns). This model-free approach allows the algorithm to handle any stationary ergodic process—a broad class where statistical properties remain stable over time.

2. The Online Weighting Scheme

To prevent new, short sequences from disrupting stable clusters, the algorithm (Alg 2) runs an offline subroutine on various subsets of data and combines them using a clever weighting system:

  • Inter-cluster distance weighting ($\gamma_j$): This penalizes clusterings where groups are too close together, which usually indicates that the sequences haven't been clearly separated yet.
  • Chronological weighting ($w_j$): This gives higher priority to older sequences that have been observed longer, protecting established clusters from being "overwritten" by the noise of new arrivals.

Experimental Evaluation

The method was tested on both synthetic DAS($\alpha$) processes and real-world Motion Capture (MOCAP) data from the CMU graphics lab. The synthetic tests confirmed that while offline algorithms struggle with the introduction of new data, the proposed online algorithm's error rate consistently converges toward zero.

On real-world locomotion data (walking, running, jumping), the algorithm demonstrated superior performance over existing state-of-the-art methods. For instance, in a "Walk vs. Run" classification task, the proposed algorithm achieved a perfect entropy score of 0.

Figure 5: Performance comparison on MOCAP data showing the proposed algorithm (Alg 1) achieving zero error/entropy on the Walk vs. Run task compared to existing methods.

Conclusion and Future Work

This research provides a mathematically grounded framework for clustering data streams on the fly. By focusing on distributional distances and robust weighting, the algorithm remains efficient and accurate even as new data points are added.

Currently, the algorithm requires a pre-defined number of clusters ($k$). Future work aims to extend this to scenarios where $k$ is unknown, potentially by constructing a hierarchy of clusters to estimate the optimal number of groups automatically. Additionally, while the algorithm excels at continuous, ergodic motions, further refinements may improve its performance on discrete, non-ergodic actions like single jumps.

Summary updated

Abstract

The problem of online clustering is considered in the case where each data point is a sequence generated by a stationary ergodic process. Data arrive in an online fashion so that the sample receive...
BibTeX
@inproceedings{khaleghi2012online,
  author = {Azadeh Khaleghi and Daniil Ryabko and Jérémie Mary and Philippe Preux},
  title = {{Online Clustering of Processes}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2012},
  url = {https://openreview.net/forum?id=QuZYAySvLMZ},
}
Figure