Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Self-Organizing Maps

English · فارسی

Self-Organizing Maps

Computer Science Dept, Ferdowsi University of Mashhad

Where this page sits

Section 14.4 of Hastie et al. (2009) (pp. 528-533) is the last clustering method of the chapter, and the book introduces it in one sentence that is also its definition: a self-organizing map (SOM) is K-means with the prototypes constrained to lie on a one- or two-dimensional manifold in feature space. The constraint is what makes the result a map: the prototypes carry grid coordinates, so every observation can be placed on a two-dimensional display, and neighbouring cells of the display hold similar observations.

Kohonen’s method is older than the machine-learning vocabulary around it, and it is still the standard tool for visualising document collections; WEBSOM, the example the section closes with, is a map of twelve thousand newsgroup articles.

What you should be able to do at the end

  • describe a SOM as a grid of prototypes and write the online update (14.46);

  • say what the neighbourhood radius and the learning rate do, and how both are scheduled;

  • write the batch update (14.48) and show that it becomes K-means when the neighbourhood shrinks to one cell;

  • judge whether the two-dimensional constraint is acceptable on a given data set by comparing reconstruction errors with K-means.

1. The model

Fix a grid, say q1×q2q_1 \times q_2 cells, and one prototype mj∈Rpm_j \in \mathbb{R}^p per cell. Each prototype carries an integer coordinate pair j∈Q1×Q2j \in Q_1 \times Q_2 - its position on the map, not in feature space. The map is a two-dimensional coordinate system, and the prototypes are points of the feature space assigned to cells of it.

The book’s picture is worth keeping: initialise the prototypes in the plane of the first two principal components and think of them as buttons sewn on that plane in a regular pattern. Fitting the SOM bends the plane so that the buttons follow the data. Distances between buttons are measured on the map, not in feature space, and that is the constraint: prototypes that are neighbours on the grid are pulled towards the same observations, so they stay neighbours in feature space.

2. The online algorithm

Observations are processed one at a time. Find the closest prototype to xix_i in Rp\mathbb{R}^p, then move it and its map-neighbours towards xix_i:

mk←mk+ε (xi−mk),for every mk with ∥j−k∥≤r.(14.46)m_k \leftarrow m_k + \varepsilon\,(x_i - m_k), \qquad \text{for every } m_k \text{ with } \lVert j - k \rVert \le r . \qquad \text{(14.46)}

The neighbourhood always contains the winner itself. The general form weights the step by the map distance,

mk←mk+h(∥j−k∥) (xi−mk),(14.47)m_k \leftarrow m_k + h(\lVert j - k \rVert)\,(x_i - m_k), \qquad \text{(14.47)}

with hh decreasing in the map distance - a Gaussian, or the indicator of a disc.

Both schedules in the book go from coarse to fine: the learning rate ε\varepsilon falls from about 1.0 to 0 over a few thousand iterations, and the radius rr falls linearly from an initial RR to 1. Early, large neighbourhoods make the map globally smooth; late, small ones let it fit local structure. This is the same annealing idea as in LVQ, and the same warning applies: the method is defined by its schedule, not by the minimisation of a criterion.

If rr is small enough that every neighbourhood is a single cell, the spatial connection is lost and the algorithm becomes online K-means: it converges to one of the local minima that K-means also finds. That is the sense in which the SOM is a constrained K-means, and it also tells you how to check the constraint on a given problem:

reconstruction error=∑i∥xi−mj(i)∥2.\text{reconstruction error} = \sum_i \lVert x_i - m_{j(i)} \rVert^2 .

It is necessarily larger for the SOM than for K-means with the same number of prototypes. If it is much larger, the two-dimensional map is a bad description of the data.

3. A worked example: three clusters on a half sphere

The book’s example is 90 points in R3\mathbb{R}^3 near the surface of a half sphere of radius 1, in three clusters near (0,1,0)(0,1,0), (0,0,1)(0,0,1) and (1,0,0)(1,0,0). The red cluster is deliberately much tighter than the other two, which is what makes the fitted map fold back on itself.

<Figure size 550x500 with 1 Axes>

The prototypes are initialised on the first two principal components, spread over the extent of the data - the “buttons sewn on the plane” of the section.

prototypes: (25, 3)  map coordinates: (25, 2)

The training loop is (14.46) verbatim: 40 passes over the 90 observations, 3600 iterations, with ε\varepsilon and rr decreased linearly over those iterations.

reconstruction error after training: 0.636
K-means with the same 25 prototypes : 0.124

The two numbers are the check the book asks for, and here they are far apart: the constrained fit costs a factor of about five. That is the price of spreading 25 buttons evenly over a surface when the data sit in three tight lumps - the grid cannot spend all of its cells on the lumps. The book’s own data are more diffuse and its SOM ends within about a quarter of K-means (Figure 14.18); the ratio is a property of the data, not of the implementation, and reading it is how you decide whether a two-dimensional map is a fair description of yours.

