cluster.dist {cba}

Clustering a Sparse Symmetric Distance Matrix

Description

Compute a clustering on a sparse symmetric distance matrix using graph cutting.

Usage

cluster.dist(x, beta)

Arguments

x

an object of class dist.

beta

the distance threshold.

Details

This function computes a clustering on an object of class dist by cutting the graph induced by the threshold beta into all disconnected subgraphs (the clusters). Two nodes are connected by a link if their distance is below the specified threshold. Note that the threshold is not strict, i.e. >=.

Note that distances of value NA and NaN are ignored. This is not strictly correct but avoids computing 2^k possible solutions if there are k NA values.

The time complexity is O(n^2) with n the number of rows/columns.

Value

A factor of cluster labels (indexed 1,2,...,k).

Note

Fixme: can the time complexity be improved?

Author(s)

Christian Buchta

See Also

dist and sdists for distance computation.

Examples

## 3 clusters (1 = connected)
x <- matrix(c(1,1,0,0,0,0,
	      1,1,0,0,0,0,
	      0,0,1,1,0,0,
	      0,0,1,1,0,0,
	      0,0,0,0,1,1,
	      0,0,0,0,1,1), ncol=6)
c <- cluster.dist(as.dist(!x), beta = 0) # invert and note that 0 >= 0
c