Sunday, 16 November 2008

C# Self Organising Map (SOM)

In this post, I shall be discussing Self Organising Maps (SOM), which are also known as Kohonen maps or topographical maps. Until now, all of my posts have focussed on supervised learning, i.e. we present a set of patterns to a neural network along with the desired outputs. The network then adjusts its weights in order to recreate the correct outputs. However, suppose we do not know in advance what the outputs should be? How can we get the network to do something useful? This is called unsupervised learning. Some reasons we may choose to do this are:

  • Finding clusters

  • Dimensionality reduction

  • Finding hidden correlations

  • Data compression

  • Classification
A SOM is a two layer neural network that accepts N-dimensional input patterns and maps them to a lattice of output neurons, which represents feature space. The output map, which is typically two-dimensional, characterises the relative position of neurons with regards their neighbours, i.e. their topological properties rather than exact geometric locations. All input neurons are fully connected to all output neurons.

The training steps of a SOM are simple.
  1. Initialise the interconnecting weights with random values.

  2. Present an input pattern to the network.

  3. Choose the output neuron with the highest activation (the “winner”).

  4. Update the weights of neurons that are within the “neighbourhood” of the winner, using a relative learning factor.

  5. Reduce the learning factor monotonically.

  6. Reduce the size of the “neighbourhood” monotonically.

  7. Repeat from step two until only small updates are observed.
The spread of the neighbourhood function will initially include all neurons on the grid, gradually reducing to include only the winning neuron.

To provide an example of what to expect from a SOM, I have prepared a simple example that will attempt to group twenty-five foods into regions of similarity, based on three parameters, which are protein, carbohydrate and fat.

Therefore, the challenge for this SOM is to reduce data containing three dimensions down to two, whilst retaining meaning. It does this by automatically indentifying differentiating features that will have the greatest effect.

The input data is as follows:

Item,protein,carb,fat
Apples,0.4,11.8,0.1
Avocado,1.9,1.9,19.5
Bananas,1.2,23.2,0.3
Beef Steak,20.9,0.0,7.9
Big Mac,13.0,19.0,11.0
Brazil Nuts,15.5,2.9,68.3
Bread,10.5,37.0,3.2
Butter,1.0,0.0,81.0
Cheese,25.0,0.1,34.4
Cheesecake,6.4,28.2,22.7
Cookies,5.7,58.7,29.3
Cornflakes,7.0,84.0,0.9
Eggs,12.5,0.0,10.8
Fried Chicken,17.0,7.0,20.0
Fries,3.0,36.0,13.0
Hot Chocolate,3.8,19.4,10.2
Pepperoni,20.9,5.1,38.3
Pizza,12.5,30.0,11.0
Pork Pie,10.1,27.3,24.2
Potatoes,1.7,16.1,0.3
Rice,6.9,74.0,2.8
Roast Chicken,26.1,0.3,5.8
Sugar,0.0,95.1,0.0
Tuna Steak,25.6,0.0,0.5
Water,0.0,0.0,0.0

After running this data through the SOM, the foods were placed on a 10x10 grid representing their relative similarities. A graphical representation is shown below.



How has the feature map grouped items together, whilst crushing three dimensions into two? Well, a number of zones have formed. Water, which contains no protein, carbs or fat, has been pushed to the bottom right. Directly above in the top right hand corner, sugar, which is made almost entirely of carbs, has taken hold. In the top left corner, butter reigns supreme, being almost entirely fat. Finally, the bottom left is occupied by tuna, which has the highest protein content of the foods in my sample. The remaining foods live between these extremes, with a junk food zone occupying the centre ground.

Below is the C# code, which will allow you to recreate and modify this example. Try adding more input dimensions and see what results. It is not always obvious to see what is happening, especially with a high number of dimensions. However, eventually you will normally be able to spot the, sometimes unexpected, correlation.

using System;

using System.Collections.Generic;

using System.IO;

 

public class Map

{

    private Neuron[,] outputs;  // Collection of weights.

    private int iteration;      // Current iteration.

    private int length;        // Side length of output grid.

    private int dimensions;    // Number of input dimensions.

    private Random rnd = new Random();

 

    private List<string> labels = new List<string>();

    private List<double[]> patterns = new List<double[]>();

 

    static void Main(string[] args)

    {

        new Map(3, 10, "Food.csv");

        Console.ReadLine();

    }

 

    public Map(int dimensions, int length, string file)

    {

        this.length = length;

        this.dimensions = dimensions;

        Initialise();

        LoadData(file);

        NormalisePatterns();

        Train(0.0000001);

        DumpCoordinates();

    }

 

