Solutions for Continuous Online Cluster Identification?

Question

Let me show you an example of a hypothetical online clustering application:

At time n points 1,2,3,4 are allocated to the blue cluster A and points b,5,6,7 are allocated to the red cluster B.

At time n+1 a new point a is introduced which is assigned to the blue cluster A but also causes the point b to be assigned to the blue cluster A as well.

In the end points 1,2,3,4,a,b belong to A and points 5,6,7 to B. To me this seems reasonable.

What seems simple at first glance is actually a bit tricky - to maintain identifiers across time steps. Let me try to make this point clear with a more borderline example:

The green point will cause two blue and two red points to be merged into one cluster which I arbitrarily decided to color blue - mind this is already my human heuristical thinking at work!

A computer to make this decision will have to use rules. For example when points are merged into a cluster then the identity of the cluster is determined by the majority. In this case we would face a draw - both blue and red might be valid choices for the new (here blue colored) cluster.

Imagine a fifth red point close to the green one. Then the majority would be red (3 red vs 2 blue) so red would be a good choice for the new cluster - but this would contradict the even clearer choice of red for the rightmost cluster as those have been red and probably should stay that way.

I find it fishy to think about this. At the end of the day I guess there are no perfect rules for this - rather heuristics optimizing some stability criterea.

This finally leads to my questions:

1. Does this "problem" have a name that it can be referred to?
2. Are there "standard" solutions to this and ...
3. ... is there maybe even an R package for that?

---

Reasonable Inheritance of Cluster Identities in Repetitive Clustering

Answer 1

Stability-Plasticity Dilemma, Learning Rates, and Forgetting Algorithms:

First, let me say that this is a really great question and is the type of thought provoking stuff that really improves one's understanding of ML algorithms.

1. Does this "problem" have a name that it can be referred to?

This is generally referred to as "stability". What's funny is that stability is actually a useful concept in regular clustering i.e. not online. The "stability" of the algorithm is often chosen as a selection criterion for whether the right number of clusters have been selected. More specifically, the online clustering stability issue that you have described is referred to as the stability-plasticity dilemma.

2. Are there "standard" solutions to this and ...

First, the big picture answer is that many online clustering algorithm are surprisingly stable when they have been well trained with a large cohort of initial data. However, its still a problem if you want to really nail down the cluster identities of points while allowing the algorithm to react to new data. The trickiness of you point is briefly addressed in Introduction to Machine Learning By Ethem Alpaydin. On page 319 he derives the online k-means algorithm through the application of stochastic gradient descent, but mentions that the stability-plasticity dilemma arises when choosing a value for the learning rate. A small learning rate results in stability, but the system looses adaptability where as a larger learning rate gains adaptability, but looses cluster stability.

I believe the best path forward is to choose an implementation of online clustering which allows you to control the stochastic gradient descent algorithm and then choose the learning rate so that you maximize stability and adaptability as best as you can using a sound cross-validation procedure.

Another method that I've seen employed is some sort of forgetting algorithm e.g. forgetting older points as the data stream matures. This allows for a fairly stable system on fast time scales and allows for evolution on slower time scales. Adaptive Resonance Theory was created to try to solve the stability-plasticity dilemma. You might find this article interesting.

I'm not well-versed enough in R to suggest an algorithm, but I suggest you look for a mini-batch k-means algorithm that allows you to control the learning rate in its stochastic gradient descent algorithm.

I hope this helps!