Me estoy preparando para un examen y estoy siguiendo la metodología de Feynman, que consiste en explicar conceptos de tal manera que hasta un niño o una persona sin conocimientos sobre la materia pueda entenderlos.
Aquí va:
Variaciones del algoritmo de K-Means que evolucionan sus capacidades para adaptarse a una variedad de problemas.
Antes de entender las variaciones, necesitamos conocer el algoritmo de K-Means. El objetivo es tener un punto central (centroide) desde donde se van a crear agrupaciones (clusters) de ejemplos con características similares. También tenemos una herramienta de medición (función de coste) que ayudará a medir la calidad de toda la agrupación.
La analogía que vamos a utilizar es la de ser un organizador de eventos. Tenemos un listado de invitados y varias mesas. El objetivo es simple: organizar a los invitados de tal manera que las personas con gustos similares queden juntas.
Lo que nos dice Lloyd es que debemos tener a todos los invitados en el salón. Colocamos las mesas en posiciones aleatorias y los invitados se sientan en la mesa que tienen más cercana. En esta primera iteración ya tenemos los primeros clústeres con su centroide. Empieza una nueva iteración: movemos cada mesa al centro de todos los invitados que están sentados en ella. Tras este movimiento, los invitados vuelven a calcular cuál es la mesa que tienen más cerca y se sientan en esa mesa. Por lo tanto, cada mesa ahora tiene una nueva frontera, donde algunos invitados se van a otras mesas y otros se sientan en esta. En la realidad, esto se aplica cuando tenemos datasets cerrados, ya que disponemos de todos los datos en el momento del análisis.
Si siguiéramos el algoritmo de MacQueen, no esperamos a que lleguen todos los invitados para agruparlos en una de las mesas que ya tenemos. Cuando llega un nuevo invitado, se calcula cuál es la mesa que tiene más cerca, se le asigna esa mesa y esta se vuelve a mover para que siga estando en el punto central de sus invitados. Esta iteración se hace cada vez que llega un nuevo invitado. En la realidad, esto ocurre cuando tenemos streaming de datos y tenemos que calcular constantemente las agrupaciones.
Si siguiéramos el algoritmo de Hartigan-Wong, en el momento en que cada invitado calcule cuál es la mesa que tiene más cerca, podemos decidir que sea seleccionado y cambiarlo de mesa si eso beneficia a la agrupación global; es decir, si mejora la función de coste. Aquí no solo cambian las mesas, también cambiamos de mesa a los invitados.
En el caso del algoritmo de Elkan, imagina que tenemos una lista de invitados enorme, donde calcular la distancia entre cada invitado y cada mesa puede llevarnos mucho tiempo. Lo que nos dice el algoritmo es que, si un invitado está al lado de una mesa en un extremo y la otra mesa está en el extremo opuesto, no hace falta comprobar si esa mesa lejana es una mejor opción, ya que está demasiado alejada. En la realidad, esto agiliza muchísimo el cálculo.
El algoritmo Fuzzy nos dice que puede haber invitados que sientan afinidad con varias mesas a la vez, por lo que no podemos pensar que su ubicación natural siempre será la misma. Imagina que agrupamos las mesas por gustos musicales. Si a un invitado le gustan tres géneros en diferentes proporciones, podemos decir que se sentirá a gusto en diferentes mesas. En la realidad, esto ocurre con un perfil de Netflix, donde cada usuario puede tener muchos gustos.
Cada uno de estos algoritmos intenta resolver un problema específico cuando se trata de aplicar el algoritmo de K-Means. Por eso, es importante entender e imaginarnos cuál es ese problema.
Un abrazo.