Compute Distances and Hierarchical Clustering for Vectors on a GPU

This function takes a set of vectors and performs clustering on them. The function will first calculate the distance between all of the pairs of vectors and then use the distances to cluster the vectors. Both of these steps are done on the GPU.

Usage

gpuDistClust(points, distmethod = "euclidean", clustmethod = "complete",
    beta = 0.5,
    precision = getOption("gputools.precision", "single"))

Arguments

points: a matrix of floating point numbers in which each row is a vector in $R^n$ space where $n$ is ncol(points).
distmethod: a string representing the name of the metric to use to calculate the distance between the vectors of 'points'. Currently supported values are: "binary", "canberra", "euclidean", "manhattan", "maximum".
clustmethod: a string representing the name of the clustering method to be applied to distances. Currently supported method names include "average", "centroid", "complete", "flexible", "flexible group", "mcquitty", "median", "single", "ward", and "wpgma".
beta: the parameter of the "flexible" and "flexible group" methods, ignored by the others; it must be below 1. The flexible-beta update of Lance and Williams (1967) is $$d(k, i \cup j) = \frac{1 - \beta}{2}\left(d(k,i) + d(k,j)\right) + \beta\, d(i,j);$$ flexible UPGMA ("flexible group", Belbin, Faith and Milligan 1992) weights $d(k,i)$ and $d(k,j)$ by the sizes of clusters $i$ and $j$ instead of equally. The default, 0.5, is the value earlier versions of gputools used (it was fixed then). Lance and Williams recommend a small negative value, beta = -0.25, which is the usual choice in the literature; positive values contract the space, so clusters tend to chain.
precision: "single" or "double": the floating point precision the GPU computes in. Single precision is the default, set with options(gputools.precision = "double"); it runs many times faster on most consumer GPUs. Results are returned as doubles either way.

Value

Copied from the native R function 'hclust' documentation. A class of type "hclust" with the following attributes.

merge: an n-1 by 2 matrix. Row i of 'merge' describes the merging of clusters at step i of the clustering. If an element j in the row is negative, then observation -j was merged at this stage. If j is positive then the merge was with the cluster formed at the (earlier) stage j of the algorithm. Thus negative entries in 'merge' indicate agglomerations of singletons, and positive entries indicate agglomerations of non-singletons. Copied from the native R function 'hclust' documentation.
order: a vector giving the permutation of the original observations suitable for plotting, in the sense that a cluster plot using this ordering and matrix 'merge' will not have crossings of the branches.
height: a set of n-1 non-decreasing real values. The clustering height: that is, the value of the criterion associated with the clustering 'method' for the particular agglomeration.

References

Lance, G. N. and Williams, W. T. (1967). A general theory of classificatory sorting strategies: 1. Hierarchical systems. The Computer Journal, 9(4), 373–380.

Belbin, L., Faith, D. P. and Milligan, G. W. (1992). A comparison of two approaches to beta-flexible clustering. Multivariate Behavioral Research, 27(3), 417–433.

Examples

if (FALSE) { # gpuAvailable()
numVectors <- 5
dimension <- 10
Vectors <- matrix(runif(numVectors*dimension), numVectors, dimension)
myClust <- gpuDistClust(Vectors, "maximum", "mcquitty")
plot(myClust)
}