Skip to content
Voltar aos resultados

Indução de Regras (RIPPER)

Proposto por
William W. Cohen
Ano
1995
Tipo
Supervised rule learning algorithm
Família
Rule learning

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

A Indução de Regras, e especificamente o algoritmo RIPPER (Repeated Incremental Pruning to Produce Error Reduction), é um método de aprendizado de máquina supervisionado que aprende um conjunto compacto de regras de classificação IF-THEN a partir de dados de treinamento rotulados.

Introduzido por William W. Cohen em 1995, o RIPPER aplica uma estratégia de separar e conquistar (separate-and-conquer) combinada com poda (pruning) de mínima descrição (MDL - Minimum Description Length) para gerar regras que são ao mesmo tempo precisas e interpretáveis, tornando-o um algoritmo marco no campo do aprendizado indutivo de regras.

A intuição por trás do método

Imagine escrever um checklist de diagnóstico para um médico: cada regra captura uma combinação específica de sintomas que prevê confiavelmente um diagnóstico. O RIPPER constrói este checklist automaticamente a partir de dados de pacientes. Ele elabora uma regra por vez, cobrindo o máximo possível de casos positivos, e então verifica cada regra em um conjunto separado para remover condições excessivamente específicas. O resultado é um livro de regras curto e legível por humanos que pode ser aplicado a novos pacientes sem a necessidade de examinar todo o histórico de treinamento.

História

A Indução de Regras tem raízes em sistemas de aprendizado de máquina iniciais como AQ (Michalski, 1969) e CN2 (Clark e Niblett, 1989). O artigo de Cohen de 1995 sobre o RIPPER abordou a ineficiência computacional e as tendências de overfitting de seus predecessores introduzindo poda incremental e otimização baseada em MDL. Apresentado na ICML 1995, o RIPPER rapidamente se tornou um algoritmo de referência devido à sua precisão competitiva e transparência, e continua sendo uma referência padrão na literatura e em livros didáticos sobre aprendizado de regras.

Quando usar

A Indução de Regras com RIPPER é apropriada quando a interpretabilidade do modelo é um requisito primário, como em suporte à decisão clínica, detecção de fraudes ou cenários de conformidade regulatória. Ele funciona com características nominais e numéricas mistas e escala razoavelmente para dezenas de milhares de instâncias. O RIPPER assume que os rótulos de treinamento são suficientemente confiáveis e que a fronteira de decisão subjacente pode ser aproximada por conjunções alinhadas aos eixos. É menos adequado para espaços de características contínuas de alta dimensionalidade ou tarefas que exigem saídas probabilisticamente calibradas; nesses casos, árvores de decisão com gradient boosting ou regressão logística podem ser preferidas.

Limitações e considerações

  • A qualidade das regras degrada significativamente em espaços de características de altíssima dimensionalidade ou esparsos
  • Listas de regras ordenadas podem ser sensíveis à ordem das classes; classes minoritárias aprendidas por último podem receber regras mais fracas
  • Não produz estimativas de probabilidade calibradas, limitando o uso em tarefas sensíveis a custo ou de ranqueamento
  • Regras conjuntivas não podem capturar interações complexas que exigem fronteiras não alinhadas aos eixos sem engenharia de características

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Produz regras IF-THEN legíveis por humanos que especialistas do domínio podem auditar e validar
  • Aprendizado eficiente de separar e conquistar com poda guiada por MDL reduz o overfitting
  • Lida com atributos nominais e numéricos sem exigir pré-processamento extensivo
  • Tempo de treinamento geralmente rápido em comparação com métodos de ensemble para tamanhos moderados de dataset

Aplicações

  • Suporte à decisão clínica e extração de regras de diagnóstico médico
  • Detecção de fraudes e anomalias no monitoramento de transações financeiras
  • Categorização de texto usando características lexicais e estruturais
  • Detecção de intrusão em redes com regras de alerta interpretáveis
  • Previsão de churn de clientes com regras de negócio acionáveis

Como funciona

Como funciona

1

