Assuming merging process was completed and we have the history of n-1
merged clusters (merge two clusters p
and q
to cluster c = min{p,q}
), we are to draw the dendrogram with k
leaf nodes (or number of records, whichever is smaller). If k
is smaller then number of records then leaves represent cluster objects
I've seen some papers with optimal leaf ordering algorithms that run in O(n^4)
time and other fancy algorithms.
I've also heard about "left sliding" ordering.
I'm looking for a simple ordering algorithm to find an admissible ordering of k
leaf objects for dendrogram, given history of n-1
merged pairs. Pseudo-code or link would be very nice.