Proportionally Representative Clustering

Resumo Técnico: Agrupamento Proporcionalmente Representativo

Definição do Problema
O artigo aborda o problema da equidade em agrupamento de centroides, uma tarefa fundamental de aprendizado não supervisionado onde o objetivo é selecionar um subconjunto de $k$ centros (centroides) de um espaço métrico para servir a um conjunto de $n$ pontos de dados (agentes). Embora objetivos padrão como $k$-means, $k$-medianas e $k$-centro otimizem o bem-estar global, eles frequentemente falham em capturar uma equidade de representação proporcional. Conceitos de equidade existentes em agrupamento, como Equidade Proporcional (PF) e Equidade do Núcleo (Core Fairness), possuem limitações: podem não ser alcançáveis para cada instância e falham em satisfazer um requisito intuitivo mínimo conhecido como "proporcionalidade unânime" (onde um grupo de agentes na mesma localização tem direito a um número de centros proporcional ao seu tamanho). Além disso, algoritmos existentes para agrupamento justo frequentemente dependem de atributos protegidos pré-especificados, enquanto este trabalho busca propriedades de equidade aplicáveis a grupos arbitrariamente definidos, determinados endogenamente pela distribuição dos dados.

Metodologia
Os autores adotam uma abordagem axiomática, propondo um novo conceito de equidade chamado Equidade Proporcionalmente Representativa (PRF). Este conceito é projetado tanto para ambientes não restritos (contínuos) quanto para ambientes discretos.

1. Definição Axiomática (PRF):

   • Ambiente Não Restrito: Um resultado $X$ satisfaz PRF se, para qualquer conjunto de agentes $S$ de tamanho pelo menos $\ell n/k$ com uma distância máxima entre pares $y$, houver pelo menos $\ell$ centros em $X$ dentro da distância $y$ de pelo menos um agente em $S$.
   • Ambiente Discreto: A definição é adaptada para considerar a granularidade do conjunto de candidatos $M$. Se houver $\ell'$ candidatos em $M$ dentro da distância $y$ de todos os agentes de um grupo $S$ (onde $|S| \ge \ell n/k$), então pelo menos $\ell'$ centros no resultado devem estar dentro da distância $y$ de algum agente em $S$.

2. Design de Algoritmo (SEAR):
   Os autores introduzem o SEAR (Spatial Expanding Approval Rule - Regra de Aprovação Espacial Expansiva), um algoritmo de tempo polinomial inspirado na Regra de Aprovações Expansivas (EAR) de votação multi-vencedor, mas adaptada para dados espaciais.

   • Mecanismo: O algoritmo expande iterativamente os raios de vizinhança com base nas distâncias ordenadas entre agentes e candidatos. Os agentes recebem pesos iniciais. Quando um candidato centroide é selecionado e cobre um grupo de agentes com um peso total de pelo menos $n/k$, esse centroide é adicionado à solução e os pesos dos agentes cobertos são reduzidos em $n/k$.
   • Implementação:
     • Algoritmo 1 (Não Restrito): Os candidatos são restritos às localizações dos agentes. Executa em $O(n^2 \log n + kn^2)$.
     • Algoritmo 2 (Discreto): Os candidatos são extraídos de um conjunto finito $M$. Executa em $O(|M|n \log n + k|M|n)$.

Principais Contribuições e Resultados

• Existência e Propriedades de PRF: O artigo prova que um resultado PRF é garantido existir tanto em ambientes não restritos quanto discretos. A PRF satisfaz várias propriedades desejáveis: implica proporcionalidade unânime, é robusta a outliers, é invariante de escala e não requer grupos protegidos pré-especificados.
• Aproximação de Equidade Proporcional (PF):
  • Não Restrito: O algoritmo SEAR para o ambiente não restrito fornece uma 3-aproximação para a Equidade Proporcional. Esta é a primeira aproximação de tempo polinomial conhecida para PF em espaços métricos gerais. O artigo também estabelece um limite estrito de $\frac{3+\sqrt{17}}{2} \approx 3.56$ para a existência geral de resultados de PRF em relação à PF.
  • Discreto: O algoritmo SEAR para o ambiente discreto fornece uma $(1+\sqrt{2})$-aproximação para PF, igualando o melhor fator de aproximação conhecido para PF no ambiente discreto, enquanto adicionalmente satisfaz o axioma mais forte de PRF.
• Resultados de Impossibilidade:
  • O artigo demonstra que algoritmos de agrupamento padrão ($k$-means, $k$-median, $k$-center) e algoritmos anteriores de agrupamento justo (como Greedy Capture) não satisfazem PRF.
  • Estratégia-imunidade (Strategyproofness): Os autores provam uma incompatibilidade entre PRF e estratégia-imunidade. Especificamente, não existe um algoritmo que seja simultaneamente baseado em estatística de ordem estratégica (order-statistic strategyproof) e que satisfaça PRF, mesmo para $k=2$ no ambiente discreto. Isso é demonstrado via uma redução da votação de comitê baseada em aprovação, ligando a PRF ao axioma de Representação Justificada Proporcional (PJR), que é conhecido por ser incompatível com a estratégia-imunidade.

Significância
O artigo reivindica significância em três áreas principais:

1. Avanço Conceitual: Introduz a PRF como um conceito de equidade axiomática robusto que supera as deficiências das definições de equidade proporcional existentes, particularmente a falha em garantir a proporcionalidade unânime.
2. Avanço Algorítmico: Fornece os primeiros algoritmos de aproximação de tempo polinomial para Equidade Proporcional em espaços métricos gerais (ambiente não restrito) e iguala os limites conhecidos para o ambiente discreto, tudo isso satisfazendo o axioma mais forte de PRF.
3. Limites Teóricos: Estabelece rigorosamente o compromisso (trade-off) entre equidade (especificamente PRF) e compatibilidade de incentivos (estratégia-imunidade), mostrando que satisfazer axiomas de representação proporcional entra em conflito inerente com a prevenção de manipulação na seleção de centroides.

O trabalho posiciona-se como uma ponte entre a teoria da escolha social (especificamente votação multi-vencedor) e o aprendizado não supervisionado, utilizando informações espaciais para tomar decisões sincronizadas que regras de votação tradicionais ou objetivos de agrupamento padrão não conseguem alcançar.