教師なし学習SOMをスプレッドシートで簡易実装してみた

はじめに

この記事はエイチーム引越し侍 / エイチームコネクトの社員による、Ateam Hikkoshi samurai Inc.× Ateam Connect Inc. Advent Calendar 20204日目の記事です。

ディレクターにジョブチェンして久しい自分が、頑張ってネタを探しました。
最近うちの会社でも機械学習を学ぼうという空気感が高まってきているけど、
大抵は「機械学習には"教師あり学習"と"教師なし学習"があってね、この講義では"教師あり学習"の方を対象にします」
て感じでイントロでチラ見せされたままその後は出てこない役回りの教師なし学習にスポット当てたいと思いました。

大学院時代、教師なし学習のニューラルネットワークであるSOM(Self Organization Map)=自己組織マップについて
教授に教えてもらったことがあって、そのあまりに簡単すぎるアルゴリズムに感動したのを思い出し、
多分今でもアドリブで実装できるはず！と思い挑戦してみました。

マップの色塗りが簡単そうなスプレッドシートでやっていきます。

SOM(Self Organization Map)=自己組織マップとは

すみません、ちゃんとした説明はググればいくらでもあるのでそちらをご覧ください。
でも一応自分の言葉でも書いてみます。

SOMは、多次元のデータを低次元になんとかギュッと詰め込んで、それなりに図示できるマップです。
あるいはクラスタリングにも使えるそうです。
SOMで言う低次元とは、大体は2次元ですが、仕組み上1,3次元でも任意の次元で実装できます。
人が図で直感的に理解できるのがせいぜい3次元かと思いますが、
それも見にくいのでSOMといったらほぼ2次元だったと思います。

今回の題材は「色」

皆さんご存知の通り、色はRGBの3次元で表すことが多いです。

3次元なので図示できなくもないですが、ここに色んな色がプロットされていくとやっぱり見づらいですよね。

一方で、いろんなアプリでこうやって色を選択するとき、本来3次元なはずのいろんな色達が、 うまいこと2次元で配置されてますよね。 こういう図って、必ずしも「横軸が◯◯で・・・」ときっぱり言えるものではないんですが、 縦横関係なしにざっくり「特徴の近いものが近くにある」ことが大切です。 SOMを使うと、まさにこういうマップが自動的に作れてしまいます！ ## 注意 * ソースとか実装方法汚いのは許してね(お気づきのことは教えて下さいませ・・・) * アルゴリズムが間違ってたらごめんなさい(お気づきのことは教えて下さいませ・・・) * 7年くらい前の思い出を頼りに実装しました、それらしい結果が出たので大丈夫だとは思ってます

実装

(1)初期化

今回は、11x11のマップにします。
いろんな色を最低限網羅するにはこれくらいかな？という感覚。

/*初期化*/
function initialize() {
  var ss = SpreadsheetApp.getActiveSpreadsheet();
  var sheet = ss.getActiveSheet();
  var r = "";
  var g = "";
  var b = "";
  
  for (let i=mapSizeFrom;i<mapSizeTo;i++) {
    for (let j=mapSizeFrom;j<mapSizeTo; j++) {
      r = ("00"+Math.floor(Math.random()*256).toString(16)).slice(-2);
      g = ("00"+Math.floor(Math.random()*256).toString(16)).slice(-2);
      b = ("00"+Math.floor(Math.random()*256).toString(16)).slice(-2);
      sheet.getRange(i,j).setValue('#'+r+g+b);
      sheet.getRange(i,j).setBackground('#'+r+g+b);
    }
  }
}

今回はとにかく、教師なし学習が進んでいく様子を肌で感じたいので、
学習の各ステップを毎度毎度 図にも反映させていきます。
スプレッドシートをGoogle Apps Scriptから操作すると、背景色も変えられるので、
(R,G,B)=(256,256,256)を乱数で決定し
→16進数に変換
→#ffffffみたいなカラーコードに変更
→セルの背景色に反映させるとともに
→セルにテキストとしてもカラーコードを保存
という方式でやっていきます。
スピード重視なら配列でやった方が断然早いですよね。

(2) 学習

早速ここから学習フェーズ。

