k-means#

k平均法（k-means clustering）

教師なしクラスタリングアルゴリズムの一つ。 クラスタの平均を用い、与えられたクラスタ数k個に分類することから、MacQueen がこのように命名した。k-平均法（k-means）、c-平均法（c-means）とも呼ばれる。

\[ min_{Cj} f = \sum_{i=1}^k \sum_{x_i < C_j} ||x_i - m_j|| \]

実装例#

import numpy as np

k=4 #クラスタ数
n=200 # データ数
# 仮想データ。(n, 2)のサイズの標準正規分布乱数
data = np.random.randn(n, 2)
# 初期値のセントロイドをデータからランダムに選択
centroids = data[np.random.choice(np.arrange(n), size=(k,))]

for l in range(10):
	indexes = np.zeros(data.shape[0])
	for centroid in centroids:
		for i, x in enumerate(data):
			# 最も近いセントロイドのインデックス番号をindexesに入れる
			indexes[i] = np.argmin(np.sum((x-centroids)**2, axis=1))
		for i in range(k):
			centroids[i] = data[indexes==i].mean(axis=0)

アルゴリズム#

  1. 全データ点にランダムにクラスタを割り当てる

  2. 各クラスタの平均ベクトル（中心）を計算する

  3. 各データ点に、最も近いクラスタを割り当てる

  4. 収束するまで２，３の工程を繰り返す

問題点と対策#

  • cons:

    • 最初のランダムな割り振りやクラスの中心に結果が左右される

  • 対策

    • 何度も繰り返し実行

    • 最初のクラスタ中心点の振り方を工夫

    • kの値を変える

例題#

1次元の入力「-2.7, -1.3, 0.7, 3.5, 5.1」に対してk-meansを適用する

Q1. k=2とし、クラスタA, Bを考え、それぞれの中心の初期値を-3, 0とする。#

１回目のステップで各入力はどちらのクラスタに割り当てられるか？

-3までの距離

0までの距離

クラスタ

-2.7

0.3

2.7

A

-1.3

1.7

1.3

B

0.7

3.7

0.7

B

3.5

6.5

3.5

B

5.1

8.1

5.1

B

Q2. 各クラスタの中心はどう更新されるか？#

\[\begin{split} Aの中心=-2.7\\ Bの中心=(-1.3+0.7+3.5+5.1)/4=8/4=2 \end{split}\]

Q3. ２回めのステップで各入力はどちらのクラスタに割り当てられるか？#

-2.7までの距離

2までの距離

クラスタ

-2.7

0

4.7

A

-1.3

1.4

3.3

A

0.7

3.4

1.3

B

3.5

6.2

1.5

B

5.1

7.8

3.1

B

Q4. 各クラスタの中心はどう更新されるか？#

\[\begin{split} Aの中心=(-2.7-1.3)/2=-4/2=-2\\ Bの中心=(0.7+3.5+5.1)/3=9.3/3=3.1 \end{split}\]

Q5. 最終的に各入力はどちらのクラスタに割り当てられるか#

-2までの距離

3.1までの距離

クラスタ

-2.7

0.7

A

-1.3

0.7

A

0.7

2.7

2.4

B

3.5

5.5

0.4

B

5.1

B

Q6. A,Bの中心の初期値を-3, 5とすると１回目のステップで各入力はどちらのクラスタに割り当てられるか？#

-3までの距離

5までの距離

クラスタ

-2.7

0.3

7.7

A

-1.3

1.7

6.3

A

0.7

3.7

4.3

A

3.5

6.5

1.5

B

5.1

8.1

0.1

B

Q7. 各クラスタの中心はどう更新されるか？#

\[\begin{split} Aの中心=(-2.7-1.3+0.7)/3=-3.3/3=-1.1\\ Bの中心=(3.5+5.1)/2=8.6/2=4.3 \end{split}\]

Q8. 最終的にどう分類されるか？#

-1.1までの距離

4.3までの距離

クラスタ

-2.7

1.6

7.0

A

-1.3

0.2

5.5

A

0.7

1.8

3.6

A

3.5

4.6

0.8

B

5.1

6.2

0.8

B

Q9. k=3, A,B,Cの中心=-3.0, 0, 5.0とすると１回目のステップでどうクラスタ分けされるか？#

-3までの距離

0までの距離

5までの距離

クラスタ

-2.7

0.3

2.7

7.7

A

-1.3

1.7

1.3

6.3

B

0.7

3.7

0.7

5.7

B

3.5

6.5

3.5

1.5

C

5.1

-

-

0.1

C
\[\begin{split} A:-2.7\\ B:(-1.3+0.7)/2=-0.6/2=-0.3\\ C:(3.5+5.1)/2=8.6/2=4.3 \end{split}\]

Q9. 最終的には？#

-2.7までの距離

-0.3までの距離

4.3までの距離

クラスタ

-2.7

0

A

-1.3

1.4

1

5.6

B

0.7

3.4

1

3.6

B

3.5

-

3.8

0.8

C

5.1

-

-

0.1

C