El algoritmo CN2 es un método de inducción de reglas utilizado en aprendizaje automático para tareas de clasificación. Genera un conjunto de reglas si-entonces a partir de un conjunto de datos, donde cada regla consiste en una conjunción de condiciones sobre valores de atributos y una clase predicha. CN2 fue introducido en 1987 por Peter Clark y Tim Niblett en el Instituto Turing, basándose en trabajos previos en aprendizaje automático y inteligencia artificial. El algoritmo es notable por combinar la estrategia de búsqueda de separar-y-conquistar de la familia AQ con los criterios de evaluación basados en teoría de la información utilizados en la inducción de árboles de decisión, como la entropía. Sigue siendo un enfoque fundamental en el aprendizaje simbólico de reglas, ofreciendo modelos interpretables que contrastan con la naturaleza opaca de los métodos de red neuronal y aprendizaje profundo.
El algoritmo opera buscando iterativamente la mejor regla que cubra un subconjunto de los ejemplos de entrenamiento, eliminando esos ejemplos y repitiendo el proceso con los datos restantes. Esta estrategia de separar-y-conquistar, también conocida como cobertura, distingue a CN2 de los algoritmos de árboles de decisión que utilizan un enfoque de dividir-y-conquistar. CN2 puede producir una lista ordenada de reglas (lista de decisión) o un conjunto no ordenado de reglas, dependiendo de la variante. La versión original genera una lista ordenada, donde las reglas se aplican en secuencia y la primera regla que coincida determina la predicción. Extensiones posteriores, como CN2-SD (Descubrimiento de Subgrupos), adaptaron el algoritmo para descubrir subgrupos interesantes en lugar de clasificadores completos.
Búsqueda y Evaluación
CN2 realiza una búsqueda de haz a través del espacio de condiciones de reglas. Comenzando con una regla vacía, añade repetidamente condiciones que mejoran la calidad de la regla, utilizando un parámetro de ancho de haz para limitar el número de reglas candidatas consideradas en cada paso. La búsqueda está guiada por una función de evaluación que mide la calidad de una regla. El CN2 original utilizaba una medida basada en teoría de la información basada en la entropía, similar al criterio de ganancia en ID3. Específicamente, el algoritmo evalúa las reglas utilizando la entropía de la distribución de clases entre los ejemplos cubiertos, prefiriendo reglas que reduzcan la entropía. Versiones posteriores introdujeron la estimación de precisión de Laplace para evitar el sobreajuste, especialmente al tratar con muestras pequeñas. La corrección de Laplace añade un pseudo-conteo a cada clase, proporcionando una estimación más robusta de la precisión de la regla.
La búsqueda de haz es de naturaleza codiciosa, ya que no retrocede, pero el ancho de haz permite explorar múltiples caminos prometedores simultáneamente. Este equilibrio entre codicia y exploración es una característica clave de CN2. El espacio de búsqueda está definido por los pares atributo-valor presentes en los datos, y las condiciones son típicamente de la forma atributo = valor para atributos nominales o atributo <= valor y atributo >= valor para atributos numéricos, aunque el algoritmo original se centraba en datos nominales.
Variantes del Algoritmo
Se han desarrollado varias variantes de CN2 a lo largo de los años. La más significativa es CN2-SD, introducida a finales de la década de 1990 por Nada Lavrač y colegas, que cambia el objetivo de la clasificación al descubrimiento de subgrupos. En el descubrimiento de subgrupos, el objetivo es encontrar reglas que describan subgrupos de población interesantes con distribuciones de clases inusuales, en lugar de construir un clasificador completo. CN2-SD utiliza una medida de precisión relativa ponderada para evaluar reglas, equilibrando la generalidad de la regla y la rareza distribucional. Otra variante, CN2-R, incorpora pruebas de aleatorización para evaluar la significancia estadística de las reglas, filtrando reglas que podrían haber surgido por azar. Esto ayuda a producir conjuntos de reglas más fiables y generalizables.
La variante no ordenada de CN2 genera un conjunto de reglas donde cada regla se aprende de forma independiente, y para la predicción, se aplican todas las reglas y sus predicciones se combinan, a menudo mediante votación o seleccionando la regla con mayor especificidad. Este enfoque puede ser más robusto para conjuntos de datos con regiones de clases superpuestas. La elección entre reglas ordenadas y no ordenadas depende de la aplicación; las listas ordenadas son más simples y rápidas, mientras que los conjuntos no ordenados pueden proporcionar una mejor cobertura para clases raras.
Aplicaciones e Impacto
CN2 se ha aplicado en diversos dominios, incluyendo diagnóstico médico, detección de fallos y modelado ecológico. Su interpretabilidad lo hace particularmente valioso en campos donde comprender el proceso de decisión es crucial, como en la atención médica y el cumplimiento normativo. Por ejemplo, en aplicaciones médicas, las reglas de CN2 pueden expresarse como condiciones simples como si presión_arterial > 140 y edad > 60 entonces alto_riesgo, que los clínicos pueden verificar fácilmente. El algoritmo también se ha utilizado como punto de referencia para comparar enfoques simbólicos y sub-simbólicos en aprendizaje automático. Mientras que métodos modernos como aprendizaje profundo a menudo logran mayor precisión en tareas complejas, CN2 sigue siendo relevante para problemas que requieren modelos transparentes o cuando los datos son limitados.
La influencia del algoritmo se extiende a sistemas posteriores de aprendizaje de reglas, como RIPPER y PART, que adoptaron estrategias similares de búsqueda y evaluación. La evaluación basada en entropía de CN2 fue un precursor de medidas más sofisticadas basadas en teoría de la información utilizadas en la inducción de árboles de decisión y la selección de características. Su marco de separar-y-conquistar ha sido analizado teóricamente, con conexiones con el marco de aprendizaje PAC y con la complejidad del aprendizaje de reglas.
Limitaciones y Extensiones
CN2 tiene limitaciones conocidas. Es sensible a datos ruidosos, ya que la búsqueda codiciosa puede sobreajustarse a patrones espurios. La búsqueda de haz, aunque más exhaustiva que la escalada pura, puede perder reglas óptimas debido a su limitada capacidad de anticipación. El algoritmo asume que los atributos son independientes, lo que puede no cumplirse en datos del mundo real. Las extensiones han abordado algunos de estos problemas. Por ejemplo, la incorporación de atributos continuos mediante discretización, ya sea como paso de preprocesamiento o dentro de la búsqueda, permite a CN2 manejar datos numéricos. El uso de pruebas estadísticas, como en CN2-R, mitiga el sobreajuste. Trabajos más recientes han integrado CN2 con métodos de conjunto, donde se combinan múltiples conjuntos de reglas para mejorar la robustez.
En el contexto del aprendizaje automático moderno, CN2 a menudo se contrasta con los enfoques de red neuronal. Mientras que las redes neuronales pueden aprender automáticamente interacciones complejas de características, requieren grandes cantidades de datos y son difíciles de interpretar. CN2, por otro lado, produce reglas compactas y legibles por humanos, pero puede tener dificultades con problemas de alta dimensionalidad o altamente no lineales. Este equilibrio continúa impulsando la investigación en sistemas híbridos que combinan reglas simbólicas con aprendizaje sub-simbólico, un tema de interés en el campo más amplio de la IA neuro-simbólica.
Implementación y Software
CN2 está implementado en varias bibliotecas de aprendizaje automático. La suite de minería de datos Orange, desarrollada en la Universidad de Liubliana, incluye un aprendiz CN2, al igual que el kit de herramientas Weka. Estas implementaciones proporcionan interfaces fáciles de usar para aplicar el algoritmo a conjuntos de datos reales. La simplicidad del algoritmo facilita su implementación en varios lenguajes de programación, y a menudo se utiliza como ejemplo didáctico en cursos de aprendizaje automático y minería de datos. La disponibilidad de implementaciones de código abierto ha contribuido a su uso continuado en investigación y educación.
A pesar de haber sido introducido a finales de la década de 1980, CN2 sigue siendo un algoritmo relevante en el arsenal de los profesionales del aprendizaje automático. Su enfoque en la interpretabilidad y su eficiente estrategia de búsqueda aseguran su lugar en la historia de la IA, junto con otros métodos simbólicos que preceden al dominio actual del aprendizaje profundo. A partir de la década de 2020, CN2 todavía se cita en investigaciones sobre aprendizaje de reglas e IA interpretable, y sirve como línea base para evaluar métodos más nuevos de inducción de reglas.