SOM neural networks

The SOM (self organizing maps) are some very intuitive neural networks. There are a lot of more detailed description of these networks but here is a more intuitive description.

You have a number of neurons usually arranged in a 2D or 3D grid, each neuron has an associated weight vector. The input, which is a vector of the same size as the weight vector is connected to each neuron. The natural association is that each vector is a point in an n-dimensional space. By providing, during the learning phase, an uniformly distributed number of n-points to the network the neurons will arrange themself uniformly in the n-dimensions hypercube from which the n-points come from. Otherwise said, the neurons will classify the (sub)space, each neuron representing a partition of that (sub)space. When provided with a new point the network will act such that a single neuron will fire and that neuron will be the one closer to the provided sample. The network will classify the new point in an appropriate partition.

As simple, graphical, example is the one provided bellow where a 2D space is classified using the euclidian distance. By starting with neurons with random weights the network learns itself into an uniform grid by providing random 2D points in the (1,1) – (-1, -1) square.

som2d som2d som2d som2d som2d som2d som2d som2d

My interest in these networks was primary classification related and I tried to use them for image classification. By using a weight vector consisting of the 16 point histogram in the LAB colorspace I achieved some interesting results. The method works very good for color comparison of the images but surely it is incomplete as more features are needed to classify an image: texture, object information etc.

Here are some positive results based only on color histogram space:

som image classification

I implemented everything in python and you can find the base network and the 2d example attached. I am curious about any ideas on this subject.

update: 11-02-2009

There has been some demand for the image algorithms and since the image code is quite a mess of various tries here are the ideas I had, in order to find “the way” to define “features” for an image which I can then use as coordinates in the som space:

histogram [H1, … H8] => no color data
combined color histograms [Hred1,…. Hgreen1 …] => some strange effects because the RGB is no a natural colorspace
moving to LAB space (these are the results here) => does not count for granularity (you can have the same result for on big blue blob and 10 small blue blobs)
image segmentation and applying the algorithm to most representative segments => does not count for texture
haar wavelets, …

I think that in the case of images the biggest problem is to find some “coordinates” which define them as required for the comparison and not to compare the images after based on these coordinates.

som.py

#!/usr/bin/env python
import gtk
import random, math

"""
Author: Marilen Corciovei
Version: $Id: som.py,v 1.9 2007/01/12 23:04:56 len Exp $
Description: Basic SOM algorithm implementation class
License: BSD

"""

class SOM_algorithm:

    def __init__(self, r, epochs = 100, epoch_iterations = 50, initial_learning_rate = 0.9):
        self.epochs = epochs;
        self.epoch_iterations = epoch_iterations
        self.initial_learning_rate = initial_learning_rate;
        self.r = r;
        #internal parameters
        self.time_constant = self.epochs/math.log(self.r/2)

    def radius_decay(self, t):
        """ returns the radius of influence for current epoch """
        return self.r / 2  * math.exp(-float(t/self.time_constant))

    def learning_rate_decay(self, t):
        """ returns the learning rate for current epoch """
        return self.initial_learning_rate * math.exp(-float(t/(self.epochs - t)))

    def distance(self, input, node):
        """ calculates the 'distance' in value space """
        dist = 0
        for i in range(len(input)):
            dist = dist + (input[i] - node[i]) * (input[i] - node[i])
        return dist

    def influence_decay(self, dist, radius):
        """ calculates the neiborhood function depending on dist to bmu and current radius
        both dist and radius are squared """
        return math.exp(- float(dist / 2 / radius))

class SA_two_phases(SOM_algorithm):

    def __init__(self, r, phaseOne = 200, phaseTwo = 100, epoch_iterations = 50, \
                initial_learning_rate = 0.9, phaseOne_learning_rate = 0.1, phaseTwo_learning_rate = 0):
        self.phaseOne = phaseOne
        self.phaseTwo = phaseTwo
        self.epochs = phaseOne + phaseTwo
        self.epoch_iterations = epoch_iterations
        self.r = r
        self.r2 = r/2

        self.lr0 = initial_learning_rate
        self.lr1 = phaseOne_learning_rate
        self.lr2 = phaseTwo_learning_rate
        #internal parameters
        self.radius = self.r2;
        self.radius_reduction = phaseOne / (self.r2 - 1) + 1;

        self.delta_lr = (self.lr0 - self.lr1)/self.phaseOne
        self.lr = self.lr0

    def radius_decay(self, t):
        if t > self.phaseOne:
            return 1
        # lineary discreet function
        if t % self.radius_reduction == 0:
            self.radius = self.radius - 1;
        return self.radius;

    def learning_rate_decay(self, t):
        if t < self.phaseOne:
            self.lr = self.lr - self.delta_lr
            return self.lr

        if t == self.phaseOne:
            self.lr = self.lr1
            self.delta_lr = (self.lr1 - self.lr2)/self.phaseTwo
            return self.lr

        self.lr = self.lr - self.delta_lr
        return self.lr

