2.3.5.1: Konsistenz
Beim ID3-Algorithmus wurde vorausgesetzt, dass die Beispiele
der Trainingsmenge
konsistent
sind. Allgemein lässt sich das so definieren:
Gibt es nur ein vorherzusagendes Attribut, sagt die Definition,
dass dessen Werte innerhalb der Beispielsammlung durch die der
vorhersagenden Attribute eindeutig bestimmt sein müssen. Das bedeutet, dass
nicht zwei Tupel, die für alle vorhersagenden Attributen gleiche Werte
haben, in verschiedenen Kategorien liegen dürfen. Das wurde bereits
bei der Definition der Kategorisierung gefordert.
Aus der Definition folgt daher unmittelbar:
Im einfachsten Fall ist dieser Algorithmus eine Aufzählung der
Beispiele. Ob mit dem Kategorisierungsalgorithmus auch neue Beispiele kategorisiert
werden können, hängt von der Definition der Attribute ab:
Wegen der Endlichkeit der Beispielmenge kann man annehmen, dass
die Wertebereiche der Attribute endlich sind. Wenn ein Algorithmus, der
mit einer Beispielmenge konstruiert wurde, zur Kategorisierung neuer Beispiele
verwendet werden soll, können die Attribute in den neuen Beispielen eventuell Werte annehmen, die
nicht in der Beispielmenge aufgetreten sind. In diesem Fall ist es sinnvoll
dafür zu sorgen, dass die Wertemengen der Attribute von vornherein endlich sind.
Bei reellen Zahlen kann das z.B. dadurch erreicht werden, dass Intervalle als
Wertebereiche gewählt werden (siehe auch Abschnitt 2.3.5.3
).
Endlichkeit des ID3 auf konsistenten Trainingsdaten
Bei einer (endlichen) konsistenten Trainingsmenge
wird in jedem Knoten des Baums ein Attribut
getestet, und die Tupel werden gemäß ihres
Werts in diesem Attribut aufgeteilt.
Jedes Attribut kann in einem Ast des Baums also
höchstens einmal auftreten, da sonst die Forderung,
dass es zwei verschiedene Werte innerhalb der
Beispielmenge des Knotens annehmen muss, nicht mehr
erfüllt ist. Spätestens, wenn alle
Attribute abgearbeitet sind, haben sämtliche Tupel in diesem Endknoten
des Baums auf allen vorhersagenden
Attributen identische Werte. Wegen der Konsistenz
handelt es sich also um genau ein Tupel, das natürlich
nur zu einer Kategorie gehört.
|
Definition 12: Konsistenz