4. Reading the map

The display is the grid. Each cell holds the observations that are closest to its prototype, drawn at random positions inside the cell - the layout of Figure 14.16. The left panel is the initial map, the right panel the trained one.

<Figure size 900x420 with 2 Axes>

The trained map has separated the three colours into neighbouring regions, and it has done so with a smooth boundary: adjacent cells hold similar observations. That is the property K-means does not have - its labels carry no adjacency, so the same 25 centroids could be permuted at random and mean the same thing.

What the map does not show is density or size. The red cluster is much tighter than the other two, and nothing in the display says so, because the distances used for the layout are map distances. The book makes the same remark about Figure 14.16.

5. The grid in feature space

Drawing the prototypes and the lattice edges in R3\mathbb{R}^3 shows what “bending the plane” means geometrically. Where the surface has to double back to reach the tight red cluster, edges lie on top of each other - the fold of Figure 14.17.

<Figure size 600x550 with 1 Axes>

6. The reconstruction error along the way

The curve that justifies the constraint is the reconstruction error against the iteration number, with the K-means value as a horizontal line (Figure 14.18).

<Figure size 650x400 with 1 Axes>

The error falls quickly while the neighbourhood is wide - the map is being unfolded - and approaches the K-means level without reaching it. Reading the last part of the curve is the honest way to answer “is a two-dimensional map appropriate for this data?”, and it is a question about the data, not about the algorithm.

7. The batch version, and the relation to K-means

Recomputing the prototype as the weighted mean of the observations that mapped to its neighbours gives the batch SOM:

mj=∑kwkxk∑kwk,(14.48)m_j = \frac{\sum_k w_k x_k}{\sum_k w_k}, \qquad \text{(14.48)}

where the sum runs over observations xkx_k whose nearest prototype is a map-neighbour of jj, and wkw_k is 1 for a rectangular neighbourhood or falls off with the map distance. Two special cases are worth knowing:

  • a rectangular neighbourhood of radius 0 makes the update “replace each prototype by the mean of its own observations”, which is K-means;

  • a smooth ww and a shrinking radius make the batch SOM a discrete version of principal curves, the topic that follows this section in the book.

Between the online and batch versions the trade-off is the familiar one: online adapts to a stream and depends on the schedule, batch is deterministic given the assignment, converges faster, and is what most implementations use by default.

8. Where this is used

The closing example of the section is WEBSOM: 12 088 articles from comp.ai.neural-nets, each turned into a sparse vector of relative term frequencies over a dictionary of tens of thousands of words (or word pairs), optionally reduced by a randomised SVD, and then mapped onto a grid whose cells are labelled automatically from their contents. The map is a browsable index - zooming into a cell shows the articles - and that is the application the method was built for: not partitioning for its own sake, but arranging a large collection so that similar things are near each other on a page.

Summary

  • A SOM is a grid of prototypes with map coordinates; the update moves the winning prototype and its map-neighbours towards the observation (14.46).

  • The learning rate and the neighbourhood radius both decay; the schedule is part of the definition, which is why the method has no criterion to optimise.

  • With a single-cell neighbourhood the algorithm is online K-means; the batch form (14.48) with radius 0 is K-means exactly.

  • The extra error over K-means measures the price of the two-dimensional constraint, and reading it is how you decide whether the map is appropriate.

  • The output is a display in which neighbouring cells are similar - the property that makes the method useful for browsing large collections.

Exercises

  1. Train with R0=0R_0 = 0 from the start. Compare the error curve and the map with K-means labels reshaped onto the grid. What has been lost?

  2. Replace the hard neighbourhood of (14.46) by the Gaussian h(d)=exp⁡(−d2/2r2)h(d) = \exp(-d^2/2r^2) of (14.47) and compare the final reconstruction errors.

  3. Vary the grid size (3×33\times3, 5×55\times5, 8×88\times8) at fixed data. How does the error approach the K-means line, and what does the map look like at 3×33\times3?

  4. Use a hexagonal grid (six neighbours per cell instead of four). Does the display look better, and is the error different?

  5. Run the SOM on 100-dimensional data (e.g. the digits) and measure how much worse the constrained solution is. Is a two-dimensional map still defensible?

  6. Implement the batch version (14.48) with radius 1 and compare the number of iterations needed to reach the same error as the online version.

Sources

  • The definition, (14.46)-(14.48), the half-sphere example with Figures 14.15-14.18, and the WEBSOM application: §14.4 of Hastie et al. (2009), pp. 528-533.

  • The relation to K-means is the same one used on Clustering-Part2; the online-versus-batch trade-off is the one discussed in Perceptron-and-Online-Learning.

  • Kohonen’s own account of the method, and the WEBSOM papers, are the references given in the section.

References
  1. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. 10.1007/978-0-387-84858-7