k-Means and Other Cost Minimization Clusterings

Two Meanings of k-Means

The phrase k-means clustering can refer to two related but different ideas. One idea is an objective function: a way to assign a cost to a proposed clustering. The other is an iterative procedure commonly used in practice to produce a clustering. Keeping these ideas separate prevents a common mistake: assuming that the procedure is guaranteed to find the clustering with the best possible objective value.

From Assignments to Cost

A k-means clustering assigns data points to clusters and gives each cluster a mean, also called its centroid. The objective function evaluates that arrangement by adding the squared Euclidean distances from the data points to the centroids of their assigned clusters. A smaller total means that the assigned points are, in aggregate, closer to their centroids according to this measure.

Distance and Assignment

Euclidean distance supplies the notion of closeness in this k-means formulation. For a data point, the relevant distance is the distance to the centroid of the cluster to which the point is assigned. That distance is then squared before it contributes to the objective's total cost. Thus, Euclidean distance plays two connected roles: it helps determine which centroid is closest during the iterative procedure, and it supplies the distances whose squared values are accumulated by the objective.

Finding a Cluster Mean

Once a cluster has been specified, its mean is computed component by component. For each coordinate, add the values from all vectors in the cluster and divide by the number of vectors. The resulting vector is not just a descriptive label: it is the value that minimizes the cluster's sum of squared Euclidean distances.

The Iterative Procedure

In the commonly used iterative approach, points are reassigned to the nearest centroid, and the centroids are recomputed from the resulting clusters. These two operations form a repeating cycle. Reassignment changes which points belong to each cluster; recomputation changes the location of each cluster mean based on its current members. The procedure therefore produces a clustering through repeated state changes rather than by directly solving every possible clustering arrangement.

Optimal Versus Obtained

It is natural to interpret k-means clustering as the clustering with the best possible objective value, but that interpretation is too strong. The optimization problem is NP-hard, and it is also NP-hard to approximate within some constant. In practice, a simpler iterative algorithm is often used instead. Its result can be locally optimal even when another clustering has a lower overall cost.

Common Reasoning Errors

• Treating the iterative algorithm as a guaranteed exact optimizer

  The optimization problem is computationally difficult, and the practical iterative procedure is not guaranteed here to find the exact optimum.

  Fix: Describe the result as the outcome of the iterative procedure unless optimality has been established separately.

• Using an arbitrary notion of closeness

  Euclidean distance supplies the notion of closeness in this formulation.

  Fix: Use Euclidean distance when describing assignments and the corresponding squared distance when describing objective cost.

• Computing a vector mean without matching coordinates

  A cluster mean is found by averaging vectors component by component.

  Fix: Average all first coordinates together, all second coordinates together, and continue this way for every coordinate.

• Confusing an evaluation quantity with an algorithm

  The objective function evaluates a proposed clustering; reassignment and centroid recomputation describe the iterative procedure.

  Fix: Use objective function for the cost definition and iterative algorithm for the process that produces a clustering.

Practice the Separation

Key Takeaways

1. The k-means objective evaluates a clustering by summing squared Euclidean distances from points to their assigned centroids.
2. Euclidean distance defines closeness for assignments, while its squared values contribute to the total cost.
3. A cluster mean is computed component by component and minimizes the cluster's sum of squared distances.
4. The commonly used iterative algorithm is a practical procedure, not the same thing as the globally optimal solution.
5. A locally optimal iterative result can have a higher cost than another possible clustering.