Proportionally Representative Clustering

Resumen Técnico: Agrupamiento Representativo Proporcionalmente

Planteamiento del Problema
El artículo aborda el problema de la equidad en el agrupamiento de centroides, una tarea fundamental en el aprendizaje automático no supervisado donde el objetivo es seleccionar un subconjunto de $k$ centros (centroides) de un espacio métrico para servir a un conjunto de $n$ puntos de datos (agentes). Mientras que los objetivos estándar como $k$-means, $k$-medianas y $k$-center optimizan el bienestar global, a menudo no logran capturar una equidad de representación proporcional. Los conceptos de equidad existentes en el agrupamiento, como la Equidad Proporcional (PF) y la Equidad de Núcleo (Core Fairness), presentan limitaciones: pueden no ser alcanzables para cada instancia y no logran satisfacer un requisito intuitivo mínimo conocido como "proporcionalidad unánime" (donde un grupo de agentes en la misma ubicación tiene derecho a un número de centros proporcional a su tamaño). Además, los algoritmos existentes para el agrupamiento justo suelen depender de atributos protegidos preespecificados, mientras que este trabajo busca propiedades de equidad aplicables a grupos definidos endógenamente por la distribución de los datos.

Metodología
Los autores adoptan un enfoque axiomático, proponiendo un nuevo concepto de equidad llamado Equidad Representativa Proporcionalmente (PRF). Este concepto está diseñado tanto para entornos no restringidos (continuos) como discretos.

1. Definición Axiomática (PRF):

   • Entorno No Restringido: Un resultado $X$ satisface la PRF si, para cualquier conjunto de agentes $S$ de tamaño al menos $\ell n/k$ con una distancia máxima entre pares $y$, hay al menos $\ell$ centros en $X$ dentro de una distancia $y$ de al menos un agente en $S$.
   • Entorno Discreto: La definición se adapta para considerar la granularidad del conjunto de candidatos $M$. Si hay $\ell'$ candidatos en $M$ dentro de una distancia $y$ de todos los agentes en un grupo $S$ (donde $|S| \ge \ell n/k$), entonces al menos $\ell'$ centros en el resultado deben estar dentro de una distancia $y$ de algún agente en $S$.

2. Diseño de Algoritmos (SEAR):
   Los autores introducen SEAR (Regla de Aprobación de Expansión Espacial), un algoritmo de tiempo polinomial inspirado en la Regla de Aprobaciones en Expansión (EAR) de la votación multi-ganador, pero adaptado para datos espaciales.

   • Mecanismo: El algoritmo expande iterativamente los radios de vecindad basados en las distancias ordenadas entre agentes y candidatos. Los agentes reciben pesos iniciales. Cuando se selecciona un centro candidato que cubre un grupo de agentes con un peso total de al menos $n/k$, ese centro se añade a la solución y los pesos de los agentes cubiertos se reducen en $n/k$.
   • Implementación:
     • Algoritmo 1 (No restringido): Los candidatos se restringen a las ubicaciones de los agentes. Se ejecuta en $O(n^2 \log n + kn^2)$.
     • Algoritmo 2 (Discreto): Los candidatos se extraen de un conjunto finito $M$. Se ejecuta en $O(|M|n \log n + k|M|n)$.

Contribuciones Clave y Resultados

• Existencia y Propiedades de la PRF: El artículo demuestra que se garantiza la existencia de un resultado PRF tanto en entornos no restringidos como discretos. La PRF satisface varias propiedades deseables: implica proporcionalidad unánime, es robusta ante valores atípicos (outliers), es invariante de escala y no requiere grupos protegidos preespecificados.
• Aproximación de la Equidad Proporcional (PF):
  • No restringido: El algoritmo SEAR para el entorno no restringido proporciona una 3-aproximación a la Equidad Proporcional. Este es el primer algoritmo de aproximación de tiempo polinomial conocido para la PF en espacios métricos generales. El artículo también establece un límite ajustado de $\frac{3+\sqrt{17}}{2} \approx 3.56$ para la existencia general de resultados de PRF respecto a la PF.
  • Discreto: El algoritmo SEAR para el entorno discreto proporciona una $(1+\sqrt{2})$-aproximación a la PF, igualando el mejor factor de aproximación conocido para la PF en el entorno discreto, mientras satisface adicionalmente el axioma más fuerte de la PRF.
• Resultados de Imposibilidad:
  • El artículo demuestra que los algoritmos de agrupamiento estándar ($k$-means, $k$-median, $k$-center) y los algoritmos previos de agrupamiento justo (como Greedy Capture) no satisfacen la PRF.
  • Estratégica-verificabilidad (Strategyproofness): Los autores demuestran una incompatibilidad entre la PRF y la estrategia-verificabilidad. Específicamente, no existe un algoritmo que sea tanto de orden estadístico estrategia-verificable como que satisfaga la PRF, incluso para $k=2$ en el entorno discreto. Esto se demuestra mediante una reducción de la votación de comités basada en aprobación, vinculando la PRF con el axioma de Representación Justificada Proporcional (PJR), el cual es conocido por ser incompatible con la estrategia-verificabilidad.

Significado
El artículo reclama importancia en tres áreas principales:

1. Avance Conceptual: Introduce la PRF como un concepto de equidad axiomático y robusto que supera las deficiencias de las definiciones de equidad proporcional existentes, particularmente el fallo en garantizar la proporcionalidad unánime.
2. Avance Algorítmico: Proporciona los primeros algoritmos de aproximación de tiempo polinomial para la Equidad Proporcional en espacios métricos generales (entorno no restringido) y iguala los mejores límites conocidos para el entorno discreto, todo ello cumpliendo el axioma más fuerte de la PRF.
3. Límites Teóricos: Establece rigurosamente el compromiso entre la equidad (específicamente la PRF) y la compatibilidad de incentivos (estrategia-verificabilidad), mostrando que satisfacer los axiomas de representación proporcional entra en conflicto inherente con la prevención de la manipulación en la selección de centroides.

El trabajo se posiciona como un puente entre la teoría de la elección social (específicamente la votación multi-ganador) y el aprendizaje automático no supervisado, utilizando información espacial para tomar decisiones sincronizadas que las reglas de votación tradicionales o los objetivos de agrupamiento estándar no pueden lograr.