Relief-Algorithmus

Die Relief-Algorithmen, eine Familie von Algorithmen zur Feature Selection für überwachte Lernmethoden des maschinellen Lernens, welche ab 1992 entwickelt wurden.

Es ist ein Werkzeug zur nachträglichen Untersuchung der Frage, welches Attribut den größten bzw. geringsten Einfluss auf die Ausgabe eines Modells hatte.

Für ihre Anwendung ist zunächst die Definition einer Entfernung zwischen zwei Instanzen erforderlich, die sich aus den Differenzen zwischen den Attributen für jede der Instanzen ergibt. Die Gesamtheit aller möglichen Instanzen wird auch als Instanzraum bezeichnet. Dieser ist i. A. kein Vektorraum im mathematischen Sinne, da gewöhnlich keine Vektoraddition sinnvoll definierbar ist, ebenso wenig die Multiplikation mit einer Zahl. Es ist aber sehr wohl ein metrischer Raum, da für je zwei Instanzen eine Entfernung (s. o.) definiert ist. Die Differenz der Attributwerte zweier Instanzen ist auch für nominale Werte definiert, nämlich (ursprünglich) als 0, falls die Instanzen in diesem Attribut übereinstimmen, und sonst als 1. Eine Möglichkeit die Entfernung zwischen den Instanzen zu berechnen ist die Manhattan-Distanz (die Summe aller Differenzbeträge).

Ein einfaches Beispiel

Um dem theoretischen „Gerippe“ von vornherein etwas „Fleisch“ hinzuzufügen, sei hier gleich zu Anfang ein einfaches Beispiel mit (nominalen) Attributen angefügt, um die Begriffe zu verdeutlichen:

|Attribute:	|Ausblick	|Temperatur	|Luftfeuchtigkeit	|windig	|Klasse:	|spielen
|mögl. Werte:	|sonnig	|kühl	|normal	|nein	|Kl.wert:	|ja
|	|veränderlich	|mild	|hoch	|ja	|	|nein
|	|regnerisch	|heiß

Es gibt hier 4 Attribute, von denen zwei 3 und die anderen 2 Werte annehmen können. Eine Instanz ist hier eine konkrete Wetterlage, und 3*3*2*2=36 verschiedene Wetterlagen sind in diesem Beispiel theoretisch möglich.

Der Entscheidungsprozess liefert zwei Möglichkeiten: Zielgröße ist die Entscheidung, ob bei einem Wetter draußen gespielt werden kann oder nicht; damit ergeben sich zwei Klassen von Beispielen (Instanzen): Jede Instanz gehört entweder der Klasse „spielen“ oder der Klasse „nicht spielen“ an. Die größte mögliche Entfernung zwischen zwei Instanzen ist in diesem Falle 4 für die Extremfälle. Wenn man als I ein Wetter wählt, bei dem draußen gespielt wird, muss H ein ähnliches Wetter sein, bei dem ebenfalls gespielt wird und M ein Wetter, das nicht weit von I entfernt ist, bei dem aber gerade nicht mehr gespielt wird.

Kurze Skizzierung der Funktionsweise von Relief

Illustration des Relief-Algorithmus

Die Relief-Algorithmen verändern die Gewichte jedes Attributes A in Abhängigkeit davon, wie groß die Differenzen benachbarter Instanzen sowohl gleicher als auch unterschiedlicher Klasse in A ist. Schließlich kann man an den Gewichten, die Relief einer Größe verliehen hat, deren Einfluss auf das Ergebnis eines Entscheidungsprozesses ablesen, den sogenannten Klassenwert einer Instanz. Im Falle des einfachsten Algorithmus, Relief, funktioniert das nur für zwei Klassen, das heißt die Zielgröße kann zwei Werte annehmen, und die Daten müssen vollständig sein. Zunächst pickt sich Relief eine Instanz I heraus und ermittelt dann deren nächste Nachbarn, einen aus der eigenen (nearest hit, also „nächster Treffer“ genannt und mit H bezeichnet) und einen aus der anderen Klasse (nearest miss, also „nächster Verfehler“, mit M bezeichnet). Die Gewichte aller Attribute, in denen die I mit H übereinstimmt oder mit M nicht übereinstimmt, werden erhöht, die Gewichte derer, in denen I sich von H unterscheidet oder mit M übereinstimmt, werden verringert. Falls die Attribute numerisch sind, hängt der Grad dieser Veränderung von der Differenz zwischen den Attributwerten ab.

Grenzen von Relief und seine Erweiterung

Voraussetzungen für die Anwendbarkeit von Relief ist, dass genau zwei Klassen definiert sind und keine Daten fehlen. Außerdem können auch verrauschte Daten die Aussagekraft des Algorithmus beeinträchtigen. In diesem Falle muss Relief erweitert werden. Solche Erweiterungen werden im Allgemeinen durch einen Großbuchstaben von A bis F gekennzeichnet:

ReliefA hat die gleichen Voraussetzungen wie Relief, sucht jedoch nicht nur nach je einem, sondern nach je k nächsten Nachbarn einer ausgewählten Instanz in deren und in der anderen Klasse. k ist dabei ein benutzerdefinierter Parameter.

ReliefB und ReliefC modifizieren die Definition für die (normierte) Differenz zwischen zwei Attributwerten. Somit kann man auch Instanzen einbeziehen, die für einzelne Attribute keinen bekannten Wert haben. Hier ist die Differenz zweier Instanzen in einem Attribut A als 1-1/(Zahl der Werte von A) definiert.

ReliefD stellt eine weitere Modifikation dar, bei der die Differenzfunktion noch etwas komplizierter, aber 'intelligenter' definiert ist. Dabei spielen bedingte Wahrscheinlichkeiten eine große Rolle, die nach den relativen Häufigkeiten von Attributwerten innerhalb der einzelnen Klassen geschätzt werden.

Schließlich kann auch der Klassenwert mehr als zwei, u. U. numerische Werte annehmen. In unserem Wetterbeispiel wäre es etwa möglich, neben der Entscheidung, ob man überhaupt draußen spielen will, auch die Möglichkeit zuzulassen, wie lange man spielt. In diesem Falle kann ein Algorithmus entweder nach dem Zufallsprinzip einen nächsten Nachbarn aus irgendeiner der anderen Klassen auswählen (so macht es ReliefE) und wie gehabt einen aus derselben Klasse, oder er sucht für eine gewählte Instanz aus jeder der k anderen Klassen einen und aus der eigenen k nächste Nachbarn (so macht es ReliefF).

Literatur

• M. Robnik-Sikonja, I. Kononenko: Theoretical and empirical analysis of ReliefF and RReliefF. Machine Learning, 53(1-2):23.69, 2003. doi 10.1023/A:1025667309714
• Ian H. Witten, E. Frank: Data Mining, Praktische Werkzeuge und Techniken für das maschinelle Lernen, Carl Hanser Verlag München Wien, 2001
• Qi Zhong: Using RELIEF to select Features on Mice Gene Data, Machine Learning, Winter 2004