sonoshouのまじめなブログ

情報系大学生からのウェブ見習い人生の記録

自己組織化写像をprocessingで実装する。 part.3

さて、前回のエントリーで自己組織化写像のアルゴリズムを紹介しました。
復習の意味も込めて、再掲致します。

1.全重みベクトルをランダマイズする
2.入力ベクトルを一つ用意する
3.各ノードを検査して、最も一致値が小さいノードを見つける。(BMU)
4.BMUの近傍のノードの重みベクトルを変更し、入力ベクトルに近付ける。
5.最大繰り返し回数に達していなければ2.に戻る。
Wikipedia:自己組織化写像の算法のステップを一部改変~

前回のエントリーでは、1.全重みベクトルをランダマイズするの実装まで完了致しました。
今日も張り切って続きを実装していきましょう!

各ユニットのデータを保存する

と、その前に前回のエントリーまでで、全重みベクトルをランダマイズすることまでは完了していたのですが、その全重みベクトルを保存するプログラムを書いていませんでした……。
(ぶっつけ本番でプログラムを書いて行っているので、このように内容が前後することがあるかもです。未熟者で申し訳ございません><;)
というわけで、今日ははランダマイズした各ユニットのデータを保存するプログラムを書くところから始めていきましょう。

プログラムの全体像は以下のようになります。

void setup()
{
  size(780, 810);

  int randR, randG, randB;
  int tempR, tempG, tempB;
  int[][][] unitArray = new int[28][23][3];  // <- add

  //1. set random vectors
  for (int i = 0; i < 28; i++)
  {
    for (int j = 0; j < 23; j++)
    {
      randR = int(random(256));
      randG = int(random(256));
      randB = int(random(256));

      unitArray[i][j][0] = randR;  // <- add
      unitArray[i][j][1] = randG;
      unitArray[i][j][2] = randB;

      if (i % 2 == 0)
      {
        hexagon(j * 34.64102, i * 30, 20, color(randR,randG,randB), color(0, 0, 0));
        } else {
        hexagon(j * 34.64102 + 17.32051 , i * 30, 20, color(randR,randG,randB), color(0, 0, 0));
      }      
    }      
  }
}

// hexagon
void hexagon(float centerX, float centerY, float size, color fillColor, color strokeColor)
{
  final float COS[] = {0, -0.8660254, -0.8660254, 0, 0.86602524, 0.86602524};
  final float SIN[] = {1, 0.5,  -0.5, -1, -0.5, 0.5};

  final float RADIUS = size;

  // color
  fill(fillColor);
  stroke(strokeColor);

  beginShape();
  for(int i = 0; i < 6; i++)
  {
    float tx = COS[i] * RADIUS + centerX;
    float ty = SIN[i] * RADIUS + centerY;
    vertex(tx, ty);
  }
  endShape(CLOSE);
}

前回のプログラムと比較して、

  • 各ユニットのRGBの値を格納する3次元配列unitArrayを定義した。
  • unitArrayにランダマイズしたRGBの値を格納した。

以上2点を書き加えました。
出力は変わりませんが、この変更により、
各ユニットのRGBの値が3次元配列unitArrayに格納され、いつでも参照できるようになりました。

2.入力ベクトルを一つ用意する

さて、気を取り直しまして、Wikipedia:自己組織化写像の算法のステップの続きを実装しましょう!
次は、2.入力ベクトルを一つ用意するですね。

しかし、これは簡単です。
以下の1文で用意することが可能です。

//2. set a known input vector  // <- add
int[] inputArray = {255,0,0}; 

これは赤の入力ベクトルを用意するためのプログラムです。
後々、ここのプログラムは、

//2. set a random input vector  // <- add
int[] inputArray = {int(random(256)),int(random(256)),int(random(256))}

と変更する予定です。
しかし、最初は本当に実装できているかを確認するために、
既知の入力ベクトルを用意することとします。

3.各ノードを検査して、最も一致値が小さいノードを見つける。(BMU)

さて、ここから少々面倒なプログラムとなります。
BMUはBest Maching Unitの略です。
すなわち、入力ベクトルとユニットベクトルの最も距離が近いユニットを指します。
今回はこのBMUを各ノードを検査することで見つけます。

早速、見つけている部分のコードを見てみましょう。

//3. find Best Maching Unit  // <- add
int BMUi = 0, BMUj = 0;  
float tempDistance;
float minDistance = Float.MAX_VALUE;

for (int i = 0; i < 28; i++)
{
    for (int j = 0; j < 23; j++)
    {
      tempDistance = calculateDistance(unitArray[i][j], inputArray);

      if(minDistance > tempDistance)
      {
        minDistance = tempDistance;
        BMUi = i;
        BMUj = j;
      }
    }
}

