2.5.2: DBLearn/DBMiner

DBLearn (Han, Cai und Cercone, 1992 [->] ) bzw. seine Weiterentwicklung DBMiner (Han, Fu, Wang, Chiang et al., 1996 [->] ) arbeitet auf relationalen Datenbanken und verwendet Konzepthierarchien als Hintergrundwissen. Einige dieser Konzepthierarchien sind in Abbildung 70 dargestellt. Dort sind die Städtenamen zunächst nach Provinzen, dann nach Ländern etc. zusammengefasst. In dieser Struktur steckt also das Wissen über die (politische) Zugehörigkeit der Städte.

Abbildung 70: Konzepthierarchien aus DBLearn

In real existierenden Datenbanken werden im Allgemeinen die Attribute nicht so "schön" vorliegen, dass mit ihnen direkt Konzepthierarchien gebildet werden können. Man kann aber z.B. vorhandene Attribute kombinieren, um Konzepthierarchien zu konstruieren. In dem von Han, Cai und Cercone (1992) [->] verwendeten Beispiel einer Datenbank mit Angaben über Studierende gibt es die Attribute city, province und country. Diese Attribute werden zu einem Attribut place kombiniert, zu dem eine Konzepthierarchie konstruiert werden kann. Dabei macht man sich zunutze, dass die vorhandenen Attribute in einem Beispiel bereits eine Hierarchie beschreiben: Die im Attribut city angegebene Stadt liegt in der im Attribut province angegebenen Provinz, die wiederum im in country angegebenen Land liegt. Der Wertebereich des Attributs province kann also als erste Verallgemeinerungsstufe in der Konzepthierarchie verwendet werden, der des Attributs country als zweite, etc. Die Zugehörigkeiten zu den Konzepten können aus den Tupeln der Datenbank abgelesen werden, in denen die entsprechenden Werte vorkommen (falls die Datenbank in diesem Teilbereich konsistent ist).

DBLearn erzeugt allgemeine Regeln einer vorgegebenen Komplexität über eine Beispielmenge in Bezug auf eine Auswahl von Attributen. Dabei wird das in Form von Konzepthierarchien vorliegende Hintergrundwissen über diese Attribute verwendet, um Regeln, die aus den Tupeln abgeleitet wurden, zu generalisieren. Han, Cai und Cercone (1992) [->] unterscheiden drei verschiedene Arten von Regeln:

• Charakteristische Regeln (characteristic rules) beschreiben Eigenschaften, die von allen durch die Bedingungen an die Attribute erfassten Beispielen erfüllt werden. Dabei wird z.B. für einzelne Attribute nichts darüber ausgesagt, wie viele andere Beispiele gleiche Werte annehmen.
• Unterscheidungsregeln (discriminant rules) beschreiben Eigenschaften, die die Beispiele einer Teilmenge von denen einer anderen Teilmenge unterscheiden.
• Quantitative Regeln (quantitative rules) sind Regeln, bei denen angegeben wird, wie viele Beispiele sie beschreiben.

DBLearn ist wie AQ ein Bottom-up-Verfahren, bei dem zunächst die Tupel der Beispielmenge als Input verwendet werden. Sie können im Sinne des AQ-Algorithmus als Komplexe aus elementaren Bedingungen aufgefasst werden. Auf diese Komplexe werden dann bei der Generalisierung die folgenden Regeln und Strategien angewendet:

Nur Selektoren generalisieren

Bei der Generalisierung werden nur einzelne Attribute, also Selektoren bearbeitet. Dabei dürfen in Selektoren auch Bezeichner für Teilmengen von Attributwerten aus den Konzepthierarchien verwendet werden.

Aufsteigen in Konzepthierarchien

Liegt die Anzahl der verschiedenen in den Beispielen angenommenen Attributwerte und Konzeptbezeichner für ein Attribut höher als eine vorgegebene Schwelle, werden die Attributwerte oder Konzeptbezeichner durch den nächsthöheren Konzeptbezeichner in der Konzepthierarchie ersetzt. Das ist die Generalisierungsoperation "Erweitern eines Wertebereichs". Es ist gleichzeitig die einzige Generalisierungsregel, die in DBLearn verwendet wird.

Selektoren mit dem maximalen Element der Teilordnung weglassen

Bezeichnet der Konzeptbezeichner eines Attributs das maximale Element der Teilordnung, also den Wertebereich des Attributs, kann dieses Attribut weggelassen werden, denn bei der Konstruktion der Komplexe ändert der Schnitt mit der Gesamtmenge der Beispiele den Komplex nicht.

Gleiche Tupel zusammenfassen

