ｋ平均法
ｋ平均法（k-means method）とは、クラスタ分析の手法の１つで、クラスタの重心との距離を最も小さくする基準でクラスタを形成していく方法です。クラスタの数（$k$）は固定とするため、この名前が付いています。
尚、クラスタ分析とは、対象（サンプル）間の距離を定義し、距離の近さによって対象を分類する分析方法の総称です。
ｋ平均法の目的関数 $J$ を以下で定義します。ここで、$x$ はサンプル（総数 $n$ 個）です。$r_{ij}$ は、クラスタ $j$ にサンプル $x_i$ が含まれれば “１”、含まれなければ “０” の２値をとります。
$$J=\sum_{i=1}^n\sum_{j=1}^kr_{ij}(x_i-z_j)^2 -①$$
ｋ平均法では、この $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$ は各クラスタの重心を表すことが分かります。
アルゴリズム
ｋ平均法のアルゴリズムは以下になります。尚、初期のクラスタ分けはランダム行い、このときの｛$r_{ij}$｝を $R_0$ とします。
- $R_l$（初期は $l=0$）の下、クラスタ重心（②）を計算する。
- 目的関数（①）を最小とするような $R_{l+1}$ を求める。
- 収束条件は $R_l=R_{l+1}$ とする。収束していなければ、ステップ１から繰り返す。
ステップ２については、$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.$$
従って、ステップ３の収束条件は、ステップ２で移動させるサンプルがなければ成り立つことになります。
k-medoids法
ｋ-medoids 法では、ｋ平均法の重心との距離の２乗を非類似度に置き換えます。非類似度を $d$ とすると、目的関数は以下で計算されます。
$$J=\sum_{i=1}^k\sum_{j=1}^nr_{ij}d(x_i,z_j)$$
ｋ平均法ではサンプルの変数が制限されてしまうことや、クラスタの重心が外れ値に過敏になってしまう問題があるため、その点が考慮されています。
