Assume there is a distance matrix d [n x n], on which we can do hierarchical clustering (say, using average distances). The dendrogram/clustering resulting from this operation is then c.

Are there any algorithms that start from the already calculated c and d, and then deal with incremental updates to d and how they affect c instead of recalculating everything from scratch? It need not give the precise same results of hierarchical clustering but it should maintain more or less the same logic.


To provide more details: Imagine matrix D and the hierarchical tree (not just the cluster labels) h. This matrix D is now updated to a matrix D' with new distances (no new objects, just updated distances) that are "relatively close to" the old ones. We can also look at the more simple case where just one point is updated (i.e. one column in the matrix) and all other distances stay the same. In principle one could then stepwise update the entire matrix. (Question is whether at this point you still gain anything.)

Is there a way to go from h to h' without recalculating everything from scratch? I.e. can we simplify the clustering procedure by knowing the previous cluster, and the fact that the distances haven't changed much?

Adding / removing points would of course also be interesting. Basically the case of substituting one column could be written as removing one column and adding one column, or the other way around...

  • $\begingroup$ Please, explain your idea more precisely/detailed. What incremental updates in this case, etc. Could your question be put in a simpler form?: (1) "Having a set of clusters of points (matrix D + their cluster labels), assign new coming points to those clusters". Or maybe (2) "Having a set of clusters (matrix D between the clusters + info how many (>=1) points are in each cluster) start cluster from this "step" and do it till the end. $\endgroup$ – ttnphns Dec 13 '16 at 10:10
  • 1
    $\begingroup$ Thanks for adding detals. So, your Q appears now primarily about some "small" disturbance of distances and whether it affects clustering results. Is there a way to go from h to h' without recalculating everything from scratch? No, generally no. Even small change to single distance can sometimes change results drastically, especially when the distance is small, so it gets clustered early on the steps. Hierarchical clustering is greedy stepwise technique. If it does "wrong" - in one's eyes - decision on one step, it cannot go back to undo it. $\endgroup$ – ttnphns Dec 13 '16 at 11:27

Hierarchical clustering results are not very well updateable.

If the nearest neighbor of a new point (similar for a disappearing) point is at height h, then you should be able to keep anything below this value.

This is inherent to the design of hierachical clustering; so if you try to find an approximation for more efficient updating (I believe I have seen such a paper) then your result quality can drop to "completely wrong result" pretty much instantly.

Here's a paper on updating MST (= single linkage clustering) in O(n) when a new node arrives: http://epubs.siam.org/doi/abs/10.1137/0204032 but it won't transfer to other linkages.

Here's a simple proof:

Theorem: Updating hierarchical clustering takes at least O(n) time for linkages with runtime O(n^2) (e.g. single-link) and at least O(n^2) for linkages with runtime O(n^3) (all popular others).

Proof: Otherwise, we had a more efficient algorithm for hierarchical clustering by repeated insertion of points, which uses O(n*updatecost).

So in the general case, updating will at least be O(n^2) (assuming that the worst case O(n^3) for dendrogram construction is proven).

In many cases it may be better to label your old data with the cluster ids, then train a classifier, and rather use your classifier for new points than trying to update the dendrogram tree.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.