Self-Organizing Maps with Google’s TensorFlow

[This post assumes that you know the basics of Google’s TensorFlow library. If you don’t, have a look at my earlier post to get started.]

kohonen1

A Self-Organizing Map, or SOM, falls under the rare domain of unsupervised learning in Neural Networks. Its essentially a grid of neurons, each denoting one cluster learned during training. Traditionally speaking, there is no concept of neuron ‘locations’ in ANNs. However, in an SOM, each neuron has a location, and neurons that lie close to each other represent clusters with similar properties. Each neuron has a weightage vector, which is equal to the centroid of its particular cluster.

AI-Junkie’s post does a great job of explaining how an SOM is trained, so I won’t re-invent the wheel.

The Code

Here’s my code for a 2-D version of an SOM. Its written with TensorFlow as its core training architecture: (Its heavily commented, so look at the inline docs if you want to hack/dig around)


import tensorflow as tf
import numpy as np


class SOM(object):
    """
    2-D Self-Organizing Map with Gaussian Neighbourhood function
    and linearly decreasing learning rate.
    """

    #To check if the SOM has been trained
    _trained = False

    def __init__(self, m, n, dim, n_iterations=100, alpha=None, sigma=None):
        """
        Initializes all necessary components of the TensorFlow
        Graph.

        m X n are the dimensions of the SOM. 'n_iterations' should
        should be an integer denoting the number of iterations undergone
        while training.
        'dim' is the dimensionality of the training inputs.
        'alpha' is a number denoting the initial time(iteration no)-based
        learning rate. Default value is 0.3
        'sigma' is the the initial neighbourhood value, denoting
        the radius of influence of the BMU while training. By default, its
        taken to be half of max(m, n).
        """

        #Assign required variables first
        self._m = m
        self._n = n
        if alpha is None:
            alpha = 0.3
        else:
            alpha = float(alpha)
        if sigma is None:
            sigma = max(m, n) / 2.0
        else:
            sigma = float(sigma)
        self._n_iterations = abs(int(n_iterations))

        ##INITIALIZE GRAPH
        self._graph = tf.Graph()

        ##POPULATE GRAPH WITH NECESSARY COMPONENTS
        with self._graph.as_default():

            ##VARIABLES AND CONSTANT OPS FOR DATA STORAGE

            #Randomly initialized weightage vectors for all neurons,
            #stored together as a matrix Variable of size [m*n, dim]
            self._weightage_vects = tf.Variable(tf.random_normal(
                [m*n, dim]))

            #Matrix of size [m*n, 2] for SOM grid locations
            #of neurons
            self._location_vects = tf.constant(np.array(
                list(self._neuron_locations(m, n))))

            ##PLACEHOLDERS FOR TRAINING INPUTS
            #We need to assign them as attributes to self, since they
            #will be fed in during training

            #The training vector
            self._vect_input = tf.placeholder("float", [dim])
            #Iteration number
            self._iter_input = tf.placeholder("float")

            ##CONSTRUCT TRAINING OP PIECE BY PIECE
            #Only the final, 'root' training op needs to be assigned as
            #an attribute to self, since all the rest will be executed
            #automatically during training

            #To compute the Best Matching Unit given a vector
            #Basically calculates the Euclidean distance between every
            #neuron's weightage vector and the input, and returns the
            #index of the neuron which gives the least value
            bmu_index = tf.argmin(tf.sqrt(tf.reduce_sum(
                tf.pow(tf.sub(self._weightage_vects, tf.pack(
                    [self._vect_input for i in range(m*n)])), 2), 1)),
                                  0)

            #This will extract the location of the BMU based on the BMU's
            #index
            slice_input = tf.pad(tf.reshape(bmu_index, [1]),
                                 np.array([[0, 1]]))
            bmu_loc = tf.reshape(tf.slice(self._location_vects, slice_input,
                                          tf.constant(np.array([1, 2]))),
                                 [2])

            #To compute the alpha and sigma values based on iteration
            #number
            learning_rate_op = tf.sub(1.0, tf.div(self._iter_input,
                                                  self._n_iterations))
            _alpha_op = tf.mul(alpha, learning_rate_op)
            _sigma_op = tf.mul(sigma, learning_rate_op)

            #Construct the op that will generate a vector with learning
            #rates for all neurons, based on iteration number and location
            #wrt BMU.
            bmu_distance_squares = tf.reduce_sum(tf.pow(tf.sub(
                self._location_vects, tf.pack(
                    [bmu_loc for i in range(m*n)])), 2), 1)
            neighbourhood_func = tf.exp(tf.neg(tf.div(tf.cast(
                bmu_distance_squares, "float32"), tf.pow(_sigma_op, 2))))
            learning_rate_op = tf.mul(_alpha_op, neighbourhood_func)

            #Finally, the op that will use learning_rate_op to update
            #the weightage vectors of all neurons based on a particular
            #input
            learning_rate_multiplier = tf.pack([tf.tile(tf.slice(
                learning_rate_op, np.array([i]), np.array([1])), [dim])
                                               for i in range(m*n)])
            weightage_delta = tf.mul(
                learning_rate_multiplier,
                tf.sub(tf.pack([self._vect_input for i in range(m*n)]),
                       self._weightage_vects))                                         
            new_weightages_op = tf.add(self._weightage_vects,
                                       weightage_delta)
            self._training_op = tf.assign(self._weightage_vects,
                                          new_weightages_op)                                       

            ##INITIALIZE SESSION
            self._sess = tf.Session()

            ##INITIALIZE VARIABLES
            init_op = tf.initialize_all_variables()
            self._sess.run(init_op)

    def _neuron_locations(self, m, n):
        """
        Yields one by one the 2-D locations of the individual neurons
        in the SOM.
        """
        #Nested iterations over both dimensions
        #to generate all 2-D locations in the map
        for i in range(m):
            for j in range(n):
                yield np.array([i, j])

    def train(self, input_vects):
        """
        Trains the SOM.
        'input_vects' should be an iterable of 1-D NumPy arrays with
        dimensionality as provided during initialization of this SOM.
        Current weightage vectors for all neurons(initially random) are
        taken as starting conditions for training.
        """

        #Training iterations
        for iter_no in range(self._n_iterations):
            #Train with each vector one by one
            for input_vect in input_vects:
                self._sess.run(self._training_op,
                               feed_dict={self._vect_input: input_vect,
                                          self._iter_input: iter_no})

        #Store a centroid grid for easy retrieval later on
        centroid_grid = [[] for i in range(self._m)]
        self._weightages = list(self._sess.run(self._weightage_vects))
        self._locations = list(self._sess.run(self._location_vects))
        for i, loc in enumerate(self._locations):
            centroid_grid[loc[0]].append(self._weightages[i])
        self._centroid_grid = centroid_grid

        self._trained = True

    def get_centroids(self):
        """
        Returns a list of 'm' lists, with each inner list containing
        the 'n' corresponding centroid locations as 1-D NumPy arrays.
        """
        if not self._trained:
            raise ValueError("SOM not trained yet")
        return self._centroid_grid

    def map_vects(self, input_vects):
        """
        Maps each input vector to the relevant neuron in the SOM
        grid.
        'input_vects' should be an iterable of 1-D NumPy arrays with
        dimensionality as provided during initialization of this SOM.
        Returns a list of 1-D NumPy arrays containing (row, column)
        info for each input vector(in the same order), corresponding
        to mapped neuron.
        """

        if not self._trained:
            raise ValueError("SOM not trained yet")

        to_return = []
        for vect in input_vects:
            min_index = min([i for i in range(len(self._weightages))],
                            key=lambda x: np.linalg.norm(vect-
                                                         self._weightages[x]))
            to_return.append(self._locations[min_index])

        return to_return

