GHSOM(Growing Hierarchical Self-Organizing Map)論文まとめ

GHSOM(Growing Hierarchical Self-Organizing Map)の提案された論文についてまとめる。
なお、参考文献番号[数字]は、後の参照のために論文中のものをそのまま引用している。

概要

SOMは高次元データを2次元空間に写像することで、マップ上のクラスタを視覚的に認識できるようになるが、SOMには以下2つの問題がある。

ニューロン数やマップ構造が固定のため、入力データに応じたモデル構造を決定するが難しい
入力データ間の階層的な関係が反映されず、全てのデータが同一マップ上で表示されるため、識別が困難

上記のSOMの問題を解決するために、本論文ではGHSOMを提案する。GHSOMは独立したGSOMで構成された階層構造のモデルであり、データの階層的な関係を可視化し、直感的に解釈することが可能になる。

先行・関連研究

クラスタ抽出に関する研究

自己組織化マップをデータマイニングに活用するために、様々な改良が提案されている。U-Matrix[15]、Adaptive Coordinates、Cluster Connections[16]などは、SOMにおけるクラスタの検出と可視化に重点を置いた技術である。これらの手法では，隣接するユニット間の距離を分析したり，参照ベクトルの適応の効果を2次元の出力空間に反映させたりする。
[17]，[18]で紹介されたLabelSOM法では、さまざまなユニットの特性を，マッピングされた入力パターンの特徴から決定する．同じ特徴を持つユニットをグループ化することで，SOMの出力空間内のクラスターを特定することができる．

階層化に関する研究

The Hierarchical Feature Map[21]は、階層構造を持ったモデルであり、学習前に、層の数や各層のマップサイズも含めてモデル構造を定義し、固定する。1つのユニットにマッピングされたデータは、そのユニットの下位のマップでさらに詳細に表現される。しかし、このモデルはデータの階層構造を反映しているわけではない。
Tree-Structured SOM[22],[23]は、ユニットをツリー状に構成することで，勝者選択時の計算速度を向上させることに重点が置かれている。一見、階層的に見えるが、入力データを階層的に分解することはできず、入力データは再び1つの平面SOM上にマップされる。

マップサイズに関する研究

Incremental Grid Growing[4]
- マップの境界に新しいユニットを追加することができる。さらに、マップのユニット間の接続は、それぞれのモデルベクトルの類似性に基づいて、いくつかの閾値設定に従って追加および削除することができる。これにより、いくつかの分離された不規則な形状のマップ構造になる可能性がありうる。
Growing Grid[5]
- 学習プロセス中にユニットを行と列の単位で追加することが出来る。最初は2×2のユニットで構成されたSOMからスタートし、どこに新しいユニットを挿入するかの決定は、各ユニットに対する何らかの指標（例えば勝者カウンタ）の計算によって決定される。
Growing SOM[6]
- マップの境界ニューロンの近傍にユニットを追加することで成長する。マップの成長を制御するためにSpread Factoerを使用する。
Hypercubical SOM[24]
- SOMを2次元以上に成長させることができるため、視覚的な解釈性を犠牲にしても、データの表現力を向上させることができる。

GHSOMアルゴリズム

GHSOMの学習アルゴリズムは以下の手順に従う。

1.初期設定

あるユニットiの平均量子化誤差は、ユニットの参照ベクトル$m_i$と、$n_C$個の入力ベクトル集合$C_i$の要素である$x_j$を用いて、以下のように表せる。

$$mqe_i=\frac{1}{n_C} \cdot \sum_{x_j \in C_i}||m_i-x_j||, \ \ \ \ n_C=|C_i|, \ C_i\neq \phi \tag{1}$$

GHSOMは訓練の最初に、第0層のユニットの平均量子化誤差$mqe_0$を以下のように計算する。ここで、$n_I$は入力データ集合$I$のデータ数である。

$$mqe_0=\frac{1}{n_I} \cdot \sum_{x_i \in I}||m_0-x_i||, \ \ \ n_I=|I| \tag{2}$$

また、上記式の代わりに、以下の量子化誤差が使われる場合もある。本稿では以下の$qe$を用いてGHSOMの訓練を行う。

$$qe_i = \sum_{x_j \in C_i} ||m_i-x_j|| \tag{3}$$

$$qe_i < \tau_2 \cdot qe_0 \tag{4}$$

GHSOMは第0層のマップの下に初期サイズ$2$x$2$のGSOMを設定し、ランダムな参照ベクトルとすることで初期化される。

2.マップの成長

