k平均法とは

/機械学習

k平均法

k平均法(k-means method)とは、クラスタ分析の手法の1つで、クラスタの重心との距離を最も小さくする基準でクラスタを形成していく方法です。クラスタの数($k$)は固定とするため、この名前が付いています。

尚、クラスタ分析とは、対象(サンプル)間の距離を定義し、距離の近さによって対象を分類する分析方法の総称です。

k平均法の目的関数 $J$ を以下で定義します。ここで、$x$ はサンプル(総数 $n$ 個)です。$r_{ij}$ は、クラスタ $j$ にサンプル $x_i$ が含まれれば “1”、含まれなければ “0” の2値をとります。

$$J=\sum_{i=1}^n\sum_{j=1}^kr_{ij}(x_i-z_j)^2  -①$$

k平均法では、この $J$ を最小にする $r_{ij}$ を求めます。

尚 $z$ は、与えられた $r_{ij}$ の下、$J$ が最小値(停留値)をもつ条件として求められます。

$$\frac{\partial J}{\partial z_j}=-\sum_{i=1}^n2r_{ij}(x_i-z_j)=0$$$$z_j=\frac{\sum_{i=1}^nr_{ij}x_i}{\sum_{i=1}^nr_{ij}}  -②$$

このように、$z_j$ は各クラスタの重心を表すことが分かります。

アルゴリズム

k平均法のアルゴリズムは以下になります。尚、初期のクラスタ分けはランダム行い、このときの{$r_{ij}$}を $R_0$ とします。

  1. $R_l$(初期は $l=0$)の下、クラスタ重心(②)を計算する。
  2. 目的関数(①)を最小とするような $R_{l+1}$ を求める。
  3. 収束条件は $R_l=R_{l+1}$ とする。収束していなければ、ステップ1から繰り返す。

ステップ2については、$J$ を最小とするように、サンプルをクラスタ間で移動させる作業を行います。

$$m=\mathrm{arg} \mathrm{min}|x_i-z_m|$$$$r_{ij}=\left\{\begin{array}{ll}
1 & (j=m) \\
0 & (j\ne m)\end{array} \right.$$

従って、ステップ3の収束条件は、ステップ2で移動させるサンプルがなければ成り立つことになります。

k-medoids法

k-medoids 法では、k平均法の重心との距離の2乗を非類似度に置き換えます。非類似度を $d$ とすると、目的関数は以下で計算されます。

$$J=\sum_{i=1}^k\sum_{j=1}^nr_{ij}d(x_i,z_j)$$

k平均法ではサンプルの変数が制限されてしまうことや、クラスタの重心が外れ値に過敏になってしまう問題があるため、その点が考慮されています。

 

応用数学
物理数学、計算数学、情報・暗号、機械学習、金融工学、ゲーム理論
散策路TOP
古典物理、量子力学、物性論、数学、応用数学、力学、電磁気学、相対論、熱・統計力学、解析学、代数学、幾何学、統計分析、情報

 

タイトルとURLをコピーしました