Rangfolge der charakteristischen Merkmale in kombinierten Wrapper-Ansätzen zur Auswahl

Die im Rahmen der beschriebenen Forschung durchgeführten Experimente wurden in zwei Stufen durchgeführt. In der ersten Stufe wurde der im Wrapper-Modell angewendete Sequential Backward Elimination (SBE) -Algorithmus verwendet, um die Rangfolge charakteristischer Merkmale zu ermitteln und deren Relevanz aufzudecken. Der Wrapper wurde für zwei Arten von Klassifikatoren konstruiert, Minimal Cover Decision Algorithms (MCDA) abgeleitet in DRSA und künstliche neuronale Netze.

Die beiden erhaltenen Rankings wurden als nächstes in der zweiten Stufe verwendet, wo eine Reduktion von Attributen durchgeführt wurde, wiederum für regel- und konnektionistische Induktoren, während ihre Leistung beobachtet wurde. Die Eliminierung von Variablen für den DRSA-Klassifikator wurde in diesem Stadium auf zwei Arten ausgeführt: durch Verwerfen von Attributen und Induzieren neuer Regeln und Algorithmen und durch Ablehnen von Regeln aus dem zuvor generierten vollständigen Entscheidungsalgorithmus (FDA), wobei alle Regeln auf Beispiele für alle Merkmale geschlossen wurden berücksichtigt.

Die Prozeduren wurden auf zwei Datensatzpaare angewendet. Die primäre Klassifizierungsaufgabe war die binäre Autorenattribution mit stylometrischen Merkmalen. Zum Vergleich wurden die Tests auch für Wellenformdatensätze mit ähnlichen Eigenschaften (gleiche Anzahl von Klassen, vergleichbare Anzahl von Abtastwerten und Attributen) durchgeführt. Die Ergebnisse für diesen zweiten Datensatz finden Sie am Ende dieses Abschnitts.

Festlegung der Rangfolge von Merkmalen durch SBE

Da der DRSA-Klassifikator als Wrapper mit sequentieller Rückwärtsreduktion von Merkmalen verwendet werden sollte, bedeutete dies, mit dem vollständigen Satz von Attributen zu beginnen und jeweils ein Element zu eliminieren. Daher wäre die Induktion aller Regeln für Beispiele in jedem Fall unpraktisch, da es für 25 Merkmale im FDA-Algorithmus 62.383 Entscheidungsregeln für Bestandteile gab. Stattdessen wurden minimale Abdeckungsentscheidungsalgorithmen MCDA abgeleitet und ihre Leistung verwendet, um ein Attribut auszuwählen, von dem jeder die besten Ergebnisse im Vergleich zu anderen auf derselben Ebene lieferte. Die Details für alle Schritte sind in Tabelle 1 aufgeführt, wobei die Spalte ganz rechts (i) die etablierte DRSA-Rangfolge der charakteristischen Merkmale zeigt.

Die oberste Zeile der Tabelle entspricht der 0. Reduktionsstufe, d. h. dem Regelklassifikator, der für alle 25 untersuchten bedingten Attribute induziert wurde, die in Spalte (c) aufgeführt sind. Der generierte Algorithmus für die minimale Deckungsentscheidung bestand aus 30 konstituierende Regeln, das war auf nur begrenzt 6 während sie forderten, dass ihre minimale Unterstützung mindestens gleich ist 6. Die maximale Klassifizierungsgenauigkeit, die durch die auferlegte Einschränkung erzielt wurde, betrug 76,67% der korrekt erkannten Testproben. Die in der Tabelle angegebene Klassifizierungsgenauigkeit (und für alle anderen in diesem Artikel vorgestellten Fälle von Data Mining mit DRSA) bezieht sich nur auf Fälle, in denen alle Übereinstimmungsregeln korrekt klassifiziert wurden. Die mehrdeutigen Fälle widersprüchlicher Entscheidungen oder fehlender Übereinstimmungsregeln wurden immer als falsch behandelt (was ziemlich streng ist, aber die sonst erforderliche zusätzliche Verarbeitung einschränkt).

Als nächstes wurden 25 neue MCDA-Klassifikatoren mit jeweils 24 Eingabemerkmalen konstruiert, wobei ein Attribut eliminiert und ihre Leistung getestet und verglichen wurde. Von diesen Systemen lieferte dasjenige mit dem reduzierten Merkmal, das der Nutzungshäufigkeit für „und“ entspricht, das beste Ergebnis, so dass dieses Attribut als das am wenigsten relevante aller Kandidaten ausgewählt und als erstes eliminiert wird, wie in Spalte (i) der Tabelle angegeben.

