[Haskell-cafe] ANNOUNCE: hierarchical-clustering and
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.
More information about the Haskell-Cafe