Der CN2-Algorithmus ist eine Regelinduktionsmethode, die im maschinellen Lernen für Klassifikationsaufgaben eingesetzt wird. Er erzeugt aus einem Datensatz eine Menge von Wenn-Dann-Regeln, wobei jede Regel aus einer Konjunktion von Bedingungen über Attributwerten und einer vorhergesagten Klasse besteht. CN2 wurde 1987 von Peter Clark und Tim Niblett am Turing Institute eingeführt und baut auf früheren Arbeiten im Bereich maschinelles Lernen und künstliche Intelligenz auf. Der Algorithmus zeichnet sich dadurch aus, dass er die Separate-and-Conquer-Suchstrategie der AQ-Familie mit informationstheoretischen Bewertungskriterien aus der Entscheidungsbauminduktion, wie etwa Entropie, kombiniert. Er bleibt ein grundlegender Ansatz im symbolischen Regellernen und bietet interpretierbare Modelle, die im Gegensatz zur opaken Natur von neuronalen Netzen und Deep-Learning-Methoden stehen.
Der Algorithmus funktioniert iterativ, indem er nach der besten Regel sucht, die eine Teilmenge der Trainingsbeispiele abdeckt, diese Beispiele entfernt und den Prozess mit den verbleibenden Daten wiederholt. Diese Separate-and-Conquer-Strategie, auch als Covering bekannt, unterscheidet CN2 von Entscheidungsbaumalgorithmen, die einen Divide-and-Conquer-Ansatz verwenden. CN2 kann je nach Variante entweder eine geordnete Regelliste (Entscheidungsliste) oder eine ungeordnete Regelmenge erzeugen. Die ursprüngliche Version erzeugt eine geordnete Liste, bei der Regeln sequenziell angewendet werden und die erste passende Regel die Vorhersage bestimmt. Spätere Erweiterungen, wie CN2-SD (Subgroup Discovery), passten den Algorithmus an, um interessante Untergruppen statt vollständiger Klassifikatoren zu entdecken.
Suche und Bewertung
CN2 führt eine Strahlensuche (Beam Search) durch den Raum der Regelbedingungen durch. Ausgehend von einer leeren Regel fügt es wiederholt Bedingungen hinzu, die die Qualität der Regel verbessern, wobei ein Strahlenbreitenparameter die Anzahl der Kandidatenregeln begrenzt, die in jedem Schritt berücksichtigt werden. Die Suche wird durch eine Bewertungsfunktion gesteuert, die die Qualität einer Regel misst. Das ursprüngliche CN2 verwendete ein informationstheoretisches Maß auf Basis der Entropie, ähnlich dem Gain-Kriterium in ID3. Konkret bewertet der Algorithmus Regeln anhand der Entropie der Klassenverteilung unter den abgedeckten Beispielen und bevorzugt Regeln, die die Entropie reduzieren. Spätere Versionen führten die Laplace-Accuracy-Schätzung ein, um Überanpassung zu vermeiden, insbesondere bei kleinen Stichproben. Die Laplace-Korrektur fügt jeder Klasse eine Pseudo-Zählung hinzu und liefert so eine robustere Schätzung der Regelgenauigkeit.
Die Strahlensuche ist von Natur aus gierig, da sie kein Backtracking durchführt, aber die Strahlenbreite ermöglicht die gleichzeitige Erkundung mehrerer vielversprechender Pfade. Dieser Kompromiss zwischen Gierigkeit und Exploration ist ein zentrales Merkmal von CN2. Der Suchraum wird durch die im Datensatz vorhandenen Attribut-Wert-Paare definiert, und Bedingungen haben typischerweise die Form Attribut = Wert für nominale Attribute oder Attribut <= Wert und Attribut >= Wert für numerische Attribute, wobei sich der ursprüngliche Algorithmus auf nominale Daten konzentrierte.
Algorithmusvarianten
Im Laufe der Jahre wurden mehrere Varianten von CN2 entwickelt. Die bedeutendste ist CN2-SD, das Ende der 1990er Jahre von Nada Lavrač und Kollegen eingeführt wurde und das Ziel von der Klassifikation zur Untergruppenentdeckung verschiebt. Bei der Untergruppenentdeckung geht es darum, Regeln zu finden, die interessante Bevölkerungsuntergruppen mit ungewöhnlichen Klassenverteilungen beschreiben, anstatt einen vollständigen Klassifikator zu erstellen. CN2-SD verwendet ein gewichtetes relatives Genauigkeitsmaß zur Bewertung von Regeln, das die Allgemeinheit der Regel und die Ungewöhnlichkeit der Verteilung ausbalanciert. Eine weitere Variante, CN2-R, integriert Randomisierungstests, um die statistische Signifikanz von Regeln zu bewerten und Regeln herauszufiltern, die rein zufällig entstanden sein könnten. Dies trägt zur Erzeugung zuverlässigerer und generalisierbarerer Regelmengen bei.
Die ungeordnete Variante von CN2 erzeugt eine Regelmenge, bei der jede Regel unabhängig gelernt wird, und für die Vorhersage werden alle Regeln angewendet und ihre Vorhersagen kombiniert, oft durch Abstimmung oder durch Auswahl der Regel mit der höchsten Spezifität. Dieser Ansatz kann für Datensätze mit überlappenden Klassenregionen robuster sein. Die Wahl zwischen geordneten und ungeordneten Regeln hängt von der Anwendung ab; geordnete Listen sind einfacher und schneller, während ungeordnete Mengen eine bessere Abdeckung für seltene Klassen bieten können.
Anwendungen und Auswirkungen
CN2 wurde in verschiedenen Bereichen angewendet, darunter medizinische Diagnose, Fehlererkennung und ökologische Modellierung. Seine Interpretierbarkeit macht es besonders wertvoll in Bereichen, in denen das Verständnis des Entscheidungsprozesses entscheidend ist, wie im Gesundheitswesen und bei regulatorischen Anforderungen. In medizinischen Anwendungen können CN2-Regeln beispielsweise als einfache Bedingungen wie wenn Blutdruck > 140 und Alter > 60 dann hohes_Risiko ausgedrückt werden, die Kliniker leicht überprüfen können. Der Algorithmus wurde auch als Benchmark für den Vergleich symbolischer und subsymbolischer Ansätze im maschinellen Lernen verwendet. Während moderne Methoden wie Deep Learning bei komplexen Aufgaben oft höhere Genauigkeit erzielen, bleibt CN2 für Probleme relevant, die transparente Modelle erfordern oder wenn Daten begrenzt sind.
Der Einfluss des Algorithmus erstreckt sich auf spätere Regellernsysteme wie RIPPER und PART, die ähnliche Such- und Bewertungsstrategien übernahmen. CN2s entropiebasierte Bewertung war ein Vorläufer für ausgefeiltere informationstheoretische Maße, die in der Entscheidungsbauminduktion und Merkmalsauswahl verwendet werden. Sein Separate-and-Conquer-Framework wurde theoretisch analysiert, mit Verbindungen zum PAC-Lernframework und zur Komplexität des Regellernens.
Einschränkungen und Erweiterungen
CN2 hat bekannte Einschränkungen. Es ist empfindlich gegenüber verrauschten Daten, da die gierige Suche zu Überanpassung an scheinbare Muster führen kann. Die Strahlensuche, obwohl gründlicher als reines Hill-Climbing, kann aufgrund ihrer begrenzten Vorausschau optimale Regeln übersehen. Der Algorithmus nimmt an, dass Attribute unabhängig sind, was in realen Daten möglicherweise nicht zutrifft. Erweiterungen haben einige dieser Probleme adressiert. Die Integration kontinuierlicher Attribute durch Diskretisierung, entweder als Vorverarbeitungsschritt oder innerhalb der Suche, ermöglicht es CN2, numerische Daten zu verarbeiten. Die Verwendung statistischer Tests, wie in CN2-R, mildert Überanpassung. Neuere Arbeiten haben CN2 mit Ensemble-Methoden integriert, bei denen mehrere Regelmengen kombiniert werden, um die Robustheit zu verbessern.
Im Kontext des modernen maschinellen Lernens wird CN2 oft mit neuronalen Netzwerk-Ansätzen kontrastiert. Während neuronale Netze automatisch komplexe Merkmalsinteraktionen lernen können, benötigen sie große Datenmengen und sind schwer zu interpretieren. CN2 hingegen erzeugt kompakte, menschenlesbare Regeln, kann aber bei hochdimensionalen oder stark nichtlinearen Problemen Schwierigkeiten haben. Dieser Kompromiss treibt weiterhin die Forschung an hybriden Systemen voran, die symbolische Regeln mit subsymbolischem Lernen kombinieren, ein Thema von Interesse im breiteren Feld der neuro-symbolischen KI.
Implementierung und Software
CN2 ist in mehreren Bibliotheken für maschinelles Lernen implementiert. Die an der Universität Ljubljana entwickelte Orange-Data-Mining-Suite enthält einen CN2-Learner, ebenso wie das Weka-Toolkit. Diese Implementierungen bieten benutzerfreundliche Schnittstellen zur Anwendung des Algorithmus auf reale Datensätze. Die Einfachheit des Algorithmus macht es leicht, ihn in verschiedenen Programmiersprachen zu implementieren, und er wird oft als Lehrbeispiel in Kursen zu maschinellem Lernen und Data Mining verwendet. Die Verfügbarkeit von Open-Source-Implementierungen hat zu seiner fortgesetzten Nutzung in Forschung und Bildung beigetragen.
Trotz seiner Einführung Ende der 1980er Jahre bleibt CN2 ein relevanter Algorithmus im Werkzeugkasten von Praktikern des maschinellen Lernens. Sein Fokus auf Interpretierbarkeit und seine effiziente Suchstrategie sichern seinen Platz in der Geschichte der KI, neben anderen symbolischen Methoden, die vor der aktuellen Dominanz des Deep Learning entstanden. In den 2020er Jahren wird CN2 weiterhin in der Forschung zu Regellernen und interpretierbarer KI zitiert und dient als Baseline für die Bewertung neuerer Regelinduktionsmethoden.