A few points about the code:

1) Since my post on K-Means Clustering, I have gotten more comfortable with matrix operations in TensorFlow. You need to be comfortable with matrices if you want to work with TensorFlow (or any data flow infrastructure for that matter, even SciPy). You can code pretty much any logic or operational flow with TensorFlow, you just need to be able to build up complex functionality from basic components(ops), and structure the flow of data(tensors/variables) well.

2) It took quite a while for me to build the whole graph in such a way that the entire training functionality could be enclosed in a single op. This op is called during each iteration, for every vector, during training. Such an implementation is more in line with TensorFlow’s way of doing things, than my previous attempt with clustering.

3) I have used a 2-D grid for the SOM, you can use any geometry you wish. You would just have to modify the _neuron_locations method appropriately, and also the method that returns the centroid outputs. You could return a dict that maps neuron location to the corresponding cluster centroid.

4) To keep things simple, I haven’t provided for online training. You could do that by having bounds for the learning rate(s).

Sample Usage

I have used PyMVPA’s example of RGB colours to confirm that the code does work. PyMVPA provides functionality to train SOMs too (along with many other learning techniques).

Here’s how you would do it with my code:


#For plotting the images
from matplotlib import pyplot as plt

#Training inputs for RGBcolors
colors = np.array(
     [[0., 0., 0.],
      [0., 0., 1.],
      [0., 0., 0.5],
      [0.125, 0.529, 1.0],
      [0.33, 0.4, 0.67],
      [0.6, 0.5, 1.0],
      [0., 1., 0.],
      [1., 0., 0.],
      [0., 1., 1.],
      [1., 0., 1.],
      [1., 1., 0.],
      [1., 1., 1.],
      [.33, .33, .33],
      [.5, .5, .5],
      [.66, .66, .66]])
