2.3.5.7: Größe und Repräsentativität der Trainingsmenge

Datenbanken enthalten häufig sehr viele Einträge. Weiter ist die Anzahl der möglichen Daten-Tupel, die sich als kartesisches Produkt der Wertebereiche der Attribute ergibt, im Allgemeinen sehr groß. Ähnlich wie bei der in Abschnitt 1.3.7.5 beschriebenen Auswahl von Testkollektionen stellt sich daher auch bei Trainingsmengen das Problem, wie eine handhabbare, aber doch ausreichend große Menge an Beispielen zusammengestellt werden kann. Anders als bei den Testkollektionen muss dabei zwischen zwei unterschiedlichen Gesichtspunkten unterschieden werden: Dem Abdecken möglichst vieler Fälle und der Repräsentativität der Häufigkeiten, mit denen die Fälle auftreten. Wie oben gezeigt wurde, gibt es zu jeder endlichen, konsistenten Trainingsmenge ein Verfahren, mit dem ein Kategorisierungsalgorithmus konstruiert werden kann. Das ist unabhängig von der Häufigkeit, mit der die Tupel in der Trainingsmenge auftreten.

Andererseits kann die Häufigkeit, mit der Tupel mit gleichen Attributwerten in der Trainingsmenge auftreten, Einfluss auf die Konstruktion des Algorithmus haben. So beeinflusst diese Häufigkeit beim ID3-Algorithmus über den Entropiewert die Auswahl der Attribute, nach denen die Beispielmengen aufgeteilt werden. Die Effizienz des gefundenen Kategorisierungsalgorithmus hängt also sehr wohl von der Häufigkeit der Tupel und damit von der diesbezüglichen Repräsentativität der Trainingsmenge ab. Bei anderen KDD-Verfahren, die keine Kategorisierung anstreben, sondern beispielsweise statistische Aussagen über Datenbestände machen, hängt die "Richtigkeit" des Verfahrens natürlich noch stärker oder völlig von der Repräsentativität der Häufigkeiten ab.

Da bei einer größeren Anzahl von Attributen mit eventuell zahlreichen möglichen Werten die Anzahl der Beispiele in einer repräsentativen Trainingsmenge sehr schnell sehr groß und damit nicht mehr handhabbar wird, müssen häufig andere Methoden verwendet werden, um eine geeignete Trainingsmenge zu konstruieren. Eine entscheidende Beobachtung für die Entwicklung solcher Methoden ist, dass der Aufwand für die Anwendung des Kategorisierungsalgorithmus auf ein Beispiel im Allgemeinen viel geringer ist als der Rechenaufwand, der bei der Konstruktion eines Algorithmus anteilig auf ein Beispiel der Trainingsmenge entfällt.

Daraus hat man folgendes Vorgehen entwickelt:

Fenstertechnik

Zunächst wird ein Lerndurchgang mit einer kleinen Teilmenge der Beispiele - einem Fenster - berechnet. Dann werden weitere Beispiele der Trainingsmenge mit dem so gewonnenen Algorithmus kategorisiert. Die Beispiele, bei denen die Kategorisierung nicht stimmt, werden zur Trainingsmenge hinzugefügt. Anschließend wird ein neuer Lerndurchgang gestartet. Auf diese Weise soll die Anzahl der Beispiele, die der Algorithmus richtig kategorisiert hat, vergrößert werden. Es kann dabei vorkommen, dass - nach dem Hinzufügen von neuen Beispielen zur Trainingsmenge - Beispiele nicht mehr richtig kategorisiert werden, die nicht in der ursprünglichen Trainingsmenge lagen, aber trotzdem richtig kategorisiert worden waren.

Um das zu illustrieren, kann man annehmen, dass die Trainingsmenge inkonsistent ist, also zwei Tupel s und t existieren, wie sie in Gleichung (70 ) definiert wurden, die nicht im zunächst gewählten Fenster liegen. Falls s durch den im ersten Durchgang berechneten Algorithmus richtig und t falsch kategorisiert wurde, wird t im ersten kategorisierenden Kontrolldurchgang durch die Trainingsmenge zur Menge der Beispiele hinzugefügt, aus der der Algorithmus gelernt wird. Dadurch kann s durch den im nächsten Schritt konstruierten Algorithmus nicht mehr richtig kategorisiert werden. Wird ein weiterer Kontrolldurchgang durchgeführt, wird sich die Inkonsistenz zeigen. Solche Effekte können bei mehreren inkonsistenten Beispielen mit identischen Werten auf den vorhersagenden Attributen noch komplexer werden.

Insgesamt dient die Fenstertechnik dazu, die "schwierigen" Beispiele in der Trainingsmenge zu finden. Dadurch besteht die Gefahr, dass die Teilmenge, mit der ein Algorithmus gelernt wird, nicht mehr repräsentativ für die gesamte Trainingsmenge ist. Insbesondere wenn die Trainingsmenge nur einen kleinen Ausschnitt aus einer großen Menge möglicher Wertekombinationen darstellt, können dadurch Verzerrungen bei den Lernergebnissen auftreten, die die Effizienz der gefundenen Algorithmen beeinträchtigen.