ASA058
the K-Means Problem

ASA058 is a FORTRAN77 library which seeks solutions of the K-Means problem, by David Sparks.

ASA058 is Applied Statistics Algorithm 58. Source code for many Applied Statistics Algorithms is available through STATLIB.

In the K-Means problem, a set of N points X(I) in M-dimensions is given. The goal is to arrange these points into K clusters, with each cluster having a representative point Z(J), usually chosen as the centroid of the points in the cluster. The energy of each cluster is

        E(J) = Sum ( all points X(I) in cluster J ) || X(I) - Z(J) ||^2
      

For a given set of clusters, the total energy is then simply the sum of the cluster energies E(J). The goal is to choose the clusters in such a way that the total energy is minimized. Usually, a point X(I) goes into the cluster with the closest representative point Z(J). So to define the clusters, it's enough simply to specify the locations of the cluster representatives.

This is actually a fairly hard problem. Most algorithms do reasonably well, but cannot guarantee that the best solution has been found. It is very common for algorithms to get stuck at a solution which is merely a "local minimum". For such a local minimum, every slight rearrangement of the solution makes the energy go up; however a major rearrangement would result in a big drop in energy.

A simple algorithm for the problem is known as "H-Means". It alternates between two procedures:

• Using the given cluster centers, assign each point to the cluster with the nearest center;
• Using the given cluster assignments, replace each cluster center by the centroid or average of the points in the cluster.

A more sophisticated algorithm, known as "K-Means", takes advantage of the fact that it is possible to quickly determine the decrease in energy caused by moving a point from its current cluster to another. It repeats the following procedure:

• For each point, move it to another cluster if that would lower the energy. If you move a point, immediately update the cluster centers of the two affected clusters.

Note: the original reference lists the input variable F as an integer workspace array. However, F is used in the CLUSTR routine exclusively as a real array. Even in single precision, this causes the routine to compute incorrect results (try it, please!); in double precision it also causes memory overwrites. The code presented here has corrected this mistake.

Languages:

ASA058 is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

ASA113, a FORTRAN77 library which implements the Banfield and Bassill clustering algorithm using transfers and swaps.

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

CITIES, a FORTRAN90 library which contains various problems associated with a set of "cities" on a map.

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

KMEANS, a FORTRAN90 library which contains several different algorithms for the K-Means problem.

LAU_NP, a FORTRAN90 library which contains heuristic algorithms for the K-center and K-median problems.

SPAETH, a FORTRAN90 library which clusters data according to various principles.

SPAETH, a dataset directory which contains sets of test data for clustering.

SPAETH2, a FORTRAN90 library which clusters data according to various principles.

SPAETH2 a dataset collection which contains sets of test data for clustering.

Author:

Original FORTRAN77 version by David Sparks; This FORTRAN77 version by John Burkardt.

Reference:

1. John Hartigan, Manchek Wong,
   Algorithm AS 136: A K-Means Clustering Algorithm,
   Applied Statistics,
   Volume 28, Number 1, 1979, pages 100-108.
2. Wendy Martinez, Angel Martinez,
   Computational Statistics Handbook with MATLAB,
   Chapman and Hall / CRC, 2002,
   ISBN: 1-58488-229-8,
   LC: QA276.4.M272.
3. David Sparks,
   Algorithm AS 58: Euclidean Cluster Analysis,
   Applied Statistics,
   Volume 22, Number 1, 1973, pages 126-130.

Source Code:

• asa058.f, the source code.
• asa058.sh, commands to compile the source code.

Examples and Tests:

• asa058_prb.f, a sample problem.
• asa058_prb.sh, commands to compile, link and run the sample program.
• asa058_prb_output.txt, the output file.
• points_100.txt, 100 2D points, used as a case study by the sample problem.

List of Routines:

• CLUSTR clusters a set of data to minimize the within-cluster sum of squares.

You can go up one level to the FORTRAN77 source codes.