Conditional anomaly detection with soft harmonic functions

1. O Problema: Detecção de Anomalias Condicionais (CAD)

O artigo aborda o problema da Detecção de Anomalias Condicionais (CAD). Diferente da detecção de anomalias tradicional (não condicional), que procura outliers em relação a todos os atributos dos dados, a CAD visa identificar valores incomuns para um subconjunto de variáveis (geralmente uma variável alvo ou rótulo) dado o contexto definido pelas demais variáveis.

• Definição Formal: Dado um conjunto de exemplos passados $(x_i, y_i)$ e novos exemplos recentes, o objetivo é identificar e classificar instâncias onde o rótulo $y$ é incomum dado o contexto $x$.
• Desafios Principais:
  1. Pontos Isolados (Isolated Points): Instâncias que estão geograficamente distantes da maioria dos dados. Como não há suporte de vizinhança, é difícil avaliar sua anomalia, e métodos tradicionais podem falhar ou gerar falsos positivos.
  2. Pontos de Borda (Fringe Points): Exemplos localizados na fronteira da distribuição de uma classe. Eles podem parecer anômalos devido à baixa probabilidade, mas não são necessariamente erros de rotulagem.
  3. Ruído de Rótulo: Os dados de treinamento podem conter erros de rotulagem, o que exige que o modelo seja robusto a isso.

2. Metodologia Proposta

Os autores propõem uma abordagem não paramétrica baseada em grafos de similaridade e propagação de rótulos, utilizando uma solução harmônica "suave" (soft harmonic solution).

A. Solução Harmônica Suave e Propagação de Rótulos

O método constrói um grafo de similaridade $G$ onde os nós são os exemplos de dados e as arestas representam a similaridade entre eles. Em vez de usar um classificador rígido, o método utiliza a propagação de informação de rótulos através do grafo.

• Confiança do Rótulo: O algoritmo calcula um rótulo suave $\ell^*_i$ para cada exemplo. A magnitude $|\ell^*_i|$ representa a confiança de que o rótulo é consistente com a vizinhança do ponto no manifold (estrutura dos dados).
• Score de Anomalia: A anomalia é definida como a diferença absoluta entre o rótulo real $y_i$ e o rótulo suave inferido $\ell^*_i$:
  $$s_i = |\ell^*_i - y_i|$$
  Um score alto indica que o rótulo observado é inconsistente com o que a estrutura local do grafo sugere.

B. Regularização para Pontos Isolados e de Borda

Para resolver os desafios de pontos isolados e de borda, os autores introduzem uma regularização diagonal no Laplaciano do grafo.

• Adiciona-se um termo $\gamma_g I$ ao Laplaciano, o que equivale a conectar todos os nós a um "nó sumidouro" (sink) com um rótulo neutro (0).
• Efeito: Isso reduz a confiança ($|\ell^*_i|$) de todos os pontos, mas reduz desproporcionalmente a confiança dos pontos isolados (que têm poucas conexões fortes com outros nós). Assim, pontos isolados recebem um score de anomalia baixo, evitando falsos positivos.

C. Grafo "Backbone" (Esqueleto) para Escalabilidade

O cálculo direto da inversa da matriz de similaridade tem complexidade $O(n^3)$, o que é inviável para grandes conjuntos de dados.

• Solução: Utiliza-se quantização de dados para criar um grafo menor ("backbone graph").
• Os dados originais são agrupados em centróides. Cada centróide recebe um peso baseado na sua multiplicidade (quantos pontos originais ele representa).
• Isso reduz a complexidade para $O(k^3)$, onde $k \ll n$, mantendo a estrutura do manifold através de pesos ajustados.

D. Ajuste para Multi-tarefas

Em cenários com múltiplos rótulos (ex: múltiplas decisões médicas), os scores de anomalia podem ter escalas diferentes. O método propõe uma normalização linear baseada nos scores mínimos e máximos do conjunto de treinamento para tornar os scores comparáveis entre diferentes tarefas.

3. Contribuições Principais

1. Abordagem Não Paramétrica: Introdução de um método baseado em propagação de rótulos em grafos para CAD, estimando a confiança do rótulo em vez de apenas classificar.
2. Regularização Específica: Proposta de uma regularização que mitiga o problema de pontos isolados e de borda, evitando que sejam classificados erroneamente como anomalias.
3. Computação Compacta: Desenvolvimento de um método para calcular a solução em um grafo backbone com pesos de multiplicidade, permitindo escalabilidade.
4. Validação em Cenários Reais: Avaliação bem-sucedida em dados sintéticos, conjuntos UCI e um conjunto de dados complexo de registros eletrônicos de saúde (EHR).

4. Resultados Experimentais

Os autores compararam seu método (SoftHAD) com várias linhas de base: SVM de 1-classe, Análise Discriminante Quadrática (QDA), SVM de classificação e k-NN ponderado.

• Dados Sintéticos: O SoftHAD superou consistentemente todas as outras abordagens, alcançando a melhor concordância com a ordem de anomalias verdadeiras (medida por AUC/Wilcoxon score). Ele foi capaz de identificar anomalias condicionais em regiões de alta sobreposição onde outros métodos falharam.
• Conjuntos UCI (Wine Quality, Housing, Auto MPG): O método obteve os melhores ou próximos dos melhores resultados, demonstrando robustez em dados do mundo real com variáveis de resposta ordinais.
• Dados Médicos (Registros Eletrônicos de Saúde):
  • Contexto: Detecção de decisões incomuns de gerenciamento de pacientes (ex: ordens de laboratório ou medicações).
  • Avaliação: A qualidade foi avaliada por especialistas clínicos.
  • Desempenho: O SoftHAD superou o SVM e o k-NN ponderado. A introdução do ajuste de escala para multi-tarefas melhorou ainda mais o desempenho e a robustez aos parâmetros de regularização.
  • Robustez: O método mostrou-se pouco sensível ao tamanho do grafo (devido ao ajuste de multiplicidade) e aos parâmetros de regularização.

5. Significado e Conclusão

O trabalho é significativo porque oferece uma solução robusta para um problema complexo onde o contexto é crucial. Ao integrar a estrutura do manifold dos dados (via grafos) com uma regularização inteligente que trata pontos de borda e isolados, o método supera as limitações de classificadores tradicionais e métodos baseados apenas em vizinhança local (como k-NN).

A aplicação em saúde demonstra a utilidade prática do método para identificar erros de diagnóstico ou decisões clínicas atípicas, onde a "anomalia" não é um valor fora do padrão geral, mas sim uma decisão que não faz sentido dado o estado específico do paciente. O uso de um grafo backbone torna a abordagem viável para grandes volumes de dados, um requisito essencial para aplicações em registros eletrônicos de saúde.