class SOM:
    def __init__(self, r, n, algorithm):
        """
        r * r = the square number of nodes
        n = the dimension of input
        """
        self.r = r
        self.n = n
        self.epoch = 1
        self.alg = algorithm

    def initialize_nodes(self):
        self.nodes = [[random.random() for j in range(self.n)] for i in range(self.r*self.r)]

    def initialize_samples(self):
        """ implement this if needed """

    def next_sample(self):
        v = []
        for i in range(self.n):
            v.append(random.random())
        return v

    def find_bmu(self, v):
        bmu = (0, self.alg.distance(v, self.nodes[0]))
        for i in range(1, self.r * self.r):
            dist = self.alg.distance(v, self.nodes[i])
            if dist < bmu[1]:
                bmu = (i, dist)
        return bmu

    def nodes_distance(self, i, j):
        xi = i % self.r
        yi = int(i / self.r)
        xj = j % self.r
        yj = int(j / self.r)
        return (xi - xj) * (xi - xj) + (yi - yj)*(yi - yj)

    def adjust_nodes(self, bmu, v, radius, learning_rate):
        for i in range(self.r * self.r):
            dist = self.nodes_distance(bmu[0], i)
            sqRadius = radius * radius
            if dist < sqRadius:
                influence = self.alg.influence_decay(dist,sqRadius)
                for j in range(self.n):
                    #adjust a single node
                    self.nodes[i][j] = self.nodes[i][j] + influence * learning_rate * (v[j] - self.nodes[i][j])

    def train_step(self):
        if self.epoch >= self.alg.epochs:
            print "Training completed"
            return 1
        radius = self.alg.radius_decay(self.epoch)
        learning_rate = self.alg.learning_rate_decay(self.epoch)
        print 'Epoch %d %0.2f %0.4f' %(self.epoch, radius, learning_rate)

        for i in range(self.alg.epoch_iterations):
            v = self.next_sample()
            bmu = self.find_bmu(v)
            self.adjust_nodes(bmu, v, radius, learning_rate)

        self.epoch = self.epoch + 1
        return 0

Som2d.py

#!/usr/bin/env python

import gtk
import som, random

