# Structural Stability of Hierarchical Clustering

I am interested in some papers and reports about analysing the following problem: Assume, we have a stream of objects and a defined similarity/distance measure to calculate similarity/distance between single objects and group of objects. We construct a clustering in an incremental way. The problem is to decide when to close the stream and stop adding new objects - which would mean that none of new objects will change the structure of the clustering. In other words there should be some convergence point where we can say the out clustering is a good representation of grouping.

I am specially interested in hierarchical clustering methods as they allow to construct cluster hierarchy without specifying and fixing the number of clusters during algorithm run.

I did some experiments that are based on comparing dendrograms over time using Bakers Gamma Index (http://rpackages.ianhowson.com/cran/dendextend/man/cor_bakers_gamma.html) and estimating the point where the correlation between past and present dendrogram is not changing up to some degree and then stop. Anyway it would be nice to compare this approach. I was looking for some papers with similar stated problems, but I did not succeed. Maybe someone can help?

• which would mean that none of new objects will change the structure of the clustering, hierarchical clustering methods as they allow to construct cluster hierarchy without specifying and fixing the number of clusters during algorithm run. These two ideas are hard to reconcile. An incoming point won't change the cluster structure only if you already decided where to partition the tree into clusters, eo ipso you had quit any hierarchy. – ttnphns Jan 24 '15 at 15:21
• When a new object in inserted into already existing dendrogram it may cause that some two existing partitions will get closer or more distant. As a result, this may lead to repartitioning existing objects. But if a new object in inserted at the bottom of the dendrogram, lets say as a sibling of existing leaf, then all other objects remain in their previous partitions. I would describe the structural stability as the moment when adding new objects does not change lowest common ancestors (LCAs) for majority of objects/leaves in dendrogram – Sebastian Widz Jan 24 '15 at 15:43
• When a new object appears and you want to find out whether and in what way it affects the dendrogram you have to re-do the entire clustering process from the very beginning. Alternatively, you could assign the new object to clusters, - but then the clusters must be just non-intersecting groups and not dendrogram. That's what I was saying. – ttnphns Jan 24 '15 at 17:57
• Yes, I have to recalculate the whole dendrogram, but there are also some incremental hierarchical clustering algorithms that recalculate only affected branches. But the point is a bit different, forgetting for a while about computational complexity, I can recalculate and calculate e.g. Backers Gamma Index (rpackages.ianhowson.com/cran/dendextend/man/…) to see how much dendrogram has changed. – Sebastian Widz Jan 24 '15 at 18:02
• The abstract of the article you yo link to says the author (Baker) used Goodman-Kruskal Gamma (not some Backer's Gamma). It is an old and well known nonparametric correlation coefficient. It can be used, in particular, to compare two dendrograms of equal size, as one of possible "cophenetic correlation" measures. – ttnphns Jan 24 '15 at 18:25