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:
- Does this "problem" have a name that it can be referred to?
- Are there "standard" solutions to this and ...
- ... is there maybe even an R package for that?