🤖 machine learning

Local Cluster Cardinality Estimation for Adaptive Mean Shift

Este artículo presenta un algoritmo de desplazamiento de media (mean shift) totalmente adaptativo y con invarianza de escala que determina automáticamente el ancho de banda local y los umbrales del núcleo para cada punto mediante la estimación de la cardinalidad de los clústeres locales a través del análisis de la distribución de distancias, logrando un rendimiento de agrupamiento competitivo sin requerir conocimiento previo del número de clústeres o de los parámetros de escala globales.

Autores originales: Étienne Pepin

Publicado 2026-08-13

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Étienne Pepin

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás en un festival de música masivo y caótico. Quieres encontrar a tus amigos, pero la multitud es una mezcla turbulenta de miles de personas: algunas están en grupos pequeños y apretados, otras deambulan solas, y algunos grupos son tan enormes que se extienden por todo el campo. En el mundo de la ciencia de datos, este es el problema del agrupamiento (clustering): intentar clasificar una pila desordenada de información en grupos limpios y significativos sin un mapa. Por lo general, los ordenadores necesitan que un humano les diga: "Oye, hay exactamente cinco grupos aquí" o "Usa un radio de búsqueda de cinco metros". Pero, ¿qué pasaría si el ordenador pudiera simplemente mirar a la multitud, identificar los grupos por su cuenta y darse cuenta de que un grupo es diminuto y compacto mientras que otro es masivo y disperso? Ese es el sueño del agrupamiento adaptativo: un método que no necesita una regla rígida, sino que utiliza sus propios ojos para medir la distancia entre los vecinos.

Este artículo presenta una nueva y astuta forma de lograr exactamente eso. Propone un método llamado Desplazamiento de Media Adaptativo (Adaptive Mean Shift), que es como un imán inteligente que atrae los puntos hacia sus grupos naturales. El ingrediente secreto aquí es un nuevo truco para determinar cuántas personas hay en un grupo específico simplemente observando qué tan lejos están unas de otras. En lugar de adivinar un tamaño fijo para el área de búsqueda, el algoritmo observa la "distribución de distancias" —una lista de qué tan lejos está un punto de todos los demás— y encuentra un "hueco" o caída natural en esa lista. Ese hueco le dice al ordenador: "Bien, todos los que estén más cerca de este hueco pertenecen a mi grupo; todos los que estén más lejos son un extraño". Esto permite que el ordenador ajuste su radio de búsqueda sobre la marcha para cada punto, lo que lo hace invariante a la escala (funciona ya sea que los datos se midan en pulgadas o en años luz) y local (solo le importa el vecindario inmediato).

La historia del imán que se mide a sí mismo

Conoce al algoritmo de Desplazamiento de Media Adaptativo. Imagina a un grupo de excursionistas tratando de encontrar el centro de su campamento. En los viejos tiempos, a cada excursionista se le decía: "Mira a todos dentro de 10 pies de ti y camina hacia el punto promedio". Esto funcionaba bien si todos estaban parados en un círculo perfecto, pero ¿qué pasa si un grupo está amontonado en un círculo apretado y otro está disperso en un campo de fútbol? La regla de los 10 pies o bien perdería al grupo disperso o accidentalmente atraería a personas del campamento equiv〯o.

Este artículo presenta a un excursionista más inteligente. En lugar de recibir una regla fija de 10 pies, este excursionista se hace una pregunta simple: "¿A qué distancia están mis vecinos?". Crea una lista de distancias a cada otra persona en la multitud. Si estás en un grupo apretado, tu lista mostrará muchas distancias cortas, y luego, de repente, un gran salto hacia el siguiente grupo. El truco mágico del artículo es encontrar ese salto.

El autor utiliza una herramienta matemática especial llamada función $\gamma$ (función gamma) para escanear esta lista de distancias. Imagina la lista de distancias como un camino accidentado. La función $\gamma$ es como un sismógrafo sensible que busca el valle más profundo entre dos colinas. La primera colina representa a las personas de tu propio grupo (vecinos cercanos) y la segunda colina representa a las personas de otros grupos (vecinos distantes). El valle entre ellas es el lugar perfecto para trazar una línea.

