Documentation Center

  • Trial Software
  • Product Updates

kmeans

K-means clustering

Syntax

IDX = kmeans(X,k)
[IDX,C] = kmeans(X,k)
[IDX,C,sumd] = kmeans(X,k)
[IDX,C,sumd,D] = kmeans(X,k)
[...] = kmeans(...,param1,val1,param2,val2,...)

Description

IDX = kmeans(X,k) partitions the points in the n-by-p data matrix X into k clusters. This iterative partitioning minimizes the sum, over all clusters, of the within-cluster sums of point-to-cluster-centroid distances. Rows of X correspond to points, columns correspond to variables. kmeans returns an n-by-1 vector IDX containing the cluster indices of each point. By default, kmeans uses squared Euclidean distances. When X is a vector, kmeans treats it as an n-by-1 data matrix, regardless of its orientation.

[IDX,C] = kmeans(X,k) returns the k cluster centroid locations in the k-by-p matrix C.

[IDX,C,sumd] = kmeans(X,k) returns the within-cluster sums of point-to-centroid distances in the 1-by-k vector sumd.

[IDX,C,sumd,D] = kmeans(X,k) returns distances from each point to every centroid in the n-by-k matrix D.

[...] = kmeans(...,param1,val1,param2,val2,...) enables you to specify optional parameter/value pairs to control the iterative algorithm used by kmeans. Valid parameter strings are listed in the following table.

ParameterValue
'distance'

Distance measure, in p-dimensional space. kmeans minimizes with respect to this parameter. kmeans computes centroid clusters differently for the different supported distance measures.

 'sqEuclidean'

Squared Euclidean distance (default). Each centroid is the mean of the points in that cluster.

 'cityblock'

Sum of absolute differences, i.e., the L1 distance. Each centroid is the component-wise median of the points in that cluster.

 'cosine'

One minus the cosine of the included angle between points (treated as vectors). Each centroid is the mean of the points in that cluster, after normalizing those points to unit Euclidean length.

 'correlation'

One minus the sample correlation between points (treated as sequences of values). Each centroid is the component-wise mean of the points in that cluster, after centering and normalizing those points to zero mean and unit standard deviation.

 'Hamming'

Percentage of bits that differ (only suitable for binary data). Each centroid is the component-wise median of points in that cluster.

'emptyaction'

Action to take if a cluster loses all its member observations.

'error'

Treat an empty cluster as an error (default).

'drop'

Remove any clusters that become empty. kmeans sets the corresponding return values in C and D to NaN.

'singleton'

Create a new cluster consisting of the one point furthest from its centroid.

'onlinephase'

Flag indicating whether kmeans should perform an online update phase in addition to a batch update phase. The online phase can be time consuming for large data sets, but guarantees a solution that is a local minimum of the distance criterion, that is, a partition of the data where moving any single point to a different cluster increases the total sum of distances.

'on'

Perform online update (default).

'off'

Do not perform online update.

'options'

Structure specifying options for the iterative algorithm used to minimize the fitting criteria. Create the options structure with statset. Applicable statset parameters are:

DisplayLevel of display output. Choices are ‘off'(default), ‘iter', and ‘final'.
MaxIterMaximum number of iterations allowed. The default is 100.
UseParallelIf true and if a parpool of the Parallel Computing Toolbox™ is open, compute in parallel. If the Parallel Computing Toolbox is not installed, or a parpool is not open, computation occurs in serial mode. Default is default, meaning serial computation.
UseSubstreamsSet to true to compute in parallel in a reproducible fashion. Default is false. To compute reproducibly, set Streams to a type allowing substreams: 'mlfg6331_64' or 'mrg32k3a'.
StreamsA RandStream object or cell array of such objects. If you do not specify Streams, kmeans uses the default stream or streams. If you choose to specify Streams, use a single object except in the case:
  • You have an open Parallel pool

  • UseParallel is true

  • UseSubstreams is false

In that case, use a cell array the same size as the Parallel pool. If a Parallel pool is not open, then Streams must supply a single random number stream.

'replicates'

Number of times to repeat the clustering, each with a new set of initial cluster centroid positions. kmeans returns the solution with the lowest value for sumd. You can supply 'replicates' implicitly by supplying a 3D array as the value for the 'start' parameter.

'start'

Method used to choose the initial cluster centroid positions, sometimes known as seeds.

'sample'

Select k observations from X at random (default).

'uniform'

Select k points uniformly at random from the range of X. Not valid with Hamming distance.

'cluster'

Perform a preliminary clustering phase on a random 10% subsample of X. This preliminary phase is itself initialized using 'sample'.

Matrix

k-by-p matrix of centroid starting locations. In this case, you can pass in [] for k, and kmeans infers k from the first dimension of the matrix. You can also supply a 3-D array, implying a value for the 'replicates' parameter from the array's third dimension.

Examples

expand all

Partition Data into Two Clusters

Randomly generate the sample data.

rng('default') % For reproducibility
X = [randn(100,2)+ones(100,2);...
     randn(100,2)-ones(100,2)];

Partition data into two clusters. Display the final output.

opts = statset('Display','final');
[idx,ctrs] = kmeans(X,2,'Distance','city',...
              'Replicates',5,'Options',opts);
Replicate 1, 4 iterations, total sum of distances = 310.651.
Replicate 2, 9 iterations, total sum of distances = 310.651.
Replicate 3, 5 iterations, total sum of distances = 310.651.
Replicate 4, 6 iterations, total sum of distances = 310.651.
Replicate 5, 9 iterations, total sum of distances = 310.651.
Best total sum of distances = 310.651

Plot the clusters and the cluster centroids.

plot(X(idx==1,1),X(idx==1,2),'r.','MarkerSize',12)
hold on
plot(X(idx==2,1),X(idx==2,2),'b.','MarkerSize',12)
plot(ctrs(:,1),ctrs(:,2),'kx',...
     'MarkerSize',12,'LineWidth',2)
plot(ctrs(:,1),ctrs(:,2),'ko',...
     'MarkerSize',12,'LineWidth',2)
legend('Cluster 1','Cluster 2','Centroids',...
       'Location','NW')
hold off

More About

expand all

Algorithms

kmeans uses a two-phase iterative algorithm to minimize the sum of point-to-centroid distances, summed over all k clusters:

  1. The first phase uses batch updates, where each iteration consists of reassigning points to their nearest cluster centroid, all at once, followed by recalculation of cluster centroids. This phase occasionally does not converge to solution that is a local minimum, that is, a partition of the data where moving any single point to a different cluster increases the total sum of distances. This is more likely for small data sets. The batch phase is fast, but potentially only approximates a solution as a starting point for the second phase.

  2. The second phase uses online updates, where points are individually reassigned if doing so will reduce the sum of distances, and cluster centroids are recomputed after each reassignment. Each iteration during the second phase consists of one pass though all the points. The second phase will converge to a local minimum, although there may be other local minima with lower total sum of distances. The problem of finding the global minimum can only be solved in general by an exhaustive (or clever, or lucky) choice of starting points, but using several replicates with random starting points typically results in a solution that is a global minimum.

References

[1] Seber, G. A. F. Multivariate Observations. Hoboken, NJ: John Wiley & Sons, Inc., 1984.

[2] Spath, H. Cluster Dissection and Analysis: Theory, FORTRAN Programs, Examples. Translated by J. Goldschmidt. New York: Halsted Press, 1985.

See Also

| |

Was this topic helpful?