Schrittweises Zusammenführen

Teil des Abschnitts Unüberwachtes Lernen der Machine Learning-Journey von Coddy. Lektion 16 von 51.

In diesem Kapitel erstellst du einen Stammbaum deiner Daten und teilst ihn dann in Gruppen auf. Hier sind zehn Sportbälle, nach Größe und Gewicht:

Ein Baumdiagramm mit zehn Sportbällen. Kleine Bälle wie Golf-, Tennis- und Baseballbälle verbinden sich auf einer Seite weiter unten, große Bälle wie Fuß- und Basketbälle auf der anderen Seite, und eine gestrichelte Linie teilt den Baum in diese beiden Gruppen

Der Baum wächst von unten nach oben. Beginne mit jedem Punkt für sich allein, führe die beiden nächstgelegenen Gruppen zusammen und wiederhole den Vorgang:

Fünf Zelte entlang eines Flusses bei 2, 7, 15, 19 und 33 Metern, in fünf Reihen dargestellt. Schritt 1 verbindet 15 und 19, Schritt 2 verbindet 2 und 7, Schritt 3 führt diese beiden Gruppen zusammen, Schritt 4 fügt 33 hinzu

Der Abstand zwischen zwei Gruppen ist der Abstand zwischen ihren Mittelwerten. Eine Zusammenführung mit Listen:

groups = [[2], [7], [15, 19], [33]]
groups[0] = groups[0] + groups[1]  # die Listen zusammenfügen
groups.pop(1)  # [7] entfernen, jetzt in Gruppe 0
print(groups)

Dies gibt [[2, 7], [15, 19], [33]] aus. Zusammenführung um Zusammenführung, das ist agglomeratives Clustering.

Aufgabe

Mittel

Familien stellen ihre Sonnenschirme am Strand dicht beieinander auf. Gruppiere die 10 Sonnenschirme in spots durch Zusammenführen, bis wanted Gruppen übrig sind. closest_pair(groups) gibt die Positionen i, j der beiden Gruppen zurück, die einander am nächsten sind.

Beginne mit jedem Sonnenschirm einzeln in einer Liste mit einem Element.
Solange es mehr Gruppen als wanted gibt: Gib die Zusammenführung aus, füge das Paar zusammen und entferne die zweite Gruppe.
Gib die übrig gebliebenen Gruppen aus.

Für andere Sonnenschirme und wanted 3:

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

Probier es selbst

import numpy as np

# Standorte der 10 Sonnenschirme, in Metern vom Rettungsschwimmerturm entfernt
spots = [2, 9, 11, 31, 45, 46, 69, 74, 92, 96]


# Gibt i, j (i < j) zurück: die Positionen der beiden Gruppen, deren Mittelwerte am nächsten beieinanderliegen
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())

# Schreibe deinen Code unten