ISODATA algoritmus - implementácia školského zadania

Na predmete Výpočtová umelá inteligencia som dostal za úlohu naprogramovať ISODATA algoritmus a naučiť ho vyhľadávať zhluky v špirále. V tomto článku opisujem spôsob, akým som toto zadanie zrealizoval.

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:

• 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