Is k-median supervised learning?

The clustering use described here is unsupervised; it does not learn from target labels.

Are coordinate-wise medians always the right centers?

They minimize Manhattan absolute-distance cost for a fixed cluster, not every possible distance objective.

Does convergence mean the best answer was found?

No. An alternating algorithm can settle at a suboptimal solution.

AI Glossary / Statistics and probability / Intermediate

k-median

Definition

K-median is a clustering approach that seeks k representative centers while minimizing the total distance from observations to their assigned centers. In the Manhattan-distance version used in Google's machine-learning glossary, each cluster center can be computed from coordinate-wise medians. The objective uses absolute differences rather than squared Euclidean distances. Broader optimization literature also discusses k-median under other distance metrics and restrictions on possible centers, so the distance and feasible-center definition should always be stated. This entry focuses on the Manhattan clustering interpretation.

What it means

The letter k is the number of centers chosen for the analysis. Observations are grouped according to their proximity to those centers, without needing preassigned category labels. A median is less influenced by a single extreme value than a mean for a fixed group, which can make absolute-distance objectives useful when large deviations should not receive a squared penalty. This does not make the entire clustering procedure immune to outliers: extreme points can still affect assignments, the choice of k and the total objective.

How it works

Start with k centers and assign each observation to a nearest center using Manhattan distance, the sum of absolute coordinate differences. For each resulting cluster, replace each center coordinate with a median of that coordinate's values. Repeat assignment and update steps until an appropriate stopping rule is met, handling ties and empty clusters explicitly. Each exact update minimizes the fixed cluster's absolute-distance cost, but the alternating procedure need not find the globally best clustering. Scaling features changes the geometry. If Euclidean distance rather than Manhattan distance is used, coordinate-wise medians are not generally the correct center update.

Three practical examples

Customer exploration: group customers using appropriately scaled activity measures when an absolute-distance notion of similarity fits the question.
Operational profiles: summarize usage patterns with representative median-based centers, while checking whether unusual observations deserve separate analysis.
Location planning: explore groups under a Manhattan-style travel approximation. Real routes, capacities, feasible sites and geographic barriers require additional constraints before turning those groups into a practical facility plan.

Think of it this way

Imagine placing k meeting points so that the total travel measured along horizontal and vertical streets is small. Moving a meeting point uses the middle positions in each coordinate rather than letting a very distant traveler pull the average strongly. This analogy explains the chosen distance objective; actual street networks may not match an unrestricted grid and may restrict where meeting points can be placed.

Worked example

Consider one-dimensional values 0, 1, 2, 10, 11 and 30 with k = 2. Suppose the groups are {0, 1, 2} and {10, 11, 30}. Their medians are 1 and 11. Absolute-distance costs are 1 + 0 + 1 = 2 and 1 + 0 + 19 = 20, giving total 22. Reassigning to centers 1 and 11 leaves these groups unchanged, so this is a stable alternating solution. However, the grouping {0, 1, 2, 10, 11} and {30} has centers 2 and 30, and cost 2 + 1 + 0 + 8 + 9 = 20. It is better. Thus stability does not prove global optimality. For the fixed second group in the first solution, its mean 17 gives absolute-distance cost 7 + 6 + 13 = 26, worse than the median's 20.

Illustrative case study

Fictional case study: Orchard Services clusters account usage using transaction count and service hours. Its initial analysis uses raw units, so the numerically larger transaction feature dominates distances. The team chooses and documents scaling based on the intended meaning of similarity, then compares several initializations and values of k. It also inspects unusual accounts individually. The resulting groups support descriptive planning, but the team avoids treating them as discovered customer types with permanent business meaning. A stable clustering is useful only if its representation and interpretation serve the actual task.

Common misconceptions and mistakes

Common mistakes include treating k-median as another name for k-nearest neighbors, assuming the centers must be observed data points, and using the k-means mean update while claiming to minimize an absolute-distance objective. A coordinate-wise median can combine coordinates in a way that does not correspond to an actual record; requiring representative observed records leads toward medoid-based formulations. Even-sized groups can have nonunique medians. Different initializations and tie policies can produce different solutions. More centers normally reduce the training objective, so that reduction alone cannot justify selecting a larger k.

Business use

Businesses can use k-median as an interpretable exploratory tool when their feature representation and distance measure are defensible. Compare cluster stability across samples, initializations and reasonable scaling choices. Evaluate whether centers and assignments support useful actions rather than only reporting a lower objective. Retain original units when explaining representative profiles. Where decisions require existing locations, minimum group sizes or capacity limits, use an appropriately constrained formulation rather than assuming a basic clustering result already satisfies those requirements.

Check your understanding

Why is total cost 22 not sufficient evidence of optimality in the example?

Answer: A different valid two-cluster grouping has cost 20. The first solution is stable under its local assignment and median updates, but a coordinated change in grouping improves the objective.

Related terms

k-means
Manhattan distance
Median
Clustering
k-medoids
initialization
facility location

Learn next

compare absolute-distance and squared-distance objectives on a small dataset containing an extreme point. Try multiple starting centers and feature scalings, and separate the question of optimizing a chosen objective from whether that objective represents useful similarity.

Sources

Sources: Google, Machine Learning Glossary: Clustering, https://developers.google.com/machine-learning/glossary/clustering (Manhattan k-median definition). Carnegie Mellon University, 15-381 homework 5, https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15381-s06/www/hw5/hw5.pdf (median update under absolute distance). Numerical comparison and fictional case are original illustrations.

Previous: k-means Next: K-nearest Neighbor Classification Algorithm