Help us understand the problem. What is going on with this article?

k-meansでクラスタリングしたら失敗したけどどうしよう(kernel k-meansの実装)

More than 3 years have passed since last update.

この記事は何?

クラスタリングのアルゴリズムで代表的なものとしてk-meansというものがあります.
k-meansは非常に単純なアルゴリズムであるため,残念なクラスタリング結果となってしまうことがあります.
そこで,この記事ではデータ空間を非線形関数によって高次元に写像しクラスタリングを行うkernel k-meansの実装を紹介します.

k-meansの失敗例

以下のデータをk-meansでクラスタリングを行ってみました.

  • クラスタリング前

origin.png

  • クラスタリング後

linear.png

ジーっと見てみると,中央部分と外側部分とでクラスタが2つ存在しているように見えますが,k-meansのクラスタリング結果は直線で区切ったようなものとなっています.

kernel k-means

kernel k-meansではデータ空間を非線形関数によって高次元に写像し,クラスタリングを行います.
つまり,データ点を$x\in X$,非線形関数$\phi$としたときに,$\phi(x)$に対しクラスタリングを行います.
非線形関数$\phi$の選び方は様々なものが考えられますが,$\phi$を選択するよりもカーネル関数$k(x_i,x_j)=\phi(x_i)^T\phi(x_j)$を選択することが多いです(カーネル法).

カーネル関数には以下のようなものがあります.

  • 線形カーネル $k(x_i,x_j)=x_i^Tx_j$
  • 多項式カーネル $k(x_i,x_j)=(x_i^Tx_j+\gamma)^c$
  • ガウスカーネル $k(x_i,x_j)=\exp(-\gamma\cdot||x_i-x_j||^2)$

線形カーネルを選択すると,k-meansと等価となります.

kernel k-meansによるクラスタリング

先程のデータに対しkernel k-meansでクラスタリングを行ってみました.
カーネル関数にはガウスカーネルを,$\gamma$の値には0.1を設定してみました.
ソースコードはここにアップロードしました.

kernel.png

中央部分と外側部分とでクラスタリングできていることがわかります.

その他

k-means,kernel k-meansは初期値に大きく依存するアルゴリズムであるため,いつもこのようにクラスタリングできるわけではありません.
kernel k-meansではカーネル関数の選択およびハイパーパラメータの設定を行う必要があるのがメンドウです….

(2015/7/2 微妙に図が異なっていたのを修正)

参考文献

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away