Concepts / k-Means Clustering

k-Means Clustering

In dictionary learning, sparsity means that an instance uses only a small number of dictionary elements to describe itself.

  • Programming

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.

Input xᵢoriginal spaceEncoder ψd dimensions to kdimensionsRepresentationdictionary coordinatesDecoder φk dimensions to ddimensionsReconstructionφ(ψ(xᵢ))encodeproducedecoderebuild
What happens to an input as the encoder maps it to a representation and the decoder reconstructs it?
Worked example

Tracing One Representation

Describe the path of an input through an auto-encoder.

  1. 1
    Start with the input

    The input begins in the original d-dimensional space.

  2. 2
    Apply the encoder

    The encoder ψ maps the input into a k-dimensional representation whose coordinates can describe dictionary features.

  3. 3
    Apply the decoder

    The decoder φ maps the representation back into the original space.

  4. 4
    Compare

    Learning evaluates the difference between the original input and its reconstruction, using total squared reconstruction difference as the error measure.

Result

The encoder creates the representation and the decoder uses it to reconstruct the input. The representation is useful only if it is both compact or restricted and informative enough for reconstruction.

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.

Inputoriginal valuesInputoriginal valuesIdentity mappingrepresentation copies inputRestrictedrepresentationlearned feature coordinatesPerfectreconstructionno useful restrictionReconstructionpreserves usefulinformationcopyreconstructencodereconstruct
What changes when the encoder and decoder are unrestricted, and how can they reconstruct inputs without learning useful features?

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.

InputinstanceAtom AactiveEncoderselect coordinatesAtom BactiveSparse codemany zerosDecodercombine active atomsReconstructionrebuilt inputencodeproduceactivateactivatecontributecontributerebuild
How does an input move through an encoder and become a sparse combination of learned dictionary atoms?
Inputone instanceInputone instanceSingle activecoordinateone centroidAt most s activecoordinatessmall set of atomsClosest centroidone selected atomDictionary atomsselected atoms combinedencodeidentifyencodecombine
How does restricting each input to select one dictionary atom turn dictionary learning into a k-means-style assignment of points to centroids?
Worked example

The Representation Continuum

Compare the representation created by k-means with the representation created by an extended sparse construction.

  1. 1
    k-means restriction

    The encoder produces exactly one nonzero coordinate. That coordinate identifies the closest centroid, which acts as the selected dictionary atom.

  2. 2
    Sparse extension

    The restriction is relaxed to allow at most s nonzero coordinates instead of exactly one.

  3. 3
    Decoder action

    The decoder combines the selected dictionary atoms using the values in the active coordinates.

  4. 4
    Shared objective

    Both constructions aim to keep reconstruction error small while using a restricted representation.

Result

k-means is the especially sparse case in which one centroid is selected, while the extended construction can combine a small number of dictionary atoms.

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.

Proposed clusteringpartition and centroidlocationsPoint assignmentswhich centroid representseach pointCentroid locationscluster representativesClustering costpositive real numberOptimization searchseek smaller costcontainscontainscontributecontributeevaluate
How do point-to-centroid assignments and centroid locations determine the total clustering cost that optimization tries to minimize?

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.

Clusteringobjectiveminimize costApproximationalgorithmsearch methodExact minimumtheoretical optimumApproximateclusteringpractical low-cost resultdefines idealproducesis searched by
What is the difference between finding the exact minimum-cost clustering, which is NP-hard, and using an algorithm such as k-means to find an approximate solution?

Common Reasoning Mistakes

  • Common mistake

    Treating raw input coordinates as automatically meaningful features.

    What it looks like

    Assuming that a long list of image pixel values is already the best representation for predicting a label.

    Why it fails

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

    Do this instead

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

  • Common mistake

    Assuming that low reconstruction error proves the representation is useful.

    What it looks like

    Accepting an unrestricted identity mapping because it reconstructs every input perfectly.

    Why it fails

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

    Do this instead

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

  • Common mistake

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

    What it looks like

    Ignoring the cost assigned to a proposed clustering.

    Why it fails

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

    Do this instead

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

  • Common mistake

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

    What it looks like

    Claiming that using k-means necessarily means the theoretical minimum has been found.

    Why it fails

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

    Do this instead

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

Check Your Understanding

MEDIUM

An input is encoded using a representation with many zero coordinates. In one version, exactly one coordinate is active. In another version, at most s coordinates are active. Explain what each active coordinate represents, what the decoder does, and which version corresponds to the especially sparse k-means case.

Hints
  • In k-means, the single active coordinate identifies the closest centroid.
  • In the extended construction, the decoder combines the selected dictionary atoms using the active-coordinate values.
  • Focus on the difference between one selected atom and a small set of selected atoms.

What do you think happens?

If an unrestricted auto-encoder has equal input and representation dimensions and both functions simply return their inputs, what happens to reconstruction error and learned features?

  • Reconstruction can be perfect, but no meaningful restriction or transformation is learned.

  • Reconstruction must be poor because the representation has the same dimension.

  • The encoder is forced to select exactly one dictionary atom.

Reveal answer
Answer:

Reconstruction can be perfect, but no meaningful restriction or transformation is learned.

Reconstruction alone does not prevent the encoder and decoder from copying every input, so restrictions are needed.

MEDIUM

In your own words, distinguish these three ideas: the clustering cost function, the exact minimum-cost clustering, and the approximation algorithm commonly called k-means.

Hints
  • The cost function scores a proposed clustering with a positive real number.
  • The exact solution is the theoretical clustering with the smallest cost.
  • The approximation algorithm searches for a practical clustering that approaches that objective.

Key Takeaways

  1. 1
    Dictionary learning discovers reusable atoms so data can be represented through learned features rather than only raw input values.
  2. 2
    An auto-encoder uses an encoder to create a representation and a decoder to reconstruct the original input.
  3. 3
    Restrictions are necessary because reconstruction alone permits an auto-encoder to copy its inputs without learning useful features.
  4. 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. 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.

At a glance

  • A learned dictionary provides reusable features for data that lacks an obvious vocabulary.
  • The encoder selects a representation and the decoder reconstructs the input from it.
  • Sparse codes use only a small number of dictionary atoms; k-means is the one-active-atom case.
  • A clustering cost function defines what counts as a good clustering.
  • The term k-means can refer to an approximation algorithm, not necessarily the exact minimum-cost solution.

Related Topics

Related concepts

More concepts starting with K