O algoritmo CN2 é um método de indução de regras utilizado em aprendizado de máquina para tarefas de classificação. Ele gera um conjunto de regras do tipo "se-então" a partir de um conjunto de dados, onde cada regra consiste em uma conjunção de condições sobre valores de atributos e uma classe prevista. O CN2 foi introduzido em 1987 por Peter Clark e Tim Niblett no Instituto Turing, com base em trabalhos anteriores em aprendizado de máquina e inteligência artificial. O algoritmo é notável por combinar a estratégia de busca "separar-e-conquistar" da família AQ com os critérios de avaliação baseados em teoria da informação usados na indução de árvores de decisão, como a entropia. Ele permanece uma abordagem fundamental na aprendizagem de regras simbólicas, oferecendo modelos interpretáveis que contrastam com a natureza opaca dos métodos de rede neural e aprendizado profundo.
O algoritmo opera buscando iterativamente a melhor regra que cobre um subconjunto dos exemplos de treinamento, removendo esses exemplos e repetindo o processo nos dados restantes. Essa estratégia de "separar-e-conquistar", também conhecida como cobertura, distingue o CN2 dos algoritmos de árvore de decisão que usam uma abordagem de "dividir-e-conquistar". O CN2 pode produzir tanto uma lista ordenada de regras (lista de decisão) quanto um conjunto não ordenado de regras, dependendo da variante. A versão original gera uma lista ordenada, onde as regras são aplicadas em sequência e a primeira regra correspondente determina a previsão. Extensões posteriores, como o CN2-SD (Descoberta de Subgrupos), adaptaram o algoritmo para descobrir subgrupos interessantes em vez de classificadores completos.
Busca e Avaliação
O CN2 realiza uma busca em feixe pelo espaço de condições de regras. Começando com uma regra vazia, ele adiciona repetidamente condições que melhoram a qualidade da regra, usando um parâmetro de largura de feixe para limitar o número de regras candidatas consideradas em cada etapa. A busca é guiada por uma função de avaliação que mede a qualidade de uma regra. O CN2 original usava uma medida baseada em teoria da informação, baseada na entropia, semelhante ao critério de ganho do ID3. Especificamente, o algoritmo avalia regras usando a entropia da distribuição de classes entre os exemplos cobertos, preferindo regras que reduzem a entropia. Versões posteriores introduziram a estimativa de precisão de Laplace para evitar sobreajuste, especialmente ao lidar com amostras pequenas. A correção de Laplace adiciona uma pseudo-contagem a cada classe, fornecendo uma estimativa mais robusta da precisão da regra.
A busca em feixe é de natureza gulosa, pois não faz retrocesso, mas a largura do feixe permite a exploração simultânea de múltiplos caminhos promissores. Esse trade-off entre gulodice e exploração é uma característica chave do CN2. O espaço de busca é definido pelos pares atributo-valor presentes nos dados, e as condições são tipicamente da forma atributo = valor para atributos nominais ou atributo <= valor e atributo >= valor para atributos numéricos, embora o algoritmo original se concentrasse em dados nominais.
Variantes do Algoritmo
Várias variantes do CN2 foram desenvolvidas ao longo dos anos. A mais significativa é o CN2-SD, introduzido no final dos anos 1990 por Nada Lavrač e colegas, que muda o objetivo da classificação para a descoberta de subgrupos. Na descoberta de subgrupos, o objetivo é encontrar regras que descrevam subgrupos populacionais interessantes com distribuições de classes incomuns, em vez de construir um classificador completo. O CN2-SD usa uma medida de precisão relativa ponderada para avaliar regras, equilibrando a generalidade da regra e a incomumidade da distribuição. Outra variante, o CN2-R, incorpora testes de randomização para avaliar a significância estatística das regras, filtrando regras que poderiam ter surgido por acaso. Isso ajuda a produzir conjuntos de regras mais confiáveis e generalizáveis.
A variante não ordenada do CN2 gera um conjunto de regras onde cada regra é aprendida independentemente, e para previsão, todas as regras são aplicadas e suas previsões são combinadas, frequentemente por votação ou selecionando a regra com maior especificidade. Essa abordagem pode ser mais robusta para conjuntos de dados com regiões de classes sobrepostas. A escolha entre regras ordenadas e não ordenadas depende da aplicação; listas ordenadas são mais simples e rápidas, enquanto conjuntos não ordenados podem fornecer melhor cobertura para classes raras.
Aplicações e Impacto
O CN2 foi aplicado em vários domínios, incluindo diagnóstico médico, detecção de falhas e modelagem ecológica. Sua interpretabilidade o torna particularmente valioso em campos onde entender o processo de decisão é crucial, como em saúde e conformidade regulatória. Por exemplo, em aplicações médicas, as regras do CN2 podem ser expressas como condições simples, como se pressão_arterial > 140 e idade > 60 então alto_risco, que os clínicos podem verificar facilmente. O algoritmo também tem sido usado como referência para comparar abordagens simbólicas e subsimbólicas em aprendizado de máquina. Embora métodos modernos como aprendizado profundo frequentemente alcancem maior precisão em tarefas complexas, o CN2 permanece relevante para problemas que exigem modelos transparentes ou quando os dados são limitados.
A influência do algoritmo se estende a sistemas posteriores de aprendizagem de regras, como RIPPER e PART, que adotaram estratégias semelhantes de busca e avaliação. A avaliação baseada em entropia do CN2 foi um precursor de medidas mais sofisticadas de teoria da informação usadas na indução de árvores de decisão e seleção de características. Seu framework de "separar-e-conquistar" foi analisado teoricamente, com conexões com o framework PAC-learning e com a complexidade da aprendizagem de regras.
Limitações e Extensões
O CN2 tem limitações conhecidas. Ele é sensível a dados ruidosos, pois a busca gulosa pode sobreajustar padrões espúrios. A busca em feixe, embora mais completa que a escalada pura, ainda pode perder regras ótimas devido ao seu horizonte limitado. O algoritmo assume que os atributos são independentes, o que pode não ser verdadeiro em dados do mundo real. Extensões abordaram alguns desses problemas. Por exemplo, incorporar atributos contínuos por meio de discretização, seja como etapa de pré-processamento ou dentro da busca, permite que o CN2 lide com dados numéricos. O uso de testes estatísticos, como no CN2-R, mitiga o sobreajuste. Trabalhos mais recentes integraram o CN2 com métodos de conjunto, onde múltiplos conjuntos de regras são combinados para melhorar a robustez.
No contexto do aprendizado de máquina moderno, o CN2 é frequentemente contrastado com abordagens de rede neural. Enquanto as redes neurais podem aprender automaticamente interações complexas de características, elas exigem grandes quantidades de dados e são difíceis de interpretar. O CN2, por outro lado, produz regras compactas e legíveis por humanos, mas pode ter dificuldades com problemas de alta dimensionalidade ou altamente não lineares. Esse trade-off continua a impulsionar pesquisas em sistemas híbridos que combinam regras simbólicas com aprendizado subsimbólico, um tópico de interesse no campo mais amplo da IA neuro-simbólica.
Implementação e Software
O CN2 é implementado em várias bibliotecas de aprendizado de máquina. O pacote de mineração de dados Orange, desenvolvido na Universidade de Ljubljana, inclui um aprendiz CN2, assim como o kit de ferramentas Weka. Essas implementações fornecem interfaces amigáveis para aplicar o algoritmo a conjuntos de dados reais. A simplicidade do algoritmo facilita sua implementação em várias linguagens de programação, e ele é frequentemente usado como exemplo de ensino em cursos de aprendizado de máquina e mineração de dados. A disponibilidade de implementações de código aberto contribuiu para seu uso contínuo em pesquisa e educação.
Apesar de ter sido introduzido no final dos anos 1980, o CN2 permanece um algoritmo relevante no arsenal de praticantes de aprendizado de máquina. Seu foco em interpretabilidade e sua estratégia de busca eficiente garantem seu lugar na história da IA, ao lado de outros métodos simbólicos que precedem o domínio atual do aprendizado profundo. A partir dos anos 2020, o CN2 ainda é citado em pesquisas sobre aprendizagem de regras e IA interpretável, e serve como base para avaliar métodos mais novos de indução de regras.