Comparison of Outlier Detection Algorithms on String Data

Esta tese compara dois algoritmos de detecção de outliers em dados textuais: uma variante do Local Outlier Factor adaptada com uma medida de Levenshtein ponderada e um novo método baseado em expressões regulares hierárquicas, demonstrando experimentalmente que cada abordagem é mais eficaz dependendo se as anomalias se distinguem pela estrutura ou pela distância de edição em relação aos dados esperados.

O essencial

Imagine que você é um detetive encarregado de encontrar "intrusos" em uma grande festa. A festa é um conjunto de dados (uma lista de nomes, endereços ou códigos) e os intrusos são os outliers (os dados estranhos que não deveriam estar ali).

A maioria dos detetives (algoritmos) é treinada apenas para lidar com números (como idades ou salários). Mas o que fazer quando a festa é feita de palavras e textos? É aí que entra o trabalho de Philip Maus, apresentado nesta tese. Ele comparou dois métodos diferentes para caçar esses intrusos em meio a textos.

Vamos explicar como cada um deles funciona usando analogias simples:

1. O Detetive do "Vizinho Próximo" (Algoritmo LOF)

Este primeiro método é baseado na ideia de que se você está sozinho em um lugar estranho, provavelmente é um intruso.

• Como funciona: Imagine que você tem uma lista de códigos de CEP (ex: "12345", "12346"). O algoritmo olha para cada código e pergunta: "Quem são meus 5 vizinhos mais próximos?". Se o seu vizinho mais próximo está muito longe de você (em termos de letras diferentes), você é considerado um estranho.
• O Truque da Hierarquia: O autor percebeu que apenas contar letras trocadas não é justo. Trocar um "1" por um "2" é fácil (são ambos números), mas trocar um "1" por uma letra "A" é muito mais estranho. Então, ele criou uma "árvore de família" para os caracteres:
  • Números são primos entre si.
  • Letras são primos entre si.
  • Números e letras são primos distantes.
  • Assim, o algoritmo entende que trocar um número por uma letra é um "crime" maior do que trocar um número por outro número.
• Quando é bom: Funciona muito bem quando os dados normais são parecidos entre si (como CEPs) e o intruso é apenas um pouco diferente (um CEP com um erro de digitação ou um número de telefone misturado). É como encontrar alguém na festa usando um terno quando todos os outros estão de jeans.

2. O Detetive do "Modelo Perfeito" (Algoritmo baseado em Expressões Regulares)

Este segundo método é diferente. Em vez de olhar para os vizinhos, ele tenta descobrir a regra secreta que define quem é convidado e quem não é.

• Como funciona: Imagine que todos os convidados têm um crachá com um padrão específico (ex: "Todos os crachás começam com '202' e têm 5 dígitos"). O algoritmo tenta adivinhar essa regra (uma "Expressão Regular") olhando para a maioria dos dados.
  • Se a regra for: "Qualquer coisa que seja 5 dígitos", então "12345" passa, mas "123456" (6 dígitos) ou "ABCDE" (letras) são expulsos como intrusos.
• O Desafio: O algoritmo precisa decidir qual regra escolher. Se ele escolher uma regra muito rígida (ex: "Só aceita o número 12345"), ele vai expulsar muitos convidados bons. Se escolher uma muito solta (ex: "Aceita qualquer coisa"), ele deixa os intrusos entrarem. O autor criou um jeito inteligente de encontrar o equilíbrio perfeito.
• Quando é bom: Funciona incrivelmente bem quando os dados normais têm uma estrutura muito clara e fixa (como datas no formato "AAAA-MM-DD"). É como se todos os convidados usassem o mesmo uniforme. Qualquer um que não use o uniforme é imediatamente identificado.
• Quando falha: Se a festa for bagunçada e todos usarem roupas diferentes (dados sem padrão), o algoritmo não consegue descobrir a regra e falha em encontrar os intrusos.

O Grande Showdown (Os Experimentos)

O autor testou esses dois detetives em dados reais de hospitais alemães (endereços, datas, códigos).

1. Cenário A (CEPs vs. Nomes de Cidades):

   • Os CEPs são todos de 5 dígitos. Os nomes das cidades são longos e variados.
   • Resultado: O "Detetive do Modelo Perfeito" (Expressão Regular) foi um gênio. Ele descobriu que "CEP = 5 dígitos" e expulsou todos os nomes de cidades instantaneamente. O "Detetive do Vizinho" também funcionou, mas foi um pouco mais lento e confuso.

