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

Felipe Lessa felipe.lessa at gmail.com
Wed Aug 4 14:27:24 EDT 2010

On Tue, Aug 3, 2010 at 8:23 AM, Felipe Lessa <felipe.lessa at gmail.com> wrote:
> On Tue, Aug 3, 2010 at 8:01 AM, Ivan Lazar Miljenovic
> <ivan.miljenovic at gmail.com> wrote:
>> Felipe Lessa <felipe.lessa at gmail.com> 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! =)


More information about the Haskell-Cafe mailing list