Adaptive Quantum Optimized Centroid Initialization

1. Planteamiento del Problema

Los algoritmos de clustering basados en prototipos, como k-means, son altamente sensibles a la selección de los centroides iniciales. Una mala inicialización puede conducir a una convergencia lenta, soluciones subóptimas atrapadas en mínimos locales y una alta variabilidad en los resultados.

• Limitaciones actuales: El método estándar de inicialización, k-means++, aunque ofrece garantías de aproximación $O(\log k)$, es un algoritmo heurístico secuencial y greedy (codicioso) que puede fallar en datos con estructuras complejas o clusters superpuestos.
• Antecedentes: Un trabajo previo de los autores, QOCI (Quantum Optimized Centroid Initialization), formuló el problema como un problema de Optimización Binaria Cuadrática sin Restricciones (QUBO) resoluble mediante recocido cuántico. Sin embargo, QOCI tenía limitaciones severas: solo permitía centroides de valores enteros, no escalaba bien a tamaños de muestra grandes y requería un ajuste manual de parámetros de penalización.

2. Metodología: AQOCI

El artículo presenta AQOCI (Adaptive Quantum Optimized Centroid Initialization), una evolución de QOCI que aborda sus limitaciones mediante un mecanismo de refinamiento iterativo adaptativo.

• Formulación QUBO: El problema se formula basándose en la factorización de matrices $V \approx WH$, donde $V$ es la matriz de datos, $W$ codifica las coordenadas de los centroides y $H$ es una matriz de asignación binaria. El objetivo es minimizar $\|V - WH\|^2$.
• Codificación Binaria Adaptativa:
  • A diferencia de QOCI, AQOCI introduce parámetros de escala ($\lambda$) y desplazamiento (offset).
  • Utiliza una codificación binaria (complemento a dos) para representar coordenadas de centroides de valores reales.
  • Mecanismo de Refinamiento: Inspirado en los métodos de Gauss-Seidel y Jacobi, el algoritmo no resuelve el QUBO completo en un solo paso. En su lugar, descompone el problema en una secuencia de instancias QUBO más pequeñas.
  • En cada iteración, el solver devuelve una cadena binaria que se interpreta como un valor real. Los parámetros de escala y desplazamiento se actualizan para estrechar la ventana de búsqueda alrededor de la solución actual, aumentando progresivamente la precisión.
• Backends de Solución: El método es agnóstico al solver. Los autores evaluaron tres motores:
  1. Búsqueda TABU (clásica).
  2. Recocido Simulado (clásico).
  3. Solucionador Híbrido BQM de D-Wave (cuántico/clásico).

3. Contribuciones Clave

1. Recuperación de Valores Reales: La introducción de escalado y desplazamiento adaptativos permite recuperar coordenadas de centroides de punto flotante a partir de salidas binarias discretas, superando la restricción de valores enteros de QOCI.
2. Descomposición Iterativa: Permite manejar problemas más grandes al dividir la optimización en bloques manejables dentro de las restricciones de tiempo de las plataformas de recocido cuántico.
3. Evaluación Rigurosa: Comparación exhaustiva contra inicialización aleatoria y k-means++ en datos sintéticos (con variaciones controladas de separación, número de clusters, dimensionalidad y tamaño de muestra) y en el conjunto de datos real MOTIF (clasificación de malware).

4. Resultados Experimentales

A. Datos Sintéticos (Gaussianos)

• Superposición de Clusters: En datos con clusters fuertemente superpuestos, AQOCI (específicamente con Recocido Simulado) supera a k-means++ y a la inicialización aleatoria (mejora de V-measure de 0.350 vs 0.329). Esto valida la hipótesis de que la optimización global del QUBO es superior cuando los límites de los clusters son ambiguos.
• Clusters Bien Separados: En datos con clusters bien separados, k-means++ domina claramente. AQOCI se estanca en un plateau de rendimiento (V-measure $\approx$ 0.648).
  • Causa: Esta limitación se atribuye a la resolución de la codificación binaria (3 bits por variable, lo que crea solo 7 intervalos representables). Cuando el rango de datos es grande en comparación con la distancia entre clusters, la precisión no es suficiente para distinguirlos, independientemente del número de iteraciones.
• Escalabilidad:
  • Dimensionalidad: El método escala hasta al menos $d=10$ sin degradación inherente (AQOCI-SimAnn logra V-measure perfecto de 1.0 en $d=10$).
  • Tamaño de Muestra: En tamaños pequeños ($n=50$), AQOCI puede igualar o superar a k-means++. A medida que $n$ aumenta, ambos convergen al mismo plateau limitado por la resolución de bits.

B. Datos Reales (MOTIF - Malware)

• En el conjunto de datos MOTIF (que tiene estructura compleja y no gaussiana tras la reducción de PCA), AQOCI demuestra un rendimiento superior, especialmente en tamaños de muestra pequeños.
• Mejoras Significativas: AQOCI-TABU logró mejoras de hasta un 26% en V-measure sobre k-means++ en $n=45$.
• Completitud: Los centroides derivados de AQOCI tienden a lograr una "completitud" muy alta (agrupar todos los miembros de una clase real en un solo cluster), aunque a veces a costa de la homogeneidad (fusionar clases distintas), lo que sugiere que captura la estructura global del datos mejor que los métodos greedy.

5. Discusión y Limitaciones

• Dependencia de la Estructura de Datos: La ventaja de AQOCI es condicional. Es superior en datos complejos/overlap y pequeños; k-means++ es superior en datos bien separados.
• Limitación de Resolución: El uso de 3 bits por variable es el cuello de botella principal en datos con rangos amplios. Aumentar los bits mejoraría la precisión pero incrementaría exponencialmente el tamaño de la matriz QUBO.
• Sensibilidad a Parámetros: Los parámetros de penalización ($\delta_1, \delta_2$) no escalan bien con el tamaño del problema, lo que lleva a violaciones de restricciones en matrices $H$ grandes.
• Convergencia No Monótona: El criterio de parada actual es un número fijo de iteraciones porque la norma L2 del residuo oscila, lo que indica que el paisaje energético del QUBO contiene mínimos locales que los solvers atraviesan sin mejora consistente.

6. Significado y Conclusión

El artículo establece que la inicialización de centroides basada en QUBO es una alternativa viable a los heurísticos clásicos.

• Ventaja Cuántica Potencial: Aunque los solvers clásicos (TABU, SimAnn) funcionan bien en los tamaños probados, la formulación está lista para hardware de recocido cuántico. A medida que el hardware cuántico madure (más qubits, mejor conectividad), AQOCI podría ofrecer una ventaja de velocidad y calidad en problemas de clustering a gran escala y de alta dimensionalidad donde los métodos greedy fallan.
• Relevancia: Proporciona un marco para recuperar valores reales de soluciones binarias en optimización cuántica, un paso crucial para aplicar estas técnicas a problemas del mundo real que requieren precisión de punto flotante.

En resumen, AQOCI demuestra que reformular la inicialización de k-means como un problema de optimización global (QUBO) puede superar a los métodos estándar en escenarios de datos complejos y de bajo volumen, ofreciendo una ruta prometedora hacia la ventaja cuántica en aprendizaje automático no supervisado.