2. Cenário B (Nomes de Cidades vs. CEPs):

   • Agora, os dados normais são os nomes das cidades (que são bagunçados e variados) e os intrusos são os CEPs (que são todos iguais).
   • Resultado: O "Detetive do Modelo Perfeito" ficou confuso. Como os nomes das cidades não seguem um padrão único, ele não conseguiu criar uma regra boa e falhou. O "Detetive do Vizinho" também teve dificuldade, pois a "bagunça" dos nomes das cidades escondia os CEPs.

3. Cenário C (CEPs vs. Números de Telefone/Casa):

   • Todos são números, mas os CEPs têm 5 dígitos e os telefones têm mais.
   • Resultado: O "Detetive do Vizinho" brilhou aqui. Ele percebeu que os CEPs formam um grupo denso e os telefones são "vizinhos distantes". O "Detetive do Modelo Perfeito" teve dificuldade porque ambos são apenas números, e ele não sabia qual regra aplicar.

Conclusão Simples

O trabalho de Philip Maus nos ensina que não existe um "super-detetive" universal.

• Se seus dados têm um padrão rígido (como datas ou códigos fixos), use o algoritmo de Expressão Regular. Ele é como um guarda que só deixa entrar quem tem o crachá certo.
• Se seus dados são mais soltos ou os intrusos são apenas "levemente diferentes" (como um erro de digitação), use o algoritmo de Vizinhos (LOF). Ele é como um segurança que olha para quem está se isolando do grupo.

A grande lição é: para limpar dados ou encontrar anomalias em textos, você precisa entender a "personalidade" dos seus dados antes de escolher qual ferramenta usar.

Resumo técnico

Resumo Técnico: Comparação de Algoritmos de Detecção de Outliers em Dados de String

1. Problema e Motivação

A detecção de outliers (valores atípicos) é um problema fundamental no aprendizado de máquina e na ciência da computação, amplamente estudado para dados numéricos. No entanto, há uma lacuna significativa na pesquisa sobre detecção de outliers em dados de string (texto). A maioria das abordagens existentes foca em dados numéricos, deixando de lado aplicações críticas como:

• Limpeza automática de dados de entrada de usuários.
• Análise de sequências de proteínas.
• Detecção de atividades anômalas em arquivos de log de sistemas.

O objetivo desta tese é preencher essa lacuna comparando dois algoritmos distintos adaptados para detectar outliers sintáticos em conjuntos de dados de strings (palavras únicas), sem a necessidade de contexto semântico adicional.

2. Metodologia e Abordagens Propostas

O autor propõe e compara duas abordagens principais:

A. Abordagem Baseada em Vizinhos Mais Próximos (LOF Adaptado)

Esta abordagem adapta o algoritmo clássico Local Outlier Factor (LOF), originalmente projetado para dados numéricos, para funcionar com strings.

• Métrica de Distância: Utiliza a Distância de Levenshtein (distância de edição) para calcular a proximidade entre strings.
• Levenshtein Hierárquico Pesado: Uma contribuição chave é a introdução de uma versão ponderada da distância de Levenshtein. Em vez de atribuir peso igual (+1) para todas as operações de substituição, o algoritmo utiliza uma partição hierárquica de classes de caracteres (ex: dígitos, letras maiúsculas, minúsculas, pontuação). A substituição de caracteres dentro da mesma classe hierárquica recebe um peso menor do que a substituição entre classes distantes. Isso permite que o algoritmo seja "sintonizado" para a estrutura sintática específica do dataset.
• Seleção de Parâmetros:
  • k (vizinhos): Utiliza um "guesser" chamado KFCS (k-finder based on neighborhood consistency) para determinar automaticamente o valor ideal de $k$ baseado na consistência das pontuações de outliers entre vizinhos.
  • Limiar (Threshold): Emprega uma estratégia de limiar dinâmico e iterativo, onde o limiar é definido como um múltiplo da média das pontuações de anomalia, permitindo a detecção incremental de grupos de outliers com diferentes graus de anomalia.

B. Abordagem Baseada em Expressões Regulares (HiLRE)

Esta é uma nova abordagem proposta pelo autor, baseada no aprendizado de Hierarchical Left Regular Expressions (HiLRE).

• Conceito: Assume-se que os dados esperados (não-outliers) podem ser descritos por uma linguagem regular específica. O algoritmo tenta inferir uma expressão regular (HiLRE) que cubra a maioria dos dados "normais".
• Algoritmo de Aprendizado: Utiliza um algoritmo incremental que constrói uma lista de "aprendizados" (Learnings) para cada string, inferindo uma expressão regular mínima que corresponde a um subconjunto dos dados.
• Seleção do Modelo ($H^*$): O algoritmo gera HiLREs para todos os subconjuntos possíveis dos dados. Ele seleciona o HiLRE ótimo ($H^*$) que maximiza a diferença mínima de correspondência em relação aos seus subconjuntos (ou seja, o modelo que captura mais dados novos sem incluir muitos dados que deveriam ser excluídos).
• Parâmetro de Minimização ($p_{min}$): Foi introduzido um parâmetro $p_{min}$ que define a porcentagem mínima de strings do dataset que a expressão regular selecionada deve corresponder. Isso evita que o algoritmo selecione expressões muito específicas que capturam apenas um único valor comum, forçando-o a encontrar padrões mais gerais.
• Detecção: Qualquer string que não corresponda ao HiLRE selecionado ($H^*$) é classificada como outlier.