color_names = \
    ['black', 'blue', 'darkblue', 'skyblue',
     'greyblue', 'lilac', 'green', 'red',
     'cyan', 'violet', 'yellow', 'white',
     'darkgrey', 'mediumgrey', 'lightgrey']

#Train a 20x30 SOM with 400 iterations
som = SOM(20, 30, 3, 400)
som.train(colors)

#Get output grid
image_grid = som.get_centroids()

#Map colours to their closest neurons
mapped = som.map_vects(colors)

#Plot
plt.imshow(image_grid)
plt.title('Color SOM')
for i, m in enumerate(mapped):
    plt.text(m[1], m[0], color_names[i], ha='center', va='center',
             bbox=dict(facecolor='white', alpha=0.5, lw=0))
plt.show()

Here’s a sample of the output you would get (varies each time you train, but the color names should go to the correct locations in the image):

figure_1

Advertisements

36 thoughts on “Self-Organizing Maps with Google’s TensorFlow

  1. Thank you for another great article. Where else
    may anybody get that type of info in such a perfect approach of writing?
    I’ve a presentation next week, and I am at the search for such
    info.

    1. ==================== RESTART: C:/Users/user/Desktop/1.py ====================
      Traceback (most recent call last):
      File “C:/Users/user/Desktop/1.py”, line 229, in
      som = SOM(20, 30, 3, 400)
      File “C:/Users/user/Desktop/1.py”, line 80, in __init__
      tf.pow(tf.sub(self._weightage_vects, tf.pack(
      AttributeError: module ‘tensorflow’ has no attribute ‘sub’

      can hope me? plz

      1. TensorFlow 1.0 changed some method names which broke backwards compatability. But it is easy to fix. Just replace the following words in the code and it should work:

        tf.sub => tf.subtract
        tf.mul => tf.multiply
        tf.neg => tf.negative
        tf.initialize_all_variables => tf.global_variables_initializer

        I found this information and more about migrating to 1.0 here:
        https://www.tensorflow.org/install/migration

  2. Hi, thanks for this clear explanation. I used your model for a MOOC form Kadenze about Deep Learning. If you are interested i can send you the notebook.

  3. i was wondering if you could help me out.. why eveyr example of some is only showing input data of a 3d vector i have not seen an example of a 4d or 5d vector, i read the theory an it says that som should work for N-dimensions, im not sure how to proceed then if want go beyond 3d… thanks in advance and thanks for your article.

    1. Hi SomNoob,
      Even I am stuck with the same problem as yours(Data has around 20 dimensions) Although am able to get the centroids, not sure how to visualize the image_grid. Did you find a workaround?

  4. I got “TypeError: Input ‘size’ of ‘Slice’ Op has type int32 that does not match type int64 of argument ‘begin’.”

    Anyone knows how to fix it?

    1. bmu_loc = tf.reshape(tf.slice(self._location_vects, slice_input,
      tf.constant(np.array([1, 2], dtype=np.int64))),
      [2])

  5. Thanks for your code, that I am studying as an introduction to TensorFlow. I have a question concerning lines 86-89, where you extract the coordinates of the BMU (bmu_loc). What don’t you just use self._location_vects[bmu_index] ?

  6. Thanks for your code, but I’m having a problem of performance. I am running with GPU and it’s taking more than 40 seconds for this example. Do you know what can be the problem?

  7. I tried running this piece of code with the latest TF (1.0.1) and i reckon this piece of great information has been written for a previous version of TF. It seems that many of the math functions (i.e. .sub and .mul) have been replaced. There is also some type conversion stuff that throws errors, of which the first few I tried to tackle were related to mismatching datatypes between int32 and int64. And I tested this with your simple example code.

      1. Isn’t this algorithm used fraudulent or anomaly detection?. I came across this algorithm in quite a few research papers.

  8. Thanks for sharing the code,Request share code for GrowingSOM, if available or any alternative of GSOM for clustering applications in sensor networks.

  9. Soo, what was the point of this? All you did was take 15 pre-labeled colors and spread them out on a 2D surface. That seemed like a disapointingly trivial task. Did the program actually learn anything? SOM is called an unsupervised learning algorithm, so I expected it to be able to find some interesting information in an unlabeled dataset. Your example data then seems pointless since it was just a list of arbitrary colors with no interesting information hidden in them. Am I missing something here? Or is SOM simply just a way to visualize data and not actually learn anything about it?

    1. SOMs in general are just a clustering algorithm, so their effectiveness depends on your data and application. This post was not about ‘discovering’ something interesting as such, but implementing that algorithm in Tensorflow (back when TF was pretty new for me). In fact this post taught me more about TF than SOMs :-). The colour example I have used is a standard one for SOMs, so I went along with that one to test if my SOM implementation worked.

      1. Ok. Clustering is what I want, so this might be good afterall. I guess it only seemed so trivial because of the simple example data you used. If I use your code, but feed it a larger dataset with 100 dimensions which I expect it to contain 2 or 3 distinct classes, should it then create 2 or 3 distinct “blobs”, and then be able to map new vectors to the blob which it resembles most? (What I want is essentially unsupervised classification, where I don’t necessarily know how many separate clusters there can be.)

      2. SOMs might not be the best algorithm for your purpose in that case. They are chiefly used as a dimensionality reduction technique (in this case, converting arbitrary vectors to a 2D representation). However, you could use them if your number of expected classes is high- say ~20. In such a case, you could just use a 5×5 SOM and then use it as a classifier after training. Some of the 25 nodes might be very close to each other in the original feature space, so you might need some manual labelling.

      3. Using a 5×5 SOM is sort of analogous to using KMeans with K=25, because we assume each output node to respond to a corresponding cluster? I have been playing with your code now and when setting the number of nodes to just the number of classes that I expect from the data, f.ex. 1×4, it “classifies” the datapoints nicely into these separate nodes and gives similar result as KMeans with K=4. This could be a good alternative to KMeans, but I still have to assume the number of clusters/classes of course.

        “Some of the 25 nodes might be very close to each other in the original feature space, so you might need some manual labelling.” Can I even use manual labeling with SOM?

        I have tested SOM with many nodes also and then my test data does indeed gather in meaningful “blobs”, like I hoped.

        So if I use many nodes, much more than the number of classes I expect, is SOM similar to Autoencoder in what it achieves? They are both used for dimensionality reduction, trying to find the new (reduced) features that best represents the data. Then I still need to use an other algorithm after the dimensionality reduction to perform the actual classification, but it might be easier than it was with the original high-dimension data.

  10. I sincerely appreciate your pioneering work 🙂 Can I ask you one question?
    I am also interested in a network that extends the SOM further. I would like to ask first whether Tensorflow is a good tool for this. if so, why? And I wonder if the TensorBoard will work properly when using structures such as SOM.

    Thank you-

  11. Hi ,
    Could you guide me as to how to how to implement SOM in tensor flow for data in a database that has multiple columns\features?
    For instance for each input I am having a matrix as the data, where each column is a feature and the row represents the inner dimension of that feature. How to train the SOM using tensor flow in that case?. And how to determine what number of nodes or neurons would be appropriate to train the data? Your guidance would be highly appreciated.

    Thank you.

    1. Are you saying that each datapoint has a feature matrix instead of a feature vector? You can just flatten the matrix into a vector.

      >>> feature = np.array([[1,2,3], [10,20,30], [100,200,300]])
      >>> feature = feature.flatten()
      >>> feature
      array([ 1, 2, 3, 10, 20, 30, 100, 200, 300])

      1. Thanks Paul. But what I had meant is that for each input I am having multiple features and each of them is a vector of the same dimension. In such a case would flattening and combining the different features into a single vector workout ?.

      2. Yes, that is what I understood and my answer still stands.

        Unless the matrix you are describing is representing an image or something similar where the position of the values in the matrix in relation to eachother matters. In that case you should use a convolutional neural network instead. Flattening will still work, but a convolutional network will just be better. If your feature vectors are in no particular order then flattening is fine.

        If you still think I have misunderstood the form of your data you will have to show me a sample.

      3. There is a considerable amount of relation of each of the feature values. That is to say, each row corresponding to these multiple feature/columns represent the features recorded at that instant. For Eg:

        Column1 Column2 Column3 Column4
        Device id Cell id recordStarttime recordEndTime
        device 1 Cell 1 Ts1 Te1
        device 1 Cell 2 Ts2 Te2
        device 1 Cell 3 Ts3 Te3
        device 2 Cell 1 Ts2 Te3

        and so on ..

  12. Ok, that is a different matter then. If the rows in your matrix represent the flow of time then each of your datapoints is essentially a “video” (time signal) where there is information in the order of the rows that you would lose by flattening. Then I think you need a convolutional network. I don’t know exactly how that works, though, or if it is possible in any way to do it unsupervised. As far as I know SOM can only handle 1D vectors. But what I know about SOM is mostly just based on this article as I am just figuring out myself.

  13. HI. Uhm if you were to put boundaries for the learning algorithm where would you place them in the code?

  14. Nice code.
    My question is, is there any way I can “force” the algorithm NOT to assign more than one data point to a single [X,Y] output?
    For example, I am interested to having a 20*30 grid (m=20, n=30), and have 600 colors as input. How can I force the algorithm to assign each input color to a unique location in the grid? In this case each [X,Y] location will end up being assigned with one color.

    Thanks.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s