Unire passo dopo passo

Fa parte della sezione Apprendimento non supervisionato del percorso Machine Learning di Coddy. Lezione 16 di 51.

Questo capitolo crea un albero genealogico dei tuoi dati, poi lo divide in gruppi. Ecco dieci palloni sportivi, in base a dimensioni e peso:

Un diagramma ad albero di dieci palloni sportivi. Le palline piccole, come quelle da golf, da tennis e da baseball, si uniscono in basso da un lato, quelle grandi, come quelle da football e da basket, dall’altro, e una linea tratteggiata divide l’albero in questi due gruppi

L’albero cresce dal basso verso l’alto. Inizia con ogni punto da solo, unisci i due gruppi più vicini e ripeti:

Cinque tende lungo un fiume a 2, 7, 15, 19 e 33 metri, disposte su cinque righe. Il passaggio 1 unisce 15 e 19, il passaggio 2 unisce 2 e 7, il passaggio 3 unisce quei due gruppi, il passaggio 4 aggiunge 33

La distanza tra due gruppi è la distanza tra le loro medie. Un’unione, con le liste:

groups = [[2], [7], [15, 19], [33]]
groups[0] = groups[0] + groups[1]  # unisci le liste
groups.pop(1)  # rimuovi [7], ora nel gruppo 0
print(groups)

Questo stampa [[2, 7], [15, 19], [33]]. Unione dopo unione: questo è il clustering agglomerativo.

Sfida

Medio

Le famiglie piantano gli ombrelloni vicini tra loro. Raggruppa i 10 ombrelloni in spots effettuando fusioni, finché non restano wanted gruppi. closest_pair(groups) restituisce le posizioni i, j dei due gruppi più vicini.

Inizia con ogni ombrellone da solo, in una lista di uno.
Finché ci sono più gruppi di wanted: stampa la fusione, unisci la coppia, rimuovi il secondo.
Stampa i gruppi rimasti.

Per altri ombrelloni e wanted 3:

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

Provalo tu

import numpy as np

# Le posizioni di 10 ombrelloni, in metri dalla torre del bagnino
spots = [2, 9, 11, 31, 45, 46, 69, 74, 92, 96]


# Restituisce i, j (i < j): le posizioni dei due gruppi le cui medie sono più vicine
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())

# Scrivi il tuo codice qui sotto