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.
Edit:
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...
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$