Keďže som chcel spraviť jednoduché používateľské rozhranie, rozhodol som sa, že zadanie implementujem ako webovú stránku. Na vstup od používateľa som využil jednoduché formulárové prvky a na vykreslenie výstupu HTML element
<canvas>
. Na naprogramovanie systému a na samotné učenie som použil jazyk JavaScript.ISODATA algoritmus
Iterative Self-Organizing Data Analysis Technique (ISODATA) algoritmy sa využívajú na zhlukovanie dát. Učenie je inkrementálne, čiže čas potrebný na naučenie pomocou takéhoto algoritma je pomerne malý v porovnaní napríklad s Kohonenovou neurónovou sieťov.Používatelské rozhranie
Systém je vytvorený ako webová stránka. Aby som sa nemusel hrať z grafikou stránky, využil som Bootstrap, vďaka čomu stránka viac lahodí oku.Vstupné dáta a nastavenia
Pre zadávanie vstupných dát (obrázka špirály) som použil jednoduchý<input type="file">
. Kedže program je písaný v JavaScripte, potreboval som nejako vstupný súbor načítať. Na to som využil rozhranie FileReader z FILE API štandardu HTML5. Na stránke html5rocks.com je o tom napísaný zaujímavý článok, z ktorého som aj vychádzal.var reader = new FileReader(); // ak načítavanie skončí reader.onload = function(e) { var bmp = e.target.result; // ... }; reader.readAsBinaryString(file_input.files[0]);
Formát vstupného obrázka som si zvolil BMP a to kvôli jednoduchému získaniu hodnôt RGB pre jednotlivé pixely. BMP formát obrázka je zložený z hlavičky a zo samotných dát. V hlavičke sú popísané základné informácie o obrázku, napríklad jeho rozmery, koľko bitové farby sú použíté, atď. Viac sa o tomto formáte dočítate na Wikipédií. Z hlavičky tiež zistíme na akej pozícií začínajú samotné dáta. Od tejto pozície sú zaradom zapísané jednotlivé pixely (pozor: farby sú zapísané v poradí blue, green, red namiesto red, green, blue).
Obrázok som potreboval prispôsobiť rozmerom plátna, preto som si určil premenné step_x a step_y, na základe ktorých vyberám len niektoré pixely z pôvodného obrázka. Tým som zabezpečil, že sa obrázok zmenší poprípade zväčší presne na rozmer plátna.
Pre učenie algoritmu potrebujem mať pozíciu každého pixela normovanú do intervalu <-1; 1>. Na to mi slúži funkcia normalize().
// lineárna normalizácia do intervalu od -1 do 1 function normalize(value) { return value / 500; }
Pre lepšie učenie sa algoritmu som rozšíril vstupné dáta o tzv. komplementárne zakódované dáta, čo sú vlastne inverzné dáta.
Tiež som si zapamätal či daný pixel patrí do obrázka (v tomto prípade do špirály) alebo nie. Rozhodoval som o tom na základe sumy farebných komponentov (RGB), ktorá keď prekročí určenú hranicu (konkrétne 500), tak pixel patrí do obrázka, inak nie.
// pozícia, kde začínajú dáta var from_id = bmp[10].charCodeAt(0); // rozmery obrázka var bmp_width = parseInt((bmp[21].charCodeAt(0).toString(16) + bmp[20].charCodeAt(0).toString(16) + bmp[19].charCodeAt(0).toString(16) + bmp[18].charCodeAt(0).toString(16)), 16); var bmp_height = parseInt((bmp[25].charCodeAt(0).toString(16) + bmp[24].charCodeAt(0).toString(16) + bmp[23].charCodeAt(0).toString(16) + bmp[22].charCodeAt(0).toString(16)), 16); // počet bitov v jednom riadku obrázka var bits_in_line = bmp_width * 3; // premenné pre prispôsobenie veľkosti obrázka var step_x = bmp_width / 500; var line_x = 0; var step_y = bmp_height / 500; var line_y = 0; for(var i=from_id, len=bmp.length; i<len; i+=3) { var train_data_length = train_data.length; // ak už sme na konci riadka, tak preskočíme na ďalší if(train_data_length > 0 && train_data_length % 500 == 0) { line_x = 0; line_y += step_y; var next_line = Math.round(line_y); // ak už máme všetky riadky, tak skončíme cyklus if(next_line > bmp_height - 1) break; // preskočíme na začiatok ďalšieho riadka i = from_id + (next_line * bmp_width * 3); } // vyberáme len niektoré pixely v riadku if((i - from_id) % bits_in_line == Math.round(line_x) * 3) { // vypočítame súčet farieb v pixely var rgb_sum = bmp[i].charCodeAt(0) + bmp[i+1].charCodeAt(0) + bmp[i+2].charCodeAt(0); var value = new Array(); // vstup value['in'] = [ normalize(train_data_length % 500), // x normalize(Math.floor(train_data_length / 500)) // y ]; // komplementárne kódovanie value['in'][2] = 1 - value['in'][0]; value['in'][3] = 1 - value['in'][1]; // výstup value['out'] = (rgb_sum > 500) ? 0 : 1; train_data.push(value); line_x += step_x; } }
Vykresľovanie výstupu
Po načítaní obrázka sú dáta uložené v premennej train_data a môžeme ich pomocou funkcie draw_background() vykresliť do plátna. Na stránke som použil dva elementy<canvas>
, ktoré sa navzájom prekrývajú. V spodnom som vykreslil vstupné dáta, čiže obrázok špirály a v hornom výsledky. Obrázok špirály som vyskreslis tak, že som postupne nakreslil malé, jednopixelové kruhy pre každý pixel na jeho pozícií.function draw_background() { context_bg.save(); for(var x=0; x<500; x++) { for(var y=0; y<500; y++) { context_bg.fillStyle = (train_data[x+(y*500)]['out'] == 1) ? '#cccccc' : '#ffffff'; context_bg.beginPath(); context_bg.arc(x, y, 1, 0, 2 * Math.PI, false); context_bg.fill(); } } context_bg.restore(); }
Následne sa spustí funkcia main(), ktorá získa hodnoty zo vstupných formulárových prvkov a spustí samotný algoritmus na učenie.
function main() { // počet vstupov var m = 2; // hranica, kedy sa má vytvárať nový zhluk var threshold = treshold_input.value; // vyčistíme plátno context.clearRect(0, 0, canvas.width, canvas.height); // ak nemáme trénovaciu množinu, tak si ju vyberieme if(train_set === undefined) train_set = get_train_set(train_size.value); // vykreslíme trénovaciu množinu draw_train_set(); weights = new Array(); // spustíme učenie var clusters = learn(m*2, 2, threshold); // vykreslíme výsledok draw_neurons(clusters); } // funkcia na vybratie trénovacej množiny z obrázka function get_train_set(train_size) { var ret = new Array(); var train_data_length = train_data.length; for(var i=0; i<train_size; i++) { // vyberieme náhodný prvok z množiny var index = Math.round(Math.random()*train_data_length); // ak patrí do obrázka, tak ho vložíme do trénovacích dát if(train_data[index]['out'] == 1) ret.push(train_data[index]); } return ret; } // funkcia na vykreslenie výsledku function draw_neurons(clusters) { context.save(); context.fillStyle = 'red'; for(var i=0, len=clusters.length; i < len; i++) { var c = clusters[i]; // vykreslenie centier zhlukov context.beginPath(); context.arc(to_pixels(c['x']), to_pixels(c['y']), 4, 0, 2 * Math.PI, false); context.fill(); // vykreslenie hraníc zhlukov var x1 = to_pixels(c['x1']); var y1 = to_pixels(c['y1']); var x2 = to_pixels(c['x2']) - x1; var y2 = to_pixels(c['y2']) - y1; context.beginPath(); context.rect(x1 - 5, y1 - 5, x2 + 10, y2 + 10); context.stroke(); } context.restore(); } // funkcia na vykreslenie trénovacej množiny function draw_train_set() { context.save(); context.fillStyle = 'blue'; // draw neurons for(var i=0, len=train_set.length; i < len; i++) { context.beginPath(); context.arc(to_pixels(train_set[i]['in'][0]), to_pixels(train_set[i]['in'][1]), 4, 0, 2 * Math.PI, false); context.fill(); } context.restore(); } // denormalizácia prvku späť na pixely function to_pixels(value) { return Math.round(value * 500); }
Učiaci algoritmus
Algoritmus podľa ktorého som implementoval učenie som prebral z dizertačnej práce Slavka Vasilica zo strany 41. Učenie je rozdelené do dvoch fáz:
Nakoniec ešte nájdeme hranice zhlukov a to tak, že prejdeme všetky vzorky, ktoré patria k zhluku a zapamätáme si z nich najvzdialenejšie od jeho centra.
- fáza inicializácie
- v tejto fáze je každá vzorka z trénovacej množiny priradená k niektorému zhluku
- fáza stabilizácie
- vo fáze stabilizácie sa jednotlivé zhluky postupne prispôsobujú, kým všetky vzorky nie sú správne zaradené
Nakoniec ešte nájdeme hranice zhlukov a to tak, že prejdeme všetky vzorky, ktoré patria k zhluku a zapamätáme si z nich najvzdialenejšie od jeho centra.
function learn(num_inputs, num_outputs, threshold) { var train_set_length = train_set.length; var weights_length = weights.length; // počet nájdených zhlukov var num_clusters = 0; // počet vzoriek, ktoré patria k zhluku var n = new Array(); // fáza inicializácie for(var s=0; s<train_set_length; s++) { var sample = train_set[s]; var sample_in = sample['in']; // nájdeme víťazný zhluk var winner = get_winner(sample_in, num_inputs); var winner_id = winner.id; // ak je to potrebné vytvoríme nový zhluk if(winner.dist > threshold) { weights.push(sample_in.slice(0)); num_clusters++; var new_id = weights.length - 1; n[new_id] = 1; sample['c'] = new_id; continue; } // zapamätáme si, do ktorého zhluku vzorka patrí sample['c'] = winner_id; // zmeníme váhy pre výsledný neurón, ktorý reprezentuje víťazný zhluk for(var i=0; i<num_inputs; i++) { weights[winner_id][i] = ((n[winner_id] * weights[winner_id][i]) / (n[winner_id] + 1)) + (sample_in[i] / (n[winner_id] + 1)); } n[winner_id]++; } // fáza stabilizácie var changed; do { changed = false; for(var s=0; s<train_set_length; s++) { var sample = train_set[s]; var sample_in = sample['in']; var winner = get_winner(sample_in, num_inputs); // ak je treba, tak vytvoríme ďalší zhluk a vzorku doňho prehodíme if(winner.dist > threshold) { weights.push(sample_in.slice(0)); num_clusters++; var new_id = weights.length - 1; n[new_id] = 1; sample['c'] = new_id; for(var i=0; i<num_inputs; i++) { weights[c][i] = ((n[c] * weights[c][i]) / (n[c] - 1)) - (sample_in[i] / (n[c] - 1)); } n[c]--; changed = true; break; } var c = sample['c']; var id = winner.id; // ak je treba, tak vzorku prehodíme do iného zhluku if(id != c) { for(var i=0; i<num_inputs; i++) { weights[id][i] = ((n[id] * weights[id][i]) / (n[id] + 1)) + (sample_in[i] / (n[id] + 1)); weights[c][i] = ((n[c] * weights[c][i]) / (n[c] - 1)) - (sample_in[i] / (n[c] - 1)); } n[id]++; n[c]--; sample['c'] = id; changed = true; break; } } } while(changed) var num_clusters = weights.length; var clusters = new Array(); // nájdeme hranice zhlukov for(var j=0; j<num_clusters; j++) { var c = weights[j]; var x_min = 1; var x_max = 0; var y_min = 1; var y_max = 0; for(var s=0; s<train_set_length; s++) { if(train_set[s]['c'] == j) { var sample_in = train_set[s]['in']; if(sample_in[0] < x_min) x_min = sample_in[0]; if(sample_in[0] > x_max) x_max = sample_in[0]; if(sample_in[1] < y_min) y_min = sample_in[1]; if(sample_in[1] > y_max) y_max = sample_in[1]; } } clusters.push({ 'x': c[0], 'y': c[1], 'x1': x_min, 'x2': x_max, 'y1': y_min, 'y2': y_max }); } return clusters; }
Vytvorená stránka
Výsledný algoritmus si môžete otestovať na mojej školskej stránke (DEMO). Keďže kód je písaný v JavaScripte, tak si ho môžete jednoducho pozrieť, a to tak, že si dáte zobraziť zdrojový kód stránky.
Výsledok učenia na špirále
Výsledok učenia algoritmu na špirále |
Žiadne komentáre:
Zverejnenie komentára