Agrupamiento jerárquico

Después de largas horas de trabajo, terminé finalmente con el reto. Este script de Python genera una lista aleatoria de 10 vectores positivos y arma los clusters siguiendo las reglas del agrupamiento jerárquico, mostrando como va quedando cada cluster en consola. Además, si tienen instalado bokeh, grafica los puntos en el plano cartesiano. El código:

import random
import math
from bokeh.plotting import figure, show


class Vector:

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def get_coordinates(self):
        return (self.x, self.y)

    def __str__(self):
        return f'{self.x}#{self.y}'


def generate_random_vectors():
    vectors = []
    for _ in range(10):
        vector = Vector(random.randint(0, 10), random.randint(0, 10))
        vectors.append(vector)
    return vectors


# We can use euclidian distance because we are dealing with a cartesian plane
def get_euclidian_distance(vector_a, vector_b):
    return math.sqrt((vector_a.x - vector_b.x)**2 + (vector_a.y - vector_b.y)**2)


def run():

    vectors = generate_random_vectors()

    # Generating a graph of the vectors with bokeh
    x_points = [vector.x for vector in vectors]
    y_points = [vector.y for vector in vectors]

    p = figure(plot_width=400, plot_height=400)

    # add a circle renderer with a size, color, and alpha
    p.circle(x_points, y_points, size=20, color="navy", alpha=0.5)

    # show the results
    show(p)

    clusters = []

    # First, I define a first cluster formed by a first random vector
    initial_vector = random.choice(vectors)
    clusters.append([initial_vector])
    vectors.remove(initial_vector)

    # I'll implement memoization with a dict of distances
    distances = {}

    # I'll work with the first cluster of my clusters list
    cluster = clusters[-1][::]

    while vectors:
        closest_relationship = ''
        for vector_tracked in cluster:
            for vector in vectors:
                if f'{vector_tracked}*{vector}' not in distances.keys():
                    distance = get_euclidian_distance(
                        vector_tracked, vector)
                    distances[f'{vector_tracked}*{vector}'] = distance
                if closest_relationship:
                    if distances[closest_relationship] > distances[f'{vector_tracked}*{vector}']:
                        closest_relationship = f'{vector_tracked}*{vector}'
                else:
                    closest_relationship = f'{vector_tracked}*{vector}'

        next_vector_x = int(closest_relationship.split('*')[1].split('#')[0])
        next_vector_y = int(closest_relationship.split('*')[1].split('#')[1])

        for vector in vectors:
            if vector.x == next_vector_x and vector.y == next_vector_y:
                cluster.append(vector)
                vectors.remove(vector)
                clusters.append(cluster[::])
                break

    for cluster in clusters:
        for vector in cluster:
            print(vector)
        print('\n')
        print('*' * 20)
        print('\n')


if __name__ == "__main__":
    run()

Faltó mencionar al menos tres cosas super importantes relacionadas con el agrupamiento jerárquico.

1. Este enfoque es “deterministico”, es decir, que a menos que cambiemos la métrica, siempre vamos a obtener el mismo dendogram.
2. la complejidad del algoritmo es del orden O(n^2), lo cual hace que sea muy lento a medida que aumente la dimensionalidad de los datos. por eso se tiende a usar otros métodos como Kmeans.
3. Si la cantidad de datos es muy grande, el aspecto visual comienza a volverse confuso y poco atractivo.

La técnica de Feynman

Paso 1. Elige el concepto que quieres entender.
Puedes anotarlo como título en una página en blanco.
Paso 2. Pretende que le estás enseñando ésta idea a alguien más.
Explica (escribí) al concepto a ti mismo como si fuera que estas enseñando a un niño, utilizando palabras simples en vez de jerga técnica.
Paso 3. Si no puedes explicarlo bien, entonces vuelve al libro. Cada vez que te atasques, vuelve nuevamente al material y re-aprende esa parte que no puedes explicar bien.
Paso 4. Simplifica tu explicación y crea analogías. El objetivo de esta técnica es que puedas describir el concepto en palabras simples y claras. Si tardas mucho en explicarlo tienes que simplificarlo aún mas, usando analogías si es necesario.

Lo logré después de pensar mucho y también de algo de investigación de cómo se usa Bokeh, aunque creo que gráficamente podría mejorar.

Terminal:

Gráfica:

Código:

import random
import operator

from bokeh.plotting import figure, show
from bokeh.models import LabelSet, ColumnDataSource
from bokeh.palettes import Category20 as palette

def distancia_euclidiana(a, b):
    return (((a[0] - b[0]) ** 2) + ((a[1] - b[1]) ** 2)) ** 0.5

def distancia_manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def distancia_chebyshov(a, b):
    return max(abs(a[0] - b[0]), abs(a[1] - b[1]))

def generar_datos(rango, cantidad):
    datos = []

    for i in range(cantidad):
        datos.append((random.randint(0, rango), random.randint(0, rango)))
 
    return datos

def par_mas_cercano(centros, tipo):
    n = len(centros)
    distancias = {}

    for i in range(n):
        for j in range(n-i-1):
            if tipo == 1:
                distancia = distancia_euclidiana(centros[i], centros[i + j + 1])
            elif tipo == 2:
                distancia = distancia_manhattan(centros[i], centros[i + j + 1])
            else:
                distancia = distancia_chebyshov(centros[i], centros[i + j + 1])

            distancias[(centros[i], centros[i + j + 1])] = distancia
    
    distancias_sorted = sorted(distancias.items(), key = operator.itemgetter(1))

    par_cercano = distancias_sorted[0][0]

    return par_cercano, distancias_sorted[0][1]

def agrupar(datos, tipo):
    
    clusters_dict = dict(zip(datos, range(len(datos))))

    x = []
    y = []
    names = []

    for coordenada in datos:
        x.append(coordenada[0])
        y.append(coordenada[1])
        names.append(str(datos.index(coordenada)))

    grafica = figure(title = 'Datos', x_axis_label = 'x', y_axis_label = 'y')
    grafica.circle(x, y)

    source = ColumnDataSource(data=dict(x=x, y=y, names=names))
    labels = LabelSet(x='x', y='y', text='names', level='glyph', x_offset=5, y_offset=5, source=source, render_mode='canvas')

    grafica.add_layout(labels)

    radio = 0.0

    while len(clusters_dict) > 0:

        print(f'\nClusters {len(datos) - len(clusters_dict) + 1} -> {clusters_dict}')

        centros = []

        for key in clusters_dict.keys():
            centros.append(key)

        if len(clusters_dict) > 1:
            par = par_mas_cercano(centros, tipo)

            print(f'Centros más cercanos -> {par[1]}')

            if type(clusters_dict[par[0][0]]) == int and type(clusters_dict[par[0][1]]) == int:
                new_value = (clusters_dict[par[0][0]], clusters_dict[par[0][1]])
            elif type(clusters_dict[par[0][0]]) == tuple and type(clusters_dict[par[0][1]]) == int:
                new_value = clusters_dict[par[0][0]] + (clusters_dict[par[0][1]],)
            elif type(clusters_dict[par[0][0]]) == int and type(clusters_dict[par[0][1]]) == tuple:
                new_value = (clusters_dict[par[0][0]],) + clusters_dict[par[0][1]]
            else:
                new_value = clusters_dict[par[0][0]] + clusters_dict[par[0][1]]
            
            x_tot = 0
            y_tot = 0

            for k in new_value:
                x_tot += datos[k][0]
                y_tot += datos[k][1]

            x_c = x_tot / len(new_value)
            y_c = y_tot / len(new_value)

            new_centro = (x_c, y_c)

            clusters_dict.pop(par[0][0])
            clusters_dict.pop(par[0][1])
            clusters_dict[new_centro] = new_value
            radio = par[1]

            grafica.circle(new_centro[0], new_centro[1], radius= radio, color = palette[11][(len(datos) - len(clusters_dict)) % len(palette[11])], fill_alpha = 0.1)
        
        else:
            break

    show(grafica)

if __name__ == "__main__":
    rango = int(input('Ingrese el rango de datos: '))
    cantidad = int(input('\nIngrese la cantidad de puntos: '))

    tipo_distancia = int(input('\nSeleccione el tipo de medicion: \n[1] = Euclidiana\n[2] = Manhattan\n[3] = Chebyshov\n\nSeleccion: '))

    datos = generar_datos(rango, cantidad)

    print(f'\nDatos iniciales: {datos}')

    agrupar(datos, tipo_distancia)

Entro en los comentarios después de solo haber sido capaz de generar los puntos aleatorios y no conseguir ni calcular la distancia mínima entre puntos y me encuentro con soluciones que no se me hubieran ocurrido en años… es verdaderamente desesperante descubrir que, después de haber hecho no sé cuántos cursos de DS y haber entendido perfectamente todo, no soy capaz de implementar un programa por mí mismo…

¿Soy el único que se siente así? ¿Cómo puedo aprender a utilizar mis conocimientos sin tener que romperme la cabeza en ejercicios imposibles sin ayuda de nadie? Aquellos que han logrado implementar su programa solos, ¿han hecho alguna carrera o curso de formación o son gente que se ha formado solo en Platzi?

(Pido por favor que nadie venga con el rollo de “esfuérzate y lo lograrás” porque son comentarios que me desesperan todavía más, puesto que yo también me esfuerzo mucho y no me parece un problema de dedicación)

Gracias y mucha suerte a todos

Agrupamiento jerárquico:

Aquí dejo mi aporte, solo funciona hasta 15 puntos (por los colores jeje). Me tomo horas y quería hacerlo animado y que fueran apareciendo los círculos pero no encontré como y me rendí. Si alguien sabe como animarlo, ¿podría decirme por favor?

15 puntos

10 puntos

5 puntos

Mi lógica fue la siguiente:

1. Crear puntos y almacenarlos en una lista
2. Preguntar a un elemento de la lista de puntos cual es el punto más cercano a él.
3. Obtengo el punto más cercano.
4. Pregunto al punto encontrado cual es el punto más cercano a él.
5. Si coinciden en ser recíprocos se crea un nuevo punto equidistante entre ellos.
   5.1. un círculo de color los encierra.
   5.2. remueve los puntos recíprocos de la lista de puntos.
   5.3. añade el nuevo punto a la lista de puntos.
6. Si no son recíprocos, regreso al punto 4.

Los círculos de color son los clusters creados.
Las cruces negras son los puntos creados originalmente
Los puntos negros más chicos son los puntos equidistantes creados.

Anexo el código:

import random
import sys
import matplotlib.pyplot as plt
import matplotlib as mpl
import matplotlib.animation

class Point:

    def __init__(self, x, y):
        self.x = x
        self.y = y


def create_points(number_of_points):
    points = []

    for _ in range(number_of_points):
        new_point = Point(random.randint(0,21), random.randint(0,21))
        points.append(new_point)

    return points


def distance(point1, point2, metric_distance = 1):

    if  metric_distance == 1:
        return (((point1.x - point2.x) ** 2) + ((point1.y - point2.y) ** 2)) ** 0.5
    elif metric_distance == 2:
        return abs(point1.x - point2.x) + abs(point1.y - point2.y)
    else:
        print('Introduce a metric')


def closer(point1, points):
    
    distances = []

    for point2 in points:

        if (point2.x == point1.x) and (point2.y == point1.y):

            continue

        else:

            distances.append(distance(point1, point2))

        if len(distances) == 1:
                closer_point = point2
                


        if len(distances) >= 2:

            if distances[-1] == min(distances):
                
                closer_point = point2

    return closer_point


def Hierarchical_clustering(points):
    point = points[0]
    x_points = [point.x for point in points]
    y_points = [point.y for point in points]
    plt.scatter(x_points, y_points, c = ['black'], s = size_choice(sizes), alpha = 0.05)


    if len(points) > 1:
        closer_point_to_original = closer(point, points)
        closer_point_to_closer = closer(closer_point_to_original, points)

        if point == closer_point_to_closer:
            new_point = Point((point.x + closer_point_to_original.x) / 2, (point.y + closer_point_to_original.y) / 2)
            points.remove(point)
            points.remove(closer_point_to_original)
            points.insert(0, new_point)
            plt.text(new_point.x, new_point.y,set_cluster(clusters), fontsize = 10, fontweight = 'bold')
            set_area = plt.Circle((new_point.x, new_point.y), distance(point, closer_point_to_original)/2, alpha = 0.15, color = color_choice(colors))

            
            ax = plt.gca()
            ax.set_aspect(1)
            ax.add_artist(set_area)

            
            
            points = Hierarchical_clustering(points)
        else:
            points.remove(closer_point_to_original)
            points.insert(0, closer_point_to_original)

            points = Hierarchical_clustering(points)
    
    return points

def color_choice(colors):
    
    color_selec = random.choice(colors)
    colors.remove(color_selec)
    
    return color_selec

def size_choice(sizes):
    size_selec = sizes[0]
    sizes.remove(size_selec)
    
    return size_selec

def set_cluster(clusters):
    cluster = clusters[0]
    clusters.remove(cluster)
    
    return cluster

if __name__ == '__main__':
    sys.setrecursionlimit(5000)
    figg=plt.figure(figsize=(10,10), dpi = 72)
    number_of_points = int(input('Introduce the number of points to cluster: '))
    colors = ['brown', 'red', 'tomato', 'sienna', 'orange', 'gold', 'yellow', 'lime', 'green', 'blue', 'turquoise', 'aqua', 'fuchsia', 'deeppink', 'blueviolet']
    sizes = [i*12 + 10 for i in range(30)]
    clusters = ['Cluster ' + str(i) for i in range(1,number_of_points)]
    points = create_points(number_of_points)
    original_points = points[:]
    x_points = [point.x for point in original_points]
    y_points = [point.y for point in original_points]
    for point in points:
        print('(' + str(point.x) + ',' + str(point.y) + ')')

    plt.scatter(x_points, y_points, c = ['black'],s=15)
    Hierarchical_clustering(points)
    plt.grid(True)


    plt.plot(x_points, y_points, 'kx',markersize=15)
    plt.show()

Me gustaría implementarle una interfaz gráfica a este código para que se vea como una animación a medida que se van formando los clusters. Alguien podría ayudarme? Aquí les dejo mi aporte 😃

import random

#generar coordenadas random
def generate_coordinates(number_points):
    points = []
    for i in range(number_points):
        order = i
        x = random.randint(0,20)
        y = random.randint(0, 20)
        points.append([order, x, y])
    return points

#calcular la distancia de todas con todas
def calculate_distances(points):
    distances = []
    for i in range(len(points)):
        for j in range(len(points)):#puntos a calcular con el point[i]
            if j + i + 1 < len(points):
                current_point = points[i]
                next_point = points[j + i + 1]
                distance = ((current_point[1] - next_point[1])**2 + (current_point[2] - next_point[2])**2)**0.5
                distances.append([current_point[0], next_point[0], distance])
    return distances

#buscar la minima entre 2
def search_min_distance(distances):
    only_distances = []
    for distance in distances:
        only_distances.append(distance[2])
    min_vector = min(only_distances)
    for distance in distances:
        if min_vector == distance[2]:
            min_distance = distance
    return min_distance

def new_coordinate(pointA, pointB):
    x_average = (pointA[1] + pointB[1]) / 2
    y_average = (pointA[2] + pointB[2]) / 2
    new_cluster = [0, x_average, y_average]
    return new_cluster

def make_cluster(points):
    number_recursions = 0
    cluster = 'C'
    while len(points) > 1:
        distances = calculate_distances(points)
        min_distance = search_min_distance(distances)
        pointA = []
        pointB = []
        for point in points:
            if min_distance[0] == point[0]:
                pointA = point
                points.remove(point)
        for point in points:
            if min_distance[1] == point[0]:
                pointB = point
                points.remove(point)
        new_cluster = new_coordinate(pointA, pointB)
        new_cluster[0] = 'C', number_recursions
        points.append(new_cluster)
        number_recursions += 1
        print(points)

    return points

#agruparlas
if __name__ == "__main__":
    number_points = 10
    points = generate_coordinates(number_points)
    print(points)
    clusters = make_cluster(points)

https://www.instintoprogramador.com.mx/2019/07/clustering-jerarquico-con-python-y.html

para los que quieran ver como se realiza el cluster con sklearn

y cuando se explicó lo de feynman?? por lo que veo del concepto en google es un conjunto de unos pocos pasos para llegar a una explicación de un concepto. Por lo tanto mi input deberia ser un concepto pero esto me lleva a pensar cosas que creo que me salgo totalmente del propósito del profesor. Y veo que las respuestas de los alumnos son simplemente algoritmos para hacer la agrupación que se explica en el video. ¿eso es lo que hay que hacer? por que de lo contrario sinceramente no se me ocurre ni como comenzar un algoritmo que vaya filtrando y discriminando palabras como para darle sentido a una explicación final de un concepto. Estoy perdido. Se agradece orientación.

Mi código:

import math
from random import randint

class Punto():
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def getData(self):
        return [self.x, self.y]

    def point_print(self):
        return 'p(' + str(self.x) + ', ' + str(self.y) + ')'

    def __repr__(self):
        return self.point_print()

    def __str__(self):
        return self.point_print()

    def isEqual(self,otro_punto):
        return (self.x == otro_punto.x) and (self.y == otro_punto.y)

def metrica_euclidiana(punto1, punto2):
    return math.sqrt((punto1.x - punto2.x)**2 + (punto1.y - punto2.y)**2)

def metrica_manhattan(punto1, punto2):
    return abs(punto1.x - punto2.x) + abs(punto1.y - punto2.y)

def metrica_chebyshev(punto1, punto2):
    return max(abs(punto1.x-punto2.x),abs(punto1.y - punto2.y))

def listar_distancias(lista_puntos, funcion_distancia):
    distancias = []
    copy_list = lista_puntos[:]
    while len(copy_list)>1:
        ref = copy_list.pop(0)
        point_list = []
        for punto in copy_list:
            dist = funcion_distancia(ref, punto)
            metric = (ref.getData(), punto.getData(), dist)
            point_list.append(metric)
        point_list.sort(key=lambda p: p[2])
        distancias.append(point_list[0])
    return distancias


