=============================== Fast K-means Clustering Toolkit

Version 0.1 (Sat May 17 17:41:11 CDT 2014) - Initial release.

WHAT: This software is a testbed for comparing variants of Lloyd's k-means clustering algorithm. It includes implementations of several algorithms that accelerate the algorithm by avoiding unnecessary distance calculations.

WHO: Greg Hamerly ([email protected], primary contact) and Jonathan Drake ([email protected]).

HOW TO BUILD THE SOFTWARE: type "make" (and hope for the best)

HOW TO RUN THE SOFTWARE: The driver is designed to take commands from standard input, usually a file that's been redirected as input:

./kmeans < commands.txt

You can read the source to find all the possible commands, but here is a summary: - threads T -- use T threads for clustering - maxiterations I -- use at most I iterations; default (or negative) indicates an unlimited number - dataset D -- use the given path name to a file as the dataset for clustering. The dataset should have a first line with the number of points n and dimension d. The next (nd) tokens are taken as the n vectors to cluster. - initialize k {kpp|random} -- use the given method (k-means++ or a random sample of the points) to initialize k centers - lloyd, hamerly, annulus, elkan, compare, sort, heap, adaptive -- perform k-means clustering with the given algorithm (requires first having initialized the centers). The adaptive algorithm is Drake's algorithm with a heuristic for choosing an initial B - drake B -- use Drake's algorithm with B lower bounds - kernel [gaussian T | linear | polynomial P] -- use kernelized k-means with the given kernel - elkan_kernel [gaussian T | linear | polynomial P] -- use kernelized k-means with the given kernel, and Elkan's accelerations - center -- give the previously-loaded dataset a mean of 0. - quit -- quit the program

Note that when a set of centers is initialized, that same set of centers is used from then on (until a new initialization occurs). So running a clustering algorithm multiple times will use the same initialization each time.

Here is an example of a simple set of commands:

dataset smallDataset.txt
initialize 10 kpp

annulus
hamerly
adaptive
heap
elkan
sort
compare

CAVEATS:

• This software has been developed and tested on Linux. Other platforms may not work. Please let us know if you have difficulties, and if possible fixes for the code.

• This software uses a non-standard pthreads function called pthread_barrier_wait(), which is implemented on Linux but not on OSX. Therefore, multithreading doesn't currently work on OSX. To turn it off, comment out the lines in the Makefile that say:

  CPPFLAGS += -DUSE_THREADS LDFLAGS += -lpthread

REFERENCES:

Phillips, Steven J. "Acceleration of k-means and related clustering algorithms." In Algorithm Engineering and Experiments, pp. 166-177. Springer Berlin Heidelberg, 2002.

Elkan, Charles. "Using the triangle inequality to accelerate k-means." In ICML, vol. 3, pp. 147-153. 2003.

Hamerly, Greg. "Making k-means Even Faster." In SDM, pp. 130-140. 2010.

Drake, Jonathan, and Greg Hamerly. "Accelerated k-means with adaptive distance bounds." In 5th NIPS Workshop on Optimization for Machine Learning. 2012.

Drake, Jonathan. "Faster k-means clustering." MS thesis, 2013.

Hamerly, Greg, and Jonathan Drake. "Accelerating Lloyd's algorithm for k-means clustering." To appear in Partitional Clustering Algorithms, Springer, 2014.