Reproduce “Rock the KASBA: Blazingly Fast and Accurate Time Series Clustering” on OpenResearch

About this paper

Christopher Holder, Anthony Bagnall

KASBA, a time series clustering algorithm, combines elastic k-means++ initialization, barycentre stochastic subgradient descent, and triangle inequality-based fast assignments. It delivers state-of-the-art clustering accuracy while achieving computational speeds 10 to 1000 times faster than comparable methods on 112 UCR datasets.

Key insights

• Optimizing all three stages of the k-means algorithm—initialization, assignment, and centroid update—with consistent application of elastic distances is crucial for balancing accuracy and speed.
• Exploiting the metric properties, specifically the triangle inequality, of elastic distance measures offers substantial computational acceleration during the assignment phase without affecting clustering results.
• Stochastic subgradient descent, combined with centroid seeding from previous iterations and random subsampling, enables efficient and stable barycentre computation for elastic centroid updates.

Summary by alphaXiv.