Relief-Algorithmus

Die Relief-Algorithmen, einer Familie von Algorithmen zur Attributsgewichtung, gehören zu den überwachten Lernmethoden des maschinellen Lernens. Zunächst einmal bezieht sich der Relief-Algorithmus nicht auf künftige Entscheidungsprozesse, sondern ist ein Werkzeug zur nachträglichen Untersuchung der Frage, welches Attribut den größten bzw. geringsten Einfluss auf die Entscheidung hatte. Besonders nützlich wird das dann, wenn Entscheidungen nicht willkürlich fallen, sondern in technischen Zusammenhängen physikalische, chemische oder andere Größen zu einem bestimmten Versuchsergebnis führen, was also wichtig ist, und was nicht. Aus der Attributsgewichtung mit einem der Relief-Algorithmen kann man nämlich dann Schlüsse von bereits durchgeführten Entscheidungsprozessen (z. B. Versuchen) auf ähnliche Prozesse (mit anderen Attributwerten) ziehen, somit unter Umständen deren Durchführung überflüssig manchen und damit Geld und Arbeitsaufwand einsparen. 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. Der in diesem Zusammenhang wesentliche Begriff der Instanz hat hier nichts mit Justiz zu tun, sondern ist, vielleicht etwas unglücklich, aus engl. instance für „Beispiel“ entlehnt und als Fachwort in die Sprache des Data-Mining eingegangen und bezeichnet ein Objekt. 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. Als Entfernung zwischen den Instanzen braucht man in der Regel nur die sogenannte Manhattan-Distanz zu verwenden, das heißt 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

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 so genannten 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 ist 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

[1] M. Robnik-Sikonja, I. Kononenko: Theoretical and empirical analysis of ReliefF and RReliefF. Machine Learning, 53(1-2):23.69, 2003

[2] Ian H. Witten, E. Frank: Data Mining, Praktische Werkzeuge und Techniken für das maschinelle Lernen, Carl Hanser Verlag München Wien, 2001
[3] Qi Zhong: Using RELIEF to select Features on Mice Gene Data, Machine Learning, Winter 2004