// culcate distance
float calculateDistance(int[] unitArray1, int[] unitArray2)
{
  float distance;

  distance = sqrt(
             sq(unitArray1[0] - unitArray2[0]) + 
             sq(unitArray1[1] - unitArray2[1]) +
             sq(unitArray1[2] - unitArray2[2]));

  return distance;
}

少々ややこしいことをやっているように見えるかもしれませんね。
今回は、

  • setup関数の中に記述するプログラム
  • calculateDistance関数(2つの引数のベクトルの距離を返す関数)

と大きく分けて2つのブロックに分かれて記述されています。

setup関数の中に記述するプログラム

こちらは全ノードを検査する必要がありますので、
for文を2回まわしてすべてのユニットを探索しています。

各ユニットを回す際、そのユニットベクトルと入力ベクトルの距離を求めています。
そして、今まで発見していた入力ベクトルと最も近い距離minDistanceと、
そのユニットベクトルと入力ベクトルの距離tempDistanceを比較して、
tenpDistanceの方が近かった場合、tempDistanceはminDistanceとなります。
このときのiとjの値がBMUのiとjの値となります。
この処理をすべてのユニットに施すことで、BMUのiとjを探すことができます。

calculateDistance関数

calculateDistance関数は引数のベクトルを2つとり、両者間の距離をfloat型で返す関数です。
求め方はユークリッド距離を用いています。 ユークリッド距離は三平方の定理などにも登場するメジャーな距離の測定法です。
詳しくはこちらのホームページをご参照ください。
通信用語の基礎知識:ユークリッド距離

まとめると

はい!というわけで、1.2.3.の実装が終わりましたので、
全体のプログラムを動かしてみましょう!

void setup()
{
  size(780, 810);

  int randR, randG, randB;
  int tempR, tempG, tempB;
  int[][][] unitArray = new int[28][23][3];  // <- add

  //1. set random vectors
  for (int i = 0; i < 28; i++)
  {
    for (int j = 0; j < 23; j++)
    {
      randR = int(random(256));
      randG = int(random(256));
      randB = int(random(256));

      unitArray[i][j][0] = randR;  // <- add
      unitArray[i][j][1] = randG;
      unitArray[i][j][2] = randB;

      if (i % 2 == 0)
      {
        hexagon(j * 34.64102, i * 30, 20, color(randR,randG,randB), color(0, 0, 0));
        } else {
        hexagon(j * 34.64102 + 17.32051 , i * 30, 20, color(randR,randG,randB), color(0, 0, 0));
      }      
    }      
  }

  //2. set a random input vector  // <- add
  int[] inputArray = {255,0,0};   

  //3. find Best Maching Unit  // <- add
  int BMUi = 0, BMUj = 0;  
  float tempDistance;
  float minDistance = Float.MAX_VALUE;

  for (int i = 0; i < 28; i++)
  {
    for (int j = 0; j < 23; j++)
    {
      tempDistance = calculateDistance(unitArray[i][j], inputArray);

      if(minDistance > tempDistance)
      {
        minDistance = tempDistance;
        BMUi = i;
        BMUj = j;
      }
    }
  }

  print("BMU = (" + BMUi + "." + BMUj + ")");

}

void draw()
{

}

// hexagon
void hexagon(float centerX, float centerY, float size, color fillColor, color strokeColor)
{
  final float COS[] = {0, -0.8660254, -0.8660254, 0, 0.86602524, 0.86602524};
  final float SIN[] = {1, 0.5,  -0.5, -1, -0.5, 0.5};

  final float RADIUS = size;

  // color
  fill(fillColor);
  stroke(strokeColor);

  beginShape();
  for(int i = 0; i < 6; i++)
  {
    float tx = COS[i] * RADIUS + centerX;
    float ty = SIN[i] * RADIUS + centerY;
    vertex(tx, ty);
  }
  endShape(CLOSE);
}

// culcate distance
float calculateDistance(int[] unitArray1, int[] unitArray2)
{
  float distance;

  distance = sqrt(
             sq(unitArray1[0] - unitArray2[0]) + 
             sq(unitArray1[1] - unitArray2[1]) +
             sq(unitArray1[2] - unitArray2[2]));

  return distance;
}

実行結果は以下のようになります。

BMU = (4.1)

これは、すべてのユニットのうち最も赤いユニットが(4.1)であるということを意味しています。
それでは、色付きハニカム構造を見てみましょう。

f:id:sonoshou:20130621022206p:plain

配列は0番目から始めることに注意して数えていくと、
上から5番目、左から2番目のユニットが赤色であることがわかります。

入力ベクトルは{255,0,0}の赤色だったので、これに近い色を発見できていることが確認できました。

今回は以上です。

続きます。

自己組織化写像をprocessingで実装する。 part.4