|
|
|
|
DBLearn (Han, Cai & Cercone 1992 [->]) bzw. seine Weiterentwicklung DBMiner (Han, Fu, Wang, Chiang et al 1996) [->]) arbeitet auf relationalen Datenbanken und verwendet zusätzlich Hintergrundwissen in Form von Konzepthierarchien.
Einige dieser Konzepthierarchien aus Han,Cai & Cercone (1992 [->]) sind in Abbildung 66 dargestellt. Dort sind die Städtenamen zunächst nach Provinzen, dann nach Ländern etc. zusammengefaßt. In dieser Struktur steckt also das Wissen über die (politische) Zugehörigkeit der Städte.
Abb. 66: Konzepthierarchien aus (Han, Cai & Cercone 1992)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 häufig vorhandene Attribute kombinieren, um Konzepthierarchien zu konstruieren. In dem von Han, Cai & 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 Stufe in der Konzepthierarchie verwendet werden, der des Attributes "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 und Hintergrundwissen über diese Attribute in Form von Konzepthierarchien, indem die Tupel aus der Beispielmenge nach verschiedenen Regeln generalisiert werden.
Han, Cai & Cercone (1992 [->]) unterscheiden drei verschiedene Arten von Regeln:
Zur Generierung dieser Regeln werden unterschiedliche Varianten des Algorithmus' verwendet. Für die quantitativen Regeln werden die Tupel um ein Attribut "vote" mit dem Anfangswert Eins erweitert, das als Wertebereich die natürlichen Zahlen hat und bei Verallgemeinerungen angibt, auf wieviele Beispiele sich eine verallgemeinerte Regel stützt.
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:
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.
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" aus Abschnitt _4.3.2.5_ . Es ist gleichzeitig die einzige Generalisierungsregel, die in DBLearn verwendet wird.
Bezeichnet der Konzeptbezeichner eines Attributes das maximale Element der Teilordnung, also den Wertebereich des Attributes, kann dieses Attribut weggelassen werden, denn bei der Konstruktion der Komplexe ändert der Schnitt mit der Gesamtmenge der Beispiele den Komplex nicht.
Tupel, die bis auf das Attribute "vote" identisch sind, werden zu einem Tupel zusammengefaßt. Dabei wird das Attribut "vote" gleich der Summe der Werte der "vote" Attribute der zusammengefassten Tupel gesetzt.
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.
A : Solange die Anzahl der verschiedenen Attributwerte
>=k ist, steige mit allen Werten in der Konzepthierarchie
von Ai auf.Ein Beispiel für die Durchführung des Algorithmus aus Han, Cai & Cercone (1992 [->]) ist in Abbildung 67 angegeben.
Abb. 67: Regelgenerierung mit DBLearn (nach Han, Cai & Cercone 1992)Die Aussagen, die mit diesem Algorithmus gewonnen werden können, sind von der Form: In den vorgegebenen Beispielen treten die und die Attributewerte zusammen auf. Wichtig ist festzuhalten, dass es das Ziel des Algorithmus ist, Aussagen, die nicht falsch sind, in Form einer Abdeckung mit einer vorgegebenen Maximalzahl von Disjunktionen und einer vorgegebenen Maximalzahl von Konjunktionen in den Komplexen zu erzeugen. Die Bezeichnung "charakteristische Regeln" legt nahe zu vermuten, dass sich diese Regeln wie die charakteristische Funktion einer Menge umkehren lassen. 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 Attributes, in der extrahierten Regel vorzukommen, hoch, 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 wieviele 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 brauchen die durch die Attribut Wert Paare beschriebenen Teilmengen der Beispielmenge, nicht mehr disjunkt zu sein. Deshalb werden solche Komplexe, die durch die Verallgemeinerungen in beiden Mengen vorkommen, markiert und nicht weiter berücksichtigt. Bleiben am Schluß in der ersten Menge unmarkierte Komplexe übrig, gibt es also Komplexe in der ersten Abdeckung, die nicht durch die zweite Abdeckung überdeckt werden, werden diese Komplexe als Unterscheidungsregeln ausgegeben. Ein Beispiel ist ebenfalls in Han, Cai & 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. Im Beispiel aus Abbildung _67_ zeigt sich das besonders darin, dass eine weitere Vereinfachung der gefundenen Regel durch Weglassen der Studienrichtung und der Benotung das selbe Ergebnis erzielen würde. DBLearn wurde in einer Erweiterung von SQL implementiert (siehe Han, Cai & Cercone (1992 [->]))
|
|
|
|