Resumen de New strategies for global optimum search in variance-based k-clustering
Francisco Javier Soto Sánchez
La partición de un conjunto de datos en subconjuntos distintos, o ``clusters'', es una técnica fundamental en minería de datos para agrupar datos similares. Un enfoque común es definir el clustering como un problema de optimización, donde una función objetivo mide la adecuación de la agrupación a los datos. Una opción estándar para esta función es la suma de las dispersiones de los grupos, calculadas como la suma de las distancias de todos los miembros del grupo respecto al centro de masas.
Encontrar la partición óptima global en k clusters con esta función objetivo es un problema difícil, reconocido como «NP-duro», incluso para el caso en que k = 2 y cuando la dimensión es un parámetro y puede crecer. Esto ha motivado la propuesta de algoritmos heurísticos, que frecuentemente producen buenos candidatos, aunque no garantizan una solución óptima. De hecho, asegurar que la solución esté cerca del óptimo global se considera como problema abierto, incluso para conjuntos de datos pequeños. Este reto motiva el desarrollo de algoritmos que encuentren explícitamente la solución óptima global, tema central de esta tesis. Entre las aplicaciones de estos algoritmos está medir la eficacia de los algoritmos heurísticos.
En este trabajo, proponemos nuevas estrategias para encontrar la solución óptima global, basándonos y mejorando las propuestas del campo. Tras el análisis realizado, reportamos mejoras en la complejidad, tanto en las cotas teóricas como en las simulaciones computacionales realizadas. La estrategia reduce el espacio de soluciones mediante una enumeración cuidadosa de los posibles candidatos y un método de ramificación y poda adaptado.
Además, estudiamos los beneficios de la aleatoriedad en la reducción de la dimensionalidad o estrategias de inicialización, para acelerar la convergencia de los algoritmos de clustering con la propuesta de varios algoritmos y su posterior simulación computacional.
Esta tesis también explora nuevas construcciones algebraicas para la generación eficiente de secuencias de números con buenas propiedades estadísticas y ofrece nuevas ideas sobre la selección de parámetros para estos generadores, lo que resulta útil en aplicaciones prácticas.
