K平均法(k-means clustering)をScalaで実装する


今回は機械学習ネタです。
教師なし学習というものにk平均法(k-means clustering)というアルゴリズムがあります。
普通ならpythonで実装しmatplotlibとやらで結果を視覚化すると思いますが、
matplotlibの使い方がわかりません。

ですのでScalaで実装してjavafxで視覚化したいと思います。


k平均法のアルゴリズム


k平均法を構成するもの

  • クラスタ… ニュアンスが正しいかわかりませんが、グループだと捉えればいいのかなと思います。
  • 入力データ… クラスタに所属させる

学習の流れ


だいたいこんな流れになるかと思います。

  1. クラスタを初期化する… 好きな値で大丈夫だそうです。
  2. データをクラスタに所属させる… クラスタとデータの距離を計算してその値が最小になるクラスタに所属させる
  3. クラスタを更新する… クラスタに属しているデータの平均をクラスタの値とする
  4. クラスタの値が変化しなくなるまで2,3と繰り返す


2でクラスタとデータの距離を計算するのですが、ユークリッド距離というのを使うらしいです。
以下のように計算します。
√(データx – クラスタx)² + (データy – クラスタy)²

以下のようにクラスタとデータが定義されているとします。
クラスタ A(2, 7), B(5, 2), C(6, 1)
データ (4, 3)
すべてのクラスタに対してデータとのユークリッド距離を求めます。
クラスタが3つあるため3回計算してその中から答えが最小になるクラスタにデータを割り振るということですね。
それぞれのクラスタとの距離はこうなりました。
A… 4.4
B… 1.4
C… 2.8
ということなのでデータ(4, 3)はBに属するということです。

今回はデータが一つだけですが、データが複数個あればそれぞれのデータに対するクラスタとの距離を計算してクラスタに割り振ります。

3の処理でクラスタを更新します。
たとえばクラスタAに以下のような四つのデータが属しているとします。
(6, 2) (3, 5) (7,5) (6, 4)
これらのデータの同じ要素の平均をもとめると以下のようになりました
(6 + 3 + 7 + 6) / 4 = 5.5
(2 + 5 + 5 + 4) / 4 = 4
ですのでクラスタAの新しい値は(5,5, 4)になりますね。

4は上で示した2,3の処理を繰り返すだけです。
クラスタの値が変わっているので、それに割り振られるデータも変化します。


実装しよう


K平均法をプログラムしてみたいと思います。

クラスタの動き


クラスタとデータの値はランダムなので実行するたびに結果はかわりますが、今回はこんな動きをしました。
クラスタごとに色をつけたのですが、見てるだけでも面白いですね。


僕は機械学習のプロではないので知識が乏しく、間違っている部分があるかもしれません。

その際はご指摘いただければと思います。

k平均法は書籍はネットに情報が結構あると思います。
僕は以下の書籍でk平均法をすこしだけ勉強しました。
Pythonで動かして学ぶ!あたらしい機械学習の教科書 第2版

コメントする