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ú.

Discussion