2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

If you read the SLINK publication (an efficient algorithm for single-link clustering; using $O(n)$ memory and $O(n^2)$ time, as opposed to the $O(n^3)$ standard algorithm), then you will find that it is based on what is called a "pointer representation". This representation allows rather efficient construction of a non-overlapping dendrogram. Should be in $O(n)$, if you have this representation.

$\endgroup$
  • $\begingroup$ Thanks. Yes, I've seen this method. The problem is that it applies to only particular inter-cluster metric and operates along with the actual clustering. I need the algo to create dendrogram having the history of mergers after any metric was used. $\endgroup$ – Oleg Shirokikh Mar 3 '14 at 16:59
  • $\begingroup$ You should be able to compute a similar representation from any other dendrogram. As far as I can tell, ELKI is doing that e.g. with UPGMA, too. $\endgroup$ – Anony-Mousse Mar 3 '14 at 17:34

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.