Kohonenová sieť
Úvod
Zadanie: Kohonenová sieť
Cieľ: Vytvoriť program v ľubovolnom programovacom jazyku, ktorý bude vyhľadavať zhluky na prezentovanej vzorke pomocou kohonenovej mapy.
Moje riešenie je napísané v jazyku v C a pre vykresľovanie využíva Gnuplot knižnicu. Ako testovacie dáta boli použité
body špirály. Pri sieťi 10x10, veľkosťi trenovacej množiny 1500 a počtu cyklov 200 bežal program 11,323 sekúnd pod operačným systemom Debian. Program je možné skompilovať
a spustiť aj pod operačným systémom Windows, problém ale spôsobuje matematická knižnica (presnejšie funkcia pow
z hlavičkového súboru math.h), ktorá je pod windowsom značne pomalšia a program je niekoľkonásobne pomalší (z mojích
testovaní pri uvedených vstupných parametroch bol program pod windowsom približne 8-krát pomalší). Ďalší problém mi pod windowsom spôsobovala funkcia
rand, ktorá pod windowsom generovala zreteľne nižšie čísla a tým pádom som mal problém s náhodným
výberom z testovacích vzoriek (different rand() results on Windows and Linux).
Okrem Gnuplot bola pre tvorbu .pbm súborov použitá aj knižnica ImageMagick.
Príklad výsledku pri uvedených vstupných parametroch:
ImageMagick
Konvertovanie obrázkov do .pbm formátu
convert.exe -compress none input.png output.pbm
Vytvorenie animovaného gif obrázku z viacerých obrázkov:
convert.exe -delay 100 input1.png input2.png inputN.png output.gif convert.exe -delay 100 input[1-9].png output.gif
Gnuplot
Pre vykresľovanie siete bola použitá knižnica Gnuplot a jednoduchý skript vytvorený pre túto knižnicu, ktorý nastavoval výstupný obrázok.
#plot.cfg set terminal jpeg size picture_width,picture_height; set output filename_output; set lmargin 0 set rmargin 0 set tmargin 0 set bmargin 0 unset xtics; unset ytics; set yrange [0:picture_height] reverse set xrange [0:picture_width] plot bg_image binary filetype=jpg with rgbimage,\ filename_input every ::0::1 with lp notitle lc rgb "green"
Tento súbor bol následne predavaný gnuplot aj spolu s definíciou použitých premenných.
sprintf(command, "gnuplot -e \"filename_output='output/plot_training_set_%d.jpg'; filename_input='output/plot_training_set_%d.txt'; picture_width=%d; picture_height=%d; bg_image='%s' \" plot_train.cfg", number, number, width, height, bg_image);
Vstupné dáta gnuplot boli vo formáte:
ciara1_bod1 ciara1_bod2 ciara2_bod1 ciara2_bod2 ciara3_bod1 ciara3_bod2
Kohonen, funkcia susednosti, zmena váh, hľadanie víťaza
Následne sú uvedené funkcie:
- pre nájdenie víťaza
- výpočet lambdy (funkcia susednosti)
- zmeny váh
// neurons - pointer to network // neurons_count - network size // inputx - position x // inputy - position y // count - number of closest neurons to find // RETURN: returns pointer to array of "count"-closest neurons Neuron** XClosestNeuron(Neuron *neurons, int neurons_count, double inputx, double inputy, int count) { Neuron **n = (Neuron**) malloc(sizeof(Neuron*) * count); double best = 0; int q,i; // Get closest n[0] = neurons; best = Distance(n[0]->weightx, n[0]->weighty, inputx, inputy); for(i = 1; i < neurons_count; i++) { if(Distance(neurons[i].weightx, neurons[i].weighty, inputx, inputy) < best) { n[0] = neurons+i; best = Distance(neurons[i].weightx, neurons[i].weighty, inputx, inputy); } } // Get rest (if needed) best = Distance(n[0]->weightx, n[0]->weighty, inputx, inputy); for(q = 1; q < count; q++) { double closest = 9999; for(i = 0; i < neurons_count; i++) { if( Distance(neurons[i].weightx, neurons[i].weighty, inputx, inputy) < closest && Distance(neurons[i].weightx, neurons[i].weighty, inputx, inputy) > best ) { n[q] = neurons+i; closest = Distance(n[q]->weightx, n[q]->weighty, inputx, inputy); } } best = closest; } return n; } double Lambda(int i, int k, int width, double h, double r) { int x_dist = abs(array2x(i, width) - array2x(k, width)); int y_dist = abs(array2y(i, width) - array2y(k, width)); double distance = sqrt( pow(x_dist, 2) + pow(y_dist, 2) ); return h * pow(EULER, -distance/r); } // n - neuron to update // http://www.willamette.edu/~gorr/classes/cs449/Unsupervised/SOM.html // Wk(new) = Wk(old) + u*N(i,k) * (x - Wk) // i-neuron is winner // // k - neuron to update // learning_rate // i - winning neuron // x,y - training set positons // neighborhood_width // neighborhood_height // network_width - width of network void UpdateWeights(Neuron *k, double learning_rate, Neuron *i, double x,double y, double neighborhood_width, double neighborhood_height, int network_width) { int watch = 0; int verbose = (k->id == watch) ? 0 : 0; //double neighborhood = Neighborhood2(k->weightx, k->weighty, i->weightx, i->weighty, neighborhood_width, neighborhood_height, verbose); double lambda = Lambda(k->id, i->id, network_width, neighborhood_height, neighborhood_width); if(k->id == watch && verbose == 1) printf("x:%.1f,y:%.1f; neigh:%.6f, set = (%.1f, %.1f);", k->weightx, k->weighty, lambda, x,y); k->weightx = k->weightx + learning_rate * lambda * (x - k->weightx); k->weighty = k->weighty + learning_rate * lambda * (y - k->weighty); if(k->id == watch && verbose == 1) printf(" new = (%.1f, %.1f)\n", k->weightx, k->weighty); }
Spustenie
Projekt obsahuje README súbor kde je opísane spúštanie programu, okrem toho obsahuje makefile pre linux aj make_win.bat pre windows. Pre správny beh je potrebné mať v priečinku projektu vytvorený adresár "output". Pod windowsom je okrem toho ešte potrebné mať v adresári projektu skopirovanú knižnicu gnuplot, pod linuxom je potrebné mať knižnicu gnuplot nainštalovanú.