🤖 machine learning

Rock the KASBA: Blazingly Fast and Accurate Time Series Clustering

The paper introduces KASBA, a novel and scalable time series clustering algorithm that leverages the Move-Split-Merge distance and stochastic subgradient descent to achieve a superior balance between high clustering accuracy and significantly reduced runtime compared to existing state-of-the-art methods.

Original authors: Christopher Holder, Anthony Bagnall

Published 2026-04-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Christopher Holder, Anthony Bagnall

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant box of thousands of different songs. Some are fast rock tracks, some are slow jazz, and some are electronic beats. Your goal is to sort them into piles so that songs in the same pile sound similar to each other, and songs in different piles sound very different. This is what Time Series Clustering does: it groups data that changes over time (like heartbeats, stock prices, or music) into similar families.

The problem is that sorting these "songs" is tricky. If you just look at the volume at every second (like comparing two songs point-by-point), a song that is slightly faster or slower than another will look completely different, even if they are the same tune. To fix this, computers use "elastic" rulers that can stretch and squish the time to line up the songs perfectly before comparing them.

However, there's a catch:

Some sorting methods are fast but do a terrible job of grouping the songs correctly.
Other methods are very accurate but take so long to run that you might age while waiting for the results.

The authors of this paper, Christopher Holder and Anthony Bagnall, have invented a new sorting machine called KASBA. They claim it is the best of both worlds: it sorts the songs with high accuracy but does it incredibly fast.

What is KASBA?

KASBA stands for K (k-means) A (accelerated) S (stochastic subgradient) B (barycentre) A (average). That's a mouthful, so let's break it down using a party analogy.

Imagine you are trying to organize a massive party and group guests into circles based on who they look most like.

