L'algorithme CN2 est une méthode d'induction de règles utilisée en apprentissage automatique pour les tâches de classification. Il génère un ensemble de règles si-alors à partir d'un jeu de données, où chaque règle consiste en une conjonction de conditions sur les valeurs d'attributs et une classe prédite. CN2 a été introduit en 1987 par Peter Clark et Tim Niblett à l'Institut Turing, s'appuyant sur des travaux antérieurs en apprentissage automatique et intelligence artificielle. L'algorithme est notable pour combiner la stratégie de recherche séparer-et-conquérir de la famille AQ avec les critères d'évaluation informationnels utilisés dans l'induction d'arbres de décision, tels que l'entropie. Il reste une approche fondamentale dans l'apprentissage symbolique de règles, offrant des modèles interprétables qui contrastent avec la nature opaque des méthodes réseaux de neurones et apprentissage profond.
L'algorithme fonctionne en recherchant itérativement la meilleure règle qui couvre un sous-ensemble des exemples d'entraînement, en supprimant ces exemples, puis en répétant le processus sur les données restantes. Cette stratégie séparer-et-conquérir, également connue sous le nom de couverture, distingue CN2 des algorithmes d'arbres de décision qui utilisent une approche diviser-pour-régner. CN2 peut produire soit une liste de règles ordonnée (liste de décision), soit un ensemble non ordonné de règles, selon la variante. La version originale génère une liste ordonnée, où les règles sont appliquées en séquence et la première règle correspondante détermine la prédiction. Des extensions ultérieures, telles que CN2-SD (Subgroup Discovery), ont adapté l'algorithme pour découvrir des sous-groupes intéressants plutôt que des classificateurs complets.
Recherche et évaluation
CN2 effectue une recherche en faisceau dans l'espace des conditions de règles. Partant d'une règle vide, il ajoute de manière répétée des conditions qui améliorent la qualité de la règle, en utilisant un paramètre de largeur de faisceau pour limiter le nombre de règles candidates considérées à chaque étape. La recherche est guidée par une fonction d'évaluation qui mesure la qualité d'une règle. Le CN2 original utilisait une mesure informationnelle basée sur l'entropie, similaire au critère de gain dans ID3. Plus précisément, l'algorithme évalue les règles en utilisant l'entropie de la distribution des classes parmi les exemples couverts, préférant les règles qui réduisent l'entropie. Des versions ultérieures ont introduit l'estimation de précision de Laplace pour éviter le surapprentissage, en particulier lors du traitement de petits échantillons. La correction de Laplace ajoute un pseudo-compte à chaque classe, fournissant une estimation plus robuste de la précision des règles.
La recherche en faisceau est de nature gloutonne, car elle ne fait pas de retour en arrière, mais la largeur du faisceau permet d'explorer simultanément plusieurs chemins prometteurs. Ce compromis entre gloutonnerie et exploration est une caractéristique clé de CN2. L'espace de recherche est défini par les paires attribut-valeur présentes dans les données, et les conditions sont généralement de la forme attribut = valeur pour les attributs nominaux ou attribut <= valeur et attribut >= valeur pour les attributs numériques, bien que l'algorithme original se concentre sur les données nominales.
Variantes de l'algorithme
Plusieurs variantes de CN2 ont été développées au fil des ans. La plus significative est CN2-SD, introduite à la fin des années 1990 par Nada Lavrač et ses collègues, qui déplace l'objectif de la classification vers la découverte de sous-groupes. Dans la découverte de sous-groupes, le but est de trouver des règles qui décrivent des sous-groupes de population intéressants avec des distributions de classes inhabituelles, plutôt que de construire un classificateur complet. CN2-SD utilise une mesure de précision relative pondérée pour évaluer les règles, équilibrant la généralité des règles et le caractère inhabituel de la distribution. Une autre variante, CN2-R, intègre des tests de randomisation pour évaluer la signification statistique des règles, filtrant les règles qui auraient pu apparaître par hasard. Cela aide à produire des ensembles de règles plus fiables et généralisables.
La variante non ordonnée de CN2 génère un ensemble de règles où chaque règle est apprise indépendamment, et pour la prédiction, toutes les règles sont appliquées et leurs prédictions sont combinées, souvent par vote ou en sélectionnant la règle avec la spécificité la plus élevée. Cette approche peut être plus robuste pour les ensembles de données avec des régions de classes qui se chevauchent. Le choix entre règles ordonnées et non ordonnées dépend de l'application ; les listes ordonnées sont plus simples et plus rapides, tandis que les ensembles non ordonnés peuvent offrir une meilleure couverture pour les classes rares.
Applications et impact
CN2 a été appliqué dans divers domaines, notamment le diagnostic médical, la détection de pannes et la modélisation écologique. Son interprétabilité le rend particulièrement précieux dans les domaines où la compréhension du processus de décision est cruciale, comme dans les soins de santé et la conformité réglementaire. Par exemple, dans les applications médicales, les règles CN2 peuvent être exprimées comme des conditions simples telles que si pression_artérielle > 140 et âge > 60 alors risque_élevé, que les cliniciens peuvent facilement vérifier. L'algorithme a également été utilisé comme référence pour comparer les approches symboliques et sub-symboliques en apprentissage automatique. Bien que les méthodes modernes comme apprentissage profond atteignent souvent une précision plus élevée sur des tâches complexes, CN2 reste pertinent pour les problèmes nécessitant des modèles transparents ou lorsque les données sont limitées.
L'influence de l'algorithme s'étend à des systèmes d'apprentissage de règles ultérieurs, tels que RIPPER et PART, qui ont adopté des stratégies de recherche et d'évaluation similaires. L'évaluation basée sur l'entropie de CN2 a été un précurseur de mesures informationnelles plus sophistiquées utilisées dans l'induction d'arbres de décision et la sélection de caractéristiques. Son cadre séparer-et-conquérir a été analysé théoriquement, avec des connexions au cadre d'apprentissage PAC et à la complexité de l'apprentissage de règles.
Limitations et extensions
CN2 présente des limitations connues. Il est sensible aux données bruitées, car la recherche gloutonne peut surapprendre des motifs parasites. La recherche en faisceau, bien que plus approfondie que l'escalade pure, peut encore manquer des règles optimales en raison de sa portée limitée. L'algorithme suppose que les attributs sont indépendants, ce qui peut ne pas tenir dans les données réelles. Des extensions ont abordé certains de ces problèmes. Par exemple, l'incorporation d'attributs continus par discrétisation, soit comme étape de prétraitement, soit dans la recherche, permet à CN2 de gérer des données numériques. L'utilisation de tests statistiques, comme dans CN2-R, atténue le surapprentissage. Des travaux plus récents ont intégré CN2 avec des méthodes d'ensemble, où plusieurs ensembles de règles sont combinés pour améliorer la robustesse.
Dans le contexte du apprentissage automatique moderne, CN2 est souvent contrasté avec les approches réseaux de neurones. Alors que les réseaux de neurones peuvent automatiquement apprendre des interactions complexes de caractéristiques, ils nécessitent de grandes quantités de données et sont difficiles à interpréter. CN2, en revanche, produit des règles compactes et lisibles par l'homme, mais peut avoir du mal avec des problèmes hautement dimensionnels ou fortement non linéaires. Ce compromis continue de stimuler la recherche sur des systèmes hybrides qui combinent des règles symboliques avec un apprentissage sub-symbolique, un sujet d'intérêt dans le domaine plus large de l'IA neuro-symbolique.
Implémentation et logiciels
CN2 est implémenté dans plusieurs bibliothèques d'apprentissage automatique. La suite de fouille de données Orange, développée à l'Université de Ljubljana, inclut un apprenant CN2, tout comme la boîte à outils Weka. Ces implémentations fournissent des interfaces conviviales pour appliquer l'algorithme à des ensembles de données réels. La simplicité de l'algorithme le rend facile à implémenter dans divers langages de programmation, et il est souvent utilisé comme exemple d'enseignement dans les cours sur le apprentissage automatique et la fouille de données. La disponibilité d'implémentations open source a contribué à son utilisation continue dans la recherche et l'éducation.
Malgré son introduction à la fin des années 1980, CN2 reste un algorithme pertinent dans la boîte à outils des praticiens de l'apprentissage automatique. Son accent sur l'interprétabilité et sa stratégie de recherche efficace assurent sa place dans l'histoire de l'IA, aux côtés d'autres méthodes symboliques qui précèdent la domination actuelle du apprentissage profond. Dans les années 2020, CN2 est encore cité dans la recherche sur l'apprentissage de règles et l'IA interprétable, et il sert de référence pour évaluer les nouvelles méthodes d'induction de règles.