データマイニング
クラスター分析

クラスター分析の手法③(非階層クラスター分析)

非階層クラスター分析とは

非階層クラスター分析とは、異なる性質のものが混ざり合った集団から、互いに似た性質を持つものを集め、クラスターを作る方法の1つですが、階層クラスター分析と異なり、階層的な構造を持たず、あらかじめいくつのクラスターに分けるかを決め、決めた数の塊(排他的部分集合)にサンプルを分割する方法といえます。 階層クラスター分析と違い、サンプル数が大きいビッグデータを分析するときに適しています。ただし、あらかじめいくつのクラスターに分けるかは、分析者が決める必要があり、最適クラスター数を自動的には計算する方法は確立されていません。また後で述べる「初期値依存性」という問題点があります。非階層クラスター分析の代表的手法である、「k-means法」を次に説明します。非階層クラスター分析を用いた事例はこちらをご参照ください。

非階層クラスターのイメージ

図21.非階層クラスターのイメージ

k-means法のアルゴリズム概要(Lloydの例)

MacQueen,Anderberg,Forgyらにより提案された非階層型クラスタリング手法で、この名称は、「クラスターの平均(means)を用い、あらかじめ決められたクラスター数「k」個に分類する」ことに由来しています。k-means法のアルゴリズムは複数ありますが、ここではLloydの例で説明します。デモツールもご用意しましたので、サンプル数やクラスター数などを変えてお試しください。

ステップ1
クラスターの「核」となるk個のサンプルを選ぶ。(ここでは5個)

ステップ2
全てのサンプルとk個の「核」の距離を測る。

非階層クラスター生成 ステップ1、2

図22.非階層クラスター生成 ステップ1、2


ステップ3
各サンプルを最も近い「核」と同じクラスターに分割する。
(この時点で全てのサンプルがk種類に分けられた)

非階層クラスター生成 ステップ3

図23.非階層クラスター生成 ステップ3


ステップ4
k個のクラスターの重心点を求め、それを新たな核とする。
(ここでは重心点の位置が移動している)

ステップ5
重心点の位置が変化したら、ステップ2に戻る。
(重心が変化しなくなるまで繰り返す:ステップ2′~ステップ5"を参照)

非階層クラスター生成 ステップ4、5

図24.非階層クラスター生成 ステップ4、5


ステップ2′
重心が変化したので、再度全てのサンプルとk個の「核」の距離を測る。

ステップ3′
各サンプルを最も近い「核」と同じクラスターに分割する

非階層クラスター生成 ステップ2'、3'

図25.非階層クラスター生成 ステップ2'、3'


ステップ4′
k個のクラスターの重心点を求め、それを新たな核とする。
(ここでは重心点の位置がさらに移動している)

ステップ5′
重心点の位置が変化したら、ステップ2に戻る。
(重心が変化しなくなるまで繰り返す)

非階層クラスター生成 ステップ4'、5'

図26.非階層クラスター生成 ステップ4'、5'


ステップ2"
重心が変化したので、再度全てのサンプルとk個の「核」の距離を測る。

ステップ3"
各サンプルを最も近い「核」と同じクラスターに分割する

ステップ4"
k個のクラスターの重心点を求め、それを新たな核とする。

非階層クラスター生成 ステップ2"、3"、4"

図27.非階層クラスター生成 ステップ2"、3"、4"


ステップ5"
重心点の位置が変化したので、ステップ2に戻る。
(重心が変化しなくなるまで繰り返す)

ステップ6
重心が変化しなくなったので終了する。

非階層クラスター生成 ステップ5"、6"

図28.非階層クラスター生成 ステップ5"、6"


K-means法デモツール

2次元のサンプルデータ分布に対して、k-means法の各ステップの挙動を確認できるデモツールを用意しました。

【使い方】
・クラスター数を2~5の間で選択し「ステップ」ボタンをクリックしていくと k-means法によりクラスターが形成されていく過程を観察できます。
・データ量を変更したい場合はサンプル数を入力して「分布更新」ボタンを クリックしてください。
※「分布更新」ボタンをクリックするたびにランダムで分布の形状が変わります。



k-means法の初期値依存について

k-means法の一つの短所として、初期値(初期に選択される「核」となるk個のサンプル)依存性があります。図29の3つのクラスターは、初期値を変えて、重心が変化しなくなるまで、繰り返し計算した時の結果です。同じデータを距離などを同じ条件にして計算しても、初期値が異なるだけで、結果が大きく違うことが分かります。従って、よいクラスターを得るためには、初期値を変えて何回か分析を実施し、平均クラスター内距離が最小になる初期値を選択するなど、最適初期値での結果を採用することが望ましいといえます。

初期値の違いによる結果の違い

図29.初期値の違いによる結果の違い

  • back