Penggabungan Langkah demi Langkah

Termasuk bagian Pembelajaran Tanpa Pengawasan dalam perjalanan Machine Learning di Coddy. Pelajaran 16 dari 51.

Bab ini menumbuhkan pohon keluarga dari datamu, lalu membaginya menjadi beberapa kelompok. Berikut sepuluh bola olahraga, berdasarkan ukuran dan berat:

Diagram pohon untuk sepuluh bola olahraga. Bola kecil seperti bola golf, tenis, dan bisbol bergabung di bagian bawah pada satu sisi, bola besar seperti bola sepak dan bola basket di sisi lain, lalu sebuah garis putus-putus membagi pohon menjadi dua kelompok ini

Pohon tumbuh dari bawah ke atas. Mulailah dengan setiap titik sendiri, gabungkan dua kelompok terdekat, lalu ulangi:

Lima tenda di sepanjang sungai pada jarak 2, 7, 15, 19, dan 33 meter, digambar dalam lima baris. Langkah 1 menggabungkan 15 dan 19, langkah 2 menggabungkan 2 dan 7, langkah 3 menggabungkan kedua kelompok itu, langkah 4 menambahkan 33

Jarak antara dua kelompok adalah jarak antara nilai rata-ratanya. Penggabungan, dalam bentuk list:

groups = [[2], [7], [15, 19], [33]]
groups[0] = groups[0] + groups[1]  # gabungkan list
groups.pop(1)  # hapus [7], sekarang ada di grup 0
print(groups)

Ini mencetak [[2, 7], [15, 19], [33]]. Penggabungan demi penggabungan, itulah pengelompokan aglomeratif.

Tantangan

Sedang

Keluarga menanam payung pantai berdekatan. Kelompokkan 10 payung dalam spots dengan menggabungkannya, hingga tersisa wanted kelompok. closest_pair(groups) mengembalikan posisi i, j dari dua kelompok yang paling dekat.

Mulai dengan setiap payung sendiri, dalam list berisi satu payung.
Selama jumlah kelompok lebih banyak daripada wanted: cetak penggabungannya, gabungkan pasangan tersebut, lalu hapus kelompok kedua.
Cetak kelompok yang tersisa.

Untuk payung lain dan wanted bernilai 3:

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

Coba sendiri

import numpy as np

# Lokasi 10 payung pantai, dalam meter dari menara penjaga pantai
spots = [2, 9, 11, 31, 45, 46, 69, 74, 92, 96]


# Mengembalikan i, j (i < j): posisi dua kelompok dengan nilai rata-rata terdekat
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())

# Tulis kodemu di bawah ini