Mesclando passo a passo

Parte da seção Aprendizado não supervisionado do Journey de Machine Learning da Coddy. Lição 16 de 51.

Este capítulo cria uma árvore genealógica dos seus dados e, em seguida, divide-a em grupos. Aqui estão dez bolas esportivas, por tamanho e peso:

Um diagrama em árvore com dez bolas esportivas. Bolas pequenas, como as de golfe, tênis e beisebol, se juntam embaixo de um lado, e bolas grandes, como as de futebol e basquete, do outro; uma linha tracejada divide a árvore nesses dois grupos

A árvore cresce de baixo para cima. Comece com cada ponto sozinho, junte os dois grupos mais próximos e repita:

Cinco barracas ao longo de um rio, a 2, 7, 15, 19 e 33 metros, desenhadas em cinco linhas. A etapa 1 junta 15 e 19, a etapa 2 junta 2 e 7, a etapa 3 une esses dois grupos, a etapa 4 adiciona 33

A distância entre dois grupos é a distância entre suas médias. Uma junção, usando listas:

groups = [[2], [7], [15, 19], [33]]
groups[0] = groups[0] + groups[1]  # junta as listas
groups.pop(1)  # remove [7], agora no grupo 0
print(groups)

Isso imprime [[2, 7], [15, 19], [33]]. Mesclagem após mesclagem: isso é agrupamento aglomerativo.

Desafio

Médio

As famílias plantam seus guarda-sóis de praia próximos uns dos outros. Agrupe os 10 guarda-sóis em spots por meio de fusões, até restarem wanted grupos. closest_pair(groups) retorna as posições i, j dos dois grupos mais próximos.

Comece com cada guarda-sol sozinho, em uma lista de um elemento.
Enquanto houver mais grupos do que wanted: imprima a fusão, junte o par, remova o segundo.
Imprima os grupos restantes.

Para outros guarda-sóis e 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]]

Experimente você mesmo

import numpy as np

# Onde estão os 10 guarda-sóis, em metros a partir da torre dos salva-vidas
spots = [2, 9, 11, 31, 45, 46, 69, 74, 92, 96]


# Retorna i, j (i < j): as posições dos dois grupos cujas médias são mais 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())

# Escreva seu código abaixo