どこかででた問題。折角なのでpythonでてきとーに実装してみた。ソースコードは以下に。 hcluster.py · GitHub

k-means

1次元ベクトルのデータ集合 {(2),(3),(4),(10),(11),(12),(20),(25),(30)} をk-means法でクラスタリングする。その際(a)-(c)の場合において、収束するまでのクラスタとセントロイドを示せ。

(a) k=2, 初期値(2,20)

1回目
data   :  [  2.   3.   4.  10.  11.  12.  20.  25.  30.]
prof   :  [ 0.  0.  0.  0.  0.  1.  1.  1.  1.]
cluster:  [  6.    21.75]
2回目
data   :  [  2.   3.   4.  10.  11.  12.  20.  25.  30.]
prof   :  [ 0.  0.  0.  0.  0.  0.  1.  1.  1.]
cluster:  [  7.  25.]
3回目
data   :  [  2.   3.   4.  10.  11.  12.  20.  25.  30.]
prof   :  [ 0.  0.  0.  0.  0.  0.  1.  1.  1.]
cluster:  [  7.  25.]
result
data   :  [  2.   3.   4.  10.  11.  12.  20.  25.  30.]
prof   :  [ 0.  0.  0.  0.  0.  0.  1.  1.  1.]
cluster:  [  7.  25.]

(注) 1回目のとき、11はクラスタ0の初期値2からもクラスタ1の初期値20からも共に等しい。この場合、どっちのクラスにアサインされるかはアルゴリズムに依存する(最終結果はほぼ変わらないはず)。

(b) k=3, 初期値(2,3,10)

1回目
data   :  [  2.   3.   4.  10.  11.  12.  20.  25.  30.]
prof   :  [ 0.  1.  1.  2.  2.  2.  2.  2.  2.]
cluster:  [  2.    3.5  18. ]
2回目
data   :  [  2.   3.   4.  10.  11.  12.  20.  25.  30.]
prof   :  [ 0.  1.  1.  1.  2.  2.  2.  2.  2.]
cluster:  [  2.           5.66666667  19.6       ]
3回目
data   :  [  2.   3.   4.  10.  11.  12.  20.  25.  30.]
prof   :  [ 0.  0.  1.  1.  1.  1.  2.  2.  2.]
cluster:  [  2.5    9.25  25.  ]
4回目
data   :  [  2.   3.   4.  10.  11.  12.  20.  25.  30.]
prof   :  [ 0.  0.  0.  1.  1.  1.  2.  2.  2.]
cluster:  [  3.  11.  25.]
5回目
data   :  [  2.   3.   4.  10.  11.  12.  20.  25.  30.]
prof   :  [ 0.  0.  0.  1.  1.  1.  2.  2.  2.]
cluster:  [  3.  11.  25.]
result
data   :  [  2.   3.   4.  10.  11.  12.  20.  25.  30.]
prof   :  [ 0.  0.  0.  1.  1.  1.  2.  2.  2.]
cluster:  [  3.  11.  25.]

(c) k=3, 初期値(12,25,30)

1回目
data   :  [  2.   3.   4.  10.  11.  12.  20.  25.  30.]
prof   :  [ 0.  0.  0.  0.  0.  0.  1.  1.  2.]
cluster:  [  7.   22.5  30. ]
2回目
data   :  [  2.   3.   4.  10.  11.  12.  20.  25.  30.]
prof   :  [ 0.  0.  0.  0.  0.  0.  1.  1.  2.]
cluster:  [  7.   22.5  30. ]
result
data   :  [  2.   3.   4.  10.  11.  12.  20.  25.  30.]
prof   :  [ 0.  0.  0.  0.  0.  0.  1.  1.  2.]
cluster:  [  7.   22.5  30. ]