Incremental Clustering with Concept Drift Detection (UIClust)

Description

Update clusters batch by batch from compact summaries, flag drift from outliers or shifting cluster shares, and use a parallel model to tell temporary from lasting change.

Segmentations built once by static clustering go stale as behaviour changes, while re-clustering everything each time is slow. UIClust keeps only a summary per cluster: centroid, radius, lifetime count and count in the current batch. New records join the nearest cluster if they fall within its radius and nudge its centroid as a running mean; others count as outliers. Drift is flagged when the share of outliers passes one threshold or when the proportion of records in any cluster shifts beyond another. A parallel clustering is then built from the current batch and both are updated for up to three batches: if the main model stops drifting, the change was temporary and the parallel model is discarded; if not, it replaces the main model. This separates short shocks such as a holiday spike from lasting shifts in user segments.

Attributes

Loss type
Unmigrated
Stage
Post-launch
Effort
Weeks

Steps

  1. Normalise numeric attributes (for example min-max) and split the incoming data into batches by time or volume.
  2. Cluster the first batch with k-means and store each cluster's centroid, radius, lifetime count and batch count; discard the raw records.
  3. For each new batch, assign each record to the nearest cluster within its radius and update that centroid as a running mean; count records outside every radius as outliers.
  4. Flag drift if the outlier ratio exceeds its threshold or any cluster's share of records changes by more than the dissimilarity threshold since the previous batch.
  5. On drift, build a parallel k-means clustering from the current batch and update both models for up to three further batches.
  6. Discard the parallel model if the main model stops drifting (temporary drift); otherwise replace the main model with it (sustained drift), and log each decision.

Sources

  • A Novel Incremental Clustering Technique with Concept Drift Detection (Woodbright et al., 2020)

Also known as

  • UIClust
  • Unsupervised Incremental Clustering
  • Streaming cluster updating with concept drift detection
  • Parallel clustering three-strike drift rule

Categories

  • Analytics & Behaviour
  • Computational & Machine Learning