k-平均クラスタリング
アルゴリズム
入力
$p$次元のデータ$N$個と、自然数$k$が与えられているとする。
ステップ 1. 初期化
$k$個の点$\mu_{1} , \cdots , \mu_{k}$をランダムに定める。各$\mu_{j}$はクラスタ$M_{j}$の平均になる。
ステップ 2. 距離計算
$i$番目のデータ$x_{i}$と$j = 1 , \cdots , k$に対して$\| x_{i} - \mu_{j} \|$を計算する。その中で最も小さいものを選び、それを$x_{i} \in M_{j}$にする。各$i = 1 , \cdots , N$に対して繰り返す。
ステップ 3. $\mu_{j}$の更新
以下の更新を$j = 1 , \cdots , k$に対して繰り返す。 $$ \mu_{j} \gets \sum_{x \in M_{j}} {{ x } \over {| M_{j} |}} $$ 更新しても$\mu_{j}$がこれ以上変わらない場合、アルゴリズムを終了し、きちんと更新された場合はステップ 2に戻る。
出力
各クラスタの重心である$\mu_{j}$と、各データがどのクラスタに属するかを返す。
- ここで$\| \cdot \|$は、$l_{2}$ノルム、またはユーグリッドノルム、普通のノルムと呼ばれる距離の概念である。
説明
$k$平均クラスタリングは、与えられたデータを$k$個の類にクラスタリングする教師なし学習法である。上記のイラストは特に、$p=2$次元で与えられた$N=20$個のデータを$k=2$個の類に分けることを示している。
平均は二乗誤差を最小化する代表値であり、$k$平均クラスタリングはこの数学的事実に基づいてデータをうまく分類する。もっと簡単に説明すると、座標を足して平均を出すというのは、幾何学的なセンスからすると重心を意味するので、$\mu_{j}$はあるデータの中心に引き寄せられるわけだ。もちろん、これを保証するためには、より強い条件と数式的な説明が必要だが、そもそも$k$平均クラスタリングは単純さが魅力のアルゴリズムなので、この点に深く立ち入らない。
長所と短所
最大の問題は、この分類があまり正確でないということだが、これを補うための多くのアルゴリズムが出てきたにもかかわらず、単純さでこのアルゴリズムを圧倒するアルゴリズムはない。データサイエンティストの立場からすると、データを受け取ったらまず試すのは、まさしく$k$平均クラスタリングだ。クラスタリング一回で分析を終えるのではなく、分析を始めるにあたって感触を得るために使うアルゴリズムというわけだ。