order.greedy {cba}

Hierarchical Greedy Ordering

Description

Compute a hierarchical greedy ordering of a data matrix.

Usage

order.greedy(dist)

Arguments

dist

an object of class dist.

Details

A single cluster is constructed by merging in each step the leaf closest to one of the two endpoints of the cluster. The algorithm starts with a random leaf and uses tie-breaking.

Clearly, the algorithm is more an ordering than a cluster algorithm. However, it constructs a binary merge tree so that the linear ordering of its leaves could be further improved.

Value

A list with the following components:

merge

a matrix containing the merge tree.

order

a vector containing the leaf ordering.

height

a vector containing the merge heights.

Note

The merge heights may not be monotonic.

Author(s)

Christian Buchta

References

F. Murtagh (1985). Multidimensional Cluster Algorithms. Lectures in Computational Statistics, Physica Verlag, pp. 15.

See Also

hclust for hierarchical clustering, order.optimal for optimal leaf ordering, and order.length for computing the objective value of a leaf ordering.

Examples

d <- dist(matrix(runif(20), ncol=2))
hc <- hclust(d)
co <- order.optimal(d, hc$merge)
md <- -as.dist(crossprod(as.matrix(d, diag = 0)))   # Murtagh's distances
hg <- order.greedy(md)
go <- order.optimal(md, hg$merge)
### compare images
op <- par(mfrow=c(2,2), pty="s")
implot(d[[hc$order]], main="hclust")
implot(d[[co$order]], main="hlcust + optimal")
implot(d[[hg$order]], main="greedy")
implot(d[[go$order]], main="greedy + optimal")
par(op)
# compare lengths
order.length(d, hc$order)
order.length(d, co$order)
order.length(d, hg$order)
order.length(d, go$order)