カスタムクラスタリング4:自己組織化マップ、微妙さ、改善、t-SNEとの比較

パート1-アフィニティ伝播
パート2-DBSCAN
パート3-時系列クラスタリング
パート4-自己組織化マップ(SOM)
パート5-成長中の神経ガス(GNG)

自己組織化マップ(SOM、Kohonen自己組織化マップ)はおなじみの古典的なデザインです。 彼らは、機械学習コースでソースを覚えていることがよくあります。「そして、ニューラルネットワークはそのようにできます」。 SOMは、1990年から2000年の離陸を生き延びました。その後、彼らは素晴らしい未来を予測し、新しい修正を作成しました。 ただし、21世紀には、SOMは徐々に背景に向かっています。 自己組織化マップの分野での新しい開発はまだ進行中ですが(主にフィンランドのコホネンの発祥地)、地図データのネイティブな視覚化とクラスタリングの分野でも、コホネンはt-SNEよりも劣っています。

SOMの複雑さを理解し、それらが当然忘れられているかどうかを調べてみましょう。



アルゴリズムの重要なアイデア


手短に言えば、標準のSOM学習アルゴリズムを思い出します[1]。 以下 Xd\回N)入力データを含む行列です。ここで、 N-データセット内の要素の数、および d-データディメンション。 W-重みの行列( d\回M)、ここで M-マップ内のニューロンの数。  eta-学習速度、 \シ-協力係数(下記参照)、 E-時代の数。

DM\回M)は、レイヤー内のニューロン間の距離のマトリックスです。 最後の行列は次と同じではないことに注意してください \左 | vecw私は- vecwj\右 |ニューロンには2つの距離があります :レイヤー内の距離( D)および値の差。

また、ニューロンは正方形グリッド上に「張られている」かのように便宜上描かれていることが多いが、これはニューロンがテンソルとして格納されることを意味するものではないことに注意してください  sqrtM\回 sqrtM\回d。 グリッドは D

すぐに紹介します \ガそして  alpha-学習率の減衰と協力の減衰の指標。 厳密に言えばそれらは義務ではありませんが、それらなしではまともな結果を得るのはほとんど不可能です。

