段階的な統合

CoddyのMachine Learningジャーニー「教師なし学習」セクションの一部。レッスン 16/51。

この章では、データの系統樹を作り、それをグループに分けます。サイズと重量を基準にした10個のスポーツボールを見てみましょう。

10個のスポーツボールを示す樹形図。ゴルフボール、テニスボール、野球ボールのような小さなボールは片側の低い位置で合流し、サッカーボールやバスケットボールのような大きなボールは反対側で合流している。破線が樹形図をこの2つのグループに分けている

木は下から上へ成長します。まず、各点を単独のグループにし、最も近い2つのグループを結合して、これを繰り返します：

川沿いに2、7、15、19、33メートル地点に並ぶ5つのテントを5段に描いた図。ステップ1で15と19を結合し、ステップ2で2と7を結合し、ステップ3でその2つのグループを結合し、ステップ4で33を加える

2つのグループ間の距離は、それぞれの平均値の差です。リストをマージする例：

groups = [[2], [7], [15, 19], [33]]
groups[0] = groups[0] + groups[1]  # リストを結合する
groups.pop(1)  # [7]を削除する。現在はグループ0に含まれている
print(groups)

これは [[2, 7], [15, 19], [33]] を出力します。マージを繰り返す、つまり凝集型クラスタリングです。

チャレンジ

中級

家族はビーチパラソルを近くに立てます。spotsにある10本のパラソルを結合して、wanted個のグループが残るまでグループ分けしてください。closest_pair(groups)は、最も近い2つのグループの位置i、jを返します。

各パラソルを1つずつ、1要素のリストにして始めます。
wantedよりグループ数が多い間、結合内容を出力し、そのペアをまとめ、2番目のグループを削除します。
残ったグループを出力します。

別のパラソルの位置で、wantedが3の場合：

Merge [33] and [35]
Merge [30] and [33, 35]
Merge [3] and [8]
3 groups: [[3, 8], [30, 33, 35], [70]]

自分で試してみよう

import numpy as np

# 10本のビーチパラソルが立っている位置。監視塔からの距離をメートルで表す
spots = [2, 9, 11, 31, 45, 46, 69, 74, 92, 96]


# 平均値が最も近い2つのグループの位置 i, j (i < j) を返す
def closest_pair(groups):
    best_i, best_j = 0, 1
    best_gap = abs(np.mean(groups[0]) - np.mean(groups[1]))
    for i in range(len(groups)):
        for j in range(i + 1, len(groups)):
            gap = abs(np.mean(groups[i]) - np.mean(groups[j]))
            if gap < best_gap:
                best_i, best_j, best_gap = i, j, gap
    return best_i, best_j


wanted = int(input())

# 以下にコードを書いてください