A Deterministic Information Bottleneck Method for Clustering Mixed-Type Data

Resumo Técnico: Um Método de Gargalo de Informação Determinístico para Agrupamento de Dados de Tipos Mistos

Definição do Problema
O agrupamento (clustering) de dados de tipos mistos — conjuntos de dados que compreendem tanto variáveis contínuas quanto categóricas (nominais e ordinais) — apresenta desafios significativos devido à heterogeneidade dos tipos de variáveis. Algoritmos de agrupamento tradicionais frequentemente lutam para equilibrar as contribuições desses tipos de variáveis díspares, levando a estruturas de agrupamento subótimas. Embora métodos existentes como K-Prototypes, KAMILA e abordagens baseadas em distância (por exemplo, PAM com dissimilaridade de Gower) ofereçam soluções, eles frequentemente dependem de suposições de centroides ou métricas de distância específicas que podem não capturar totalmente a estrutura de informação subjacente de dados heterogêneos. Além disso, muitas abordagens existentes carecem de um arcabouço teórico unificado que trate naturalmente variáveis contínuas, nominais e ordinais sem exigir pré-processamentos extensivos, como a codificação one-hot, que pode obscurecer as estruturas de agrupamento e aumentar a dimensionalidade.

Metodologia: DIBmix
O artigo propõe o DIBmix, um algoritmo de agrupamento baseado no arcabouço de Gargalo de Informação Determinístico (DIB), estendido para lidar com dados de tipos mistos. O objetivo central é encontrar uma representação comprimida $T$ (agrupamentos) dos dados de entrada $X$ que maximize a informação mútua com a localização dos dados $Y$ no espaço de atributos mistos, sujeito a uma restrição de compressão.

Componentes metodológicos principais incluem:

1. Kernels de Produto Generalizados: Para estimar a densidade conjunta $p(x, y)$, os autores empregam um kernel de produto generalizado. Este integra:

   • Kernels Gaussianos para variáveis contínuas.
   • Kernels de Aitchison & Aitken para variáveis nominais (categóricas não ordenadas).
   • Kernels de Li & Racine para variáveis ordinais (categóricas ordenadas).
     Esta abordagem evita assumir a independência das variáveis, utilizando o produto de kernels como um mecanismo de ponderação para uma estimativa de densidade robusta.

2. Estrutura de Otimização: O algoritmo busca minimizar a função objetivo $H(T) - \beta I(Y; T)$, onde $H(T)$ é a entropia das atribuições de agrupamento (atuando como um regularizador para os tamanhos dos agrupamentos) e $I(Y; T)$ é a informação mútua entre os agrupamentos e as localizações dos dados. O parâmetro $\beta$ controla o equilíbrio (trade-off) entre compressão e relevância.

3. Seleção Adaptativa de Hiperparâmetros:

   • Seleção de Bandwidth (Largura de Banda): Uma estratégia sistemática é proposta para equalizar as contribuições de variáveis contínuas e categóricas. Isso envolve definir razões de kernel (por exemplo, razão de kernel de vizinho mais distante médio para variáveis contínuas e razões de discordância para variáveis categóricas) e ajustar as larguras de banda para garantir que nenhum tipo de variável domine a matriz de similaridade.
   • $\beta$ Adaptativo: Diferente das implementações padrão de DIB onde $\beta$ é fixo, o DIBmix emprega um esquema de atualização adaptativa para o parâmetro de regularização $\beta$ em cada iteração. Isso garante que o algoritmo converja para uma solução com exatamente $C$ agrupamentos não vazios, mesmo quando os dados contêm tamanhos de agrupamento desbalanceados, ao evitar que o menor agrupamento desapareça.

4. Escalabilidade: Para grandes conjuntos de dados, o método utiliza a aproximação de Nyström para reduzir a complexidade computacional da construção da matriz de similaridade completa de $O(n^2)$ para $O(n\sqrt{n})$, tornando a abordagem viável para aplicações de larga escala.