以下を全ての階層の全てのマップに対して行う
- あるマップ上のニューロンをSOMアルゴリズムにより更新する
- あるマップ上の各ユニットに対して、$qe$を求める
- 最も$qe$の大きいユニット$e$と、その近傍で、$e$との参照ベクトルの誤差が一番大きいユニット$d$を探索する
  $$e = \underset{i}{\textrm{argmax}} (\sum_{x_j \in C_i} ||m_i-x_j||), \ \ \ n_C=|C_i|, C_i\neq \phi \tag{5}$$
  $$d = \underset{i}{\textrm{argmax}} (||m_e-m_i||), \ \ m_i\in N_e \tag{6}$$
- $e$と$d$の間にユニットを挿入する。尚、挿入ユニットの初期値は、挟み込んでいる近傍ユニットの平均値で初期化する。
- マップ上の全てのユニットの$qe$の平均をとった、マップの平均量子化誤差$MQE_m$を以下のように定義される。ここで、$U$はマップ上のユニット集合である。
  $$MQE_m = \frac{1}{n_U} \cdot \sum_{i\in U}qe_i, \ \ n_U=|U| \tag{7}$$
- あるマップmの成長に対する停止基準は以下の式で定義される。ここで、$\tau_1$は調整用の係数、$qe_u$は階層化元のユニット$u$の量子化誤差に対応する
  $$MQE_m < \tau_1 \cdot qe_u \tag{8}$$
- SOM更新のパラメータをリセットし、次のマップの成長を行う

3.階層化

2.が全て終わると、すべてのユニットで以下の式を満たしているかを判定し、満たしていないユニットで、階層化を行う。
$$mqe_i < \tau_2 \cdot mqe_0 \ \ (平均量子化誤差の場合) \tag{9}$$
$$qe_i < \tau_2 \cdot qe_0 \ \ (量子化誤差の場合) \tag{10}$$
階層化先のマップの初期値は、階層化元のユニットとその近傍の参照ベクトルによって、(平均をとるなどで)初期化される。
階層化先のマップでは、階層化元のユニットに分類された入力データを用いて再び、マップの成長と階層化を行う。

GHSOM学習概略図

GHSOMの学習の概略図を以下に示す。全体の学習をwhileループで考えると学習の順序は以下のようになる。

1ループ目で、layer1の階層化のみを行う。
2ループ目ではlayer1のマップの成長を、停止基準まで行い、成長が終わった後、条件を満たすユニットをlayer2へ階層化させる。このとき、layer2の各マップには階層化元のユニットに分類されているデータを全て引き継ぐ形で、学習を行う。
3ループ目では、layer1に対しては何も行わず、layer2の成長を行い、その後、layer3への階層化を行う。

このように、上位層から下位層へ1層ずつ完成させていくように学習を行う。

実験

本研究では、GHSOMの有用性を2つの文書アーカイブの整理タスクに適用して実験している。

TIME Magazine：国際政治から社会的なゴシップまで様々なトピックをカバーする420の記事
Der Standard：オーストリアの日刊紙に掲載された10,000以上の記事

実験結果の考察

SOMでは表現できない階層構造を表現できている。
- 例えば、GHSOM上で見える、Europeの西側と東側の国の記事のクラスタの関係がある。
- SOM上で、左上にある7つのユニットのグループがドイツ関連の記事を表すクラスタであり、右上のクラスタが、NATO関連の記事でまとまっているが、この2つのサブクラスタの関係は、SOMで、飛び地となっている。(図はなし)
- これは、SOMのサイズが大きいため、最初の学習ステップで、広い近傍範囲の領域でマップを学習させるためであると考えられる。
- 同様のことがいくつかの小さなクラスタについても見られる。
- これらのクラスタについて、GHSOMでは最初の層であるユニットにまとめられているが、次の層でさらに細分化され、独立したサブクラスタとして分離される。
GHSOMではSOMとほぼ同レベルで詳細にトピックを分類していることにも関わらず、SOMと比較して全体的なマップサイズが縮小した。
- SOMは10×15=150ユニットに対し、GHSOMのユニット数は69ユニット。
- GHSOMでは、必要な数のマップとユニットだけが自動的に決定されるため、参照ベクトル更新や勝者ユニット計算は、SOMモデルに比べて高速になる。

結論

GHSOMは独立したGSOMで構成された階層構造のモデルである。

標準的なSOMと比較した場合のGHSOMモデルの主な利点は以下の通りである。

ユニットやマップを最小限に出来るので、全体の学習時間が大幅に短縮される。
GHSOMはデータの階層構造を明らかにするため、データの理解や分析が容易にできる。
各階層のマップサイズが小さくなりがちなため、クラスタを把握しやすくなる。
隣接するマップで表現される類似のクラスタを探索しやすくなる。

本稿では、GHSOMを文書のクラスタリングのタスクで検証した。これは、高次元でノイズが多いためクラスタリングが難しいデータであるが、文書のクラスタをうまく識別することができ、GHSOMの有意性が示された。