Re: [Haskell-cafe] ANNOUNCE: hierarchical-clustering and gsc-weighting

On Tue, Aug 3, 2010 at 8:23 AM, Felipe Lessa wrote:

On Tue, Aug 3, 2010 at 8:01 AM, Ivan Lazar Miljenovic wrote:

...

Felipe Lessa writes:

...

'hierarchical-clustering' provides a function to create a dendrogram from a list of items and a distance function between them.  The most common linkage types are available: single linkage, complete linkage and UPGMA.  An item can be anything, for example a DNA sequence, so this may used to create a phylogenetic tree.

What actual clustering algorithm are you using here?

A naïve O(n^2) algorithm using a distance matrix.  This can be improved without changing the API, however.

What a blunder! I mean, an O(n^3) algorithm -- each step takes O(n^2), and you need 'n' steps to create the whole dendrogram. I'll fix the documentation on the next release. Cheers! =) -- Felipe.