(2-1)ランダムな特徴ベクトルを用意

教師なし学習なので、「これが青色(#ffff00)だよ！」
「これがクー・ドィ・フードゥル（#e81619）だよ！」ということはしません。
そういったラベルをもった教師、クラスタリング済みの教師が居ないので、
SOMの学習は、ひたすらランダムな特徴ベクトルを与えまくります。

今回は色なので、初期化したときと同じように、ランダムな特徴ベクトル(色)を1つ用意します。

  //ランダムな色を用意
  var r = ("00"+Math.floor(Math.random()*256).toString(16)).slice(-2);
  var g = ("00"+Math.floor(Math.random()*256).toString(16)).slice(-2);
  var b = ("00"+Math.floor(Math.random()*256).toString(16)).slice(-2);
  sheet.getRange(3,1).setValue('#'+r+g+b);
  sheet.getRange(3,1).setBackground('#'+r+g+b);
  var randColCode = '#'+ r + g + b;

今回は#45f048という黄緑色のようが色が生成されたとしましょう。

(2-2)マップ上でランダムな特徴ベクトルに一番近いベクトル(ニューロン)を探す

次に、今作ったランダムな特徴ベクトルに一番近いベクトルをマップ上で探します。
どうやって「一番近い」を計算するか。
いわゆるユークリッド距離ってやつを使います。
三平方の定理の立体版です。

  //近い色を探す
  for (let i=mapSizeFrom;i<mapSizeTo;i++) {
    for (let j=mapSizeFrom;j<mapSizeTo; j++) {
      mapColCode=sheet.getRange(i,j).getBackground();
      if (minDiff > colorDiff(randColCode,mapColCode)) {
        minI =i;
        minJ =j;
        minDiff = colorDiff(randColCode,mapColCode);
      }
    }
  }
/*カラーコードの差分取得*/
function colorDiff(a,b) {
  var diffR = Math.pow(parseInt(a.substr(1,2), 16) - parseInt(b.substr(1,2), 16),2);
  var diffG = Math.pow(parseInt(a.substr(3,2), 16) - parseInt(b.substr(3,2), 16),2);
  var diffB = Math.pow(parseInt(a.substr(5,2), 16) - parseInt(b.substr(5,2), 16),2);
 
  return(Math.sqrt(diffR + diffG + diffB));
}

さて、#45f048 に最も近い色として選ばれたのは、
座標で言うと(5,6)のちょうど中央あたりの色でした！
目視で見ても、似ている色が選ばれているのがわかります。

(2-3)選ばれた色と周りの色を、「ちょっと」寄せる

さて、この処理がSOMにおける「学習」の本体なのですが、
選ばれた色を、ランダム生成した色(#45f048)に”近づけ”ます。
近づける処理は、こんな感じ。

/*x%近づける*/
function close(sheet, r, c, randColCode, x){
  colCode = sheet.getRange(r,c).getValue();
  var newR = parseInt(colCode.substr(1,2), 16) + x * (parseInt(randColCode.substr(1,2), 16) - parseInt(colCode.substr(1,2), 16));
  var newG = parseInt(colCode.substr(3,2), 16) + x * (parseInt(randColCode.substr(3,2), 16) - parseInt(colCode.substr(3,2), 16));
  var newB = parseInt(colCode.substr(5,2), 16) + x * (parseInt(randColCode.substr(5,2), 16) - parseInt(colCode.substr(5,2), 16));
  newR = ("00"+ Math.floor(newR).toString(16)).slice(-2);
  newG = ("00"+ Math.floor(newG).toString(16)).slice(-2);
  newB = ("00"+ Math.floor(newB).toString(16)).slice(-2);

  sheet.getRange(r,c).setValue("#" + newR + newG +  newB);
  sheet.getRange(r,c).setBackground("#" + newR + newG +  newB);

  return ("#" + newR + newG +  newB);
}

でもちょっとここの処理が雑すぎる気もする。。。
ベクトルの足し算引き算的にこれでいいんだっけ。
いったんこのままいきます。
今は、aをbに近づけるとき、bに対して(a-b)のx%を足すことで近づけようとしています。

そして、重要なのは、「周りのセルも少し近づける」こと。

この画像を見てもらうと、選ばれたセルの回りも全体的に緑っぽくなっているのがわかると思います。

2-1から2-3を繰り返す・・・！

あとはこの繰り返しです。
ランダムで色を作る
→一番近い色を探す
→その色とその周りの色をちょっと近づける
この繰り返しをひたすらしていきます

ちなみに、最初は大雑把に、後半は繊細に調整していくのがベターです。
この考え方を実現する要素はいくつかあります。

• 学習範囲を大きくとって狭めていく
  • 2-3では「周り」を隣接しているセルに限定しましたが、始めはもっと広範囲を一度に学習させるやり方もあります
  • このとき、中央に近いほど強め学習させると良いです
• 学習の強さを弱めていく
  • 最初は、選ばれた色を、ランダムの色にガッツリ近づける、後半はきもーち近づける、というイメージ。上のコードだとxのところです
    この辺はチューニング対象ですし、「徐々に」の実現に適した関数も研究されていたはず。

お楽しみの実行結果は・・・

こんな感じになりました！
100回の時点で既にちょっとしたカラーマップっぽくなっていますが、
1000回終えるときれいにグラデーションになってますね！（なってますよね...?)

ちなみに、500回までは中央のニューロンを80%,周りのニューロンを40%近づけており、
501~1000回ではそれを40%,20%に変えてより微調整っぽくしています。

試しにもうちょっと大きいサイズでも

これはイマイチですね。
マップに対して学習半径が小さすぎるのが問題で、局所解に陥っています。
（さすがに毎回描画していると日が暮れるので、カラーコードはセルそのものではなく配列に持つようにして100回ごとに書き出すようにしました。）

SOMの応用先

色と並んで、SOMのおもしろ事例として有名なのが、
動物をマッピングするものです。
「動物なんてどうやって数値化するんだ」と思われるかもしれませんが、
平均の全長、体重はもちろん、「羽があるか」「卵を生むか」なども0,1で数値化できます。
それをうまいこと正規化して平等に１つの次元として扱うと、10次元〜20次元くらいの特徴ベクトルが生成でき、
完成したSOM上で、哺乳類、鳥類、爬虫類、、、と似た性質の動物が固まったマップを作成することができます。

何か多くの要素を持つデータを分析したいとき、直感的に傾向を掴みたい場合に、SOMを使って無理やり２次元に落とし込むことで
分析が捗ることもあるかも知れません。

滞在時間、セッション数、閲覧ページ数などを食わしてCVRの分析にも使えないかな・・・

SOMの亜種

色々研究されてます。
ほんと、教授から聞いた思い出だけで書きますが笑、

• セルが六角形型
  • 蜂の巣みたいに六角形を敷き詰める
  • こうすることで近傍ニューロンへの距離が全て等しくなる
• 球体型
  • 「端」がなくなる
  • 右端が左端に、上が下に繫がっている状態
  • こうすること多分、両端に似た特徴を持つものが別れてしまう可能性を防げるのかも
    などがあるそうです。
    どちらも、直感では精度が上がる気がしますよね笑

まとめ

3時間くらいで1から実装できました。
気軽に教師なし学習を感じる手段としてどなたかの参考になれば幸いです。

しょぼい実装で恥ずかしいですが、一応コードまるまる貼っときます。

ソースコードを見る

// MAPの大きさ
var mapSizeFrom = 3;
var mapSizeTo = 14;

/*繰り返し学習させる*/
function som() {
  var ss = SpreadsheetApp.getActiveSpreadsheet();
  var sheet = ss.getActiveSheet();

  for (let i=0; i<500; i++)  {
    learn(sheet);
  }
}

/*学習1回*/
function learn(sheet) {
  //ランダムな色を用意
  var r = ("00"+Math.floor(Math.random()*256).toString(16)).slice(-2);
  var g = ("00"+Math.floor(Math.random()*256).toString(16)).slice(-2);
  var b = ("00"+Math.floor(Math.random()*256).toString(16)).slice(-2);
  r = "45";
  g = "f0";
  b = "48";
  sheet.getRange(3,1).setValue('#'+r+g+b);
  sheet.getRange(3,1).setBackground('#'+r+g+b);
  var randColCode = '#'+ r + g + b;
  var minI =0;
  var minJ =0;
  var minDiff = 999;
  //近い色を探す
  for (let i=mapSizeFrom;i<mapSizeTo;i++) {
    for (let j=mapSizeFrom;j<mapSizeTo; j++) {
      mapColCode=sheet.getRange(i,j).getBackground();
      if (minDiff > colorDiff(randColCode,mapColCode)) {
        minI =i;
        minJ =j;
        minDiff = colorDiff(randColCode,mapColCode);
      }
    }
  }
  sheet.getRange(4,1).setValue(minI);
  sheet.getRange(4,2).setValue(minJ);
  sheet.getRange(5,1).setValue(minDiff);
  sheet.getRange(minI,minJ).setBorder(true, true, true, true, true, true, "#0000000", SpreadsheetApp.BorderStyle.DOUBLE);

  // 学習させる
  for (let k = minI-1; k <  minI + 2; k++) {
    for (let l = minJ-1; l < minJ + 2; l++) {  
      if (k==minI && l==minJ) {
        close(sheet, k, l, randColCode,0.8);       
      } else {
        if (mapSizeFrom <= k && k < mapSizeTo && mapSizeFrom <= l && l < mapSizeTo ) {
          close(sheet, k, l, randColCode,0.4);
        }
      }
    }
  }
  sheet.getRange(minI,minJ).setBorder(false, false, false, false, false, false, "#0000000", SpreadsheetApp.BorderStyle.DOUBLE);
}

/*x%近づける*/
function close(sheet, r, c, randColCode, x){
  colCode = sheet.getRange(r,c).getValue();
  var newR = parseInt(colCode.substr(1,2), 16) + x * (parseInt(randColCode.substr(1,2), 16) - parseInt(colCode.substr(1,2), 16));
  var newG = parseInt(colCode.substr(3,2), 16) + x * (parseInt(randColCode.substr(3,2), 16) - parseInt(colCode.substr(3,2), 16));
  var newB = parseInt(colCode.substr(5,2), 16) + x * (parseInt(randColCode.substr(5,2), 16) - parseInt(colCode.substr(5,2), 16));
  newR = ("00"+ Math.floor(newR).toString(16)).slice(-2);
  newG = ("00"+ Math.floor(newG).toString(16)).slice(-2);
  newB = ("00"+ Math.floor(newB).toString(16)).slice(-2);

  sheet.getRange(r,c).setValue("#" + newR + newG +  newB);
  sheet.getRange(r,c).setBackground("#" + newR + newG +  newB);

  return ("#" + newR + newG +  newB);
}

/*カラーコードの差分取得*/
function colorDiff(a,b) {
  var diffR = Math.pow(parseInt(a.substr(1,2), 16) - parseInt(b.substr(1,2), 16),2);
  var diffG = Math.pow(parseInt(a.substr(3,2), 16) - parseInt(b.substr(3,2), 16),2);
  var diffB = Math.pow(parseInt(a.substr(5,2), 16) - parseInt(b.substr(5,2), 16),2);
 
  return(Math.sqrt(diffR + diffG + diffB));
}

/*初期化*/
function initialize() {
  var ss = SpreadsheetApp.getActiveSpreadsheet();
  var sheet = ss.getActiveSheet();
  var r = "";
  var g = "";
  var b = "";
  
  for (let i=mapSizeFrom;i<mapSizeTo;i++) {
    for (let j=mapSizeFrom;j<mapSizeTo; j++) {
      r = ("00"+Math.floor(Math.random()*256).toString(16)).slice(-2);
      g = ("00"+Math.floor(Math.random()*256).toString(16)).slice(-2);
      b = ("00"+Math.floor(Math.random()*256).toString(16)).slice(-2);
      sheet.getRange(i,j).setValue('#'+r+g+b);
      sheet.getRange(i,j).setBackground('#'+r+g+b);
    }
  }
}

以上、Ateam Hikkoshi samurai Inc.× Ateam Connect Inc. Advent Calendar 2020 4日目でした！
明日は新卒一年目の @sho-hata くんです！