アルゴリズム1(標準SOM学習アルゴリズム):
ログイン: X eta\シ\ガ alphaE
  1. 初期化するには W
  2. E回:

    1. インデックスリストをランダムに並べ替えます:= shuffle( [01\ドN-2N-1]
    2. それぞれについて 私はdx注文から:
      1.  vecx=X[私はdx]// Xからランダムなベクトルを取得します
      2. 私は= arg m私はnj left | vecx- vecwj r私はght |//最も近いニューロンの番号を見つけます
      3.  foralljh私はj=eD私はj/ s私はgma2//グリッド内のニューロンの近接係数を見つけます。 に注意してください h私は私は常に1
      4.  forallj vecwj= vecwj+ etah私はj vecx- vecwj
    3.  eta:= \ガ eta
    4. \シ:=  alpha\シ

学習の各エポックでは、入力データセットの要素を調べます。 各要素について、それに最も近いものを見つけます。 xニューロン、次にその重みと、レイヤー内のすべての近傍の重みを、距離に応じて更新します x協力係数について \シ。 以上 \シ、より多くのニューロンが各ステップで効果的に重みを更新します。 次の図は、次の場合のステップA1.2.2.1〜A1.2.2.4のグラフィカルな解釈です。 \シ同じ学習速度と最も近いベクトルでの大きい(1)および小さいとき(2)。


最初の場合 h私はj団結に近く、そして  vecx最も近いベクトルが移動するだけでなく、その最初の隣接、さらにはわずかに小さい2番目の隣接も移動します。 2番目のケースでは、同じ隣人がかなり移動します。 どちらの場合も、同じ4番目のベクトル \左 | vecw私は- vecwj\右 |最も近いベクトルから、ただしはるかに大きい D私はj動かない。

わかりやすくするためにコホーネンマップを学習するいくつかの時代:


アルゴリズムについて簡単に思い出せなかった場合は、 この記事を読んでください。A1の手順について詳しく説明しています。

したがって、SOMの主なアイデア:


いくつかの些細な変更がすぐに示唆されます:


ニューロントポロジー


自己組織化カードのやや目立たない変更で、その強さと一意性は構成されていますが、常に忘れているのは初期化フェーズにあります Wそして D。 例のKohonenレイヤーは常にグリッドとして描かれていますが、これは決して必要ではありません。 それどころか、ニューロンの相互配置を微調整することを強くお勧めします( D)データ層。

少なくとも、通常のグリッドの代わりに、六角形のグリッドを使用することをお勧めします。正方形のグリッドは、直線を優先して結果を歪め、六角形のグリッドよりも見た目が悪くなります。 データが周期的であると想定される場合、初期化する価値があります Dニューロンがテープ上またはトーラス上にあるかのように(下図の番号1を参照)。 明らかにハイパーフォールディングに適合しない3D SOM 3次元データに適合させようとする場合、「フリースカーペット」構造を使用する必要があります(2)。 一部のクラスターが他のクラスターから遠く離れていることがわかっている場合は、「花弁」層構造を試してください(3)。 データに何らかの階層があることがわかっている場合は非常に便利です。 Dこの階層のグラフの距離行列を取得できます(4)。

一般的に Dあなたの想像力、データの知識、それに続くニューロンの視覚化の利便性に限定されます。 後者の要因のため、たとえばコホネンの立方体層を行う価値はありません。 ニューロン間の適切な順序を確立することは強力なツールですが、構造が複雑になるほど D、初期重みを初期化することがより困難です Wそして、出力のKohonen層にいわゆるキンクを取得する可能性が高くなります。 ねじれは、次の場合の学習障害です W世界的に一貫した Dレイヤーがねじれたり、不自然に引き伸ばされたり、2つのクラスター間で分割されたりする特別なポイントを除き、データ。 同時に、SOM学習アルゴリズムは、既に確立された構造を破壊せずにこの状態から抜け出すことはできません。 ねじれは、通常のニューラルネットワークのトレーニングにおける深い局所的最小値の類似物であることが容易にわかります。

古典的なねじれの抽象的な例:

長い曲線をクラスターに適合させようとするときの合成データのねじれの例。 左上と右の花びらは信じられそうに見えますが、割り当てられたスペースは順序を台無しにします。

レイヤーの重みをランダムに初期化することにより、出力結果が悪いことを実際に保証します。 構築する必要がある W特定の各領域でニューロンの密度がデータ密度にほぼ一致するようにします。 残念ながら、超感覚能力やデータセットに関する追加情報がなければ、これを行うのは非常に困難です。

したがって、多くの場合、ニューロンが交差せずにデータ空間全体に単純に均一に分散することを確認する必要があります(中央の図のように)。

勝者の緩和/勝者の強化


このアイデアは、もともとコホネンによって提案され[1]、その後彼の信者によって一般化されました[4]。 勝者ニューロンの更新を削除したり、隣接ニューロンの更新を追加したりするとどうなりますか? 数学的には、次のようになります。勝者ニューロンのステップA1.2.2.4は、

 vecw私は= vecw私は+ eta vecx- vecw私は+ lambda sあなたはmj neq私はh私はj vecx- vecwj


どこで \ラ-緩和パラメーター。 残りのニューロンの更新は変更されないままであるか、リラックス期間の一部が追加されます。 それは奇妙に聞こえます。 それが判明した場合 \ラ<0ニューロンには多くの隣人がいるので、そこからロールバックすることさえできます  vecx? ベクトルの長さに上からの制限を適用しない場合、次のようになります。

負の \ラニューロンは、いわば隣人を自分自身に引き寄せますが、ニューロンが正であれば、反対に、環境から飛び出そうとします。 違いは、トレーニングの開始時に特に顕著です。 同じ初期構成と負、ゼロ、正の最初の時代の後のSOMの状態の例を次に示します \ラしたがって:



上記の影響のため \ラ<0ニューロンはより広いファンから飛び、  lambda>0-引き出されます。 したがって、最初の場合はコーティングがより均一になり、2番目の場合は小さな孤立したクラスターと放出がより大きな効果を発揮します。 後者の場合、ねじれの可能性もチャートの上部に表示されます。 文献は助言する  lambda 私はn[-1;1]、しかし、より大きなモジュロ値でも良い結果が得られることがわかりました。 追加された用語には、 h私はj順番に依存します \シ。 したがって、上記の手法は、トレーニングの開始時-協力の段階で大きな役割を果たします。

クラスターの洗練段階


アルゴリズムのメインサイクルの後、SOMニューロンが何かに接続されていても、クラスター上のそれらの密度がクラスターがない場所の密度に非常に匹敵することが判明することがよくあります。 そのような状況で分析することはかなり困難です。 Narni Manukyanとチーム[5]は、かなり単純なソリューションを提供します。メインアルゴリズムの後、別のニューロンフィッティングサイクルを開始します。

アルゴリズム2、クラスター調整フェーズ(クラスター調整フェーズ):
ログイン: X etaCR s私はgmaCR gammaCR alphaCRECR
  1. ECR回:

    1. インデックスリストをランダムに並べ替えます:= shuffle( [01\ドN-2N-1]
    2. それぞれについて 私はdx注文から:

      1.  vecx=X[私はdx]// Xからランダムなベクトルを取得します
      2.  foralljh私はj=e left | vecx- vecwj r私はght |/ s私はgmaCR2//選択したデータ要素に対するニューロンの近接係数を見つけます
      3.  forallj vecwj= vecwj+ etaCRh私はj vecx- vecwj
    3.  etaCR:=  gammaCR etaCR
    4.  s私はgmaCR:=  alphaCR s私はgmaCR

アルゴリズムは見た目もA1と非常に似ていますが、現在は最も近いニューロンを探しているのではなく、すべてのニューロンを x。 相互作用のため  vecx- vecwjA2.2.2.2で指数的に、重みを更新する段階で、実際には、特定のリングにあるニューロンのみが  vecx。 明確にするために、調整の5つの時代を見てみましょう。

より正確に:CRフェーズでの調整が強いほど、クラスターはよく見えますが、クラスターの形状に関するより多くのローカル情報が失われます。 いくつかの時代の後、血餅の伸びに関するデータのみが残っています。 CRは近くにあるいくつかの折り目を折りたたむことができ、大きすぎる場合  s私はgmaCR、次の図のように、メインステップで取得した構造を台無しにするだけです。

ただし、指数の代わりに何らかの関数を使用することにより、最後の問題を回避できます。指数は、特定の最大値の後に0になります。

記事の著者は同じを使用することを助言します  s私はgmaCRしかし、これは率直に機能しません:if  s私はgmaCR大きい場合(1のオーダー)、アルゴリズムは行商です。小さい場合(0.01)、何も更新されません。 奇妙なことに、彼らはいくつかの良いデータや変数の重要性の適合ベクトルを持っているのでしょうか?

可視化、SOMの修正


これまでのところ、SOMを使用したデータクラスタリングについて一言も述べていません。 で構築 Dそして Wグリッドは楽しい視覚化ですが、それ自体ではクラスターの数については何も言いません。 さらに、リクエストに応じてグーグルにすることができる美しいマルチカラーのグリッド「SOM視覚化」は、本当に便利なものよりもプレスリリースや人気のある記事の可能性が高いとさえ言えます。

フォールド内のデータクランプの数を判断する最も簡単な方法は、いわゆるU-matrixを注意深く検討することです。 これは、Kohonenマップの一種の視覚化であり、ニューロンの値とともに、ニューロン間の距離が表示されます。 したがって、クラスターが接触している場所と境界が通過する場所を簡単に判断できます。

より興味深い方法は、結果の行列の上で実行することです W他のクラスタリングアルゴリズム。 たとえば、 DBSCANは 、特に上記のSOM CR修正とともに適しています。 2番目のアルゴリズムの距離関数は、レイヤーのグリッドに沿った距離から結合する必要があります( D)およびニューロン間の実際の距離( \左 | vecw私は- vecwj\右 |)フォールドに関するトポロジ情報を失わないようにします。

しかし、より高度なのは、メインアルゴリズムの操作中に関連するクラスター情報を蓄積することです。 Eren GolgeとPinar Daigulu [6]は、メインアルゴリズムの各エポックにニューロンがアクティブ化された回数を記憶することを提案します(つまり、ニューロンが勝者であるか、ニューロンが勝者に近いため、その重みが更新されます)。ニューロンがクラスターを表すか、空のスペースでハングするか。

アルゴリズム3、SOMの修正(A1に変更あり):
ログイン: X eta\シ\ガ alphaE
  1. 初期化するには W
  2. 初期化するには ES= vec0//興奮スコア-ニューロン興奮の合計スコア
  3. E回:

    1. 初期化するには WC= vec0//勝利数-現在の時代のニューロンの興奮の説明
    2. インデックスリストをランダムに並べ替えます:= shuffle( [01\ドN-2N-1]
    3. それぞれについて 私はdx注文から:
      1.  vecx=X[私はdx]// Xからランダムなベクトルを取得します
      2. 私は= arg m私はnj left | vecx- vecwj r私はght |//最も近いニューロンの番号を見つけます
      3.  foralljh私はj=eD私はj/ s私はgma2//グリッド内のニューロンの近接係数を見つけます。 に注意してください h私は私は常に1
      4.  forallj vecwj= vecwj+ etah私はj vecx- vecwj
      5.  foralljWCj=WCj+h私はj//現在のアクティベーションアカウントを更新します
    4.  eta:= \ガ\イ
    5. \シ:=  alpha s私はgma
    6.  foralljES=ES+WC/ eta//合計スコアを累積します

ニューロンが勝者である頻度が高いほど、それはクラスターの厚さのどこかであり、その外側ではありません。 総ニューロン数は乗数で累積することに注意してください 1/\イ:学習速度が遅いほど、WCの重みが大きくなります。 これは、サイクルの最後のエポックが最初のエポックよりも大きく貢献するように行われます。 これは他の方法でも実行できるため、この特定のフォームに軽くアタッチしてください。

ESは無次元の量であり、その絶対値にはあまり意味がありません。 単純に、値が大きいほど、ニューロンが意味のある何かに結び付けられる可能性が高くなります。 A3の終了後、結果のベクトルを何らかの方法で正規化する必要があります。 ESをニューロンに適用すると、次のようになります。

大きな赤い点は励起数が多いニューロン、小さな赤紫は小さいニューロンを表します。 RSOMは、ESの最終処理方法およびデータ内の異なる密度のクラスターに敏感であることに注意してください(図の右下隅を参照)。 ESが正確な値を正確に蓄積できるように、アルゴリズムの収束に必要以上の時代を指定するようにしてください。

もちろん、RSOMと追加のクラスター化ツールの両方を最上部に適用し、視覚化を目で見ることをお勧めします。

その他


レビューに含まれていません。


SOMとt-SNEの比較


ソムt-SNE
難易度OdENMkNN最適化を使用したBarnes-Hut t-SNE- OdEN logN、しかし、他の実装は、より計算的に集中する可能性があります。 OdEN2
ハイパーパラメーターの数3〜5、おそらくニューロンのはるかに+距離行列。 必須の時代数、学習率、協力の初期係数。 学習率の減衰と協調係数もしばしば示されますが、問題はほとんど発生しません。3〜4、データに関するもっと多くのメトリック。 必要な時代の数、学習率、困惑は、しばしば初期の誇張に遭遇しました。 困惑は非常に魔法であり、間違いなくそれをいじる必要があります。
結果の可視化解像度ニューロン以外の要素はありません( Mデータセットの要素よりも多くの要素はありません( N
可視化トポロジいずれにしても、ニューロン間の距離の行列を提供するだけです通常の平面または3次元空間のみ
さらなる教育、構造の拡大はい、実装するのは非常に簡単ですいや
追加の変換レイヤーのサポートはい、Kohonenレイヤーの前に好きなだけ密に接続されたレイヤーまたは畳み込みレイヤーを配置し、通常のバックプロップでトレーニングすることができますいいえ、手動のデータ変換と機能エンジニアリングのみ
優先クラスタータイプデフォルトでは、2次元の折り畳みとエキゾチックなクラスターの形でクラスターを表示します。 次元が2より大きい井戸構造を視覚化するには、トリックが必要です。ハイパーボールを著しく表示します。 ハイパーフォールディングとエキゾチックはわずかに悪く、距離関数に大きく依存しています。
優先データスペースディメンションそれはデータに依存しますが、もっと悪いです。 アルゴリズムは、 d geq4、ニューロンによって形成されるハイパーフォールドの自由度が多すぎるため。任意、次元の呪いが影響し始めるまで
初期データの問題ニューロンの重みを初期化する必要があります。 ( «»)いや
,,
SOM
いや
視覚化におけるクラスター間隔セマンティックロードを運ぶしばしば何も意味しない
視覚化におけるクラスター密度通常、セマンティックロードがありますが、初期化が不十分な場合は誤解を招く可能性がありますしばしば何も意味しない
視覚化におけるクラスター形状セマンティックロードを運ぶカンニングするかもしれない
クラスタリングの品質を評価することの難しさ非常に難しい:(非常に難しい:(

SOMは計算の複雑さで勝つように見えますが、見ずに前もって喜ばないでください。 O-bigの下の N 2N2は、自己組織化マップの望ましい解像度に依存します。これは、データの広がりと不均一性に依存し、その結果、暗黙的に依存しますMN そして d 現実には、複雑さは次のようなものです OdN32E

この表は、SOMとt-SNEの長所と短所を示しています。自己組織化マップが他のクラスタリング手法に取って代わった理由を理解するのは簡単です:Kohonenマップを使用した視覚化の方が意味がありますが、新しいニューロンを構築し、ニューロンに目的のトポロジを設定できます。は、現代のデータサイエンスにおけるSOMの関連性を大きく損ないます。さらに、t-SNE視覚化をすぐに使用できる場合、自己組織化カードには後処理および/または追加の視覚化の努力が必要です。追加のマイナス要因-初期化の問題dおよびねじれ。これは、自己組織化マップが過去のデータサイエンスにあるということですか?W

そうでもない。いいえ、いや、時にはあまり多次元でないデータを処理する必要があります-このため、SOMを使用することはかなり可能です。視覚化は本当にきれいで壮観です。アルゴリズムに洗練を適用するのが面倒ではない場合、SOMはハイパーフォールド上のクラスターを完全に検出します。

ご清聴ありがとうございました。私の記事が、誰かが新しいSOMビジュアライゼーションを作成するきっかけになることを願っています。githubから、記事で提案されている主な最適化を含む最小限のSOMの例を含むコードをダウンロードし、アニメーション化されたマップトレーニングを見ることができます。次回は、競争トレーニングにも基づいた「神経ガス」アルゴリズムを検討します。

[1]:自己組織化マップ、本。 Teuvo Kohonen
[2]:自己組織化マップのエネルギー関数。トム・ヘスケサ、理論財団SNN、ナイメーヘン大学
[3]:bair.berkeley.edu/blog/2017/08/31/saddle-efficiency
[4]:勝者リラックス型自己組織化マップ、Jens Christian Claussen
[5]:まばらに一致した自己組織化マップでのデータ駆動型クラスター強化と可視化。 Narine Manukyan、Margaret J. Eppstein、およびDonna M. Rizzo
[6]:Web画像からの自動概念学習のための自己組織化マップの修正。 Eren Golge&Pinar Duygulu
[7]:バイナリおよびカテゴリー自己組織化マップの代替アプローチ。 Alessandra Santana、Alessandra Morais、Marcos G. Quiles
[8]:複数勝者の自己組織化マップでのシーケンス処理をサポートする一時的非対称学習
[9]:自己組織化マップおよび神経ガスでの拡大制御。 Thomas Villmann、Jens Christian Claussen
[10]:自己組織化マップにおけるニューロン選択のための埋め込み情報強化。上村亮太郎、上村多恵子
[11]:自己組織化マップの初期化問題。Iren Valova、George Georgiev、Natacha Gueorguieva、Jacob Olsona
[12]:自己組織化マップの初期化。Mohammed Attik、Laurent Bougrain、Frederic Alexandre

Source: https://habr.com/ru/post/J338868/


All Articles