K-Means Clustering With a GPU

Partitions the rows of x into k clusters by Lloyd's algorithm, as kmeans(x, centers, algorithm = "Lloyd") does, with the distances and the cluster means computed on the GPU. It is for many points and many clusters: hundreds of thousands of cells of a single-cell experiment into hundreds of clusters, say.

Usage

gpuKmeans(x, centers, iter.max = 10L, nstart = 1L,
    precision = getOption("gputools.precision", "single"))

Arguments

x

a numeric matrix, a row per point, with no missing values.

centers

the number of clusters, k, or a k-row matrix of distinct starting centres.

iter.max

the most iterations to run.

nstart

with a number of clusters, how many random starts to try; the best (least total within-cluster sum of squares) is kept.

precision

"single" or "double": the floating point precision the GPU computes in; see gpuCor.

Details

Each iteration assigns every point to its nearest centre and moves each centre to the mean of its points, until no assignment changes. The random starts are chosen exactly as kmeans chooses them, so with the same seed the two start from the same centres, and with the same starts they take the same steps: the results agree, apart from a point equally near two centres, which rounding can send either way (more often in single precision).

kmeans' default is the Hartigan-Wong algorithm, which also moves single points between clusters and usually ends at a lower within-cluster sum of squares from the same start; Lloyd's is the one that parallelises. A few random starts (nstart) make up much of the difference.

As kmeans does, it warns of a cluster left empty (its centre is then NaN) and of not converging in iter.max iterations.

Value

An object of class "kmeans", as kmeans returns, so its print and fitted methods apply.

See also

kmeans

Examples

if (FALSE) { # gpuAvailable()
set.seed(1)
x <- rbind(matrix(rnorm(2000, sd = 0.3), ncol = 2),
           matrix(rnorm(2000, mean = 2, sd = 0.3), ncol = 2))
cl <- gpuKmeans(x, 2, nstart = 5)
cl$size
cl$centers

# the same starts give the same clustering as kmeans()
set.seed(2)
g <- gpuKmeans(x, 4, precision = "double")
set.seed(2)
k <- kmeans(x, 4, algorithm = "Lloyd")
all(g$cluster == k$cluster)
}