3. Contribuições Principais

1. Adaptação do LOF para Strings: Demonstração prática de como o LOF pode ser aplicado a dados de texto usando a métrica de Levenshtein, com uma melhoria significativa através da ponderação hierárquica das classes de caracteres.
2. Novo Algoritmo Baseado em HiLRE: Proposta de um novo método de detecção de outliers que infere expressões regulares hierárquicas para definir a "normalidade" dos dados, classificando o que não se encaixa como anomalia.
3. Mecanismo de Ponderação Hierárquica: A definição de uma partição hierárquica de caracteres que permite ajustar a sensibilidade do algoritmo à estrutura sintática dos dados (ex: diferenciar a troca de um dígito por uma letra de uma troca entre dois dígitos).
4. Comparação Empírica Rigorosa: Avaliação extensiva usando datasets sintéticos e dados reais (relatórios de qualidade de hospitais alemães), focando em endereços (CEP, nomes de condados, números de telefone) e datas.

4. Resultados Experimentais

Os experimentos foram realizados em datasets reais (CEPs, nomes de condados, datas, horários, números de telefone) com a inserção controlada de outliers.

• Desempenho do LOF:

  • Funciona bem quando os outliers têm uma estrutura sintática semelhante aos dados normais, mas diferem em distância de edição (ex: CEPs válidos vs. CEPs com erros de digitação ou números de telefone com o mesmo comprimento).
  • A versão com pesos hierárquicos mostrou-se mais estável e capaz de distinguir melhor entre classes de caracteres diferentes (ex: letras vs. números), reduzindo falsos positivos em casos onde strings de mesmo comprimento pertencem a classes distintas.
  • Tendência a ter taxas mais altas de falsos positivos e negativos em comparação com o HiLRE em cenários de estrutura muito distinta.

• Desempenho do HiLRE:

  • Excelente quando os dados esperados possuem uma estrutura rígida e distinta (ex: CEPs de 5 dígitos). O algoritmo consegue inferir a expressão regular perfeita e detectar 100% dos outliers com 0% de falsos positivos.
  • Fraco quando os dados esperados são heterogêneos e desestruturados (ex: nomes de condados com variáveis de comprimento e caracteres). Nesses casos, o algoritmo falha em encontrar uma expressão regular que generalize bem, resultando em baixa detecção de outliers ou seleção de modelos muito genéricos que não filtram nada.
  • O parâmetro $p_{min}$ provou ser crucial para evitar a seleção de modelos que capturam apenas outliers frequentes ou padrões muito restritos.

• Comparação Geral:

  • Não existe um algoritmo superior universal; o desempenho depende intrinsecamente da natureza do dataset.
  • HiLRE é superior para dados com estrutura forte e previsível.
  • LOF é superior para dados onde a anomalia é definida pela "distância" ou densidade, especialmente quando a estrutura geral é mantida, mas os valores variam.

5. Significado e Conclusão

A tese demonstra que a detecção de outliers em dados de string é viável e eficaz, mas requer abordagens específicas que considerem a natureza sintática dos dados.

• Impacto Prático: As técnicas propostas podem ser aplicadas diretamente em sistemas de validação de dados, limpeza de bancos de dados e monitoramento de logs, onde a entrada é textual.
• Insight sobre Dados: O uso do algoritmo HiLRE revelou propriedades ocultas dos dados reais (ex: a maioria dos relatórios de qualidade hospitalar é enviada no final do ano, entre 10h e 20h), sugerindo que a detecção de outliers pode ser usada também para descoberta de padrões (data mining).
• Trabalho Futuro: O autor sugere que futuras pesquisas devem focar na análise teórica de complexidade (tempo/espaço) do algoritmo HiLRE, na extensão para strings com múltiplas palavras e na incorporação de contexto semântico para detecção de outliers mais sofisticada.

Em suma, o trabalho oferece um framework comparativo robusto, provando que a escolha entre uma abordagem baseada em densidade (LOF) e uma baseada em inferência de linguagem (HiLRE) deve ser guiada pela estrutura e variabilidade do conjunto de dados específico.