    private void Initialise()

    {

        outputs = new Neuron[length, length];

        for (int i = 0; i < length; i++)

        {

            for (int j = 0; j < length; j++)

            {

                outputs[i, j] = new Neuron(i, j, length);

                outputs[i, j].Weights = new double[dimensions];

                for (int k = 0; k < dimensions; k++)

                {

                    outputs[i, j].Weights[k] = rnd.NextDouble();

                }

            }

        }

    }

 

    private void LoadData(string file)

    {

        StreamReader reader = File.OpenText(file);

        reader.ReadLine(); // Ignore first line.

        while (!reader.EndOfStream)

        {

            string[] line = reader.ReadLine().Split(',');

            labels.Add(line[0]);

            double[] inputs = new double[dimensions];

            for (int i = 0; i < dimensions; i++)

            {

                inputs[i] = double.Parse(line[i + 1]);

            }

            patterns.Add(inputs);

        }

        reader.Close();

    }

 

    private void NormalisePatterns()

    {

        for (int j = 0; j < dimensions; j++)

        {

            double sum = 0;

            for (int i = 0; i < patterns.Count; i++)

            {

                sum += patterns[i][j];

            }

            double average = sum / patterns.Count;

            for (int i = 0; i < patterns.Count; i++)

            {

                patterns[i][j] = patterns[i][j] / average;

            }

        }

    }

 

    private void Train(double maxError)

    {

        double currentError = double.MaxValue;

        while (currentError > maxError)

        {

            currentError = 0;

            List<double[]> TrainingSet = new List<double[]>();

            foreach (double[] pattern in patterns)

            {

                TrainingSet.Add(pattern);

            }

            for (int i = 0; i < patterns.Count; i++)

            {

                double[] pattern = TrainingSet[rnd.Next(patterns.Count - i)];

                currentError += TrainPattern(pattern);

                TrainingSet.Remove(pattern);

            }

            Console.WriteLine(currentError.ToString("0.0000000"));

        }

    }

 

    private double TrainPattern(double[] pattern)

    {

        double error = 0;

        Neuron winner = Winner(pattern);

        for (int i = 0; i < length; i++)

        {

            for (int j = 0; j < length; j++)

            {

                error += outputs[i, j].UpdateWeights(pattern, winner, iteration);

            }

        }

        iteration++;

        return Math.Abs(error / (length * length));

    }

 

    private void DumpCoordinates()

    {

        for (int i = 0; i < patterns.Count; i++)

        {

            Neuron n = Winner(patterns[i]);

            Console.WriteLine("{0},{1},{2}", labels[i], n.X, n.Y);

        }

    }

 

    private Neuron Winner(double[] pattern)

    {

        Neuron winner = null;

        double min = double.MaxValue;

        for (int i = 0; i < length; i++)

            for (int j = 0; j < length; j++)

            {

                double d = Distance(pattern, outputs[i, j].Weights);

                if (d < min)

                {

                    min = d;

                    winner = outputs[i, j];

                }

            }

        return winner;

    }

 

    private double Distance(double[] vector1, double[] vector2)

    {

        double value = 0;

        for (int i = 0; i < vector1.Length; i++)

        {

            value += Math.Pow((vector1[i] - vector2[i]), 2);

        }

        return Math.Sqrt(value);

    }

}

 

public class Neuron

{

    public double[] Weights;

    public int X;

    public int Y;

    private int length;

    private double nf;

 

    public Neuron(int x, int y, int length)

    {

        X = x;

        Y = y;

        this.length = length;

        nf = 1000 / Math.Log(length);

    }

 

    private double Gauss(Neuron win, int it)

    {

        double distance = Math.Sqrt(Math.Pow(win.X - X, 2) + Math.Pow(win.Y - Y, 2));

        return Math.Exp(-Math.Pow(distance, 2) / (Math.Pow(Strength(it), 2)));

    }

 

    private double LearningRate(int it)

    {

        return Math.Exp(-it / 1000) * 0.1;

    }

 

    private double Strength(int it)

    {

        return Math.Exp(-it / nf) * length;

    }

 

    public double UpdateWeights(double[] pattern, Neuron winner, int it)

    {

        double sum = 0;

        for (int i = 0; i < Weights.Length; i++)

        {

            double delta = LearningRate(it) * Gauss(winner, it) * (pattern[i] - Weights[i]);

            Weights[i] += delta;

            sum += delta;

        }

        return sum / Weights.Length;

    }

}



As always, let me know what you think.

John