今回は機械学習ネタです。
教師なし学習というものにk平均法(k-means clustering)というアルゴリズムがあります。
普通ならpythonで実装しmatplotlibとやらで結果を視覚化すると思いますが、
matplotlibの使い方がわかりません。
ですのでScalaで実装してjavafxで視覚化したいと思います。
k平均法のアルゴリズム
k平均法を構成するもの
- クラスタ… ニュアンスが正しいかわかりませんが、グループだと捉えればいいのかなと思います。
- 入力データ… クラスタに所属させる
学習の流れ
だいたいこんな流れになるかと思います。
- クラスタを初期化する… 好きな値で大丈夫だそうです。
- データをクラスタに所属させる… クラスタとデータの距離を計算してその値が最小になるクラスタに所属させる
- クラスタを更新する… クラスタに属しているデータの平均をクラスタの値とする
- クラスタの値が変化しなくなるまで２,３と繰り返す
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平均法をプログラムしてみたいと思います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 |
import javafx.application._ import javafx.stage._ import javafx.animation._ import javafx.scene.shape._ import javafx.scene.Scene import javafx.scene.layout._ import javafx.scene.paint.Color import java.math import scala.util.Random // エントリーポイント object KMeansMain { def main(args: Array[String]) { Application.launch(classOf[KMeansVisual], args:_*) } } // 割り振りと更新を行うクラス class KMeans { // データの数 val dataNum = 1600 // クラスタの数 val cNum = 4 // ここから var r = new Random() // 学習の流れの1 var cluster = Array.fill(cNum)(Array.fill(2)((r.nextInt(500)).asInstanceOf[Float])) val data = Array.fill(dataNum)(Array.fill(2)(0.0f)) val gr = data.size/cNum for (i <- 0 to data.size-1) { data(i)(0) = r.nextInt(250) + r.nextInt(250) * (i / gr) data(i)(1) = r.nextInt(250) + r.nextInt(250) * (i / gr) } // ここまではいろいろしてデータを作ってる // どのデータがどのクラスタに属しているかを格納する配列 var indexOfAssign = Array.fill(dataNum)(0) // データをクラスタに割り当てる // 学習の流れの2 def assign() { for (d <- 0 to data.size-1) { var distArr = Array.fill(cluster.size)(0.0) for (c <- 0 to cluster.size-1) { val x = data(d)(0) - cluster(c)(0) val y = data(d)(1) - cluster(c)(1) distArr(c) = Math.sqrt( Math.pow(x,2) + Math.pow(y,2) ) } indexOfAssign(d) = distArr.indexOf(distArr.min) } } // クラスタを更新する クラスタごとのデータの平均を求める // 学習の流れの3 def update() { for (c <- 0 to cluster.size-1) { var xSum = 0.0f var ySum = 0.0f for (i <- 0 to indexOfAssign.size-1) { if (indexOfAssign(i) == c) { xSum += data(i)(0) ySum += data(i)(1) } } val num: Float = indexOfAssign.count(cInd => cInd == c) cluster(c)(0) = xSum / num cluster(c)(1) = ySum / num } } } // 描画をしてくれるクラス // 今回の議題ではないのでそこまで重要ではない class KMeansVisual extends Application { // 図形を描画するために使う val pane = new Pane val shapes = pane.getChildren // KMeansクラスをメンバにもつ val km = new KMeans // ウインドウの大きさ val w = 900 val h = 900 // 矩形の配列 クラスタとデータ var cRects: Array[Rectangle] = null var dRects: Array[Rectangle] = null // クラスタごとの色 var colors = Array( Color.web("0x000000"), Color.web("0xff0000"), Color.web("0x00ff00"), Color.web("0x0000ff") ) // 矩形をペーンに加える override def init() { cRects = Array.fill(km.cluster.size)(new Rectangle(20,20)) for (rect <- cRects) { shapes.add(rect) } dRects = Array.fill(km.data.size)(new Rectangle(5,5)) for (rect <- dRects) { shapes.add(rect) } } // 割り振りと更新を別スレッドで行う // 学習の流れの4 // ※クラスタの値が変化しなくなったかを判断する処理は実装してません。 override def start(stage: Stage) { stage.setScene(new Scene(pane, w, h)) stage.show new Thread() { override def run() { while(true) { km.assign() km.update() Thread.sleep(80) } } }.start new AnimationTimer() { override def handle(now: Long) { draw() } }.start } def draw() { for (i <- 0 to km.cluster.size-1) { cRects(i).setFill(Color.web("0xaabbcc")) cRects(i).setX(km.cluster(i)(0)) cRects(i).setY(km.cluster(i)(1)) } for (i <- 0 to km.data.size-1) { dRects(i).setFill(colors(km.indexOfAssign(i))) dRects(i).setX(km.data(i)(0)) dRects(i).setY(km.data(i)(1)) } } } |
クラスタの動き
クラスタとデータの値はランダムなので実行するたびに結果はかわりますが、今回はこんな動きをしました。
クラスタごとに色をつけたのですが、見てるだけでも面白いですね。
僕は機械学習のプロではないので知識が乏しく、間違っている部分があるかもしれません。
その際はご指摘いただければと思います。
k平均法は書籍はネットに情報が結構あると思います。
僕は以下の書籍でk平均法をすこしだけ勉強しました。
Pythonで動かして学ぶ!あたらしい機械学習の教科書 第2版