kmeans_fast

kmeans_fast, an Octave code which handles the K-Means problem, which organizes a set of N points in M dimensions into K clusters, by Charles Elkan.

Licensing:

The computer code and data files made available on this web page are distributed under the MIT license

Languages:

kmeans_fast is available in a MATLAB version and an Octave version.

Related Data and Programs:

kmeans_fast_test

asa058, an Octave code which implements the K-means algorithm of Sparks.

asa136, an Octave code which implements the Hartigan and Wong clustering algorithm.

cities, an Octave code which handles various problems associated with a set of "cities" on a map.

cities, a dataset directory which contains sets of data defining groups of cities.

image_quantization, an Octave code which demonstrates how the KMEANS algorithm can be used to reduce the number of colors or shades of gray in an image.

kmeans, an Octave code which contains several different algorithms for the K-Means problem, which organizes a set of N points in M dimensions into K clusters;

lorenz_ode_cluster_test, an Octave code which takes a set of N points on a trajectory of solutions to the Lorenz equations, and applies the K-means algorithm to organize the data into K clusters.

sammon_data, an Octave code which generates six sets of M-dimensional data for cluster analysis.

spaeth, a dataset directory which contains a set of test data.

spaeth22, a dataset directory which contains a set of test data.

Reference:

1. Charles Elkan,
   Using the Triangle Inequality to Accelerate k-Means,
   Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003), Washington DC, 2003.
2. https://cseweb.ucsd.edu/~elkan/fastkmeans.html, where Charles Elkan makes his paper and MATLAB source code available.
3. John Hartigan, Manchek Wong,
   Algorithm AS 136: A K-Means Clustering Algorithm,
   Applied Statistics,
   Volume 28, Number 1, 1979, pages 100-108.
4. Wendy Martinez, Angel Martinez,
   Computational Statistics Handbook with MATLAB,
   Chapman and Hall / CRC, 2002.
5. David Sparks,
   Algorithm AS 58: Euclidean Cluster Analysis,
   Applied Statistics,
   Volume 22, Number 1, 1973, pages 126-130.

Source Code:

• alldist.m computes the matrix of all pairwise distances.
• anchors.m chooses K centers by the furthest-first method.
• calcdist.m computes the distances from each point to its center.
• kmeans_fast.m carries out Elkan's fast K-means algorithm.
• r8mat_print.m, prints an R8MAT.
• r8mat_print_some.m, prints some of an R8MAT.