Fusion étape par étape

Fait partie de la section Apprentissage non supervisé du Journey Machine Learning de Coddy. Leçon 16 sur 51.

Ce chapitre construit un arbre généalogique de vos données, puis le découpe en groupes. Voici dix ballons de sport, classés par taille et par poids :

Un diagramme en arbre représentant dix ballons de sport. Les petits ballons, comme les balles de golf, de tennis et de baseball, se rejoignent en bas d’un côté, les gros ballons, comme les ballons de football et de basket-ball, de l’autre, et une ligne en pointillés découpe l’arbre en ces deux groupes

L’arbre se développe de bas en haut. Commencez avec chaque point isolé, fusionnez les deux groupes les plus proches, puis répétez :

Cinq tentes le long d’une rivière, situées à 2, 7, 15, 19 et 33 mètres, dessinées sur cinq rangées. L’étape 1 fusionne 15 et 19, l’étape 2 fusionne 2 et 7, l’étape 3 réunit ces deux groupes, l’étape 4 ajoute 33

L’écart entre deux groupes est l’écart entre leurs moyennes. Une fusion, sous forme de listes :

groups = [[2], [7], [15, 19], [33]]
groups[0] = groups[0] + groups[1]  # fusionner les listes
groups.pop(1)  # supprimer [7], désormais dans le groupe 0
print(groups)

Cela affiche [[2, 7], [15, 19], [33]]. Fusion après fusion, c’est le regroupement agglomératif.

Défi

Moyen

Les familles plantent leurs parasols de plage les uns près des autres. Regroupe les 10 parasols de spots en les fusionnant, jusqu’à ce qu’il reste wanted groupes. closest_pair(groups) renvoie les positions i, j des deux groupes les plus proches.

Commence avec chaque parasol seul, dans une liste d’un élément.
Tant qu’il y a plus de groupes que wanted : affiche la fusion, réunis la paire, supprime le deuxième groupe.
Affiche les groupes restants.

Pour d’autres parasols et wanted égal à 3 :

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

Essayez vous-même

import numpy as np

# Emplacement des 10 parasols, en mètres par rapport au poste de secours
spots = [2, 9, 11, 31, 45, 46, 69, 74, 92, 96]


# Renvoie i, j (i < j) : les positions des deux groupes dont les moyennes sont les plus proches
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())

# Écrivez votre code ci-dessous