K-means 法(K平均法)

統計

非階層型クラスタリング手法

 状態:-  閲覧数:931  投稿日:2016-08-22  更新日:2016-09-19  
「クラスターの平均(means)を用い、予め決められたクラスター数「k」個に分類する」ことに由来
・「MacQueen」,「Anderberg」,「Forgy」らにより提案された

1967年
・「James MacQueen」が、「k-means」 と命名

k-means法のアルゴリズム
・複数ある

K-means 法 の アルゴリズム

 閲覧数:268 投稿日:2016-08-25 更新日:2016-10-18 

一般的な流れ


データ数
・n

クラスタ数
・k
・まず事前に分割したいクラスター数を指定

1.シードをランダム選出
・サンプルの中から、予め設定した「分割したいクラスター数と同じ数のサンプル」をランダムに選出
・選出したサンプルをシード(seed = 種)と言う

2.各サンプルと各シードに対する距離を計算。各サンプルに最も近いシードを求める
・各サンプルを、「最も近いシードと同じクラスターに属する」と仮決定

3.クラスターの重心という架空の点をそれぞれ求める
・重心は、各クラスターの平均値をもとに算出

4.2度目のクラスター分け
・この重心を新しいシードとして、最初と同様に、それぞれのサンプルを「最も近いシード」と「同じクラスター」に属するよう「仮クラスター分け」

5.2度目の各クラスター重心を求める
・クラスター構成が変わったため、そのクラスターの平均値を表わす重心も移動

6.以下、「重心を求め、クラスタリングをしなおすという手法」を繰り返せなくなるまで継続
・全ての クラスタ割り当てが変化しなかった場合、あるいは変化量が事前に設定した一定の閾値を下回った場合に、収束したと判断して処理を終了する
・そうでない場合は新しく割り振られたクラスタから 重心 を再計算して上記の処理を繰り返す




結果


最初のクラスタのランダムな割り振りに大きく依存する
・1回の結果で最良のものが得られるとは限らない

対策案
1.何度か繰り返して行って最良の結果を選択する手法
2.k-means++法のように最初のクラスタ中心点の振り方を工夫する手法

k-means法の短所

 閲覧数:269 投稿日:2016-09-21 更新日:2016-10-26 

初期値依存性


初期値(初期に選択される「核」となるk個のサンプル)依存性がある
・「同一データ」に対して「同一条件(距離など)」で計算しても、初期値が異なるだけで結果は大きく異なる

対策
・最適初期値での結果を採用
→ 良いクラスターを得るために、初期値を変えて何回か分析を実施し、平均クラスター内距離が最小になる初期値を選択する










尺度

データクラスタリング / クラスタリング / クラスタ解析 / クラスター分析

コメント投稿(ログインが必要)



類似度ページランキング
順位 ページタイトル抜粋
1 Same-origin policy 36
2 Basecamp 35
3 Chromecast 32
4 リスト探索(list search)アルゴリズム 31
5 Flash Video 31
6 Senna 30
7 stable build 30
8 latest build 30
9 Lucene(ルシーン) 30
10 git push 29
11 MeCab 29
12 Ordinal Scale 29
13 N-Gram 29
14 Knuth–Morris–Pratt algorithm border 28
15 Hyper Estraier 28
16 Morris-Pratt algorithm border 27
17 Cross-Origin Resource Sharing 27
18 Morris-Pratt algorithm 27
19 Selenium 26
20 memcached 25
2023/2/06 1:34 更新