Łączenie krok po kroku

Część sekcji Uczenie nienadzorowane ścieżki Machine Learning w Coddy. Lekcja 16 z 51.

W tym rozdziale utworzysz drzewo genealogiczne swoich danych, a następnie podzielisz je na grupy. Oto dziesięć piłek sportowych, według rozmiaru i wagi:

Diagram drzewa przedstawiający dziesięć piłek sportowych. Małe piłki, takie jak golfowa, tenisowa i baseballowa, łączą się nisko po jednej stronie, a duże, takie jak piłka nożna i koszykowa, po drugiej; przerywana linia dzieli drzewo na te dwie grupy

Drzewo rośnie od dołu do góry. Zacznij od każdego punktu osobno, połącz dwie najbliższe grupy i powtarzaj:

Pięć namiotów wzdłuż rzeki na 2, 7, 15, 19 i 33 metrach, narysowanych w pięciu rzędach. Krok 1 łączy 15 i 19, krok 2 łączy 2 i 7, krok 3 łączy te dwie grupy, krok 4 dodaje 33

Odległość między dwiema grupami to odległość między ich średnimi. Łączenie list:

groups = [[2], [7], [15, 19], [33]]
groups[0] = groups[0] + groups[1]  # połącz listy
groups.pop(1)  # usuń [7], teraz znajduje się w grupie 0
print(groups)

To wypisuje [[2, 7], [15, 19], [33]]. Łączenie po łączeniu — to klasteryzacja aglomeracyjna.

Wyzwanie

Średni

Rodziny rozstawiają swoje parasole plażowe blisko siebie. Grupuj 10 parasoli w spots, łącząc je, aż zostanie wanted grup. closest_pair(groups) zwraca pozycje i, j dwóch najbliższych grup.

Zacznij od każdego parasola osobno, na liście jednoelementowej.
Gdy grup jest więcej niż wanted: wypisz połączenie, połącz parę, usuń drugą grupę.
Wypisz pozostałe grupy.

Dla innych parasoli i wartości wanted równej 3:

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

Spróbuj swoich sił

import numpy as np

# Położenie 10 parasoli plażowych, w metrach od wieży ratownika
spots = [2, 9, 11, 31, 45, 46, 69, 74, 92, 96]


# Zwraca i, j (i < j): pozycje dwóch grup, których średnie są najbliższe sobie
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())

# Wpisz swój kod poniżej