Introduction English ver 今日はK-meansアルゴリズムの理論について書きます。 K-meansアルゴリズムはクラスタリングのためのアルゴリズムです。 K-meansの実装の記事は カーネルK-meansの実装 を御覧ください。 この記事はカーネルK-menasの実装についての記事ですが、通常のK-meansの実装も行っています。カーネルK-meansについてはまた、今度別の記事で紹介したいと思います。 概要 1 of K 符号化法 プロトタイプ 歪み尺度 最適化 1 of K 符号化法 K-meansはK個のクラスについて分類することを考えます。 K-meansでは x_nがkのクラスに属していることを次のように表します。 ベクトルr_n:1 \times K を r_n := (0,0,..,1,..,0)
このベクトルはk番目にのみ1を持ち、それ以外は0を要素に持つようなベクトルです。 こののような表現の仕方を1 of K符号化法と呼びます。 プロトタイプ K-meansではプロトタイプと呼ばれるベクトルを選びます。このベクトルは各クラスに一つあり、そのクラスの代表のようなベクトルです。 K-means ではそのようなベクトルは各クラスの平均ベクトルとなります。これは目的関数から自然と導かれます。 歪み尺度 プロトタイプベクトルを \mu_i ~\forall k \in Kとします。 この時、k-meansの目的関数は次のようになります。 J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2
ここで、 r_{nk} はr_nのk番目の要素です。 この目的関数について少し説明をします。r_{n}はx_nが属しているクラスのラベルの場所だけ1で他は0であるので、 J = \sum_{n=1}^{N} ||x_n - \mu_{x_n}||
ここで、\mu_{k_n}はx_nが属しているクラスのプロトタイプです。 よって、 $$J = ||x_1 - \mu_{x_1}|| + ||x_2 -\mu_{x_2}|| + ...