Principais Contribuições
O artigo descreve três contribuições primárias:

1. Extensão do Arcabouço: Adaptar o arcabouço DIB para lidar nativamente com dados de tipos mistos (contínuos, nominais e ordinais) sem exigir redução de dimensionalidade ou codificação one-hot.
2. Estratégia Sistemática de Hiperparâmetros: Propor um método para selecionar larguras de banda e o parâmetro de regularização $\beta$ que equilibre as contribuições das variáveis e garanta uma partição válida em um número predeterminado de agrupamentos, abordando o problema de tamanhos de agrupamento desbalanceados.
3. Avaliação Abrangente: Testar o DIBmix contra quatro métodos estabelecidos (KAMILA, K-Prototypes, FAMD com K-Means e PAM com dissimilaridade de Gower) através de extensas simulações e conjuntos de dados do mundo real.

Resultados
O desempenho do DIBmix foi avaliado através de:

• Simulações: 28.800 conjuntos de dados sintéticos foram gerados variando em tamanho de amostra, número de agrupamentos, proporções de variáveis, níveis de sobreposição e formas de agrupamento.
  • O DIBmix alcançou o maior Índice Rand Ajustado (ARI) e Informação Mútua Ajustada (AMI) mediana em comparação com todos os competidores.
  • Demonstrou robustez particular em cenários com tamanhos de agrupamento desbalanceados e sobreposição de baixa a moderada.
  • Os efeitos de tamanho ( $\eta^2$ parcial) indicaram que o DIBmix superou consistentemente os competidores, com valores variando de 0,32 a 0,99.
• Benchmarks de Mundo Real: O método foi testado em dez conjuntos de dados públicos da UCI.
  • O DIBmix alcançou o melhor ARI em quatro de dez conjuntos de dados.
  • Teve o melhor desempenho quando os conjuntos de dados continham uma mistura equilibrada de tipos de variáveis.
  • O desempenho foi competitivo, mas ligeiramente inferior ao FAMD ou K-Prototypes em conjuntos de dados dominados quase exclusivamente por um ou outro tipo de variável (categórica ou contínua).
  • Um teste de Friedman nos dez conjuntos de dados mostrou que o DIBmix teve o melhor ranking médio (2,45), embora a significância estatística não tenha sido alcançada devido ao pequeno número de conjuntos de dados e ao limiar de diferença crítica.

Significância e Alegações
Os autores afirmam que o DIBmix estabelece uma alternativa teoricamente fundamentada para o agrupamento de dados de tipos mistos. Sua significância reside em:

• Lidar com Desbalanceamento: Ao contrário dos algoritmos tradicionais baseados em centroides que frequentemente favorecem agrupamentos de tamanhos iguais, a função objetivo baseada em entropia do DIBmix permite e lida efetivamente com tamanhos de agrupamento altamente desbalanceados.
• Rigor Teórico: Ao utilizar o princípio do Gargalo de Informação, o método oferece uma maneira fundamentada de extrair informação relevante enquanto comprime os dados, oferecendo uma perspectiva diferente das abordagens baseadas em distância ou modelos.
• Interpretabilidade: O arcabouço permite a quantificação da importância das variáveis via informação mútua, ajudando a identificar quais características impulsionam a estrutura de agrupamento (por exemplo, identificando biomarcadores clinicamente relevantes em um conjunto de dados de câncer de próstata).

O artigo conclui que, embora o DIBmix seja altamente competitivo e robusto, particularmente para dados genuinamente mistos, pode não ser a escolha ideal para conjuntos de dados onde um tipo de variável domina esmagadoramente. Os autores reconhecem limitações em relação à seleção de largura de banda em cenários extremos e à suposição de homogeneidade dos agrupamentos, sugerindo que trabalhos futuros possam explorar larguras de banda locais e robustez a outliers.