k-means clustering

22.1.2 k-means clustering

The kmeans command is an efficient implementation of k-means algorithm for clustering numerical multidimensional data.

kmeans accepts one or more input arguments:
- data, which must be a list of 2D points or m-dimensional Euclidean points entered as vectors. For n such points, data should be a n× m matrix.
- Optionally, opt, a sequence of options which may contain the following:
  - k or count=k or count=k_l..k_u, where k is a positive integer specifying the number of clusters and k_l..k_u is an interval specifying minimal and maximal number of clusters (by default, unset).
  - count_inf=k_l, where k_l is a positive integer specifying the minimal number of clusters (by default, k_l=2).
  - count_sup=k_u, where k_u is a positive integer specifying the maximal number of clusters (by default, k_u=n−1).
  - limit=N, where N is a positive integer specifying the maximal number of iterations for the k-means algorithm (by default, N=100).
  - index=str, where str is a string or a list of strings specifying the index functions used to find the optimal number of clusters automatically. Available indices are: ball-hall, banfeld-raftery, calinski-harabasz, davies-bouldin, det, ksq-detW, log-det, log-ss, pbm, ratkowsky-lance, ray-turi, scott-symons, trace-W, trace-WiB and all (note that you must surround these names by double-quotes). For details, see Desgraupes (2017) (PDF). str may also take a boolean value, in which case either no index is used (str=false) or the Calinski-Harabasz index is used (str=true). By default, Hartigan’s criterion is used to determine the optimal number of clusters if k is not given.
  - output=out, where out is one of the following:
    - part, for outputting the partition of input data into clusters.
    - list, for outputting the list of cluster indices for data points (the default).
    - plot, for outputting a colored visualization of data points with additional specifications given in display option (see below). Note that this is possible only with two- and 3D data.
    - count, for outputting only the number of clusters.
    - index, for outputting the list of values of the (first) used index.
  - display=disp, where disp is a configuration for plot output (by default, points are drawn as dots of width 2).
  - color=colors, where colors is a list of colors that will be used for cluster coloring in the plot output mode (by default, the standard palette of first 16 colors is used, with white and yellow replaced for visibility).
kmeans(data ⟨,opt ⟩) returns the result as specified by the output argument (see above).
kmeans applies the Hartigan-Wong implementation of k-means algorithm, which is fast and suitable for large datasets.
kmeans does not support custom distance functions. If you want to cluster data by using a distance function other than the Euclidean distance, use the cluster command (see Section 22.1.1).
If more than one index is computed in a clustering process, then the optimal number of clusters is decided by voting: the number which was selected by most indices is used.

Example

We cluster some random gaussian data and use the Calinski-Harabasz index for choosing the optimal number of clusters.

d:=5:; n:=2500:; data:=[]:; C:=[[5,6],[14,10],[27,5],[10,21],[30,-2]]:; R:=[[2,2.5],[1.2,1],[3,3],[2,1.8],[1,0.5]]:; for k from 1 to n do j:=rand(d); x:=sample(randvar(normal,C[j][0],R[j][0])); y:=sample(randvar(normal,C[j][1],R[j][1])); data:=append(data,[x,y]); od:; kmeans(data,index="calinski-harabasz",output=plot)