Die Menge der 24 verbleibenden Variablen ergibt die Basis für die nächste Reduktionsstufe mit dem Index gleich 1, wie in Tabelle 1 in der zweiten Zeile gezeigt. Auch hier bestand der beste MCDA-Entscheidungsalgorithmus aus 30 Regeln, aber mit einer Unterstützung gleich oder höher als 2 gab es 17 Regeln mit einer maximalen Klassifizierung von 77,78%.

In Spalte (h) der Tabelle kann beobachtet werden, dass die Klassifizierungsgenauigkeit allmählich von 76,67 % auf maximal 91,11 % korrekt erkannte Stichproben ansteigt, wenn nur noch 5, 4 oder 3 Merkmale im Eingabesatz vorhanden sind, um dann für zwei bedingte Attribute auf 84,44 % und für ein einzelnes Attribut auf 61,11 % zu sinken.

Der Vorgang der Attributeliminierung kann so interpretiert werden, dass das System diese irrelevanten oder redundanten Elemente verwirft und diese, die für die Klassifizierung wesentlich sind, beibehält, wodurch die Klassifizierungsgenauigkeit entweder zunimmt oder zumindest auf dem gleichen Niveau liegt, jedoch für weniger Merkmale. Die Reihenfolge, in der die Attribute eliminiert werden, spiegelt ihre Wichtigkeit wider. Wenn diese Reihenfolge umgekehrt wird, nimmt die Leistung von DRSA-Klassifikatoren sofort und unwiederbringlich ab, was in Fig. 1.

Das gleiche sequentielle Rückwärtsreduktionsverfahren wurde als nächstes auf ANN-Klassifikatoren angewendet (Tabelle 2), beginnend mit dem Aufbau eines Netzwerks für alle 25 Merkmale. Für dieses Set lag die durchschnittliche Klassifizierungsgenauigkeit knapp über 91 %. Dieser Wert ist offensichtlich höher als für den Basis-DRSA-Klassifikator, für den er nur 76,67% betrug. Es ist jedoch zu beachten, dass die mehrdeutige Klassifizierung des regelbasierten Systems, von widersprüchlichen Entscheidungen oder keiner Regelübereinstimmung, in allen betrachteten Fällen als falsch behandelt wurde und diese geringere Vorhersagegenauigkeit beeinflusste. Darüber hinaus garantiert die Generierung von Entscheidungsalgorithmen mit minimaler Abdeckung nicht die Induktion der besten Regeln mit dem höchsten Potenzial für eine korrekte Klassifizierung, und es ist durchaus üblich, dass Entscheidungsalgorithmen, die mit anderen Ansätzen konstruiert wurden, signifikant besser testen, jedoch auf Kosten komplexerer Verfahren, mehr Rechenkosten und mehr Verarbeitungszeit .

Die positive Änderung des Klassifizierungsverhältnisses oder die gleiche Leistung bei weniger Eingaben ist nicht der einzige Indikator für Attributrelevanz oder Redundanz. Wenn ein Merkmal reduziert wird, wird auch die interne Struktur des Klassifikators entsprechend modifiziert. Für die DRSA-Verarbeitung bedeutet dies weniger konstituierende Regeln in einem Entscheidungsalgorithmus, während für ein künstliches neuronales Netzwerk seine Schichten durch Entfernen von Neuronen kleiner werden.

Wenn ein solches kleineres Netzwerk nicht schlechter als vor der Reduktion klassifiziert, bedeutet dies, dass die Relevanz der kürzlich verworfenen Eingabe vernachlässigbar ist und als redundant behandelt werden kann. Die Durchführung ist in Fig. 2, während Fig. 3 zeigt, was mit der Klassifizierungsgenauigkeit des Systems passiert, wenn die Eingabemerkmale reduziert werden, während die umgekehrte ANN-Rangfolge befolgt wird. Die beiden Graphen aus Fig. 2 und 3 zeigen die gleichen Trends, die in der zuvor aufgezeichneten Leistung von DRSA-Klassifikatoren in Fig. 1.

