Fusión paso a paso

Parte de la sección Aprendizaje no supervisado del Journey de Machine Learning de Coddy. Lección 16 de 51.

Este capítulo crea un árbol genealógico de tus datos y después lo divide en grupos. Aquí tienes diez pelotas deportivas, según su tamaño y peso:

Un diagrama de árbol de diez pelotas deportivas. Las pelotas pequeñas, como las de golf, tenis y béisbol, se unen abajo en un lado; las grandes, como las de fútbol y baloncesto, en el otro, y una línea discontinua divide el árbol en estos dos grupos

El árbol crece de abajo hacia arriba. Empieza con cada punto por separado, une los dos grupos más cercanos y repite:

Cinco tiendas de campaña a lo largo de un río, a 2, 7, 15, 19 y 33 metros, dibujadas en cinco filas. En el paso 1 se unen 15 y 19; en el paso 2 se unen 2 y 7; en el paso 3 se unen esos dos grupos; en el paso 4 se añade 33

La distancia entre dos grupos es la distancia entre sus medias. Una fusión, expresada como listas:

groups = [[2], [7], [15, 19], [33]]
groups[0] = groups[0] + groups[1]  # une las listas
groups.pop(1)  # elimina [7], ahora está en el grupo 0
print(groups)

Esto imprime [[2, 7], [15, 19], [33]]. Fusión tras fusión: eso es agrupamiento aglomerativo.

Desafío

Intermedio

Las familias colocan sus sombrillas de playa muy cerca unas de otras. Agrupa las 10 sombrillas de spots fusionándolas hasta que queden wanted grupos. closest_pair(groups) devuelve las posiciones i, j de los dos grupos más cercanos.

Empieza con cada sombrilla sola, en una lista de una.
Mientras haya más grupos que wanted: imprime la fusión, une el par y elimina el segundo.
Imprime los grupos restantes.

Para otras sombrillas y wanted igual a 3:

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

Pruébalo tú mismo

import numpy as np

# Ubicación de 10 sombrillas de playa, en metros desde la torre del socorrista
spots = [2, 9, 11, 31, 45, 46, 69, 74, 92, 96]


# Devuelve i, j (i < j): las posiciones de los dos grupos cuyas medias están más próximas
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())

# Escribe tu código a continuación