K-median problem: Difference between revisions
Content deleted Content added
distinguish from k-means ... definition was the same |
Distances are always nonnegative, so "absolute values of distances" is redundant. |
||
| Line 1: | Line 1: | ||
The '''''k''-median problem''' is the problem of finding ''k'' centers such that the clusters formed by them are the most compact. |
The '''''k''-median problem''' 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 |
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 ''c''<sub>''i''</sub>. |
||
The problem constitutes a better measure for the [[k-means clustering|''k''-means clustering]] algorithm, and is widely used in applications such as [[facility location]]<ref>http://www.aladdin.cs.cmu.edu/reu/mini_probes/papers/facilitylocation.ppt</ref>. |
The problem constitutes a better measure for the [[k-means clustering|''k''-means clustering]] algorithm, and is widely used in applications such as [[facility location]]<ref>http://www.aladdin.cs.cmu.edu/reu/mini_probes/papers/facilitylocation.ppt</ref>. |
||
Revision as of 17:34, 23 April 2010
The k-median problem 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 ci are to be chosen so as to minimize the sum of the distances from each x to the nearest ci.
The problem constitutes a better measure for the k-means clustering algorithm, and is widely used in applications such as facility location[1].
References
 | This statistics-related article is a stub. You can help Wikipedia by expanding it. |