The Elastic Ruler (MSM):
Most old sorting methods use a ruler that can stretch (called DTW) to match patterns. KASBA uses a slightly different, smarter ruler called MSM (Move-Split-Merge). Think of MSM as a ruler that not only stretches but also understands that if someone moves their hand slightly, it's a small "move," but if they suddenly jump, it's a bigger "split." This ruler is special because it follows strict mathematical rules (it's a "metric"), which allows KASBA to cheat a little to save time.
The Smart Start (Elastic k-means++):
Before sorting begins, you need to pick a few "leaders" to start the groups. Old methods might pick leaders randomly, which is like guessing who the popular kids are. KASBA uses a smart strategy (k-means++) to pick leaders that are far apart from each other, ensuring the groups start off well-separated. It does this using the elastic ruler right from the start, not just a standard ruler.
The "Guess and Check" Leader (Stochastic Subgradient):
Once the groups are formed, the computer needs to find the "perfect average" guest for each group (the centroid).
- Old way: It looks at every single guest in the group, calculates the perfect average, and updates the leader. This is slow.
- KASBA way: It picks a random small sample of guests, calculates a new leader, and updates immediately. Then it picks another small sample. It's like a teacher who doesn't wait for the whole class to finish a test before giving feedback; they give feedback as they go. This "Stochastic Subgradient" method is much faster.
The "Don't Bother Checking" Trick (Triangle Inequality):
This is the secret sauce that makes KASBA blazingly fast. Because the MSM ruler follows strict rules, KASBA can use a logic trick called the Triangle Inequality.
- The Analogy: Imagine you know that Guest A is 10 steps from the "Rock" leader and 100 steps from the "Jazz" leader. If the "Rock" leader and "Jazz" leader are 200 steps apart, you don't even need to measure the distance between Guest A and the Jazz leader to know Guest A belongs with Rock. The math proves it's impossible for them to be closer.
- KASBA uses this to skip millions of unnecessary calculations, saving huge amounts of time.

What Did They Find?

The authors tested KASBA on 112 different datasets (like a library of 112 different types of time-series data) from the University of California, Riverside. They compared it against the best existing methods.

Speed: KASBA is orders of magnitude faster than the most accurate competitors.
- While a top competitor called Shape-DBA took 8 days to sort the data, KASBA did it in minutes.
- Another competitor, Soft-DBA, would have taken nearly two months to finish the same job.
Accuracy: Despite being so fast, KASBA didn't sacrifice quality. It performed just as well as, or better than, the slow, accurate methods. It was the top-ranked algorithm for accuracy in their tests.
Robustness: Even on difficult datasets where other methods failed or got stuck, KASBA kept working and finished quickly.

The Bottom Line

The paper claims that KASBA is a "rock star" solution for time series clustering. It combines the best parts of previous methods (smart starting, smart averaging, and smart skipping of calculations) into one package.

The authors conclude that KASBA is ready for real-world use. It allows scientists and engineers to get high-quality groupings of their time-based data without having to wait days or weeks for the computer to finish the job. It's available for free in a software toolkit called aeon, so anyone can use it today.

1. Problem Statement

Time Series Clustering (TSCL) is a critical task for exploratory analysis and preprocessing in domains ranging from finance to medicine. However, a significant trade-off exists in current TSCL algorithms:

High Performance, Low Speed: Algorithms that use elastic distances (like Dynamic Time Warping - DTW) and advanced averaging techniques (like Barycentre Averaging) produce high-quality clusters but are computationally expensive, often failing to scale to large datasets or requiring days to run.
High Speed, Low Performance: Faster algorithms (like standard k-means with Euclidean distance or k-Shape) often fail to capture the temporal alignment and shape similarities inherent in time series data, leading to poor clustering accuracy.

The authors aim to bridge this gap by developing an algorithm that matches the accuracy of state-of-the-art (SOTA) methods while offering orders-of-magnitude improvements in runtime.

2. Methodology: The KASBA Algorithm

The authors propose KASBA (K-means accelerated A by Stochastic subgradient Barycentre Average). It is a k-means variant specifically designed for time series that integrates elastic distances throughout the entire clustering pipeline.

Core Components:

Elastic Distance Metric (MSM):
- KASBA utilizes the Move-Split-Merge (MSM) distance. Unlike DTW, MSM satisfies the metric property (specifically the triangle inequality), which is crucial for the algorithm's speed optimizations.
- The same distance function is applied consistently across initialization, assignment, and centroid updates.
Initialization (Elastic k-means++):
- Adapts the standard k-means++ initialization to use the elastic MSM distance instead of Euclidean distance.
- Selects initial centroids probabilistically based on distance to existing centroids, ensuring better starting points and faster convergence compared to random restarts (Forgy initialization).
Centroid Update (Stochastic Subgradient Barycentre):
- Instead of the greedy, full-batch DBA (DTW Barycentre Averaging) which is slow, KASBA uses a Stochastic Subgradient (SSG) descent approach.
- Subsampling: In each epoch, only a random subset of the cluster members is used to update the centroid. This reduces the number of distance calculations per iteration.
- Seeding: The update process is seeded with the centroid from the previous iteration (rather than recalculating from a simple arithmetic mean), significantly reducing the number of epochs required for convergence.
- Learning Rate: Uses an exponentially decaying learning rate to fine-tune the centroid position.
Assignment (Triangle Inequality Optimization):
- Exploits the triangle inequality property of the MSM distance (a feature DTW lacks).
- Before assigning a time series to a new centroid, the algorithm checks if the distance between the current centroid and the candidate centroid is large enough to guarantee the series cannot be closer to the candidate.
- If the condition $d(c_a, c_b) \ge 2d(x, c_a)$ is met, the distance calculation to the new centroid is skipped. This drastically reduces the number of expensive elastic distance computations.

3. Key Contributions

Algorithm Design: Introduction of KASBA, a fully integrated k-means framework that uses elastic distances (MSM) for initialization, assignment, and centroid averaging.
Speed Optimization:
- Implementation of Triangle Inequality skipping in the assignment phase, reducing distance calculations by ~40%.
- Development of a Stochastic Subgradient averaging method that avoids the computational bottleneck of full-batch barycentre averaging.
Initialization Strategy: Adaptation of k-means++ for elastic distances, proving it superior to random restarts in terms of both speed and final clustering quality.
Reproducibility: All experiments are conducted using the aeon toolkit and tsml-eval, with code and data available for full reproducibility.

4. Experimental Results

The authors evaluated KASBA on 112 datasets from the UCR Time Series Archive, comparing it against SOTA algorithms including DBA, Shape-DBA, Soft-DBA, k-Shape, PAM-MSM, and standard k-means.

Clustering Performance:
- KASBA achieved state-of-the-art performance across four metrics: Clustering Accuracy (CLACC), Adjusted Rand Index (ARI), Normalized Mutual Information (NMI), and Adjusted Mutual Information (AMI).
- It significantly outperformed k-Shape, Soft-DBA, and standard Euclidean k-means.
- It performed comparably to (and in some metrics slightly better than) the highly accurate but slow Shape-DBA and DBA.
Runtime Efficiency:
- Orders of Magnitude Faster: KASBA is 15 to 100 times faster than DBA and Shape-DBA.
- Scalability: While Shape-DBA took over 8 days to cluster 98 datasets, KASBA completed the same task in under 45 minutes.
- Comparison to PAM: KASBA is significantly faster than PAM-MSM (Partitioning Around Medoids), which struggles with memory and time on large datasets due to the need for pairwise distance matrices.
Ablation Studies:
- Removing the triangle inequality optimization doubled the runtime.
- Removing stochastic subsampling (using full batches) increased convergence time and reduced clustering quality (ARI).
- Using the previous centroid for seeding reduced runtime by 20% and improved convergence stability.

5. Significance

Practical Utility: KASBA solves the "accuracy vs. speed" dilemma, making high-quality elastic time series clustering feasible for real-world applications where large datasets and time constraints exist.
Benchmarking: The authors position KASBA as a new standard baseline for TSCL research, arguing that future algorithms should be compared against KASBA's balance of performance and efficiency.
Exploratory Analysis: The centroids generated by KASBA are shown to be highly interpretable and discriminative (demonstrated on the GunPoint dataset), making the algorithm a powerful tool for understanding temporal patterns without supervision.
Accessibility: By being implemented in the aeon toolkit and requiring minimal parameter tuning, KASBA lowers the barrier to entry for practitioners needing robust time series clustering.

In conclusion, KASBA represents a significant advancement in time series machine learning, delivering SOTA clustering quality with the computational efficiency required for modern, large-scale data analysis.