hierarchical-clustering-0.4.7: Fast algorithms for single, average/UPGMA and complete linkage clustering.

Safe Haskell | Safe-Inferred
Language | Haskell98

Data.Clustering.Hierarchical.Internal.Types

Synopsis

- data Dendrogram a
  - = Leaf a
  - | Branch !Distance (Dendrogram a) (Dendrogram a)
- data Linkage
  - = SingleLinkage
  - | CompleteLinkage
  - | CLINK
  - | UPGMA
  - | FakeAverageLinkage
- type Distance = Double

# Documentation

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

Instances details

Functor Dendrogram Source # | Does not recalculate the distances!
Instance details Defined in Data.Clustering.Hierarchical.Internal.Types Methods fmap :: (a -> b) -> Dendrogram a -> Dendrogram b Source # (<$) :: a -> Dendrogram b -> Dendrogram a Source #
Foldable Dendrogram Source # |

Instance details

Defined in Data.Clustering.Hierarchical.Internal.Types

Methods

fold :: Monoid m => Dendrogram m -> m Source #

foldMap :: Monoid m => (a -> m) -> Dendrogram a -> m Source #

foldMap' :: Monoid m => (a -> m) -> Dendrogram a -> m Source #

foldr :: (a -> b -> b) -> b -> Dendrogram a -> b Source #

foldr' :: (a -> b -> b) -> b -> Dendrogram a -> b Source #

foldl :: (b -> a -> b) -> b -> Dendrogram a -> b Source #

foldl' :: (b -> a -> b) -> b -> Dendrogram a -> b Source #

foldr1 :: (a -> a -> a) -> Dendrogram a -> a Source #

foldl1 :: (a -> a -> a) -> Dendrogram a -> a Source #

toList :: Dendrogram a -> [a] Source #

null :: Dendrogram a -> Bool Source #

length :: Dendrogram a -> Int Source #

elem :: Eq a => a -> Dendrogram a -> Bool Source #

maximum :: Ord a => Dendrogram a -> a Source #

minimum :: Ord a => Dendrogram a -> a Source #

sum :: Num a => Dendrogram a -> a Source #

product :: Num a => Dendrogram a -> a Source #

Traversable Dendrogram Source # |
Instance details Defined in Data.Clustering.Hierarchical.Internal.Types Methods traverse :: Applicative f => (a -> f b) -> Dendrogram a -> f (Dendrogram b) Source # sequenceA :: Applicative f => Dendrogram (f a) -> f (Dendrogram a) Source # mapM :: Monad m => (a -> m b) -> Dendrogram a -> m (Dendrogram b) Source # sequence :: Monad m => Dendrogram (m a) -> m (Dendrogram a) Source #
Show a => Show (Dendrogram a) Source # |
Instance details Defined in Data.Clustering.Hierarchical.Internal.Types Methods showsPrec :: Int -> Dendrogram a -> ShowS Source # show :: Dendrogram a -> String Source # showList :: [Dendrogram a] -> ShowS Source #
Eq a => Eq (Dendrogram a) Source # |
Instance details Defined in Data.Clustering.Hierarchical.Internal.Types Methods (==) :: Dendrogram a -> Dendrogram a -> Bool Source # (/=) :: Dendrogram a -> Dendrogram a -> Bool Source #
Ord a => Ord (Dendrogram a) Source # |

Instance details

Defined in Data.Clustering.Hierarchical.Internal.Types

Methods

compare :: Dendrogram a -> Dendrogram a -> Ordering Source #

(<) :: Dendrogram a -> Dendrogram a -> Bool Source #

(<=) :: Dendrogram a -> Dendrogram a -> Bool Source #

(>) :: Dendrogram a -> Dendrogram a -> Bool Source #

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

max :: Dendrogram a -> Dendrogram a -> Dendrogram a Source #

min :: Dendrogram a -> Dendrogram a -> Dendrogram a Source #

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

Instances details

Enum Linkage Source # |

Instance details

Defined in Data.Clustering.Hierarchical.Internal.Types

Methods

succ :: Linkage -> Linkage Source #

pred :: Linkage -> Linkage Source #

toEnum :: Int -> Linkage Source #

fromEnum :: Linkage -> Int Source #

enumFrom :: Linkage -> [Linkage] Source #

enumFromThen :: Linkage -> Linkage -> [Linkage] Source #

enumFromTo :: Linkage -> Linkage -> [Linkage] Source #

enumFromThenTo :: Linkage -> Linkage -> Linkage -> [Linkage] Source #

Show Linkage Source # |
Instance details Defined in Data.Clustering.Hierarchical.Internal.Types Methods showsPrec :: Int -> Linkage -> ShowS Source # show :: Linkage -> String Source # showList :: [Linkage] -> ShowS Source #
Eq Linkage Source # |
Instance details Defined in Data.Clustering.Hierarchical.Internal.Types Methods (==) :: Linkage -> Linkage -> Bool Source # (/=) :: Linkage -> Linkage -> Bool Source #
Ord Linkage Source # |
Instance details Defined in Data.Clustering.Hierarchical.Internal.Types Methods compare :: Linkage -> Linkage -> Ordering Source # (<) :: Linkage -> Linkage -> Bool Source # (<=) :: Linkage -> Linkage -> Bool Source # (>) :: Linkage -> Linkage -> Bool Source # (>=) :: Linkage -> Linkage -> Bool Source # max :: Linkage -> Linkage -> Linkage Source # min :: Linkage -> Linkage -> Linkage Source #

type Distance = Double Source #

A distance is simply a synonym of `Double` for efficiency.