4.3.2: Der AQ-Algorithmus

Unter dem Namen AQ Algorithmus werden eine ganze Reihe Verfahren zusammengefasst, die für verschiedene Probleme entwickelt wurden. Einführungen finden sich in Michalski 1983 [->] und Michalski, Mozetic, Hong und Lavrac (1986 [->]). Hier soll der auch in Holsheimer und Siebes (1994) [->] dargestellte AQ15 Algorithmus in einer einfachen Form vorgestellt werden. Der AQ15 Algorithmus generiert IF-THEN-Regeln, die Kategorien in einem "Variable-Valued Logic System 1" genannten Formalismus beschreiben.

Im folgenden sei wieder D eine Menge von konsistenten Beispielen mit Attributen A_i:D->R_i ,i=1,...,n .

4.3.2.1: Selektor, Komplex, Abdeckung

Für jede Kategorie in einer konsistenten Beispielsammlung kann man eine Abdeckung finden, die die Kategorie beschreibt. Dazu schreibt man, wie im formalen Algorithmus aus Abschnitt _4.3_ beschrieben, die Tupel aus einer Kategorie als Konjunktionen ihrer Attribut-Wert-Paare und bildet über diese (sehr einfachen) Komplexe eine Disjunktion. Diese Beschreibung durch Aufzählung ist aber natürlich nicht sehr nützlich. Es müssen also einfachere Beschreibungen gefunden werden.

Dazu führt AQ15 eine heuristische Suche im Raum aller Abdeckungen durch, um diejenigen zu finden, die genau die Beispiele einer Kategorie beschreiben und keine anderen Beispiele des Trainingssets. Dabei können von Nutzenden Präferenzkriterien angegeben werden, die bei mehreren passenden Regeln die bevorzugte auswählen. Solche Präferenzkriterien können zum Beispiel die Anzahl der Selektoren in einem Komplex oder auch spezifische Kostenfunktionen für einzelne Selektoren sein.

Die Suche im Raum der Abdeckungen wird konstruktiv durch Operationen, die generalisieren, und solche, die spezialisieren, durchgeführt. In einem einfachen Fall kann man dazu die folgenden Operationen verwenden:

• Hinzufügen von erlaubten Werten zu einem Selektor (Generalisierung)
• Hinzufügen eines Komplexes zu einer untersuchten Abdeckung (Generalisierung)
• Schneiden eines Komplexes mit einem weiteren Selektor (Spezialisierung)

Der Algorithmus geht entweder von einer (z. B. durch Nutzende) gegebenen Abdeckung aus, oder er beginnt mit der leeren Abdeckung. Dann werden zu einem zufälligen Beispiel, das zur Kategorie, aber nicht zur Abdeckung gehört, alle Komplexe gesucht, die das Beispiel abdecken, in denen aber kein Beispiel des Trainingssets liegt, das nicht zur Kategorie gehört. Die Vereinigung über alle so konstruierten Komplexe ist eine Abdeckung, die die Kategorie beschreibt.

Das zentrale Konstrukt des Algorithmus ist das des Sterns ( star):

4.3.2.2: Stern

Im Folgenden werden Sterne häufig innerhalb der Elemente einer Kategorie XD berechnet, d. h. wir setzen Y=D\X , und die zweite Bedingung geht in die äquivalente Bedingung KX über.

Der Algorithmus zum Lernen einer einzelnen Kategorie XD aus einer Menge von Beispielen D kann folgendermaßen geschrieben werden:

4.3.2.3: Algorithmus AQ15

Ein maximaler Komplex eines Beispiels dD in X ist ein Komplex KX , für den gilt: Falls ein Komplex QK mit KQ existiert, folgt Q⊄X . Ein Element kann mehrere maximale Komplexe haben (zwischen denen dann aber natürlich keine Teilmengenrelation herrschen kann).

Um eine Annäherung an die maximalen Komplexe eines Elementes dX in einer Kategorie X zu berechnen, verwendet man in Schritt 2 einen beschränkten partiellen Stern für ein positives Beispiel d aus X :

4.3.2.4: Algorithmus: AQ15 Partieller Stern

Die mit dem Algorithmus gefundene Abdeckung C kann durch weitere Generalisierungen optimiert werden. Bei der Berechnung des beschränkten Sterns handelt es sich um ein beam search Verfahren, da eine ganze Liste von Komplexen verwaltet wird.

Abb. 56: Beispiele aus Abbildung nach Kategorien sortiert

Abb. 57: Konstruktion einer Abdeckung für die ersten zwei Beispiele von K2 aus Abbildung mit dem AQ15 Algorithmus.

Abb. 58: Fertigstellung der Abdeckung für K2 aus Abbildung mit dem AQ15 Algorithmus.

