imported>Leyo: Unsinnsformatierung

2026-04-12T23:42:58Z

Unsinnsformatierung

Neue Seite

{{Überarbeiten}}
Die '''Relief-Algorithmen''' sind eine Familie von Algorithmen zur [[Feature Selection]] für überwachte Lernmethoden des [[Maschinelles Lernen|maschinellen Lernens]] und werden seit 1992 entwickelt.

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 ''[[Attributsgewichtung|Instanz]]en'' erforderlich, die sich aus den Differenzen zwischen den ''[[Attributsgewichtung|Attribut]]en'' 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 [[Distanzfunktion|Manhattan-Distanz]] (die Summe aller Differenzbeträge).

== Ein einfaches Beispiel ==

Um die theoretischen Grundlagen von Anfang an anschaulicher zu machen, wird hier 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 [[Attributsgewichtung|Attribute]], von denen zwei 3 und die anderen 2 Werte annehmen können. Eine [[Attributsgewichtung|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 [[Attributsgewichtung|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. M muss ein Wetter sein, das nicht weit von I entfernt ist, bei dem aber gerade nicht mehr gespielt wird.

== Kurze Skizzierung der Funktionsweise von Relief ==
[[Datei:Relief Wiki.svg|mini|443x443px|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 [[Attributsgewichtung|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. Dabei ist k 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 u. U. auch mehr als zwei 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 einer 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

[[Kategorie:Maschinelles Lernen]]

Relief-Algorithmus - Versionsgeschichte

imported>Leyo: Unsinnsformatierung