E189 - K-Means y DBSCAN from scratch

Resumen

El episodio 189 de enCoders es el segundo de la serie "from scratch": se implementan desde cero K-Means y DBSCAN, dos algoritmos clásicos de clusterización (aprendizaje no supervisado). Matías explica la intuición y programa K-Means (centroides, distancia euclidiana, asignación, actualización, SSE y convergencia), y muestra que puede caer en mínimos locales según la semilla, por lo que conviene probar varias inicializaciones (`n_init` en scikit-learn). Se discute cómo elegir K (método del codo, silueta y, sobre todo, el sentido para el negocio) y las limitaciones de K-Means: clusters no convexos y sensibilidad a outliers. Luego se presenta DBSCAN, basado en densidad con dos parámetros (radio épsilon y `min_samples`), que distingue puntos core, border y ruido, maneja formas curvas y detecta outliers, aunque es sensible a la calibración de sus parámetros y a "puentes" entre grupos. La conclusión general es que programar los algoritmos a mano ayuda a entender sus parámetros y defectos, y que se debe mantener el pensamiento crítico al usar LLMs.

Capítulos

• 00:00
  Bienvenida y objetivoPresentación del episodio 189 sobre K-Means y DBSCAN, segundo de la serie from scratch. Se menciona que el tema ya se vio de forma más intuitiva en el episodio 102 (sobre métodos de clustering).
• 01:35
  Formato from scratchTodo el material es código implementado desde cero. Matías usa un archivo `.py` con celdas (marcadores `# %%`) como alternativa a un notebook, a modo de broma para Rob.
• 02:58
  Base matemática necesariaPara estos dos algoritmos basta con promedios y distancias, sin matemática avanzada. Se menciona UMAP como algoritmo de reducción de dimensionalidad, más sofisticado, para un episodio futuro.
• 05:15
  Datos sintéticos y escaladoUso de `make_blobs` y `make_moons` de scikit-learn para generar datos, con `StandardScaler` porque las distancias son sensibles a la escala de las variables.
• 07:01
  Qué es clusteringClustering es aprendizaje no supervisado, sin etiquetas. Ejemplo real: perfilar clientes por su comportamiento de compra (por ejemplo "comprador de ocasión") para definir acciones sobre cada grupo.
• 10:00
  Centroides e intuiciónEl centroide es el promedio de los puntos de un grupo, análogo al centro de masa. K-Means asigna cada punto al centroide más cercano.
• 13:48
  Distancia euclidianaSe define la distancia euclidiana (Pitágoras, norma 2) con un ejemplo 3-4-5. Se menciona que existen otras normas P, con cambios de comportamiento según la métrica.
• 17:35
  Función de distanciasSe programa la función que calcula la distancia de cada punto a cada centroide, devolviendo una distancia por centroide.
• 20:26
  Pasos de K-meansCiclo del algoritmo: inicializar centroides, asignar cada punto al más cercano, recalcular centroides y repetir. K es un parámetro que debe fijarse de antemano.
• 21:56
  Elegir K y codoK se debe elegir a priori; se anticipa la regla del codo. Rodolfo aclara la diferencia: K es un hiperparámetro y las coordenadas de los centroides son parámetros que el modelo aprende.
• 24:21
  Inicialización aleatoriaLos centroides iniciales se eligen al azar entre los puntos del dataset (`choice` sin reemplazo, con `random_state`). Una mala inicialización puede llevar a otra solución.
• 26:07
  Asignación de clustersSe usa `argmin` sobre las distancias para obtener los labels. Se visualiza cómo los puntos se asignan al centroide más cercano.
• 28:32
  Actualizar centroidesSe recalcula cada centroide como el promedio de los puntos de su cluster; se visualiza el movimiento de los centroides.
• 29:45
  Objetivo y formulaciónFormulación matemática: encontrar una partición en K grupos que minimice la suma de distancias a los centroides. Se explica el concepto de partición y la función `update_centroids`, que conserva el centroide anterior si un cluster queda vacío.
• 34:27
  SSE y convergenciaEl SSE (suma de errores al cuadrado) baja tras cada actualización. El algoritmo termina porque el error es monótono decreciente, está acotado por cero y hay un número finito de particiones; en la práctica se usan `max_iter` y tolerancia.
• 39:59
  Implementando Fit de K-MeansSe define la clase con `max_iter`, `tol` y `random_state`, que guarda centroides, labels, historia del SSE e historia de centroides. El método `fit` inicializa los centroides y luego itera.
• 40:52
  Asignación y actualización iterativaCada iteración asigna labels, calcula el SSE, actualiza centroides y corta si el movimiento es menor a la tolerancia. `predict` asigna nuevos puntos a los centroides ya aprendidos.
• 42:33
  Resultados y convergencia del errorCon K=4 y `random_state` 3, el algoritmo converge en 9 iteraciones con SSE de ~75, pero a una solución mala: un cluster unido y otro partido en dos.
