self-organizing maps.

Kohonen Self-Organizing Maps (SOMs) are a type of neural network. Neural nets are commonly used for supervised learning, where inputs are associated with known outputs using techniques such as backpropagation. In contrast, SOMs are commonly used for unsupervised learning where no input/output pairs are specified by an instructor. They blend the concepts of vector quantization and dimensionality reduction, by clustering inputs and visualizing their topological similarities.

Demo

Click the applet and press any key to start or re-start the demo. Java 1.5 or above required.

Code

The above demo is written in Processing. I'll briefly discuss a similar, more compact implementation in Python. First, we create input vectors for several colors and store them in a list of inputs.

red = numpy.array([1, 0, 0])
orange = numpy.array([1, .5, 0])
yellow = numpy.array([1, 1, 0])
green = numpy.array([0, 1, 0])
blue = numpy.array([0, 0, 1])
purple = numpy.array([1, 0, 1])
inputs = [red, orange, yellow, green, blue, purple]
inputDimension = len(inputs[0])

Next we create our matrix of weights, where each neuron stores an associative strength to each input dimension. Each neuron starts with random weights summing to 1, provided by the stochasticmatrix function.

width = 40
height = 20
weights = numpy.zeros([height, width, inputDimension])

for x in range(height):
    for y in range(width):
        weights[x, y] = stochasticmatrix(1, inputDimension)

The main loop of the algorithm performs training by selecting a random input, computing the distance between that input and all node weights, and finding the node whose weight is closest to the input.

for epoch in range(1, epochs):
    input = inputs[random.randint(0, len(inputs)-1)]
    distance =  input - weights[:, :]
    distance2 = distance**2
    
    minIndex = distance2.sum(axis=2).argmin()
    closestX = minIndex / width
    closestY = minIndex % width
    
    neighborhoodRadius = initialNeighborhoodRadius * numpy.exp(-epoch / timeConstant)
    neighborhoodRadius2 = neighborhoodRadius**2
    learningRate = initialLearningRate * numpy.exp(-epoch / epochs)

We find all nodes within some radius of the closest node, and move their weights towards the current input by a small amount. This amount is influenced by the node's distance from the closest node, and by a learning rate. The radius that determines which nodes are considered close, as well as the learning rate, decrease with each iteration of the loop.

    for x in range(height):
        for y in range(width):
            d2 = (x - closestX)**2 + (y - closestY)**2
            
            if d2 < neighborhoodRadius2:
                influence = numpy.exp(-d2 / (2 * neighborhoodRadius2))
                weights[x, y] += learningRate * influence * distance[x, y]

The weights matrix can be visualized by passing it to matplotlib's imshow function.

Links

Kohonen gives his overview on Scholarpedia.
Another nice overview with helpful figures at the Synapse wiki.
Juha Vesanto's master's thesis on using SOMs for data mining.
The tutorial at AI Junkie inspired this code.
Generation 5 has a tutorial on content-based image retrieval using SOMs.