3
$\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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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, 2014 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$
    – Has QUIT--Anony-Mousse
    Mar 3, 2014 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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