"""
Author: Marilen Corciovei
Version: $Id: som2d.py,v 1.6 2007/01/12 23:04:56 len Exp $
Description: 2D SOM example
License: BSD

"""
class SOMDisplay(som.SOM):
    def __init__(self):
        #som.SOM.__init__(self, 16, 2, som.SOM_algorithm(16))
        som.SOM.__init__(self, 16, 2, som.SA_two_phases(16))
        self.initialize_nodes()
        self.W = 400
        self.H = self.W
        self.TIMEOUT = 20
        window = gtk.Window(gtk.WINDOW_TOPLEVEL)
        window.set_title("SOM 2d representation")
        window.connect("destroy", lambda w: gtk.main_quit())
        self.area = gtk.DrawingArea()
        self.area.set_size_request(self.W, self.H)
        window.add(self.area)
        self.area.connect("expose-event", self.draw_network)
        self.area.show()
        window.show()

    def initialize_nodes(self):
        self.nodes = []
        for i in range(self.r*self.r):
            node = []
            for j in range(self.n):
                node.append(random.random()/2 + .25)
            self.nodes.append(node)

    def next_sample(self):
        return [random.random(), random.random()]

    def timed_training(self):
        gtk.timeout_add(self.TIMEOUT, self.timer)

    def timer(self):
        if self.train_step() == 0:
            gtk.timeout_add(self.TIMEOUT, self.timer)
            self.refresh()

    def draw_network(self, area, event):
        self.style = self.area.get_style()
        self.gc = self.style.fg_gc[gtk.STATE_NORMAL]

        self.setColor(1, 1, 1)
        self.area.window.draw_rectangle(self.gc, True, 0, 0, self.W, self.H)

        self.setColor(0, 0, 0)

        #draw lines
        for x in range(self.r-1):
            for y in range(self.r-1):
                self.area.window.draw_line(self.gc, \
                                           self.nodes[x*self.r+y][0]*self.W, self.nodes[x*self.r+y][1]*self.H, \
                                           self.nodes[(x+1)*self.r+y][0]*self.W, self.nodes[(x+1)*self.r+y][1]*self.H)
                self.area.window.draw_line(self.gc, \
                                           self.nodes[x*self.r+y][0]*self.W, self.nodes[x*self.r+y][1]*self.H, \
                                           self.nodes[x*self.r+y+1][0]*self.W, self.nodes[x*self.r+y+1][1]*self.H)

        for i in range(self.r-1):
            self.area.window.draw_line(self.gc, \
                                       self.nodes[i*self.r+self.r-1][0]*self.W, self.nodes[i*self.r+self.r-1][1]*self.H, \
                                       self.nodes[(i+1)*self.r+self.r-1][0]*self.W, self.nodes[(i+1)*self.r+self.r-1][1]*self.H)
            self.area.window.draw_line(self.gc,
                                       self.nodes[(self.r-1)*self.r+i][0]*self.W, self.nodes[(self.r-1)*self.r+i][1]*self.H, \
                                       self.nodes[(self.r-1)*self.r+i+1][0]*self.W, self.nodes[(self.r-1)*self.r+i+1][1]*self.H)

        self.setColor(1, 0, 0)
        for x in range(self.r):
            for y in range(self.r):
                self.area.window.draw_rectangle(self.gc, True, \
                                                self.nodes[x*self.r+y][0]*self.W-2, self.nodes[x*self.r+y][1]*self.H-2, \
                                                4, 4)

    def setColor(self,red,green,blue,mult=65535):
        color = self.gc.get_colormap().alloc_color(int(red * mult), int(green * mult), int(blue * mult))
        self.gc.set_foreground(color)

    def refresh(self):
        self.area.emit("expose-event", gtk.gdk.Event(gtk.gdk.EXPOSE))
        self.area.queue_draw()

def main():
    net = SOMDisplay()
    net.timed_training()
    gtk.main()
    return 0

if __name__=='__main__':
    main()

som3d.py

#!/usr/bin/env python

"""
Author: Marilen Corciovei
Version: $Id: som3d.py,v 1.6 2007/01/12 23:04:56 len Exp $
Description: 3D SOM example
License: BSD

"""

import gtk
import som, random

class SOMDisplay(som.SOM):
    def __init__(self):
        som.SOM.__init__(self, 32, 3, som.SOM_algorithm(32))
        #som.SOM.__init__(self, 32, 3, som.SA_two_phases(32))
        self.initialize_nodes()
        self.initialize_samples()
        self.W = int(400/32)*32
        self.H = self.W
        self.TIMEOUT = 20
        window = gtk.Window(gtk.WINDOW_TOPLEVEL)
        window.set_title("SOM 3d representation")
        window.connect("destroy", lambda w: gtk.main_quit())
        self.area = gtk.DrawingArea()
        self.area.set_size_request(self.W, self.H)
        window.add(self.area)
        self.area.connect("expose-event", self.draw_network)
        self.area.show()
        window.show()

    def initialize_samples(self):
        self.test_data = []
        self.test_data.append([1,0,0])
        self.test_data.append([0,1,0])
        self.test_data.append([0,0,1])
        self.test_data.append([0,1,1])
        self.test_data.append([1,1,0])
        self.test_data.append([1,0,1])
        self.vsize = len(self.test_data)

    def next_sample(self):
        #ri = random.randint(0, len(self.test_data)-1)
        #return self.test_data[ri]
        return [ random.random() for i in range(3) ]

    def timed_training(self):
        gtk.timeout_add(self.TIMEOUT, self.timer)

    def timer(self):
        if self.train_step() == 0:
            gtk.timeout_add(self.TIMEOUT, self.timer)
            self.refresh()

    def draw_network(self, area, event):
        self.style = self.area.get_style()
        self.gc = self.style.fg_gc[gtk.STATE_NORMAL]
        #self.setColor(.9,0,0)
        #self.area.window.draw_rectangle(self.gc, True, 10, 10, 20, 20)
        wi = self.W/self.r
        hi = self.H/self.r

        for x in range(self.r):
            for y in range(self.r):
                self.setColor(self.nodes[x*self.r+y][0], self.nodes[x*self.r+y][1], self.nodes[x*self.r+y][2])
                self.area.window.draw_rectangle(self.gc, True, x*wi, y*hi, wi, hi)

    def setColor(self,red,green,blue,mult=65535):
        color = self.gc.get_colormap().alloc_color(int(red * mult), int(green * mult), int(blue * mult))
        self.gc.set_foreground(color)

    def refresh(self):
        self.area.emit("expose-event", gtk.gdk.Event(gtk.gdk.EXPOSE))
        self.area.queue_draw()