Wenn wir DRSA- und ANN-Rankings miteinander vergleichen und die allen Attributen zugewiesenen Scores analysieren, können wir feststellen, dass, obwohl beide Arten von Klassifikatoren mit denselben Datensätzen arbeiten, die resultierenden Ordnungen reduzierter Merkmale unterschiedlich sind, nur das letzte verbleibende Merkmal in beiden Rankings gleich ist: die Häufigkeit der Verwendung für „nicht“. Dies ist ein direktes Ergebnis der inhärenten Eigenschaften der Induktoren, die auf die mit ihrer Hilfe berechneten Werte übertragen werden.

Da Wrapper oft einer solchen Voreingenommenheit beschuldigt werden, müssen die erhaltenen Rankings bei der Reduzierung charakteristischer Merkmale für andere Klassifikationssysteme beobachtet werden, indem Wrapper desselben und eines anderen Typs kombiniert werden, um ihre Nützlichkeit durch Tests zu bewerten, was im nächsten Abschnitt erläutert wird.

Ranking von Features in ihrer Reduktion einsetzen

Der allgemeinen Kategorisierung von Feature-Selection-Ansätzen folgend, gehört Ranking mit Filtern dazu. In der vorgestellten Studie wurden zwei Rankings unter Verwendung von DRSA- und ANN-basierten Wrappern erhalten, die in den Spalten ganz rechts in den Tabellen 1 und 2 angegeben sind. Diese Ordnungen wurden als nächstes verwendet, um die bedingten Attribute aus dem ursprünglichen Satz von 25 herauszufiltern, um Eingabevariablen für neue Klassifikatoren zu eliminieren.

Die Einzelheiten der Anwendung des ANN-Rankings auf die Rückwärtsreduktion von Attributen in der DRSA-Verarbeitung, die zu einer Hybridlösung führt, sind in Tabelle 3 dargestellt. Erstens wurden Teilmengen von Merkmalen mit zunehmenden Kardinalitäten abgelehnt, und dann wurden für die verbleibenden Teilmengen neue Entscheidungsalgorithmen induziert, wobei nur eine minimale Abdeckung MCDA bereitgestellt wurde und auch alle Regeln auf die FDA abgeleitet wurden.

Da die Klassifizierungsgenauigkeit normalerweise als der wichtigste Faktor für die Qualität der erhaltenen Lösung behandelt wird, können wir unsere Aufmerksamkeit auf zwei (g) Spalten in Tabelle 3 oder ein Diagramm in Abb. 4. Sowohl für MCDA- als auch für FDA-Klassifikatoren gibt es mehrere Fälle verbesserter oder gleicher Leistung, wenn Merkmale reduziert werden, aber der Gewinn, der entweder in Bezug auf eine Anzahl von abgelehnten Merkmalen oder eine Erhöhung der Vorhersagegenauigkeit oder eine geringere Anzahl von Entscheidungsregeln betrachtet wird, die im Algorithmus verbleiben, ist nicht so hoch, wie es zuvor für einfache ANN- oder MCDA-Wrapper beobachtet wurde.

Anstatt bedingte Attribute zu reduzieren und dann neue Entscheidungsalgorithmen abzuleiten, was sehr zeitaufwändig sein kann, können wir diese Attribute auch eliminieren, indem wir Regeln mit Bedingungen verwerfen und alle Regeln für den zuvor induzierten Entscheidungsalgorithmus für alle Features einschränken . Ein solcher Ansatz kann als Ausführung des Rankings für Entscheidungsregeln betrachtet werden.

Zunächst wird jeder Regel im induzierten Algorithmus eine Punktzahl zugewiesen, die auf individuellen Punktzahlen für alle Attribute basiert, die im Prämiss-Teil der Regel enthalten sind. Aus all diesen Elementarwerten, die den konstituierenden Bedingungen entsprechen, wird die höchste ausgewählt, die das Attribut angibt, das als am wenigsten wichtig empfunden wird; Somit wird die erste eliminiert, und diese Punktzahl wird der Entscheidungsregel gegeben. Dann werden alle Regeln nach ihren Punktzahlen geordnet, und in jedem Reduktionsschritt werden alle Regeln mit einer bestimmten Punktzahl abgelehnt, was zu reduzierten Entscheidungsalgorithmen führt.