Tupel, die bis auf das Attribute VOTE identisch sind, werden zu einem Tupel zusammengefasst. Dabei wird das Attribut VOTE gleich der Summe der Werte der VOTE-Attribute der zusammengefassten Tupel gesetzt.

Einfachere Form erzwingen

Falls die Anzahl der Komplexe über einer vorgegebenen Schwelle liegt (also die Regel noch zu wenig allgemein ist) und trotzdem die Bedingung aus der Regel zum Aufsteigen in der Konzepthierarchie für keines der Attribute erfüllt ist, wird die Schwelle aus dieser Regel gesenkt.

Der Algorithmus zur Extraktion von charakteristischen Regeln zu einer Beispielmenge kann jetzt folgendermaßen geschrieben werden.

Eingaben

• Die Beispiele (Tupel) aus der Datenbank.
• Die Menge A={A₁,...,A_s} der Attribute, mit denen die Beispiele beschrieben werden sollen, und ihre Konzepthierarchien.
• Grenzwert k für die maximal zulässige Anzahl von verschiedenen Attributwerten je Attribut in der Menge der zu erzeugenden Komplexe.
• Grenzwert n für die maximal zulässige Anzahl an Komplexen.

Algorithmus 8: DBLearn

Ein Beispiel für die Durchführung des Algorithmus aus Han, Cai und Cercone (1992) [->] ist in Abbildung 71 angegeben.

Abbildung 71: Regelgenerierung mit DBLearn

Die mit dem Algorithmus gewonnenen charakteristischen Regeln besagen, dass in der untersuchten Beispielmenge die angegebenen Attributwerte bzw. Werte aus den durch die Konzeptbezeichner beschriebenen Wertebereichen zusammen auftreten. Die Attribute, die in den Regeln auftauchen, werden über die Parameter n und k so ausgewählt, dass nicht zu viele und nicht zu "komplizierte" Regeln gefunden werden. Sie werden nicht danach bestimmt, ob die Regeln besonders typisch oder interessant sind.

Die Bezeichnung "charakteristische Regeln" legt die Vermutung nahe, dass sich alle Eigenschaften der Beispielmenge aus diesen Regeln erschließen lassen, so wie eine Basismenge aus ihrer charakteristischen Funktion erschlossen werden kann. Das ist aber nicht der Fall. Eigenschaften der Beispielmenge, die sich nicht in der geforderten Einfachheit darstellen lassen, gehen gegebenenfalls durch Aufsteigen zu ANY verloren. Welche Eigenschaften extrahiert werden und welche nicht, hängt vor allem von dem vorhandenen Hintergrundwissen ab. Hat die Konzepthierarchie einen kleinen Verzweigungsgrad, ist die Chance des zugehörigen Attributs hoch, in der extrahierten Regel vorzukommen, hat sie einen hohen Verzweigungsgrad, ist sie eher gering. So können seltene Ausnahmen bereits zur Entfernung eines Attributs führen, auch wenn die große Mehrzahl der Werte sich auf eine kleine Menge beschränkt.

Um für eine charakteristische Regel eine quantitative Regel zu erzeugen, verwendet man das VOTE-Attribut. Es gibt für die verbleibenden Komplexe an, auf wie viele Beispiele sie sich stützen. Bei der Konstruktion der Abdeckung kann man für jeden Komplex den entsprechenden Prozentwert angeben.

Um Unterscheidungsregeln zu lernen, müssen zwei Beispielmengen, zwischen denen unterschieden werden soll, angegeben werden. In beiden Beispielmengen wird dann simultan der Verallgemeinerungsalgorithmus durchgeführt. Dadurch müssen die durch die Attribut-Wert-Paare beschriebenen Teilmengen der Beispielmenge nicht mehr disjunkt sein. Deshalb werden solche Komplexe, die durch die Verallgemeinerungen in beiden Mengen vorkommen, markiert und nicht weiter berücksichtigt. Bleiben am Schluss in der ersten Menge unmarkierte Komplexe übrig, gibt es also Komplexe in der ersten Abdeckung, die die zweite Abdeckung nicht überdeckt, werden diese Komplexe als Unterscheidungsregeln ausgegeben. Ein Beispiel ist ebenfalls in Han, Cai und Cercone (1992) [->] angegeben.

Auch hier geht es nicht darum, die beste Unterscheidung zwischen zwei Beispielmengen zu finden, sondern darum, Mengen zu finden, die sich in einer vorgegebenen Form schreiben lassen und kein Beispiel enthalten, das in der entstehenden Obermenge der zweiten Beispielmenge liegt.