def main():
    net = SOMDisplay()
    net.timed_training()
    gtk.main()
    return 0

if __name__=='__main__':
    main()

Comments:

Silveira Neto - Oct 5, 2008

Where is the code? Show me the code. :-)

len - Oct 5, 2008

Sorry, lost in migration: http://www.len.ro/2008/10/plone-to-wordpress-migration/ :)

dave - Dec 2, 2008

If I wanted to do a 3D SOM, which parts of your code should be modified?: eg. nodes_distance(), I’d need to consider x,y,z to calculate the distance between nodes. Do i need to modify the radius too? thx

len - Dec 5, 2008

@dave: I’ve just added an example of 3D som in the rgb color space which might be of use to you.

mr T - Jan 3, 2009

Hi, care to share the code of your image comparing example also? (or explain how to do it ourselves:)

John Haugeland - Feb 2, 2009

Self organizing maps aren’t neural networks at all. Not all graphs that are organized by software are neural networks.

len - Feb 2, 2009

@John - I have to say I agree with you, from my perspective the SOM’s are more related to the geometry and distance but I am not very strict as to the propriety of words so I used the common classification :)

jlbit - Feb 3, 2009

@John and len - Of course they can be classified as neural network! Take a look at any publication from Kohonen. They are in fact more than that, because they use self-organizing neural networks and additional data visualization techniques.

T-mo - Feb 3, 2009

Great stuff! Do you mind posting the implementation of the image comparison as weel?

len - Feb 3, 2009

@T-mo: actually the image code is quite a mess but here are the ideas I had, in order to find some way to define “features” for an image which I can then use as coordinates in the som space: - 1 try: histogram [H1, … H8] => no color data - 2 try: combined color histograms [Hred1,…. Hgreen1 …] => some strange effects because the RGB is no a natural colorspace - 3 try: moving to LAB space (these are the results here) => does not count for granularity (you can have the same result for on big blue blob and 10 small blue blobs) - 4 try: image segmentation and applying the algorithm to most representative segments => does not count for texture - 5 try: haar wavelets, … (I’ve also added an update in the text of the post above with these thoughts)

Game AI Roundup Week #7 2009: 6 Stories, 2 Videos, 1 Paper, 1 Book — AiGameDev.com - Feb 2, 2009

[…] SOM neural networks […]

Answer My Searches » Blog Archive » Mini Searches with Answers - Dec 2, 2009

[…] These are links associated with recent searches I’ve done. They’re not difficult enough to warrant to their own posts but still super useful. Len » SOM neural networks […]

Pascal - Apr 0, 2019

Good morning, I discovered your very interesting site and I tried your samples. But I have a problem : the example som3d.py works well but the example som2d.py does not works : it says it wait an integer and get a float in line_draw. Do you know how I can solve that issue ? It is probably a problem of gtk version ; I use Ubuntu 18.04 with python 2.7. Thank you very much and felicitations for your site and your examples. Excuse my very bad english. Pascal Grandeau

update: 11-02-2009#

som.py#

Som2d.py#

som3d.py#

Comments:#

Silveira Neto - Oct 5, 2008#

len - Oct 5, 2008#

dave - Dec 2, 2008#

len - Dec 5, 2008#

mr T - Jan 3, 2009#

John Haugeland - Feb 2, 2009#

len - Feb 2, 2009#

jlbit - Feb 3, 2009#

T-mo - Feb 3, 2009#

len - Feb 3, 2009#

Game AI Roundup Week #7 2009: 6 Stories, 2 Videos, 1 Paper, 1 Book — AiGameDev.com - Feb 2, 2009#

Answer My Searches » Blog Archive » Mini Searches with Answers - Dec 2, 2009#

Pascal - Apr 0, 2019#