k-medians clustering

In statistics, k-medians clustering^[1]^[2] is a cluster analysis algorithm. It is a variation of k-means clustering where instead of calculating the mean for each cluster to determine its centroid, one instead calculates the median. This has the effect of minimizing error over all clusters with respect to the 2-norm distance metric, as opposed to the squared 2-norm distance metric (which k-means does).

This relates directly to the k-median problem which is the problem of finding k centers such that the clusters formed by them are the most compact with respect to the 2-norm. Formally, given a set of data points x, the k centers c_i are to be chosen so as to minimize the sum of the distances from each x to the nearest c_i.

The criterion function formulated in this way is sometimes a better criterion than that used in the k-means clustering algorithm, in which the sum of the squared distances is used. The sum of distances is widely used in applications such as the facility location problem.

The proposed algorithm uses Lloyd-style iteration which alternates between an expectation (E) and maximization (M) step, making this an expectation–maximization algorithm. In the E step, all objects are assigned to their nearest median. In the M step, the medians are recomputed by using the median in each single dimension.

Medians and medoids

The median is computed in each single dimension in the

Manhattan-distance formulation of the k-medians problem, so the individual attributes will come from the dataset (or be an average of two values from the dataset). This makes the algorithm more reliable for discrete or even binary data sets. In contrast, the use of means or Euclidean-distance

medians will not necessarily yield individual attributes from the dataset. Even with the Manhattan-distance formulation, the individual attributes may come from different instances in the dataset; thus, the resulting median may not be a member of the input dataset.

This algorithm is often confused with the k-medoids algorithm. However, a medoid has to be an actual instance from the dataset, while for the multivariate Manhattan-distance median this only holds for single attribute values. The actual median can thus be a combination of multiple instances. For example, given the vectors (0,1), (1,0) and (2,2), the Manhattan-distance median is (1,1), which does not exist in the original data, and thus cannot be a medoid.

Software

ELKI includes various k-means variants, including k-medians.
FORTRAN kmedians

GNU R

includes k-medians in the "flexclust" package.

Stata kmedians

References

^ A. K. Jain and R. C. Dubes, Algorithms for Clustering Data. Prentice-Hall, 1988.
^ P. S. Bradley, O. L. Mangasarian, and W. N. Street, "Clustering via Concave Minimization," in Advances in Neural Information Processing Systems, vol. 9, M. C. Mozer, M. I. Jordan, and T. Petsche, Eds. Cambridge, Massachusetts: MIT Press, 1997, pp. 368–374.

[1] A. K. Jain and R. C. Dubes, Algorithms for Clustering Data. Prentice-Hall, 1988.

[2] P. S. Bradley, O. L. Mangasarian, and W. N. Street, "Clustering via Concave Minimization," in Advances in Neural Information Processing Systems, vol. 9, M. C. Mozer, M. I. Jordan, and T. Petsche, Eds. Cambridge, Massachusetts: MIT Press, 1997, pp. 368–374.

[1]

[2]

Medians and medoids

Software

See also

References