Die Abbildungen _57_ und _58_ zeigen die Anwendung des AQ15 Algorithmus auf die Beispiele aus Abbildung _56_ . Zunächst wird ein Beispiel d=(0,1,0,0) aus der zu beschreibenden Kategorie gewählt und dazu der partielle Stern berechnet. Dabei wurden die Beispiele r(D\X)K_j , j{1,...,k} so gewählt, dass sie sich in möglichst wenigen Attributen von dem Beispiel d unterscheiden. Dadurch wird die Anzahl der maximalen Komplexe klein gehalten und das Beispiel überschaubar. Es können natürlich auch andere Auswahlkriterien angewendet werden.

Die Beschränkung des partiellen Sterns auf eine feste Anzahl von Komplexen wurde nicht verwendet (d. h. die zulässige Anzahl an Komplexen wurde so groß gewählt, dass sie nicht erreicht wurde). Dadurch werden alle Komplexe mitgeführt.

Beim ersten Beispiel d=(0,1,0,0) zeigt sich der Einfluss der Auswahl des Komplexes, der in die Abdeckung übernommen wird. Wäre statt des Komplexes mit dem Selektor (A3=0), der andere Komplex mit (A4=0) gewählt worden, wäre das zweite Beispiel d=(0,1,1,0) bereits mit abegedeckt gewesen. Eine Regel, die eine solche Wahl bewirkt hätte, wäre z. B. die, solche Komplexe zu wählen, die möglichst viele positive Beispiele abedecken.

Beim dritten Beispiel d=(1,1,0,1) aus der Kategorie wurde mit r=(0,0,0,1)(D\X)K_j zunächst ein Beispiel gewählt, das sich in vielen Attributen von d unterscheidet. Dadurch ergeben sich erheblich mehr Komplexe. In Abbildung _58_ sind zunächst alle Schnittmengen aufgeführt. Man sieht aber, dass eine ganze Reihe davon doppelt auftreten. Nach dem zweiten P sind die doppelten Komplexe weggelassen.

Weiter sieht man, dass durch die Durchschnittsbildung Komplexe entstehen, die Teilkomplexe von anderen Komplexen sind. Hier könnte man im Sinne einer maximalen Generalisierung die Teilmengen weglassen. Die einzige Forderung an den partiellen Stern, die dabei immer erfüllt sein muß, ist die, dass er d enthalten muss und r nicht enthalten darf. Darüber hinaus können Operationen und Auswahlregeln angewendet werden, die sinnvoll erscheinen, um das Verfahren zu vereinfachen und zu beschleunigen. So könnte man wieder vor allem solche Komplexe übernehemen, die möglichst viele Beispiele aus der zu beschreibenden Kategorie enthalten, und möglichst wenige, die nicht in diese Kategorie fallen. Man könnte so, im Gegensatz zur oben vorgeschlagenen Verallgemeinerung, solche Komplexe weglassen, die Obermengen von anderen Komplexen sind und noch Gegenbeispiele enthalten während die Untermengen ganz in der Kategorie liegen. So ist im letzten Block von Abbildung _58_ (A1=1)&(A4=1) Obermenge von (A1=1)&(A3=0)&(A4=1). Der erste Komplex enthält aber mit (1,0,1,1) noch ein Beispiel, dass nicht in der zu beschreibenden Kategorie liegt, der zweite enthält dagegen keines mehr. In diesem Fall ist es klar, das der erste Komplex zugunsten des zweiten weggelassen werden kann. Wenn es aber verschiedenen Spezialisierungen gäbe, die alle zwar weniger, aber doch immer Beispiele enthalten, die nicht in der Kategorie liegen, wäre es nicht so eindeutig, welche Spezialisierung günstiger ist.

In diesem Beispiel enthält die Beispielmenge einen großen Teil der möglichen Tupel. In vielen praktischen Fällen tritt nur ein vergleichsweise kleiner Teil der möglichen Tupel auch tatsächlich im Trainingsset auf. Sind die Wertebereiche der Attribute z. B. die reellen Zahlen oder reelle Intervalle, so schneidet die Konstruktion über maximale Komplexe nur jeweils die Punkte der Gegenbeispiele heraus. Es ist aber z. B. bei Ergebnissen physikalischer Experimente oder bei medizinischen Tests sehr unwahrscheinlich, dass nur die exakten Werte der Beispiele aus der Kategorie herausfallen. Viel wahrscheinlicher ist es, dass ganze Intervalle entfernt werden müßten, für die ein Gegenbeispiel jeweils nur ein Prototyp ist. In diesen Fällen kann es sinnvoll sein, neben den hier betrachteten Spezialisierungen auch Generalisierungen zu verwenden.

4.3.2.5: Generalisierungsoperationen