Die Einzelheiten dieses Entscheidungsregel-Rankingverfahrens sind in Tabelle 4 aufgeführt. Zum Vergleich sind auch Ergebnisse einer Algorithmusreduktion unter Befolgung des umgekehrten ANN-Rankings aufgeführt, die beide ebenfalls in Fig. 5.

Die Anwendung des ANN-Rankings bei der Reduzierung von FDA führt zu einer ziemlich starken Abnahme der Anzahl der verbleibenden Entscheidungsregeln, während die Klassifikatoren mit der gleichen oder nur geringfügig verringerten Genauigkeit vorhersagen. Das umgekehrte ANN-Ranking bringt eine viel langsamere Algorithmusreduktion mit sich, aber die Leistung wird sofort und irreparabel verschlechtert.

Da die Etablierung des DRSA-Rankings durch sequentielle Rückwärtseliminierung mit Erzeugung von minimalen Deckungsentscheidungsalgorithmen als separater Prozess behandelt wird, kann dieses Ranking auch im Verfahren des Decision Rule Rankings und der Reduktion verwendet werden, wobei alle Regeln auf den Algorithmus beschränkt werden, dessen Ergebnisse in Tabelle 5 und die Leistung in Abb. 6.

Die Tendenzen, die in der Vorhersagegenauigkeit für reduzierte Entscheidungsalgorithmen sichtbar sind, während sie dem DRSA-Ranking folgen, und seine Umkehrung erinnern direkt an diese, die zuvor im Wrapper-Modus beobachtet wurden, als das Ranking erstellt wurde. Die Verfahren ermöglichen es, diese Regeln aus einem Algorithmus herauszufiltern, der Bedingungen für irrelevante Attribute enthält, und Algorithmen mit deutlich verringerter Anzahl von Entscheidungsregeln zurückzugeben, während die Klassifizierungsgenauigkeit beibehalten oder sogar erhöht wird.

Als das DRSA-Ranking zur Reduzierung der Eingangscharakteristiken in das künstliche neuronale Netzwerk eingesetzt wurde, führte dies zu einer weiteren Hybridlösung. In jeder Eliminationsstufe wurde ein einzelnes Merkmal außer Acht gelassen und dessen Einfluss auf die Netzwerkleistung untersucht, wie in Fig. 7. Wenn das umgekehrte Ranking ausgenutzt wird (Abb. 8) zeigt ein Vergleich dieser beiden Graphen eine sehr große Ähnlichkeit mit dem in Fig. 1, veranschaulicht die Leistung von DRSA Wrapper unter Verwendung von SBE.

Von allen getesteten Kombinationen von Wrappern wurde die beste Leistung für ANN-Klassifikatoren mit DRSA-Ranking bei der Rückwärtseliminierung von Merkmalen angezeigt (Abb. 7). Gute Ergebnisse wurden auch bei der Reduzierung aller Regeln für den Algorithmus erzielt, der für alle Merkmale generiert wurde, während das DRSA-Ranking befolgt wurde (Tabelle 5; Abb. 6). In diesem Fall kann dies jedoch durch den Wrapper-Bias erklärt werden, wenn zwei Systeme desselben Typs mit denselben Eigenschaften kombiniert werden. Dasselbe kann nicht für den ersteren Fall angegeben werden, da die Unterschiede zwischen DRSA- und ANN-Klassifikatoren deutlich im beobachteten Prozess der sequentiellen Rückwärtseliminierung von Merkmalen gezeigt werden, was zu zwei deutlich unterschiedlichen Rankings führt.

Die Verwendung von ANN-Ranking bei der Rückwärtsattributreduktion und die anschließende Induktion neuer Regeln und Algorithmen für alle Regeln an Beispielen ermöglicht es, acht Variablen (32 %) zu verwerfen, bevor die Leistung abnimmt (Tabelle 3; Abb. 4). ANN Ranking in FDA Reduktion bringt auch Ablehnung von acht Variablen und so viele wie 51,888 Entscheidungsregeln (83 %). Die Anwendung umgekehrter Rankings, sowohl DRSA- als auch ANN-basiert, führte immer zu einer Verschlechterung der Leistung.

Ergebnisse für Wellenformdatensatz

