k-Means Clustering

From Raw Values to Reusable Features

Suppose a learning algorithm receives an image. The raw input may contain many pixel values, but those values do not automatically provide the most useful description for predicting a label. Dictionary learning addresses this problem by searching for reusable features, sometimes called words or atoms, and representing each instance through those features.

Text already supplies a natural dictionary: its entries are words. A document can be represented by a vector whose coordinates indicate which dictionary words occur. Images do not come with an equally direct vocabulary, so dictionary learning tries to discover a collection of reusable visual features instead. For example, a learned feature might correspond to the presence of an eye. The important transfer is not that images literally contain words; it is that useful representations can be built from reusable features.

Encoding and Reconstruction

An auto-encoder learns two functions. The encoder, written as ψ, maps an input from the original d-dimensional space into a k-dimensional representation. The decoder, written as φ, maps that representation back into the original space. Learning seeks functions that make the reconstruction φ(ψ(xᵢ)) close to the original input xᵢ for the training instances.

Why Reconstruction Needs Restrictions

Reconstruction error by itself does not guarantee a useful representation. If k equals d and both functions simply return their inputs, reconstruction is perfect, but the representation has not provided a meaningful restriction or transformation. The auto-encoder must therefore constrain the encoder and decoder in some way so that copying every input is not the easiest solution.

Sparse Atoms and the k-Means Link

A sparse representation has many zero entries and only a limited number of nonzero entries. In dictionary learning, sparsity means that an instance uses only a small number of dictionary elements to describe itself. The active coordinates identify the atoms involved in representing that instance, while the values in those coordinates determine how the decoder combines them.

Clustering as an Optimization Problem

A clustering cost function assigns a positive real number to an input and a proposed clustering. The cost gives a way to score a partition: the optimization goal is to find a clustering whose cost is as small as possible. This separates two tasks that are often blended together: scoring a proposed clustering and searching for a low-scoring proposal.

The name k-means is used in two related ways. It can refer to the clustering objective: find a low-cost division of the data into k groups. It can also refer to a particular common approximation algorithm used to search for a good clustering. The algorithm should not be confused with the exact optimization problem or with the exact minimum-cost solution.

Common Reasoning Mistakes

• Treating raw input coordinates as automatically meaningful features.

  Raw values do not automatically provide a reusable vocabulary of meaningful features.

  Fix: Understand dictionary learning as a search for reusable atoms or features that can describe many instances.

• Assuming that low reconstruction error proves the representation is useful.

  An encoder and decoder can copy the input without learning a meaningful restriction or transformation.

  Fix: Ask what restriction prevents copying and what information the representation is forced to preserve.

• Describing k-means only as a procedure that divides data into k groups.

  The central formulation is an optimization task: propose a clustering, assign it a cost, and search for a low-cost proposal.

  Fix: Separate the objective being minimized from the algorithm used to search for a good solution.

• Confusing an approximation algorithm with the exact minimum-cost clustering.

  The practical algorithm seeks an approximation, while the exact optimization problem may be NP-hard.

  Fix: State whether you are discussing the objective, the exact optimum, or the approximation algorithm.

Check Your Understanding

Key Takeaways

1. Dictionary learning discovers reusable atoms so data can be represented through learned features rather than only raw input values.
2. An auto-encoder uses an encoder to create a representation and a decoder to reconstruct the original input.
3. Restrictions are necessary because reconstruction alone permits an auto-encoder to copy its inputs without learning useful features.
4. k-means uses an especially sparse code with exactly one active coordinate identifying the closest centroid; a broader sparse construction can combine several atoms.
5. Clustering uses a cost function to define the objective, while an approximation algorithm searches for a practical low-cost solution when exact optimization is difficult.