KMEANS_FAST
A Fast K-Means Algorithm

KMEANS_FAST, a MATLAB library which handles the K-Means problem, which organizes a set of N points in M dimensions into K clusters, by Charles Elkan.

Languages:

KMEANS_FAST is available in a MATLAB version.

Related Data and Programs:

ASA058, a MATLAB library which implements the K-means algorithm of Sparks.

ASA136, a MATLAB library which implements the Hartigan and Wong clustering algorithm.

CITIES, a MATLAB library 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, a MATLAB library which demonstrates how the KMEANS algorithm can be used to reduce the number of colors or shades of gray in an image.

KMEANS, a MATLAB library which contains several different algorithms for the K-Means problem, which organizes a set of N points in M dimensions into K clusters;

kmeans_fast_test

LORENZ_CLUSTER, a MATLAB library 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.

MATLAB_KMEANS, MATLAB programs which illustrate the use of MATLAB's kmeans() function for clustering N sets of M-dimensional data into K clusters.

SAMMON_DATA, a MATLAB program which generates six sets of M-dimensional data for cluster analysis.

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

SPAETH2, 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. http://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.
• timestamp.m, prints the current YMDHMS date as a timestamp.