if __name__ == "__main__":
    num_puntos = int(input('Ingrese la cantidad de puntos a generar: '))
    dist_functions = [metrica_euclidiana,metrica_manhattan,metrica_chebyshev]
    dist_select = int(input('''
            Seleccione el tipo de medicion:
            [0] = Euclidiana
            [1] = Manhattan
            [2] = Chebyshev
            
            Seleccion: '''))
    #Generamos un rango aleatorio de puntos
    puntos = []
    for _ in range(num_puntos):
        punto = Punto(randint(0,100), randint(0,100))
        puntos.append(punto)

    print(f'Lista inicial de puntos:\n{puntos}')

    while len(puntos) > 1:
        distancias = listar_distancias(puntos, dist_functions[dist_select])
        #print(f'minimos:\n{distancias}')
        for metrica in distancias:
            p1 = Punto(metrica[0][0],metrica[0][1])
            p2 = Punto(metrica[1][0],metrica[1][1])
            new_p = Punto((p1.x + p2.x)//2,(p1.y + p2.y)//2)
            for p in puntos:
                if p.isEqual(p1):
                    puntos.remove(p)
                    puntos.append(new_p)
            for p in puntos:
                if p.isEqual(p2):
                    puntos.remove(p)
        print(f'Lista de puntos:\n{puntos}')

Después de dos tardes planteandome el problema y las iteraciones, logre generar el algoritmo, y conseguí obtener el vector final, así como graficar todos los vectores, los generados aleatoriamente y los generados por un agrupamiento, y un algoritmo optimizado para calcular las distancias entre todos los vectores.

Este es el código:

# Algoritmo de Agrupamiento Jerarquico
import random
from bokeh.plotting import figure, show, output_file
import os

# limpiamos la consola
os.system('clear')

# lsita para pintar los vectores, 8 colores
colors = ['red', 'blue', 'green', 'cyan', 'orange', 'black', 'yellow', 'pink']

# clase para instanciar vectores
class Vector:
  # constructor de la clase, construimos coordenadas, si rand, entoces seran aleatorios
  def __init__(self, rand, x=0, y=0):
    if rand:
      self.x = random.randint(0,10)
      self.y = random.randint(0,10)
    else:
      self.x = x
      self.y = y

  # obtenemos las coordenadas del vector
  def getCoords(self):
    return self.x, self.y

  # si imprimimos la clase nos dara las coordenadas
  def __str__(self):
    return f'( {self.x}, {self.y} )'

# funcion para instanciar n nuevos vectores
def createRandomVectors(number):
  # aqui almacenaremos los vectores creados
  vectors = []

  for _ in range(number):
    # construimos el vector con la coordenada
    new_vector = Vector(rand=True)
    # y registramos el vector
    vectors.append(new_vector)

  # y retornamos los nuevos vectores
  return vectors

# funcion para graficar vectores
def plotVectors(vectores_random, vectores_nuevos):
  # coordenadas de vectores aleatorios
  x_coords_rand, y_coords_rand = [], []
  # iteramos el numero de vectores de number, los aleatorios
  for vector in vectores_random:
    # obtenemos las coordenadas de cada vector
    x,y = vector.getCoords()
    # y las registramos
    x_coords_rand.append(x)
    y_coords_rand.append(y)
    
  # coordenadas de vectores agrupados
  x_coords_group, y_coords_group = [], []
  # iteramos los vectores que se crearon por agrupamiento, los totales - los solicitados
  for vector in vectores_nuevos:
    # obtenemos las coordenadas de cada vector
    x,y = vector.getCoords()
    # y las registramos
    x_coords_group.append(x)
    y_coords_group.append(y)
  
  # obtenemos las coordenadas del vector resultante, se pintara sobre un vector_nuevo
  x, y = vectores_nuevos[len(vectores_nuevos)-1].getCoords()

  # y graficamos

  # nombre del html
  output_file("Agrupamiento.html")
  # creamos la grafica
  grafica = figure(plot_width=600, plot_height=600, title='Grafica de Vectores')

  # dibujamos los vectores generados aleatoriamente
  grafica.circle(x_coords_rand, y_coords_rand, size=15, color=colors[1], alpha=0.5)
  # dibujamos los vectores generados por la agrupacion
  grafica.circle(x_coords_group, y_coords_group, size=20, color=colors[4], alpha=0.5)
  # dibujamos el vector resultante
  grafica.circle(x, y, size=25, color=colors[0], alpha=0.5)

  # y renderizamos la grafica
  show(grafica)

# calcular la distancia entre dos instancias de Vector, dos puntos, por metodo euclidiano
def calcDistance(vector1, vector2):
  # obtenemos las coordenadas de los puntos
  x1, y1 = vector1.getCoords()
  x2, y2 = vector2.getCoords()
  # retornamos la distancia entre los puntos
  return ((x2 - x1)**2 + (y2 - y1)**2) ** .5

# funcion para tratar de ubicar un registro de un diccionario
def findKey(dic, value):
  # tratamos de buscar
  try:
    # retornamos la clave del valor del diccionario
    index = list(dic.values()).index(value)
    return list(dic.keys())[index]

  # si no se encuentra pues retornamos un False
  except KeyError:
    return False
  except ValueError:
    return False  
  else:
    return False
    
# funcion para regresar un diccionario que contenga las distancias entre cada punto
def getDistances(vectors):
  # Diccionario para las distancias
  # Estructura: 'a,b': distancia
  # ejemplo: '0,1': 10.2
  
  # diccionario, y lista de distancias
  distancias = {}
  valores = []
  # cantidad de vectores
  size = len(vectors)

  # definimos las listas para iterar
  i_puntos = list(range(size - 1)) # 0,1,2 itera el punto a respecto al cual calcula distancias
  i_sig = list(range(size))
  i_sig.pop(0) # 3,2,1 itera los segundos puntos para calcular

  # iteramos
  # iteramos el punto a para calcular distancias
  for p in i_puntos: # 0,1,2
    # obtenemos el indice del punto a
    punto_a = i_puntos[p]
    
    # iteramos los demas puntos para calcular la distancia del punto a y los demas puntos
    # representando i es el indice del iterador de puntos siguiente, y p el punto actual
    for i in range(len(i_sig)):
      # obtenemos el indice del punto b
      punto_b = i_sig[i]
      # en esta parte tenemos para iterar los puntos o vectores mediante punto_a y punto_b

      # calculamos la distancia entre los puntos
      distancia = calcDistance(vectors[punto_a], vectors[punto_b])

      # definimos la clave y valor para regitrar en el diccionario
      clave = f'{punto_a},{punto_b}'
      valor = distancia

      # registramos en el diccionario y la lista de distancias
      distancias[clave] = valor
      valores.append(valor)
      
    # para no repetir [dis]tancias eliminamos la primera de la cadena
    i_sig.pop(0)
  
  # ordenamos los valores antes de mandarlos
  valores.sort()

  # y retornamos el diccionario y los valores ordenados
  return distancias, valores

# funcio para obtener los indices de vectores pasando una clave de diccionario como 1,2
def getVectorIndex(clave):
  clave = list(clave)
  return int(clave[0]), int(clave[2])

# funcion para obtener el punto medio entre dos vectores, con el fin de agruparlos
def middlePoint(vector1, vector2):
  # obtenemos las coordenadas de los vectores
  x1, y1 = vector1.getCoords()
  x2, y2 = vector2.getCoords()
  # obtenemos las nuevas coordenadas medias
  new_x = (x2 + x1)/2
  new_y = (y2 + y1)/2
  # retornamos un nuevo vector con las coordenadas medias
  return Vector(False, new_x, new_y)
  
# funcion para agrupar vectores, recibe el diccionario de distancias y las distancias ordenadas
def agroup(dic, distancias, vectores):
  # lista de todos los vetcores para graficar, de primeras son los ya generados aleatoriamente
  nuevos_vectores = []

  # proceso para agrupar los vectores

  # iteramos la cantidad de vectores existentes, agrupamos, actualizamos y repetimos, hasta que solo hay 1
  for _ in range(len(vectores) - 1):
    # obtenemos la distancia menor de la lista de distancias
    dist_menor = distancias[0]
    # obtenemos la clave de dicha distancia
    clave = findKey(dic, dist_menor)
    # y de la clave los indices de los vectores
    v1, v2 = getVectorIndex(clave)
    # ahora obtenemos los vectores
    vector1 = vectores[v1]
    vector2 = vectores[v2]
    # calculamos las coordenadas del vector resultante, basicamente un punto medio
    new_vector = middlePoint(vector1, vector2)
    # ya tenemos el nuevo vector!
    nuevos_vectores.append(new_vector) # ahora lo agregamos a la lista para graficar
    # ahora, eliminamos de vectores los vectores agrupados
    vectores.pop(v1)
    vectores.pop(v2 - 1) # menos uno porque la lista se encogio -1 por el pop anterior
    # y registramos dentro de vectors el nuevo
    vectores.append(new_vector)

    # generamos un nuevo diccionario, lista de dist. mediante un nuevo calculo de distancias
    dic, distancias = getDistances(vectores)

  # ese 1 restante sera el vector resultante del agrupamiento de todos, y todos los vectores
  return vectores[0], nuevos_vectores

# funcion principal
def main(number):
  # lista para guardar todos los vectores
  vetcores_random = []

  # creamos los n vectores
  vectores = createRandomVectors(number)

  print('Vectores Generados:')

  # vemos los coordenadas de todos los vectores creados
  for v in vectores:
    # vemos las coordenadas de los vectores generados aleatoriamente
    print('-> ',v.getCoords())
    # los guardamos, porque seran eliminados de vectors por el agrupamiento
    vetcores_random.append(v)

  # obtenemos las distancias
  distancias, valores = getDistances(vectores)

  # vemos el diccionario de las distancias
  print('\nDiccionario de distancias:')
  print(distancias)

  # realizamos el agrupamiento, y obtenemos un grafo en forma de lista con los vectores
  vector_resultante, nuevos_vectores = agroup(distancias, valores, vectores)

  # vemos el vector resultante
  print('\nVector Resultante:',vector_resultante.getCoords())

  # y por ultimo graficamos
  plotVectors(vetcores_random ,nuevos_vectores)

if __name__ == "__main__":
  print('*' * 60)

  # solicitamos el numero de vectores a generar
  number = int(input('Cuantos vectores quieres generar: '))
  main(number)

  print('*' * 60)

Y así lucen las gráficas, los puntos azules son los aleatorios, los naranjas son los que resultaron de un agrupamiento, y el rojo es el resultante

En caso de no verse las imágenes aquí dejo los links:

• https://drive.google.com/file/d/1OfIRoVj4ndbf-Gom_LRh1iMdyUzQjxxD/view?usp=sharing
• https://drive.google.com/file/d/1ELugZkogHM_HbNX2ff6QWWfFPghVmM64/view?usp=sharing
• https://drive.google.com/file/d/1IsBPf_D2T6hcat6J3nlDIzj81rILU5ip/view?usp=sharing

este video me ayudó a entender más
https://www.youtube.com/watch?v=LGT9v1QMgTE&ab_channel=LuisSerrano

Code for group number in a matrix 10x10

import numpy as np 
import random

def matrix_creator():
    matrix = np.zeros((10 , 10))
    return matrix

def ramdom_positions(matrix):
    positions= []
    for _ in range(50):
        i = random.randint(1 , 7)
        j = random.randint(1 , 7)
        positions.append([i , j])
        matrix[i][j] = 1
    
    return positions

def proximity_sum(positions, matrix):
    for position in positions:
        for i in range(2):
            squares = ([(position[0] - (i + 1)) , (position[1] + (i + 1))]) , ([(position[0]) , (position[1] + (i + 1))]), ([(position[0] + (i + 1)) , (position[1] + (i + 1))]), ([(position[0] - (i + 1)) , (position[1])]),([(position[0]) , (position[1] + (i + 1))]), ([(position[0] - (i + 1)) , (position[1] - (i + 1))]),([(position[0] ) , (position[1] - (i + 1))]), ([(position[0] + (i + 1)) , (position[1] - (i + 1))])
            for square in squares:
                if matrix[square[0]][square[1]] > 0:
                    matrix[position[0]] [position[1]] = (matrix[square[0]][square[1]]) + (matrix[position[0]] [position[1]])
                    matrix[square[0]][square[1]] = 0

    return matrix   

if __name__ == "__main__":
    matrix = matrix_creator()
    positions = ramdom_positions(matrix)
    print('------------------------ Matrix Original------------')
    print(matrix)
    print('----------------------------------------------------')
    print('------------------------ Matrix grouped------------')
    Adding = proximity_sum(positions , matrix)
    print(Adding)
    ```

Este fue el código que hice, al parecer, funciona bien aún combinando coordenadas positivas y negativas, le puse bastantes prints para poder visualizar el proceso. Un saludo!

import random 
import math
coordenada_posibles = (-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,1,2,3,4,5,6,7,8,9,10)
puntos_arr = [] 
distancias_arr=[]
puntos_medios = []
puntos_a_prueba = {}

def crear_puntos(numero_puntos):
    for _ in range(0, numero_puntos):
        coordenadas = random.sample(coordenada_posibles, 2)
        puntos_arr.append(coordenadas)
    return puntos_arr

def medir_distancia_euclidiana(punto_inicial, punto_final):
    print(punto_inicial, punto_final)
    return math.sqrt(((punto_final[0] - punto_inicial[0])**2) + ((punto_final[1] - punto_inicial[1])**2))
    
def crear_punto_medio(punto_inicial,punto_final):
    punto_medio = ( (punto_inicial[0] + punto_final[0]) / 2 ,  (punto_inicial[1] + punto_final[1]) / 2)
    return punto_medio

def main():
    crear_puntos(5)
    print(f'Lista de puntos inicial: {puntos_arr}')
    while len(puntos_arr) > 1:
        print()
        print()
        print()
        print()
        puntos_medios.clear()
        contador_pruebas = 0
        distancias_arr.clear()
        puntos_a_prueba.clear()
        for punto_inicial in puntos_arr:
            for punto_final in puntos_arr[puntos_arr.index(punto_inicial) + 1 :]:
                distancia_medida = medir_distancia_euclidiana(punto_inicial, punto_final)
                distancias_arr.append(distancia_medida) 
                crear_punto_medio(punto_inicial, punto_final)
                puntos_medios.append(crear_punto_medio(punto_inicial, punto_final))
                puntos_a_prueba[contador_pruebas] = [punto_inicial, punto_final]
                contador_pruebas += 1

        distancia_minima = min(distancias_arr)
        print(f'Lista de distancias: {distancias_arr}')
        print(f'Distancia minima {distancia_minima}')
        print(f'Diccionario de puntos probados: {puntos_a_prueba}')
        print(f'Puntos Medios: {puntos_medios}')
        print(f'Punto a Crear {puntos_medios[distancias_arr.index(distancia_minima)]}')
        print(f'Puntos a Eliminar: {puntos_a_prueba[distancias_arr.index(distancia_minima)][0] , puntos_a_prueba[distancias_arr.index(distancia_minima)][1]}')
        puntos_arr.remove(puntos_a_prueba[distancias_arr.index(distancia_minima)][0])
        puntos_arr.remove(puntos_a_prueba[distancias_arr.index(distancia_minima)][1])
        puntos_arr.append(puntos_medios[distancias_arr.index(distancia_minima)])
        print(f'Nueva combinacion: {puntos_arr}')
    print(f'PUNTO FINAL: {puntos_arr}')


if __name__ == '__main__':
 
    main()

Decirlo es mucho más fácil que hacerlo, me costo desarrollar la lógica. En el proceso tuve que buscar referencias y ejemplos, al final encontré parte que adaptar y se comprende la funcionalidad.

from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score
import numpy as np

NUM_BINS = 10
NUM_TRIALS = 1000

NUM_TRAINING_EXAMPLES = 100

def single_run(num_bins):
    t_truth = np.random.uniform()
    print("t_truth: " + str(t_truth))
    single_features = np.random.uniform(0, 1, NUM_TRAINING_EXAMPLES)
    #print single_features
    
    bins = np.linspace(0, 1, NUM_BINS + 1)
    #print bins
    X_train_discretized = [[bins[i]] for i in np.digitize(single_features, bins)]
    #print X_train_discretized

    y_train = [1.0 if single_features[i] - t_truth > 0 else 0.0 for i in
               range(NUM_TRAINING_EXAMPLES)]
    
    #print(y_train)

    regr_discretized = DecisionTreeClassifier(max_depth=1)
    regr_discretized.fit(X_train_discretized, y_train)
    y_train_pred_discretized = regr_discretized.predict(X_train_discretized)

    train_accuracy = accuracy_score(y_train, y_train_pred_discretized)
    print ("Train Accuracy Discretized: ", train_accuracy)
    return train_accuracy

print ("Training discretized decision stump for %d trials" % (NUM_TRIALS))
accuracies = [single_run(NUM_BINS) for i in range(NUM_TRIALS)]
print ("Accuracy Mean for %d bins: %f" % (NUM_BINS, np.mean(accuracies)))

Notas:
El agrupamiento jerárquico es el algoritmo que agrupa objetos similares en clusters.
El algoritmo comienza tratando a un cluster de manera individual y luego realiza los siguientes pasos de manera recursiva:

1. Identifica los dos clusters dependiendo la distancia

2. Agrupa ambos clusters en uno

Distancias:

• Puntos más cercanos (con mayor similitud)

• Puntos más lejanos (con menor similitud)

• Puntos intermedios o promedios

El output final es un dendrograma que nos permitirá mostrar la relación entre grupos.

Dendrograma es otra forma de decir árbol.

Hola a todos,

Después de ver los aportes de los compañeros pude entender mejor, gracias!

Aquí está mi aporte, incluye los 3 “linkage” mencionados por el profesor y la opción de cambiar el tipo de métrica de distancia. El programa imprime en consola todos los clusters.

import math
import random

def euclidean_distance(u, v):
    assert len(u) == len(v)
    diff = [u[i] - v[i] for i in range(len(u))]
    sq = [d ** 2 for d in diff]
    return math.sqrt(sum(sq))

def single_linkage(cluster_a, cluster_b, distance):
    dist = [[distance(a, b) for a in cluster_a] for b in cluster_b]

    min_value = math.inf
    min_pair = [-1, -1]
    for i in range(len(cluster_a)):
        for j in range(len(cluster_b)):
            if dist[i,j] < min_value:
                min_value = dist[j][i]
                min_pair = [i, j]
    
    a = cluster_a[min_pair[0]]
    b = cluster_b[min_pair[1]]

    return a, b

def complete_linkage(cluster_a, cluster_b, distance):
    dist = [[distance(a, b) for a in cluster_a] for b in cluster_b]

    max_value = -math.inf
    max_pair = [-1, -1]
    for i in range(len(cluster_a)):
        for j in range(len(cluster_b)):
            if dist[i,j] > max_value:
                max_value = dist[j][i]
                max_pair = [i, j]
    
    a = cluster_a[max_pair[0]]
    b = cluster_b[max_pair[1]]

    return a, b

def average_linkage(cluster_a, cluster_b, distance):
    dim = 0
    if len(cluster_a) > 0:
        dim = len(cluster_a[0])
    elif len(cluster_b) > 0:
        dim = len(cluster_b[0])
    
    a = [sum([v[i] for v in cluster_a]) / len(cluster_a) for i in range(dim)]
    b = [sum([v[i] for v in cluster_b]) / len(cluster_b) for i in range(dim)]

    return a, b

def hierarchical_clustering(points, distance=euclidean_distance, linkage=average_linkage):
    clusters = [[p.copy()] for p in points]
    labels = [f'P{n}' for n in range(len(points))]
    dendrogram = []
    count = 0

    while len(clusters) > 1:
        print('Current clusters: ', clusters)

        min_dist = math.inf
        min_pair = [-1, -1]

        for i in range(len(clusters)):
            cluster_a = clusters[i]
            for j in range(i):
                cluster_b = clusters[j]

                a, b = linkage(cluster_a, cluster_b, distance)

                dist = distance(a, b)
                if dist < min_dist:
                    min_dist = dist
                    min_pair = [i, j]
        
        cluster_a = clusters[min_pair[0]]
        cluster_b = clusters[min_pair[1]]
        
        label_a = labels[min_pair[0]]
        label_b = labels[min_pair[1]]

        print(f'Minimum found: {min_dist} with {cluster_a} and {cluster_b}')

        group_label = f'C{count}'

        dendrogram.append({group_label: [label_a, label_b]})
        count += 1

        clusters.append(cluster_a + cluster_b)
        labels.append(group_label)

        clusters.pop(min_pair[0])
        clusters.pop(min_pair[1])

        labels.pop(min_pair[0])
        labels.pop(min_pair[1])
    
    return dendrogram

if __name__ == "__main__":
    dim = int(input('¿Qué dimensión tienen los datos?: '))
    size = int(input('¿Cuántos datos quieres generar?: '))
    points = [[random.randint(0, 10) for _ in range(dim)] for _ in range(size)]
    print('Point set', points)

    print(80*'=')
    dendrogram = hierarchical_clustering(points)
    print(80*'=')
    
    print('Dendrogram', dendrogram)

Hola compañeros,

Quiero compartirles mi código así como una animación de la salida producida. La verdad es que para generar el gif fue todo un dolor de cabeza y no guardó todas las propiedades de la animación original que produce mi programa. Aún soy un novato en esto de Matplotlib y en generar gráficos de calidad. Opté por trabajar con tuplas y mediante fuerza bruta calculé la distancia entre todos los puntos de mi código. Como bien comenta el profesor David, debe haber una manera mucho más óptima sobre cómo realizar esto y al finalizar el curso indagaré en el asunto.

Una librería que me fue de gran ayuda es combinations. La cual me ayudó a obtener todas las posibles combinaciones entre mis coordenadas (tuplas) y poder calcular la distancia euclidiana entre ellas. Tras calcular la distancia mínima, promedié la distancia entre puntos y así obtuve un nuevo punto medio el cual reemplazaba a los 2 puntos anteriores con la mínima distancia de todo el conjunto.

Saludos 😃

import random
import numpy as np
import matplotlib.pyplot as pl
import matplotlib.animation as animation
from matplotlib.animation import ImageMagickWriter
import math
from itertools import combinations

def main():

    cartesian_points = _define_random_points(10)
    _iterate_clustering(cartesian_points)

def _define_random_points(dimension):
    ret = set()
    while len(ret) < dimension:
        ret.add((random.randint(0,20), random.randint(0,20)))
    return list(ret)

def _calculate_initial_distance(cartesian_points):
    max_distance = 0

    for pair in combinations(cartesian_points, 2):
        coord1, coord2 = pair
        initial_distance = _calculate_euclidian_distance(coord1,coord2)

        if initial_distance > max_distance:
            max_distance = initial_distance

    return max_distance

def _iterate_clustering(cartesian_points):

    max_distance = _calculate_initial_distance(cartesian_points)
    calculated_distance = 0.0
    coord1 = ()
    coord2 = ()
    iteration = 1
    
    while(len(cartesian_points) != 2):
        continuous_graph_points(cartesian_points, iteration)
        max_distance = _calculate_initial_distance(cartesian_points)
        for i in range(0, len(cartesian_points)):
                for j in range(0, len(cartesian_points)):
                    if (cartesian_points[i] != cartesian_points[j]):
                        calculated_distance = _calculate_euclidian_distance(cartesian_points[i], cartesian_points[j])
                        if calculated_distance < max_distance:
                            max_distance = calculated_distance
                            coord1 = cartesian_points[i]
                            coord2 = cartesian_points[j]
    
        cartesian_points = _update_cartesian_point_set(cartesian_points, coord1, coord2)
        iteration += 1
    else:
        continuous_graph_points(cartesian_points, iteration)  

        coord1 = cartesian_points[0]
        coord2 = cartesian_points[1]

        iteration += 1
        cartesian_points = _update_cartesian_point_set(cartesian_points, coord1, coord2)
    
    continuous_graph_points(cartesian_points, iteration)

def _calculate_euclidian_distance(coord1,coord2):
     x1, y1 = coord1
     x2, y2 = coord2

     euclidean_distance = math.sqrt(math.pow(x1-x2,2)+math.pow(y1-y2,2))
     return euclidean_distance
    
def _calculate_medium_point(coord1, coord2):
    x1, y1 = coord1
    x2, y2 = coord2

    new_coordinate = ((x1+x2)/2,(y1+y2)/2)

    return new_coordinate

def _update_cartesian_point_set(cartesian_points, coord1, coord2):
    new_coordinate = _calculate_medium_point(coord1, coord2)
    cartesian_points.append(new_coordinate)
    cartesian_points = [point for point in cartesian_points if point != coord1]
    cartesian_points = [point for point in cartesian_points if point != coord2]

    return cartesian_points

def continuous_graph_points(cartesian_points, iteration):
    dimension = 1000/len(cartesian_points)

    dimension_array = [60] * len(cartesian_points)
    dimension_array[-1] = dimension * 2
    pl.ion()
    pl.scatter(*zip(*cartesian_points),dimension_array)

    pl.axis([0,35, 0, 35])
    pl.title('Agrupamiento Jerarquico iteracion {}'.format(iteration))
    pl.ylabel('Eje Y')
    pl.xlabel('Eje X')
    pl.grid()
    pl.draw()
    pl.pause(0.8)
        
    pl.clf()

if __name__ == "__main__":
    main()```

Bueno, en mi caso lo unico que me faltaria por hacer es el dendrograma, porque la mayoria de las librerias para graficar al hacer el dendograma hacian el clustering por mi.

Mi codigo lo que hace es generar una cantidad variable de puntos y en un ciclo while voy ejecutando el algoritmo hasta que quede un solo cluster.

Lo que hace en el ciclo es: encontrar a los 2 clusters que esten mas cerca uno del otro y tomando en cuenta el linkage type al comparar a los puntos que integran cada cluster.

Luego hace un merge entre esos 2 clusters, creando un nuevo cluster en el array y eliminando los otros 2 clusters.

y guardo adicionalmente en un array el historial de merge, que puntos se hacen merge a cual distancia y posteriormente eso se usaria para armar el dendrograma.

Pensaba hacer el dendrograma con turtle a mano, pero por falta de tiempo lo postergare

import random
import math

def generate_points(n):
	points = []
	for i in range(1,n+1):
		x = random.random()
		y = random.random()
		point = {
			'name': f'p{i}',
			'coords': [
				{
					'x': x,
					'y': y,
				}
			]
		}
		points.append(point)

	return points

def get_distance_between_clusters(cluster_a, cluster_b, linkage_type):
	distances = []
	for i in cluster_a['coords']:
		for j in cluster_b['coords']:
			distances.append( round( math.sqrt( (i['x']-j['x'])**2 + (i['x']-j['x'])**2 ), 3 ) )

	distance = None

	if linkage_type == 'single':
		distances.sort()
		distance = distances[0]
	elif linkage_type == 'complete':
		distances.sort(reverse=True)
		distance = distances[0]
	else:
		distance = sum(distances) / len(distances)

	return distance

def find_shortest_clusters(clusters, linkage_type):
	results = []
	for i in range(len(clusters)):
		for j in range(len(clusters)):
			if clusters[i]['name'] != clusters[j]['name']:
				distance = get_distance_between_clusters(clusters[i], clusters[j], linkage_type)
				results.append({
					'index_a': i,
					'index_b': j,
					'distance': distance
				})

	results = sorted(results, key=lambda k: k['distance'])

	return (results[0]['index_a'], results[0]['index_b'])

def merge(index_a, index_b, clusters, clusters_number):
	a = clusters[index_a]
	b = clusters[index_b]

	clusters.remove(a)
	clusters.remove(b)

	clusters.append({
		'name': f'c{clusters_number}',
		'coords': a['coords'] + b['coords']
	})

	return clusters

if __name__ == '__main__':
	points_number = int(input('Insert points number to generate: '))
	linkage_type = 'single'
	clusters = generate_points(points_number)
	clusters_number = 1
	merge_history = []

	while len(clusters) > 1:
		index_a, index_b = find_shortest_clusters(clusters, linkage_type)
		merge_history.append({
			'cluster_a': clusters[index_a],
			'cluster_b': clusters[index_b],
			'distance': get_distance_between_clusters(clusters[index_a], clusters[index_b], linkage_type)
		})
		clusters = merge(index_a, index_b, clusters, clusters_number)
		clusters_number += 1

Aquí esta mi código uwu me gusto este reto y en mi algoritmo puedes elegir el numero de clusters y de vectores, no supe como hacer para que el programa tomara colores sin el arreglo feo que esta ahí, agradecería si alguien me ayuda. También recibo todo tipo de criticas

from Dendogram import Dendogram
import random
from bokeh.plotting import figure, output_file, show

def generate_rnd_vectors(n,a,b):
	return [[random.randint(a,b),random.randint(a,b)] for _ in range(0,n)]

def link_dendograms(dendogram):
	n = len(dendogram)
	d1 = None
	d2 = None
	dist = float('inf')
	for i in range(n-1):
		for j in range(i+1,n):
			dist_ij = dendogram[i].distance(dendogram[j])
			if dist_ij < dist:
				dist = dist_ij
				d1 = dendogram[i]
				d2 = dendogram[j]
	aux = Dendogram(left = d1, right = d2)
	dendogram.remove(d1)
	dendogram.remove(d2)
	dendogram.append(aux)
	return dendogram

if __name__ == "__main__":
	
	output_file("clusters.html")
	fig = figure()
	no_clusters = 4
	no_vectors = 50

	vectors = generate_rnd_vectors(100,1,100)
	dendogram = [Dendogram(x = x_m,y = y_m) for [x_m,y_m] in vectors]
	while(len(dendogram) > no_clusters):
		dendogram = link_dendograms(dendogram)

	i = 0
	colors = ["orange","yellow","brown","green"]
	for den in dendogram:
		print(den.components)
		x_vals = [aux[0] for aux in den.components]	
		y_vals = [aux[1] for aux in den.components]	
		fig.circle(x_vals,y_vals,size=10,color = colors[i])
		i+=1
	show(fig)

En otro archivo defini mi clase Dendogram

class Dendogram:
	
	def __init__(self,left = None,right = None,x = None ,y = None):
		self.x = x
		self.y = y
		self.left = left
		self.right = right
		if not(x or y) and (left and right):
			lx,ly = self.left.position
			rx,ry = self.right.position
			self.x = lx + 0.5*(rx-lx)
			self.y = ly + 0.5*(ry-ly)

	def distance(self,other):
		ox,oy = other.position
		return ((self.x-ox)**2 + (self.y-oy)**2)**0.5

	@property
	def position(self):
		return [self.x,self.y]

	@property
	def components(self):
		if not (self.right or self.left):
			return [self.position]
		return self.left.components + self.right.components

Pude implementar este algoritmo, y creé esta visualización para ver el proceso 😄

el código para esto se encuentra aquí: código

La Agrupación Jerárquica es un tipo de algoritmo de Aprendizaje no Supervisado que se utiliza para agrupar puntos de datos no etiquetados. La Agrupación Jerárquica también agrupa los puntos de datos con características similares. En algunos casos, el resultado de la Agrupación Jerárquica y de K Means puede ser similar.

El objeto, de Scikit Learn, AgglomerativeClustering realiza una agrupación jerárquica utilizando un enfoque de abajo hacia arriba, cada observación comienza en su propio cúmulo, y los cúmulos se fusionan sucesivamente.

sklearn.cluster.AgglomerativeClustering()

def distancia(x, y):
    return math.sqrt((x[0] - y[0])**2 + (x[1] - y[1])**2)


def medio(x,y):
    return ((x[0] + y[0])/2, (y[1] + x[1])/2 )

def graf(x,y):
    plt.scatter(x, y, s = 300, c = 'green')
    plt.show()
    

def jerarquico(arreglo, cluster = []):

    if len(arreglo) == 1:
        graf(arreglo[0][0], arreglo[0][1])

    else:
        x = []
        y = []
        dist = {}
        n  = len(arreglo)

        n_cord1 = 0
        n_cord2 = 1
        cont = 0

        for cord1 in arreglo [ : n-1 ]:
            cont += 1
            for cord2 in arreglo[cont:]:
                d = distancia(cord1, cord2)
                dist[(n_cord1, n_cord2)] = d
                n_cord2 += 1
            n_cord1 += 1
            n_cord2 = n_cord1 + 1

        minimo = min(dist.values())

        for key in dist.keys():
            if dist[key] == minimo:
                puntos = key
                break


        cluster.append(arreglo[puntos[0]])
        cluster.append(arreglo[puntos[1] ] )

        punto_med = medio(arreglo[puntos[0]], arreglo[puntos[1]])

        for cord  in arreglo:
            y.append(cord[1])
            x.append(cord[0])
      
        
        n_arreglo = []
        for punto in arreglo:
            
            if punto == arreglo[puntos[0]] or punto == arreglo[puntos[1]]:
                continue
            else:
                n_arreglo.append(punto)
        n_arreglo.append(punto_med)
        graf(x,y)
        
        print('Vector {} Cluster {}'.format(arreglo, cluster) )
        jerarquico(n_arreglo, cluster)   

    
    
if __name__ == "__main__":
    arreglo = [(1,5), (2,1), (5,10), (6, 20), (8, 15), (10, 2), (12,12), (15,2)]
    jerarquico(arreglo)

Pruebenlo en jupyter notebook

import random
import math
from bokeh.plotting import figure, output_file, show


def get_random_points(number):
    pointsList = []

    for i in range(number):
        pointsList.append([random.randint(0, 10), random.randint(0, 10)])

    return pointsList


class RenderData:

    def __init__(self, coordinates):
        self.coordinates = coordinates
        self.level_two_coords = []

    def generate_new_level(self, coord_list):

        if len(coord_list) == 1:
            self.level_two_coords.append(coord_list[0])
        elif len(coord_list) == 0:
            return
        else:
            new_coord, nearest_coord_index = self.calculate_distances_media(
                coord_list[0], coord_list[1::])

            self.level_two_coords.append(new_coord)
            coord_list.pop(nearest_coord_index)
            self.generate_new_level(coord_list[1::])

    def calculate_distances_media(self, origin_point, coordinates):
        """
        find the nearest point to the origin point and return the medium point between them and the index of the nearest point.
        """
        distances_array = []

        for coord in coordinates:
            distance = math.sqrt(
                (origin_point[0] - coord[0]) ** 2 + (origin_point[1] - coord[1]) ** 2)
            distances_array.append(distance)

        n_coord = distances_array.index(min(distances_array))

        return [(coordinates[n_coord][0] + origin_point[0]) / 2, (coordinates[n_coord][1] + origin_point[1]) / 2], n_coord

    def plot_points(self, coordinates, level_name):
        output_file(f'{level_name}.html')
        p = figure(plot_width=600, plot_height=600,
                   x_range=[0, 11], y_range=[0, 11])
        x = []
        y = []

        for i in coordinates:
            x.append(i[0])
            y.append(i[1])

        p.circle(x, y, size=20, color='navy', alpha=0.7)

        show(p)


if __name__ == "__main__":
    coordinates = get_random_points(11)
    h = RenderData(coordinates)
    h.generate_new_level(h.coordinates)
    h.plot_points(h.coordinates, 'level-one')
    h.plot_points(h.level_two_coords, 'level-two')

Este es mi resultado del reto utilizando puro Python. Es una implementación muy sencilla explicando como se agrupan los dos puntos más cercanos de forma iterativa. 🤓🤓

def obtener_distancias(points):
    """Calcula la distancia de puntos de una lista.

    Parámetros: points list [int, int, int]

    Retorna: Lista de distancias_calculadas [int, int, int]
    """
    points_size = len(points) - 1
    distancias_calculadas = []
    position_counter = 1

    for i in range(len(points) - 1):
        for j in range(points_size):
            # print(points[i])
            # print(points[j + position_counter])
            distancias_calculadas.append(distancia(points[i], points[j + position_counter]))

        position_counter += 1 #Recorre una posición para calcular las posiciones siguientes
        points_size -= 1 #Disminuye el alcance del rango para no exceder la lista de vectores

    print(f'Distancias calculadas: {distancias_calculadas}')
    return distancias_calculadas


def obtener_distancia_mas_corta(distancias):
    """De una lista de distancias identifica la más corta.

    Parámetros: distancias list [int, int, int]

    Retorna: Lista con el valor de la distancia menor con sus identificadores de punto [int, int, int]
    """
    valores_distancias = []
    for distancia in distancias:
        valores_distancias.append(distancia[0])

    distancia_menor = min(valores_distancias)
    # print(valores_distancias)
    # print(distancia_menor)

    distancia_mas_corta = []
    for distancia in distancias:
        if distancia_menor == distancia[0]:
            distancia_mas_corta = distancia

    # print(distancia_mas_corta)
    return distancia_mas_corta


def distancia(punto_1, punto_2):
    """Calcula la distancia euclidiana entre dos puntos.

    Parámetros: punto_1, punto_2 list [int, int, int]

    Retorna: Una lista con el cálculo de la distancia y los identificadores de cada punto. [int, int, int]"""
    a = punto_1[1]
    b = punto_1[2]
    c = punto_2[1]
    d = punto_2[2]
    id_punto_1 = punto_1[0]
    id_punto_2 = punto_2[0]

    result = ((a - c)**2 + (b - d)**2)**0.5 #Cálculo de distancia euclidiana

    return [result, id_punto_1, id_punto_2]


def crear_cluster(distancia_mas_corta, vectors):
    """Agrupa dos puntos en un solo punto que está en medio de esos dos.

    Parámetros:
    distancia_mas_corta list [float, int, int]
    vectors list [list, list, ...]

    Retorna: Una lista con el cluster creado en forma de punto y los id de los puntos con los que se creó. 
    tuple (list, int, int)
    """
    # puntos_a_agrupar = []

    punto_a_agrupar_1 = vectors[distancia_mas_corta[1]]
    punto_a_agrupar_2 = vectors[distancia_mas_corta[2]]
    # puntos_a_agrupar.append(vectors[distancia_mas_corta[1]]) #Accediendo a puntos dentro de los vectors con sus id.
    # puntos_a_agrupar.append(vectors[distancia_mas_corta[2]])

    a = punto_a_agrupar_1[1]
    b = punto_a_agrupar_1[2]
    c = punto_a_agrupar_2[1]
    d = punto_a_agrupar_2[2]
    id_punto_1 = punto_a_agrupar_1[0]
    id_punto_2 = punto_a_agrupar_2[0]

    x = (a + c)/2 #Cálculo de coordenadas punto medio entre dos puntos.
    y = (b + d)/2

    id_punto = min(id_punto_1, id_punto_2)
    cluster = [id_punto, x , y]

    print(f'Cluster: {cluster}. Agrupa: {punto_a_agrupar_1}, {punto_a_agrupar_2}') #Cluster
    return (cluster, id_punto_1, id_punto_2)


def agrupamiento_jerarquico(vectors):
    while len(vectors) > 1:
        print(vectors)
        distancias = obtener_distancias(vectors)
        distancia_mas_corta = obtener_distancia_mas_corta(distancias)
        punto, eliminar_1, eliminar_2 = crear_cluster(distancia_mas_corta, vectors)

        vectors_copy = vectors.copy()
        for vector in vectors:
            if vector[0] == eliminar_1 or vector[0] == eliminar_2:
                vectors_copy.remove(vector)
        vectors_copy.append(punto)
        vectors = vectors_copy.copy()
        
        print('****'*20)

    print(f'Agrupamiento final: {vectors}')


if __name__ == "__main__":
    coordenadas = [[0, 5, 0], [1, 3, 2], [2, 4, 5], [3, 0, 4], [4, 4, 4]] #[id_punto, x, y]
    agrupamiento_jerarquico(coordenadas)

Le he dedicado la tarde a ésto, así que veo bien compartirlo:

Empezamos con unas sencillas clases: Point y Cluster, ambas heredando de PlainObject. Cluster tiene el atributo sub_clusters, donde contiene a otros clusters y a puntos. Leyendo este atributo se puede obtener el dendrograma.

import math

class PlainObject:
    def __init__(self, x: float, y: float, label: str = "generic_plain_object"):
        self.x = x
        self.y = y
        self.label = label

    def __str__(self):
        return f"{self.label}: ({self.x}, {self.y})\n"
    def __repr__(self):
        return f"{self.label}: ({self.x}, {self.y})\n"

class Cluster(PlainObject):
    def __init__(self, x, y, label = "generic_plain_object", sub_clusters = []):
        super().__init__(x, y, label)
        self.sub_clusters = sub_clusters

    def __str__(self):
        return str(self.sub_clusters)

    def __repr__(self):
        return repr(self.sub_clusters)


class Point(PlainObject):
    def __init__(self, x, y, label = "generic_point"):
        super().__init__(x, y, label)

def cartesian_distance_between(p1, p2):
    dx = p1.x - p2.x
    dy = p1.y - p2.y

    return math.sqrt(dx**2 + dy**2)

Con estas clases definidas, pasamos al código principal.

Almacenamos puntos generados aleatoriamente en una lista con generate_points(amount_of_points) y utilizamos organize_in_one_big_fucking_cluster(points) (sí, el nombre era “temporal”) para hacer el proceso que se ve en el vídeo:

1. Encontrar los puntos o clusters más cercanos entre sí.
2. Crear un cluster que los contenga y ponerlo en su lugar.
3. Dibujar el proceso (opcional)
4. Repetir el proceso de manera recursiva
5. Cuando la lista de puntos/clusters solo tenga 1 elemento, hemos terminado (caso base).

Admito que el código es algo feo, pero cumple su función y no sería muy difícil acicalarlo. Disfruten!

import random
import matplotlib.pyplot as plt

from point import Point, cartesian_distance_between, Cluster
from statistics import average

def generate_points(amount_of_points):
    points = []
    for i in range(amount_of_points):
        point = Point(x=random.uniform(0, 10), y=random.uniform(0, 10), label=i)
        points.append(point)

    return points
    
def get_least_separated_points(points):
    smallest_distance = {
        "value": float("inf"),
        "point1": 0,
        "point1_idx": 0,
        "point2": 0,
        "point2_idx": 0
    }

    for ref_idx,reference_point in enumerate(points):
        for mov_idx,moving_point in enumerate(points):
            if distance_between(reference_point, moving_point) < smallest_distance["value"] and reference_point is not moving_point:
                smallest_distance["value"] = distance_between(reference_point, moving_point)
                smallest_distance["point1"] = reference_point
                smallest_distance["point1_idx"] = ref_idx
                smallest_distance["point2"] = moving_point
                smallest_distance["point2_idx"] = mov_idx

    return smallest_distance

def print_points(points):
    smallest_distance = get_least_separated_points(points)
    print("Puntos:")
    for point in points:
        print(f">   {point}")
    print(f"Los puntos a menos distancia son: {smallest_distance['point1']} y {smallest_distance['point2']}")

def plot(points):
    plt.scatter(
            x = [point.x for point in points],
            y = [point.y for point in points],
    )
    plt.xlim((0, 11))
    plt.ylim((0, 11))
    plt.show()

def organize_in_one_big_fucking_cluster(points_plus_clusters):
    if len(points_plus_clusters) == 1:
        print("Todo organizado")
        return points_plus_clusters

    smallest_distance = get_least_separated_points(points_plus_clusters)

    point1 = points_plus_clusters[smallest_distance["point1_idx"]]
    point2 = points_plus_clusters[smallest_distance["point2_idx"]]
    cluster = Cluster(
            x = average([point1.x, point2.x]),
            y = average([point1.y, point2.y]),
            sub_clusters = [point1, point2]
    )

    points_plus_clusters[smallest_distance["point1_idx"]] = cluster
    points_plus_clusters.remove(point2)

    # Graficar cada paso (opcional)
    plot(points_plus_clusters)
    return organize_in_one_big_fucking_cluster(points_plus_clusters)

def main(amount_of_points, distance_between):
    points = generate_points(amount_of_points)
    plot(points)
    final_cluster = organize_in_one_big_fucking_cluster(points)

if __name__ == "__main__":
    # Podemos elegir distintas funciones para determinar la distancia, yo he elegido la cartesiana, la cual defino en el archivo point importado previamente

    distance_between = cartesian_distance_between
    amount_of_points = 10
    main(amount_of_points, distance_between)

Hecho

import random

class Punto:
    """Clase que contienne las coordenadadas (x,y) de un par de puntos 
    y el índice de cada uno de ellos en la matriz"""    
    def __init__(self, x1, y1, x2, y2, indice_p1, indice_p2):
        self.x1 = x1
        self.y1 = y1
        self.x2 = x2
        self.y2 = y2
        self.indice_p1 = indice_p1
        self.indice_p2 = indice_p2
    
    def calcular_distancia(self):
        """Distancia euclidiana"""
        distancia = ((self.x2 - self.x1)**2 + (self.y2 - self.y1)**2)**0.5
        return round(distancia, 2)
    
    def punto_medio(self):
        x_medio = round((self.x1 + self.x2)/2,2)
        y_medio = round((self.y1 + self.y2)/2,2)
        return(x_medio, y_medio)

def generar_punto():
    """Genera un punto en el rango x = [0 , 100], y = [0 , 100]"""
    nuevo_punto = (random.randint(0,100), random.randint(0,100))
    
    return nuevo_punto

def generar_matriz(n):
    """Genera n puntos diferentes"""
    puntos = []

    while len(puntos)<n:
        punto = generar_punto()
        if punto in puntos:
            continue
        puntos.append(punto)
    
    return puntos

if __name__ == '__main__':
    n = 0

    while n < 2 or n > 10201: #En el plano comprendido entre (0,0) y (100,0), caben 10.201 puntos (enteros) diferentes.
        try:
            n = int(input('¿Cuántos puntos (entre 2 y 10.201 puntos)? '))
        except ValueError:
            n = 0

    matriz = generar_matriz(n)
    print(matriz)
    copia_matriz = matriz   #Matriz de trabajo para conservar la matriz original

    while len(copia_matriz) > 1:    #Se repite el ciclo hasta que solo quede un punto.
        menor_distancia = 200
        nuevo_punto = []
        for i in range(len(matriz)):    #Se comparan todos los pares de puntos posibles y se guardan los resultados como un objeto de la clase Punto.
            for j in range(i + 1, len(matriz)):
                combinacion = Punto(matriz[i][0], matriz[i][1], matriz[j][0], matriz[j][1], i, j)
                
                distancia = combinacion.calcular_distancia()
                
                if distancia < menor_distancia: #Se actualizan los datos con el par de puntos que estén más cerca.
                    menor_distancia = distancia
                    nuevo_punto = combinacion
                    
        
        print(f'Índices a eliminar: {nuevo_punto.indice_p1}, {nuevo_punto.indice_p2}')
        print(f'La distancia entre estos puntos es: {menor_distancia}')

        if nuevo_punto.indice_p1 > nuevo_punto.indice_p2:   #Se borran los dos puntos, del mayor al menor índice.
            del copia_matriz[nuevo_punto.indice_p1]
            del copia_matriz[nuevo_punto.indice_p2]
        else:
            del copia_matriz[nuevo_punto.indice_p2]
            del copia_matriz[nuevo_punto.indice_p1]
        
        copia_matriz.append(nuevo_punto.punto_medio())  #Se agrega el nuevo punto.
        print(copia_matriz)

despues de buscar por horas me apoye de la siguiente librería:

https://scikit-learn.org/stable/auto_examples/cluster/plot_agglomerative_dendrogram.html#sphx-glr-auto-examples-cluster-plot-agglomerative-dendrogram-py

pero no logro que arranque, me ayudan por favor para corregir los errores…gracias 😃

![](

Devolviéndome a mis apuntes del curso de POO y algoritmos encuentro que esta clase de agrupamiento jerárquico es muy similar a los algoritmos de FIBONACCI.

me gastaría conocer las opiniones de los compañeros para saber si mi conclusión es correcta o hay elemento que no estoy teniendo en cuenta.

Yo intenté realizar un ejercicio parecido al del GIF del profesor, pero la verdad no pude realizar el dendrograma en codigo por eso lo realice a mano en excel:

a partir de los resultados:

y este fue mi codigo:

import math
import random

def NuevoVector(Vector1, Vector2):
    
    x1 = Vector1[0]
    x2 = Vector2[0]
    y1 = Vector1[1]
    y2 = Vector2[1]

    x = round(float((x1 + x2) / 2), 2)
    y = round(float((y1 + y2) / 2), 2)

    vectorN = [x, y]

    return vectorN

def DistanciaEuclidiana(vector1, vector2):
    
    return round(math.sqrt((vector1[0] - vector2[0])**2 + (vector1[1] - vector2[1])**2), 2)

def Vectores(numVectores):
    
    Lista = []
    for i in range(numVectores):
        i = [random.randint(0, 10), random.randint(0, 10)]
        Lista.append(i)
    
    return Lista

def Distancias(Vectores):
    
    distancias = {}
    a = 0
    for i in Vectores:
        b = 0
        for j in Vectores:
            clave = [a, b]
            clave = str(clave)
            if a != b:
                distancias[clave] = DistanciaEuclidiana(i, j)
            else:
                pass
            b += 1
        a += 1
    return distancias

def LeerClave(clave):
    a =''
    b =''
    i = ''
    for c in clave:
        if c == '[' or c == ' ':
            pass
        elif c == ',':
            break
        else: 
            a += c

    for c in clave[::-1]:
        if c == ']' or c == ' ':
            pass
        elif c == ',':
            break
        else: 
            i += c
            b = i[::-1]

    return a, b

def AgruparVectores(DistanciasVectores, Vectores):

    llave = min(DistanciasVectores, key=DistanciasVectores.get)
    valor = DistanciasVectores[llave]
    # print(f'La llave: {llave} \n tiene valor minimo: {valor}')
    
    vectores_agrupar = LeerClave(llave)
    a = int(vectores_agrupar[0])
    b = int(vectores_agrupar[1])
    vector1 = Vectores[a]
    vector2 = Vectores[b]

    vectorN = NuevoVector(vector1, vector2)

    if a > b:
        Vectores.pop(a)
        Vectores.pop(b)
    else: 
        Vectores.pop(b)
        Vectores.pop(a)
    
    Vectores.append(vectorN)

    return Vectores, vector1, vector2

def run(ListaVectores):
    if len(ListaVectores) > 1:
        distancias_vectores = Distancias(ListaVectores)
        intermedios = AgruparVectores(distancias_vectores, ListaVectores)
        nuevosVectores = intermedios[0]
        a = intermedios[1]
        b = intermedios[2]
        print(f'Se agruparon el vector {a} y {b} = {nuevosVectores[-1]}\nQuedando los {nuevosVectores} ')
        run(nuevosVectores)
    else:
        print(ListaVectores)
        

    pass

if __name__ == '__main__':
    vectores = Vectores(10)
    print(f'De los vectores {vectores}')
    run(vectores)
    print('fin')

Esté es mi código, tiene unas funciones más, como sacar una matriz de distancias.
No pude hacer los círculos en el gráfico, pero clasifica.

from matplotlib import pyplot as plt
import numpy as np
import pandas as  pd 
def generate_random_vectors():
    vectors = []
   # for _ in range(100):
                                     #coords #disp x  #disp y   #size
    a = np.random.multivariate_normal([10,0], [[3,1], [1,4]], size=[10,])
    b = np.random.multivariate_normal([0,20], [[3,1], [1,4]], size=[10,])
    for i in range(10): 
        vector = (a[i][0],a[i][1])
        vectors.append(vector)
        vector2 = (b[i][0],b[i][1])
        vectors.append(vector2)
    #vector = (a,b)
    #vectors.append(vector)
    return vectors
    

def distancia_euclidiana(d1,d2):
    x0=d1[0]
    x1=d2[0]
    y0=d1[1]
    y1=d2[1]
    return ((x1-x0)**2+(y1-y0)**2)**0.5

def plot(vector):
    x=[]
    y=[]
    for coord in vector: 
        #print(coord)
        x.append(coord[0])
        y.append(coord[1])
    plt.scatter(x,y,color="red")
    plt.show()

def puntos(punto, vectors): 
    vector_final = []
    for vector in vectors: 
        distancia = distancia_euclidiana(punto,vector)
        vector_final.append(distancia)     
    return vector_final

def matriz_distancias(vectors):
    index = 0
    matriz = []

    for vector in vectors: 
        vectores_obtenidos = puntos(vector, vectors)
        #print(vectores_obtenidos)
        index += 1
        matriz.append(vectores_obtenidos)
    data_df = pd.DataFrame(matriz)
    return data_df
    #print(matriz)
def punto_mas_cercano(coord,vector):
    cercano = 10000
    aux = (0,0)
    for i in vector:
        d = distancia_euclidiana(coord,i)
        if d !=0:
            if cercano>d: 
                cercano = d
                aux = i
                
    return aux


def vector_con_removidos(vector,coord,coord2): 
    vector_final = []
    for j in vector:
        if coord != j and coord2 != j:
            vector_final.append(j)
    
    
    return vector_final



def cluster(vector):
    index = 0
    lista_final = []
    vector_aux = []
    listax = []

    for i in vector: 
        if(len(lista_final)==0):
            coord = i
            coord2 = punto_mas_cercano(coord, vector)
            vector_aux = vector_con_removidos(vector, coord, coord2)
            listax.append(coord)
            listax.append(coord2)
            lista_final.append(listax[:index+2])
        else: 
            coord = coord2
            coord2 = punto_mas_cercano(coord, vector_aux)
            listax.append(coord2)
            lista_final.append(listax[:index+2])
            
            vector_aux = vector_con_removidos(vector_aux, coord, coord2)
        index +=1
    
    return lista_final
   
    

if __name__ == '__main__':
    vectors = generate_random_vectors()
    plot(vectors)
    matriz = matriz_distancias(vectors)
    vector = matriz[0]
    #p=punto_mas_cercano(vectors[0],vectors)
    lista_final = cluster(vectors)
    lista_final.pop()
    
    for lista in lista_final:
        x=[]
        y=[]
        for l in lista: 
            x.append(l[0])
            y.append(l[1])
        draw_circle = plt.Circle((0, 0), 10,fill=False)
        #axes.set_aspect(1)
        #figure, axes = plt.subplots()
        #axes.add_artist(draw_circle)
        plt.scatter(x,y)
        
        plt.show()

    
    dataframe = pd.DataFrame(lista_final)

Linkage criteria: Single linkage, es que tomamos los puntos más cercanos. Complete linkage, en los que tomamos los puntos más lejanos dentro del grupo. Average Linkage, que tomamos la distancia promedio entre los puntos.

La forma en cómo vamos a encontrar la distancia es crucial, pero también lo es, el medir la distancia.

Es vital para este algoritmo encontrar la distancia entre puntos.

Para este algoritmo, cada data point, es un grupo individual.

A la hora de pensar en algoritmos jerárquicos tenemos que pensar en las relaciones de cada uno de nuestros grupos.

El algoritmo jerárquico agrupa objetos similares en grupos llamados clusters. El algoritmo comienza tratando a cada objeto como un cluster individual y luego realiza los siguientes pasos de manera recursiva: Identifica lo dos clusters con menos distancia (los más similares), agrupa los dos clusters en uno nuevo. El output final es dendrograma que muestra la relación entre objetos y grupos. Es importante determinar qué medidad de distancia vamos a utilizar y los puntos a utilizar en cada cluster (linkage criteria)

Hola a todos, me llevó un día terminar mi código, debido a que me estanque con graficar los datos, quería graficarlos en forma de círculo, así como que un círculo contenía a otro círculo, osea un cluster dentro de otro cluster y así. Pero cuando lo graficaba con Bokeh los círculos no coincidían y no hacían la función de estar uno dentro de otro. Si alguien sabe como puedo graficar los datos como los describo, agradecería su ayuda. La parte técnica de los clusters todo muy bien, solo falto graficarlos para verlo visualmente.

Terminal:

Código:

import operator
import random
import math
from bokeh.plotting import figure, show

colores = ['red', 'green', 'brown', 'gray', 'cyan', 'magenta', 'purple', 'salmon', 'black']
cluster_number = 1
color = 0


def obtener_coordenadas(n_de_puntos):
    puntos = []
    for _ in range(n_de_puntos):
        x = random.randint(0, 10)
        y = random.randint(0, 10)
        coordenada = (x, y)
        puntos.append(coordenada)
    return puntos


def obtener_distancia_euclidiana(coordenada_a, coordenada_b):
    return math.sqrt((coordenada_a[0] - coordenada_b[0])**2 + (coordenada_a[1] - coordenada_b[1])**2)


def obtener_cluster(clusters, grafica):
    global cluster_number
    global color

    distancias = {}
    print(f'Cluster {cluster_number}: {clusters}')
    for p in clusters:
        point_index = clusters.index(p)
        for p2 in clusters:
            if not clusters.index(p2) == point_index:
                distancia = obtener_distancia_euclidiana(p, p2)
                distancias[p, p2] = distancia

    distancias_ordenadas = sorted(distancias.items(), key=operator.itemgetter(1))

    coordenada1 = distancias_ordenadas[0][0][0]
    coordenada2 = distancias_ordenadas[0][0][1]
    distancia = distancias_ordenadas[0][1]
    punto_medio = ( (coordenada1[0] + coordenada2[0]) / 2 , (coordenada1[1] + coordenada2[1]) / 2 )

    clusters.pop(clusters.index(coordenada1))
    clusters.pop(clusters.index(coordenada2))

    clusters.append(punto_medio)

    if len(clusters) == 1:
        cluster_number += 1
        print(f'Cluster {cluster_number}: {clusters}')
        return clusters
    else:
        cluster_number += 1
        return obtener_cluster(clusters, grafica)


def main(n_de_puntos, puntos):
    grafica = figure(title="Agrupamiento jerarquico",)
    x = [p[0] for p in puntos]
    y = [p[1] for p in puntos]

    cluster = obtener_cluster(puntos, grafica)


if __name__ == '__main__':
    n_de_puntos = int(input('Cuántos puntos quieres graficar: '))
    puntos = obtener_coordenadas(n_de_puntos) # Regresa la lista de los puntos
    main(n_de_puntos, puntos)

Me tomó un poco de tiempo, pero les comparto mi solución del reto.

import matplotlib.pyplot as plt
import imageio
import random
from collections import Counter


class Node:
    def __init__(self, x, y, cluster):
        self.x = x
        self.y = y
        self.cluster = cluster
        self.color = (random.randint(0,255), random.randint(0,255), random.randint(0,255))
        self.color = "#" + '%02x%02x%02x' % self.color
    
    def __str__(self):
        return f"({self.x},{self.y})\t--- Cluster: {self.cluster}"


def generate_random_nodes(n,range_min,range_max):
    """
    Generate n random nodes with integer coordinates between range_min and range_max.
    """
    nodes = []
    for i in range(n):
        nodes.append(Node(random.randint(range_min, range_max), random.randint(range_min, range_max), i))
    
    return nodes


def get_distance(node1, node2):
    """
    Return the Euclidean distance between 2 nodes.
    """
    return ((node2.x-node1.x)**2 + (node2.y-node1.y)**2)**0.5


def run_clustering(nodes, clusters, print_term=False):
    """
    Run a clustering iteration. Returns a tuple with the number of clusters and th cluster Counter.
    """
    global iteration
    short_dist = None

    # Get the closest nodes from diferent cliusters.
    for i, current_node in enumerate(nodes):
        for j in range(i+1,len(nodes)):
            comparing_node = nodes[j]
            distance = get_distance(current_node, comparing_node)
            if (short_dist == None or distance <= short_dist) and current_node.cluster != comparing_node.cluster:
                short_dist = distance
                ref1_node = current_node
                ref2_node = comparing_node
    
    # Join the closest nodes, the cluster with less elements joins with the bigger cluster.
    if clusters[str(ref1_node.cluster)] >= clusters[str(ref2_node.cluster)]:
        bigger_cl_node, smaller_cl_node = ref1_node, ref2_node
    else:
        bigger_cl_node, smaller_cl_node = ref2_node, ref1_node
    
    changing_nodes = [node for node in nodes if node.cluster == smaller_cl_node.cluster]
    for ch_node in changing_nodes:
        ch_node.cluster = bigger_cl_node.cluster
        ch_node.color = bigger_cl_node.color

    # Calculate the number of clusters
    clusters = Counter()
    for node in nodes:
        clusters.update({str(node.cluster):1})
        if print_term:
            print(node)
    num_clusters = len(clusters)
    iteration += 1
    print(f"Clusters: {num_clusters} -> {clusters}")

    return num_clusters, clusters       


def plot_clustering():
    fig, ax = plt.subplots()
    for node in nodes:
        ax.scatter(node.x, node.y, s=50, color=node.color)
    ax.set_title(f"""Hierarchical clustering: simple linkage | {len(nodes)} points
    Iteration: {iteration} | {len(clusters)} clusters""")
    fig.savefig(f"gif/iter-{iteration}.png")
    plt.close(fig)


def create_gif():
    images = []
    for i in range(iteration+1):
        images.append(imageio.imread(f"gif/iter-{i}.png"))
    imageio.mimsave("clustering.gif", images, duration=0.8)


if __name__ == "__main__":
    # Configure the experiment.
    nodes = generate_random_nodes(50,0,50)
    num_clusters_limit = 1
    print_term = False
    
    # Assign the initial status conditions 
    num_clusters = len(nodes)
    clusters = Counter([str(node.cluster) for node in nodes])
    iteration = 0

    # Show the initial status of the nodes
    if print_term:
        for node in nodes:
            print(node)
    
    plot_clustering()
    print(f"Clusters: {num_clusters} -> {clusters}")

    # Run the clustering iterations
    while num_clusters > num_clusters_limit:
        num_clusters, clusters = run_clustering(nodes, clusters, print_term)
        plot_clustering()
    
    create_gif()
        

Intentare hacer mi código

Intente hacerlo y me encontre con dos problemas, el primero era que no sabia como recolectar el nombre del grupo mas cercano, y el segundo era como generar la nueva ubicacion del grupo que se acaba de crear con la unicion de los dos grupos mas cercanos. Pero para nuestra suerte, hay librerias donde esta todo hecho de manera genial jajajaja asique usando esas librerias se puede hacer esto

import numpy as np
from scipy.cluster.hierarchy import dendrogram, linkage  
from matplotlib import pyplot as plt

if __name__ == "__main__":
    X = np.array([[5,3],  
        [10,15],
        [15,12],
        [24,10],
        [30,30],
        [85,70],
        [71,80],
        [60,78],
        [70,55],
        [80,91],])

    import matplotlib.pyplot as plt

    labels = range(1, 11)  
    plt.figure(figsize=(10, 7))  
    plt.subplots_adjust(bottom=0.1)  
    plt.scatter(X[:,0],X[:,1], label='True Position')

    for label, x, y in zip(labels, X[:, 0], X[:, 1]):  
        plt.annotate(
            label,
            xy=(x, y), xytext=(-3, 3),
            textcoords='offset points', ha='right', va='bottom')
    plt.show()  



    linked = linkage(X, 'single')

    labelList = range(1, 11)

    plt.figure(figsize=(10, 7))  
    dendrogram(linked,  
                orientation='top',
                labels=labelList,
                distance_sort='descending',
                show_leaf_counts=True)
    plt.show()  
#Se va a abrir un diagrama, cerralo y se volvera a abrir otro```

Hola!, no fui capaz (lo reconozco) de desarrollar el programa solo, así que opté por buscar la herramienta de scikit learn y adaptarlo a una entrada de números random, lo que concluí es que como entrada necesitan una lista de listas, o un array de numpy y de ahí para adelante la librería se encarga del resto, me falta mucha teoría aún pero desde el vamos, la librería es poderosísima.

import numpy as np
import random

from matplotlib import pyplot as plt
from scipy.cluster.hierarchy import dendrogram

from sklearn.cluster import AgglomerativeClustering


def plot_dendrogram(model, **kwargs):
    # Create linkage matrix and then plot the dendrogram

    # create the counts of samples under each node
    counts = np.zeros(model.children_.shape[0])
    n_samples = len(model.labels_)
    for i, merge in enumerate(model.children_):
        current_count = 0
        for child_idx in merge:
            if child_idx < n_samples:
                current_count += 1  # leaf node
            else:
                current_count += counts[child_idx - n_samples]
        counts[i] = current_count

    linkage_matrix = np.column_stack([model.children_, model.distances_,
                                      counts]).astype(float)

    # Plot the corresponding dendrogram
    dendrogram(linkage_matrix, **kwargs)


def generate_points(number_of_points):
    for _ in range(numero_puntos):
        x = random.randint(1,50)
        y = random.randint(1,50)
        points.append([x, y])



points = []
number_of_points = int(input('Ingrese cantidad de puntos que desea encapsular: '))
generate_points(number_of_points)


# setting distance_threshold=0 ensures we compute the full tree.
model = AgglomerativeClustering(distance_threshold=0, n_clusters=None)

model = model.fit(points)

plt.title('Hierarchical Clustering Dendrogram')
# plot the top three levels of the dendrogram
plot_dendrogram(model, truncate_mode='level', p=3)
plt.xlabel("Number of points in node (or index of point if no parenthesis).")
plt.show()

Al final el ultimo Cluster tiene algo en común, con los últimos clusters. aun que sea un porcentaje muy ligero

import random
import plotly.figure_factory as ff
import numpy as np
from bokeh.plotting import figure, show

# clase vector para determinar el punto en el plano
class Vector:

    def __init__(self, vect_x, vect_y):
        self.vect_x = vect_x
        self.vect_y = vect_y

    def coordenadas_actuales(self):
        return (self.vect_, self.vect_y)
    

def generar_vectores(numero_vectores):
    vectores = []
    for _ in range(numero_vectores):
        vector = Vector(random.randint(0, 100), random.randint(0, 100))
        vectores.append(vector)
    return vectores

def ver_distancia_euclidiana(vector_a, vector_b):
    return ((vector_a.vect_x - vector_b.vect_x)**2 + (vector_a.vect_y - vector_b.vect_y)**2)**0.5

def encontrar_distancia_minima(vector1, vectores):

    ditancias = []

    for vector2 in vectores:

        if (vector2.vect_x == vector1.vect_x) and (vector2.vect_y == vector1.vect_y):
             continue
        else:
            ditancias.append(ver_distancia_euclidiana(vector1, vector2))

            if len(ditancias) == 1:
                vector_cercano = vector2
                
            if len(ditancias) >= 2:
                if ditancias[-1] == min(ditancias):
                    vector_cercano = vector2

    return vector_cercano
        
def graficar_puntos(vectores):
    axis_x = [vector.vect_x for vector in vectores]
    axis_y = [vector.vect_y for vector in vectores]

    p = figure(plot_width = 400, plot_height = 400)

    p.circle(axis_x, axis_y, size=10, color="navy", alpha=0.5)

    show(p)

def graficar_dendograma(vectores):
    listax = [vector.vect_x for vector in vectores]
    print(listax)
    fig = ff.create_dendrogram(listax)
    fig.update_layout(width=800, height = 500)
    fig.show()

def clusterizar(vectores):

    clusters = []

    vector_inicial = random.choice(vectores)
    clusters.append(vector_inicial)
    vectores.remove(vector_inicial)
    

    while vectores:
        vector_cercano = encontrar_distancia_minima(vector_inicial, vectores)
        clusters.append(vector_cercano)
        vectores.remove(vector_cercano)

    
    graficar_dendograma(clusters)

def main():
    puntos = int(input('Cuantos vectores desea: '))
    vectores = generar_vectores(puntos)
    graficar_puntos(vectores)
    clusterizar(vectores)

if __name__ == "__main__":
    main()

Aquí pueden encontrar la documentación y el código de Scikit-learn

https://scikit-learn.org/stable/modules/generated/sklearn.cluster.AgglomerativeClustering.html#sklearn.cluster.AgglomerativeClustering

https://scikit-learn.org/stable/auto_examples/cluster/plot_agglomerative_dendrogram.html#sphx-glr-download-auto-examples-cluster-plot-agglomerative-dendrogram-py

https://github.com/scikit-learn/scikit-learn/blob/fd237278e/sklearn/cluster/_agglomerative.py#L790

import random
import math

#genera una lista de n_coord tuplas con coordenadas
def generar_coord(n_coord):
    return [(random.randint(1,10),random.randint(1,10)) for i in range(n_coord)]

#Realiza agrupamiento jerarquico
def agrupamiento_jerarquico(list_coord):

    for x in range(len(list_coord)-1):
        indexp1, indexp2, nuevo_punto = puntos_mas_cercanos(list_coord)
        print(f'Index a eliminar: {indexp1} y {indexp2}')
        print (f'Nueva coordenada: {nuevo_punto}')
        list_coord.remove(list_coord[indexp1]) #elimina el primer punto
        list_coord.remove(list_coord[indexp2-1]) #elimina el segundo punto
        list_coord.append(nuevo_punto) #adiciona el nuevo punto cluster
        print(list_coord)
    return list_coord

#devuleve los index de los puntos más cercanos dentro de la lista y la nueva coordenada entre los puntos
def puntos_mas_cercanos(list_coord):
    distancia_min = 100000000 #esto debo mejorarlo

    for i in range(len(list_coord)-1):
        for j in range(i,len(list_coord)-1):

            distancia=(distancia_puntos(list_coord[i],list_coord[j+1]))

            if(distancia<distancia_min):
                indexp1, indexp2 = i, j+1
                distancia_min=distancia

    nuevo_punto = nueva_coord(list_coord[indexp1],list_coord[indexp2])

    return indexp1, indexp2, nuevo_punto

#Calcula la distancia entre puntos
def distancia_puntos(punto1,punto2):

    return (math.sqrt((punto2[0] - punto1[0])**2 + (punto2[1] - punto1[1])**2))

#Calcula la nueva coordenada del cluster
def nueva_coord(punto1,punto2):

    return(punto2[0]-(punto2[0]-punto1[0])/2, punto2[1]-(punto2[1]-punto1[1])/2)

if __name__=='__main__':

    n_coord = int(input('Cuantas coordenadas quiere generar: '))
    list_coord = generar_coord(n_coord)
    print(list_coord)
    list_coord = agrupamiento_jerarquico(list_coord)
    print(f'La coordenada del cluster es: {list_coord}')

Agrupamiento jerárquico
relaciones entre cada grupo

Estás técnicas son muy utilizadas en el reconocimiento de patrones, permitiéndonos clasificar objetos por medio de clusters, existen varías técnicas que nos permiten hacer esta clasificación.
Entre sus aplicaciones podemos encontrar:
° Procesamiento de Imágenes
° Visión Artificial
° Inteligencia Artificial
° Machine Learning
° Imagenología
° Control Neurodifuso
° Neuróbotica
° Procesamiento de Señales Biológicas
° Biognosis
Actualmente estudio ingeniería biónica en el IPN y estos son algunos ejemplos en los que he aplicado estás técnicas en mi carrera.

Aun tiene cosas por mejorar, entre el primer nivel y el segundo aun se ven cosas extrañas jajaja si alguien puede terminarlo estaría genial

Alguien podría ayudarme a implementar esto con bokeh?

import random as ran

class Coordenada:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

class Cluster(Coordenada):
    def __init__(self, identificador, x, y):
        self.identificador = identificador
        self.clusters = [] #clusters internos
        super().__init__(x, y)

    def agregar_cluster(self, cluster_1):
        self.clusters.append(cluster_1)

    def calcular_distancia(self, otro_cluster):
        dx = self.x - otro_cluster.x
        dy = self.y - otro_cluster.y
        return (dx**2 + dy**2)**(0.5) #regresa la distancia con otro cluster


class Plano:
    def __init__(self, ancho = 100, alto = 100):
        self.ancho = ancho
        self.alto = alto
        self.clusters = [] #Clusters en el plano

    def agregar_cluster(self, cluster_plano):
        self.clusters.append(cluster_plano) #agrega el cluster al plano

    def agrupar_dos(self, cluster_1, cluster_2):
        nombre = cluster_1.identificador + cluster_2.identificador #forma un nombre con dos ids
        new_x = (cluster_1.x + cluster_2.x)/2
        new_y = (cluster_1.y + cluster_2.y)/2
        nuevo_cluster = Cluster(nombre, new_x, new_y)
        nuevo_cluster.agregar_cluster(cluster_1)
        nuevo_cluster.agregar_cluster(cluster_2)
        self.clusters.remove(cluster_1)
        self.clusters.remove(cluster_2) #remover clusters pequeños
        self.clusters.append(nuevo_cluster)

    def agrupar_todos(self):
        while len(self.clusters) > 1:
            self.mostrar_clusters() ############################################################ printstatement
            Distancias = {}
            for n in range(len(self.clusters)): #inicia en indice n = 0
                if n == (len(self.clusters)-1): #se llegó al ultimo cluster
                    break
                elif n < (len(self.clusters)-1):
                    for i in range(n+1, len(self.clusters), 1): #no inclusivo
                        distancia = self.clusters[n].calcular_distancia(self.clusters[i])
                        Distancias[distancia] = [self.clusters[n], self.clusters[i]]
            self.mostrar_distancias(Distancias) ################################################# monitoreo
            self.agrupar_dos(Distancias[min(Distancias)][0], Distancias[min(Distancias)][1])
        self.mostrar_clusters() ################################################################## print statement
    
    def mostrar_clusters(self):
        print('Clusters :')
        for j in self.clusters:
            print(f'{j.identificador}:({j.x},{j.y})', end = ' || ')
        print('')
        print("_ "*30) #separador

    def mostrar_distancias(self, Distancias):
        print('Distancias entre puntos : ')
        for i in Distancias:
            print(f'{Distancias[i][0].identificador}{Distancias[i][1].identificador} : {round(i, 2)}', end=' ')
        print('\n')



if __name__ == '__main__':
    campo = Plano()
    campo.agregar_cluster(Cluster('A', ran.randint(0,100), ran.randint(0,100)))
    campo.agregar_cluster(Cluster('B', ran.randint(0,100), ran.randint(0,100)))
    campo.agregar_cluster(Cluster('C', ran.randint(0,100), ran.randint(0,100)))
    campo.agregar_cluster(Cluster('D', ran.randint(0,100), ran.randint(0,100)))
    campo.agregar_cluster(Cluster('E', ran.randint(0,100), ran.randint(0,100)))
    campo.agregar_cluster(Cluster('F', ran.randint(0,100), ran.randint(0,100)))
    campo.agrupar_todos()
    ```

Realicé este código pero tiene bugs. de repente funciona y genera todos los clusters pero a veces entra en bucle infinito. en fin se hizo lo que se pudo 😕

import random as rnd
from bokeh.plotting import show, figure

archivo=open("colores_bokeh2.txt","r")
colores=archivo.readlines()
archivo.close()
col="\n".join(colores)+" "
colores=col.split()

class Punto:
    def __init__(self,x, y, ident):
        self.ident=ident
        self.x=x
        self.y=y

def distancia(C1, C2):
    d_p=(((C1.x-C2.x)**2)+((C1.y-C2.y)**2))**0.5
    return d_p

def centroide(array_pts):
    x=0
    y=0
    for i in array_pts:
        x+=i.x
        y+=i.y
    x/=len(array_pts)
    y/=len(array_pts)
    return (x,y)

def gen_puntos(n_puntos):
    P_array=[]
    X=[]
    Y=[]
    for i in range(n_puntos):
        x=rnd.randint(1,100)
        y=rnd.randint(1,100)
        X.append(x)
        Y.append(y)
        P_array.append(Punto(x,y,i))
    P_array.append(Punto(0,0,-1))
    return (P_array,X,Y)

def get_min(P_array):
    D={}
    for i in range(len(P_array)-1):
        P=[P_array[i]]
        d_min=distancia(P_array[i],P_array[i+1])
        
        for j in range(len(P_array)-1):
            if j>i:        
                d_try=distancia(P_array[i],P_array[j])
                if d_try<d_min:
                    d_min=d_try
                    P.clear()
                    P.append(P_array[i])
                    P.append(P_array[j])            
                elif d_try==d_min and P_array[j] not in P:            
                    P.append(P_array[j])
        D[d_min]=P
    return D

def new_points(P_array):
    new_P=[]
    D_P=get_min(P_array)#diccionario
    pminimo=min(D_P)
    
    for j, k in D_P.items():
        if k[0] not in D_P[pminimo]:
            new_P.append(D_P[j][0])
    
    centrXY=centroide(D_P[pminimo])        
    new_P.append(Punto(centrXY[0],centrXY[1], len(new_P)+len(P_array)))    
    new_P.append(Punto(0,0,-1))
    print(f"Distancia minima: {pminimo}")
    print(f"centroide de puntos en: {centrXY}")
    return (new_P,centrXY)
    
            
if __name__=="__main__":
    P_array, X, Y =gen_puntos(10)
    CX=[]
    CY=[]
    while len(P_array)>3:
        P_array, centroid =new_points(P_array)
        CX.append(centroid[0])
        CY.append(centroid[1])
        for i in P_array:
            print(i.ident)
    
    grafica=figure()
    grafica.circle(X,Y, size=10,color=colores)
    grafica.circle_cross(CX,CY,size=10,color="#FB8072", fill_alpha=0.2, line_width=2)
    show(grafica)
    ```

Listo! Después de bastante tiempo conseguí terminar mi algoritmo. Lo hice que graficara cada una de las veces que agrupaba un vector para conseguir apreciar su funcionamiento mas fácilmente.

![](

Si quieren ver mi código en Github apreciaría que lo probaran!

código completo en Github

Les comparto una parte del código.

from circle import CircleVector
from bokeh.plotting import figure, show
from random_color import gen_random_color


def gen_vector_circles(number_circles):
    circles_vector = []

    for i in range(number_circles):
        circle = CircleVector(i)
        circles_vector.append(circle)
    return circles_vector


def graph(vectors):

    x = []
    y = []
    colors = []
    for vector in vectors:
        position_x, position_y, size, color = vector.get_state()
        x.append(position_x)
        y.append(position_y)
        colors.append(color)
        # sizes.append(size)

    p = figure(plot_width=800, plot_height=800)
    p.annulus(x=x, y=y, inner_radius=size,
              color=colors, alpha=0.5)
    show(p)


def implement(vectors):
    clusters = []
    distances = []
    for vector in vectors:
        distances.append(vector.calculate_distance(vectors, memo={}))

    min_distances = []
    index_min_object = 0
    for distance in distances:
        min_distances.append(min(distance))

    min_distance = min(min_distances)
    for i in min_distances:
        if i == min_distance:
            break
        else:
            index_min_object += 1

    new_vector, cluster = vectors[index_min_object].join_vectors(
        distances[index_min_object], vectors)
    clusters.append(cluster)

    print(clusters)

    # print(index_min_object)
    # print(min_distances)
    # print(min_distance)
    # print(new_vector)
    # print(distances)

    graph(new_vector)
    return new_vector


def run():
    number_circles = int(input("How many vectors do you wanna create:  "))
    circle_vectors = gen_vector_circles(number_circles)
    size = 0.04
    graph(circle_vectors)

    while number_circles > 1:
        new_vector = implement(circle_vectors)
        circle_vectors = new_vector
        number_circles -= 1


if __name__ == "__main__":
    run()

Encontre muchos videos en youtobe sobre el metodo Feynman. Alguien recomienda algun link?

Aquí dejo mi código del reto use la librería scipy. espero les sea útil

import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage
from scipy.cluster.hierarchy import cophenet
from scipy.spatial.distance import pdist
import numpy as np

np.random.seed(4711)
a = np.random.multivariate_normal([10,0],[[3,1], [1,4]], size = [100,])
b = np.random.multivariate_normal([0,20],[[3,1], [1,4]], size = [50,])
X = np.concatenate((a,b))
print(X.shape)
X
plt.scatter(X[:,0],X[:,1])
plt.show()

Z = linkage(X,"ward")

c, coph_dist = cophenet(Z, pdist(X))
print(c)


Z[:20]

print(Z[152-len(X)])# cluster 152
print(Z[158-len(X)])# cluster 158

X[[33,62,68]]

idx = [33,62,68]
idx2 = [15,69,41]
plt.figure(figsize=[10,8])
plt.scatter(X[:,0], X[:,1])# pintar todos los puntos
plt.scatter(X[idx,0], X[idx,1], c="r")#destacamos en rojo los puntos interesantes
plt.scatter(X[idx2,0], X[idx2,1], c="y")#destacamos en amarillo otro cluster que nos interesa
plt.show()

#Representacion gráfica del dendrograma
plt.title("Dendrograma del clustering jerárquico")
plt.xlabel("Indices de la muestra")
plt.ylabel("Distancias")
dendrogram(Z, leaf_rotation=90., leaf_font_size=0.8, color_threshold=0.1*180)
plt.show()

import random

def genera_coordenadas():
puntos= []
orden = 0
# Generar 20 puntos entre 10 y 20
for _ in range(20):
x_coordenada = random.randint(10,20)
y_coordenada = random.randint(10,20)
puntos.append([orden,x_coordenada,y_coordenada])
orden+=1
# Generar 10 puntos entre 50 y 70
for _ in range(10):
x_coordenada = random.randint(50,70)
y_coordenada = random.randint(50,70)
puntos.append([orden,x_coordenada,y_coordenada])
orden+=1
return puntos

#calcular la distancia euclidania
#toma un vector de coordenadas y saca la distancia con cada punto del mismo vector
#el resultado en lo deja en un vector llamado distancia
#que contiene un arreglo de todas las combinaciones de puntos y la distancia
def calcula_distancias(puntos):
distancias = []
for i in range(len(puntos)): #i = 0-4
for j in range(len(puntos)):# j = 0 - 4 puntos a calcular con el point[i]
if j + i + 1 < len(puntos): # 0+0+1 < 5 falso (0-4) + (0-4) < 5
current_point = puntos[i]
next_point = puntos[j + i + 1]
distance = ((current_point[1] - next_point[1])**2 + (current_point[2] - next_point[2])**2)**0.5
distancias.append([current_point[0], next_point[0], distance])
return distancias

#buscar la distancia minima de un vector
def search_min_distance(distancias):
solo_distancias = [] # Crea un vector para almacenar las distancias
for distancia in distancias: #Recorre el vector
solo_distancias.append(distancia[2])

min_vector = min(solo_distancias) #Recupera la distancia minima

for distancia in distancias: #recorre el vector buscando la distancia minima
    if min_vector == distancia[2]: #Si el vector coincidde con la distancia minimoa
        min_distance = distancia # Recupera el vector de distancia minima [p1,p2,distacia]
return min_distance

def new_coordinate(pointA, pointB):
x_average = (pointA[1] + pointB[1]) / 2
y_average = (pointA[2] + pointB[2]) / 2
new_cluster = [0, x_average, y_average]
return new_cluster

def make_cluster(puntos):
number_recursions = 0
cluster = 'C’
while len(puntos) > 1:
distances = calcula_distancias(puntos)
min_distance = search_min_distance(distances)
pointA = []
pointB = []
for point in puntos:
if min_distance[0] == point[0]:
pointA = point
puntos.remove(point)
for point in puntos:
if min_distance[1] == point[0]:
pointB = point
puntos.remove(point)
new_cluster = new_coordinate(pointA, pointB)
new_cluster[0] = ‘C’, number_recursions
puntos.append(new_cluster)
number_recursions += 1
print(puntos)

return puntos

#**********************
if name == “main”: #Delfina Meroal
puntos = genera_coordenadas()
print(“vectores de puntos”)
print(puntos)
print ("****************************************")
clusters = make_cluster(puntos)
print(clusters)

Este es mi intento de hacer este ejercicio aunque fue usando los parámetros más simples, logré que pudiera clusterizar correctamente dos series de datos generados de forma uniforme:

#%% libraries

import numpy as np

#%% Hierarchical Clustering Class

class HierarchicalClustering():
    
    #Initialize N is the array of datapoints
    def __init__(self, N, distance="Euclidian", linkage = "simple"):
        self.N = N
        self.distance = distance
        self.linkage = linkage
    
    def Calc_distance(self, C1, C2):
        if self.distance == "Euclidian":
            total_distance = np.linalg.norm(C1-C2)
            return total_distance
        else:
            print("For now we dont have that implemented yet")
    
    def Calc_linkage(self, C1, C2):
        if self.linkage == "simple":
            argminC1 = np.argmin([np.dot(C1[i][0], C1[i][1]) for i in range(len(C1))])
            argminC2 = np.argmin([np.dot(C2[i][0], C2[i][1]) for i in range(len(C2))])
            return C1[argminC1], C2[argminC2]
        else:
            print("For now we dont have that implemented yet")
    
    def Cluster(self):
        n = len(self.N) #Number of points
        D = {} #Set of distances
        C = {i:[j] for i,j in enumerate(self.N)} #Set of clusters
        Clusters = {1:C} #We will save each iteration of clusters
        count = n
        while len(C) != 1:
            count = count + 1
            for i in C:
                for j in C:
                    if i != j:
                        arg1, arg2 = self.Calc_linkage(C[i], C[j])
                        dij = self.Calc_distance(arg1,arg2)
                        
                        if dij not in D:
                            D[dij] = [i,j]
                        else:
                            pass
                            #D[dij].append([i,j])  
                        
            mindij = min(D)
            kCluster = np.append(C[D[mindij][0]], C[D[mindij][1]], axis=0)
            del C[D[mindij][0]]
            del C[D[mindij][1]]
            C[count] = kCluster
            Clusters[count-n] = C.copy()
            D = {}
            
        return Clusters
    
#%% Initialize

if __name__ == "__main__":
    N = np.append(np.random.randint(1,10,[20,2]), np.random.randint(15,35,[10,2]),axis=0)
    C1 = HierarchicalClustering(N)
    Clusters = C1.Cluster()

Generé 20 puntos en 2D aleatorios entre 1 y 10. Y 10 puntos entre 15 y 35. Y cuando se tienen 2 clusters justamente los separa como esperaba, uno contiene los 20 puntos y el otro contiene 10.

Por ahora regresa cómo fue clusterizando en cada iteración, como siguientes pasos se podrían extender los parámetros para aceptar más distancias, otras formas de enlace (linkage) y que regrese cuál sería el mejor agrupamiento (número de clusters) para estos datos.

import random
from bokeh.plotting import figure, output_file, show


def random_coordinates():
    coor = {}
    for _ in range(9):
        x = random.randrange(0,10)
        y = random.randrange(0,10)
        c =  (x **2+y **2) **.5 # c^2 = a^2 + c^2
        coor[c] = (x,y)
    dist = [c for c in coor.keys()]
    dist = sorted(dist)
    return coor, dist

def shortest(dist):
    short = abs(dist[0]-dist[1])
    num_1 = dist[0]
    num_2 = dist[1]
    if len(dist) == 2:
        return 0, 1
    for num in dist:
        for roll in dist:
            comp = abs(num - roll)
            if comp < short and num != roll:
                short = comp
                num_1 = num
                num_2 = roll
    return dist.index(num_1), dist.index(num_2)

def graph(x_val, y_val):
    fig = figure()
    fig.circle(x_val, y_val)
    show(fig)

def join_coordinates(coor, dist):
    show_coor = [coor[i] for i in dist]
    graph([x[0] for x in show_coor], [y[1] for y in show_coor])
    while True:
        show_coor = [coor[i] for i in dist]
        graph([x[0] for x in show_coor], [y[1] for y in show_coor])
        print(show_coor)
        if len(dist) == 1: #6
            break
        short_1, short_2 = shortest(dist)
        x = (coor[dist[short_1]][0] + coor[dist[short_2]][0]) /2
        y = (coor[dist[short_1]][1] + coor[dist[short_2]][1]) /2
        c =  (x **2+y **2) ** 0.5 # c^2 = a^2 + c^2
        coor[c] =  (x,y)
        short_1 = dist[short_1]
        short_2 = dist[short_2]
        dist.remove(short_1)
        dist.remove(short_2)
        dist.append(c)
        dist.sort()
    return


def agrupamiento():
    coor, dist =  random_coordinates()
    join_coordinates(coor, dist)


if __name__ == "__main__":
    output_file('agrupamiento.html')
    agrupamiento()

Después de hacer este ejercicio, tengo una duda, y es que en los comentarios he visto que unas personas se refieren a la unidad con la que se ejecuta el algoritmo de clustering como coordenadas y otros como vectores. Esto me confunde porque yo pensaba que una coordenada viene definida por un punto y que el vector era la unión de dos coordenadas(2 puntos).
Entonces…es posible definir un vector con una sola coordenada? o el algoritmo de clustering necesita puntos y no vectores para ser ejecutado?
Ojala me puedan ayudar, gracias 😃

![](

![](

![](

![](

Un punto muy importante que debes considerar cuando ejecutas técnicas de agrupamiento es que debes definir muy claro a qué te refieres cuando hablas de similitud entre puntos, porque esto puede ayudarte a definir el algoritmo correcto para tus necesidades particulares.

Hola, comparto mi codigo en Python del reto del agrupamiento jerárquico

import random
import math 

def coordinates(attempts):
    #Generates a number of user-given coordinates between 0-10
    coord= []

    for _ in range(attempts):

        x = random.randint(0,10)
        y = random.randint(0,10)
        coord.append([x,y])
    
    print(f'The original coordinates: {coord}' + '\n')
    return coord

def average_point(x_ini,y_ini,x_end,y_end):

    #Calculate the average coordinate between 2 coordinates
    x_avg = round((math.sqrt(x_end + x_ini)),4)
    y_avg = round((math.sqrt(y_end + y_ini)),4)

    coord_avg = (x_avg , y_avg)
  
    return coord_avg

def distance(x_ini,y_ini,x_end,y_end):

    #Calculate the average distance between 2 coordinates
    dist = round((math.sqrt((x_end - x_ini)**2 + (y_end - y_ini)**2)),4)

    return dist

def estimates(coord):

    distances = []
    distances_loc = []
    avg_point = []
    index=0

    #Comparate all the coordinates and choose the closest pair
    for i in range(len(coord)):
        index += 1
        for j in range(index, len(coord)):
            x_ini = coord[i][0]
            y_ini = coord[i][1]
            x_end = coord[j][0]
            y_end = coord[j][1]

            #Distances between two coordinates
            distances.append(distance(x_ini,y_ini,x_end,y_end))
            #Create a list of all possible comparisons
            distances_loc.append([i,j])
            #Create the average coordinate between 2 coordinates
            avg_point.append(average_point(x_ini,y_ini,x_end,y_end))
    
    clusters(coord,distances,distances_loc,avg_point)
    
    return distances,distances_loc,avg_point

def clusters(coord,distances,distances_loc,avg_point):
    #Save the coordinates in a new list
    cluster = coord

    #Returns the index of the closest coordinates
    min_dist_index = distances.index(min(distances))
    #Returns the coordinates closest
    min_local=distances_loc[min_dist_index]
    print(f'The closest position of coordinates: {min_local}' + '\n')

    #Delete the closest coordinates from the coordinates list
    cluster.pop(min_local[1])
    cluster.pop(min_local[0])

    #Replace the deletion coordinates with the average coordinates
    cluster.append(avg_point[min_dist_index])
    print('----'*20)
    print(f'New cluster {cluster}')

    return clusters

def main(coord):

    while len(coord) >1:
        estimates(coord)
        
    return coord

if __name__ == "__main__":

    attempts = int(input("Coordenates number: "))
    coord = coordinates(attemps)
    print(coord)
    hierachical_grouping = main(coord)

https://developers.google.com/machine-learning/clustering/clustering-algorithms#hierarchical-clustering

Implementación de agrupamiento jerárquico en data ficticia como en real con python:
https://www.instintoprogramador.com.mx/2019/07/clustering-jerarquico-con-python-y.html

Este seria el algoritmo que hice para el reto.

import random
import math

#Generamos un vector aleatorio de coordenadas entre 0 y 20 
def generar_vector_aleatorio():
	return (random.randrange(20), random.randrange(20))

#Generamos varios vectores, cantidad de vectores es numero_vectores
def numero_de_vectores(numero_vectores):
	vectores = []
	for _ in range(numero_vectores):
		vector = generar_vector_aleatorio()
		vectores.append(vector)
	return vectores

#Medimos la distancia entre vectores 
def medir_distancia(x, y):
	return math.sqrt((x**2)+(y**2))

#Comparamos la distancia entre dos grupos
def comparar(vector1, vector2):
	distancia_menor = None
	if isinstance(vector1, list):
		for vector in vector1:
			distancia = comparar(vector, vector2)
			if distancia_menor:
				if distancia < distancia_menor:
					distancia_menor = distancia
			else:
				distancia_menor = distancia
		return distancia_menor
	if isinstance(vector2, list):
		for vector in vector2:
			distancia = comparar(vector1, vector)
			if distancia_menor:
				if distancia < distancia_menor:
					distancia_menor = distancia
			else:
				distancia_menor = distancia
		return distancia_menor 
	return medir_distancia(vector1[0]-vector2[0],vector1[1]-vector2[1])	

#Funcion recursiva que agrupa por jerarquias, termina en el momento que solo quede un elemento
#Esto significaria que solo queda un grupo y todos los grupos estaran unidos
def agrupar(vectores):
	distancia_menor = None		
	vector1, vector2 = None, None 
	#Busca la menor distancia
	for i in range(len(vectores)-1):		
		for j in range(i+1, len(vectores)):
			distancia = comparar(vectores[i],vectores[j])
			
			if distancia_menor:				
				if distancia < distancia_menor:
					distancia_menor = distancia
					vector1 = vectores[i]
					vector2 = vectores[j]
			else:
				distancia_menor = distancia
				vector1 = vectores[i]
				vector2 = vectores[j]
	
	print('_'*20)		
	vector =[vector1,vector2]
	print(f'La menor distancia es {distancia_menor}')
	print(f'Se va a unir el grupo {vector1}, con el grupo {vector2} para formar {vector}')	
	#Formamos el grupo
	vectores.remove(vector1)
	vectores.remove(vector2)
	vectores.append(vector)
	
	print('-'*50)
	print('El vector completo es:')
	print(vectores)
	
	if (len(vectores)>1):
		vectores = agrupar(vectores)
	
	return vectores


#Funcion main
if __name__=='__main__':
	vectores = numero_de_vectores(10)
	print('Estas son nuestras coordenadas iniciales formando grupos individuales')
	print(vectores)
	grupos = agrupar(vectores)
	print('_'*50)
	print('Se ha formado un solo grupo')
	print(grupos)

Les comparto mi código para este ejecicio y una demostración paso a paso para una colección de 5 vectores, espero que no este muy lioso.
Nota: el dendograma no he sido capaz de representarlo pero dentro del código se guarda cada relación que se va haciendo entre los diferentes vectores en el clustering.

import random
import math
from bokeh.plotting import figure, output_file, show

COLOURS = ['red', 'green', 'purple', 'orange', 'black', 'pink']

def generate_random_vector():

    vectors = []
    for i in range(5):
        vectors.append((random.randint(1, 10), random.randint(1, 10)))

    return vectors

def get_euclidean_distance(originVector, comparisonVector):
    return math.sqrt( (originVector[0] - comparisonVector[0])**2 + (originVector[1] - comparisonVector[1])**2 )

def generate_graph(x_values, y_values, stepsCounter):

    # output to static HTML file
    output_file(f"step_{stepsCounter}.html")

    # create a new plot with a title and axis labels
    p = figure(plot_width=400, plot_height=400, x_range = (0, 11), y_range = (0, 11))

    # add a circle renderer with a size, color, and alpha
    p.scatter(x_values, y_values, size=20, color=COLOURS[stepsCounter], alpha=0.5)

    # show the results
    show(p)


if __name__ == "__main__":

    stepsCounter = 1
    global_relationship = []
    
    # generate a random vectors collection
    vectors = generate_random_vector()

    # get x and y values to generate the graph
    x_values = [ vector[0] for vector in vectors ]
    y_values = [ vector[1] for vector in vectors ]

    # we generate the first graph
    generate_graph(x_values, y_values, stepsCounter)

    # for initial_index, initial_vector in enumerate(vectors):
    while len(vectors) > 1:

        # We will compare against the first vector (We could do it randomly)
        initial_vector = vectors[0]
        closest_vector = ''
        closest = {
            'distance': '',
            'relationship': ''
        }
        stepsCounter += 1

        for comparing_index, comparing_vector in enumerate(vectors):
            
            if initial_vector != comparing_vector:

                # get the distances between vectors and save the closest
                distance = get_euclidean_distance(initial_vector, comparing_vector)
                if closest['distance'] == '':
                    closest['distance'] = distance
                    closest_vector = comparing_vector
                    closest['relationship'] = f'{initial_vector}*{comparing_vector}'  
                else:
                    if distance < closest['distance']:
                        closest['distance'] = distance
                        closest_vector = comparing_vector
                        closest['relationship'] = f'{initial_vector}*{comparing_vector}'  

        # we calculate the mid point between the two vectors and add the relationship clustered
        cluster_vector = ((initial_vector[0] + closest_vector[0]) / 2, (initial_vector[1] + closest_vector[1]) / 2)
        global_relationship.append(closest['relationship'])
        
        # we add the new clutered vector
        vectors.append(cluster_vector)

        # we remove the clustered vectors
        vectors.remove(initial_vector)
        vectors.remove(closest_vector)

        # get x and y values to generate the graph
        x_values = [ vector[0] for vector in vectors ]
        y_values = [ vector[1] for vector in vectors ]

        # we generate the follow clustering steps
        generate_graph(x_values, y_values, stepsCounter)

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

X = np.array([[1,1],
    [3,2],
    [1,4],
    [7,2],
    [5,6],
    [6,6],
    [7,5],]) 

def generar_trazos():

    labels = range(1, 8)  
    plt.figure(figsize=(10, 7))  
    plt.subplots_adjust(bottom=0.1)  
    plt.scatter(X[:,0],X[:,1], label='True Position')

    for label, x, y in zip(labels, X[:, 0], X[:, 1]):  
        plt.annotate(
            label,
            xy=(x, y), xytext=(-3, 3),
            textcoords='offset points', ha='right', va='bottom')
    plt.show()  

from scipy.cluster.hierarchy import dendrogram, linkage  
from matplotlib import pyplot as plt

def generar_dendrograma():
    linked = linkage(X, 'single')

    labelList = range(1, 8)

    plt.figure(figsize=(10, 7))  
    dendrogram(linked,  
                orientation='top',
                labels=labelList,
                distance_sort='descending',
                show_leaf_counts=True)
    plt.show()

from sklearn.cluster import AgglomerativeClustering

def generar_agrupaciones_sklearn():
    cluster = AgglomerativeClustering(n_clusters=2, affinity='euclidean', linkage='ward')  
    cluster.fit_predict(X)
    print(cluster.labels_)
    plt.scatter(X[:,0],X[:,1], c=cluster.labels_, cmap='rainbow')
    plt.show()

if __name__ == "__main__":
    generar_trazos()
    generar_dendrograma()
    generar_agrupaciones_sklearn()

Comparto mi implementacion, las distancias para no tener que generar las varias veces al coloque en una matriz que va cambiando dependiendo de la cantidad de puntos que halla en el arreglo de puntos, en el proceso se almacenan los puntos iniciales y los puntos promedio en un árbol para visualizar el árbol al final en inorder ([muestra el punto ] -> .[altura del nodo])

Resultado:

Me tomo bastantes horas pero aquí está.
Con un poco de ayuda de Google y siguiendo el concepto de decomposición logré hacer el algoritmo.

El código:

import random 
import math
import itertools
from bokeh.plotting import figure, output_file, show

def get_random_coordinates():
        x = random.randint(0, 10)
        y = random.randint(0, 10)
        return (x, y)

def get_euclidean_distance(vector_1, vector_2):
        d = math.sqrt((vector_2[0]-vector_1[0])**2 + \
                      (vector_2[1] - vector_1[1])**2)
        return round(d, 2) 

def list_of_random_vectors(n_vectors):
    '''
    Generate a list of random vectors
    list_of_random_vectors = [(x1,y1), (x2,y2), (x3,y3)...]
    '''
    list_of_random_vectors = []
    for _ in range(n_vectors):
        list_of_random_vectors.append(get_random_coordinates()) 
    return list_of_random_vectors

def archive(lista):
    '''
    Input: list_of_random_vectors
    Generate a dictionary
    Returns:
    archive = {((x1, y1), (x2, y2)): m, ((x3, y3), (x4, y4)): n}
    where n is given by get_euclidean_distance()
    '''
    archive = {}

    for vector_1, vector_2 in itertools.combinations(lista, 2):
        archive[vector_1,vector_2] = get_euclidean_distance(vector_1,vector_2) 

    return archive 

def closest_vectors(dictionary):
    """
    Input: the dictionary archive
    Generate a tuple with the most closest vectors
    returns ((x1,y1),(x2,y2))
    in here, vector_1 = (x1,y1) and vector_2 = (x2,y2)
    """
    min_value = min(dictionary.values())

    key_for_min_value = [key for key in dictionary if dictionary[key] == min_value] 
    vector_1 = key_for_min_value[0][0]
    vector_2 = key_for_min_value[0][1]
    return (vector_1, vector_2)


def middle_vector(vector1, vector2):
    """
    input: vector_1: (x1,y1); vector_2: (x2,y2)
    returns the middle vector (x,y)
    """
    x1 = vector1[0]
    x2 = vector2[0]
    y1 = vector1[1]
    y2 = vector2[1]
    x_medio = round((x1+x2)*0.5, 2)
    y_medio = round((y1+y2)*0.5, 2)
    middle_vector = (x_medio, y_medio)
    return middle_vector


tracked_vectors = []

def clustering(random_list):
    global tracked_vectors

    random_list = list of random vectors
    print(f"random_list: {random_list}")
    
    # base case for recursivity
    if len(random_list) == 1:
        return random_list[0]

    # calculate the vectors distance and save it into a dictionary
    archive_of_distances = archive(random_list)
    #print(archive_of_distances)  # for check 

    # get the closest vectors
    the_closest_vectors = closest_vectors(archive_of_distances)
    vector_1 = the_closest_vectors[0]
    vector_2 = the_closest_vectors[1]

    # record those closest vectors into the tracked_vectors list
    tracked_vectors.append(vector_1)
    tracked_vectors.append(vector_2)
    print(f"tracked_vectors: {tracked_vectors}")

    # calculate the middle point of these vectors
    the_middle_vector = middle_vector(vector_1, vector_2)

    # delete those vectors from the random_list
    random_list.remove(vector_1) 
    random_list.remove(vector_2)

    # add the middle vector to the random_list
    random_list.append(the_middle_vector)

    # do it agan
    return clustering(random_list)


if __name__ == '__main__':
    # vectores aleatorios
    number = int(input("Choose the number of vectors: "))
    vectors = list_of_random_vectors(number)

    cluster = clustering(vectors)
    print(f"clustering: {cluster}")

El output:
![](

(P.D.: si imprimen tracked_vectors pueden ver la lista de vectores almacenados)

Me recuerda un poco este proceso al ordenamiento por mezcla, no les parece?

Ahí va mi implementación. En cada iteración se crea una nueva lista de puntos, eliminando de la lista anterior los dos más cercanos y añadiendo el punto medio de éstos.
Además se va guardando en un diccionario los puntos a partir de los cuáles se ha originado el nuevo.
Es decir, si por ejemplo los puntos (10,10): 5 y 8 (20,20): 8 son los más cercanos se eliminan los dos de la lista y se añade su punto medio (15, 15). Y en el diccionario se guardarían las coordenadas del punto medio como key y los puntos de los que procede como value -> (15,15): (5,8)

import random
import math


def generate_random_points( number_points ):

    points = []

    for _ in range( number_points ):
        x_coord = random.randint(0, 50)
        y_coord = random.randint(0, 50)

        point = (x_coord, y_coord)
        points.append( point )

    return points


def euclidean_distance( point1, point2 ):

    x_diff = point1[0] - point2[0]
    y_diff = point1[1] - point2[1]

    distance = math.sqrt( x_diff**2 + y_diff**2 )

    return distance


def make_diccionary_distances( points ):

    distances = {}

    for i in range( 1, len(points)  ):
        for j in range( i+1, len(points) + 1 ):
            distances[(i,j)] = round(euclidean_distance(points[i-1], points[j-1]), 2)

    return distances


def calculate_medium_point( point1, point2 ):

    medium_point_x = (point1[0] + point2[0]) / 2
    medium_point_y = (point1[1] + point2[1]) / 2

    medium_point = ( medium_point_x, medium_point_y )

    return medium_point


def clustering( points, points_dictionary ):

    distances = make_diccionary_distances( points )

    # print(distances)
    # Find the minimum distance between points
    # Remove that points and add the average 

    for key, value in distances.items():
        if value == min( distances.values() ):

            new_point =  calculate_medium_point(points[key[0]-1], points[key[1]-1]) 

            # print(( points_dictionary[ points[key[0]-1] ], points_dictionary[ points[key[1]-1] ] ))

            points_dictionary[new_point] = ( points_dictionary[ points[key[0]-1] ], points_dictionary[ points[key[1]-1] ] )

            points.pop(key[0]-1)
            points.pop(key[1]-2)
            points.append( new_point )


    return points


def run():
    
    points = generate_random_points(10)
    original_points = tuple(points)

    points_dic = {}

    for i in range( len(points) ):
        points_dic[original_points[i]] = i+1

    print(points_dic)
    print(points)

    print("-----------------------------------")

    while len(points) > 1:
        points = clustering( points, points_dic)

        print("POINTS")
        print(points)
        print("    ")
        print("POINTS DICTIONARY")
        print(points_dic)
        print("-----------------------------------")
        
    
if __name__ == '__main__':
    run()

<from functools import partial
from random import random
from threading import Thread
import time
from bokeh.models import ColumnDataSource
from bokeh.plotting import curdoc, figure
from tornado import gen

# this must only be modified from a Bokeh session callback
source = ColumnDataSource(data=dict(x=[], y=[]))
source2 = ColumnDataSource(data=dict(x=[], y=[]))
# This is important! Save curdoc() to make sure all threads
# see the same document.
doc = curdoc()
@gen.coroutine
def update(x, y):
    source.stream(dict(x=[x], y=[y]))
def update2(x, y):
    source2.stream(dict(x=[x], y=[y]))
def blocking_task():
    contador=0
    contador2=0
    contador3=0
    contador4=0
    contadorUnico=2
    ubicacion=0
    save_x=[]
    save_y=[]
    while True:
         # do some blocking computation
        time.sleep(1)
        if contador<5:
            x, y = random(), random()
            save_x.append(x)
            save_y.append(y)
            # but update the document from callback
            doc.add_next_tick_callback(partial(update, x=x, y=y))
            contador+=1
        elif contador<=8:
            Acumulado_distancias=[]
            ubicacion=0
            for i in range(0,len(save_x)):
                ubicacion+=1
                for j in range (ubicacion,int(len(save_x))):
                    distancia=((save_x[j]-save_x[i])**2+(save_y[j]-save_y[i])**2)**0.5
                    Acumulado_distancias.append(distancia)
            contador+=1
            Hallar_Numero=Acumulado_distancias[0]
            posicion=0
            for k in range(len(Acumulado_distancias)):
                if Acumulado_distancias[k]<Hallar_Numero:
                    Hallar_Numero=Acumulado_distancias[k]
                    posicion=k
            if posicion<=(3-contador2):
                x=(save_x[0]+save_x[posicion+1])/2
                y=(save_y[0]+save_y[posicion+1])/2

                save_x.pop(posicion+1)
                save_y.pop(posicion+1)

                save_x.pop(0)
                save_y.pop(0)

                save_x.insert(0,x)
                save_y.insert(0,y)

                doc.add_next_tick_callback(partial(update2, x=x, y=y))
            elif posicion>=(4-contador2) and posicion<=(6-contador3):
                x=(save_x[1]+save_x[posicion-contadorUnico])/2
                y=(save_y[1]+save_y[posicion-contadorUnico])/2

                save_x.pop(posicion-contadorUnico)
                save_y.pop(posicion-contadorUnico)
                save_x.pop(1)
                save_y.pop(1)

                save_x.insert(1,x)
                save_y.insert(1,y)

                doc.add_next_tick_callback(partial(update2, x=x, y=y))
            elif posicion>(6-contador3) and posicion <=(8-contador4):
                x=(save_x[2]+save_x[posicion-4+contador3])/2
                y=(save_y[2]+save_y[posicion-4+contador3])/2

                save_x.pop(posicion-4+contador3)
                save_y.pop(posicion-4+contador3)

                save_x.pop(2)
                save_y.pop(2)

                save_x.insert(2,x)
                save_y.insert(2,y)

                doc.add_next_tick_callback(partial(update2, x=x, y=y))
            elif posicion>8:
                x=(save_x[3]+save_x[posicion-5])/2
                y=(save_y[3]+save_y[posicion-5])/2

                
                save_x.pop(posicion-5)
                save_y.pop(posicion-5)

                save_x.pop(3)
                save_y.pop(3)

                save_x.insert(3,x)
                save_y.insert(3,y)

                doc.add_next_tick_callback(partial(update2, x=x, y=y))
                
            contador2+=1
            contador3+=2
            contador4+=3
            contadorUnico-=1


p = figure(x_range=[0, 1.5],y_range=[0,1.5])
l = p.circle(x='x', y='y',size=30,fill_alpha=0.5, source=source)
lp = p.circle(x='x', y='y',size=18,fill_color="#FE7152", source=source2)

doc.add_root(p)

thread = Thread(target=blocking_task)
thread.start()>

https://drive.google.com/file/d/16QVQEpp70hkwY8qkZ3kutBkApkbxvDRD/view?usp=sharing

para ver el funcionamiento. Lo realice mediante Threads o hilos para poder ver la visualización dinámica de las esferas ubicándose aleatoria mente y posteriormente haciendo el agrupamiento jerárquico

Para la Data en un bloque separado en un Colab

<import random
import math
import matplotlib.pyplot as plt

rango = 10
x = [random.randint(1,21) for _ in range(rango)]
y = [random.randint(1,21) for _ in range(rango)]
print(len(x))
plt.scatter(x,y)
plt.show()>

y en otro bloque, ejecutando una y otra podremos pareciar el average linkench etc hasta que quede uno

<def distance(x1,y1,x2,y2):
  return math.sqrt((x2-x1)**2 + (y2-y1)**2)

def media(x1,y1,x2,y2):
  return (x1+x2)/2, (y1+y2)/2

def clear_data(x,y,xy1,xy2):
  new_x = []
  new_y = []
  for i in range(len(x)):
    if i != xy1 and i != xy2:
      new_x.append(x[i])
      new_y.append(y[i])
  return new_x, new_y

def new_average_link(points_x,points_y):
  min = 10000

  for i in range(len(points_x)):
    for f in range(len(points_x)):
      dist = distance(points_x[i],points_y[i],points_x[f],points_y[f])
      if dist < min and dist != 0:
        min = dist
        xy1 = i
        xy2 = f

  new_x, new_y = media(points_x[xy1],points_y[xy1], points_x[xy2], points_y[xy2])

  points_x.append(new_x)
  points_y.append(new_y)

  points_x, points_y = clear_data(points_x,points_y,xy1,xy2)

  return points_x, points_y

x, y = new_average_link(x,y)

plt.scatter(x,y)
plt.show()>

Despues de tomarme un tiempo para arreglar el código y usando el comentario de @jvera7 logré mejorar mis resultados y les añadi la grafica.

Estoy contenta con lo que tengo auque si pienso que puede estar mejor 😄

import random 
import math
import itertools

from bokeh.plotting import figure, show, output_file
from bokeh.models import LabelSet, ColumnDataSource
from bokeh.palettes import Category20 as palette

 
def get_random_coordinates():
        x = random.randint(0, 10)
        y = random.randint(0, 10)
        return (x, y)
    
def get_euclidean_distance(vector_1, vector_2):
        d = math.sqrt((vector_2[0]-vector_1[0])**2 + \
                      (vector_2[1] - vector_1[1])**2)
        return round(d, 2) 
       
def list_of_random_vectors(n_vectors):
    '''
    Generate a list of random vectors
    list_of_random_vectors = [(x1,y1), (x2,y2), (x3,y3)...]
    '''
    list_of_random_vectors = []
    for _ in range(n_vectors):
        list_of_random_vectors.append(get_random_coordinates()) 
    return list_of_random_vectors

def archive(lista):
    '''
    Input: list_of_random_vectors
    Generate a dictionary
    Returns:
    archive = {((x1, y1), (x2, y2)): m, ((x3, y3), (x4, y4)): n}
    where n is given by get_euclidean_distance()
    '''
    archive = {}

    for vector_1, vector_2 in itertools.combinations(lista, 2):
        archive[vector_1,vector_2] = get_euclidean_distance(vector_1,vector_2) 

    return archive    

def closest_vectors(dictionary):
    """
    Input: the dictionary archive
    Generate a tuple with the most closest vectors
    returns ((x1,y1),(x2,y2))
    in here, vector_1 = (x1,y1) and vector_2 = (x2,y2)
    """
    min_value = min(dictionary.values())

    key_for_min_value = [key for key in dictionary if dictionary[key] == min_value] 
    vector_1 = key_for_min_value[0][0]
    vector_2 = key_for_min_value[0][1]
    return (vector_1, vector_2)

def middle_vector(vector1, vector2):
    """
    input: vector_1: (x1,y1); vector_2: (x2,y2)
    returns the middle vector (x,y)
    """
    x1 = vector1[0]
    x2 = vector2[0]
    y1 = vector1[1]
    y2 = vector2[1]
    x_medio = round((x1+x2)*0.5, 2)
    y_medio = round((y1+y2)*0.5, 2)
    middle_vector = (x_medio, y_medio)
    return middle_vector

def from_tuple_to_list(list_of_tuples):
    """
    input: list of tuples [(x1,y1), (x2,y2), (x3,y3)...]
    output: ([x1,x2,x3...],[y1,y2,y3...])
    """
    x = []
    for i in range(len(list_of_tuples)):
        x.append(list_of_tuples[i][0])

    y = []
    for i in range(len(list_of_tuples)):
        y.append(list_of_tuples[i][1])

    return x, y

n = 0

def clustering(random_list):
    '''
    1. Take the_closest_vectors of random_list and agroup them into cluster
    2. Replace the closest_vectors for the_middle_point 
    3. the_middle_point is now a vector and represents a cluster
    4. Repeat 1 till there is no more vectors to agroup
    '''

    global n
    vectors_dict = dict(zip(random_list, range(len(random_list))))
    list_xy = from_tuple_to_list(random_list)
    x = list_xy[0] # list_x_random
    y = list_xy[1] # list_y_random
    names = ['0','1','2','3','4']
   
    # plotting the random vectors
    graph = figure(title = 'Hierarchical clustering', x_axis_label = 'x', y_axis_label = 'y')
    graph.circle(x, y)
    source = ColumnDataSource(data=dict(x=x, y=y, names=names))
    labels = LabelSet(x='x', y='y', text='names', level='glyph', x_offset=5, y_offset=5, source=source, render_mode='canvas')
    graph.add_layout(labels)

    # keep clustering till there is no more items to agroup
    while len(random_list) != 1:
        archive_of_distances = archive(random_list)
        
        if len(vectors_dict) > 1:
            cluster = []

            # get the_closest_vectors
            the_closest_vectors = closest_vectors(archive_of_distances)
            vector_1 = the_closest_vectors[0]
            vector_2 = the_closest_vectors[1]

            print(' ' *80)
            print(f"The closest vectors are: {vector_1}, {vector_2}")
            print(f"So they are part of the cluster {n+1}")

            # add them into the cluster
            cluster.append(vector_1)
            cluster.append(vector_2)
            
            # calculate the middle point of these vectors (cluster)
            the_middle_vector = middle_vector(vector_1, vector_2)

            print(f"And the cluster {n+1} is: {the_middle_vector}")
            print(' ' *80)

            # delete the_closest_vectors from the random_list
            random_list.remove(vector_1) 
            random_list.remove(vector_2)

            # add the middle vector to the random_list
            random_list.append(the_middle_vector)

            # plot that middle vector (cluster)
            ratio = get_euclidean_distance(vector_1, vector_2)
            graph.circle(the_middle_vector[0], the_middle_vector[1], radius= ratio, color = palette[11][(len(vectors) - len(vectors_dict)) % len(palette[11])], fill_alpha = 0.1)
            n = n+1
        else:
            break
        
    show(graph)
    
if __name__ == '__main__':
    print('*' * 80)
    number = int(input("Choose the number of vectors: "))
    print(' ' * 80)

    vectors = list_of_random_vectors(number)
    print(f"The random vectors are: {vectors}")

    clustering(vectors)

![](

![](

Comparto mis NOTAS:
Es un algoritmo jerárquico que agrupa objetos similares en grupos llamados clusters.
El algoritmo comienza tratando a cada objeto como un cluster individual y luego realiza los siguientes pasos de manera recursiva:
-Identifica los dos cluster con menor distancia (los mas similares).
-Agrupa estos os clusters en uno nuevo.
El output final es un dendograma que muestra la relación entre grupos y objetos.
Es importante determinar que medida vamos a utilizar y los puntos a utilizar en cada cluster (linkage criteria).
Existen por lo menos 3 métodos para medir esta distancia:
-Tomar los puntos mas cercanos (singly linkage)
-Tomar los puntos más lejanos entre grupos (complete linkage).
-Buscar las puntos promedio de cada grupo (average linkage)

Hola! Este es mi codigo. Genera un grafico nuevo por cada iteración que elimina la pareja de puntos con distancia minima y añade el punto promedio que corresponde al centro del cluster.

from random import randint
import math
from bokeh.plotting import figure, output_file, show

def generar_puntos(numero_puntos):
    puntos = []
    valor_x_max = 10  #valor maximo que puede tener X
    valor_y_max = 10  #valor maximo que puede tener Y

    for _ in range(numero_puntos):
        nuevo_punto = randint(0,valor_x_max),randint(0,valor_y_max)
        puntos.append (nuevo_punto)
    
    return puntos

def calcula_distancia_euclidiana(punto_a, punto_b):
    return math.sqrt((punto_a[0] - punto_b[0])**2 + (punto_a[1] - punto_b[1])**2)    

def promedio_puntos(punto_a,punto_b): #genera un punto en las coordenadas promedio
    print (punto_a[0], punto_b[0])
    print (punto_a[1], punto_b[1])
    x_promedio = (punto_a[0] + punto_b[0])/2
    y_promedio = (punto_a[1]+ punto_b[1])/2
    return x_promedio,y_promedio

def agrupar_puntos(puntos):
    lista_parejas=[]
    lista_distancias=[]
    a=0
    #print(f'A = {a}')

    #Creamos una lista con todas las parejas posibles entre puntos (excluyendo repeticiones y la pareja con el mismo punto). Creamos una lista con las distancias calculadas para cada pareja. Los índices de ambas listas seran correlativos, por lo que podremos calcular la distancia minima y extraer la pareja de puntos correspondiente para generar el cluster y eliminar los puntos.

    while a < len(puntos):
        b = a #evitamos que se repitan los cálculos de las distancias por duplicado. Ej: (1,0, 0.231) y (0,1, 0,231)
        #print(f'B = {b}')
        punto_a = puntos[a]

        while b < len(puntos):
            punto_b = puntos[b] 
            if punto_a != punto_b: #con esto evitamos que calcule la distancia con sigo mismo y de 0.0
                a_b = (punto_a,punto_b) #crea una tupla que contiene la pareja de puntos a comparar
                distancia = calcula_distancia_euclidiana(punto_a,punto_b) #calcula la distamcia de la pareja de puntos
                #print(distancia)
                lista_parejas.append(a_b) #añade la pareja de puntos a la lista de parejas
                lista_distancias.append(distancia) #añade la distancia entre los puntos de la pareja
            b +=1
        a +=1
    
    #print(lista_parejas)
    #print(lista_distancias)
    indice_distancia_minima = lista_distancias.index(min(lista_distancias)) #buscamos la distancia minima de la lista y devolvemos el indice
    
    print(f'Indice distancia minima: {indice_distancia_minima}')
    puntos_distancia_minima = lista_parejas[indice_distancia_minima] #extrae la pareja de puntos del indice que corresponde al de la distancia minima
    #print(puntos_distancia_minima)
    nuevo_cluster = promedio_puntos(puntos_distancia_minima[0],puntos_distancia_minima[1]) #crea un nuevo cluster (punto) en las coordenadas promedio de la pareja ("AVERAGE LINKAGE")

    #print(nuevo_cluster)
    
    puntos.remove(puntos_distancia_minima[0]) #elimina el punto_a de la pareja de la lista de puntos
    puntos.remove(puntos_distancia_minima[1]) #elimina el punto_b de la pareja  de la lista de puntos
    puntos.append(nuevo_cluster)                #añade el cluster generado a la lista de puntos
    #print(f'Puntos nuevos: {puntos}')           

    return puntos   #actualizamos la lista de puntos

def extraer(matriz, indice):
    lista = []
    i = 0
    for i in range(len(matriz)):
        punto = matriz[i]
        valor = punto[indice]
        lista.append(valor)
        i += 1
    return lista

def graficar(puntos,contador):
    puntos_x = extraer(puntos,0)
    puntos_y = extraer(puntos,1)

    output_file(f'jerarquia_paso{contador}.html') # el contador indica la iteración correspondiente
    grafico = figure(plot_width=400, plot_height=400)

    # add a circle renderer with a size, color, and alpha
    grafico.circle(puntos_x,puntos_y, size=20, color="navy", alpha=0.5)

    # show the results
    show(p)
 

if __name__ == "__main__":
    
    numero_puntos = int(input('Indique el número de puntos aleatorios a generar:'))
    numero_clusters = int(input('Indique el número de clusters esperados:'))

    puntos = generar_puntos(numero_puntos)
    print(puntos)

    contador_graficos = 0 #permite ordenar los diferentes graficos HTML generados
    graficar(puntos,contador_graficos) #graficado inicial de los puntos
    
    while numero_clusters < len(puntos): #bucle que genera clusters hasta llegar al numero de clusters indicados
        contador_graficos +=1
        puntos_actualizados = agrupar_puntos(puntos)
        puntos = puntos_actualizados #actualiza los puntos eliminando la pareja con distancia minima y añade el cluster
        graficar(puntos,contador_graficos) #graficado de la siguiente iteracion

Aqui un mi codigo, con un ejemplo sencillo que como realicé el agrupamiento jerarquico y el dendrograma. Cree una lista de coordenadas aleatorios y estas las agrupé con este algoritmo haciendo uso de las librerias random y scipy, tambien usé bokeh para mostrar las posiciones de los puntos de manera grafica.

import random
# libreria para dendrograma
import scipy.cluster.hierarchy as sch
from scipy.cluster.hierarchy import dendrogram, linkage
# librerias para graficas
from bokeh.plotting import figure, show


# generamos coordeanadas aleatorias en un espacio 2D
def random_points(number_of_points):
    # listas para las coordenadas individuales y en pares
    x_coords = []
    y_coords = []
    coords = []
    # generamos las coordenadas
    for i in range(number_of_points):
        x_coords.append(random.randint(1,100))
        y_coords.append(random.randint(1,100))
        coords.append([x_coords[i], y_coords[i]])
    # regresamos una tupla con las coordenadas en separado y en pares
    return (x_coords, y_coords, coords)

# Funcion que genera la grafica que muestra los puntos generados
def plot_points(points):
    # parametros del plot
    pl = figure(plot_width=600, plot_height=600)
    pl.circle(points[0], points[1], size=5, color="navy", alpha=1)
    show(pl)

# PRINCIPAL
def main(number_of_points):
    points = random_points(number_of_points)
    # Para debugging
    print(points)
    print(f"X coordinates: {points[0]}")
    print(f"Y coordinates: {points[1]}")
    print(f"Pair of points: {points[2]}")
    plot_points(points)
    
    # Graficamos el Dendrograma
    cluster_jerarquico = linkage(points[2])
    dendrograma = sch.dendrogram(cluster_jerarquico) 


if __name__ == "__main__":
    number_of_points = 20
    main(number_of_points)

Puntos

Dendrograma

decidi hacer el programa en jupyter, principalmente por que al ahora de graficar no detiene el programa
aunque me hubiera gustado hacerlo mas pequeño

import random 
import matplotlib.pyplot as plt
import math
def main():
    posx=np.array([random.randint(1,11) for i in range(4)])
    posy=np.array([random.randint(1,11) for i in range(4)])
    print(posx)
    print(posy)
    plt.scatter(posx, posy)
    plt.show()
    while len(posx)>1:
        posx=list(posx)
        posy=list(posy)
        i=random.randint(0,(len(posx)-1))
        posx, posy=minimo(posx,posy,i)
        posx=np.array(posx)
        posy=np.array(posy)
        plt.scatter(posx, posy, color="red")
        plt.show()
        
    
    print(f'El punto se encuentra en la posicion x= {posx} y y= {posy}')
    

def distancia(x_a, y_a, x_s, y_s):
    return math.sqrt((x_a-x_s)**2 + (y_a-y_s)**2)
def nuevo(pos_x,pos_y,ahora, pos):
    x=(pos_x[ahora]+pos_x[pos])/2
    y=(pos_y[ahora]+pos_y[pos])/2
    return x, y
def minimo(pos_x,pos_y, ahora):
    d2=100
    for j in range(len(pos_x)):
        d=distancia(pos_x[ahora], pos_y[ahora], pos_x[j],pos_y[j])
        if j==ahora:
            continue
        if d<d2:
            d2=d
            pos=j
    nuevoX, nuevoY= nuevo(pos_x,pos_y,ahora, pos)
    if pos<ahora:
        pos_y.pop(ahora)
        pos_x.pop(ahora)
        pos_x.pop(pos)
        pos_y.pop(pos)
    else:
        pos_x.pop(pos)
        pos_y.pop(pos)
        pos_y.pop(ahora)
        pos_x.pop(ahora)
    
    pos_x.append(nuevoX)
    pos_y.append(nuevoY)
    return pos_x, pos_y


   
    
if __name__=='__main__':
    main()

Este articulo explica bien el funcionamiento del algoritmo, a mi me sirvió mucho para implementar el mío 😃

Por fin salio

Entendí perfectamente el concepto pero a la hora de hacer el reto me rendí por problemas de compatibilidad en la librería de bokeh 😦 pero encontre que con matplotlib y scipy es mucho más fácil 😃

Agrupamiento jerárquico
Toma los puntos más cercanos de los datos y los agrupa (generando un nuevo punto), luego vuelve a detectar los puntos (o grupos) más cercanos y los agrupa iterativamente hasta que quede un solo punto generando un dendrograma que nos permite conocer las relaciones entre los objetos y grupos de nuestra data.

Nota:
La métrica de distancia la definimos de acuerdo al programa. Puede ser:

• puntos más cercanos: single linkage
• puntos más lejanos: complete linkage
• puntos más promedio: average linkage

Agrupamiento Jerárquico

Puede pertenecer a dos grupos:

• Aglomerativo: Empieza de “abajo hacía arriba”, cada observación es considerada como un grupo y se van uniendo estos grupos a medida que se sube en la jerárquia.

• Divisivo: Se empieza de “arriba hacía abajo” se tiene un gran grupo con el que se comienza y se van separando a medida que se va bajando en la jerárquia.

Scikit learn

Para utilizar el agrupamiento Jerárquico en scikit learn se utiliza el objeto AgglomerativeClustering, este el proceso aglomerativo.

Es llamada con AglomerativeClustering() y debes pasarle ciertos parámetros, los cuales son:

• n_cluster= Es el número de agrupamientos a encontrar. Este parámetros acepta enteros, si se deja vacío el valor por defecto es 2.

• affinity= Este es el que define que medida de distancia usaremos, Acepta strings el valor por defecto es ‘euclidian’ que calcula la distancia a través de la fórmula

  
  también se encuentran ‘l1’, ‘l2’, ‘manhattan’, ‘cosine’, o ‘precomputed’.
  Manhattan se calcula a través de la fórmula

  
  Sí se utiliza el método de Ward para la unión de los puntos sólo puede utilizarse la distancia euclidiana. Además sí se usa el precomputed debe una matriz de distancia (no de parecido) para que se ajuste al método.

• memory= Se usa para guardar en cache el resultado. Acepta un string o un objeto con interface joblib.Memory (que se usa para capturar el valor de una función cada vez que es llamada con los mismos argumentos de entrada). Por defecto no se hace este guardado, si se coloca un string este debe ser la ruta del directorio.

• connectivity= Es la matriz de conectividad. Define para cada muestra las muestras vecinas usando una estructura de datos determinada. Acepta una array o una función llamable, siendo esta la matriz de conectividad como tal o la función que transforma los datos en una matriz de conectividad. Por defecto es None.

• compute_full_tree= Puedes detener la construcción del dendograma en cierta cantidad de agrupamientos(n_clusters). Es utilizado para minimizar el tiempo de cómputo sí el número de agrupaciones no es pequeño en comparación al número de muestras. Acepta el string ‘auto’ o un booleano. Por defecto es ‘auto’, que puede ser equivalente a True o False dependiendo de otros parámetros.

• linkage= Es el criterio de unión a utlizar. El algoritmo unirá el par de agrupaciones que minimicen ese criterio. Puede ser ‘ward’, ‘complete’, ‘average’ o ‘single’

1. ‘ward’ minimiza la varianza de los agrupamientos que se están uniendo.
2. ‘complete’ usa la distancia maxima entre todas las observaciones de los dos conjuntos.
3. ‘average’ usa el average de la distancia de cada observación de dos conjuntos.
4. ‘single’ usa el mínimo de la distancia entre todas las observaciones de dos conjuntos.

Para saber más de cómo funciona AglomerativeClustering en scikit learn puedes visitar acá

Comparto mi solución al reto:

import random
import math
from time import sleep
from math import pi
from bokeh.plotting import figure, show
from bokeh.io import output_notebook, push_notebook
get_ipython().run_line_magic('matplotlib', 'inline')
output_notebook()


# Graficado puntos


# Función para calcular la distancia euclidiana
def distancia_euclidiana(a, b, c, d):
    distancia = math.sqrt( (a - c)**2 + (b - d)**2 ) # Distancia Euclidiana
    distancia = round(distancia, 5)
    return distancia



# Función para generar colores aleatorios
def random_color():
    rgbl=[255,2,0]
    random.shuffle(rgbl)
    return tuple(rgbl)


def analizar_distancia_min(lista_x, lista_y):
    
    
    #print(f'Lista x {lista_x}')
    #print(f'Lista y {lista_y}')    
    
    if len(lista_x) > 1:
        # Creando lista de distancias entre puntos y coordenadas de la comparacion
        lista_distancias = []
        lista_comparativo = []

        for i in range(len(lista_x)):

                a = lista_x[i]
                b = lista_y[i]

                for j in range(len(lista_x)):
                    c = lista_x[j]
                    d = lista_y[j]

                    coordenada_1 = [a, b]
                    coordenada_2 = [c, d]
                    punto1  = [[a, b], [c, d]]
                    punto2  = [[c, d], [a, b]]

                    if ((coordenada_1 != coordenada_2) and (punto1 not in lista_comparativo) 
                        and(punto2 not in lista_comparativo)):

                        distancia = distancia_euclidiana(a, b, c, d)
                        lista_distancias.append(distancia)
                        lista_comparativo.append(punto1)


        # Puntos mas cercanos
        valor_min = min(lista_distancias)
        posicion = lista_distancias.index(valor_min)
        resultado = lista_comparativo[posicion]
        
        

        # Ubicando la coordenada media entre los dos puntos
        x_centroide_dif = (abs((resultado[0][0]) - (resultado[1][0])))/2
        y_centroide_dif = (abs((resultado[0][1]) - (resultado[1][1])))/2
        x_centroide_min = min((resultado[0][0]), (resultado[1][0]))
        y_centroide_min = min((resultado[0][1]), (resultado[1][1]))
        x_centroide = x_centroide_min + x_centroide_dif
        y_centroide = y_centroide_min + y_centroide_dif
        

        # Quitando puntos ya usados
        lista_x.remove(resultado[0][0])
        lista_x.remove(resultado[1][0])
        lista_y.remove(resultado[0][1])
        lista_y.remove(resultado[1][1])

        # Agregando punto medio
        lista_x.append(x_centroide)
        lista_y.append(y_centroide) 


        
        
        # Radio de la circunferencia
        radio_centroide = (valor_min)
    
        
        
        # Modificando la grafica haciendo agrupación
        p.asterisk(x=[x_centroide], y=[y_centroide], size=20, color="green")
        p.scatter(x=[x_centroide], y=[y_centroide], radius=radio_centroide, color="black", 
                      fill_color=random_color(), width=5)

        # push_notebook to the concerned target
        push_notebook(handle=target)        
        
        sleep(3)
        
        return analizar_distancia_min(lista_x, lista_y)
    
    else:
        
        return print("Fin")



# Coordenadas
valores_x = [87, 6, 11, 55, 20, 75, 17, 37]
valores_y = [69, 28, 78, 58, 33, 75, 61, 68]


# Graficando puntos
p = figure(title="Titulo", x_axis_label='Titulo x', y_axis_label='Titulo y')
p.scatter(valores_x, valores_y, legend_label="Serie", line_width=2)
target = show(p, notebook_handle=True)


analizar_distancia_min(valores_x, valores_y)

https://drive.google.com/file/d/1nX5Uq1XGF7DXylu5bqKEODnAiFUw_38z/view?usp=sharing

Después de mucho tiempo he aquí mi solución, aunque aún me falta graficar.

import random
import math
import time

def metrica_euler(coordenada_inicio, coordenada_final):
    '''Regresa la distancia utilizando la metrica de euler'''
    diff_x = coordenada_final[0] - coordenada_inicio[0]
    diff_y = coordenada_final[1] - coordenada_inicio[1]
    distancia = math.sqrt(diff_x**2 + diff_y**2)
    return distancia


def emparejamiento(coordenada_ref, coordenada_meta, coordenada_candidata):
    '''
    Ingresamos tres coordenadas 
    La "coordenada_ref" es el punto de partida de dos distancias
    La primera distancia se compone con la "coordenada_meta".
    La segunda distancia se compone con la "coordenada_candidata".
    Ademas se necesita una tercera distancia que se compone por
    la "coordenada_meta" y la "coordenada candidata".

    Se comparan las tres distancias y se regresan 3 coordenas que
    ref, meta, candidata
    '''
    primera_distancia = metrica_euler(coordenada_ref, coordenada_meta)
    segunda_distancia = metrica_euler(coordenada_ref, coordenada_candidata)
    tercera_distancia = metrica_euler(coordenada_candidata, coordenada_meta)
    if tercera_distancia < primera_distancia and tercera_distancia < segunda_distancia:
        ref = coordenada_candidata
        meta = coordenada_meta
        candidata = coordenada_ref
    elif segunda_distancia < primera_distancia:
        ref = coordenada_ref
        meta = coordenada_candidata
        candidata = coordenada_meta
    else:
        ref = coordenada_ref
        meta = coordenada_meta
        candidata = coordenada_candidata
        
    return ref, meta, candidata


def nueva_coordenada(cluster):
    '''Se genera una coordenada a partir de un cluster'''
    inicio =  cluster['inicio']
    final = cluster['final']
    x = (final[0] + inicio[0]) / 2
    y = (final[1] + inicio[1])
    return [x, y]


def agrupamiento_jerarquico(coordenadas):
    '''
    Obten el par de coordenas mas cercanas de una serie de coordenas 
    y creamos un cluster con ese par
    '''
    cluster = {}
    coordenadas_sin_pareja = []
    coordenada_meta = random.choice(coordenadas)
    coordenadas.remove(coordenada_meta)
    while len(coordenadas) > 1:
        coordenada_ref = coordenadas[0]
        coordenada_candidata = coordenadas[1]
        ref, meta, candidata = emparejamiento(coordenada_ref, coordenada_meta, coordenada_candidata)
        # Comparamos que coordenadas se mantienen igual, para saber cual de las 3 se tiene que remover
        # Si todo se mantiene igual quiere decir que la candidata no genera una distancia mas corta
        if meta == coordenada_meta and coordenada_candidata == candidata:
            coordenadas_sin_pareja.append(coordenada_candidata)
            coordenadas.remove(coordenada_candidata)
        # Si nuestra ref se mantiene pero las otras dos no, significa que nuestra meta necesita ser cambiada
        elif ref == coordenada_ref and meta != coordenada_meta:
            coordenadas_sin_pareja.append(coordenada_meta)
            coordenada_meta = coordenada_candidata
            coordenadas.remove(coordenada_candidata)
        # si nuestra meta se mantiene pero lo demas no, significa que nuestra ref necesita ser cambiada
        elif meta == coordenada_meta and ref != coordenada_ref:
            coordenadas_sin_pareja.append(coordenada_ref)
            coordenadas.remove(coordenada_ref)
        
    cluster['inicio'] = coordenadas[0]
    cluster['final'] = coordenada_meta
    return cluster, coordenadas_sin_pareja


def encontrando_clusters(coordenadas):
    '''
    Encontramos la coordenada final, y todos los clusters 
    que se fueron creando para llegar a ella
    '''
    clusters_temporal = []
    clusters = []
    while len(coordenadas) > 1:
        print(coordenadas)
        cluster, coordenadas = agrupamiento_jerarquico(coordenadas)
        clusters_temporal.append(cluster)
        size_coord = len(coordenadas)
        size_clust_temp = len(clusters_temporal)
        # cuando nos quedamos con 1 o 0 coordenadas, vemos si hay mas de un cluster
        # Por que quiere decir que aun no tenemos un cluster que unifique todas
        if (size_coord <= 1 and size_clust_temp >= 1):
            for cluster in clusters_temporal:
                print(cluster)
                coordenada = nueva_coordenada(cluster)
                coordenadas.append(coordenada)
                clusters.append(cluster)
            clusters_temporal.clear()
            print()
    coordenada_final = coordenadas[0] 

    return clusters, coordenada_final

Hola,
Generé un código para agrupar “n” random features vectors de “m” dimensiones

# programa de agrupamiento - con denograma

import random

################### calse para crear los puntos o feature vector #############################
class feature_vector_random:

    def __init__(self, number, dimension):
        self.num = number 
        self.dim = dimension

    def vectores_random(self):          # genera "num" vectores de dimension "dim"
        vect = []
        vectM = []
        for i in range(self.num):
            for j in range(self.dim):
                #valorRand =  2*(random.random()-0.5)    ## los valores van de -1 a +1
                valorRand = random.randint(1,100)        ## utilizo esto para visualizar mejor el desarrollo del código

                vectM.append(valorRand)
            vect.append(vectM)
            vectM = []
        return vect
     

################################### clase de agrupamiento ############################
class agrupamiento_de_vectores:

    def __init__(self, vectores_Features):
        self.vecFeat = vectores_Features
        
    def agrupamiento_jerarquico(self):
        denograma = []             
        denograma_ind =[]
        num_vecFeat = len(self.vecFeat)
        vector = self.vecFeat

        for i in range(num_vecFeat):
            Distancias = distancias_(vector)            # creo una matriz de distancias 
            min_i,vect_i, min_j,vect_j, vector = elegir_cluster(vector, Distancias)  # esta función elijge el grupo a clusterizar
                        
            denograma_ind.append([min_i,min_j]) ## solo utilizo denograma_ind para ver el còdigo
            denograma.append([vect_i,vect_j])   
        
        return denograma

############# Función de distancia
## calcula la matriz distancia tipo [[d11 d12 d13...d1n],[d21,d22,d23...d2n]...]  
## recordar que dij == dji and dii == djj == 0

def distancias_(vectors):
    tamano = len(vectors)
    DIST = []
    DISTM = []
      
    for i in range(tamano):
        for j in range(tamano):
            if i == j:
                distij = 0         
            else:
                distij = metodo_distancia1(vectors[i],vectors[j])
            DISTM.append(distij)
        DIST.append(DISTM)
        DISTM = []
        
    return DIST


############# Metodo de disntacia1 = euclidiano
## es la distnacia euclidiana de dos vectores
def metodo_distancia1(X1, X2):
    num = len(X1)
    sum = 0
    for i in range(num): 
        sum += (X1[i] - X2[i])**2
    return (sum)**0.5


############ elegir los vectores a hacer un cluster o agruparse
## Como la matriz de distancia es simètrica y la identidad = 0 (dii == 0), relleno...
## la parte triangular inferior de la matriz y la identidad del valor 100*màximo
## esto es para que al buscar el menor valor no encuentre un cero de la identidad y no...
## encuentre nada en la parte triangular inferior de la matriz

def elegir_cluster(vector, MDistan):
    MD = []
    MDD = []
    n = len(MDistan)
    max_valor = 100*maximo_val(MDistan)
    for i in range(n):
        for j in range(n):
            if i < j:
                MDij = MDistan[i][j]
            else:
                MDij = max_valor
            MD.append(MDij)   
        MDD.append(MD)
        MD=[]     
    
    min_val, min_i, min_j = indice_min(MDD)
    vector_i = vector[min_i]
    vector_j = vector[min_j]
    new_vectorij = suma_vector_nuevo(vector_i,vector_j)
    new_vector = nueva_matriz_vectores(vector,new_vectorij, min_i, min_j)

    return min_i,vector_i, min_j,vector_j, new_vector


## retira los vectores de la distancia minima y lo reemplaza por el vector nuevo
def nueva_matriz_vectores(vector, new_vectorij,min_i,min_j):
    # por defecto j > i // recordar que es una matriz triangular superior 
    new_matrix_vec = vector[:min_i] + vector[min_i+1:min_j] + vector[min_j+1:]
    new_matrix_vec.append(new_vectorij) 
    return new_matrix_vec

## crear el nuevo vector que reemplaza a los dos anteriores
## es el vector "promedio" o la suma de ambos entre 2
def suma_vector_nuevo(Xi, Xj):
    n = len(Xi)
    new_vec_sum = []
    for k in range(n):
        nvs = (Xi[k] + Xj[k])/2      ## promedio 
        new_vec_sum.append(nvs)
    return new_vec_sum

## dar la posición i,j y el menor valor de una matriz
def indice_min(MDD):
    min_val = minimo_val(MDD)

    n = len(MDD)
    for i in range(n):
        for j in range(n):
            if MDD[i][j] == min_val:
                min_i = i
                min_j = j
                break
  
    return min_val, min_i, min_j

## dar el maximo valor de la matriz
def maximo_val(M):
    n = len(M)
    max_val = M[0][0]
    for i in range(n):
        for j in range(n):
            if M[i][j] > max_val:
                max_val = M[i][j]
    return max_val

## dar el minimo valor de la matriz
def minimo_val(M):
    n = len(M)
    min_val = M[0][0]
    for i in range(n):
        for j in range(n):
            if M[i][j] < min_val:
                min_val = M[i][j]
    return min_val


####################################### Entry Point ############################

if __name__ == '__main__':
    number = 20     # numero de vectores, 
    dimension = 5   # dimension de los vectores
    
    Fvectors = feature_vector_random(number , dimension)
    rand_vectors = Fvectors.vectores_random() 
    print('-----numero de Features Vectors----------')
    print(len(rand_vectors))
    print('------Features Vectors---------')
    print(rand_vectors)
    print('---------------')
    clusters = agrupamiento_de_vectores(rand_vectors)
    print('---------------')
    denograma = clusters.agrupamiento_jerarquico()
    print('-----Denograma-------')
    print(denograma)

hola! me demoré bastante haciendo el reto jeje, planteé generar datos que podrían graficarse como el dendrograma no sé si sea lo correcto, por favor si alguien sabe como mejorar mi código sería de mucha ayuda.

import random 
import math

    
def hierarchy(array):
    cluster={}
    other_array=array[::]
    for number  in array:
        other_array.remove(number)
        for other_number in other_array: 

            euclidean_distance= math.sqrt((number-other_number)**2)
            cluster[(other_number, number)]= euclidean_distance
        
        other_array.append(number)

            #print(cluster)
    least_distance(array, cluster)


def least_distance(array,cluster):
    valores=[]
    grupos=[]
    circulos=[]
    if len(array)==1:
        return 0
    
    for value in sorted (cluster.values()):
        valores.append(value)
        grupos.append(list(cluster.keys())[list(cluster.values()).index(value)])

        distancias= valores[0:len(array)]
        clusters=grupos[0:len(array)]
    endeograma(distancias,clusters, array)
           

def tipos( array):
    for posicion in array:
        if type(posicion) is tuple:
            #print('yes')
            media=sum(posicion)/len(posicion)
            array.remove(posicion)
            array.append(media)
    return array 
    
def eliminar_numeros_de_lista(numero_1, numero_2, array_rec, circulito):
    
    while len(array_rec)>=0:
        array_rec.remove(numero_1)
        array_rec.remove(numero_2)
        array_rec.append(circulito)
        #print(f'el array recuperado es  = {array_rec}')
        array_nuevo= tipos(array_rec)
        #print(f'array_nuevo es {array_nuevo}')
        return(array_nuevo)
    

def endeograma( valores, grupos, array): 
    new_array=array[::]
    array_rec=array
    arbolito={}
    while len (new_array ) >= 1:
        for posicion in range(len(new_array)-1):
            if min(valores)== valores[posicion]:
                distance=valores[posicion]
                circulito=grupos[posicion]
                numero_1,numero_2=grupos[posicion]
                arbolito[distance]=circulito    
                #print(f'numero1 = {numero_1} y numero_2 = {numero_2}')
                array_nuevo=eliminar_numeros_de_lista(numero_1, numero_2, array_rec, circulito)
                new_array.remove(new_array[posicion])
                print(f' el arbolito: {arbolito}')

                hierarchy(array_nuevo)
            if len(array_nuevo)==1:
                break

        

        break            

   
if __name__=='__main__':
    array=[random.randint(1,20) for i in range(10)] 
    print (array)
    print('el arbolito: {distancia:(cluster)}')
    hierarchy(array)```

hierarchical-clustering.py
[1, 6, 15, 10, 12, 16, 5, 7, 9, 14]
el arbolito: {distancia:(cluster)}
 el arbolito: {1.0: (5, 6)}
 el arbolito: {1.0: (16, 15)}
 el arbolito: {1.0: (9, 10)}
 el arbolito: {1.5: (5.5, 7)}
 el arbolito: {1.5: (15.5, 14)}
 el arbolito: {2.5: (9.5, 12)}
 el arbolito: {4.0: (10.75, 14.75)}
 el arbolito: {5.25: (6.25, 1)}
 el arbolito: {9.125: (3.625, 12.75)}

Hola!
Así lo realice yo…

Dejo por acá el código, aunque aun no entiendo como subir imágenes a este chat, si alguno me explica subo la evidencia de como queda…

El programa crea un diccionario de puntos con sus dos coordenadas del tamaño indicado, y con ese trabaja reemplazando por clusters

import random
from plotting import Plotting


plot_circles = Plotting()

def make_clusters(distances_points, points):

    while len(points) > 1:
        distances = [n[2] for n in distances_points]
        min_distance = min(distances)
        index_min_distance = distances.index(min_distance)

        point1 = points[distances_points[index_min_distance][0]]
        point2 = points[distances_points[index_min_distance][1]]
        new_cluster =  medium_point(point1,point2)
        new_cluster_name = obtain_cluster_name(points) 

        plot_circles.add_circles(new_cluster[0],new_cluster[1],(min_distance / 2),(random.randint(0,255),random.randint(0,255),random.randint(0,255)),0.5, f'Cluster {new_cluster_name[1]}')

        

        points.pop(distances_points[index_min_distance][0])
        points.pop(distances_points[index_min_distance][1])
        points[new_cluster_name] = new_cluster
        obtain_cluster_name(points)
        distances_points = take_distances(points)
        print('----------')
        print(points)
        print(distances_points)


def obtain_cluster_name(points):
    last_cluster = 0
    keys = points.keys()
    print('keys')
    for key in keys:
        print(key)
        if key[0] == 'C':
            if int(key[1]) > last_cluster:
                last_cluster = int(key[1])

    return f'C{last_cluster + 1}'



def take_distances(points):
    distances = []

    n = 0
    key_list = list(points.values())
    for point1 in points:
        for point2 in points:
            if key_list.index(points[point2]) < n or point1 == point2:
                continue
    
            distance = distance_between(points[point1],points[point2])
            distances.append((point1,point2,distance))

        n += 1

    return distances

def medium_point(point1, point2):
    return ((point1[0] + point2[0])/2,(point1[1] + point2[1])/2)

def distance_between(point1,point2):
    return ((point2[1] - point1[1])**2 + (point2[0] - point1[0])**2)**(1/2)


def generate_vectors(q_vectors):
    return {f'P{n}':(random.randint(0,20),random.randint(0,20)) for n in range(q_vectors)}


if __name__ == '__main__':
    
    q_points = int(input("Ingrese la cantidad de vectores a ordenar: "))

    points = generate_vectors(q_points)
    print(points)
    distances = take_distances(points)
    print(distances)

    plot_circles.add_circles([points[n][0] for n in points],[points[n][1] for n in points],0.25,"black",1, "Point")
    

    make_clusters(distances,points)

    plot_circles.plot()```

from bokeh.plotting import figure, output_file, show

output_file(“circles.html”)

class Plotting:

def __init__(self): 
    self.p_circles = figure(plot_width = 1000, plot_height = 500, x_range = (-2,22), y_range = (-2,22))
   

def add_circles(self, x_axis, y_axis, radius, color, alpha, legend_label):
    self.p_circles.circle(x_axis,y_axis,radius = radius, color = color, alpha = alpha, legend_label = legend_label)

def plot(self):
    show(self.p_circles)```

Agrupamiento jerárquico

• Agrupa objetos similares en grupos llamados clusters
• El algoritmo comienza tratando a cada objeto como un cluster individual y luego realiza los siguientes pasos de manera recursiva:
  - Identifica los dos clusters con menor distancia (los más similares).
  - Agrupa los dos clusters en uno nuevo.
• El output final es un dendrograma que muestra la relación entre objetos y grupos.
• Es importante determinar qué medida de distancia vamos a utilizar y los puntos a utilizar en cada cluster.
  • Existen por lo menos 3 diferentes métodos para medir esta distancia:
    • Tomar los puntos mas cercanos.
    • Tomar los puntos mas lejanos entre grupos.
    • Buscar los puntos promedios de cada grupo.

Despues de mucho esfuerzo (casi 2 horas) logré armar el programa. La parte grafica todavia me cuesta pero se que es cuestion de aprender a usar bokeh.

Estoy abierto a escuchar consejos para mejorar el programa y cualquier critica que quieran hacer es bienvenida.

import random
import collections
import operator

def genera_vector():
    #aca genero un vector cualquiera en la region (0,20) en x y (0,20) en y
    x = random.randint(0,20)
    y = random.randint(0,20)
    return (x,y)

def genera_lista_de_vectores(cantidad):
    #aca le digo cuantos vectores tiene que generar y los meto en una lista
    vectores = []
    for _ in range(cantidad):
        vector = genera_vector()
        vectores.append(vector)
    return vectores

def une_puntos_mas_cercanos(vectores):
    #esta funcion nos devuelve ((vector1,vector2),distancia) despues lo ordenamos y con eso unimos los dos vectores que den lo mas chico
    vectores_sin_repetidos = saca_redundancias(vectores)
    diccionario_vectores_distancias = {}
    for i in vectores:
        for j in vectores:
            if j == i:
                pass
            else:
                diccionario_vectores_distancias[(i,j)] = calcula_distancia_entre_puntos(i,j)
    ordenado = valor_minimo_en_un_dict(diccionario_vectores_distancias)
    puntos_a_unir = ordenado[0][0]
    punto1, punto2 = puntos_a_unir
    x1, y1 = punto1
    x2, y2 = punto2
    vectores.remove(punto1)
    vectores.remove(punto2)
    xnuevo = (x1 + x2) /2
    ynuevo = (y1 + y2) /2
    puntonuevo = (xnuevo,ynuevo)
    vectores.append(puntonuevo)
    return vectores
    


def saca_redundancias(vectores):
    #esta funcion me elimina si hay un valor repetido para que no hayan redundancias ni distancia 0
    counter = dict(collections.Counter(vectores))
    repetido = 0
    for i in counter.items():
            if i[1] > 1:
                repetido = int(i[1])
                vector = i[0]
                for _ in range(repetido-1):
                    vectores.remove(vector)
    return vectores

def calcula_distancia_entre_puntos(vector1,vector2):
    #esta funcion calcula la distancia entre dos puntos usando pitagoras
    x1, y1 = vector1
    x2, y2 = vector2
    dist_x = x1 - x2
    dist_y = y1-y2
    dist = (dist_x**2 + dist_y**2)**0.5
    return dist



def valor_minimo_en_un_dict(dict):
    #esta funcion devuelve una tupla (valor minimo, key del valor) para un diccionario
    #recibe diccionario con muchos keys y valores acorde
    ordenado_de_menor_a_mayor = sorted(dict.items(), key=operator.itemgetter(1))
    return ordenado_de_menor_a_mayor


if __name__ == '__main__':
    cantidad_de_puntos = int(input('¿Cuantos puntos queres usar? '))
    cantidad_de_clusters = int(input('¿Cuantos clusters queres tener al final? '))
    vectores = genera_lista_de_vectores(cantidad_de_puntos)
    print('Los vectores de inicio son:')
    print(vectores)
    while len(vectores)>cantidad_de_clusters:
        une_puntos_mas_cercanos(vectores)
    print('Los vectores con los que finalizaste como cluster son: ')
    print(vectores)```

Por si alguien gusta guiarse, así realicé el agrupamiento jerarquico, el codigo tambien genera pestañas donde se puede apreciar graficamente como se van agrupando las coordenadas.

import random
import math
from bokeh.plotting import figure, show


class coordenadas:

    def __init__(self, dupla):
        self.x = dupla[0]
        self.y = dupla[1]

    def distancia(self, otra_cordenada):
        return (pow(self.x - otra_cordenada.x ,2) + pow(self.y - otra_cordenada.y ,2))**0.5

    def punto_medio(self, otra_coordenada):
        return ((self.x + otra_coordenada.x) / 2 , (self.y + otra_coordenada.y) / 2)

    def coord_izq(self):
        return self.x
    
    def coord_der(self):
        return self.y

def borrar_coordenada(lista, coordenada):
    list_coord = lista
    coord_1 = coordenadas(coordenada).coord_izq()
    coord_2 = coordenadas(coordenada).coord_der()
    nueva_coord = coordenadas(coord_1).punto_medio(coordenadas(coord_2))
    list_coord.append(nueva_coord)
    list_coord.remove(coord_1)
    list_coord.remove(coord_2)
    return list_coord


def vectores():
    lista = [(random.randint(0,10) , random.randint(0,10)) for _ in range (10)]
    return lista


def agrupamiento(lista):
    lista_1 = lista
    lista_2 = lista_1[:]
    distancias = {}
    for vector in lista_1:
        for otro_vector in lista_2:
            distancia_vectores = round( coordenadas(vector).distancia(coordenadas(otro_vector)) , 4)
            if vector == otro_vector:
                continue 
            distancias[distancia_vectores]=vector,otro_vector
        lista_1.remove(vector)

    distancia_min = min(distancias)
    borrar_coordenada(lista_2, distancias[distancia_min])
    return lista_2

def grafico(lista):
    fig = figure(plot_width=400, plot_height=400)
    x_vals = []
    y_vals = []
    for coordenadas in lista:
        x = coordenadas[0]
        x_vals.append(x)
        y = coordenadas [1]
        y_vals.append(y)
    fig.circle( x_vals, y_vals, size=20, color="navy", alpha=0.5)
    show(fig)

def run():
    lista_1 = vectores()
    print(lista_1)
    grafico(lista_1)
    for _ in range(len(lista_1)-1):
        grafico(lista_1)
        lista_1 = agrupamiento(lista_1)
        print(lista_1)
    grafico(lista_1)

if __name__ == '__main__':
    run()

Yo hice lo solicitado, pero con la opcion que el usuario inserte sus propias coordenadas (o vectores). Funciona independientemente de la cantidad que se inserte.

cords=[[2,4], [1,1] , [3,4], [10,2] , [8,15]]
#encontrar los dos puntos mas proximos entre ellos.
def distancia_vectores(cords):
    aux=0
    for i in range (0, (len(cords)-1)):
        for j in range (1, (len(cords)-i)):
            dist=((cords[i][0]-cords[i+j][0])**2+(cords[i][1]-cords[i+j][1])**2)**0.5
            if aux==0:
                aux=dist
                solucion =[i, j]
            elif dist<aux:
                aux=dist
                solucion =[i, j]
    return solucion

#promediar los puntos entre ellos y generar un nuevo punto intermedio, que reemplace

def promedio_vectores(a,b):
    return[(a[0]+b[0])/2,(a[1]+b[1])/2]

# iterar. se detiene cuando queda un solo punto.
if __name__ == "__main__":
    while(len(cords)>1):
        distancia_vectores(cords)
        print("posicion de valores de min distancia son" , distancia_vectores(cords))
        #transformacion
        valor_1=distancia_vectores(cords)
        a=cords[valor_1[0]]
        b=cords[valor_1[1]]
        #promediamos
        print("el promedio de dichos puntos" ,promedio_vectores(a,b))
        #borramos valores pasados y agregamos el nuevo promediado
        cords.remove(a)
        cords.remove(b)
        cords=cords+([promedio_vectores(a,b)])
        print("los nuevos valores a evaluar son" , cords)

Hola, en este video se explica de manera muy gráfica y didáctica el agrupamiento por K-medios y jerárquico.
https://youtu.be/LGT9v1QMgTE

Hey, tal muchachos, comparto mi código de cómo realicé el ejercicio, los resultados se muestran en consola, ya que aún estoy en busca de hacerlo con gráficos.

import random

def EncontrarPuntoCercano(puntosNum, listaX, listaY, numeroDeRound):

    if len(listaX)<2:
        print(f'Ganador!!!: Punto #{puntosNum[0]}')
        print(f'Coordenada: {listaX}, {listaY}')
        return

    auxiliarContador = 1
    gruposCercanos = []

    print(f'Vuelta #{numeroDeRound}')

    for i in range(len(listaX)):
        pX = listaX[i]
        pY = listaY[i]

        if(i<len(listaX)-1): 

            print(f'Punto #{puntosNum[i]}')
            print(f'Coordenada: {pX}, {pY}')


            #Variable "masCercano"
            #En el index "0" Almacena el valor total de la distancia entre un punto y otro más cercano
            #En el index "1" Almacena el index de cuál es esa coordenada cercana
            masCercano = [] 

            for j in range(auxiliarContador, len(listaX)):

                thisX = abs(pX-listaX[j])
                thisY = abs(pY-listaY[j])
                total = thisX+thisY

                if len(masCercano)>0:
                    if total < masCercano[0]:
                        masCercano = [total, j]
                    
                else:
                    masCercano = [total, j]
        
            print(f'Mas cercano: {masCercano}')
            gruposCercanos.append(masCercano)  

            auxiliarContador+=1
        
            print("-"*20)
        else:
            print(f'Ultimo Punto #{puntosNum[i]}')
            print(f'Coordenada: {pX}, {pY}')

    UnirCercanos(gruposCercanos, listaX, listaY, numeroDeRound)



def UnirCercanos(grupos, listaX, listaY, numeroDeRound):
    distancia = grupos[0]
    aux = distancia[0]
    indexRey = 0
    indexSubordinado = distancia[1]
    
    for i in range(1, len(grupos)):
        distancia = grupos[i]
        auxthis = distancia[0]
        if auxthis < aux:
            aux = auxthis
            indexRey = i
            indexSubordinado = distancia[1]

    NuevoGrupo(listaX, listaY, indexRey, indexSubordinado, numeroDeRound)

    


def NuevoGrupo(listaX, listaY, indexRey, indexSubordinado, numeroDeRound):
    ubicacionNuevoX = 0
    auxPunX1 = puntosX[indexRey]
    auxPunX2 = puntosX[indexSubordinado]

    if auxPunX1 < auxPunX2:
        ubicacionNuevoX = auxPunX1 + ((auxPunX2-auxPunX1)/2)
    else:
        ubicacionNuevoX = auxPunX2 + ((auxPunX1-auxPunX2)/2)


    ubicacionNuevoY = 0
    auxPunY1 = puntosY[indexRey]
    auxPunY2 = puntosY[indexSubordinado]

    if auxPunY1 < auxPunY2:
        ubicacionNuevoY = auxPunY1 + ((auxPunY2-auxPunY1)/2)
    else:
        ubicacionNuevoY= auxPunY2 + ((auxPunY1-auxPunY2)/2)

    puntosX[indexRey] = ubicacionNuevoX
    puntosY[indexRey] = ubicacionNuevoY
    
    puntosNum.pop(indexSubordinado)
    puntosX.pop(indexSubordinado)
    puntosY.pop(indexSubordinado)

    print('*'*20)
    print('*'*20)
    print('*'*20)
    print()
    print()

    EncontrarPuntoCercano(puntosNum, puntosX, puntosY, numeroDeRound+1)



if __name__=='__main__':
    puntosNum = []
    puntosX = []
    puntosY = []

    cantidad = int(input('Escriba la cantidad de coordenadas: '))
    
    #Generamos coordenadas aleatorias
    #La variable "puntosNum" contendrá el número(nombre) de la coordenada. Ejemplo Punto#'puntoNum' = 1,2,3 etc
    for i in range(cantidad):
        puntosNum.append(i)
        puntosX.append(random.randint(0, 21))
        puntosY.append(random.randint(0, 21))

    print('PARTICIPANTES!!')
    for i in range(len(puntosX)):
        print(f'Punto #{puntosNum[i]}')
        print(f'Coordenada: {puntosX[i]}, {puntosY[i]}')
    
    print()
    print()

    EncontrarPuntoCercano(puntosNum,puntosX, puntosY, 0)```

Después de muchos días investigando y pensando y revisando el trabajo hecho por otros compañeros, les dejo mi código. Espero que les sirva, lo hice todo en castellano porque me costó entender que había que hacer y ví varios comentarios al respecto. Si tienen alguna duda pregúntenla sin problemas!