2.3.5.5: Inkonsistente Trainingsdaten
Wird der ID3-Algorithmus auf eine inkonsistente Trainingsmenge
angewendet, bricht das Verfahren zusammen.
In diesem Fall existieren zwei Tupel
s=(s0,...,sn)
, t=(t0,...,tn
) T
, die auf den vorhersagenden Attributen
A0,...,Am-1
dieselben Werte haben, sich auf den vorherzusagenden
Attributen
Am,...,An
aber unterscheiden, für die
also gilt:
si=ti  i
{m,...,n}, j{
0,...,m-1} s.d.
sj tj
|
Diese beiden Tupel werden stets demselben Knoten zugeordnet.
Dadurch wird die
Beispielmenge dieses Knotens niemals nur Elemente einer Kategorie
enthalten und somit der
Algorithmus nicht enden. (Man sollte für diesen Fall ein weiteres Abbruchkriterium im zweiten Schritt
des Algorithmus einführen.) Datensammlungen können aus vielen Gründen inkonsistent sein:
- Die Attribute, mit denen die Dokumente in der Datenbank
repräsentiert werden, wurden nicht für die KDD-Aufgabe
entwickelt.
- Bei der manuellen Dateneingabe können
Tippfehler oder andere Eingabefehler
auftreten.
- Bei der manuellen Kategorisierung von Beispielen
können Unterschiede zwischen verschiedenen Personen oder
Eingabezeitpunkten auftreten.
- Wenn die Kategorisierung an
Objekten vorgenommen wurde und nicht an
den Daten-Tupeln, die mit den
Attributen berechnet wurden, kann es vorkommen, dass
Unterschiede, die zwischen
Objekten sichtbar waren, zwischen den zugehörigen Tupeln nicht sichtbar
sind. In diesem Fall muss entweder die Kategorisierung
an den Tupeln vorgenommen werden oder die
Attribute sind ungeeignet, um mit ihnen die
Kategorisierung der Objekte zu bestimmen.
- Schließlich ist es möglich, dass eine
Kategorisierung nicht die geeignete Fragestellung für
eine Datensammlung ist. Das kann z.B. bei
statistischen Daten über Objekte der Fall
sein, die lediglich Aussagen über die
Wahrscheinlichkeit zulassen, mit der ein Tupel in eine Kategorie
fällt.
Mit Inkonsistenzen in Trainingsdaten kann je nachdem, welche Ursache die Inkonsistenz hat,
unterschiedlich umgegangen werden (sofern die Ursachen überhaupt erschlossen werden können).
Handelt es sich um kleine Anzahlen unsystematischer Eingabefehler, können die
fehlerhaften Tupel aus der Trainingsmenge entfernt werden. Bei größeren Fehlerzahlen kann es
schwierig werden zu entscheiden, welche Einträge korrekt sind und welche fehlerhaft.
Bei systematischen Eingabefehlern kann die Repräsentativität der Trainingsmenge leiden.
Bei unterschiedlicher manueller Kategorisierung kann
versucht werden, die Gründe der Unterschiede, also
z.B. den Zeitpunkt der Kategorisierung oder die Person, die die
Kategorisierung durchgeführt hat, als
zusätzliches Attribut zu verwenden, um
so eine konsistente Kategorisierung zu erreichen.
Eine andere Möglichkeit besteht darin,
Kategorien, die zu Inkonsistenzen führen,
zusammenzulegen, sodass die Trainingsmenge
bezüglich der neuen Kategorisierung konsistent ist.
Theoretisch ist das immer möglich, da
man im schlimmsten Fall (der damit auch der am wenigsten nützliche
ist) nur noch eine einzige Kategorie übrig behält,
bezüglich der aber jede Trainingsmenge natürlich konsistent
ist. Es bleibt also im Einzelfall zu prüfen, ob eine solche vergröberte
Kategorisierung noch nützlich ist.
Ähnlich kann man auch im letzten Fall verfahren:
Datensammlungen, die in einer feinen Kategorisierung inkonsistent sind,
da eigentlich nur Wahrscheinlichkeitswerte über die
Zugehörigkeit zu einer bestimmten Kategorie vorliegen, können
für eine wesentlich gröbere Kategorisierung konsistent
sein. In vielen Fällen ist es aber
unzweckmäßig, die Trainingsmenge in eine deterministische Form
zu zwingen, weil sie dem Bereich, aus dem die Beispiele
stammen, nicht angemessen ist.
In diesen Fällen kann eine statistische Aussage, die
z.B. assoziative Regeln oder Wahrscheinlichkeiten für die Zugehörigkeit von
Beispielen zu verschiedenen Kategorien angibt, viel nützlicher
sein.
Die meisten KDD-Verfahren, die Kategorisierungsalgorithmen
konstruieren, setzen konsistente Trainingsmengen voraus.
Das heißt, Trainingsmengen müssen vor der Verwendung im KDD-Verfahren
auf Konsistenz geprüft werden und gegebenenfalls durch
eine geeignete Vorbehandlung
(preprocessing) in eine
konsistente Form gebracht werden. Bei diesem Vorgehen geht aber im Allgemeinen die
Information über die Inkonsistenzen, die ja in vielen Fällen
durchaus wichtig sein kann, verloren. Besser wäre es, Inkonsistenzen im
eigentlichen KDD-Algorithmus zu bearbeiten und soweit wie möglich auch zur
Beschreibung der Daten zu nutzen.
|
