AI.Clustering.Hierarchical

High performance agglomerative hierarchical clustering library. Example:

>>> :set -XOverloadedLists
>>> import qualified Data.Vector as V
>>> let points = [[2, 3, 4], [2, 1, 2], [2, 1, 6], [2, 4, 6], [5, 1, 2]] :: V.Vector (V.Vector Double)
>>> let dendro = hclust Average points euclidean
>>> print dendro
Branch 5 4.463747440868191 (Branch 3 2.914213562373095 (Leaf (fromList [2.0,1.0,6.0]))
(Branch 2 2.23606797749979 (Leaf (fromList [2.0,3.0,4.0])) (Leaf (fromList [2.0,4.0,6.0]))))
(Branch 2 3.0 (Leaf (fromList [2.0,1.0,2.0])) (Leaf (fromList [5.0,1.0,2.0])))
>>> putStr $ drawDendrogram $ fmap show dendro
h: 4.4637
|
+- h: 2.9142
|  |
|  +- fromList [2.0,1.0,6.0]
|  |
|  `- h: 2.2361
|     |
|     +- fromList [2.0,3.0,4.0]
|     |
|     `- fromList [2.0,4.0,6.0]
|
`- h: 3.0000
   |
   +- fromList [2.0,1.0,2.0]
   |
   `- fromList [5.0,1.0,2.0]

Documentation

data Dendrogram a

Constructors

Leaf !a

Branch !Size !Distance !(Dendrogram a) !(Dendrogram a)

Instances

Functor Dendrogram

Defined in AI.Clustering.Hierarchical.Types

Methods

fmap :: (a -> b) -> Dendrogram a -> Dendrogram b

(<$) :: a -> Dendrogram b -> Dendrogram a

Eq a => Eq (Dendrogram a)

Defined in AI.Clustering.Hierarchical.Types

Methods

(==) :: Dendrogram a -> Dendrogram a -> Bool

(/=) :: Dendrogram a -> Dendrogram a -> Bool

Show a => Show (Dendrogram a)

Defined in AI.Clustering.Hierarchical.Types

Methods

showsPrec :: Int -> Dendrogram a -> ShowS

show :: Dendrogram a -> String

showList :: [Dendrogram a] -> ShowS

Binary a => Binary (Dendrogram a)

Defined in AI.Clustering.Hierarchical.Types

Methods

put :: Dendrogram a -> Put

get :: Get (Dendrogram a)

putList :: [Dendrogram a] -> Put

size :: Dendrogram a -> Int

O(1) Return the size of a dendrogram

data Linkage

Different hierarchical clustering schemes.

Constructors

Single

O(n^2) Single linkage, $d(A,B) = min_{a in A, b in B} d(a,b)$.

Complete

O(n^2) Complete linkage, $d(A,B) = max_{a in A, b in B} d(a,b)$.

Average

O(n^2) Average linkage or UPGMA, $d(A,B) = frac{sum_{a in A}sum_{b in B}d(a,b)}{|A||B|}$.

Weighted

O(n^2) Weighted linkage.

Ward

O(n^2) Ward's method.

Centroid

O(n^3) Centroid linkage, not implemented.

Median

O(n^3) Median linkage, not implemented.

hclust :: Vector v a => Linkage -> v a -> DistFn a -> Dendrogram a

Perform hierarchical clustering.

normalize :: Dendrogram a -> Dendrogram a

Normalize the tree heights so that the highest is 1.

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

Cut a dendrogram at given height.

flatten :: Dendrogram a -> [a]

Return the elements of a dendrogram in pre-order.

drawDendrogram :: Dendrogram String -> String

2-dimensional drawing of a dendrogram

Distance functions

euclidean :: Vector v Double => DistFn (v Double)

Compute euclidean distance between two points.

hamming :: (Vector v a, Vector v Bool, Eq a) => DistFn (v a)

Hamming distance.

References

Müllner D (2011). Modern Hierarchical, Agglomerative Clustering Algorithms. ArXiv:1109.2378 [stat.ML]. http://arxiv.org/abs/1109.2378