Self organizing maps vs k-means, when the SOM has a lot of nodes

Question

On Wikipedia it says:

It has been shown that while self-organizing maps with a small number of nodes behave in a way that is similar to k-means, larger self-organizing maps rearrange data in a way that is fundamentally topological in character.

What does that means exactly? I understood the first part: A SOM with small nodes behaves like a k-means algorithm. But for a larger SOM, what does it mean by "fundamentally topological in character"? It makes no sense to me.

So Basically my questions are:

1. What is "..fundamentally topological in character..."?
2. What is the difference between a SOM and k-means, when the SOM has a high number of nodes?

Answer 1

The idea behind a SOM is that you're mapping high-dimensional vectors onto a smaller dimensional (typically 2-D) space. You can think of it as clustering, like in K-means, with the added difference that vectors that are close in the high-dimensional space also end up being mapped to nodes that are close in 2-D space.

SOMs therefore are said to "preserve the topology" of the original data, because the distances in 2-D space reflect those in the high-dimensional space. K-means also clusters similar data points together, but its final "representation" is hard to visualise because it's not in a convenient 2-D format.

A typical example is with colours, where each of the data points are 3-D vectors that represent R,G,B colours. When mapped to a 2-D SOM you can see regions of similar colours begin to develop, which is the topology of the colour space. I like this tutorial as an explanation, with added code snippets.

Answer 2

You've already accepted an answer, but I think that part of the answer needs to be made clearer...

A SOM is always topological in nature. It is essentially embedding a 2D manifold in the higher-dimensional space of your data.

At an intuitive level, both k-means and SOM are moving nodes towards denser areas of your space. With k-means, the nodes move freely, with no direct relationship to each other. And a node that is responsible for zero or one data points is degenerate and the k-means algorithm must avoid this situation.

With SOM, when a node moves towards the data, it pulls neighboring nodes in the 2D manifold along with it. This naturally maintains a topology embedded in the data space. And a node can be responsible for 0 or 1 data points with no problem. (Such nodes are sitting in empty space, pulled by their neighbors in all directions. In some sense, they might be an artifact of a manifold, but in another sense they are interpolating between denser space.)

So there isn't some kind of phase change where a SOM goes from not topological to topological. Rather, as the number of SOM nodes increases, you get a higher-resolution manifold.

If you fit a 2x3 (6 node) SOM to the Iris data, you'll get something much more like k-means with 6 nodes than if you fit a 10x15 (150 node) SOM. So I think of it that a low-resolution SOM looks more like the non-topological k-means that is doing a similar task, but a high-resolution SOM's topological nature will be more visible.

Answer 3

The case for a low number of nodes is similar to K-means because you are forcing every vector to match an existing node, acting as a prototype/centroid, without any marging for divergence.

In the case of a high number of nodes, there is margin for slowing transitioning zones, which mimic the space among protopypes/centroids, thus modeling the transformed topological space among samples. This way, the relative distances are 'in some sense' preserved.