非階層クラスター分析のアルゴリズム

非階層クラスター分析のための手法は複数存在しますが、ここでは最もポピュラーな手法であり、
当社でも用いているk-means法のアルゴリズムを紹介します。

ある集団を、身長と体重という2つの変数を基準にして、3つのクラスターにk-means法で分類します。

図1

図1

使用するデータは左図にプロットされています。非階層クラスター分析では、まず事前に分割したいクラスター数を入力しなくてはなりません。今回のクラスター数は3です。
 
図2

図2

サンプルの中から、分割したいクラスター数と同じ数のサンプル(この場合では3)をランダムに選び出します。水色で表示しました。この3つのサンプルはシード(seed = 種)といいます。それぞれのサンプルと3つのシードに対する距離を計算し、それぞれのサンプルに最も近いシードをもとめます。そして、仮に、それぞれのサンプルを最も近いシードと同じクラスターに属すると決めます。
 
図3

図3

このようにピンク、水色、黄色の3つのクラスターを仮につくることができます。しかし、これでは明らかにクラスター分けされているとはいえません。非階層クラスター分析の目的は、同じクラスターの中に属するサンプルはなるべく似通っているように、異なるクラスターに属するサンプル間ではなるべく違いがはっきりするようにすることです。
 
図4

図4

そこで、3つのクラスターの重心という架空の点をそれぞれ求めます。重心は、各クラスターの平均値をもとに算出します。ピンクのクラスターの重心をもとめるには、ピンクのクラスターの平均体重・平均身長をもとめればよいのです。3つのクラスターからもとめられた重心をひし形で表わしました。
 
図5

図5

次にこの重心を新しいシードとして、最初と同様に、それぞれのサンプルを最も近いシードと同じクラスターに属するように仮にクラスター分けします。2度目のクラスター分けの結果を示しました。ピンクのクラスターの2つが水色に、水色のクラスターのうちの1つが黄色のクラスターに移動しました。ここでまた、それぞれの重心を求めます。クラスターの構成が変わったので、そのクラスターの平均値を表わす重心も移動します。
 
図6

図6

前ステップでもとめた新しいクラスターをもとに、新しい重心を求め、クラスター分けをしなおしています。前ステップで図の上の方にあるサンプルを失ったピンクのクラスターの重心が多少下方向に移動し、そのそのためさらにもう一つのサンプルを水色のクラスターにとられていることがわかります。
 
図7

図7

また同じことを行ないます。水色のクラスターがピンクのクラスターから左方向のサンプルを獲得したため、重心が左に移動し、黄色との境界線上のサンプルを失いはじめました。
 
図8

図8

水色の重心がさらに右側へ移動し、もう一つのサンプルを黄色のクラスターにとられました。この時点できれいに分かれているように見えますが、実際いままで繰り返したステップをこれ以降何度繰り返しても、これ以上クラスターに変化はありません。
 
図9

図9

このように、重心をもとめ、クラスタリングをしなおすという手法を繰り返せなくなるまで続けることがk-means法の考え方です。
 

クラスター分析TOPへ