View source for Shapley–Shubik power index

{{DISPLAYTITLE:''k''-medians clustering}}
In [[statistics]] and [[data mining]], '''''k''-medians clustering'''<ref>[[Anil K. Jain|A. K. Jain]] and R. C. Dubes, ''Algorithms for Clustering Data''. Prentice-Hall, 1988.</ref><ref>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, MA: MIT Press, 1997, pp. 368&ndash;374.</ref> is a [[cluster analysis]] algorithm. It is a variation of [[k-means clustering|''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 1-[[Norm (mathematics)|norm]] distance metric, as opposed to the square of the 2-[[Norm (mathematics)|norm]] distance metric (which [[k-means clustering|''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. Formally, given a set of data points ''x'', the ''k'' centers ''c''<sub>''i''</sub> are to be chosen so as to minimize the sum of the distances from each ''x'' to the nearest&nbsp;''c''<sub>''i''</sub>.

The criterion function formulated in this way is sometimes a better criterion than that used in the [[k-means clustering|''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 [[facility location]].

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 ==

As the median is computed in each single dimension, the individual attributes will come from the data set, making this algorithm more reliable for discrete or even binary data sets. The means will however not necessarily be instances from the data set, as the attributes may come from different instances.

This algorithm is often confused with the [[k-medoids|''k''-medoids]] algorithm. However, a medoid has to be an actual instance from the dataset, while for the (multivariate) median this only holds for single attribute values. The actual median can thus be a combination of multiple instances. Given the vectors <math>(0,1)</math>, <math>(1,0)</math> and <math>(2,2)</math>, the median obviously is <math>(1,1)</math> and does not exist in the original data, and thus cannot be a medoid.

==Software==
* [[ELKI]] includes various k-means variants, including k-medians.
* [[GNU R]] includes k-medians in the "flexclust" package.
* [[Stata]] [http://www.stata.com/help13.cgi?cluster+kmedians kmedians]

==See also==
*[[cluster analysis]]
*[[k-means]]
*[[medoid]]
*[[silhouette (clustering)|silhouette]]

==References==
{{reflist}}

[[Category:Data clustering algorithms]]
[[Category:Statistical algorithms]]
[[Category:Operations research]]


{{algorithm-stub}}
{{statistics-stub}}