O RIPPER processa uma classe por vez, tratando todas as instâncias restantes como o conjunto negativo. Ele cresce gananciosamente uma regra conjuntiva adicionando repetidamente a condição que maximiza a razão de positivos para instâncias totais cobertas. Uma vez crescida, a regra é comprometida e todas as instâncias que ela cobre são removidas antes que a próxima regra seja aprendida, seguindo o paradigma clássico de separar e conquistar descrito por Cohen (1995).

Fórmula
\text{For each class } c \in \mathcal{C} \text{, grow a rule } R: \text{cond} \Rightarrow c \text{ maximizing } \frac{p}{p+n}
2

Cada regra candidata é podada em uma partição de validação separada usando a métrica (p - n) / (p + n), onde p e n contam instâncias corretamente e incorretamente cobertas, respectivamente. As condições são deletadas da cauda da regra para dentro, desde que a poda aumente este valor, protegendo contra overfitting causado por conjunções altamente específicas que se ajustam ao conjunto de treinamento.

Fórmula
\text{Prune rule } R \text{ by removing conditions to maximize } v(R, \text{prune set}) = \frac{p - n}{p + n}
3

Após todas as regras por classe serem aprendidas, o RIPPER executa uma passagem de otimização opcional guiada pelo princípio da Mínima Descrição (MDL). Para cada regra no conjunto final, o algoritmo considera substituí-la ou revisá-la e aceita a mudança apenas se ela reduzir o comprimento total de descrição do conjunto de regras e dos dados residuais mal classificados, balanceando precisão contra complexidade do modelo.

Fórmula
\text{Minimize description length: } DL(\text{ruleset}) + DL(\text{data} \mid \text{ruleset})
4

No momento da predição, as regras são aplicadas na ordem em que foram aprendidas. Uma instância não vista é atribuída ao rótulo da classe da primeira regra cujas condições são todas satisfeitas pelos valores das características dessa instância. Se nenhuma regra disparar, a instância cai em uma classe padrão (default), tipicamente a classe majoritária dos dados de treinamento, garantindo cobertura completa do espaço de entrada.

Fórmula
\hat{y} = c_k \text{ where } R_k \text{ is the first rule in the ordered list that fires on instance } \mathbf{x}

Erros comuns

  • Aplicar RIPPER a datasets pequenos sem dados suficientes para poda separada leva a regras super-podadas e de baixa cobertura
  • Ignorar o desbalanceamento de classes faz com que a classe padrão absorva a classe minoritária, mascarando a baixa recall da classe minoritária
  • Tratar a ordem das regras aprendidas como causal em vez de preditiva leva a interpretações errôneas em análises exploratórias
  • Pular a passagem de otimização MDL (disponível em algumas implementações) pode deixar regras redundantes ou conflitantes no conjunto final

Perguntas frequentes

Como o RIPPER difere de uma árvore de decisão?

Ambos aprendem fronteiras alinhadas aos eixos, mas árvores de decisão particionam recursivamente todo o espaço de características, produzindo uma estrutura hierárquica. O RIPPER, em vez disso, aprende uma lista ordenada de regras usando o método de separar e conquistar, o que pode gerar representações mais compactas quando apenas alguns padrões específicos da classe importam. As regras também são mais fáceis para especialistas do domínio lerem isoladamente do que caminhos de árvore.

O RIPPER pode lidar com problemas multiclasse?

Sim. O RIPPER se estende para configurações multiclasse aprendendo regras para cada classe por vez, ordenadas da classe mais rara para a mais frequente. Instâncias cobertas por regras para classes anteriores são removidas antes que as regras para classes posteriores sejam aprendidas. Uma regra padrão atribui a classe majoritária a qualquer instância não coberta pelas regras explícitas.

Qual o papel do princípio da Mínima Descrição (MDL) no RIPPER?

O MDL fornece um critério formal para balancear a complexidade das regras com o ajuste aos dados. Na fase de otimização, o RIPPER favorece conjuntos de regras cujo comprimento total de descrição — codificando tanto as regras quanto as instâncias mal classificadas — seja menor. Isso impede que o algoritmo retenha regras excessivamente específicas que memorizam ruído em vez de capturar padrões genuínos nos dados.

Métodos relacionados

Fontes

  1. Cohen, W. W. (1995). Fast effective rule induction. Proceedings of the 12th International Conference on Machine Learning, 115–123.

    Abrir referência DOI
    Copiado.