over 3 years ago

最近 Haskell の練習に機械学習の基本的なアルゴリズムを自分の手で実装してみています。
今日は k-means method を実装してみました!
混合ガウシアンからサンプリングしたデータを使ったので特に面白味は無いかもしれませんが、
代わりに実装したコードの解説多めで書いていきたいと思います。

k-means method はクラスタリングの手法の一つです。
詳しい解説はデモと共にわかりやすいサイトがあるので参考にしてみてください。
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた

アルゴリズムを簡単に説明すると

  1. (初期化)データに対してクラスを適当に振り分ける
  2. クラス分けされたデータを元にクラスの重心を計算する
  3. クラスの重心から構成されるボロノイ図を元にデータを分類する
  4. 2~3を収束するまで繰り返す

となります。

import Data.List
import System.IO
import System.Random

type Cluster = Int
type Point = (Double, Double)  -- Point in R^2

type CPoint = (Cluster, Point) -- Classified Point

まず見やすいように型に名前をつけます。

  • クラスを表す Int は Cluster
  • \(\mathbb{R}^2\)の元 を Point
  • PointCluster の組を CPoint

としています。

名前をつけた型に対して基本的な関数を定義します。

---- Euclid Distance between Two Points

dist :: Point -> Point -> Double
dist (x0,y0) (x1,y1) = sqrt $ (x0-x1)^2 + (y0-y1)^2

---- Center of Points

center :: [Point] -> Point
center = (\(ys,zs) -> (average ys, average zs)).unzip
  where average xs = (sum xs)/((fromIntegral.length) xs)

---- CPoints are Same Cluster or Not

colleague :: CPoint -> CPoint -> Bool
colleague (c0,_) (c1,_) = c0 == c1
  • dist は二点間の距離を求める関数
  • center は点集合の重心を求める関数
  • colleague は二つの CPoint が同じクラスに属するかどうかを返す関数

です。
では本題の k-means method の実装です

--- One Step of K-means Method

kmeans :: [CPoint] -> [CPoint]
kmeans xs = map (\(_,p) -> (classify p, p)) xs
  where
  ---- Classify a Point 

  classify :: Point -> Cluster
  classify x = (snd.last.sort) $ map (\(c,p) -> (dist x p, c)) (centers xs)
  ----

  ---- Calculate Prototypes

  centers :: [CPoint] -> [CPoint]
  centers xs = map ((\(cs,ps) -> (head cs, center ps)).unzip) $ (groupBy colleague).sort $ xs

kmeans と名前がついていますが実際はアルゴリズムの 2,3 を行う関数になっています。
使う時は iterate で無限列を作り適当なところを取ってきます。
where 句以降の関数が本命で

  • classify は点が属するクラスを返す関数
  • centers は分類されたデータからクラスのプロトタイプを返す関数

になっています。
あとはそれらを用いてデータを再分類しています。
使い方は

---- iv は初期データ(initial value)

experiment = iterate kmeans iv
result = experiment!!100

こんな感じです。これは100回のイテレーションをしています。
このプログラムを使って


のようなデータを分類すると

このようになりました。
ちょっと色が見にくいかもしれませんが大体直感にあった分類になっていますね

全体のコードを gist で公開しています。
tatyusa / kmeans.hs
ご指摘あればコメントお願いします。

← クリスマスキャロルの単語出現頻度 リア友とフレンドになる方法 #ウチ姫 →
 
comments powered by Disqus