Kohonen Self-Organizing Maps algorithm clarification. On each iteration, it goes trough all dataset or just a subsample?

Question

If I understood the algorithm properly it should go like this:

1. Randomly initialize SOM weights $\xi_1, ... , \xi_n$ in feature space.
2. Randomly pick sample from training set v(k) (k as in step k)
3. Find BMU (Best matching unit, closest SOM vector to feature vector) b(k)
4. Update all $\xi_m$ according to the following rule:

$$ \xi_m(k + 1) = \xi_m(k) + \alpha(k)h(k, dist(V_m, b(k))[v(k) - \xi_m(k)] $$

Where $\alpha(k)$ is the learning rate and $h(k, dist(V_m, b(k)) = exp(-\frac{dist(V_m, b(k))}{\sigma^2(k)}) $

5. Update $\alpha(k+1)= \alpha(0) exp(- k/ \lambda)$ and $\sigma(k+1) = \sigma(0) exp(-k/\lambda)$
6. Repeat from step 2 until desired number of iterations is reached.

So from my understanding execution time should be mainly dependant on number of iterations and dimension, not on size of training set.

Problem is that when playing around with (mvpa2.mappers.som.SimpleSOMMapper). I get that the execution time incresases with the size of my dataset.

data = np.random.randint(low=0, high= 255, size = (100,3))
data =data/255

%%time
som = SimpleSOMMapper((10,10), 1000, learning_rate= 0.01)
som.train(data)

Outputs wall time of 5.8 s. While,

data = np.random.randint(low=0, high= 255, size = (1000,3))
data =data/255

%%time
som = SimpleSOMMapper((10,10), 1000, learning_rate= 0.01)
som.train(data)

Outputs wall time of 58 s. What am I missing? And, most importantly how can I apply this algorithm to large data sets ? Are there better python libraries for this?

Answer 1

It seems more common to run 2-5 for every data point, not just for one random point, per iteration.

Then each iteration takes O(Ndimnumnodes) time.

Answer 2

That linear increase in training time looks fine. Every iteration you randomly pick one sample (step 2) and update it at the end (step 5). 10 times more vectors 10 times more updates and therefor it takes 10 times more time to train. I think that you can reduce number of training iterations (a.k.a epochs) since you have more data. In both cases you use 1000 iterations, but in second case you have 10 times more data. It means that in first case you make 100x1000 or 100,000 updates, where in second case you make 1,000,000 updates. For larger data sets you can reduce number of iterations.

Also you can try to use different library, neupy. It has lots of neural network algorithm, including SOM (a.k.a SOFM) and it has lots of examples. It can be faster for your problem.

Another way to speed up training is to use batch algorithm for SOM. In this case you use all your data instead of one training sample and as a consequence you updates all SOM vectors at the same time. But, I'm not sure if any python library has implementation of this approach.

Answer 3

For large data sets, try somoclu.

Your steps 1-6 form one version of the SOM algorithm. The learning rate can be reduced after every update of $\xi_m$, but typically it is only done after the complete data set has been presented to the BMU comparitor. The data set may be presented in random order, or an order determined by the user. There are also difference between 'classic' SOM and 'batch' SOM, the latter allowing greater computational efficiency.

EDIT: Having read your comment on another answer, I think you are confused over the term 'number of iterations'. One iteration in SOM typically involves presenting the whole data set to the BMU comparitor once. The order in which the data is presented to the BMU comparitor, and exactly how the SOM weights are updated are two determining factors of the variant of the SOM method being used.