Una vez que el algoritmo encuentra este valle, sabe exactamente cuántas personas hay en el grupo local (la cardinalidad) y qué tanto se extiende el grupo (el radio). Luego utiliza esta información específica para establecer su propio "radio de búsqueda" y su "fuerza de atracción" solo para ese lugar. Es como un camaleón cambiando su color para coincidir exactamente con el entorno en el que se encuentra.

Por qué esto importa: No más adivinar el número de grupos

El mayor dolor de cabeza en el agrupamiento es usualmente saber cuántos grupos existen. La mayoría de los algoritmos necesitan que digas: "Busca 3 grupos" o "Busca 10". Si adivinas mal, todo el proceso se desmorona. Este nuevo método no necesita ese número. Determina los grupos buscando los huecos naturales en los datos de distancia.

El autor probó esta idea primero en un "conjunto de datos de juguete" —un mundo inventado con cuatro grupos de diferentes tamaños y distribuciones. El algoritmo encontró con éxito los cuatro, a pesar de que uno era diminuto y otro era enorme. Se dio cuenta de que el grupo pequeño necesitaba un radio de búsqueda pequeño, mientras que el grupo grande necesitaba uno grande, todo esto sin que se le dijera cuántos grupos había.

Cuando el autor comparó su método con otras técnicas de agrupamiento inteligentes (específicamente un método llamado WAMS por Ren et al. de 2014), los resultados fueron prometedores. En siete de nueve conjuntos de datos del mundo real (como imágenes de letras escritas a mano o datos biológicos), su nuevo método encontró mejores agrupaciones que la competencia. No solo ganó; a menudo ganó por un margen claro, obteniendo un "Índice de Rand" (una puntuación de qué tan bien coinciden los grupos con la verdad) de 0.9575 en el conjunto de datos Iris, frente al 0.9495 del otro método. En algunos conjuntos de datos, la diferencia fue pequeña (menos de 0.012), pero en otros, fue significativa.

Las reglas del juego

El artículo señala cuidadosamente lo que este método no hace. No es una varita mágica que resuelve todos los problemas instantáneamente.

No es perfecto para grupos enormes: El algoritmo tiene una regla que dice: "No buscaremos un grupo que sea más grande que la mitad de los datos totales". Si un conjunto de datos tiene un grupo gigante que constituye el 60% de todo, este método podría confundirse y dividir ese grupo gigante en piezas. El autor admite que esto es una limitación y sugiere que la regla del "límite máximo" necesita ser más inteligente en el futuro.
No es un avance probado para todo: Aunque supera a la competencia en las pruebas específicas que realizaron, el autor señala que solo lo compararon con otro método adaptativo. Sugieren que se necesitan más pruebas contra métodos más nuevos.
Es un prototipo: El autor describe esto como un "primer prototipo funcional". Ven espacio para la mejora, como usar diferentes formas de encontrar el "valle" en la lista de distancias o probar cómo maneja los datos de muy alta dimensión (datos con cientos de características).

La conclusión

Al final, este artículo ofrece una perspectiva fresca sobre cómo los ordenadores pueden organizar datos desordenados. En lugar de imponer una regla rígida sobre una multitud flexible, le enseña al ordenador a sentir el pulso de la multitud. Al medir la distancia entre los vecinos y encontrar los huecos naturales, el algoritmo puede adaptarse a grupos de cualquier tamaño o forma, desde un grupo apretado de amigos hasta una multitud dispersa en un festival. No necesita saber la respuesta antes de empezar; solo necesita mirar las distancias y dejar que los datos cuenten la historia. Aunque todavía tiene algunos bordes rugosos y supuestos que refinar, demuestra que con las mediciones locales adecuadas, un ordenador puede aprender a encontrar su propio camino a través del ruido.

Resumen Técnico: Estimación de la Cardinalidad de Clústeres Locales para el Desplazamiento de Media Adaptativo

Planteamiento del Problema

El artículo aborda el desafío de la selección de parámetros en el agrupamiento por Desplazamiento de Media Adaptativo (AMS, por sus siglas en inglés). Los algoritmos de AMS tradicionales dependen de un parámetro de ancho de banda para definir el vecindario local para calcular las medias ponderadas. Mientras que el AMS básico utiliza un ancho de banda global fijo, las variantes adaptativas intentan ajustar este parámetro localmente, apoyándose frecuentemente en la estimación de la densidad local (por ejemplo, la Estimación de Densidad de Kernel o KDE).

El autor identifica dos limitaciones principales en los enfoques existentes:

Dependencia de la Escala: Muchos métodos requieren una constante de longitud (ancho de banda) elegida para el conjunto de datos en su totalidad, lo que los hace sensibles a la escala de los datos.
Localidad y Ruido: El KDE estándar mide la densidad en un vecindario de tamaño fijo. Si este vecindario es demasiado grande, incluye puntos de clústeres distantes, perturbando la estimación local. Si es demasiado pequeño, puede perder la estructura del clúster. Además, el KDE requiere un parámetro de ancho de banda que no es trivial de elegir, especialmente para clústeres pequeños o datos de alta dimensión donde puede ocurrir un suavizado excesivo (oversmoothing).

El artículo propone un método para estimar la cardinalidad (número de puntos) de un clúster local directamente a partir de la distribución de distancias de un punto a sus vecinos. Esta cardinalidad estimada se utiliza luego para derivar el ancho de banda y el radio del kernel para el proceso de desplazamiento de media, eliminando la necesidad de un ancho de banda global predefinido o un número fijo de clústeres.

Metodología

El algoritmo propuesto opera en tres etapas principales: Estimación de la Cardinalidad del Clúster, Desplazamiento de Media Adaptativo y Clasificación de Valores Atípicos.

1. Estimación de la Cardinalidad del Clúster Local

La innovación central es la estimación de la cardinalidad del clúster local ( $\hat{n}$ ) utilizando la distribución de distancias de un punto $x_i$ a todos los demás puntos.

Distribución de Distancias: Para cada punto, las distancias a todos los demás puntos se ordenan. El autor hipotetiza que en un conjunto de datos multimodal, esta distribución es bimodal: el primer modo representa las distancias a los puntos dentro del mismo clúster local, y el segundo modo representa las distancias a los puntos en otros clústeres.
La Función $\gamma$ : Para localizar el límite entre estos dos modos (el "valle" de densidad mínima), el artículo introduce una función $\gamma$ :
$\gamma(y^{(k)}) = \frac{s^2}{(\bar{y} - y^{(k)})^2}$
donde $y^{(k)}$ es la $k$ -ésima distancia ordenada, $\bar{y}$ es la media de las primeras $k$ distancias, y $s^2$ es su varianza.
Lógica de Estimación: El algoritmo busca el rango $k$ que minimiza $\gamma$ dentro de una ventana de búsqueda ($minBoundary $a$ maxBoundary$). Este mínimo corresponde a la cardinalidad de clúster estimada $\hat{n}_i$ .
Propiedades Clave:
- Invarianza de Escala: La función $\gamma$ es una razón entre la varianza y la distancia al cuadrado. Multiplicar los datos por una constante positiva deja $\gamma$ sin cambios, lo que significa que no se requiere una constante de escala de longitud.
- Localidad: El valor de $\gamma$ en el rango $k$ depende únicamente de las $k$ distancias más cercanas. Los puntos más alejados no influyen en la estimación del límite del clúster local.

2. Desplazamiento de Media Adaptativo

Una vez que se estima $\hat{n}_i$ para cada punto, estos valores dirigen el proceso de desplazamiento de media:

Definición del Kernel: Se utiliza un kernel gaussiano truncado $K(x; h, \omega)$ $K (x; h, ω)$ .
- Ancho de Banda ( $h$ ): Calculado como la desviación estándar de la distribución de distancia local restringida a la cardinalidad estimada $\hat{n}_i$ .
- Umbral ( $\omega$ ): Establecido como la $\hat{n}_i$ -ésima distancia ordenada, lo que efectivamente trunca el kernel en el radio del clúster estimado. Los puntos más allá de este radio reciben un peso de cero.
Adaptación de Alta Dimensión: Se propone un kernel modificado (Ec. 6) para altas dimensiones con el fin de compensar las distancias, evitando que la autodistancia (cero) domine el peso y evitando la inestabilidad numérica.
Incremento Gradual del Área: Para mitigar el sesgo positivo en las estimaciones de cardinalidad para puntos cerca de los límites de los clústeres, el algoritmo aumenta gradualmente el número de puntos considerados ( $n_k^*$ ) durante los pasos iterativos del desplazamiento de media, permitiendo que la media ponderada converja hacia el modo real.

3. Manejo de Estimaciones "Malas"

