【疑問】k-means法とウォード法、どっちもグループ分けやろ？デンドログラムってどこで切るん【G検定】

クラスタリングの手法で、k-means法とウォード法が出てくる
どっちもデータをグループに分けるんやろ？何が違うん

前提のおさらい。ユークリッド距離は2点をまっすぐ測った距離。クラスタリングは、この距離が近いものどうしを同じグループ（クラスタ）にまとめる教師なし学習

＞＞1
k-means法は、最初にクラスタの数 $k$ を決めて、次の2つをくり返す
1. 各データを一番近い中心（重心）のクラスタに入れる
2. 各クラスタの平均を新しい中心にする
中心が動かんくなったら終わり

＞＞3
数字で回す。1次元のデータ 1, 2, 3, 10, 11, 12 を $k=2$ で、最初の中心を2と3にすると
1回目：1と2は中心2に、3・10・11・12は中心3に入る。新しい中心は 1.5 と 9
2回目：1・2・3は1.5に、10・11・12は9に入る。新しい中心は 2 と 11
3回目は入れ替わりがなくて終わり。{1, 2, 3} と {10, 11, 12} に分かれた

＞＞4
最初の中心の選び方で、結果は変わらんの？

＞＞5
変わることがある。悪い場所から始めると、変なところで止まる
だから最初の中心を変えて何回か回して、クラスタ内のばらつきが一番小さい結果を選ぶのがふつう。$k$ の値も人が決めなあかん

ウォード法は、階層的なクラスタリング
最初は1点ずつが1つのクラスタ。そこから「くっつけたときに、クラスタ内のばらつき（平均からの差の2乗の合計）の増え方が一番小さい組」を順にくっつけていく
2つのクラスタA, Bをくっつけたときの増え方は

＞＞7
さっきのデータで計算すると
1と2をくっつける：$\frac{1\cdot 1}{2}(1-2{)}^2=0.5$
{1, 2} と 3：$\frac{2\cdot 1}{3}(1.5-3{)}^2=1.5$
{1, 2, 3} と {10, 11, 12}：$\frac{3\cdot 3}{6}(2-11{)}^2=121.5$
最後のくっつけだけ増え方が飛びぬけて大きい

＞＞8
くっつけた順番と、そのときの増え方を高さにして描いた木の図がデンドログラム（樹形図）
高さ121.5の手前で横に切れば2つのクラスタ、もっと低いところで切ればもっと細かく分かれる。クラスタの数を後から決められるのがええところ

＞＞9
それやったら、いつもウォード法を使えばええやん。$k$ を先に決めんでええし

＞＞10
データが多いと重い。全部のクラスタの組み合わせを比べながらくっつけていくから、何十万件もあると計算が追いつかん
k-means法は1回のくり返しがデータ数に比例するくらいで軽い。大きなデータではk-means法、少なめで分かれ方を見たいならウォード法、と使い分ける