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?Reasonable Inheritance of Cluster Identities in Repetitive Clustering
Solutions for Continuous Online Cluster Identification?
machine learning;clustering