Die Attribute für den Wellenformdatensatz sind im UCI ML Repository nicht detailliert beschrieben; daher wurden sie der Einfachheit halber einfach mit den Formen a1 bis a21 bezeichnet, und die beiden Entscheidungsklassen entsprachen den ausgewählten Wellentypen Typ 0 und Typ 1. Die beiden Rankings, die durch sequentielle Rückwärtselimination für DRSA- und ANN-Klassifikatoren erhalten wurden, sind in Tabelle 6 angegeben, mit Details zu induzierten Algorithmen und Leistung für beide Systeme, Dies ist auch für beide Arten von Klassifikationssystemen in Abb. 9.

Die Leistung der Klassifikatoren wird miteinander und mit dem Bezugspunkt verglichen, der aus den Vorhersagegenauigkeiten besteht, die für den gesamten Satz von 21 Attributen erhalten wurden. Minimaler Deckungsentscheidungsalgorithmus induziert klassifiziert nur 65 % mit 55 Regeln begrenzt auf 20 durch Einschränkungen der Unterstützung, um mindestens gleich zu sein 3. Alle Regeln auf Beispiele Algorithmus erreicht 74% Erkennungsrate (31.718 Regeln beschränkt auf 58 für die Unterstützung gleich oder höher als 48). ANN mit 21 Eingabemerkmalen erkannte 89% der Testmuster korrekt.

Wenn das DRSA-Ranking von Merkmalen zur systematischen Reduzierung der Eingaben in konnektionistische Klassifikatoren angewendet wird, kann in der Anfangsphase eine gewisse Leistungssteigerung beobachtet werden (siehe Abb. 10), aber der sichtbare Trend ist nicht streng monoton. Das gleiche Ranking wird auch für die Reduzierung ausgewählter Regeln aus allen Regeln des Algorithmus in den zuvor beschriebenen Verfahren verwendet, und in diesem Prozess können signifikante Gewinne beobachtet werden: Wir können 17 von 21 Attributen reduzieren (fast 81%) und haben dennoch eine erhöhte Leistung. Dies ist jedoch nicht überraschend, da beide Induktoren die gleichen allgemeinen Eigenschaften aufweisen, daher die resultierende Vorspannung.

Das Auferlegen eines Rankings für die DRSA-Verarbeitung erfolgt erneut auf zwei Arten: entweder werden für die allmählich abnehmenden Teilmengen von bedingten Attributen neue Entscheidungsregeln induziert (sowohl MCDA als auch FDA), oder der Regelsatz aus dem zuvor abgeleiteten vollständigen Entscheidungsalgorithmus wird analysiert und einige Regeln werden abgelehnt, wenn sie sich auf verworfene Merkmale beziehen. Die Einzelheiten aller resultierenden Lösungen sind in Tabelle 7 angegeben. Aus der beobachteten Leistung können wir erkennen, dass es für alle Regeln an Beispielen möglich ist, 13 von 21 bedingten Variablen (fast 62 %) abzulehnen, während nicht nur die Erkennung nicht schlechter, sondern erhöht ist.

Wenn alle Regeln für die Entscheidungsalgorithmen (ein neuer und der reduzierte) in jeder Phase verglichen werden, wird deutlich, dass sie tatsächlich sehr nahe beieinander liegen. Obwohl die Anzahl der beteiligten Regeln nicht immer genau gleich ist, ist die resultierende Klassifizierungsgenauigkeit nahezu identisch, was darauf hindeutet, den zweiten Weg zu wählen, dh die für den gesamten Satz von Merkmalen generierten Daten zu reduzieren, anstatt neue Algorithmen zu induzieren. Es erfordert deutlich weniger Aufwand, da der schwierige Teil der Berechnungen bereits ausgeführt wird. Sobald eine Methode zum Beschneiden von Regeln etabliert ist, könnte ihre Ausführung weniger anspruchsvoll sein als der Induktionsprozess.

Zum Vergleich wurden auch einige Tests für umgekehrte Rankings durchgeführt, wobei die geringsten Rankingattribute verworfen wurden, die Ergebnisse jedoch im Vergleich zur entsprechenden Lösung für die meisten Rankingvariablen schlechter waren, wobei die Unterschiede von der Anzahl der Elemente abhingen reduziert, oft mit zunehmendem Alter.

Alle durchgeführten Experimente, sowohl für stylometrische als auch für Wellenformdatensätze, bestätigen die Nützlichkeit der vorgeschlagenen Methode der Kombination von Wrappern zur Schätzung der Merkmalsrelevanz, die neben ihrer Rückwärtsreduktion verwendet wird.