K-means 法(K平均法)

統計

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

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

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

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

K-means 法 の アルゴリズム

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

一般的な流れ


データ数
・n

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

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

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

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

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

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

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




結果


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

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

k-means法の短所

 閲覧数:221 投稿日: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 N-Gram 29
11 Ordinal Scale 29
12 MeCab 29
13 Knuth–Morris–Pratt algorithm border 28
14 Hyper Estraier 28
15 Morris-Pratt algorithm border 27
16 Cross-Origin Resource Sharing 27
17 Morris-Pratt algorithm 27
18 Selenium 26
19 memcached 25
20 Hibernate 25
2022/7/01 3:52 更新
週間人気ページランキング / 6-24 → 6-30
順位 ページタイトル抜粋 アクセス数
1 Flash Video | コンテナフォーマット | プログラミング用語 306
2 curl | HTTPクライアント(ネットワーク) | プログラミング用語 286
3 ルーター | ネットワーク | プログラミング用語 281
3 ユースケース | 開発 | プログラミング用語 281
4 ベクトル | 数学 | プログラミング用語 236
5 デーモン | Linux | プログラミング用語 227
6 正規表現 | プログラミング | プログラミング用語 194
7 YouTube | API | プログラミング用語 171
8 チェックアウト | バージョン管理システム(開発) | プログラミング用語 117
9 分かち書き | 形態素解析 | プログラミング用語 63
10 Linux | プログラミング用語 57
11 リバースエンジニアリング | 開発 | プログラミング用語 54
12 ネットワークアドレス | ネットワーク | プログラミング用語 50
13 PowerShell | スクリプト | プログラミング用語 44
14 クローラ | 検索エンジン | プログラミング用語 31
14 可搬性 | プログラミング | プログラミング用語 31
15 Subversion | バージョン管理システム(開発) | プログラミング用語 27
16 アンチパターン | プログラミング | プログラミング用語 11
17 プログラミング用語 9
18 deflate | ネットワーク | プログラミング用語 8
2022/7/1 1:01 更新