Los puntos donde la estimación de la cardinalidad alcanza los límites de búsqueda (por ejemplo, puntos entre clústeres donde la distribución es ambigua) se etiquetan como "malos". Estos puntos se excluyen del desplazamiento de media iterativo. En el paso final, se asignan al modo de clúster más cercano, ponderados por el ancho de banda de dicho clúster.

Principales Contribuciones

Parametrización Basada en la Cardinalidad: El artículo introduce un método para derivar el ancho de banda y el radio del kernel para el AMS directamente de la cardinalidad de clúster estimada, eliminando la necesidad de un parámetro de ancho de banda global.
La Función $\gamma$ : Una función novedosa, invariante de escala y local para detectar el mínimo de densidad entre dos modos en una distribución de distancias, evitando los problemas de selección de ancho de banda inherentes al KDE.
Independencia de Escala y de Clúster: El algoritmo no requiere el número de clústeres como entrada y es invariante a la escala de los datos.
Estrategia de Kernel Truncado: Al truncar el kernel en el radio del clúster estimado, el método asegura que los puntos distantes (de otros clústeres) no contaminen la media ponderada local.

Resultados Experimentales

El autor evaluó el algoritmo en dos conjuntos de pruebas de referencia:

Comparación con WAMS de Ren et al. (2014):
- Probado en 9 conjuntos de datos (Iris, Yeast, Steel, USPS, CTG, Letter, Image, Pen, Wave).
- El método propuesto logró un Índice de Rand superior al algoritmo de Desplazamiento de Media Adaptativo Ponderado (WAMS) en 7 de los 9 conjuntos de datos.
- Superó a todas las líneas base publicadas (WAMS, k-means, EM, Single-linkage) en estos 7 conjuntos de datos.
- Su rendimiento fue competitivo en los dos conjuntos restantes (USPS, Image), aunque el autor señala que no pudo acceder a los detalles de implementación específicos de esas líneas base para investigar completamente la discrepancia.
Comparación con el Benchmark de Gagolewski (2022):
- Probado en 8 conjuntos de datos de la UCI (Ecoli, Glass, Ionosphere, Sonar, Statlog, WDBC, Wine, Yeast).
- El algoritmo funcionó de manera competitiva frente a métodos establecidos (GIc, EM, k-means, Spectral, Birch) en conjuntos de datos donde el Índice de Rand separaba claramente los métodos.
- Limitación: El algoritmo tiene dificultades cuando el clúster más grande contiene más del 50% de los datos (el maxBoundary por defecto es $0.5n$ ). En tales casos (por ejemplo, Ionosphere, Sonar, WDBC), el algoritmo falla al representar la clase mayoritaria como un solo clúster, lo que resulta en índices de Rand más bajos. El autor señala que ajustar el parámetro maxBoundary puede mejorar los resultados en estos conjuntos de datos específicos, pero requiere conocimiento de la distribución de los datos.

Significado y Reivindicaciones

El artículo afirma que el algoritmo propuesto es competitivo dentro de la familia del desplazamiento de media adaptativo y ofrece una ventaja distintiva al no requerir el número de clústeres como entrada.

Modestia: El autor reconoce que el estimador de cardinalidad es un "primer prototipo funcional" y un "trabajo en progreso". Admite que la comparación contra el algoritmo WAMS cubre solo un miembro de la familia del desplazamiento de media adaptativo y que se necesitan comparaciones más amplias.
Invarianza de Escala: El autor enfatiza que la invariancia de escala de su estimador es una mejora teórica significativa, ya que elimina la necesidad de elegir una constante de longitud para la escala de los datos.
Localidad: Se destaca la estricta localidad del método, asegurando que la estimación de un clúster local no sea perturbada por puntos de datos distantes.
Trabajo Futuro: El artículo sugiere que la tarea de estimación de la cardinalidad en sí misma es novedosa y merece más investigación. Las mejoras futuras podrían incluir el reemplazo de los límites fijos por la búsqueda de modos algorítmicos (por ejemplo, desplazamiento de media en 1D) y el refinamiento del manejo del parámetro maxBoundary para hacerlo totalmente basado en los datos.

En conclusión, el artículo presenta un enfoque novedoso para el desplazamiento de media adaptativo que aprovecha las distribuciones de distancia para determinar automáticamente los parámetros locales de los clústeres, demostrando un sólido rendimiento empírico en pruebas estándar mientras mantiene propiedades teóricas de invariancia de escala y localidad.