• 43:01
  Mínimos locales y múltiples semillasK-Means converge, pero no necesariamente al óptimo global. La solución es probar varias semillas y quedarse con la de menor SSE; con seis semillas, tres dieron la solución buena.
• 44:40
  Comparación con Scikit-LearnScikit-learn llega a la solución correcta con SSE ~24 en pocas líneas. Rodolfo destaca el parámetro `n_init`, que repite las inicializaciones.
• 47:07
  Elegir K con método del codoSe grafica el SSE para distintos K (≈600 con K=1, ≈300 con K=2, ≈80 con K=3, ≈20 con K=4). Hay debate entre el codo en 3 o en 4: es una heurística y depende del rango graficado y del negocio.
• 50:12
  Limitaciones K-Means y outliersCon datos en forma de lunas falla porque sus fronteras son líneas (diagrama de Voronoi). Los outliers distorsionan los centroides porque se usa la media y todo punto debe asignarse a algún cluster.
• 53:52
  Cierre K-Means y salto a DBSCANResumen: K-Means es relativamente fácil de implementar y existen variantes (otras distancias, medianas). Pasan a los memes y luego a DBSCAN.
• 54:41
  MemesMemes sobre prompts del tipo "no cometas errores", sobre pasar de junior a senior diciendo "depende", y sobre el diagrama de Voronoi hecho con humanos. Se comenta la experiencia real de usar K-Means en perfiles de clientes (retail, RFM), que requiere mucha iteración, criterio de negocio y la silueta como alternativa al codo; las variables usadas incluyeron volumen y frecuencia de compra y tipo de producto.
• 01:04:57
  Feedback de CV y update de trabajosFeedback a un currículum: evitar verbos como "ayudé", usar verbos de acción y enfocarse en el impacto. Matías cuenta que corrigió un chatbot de soporte para técnicos en producción, con un flujo de videos tipo N8N.
• 01:10:48
  Introducción a DBSCAN y densidadDBSCAN se basa en densidad. Se hace una digresión sobre el conjunto de Cantor y la noción matemática de "denso", y se explica que alrededor de un punto se dibuja una bola y se cuentan vecinos.
• 01:15:29
  Parámetro epsilon y vecinosÉpsilon es el radio de vecindad; dos puntos son vecinos si su distancia es menor que épsilon. Se menciona que DBSCAN significa Density-Based Spatial Clustering of Applications with Noise.
• 01:18:43
  Normas y vecindadesSe programa `region_query`, que devuelve los vecinos dentro del radio. Con norma 2 la bola es un círculo; con norma 1 es un rombo y con norma infinito un cuadrado.
• 01:20:16
  Core border y ruidoUn punto es core si tiene al menos `min_samples` vecinos en su radio, border si no lo es pero está cerca de un core, y ruido si no cumple ninguna de las dos condiciones.
• 01:23:35
  Intuición de expansiónEl algoritmo parte de un punto, dibuja la bola y, si los vecinos también son densos, los encadena y expande el cluster hasta que no hay más vecinos.
• 01:25:17
  Programando expand clusterFunción `expand_cluster` con radio y `min_samples`, que modifica los labels in place. Usa una lista de puntos por visitar y reclasifica como border los puntos antes marcados como ruido.
• 01:34:05
  DBSCAN completoEl `fit` recorre todos los puntos y expande un cluster nuevo con cada punto sin visitar. Termina siempre, porque es un proceso finito, y no minimiza ninguna función. En scikit-learn se reduce a dos líneas.
• 01:37:48
  Parámetros y fallasUn épsilon muy pequeño fragmenta en muchos clusters y uno muy grande los une en uno solo. Los puentes de puntos entre dos grupos pueden fusionarlos, y un `min_samples` bajo forma clusters muy pequeños mientras que uno alto genera más ruido.
• 01:41:18
  Outliers y ejemplosDBSCAN deja los outliers como ruido en lugar de asignarlos a un cluster. Se muestra un ejemplo con tres nubes bien separadas y puntos aislados marcados como ruido.
• 01:43:46
  Usos y extensionesMatías usó DBSCAN con puntos geoespaciales (nubes de puntos de un mapa). Se menciona HDBSCAN como versión jerárquica para otro episodio.
• 01:45:21
  Aprender haciendoProgramar los algoritmos enseña más que leer o ver videos. Cris recomienda profundizar en una técnica cuando se aplica a un proyecto real; se destaca el valor de las visualizaciones al cambiar parámetros, y que los LLM facilitan crear dashboards interactivos.
• 01:49:29
  Curiosidad y pensamiento críticoImportancia de formular uno mismo las preguntas y no delegarlas al LLM. Cintia comenta que mucha gente aplica modelos sin revisar supuestos (por ejemplo, un outlier en K-Means).
• 01:50:22
  Cantor y cierreDigresión sobre el conjunto de Cantor y el contenido corto en TikTok; despedida y avance de próximos temas (algoritmos y estructuras de datos o agentes).

Palabras clave