初めに
Kohonenにより提唱されたSOMですが、その仕組みを説明するサイトは多々あれど六角形マップ(ヘキサマップ)の実装に関する説明がないため、私を含め初学者にはどのように六角形マップを実装すればよいのかわからないと思います。
ネット上の少ない情報をかき集めて無事実装することが出来ましたので、今回は備忘録を兼ねて記事にしようと思います。
なぜ六角形マップなのか
SOMはノード間の距離で類似度を表現しているため、隣接するノード間の距離は全て同じであることが望ましいです。
四角形マップは実装が簡単という素晴らしい長所があるのですが、上下左右方向のノードと、斜め方向のノードとでは距離が$\sqrt{2}$倍異なることになるという欠点があります。
六角形マップでは隣接するノードの距離は全て等しいのですが、実装方法がわからず今まで避けていました...
SOMとは
SOM(Self Organizing Maps)とはKohonenにより提唱されたニューラルネットワークの一種で、
入力層と出力層の2層構造をとります。
用途としてはデータの可視化、次元圧縮、クラスタリングで使用されます。
(詳細な説明はWikiをご確認ください)
SOMの一般的なアルゴリズム
単純なSOMを例にアルゴリズムを説明します。
入力データを$X$($M×N$次元のデータ)、学習回数を$T$とすると、以下のステップを繰り返すことで学習をしていきます。
- 出力層の各ノードを乱数で初期化する
- 入力データ$X$から ベクトルを1つ選ぶ
- 2.で選択したベクトル$\boldsymbol{x}$に一番似ているノードを探索し、勝者ノードとする
- 勝者ノードの含む近傍ノードを$\boldsymbol{x}$に近づけるように学習する
- 2.-4.を全入力データに関して繰り返す
- 上記2-5を$T$回繰り返す
3.で勝者ノードを探索する際に、何をもって似ているとするかですが、一般的にはユークリッド距離が使われます。距離についてはここなどを参考にしてください。
その他、近傍や学習係数などの細かい部分は参考になりそうなサイトを挙げておきますので適宜参照してください。
http://www.brain.kyutech.ac.jp/~furukawa/data/SOMtext.pdf
http://www.sist.ac.jp/~kanakubo/research/neuro/selforganizingmap.html
出力層の生成
説明のために、出力層のサイズを8×8とします。
通常であれば8×8=64個のノードが存在することになりますが、六角形マップでは以下の図のように半分しか使いません(黄色が有効なノード、灰色が無効なノードと考えてください)。
縦方向の添え字をh、横方向の添え字をwとすると、有効なノードは以下の式で簡単に識別可能です。
if(h + w % 2 == 0)
{
// 有効なノード
}
else
{
// 無効なノード
}
そのため、六角形マップで実装するためには、SOMの一般的なアルゴリズムの1.で出力層の各ノードを初期化する際、有効ノードだけ初期化すれば良いことになります。
学習
学習では勝者ノードを含む近傍ノードを更新していくわけですが、
六角形マップでは隣接ノード間の距離は全方向で等しいため、近傍半径が1だった場合、勝者ノードと隣接するノードの計7ノードを更新すればよいことになります。
勝者ノードの座標を(X, Y)、近傍半径をrとすると、コードは以下のような感じになります。
for (int h = Y - r; h <= Y + r; h++)
{
for (int w = X - r; w <= X + r; w++)
{
// 勝者ノードと現在注目しているノードとのハミング距離を計算
hammingDist = Math.Abs(h - Y) + Math.Abs(w - X);
// ハミング距離が近傍半径以内なら更新対象
if (hammingDist <= r)
{
// 有効ノードかをチェック
if ((h + w) % 2 == 0)
{
// ノードを更新する
}
}
}
}
学習後
学習が完了するとこんな感じの六角形マップが得られます。
ソース一式
Githubにアップしておきました。
C#(UWP)で作った汚いソースですが動きはわかると思います。
参考リンク
六角形マップを実装するにあたり参考になったサイトは以下です。
http://ninagreen.hatenablog.com/entry/2015/11/14/193417
http://blogs.wankuma.com/izmktr/archive/2009/06/26/176657.aspx
https://teratail.com/questions/129504
http://keekerdc.com/2011/03/hexagon-grids-coordinate-systems-and-distance-calculations/