WASY-LOG

たいした話はしません

k-means++を可視化するやつを作った & 少し解説

話はいいから動かさせてくれという人へ

こちらからどうぞ.

はじめに

大学の課題でProcessingを用いて任意の作品を作ってレポートを書けというものが出されたので,k-means++法のアルゴリズムを可視化するやつを作りました.こんな感じのです.
f:id:beybr6:20170731214803p:plain

こちらの記事にてにとよん氏が公開されているk-means法のアルゴリズムの可視化するやつをかなり参考にしましたので,紹介しておきます.

k-means法

教師なし学習の分類問題であるクラスタリングにおいて,k-means法というプロトタイプベースのクラスタリング手法が存在します.
k-means法では与えられたデータをk個のクラスタに分類します.ここでkは予め指定された値です.
k-means法の詳しい説明はインターネットにたくさん存在するためここでは省きますが,各クラスタの中心だと「思われる」特徴空間上の座標(セントロイド)を,ランダムに選んだ初期値から,よりもっともらしい座標へと移動していくことによってクラスタ分類を実現します. 言い換えると各クラスタの分散が局所的に最小となるようセントロイドの座標を更新していくということです.

k-means++法

k-means法は実装が容易であり計算効率にも優れているため,分類問題において定番のアルゴリズムとなっています.一方でクラスタの個数を指定しなければならなかったり,初期値が不適切であるときにうまく分類ができなかったりする問題も抱えています.
特に後者の問題について解決を図るためにk-means法の改良として考案されたのが,k-means++法です.
k-means++法の特徴はセントロイドの初期値の決定方法にあります.n個の入力サンプルx_{0}x_{n-1}クラスタ1〜クラスタkに分類するとき,以下のような手順でk個のセントロイドの初期値が決定されます.

 1. 入力のサンプルのうち一つをランダムに選択し,その座標をクラスタ1のセントロイドの初期値とする.
 2. 入力の全てのサンプルに対して,既に座標が決定しているセントロイドのうち最も近いものとのユークリッド距離を計算する.ここでx_{i}の最近傍セントロイドとの距離をd(x_{i})とおく.
 3. いずれかのサンプル点の座標を次のセントロイドの座標として選択する.このときx_{p}の座標が選ばれる確率を以下の式を用いて定義する.
{{d(x_{p})}^2}/{\sum_{i=0}^{n-1} {d(x_{i})}^2}
 ここで既にセントロイドの座標として選ばれているサンプル点は最近傍セントロイドとの距離が0であるため,選択される可能性は0になり,分母の総和にも影響を与えない.
 4.手順2〜3をk個のセントロイドの初期値が選択されるまで繰り返す.

上記の手順でセントロイドの初期値を決定したのち,従来のk-means法を用いて分類を行います.

作ったやつ

こちらからブラウザ上でデモを行えます.初期値の計算時にはこのように上記手順3で計算した確率分布に従って,各サンプル点の大きさが変化するようにしています.
f:id:beybr6:20170731214456p:plain

GitHubリポジトリも一応.
github.com

おしまい.

参考