Safe Haskell	None
Language	Haskell98

Data.Clustering.Hierarchical

Contents

Dendrogram data type
Linkage data type
Clustering function

Synopsis

Dendrogram data type

data Dendrogram a Source

Data structure for storing hierarchical clusters. The distance between clusters is stored on the branches. Distances between leafs are the distances between the elements on those leafs, while distances between branches are defined by the linkage used (see Linkage).

Constructors

Leaf a	The leaf contains the item `a` itself.
Branch !Distance (Dendrogram a) (Dendrogram a)	Each branch connects two clusters/dendrograms that are `d` distance apart.

Instances

Functor Dendrogram	Does not recalculate the distances!
Foldable Dendrogram
Traversable Dendrogram
Eq a => Eq (Dendrogram a)
Ord a => Ord (Dendrogram a)
Show a => Show (Dendrogram a)

type Distance = Double Source

A distance is simply a synonym of Double for efficiency.

elements :: Dendrogram a -> [a] Source

List of elements in a dendrogram.

cutAt :: Dendrogram a -> Distance -> [Dendrogram a] Source

dendro `cutAt` threshold cuts the dendrogram dendro at all branches which have distances strictly greater than threshold.

For example, suppose we have

dendro = Branch 0.8
           (Branch 0.5
             (Branch 0.2
               (Leaf 'A')
               (Leaf 'B'))
             (Leaf 'C'))
           (Leaf 'D')

Then:

dendro `cutAt` 0.9 == dendro `cutAt` 0.8 == [dendro] -- no changes
dendro `cutAt` 0.7 == dendro `cutAt` 0.5 == [Branch 0.5 (Branch 0.2 (Leaf 'A') (Leaf 'B')) (Leaf 'C'), Leaf 'D']
dendro `cutAt` 0.4 == dendro `cutAt` 0.2 == [Branch 0.2 (Leaf 'A') (Leaf 'B'), Leaf 'C', Leaf 'D']
dendro `cutAt` 0.1 == [Leaf 'A', Leaf 'B', Leaf 'C', Leaf 'D'] -- no branches at all

Linkage data type

data Linkage Source

The linkage type determines how the distance between clusters will be calculated. These are the linkage types currently available on this library.

Constructors

SingleLinkage	The distance between two clusters `a` and `b` is the minimum distance between an element of `a` and an element of `b`.
CompleteLinkage	The distance between two clusters `a` and `b` is the maximum distance between an element of `a` and an element of `b`.
CLINK	The same as `CompleteLinkage`, but using the CLINK algorithm. It's much faster however doesn't always give the best complete linkage dendrogram.
UPGMA	Unweighted Pair Group Method with Arithmetic mean, also called "average linkage". The distance between two clusters `a` and `b` is the arithmetic average between the distances of all elements in `a` to all elements in `b`.
FakeAverageLinkage	This method is usually wrongly called "average linkage". The distance between cluster `a = a1 U a2` (that is, cluster `a` was formed by the linkage of clusters `a1` and `a2`) and an old cluster `b` is `(d(a1,b) + d(a2,b)) / 2`. So when clustering two elements to create a cluster, this method is the same as UPGMA. However, in general when joining two clusters this method assigns equal weights to `a1` and `a2`, while UPGMA assigns weights proportional to the number of elements in each cluster. See, for example: http://www.cs.tau.ac.il/~rshamir/algmb/00/scribe00/html/lec08/node21.html, which defines the real UPGMA and gives the equation to calculate the distance between an old and a new cluster. http://github.com/JadeFerret/ai4r/blob/master/lib/ai4r/clusterers/average_linkage.rb, code for "average linkage" on ai4r library implementing what we call here `FakeAverageLinkage` and not UPGMA.

Instances

Enum Linkage
Eq Linkage
Ord Linkage
Show Linkage

Clustering function

dendrogram Source

Arguments

:: Linkage	Linkage type to be used.
-> [a]	Items to be clustered.
-> (a -> a -> Distance)	Distance function between items.
-> Dendrogram a	Complete dendrogram.

Calculates a complete, rooted dendrogram for a list of items and a linkage type. The following are the time and space complexities for each linkage:

SingleLinkage: O(n^2) time and O(n) space, using the SLINK algorithm. This algorithm is optimal in both space and time and gives the same answer as the naive algorithm using a distance matrix.
CompleteLinkage: O(n^3) time and O(n^2) space, using the naive algorithm with a distance matrix. Use CLINK if you need more performance.
Complete linkage with CLINK: O(n^2) time and O(n) space, using the CLINK algorithm. Note that this algorithm doesn't always give the same answer as the naive algorithm using a distance matrix, but it's much faster.
UPGMA: O(n^3) time and O(n^2) space, using the naive algorithm with a distance matrix.
FakeAverageLinkage: O(n^3) time and O(n^2) space, using the naive algorithm with a distance matrix.