非階層型クラスタリング手法
状態:-
閲覧数:1,118
投稿日:2016-08-22
更新日:2016-09-19
「クラスターの平均（means）を用い、予め決められたクラスター数「k」個に分類する」ことに由来
・「MacQueen」,「Anderberg」,「Forgy」らにより提案された
1967年
・「James MacQueen」が、「k-means」 と命名
k-means法のアルゴリズム
・複数ある
・「MacQueen」,「Anderberg」,「Forgy」らにより提案された
1967年
・「James MacQueen」が、「k-means」 と命名
k-means法のアルゴリズム
・複数ある
K-means 法 の アルゴリズム
一般的な流れ
データ数
・n
クラスタ数
・k
・まず事前に分割したいクラスター数を指定
1.シードをランダム選出
・サンプルの中から、予め設定した「分割したいクラスター数と同じ数のサンプル」をランダムに選出
・選出したサンプルをシード（seed = 種）と言う
2.各サンプルと各シードに対する距離を計算。各サンプルに最も近いシードを求める
・各サンプルを、「最も近いシードと同じクラスターに属する」と仮決定
3.クラスターの重心という架空の点をそれぞれ求める
・重心は、各クラスターの平均値をもとに算出
4.2度目のクラスター分け
・この重心を新しいシードとして、最初と同様に、それぞれのサンプルを「最も近いシード」と「同じクラスター」に属するよう「仮クラスター分け」
5.2度目の各クラスター重心を求める
・クラスター構成が変わったため、そのクラスターの平均値を表わす重心も移動
6.以下、「重心を求め、クラスタリングをしなおすという手法」を繰り返せなくなるまで継続
・全ての クラスタ割り当てが変化しなかった場合、あるいは変化量が事前に設定した一定の閾値を下回った場合に、収束したと判断して処理を終了する
・そうでない場合は新しく割り振られたクラスタから 重心 を再計算して上記の処理を繰り返す
結果
最初のクラスタのランダムな割り振りに大きく依存する
・1回の結果で最良のものが得られるとは限らない
対策案
1.何度か繰り返して行って最良の結果を選択する手法
2.k-means++法のように最初のクラスタ中心点の振り方を工夫する手法
k-means法の短所
初期値依存性
初期値（初期に選択される「核」となるk個のサンプル）依存性がある
・「同一データ」に対して「同一条件(距離など)」で計算しても、初期値が異なるだけで結果は大きく異なる
対策
・最適初期値での結果を採用
→ 良いクラスターを得るために、初期値を変えて何回か分析を実施し、平均クラスター内距離が最小になる初期値を選択する