Agrupamiento Jerárquico: Algoritmo y Visualización

Clase 18 de 24 • Curso de Introducción al Pensamiento Probabilístico

Contenido del curso

Programación probabilística

Mentiras estadísticas

Introducción a Machine Learning

Agrupamiento

Clasificación

Tomar examen

Resumen

Detrás de los motores de recomendación, las redes sociales y el reconocimiento de voz existen conceptos sorprendentemente accesibles. Uno de ellos es el agrupamiento jerárquico, un algoritmo que construye grupos de datos partiendo de una idea simple: encontrar los puntos más cercanos y unirlos de forma iterativa hasta revelar la estructura oculta en la información.

¿Cómo funciona el agrupamiento jerárquico?

El algoritmo parte de un supuesto directo: cada dato es, inicialmente, un grupo individual [0:12]. A partir de ahí, calcula las distancias entre todos los puntos, identifica la distancia más pequeña y une esos dos puntos en un nuevo clúster. Este proceso se repite de manera iterativa: en cada paso se evalúan las distancias entre los grupos existentes y se fusionan los más cercanos, hasta que finalmente queda un solo grupo [0:30].

Podría parecer que tener un único grupo al final no aporta valor. Sin embargo, lo realmente útil no es el grupo final, sino el objeto que se produce durante el proceso: el dendrograma.

¿Qué es un dendrograma y por qué es importante?

Un dendrograma es una representación gráfica que muestra las relaciones entre cada individuo y entre cada grupo conforme se van construyendo [0:48]. Funciona como un árbol invertido donde cada rama indica qué elementos se unieron y en qué momento del proceso.

Permite visualizar relaciones individuales entre datos.
Muestra cómo los grupos se fusionan paso a paso.
El output principal del algoritmo es esta gráfica, no el grupo completo [1:15].

Gracias al dendrograma, es posible decidir en qué nivel "cortar" el árbol para obtener el número de grupos que mejor represente los datos.

¿Qué métricas de distancia se pueden utilizar?

Dado que el algoritmo se basa en encontrar distancias entre puntos, elegir la métrica adecuada es fundamental [1:30]. Entre las opciones disponibles están:

Distancia euclidiana: la línea recta entre dos puntos en el espacio.
Distancia de Manhattan: suma de las diferencias absolutas en cada dimensión.
Distancia de Minkowski: una generalización que incluye las dos anteriores.

Cada métrica tiene ventajas y desventajas según la naturaleza de los datos, por lo que la elección impacta directamente en los resultados del agrupamiento.

¿Cuáles son los métodos de enlace entre grupos?

Además de la métrica, es necesario definir cómo se mide la distancia entre grupos ya formados. Existen al menos tres métodos principales [1:50]:

Single linkage: toma los puntos más cercanos entre dos grupos. Tiende a generar cadenas alargadas de datos.
Complete linkage: toma los puntos más lejanos entre grupos. Produce clústers más compactos.
Average linkage: calcula el promedio de todos los puntos de cada grupo y mide la distancia entre esas medias. Ofrece un balance entre los dos métodos anteriores.

La combinación de métrica de distancia y método de enlace define el comportamiento completo del algoritmo, lo que hace posible ajustarlo según el problema que se quiera resolver.

¿Cómo practicar el agrupamiento jerárquico con la técnica de Feynman?

Una forma efectiva de consolidar este conocimiento es aplicar la técnica de Feynman [2:28]. El proceso consiste en tres pasos:

Comprender el concepto a nivel teórico.
Generar un programa que implemente el algoritmo desde cero, identificando las dificultades reales.
Revisar implementaciones profesionales en librerías como Scikit-learn para entender cómo personas con amplia experiencia han resuelto esos mismos problemas [2:40].

Este enfoque permite pasar de la comprensión superficial a un dominio real del algoritmo. Al escribir tu propia función de agrupamiento jerárquico, descubrirás los retos de calcular distancias, gestionar la fusión de grupos y construir el dendrograma de forma eficiente.

Si ya pusiste en práctica tu implementación, comparte tu función y cuéntanos qué método de enlace y qué métrica de distancia elegiste.

Omar Larasa

student•

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

!Grafica de 4 puntos

!Grafica de 8 puntos

!Resultado en consola

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

Facundo Nicolás García Martoni

teacher•

- -

JESUS ALBERTO CARREÑO MARTINEZ

johan Stever Rodriguez Molina

William Leonardo Torres Toloza

Iván Godoy

Jhon Freddy Puentes Nuñez

Santiago Manuel Pérez García

Luis Enrique Huamán Quispe

Carlos Vargas

Jonathan Efraín Vera Ruiz

María José Medina

Carlos Fernando Aguilar González

Joaquin Chartier

Julio Cesar Estrada Marcial

Luis Fernando Pedroza Taborda

Alfonso Morán

Delfina Merola Moreschi

Elvis Ojeda Melo

Braulio Alberto Bueno Pabon

Daniel Alejandro Moreno Astorga

William Chamorro

Josue Farley Lopez Carvajal

Eduardo Kiriakos Piazza

Miguel Angel Jimenez Huamani

Gonzalo Ferrando

Alveiro Mejia Lopez

Camilo Quiceno Quintero

Ramón Ruiz

Maria Aurora Molina Vilchis

César Isaac González Naranjo

Fredy Rodriguez

Jose Fernando Jaramillo Boon

Miguel Torres

Diego Fernando Torres Coy

Angel Gerardo Ochoategui Occampo

Roger Carlos Ariel Alba

Jesús Joel Sarabia Félix

Gabriel Missael Barco

Agrupamiento Jerárquico: Algoritmo y Visualización

Programación probabilística

Programación Probabilística: Fundamentos y Aplicaciones Prácticas

Probabilidad Condicional y Eventos Dependientes

Teorema de Bayes: Aplicaciones y Comprensión de Probabilidades

Teorema de Bayes: Intuición y Visualización Práctica

Cálculo de Probabilidad Condicional con Teorema de Bayes y Python

Aplicaciones Modernas del Teorema de Bayes

Mentiras estadísticas

Errores de Datos en Modelos Estadísticos y su Impacto

Detectar Manipulación en Gráficas Estadísticas

Correlación vs Causalidad: Evitando Errores de Razonamiento

Errores Comunes en el Muestreo Estadístico

Identificación y prevención de la falacia del francotirador

Detectar Manipulación de Datos con Porcentajes

Falacia de Regresión a la Media: Concepto y Ejemplos Prácticos

Introducción a Machine Learning

Historia y evolución del Machine Learning

Vectores Numéricos para Modelado en Machine Learning

Métricas de Distancia en Algoritmos de Machine Learning

Agrupamiento

Algoritmos de Agrupamiento: Clasificación y Aplicaciones Prácticas

Agrupamiento Jerárquico: Algoritmo y Visualización

Algoritmo K-means: Conceptos y Aplicación Práctica

Técnicas de Agrupamiento en Machine Learning

Clasificación

Técnicas de Clasificación en Aprendizaje Supervisado

Clasificación de Datos con Algoritmo K-Nearest Neighbors

Algoritmos de Clasificación en Machine Learning

Pensamiento Computacional: Fundamentos y Aplicaciones Prácticas