k-Medians Clustering Algorithm

A k-Medians Clustering Algorithm is a top-down clustering algorithm that relocates cluster centroids by minimizing median within-cluster sum of squares (median error).

• Context:
  • It can be applied by a k-Medians Clustering System (that solve s a k-Medians clustering task).
  • …
• Counter-Example(s):
  • k-Means Clustering.
  • k-Medoids Clustering.
• See: Norm (Mathematics), EM Algorithm, k-Distribution.

---

---

References

2015

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/k-medians_clustering Retrieved:2015-1-16.
  • In statistics and data mining, k-medians clustering 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 1-norm distance metric, as opposed to the square of the 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. 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 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.

---