Abbildungsverzeichnis IV
Verzeichnis der Definitionen VI
1 Einleitung
2 Einführung
2.1 Kostenprognose für die Angebotsplanung von Demontageunternehmen
2.1.1 Demontage von Elektro- und Elektronikaltprodukten - die gegenwärtige Situation
2.1.2 Angebotsplanung für die Demontage
2.1.3 Verfahren der Kostenprognose
2.2 Automatische Wissensakquisition
2.3 Fuzzy Logik
2.4 Aktive Datenbanken als Grundlage für die Implementierung wissensbasierter Systeme
3 Vorüberlegungen zur Akquisition unscharfer Regeln
4 STAR, Fuzzy-STAR und Incremental Fuzzy-STAR
4.1 Die STAR-Methode
4.2 Fuzzy-STAR
4.2.1 Vorüberlegungen
4.2.2 Das Verfahren
4.2.3 Ein Beispiel
4.3 Incremental Fuzzy-STAR
4.3.1 Vorüberlegungen
4.3.2 Das Verfahren
4.3.3 Ansätze für eine Optimierung des Verfahrens
4.3.4 Ein Beispiel
4.3.5 Implementierung des Verfahrens
4.3.6 Bewertung des Verfahrens
5 MUSP
5.1 Vorüberlegungen
5.2 Das Verfahren
5.3 Ansätze für eine Optimierung des Verfahrens
5.4 Ein Beispiel
5.5 Implementierung des Verfahrens
5.6 Bewertung des Verfahrens
6 Weitere Verfahren; Ausblick
6.1 Fuzzy-ID3
6.1.1 Das Verfahren
6.1.2 Bewertung des Verfahrens
6.2 Akquisition unscharfer Regeln durch verallgemeinerte Mengenoperationen
6.2.1 Das Verfahren
6.2.2 Bewertung des Verfahrens
6.3 Ausblick
Literatur
Anhang
A Datenträger mit Dateien zur Implementierung von MUSP
B Kurzbeschreibung der Dateien auf dem Datenträger

Abbildungsverzeichnis:

Abbildung 1: Architektur eines Systems zur Prognose von Kosten und Zeiten
Abbildung 2: Einmalige Wissensakquisition
Abbildung 3: Intervallweise Wissensakquisition
Abbildung 4: Fortwährende Wissensakquisition
Abbildung 5: Beispiele für t-Normen und s-Normen
Abbildung 6: Beispiel für Gipfel- und Spannweitenexpansion
Abbildung 7: Bildung eines Spezialisierungspfades für einen metrisch skalierten Attributwert
Abbildung 8: Bildung eines Spezialisierungspfades für einen ordinalen Attributwert
Abbildung 9: Bildung eines individuellen F-STARs für ein Beispielobjekt zu einer Klasse
Abbildung 10: Bildung eines Fuzzy-STARs für eine Klasse anhand einer Menge von Beispielen
Abbildung 11: Beispiel-Datensätze
Abbildung 12: LR-Fuzzy-Vektor für Shredder-Zeitaufwandsklassen
Abbildung 13: Zugehörigkeit der Beispieldatensätze zu Zeitaufwandsklassen
Abbildung 14: Spezialisierungspfade für Datensatz EX₃
Abbildung 15: Individueller F-STAR für Datensatz EX₃ (Verfahren Fuzzy-STAR)
Abbildung 16: Spezialisierungspfade für Datensatz EX₂
Abbildung 17: Individueller F-STAR für Datensatz EX₂ (Verfahren Fuzzy-STAR)
Abbildung 18: Beispiel für einen Spezialisierungsgraphen
Abbildung 19: Modifikation eines individuellen F-STARs
Abbildung 20: Ständige Aktualisierung eines Fuzzy-STARs
Abbildung 21: Spezialisierungspfade für Datensatz EX₁
Abbildung 22: Individueller F-STAR für Datensatz EX₂ (Verfahren Incremental Fuzzy-STAR)
Abbildung 23: Spezialisierungsgraph für den individuellen F-STAR zu Datensatz EX₂
Abbildung 24: Individueller F-STAR für Datensatz EX₃ (Verfahren Incremental Fuzzy-STAR)
Abbildung 25: Spezialisierungsgraph für den individuellen F-STAR zu Datensatz EX₃
Abbildung 26: Klassifizierung von EX₄ durch den individuellen F-STAR F⁽²⁾
Abbildung 27: Teilweise aktualisierter individueller F-STAR zu Datensatz EX₂
Abbildung 28: Ergänzung des individuellen F-STARs zu Datensatz EX₂
Abbildung 29: Klassifizierung von EX₄ durch den individuellen F-STAR F⁽³⁾
Abbildung 30: Teilweise aktualisierter individueller F-STAR zu Datensatz EX₃
Abbildung 31: Zeitaufwandsklassen als Tabelleneinträge
Abbildung 32: Widerspruchsgesteuerte Spezialisierung einer nominalen unscharfen Bedingung
Abbildung 33: Widerspruchsgesteuerte Spezialisierung einer metrischen unscharfen Bedingung
Abbildung 34: Korrektur einer Regel anhand eines Widerspruchsbeispiels
Abbildung 35: Korrektur einer Menge von Regeln anhand eines Beispiels
Abbildung 36: MUSP-Hauptalgorithmus
Abbildung 37: Spezialisierung der Regel R₂₀ (Verfahren MUSP)
Abbildung 38: Spezialisierung der Regel R₃₀ (Verfahren MUSP)
Abbildung 39: Spezialisierung der Regel R₃₂ (Verfahren MUSP)
Abbildung 40: Spezialisierung der Regel R₃₃ (Verfahren MUSP)
Abbildung 41: Das Verfahren ID3
Abbildung 42: Beispieldaten für die Anwendung verallgemeinerter Mengenoperationen

Verzeichnis der Definitionen:

Definition 1: Inkrementelles Lernverfahren
Definition 2: Unscharfe Menge
Definition 3: Normalisierte unscharfe Menge
Definition 4: Stützmenge einer unscharfen Menge
Definition 5: Referenzfunktion
Definition 6: LR-Fuzzy-Intervall
Definition 7: Diskretes LR-Fuzzy-Intervall
Definition 8: LR-Fuzzy-Vektor
Definition 9: Anfragefunktion für LR-Fuzzy-Vektoren
Definition 10: Aktives Datenbanksystem
Definition 11: Unscharfe Bedingung
Definition 12: Kompatibilität einer Merkmalsausprägung mit einer Bedingung
Definition 13: Aggregationsoperator
Definition 14: Prämisse
Definition 15: Beispielobjekt, Lerndatenbank
Definition 16: Kompatibilität von Merkmalsausprägungen mit einer Prämisse
Definition 17: Regel, Konklusion
Definition 18: Regelanfrage
Definition 19: Individueller Fehler einer Regel
Definition 20: Korrekte / falsche Klassifikation, Nicht-Überdeckung
Definition 21: #GOOD, #BAD, #NONC
Definition 22: Konsistenzgrad einer Regel
Definition 23: Vollständigkeitsgrad einer Regel
Definition 24: Fuzzy-Generalisierung
Definition 25: Gipfelexpansion
Definition 26: Spannweitenexpansion
Definition 27: Allgemeine Expansion
Definition 28: Auswahl der spezielleren zweier Bedingungen
Definition 29: Verschmelzung von Regeln
Definition 30: Fuzzy-Klassifizierung
Definition 31: Nutzen einer Regel
Definition 32: Spezialisierungsgraph
Definition 33: Schnittmenge von Fuzzy-Mengen
Definition 34: Grad des Enthaltenseins einer Fuzzy-Menge in einer anderen
Definition 35: Grad der Schneidung zweier Fuzzy-Mengen

1 Einleitung

Ein noch relativ junger, jedoch zukünftig vermutlich stark expandierender Industriezweig entsteht mit der Demontage von Elektro- und Elektronikaltprodukten. Wie bereits in anderen Bereichen, so wächst auch hier der Wunsch nach integrierten Informationssystemen, welche sowohl die tägliche Routinearbeit unterstützen, als auch die Grundlage für strategische Entscheidungen bilden. Ein davon betroffener Teil des operativen Geschäfts ist die Angebots-planung und -erstellung. Hier ist es von unbestreitbarem Vorteil, einen effizienten Zugriff auf Informationen bezüglich Kosten- und Zeitaufwand zu besitzen, der in der Vergangenheit für die Demontage von Geräten verursacht wurde. Wünschenswert ist somit ein Prognosesystem, welches in der Lage ist, aufgrund gegenwärtig beobachtbarer Produktmerkmale auf bei einer Demontage zu erwartende Kosten und Zeiten zu schließen.
Die vorliegende Diplomarbeit soll aufzeigen, wie Verfahren der automatischen, inkrementellen Wissensakquisition unter Berücksichtigung von Unschärfe dazu dienen können, das hierfür erforderliche maschinell repräsentierte Wissen zu generieren. Ferner soll dargestellt werden, wie ein aktives Datenbanksystem dazu verwendet werden kann, die Implementierung dieser Verfahren durchzuführen, so daß es als Grundlage für die Akquisitionskomponente, die Wissensbasis und die Prognosekomponente eines solchen Systems dient.
Es erfolgt dazu im zweiten Kapitel eine einführende Einordnung des Themas in die Umfelder Kostenprognose für die Angebotsplanung von Demontageunternehmen und automatische Wissensakquisition. Dabei werden auch die einzusetzenden Werkzeuge wie Fuzzy Logik und aktive Datenbanken einer Betrachtung unterzogen.
Im dritten Kapitel werden Vorüberlegungen zum Gebiet der Akquisition unscharfer Regeln angestellt. Hierzu werden insbesondere einige für die folgenden Ausführungen hilfreiche formale Grundlagen erarbeitet.
Im vierten Kapitel wird zunächst eine bereits bekannte Methodik zur Regelerzeugung für Klassifikationssysteme (STAR) kurz vorgestellt. Daran anknüpfend wird aufgezeigt, wie das Verfahren schrittweise zu modifizieren ist, um es für die inkrementelle Akquisition unscharfer Regeln verwendbar zu machen. Darauf aufbauend werden Hinweise für eine Implementierung der STAR-Weiterentwicklungen innerhalb eines aktiven Datenbanksystems gegeben.
Mit MUSP wird im fünften Kapitel ein gänzlich neuen Verfahren entworfen, welches insbesondere auf inkrementelles Lernen zugeschnitten ist. Auch hierfür wird die Implemen-tierung innerhalb eines aktiven Datenbanksystems skizziert.
Im abschließenden sechsten Kapitel richtet sich das Interesse auf zwei weitere aus der Literatur bekannte Verfahren: eine Weiterentwicklung von ID3 und ein Ansatz zur Akquisition unscharfer Regeln durch verallgemeinerte Mengenoperationen. Die Ausführungen werden durch einen Ausblick auf Möglichkeiten zur Weiterentwicklung der präsentierten Verfahren abgerundet.

2 Einführung

In diesem Kapitel erfolgt eine Einordnung des Themas dieser Arbeit in seine Umfelder. Dabei wird insbesondere deutlich werden, wie erfolgversprechend die Kombination von Verfahren der automatischen Wissensakquisition mit Techniken der unscharfen Logik sowie eine Umsetzung dieser Methoden mit einem modernen aktiven Datenbanksystem für die Kosten-prognose ist.

2.1 Kostenprognose für die Angebotsplanung von Demontageunternehmen

2.1.1 Demontage von Elektro- und Elektronikaltprodukten die gegenwärtige Situation

Bisher werden elektrische und elektronische Geräte nach Ablauf des Nutzungszeitraums fast ausschließlich als Sperr- oder Hausmüll auf Deponien gelagert bzw. in dafür nicht vorgesehene Verbrennungsanlagen entsorgt [1]⁾. Damit gelangen Schadstoffe in Beseitigungsanlagen, die hierfür nicht ausgelegt sind, und es entstehen offene Stoffkreisläufe. Jedoch wird der sich in den letzten Jahren aufgrund einer gewachsenen gesellschaftlichen Sensibilität gegenüber Umweltproblemen deutlich abzeichnende Trend weg von der Mülldeponierung bzw. Müll-verbrennung hin zur Wiederverwertung oder sogar Müllvermeidung in naher Zukunft auch vor Produkten aus dem Elektro- und Elektronikbereich nicht haltmachen. Als Indizien hierfür sind beispielweise anzuführen [2]⁾:
* Eine an der bereits existierenden Verpackungsordnung orientierte "Verordnung über die Vermeidung, Verringerung und Verwertung von Abfällen gebrauchter elektrischer und elektronischer Geräte" (Elektronikschrott-Verordnung) befindet sich in der Bundesrepublik Deutschland auf dem parlamentarischen Wege, wobei sich allerdings zur Zeit noch nicht absehen läßt, wann diese Verordnung Gesetzeskraft erlangen wird.
* Hersteller bemühen sich zum Teil bereits, Produkte des Eletronikbereichs nicht nur unter Einsatz umweltfreundlicher Materialien, sondern auch demontagegerecht zu gestalten. Sie tun dies zum einen in der Erwartung der oben erwähnten Verordnung, zum anderen in dem Wissen um eine immer größer werdende Käufergruppe, welche bereit ist, entsprechende Bemühungen über die Akzeptanz eines höheren Preises zu honorieren. Hinzu kommt, daß bereits jetzt die Verwertung von Platinenschrott insbesondere aus Computern durchaus ökonomisch interessant ist: In jeder Tonne solchen Platinenschrotts befinden sich zwischen 100 und 200 kg Kupfer, ca. 1 kg Gold, 0,5 bis 3 kg Silber sowie geringere Mengen der Edelmetalle Iridium, Osmium, Palladium, Platin, Rhodium und Ruthenium. Das geschätzte gegenwärtige Gesamtaufkommen an Platinenschrott beträgt etwa 25.000 Tonnen - bei stark steigender Tendenz [3]⁾.
* Es existieren z.B. für Computer bereits Normen für die Vergabe von Öko-Plaketten, wie der deutsche Blaue Umweltengel oder die schwedische TCO 95, welche für umweltgerecht produzierte Geräte vergeben werden.
Einige Unternehmen (z.B. IBM, Siemens Nixdorf, Nokia) führen, wenn auch auf mengenmäßig bisher sehr niedrigem Niveau, bereits die Rücknahme von Computern mit dem Ziele des Material- bzw. Teilproduktrecycling durch. Der dabei zu betreibende Aufwand ist im wesentlichen davon abhängig, aus welchen Materialien das zu rezyklierende Produkt besteht und wie diese Materialien bei der Herstellung miteinander kombiniert wurden.
Der erste Schritt in einem solchen Recyclingprozeß besteht in einer Herauslösung von Bauteilen oder -gruppen aus dem Altgerät (Demontage im engeren Sinne). Dies kann einerseits geschehen, um Bauteile oder -gruppen zu gewinnen, die nach einer eventuell erforderlichen Aufarbeitung als Ersatzteile für gleiche oder ähnliche Geräte (Wiederverwendung) oder zur Produktion anderer Erzeugnisse (Weiterverwendung) genutzt werden können [4]⁾. (Eine bemerkenswerte, wenn auch sicherlich auf eine Marktnische beschränkte Möglichkeit für eine solche Weiterverwendung zeigt das Beispiel der Firma Ohm Design aus Bexbach: Das Unternehmen veredelt interessant aussehende Platinenteile und vermarktet diese als Schmuck in Form von Broschen, Krawattenschiebern etc.) Andererseits können hierdurch Einheiten gewonnen werden, welche eine recht homogene Materialzusammensetzung aufweisen und somit getrennt vom Gesamtgerät einer Stofftrennung zuzuführen sind. Ferner müssen solche Bauteile entfernt werden, die aufgrund ihres Gehalts an besonders kritischen Substanzen gesondert zu entsorgen sind.
Eine solches Herauslösen von Bauteilen oder -gruppen ist - wenn überhaupt - in der Regel nicht zerstörungsfrei durchzuführen, da die Baustruktur der Geräte oft nicht demontagegerecht ist. So ist allgemein der Einsatz von Schrauben, Nieten, Schweißnähten etc. anstelle modul-artiger Stecksysteme üblich. Es läßt sich allerdings eine Tendenz hin zu einer recycling-gerechteren Konstruktion verzeichnen [5]⁾. So wird gegenwärtig kaum eine automatisierte Trennung solcher Produkte durchgeführt; stattdessen wird der weitaus größte Teil dieser Demontageprozesse noch in zeit- und lohnintensiver Handarbeit von qualifizierten Arbeits-kräften erledigt [6]⁾. (Dieser insgesamt eher zu bedauernde Umstand ist jedoch, wie sich noch zeigen wird, von Vorteil für die Kostenprognose.)
Bauteile, für die keine Wieder- oder Weiterverwendungsmöglichkeiten besteht, bzw. Geräte, für die eine Herauslösung von Baugruppen unwirtschaftlich ist, werden einem automatischen Zerkleinerungsverfahren unterzogen. Anschließend erfolgt die Stofftrennung mit dem Ziel, die so gewonnenen Materialien in den Stoffkreislauf zurückzuführen oder fachgerecht zu entsorgen.
Zu den verwendeten umweltschädlichen Materialien, welche bei einer solchen Stofftrennung zu isolieren sind, gehören beispielsweise:
* polybromierte Diphenylether und Chlorparaffine, welche in Kunststoffgehäusen als Flammenhemmer eingesetzt werden und bei der Müllverbrennung zu giftigen Dioxinen und Furanen umgewandelt würden;
* die giftigen Schwermetalle Cadmium, Barium und Blei, welche in der Beschichtung der Bildschirmgläser zur Leuchtkrafterhöhung bzw. zur Adsorption der Röntgenstrahlung eingesetzt werden;
* eine Vielzahl weiterer Schwermetalle und anderer stark toxischer Stoffe aus den verschiedenen Bauteilen auf Leiterplatten.
Insbesondere die mannigfaltige Kombination von insgesamt etwa fünfzig verschiedenen chemischen Stoffen auf Leiterplatten [7]⁾ sowie die Verwendung von Verbundmaterialien und Beschichtungen führen zu einer immensen Erschwerung der Stofftrennung.
Von der kommenden Elektronikschrott-Verordnung betroffen sind praktisch sämtliche Geräte der Informations- und Kommunikationstechnologie, der Unterhaltungselektronik sowie Geräte aus dem Haushaltsbereich. Die Verpflichtung zur Rücknahme und Verwertung ihrer Produkte obliegt allen Unternehmen, die derartige Geräte herstellen oder mit einem Markenzeichen versehen und in Verkehr bringen. Dabei ist ausdrücklich eine sogenannte Öffnungsklausel vorgesehen, welche die geordnete Übertragung dieser Pflichten an Dritte erlaubt. Da es sich aufgrund der Komplexität der Demontageprozesse für kleinere Unternehmungen als schwierig erweisen dürfte, die Entsorgung individuell selbst durchzuführen, ist eine entsprechende Konzentration auf hierfür spezialisierte Unternehmungen zu erwarten bzw. zum Teil bereits beobachtbar. Insgesamt ist jedoch bisher ein eher zögerliches Ingangkommen einer geordneten Entsorgungspraxis zu verzeichnen [8]⁾.

2.1.2 Angebotsplanung für die Demontage

An Kunden gerichtete Angebote bezüglich der Entsorgung von Elektro- und Elektronik-altprodukten beinhalten in jedem Falle eine Preis- und Terminangabe. Dies gilt in unterschiedlichen Detaillierungsgraden für Kontakt-, Richt- und Festangebote [9]⁾. Eine Begrün-dung dieser Angaben kann zusätzlich erfolgen, indem die zur korrekten Entsorgung erforderlichen fertigungstechnischen Maßnahmen aufgeführt werden.
Die mit der Erstellung eines Angebots verbundenen Risiken lassen sich wie folgt kenn-zeichnen [10]⁾:
* Das Angebot wird aufgrund eines zu hoch kalkulierten Preises nicht angenommen, so daß der Auftrag verloren geht.
* Mit dem aufgrund des Angebots erteilten Auftrag wird wegen eines zu niedrig kalkulierten Preises kein ausreichender Beitrag zur Kostendeckung erzielt.
* Das Angebot wird aufgrund eines zu fernen Termins für die Entsorgung vom Kunden ausgeschlagen.
* Es wurde ein zu früher Termin angegeben, so daß zum Fälligkeitszeitpunkt der Abnahme zu entsorgender Produkte keine entsprechenden Kapazitäten vorhanden sind.
Unter der Annahme, daß im Betrieb bereits eine mehr oder minder große Zahl von Daten über bereits demontierte Produkte vorliegt, können die oben erläuterten Angebotsrisiken durch einen effizienten Rückgriff auf diese Informationen reduziert werden. Qualitativ hochwertige Klassifikationssysteme zur Verfügbarmachung von Vergangenheitsdaten können somit eine fundierte Grundlage für die Prognose zu erwartender Kosten und Zeiten bilden. Zusätzlich wird die Angebotserstellung durch ihren Einsatz rationalisiert, da zeitraubende Rückfragen an qualifizierte Personen in den entsprechenden Verantwortungsbereichen der Betriebe teilweise entfallen; hierdurch wird offensichtlich ein weiteres Risiko, nämlich die Ausschlagung des Angebots, weil es dem Kunden zu spät offeriert wird, verringert.
An ein System zur Prognose von Kosten und Zeiten für die Unterstützung von Sachbearbeitern in der Angebotsbearbeitung sind folgende Anforderungen zu stellen:
* Das System soll in der Lage sein, aus produktspezifischen Merkmalen wie Volumen, Gewicht, Hersteller, Alter etc. zu erwartende technische Konsequenzen zu ermitteln (siehe hierzu im nächsten Kapitel). Diese technischen Konsequenzen sind anschließend mit Kostensätzen zu bewerten, um letztendlich zu aggregierten Kostengrößen, den monetären Konsequenzen, zu gelangen.
* Die prognostizierten Daten sollen möglichst genau den Wissensstand des Systems repräsentieren. Insbesondere ist zu fordern, daß Unsicherheiten, welche aus einem Mangel an anwendbarem Vergangenheitswissen resultieren, explizit gemacht werden. In keinem Falle sollte eine Prognosegenauigkeit suggeriert werden, welche das System de facto nicht erreichen kann. Andererseits muß gewährleistet sein, daß in Situationen, welche nahezu exakt so bereits vorkamen, die Prognosedaten recht genau den erlernten entsprechen. Dabei ist jedoch zu beachten, inwiefern veränderte Betriebssituationen wie Auslastung, Mitarbeiterstruktur u.ä. von Bedeutung für die zu prognostizierenden Zielgrößen sind. Eventuell sollten derartige Daten bereits beim Lernprozeß mit erfaßt werden, also in ähnlicher Weise wie Produktmerkmale behandelt werden.
* Das System soll jederzeit "up to date" sein. Es ist dafür Sorge zu tragen, daß das aus einem abgeschlossenen Auftrag resultierende neue Wissen über den Zusammenhang von Produkt-merkmalen und den Konsequenzen für den Demontageaufwand in Zukunft verfügbar ist. Für die Bereitstellung der neuen Daten ist es dabei unzweifelhaft von erheblichem Vorteil, wenn auf eine funktionierende Betriebsdatenerfassung (BDE)[11]⁾ zurückgegriffen werden kann. Die neuen Daten sind dabei so zu transformieren, daß aus ihnen in Zukunft auf effiziente Weise Schlußfolgerungen gezogen werden können - dies geschieht idealerweise durch den Einsatz der noch zu erläuternden Verfahren der automatischen Wissens-akquisition.
* Es darf sich bei dem System nicht um eine "black box" handeln. Stattdessen ist zu fordern, daß eine Erklärungskomponente vorhanden ist, welche es dem Sachbearbeiter ermöglicht, die Prognose des Systems nachzuvollziehen. Dazu sind einerseits die zur Anwendung gelangten Regeln in einer verständlichen Form zu präsentieren. Andererseits sollte es möglich sein, sich von aggregierten Kostengrößen ausgehend hin zu detaillierteren Kosten-daten, bzw. weiter zu deren technischen Ursachen zu bewegen; dieses Vorgehen wird auch als "Drill-Down-Technik" bezeichnet.
* Es soll auch bei unvollständigen bzw. ungenauen Angaben bezüglich der Merkmale der zu demontierenden Produkte möglich sein, eine Prognose zu stellen. Dabei ist natürlich der Forderung, vorhandene Prognoseunsicherheiten deutlich zu machen, besondere Beachtung zu schenken.
* Das System soll seine Schlüsse so weit wie möglich auf der Grundlage objektiv nachprüf-barer Kriterien ziehen. Damit soll erreicht werden, daß ähnliche Fälle gleich behandelt werden, ohne subjektive Wertungen eines Sachbearbeiters mit einzubeziehen.
Die konkrete Ausgestaltung der Kostenprognose ist in unterschiedlichem Detaillierungsgrad vorstellbar; dieser hängt ab von dem Vorhandensein bzw. Detaillierungsgrad der betrieblichen Datenerfassung und Kostenrechnung. Im Extremfall ist es nicht oder nur unzureichend möglich, technische Konsequenzen zu ermitteln; es muß dann von produktspezifischen Merkmalen direkt auf Zeiten und Kosten geschlossen werden. Auf die daraus resultierenden verschiedenen Möglichkeiten der Kostenkalkulation wird im nächsten Kapitel eingegangen.
Abschließend sei die Architektur eines solchen Systems skizzenhaft dargestellt:

Abb. 1: Architektur eines Systems zur Prognose von Kosten und Zeiten

2.1.3 Verfahren der Kostenprognose

In der Literatur findet sich eine Vielzahl von Verfahren zur Kostenprognose, welche mitunter auch als Vor- oder Kurzkalkulationsmethoden bezeichnet werden [12]⁾. Es soll nun auf die wichtigsten dieser Verfahren eingegangen werden, um diese unter Berücksichtigung der oben aufgestellten Forderungen an ein System zur Unterstützung der Angebotsbearbeitung zu bewerten. Daran anschließend wird ein Vorschlag für ein differenziertes Modell zur Kosten-prognose für die Demontage gemacht.
Grundsätzlich wird in der vorliegenden Arbeit davon ausgegangen, daß eine Preiskalkulation auf der Grundlage von Herstell- bzw. Selbstkosten erfolgt. Obwohl der Begriff "Herstell-kosten" im Zusammenhang mit der Demontage von Produkten unangemessen erscheint, wird er in der vorliegenden Arbeit weiter Verwendung finden, da er sich in der Kostenrechnung weiter Verbreitung erfreut. Diese Kalkulationsmethode auf Basis von Vollkosten ist zwar in letzter Zeit wegen des insbesondere bei einer automatisierten flexiblen Fertigung mitunter gravierenden Mißverhältnisses von Einzel- zu Gemeinkosten in Mißkredit geraten [13]⁾; trotzdem wird das Verfahren in der Praxis noch überwiegend angewendet. Der aus dem Zuschlag von Gemeinkosten auf Produkte nach deren Einzelkostenverursachung resultierende Fehler dieser Methode ist bei einer hochgradig manuell vollzogenen Arbeit - wie der Demontage von Elektro- und Elektronikaltprodukten - besonders gering, was als zusätzliche Rechtfertigung für ihren Einsatz zu werten ist.
Kostenschätzung
Als erstes Vorkalkulationsverfahren ist die Kostenschätzung [14]⁾ zu nennen. Dabei werden ausgehend von vergleichbaren Lösungen durch eine sachkundige Person, dem "Kalkulator", die Herstellkosten einzelner Baueinheiten aus dessen Erfahrungen geschätzt. Hierfür können zusätzlich "wichtige" Merkmale, wie z.B. Gewicht oder Volumen, herangezogen werden ("Kilokostenmethode"). Es liegt auf der Hand, daß dieses Verfahren nicht nur sehr ungenau ist, sondern auch in erheblichem Maße subjektiven Einflüssen unterliegt. Seine Anwendung in einem maschinellen Prognosesystem in der Weise, daß der Versuch unternommen wird, die pauschalen Urteile einer Person in Algorithmen zu fassen, ist daher abzulehnen.
Materialkostenmethode
Als nächstes sei die Materialkostenmethode [15]⁾ angeführt, welche auf der Annahme beruht, die Herstellkosten setzen sich grundsätzlich zu einem nahezu konstanten Anteil aus Material-kosten, Lohnkosten und Fertigungsgemeinkosten zusammen. So ist bei bekannter quantitativer Kostenstruktur eines vergleichbaren Produkts nur die absolute Höhe einer der Kostenarten des neuen Produkts zu bestimmen, um daraus die gesamten Herstellkosten zu ermitteln. Abgesehen von der auch hier mangelnden Genauigkeit und Nachprüfbarkeit aufgrund einer recht zweifel-haften Grundannahme bleibt nach wie vor das Problem, wenigstens die absolute Höhe einer der Kostenarten zu bestimmen. Insgesamt ist das Verfahren aus den genannten Gründen für den Einsatz in einem maschinellen Prognosesystem ebenfalls als untauglich einzustufen.
Einflußgrößenrechnung
Ein weiteres Verfahren ist die Einflußgrößenrechnung [16]⁾. Hier wird der Versuch unter-nommen, mit Hilfe der statistischen Regressionsrechnung einen funktionalen Zusammenhang zwischen quantitativen Produktmerkmalen und Herstellkosten abzuleiten. Dem unter günstigen Umständen hohen Genauigkeitsgrad der so ermitttelten Kostenfunktionen stehen jedoch erhebliche Nachteile gegenüber: Zunächst ist es eine praxisferne Annahme, Produkte seien nur über quantitative Merkmale ausreichend charakterisierbar, um daraus Kosteninformationen abzuleiten. Tatsächlich findet sich in der Praxis regelmäßig eine Mischung von relevanten nominalen, ordinalen und metrisch skalierten Merkmalen. Weiter ist der Aufwand für die Erstellung der Kostenfunktionen erheblich, wobei es sich als besonders nachteilig erweist, daß die verfügbaren Methoden der statistischen Datenanalyse das Vorhandensein aller relevanten Datensätze voraussetzen; eine ständige Aktualisierung der Kostenfunktionen ist daher kaum möglich, so daß das Verfahren den eingangs genannten Forderungen nicht genügt.
Kostenwachstumsgesetze
Als weiteres Verfahren ist die Aufstellung und Anwendung von Kostenwachstumsgesetzen [17]⁾ zu erwähnen. Diesem liegt zugrunde, daß Erzeugnisse aus Baureihen- oder Varianten-konstruktion oftmals Ähnlichkeiten in bezug auf Form, Abmessung etc. aufweisen, so daß es naheliegt, von den Herstellkosten bekannter Teile auf die ähnlicher Teile zu schließen. Auch hier muß ein erheblicher Aufwand für die Erstellung derartiger Gesetzmäßigkeiten betrieben werden. Dabei ist das Verfahren ohnehin nur für solche Produkte geeignet, die aus einer entsprechenden Herstellung stammen bzw. eine durch die Funktion determinierte Ähnlichkeit aufweisen.
Suchkalkulation
Als letztes Verfahren in dieser Reihe soll die Suchkalkulation [18]⁾ Beachtung finden. Hier liegt ein Informationsspeicher bekannter Zuordnungen von Produkten zu Kosten zugrunde, in welchem bei Bedarf nach ähnlichen Produkten gesucht wird, deren Kosten dann übertragen werden. Erforderlich ist hierzu die Definition eines Abstandsmaßes zwischen den relevanten Merkmalen - ein bei einer Mischung von nominalen, ordinalen und metrisch skalierten Merkmalen schwieriges Unterfangen.
Aufgrund der offensichtlichen Unzulänglichkeiten der beschriebenen Verfahren soll nun ein konkurrierender Vorschlag für die Ermittlung prognostizierter Herstellkosten gemacht werden. Dabei wird vom Vorhandensein einer Betriebsdatenerfassung ausgegangen, deren Automatisierungs-, Aktualitäts- und Detaillierungsgrad idealerweise möglichst hoch sein sollte (z.B. unter Nutzung sogenannter BDE-Terminals), jedoch grundsätzlich auch auf niedrigerem Niveau angesiedelt sein kann (z.B. über die Verwendung von Aufschrieben).[19]⁾
Grundgedanke ist es, ein möglichst differenziertes Modell aufzustellen, um einerseits eine hohe Genauigkeit zu erzielen und andererseits die Implementierung einer Erklärungskomponente zu vereinfachen. Dazu ist zunächst von einer direkten Zuordnung von Produkteigenschaften zu Kosten Abstand zu nehmen; stattdessen ist eine zweistufige Vorgehensweise anzustreben:
1) In einer ersten Kalkulationsphase werden aufgrund der Produkteigenschaften wie Funktion, Volumen, Hersteller, Alter etc. technische Konsequenzen prognostiziert. Dabei kann es sich im Falle der Demontage von Elektro- und Elektronikaltprodukten beispielsweise um folgende handeln:
* Spezielle Maschinen oder Verfahren, die für die Vordemontage eingesetzt werden müssen [20]⁾:
- Welche Art der Vorbehandlung ist erforderlich? Ist es realisierbar und lohnenswert, das Gerät teilweise von Hand zu demontieren, oder ist der Einsatz mechanischer Trennverfahren für das gesamte Gerät sinnvoller? Falls mechanische Trennverfahren eingesetzt werden, handelt es sich um Zerkleinerungstechniken (z.B. Shredder, Schneidmühlen, Granulatoren), trockene Sortierverfahren (z.B. Siebe, Windsichter, Aero-Zyklone), naß-mechanische Sortiermethoden (z.B. Schwimm-Sink-Bad, Hydro-Zyklone) oder magnet- bzw. elektrostatische Trenntechniken (z.B. ferromagnetische Verfahren, Wirbelstromscheider)? Falls eine manuelle Demontage möglich ist, können eventuell Bauteile oder ganze Baugruppen wiederverwendet werden, oder ist sogar ein Produktrecycling im Sinne einer Aufarbeitung des Altgerätes möglich?
* Aggregate oder Verfahren, welche für die Stofftrennung einzusetzen sind:
- Welche Verfahren können nach der Vorbehandlung für die Metall-rückgewinnung eingesetzt werden (z.B. pyro- oder hydrometallurgische Verfahren, elektrochemische Verfahren)?
- Welche Techniken sind für die Rückgewinnung der verschiedenen Kunst-stoffe einzusetzen? Hier steht ein Vielzahl unterschiedlicher physikalischer und chemischer Verfahren zur Verfügung, welche je nach Art und Kombination der verwendeten Kunststoffe zum Einsatz gelangen können.
* Der Grad der erforderlichen Qualifikation derjenigen Personen, die mit der Demontage beauftragt werden; beispielsweise setzt die manuelle Kunststoff-sortierung gute Materialkenntnisse des Personals voraus, da die verwendeten Kunststoffe nur bei relativ jungen Altprodukten gekennzeichnet sind [21]⁾.
* Die für die Ausführung der einzelnen notwendigen Schritte zu veranschlagende Zeit.
* Die mit den einzelnen Arbeitsschritten verbundenen stofflichen und energetischen Inputs und Outputs..
* Im Rahmen einer "integrierten Entsorgungssicherung"[22]⁾ sollten zusätzlich Kenn-größen für den zu erwartenden logistischen Aufwand für Sammlung und Transport sowie für die Rückführung der gewonnenen Sekundär-Rohstoffe in den Wirtschafts-kreislauf (Verwertung im engeren Sinne) ermittelt werden. Angesichts einer zunehmenden Verknappung und damit einhergehenden Verteuerung von Deponie- und Verbrennungskapazitäten [23]⁾ ist es weiter von Interesse, die Menge und Art der verbleibenden, nicht weiter verwertbaren Rückstände zu prognostizieren.
2) In der zweiten Phase werden die ermittelten technischen Konsequenzen mit Kostensätzen bewertet, um so zu möglichst differenzierten Einzelposten der Herstellkosten zu gelangen.
Die Ermittlung der technischen Konsequenzen in der ersten Phase sollte dabei vollständig automatisiert sein und auf ständig aktualisiertem Erfahrungswissen beruhen. Das Vorhanden-sein einer solchen ständig aktuellen Wissensbasis ist durch den Einsatz inkrementeller Verfahren der automatischen Wissensakquisition zu erreichen. Die zweite Phase erfordert unter Umständen zuvor ein grundsätzliches Überdenken der in der Kostenrechnung verwendeten Zuordnung von Ressourceninanspruchnahmen zu Kosten.
Durch die so erzielte Trennung der Zuordnung von Produkteigenschaften zu technischen Konsequenzen und deren anschließender Bewertung wird zusätzlich erreicht, daß das gelernte Wissen unabhängig von Änderungen in der Kostenzuordnungspolitik eines Unternehmens Gültigkeit behält. Die Einrichtung einer Erklärungskomponente mit Drill-Down-Möglichkeit dürfte sich hierdurch als sehr einfach erweisen.

2.2 Automatische Wissensakquisition

Unter Wissensakquisition [24]⁾ versteht man den wie auch immer gearteten Prozeß der Gewinnung einer maschinell repräsentierbaren und verarbeitbaren Form von Wissen. Dabei kann es sich um die Transformation von bereits vorhandenem Expertenwissen in eine maschinell repräsentierte Form, aber auch um die Anwendung von Verfahren zum Erwerb neuen Wissens aus vorhandenen Beispielen handeln.
Im ersten Falle findet ein Dialog zwischen dem Experten und einem sogenannten Knowledge Engineer (indirekte Wissensakquisition) bzw. einer maschinellen Akquisitionskomponente (direkte Wissensakquisition) statt. Die Resultate eines solchen Dialogs bilden die Grundlage für die Generierung und Verfeinerung des Maschinenwissens. Dabei steht der Experte als alleinige Wissensquelle im Zentrum der Bemühungen. Diese Vorgehensweise ist jedoch nicht frei von Nachteilen [25]⁾:
* Experten sind selten in der Lage, ihr Wissen vollständig in Form von Regeln o.ä. zu beschreiben, so daß bei der Wissensakquisition ein Informationsverlust hingenommen werden muß.
* Auch das Expertenwissen ist häufig nicht vollständig in Bezug auf den betrachteten Anwendungsfall; hinzu kommt, daß auch Experten häufig Fallbeispiele und Analogiebildung anstelle von Regeln verwenden.
* Der bei einer Wissensakquisition durch Experten hinzunehmende Zeitaufwand ist sehr hoch.
Im zweiten Falle kann auf die Befragung eines Experten vollständig verzichtet werden: Das in Beispielen aus der Vergangenheit der Realwelt implizit enthaltene Wissen wird durch ein vollautomatisches Akquisitionsverfahren entweder in explizite Regeln (induktives Lernen [26]⁾) oder in eine andere, automatische Schlußfolgerungen ermöglichende Darstellungsform überführt (z.B. in die Gewichtematrix eines künstlichen neuronalen Netzes). Diese Vorgehens-weise wird automatische Wissensakquisition genannt. In der Literatur finden sich hierzu Wertungen, die von Begriffen wie "weitgehend Zukunftsmusik"[27]⁾ bis hin zur Ansicht gehen, die wesentlichen Vorarbeiten auf diesem Gebiet seien bereits geleistet und müßten lediglich noch in Anwendungen umgesetzt werden [28]⁾. Im Gegensatz zu einem profunden Experten-wissen sind hier wesentlich geringere Anforderungen an den Kenntnisstand a priori zu stellen; dies sind im einzelnen:
* Domänenstruktur: Es muß detailliertes Wissen über den Wertebereich der Merkmale vorliegen.
* Basiskausalitäten: Es ist zwar nicht unbedingt erforderlich, jedoch vielfach von großer Hilfe, zu wissen, welche Merkmale der beobachtbaren Realwelt einen kausalen Zusammenhang zu den betrachteten Zielgrößen aufweisen.
Die mittlerweile zahlreichen Verfahren der automatischen Wissensakquisition lassen sich bezüglich unterschiedlicher Dimensionen klassifizieren [29]⁾. Diese sind z.B.
* der hauptsächliche Zweck des Lernprozesses: Soll neues Wissen erworben werden (synthetisches Lernen) oder soll bereits bekanntes Wissen in eine andere, effizientere Darstellungsform überführt werden (analytisches Lernen)?
* die Art der Eingangsinformationen: Handelt es sich um bereits klassifizierte Beispiele (überwachtes Lernen) oder um unklassifizierte Beobachtungen (unüberwachtes Lernen)?
* die Art der hauptsächlich angewandten Inferenzmethode: Werden aufgrund gegebener Prämissen und eines gegebenen Hintergrundwissens Konklusionen abgeleitet (deduktive Inferenz), oder werden aufgrund gegebener Konsequenzen und eines gegebenen Hintergrundwissens mögliche Prämissen erzeugt (induktive Inferenz)?
* die Rolle des bereits vorhandenen Hintergrundwissens während des Lernprozesses: Beruht der Lernvorgang in erster Linie auf den Eingangsdaten, auf dem Hintergrundwissens oder auf einer ausgewogenen Kombination beider?
Zu erwähnen ist weiter die Unterscheidung zwischen wissensintensivem Lernen, d.h. der Generierung einer möglichst hohen Anzahl korrekter Regeln, und dem Lernen aus Massendaten, bei dem es eher um das Ziel einer kompakten Darstellung relevanter Zusammenhänge geht. Diesbezüglich muß in der vorliegenden Arbeit ein Kompromiß gefunden werden: Einerseits ist es zu Prognosezwecken wünschenswert, ein möglichst hohes Maß an Wissen aus bekannten Fakten zu extrahieren; andererseits ist gerade im Falle der Anbindung an eine elektronische Betriebsdatenerfassung zu erwarten, daß sich eine Verarbeitung von Massendaten nicht vermeiden läßt.
Bei Einsatz der automatischen Wissensakquisition sind in temporaler Hinsicht folgende Vorgehensweisen zu unterscheiden:
Einmalige Wissensakquisition

Die zur Verfügung stehenden Beispiele werden der automatischen Wissensakquisitions-komponente einmalig zur Verfügung gestellt; anschließend erfolgt die fortwährende Nutzung des generierten Wissens (vgl. Abbildung 2). Eine erneute Wissensakquisition ist zunächst nicht vorgesehen und wird erst durchgeführt, wenn das ursprünglich generierte Wissen mittlerweile varaltet oder unvollständig, mithin offensichtlich unbrauchbar geworden ist. Eine solche Vorgehensweise ist zwar relativ einfach, aber nur dann sinnvoll, wenn die zum Wissens-akquisitionszeitpunkt vorliegenden Beispiel-Datensätze bereits eine recht vollständige Beschreibung der zugrundeliegenden Domäne darstellen.

Abb. 2: Einmalige Wissensakquisition

Intervallweise Wissensakquisition

Nach einer initialen Wissensakquisition wird der Akquisitionskomponente nach bestimmten Intervallen entweder erneut das gesamte bisher vorhandene Beispielwissen zur Neubildung einer Wissensbasis präsentiert, oder nur die nach dem letzten Lernvorgang neu entstandenen Fälle (Delta-Beispiele, vgl. Abbildung 3). Im letzteren Falle muß die Akquisitionskomponente anhand von Konsistenzkriterien selbst entscheiden, ob ein neuer Lernzyklus durchzuführen ist. Die eigentlichen Lernverfahren sind jedoch nach wie vor auf die gleichzeitige Anwesenheit sämtlicher Beispieldatensätze angewiesen. Die Wahl der Intervallänge kann sich dabei an einer festen Zeitvorgabe (z.B. einem Jahr) oder an der Menge der neu entstandenen, also an der Bildung des bisherigen expliziten Wissen noch nicht beteiligten Beispiele orientieren. (Eine Kombination beider Ansätze ist natürlich ebenfalls denkbar, z.B. in einer Regel der Art "Wiederhole den Lernvorgang, falls sich die Anzahl der Beispiele seit dem letzten Lernen um 100 erhöht hat oder ein Jahr vergangen ist".)

Abb. 3: Intervallweise Wissensakquisition

Fortwährende Wissensakquisition

Nach einer eventuellen initialen Wissensakquisition wird jeder neue Beispiel-Datensatz der Akquisitionskomponente zur Verfügung gestellt, sobald er verfügbar ist (vgl. Abbildung 4). Dieses Vorgehen ist sicherlich ideal hinsichtlich des Aktualitätsgrades des in einer maschinell repräsentierten Darstellung vorliegenden Wissens; es stellt jedoch erhöhte Anforderungen an das verwendete Lernverfahren, um zu einem vertretbaren Laufzeitverhalten zu gelangen: Das Verfahren muß inkrementell sein.

Abb. 4: Fortwährende Wissensakquisition
Definition 1: (Inkrementelles Lernverfahren)
Ein Lernverfahren heißt inkrementell, wenn die Erweiterung oder Umstrukturierung des vorhandenen Wissens
* nach jedem neu präsentierten Beispiel-Datensatz und
* ohne die erneute intensive Betrachtung von bereits bearbeiteten Vergangenheitsfällen
erfolgen kann [30]⁾.
Die Forderung einer nicht-intensiven Betrachtung bereits bearbeiteter Vergangenheitsfälle in obiger Definition ist notwendig, da man ohne diese Einschränkung jede nicht-inkrementelle Methode auf triviale Weise inkrementalisieren könnte, indem einfach zur bisherigen Beispiel-menge eines hinzugefügt und das Verfahren erneut angewendet würde. Man beachte jedoch, daß durch diese Definition keineswegs die Speicherung sämtlicher Beispiele ausgeschlossen wird.
Die Vorgehensweise der fortwährenden Wissensakquisition bietet zusätzlich die Möglichkeit, innerhalb des Lernverfahrens Datensätze unterschiedlichen Aktualitätsgrades angemessen zu berücksichtigen. Durch eine Ergänzung der anfallenden Datensätze um einen Zeitstempel könnten z.B. aus jüngeren Datensätzen gebildete Regeln mit höheren Gewichtungsfaktoren als ältere versehen werden. Eine darart optimierte Wissensaktualität erscheint in Anbetracht einer sich ständig ändernden Unternehmensumwelt insbesondere für Systeme zur Prognose von Kosten und Zeiten äußerst erstrebenswert.
Ebenso, wie es realitätsfern erscheint, ein Verfahren zu entwickeln, welches in der Lage ist, Kosten und Zeiten völlig exakt vorherzusagen, so ist es unangemessen, den vorliegenden Beispielen die Möglichkeit einer vollständigen Beschreibung der Wirkungszusammenhänge der Realität zuzuschreiben. Vielmehr ist davon auszugehen, daß die verfügbaren Datensätze nur einen begrenzten Ausschnitt der Realwelt darzustellen in der Lage sind. Ferner muß hin-genommen werden, daß die vorhandenen Beispiele Ungenauigkeiten aufweisen.
Aus diesen Gründen steht die ständige Wissensakquisition unter Berücksichtigung von Unschärfe im Zentrum der Überlegungen dieser Arbeit.
Die in den Lernverfahren angewandten Methoden lassen sich trennen in symbolische und sub-symbolische Akquisitionstechniken. Symbolische Lernverfahren beruhen in der Regel auf der Suche nach geeigneten Konzepten in einem Hypothesenraum. Mit ihnen ist der wesentliche Vorteil verbunden, daß die erlernten Konzepte anschließend direkt in einer symbolischen und somit leicht verständlichen Form vorliegen [31]⁾. Anders verhält es sich z.B. bei künstlichen neuronalen Netzen. Hier wird das erlernte Wissen in sub-symbolischer Form durch eine Gewichtematrix repräsentiert. Die Ergebnisse eines Lernvorgangs lassen sich somit nur sehr schwierig nachvollziehen. Insbesondere ist die Rechtfertigung von Schlußfolgerungen im Sinne einer Erklärungskomponente nur unzureichend realisierbar. Es existieren dazu zwar neuere Ansätze, welche die Aktivierungen bestimmter Neuronen in Abhängigkeit von anderen Neuronen zu erklären versuchen [32]⁾; die Forschungsarbeiten befinden sich in diesem Bereich jedoch erst am Anfang. Hinzu kommen weitere Probleme des Einsatzes künstlicher neuronaler Netze [33]⁾:
* Das Erlernen komplexer Zusammenhänge erfordert in der Regel sehr lange Lernzeiten. Es kann dabei je nach Wahl des Netzwerktyps vorkommen, daß auch nach beliebig langer Laufzeit keine befriedigenden Ergebnisse erzielt werden (Konvergenzproblematik).
* Zur Ausnutzung der inhärenten Parallelität künstlicher neuronaler Netze ist eine sehr aufwendige Hardwareausrüstung erforderlich (Mehrprozessorsysteme), so daß meist auf eine vergleichsweise ineffiziente sequentielle Implementierung ausgewichen wird.
* Es müssen für einen Lernzyklus sämtliche relevanten Beispielmuster vorhanden sein, so daß bei zusätzlichen Beispielen ein gänzlich neues Erlernen aller Muster erforderlich wird. Die auf künstlichen neuronalen Netzen beruhenden Algorithmen sind somit kaum inkrementell zu gestalten.
* Es existieren zwar viele unterschiedliche Modelle mit diversen Möglichkeiten des Adjustierens verschiedener Parameter, jedoch fehlt es an allgemein akzeptierten Vorgehens-weisen bezüglich bestimmter Problemstellungen. Stattdessen wird z.B. bei der Auswahl einer Netztopologie häufig eher intuitiv bzw. unter Anwendung zweifelhafter Heuristiken vorgegangen [34]⁾.
In der vorliegenden Arbeit werden aus diesen Gründen nur symbolische Lernverfahren entwickelt und untersucht.

2.3 Fuzzy Logik

Ziel der Wissensakquisition ist es, ein maschinell repräsentiertes Modell der Realwelt zu entwickeln, welches diese beschreibt und ihre Gestaltung unterstützt. Die Beschreibung der tatsächlichen Realweltzusammenhänge ist notwendigerweise vereinfachend, da eine voll-ständige Abbildung im allgemeinen weder möglich noch wünschenswert ist, wenn das Modell operabel bleiben soll. Nichtsdestotrotz ist es erforderlich, daß ein Modell Strukturgleichheit oder -ähnlichkeit mit dem betrachteten Realweltausschnitt bzw. der Art und Weise, wie dieser von einen Beobachter wahrgenommen wird, besitzt. Nur so kann das Modell eine adäquate Entscheidungsgrundlage bilden [35]⁾. Die Fuzzy Logik (engl. fuzzy = unscharf, undeutlich, verschwommen) stellt eine Möglichkeit dar, diese Eigenschaften eines Modells zu erreichen.
Fuzzy Logik basiert auf der erstmals von Zadeh 1965 aufgestellten Theorie der unscharfen Mengen [36]⁾. Mittlerweile hat die Fuzzy Logik eine regelrechte Renaissance erfahren, wie insbesondere an der mittlerweile unüberschaubaren Anzahl technischer Anwendungen zu ersehen ist. Dabei ist der Bereich der Steuerungs- und Regelungstechnik stark dominierend. In jüngerer Zeit finden sich jedoch vermehrt auch Ansätze einer Einbeziehung von Konzepten der unscharfen Logik in entscheidungstheoretische Modelle [37]⁾, bis hin zur Konstruktion von Fuzzy-Expertensystemen [38]⁾. Im folgenden werden nur diejenigen Konzepte der Fuzzy Logik dargestellt, die für das Verständnis der vorliegenden Arbeit erforderlich sind.
Im Gegensatz zum klassischen Mengenbegriff von Cantor, bei dem ein Objekt entweder zu exakt einer Menge gehört oder nicht, ist ein Objekt in der Theorie unscharfer Mengen einer bestimmten Fuzzy-Menge zu einem bestimmten Grade zuzuordnen. So lassen sich menschliche Begriffe wie "ungefähr zehn", "ziemlich groß" etc. in einer vernünftig handhabbaren Form formal beschreiben.
Definition 2: (Unscharfe Menge)

Sei X eine scharfe Menge von Objekten. Dann heißt

mit

eine unscharfe Menge oder Fuzzy-Menge auf X. Die Menge aller Fuzzy-Mengen auf X heißt .

Dabei heißen die Werte Zugehörigkeitsgrade, welche durch die Zugehörigkeitsfunktion bestimmt werden. Bei der Arbeit mit unscharfen Mengen bietet es sich an, diese zu normalisieren, indem jeder Zugehörigkeitsgrad durch das Maximum aller Zugehörigkeitsgrade dividiert wird:

Definition 3: (Normalisierte unscharfe Menge)

Eine unscharfe Menge heißt normalisiert, falls sämtliche ihrer Zugehörigkeitsgrade innerhalb des Intervalls [0,1] liegen.

Aus dieser Definition geht deutlich hervor, daß es sich bei unscharfen Mengen um eine Verallgemeinerung des klassischen scharfen Mengenbegriffs handelt. Im weiteren Verlauf der vorliegenden Arbeit ist mit dem Begriff "unscharfe Menge" oder "Fuzzy-Menge" grundsätzlich eine normalisierte unscharfe Menge gemeint.

Häufig wird man insbesondere an der (scharfen) Menge derjenigen Elemente interessiert sein, welche eine positive Zugehörigkeit zu einer bestimmten unscharfen Menge besitzen:

Definition 4: (Stützmenge einer unscharfen Menge)

Die scharfe Menge

heißt Stützmenge der unscharfen Menge .

Eine besonders kompakte Darstellung eines bestimmten Typs von Fuzzy-Mengen erreicht man durch die Einführung des Begriffs der Referenzfunktion:

Definition 5: (Referenzfunktion)

Eine Funktion L: [0, +¥ [ ® [0, 1] heißt Referenzfunktion, wenn L(0) = 1 gilt und L in [0, +¥ [ nicht steigend ist.

Folgende Beispiele für Referenzfunktionen finden häufige Verwendung:

(mit d > 0)

Der nun einzuführende Begriff des LR-Fuzzy-Intervalls ist von zentraler Bedeutung für die weiteren Ausführungen.

Definition 6: (LR-Fuzzy-Intervall)

Eine Fuzzy-Menge auf der Grundmenge der reellen Zahlen heißt LR-Fuzzy-Intervall, wenn sich ihre Zugehörigkeitsfunktion mit geeigneten Referenzfunktionen L und R wie folgt darstellen läßt:

(m₁ £ m₂, m₁,m₂ Î IR)

Die eindeutig bestimmten Werte m₁ und m₂ heißen linker bzw. rechter Gipfelpunkt des LR-Fuzzy-Intervalls. Die Größen a und b heißen linke bzw. rechte Spannweite. Als Notation für ein solches LR-Fuzzy-Intervall bietet sich an. Die folgende Grenzwert-betrachtung zeigt, daß es sich auch bei LR-Fuzzy-Intervallen um eine Verallgemeinerung klassischer scharfer Intervalle auf der Menge der reellen Zahlen handelt:

Es werden daher im weiteren Nullwerte für a bzw. b mit zugelassen. Dabei bedeutet ein Nullwert für a (b), daß für alle x < m₁ (x > m₂) die Zugehörigkeitsfunktion den Wert Null annimmt.

Die wesentlichen Vorteile von LR-Fuzzy-Intervallen liegen in ihrer einfachen, kompakten Darstellungform sowie der Tatsache, daß unter Anwendung des hier nicht näher zu erläuternden Erweiterungsprinzips [39]⁾ arithmetische Operationen mit ihnen durchführbar sind.
Um auch auf abzählbaren Grundmengen basierende unscharfe Intervalle zu erhalten, wird der Begriff des diskreten LR-Fuzzy-Intervalls eingeführt:
Definition 7: (Diskretes LR-Fuzzy-Intervall)

Eine unscharfe Menge auf einer abzählbaren Grundmenge X Ì IR heißt diskretes LR-Fuzzy-Intervall, wenn ein LR-Fuzzy-Intervall auf IR existiert, so daß .

Ein weiteres für die folgenden Überlegungen nützliches Konzept ist das eines LR-Fuzzy-Vektors:

Definition 8: (LR-Fuzzy-Vektor)

Ein Vektor

mit , 1 £ i £ n, n Î IN heißt n-stelliger LR-Fuzzy-Vektor. Dabei heißt das LR-Fuzzy-Intervall die i-te Ausprägung von . Falls sämtliche Ausprägungen diskret sind, so heißt n-stelliger diskreter LR-Fuzzy-Vektor. Die Menge aller n-stelligen LR-Fuzzy-Vektoren heißt .

Es sei angemerkt, daß es sich bei einem LR-Fuzzy-Vektor um eine Vereinfachung des Konzepts der linguistischen Variablen [40]⁾ handelt. Es lassen sich damit Mengen von Zuordnungen von Begriffen zu LR-Fuzzy-Intervallen codieren. Es wird jedoch auf die explizite Angabe einer Grammatik für die Zuordnung von linguistischen Termen zu Fuzzy-Mengen verzichtet.
Zur Arbeit mit LR-Fuzzy-Vektoren bietet sich die Einführung einer Anfragefunktion an:
Definition 9: (Anfragefunktion für LR-Fuzzy-Vektoren)

Sei und x Î IR.

Die Abbildung

mit 1 £ i £ n heißt Anfragefunktion für den LR-Fuzzy-Vektor mit den Einträgen .

Beispiel:

Das Gewicht verschiedener Produkte variiere zwischen 10 und 4000 Gramm und lasse sich nach folgenden unscharf formulierten Kategorien unterscheiden:

Kategorie 1 ("leicht"):

Kategorie 2 ("mittel"):

Kategorie 3 ("schwer"):

Als Referenzfunktionen seien L(u) = R(u) = Max(0, 1-u) gewählt. Damit läßt sich nun folgender LR-Fuzzy-Vektor definieren:

Die Anfragefunktion liefert nun beispielsweise folgende Resultate:

2.4 Aktive Datenbanken als Grundlage für die Implementierung wissensbasierter Systeme

Die Ausführungen der Kapitel 2.1 und 2.2 haben die Forderung nach einem wissensbasierten Prognosesystem für die Zwecke der Angebotsplanung aufgestellt, welches zusätzlich in der Lage sein soll, aufgrund neuer Datensätze inkrementell zu lernen. Weiter ist klar geworden, daß ein solches System hierfür grundsätzlich zu einer effizienten Verarbeitung der aus der BDE stammenden Massendaten befähigt sein muß. Wünschenswert ist ferner die Möglichkeit einer parallelen Verwendung des akquirierten Wissens durch mehrere Benutzer. Dem stehen jedoch folgende Eigenschaften herkömmlicher wissensbasierter Systeme entgegen [41]⁾:
* Die Speicherkonzeption erlaubt es häufig nur, Fakten und Regeln im begrenzten Hauptspeicher zu halten, wodurch eine effiziente Verwaltung großer Wissensbasen verhindert wird. Falls die Auslagerung auf sekundäre Speichermedien möglich ist, so sind die vorhandenen Inferenzmechanismen zu einer Verarbeitung dieser Daten häufig nur schlecht in der Lage.
* Ein Mehrbenutzermodus, bei dem jeder Anwender des Systems von an anderer Stelle neu gebildetem maschinellem Wissen sofort profitieren kann, wird typischerweise nicht unterstützt. Es fehlen insbesondere Mechanismen zu einer Koordination paralleler Schreib- und Lesevorgänge verschiedenen Benutzer.
* Es existiert nur eine unzureichende Unterstützung von Maßnahmen zur Behebung von Fehlern bzw. zur Herstellung des Zustandes vor einer Störung.
* Es ist nicht möglich, eine logische Wissensbasis für den Benutzer transparent auf mehrere verschiedene Orte zu verteilen.
Insbesondere die drei letztgenannten Punkte können hingegen für moderne Datenbanksysteme als gelöst betrachtet werden: Es steht mittlerweile eine Vielzahl ausgereifter und erfolgreich implementierter Mechanismen für die Kontrolle paralleler Datenzugriffe (Concurrency Control)[42]⁾, die Behandlung von Fehlersituationen (Recovery)[43]⁾ und die transparente physische Verteilung einer logischen Datenbank [44]⁾ zur Verfügung. Zum ersten Punkt ist anzumerken, daß moderne Datenbanksysteme zwar durchaus hervorragend zur Verwaltung großer Datenmengen geeignet sind, das diesen in der Regel zugrundeliegende relationale Modell jedoch vielfach als semantisch zu schwach und benutzerunfreundlich für die Modellierung von Wissensstrukturen angesehen wird. Dieser Einwand hat zwar seine Berechtigung, er kann jedoch durch die Verwendung aktiver Datenbanksysteme, welche eine Kapselung der zugrundeliegenden Strukturen nach außen hin ermöglichen, relativiert werden.
Definition 10: (Aktives Datenbanksystem)
Ein aktives Datenbanksystem ist ein Datenbanksystem, welches nicht nur die Speicherung von Daten, sondern auch von Funktionen in der Datenbank und deren Ausführung durch das Datenbankmanagementsystem ermöglicht [45]⁾.
In der Literatur finden sich mitunter auch wesentliche härtere Anforderungen an ein aktives Datenbanksystem. So wird z.B. die Möglichkeit zur Deklarierung von "Event-Condition-Action"-Regeln verlangt. Ein Event kann dabei eine bestimmte Datenbank-Operation, ein zeitliches Ereignis oder ein von außen kommendes Prozeßsignal sein. Die Condition ist eine Datenbank-Anfrage oder ein Ausdruck, welcher zu einem booleschen Ergebnis evaluiert wird und auf diese Weise bestimmt, ob die spezifizierte Aktion tatsächlich zur Ausführung gelangt. Aufgrund des Fehlens eines derartig mächtigen Systems wird geschlossen, daß derzeit kein aktives Datenbanksystem kommerziell verfügbar sei [46]⁾. Dieser Argumentation wird hier nicht gefolgt.
Es ist für den vorliegenden Anwendungsfall insbesondere von Interesse, wie Komponenten für die automatische Wissensakquisition und die Inferenzbildung innerhalb eines aktiven Daten-banksystems zu implementieren sind, so daß insgesamt eine Erweiterung des Datenbank-systems zu einem "Expertendatenbanksystem" erreicht wird.
Ein Beispiel für ein ausgereiftes aktives Datenbanksystem im Sinne obiger Definition ist das Standard-Softwareprodukt Oracle 7. Es sollen daher im folgenden kurz diejenigen Konzepte von Oracle 7 vorgestellt werden, welche das System von einer gewöhnlichen relationalen Datenbank zu einem aktiven Datenbanksystem aufwerten.
PL/SQL
PL/SQL (= Procedural SQL) ist eine prozedurale Erweiterung der deklarativen und tupel-mengenorientierten Datenbanksprache SQL. Die Syntax sowie wesentliche Konzepte von PL/SQL sind in weiten Teilen eng an die prozedurale Programmiersprache Ada [47]⁾ angelehnt.
Das strenge Typkonzept sieht Variablen mit einem wohldefinierten Sichtbarkeitsbereich (Scope), für die neben sämtlichen SQL-Datentypen auch beliebig komplex geschachtelte Verbundtypen (Records) erlaubt sind, vor. Über sogenannte PL/SQL-Tabellen können Felder (Arrays) auf skalaren Elementtypen realisiert werden.
Gängige prozedurale Kontrollstrukturen wie Konditionalanweisungen oder Schleifen stehen ebenso zur Verfügung wie normale SQL-Abfragen bzw. -Datenmanipulationen.
Zur Behandlung von Fehlersituationen gibt es eine strukturierte Ausnahmebehandlung (Exception Handling), durch welche sowohl Standardfehler, als auch benutzerdefinierte Ausnahmesituationen kontrolliert behandelt werden können.
Es besteht die Möglichkeit zur Definition von Prozeduren und Funktionen, für die anhand formaler Parameter wohldefinierte Schnittstellen zu schaffen sind. Auch hier finden sich die wesentlichen Konzepte prozeduraler Programmiersprachen wieder: Es gibt die Möglichkeit zur Rekursion und eine als "Überladen" (Overloading) bezeichnete Form des Polymorphismus. Die beliebige Schachtelung von Prozeduren und Funktionen ist ebenfalls erlaubt.
Bei der Arbeit mit PL/SQL fallen jedoch auch erhebliche Schwächen auf:
* Wie bereits erwähnt, dürfen PL/SQL-Tabellen in der aktuellen PL/SQL-Version (2.1.4.0.0) nur für Elemente mit skalarem Datentyp definiert werden. Diese Einschränkung ist bei der Programmierpraxis mehr als lästig, denn wann immer eigentlich ein Feld aus Verbunddatensätzen benötigt wird, muß dieses durch mehrere Felder ersetzt werden, welche auf den skalaren Elementtypen des Verbundtypen definiert sind. Dies läßt sich sich zwar nach außen durch die Verwendung entsprechender Pakete verbergen (siehe hierzu später); nichtsdestotrotz erfordert es einen deutlich erhöhten Programmieraufwand. Für eine der folgenden Versionen von PL/SQL ist eine Aufhebung dieser Einschränkung angekündigt [48]⁾.
* Es gibt keine dynamische Speicherallokation oder -freigabe über Zeigervariablen. Abstrakte Datentypen wie Stacks, Schlangen, Listen etc. müssen somit über die schwachen PL/SQL-Tabellen realisiert werden.
* Es ist keine Interaktion mit dem Benutzer in Form eines Dialogs möglich. Lediglich in Fehlersituationen kann die Ausgabe einer Meldung erfolgen, welche allerdings sodann unweigerlich zum Programmabbruch führt.
Stored Procedures/Functions
Prozeduren und Funktionen können durch Anwendung des CREATE-Kommandos als persistente Datenbankobjekte mit Quell- und Objektcode gespeichert werden. Sie können dann später von anderen Unterprogrammen, Datenbank-Werkzeugen oder aus Anwendungs-programmen heraus aufgerufen werden. Diese Vorgehensweise bietet diverse Vorteile:
* Durch Implementierung einer Bibliothek verschiedenster validierter Funktionen und deren Nutzung durch mehrere Anwendungen läßt sich redundante und fehlerhafte Programmierung vermeiden und somit eine Produktivitätssteigerung erzielen.
* Durch Verlagerung "datennaher" Funktionen aus Anwendungen heraus in das aktive Datenbanksystem läßt sich die Anzahl der Schnittstellen zwischen Applikation und Datenbank deutlich reduzieren, was sich insgesamt in einer Komplexitätsreduktion und einem Geschwindigkeitszuwachs bemerkbar machen kann.
* Auch für den Fall der parallelen Ausführung einer gespeicherten Prozedur bzw. Funktion durch mehrere Benutzer befindet sich durch Anwendung von Memory-Sharing-Mechanismen grundsätzlich nur eine Kopie des auszuführenden Objektcodes im Hauptspeicher.
Packages
Logisch zusammenhängende Prozeduren und Funktionen können zu eigenen persistenten Datenbank-Objekten, sogenannten Packages (Paketen), zusammengefaßt werden. Zusätzlich zu den bereits beschriebenen Vorteilen von Stored Procedures/Functions bietet die Verwendung von Paketen weitere gewichtige Vorzüge:
* Pakete sind ein ausgezeichnetes Mittel der Softwaretechnik zur Modularisierung von Anwendungen. Die Paketspezifikation kann unabhängig von Paketrumpf übersetzt werden, so daß die dort zur Verfügung gestellten Objekte bereits in anderen Paketen referenziert werden können, ohne bereits vollständig implementiert zu sein. Die Aufrechterhaltung der Datenintegrität wird durch das so ermöglichte Information Hiding wesentlich vereinfacht - ein Benutzer erhält nur diejenigen Informationen über eine Routine, die er zu deren Einsatz benötigt, nicht jedoch die Details der Implementierung. Insgesamt stellen Pakete alle Techniken zur Verfügung, die für die Programmierung Abstrakter Datentypen (ADT) benötigt werden - ein weiteres Mittel zur Konsistenzsicherung [49]⁾.
* Die in einem Paket zusammengefaßten Variablen bestehen für den Zeitraum einer Sitzung, d.h. es können Daten zwischen Transaktionen aufrechterhalten werden, ohne zwischen-zeitlich in der Datenbank persistent gemacht werden zu müssen.
* Bei der erstmaligen Verwendung eines Objektes aus einem Paket während einer Sitzung wird das gesamte Paket in den Hauptspeicher geladen. Die zu erwartenden Aufrufe weiterer Unterprogramme aus dem Paket verursachen also anschließend keine zeitraubenden Zugriffe mehr auf den Sekundärspeicher.
Als einziges Manko der PL/SQL-Packages ist die fehlende Möglichkeit zur Implementation generischer Pakete zu nennen. So muß also bei der Implementation eines abstrakten Datentyps für jeden zugrundeliegenden Elementtypen eine eigenständige Version erzeugt werden.
Trigger
Trigger als spezielle Form von Stored Procedures werden nicht durch einen expliziten Aufruf, sondern durch das Eintreten eines zuvor spezifizierten Ereignisses zur Ausführung gebracht. Im Gegensatz zu einer normalen Stored Procedure besitzt ein Trigger jedoch keine nach außen hin spezifizierte Schnittstelle in der Art von Input- oder Output-Parametern. Stattdessen wird ein bestimmtes Ereignis (Update, Insert oder Delete auf einer bestimmten Tabelle) spezifiziert, vor (BEFORE) oder nach (AFTER) dem der Trigger zur Ausführung gelangen soll. Zusätzlich wird noch festgelegt, ob der Trigger nur genau einmal pro auslösendem Befehl (befehlsorientierter Trigger) oder für jeden Datensatz ausgeführt werden soll, welcher durch den Befehl verändert wird (zeilenorientierter Trigger). Innerhalb eines zeilenorientierten Triggers kann man explizit auf den alten und neuen Wert des betroffenen Datensatzes zugreifen.
Da der Trigger-Rumpf aus gewöhnlichem PL/SQL-Code besteht, können von dort insbesondere auch andere Stored Procedures/Functions, die eventuell in Paketen gespeichert sind, zur Abarbeitung gelangen.
Während in der Literatur hauptsächlich auf die Möglichkeiten der Zugangs- bzw. Konsistenz-sicherung und Protokollierung durch Trigger hingewiesen wird [50]⁾, wird das Triggerkonzept in der vorliegenden Arbeit gemeinsam mit den anderen aktiven Elementen von Oracle zusätzlich dazu benutzt werden, inkrementelles Lernen im Rahmen der automatischen Wissensakquisition als Reaktion auf neu eintreffende Datensätze anzustoßen. (Dabei muß es sich allerdings nicht unbedingt um einen Gegensatz handeln: Man könnte die Konsistenz einer Expertensystem-Datenbank als dann gegeben definieren, wenn die Anpassung von Regeln o.ä. an neue Daten-sätze erfolgt ist, so daß ein Trigger auch hier "nur" ein Instrument zur Konsistenzsicherung ist.)

3 Vorüberlegungen zur Akquisition unscharfer Regeln

Ziel der regelbasierten Wissensakquisition ist es, zu einer bestimmten Klasse von Beispiel-objekten eine Menge von Regeln zu generieren, welche es erlauben, für einzelne, eventuell zum Erzeugungszeitpunkt der Regeln noch unbekannte Objekte aufgrund ihrer Merkmals-ausprägungen eine korrekte Klassenzuordnung vorzunehmen. Dabei können zunächst drei verschiedene Arten von Merkmalen unterschieden werden:
* nominale Merkmale: Nominale Merkmale werden durch eine Aufzählung möglicher Ausprägungen gebildet, wobei die Aufzählungsreihenfolge in Bezug auf den zu erlernenden Sachverhalt irrelevant ist. Als Beispiele seien die Attribute "Haarfarbe" mit den möglichen Ausprägungen ("blond", "braun", "schwarz", "rot") oder "Geschlecht" mit den möglichen Ausprägungen ("männlich", "weiblich") genannt. (Die Begriffe "Merkmal" und "Attribut" werden in der vorliegenden Arbeit synonym verwendet.)
* ordinale Merkmale: Bei ordinalen Merkmalen sind die Ausprägungen ebenfalls aufzählbar; die Reihenfolge der Nennung ist jedoch für den zu erlernenden Sachverhalt von Interesse. Als Beispiele seien hier die Attribute "Herstellungsjahr" (Ausprägungen z.B. "1950", "1951", ..., "1995") oder "Qualitätsstufe" mit den möglichen Ausprägungen ("A", "B", "C") angeführt. Ordinale Merkmale lassen sich somit grundsätzlich informationserhaltend durch eine Codierung mittels natürlicher Zahlen beschreiben.
* metrisch skalierte Merkmale: Metrisch skalierte Merkmale haben Attributausprägungen, welche originär aus Teilmengen der Menge der reellen Zahlen stammen. Hier lassen sich z.B. die Merkmale "Gewicht" oder "Volumen" nennen.
In der Praxis anzutreffende Klassifikationsprobleme zeichnen sich häufig durch ein gemeinsames Auftauchen aller drei skizzierten Merkmalstypen aus. Dieser Sachverhalt stellt bereits für die Methoden der multivariaten statistischen Datenanalyse (z.B. Regressions-, Diskriminanz-, Clusteranalyse, Conjoint Analysis) eine erhebliche Problematik dar und erfordert somit eine angemessene Berücksichtigung bei der Entwicklung von Lernverfahren.
Es wird daher nun eine Notation für die Darstellung unscharfer Regeln entwickelt, welche dem Vorhandensein unterschiedlicher Merkmalstypen Rechnung trägt. Dazu werden aufeinander aufbauend zentrale Begriffe wie Beispielobjekt, unscharfe Bedingung, Prämisse und Regel formalisiert. Ferner werden einige Operationen und Maße eingeführt, welche das Arbeiten mit diesen Begriffen ermöglichen.
Zunächst können Attribute und Attributausprägungen zur Formulierung von Bedingungen herangezogen werden:
Definition 11: (Unscharfe Bedingung)

Sei MB eine Merkmalsbezeichnung und eine Fuzzy-Menge auf der Grundmenge der möglichen Ausprägungen dieses Merkmals X. Ein Tupel

heißt dann unscharfe Bedingung für das Merkmal MB. Falls

gilt, die unscharfe Menge also den gesamten Wertebereich des Merkmals MB mit voller Zugehörigkeit umfaßt, so heißt C leer, notiert

Die Menge aller möglichen unscharfen Bedingungen heißt CC.

Man beachte, daß scharfe Bedingungen somit gemäß obiger Definition nur ein Spezialfall unscharfer Bedingungen sind.

Um zu erfahren, inwiefern eine konkret vorliegende Merkmalsausprägung einer bestimmten unscharfen Bedingung genügt, wird ein Kompatibilitätsmaß eingeführt:

Definition 12: (Kompatibilität einer Merkmalsausprägung mit einer Bedingung)

Sei eine unscharfe Bedingung. X sei die Menge der möglichen Ausprägungen des Merkmals MB; x Î X sei eine Merkmalsausprägung. Der Wert der Kompatibilitätsfunktion

heißt Kompatibilität der Merkmalsausprägung x mit der Bedingung C.

Eine Kompatibilität von 1.0 bedeutet also, daß die vorliegende Merkmalsausprägung die Bedingung voll erfüllt, während eine Kompatibilität von 0.0 das Erfülltsein der Bedingung vollständig ausschließt. Werte zwischen 0 und 1 repräsentieren eine entsprechende graduelle Erfüllung der Bedingung.

Unscharfe Bedingungen lassen sich zu Prämissen zusammenfassen, wobei ein wie folgt zu formalisierender Aggregationsoperator Verwendung findet:

Definition 13: (Aggregationsoperator)

Sei X eine Menge reeller Zahlen x₁, ..., x_n aus dem Intervall [0, 1] mit Card(X) >= 2 und die Abbildung N: [0, 1] × [0, 1] -> [0, 1] eine trianguläre Norm (t-Norm) oder Conorm (s-Norm)[51]⁾. Eine Abbildung

heißt Aggregationsoperator.

In diesem Zusammenhang häufig verwendete t-Normen und s-Normen sind z.B.:

	formale Darstellung	Bezeichnung
t-Normen:		Minimum-Operator
		Algebraisches Produkt
s-Normen:		Maximum-Operator
		Algebraische Summe

Abb. 5: Beispiele für t-Normen und s-Normen

Man verwendet t-Normen dazu, um eine dem sprachlichen "Und" entsprechende Verknüpfung unscharfer Bedingungen durchzuführen; s-Normen dienen für die Darstellung des linguistischen "Oder". Eine Vielzahl weiterer Beispiele von t-Normen und s-Normen findet sich in der Literatur [52]⁾.
Damit kann der Begriff der Prämisse nun auf einfache Weise dargestellt werden:
Definition 14: (Prämisse)

Sei ein Vektor unscharfer Bedingungen für unterschiedliche Merkmale und AO ein Aggregationsoperator (n = Anzahl der betrachteten Merkmale). Ein Tupel

heißt dann Prämisse. Die Menge aller Prämissen heißt .

Vorliegende Beispielobjekte werden durch bestimmte Ausprägungen der betrachteten Merkmale und Zugehörigkeiten zu (evtl. unscharfen) Klassen charakterisiert:

Definition 15: (Beispielobjekt, Lerndatenbank)

Seien die X_i (1 £ i £ n) die Mengen möglicher Ausprägungen der Merkmale MB_i und der Vektor eine Zusammenfassung tatsächlich vorliegender Ausprägungen. Sei ferner eine Fuzzy-Menge, welche die Zugehörigkeit zu verschiedenen Klassen K₁ bis K_k repräsentiert. Ein Tupel

heißt dann Beispielobjekt oder kurz Beispiel. Die Menge aller vorhandenen Beispiele ML heißt Lerndatenbank.

Es sei angemerkt, daß die Fuzzy-Menge z.B. das Ergebnis einer Anfragefunktion für einen LR-Fuzzy-Vektor sein kann (vgl. Definition 9). Im Falle scharf abgegrenzter Klassen reduziert sich auf die Angabe derjenigen Klasse mit dem Zugehörigkeitsgrad 1.

Durch eine Verallgemeinerung des Zusammenhangs zwischen Merkmalsausprägung und unscharfer Bedingung läßt sich ein entsprechendes Kompatibilitätsmaß für Vektoren von Merkmalsausprägungen und Prämissen herleiten:

Definition 16: (Kompatibilität von Merkmalsausprägungen mit einer Prämisse)

Sei die Menge aller möglichen Vektoren von Merkmalsausprägungen und ein Element dieser Menge. Sei ferner eine Prämisse. Der Wert der Kompatibilitätsfunktion

heißt Kompatibilität der Ausprägungen mit der Prämisse P.

Eine Regel ist formal die Beschreibung des Zusammenhangs zwischen einer Prämisse und der hieraus als Konklusion abzuleitenden Klassenzugehörigkeit:

Definition 17: (Regel, Konklusion)

Sei eine Prämisse und K eine Klassenbezeichnung. Ein Tripel

heißt dann Regel. Das Tupel (K, m) wird als Konklusion der Regel bezeichnet. Dabei ist der auch als maximale Aktivierung bezeichnete Wert m Î [0, 1] die aus der Kompatibilität mit der Prämisse maximal abzuleitende Zugehörigkeit zur Klasse K.

Es lassen sich durch solche Regeln also Aussagen wie "Wenn das Volumen eines Produktes groß und das Produkt ein Bildschirm ist, dann ist der Transport des Produktes schwierig." formal darstellen. In diesem Beispiel sind "Volumen ist groß" und "Funktion ist Bildschirm" Elemente der Prämisse P, während "Transport ist schwierig" die Konklusion (K, m) bildet. Über den Wert m läßt sich spezifizieren, ob aus der Prämisse eine volle oder nur graduelle Mitgliedschaft in der Klasse "schwieriger Transport" ableitbar ist.

Um aus einer vorhandenen Regel und dem Vorliegen konkreter Merkmalsausprägungen eine Klassenzugehörigkeit ableiten zu können, muß auch für Regeln eine Anfragefunktion eingeführt werden, die wie folgt definiert werden kann:

Definition 18: (Regelanfrage)

Sei

RR die Menge aller möglichen Regeln und R = (P, K_R, m) ein Element dieser Menge,

eine Zusammenfassung von Merkmals-ausprägungen,

die Abbildung INFOP: [0, 1] ´ [0, 1] ® [0, 1] ein Element der Menge aller triangulären Normen TN und

K ein Element der Menge aller möglichen Klassen KK.

Dann heißt die Abbildung

Regelanfrage. Der Inferenzoperator INFOP bestimmt dabei also, wie die maximale Klassenzugehörigkeit µ und die Kompatibilität der Merkmalsausprägungen mit der Regelprämisse zu verknüpfen sind, um so zu einer konkret vorliegenden Aktivierung der Regel zu gelangen.
Falls der verwendete Inferenzoperator mit dem Aggregationsoperator der Regelprämisse übereinstimmt, so könnte aufgrund der Assoziativität triangulärer Normen [53]⁾ der vorstehende Formalismus etwas vereinfacht werden, indem die maximale Klassenzugehörigkeit als zusätzliche unscharfe Bedingung interpretiert wird, deren Kompatibilität den konstanten Wert µ aufweist.
Für die weiteren Ausführungen wird zur Vereinfachung die folgende Vereinbarung getroffen: Sofern nicht anders angegeben, wird grundsätzlich für Aggregations- und Inferenzoperatoren von Regeln der Minimum-Operator verwendet, so daß das vierte Argument der Regelanfrage nicht näher bezeichnet werden muß.
Eine bezüglich einer Klasse und eines vorliegenden Beispielobjekts absolut korrekte Regel führt bei Anwendung der Regelanfrage zu einer Aktivierung, welche exakt der entsprechenden Klassenzugehörigkeit des Beispielobjekts entspricht. Ist dies nicht der Fall, so ergibt sich ein Fehler:
Definition 19: (Individueller Fehler einer Regel)

Sei R = (P, K_R, m) Î RR eine Regel, K Î KK eine bestimmte Klasse und ein Objekt aus der Menge aller möglichen Beispiele EXX mit , . Dann heißt die Abbildung

individueller Fehler der Regel R bezüglich der Klasse K anhand des Beispiels EX.

Der individuelle Fehler gibt also Aufschluß darüber, inwiefern die Aktivierung einer Regel zu einem bestimmten Beispiel einer Klasse von der tatsächlichen Klassenzugehörigkeit des Beispiels abweicht. Anhand dieses Maßes läßt sich nun genauer spezifizieren, wie eine Regel ein bestimmtes Beispiel klassifiziert:

Definition 20: (Korrekte / falsche Klassifikation, Nicht-Überdeckung)

Sei R = (P, K_R, m) eine Regel, ein Beispielobjekt und K Î KK eine Klasse. Das Beispiel EX wird von der Regel R gegen die Toleranzschwelle e Î [0, 1] und die Signifikanz s (0 < s < e) falsch klassifiziert, falls gilt: IF(R, K, EX) > e. Falls IF(R, K, EX) < -e gilt, so wird das Beispiel EX von der Regel R nicht überdeckt. Das Beispiel EX wird von R korrekt klassifiziert, falls die Zugehörigkeit von EX zur Klasse K größer als s ist und gilt: -e £ IF(R, K, EX) £ e. Andernfalls wird EX von der Regel R ebenfalls nicht überdeckt.

Die Bewertung eines Beispiels durch eine Regel mit einer zu hohen Klassenzugehörigkeit wird also als Fehlklassifikation verstanden, während eine zu geringe Aktivierung als Irrelevanz der Regel in Bezug auf das betrachtete Beispiel gewertet wird (Nicht-Überdeckung). Die Überdeckung eines Beispiels durch eine Regel kann somit falsche oder korrekte Klassifizierung bedeuten.

Damit läßt sich das Verhalten einer gegebenen Regel bezüglich einer Lerndatenbank durch folgende Kenngrößen ausdrücken:

Definition 21: (#GOOD, #BAD, #NONC)

Sei R eine Regel, ML eine Lerndatenbank und K eine Klassenbezeichnung. Dann heißt die Anzahl der Beispiele aus ML, welche durch R korrekt bzw. falsch klassifiziert werden, #GOOD(R, ML, K) bzw. #BAD(R, ML, K). Die Anzahl der nicht überdeckten Beispiele wird mit #NONC(R, ML, K) bezeichnet.

Auf die Angabe von Toleranz- und Signifikanzschwellen für die Klassifizierung wurde in obiger Definition der Einfachheit zuliebe verzichtet.

Zu einer vorliegenden Menge von Beipielobjekten läßt sich ermitteln, wie konsistent eine Regel bezüglich einer bestimmten Klasse ist:

Definition 22: (Konsistenzgrad einer Regel)

Sei ML = {EX₁, ..., EX_m} die Menge der vorliegenden Beispielobjekte, R Î RR eine Regel und K Î KK eine Klassenbezeichnung. Dann heißt die Abbildung

Konsistenzgrad der Regel R bezüglich der Klasse K anhand der Beispiele ML.

Beispiele, deren Zugehörigkeitsgrade zu einer Klasse oberhalb eines bestimmten Grenzwertes liegen, können als typische Objekte dieser Klasse betrachtet werden. Häufig wird es von Interesse sein, wie gut eine Regel gerade diese Beispiele klassifiziert, so daß auch hierfür ein Maß eingeführt wird:

Definition 23: (Vollständigkeitsgrad einer Regel)

Sei ML = {EX₁, ..., EX_m} die Menge der vorliegenden Beispielobjekte, R Î RR eine Regel, K Î KK eine Klassenbezeichnung und a Î [0, 1]. sei die Menge ML, reduziert um diejenigen Beispiele, deren Zugehörigkeitsgrad zur Klasse K unterhalb von a liegt. Dann heißt die Abbildung

Vollständigkeitsgrad der Regel R bezüglich der Klasse K anhand der Beispiele ML gegen die Typisierungsschranke a.

4 STAR, Fuzzy-STAR und Incremental Fuzzy-STAR

4.1 Die STAR-Methode

Das Verfahren STAR [54]⁾ beruht auf der Spezialisierung von Prämissen als grundlegendem Mechanismus zur Wissensextraktion. Ausgangspunkt des Verfahrens bildet eine Menge von Beispielobjekten, die folgenden Bedingungen genügen:

Die betrachteten Attribute der Beispiele sind sämtlich nominaler Natur.

Jedes Beispielobjekt ist genau einer scharf abgegrenzten Klasse zugeordnet.

Die Menge der Beispiele ist in sich konsistent, d.h. für und gilt:

Dabei wird wie folgt vorgegangen [55]⁾:
Man bilde zunächst die Menge aller Beispiele, welche derjenigen Klasse angehören, für die es eine Beschreibung zu finden gilt. Aus dieser Menge wähle man ein beliebiges Beispiel als Initialdatensatz zufällig aus. Nun erzeuge man durch mehrfaches Anwenden der Dropping-Condition-Generalisierungsregel [56]⁾ eine Liste von k Regeln (k = Anzahl der Attribute), welche jeweils nur eine einzige Bedingung enthalten: Attribut i = Ausprägung des Attributs i im betrachteten Beispiel (1 <= i <= k). Jede dieser Regeln wird anhand eines Qualitätsmaßes LEF (= lexicographic evaluation functional [57]⁾), in welches z.B. Konsistenz und Vollständigkeit eingehen, anhand aller vorliegenden Beispiele bewertet und entsprechend in die Liste einsortiert. Dabei kann die Größe der Liste durch eine Schranke begrenzt werden. Die in der Liste enthaltenen inkonsistenten Regeln werden nun solange konjunktiv miteinander zu neuen bewerteten Regeln verknüpft und in die Liste einsortiert, bis entweder keine inkonsistenten Regeln mehr in der Liste enthalten sind, oder keine neuen Kombinationen mehr möglich sind. Daraufhin wird aus der so gebildeten Liste die konsistente Regel mit dem höchsten Qualitätsmaß verwendet, um die Menge der Beispiele zur betrachteten Klasse um diejenigen Datensätze zu reduzieren, welche von der Regel überdeckt werden. Nun wähle man aus dieser reduzierten Menge einen weiteren Datensatz aus und wiederhole den Prozeß, bis die Menge der Beispiele leer ist. Die Disjunktion aller zur Reduktion der Beispielmenge verwendeten Regeln bildet eine konsistente Beschreibung der betrachteten Klasse.
Der erläuterte Algorithmus STAR gehört zur Klasse der Lernverfahren, welche durch Spezialisierung Regeln induzieren. Daneben existieren auch Ansätze, welche den umgekehrten Weg verfolgen: Vorliegende Beispiele werden als maximal spezielle Regeln aufgefaßt, welche schrittweise zu generalisieren sind, um zu einer möglichst allgemeinen Klassenbeschreibung zu gelangen.[58]⁾

4.2 Fuzzy-STAR

Es wird in diesem Kapitel ein Verfahren neu konstruiert, welches als eine Erweiterung der bekannten STAR-Methodik zu betrachten ist. Als Hilfsmittel werden dazu Konzepte der Fuzzy-Logik eingesetzt.

4.2.1 Vorüberlegungen

Wie bereits erwähnt, zeichnen sich Realwelt-Domänen in der Regel dadurch aus, daß nominale, ordinale und metrisch skalierte Attribute simultan nebeneinander auftreten. Ferner ist häufig keine scharfe Zuordnung von Beispielobjekten zu einer einzigen Klasse möglich; vielmehr ist gerade bei der Einordnung in Klassen numerischer Grundmengen davon auszugehen, daß nur eine graduelle Zuordnung möglich ist. Um diesem Sachverhalt Rechnung zu tragen, soll nun untersucht werden, wie die Konzepte der Fuzzy Logik für eine Erweiterung der STAR-Methode genutzt werden können. Die zu erarbeitende neue Methode soll daher den Namen "Fuzzy-STAR" erhalten.
Dazu werden zunächst die drei Typen von Merkmalen in Bezug auf ihr Fuzzifizierungs-potential sowie die daraus resultierenden Generalisierungsmöglichkeiten einer näheren Betrachtung unterzogen.
Zunächst ist es sinnvoll, den Begriff der Generalisierung von Bedingungen auf unscharfe Bedingungen zu erweitern:
Definition 24: (Fuzzy-Generalisierung)

Sei eine unscharfe Bedingung (vgl. Definition 11). Eine Abbildung

heißt Fuzzy-Generalisierung, falls gilt:

Man beachte, daß z.B. die Anwendung der Dropping-Condition-Generalisierungsregel [59]⁾ nur einen Spezialfall einer Fuzzy-Generalisierung darstellt: Neben der bereits in der ursprünglichen Bedingung mit voller Zugehörigkeit enthaltenen Merkmalsausprägung werden alle weiteren möglichen Merkmalsausprägungen mit Zugehörigkeitsgrad 1.0 in die generalisierte Bedingung aufgenommen.
Nominale Bedingungen sind grundsätzlich fuzzifizierbar, indem eine unscharfe Menge auf der Grundmenge der Merkmalsdomäne gebildet wird, welche z.B. zu Beginn nur einen Eintrag mit dem Zugehörigkeitsgrad 1.0 besitzt. Die zusätzliche Aufnahme aller weiteren möglichen Merkmalsausprägungen der Domäne mit einem Zugehörigkeitsgrad von 1.0 entspräche einer Anwendung der Dropping-Condition-Generalisierungsregel. Da jedoch bis auf die konkrete Merkmalsausprägung beim betrachteten Beispiel sämtliche möglichen Merkmalsausprägungen als gleichrangig betrachtet werden müssen, ist es nicht ohne weiteres möglich, eine geeignete Heuristik zur Generalisierung von Fuzzy-Mengen auf nominalen Attributen anzugeben. Ferner ist nicht davon auszugehen, daß die vorliegenden Beispiele unscharfe Informationen in Bezug auf nominale Attribute aufweisen. Aus diesen Gründen wird auch bei Fuzzy-STAR für nominale Attribute nur von der Dropping-Condition-Generalisierungsregel Gebrauch gemacht; ein Verfahren, welches auch auf nominalen Attributen beruhende Bedingungen fuzzifiziert, wird später in dieser Arbeit vorgestellt werden (vgl. Kapitel 5).
Völlig anders präsentiert sich die Sachlage bei ordinalen bzw. metrisch skalierten Attributen. Hier ist durchaus davon auszugehen, daß Beispielobjekte mit ungefähren Angaben vorliegen, z.B. weil eine genaue Ermittlung nicht oder nur mit unangemessenen Aufwand erreichbar gewesen wäre oder unvollständige Datensätze im nachhinein durch Schätzungen ergänzt wurden. Ferner erscheint es für die meisten Anwendungen unsinnig, Regeln der Art "Wenn (a = 1.2312) und (b = 3.22221), dann ..." zu bilden. Gerade bei metrisch skalierten Attributen dürften unscharf definierte Bereiche eine bei weitem brauchbarere Grundlage zur Regel-induktion bilden. Eine besonders gut handhabbare Art von Fuzzy-Mengen auf ordinalen bzw. metrisch skalierten Grundmengen sind die bereits eingeführten LR-Fuzzy-Intervalle. Für diese sollen nun zwei recht einfache Fuzzy-Generalisierungen betrachtet werden:
Definition 25: (Gipfelexpansion)

Sei mit eine unscharfe Bedingung (vgl. Definition 11). Die Fuzzy-Generalisierung

heißt Gipfelexpansion.

Definition 26: (Spannweitenexpansion)

Sei C gegeben wie in Definition 25. Die Fuzzy-Generalisierung

heißt Spannweitenexpansion.

Natürlich lassen sich beide Fuzzy-Generalisierungen auch verknüpfen:

Definition 27: (Allgemeine Expansion)

Sei C wieder gegeben wie in Definition 25. Die Fuzzy-Generalisierung

heißt allgemeine Expansion.

Geometrisch bedeutet die Anwendung der beschriebenen Fuzzy-Generalisierungen ein Auseinanderziehen des LR-Fuzzy-Intervalls, welches der zu generalisierenden unscharfen Bedingung zugrunde liegt. Abbildung 6 veranschaulicht dies anhand eines Beispiels, indem die Veränderung eines LR-Fuzzy-Intervalls nach Anwendung einer Gipfel- () bzw. einer Spannweitenexpansion () aufgezeigt wird.

Abb. 6: Beispiel für Gipfel- und Spannweitenexpansion

Weitere Fuzzy-Generalisierungen sind denkbar; beispielsweise könnte eine verallgemeinerte Dilation durchgeführt, also jeder Zugehörigkeitsgrad mit einer Zahl l Î ]0, 1[ potenziert werden. Eine auf diese Weise entstandene Fuzzy-Menge hat allerdings den gravierenden Nachteil, daß sie im allgemeinen nur noch approximativ als LR-Fuzzy-Intervall mit den ursprünglichen Referenzfunktionen darstellbar ist, was numerisch aufwendig sein kann. Aufgrund dessen ist in den folgenden Ausführungen mit "Fuzzy-Generalisierung" grundsätzlich die allgemeine Expansion gemeint.

4.2.2 Das Verfahren

Das Verfahren Fuzzy-STAR arbeitet (wie STAR) auf der Grundlage allmählicher Spezialisierung nach anfänglich maximalen Generalisierungen; dabei ist jedoch nicht nur die Aufnahme einer scharfen Bedingung aufgrund einer konkret vorliegenden nominalen Merkmalsausprägung bzw. die Kombination inkonsistenter Bedingungen zugelassen; stattdessen existiert für jedes Attribut ein aufgrund eines Beispiels gebildeter Spezialisierungs-pfad, auf dem in Richtung stärkerer Spezialisierung gewandert werden darf. Die Bildung dieses Pfades soll nun für die drei betrachteten Merkmalstypen erläutert werden.
Aufgrund ihrer besonders guten Eignung für die Visualisierung von Programmabläufen werden in der vorliegenden Arbeit für die Beschreibung von Algorithmen grundsätzlich Struktogramme verwendet [60]⁾. Zunächst wird der Algorithmus für die Bildung des Spezialisierungspfades zu metrisch skalierten Attributen dargestellt:
Algorithmus: Bildung eines Spezialisierungspfades für einen metrisch skalierten Attributwert
Input: MB: Bezeichnung des betrachteten Merkmals
x_Min [element] IR: minimal möglicher Wert des betrachteten Attributs
x_Max [element] IR: maximal möglicher Wert des betrachteten Attributs
x_Min <= x <= x_Max: tatsächlich vorliegende Merkmalsausprägung
[delta] > 0: initialer Spannweitenwert
[lambda] > 1: Spannweitenmultiplikator
n [element] IN^>1: Anzahl der gewünschten Spezialisierungen
L, R: linke bzw. rechte Referenzfunktion
Output: Spezialisierungspfad der Ordnung n mit

, 0 £ i £ n

Beschreibung:

DO i = n-1 (-1) 1

Abb. 7: Bildung eines Spezialisierungspfades für einen metrisch skalierten Attributwert

Es wird also durch sukzessive allgemeine Expansion eine Folge unscharfer Bedingungen produziert, welche nach ihrem jeweiligen Spezialisierungsgrad aufsteigend sortiert sind. Im Falle ordinaler Attribute ergeben sich nur geringfügige Änderungen:

Algorithmus: Bildung eines Spezialisierungspfades für einen ordinalen Attributwert

Input: MB: Bezeichnung des betrachteten Merkmals

x_Min Î IN: minimal möglicher Wert des betrachteten Attributs

x_Max Î IN: maximal möglicher Wert des betrachteten Attributs

x_Min £ x £ x_Max: tatsächlich vorliegende Merkmalsausprägung (Î IN)

0 < d £ 1: initialer Spannweitenwert

l > 1: Spannweitenmultiplikator

n Î IN^>1: Anzahl der gewünschten Spezialisierungen

L, R: linke bzw. rechte Referenzfunktion

Output: Spezialisierungspfad der Ordnung n mit

, 0 £ i £ n

Beschreibung:

DO i = n-1 (-1) 1

Abb. 8: Bildung eines Spezialisierungspfades für einen ordinalen Attributwert

(Der Ausdruck ë xû liefert die größte ganze Zahl, welche kleiner als x ist.)

Für nominale Attribute besteht der Spezialisierungspfad grundsätzlich nur aus zwei Einträgen: C₀ = (MB, Æ ) und C₁ = (MB, {x}); dabei ist x wieder die beim betrachteten Beispiel vorliegende Merkmalsausprägung. Der Ausdruck bezeichnet zukünftig die i-te unscharfe Bedingung eines Spezialisierungspfades.

Zwei auf Grundlage desselben Beispiels erzeugte Regeln mit gleichen Konklusionen dürfen miteinander verschmolzen werden, wenn in jeder der beiden Prämissen mindestens eine Bedingung enthalten ist, welche spezieller als ihre Entsprechung in der potentiellen Partnerregel ist. Die Verschmelzung wird dann wie folgt durchgeführt:

Definition 28: (Auswahl der spezielleren zweier Bedingungen)

Seien C₁ und C₂ zwei unscharfe Bedingungen desselben Spezialisierungspfades der Länge n, d.h. und . Dann führt die Abbildung

zur Auswahl der spezielleren der beiden Bedingungen.

Definition 29: (Verschmelzung von Regeln)

Seien R₁ = {P₁, K, m} Î RR mit und sowie R₂ = {P₂, K, m} Î RR mit und zwei Regeln, die mit-einander verschmolzen werden dürfen. Die Abbildung

heißt dann Verschmelzung der Regeln R₁ und R₂.

Einzelne Objekte der Beispieldatenbank werden im Verlauf des Verfahrens dazu herangezogen, einen individuellen F-STAR zu bilden:

Algorithmus: Bildung eines individuellen F-STARs für ein Beispielobjekt zu einer Klasse

Input: : Beispielobjekt

ML: Lerndatenbank

K: Klassenbezeichnung

Output: eine Menge MM von bewerteten Regeln (individueller F-STAR)

Beschreibung:

m ¬ Anzahl der Merkmale

MM ¬ leere Menge von 4-Tupeln aus Regeln und den

korrespondierenden Bewertungen #GOOD, #BAD und #NONC

DO i = 1 (+1) m

Bilde für jede vorliegende Merkmalsausprägung

einen Spezialisierungspfad .

Bilde eine maximal generalisierte Regel R = (P, K, m) mit und derart, daß und m der aus stammende Zugehörigkeitswert des Beispiels EX zur Klasse K ist.

Bewerte R anhand von ML und füge das resultierende 4-Tupel

(R, #GOOD, #BAD, #NONC) in MM ein.

Wiederhole, solange durch Spezialisierung von Regeln mit #BAD > 0 neue Regeln erzeugt werden können, die nicht spezieller als bereits vorhandene Regeln mit #BAD = 0 sind:

Wähle eine Regel R_A aus MM, für die #BAD > 0 gilt.

Ist eine Regelverschmelzung

möglich?

Ja Nein

Wähle eine Regel R_B aus MM Bilde R_N, indem eine

und verschmelze diese mit R_A zu Bedingung aus R_A durch

R_N = Merge(R_A, R_B). ihren direkten Nachfolger

im Spezialisierungspfad

ersetzt wird.

Bewerte R_N anhand von ML und füge das Ergebnis in MM ein.

Abb. 9: Bildung eines individuellen F-STARs für ein Beispielobjekt zu einer Klasse

Mit der Bildung eines individuellen F-STARs liegt nun die wesentliche Grundlage des Fuzzy-STAR-Algorithmus vor. Dieser beruht darauf, daß zunächst zu "typischen", später auch "untypischen" Beispielen einer bestimmten Klasse solange individuelle F-STARs gebildet werden, bis alle Beispiele dieser Klasse gut erfaßt werden. Im Gegensatz zum klassischen STAR-Algorithmus, bei welchem die Menge, anhand welcher Regeln gebildet und bewertet werden, sukzessiv um bereits überdeckte Beispiele reduziert wird, arbeitet Fuzzy-STAR mit einer Bildungsliste und einer Bewertungsmenge. Dabei werden solche Beispiele, die korrekt mit der für die Regel maximal möglichen Aktivierung klassifiziert werden, aus der Bewertungsmenge entfernt. Sämtliche korrekt klassifizierten Beispiele werden jedoch aus der Bildungsliste entfert, so daß sie nicht mehr für die Generierung neuer individueller F-STARs herangezogen werden können. Durch diese Vorgehensweise wird vermieden, daß im späteren Verlauf erzeugte Regeln bereits betrachtete Beispiele falsch klassifizieren. Jede Regel klassifiziert zumindest das ihren Spezialisierungspfaden zugrundeliegende Beispielobjekt korrekt. Somit wird also auch die Bildung solcher Regeln verhindert, die kein Beispiel überdecken und damit später nichts zu einer Klassifikation beitragen können.
Der Algorithmus zur Bildung des Fuzzy-STARs stellt sich im Detail wie folgt dar:
Algorithmus: Bildung eines Fuzzy-STARs für eine Klasse anhand einer Menge von Beispielen
Input: K: Klassenbezeichnung
ML: Lerndatenbank ( = Bewertungsmenge)
[sigma] [element] ]0, 1[: Typisierungsschranke
Output: Fuzzy-STAR S^* für die Klasse K anhand der Beispiele ML
Beschreibung:

S^* <- leere Menge von Regeln

Sortiere die in der Lerndatenbank ML enthaltenen Beispielobjekte gemäß ihrer Zugehörigkeitsgrade zur Klasse K und speichere das Ergebnis in einer Liste L (Bildungsliste).

Wiederhole
EX^* <- dasjenige Beispiel aus L mit dem höchsten
Zugehörigkeitsgrad zur Klasse K
Bilde zu EX^* anhand von K und ML den individuellen F-STAR FS^*;
R^* <- die am wenigsten spezielle aller Regeln aus FS^*, welche
#GOOD maximieren
Entferne alle Beispiele aus L, welche von R^* korrekt klassifiziert
werden;
Entferne alle Beispiele aus ML, welche von R^* korrekt mit der für
R^* angegebenen maximalen Zugehörigkeit klassifiziert werden;
Füge die Regel R^* in die Menge S^* ein;
bis L kein Beispiel mehr enthält, dessen Zugehörigkeit zur Klasse K oberhalb der Typisierungsschranke [sigma] liegt;

Abb. 10: Bildung eines Fuzzy-STARs für eine Klasse anhand einer Menge von Beispielen
Ein Fuzzy-STAR ist also die Zusammenfassung derjenigen Regeln aus den zu den einzelnen Beispielobjekten gebildeten individuellen F-STARs, welche gemeinsam in der Lage sind, sämtliche bisher präsentierten Beispiele korrekt zu klassifizieren.
Die Klassifizierung eines Beispiels auf der Grundlage eines auf diese Weise gebildeten Fuzzy-STARs geschieht folgendermaßen:
Definition 30: (Fuzzy-Klassifizierung)

Sei eine Zusammenfassung von Merkmals-ausprägungen und S^* = {R₁, ..., R_n} ein Element der Menge SS^* aller möglichen Fuzzy-STARs zu einer Klasse K Î KK. Dann heißt die Abbildung

Fuzzy-Klassifizierung.
Das Ergebnis der Fuzzy-Klassifizierung ist also die aufgrund eines gegebenen Fuzzy-STARs zu vermutende Zugehörigkeit eines Objektes mit bestimmten Merkmalsausprägungen zu einer Klasse K.

4.2.3 Ein Beispiel

Die Arbeitsweise des vorstehend geschilderten Algorithmus soll nun anhand eines Beispiels demonstriert werden. Die durch die Beispielobjekte gegebenen Attributausprägungen beziehen sich auf die Merkmale
* Funktion (nominal; Wertebereich: "Bildschirm", "Drucker", "Zentral-einheit", "Tastatur"),
* Herstellungsjahr (ordinal; Wertebereich: 1950 - 1995) und
* Gewicht (metrisch; Wertebereich: 0 - 30).
Dazu seien zunächst die folgenden fünf Datensätze gegeben:

Nummer	Funktion	Herst.-Jahr	Gewicht	Shredder-Zeitaufwand
EX₁	Bildschirm	1960	30,0 kg	45,0 Sek.
EX₂	Bildschirm	1980	15,0 kg	40,0 Sek.
EX₃	Drucker	1985	6,0 kg	17,5 Sek.
EX₄	Tastatur	1985	0,5 kg	12,5 Sek.
EX₅	Zentraleinheit	1989	29,0 kg	45,0 Sek.

Abb. 11: Beispiel-Datensätze

Der jeweils verursachte Zeitaufwand an der Shreddermaschine kann folgenden, durch einen LR-Fuzzy-Vektor codierten Fuzzy-Mengen zugeordnet werden:

mit

Klasse 1 ("niedrig"):

Klasse 2 ("normal"):

Klasse 3 ("hoch"):

Als Referenzfunktionen seien L(x) = R(x) = max(0, 1- x) gegeben, so daß sich die Zuordnung von Zeitaufwand zu Fuzzy-Mengen wie folgt darstellen läßt:

Abb. 12: LR-Fuzzy-Vektor für Shredder-Zeitaufwandsklassen

Durch Anwendung der Anfragefunktion für den LR-Fuzzy-Vektor (vgl. Definition 9) auf den jeweiligen Zeitaufwand erhält man die Zugehörigkeit der Beispieldatensätze zu den Zeit-aufwandsklassen:

Abb. 13: Zugehörigkeit der Beispieldatensätze zu Zeitaufwandsklassen

Es soll nun der Fuzzy-STAR für die Klasse 2 ("normal") gebildet werden. Die nach dem jeweiligen Zugehörigkeitsgrad zur Klasse 2 absteigend sortierte Bildungsliste lautet L = (EX₃, EX₂, EX₁, EX₄, EX₅), so daß der Algorithmus also mit der Bildung des individuellen F-STARs für Beispiel 3 beginnt. Hierzu müssen zunächst für die betrachteten Merkmale die jeweiligen Spezialisierungspfade gebildet werden; als initiale Spannweite wird für ordinale Attribute 1,0, für metrisch skalierte Attribute ein Zehntel der Länge des Wertebereichs gewählt; ferner wird der Spannweitenmultiplikator 2,0 eingesetzt. Als Referenzfunktionen werden grundsätzlich L(x) = R(x) = max(0, 1 - x) verwendet. Es werden maximal 3 Spezialisierungen gewünscht. Bei Wahl dieser Parameter ergeben sich folgende Spezialisierungspfade für Beispiel 3:

Abb. 14: Spezialisierungspfade für Datensatz EX₃
Nun können die Regeln des individuellen F-STARs erzeugt werden; für die Klassifizierung von Datensätzen durch eine generierte Regel wird dabei die Toleranzschwelle [epsilon] = 0,1 und die Signifikanz [sigma] = 0,1 zugrunde gelegt (vgl. Definition 20); für die Aggregation und Inferenz wird der Minimum-Operator verwendet:

Regel	#GOOD	#NONC	#BAD
R₀ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(0)), "normal", 0,75)	1	0	4
R₁ = ((P^Fkt(1), P^HJahr(0), P^Gewicht(0)), "normal", 0,75)	1	4	0
R₂ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(0)), "normal", 0,75)	2	0	3
R₃ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(1)), "normal", 0,75)	1	0	4
R₄ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(1)), "normal", 0,75)	2	0	3
R₅ = ((P^Fkt(0), P^HJahr(2), P^Gewicht(1)), "normal", 0,75)	1	1	3
R₆ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(2)), "normal", 0,75)	1	2	2
R₇ = ((P^Fkt(0), P^HJahr(2), P^Gewicht(2)), "normal", 0,75)	1	2	2
R₈ = ((P^Fkt(0), P^HJahr(3), P^Gewicht(2)), "normal", 0,75)	1	3	1
R₉ = ((P^Fkt(0), P^HJahr(2), P^Gewicht(3)), "normal", 0,75)	1	4	0

Abb. 15: Individueller F-STAR für Datensatz EX₃ (Verfahren Fuzzy-STAR)
Regel R₅ wird nun exemplarisch zu einer Erläuterung obiger Tabelle herangezogen. Die Prämisse dieser Regeln besteht aus drei unscharfen Bedingungen, von denen die erste leer ist, da sie den gesamten Wertebereich des Merkmals "Funktion" mit voller Zugehörigkeit umfaßt (vgl. Definition 11). Die Bedingung zum Merkmal "Herstellungsjahr" bezieht sich auf den zweiten, die zum Merkmal "Gewicht" auf den ersten Eintrag im jeweiligen Spezialisierungs-pfad. Die Regel kann also linguistisch z.B. wie folgt formuliert werden: "Falls das Produkt ungefähr zwischen den Jahren 1974 und 1988 hergestellt wurde und sein Gewicht etwa im Bereich von 2 bis 22 kg liegt, so beträgt die Zugehörigkeit zur Klasse ´normaler Shredder-Zeitaufwand´ 0,75." Die Bewertung dieser Regel lautet #GOOD = 1, #NONC = 1 und #BAD = 2 (vgl. Definition 21). Sie klassifiziert also ein Beispiel korrekt und zwei Beispiele falsch; ein weiteres Beispiel wird von der Regel nicht überdeckt. Die Anzahl der von einer Regel nicht überdeckten Beispiele #NONC ist für den Ablauf des Verfahrens eigentlich unerheblich; sie wird der Übersichtlichkeit zuliebe dennoch grundsätzlich mit angeführt werden.
Die Regeln 2 bis 8 werden bezüglich des Merkmals "Funktion" nicht weiter spezialisiert, da jede so erzeugte Regel spezieller als Regel 1 wäre. Diese jedoch kann durch weitere Spezialisierung nicht mehr verbessert werden: Von einer Regel nicht überdeckte Beispiele können durch eine speziellere Regel keinesfalls korrekt klassifiziert werden. Als beste Regel wird demnach nun R₁ ausgewählt und als erste in den Fuzzy-STAR S^* aufgenommen. Datensatz EX₃ wird von dieser Regel mit maximal möglicher Aktivierung korrekt klassifiziert, so daß er sowohl aus der Bewertungsmenge ML, als auch aus der Bildungsliste L entfernt werden kann. Das nun laut Bildungsliste zur Generierung des nächsten individuellen F-STARs heranzuziehende Bespiel ist Datensatz EX₂, für den zunächst die Spezialisierungspfade erzeugt werden:

Abb. 16: Spezialisierungspfade für Datensatz EX₂
Die zu erzeugenden Regeln lauten:

Regel	#GOOD	#NONC	#BAD
R₀ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(0)), "normal", 0,5)	1	0	3
R₁ = ((P^Fkt(1), P^HJahr(0), P^Gewicht(0)), "normal", 0,5)	1	2	1
R₂ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(0)), "normal", 0,5)	1	0	3
R₃ = ((P^Fkt(1), P^HJahr(1), P^Gewicht(0)), "normal", 0,5)	1	2	1
R₄ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(1)), "normal", 0,5)	1	0	3
R₅ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(1)), "normal", 0,5)	1	0	3
R₆ = ((P^Fkt(1), P^HJahr(0), P^Gewicht(1)), "normal", 0,5)	1	0	3
R₇ = ((P^Fkt(1), P^HJahr(1), P^Gewicht(1)), "normal", 0,5)	1	3	0
R₈ = ((P^Fkt(0), P^HJahr(2), P^Gewicht(0)), "normal", 0,5)	1	2	1
R₉ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(2)), "normal", 0,5)	1	3	0
R₁₀ = ((P^Fkt(1), P^HJahr(2), P^Gewicht(0)), "normal", 0,5)	1	3	0
R₁₁ = ((P^Fkt(0), P^HJahr(2), P^Gewicht(1)), "normal", 0,5)	1	2	1
R₁₂ = ((P^Fkt(0), P^HJahr(3), P^Gewicht(0)), "normal", 0,5)	1	3	0

Abb. 17: Individueller F-STAR für Datensatz EX₂ (Verfahren Fuzzy-STAR)
Die Generierung von Regeln, die spezieller sind als die Regeln R₇, R₉ und R₁₀, wird aus dem gleichen Grunde wie oben vermieden. Regel R₇ wird als beste ausgewählt und dem Fuzzy-STAR S^* hinzugefügt. Datensatz EX₂ wird von dieser Regel mit maximal möglicher Aktivierung korrekt klassifiziert, so daß er sowohl aus der Bewertungsmenge ML, als auch aus der Bildungsliste L entfernt werden kann. Für den als nächstes zur Bildung eines individuellen F-STARs heranzuziehenden Datensatz EX₁ führt bereits die maximal generalisierte Regel R₀ zu einer korrekten Klassifizierung aller Datensätze in der Bewertungsmenge, so daß der Fuzzy-STAR für die Klasse "normal" insgesamt lautet:
S^* ={ ( ( (Funktion, {"Drucker"}),
(Herst.-Jahr, (1950; 1995; 0; 0)_LR),
(Gewicht, (0; 30; 0; 0)_LR) ), "normal", 0,75 ),
( ( (Funktion, [emptyset]),
(Herst.-Jahr, (1950; 1995; 0; 0)_LR),
(Gewicht, (10; 20; 6; 6)_LR) ), "normal", 0,5 ),
( ( (Funktion, [emptyset]),
(Herst.-Jahr, (1950; 1995; 0; 0)_LR),
(Gewicht, (0; 30; 0; 0)_LR) ), "normal" 0,25 ) }
Die Fuzzy-Klassifizierung führt nun für jedes der ursprünglichen Beispiele zu einer korrekten Zugehörigkeit zur Klasse "normal". Für die übrigen Klassen ist ebenso vorzugehen.

4.2.4 Nutzung für die Prognose

Die Fuzzy-Klassifizierung neuer Beispiele ergibt bisher "nur" Zugehörigkeitsgrade zu einzelnen Klassen. Um zu einer konkreten Prognoseaussage zu gelangen, ist daher noch eine Umformung dieser Zugehörigkeitsgrade in eine verständlichere Darstellungsweise erforderlich. Dabei sind die beiden folgenden Fälle zu unterscheiden:
1. Der Benutzer des Verfahrens wünscht lediglich eine tendenzielle Aussage der Art "Der Zeitaufwand an der Shreddermaschine liegt vermutlich im Normalbereich, wobei die Tendenz eher in Richtung ´hoch´ weist.". Derartige Aussagen sind leicht zu generieren, indem z.B. diejenige Klasse, zu welcher ein Beispiel aufgrund der Fuzzy-Klassifizierung die höchste Zugehörigkeit aufweist, als Hauptvermutung geliefert wird, und die Klasse mit der zweithöchsten Zugehörigkeit die zusätzliche Tendenz angibt.
2. Der Benutzer des Verfahrens wünscht konkrete Zahlenwerte. Um dies zu erreichen, ist eine Defuzzifizierung erforderlich, die auf vielfältige Weise erfolgen kann (z.B. Mean-of-Maximum-Methode, Schwerpunktmethode, Center-of-Area-Methode etc.[61]⁾). Es sollte allerding in jedem Falle vermieden werden, durch die alleinige Angabe eines errechneten Zahlenwertes eine Prognosegenauigkeit zu suggerieren, welche durch das Verfahren nicht erreicht werden kann.
In beiden Fällen ist vor der Produktion eines Ergebnisses zu überprüfen, ob die erzeugten Zugehörigkeitswerte überhaupt einen Aussagewert besitzen. So könnte es bezogen auf das vorliegende Beispiel vorkommen, daß eine hohe Zugehörigkeit zu den Klassen "niedrig" und "hoch" errechnet wird, jedoch nur eine geringe für die Klasse "normal" - ein bei der vorliegenden Zuordnung von Zeitaufwand zu LR-Fuzzy-Intervallen inkonsistentes Ergebnis. In solchen Fällen ist aufgrund des vorliegenden Fuzzy-STARs keine sinnvolle Prognose möglich.
Das dargestellte Verfahren liefert unter anderem dadurch, daß aus jedem individuellen F-STAR nur eine einzige Regel für die Bildung des Fuzzy-STARs gewählt wird, eine knappe, jedoch konsistente Beschreibung derjenigen Aspekte, welche die Zuordnung der betrachteten Beispiele zu den Klassen ermöglichen. Insbesondere für die Prognose der Klassen-zugehörigkeiten neuer Merkmalsausprägungen erscheint es jedoch wünschenswert, aus den vorhandenen Beispielen mehr als dieses Minimum an Wissen zu extrahieren. Dieser Gedanke wird neben anderen im folgenden Kapitel mit in die Betrachtungen einbezogen.

4.3 Incremental Fuzzy-STAR

In diesem Kapitel wird ein Verfahren neu entworfen, welches die soeben entwickelte Methode Fuzzy-STAR dahingehend erweitert, daß inkrementelles Lernen im Sinne von Definition 1 möglich wird.

4.3.1 Vorüberlegungen

Wesentliche Vorbedingung für das vorstehend präsentierte Verfahren Fuzzy-STAR ist das gleichzeitige Vorhandensein aller verfügbaren Beispielobjekte. Dies ist leicht einzusehen, werden doch die vorhandenen Beispiele vor der Bildung des Fuzzy-STARs anhand ihrer Zugehörigkeiten zu einer bestimmten Klasse absteigend sortiert. Nur dadurch ist es später möglich, bereits korrekt klassifizierte Beispiele aus der zur Bewertung heranzuziehenden Lerndatenbank ML bzw. aus der Bildungsliste L zu entfernen, ohne Gefahr zu laufen, daß diese entfernten Beispiele durch später erzeugte Regeln falsch klassifiziert werden.
Diese Bedingung ist nicht mehr erfüllt, wenn über die Reihenfolge, in welcher die Datensätze präsentiert werden, keine Kenntnis vorliegt, jedoch dennoch eine ständig aktuelle Regelbasis gewünscht wird. Aus diesem Grunde muß bei einer Inkrementalisierung des Fuzzy-STAR-Verfahrens darauf verzichtet werden, die Bewertungsmenge um korrekt klassifizierte Beispiele zu reduzieren. Eine Bildungsliste L existiert nicht mehr, da jeder neue Datensatz sofort zu einer Aktualisierung der Regelbasis verwendet werden soll.
Ferner soll aus jedem Beispiel ein Maximum an Wissen extrahiert werden, um die Wahrscheinlichkeit einer Prognosefähigkeit für neue Datensätze zu erhöhen. Um dies zu erreichen, sind aus den individuellen F-STARs sämtliche Regeln zur Bildung des Fuzzy-STARs heranzuziehen, welche als "nützlich" zu betrachten sind:
Definition 31: (Nutzen einer Regel)
Eine Regel R eines gegebenen individuellen F-STARs F^* heißt nützlich, wenn sie mindestens ein Beispiel korrekt, jedoch keines falsch klassifiziert, sowie gleichzeitig maximal-generalisiert ist in dem Sinne, daß im selben individuellen F-STAR keine generellere Regel existiert, welche ebenfalls keines der Beispiele falsch klassifiziert.
Weiter erscheint es sinnvoll, bereits erzeugte Regeln, die jedoch nicht zur Bildung eines Fuzzy-STARs herangezogen wurden, nicht zu "vergessen". Stattdessen sollten sämtliche individuellen F-STARs in einer Form gespeichert werden, welche eine effiziente Änderung erlaubt. So ist es möglich, das Verfahren tatsächlich inkrementell (im Sinne von Definition 1) zu gestalten, d.h. ohne die intensive Neubetrachtung von Vergangenheitsfällen auszukommen.

4.3.2 Das Verfahren

Zunächst wird dargestellt, wie die Bildung individueller F-STARs zu erweitern ist, um eine beschleunigte spätere Anpassung an neue Beispiele zu ermöglichen.
Eine wichtige Zusatzinformation für Regeln, deren Bewertung es zu modifizieren gilt, ist die Art und Weise ihrer Entstehung. Für jede Regel - abgesehen von der zuerst erzeugten maximal-generalisierten - kann mindestens eine Regel angegeben werden, aus der sie durch Spezialisierung hervorgeht; im Falle des Entstehens durch Verschmelzung handelt es sich um genau zwei Regeln. Die vorgenommene Spezialisierung läßt sich also insgesamt durch einen gerichteten azyklischen Graphen darstellen:
Definition 32: (Spezialisierungsgraph)
Sei F = (R₁, ..., R_n) ein individueller F-STAR mit n erzeugten Regeln R₁ bis R_n. Dann heißt das Tupel

SG = (N = {1, ..., n}, V = {(x, y) [element] N²})

Spezialisierungsgraph zu F. Dabei bezeichnet N die Menge der Knoten und die Relation V als Teilmenge des kartesischen Produkts N×N die Menge der Kanten zwischen diesen. Eine Kante (x, y) [element] V trägt dabei die Semantik "Regel R_y entsteht direkt durch Spezialisierung von Regel R_x".
Als Beispiel sei der folgende Spezialisierungsgraph dargestellt, welcher dem ersten individuellen F-STAR im Beispiel zur Methode Fuzzy-STAR entspricht:

Abb. 18: Beispiel für einen Spezialisierungsgraphen

Mit "direkter Spezialisierung" ist gemeint, daß eine Regel R_y entweder durch Vollziehung eines Schrittes auf einem der Spezialisierungspfade aus einer Regel R_x oder unter Zuhilfenahme einer dritten Regel R_z durch Verschmelzung von R_x mit R_z entsteht.
Satz 1:
Sei SG = (N = {1, ..., n}, V = {(x, y) [element] N²}) ein Spezialisierungsgraph. Eine Regel R_v ist spezieller als eine Regel R_u, notiert R_v <_s R_u, wenn das Tupel (u, v) Element der transitiven Hülle [62]⁾ V⁺ der Relation V ist.
Da die Berechnung der transitiven Hülle nicht-polynomialen Aufwand erfordert, wird man bei einer Implementierung der Suche nach spezielleren Regeln zu einer bestimmten Regel den gegebenen Spezialisierungsgraph traversieren, anstatt auf Mitgliedschaft in der transitiven Hülle zu prüfen.
Ein einleuchtender, nichtsdestoweniger wichtiger Zusammenhang läßt sich für nicht-überdeckte bzw. falsch klassifizierte Beispielobjekte und die Spezialisierung von Regeln wie folgt konstatieren:
Satz 2:
Sei EX ein Beispielobjekt. Seien ferner R_a und R_b zwei Regeln desselben individuellen F-STARs mit R_b <_s R_a.
* Falls EX von R_a nicht überdeckt wird, so wird EX auch von R_b nicht überdeckt.
* Falls EX von R_b falsch klassifiziert wird, so wird EX auch von R_a falsch klassifiziert.
Leider ist es nicht möglich, eine ähnliche Eigenschaft auch für korrekt klassifizierte Beispiele anzugeben. Ein korrekt klassifiziertes Beispiel kann nämlich durch eine weniger spezielle Regel falsch oder ebenfalls korrekt klassifiziert werden; durch eine speziellere Regel kann das Beispiel korrekt klassifiziert oder nicht überdeckt werden, so daß der Spezialisierungsgraph hier nichts zu einer effizienteren Klassifizierung beitragen kann.
Dem folgenden Algorithmus zur nachträglichen Änderung individueller F-STARs liegt folgende Überlegung zugrunde: Es läßt sich festhalten, daß die Wahrscheinlichkeit für die Nicht-Überdeckung eines bestimmten Beispiels bei den weniger speziellen Regeln eines individuellen F-STARs relativ gering ist. Wird jedoch bei solchen recht generellen Regeln eine Nicht-Überdeckung gefunden, so läßt sich dadurch die ergänzende Bewertung aller spezielleren Regeln erheblich beschleunigen.
Ein analoger Zusammenhang besteht für Fehlklassifikation: Es zwar relativ unwahrscheinlich, ausgerechnet unter den sehr speziellen Regeln eine falsche Klassifikation vorzufinden. Ist dies jedoch der Fall, so läßt sich die zusätzliche Bewertung sämtlicher Regeln, die spezieller sind, mit sehr geringem Aufwand durchführen.
Die Erzeugung eines individuellen F-STARs ist also dahingehend zu erweitern, daß zu jeder erzeugten Regel R_x zusätzlich zur Bewertung auch die Indizes der Ursprungsregeln R_y und R_z (y < x, z < x) festgehalten werden, falls R_x durch Verschmelzung dieser beiden entstanden ist. Ist die Regel R_x durch einfaches Wandern auf einem Spezialisierungspfad entstanden, so muß entsprechend nur ein einziger Index gespeichert werden. Ferner sind die Spezialisierungspfade nach der Generierung ebenfalls zu speichern, da sie eventuell zu einem späteren Zeitpunkt erneut benötigt werden.
Der Algorithmus zur Modifikation bestehender individueller F-STARs auf der Grundlage eines neuen Beispiel-Datensatzes stellt sich nun wie folgt dar:
Algorithmus: Modifikation eines individuellen F-STARs
Input: F: bestehender individueller F-STAR
: neues Beispielobjekt
ML: Lerndatenbank
K: Klassenbezeichnung
Output: aktualisierter individueller F-STAR
Beschreibung:

Markiere alle Regeln aus F als "noch nicht bearbeitet";

Wiederhole, solange noch nicht-bearbeitete Regeln vorliegen:
Aktualisiere die Bewertung der noch nicht bearbeiteten Regel mit
dem kleinsten Index anhand des neuen Beispiels EX;
Markiere diese Regel als "bearbeitet";
Wurde EX von der Regel überdeckt?
Nein Ja
Erhöhe durch rekursives Traversieren aller
spezielleren Regeln deren jeweiligen #NONC-Wert
und markiere diese ebenfalls als "bearbeitet";
Liegt noch eine unbearbeitete Regel vor?
Ja Nein
Aktualisiere die Bewertung der noch nicht bearbeiteten
Regel mit dem höchsten Index anhand des neuen
Beispiels EX;
Markiere diese Regel als "bearbeitet";
Wurde EX von der Regel
falsch klassifiziert?
Ja Nein
Erhöhe durch rekursives Traversieren aller weniger
speziellen Regeln deren jeweiligen #BAD-Wert und
markiere diese ebenfalls als "bearbeitet";

Falls sich dabei der #BAD-Wert einer Regel erhöht hat, so ist mit der
Erzeugung neuer Regeln (wie früher beschrieben, unter Zuhilfenahme der
Lerndatenbank ML und der Spezialisierungspfade) fortzufahren, bis keine
neuen Regeln mehr erzeugt werden können;

Abb. 19: Modifikation eines individuellen F-STARs
Damit stehen nun alle Hilfsmittel zur Verfügung, um den Algorithmus zur stetigen Adaption eines Fuzzy-STARs an neue Beispiele zu entwickeln:
Algorithmus: Ständige Aktualisierung eines Fuzzy-STARs
Input (einmalig): K: Klassenbezeichnung
[sigma] [element] ]0, 1[: Typisierungsschranke
Input (ständig): EX: neues Beispielobjekt
Beschreibung:

FF^* <- leere Menge individueller F-STARs

ML <- leere Menge von Beispielobjekten

S^* <- leere Menge von Regeln (Fuzzy-STAR)

Wiederhole für jedes neue Beispiel EX:
Füge EX in die Lerndatenbank ML ein;
Ist die Zugehörigkeit von EX zu K größer als [sigma]?
Ja Nein
Entferne alle Regeln aus dem bisherigen Fuzzy-STAR S^*;
Wiederhole für alle individuellen F-STARs F^* aus FF^*:
Modifiziere F^* anhand von EX und ML;
Füge alle nützlichen Regeln aus F^* in den
Fuzzy-STAR S^* ein;
Bilde den individuellen F-STAR zu EX anhand von ML und
füge die daraus resultierenden nützlichen Regeln in S^* ein;
S^* stellt nun den aktualisierten Fuzzy-STAR dar;

Abb. 20: Ständige Aktualisierung eines Fuzzy-STARs
Es sei angemerkt, daß sich die Extraktion nützlicher Regeln aus individuellen F-STARs darauf beschränkt, Regeln auszuwählen, welche einen Wert von #BAD = 0 aufweisen. Diese Regeln klassifizieren kein Beispiel falsch und mindestens das Ausgangsbeispiel des individuellen F-STARs korrekt. Da nur Regeln mit #BAD > 0 für eine weitere Spezialisierung herangezogen werden, sind diese Regeln gleichzeitig maximal generalisiert in dem in Definition 31 spezifizierten Sinne, und somit insgesamt nützlich.

4.3.3 Ansätze für eine Optimierung des Verfahrens

Bei einer konkreten Implementierung dieses Algorithmus sind noch einige Optimierungs-möglichkeiten gegeben. Insbesondere wird man die doppelte Speicherung nützlicher Regeln in individuellen F-STARs und im gemeinsamen Fuzzy-STAR vermeiden. Stattdessen wird der Fuzzy-STAR aus Verweisen auf die entsprechenden Regeln bestehen; diese Verbindungen werden dann bei bei der Modifizierung und Bildung individueller F-STARs gelöscht bzw. ergänzt, anstatt den Fuzzy-STAR laufend zu löschen und neu aufzubauen.
Ferner ist zu überlegen, ob tatsächlich für jedes Beispielobjekt ein individueller F-STAR gebildet werden soll. Stattdessen könnte man sich darauf beschränken, dies zunächst nur für solche Beispiele durchzuführen, die vom aktuellen Fuzzy-STAR nicht korrekt klassifiziert werden. Dabei ergäbe sich allerdings das Problem, daß eventuell gerade diejenige Regel, welche zur korrekten Klassifikation eines neuen Datensatzes ohne eigenen individuellen F-STAR herangezogen wurde, durch spätere Beispiele falsifiziert würde. Solche Beispiele müßten daher einer besonderen Kennzeichnung unterliegen. Nach jeder Modifikation bestehender individueller F-STARs, bei der sich eine der bisherigen Regeln als falsch erweist, wäre zu überprüfen, ob die gekennzeichneten Beispiele noch korrekt klassifiziert werden; für jedes nun falsch klassifizierte bzw. nicht mehr überdeckte Beispiel wäre dann die Generierung eines eigenen individuellen F-STARs einzuleiten. Dem hierdurch erzielbaren Vorteil in Bezug auf Laufzeit und Speicherplatzbedarf des Verfahrens stünde jedoch der Nachteil gegenüber, daß nun nicht mehr so viel Regelwissen aus den Beispielen extrahiert würde.
Alternativ besteht die Möglichkeit, von Zeit zu Zeit zu überprüfen, ob im aktuellen Fuzzy-STAR relativ "alte" Regeln existieren, welche nur ein einziges Beispiel korrekt klassifizieren. Anstelle einer Beibehaltung und damit eventuell verbundenen weiteren Spezialisierung dieser Regeln sollten die zugrundeliegenden Beispiele dann als Ausnahmefälle betrachtet werden, für welche sich die Vorhaltung eigener Regeln nicht lohnt. Stattdessen sollten derartige Beispiele Eingang in eine spezielle Falldatenbank finden. Somit bestünde eine sinnvolle Trennung zwischen häufigen Fällen, welche durch Regeln abgedeckt werden, und Sonderfällen, welche sich als Beispiele in der Falldatenbank befinden. Für Regeln muß dabei weiterhin sichergestellt werden, daß es keine ihnen widersprechenden Beispiele in der Falldatenbank gibt. Wird bei einem Klassifizierungsversuch nun eine inkonsistente oder nur sehr schwache Regelaktivierung erzielt, so kann in der Falldatenbank mit Techniken des Case-Based Reasoning (CBR)[63]⁾ nach ähnlichen Beispielen gesucht werden, um aus diesen eine Klassenzugehörigkeit abzuleiten.

4.3.4 Ein Beispiel

Die Arbeitsweise des Verfahrens Incremental Fuzzy STAR soll nun anhand der bereits bekannten Beispiel-Datensätze (vgl. Abbildung 11) demonstriert werden, welche in der Reihenfolge ihrer Indizes zur Bildung eines Fuzzy-STARs für die Klasse "normal" abgearbeitet werden. Die Parameter wie Typisierungsschranke, Spannweitenmultiplikator etc. werden ebenfalls wie im vorherigen Beispiel gewählt.
Datensatz EX₁:
Die bisher leere Bewertungsmenge wird zu ML = {EX₁} ergänzt. Der Zugehörigkeitswert des Datensatzes zur relevanten Klasse übersteigt mit 0,25 die Typisierungsschranke [sigma] = 0,1. Da bisher noch keine individuellen F-STARs aufgrund anderer Beispiele existieren, kann direkt mit der Bildung des vorläufigen eigenen individuellen F-STARs F₁ fortgefahren werden. Hierzu sind zunächst wieder die Spezialisierungspfade zu den Attributen zu bilden:

Abb. 21: Spezialisierungspfade für Datensatz EX₁

Trivialerweise führt bereits R₀⁽¹⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(0)), "normal", 0,25) zu einer korrekten Klassifikation aller vorhandenen Datensätze, so daß die Bildung des individuellen F-STARs zu Beispiel 1 vorerst beendet ist. Der vorläufige Fuzzy-STAR lautet damit also S^* = {R₀⁽¹⁾}.
Datensatz EX₂:
Die Bewertungsmenge wird zu ML = {EX₁, EX₂} ergänzt. Der Zugehörigkeitswert des Datensatzes überschreitet mit 0,5 die Typisierungsschranke, so daß also nun bereits vorhandene individuelle F-STARs modifiziert werden müssen, falls die darin enthaltenen Regeln zu einer Fehlklassifikation des neuen Datensatzes führen. EX₂ wird von R₀⁽¹⁾ nicht überdeckt, so daß F⁽¹⁾ zunächst nicht erweitert wird. Daraufhin ist der eigene individuelle F-STAR F⁽²⁾ zu bilden; die zugehörigen Spezialisierungspfade wurden bereits früher präsentiert.

Regel	#GOOD	#NONC	#BAD
R₀⁽²⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(0)), "normal", 0,5)	1	0	1
R₁⁽²⁾ = ((P^Fkt(1), P^HJahr(0), P^Gewicht(0)), "normal", 0,5)	1	0	1
R₂⁽²⁾ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(0)), "normal", 0,5)	1	0	1
R₃⁽²⁾ = ((P^Fkt(1), P^HJahr(1), P^Gewicht(0)), "normal", 0,5)	1	0	1
R₄⁽²⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(1)), "normal", 0,5)	1	0	1
R₅⁽²⁾ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(1)), "normal", 0,5)	1	0	1
R₆⁽²⁾ = ((P^Fkt(1), P^HJahr(0), P^Gewicht(1)), "normal", 0,5)	1	0	1
R₇⁽²⁾ = ((P^Fkt(1), P^HJahr(1), P^Gewicht(1)), "normal", 0,5)	1	0	1
R₈⁽²⁾ = ((P^Fkt(0), P^HJahr(2), P^Gewicht(0)), "normal", 0,5)	1	1	0
R₉⁽²⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(2)), "normal", 0,5)	1	1	0

Abb. 22: Individueller F-STAR für Datensatz EX₂ (Verfahren Incremental Fuzzy-STAR)
Die Regeln R₈⁽²⁾ und R₉⁽²⁾ werden dem Fuzzy-STAR hinzugefügt, der also nun S^* = {R₀⁽¹⁾, R₈⁽²⁾, R₉⁽²⁾} lautet. Der zu F⁽²⁾ gehörige vorläufige Spezialisierungsgraph sieht wie folgt aus:

Abb. 23: Spezialisierungsgraph für den individuellen F-STAR zu Datensatz EX₂
Datensatz EX₃:
Die Bewertungsmenge wird zu ML = {EX₁, EX₂, EX₃} ergänzt. Auch dieser Datensatz überschreitet mit 0,75 die Typisierungsschranke, so daß zunächst die bereits gebildeten individuellen F-STARs F⁽¹⁾ und F⁽²⁾ betrachtet werden müssen. EX₃ wird von R₀⁽¹⁾ und R₀⁽²⁾ nicht überdeckt, womit klar ist, daß EX₃ auch von R₁⁽²⁾ bis R₉⁽²⁾ nicht überdeckt wird, und sich somit eine Erweiterung von F⁽¹⁾ und F⁽²⁾ erübrigt. Als nächstes ist der eigene individuelle F-STAR F⁽³⁾ zu bilden, wobei die zugehörigen Spezialisierungspfade ebenfalls bereits früher präsentiert wurden.

Regel	#GOOD	#NONC	#BAD
R₀⁽³⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(0)), "normal", 0,75)	1	0	2
R₁⁽³⁾ = ((P^Fkt(1), P^HJahr(0), P^Gewicht(0)), "normal", 0,75)	1	2	0
R₂⁽³⁾ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(0)), "normal", 0,75)	2	0	1
R₃⁽³⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(1)), "normal", 0,75)	2	0	1
R₄⁽³⁾ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(1)), "normal", 0,75)	2	0	1
R₅⁽³⁾ = ((P^Fkt(0), P^HJahr(2), P^Gewicht(0)), "normal", 0,75)	1	1	1
R₆⁽³⁾ = ((P^Fkt(0), P^HJahr(2), P^Gewicht(1)), "normal", 0,75)	1	1	1
R₇⁽³⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(2)), "normal", 0,75)	1	1	1
R₈⁽³⁾ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(2)), "normal", 0,75)	1	1	1
R₉⁽³⁾ = ((P^Fkt(0), P^HJahr(2), P^Gewicht(2)), "normal", 0,75)	1	1	1
R₁₀⁽³⁾ = ((P^Fkt(0), P^HJahr(3), P^Gewicht(0)), "normal", 0,75)	1	2	0
R₁₁⁽³⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(3)), "normal", 0,75)	1	2	0

Abb. 24: Individueller F-STAR für Datensatz EX₃ (Verfahren Incremental Fuzzy-STAR)
Der Fuzzy-STAR wird um die Regeln R₁⁽³⁾, R₁₀⁽³⁾ und R₁₁⁽³⁾ ergänzt und lautet nun S^* = {R₀⁽¹⁾, R₈⁽²⁾, R₉⁽²⁾, R₁⁽³⁾, R₁₀⁽³⁾, R₁₁⁽³⁾}. Der zu F⁽³⁾ gebildete Spezialisierungsgraph lautet:

Abb. 25: Spezialisierungsgraph für den individuellen F-STAR zu Datensatz EX₃
Datensatz EX₄:
Die Bewertungsmenge wird zu ML = {EX₁, EX₂, EX₃, EX₄} ergänzt. Der Datensatz überschreitet mit 0,25 die Typisierungsschranke, so daß wiederum zuerst die bereits gebildeten individuellen F-STARs F⁽¹⁾ bis F⁽³⁾ zu betrachten sind. EX₄ wird von R₀⁽¹⁾ korrekt klassifiziert, so daß erneut keine Ergänzung von F⁽¹⁾ erforderlich ist. Die Klassifizierung durch die Regeln aus F⁽²⁾ ist folgender Tabelle zu entnehmen:

Regel	Klassifizierung	Folgerung
R₀⁽²⁾	falsch
R₉⁽²⁾	nicht überdeckt
R₁⁽²⁾	nicht überdeckt	R₃⁽²⁾, R₆⁽²⁾ und R₇⁽²⁾ ebenfalls nicht überdeckt
R₈⁽²⁾	falsch	R₂⁽²⁾ ebenfalls falsch
R₄⁽²⁾	falsch
R₅⁽²⁾	falsch

Abb. 26: Klassifizierung von EX₄ durch den individuellen F-STAR F⁽²⁾
Die Spalte "Folgerung" ist dabei so zu verstehen: Aus der Tatsache, daß der Datensatz EX₄ durch die Regel R₁⁽²⁾ nicht überdeckt wird, kann anhand des bisherigen Spezialisierungs-graphen zum Datensatz EX₂ gefolgert werden, daß auch durch die spezielleren, noch nicht näher betrachteten Regeln R₃⁽²⁾, R₆⁽²⁾ und R₇⁽²⁾ keine Überdeckung erfolgt. Analog kann aus der Fehlklassifikation durch die Regel R₈⁽²⁾ geschlossen werden, daß auch die Anwendung der generelleren Regel R₂⁽²⁾ zu einer falschen Klassifikation führt. Es muß also durch diese Art der Regelorganisation in vielen Fällen kein Rückgriff auf die Regelanfrage (vgl. Definition 18) erfolgen, um herauszufinden, wie eine bestimmte Regel einen vorliegenden Datensatz klassifiziert.
Der teilweise aktualisierte individuelle F-STAR F⁽²⁾ lautet demzufolge:

Regel	#GOOD	#NONC	#BAD
R₀⁽²⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(0)), "normal", 0,5)	1	1	2
R₁⁽²⁾ = ((P^Fkt(1), P^HJahr(0), P^Gewicht(0)), "normal", 0,5)	1	2	1
R₂⁽²⁾ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(0)), "normal", 0,5)	1	1	2
R₃⁽²⁾ = ((P^Fkt(1), P^HJahr(1), P^Gewicht(0)), "normal", 0,5)	1	2	1
R₄⁽²⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(1)), "normal", 0,5)	1	1	2
R₅⁽²⁾ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(1)), "normal", 0,5)	1	1	2
R₆⁽²⁾ = ((P^Fkt(1), P^HJahr(0), P^Gewicht(1)), "normal", 0,5)	1	2	1
R₇⁽²⁾ = ((P^Fkt(1), P^HJahr(1), P^Gewicht(1)), "normal", 0,5)	1	2	1
R₈⁽²⁾ = ((P^Fkt(0), P^HJahr(2), P^Gewicht(0)), "normal", 0,5)	1	2	1
R₉⁽²⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(2)), "normal", 0,5)	1	3	0

Abb. 27: Teilweise aktualisierter individueller F-STAR zu Datensatz EX₂
Regel R₈⁽²⁾ klassifizierte vorher sämtliche Beispiele korrekt, weist jedoch jetzt einen Wert für #BAD größer als Null auf. F⁽²⁾ wird daher unter Berücksichtigung der aktuellen Bewertungsmenge ML um folgende Regeln ergänzt:

Regel	#GOOD	#NONC	#BAD
R₁₀⁽²⁾ = ((P^Fkt(0), P^HJahr(2), P^Gewicht(1)), "normal", 0,5)	1	2	1
R₁₁⁽²⁾ = ((P^Fkt(1), P^HJahr(2), P^Gewicht(0)), "normal", 0,5)	1	3	0
R₁₂⁽²⁾ = ((P^Fkt(0), P^HJahr(3), P^Gewicht(0)), "normal", 0,5)	1	3	0

Abb. 28: Ergänzung des individuellen F-STARs zu Datensatz EX₂
Als nächstes gilt es zu überprüfen, wie die Klassifizierung von EX₄ durch F⁽³⁾ erfolgt:

Regel	Klassifizierung	Folgerung
R₀⁽³⁾	falsch
R₁₁⁽³⁾	nicht überdeckt
R₁⁽³⁾	nicht überdeckt
R₁₀⁽³⁾	falsch	R₅⁽³⁾ und R₂⁽³⁾ ebenfalls falsch
R₃⁽³⁾	falsch
R₉⁽³⁾	falsch	R₄⁽³⁾, R₆⁽³⁾, R₇⁽³⁾ und R₈⁽³⁾ ebenfalls falsch

Abb. 29: Klassifizierung von EX₄ durch den individuellen F-STAR F⁽³⁾
Der teilweise aktualisierte individuelle F-STAR F⁽³⁾ lautet also:

Regel	#GOOD	#NONC	#BAD
R₀⁽³⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(0)), "normal", 0,75)	1	0	3
R₁⁽³⁾ = ((P^Fkt(1), P^HJahr(0), P^Gewicht(0)), "normal", 0,75)	1	3	0
R₂⁽³⁾ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(0)), "normal", 0,75)	2	0	2
R₃⁽³⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(1)), "normal", 0,75)	2	0	2
R₄⁽³⁾ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(1)), "normal", 0,75)	2	0	2
R₅⁽³⁾ = ((P^Fkt(0), P^HJahr(2), P^Gewicht(0)), "normal", 0,75)	1	1	2
R₆⁽³⁾ = ((P^Fkt(0), P^HJahr(2), P^Gewicht(1)), "normal", 0,75)	1	1	2
R₇⁽³⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(2)), "normal", 0,75)	1	1	2
R₈⁽³⁾ = ((P^Fkt(0), P^HJahr(1), P^Gewicht(2)), "normal", 0,75)	1	1	2
R₉⁽³⁾ = ((P^Fkt(0), P^HJahr(2), P^Gewicht(2)), "normal", 0,75)	1	1	2
R₁₀⁽³⁾ = ((P^Fkt(0), P^HJahr(3), P^Gewicht(0)), "normal", 0,75)	1	2	1
R₁₁⁽³⁾ = ((P^Fkt(0), P^HJahr(0), P^Gewicht(3)), "normal", 0,75)	1	3	0

Abb. 30: Teilweise aktualisierter individueller F-STAR zu Datensatz EX₃
Da Regel R₁₀⁽³⁾ nun ein Beispiel falsch klassifiziert, muß F⁽³⁾ erweitert werden; anschließend ist der eigene individuelle F-STAR F⁽⁴⁾ zu bilden, woraufhin aus F⁽¹⁾ bis F⁽⁴⁾ die nützlichen Regeln für den Fuzzy-STAR zu extrahieren sind, usw.
Bis hierher sind sämtliche Spezifika des Algorithmus aufgetreten. Auf eine Fortführung des Beispiels wird daher verzichtet.

4.3.5 Implementierung des Verfahrens

Im folgenden wird skizziert, wie eine Umsetzung des Verfahrens Incremental Fuzzy STAR mittels eines aktiven Datenbanksystems erfolgen kann. Dabei soll das weit verbreitete System Oracle 7 mit der Erweiterung PL/SQL zum Einsatz gelangen (vgl. Kapitel 2.4).
Zunächst wird eine Tabelle benötigt, welche die Beschreibung der bei den Beispielobjekten betrachteten Merkmale beinhaltet:
CREATE TABLE Attribute (AttrNr NUMBER(2,0),
Bezeichnung VARCHAR2(20) NOT NULL,
Typ NUMBER(1,0) NOT NULL,
Minimum NUMBER(7,2) NOT NULL,
Maximum NUMBER(7,2) NOT NULL,
CONSTRAINT pk_attribute
PRIMARY KEY(AttrNr),
CONSTRAINT ck_attr_min_max
CHECK (Minimum < Maximum));
Die Spalte "Typ" repräsentiert durch die Zahlen 0 bis 2, ob es sich um ein nominales, ordinales oder metrisch skaliertes Attribut handelt. Die Angaben "Minimum" und "Maximum" kenn-zeichnen den Wertebereich; sie werden einerseits benötigt, um konkrete Beispiele auf ihre Korrektheit hin zu überprüfen und andererseits, um bei ordinalen und metrisch skalierten Attributen die Bildung von Spezialisierungspfaden zu ermöglichen.
Außerdem sind zwei Tabellen für die Beschreibung der zu erlernenden Klassen nötig:
CREATE TABLE KlassenTypen ( KlassTypNr NUMBER(2,0),
Bezeichnung VARCHAR2(20) NOT NULL,
Minimum NUMBER(7,2) NOT NULL,
Maximum NUMBER(7,2) NOT NULL,
CONSTRAINT pk_klassentypen
PRIMARY KEY (KlassTypNr),
CONSTRAINT ck_klasstyp_min_max
CHECK (Minimum < Maximum));
CREATE TABLE Klassen ( KlassenNr NUMBER(3,0),
KlassenTyp NUMBER(2,0),
Auspraegung VARCHAR2(20) NOT NULL,
M1 NUMBER(7,2) NOT NULL,
M2 NUMBER(7,2) NOT NULL,
Alpha NUMBER(7,2) NOT NULL,
Beta NUMBER(7,2) NOT NULL,
LR NUMBER(1,0) NOT NULL,
CONSTRAINT pk_klassen
PRIMARY KEY (KlassenNr),
CONSTRAINT fk_klassen
FOREIGN KEY (KlassenTyp)
REFERENCES KlassenTypen(KlassTypNr),
CONSTRAINT ck_klass_m1_m2_alpha_beta
CHECK ((M1 <= M2) AND (Alpha >= 0) AND
(Beta >= 0)));
Durch die Einträge in diesen Tabellen wird für jeden Klassentypen ein LR-Fuzzy-Vektor mit LR-Fuzzy-Intervallen für bestimmte Ausprägungen (= Klassen) definiert. So würde etwa durch die Einträge
KlassenTypen:

KlassTypNr	Bezeichnung	Minimum	Maximum
1	"Zeitaufwand Shreddern"	0	70

Klassen:

KlassenNr	KlassenTyp	Auspraegung	M1	M2	Alpha	Beta	LR
1	1	"niedrig"	0	10	0	10	0
2	1	"normal"	20	30	10	20	0
3	1	"hoch"	50	70	20	0	0

Abb. 31: Zeitaufwandsklassen als Tabelleneinträge
der LR-Fuzzy-Vektor für die Codierung des Zeitaufwands an der Shreddermaschine (vgl. Abbildung 12) beschrieben. Die Spalte "LR" kennzeichnet dabei die zu verwendenden Referenzfunktionen, also z.B. 0 für L(u) = R(u) = Max(0, 1-u), 1 für L(u) = R(u) = e^-u etc. Denkbar wäre selbstverständlich auch die Trennung in zwei Spalten "L" und "R", um die Möglichkeit unterschiedlicher Referenzfunktionen für den linken bzw. rechten Randbereich zu bieten.
Die drei bisher beschriebenen Tabellen werden in der Regel nur eine sehr beschränkte Anzahl von Datensätzen aufnehmen, welche jedoch zur Abarbeitung der Algorithmen recht häufig benötigt werden. Es bietet sich daher an, ein Package [64]⁾ zu implementieren, welches bei der erstmaligen Benutzung automatisch die Datensätze dieser Tabellen einliest, und sie anschließend im Hauptspeicher hält, um auf Anfrage den lesenden Zugriff sehr schnell zu ermöglichen.
Die Beispielobjekte sind in einer Tabelle abzulegen, welche anwendungsspezifisch ist und für die bisher dargestellten Beispiele z.B. den folgenden Aufbau besitzt:
CREATE TABLE Beispiele( BspNr NUMBER(4,0),
Funktion NUMBER(1,0),
HerstJahr NUMBER(4,0),
Gewicht NUMBER(7,2),
ShreddZeit NUMBER(7,2) NOT NULL,
CONSTRAINT pk_beispiele
PRIMARY KEY (BspNr));
Für diese Tabelle sind zwei Trigger [65]⁾ zu implementieren: Zunächst ein BEFORE-Trigger, dessen Aufgabe es ist, vor der Neuanlage eines Beispieldatensatzes anhand der Tabellen "Attribute" bzw. "KlassenTypen" zu überprüfen, ob die einzutragenden Werte mit den Beschreibungen der Attribute bzw. Klassenarten verträglich sind, und gegebenenfalls die Speicherung inkonsistenter Datensätze zurückzuweisen. Alternativ ist es auch möglich, einen solchen Trigger dazu zu verwenden, die Beschreibung der Merkmale entsprechend zu erweitern. Dabei ist jedoch zu beachten, inwiefern diese Merkmalsbeschreibungen bei der Bildung der Spazialisierungspfade verwendet wurden. Falls z.B. für die allgemeine Expansion eine Schrittweite in Abhängigkeit der Breite des Wertebereichs gewählt wurde, können hier im nachhinein Änderungen erforderlich werden. Zweitens wird ein AFTER-Trigger benötigt, welcher jeden Datensatz in ein internes Format umwandelt, welches in folgenden Tabellen abgelegt wird:
CREATE TABLE BspAttr ( BspNr NUMBER(4,0),
Attribut NUMBER(2,0),
Wert NUMBER(7,2) NOT NULL,
CONSTRAINT pk_bspattr
PRIMARY KEY (BspNr, Attribut),
CONSTRAINT fk_bspattr_1
FOREIGN KEY (BspNr)
REFERENCES Beispiele(BspNr)
ON DELETE CASCADE,
CONSTRAINT fk_bspattr_2
FOREIGN KEY (Attribut)
REFERENCES Attribute(AttrNr));
CREATE TABLE BspKls ( BspNr NUMBER(4,0),
Klasse NUMBER(3,0),
Zugehoerig NUMBER(3,2) NOT NULL,
CONSTRAINT pk_bspkls
PRIMARY KEY (BspNr, Klasse),
CONSTRAINT fk_bspkls_1
FOREIGN KEY (BspNr)
REFERENCES Beispiele(BspNr)
ON DELETE CASCADE,
CONSTRAINT fk_bspkls_2
FOREIGN KEY (Klasse)
REFERENCES Klassen(KlassenNr),
CONSTRAINT ck_bspkls_zugehoerig
CHECK (Zugehoerig BETWEEN 0 AND 1));
"BspAttr" enthält sämtliche Attributwerte der Beispiele, während in "BspKls" die Zugehörigkeiten zu den betrachteten Klassen gespeichert werden. Durch diese Form der Speicherung wird erreicht, daß von diesem Zeitpunkt an Anwendungsunabhängigkeit besteht: Die eigentlichen Prozeduren zur Umsetzung von Incremental Fuzzy-STAR müssen nicht mehr anwendungsindividuell angepaßt werden; stattdessen besteht eine exakt definierte Schnittstelle zu den zugrundeliegenden Daten.
Zu jedem Datensatz der Tabelle "BspAttr" ist ein Spezialisierungspfad zu bilden. Es bietet sich daher an, diesen durch einen entsprechenden AFTER-Trigger generieren zu lassen und in folgender Tabelle zu speichern:
CREATE TABLE SpezPfade( BedNr NUMBER(5,0),
Beispiel NUMBER(4,0),
Attribut NUMBER(2,0),
SpezGrad NUMBER(1,0),
M1 NUMBER(7,2),
M2 NUMBER(7,2),
Alpha NUMBER(7,2),
Beta NUMBER(7,2),
CONSTRAINT pk_spezpfade
PRIMARY KEY (BedNr),
CONSTRAINT unique_spezpfade
UNIQUE INDEX (Beispiel, Attribut,
SpezGrad),
CONSTRAINT fk_spezpfade
FOREIGN KEY (Beispiel, Attribut)
REFERENCES BspAttr(BspNr, Attribut)
ON DELETE CASCADE);
Für nominale Attribute wird die (scharfe, ganzzahlige) Merkmalsausprägung in der Spalte "M1" abgelegt. Für ordinale und metrisch skalierte Attribute repräsentiert jeder Datensatz ein LR-Fuzzy-Intervall. Um weiteren Tabellen eine möglichst einfache Referenzierung der durch "SpezPfade" repräsentierten Bedingungen zu ermöglichen, wird jeder Spezialierung zusätzlich noch eine eindeutige Bedingungsnummer zugeordnet.
Jedem Datensatz der Tabelle "BspKls" ist ein individueller F-STAR zuzuordnen. Auch hier ist es daher von Vorteil, diesen Vorgang von einem AFTER-Trigger anstoßen zu lassen. Da für die Generierung bzw. Modifikation individueller F-STARs die Spezialisierungspfade benötigt werden, muß sichergestellt werden, daß zu jedem Datensatz der Tabelle "Beispiele" zunächst die entsprechenden Einträge in "BspAttr", und erst anschließend diejenigen in "BspKls" gespeichert werden. Die individuellen F-STARs werden durch die folgenden beiden Tabellen repräsentiert:
CREATE TABLE Regeln ( RegelNr NUMBER(5,0),
Beispiel NUMBER(4,0),
Klasse NUMBER(3,0),
MaxAktiv NUMBER(3,2) NOT NULL,
Good NUMBER(4,0) NOT NULL,
NonC NUMBER(4,0) NOT NULL,
Bad NUMBER(4,0) NOT NULL,
Vater1 NUMBER(5,0),
Vater2 NUMBER(5,0),
CONSTRAINT pk_regeln
PRIMARY KEY (RegelNr),
CONSTRAINT fk_regeln_1
FOREIGN KEY (Beispiel, Klasse)
REFERENCES BspKls(BspNr, Klasse)
ON DELETE CASCADE,
CONSTRAINT fk_regeln_2
FOREIGN KEY (Vater1)
REFERENCES Regeln(RegelNr),
CONSTRAINT fk_regeln_3
FOREIGN KEY (Vater2)
REFERENCES Regeln(RegelNr));
CREATE TABLE Bedingungen ( Regel NUMBER(5,0),
Bedingung NUMBER(5,0),
CONSTRAINT pk_bedingungen
PRIMARY KEY (Regel, Bedingung),
CONSTRAINT fk_bedingungen_1
FOREIGN KEY (Regel)
REFERENCES Regeln(RegelNr)
ON DELETE CASCADE,
CONSTRAINT fk_bedingungen_2
FOREIGN KEY (Bedingung)
REFERENCES SpezPfade(BedNr)
ON DELETE CASCADE);
Die Tabelle "Regeln" enthält also nicht nur die Klasse, auf welche sich eine bestimmte Regel bezieht, sondern außerdem die Nummer des Beispiels, auf dessen Grundlage sie erzeugt wurde. Somit ist es durch eine einfache Abfrage der Form
SELECT ...
FROM Regeln
WHERE (Beispiel = ...) AND (Klasse = ...);
möglich, den individuellen F-STAR zu einem bestimmten Beispielobjekt und einer bestimmten Klasse zu erhalten. Die Felder "Good", "Nonc" und "Bad" enthalten die aktuelle Bewertung der Regel. Die Spalten "Vater1" bzw. "Vater2" enthalten gegebenenfalls die Nummern derjenigen Regeln, aus denen die betrachtete Regel durch Spezialisierung entstanden ist. Da Fremdschlüsselwerte nicht den Wert NULL annehmen dürfen, ist bei dieser Konstruktion die Anlage einer Dummy-Regel (z.B. unter Angabe der Zahl -1 sowohl für die eigene Nummer, als auch für die der Väter) erforderlich, auf die verwiesen wird, wenn die Regel nicht aus der Verschmelzung zweier anderer Regeln entstanden ist bzw. sogar die Wurzel in einem Spezialisierungsgraphen darstellt. Falls das verwendete Datenbanksystem keine rekursive referenzielle Integrität [66]⁾, also die Einrichtung von Fremdschlüssel-Constraints, welche sich auf den Primärschlüssel derselben Tabelle beziehen, unterstützt, müssen die Informationen für den Spezialisierungsgraphen in einer separaten Tabelle gespeichert werden.
Die Tabelle "Bedingungen" schließlich gibt Aufschluß darüber, aus welchen Bedingungen der zuvor gebildeten Spezialisierungspfade eine bestimmte Regel zusammensetzt ist.
Der aktuelle Fuzzy-STAR zu einer bestimmten Klasse läßt sich nun auf einfache Weise durch eine Abfrage der Form
SELECT ...
FROM Regeln
WHERE (Klasse = ...) AND (BAD = 0);
ermitteln.

4.3.6 Bewertung des Verfahrens

Nachfolgend soll das Verfahren Incremental Fuzzy-STAR kurz anhand seiner Vor- und Nachteile bewertet werden.
Positiv anzumerken ist zunächst, daß das Verfahren eine echte Inkrementalisierung (vgl. Definition 1) der STAR-Methode darstellt. Bereits präsentierte Beispiele werden nur für die erneute Bewertung von Regeln herangezogen, wenn bereits erzeugte Regeln durch neue Beispielobjekte falsifiziert werden, bzw. auf der Grundlage eines neuen Beispiels gänzlich neue Regeln zu generieren sind. Jedes dem Verfahren dargebotene Beispiel wird zukünftig im Rahmen der für den Lernvorgang verwendeten Toleranzschwelle korrekt klassifiziert - eine wichtige Eigenschaft, denn ein Verfahren, welches bekannte Beispiele nur ungenau oder sogar falsch klassifiziert, dürfte auf erhebliche Akzeptanzprobleme stoßen.
Die Methode läßt sich in außerordentlich einfacher Weise dahingehend erweitern, daß auch aus Beispielen mit ungefähren oder sogar teilweise fehlenden Angaben gelernt werden kann: Es ist lediglich die Bildung von Spezialisierungspfaden leicht zu modifizieren.
Ferner wird aus den bekannten Beispielen ein hohes Maß an Regelwissen extrahiert, wodurch die Wahrscheinlichkeit für eine korrekte Klassifikation zukünftiger Beispiele steigt.
Schließlich ist hervorzuheben, daß die für eine Klassifikation verwendeten Regeln sich dem Benutzer auf Wunsch in einer vertrauten Form präsentieren lassen, wie z.B. "Wenn die Funktion ´Bildschirm´ ist und das Gewicht etwa 10 bis 15 kg beträgt, so liegt vermutlich eine hohe Zugehörigkeit zur Klasse ´hoher Materialverbrauch´ vor". Die aus den Regeln resultierenden Prognosen lassen sich somit leicht um eine Erklärungskomponente ergänzen, was ebenfalls im Hinblick auf die Praxisakzeptanz als sehr wichtig einzustufen ist [67]⁾.
Nichtsdestotrotz sind auch negative Aspekte des Verfahrens nicht zu übersehen. Hier ist in erster Linie die Vielzahl der Parameter zu nennen, welche den Lernerfolg wesentlich beeinflussen können. Es dürfte nicht gerade leicht fallen, intuitiv zu guten Werten für initiale Spannweiten, Länge der Spezialisierungspfade, Spannweitenmultiplikator, Typisierungs-schranke usw. zu kommen. Ferner ist nicht klar, welche Referenzfunktionen und welche Aggregations- oder Inferenzoperatoren für eine optimale Arbeitsweise zu verwenden sind; es ist allerding einzuräumen, daß es sich bei den letztgenannten um typische Probleme unscharfer Verfahren handelt.
Abschließend muß erwähnt werden, daß das Verfahren einen recht hohen Speicherbedarf besitzt, da neben den bereits bekannten Beispielen deren Spezialisierungspfade, individuelle F-STARs und Spezialisierungsgraphen zu speichern sind. Dem ist allerdings entgegenzuhalten, daß die Kosten für Sekundärspeicher nach wie vor stark rückläufig sind Beleg?, so daß diesem Aspekt eine eher untergeordnete Bedeutung beizumessen ist.

5 MUSP

Es wird nun ein gänzlich neues Verfahren entworfen, welches einerseits ebenfalls auf der allmählichen Spezialisierung recht allgemeiner Regeln beruht, andererseits jedoch einfacher ist und dennoch deutlich mehr an vorhandenen Informationen sinnvoll nutzt.

5.1 Vorüberlegungen

Neben den bereits diskutierten Nachteilen des Verfahrens Incremental Fuzzy-STAR fällt ins Auge, daß die Methode einen recht statischen Charakter aufweist in dem Sinne, daß einmal gebildete Bedingungen später keine Veränderung mehr erfahren. Die Bildung eines Spezialierungspfades, anhand dessen Bedingungen ausgetauscht bzw. durch die Ver-schmelzung von Regeln neu kombiniert werden, geschieht unabhängig von bereits bekannten anderen Beispielen und wird im weiteren Verlauf nicht mehr revidiert. Es wird deshalb nun ein neues Verfahren entwickelt, welches nicht nur einfacher ist, sondern zudem bei der Spezialisierung bisheriger Regeln wesentlich mehr an vorhandenen Informationen ausnutzt. Grundidee auch dieses Verfahrens ist es, anfänglich maximal-generalisierte Regeln zu bilden, welche dann im weiteren Verlauf solange spezialisiert werden, bis keine Fehlklassifikationen mehr auftreten. Es gehört also ebenfalls in die Kategorie "Lernen durch Spezialisierung". Aufgrund der verwendeten Strategie der Vervielfachung und anschließenden Spezialisierung von Regeln soll das Verfahren den Namen "MUSP" (für Multiply & Specialize) erhalten.

5.2 Das Verfahren

Das Verfahren MUSP wird derart konstruiert, daß es wesentlich auf einer durch Widersprüche gesteuerten Spezialisierung unscharfer Bedingungen beruht. Es wird dazu für jedes Beispiel zunächst eine maximal-generalisierte Regel gebildet, deren unscharfe Bedingungen dann im weiteren Verlauf unter Umständen in mehreren parallelen Zweigen soweit wie nötig auf die Ausprägungen ihres Ursprungsbeispiels hin spezialisiert werden. Zu jeder vorhandenen Bedingung gibt es also ein Urprungsbeispiel, dessen jeweilige Ausprägung zu dem in der Bedingung betrachteten Merkmal die Grenze für mögliche Spezialisierungen bildet. Diese Ausprägung heißt Zentralwert. Dabei wird im folgenden davon ausgegangen, daß Bedingungen für nominale Attribute auf "normalen" Fuzzy-Mengen beruhen. Eine Spezialisierung solcher Bedingungen läßt sich wie folgt formalisieren:

Algorithmus: widerspruchsgesteuerte Spezialisierung einer auf ein nominales Attribut bezogenen unscharfen Bedingung

Input: : unscharfe Bedingung

x Î X: Widerspruchsausprägung

: Zielzugehörigkeit der Widerspruchsausprägung

Output: C´: spezialisierte unscharfe Bedingung

Beschreibung:

Abb. 32: Widerspruchsgesteuerte Spezialisierung einer nominalen unscharfen Bedingung

Bedingungen für ordinale und für metrisch skalierte Merkmale sollen weiterhin auf den bereits eingeführten LR-Fuzzy-Intervallen basieren. Ihre widerspruchsgesteuerte Spezialisierung besteht in einer Kontraktion des LR-Fuzzy-Intervalls, so daß die Zugehörigkeit des Widerspruchswerts zum LR-Fuzzy-Intervall nicht mehr zu hoch ist. Dabei ist jedoch zu gewährleisten, daß der Zentralwert der unscharfen Bedingung auch nach der Spezialisierung noch volle Zugehörigkeit besitzt. Eine solche Spezialisierung läßt sich folgendermaßen durchführen:

Algorithmus: widerspruchsgesteuerte Spezialisierung einer auf ein metrisch skaliertes

Attribut bezogenen unscharfen Bedingung

Input: : unscharfe Bedingung mit

z Î [m₁, m₂]: Zentralausprägung der unscharfen Bedingung

x ¹ z: Widerspruchsausprägung

: Zielzugehörigkeit der Widerspruchsausprägung

f Î [0, 1[: Spezialisierungsintensität

g > 0: Spannweitengranularität

Output: C´: spezialisierte unscharfe Bedingung

Beschreibung:

x > z ?

Ja Nein

m₂´ ¬ z + f(x - z) m₁´ ¬ z - f(z - x)

b´ ¬ 0 a´ ¬ 0

Wiederhole, solange : Wiederhole, solange :

b´ ¬ b´ + g a´ ¬ a´ + g

b´ ¬ b´ - g a´ := a´ - g

Abb. 33: Widerspruchsgesteuerte Spezialisierung einer metrischen unscharfen Bedingung

Für den ordinalen Falle ist im obigen Struktogramm die Zuweisung m₂´ ¬ z + f(x - z) durch m₂´ ¬ ë z + f(x - z)û und m₁´ ¬ z - f(z - x) durch m₁´ ¬ é z - f(z - x)ù zu ersetzen.

Das Verfahren MUSP läuft nun wie folgt ab: Für jedes Beispiel einer bestimmten Klasse wird eine maximal-generalisierte Regel gebildet, deren unscharfe Bedingungen zunächst den gesamten Wertebereich der betrachteten Attribute mit vollem Zugehörigkeitsgrad beinhalten. Die maximal mögliche Aktivierung der Regel wird auf den Zugehörigkeitsgrad des Beispiels zur betrachteten Klasse gesetzt. Somit wird das Beispiel von der Regel korrekt klassifiziert. Daraufhin wird überprüft ob Beispiele existieren, die von der Regel falsch klassifiziert werden. Ist dies der Fall, so wird für das erste jener Beispiele festgestellt, welche der Bedingungen der Regelprämisse in Bezug auf die konkrete Ausprägung beim Widerspruchsbeispiel eine zu hohe Teilaktivierung liefern. Für jede solche noch zu generelle Bedingung wird eine neue Regel erzeugt, in welcher diese Bedingung widerpruchsgesteuert spezialisiert und alle anderen Bedingungen übernommen wurden. Anschließend wird die Ausgangsregel entfernt, um die neuen Regeln anhand des nächsten Widerspruchsbeispiels weiter zu spezialisieren, usw. Grundlegender Mechanismus des Verfahrens ist also die wie folgt zu formalisierende Korrektur einer Regel anhand eines Widerspruchsbeispiels, wobei vorausgesetzt wird, daß für jede Regel deren Ursprungsbeispiel bekannt ist, so daß mithin die für die Spezialisierungen erforderlichen Zentralwerte vorliegen:

Algorithmus: Korrektur einer Regel anhand eines Widerspruchsbeispiels

Input: R = (P, K, m): zu korrigierende Regel (mit P = (C₁, ..., C_n))

: Widerspruchsbeispiel, welches von R falsch klassifiziert wird

(mit )

Output: MR: Menge von Regeln, welche EX nicht falsch klassifizieren

Beschreibung:

MR ¬ leere Menge von Regeln

(die Zugehörigkeit von EX zur betrachteten Klasse)

n ¬ Anzahl der Merkmale

DO i = 1 (+1) n

MC(C_i, x_i) > m_EX Ù x_i ¹ Zentralwert für C_i?

Ja Nein

Erzeuge eine neue Regel R_i, indem die Bedingung C_i

anhand von x_i und m_EX widerspruchsgesteuert spezialisiert

wird und alle übrigen Bedingungen sowie die maximale

Aktivierung von R unverändert übernommen werden;

Füge R_i in MR ein;

Abb. 34: Korrektur einer Regel anhand eines Widerspruchsbeispiels

Man beachte, daß das Vorliegen einer leeren Menge MR nach Abarbeitung dieses Algorithmus eine Fehlersituation anzeigt: Entweder wurde versucht, eine Regel anhand eines Beispiels widerspruchsgesteuert zu korrigieren, obwohl diese Regel das Beispiel nicht falsch klassifiziert, oder die Zentralwerte der Regel stimmen für alle Bedingungen mit der jeweiligen Ausprägung des Widerspruchsbeispiels überein. Letzterer Fall bedeutet das Vorhandensein von Beispielen mit identischen Merkmalsausprägungen, jedoch unterschiedlichen Klassenzugehörigkeiten - die Lerndatenbank wäre somit inkonsistent.

Damit ist es ein nun leichtes, den Algorithmus für die Korrektur einer Menge von Regeln aufgrund eines Beispiels zu formulieren:

Algorithmus: Korrektur einer Menge von Regeln anhand eines Beispiels

Input: MR = {R₁, ..., R_m}: zu korrigierende Regelmenge

: Beispielobjekt

Output: MR: korrigierte Regelmenge

Beschreibung:

DO i = 1 (+1) m

Markiere die Regel R_i als "noch nicht bearbeitet";

Wiederhole, solange MR noch unbearbeitete Regeln enthält:

Wähle eine beliebige unbearbeitete Regel R aus MR;

Wird EX von R falsch klassifiziert?

Ja Nein

Erzeuge durch widerspruchsge- Markiere R als "bereits bearbeitet";

steuerte Korrektur von R anhand

EX eine neue Regelmenge MRC;

Markiere die Regeln in MRC als

"bereits bearbeitet";

Ersetze die Regel R in MR durch

die Regeln aus MRC;

Abb. 35: Korrektur einer Menge von Regeln anhand eines Beispiels
Der MUSP-Algorithmus zur inkrementellen Bildung einer Regelmenge anhand fortlaufend eintreffender Beispielobjekte lautet also insgesamt:
Algorithmus: MUSP
Input: MR = {R₁, ..., R_m}: Menge bisher vorhandener Regeln
ML = {EX₁, ..., EX_n}: Menge bisher vorhandener Beispiele
EX: neues Beispiel
Output: MR´: korrigierte und erweiterte aktuelle Regelmenge
Beschreibung:

Korrigiere die bisherige Regelmenge MR anhand des neuen Beispiels EX;

Erzeuge eine neue maximal-generalisierte Regel R und versieh jede ihrer
Bedingungen zusätzlich mit der jeweiligen Merkmalsausprägung von EX
(dem "Zentralwert");

MRN <- {R}

DO i = 1 (+1) n
Korrigiere MRN anhand von EX_i;

Füge EX in ML ein;

MR´ <- MR [union] MRN

Abb. 36: MUSP-Hauptalgorithmus

5.3 Ansätze für eine Optimierung des Verfahrens

Das Verfahren MUSP geht, ähnlich wie die vorgestellten STAR-Varianten, von sehr allgemeinen Regeln aus, welche nach und nach weiter spezialisiert werden. Unter Berücksichtigung von Satz 2 liegt es daher auch hier nahe, die Informationen des Spezialisierungsprozesses in Form von Spezialisierungsgraphen zu speichern, um sie anschließend für das schnellere Auffinden weiterer zu spezialisierender Regeln zu verwenden. Dazu dürfen falsifizierte Regeln nicht völlig entfernt, sondern lediglich als ungültig gekennzeichnet werden. Zusätzlich müssen Regeln, die als Spezialisierung anderer Regeln entstehen, einen Verweis auf eben diese erhalten. Durch die Verwendung der auf diese Weise entstehenden Spezialisierungsinformationen ist es dann wieder möglich, auf der Suche nach Regeln, die ein vorliegendes Beispiel falsch klassifizieren, ganze Äste des Spezialisierungs-graphen abzuschneiden.
Falls ein Beispiel durch viele oder sogar alle unscharfen Bedingungen in einer Regelprämisse falsch klassifiziert wird, kommt es bei der bisherigen Variante des Verfahrens zur Bildung vieler neuer Regeln; dieser Prozeß kann sich in ungünstigen Konstellationen so fortsetzen, daß es zu einer "kombinatorischen Explosion" der Anzahl vorhandener Regeln kommt. Dem kann entgegengewirkt werden, indem eine Schranke eingeführt wird, welche die Anzahl der jeweils neu zu erzeugenden Regeln nach oben hin begrenzt. Das Verfahren funktioniert selbst dann noch, wenn für diese Schranke 1 gewählt wird; es wird dann allerdings nur relativ wenig an Regelwissen aus den Beispielen generiert. Für die Auswahl der zu spezialisierenden Bedingungen sind im Falle des Vorhandenseins einer solchen Schranke verschiedene Strategien denkbar; beispielsweise könnten diejenigen Bedingungen gewählt werden, bei denen bereits eine relativ geringfügige Spezialisierung das gewünschte Resultat bildet. Dabei entsteht allerdings die Problematik, daß ein Maß für die Intensität von Spezialisierungen eingeführt werden muß, um diese vergleichbar zu machen, welches auch für Bedingungen auf verschiedenen Attributen Sinn ergibt. Hierzu könnte man ein auf Fuzzy-Mengen mit metrisch skalierten Stützmengen erweitertes Unschärfemaß verwenden [68]⁾.
Bisher wird für jedes Beispiel mindestens eine Regel gebildet, welche normalerweise innerhalb kürzester Zeit zu mehreren Regeln korrigiert wird. Um einer immer größer werdenden Anzahl von Regeln entgegenzuwirken, sollte daher bei Vorliegen einer bestimmten Menge von Regeln dazu übergegangen werden, vor der Bildung einer neuen Wurzelregel für ein neues Beispiel zu überprüfen, ob dieses bereits von den vorhandenen Regeln korrekt klassifiziert wird. Ist dies der Fall, so kann vorerst auf die Bildung einer neuen Ursprungsregel verzichtet werden. Es muß allerdings auch hier wieder beachtet werden, daß eventuell im späteren Verlauf gerade diejenige Regel falsifiziert wird, welche zu einer korrekten Klassifikation des Beispiels geführt hat. Solche auf Anhieb korrekt klassifizierten Beispiele sollten daher gesondert markiert werden, um bei Falsifizierung einer bestehenden Regel anschließend zu überprüfen, ob nicht doch noch die Generierung neuer Ursprungsregeln für einige dieser Beispiele erforderlich wird.
Die durch die Anwendung des Verfahrens möglicherweise entstehende Redundanz innerhalb der Menge aktueller Regeln wird bewußt in Kauf genommen - Regeln, welche dieselben Beispiele korrekt klassifizieren und somit als redundant angesehen werden müssen, können eventuell im nächsten Schritt so spezialisiert werden, daß sie zu einer korrekten Klassifizierung disjunkter Beispielmengen führen. Nichtsdestotrotz erscheint es sinnvoll, Regeln anhand eines Gütekriteriums zu bewerten und entsprechend sortiert zu speichern [69]⁾. Ein solches Gütekriterium könnte beispielsweise durch folgende lexikographische Ordnung definiert werden:
1. Kriterium: maximal mögliche Regelaktivierung
2. Kriterium: Anzahl der bisher durch die Regel korrekt klassifizierten Beispiele
3. Kriterium: Positionierung der Regel im Spezialierungsgraph
Dabei ist das erstgenannte Kriterium zwingend, um bei der nun möglichen schnelleren Klassifizierung neuer Beispiele zu gewährleisten, daß keine Regel übergangen wird, welche eventuell zu einer höheren Aktivierung geführt hätte. Weitere Kriterien könnten unter Berück-sichtigung des Konsistenz- bzw. Vollständigkeitsgrades (vgl. Definitionen 22 und 23) definiert werden.
Die Sortierung der Regeln läßt sich zusätzlich vortrefflich ausnutzen, um nur solche Regeln im schnellen, jedoch relativ begrenzten Hauptspeicher zu halten, welche mit hoher Wahr-scheinlichkeit für die Klassifikation zukünftiger Beispiele Anwendung finden werden. Hingegen können "weniger nützliche" Regeln im langsamen, jedoch in wesentlich größerem Umfang zur Verfügung stehenden Sekundärspeicher abgelegt werden. Durch die Wahl einer Schranke für die Anzahl der im Hauptspeicher maximal zu haltenden Regeln wird die Menge der aktuellen Regeln also in eine Vordergrund- und eine Hintergrund-Regelmenge aufgeteilt [70]⁾. Je größer die Schranke gewählt wird, desto höher ist die Wahrscheinlichkeit einer schnellen Klassifikation, jedoch unter Inkaufnahme eines entsprechend erhöhten Hauptspeicherbedarfs.
Eine weitere Möglichkeit zur Optimierung besteht in der turnusmäßigen Beseitigung von Regeln, welche spezieller sind als andere Regeln bzw. eine exakte Übereinstimmung der Bedingungen mit ihnen aufweisen, jedoch vom demselben Ursprungsbeispiel stammen. Wie man sich leicht klarmacht, können derartige Regeln von MUSP generiert werden (siehe nachfolgendes Beispiel); sie sind jedoch überflüssig und können daher entfernt werden - eine Variante des Problems der "Überspezialisierung bei Spezialisierung als Suchstrategie"[71]⁾.

5.4 Ein Beispiel

Die Arbeitsweise des MUSP-Verfahrens wird nun ebenfalls anhand eines Beispiels verdeutlicht, wobei von den soeben erläuterten Optimierungsmethoden kein Gebrauch gemacht wird. Es werden wieder die bereits bekannten Datensätze herangezogen, um Regeln für die Klasse "normaler Zeitaufwand für Shreddern" zu erzeugen. Die verwendeten Parameter lauten wie folgt:
Spezialisierungsintensität: [phi] = 0,8
Spannweitengranularität: [gamma] = 1,0 (für Bedingungen zu ordinalen Attributen)
[gamma] = 0,5 (für Bedingungen zu metrischen Attributen)
Referenzfunktionen: L(u) = R(u) = Max(0, 1-u)
Toleranzschwelle: [epsilon] = 0,0
Beginnend mit Datensatz EX₁ wird zunächst eine maximal-generalisierte Regel wie folgt gebildet:
R₁₀ = (((Funktion, [emptyset]), (Herst.-Jahr, [emptyset]), (Gewicht, [emptyset])), "normal", 0,25)
Da noch keine anderen Datensätze existieren, anhand derer diese Regel spezialisiert werden könnte, kann sofort mit Datensatz EX₂ fortgefahren werden. Dieser wird von R₁₀ nicht überdeckt, so daß diese Regel zunächst unverändert bleibt. Nun wird auch für EX₂ eine zunächst noch maximal-generalisierte Regel gebildet:
R₂₀ = (((Funktion, [emptyset]), (Herst.-Jahr, [emptyset]), (Gewicht, [emptyset])), "normal", 0,5)
Da der Datensatz EX₁ von R₂₁ gegen [epsilon] falsch klassifiziert wird (vgl. Definition 20), muß R₂₀ anhand von EX₁ widerspruchsgesteuert spezialisiert werden. Da der Zentralwert von R₂₀ für das Merkmal "Funktion" mit der Ausprägung desselben Merkmals bei EX₁ übereinstimmt, kann dieses Attribut nicht für eine Spezialisierung herangezogen werden. Das Attribut "Herstellungsjahr" mit der Ausprägung "1960" führt zu einem Zugehörigkeitsgrad von 1,0 zur entsprechenden Bedingung von R₂₁. Das Attribut "Gewicht" mit der Ausprägung "30" führt ebenfalls zu einer Zugehörigkeit von 1,0 zur entsprechenden Bedingung von R₂₀. Wünschenswert wäre in beiden Fällen die Zielzugehörigkeit von maximal 0,25. Es werden daher zwei widerspruchsgesteuerte Spezialisierungen anhand von EX₁ durchgeführt, welche zu einer Ersetzung der Regel R₂₀ durch die folgenden beiden Regeln führen:

R₂₁ = (( (Funktion, [emptyset]),
(Herst.-Jahr, (1964; 1995; 5; 0)_LR),
(Gewicht, [emptyset])), "normal", 0,5)

R₂₂ = (( (Funktion, [emptyset]),
(Herst.-Jahr, [emptyset]),
(Gewicht, (0; 27; 0; 4)_LR)), "normal", 0,5)

Abb. 37: Spezialisierung der Regel R₂₀ (MUSP)
Das Beispiel EX₁ wird nun von R₂₁ nicht überdeckt und von R₂₂ korrekt klassifiziert.
Auch der nun zu bearbeitende Datensatz EX₃ wird noch von keiner der bestehenden Regeln überdeckt, so daß diese erneut keine Änderung erfahren. Wieder wird zunächst eine maximal-generalisierte Regel gebildet:
R₃₀ = (((Funktion, [emptyset]), (Herst.-Jahr, [emptyset]), (Gewicht, [emptyset])), "normal", 0,75)
Da EX₁ von dieser Regel falsch klassifiziert wird, keiner der Zentralwerte der Regel-bedingungen mit der Ausprägung von EX₁ übereinstimmt, und der Zugehörigkeitsgrad jeder Ausprägung von EX₁ zur entsprechenden Bedingung mit 1,0 die wünschenswerte Zielzugehörigkeit von 0,25 überschreitet, werden drei widerspruchsgesteuerte Spezialisierungen durchgeführt. Diese führen zunächst zu einer Ersetzung von R₃₀ durch die Regeln R₃₁ bis R₃₃:

R₃₁ = (( (Funktion, { ("Bildschirm", 0,25), ("Drucker", 1,0),
("Tastatur", 1,0), ("Zentraleinheit", 1,0)}),
(Herst.-Jahr, [emptyset]),
(Gewicht, [emptyset])), "normal", 0,75)

R₃₂ = (( (Funktion, [emptyset]),
(Herst.-Jahr, (1965; 1995; 6; 0)_LR),
(Gewicht, [emptyset])), "normal", 0,75)

R₃₃ = (( (Funktion, [emptyset]),
(Herst.-Jahr, [emptyset]),
(Gewicht, (0; 25,2; 0; 6)_LR)), "normal", 0,75)

Abb. 38: Spezialisierung der Regel R₃₀ (MUSP)
In Regel R₃₁ findet sich also jetzt erstmalig eine nicht-leere Bedingung, welche nicht auf einem LR-Fuzzy-Intervall, sondern auf einer "gewöhnlichen" Fuzzy-Menge mit diskreter Grund-menge für ein nominales Merkmal beruht.
Die neu entstandenen Regeln R₃₁ bis R₃₃ müssen nun noch an das Beispiel EX₂ angepaßt werden. Dieses wird von R₃₁ nicht überdeckt, jedoch von R₃₂ und R₃₃ falsch klassifiziert. Es werden daher wieder die notwendigen widerspruchsgesteuerten Spezialisierungen durchgeführt. R₃₂ wird ersetzt durch:

R₃₂₁ = (( (Funktion, { ("Bildschirm", 0,5), ("Drucker", 1,0),
("Tastatur", 1,0), ("Zentraleinheit", 1,0)}),
(Herst.-Jahr, (1965; 1995; 6; 0)_LR),
(Gewicht, [emptyset])), "normal", 0,75)

R₃₂₂ = (( (Funktion, [emptyset]),
(Herst.-Jahr, (1981; 1995; 2; 0)_LR),
(Gewicht, [emptyset])), "normal", 0,75)

R₃₂₃ = (( (Funktion, [emptyset]),
(Herst.-Jahr, (1965; 1995; 6; 0)_LR),
(Gewicht, (0; 13,2; 0; 3,5)_LR)), "normal", 0,75)

Abb. 39: Spezialisierung der Regel R₃₂ (MUSP)
Die Regel R₃₃ wird ersetzt durch:

R₃₃₁ = (( (Funktion, { ("Bildschirm", 0,5), ("Drucker", 1,0),
("Tastatur", 1,0), ("Zentraleinheit", 1,0)}),
(Herst.-Jahr, [emptyset]),
(Gewicht, (0; 25,2; 0; 6)_LR)), "normal", 0,75)

R₃₃₂ = (( (Funktion, [emptyset]),
(Herst.-Jahr, (1981; 1995; 2; 0)_LR),
(Gewicht, (0; 25,2; 0; 6)_LR)), "normal", 0,75)

R₃₃₃ = (( (Funktion, [emptyset]),
(Herst.-Jahr, [emptyset]),
(Gewicht, (0; 13,2; 0; 3,5)_LR)), "normal", 0,75)

Abb. 40: Spezialisierung der Regel R₃₃ (MUSP)
Offensichtlich ist die Regel R₃₂₃ spezieller als R₃₃₃ und R₃₃₂ spezieller als R₃₂₂, so daß sich nun die unter "Ansätze für eine Optimierung des Verfahrens" beschriebene Beseitigung über-flüssiger Regeln anbietet.
Mit dem Eintreffen von Datensatz EX₄ sind nun erstmalig die bestehenden Regeln zu spezialisieren, da Fehlklassifikationen auftreten. Dies und die Anpassung der maximal-generalisierten Regel R₄₀ anhand der vorhandenen Beispiele soll jedoch hier nicht mehr näher betrachtet werden, da hierzu lediglich die bereits dargestellten Operationen in analoger Weise wiederholt werden.

5.5 Implementierung des Verfahrens

Es sollen nun auch für das Verfahren MUSP einige Hinweise zu einer Implementierung in Oracle 7 gegeben werden. Der vollständige, lauffähige Quellcode für eine prototypische Implementierung befindet sich auf dem Datenträger im Anhang zu dieser Arbeit.
Auch hier ist es sinnvoll, zunächst zu einer anwendungsunabhängigen internen Beschreibung der zugrundeliegenden Daten zu gelangen. Hierzu sind die Tabellen "Attribute", "KlassenTypen", "Klassen", "Beispiele", "BspAttr" und "BspKls" entsprechend den Ausführungen in Kapitel 4.3.4 anzulegen. Auch die beiden Trigger zur Konsistenzprüfung bzw. Erzeugung des anwendungsunabhängigen Formats können unverändert übernommen werden. Anstelle der Konsistenzprüfung von Attributwerten durch einen Trigger könnte hier alternativ eine entsprechende automatische Erweiterung der Attributbeschreibungen erfolgen - das Verfahren würde damit um ein weiteres dynamisches Element erweitert.
Durch einen AFTER-Trigger ist eine PL/SQL-Prozedur anzustoßen, welche nach dem Eintreffen eines neuen Beispiels die Erzeugung bzw. widerspruchsgesteuerte Spezialisierung von Regeln übernimmt. Die Darstellung von Bedingungen und Regeln sieht nun wie folgt aus:
CREATE TABLE Regeln ( RegelNr NUMBER(5,0),
Beispiel NUMBER(4,0),
Klasse NUMBER(3,0),
MaxAktiv NUMBER(3,2) NOT NULL,
Vater NUMBER(5,0),
Gueltig NUMBER(1,0),
CONSTRAINT pk_regeln
PRIMARY KEY (RegelNr),
CONSTRAINT fk_regeln_1
FOREIGN KEY (Beispiel, Klasse)
REFERENCES BspKls(BspNr, Klasse)
ON DELETE CASCADE,
CONSTRAINT fk_regeln_2
FOREIGN KEY (Vater)
REFERENCES Regeln(RegelNr));
CREATE TABLE FuzzyMengen ( Regel NUMBER(5,0),
Attribut NUMBER(2,0),
Auspraegung NUMBER(3,0),
Zugehoerig NUMBER(3,2),
CONSTRAINT pk_fuzzymengen
PRIMARY KEY (Regel, Attribut,
Auspraegung),
CONSTRAINT fk_fuzzymengen_1
FOREIGN KEY (Regel)
REFERENCES Regeln(RegelNr)
ON DELETE CASCADE,
CONSTRAINT fk_fuzzymengen_2
FOREIGN KEY (Attribut)
REFERENCES Attribute (AttrNr),
CONSTRAINT ck_fmengen_zugehoerig
CHECK (Zugehoerig BETWEEN 0 AND 1));
CREATE TABLE LR_Intervalle ( Regel NUMBER(5,0),
Attribut NUMBER(2,0),
M1 NUMBER(7,2) NOT NULL,
M2 NUMBER(7,2) NOT NULL,
Alpha NUMBER(7,2) NOT NULL,
Beta NUMBER(7,2) NOT NULL,
CONSTRAINT pk_lr_intervalle
PRIMARY KEY (Regel, Attribut),
CONSTRAINT fk_lr_intervalle_1
FOREIGN KEY (Regel)
REFERENCES Regeln(RegelNr)
ON DELETE CASCADE,
CONSTRAINT fk_lr_intervalle_2
FOREIGN KEY (Attribut)
REFERENCES Attribute(AttrNr),
CONSTRAINT ck_lr_interv_m1_m2_alpha_beta
CHECK ((M1 <= M2) AND (Alpha >= 0)
AND (Beta >= 0)));
Da NULL-Werte in Fremdschlüsseln nicht erlaubt sind, ist in der Tabelle "Regeln" auch hier wieder die Eintragung eines Dummy-Datensatzes vonnöten, um die maximal-generalisierten Regeln, welche nicht durch widerspruchsgesteuerte Spezialisierung anderer Regeln entstanden sind, anlegen zu können. Alternativ ist es auch möglich, bei solchen Regeln die eigene Nummer für die Spalte "Vater" einzusetzen. Die Tabelle "FuzzyMengen" nimmt diejenigen Bedingungen auf, welche sich auf nominale Attribute beziehen; dabei könnte eventuell als zusätzliche Konsistenzprüfung durch einen zeilenorientierten BEFORE-Trigger sichergestellt werden, daß nur Ausprägungen vorkommen, welche für das angegeben Attribut in der Tabelle "Attribute" vorgesehen sind. "LR_Intervalle" ist für die Repräsentation derjenigen Bedingungen erforderlich, die sich auf ordinale oder metrisch skalierte Merkmale beziehen.
Der Zugriff auf Regeln für die zukünftige Klassifikation neuer Zusammenfassungen von Merkmalsausprägungen sollte innerhalb eines Packages [72]⁾ gekapselt werden. So läßt sich die Vorhaltung besonders "wertvoller" Regeln im schnellen Hauptspeicher nach außen hin transparent realisieren.

5.6 Bewertung des Verfahrens

Auch die Methode MUSP soll nun kurz einer Bewertung unterzogen werden. Es lassen sich dabei einige Vor- und Nachteile des Verfahrens Incremental Fuzzy STAR übernehmen:
Positiv ist auch hier wieder hervorzuheben, daß es sich um ein echt inkrementelles Verfahren (im Sinne von Definition 1) handelt, da Vergangenheitsbeispiele nur in recht begrenztem Umfang für den späteren Verlauf des Lernprozesses herangezogen werden.
Ferner ist auch durch dieses Verfahren gewährleistet, daß jedes bereits präsentierte Beispiel in Zukunft korrekt klassifiziert wird.
Durch einige kleinere Änderungen ist auch MUSP leicht dahingehend erweiterbar, daß aus Beispielen mit nur ungefähren Angaben gelernt werden kann. Es sind dazu die bisherigen scharfen Zentralwerte durch entsprechende Fuzzy-Mengen zu ersetzen und die widerspruchsgesteuerte Spezialisierung dahingehend anzupassen.
Auch MUSP ist in der Lage, ein sehr hohes Maß an Regelwissen zu induzieren. Dabei ist es über die im vorherigen Kapitel dargestellten Optimierungstechniken möglich, den Trade-Off zwischen der Anzahl erzeugter Regeln und dem Laufzeit- und Speicherplatzbedarf des Verfahrens frei zu wählen, ohne Gefahr zu laufen, daß bereits bekannte Beispiele in Zukunft falsch klassifiziert werden.
Im Gegensatz zu Incremental Fuzzy STAR ist jedoch hervorzuheben, daß die Spezialisierung deutlich mehr an vorhandenen Informationen nutzt und so grundsätzlich zu Regeln führt, die so generell wie möglich sind, ohne dabei ein bekanntes Beispiel falsch zu klassifizieren oder kein Beispiel mehr zu überdecken. Das Verfahren kann also als "intelligenter" angesehen werden.
Die von MUSP generierten Regeln lassen sich im Hinblick auf eine Erklärungskomponente unter Umständen nicht ganz so leicht in einer vertrauten Form dem Benutzer präsentieren. Dies ist darauf zurückzuführen, daß als Grundlage von Bedingungen für nominale Merkmale nun ebenfalls Fuzzy-Mengen zugelassen sind. Als Lösung könnte man z.B. in Erwägung ziehen, die Zugehörigkeit nominaler Ausprägungen zu Fuzzy-Mengen oberhalb einer bestimmten Schranke durch unterschiedliche Farbintensitäten o.ä. darzustellen. Für ordinale und metrisch skalierte Attribute besteht aufgrund der kompakten Repräsentation in Form von LR-Fuzzy-Intervallen kein Problem.
Negativ anzumerken ist auch hier die relativ hohe Anzahl von Parametern, welche das Verfahren steuern, sowie der je nach Wahl der Parameter hohe Speicherbedarf des Verfahrens.

6 Weitere Verfahren; Ausblick

Dieses Kapitel gibt einen Überblick über zwei weitere Verfahren zur Akquisition unscharfer Regeln. Es handelt sich dabei zum einen um eine Erweiterung der bekannten Methode ID3, zum anderen um einen neuen Ansatz, welchem auf Fuzzy-Mengen verallgemeinerte Mengenoperationen und Maße zugrunde liegen. Abschließend wird in einem Ausblick aufgezeigt, welche Forschungstätigkeiten im Sinne einer Erweiterung der vorliegenden Arbeit wünschenswert sind.

6.1 Fuzzy-ID3

6.1.1 Das Verfahren

ID3 ist ein nicht-inkrementelles Verfahren (vgl. Definition 1) zur Induktion eines minimalen Entscheidungsbaums auf der Grundlage von Beispielen mit nominalen Attributausprägungen und scharf abgegrenzten Zugehörigkeiten zu zwei disjunkten Klassen ("Ja"/"Nein")[73]⁾. Jeder Knoten eines solchen Entscheidungsbaums repräsentiert eine Menge von Beispielen. Die Kanten stehen für scharfe Bedingungen, welche die Beispielmenge eines Knotens in so viele Knoten der untergeordneten Ebene aufteilen, wie es bei den Beispielen verschiedene Ausprägungen des in der Bedingung geprüften Merkmals gibt. Die Beispielmengen verschiedener Knoten auf einer Ebene sind also disjunkt. Falls ein Knoten nur Beispiele zu einer einzigen Klasse enthält, so heißt er homogen, ansonsten inhomogen. Die genaue Vorgehensweise des Verfahrens ist folgendem Struktogramm zu entnehmen:

Bilde einen Wurzelknoten, in welchem sämtliche Beispiele zusammengefaßt sind;

Wiederhole, solange noch inhomogene Blätter existieren:
Wähle eine beliebiges inhomogenes Blatt B;
Bilde die Attributmenge A = {a₁, ..., a_n) , in der alle Attribute, nach denen auf dem
Pfad von der Wurzel bis zum Blatt B noch nicht aufgespalten wurden, enthalten sind;
IG_Min <- 1
a_Min <- a₁
DO i = 1 (+1) nicht
m <- Anzahl möglicher Ausprägungen von Attribut a_i
IG(i) <- 0
DO j = 1 (+1) m
K_j<- Menge der Beispiele aus B, bei denen das Attribut a_i die
Ausprägung j besitzt
p <- (Anzahl der "Ja"-Beispiele in K_j) / Card(K_j)
q <- 1-p
E <- - p · log₂p - q · log₂q
p_j <- Card(K_j) / Card(B)
IG(i) <- IG(i) + p_j · E
IG(i) < IG_Min ?
Ja Nein
IG_Min <- IG(i)
a_Min <- a_i
m <- Anzahl möglicher Ausprägungen von Attribut a_Min
DO i = 1 (+1) m
Erzeuge ein neues Blatt B_i als Kind von B;
Füge alle Beispiele aus B, bei denen das Attribut a_Min die Ausprägung i
aufweist, in das Blatt B_i ein;

Abb. 41: Das Verfahren ID3
Dabei heißt die Größe E zu einem bestimmten Knoten Entropie. Sie ist ein Maß für die Unordnung in der Beispielmenge eines Knotens bezüglich der Klassenzugehörigkeit. Der Wert IG(i) ist der erwartete Informationsgehalt in den neu zu erzeugenden Blättern, falls am betrachteten Knoten eine Aufspaltung nach Attribut a_i durchgeführt wird. Durch Wahl desjenigen Attributs a_Min für die Aufspaltung, welches IG minimiert, werden inhomogene Blätter so aufgeteilt, daß die in ihnen enthaltenen Beispiele möglichst intensiv gemäß ihrer Klassenzugehörigkeit getrennt werden. Der durch das Verfahren generierte Entscheidungs-baum läßt sich auf triviale Weise in Regeln überführen, welche das komplette für eine Klassifikation der vorhandenen Beispiele erforderliche Wissen repräsentieren.
Fuzzy-ID3 ist eine Erweiterung dieses Verfahrens mit dem Ziel, auch unscharfes Wissen bezüglich metrisch skalierter Attribute durch Bildung eines Entscheidungsbaums zu akquirieren [74]⁾. Dazu wird die vorgestellte Methode folgendermaßen modifiziert:
Für die betrachteten Attribute wird angenommen, sie seien entweder nominaler oder metrisch skalierter Natur. Metrisch skalierte Attribute werden durch linguistische Variablen [75]⁾ repräsentiert. Die als Grundlage für die Induktion des Entscheidungsbaums dienenden Beispiele sind den Termen dieser linguistischen Variablen entsprechend ihrer konkreten Merkmalsausprägungen graduell zugehörig. Die Berechnung des Informationsgehalts IG wird dahingehend verändert, daß die Werte für p_j nun nicht mehr als relative Häufigkeit der j-ten Ausprägung des betrachteten Attributs aller Beispiele im Blatt, sondern als relative Kardinalität [76]⁾ der j-ten Ausprägung des betrachteten Attributs angenommen wird:
p_j = (Summe der Zugehörigkeitswerte zur j-ten Ausprägung) / (Anzahl der Beispiele im Blatt)
Da im Falle scharfer Attributausprägungen die relativen Kardinalitäten mit den relativen Häufigkeiten übereinstimmen, handelt es sich bei Fuzzy-ID3 um eine echte Erweiterung von ID3.
Die Knoten von Fuzzy-ID3 sind nun Fuzzy-Mengen von Beispielen, wobei sich der Zugehörigkeitsgrad eines Beispiels zu einem Knoten aus dem minimalen Zugehörigkeitswert zu den auf dem Pfad von der Wurzel bis zum Knoten betrachteten linguistischen Termen ergibt. Da die Stützmengen der Terme linguistischer Variablen im allgemeinen nicht disjunkt sind, kann ein Beispiel nun in mehreren Knoten mit jeweils gradueller Zugehörigkeit enthalten sein. Durch Zusammenfassung der linguistischen Terme, nach denen bis zu einem bestimmten Blatt aufgespalten wurde, in einer Prämisse, können nun auf einfache Weise unscharfe Regeln gebildet werden, deren Konklusion aus der Klassenzugehörigkeit der Beispiele im betrachteten Blatt besteht.

6.1.2 Bewertung des Verfahrens

Das vorgestellte Verfahren Fuzzy-ID3 wird nun einer kurzen Bewertung unterzogen. Dabei wird das Augenmerk insbesondere auf der Eignung für den Einsatz in einem Prognosesystem (wie in Kapitel 2.1.2 geschildert) ruhen.
Problematisch zu beurteilen sind zunächst die Prämissen der Methode:
Eines der Grundprobleme bei der Darstellung unscharfen Wissens besteht gerade in der Festlegung linguistischer Variablen für die betrachteten Attribute [77]⁾. Zu einem Erlernen der zugrundeliegenden linguistischen Terme trägt Fuzzy-ID3 jedoch nichts bei. Stattdessen wird von dem unrealistischen Idealfall ausgegangen, eine derartige Zuordnung läge bereits vor. Eine eventuelle Inkrementalisierung des Verfahrens scheidet daher praktisch aus, denn die Festlegung linguistischer Terme wird in aller Regel wesentlich auf den Verteilungen der Attributausprägungen beruhen, die jedoch a priori unbekannt sind.
Ferner sind die für den Lernprozeß heranzuziehenden Beispiele in zwei klar voneinander abgegrenzte Klassen eingeteilt - es wird also nur der Fall einer binären scharfen Entscheidung berücksichtigt. Damit ist nicht nur die Einsatzfähigkeit des Verfahrens erheblich eingeschränkt, sondern es muß geradezu als inkonsequent beurteilt werden, da zwar einerseits mit unscharfen Prämissen, jedoch andererseits mit scharfen Konklusionen operiert wird.
Die graduelle Zugehörigkeit von Beispielen zu mehreren Blättern kann bei Einsatz eines entsprechenden Inferenzmachanismus sicherlich sinnvoll sein. Bei Fuzzy-ID3 führt sie jedoch unter Umständen dazu, daß Beispiele, deren Zugehörigkeit zu einer der betrachteten Klassen klar gegeben ist, von den aus dem Verfahren resultierenden Regeln nur noch eine graduelle Zugehörigkeit zu ihrer Klasse zugeordnet bekommen - eine mehr verwirrende als nützliche Eigenschaft der Methode.
Im Hinblick auf die Einsatzfähigkeit in einem Prognosesystem ist anzumerken, daß die Menge der durch Fuzzy-ID3 erzeugten Regeln vergleichsweise gering ist. Dies ist darauf zurückzuführen, daß die Generierung eines minimalen Entscheidungsbaums angestrebt wird. Für Prognosezwecke sollte es jedoch möglich sein, ein Maximum an Wissen aus den gegebenen Beispielen zu extrahieren bzw. über die Wahl entsprechender Parameter den Trade-Off zwischen der Menge zu erzeugender Regeln einerseits und Speicherplatzbedarf / Laufzeitverhalten andererseits festzulegen.
Aus den angeführten Gründen ist das Verfahren Fuzzy-ID3 für den Zweck der vorliegenden Arbeit ungeeignet.

6.2 Akquisition unscharfer Regeln durch verallgemeinerte Mengenoperationen

6.2.1 Das Verfahren

Für das nun darzustellende Verfahren ist zunächst die Einführung einer Operation nötig, welche die Bildung der Schnittmenge scharfer Mengen auf Fuzzy-Mengen verallgemeinert:

Definition 33: (Schnittmenge von Fuzzy-Mengen)

Es seien Fuzzy-Mengen auf derselben Grundmenge X. Dann heißt die Abbildung

Schnittmenge der Fuzzy-Mengen ). [78]⁾. Analog der Notation für die Schnittmenge scharfer Mengen wird als Schreibweise für auch verwendet.

Ferner werden zwei Maße definiert, welche angeben, wie sehr zwei Fuzzy-Mengen sich schneiden bzw. wie vollständig eine Fuzzy-Menge in einer zweiten Fuzzy-Menge enthalten ist:

Definition 34: (Grad des Enthaltenseins einer Fuzzy-Menge in einer anderen)

Seien und zwei Fuzzy-Mengen auf derselben Grundmenge X. Dann heißt die Abbildung

Grad des Enthaltenseins von in ).[79]⁾.
Definition 35: (Grad der Schneidung zweier Fuzzy-Mengen)
Seien und zwei Fuzzy-Mengen auf derselben Grundmenge X. Dann heißt die Abbildung

Grad der Schneidung von und ).[80]⁾.
Vorstehende Maßzahlen sind Verallgemeinerungen entsprechender Zusammenhänge zwischen scharfen Mengen A und B:
* I(A, B) = 1 gilt genau dann, wenn A [reflexsubset] B, ansonsten 0.
* J(A, B) = 1 gilt genau dann, wenn A [intersection] B != [emptyset].
Das Verfahren beruht nun auf folgender Vorgehensweise [81]⁾:
Ausgehend von Attributen, deren mögliche Ausprägungen bereits durch LR-Fuzzy-Vektoren (vgl. Definition 8) codiert wurden, wird für jede konkret vorliegende Merkmalsausprägung eines Beispielobjekts die Zugehörigkeit zu den LR-Fuzzy-Intervallen des entsprechenden Attributs durch Anwendung der Anfragefunktion (vgl. Definition 9) ermittelt. Auf analoge Weise wird die Zugehörigkeit der Beispiele zu den betrachteten Klassen festgestellt. Für jedes LR-Fuzzy-Intervall wird nun eine Fuzzy-Menge gebildet, in die alle Beispielobjekte mit dem ermittelten Zugehörigkeitsgrad ihrer entsprechenden Merkmalsausprägung zu dem betrachteten LR-Fuzzy-Intervall aufgenommen werden. Auf der Grundlage der so gebildeten Fuzzy-Mengen werden nun zwei Arten unscharfer Regeln gebildet:
Sichere Regeln ergeben sich, indem zu einer bestimmten Auswahl von Fuzzy-Mengen zu Attributen zunächst die Schnittmenge gebildet wird. Durch Berechnung des Grades der Schneidung dieser Fuzzy-Menge mit der zu einer bestimmten Klasse gehörigen Fuzzy-Menge von Beispielen erhält man den Glaubwürdigkeitsgrad einer solchen Regel.
Die Glaubwürdigkeitsgrade möglicher Regeln ergeben sich auf analoge Weise durch Berechnung des Grades des Enthaltenseins der gebildeten Schnittmenge in der zu einer Klasse gehörigen Fuzzy-Menge.
Die Berechnung der Schnittmenge entspricht dabei der Verknüpfung der durch die Fuzzy-Mengen dargestellten unscharfen Bedingungen durch ein logisches "Und".
Das geschilderte Verfahren wird nun durch ein kurzes Beispiel verdeutlicht, dem folgende Datenkonstellation zugrunde liegt [82]⁾:

	Alter:		Gewicht:		Shredderabfall:
Produkt	jung	alt	leicht	schwer	normal
P₁	0,3	0,8	0,2	0,9	0,3
P₂	0,4	0,7	0,4	0,7	0,8
P₃	0,7	0,4	0,6	0,7	0,5
P₄	0,8	0,5	0,3	0,8	0,7
P₅	0,2	0,7	0,2	0,5	0,4
P₆	0,9	0,2	0,8	0,2	0,7
P₇	0,3	0,6	0,7	0,1	0,4

Abb. 42: Beispieldaten für die Anwendung verallgemeinerter Mengenoperationen
Durch die Attribute "Alter" und "Gewicht" werden somit folgende Fuzzy-Mengen definiert:

"Alter - jung": {(P₁, 0,3), (P₂, 0,4), (P₃, 0,7), (P₄, 0,8), (P₅, 0,2), (P₆, 0,9), (P₇, 0,3)}

"Alter - alt": {(P₁, 0,8), (P₂, 0,7), (P₃, 0,4), (P₄, 0,5), (P₅, 0,7), (P₆, 0,2), (P₇, 0,6)}

"Gewicht - leicht": {(P₁, 0,2), (P₂, 0,4), (P₃, 0,6), (P₄, 0,3), (P₅, 0,2), (P₆, 0,8),

(P₇, 0,7)}

"Gewicht - schwer": {(P₁, 0,9), (P₂, 0,7), (P₃, 0,7), (P₄, 0,8), (P₅, 0,5), (P₆, 0,2),

(P₇, 0,1)}

Eine weitere Fuzzy-Menge repräsentiert die Klasse "Shredderabfall normal":

{(P₁, 0,3), (P₂, 0,8), (P₃, 0,5), (P₄, 0,7), (P₅, 0,4), (P₆, 0,7), (P₇, 0,4)}

Zur Bildung der sicheren Regeln werden zunächst die Grade des Enthaltenseins der möglichen Schnittmengen von Fuzzy-Mengen zu Attributen in der Fuzzy-Menge zur Klasse "Shredder-abfall normal" berechnet:

Bei Annahme einer Signifikanzschranke von 0,5 für die Glaubwürdigkeit lassen sich daraus folgende unscharfe Regeln ableiten:

"Wenn Alter = jung, dann Shredderabfall = normal." (sicher: 0,5)

"Wenn Alter = jung und Gewicht = leicht, dann Shredderabfall = normal." (sicher: 0,5)

"Wenn Alter = jung und Gewicht = schwer, dann Shredderabfall = normal." (sicher: 0,5)

Dabei geben die in Klammern gesetzten numerischen Werte die Glaubwürdigkeitsgrade bezüglich der Sicherheit der Regeln an.

Analog hierzu werden die Grade des Schneidens der Fuzzy-Mengen ermittelt, um die Glaubwürdigkeitsgrade der möglichen Regeln zu bestimmen:

Wieder unter der Annahme einer Signifikanzschranke von 0,5 für die Glaubwürdigkeit lassen sich daraus folgende unscharfe Regeln ableiten:
"Wenn Alter = jung, dann Shredderabfall = normal." (möglich: 0,7)
"Wenn Alter = alt, dann Shredderabfall = normal." (möglich: 0,7)
"Wenn Gewicht = leicht, dann Shredderabfall = normal." (möglich: 0,7)
"Wenn Gewicht = schwer, dann Shredderabfall = normal." (möglich: 0,7)
"Wenn Alter = jung und Gewicht = leicht, dann Shredderabfall = normal." (möglich: 0,7)
"Wenn Alter = jung und Gewicht = schwer, dann Shredderabfall = normal." (möglich: 0,7)
"Wenn Alter = alt und Gewicht = schwer, dann Shredderabfall = normal." (möglich: 0,7)
Hier geben die Werte in Klammern die Glaubwürdigkeitsgrade für die Möglichkeit der Regeln an.

6.2.2 Bewertung des Verfahrens

Zur Überprüfung der Eignung einer Akquisition unscharfer Regeln durch verallgemeinerte Mengenoperationen für den Einsatz in einem Prognosesystem soll auch dieses Verfahren einer kurzen Bewertung unterzogen werden.
Positiv anzumerken ist zunächst die Möglichkeit, das Verfahren auf sehr einfache Weise inkrementell zu gestalten. Da die verwendeten Mengenoperatoren und -maßzahlen sämtlich auf der Anwendung von Minimum- und Maximum-Operatoren beruhen, läßt sich die Aktualisierung der Bewertung einer Regel anhand eines neuen Beispieldatensatzes sehr effizient durchführen, sofern die bisher für die Berechnung relevanten Minimal- bzw- Maximalwerte bekannt sind.
Andererseits darf jedoch nicht übersehen werden, daß die Methode eigentlich nur zu einem initialen Zeitpunkt Regeln generiert, um diese dann anschließend anhand der vorliegenden Beispiel-Datensätze zu bewerten. Eine Verfeinerung von Regeln durch die Hinzuziehung neuer Datensätze findet nicht statt. Die Erzeugung der Regeln ist stattdessen ausschließlich von der als bekannt vorausgesetzten Codierung der Merkmalsdomänen in LR-Fuzzy-Intervallen abhängig - ein Problem, welches bereits im Zusammenhang mit der Methode Fuzzy-ID3 diskutiert wurde.
Die Anzahl der erzeugten Regeln wirkt zwar im vorgestellten Beispiel überschaubar, sie nimmt jedoch mit der Anzahl der Attribute und den auf diesen definierten LR-Fuzzy-Intervallen stark zu: Bei n Attributen mit jeweils k LR-Fuzzy-Intervallen werden pro Klasse

zu bewertende Regeln erzeugt. So ergeben sich z.B. bei 10 Attributen mit jeweils nur 3 LR-Fuzzy-Intervallen für jede Klasse bereits r = 1.048.575 Regeln. Bedenkt man, daß kommerzielle Datenbanken in der Regel mehr als vierzig, manchmal sogar über hundert Attribute aufweisen [83]⁾, so würde durch das Verfahren eine gigantische Anzahl an Regeln erzeugt.
Problematisch ist schließlich die Interpretation der erzeugten Regeln. So liefern die Autoren keinerlei Auskunft darüber, inwiefern daß Vorhandensein "sicherer" und "möglicher" Regeln mit unterschiedlichen Glaubwürdigkeitsgraden in einem Inferenzprozeß Berücksichtigung finden kann.
Das Verfahren wird aus den erörterten Gründen ebenfalls als ungeeignet für den Zweck dieser Arbeit zurückgewiesen.

6.3 Ausblick

Die vorliegenden Arbeit stellt keineswegs eine erschöpfende Darstellung des Entwurfs inkrementeller und unscharfer Verfahren der automatischen Wissensakquisition und deren Anwendung in einem betrieblichen Prognosesystem dar. Vielmehr sind verschiedene Erweiterungen sinnvoll, von denen einige beispielhaft angeführt werden sollen.
Hier ist zunächst eine Weiterentwicklung der Verfahren an sich anzustreben. Als wichtiges Ziel ist dabei eine kontrollierte Behandlung von Inkonsistenzen oder fehlenden Daten zu nennen. Auch die Untersuchung einer Kopplung der vorgestellten Verfahren mit menschlichen Experten im Sinne einer Vorgabe- oder Validierungsmöglichkeit von Regeln ist wünschens-wert. Schließlich sollte geprüft werden, welche Kombinationen möglicher Parameter-einstellungen der Verfahren bezüglich welcher Datenkonstellationen erfolgversprechend sind.
Schließlich sollte auch eine softwaretechnische Aufarbeitung der Verfahren erfolgen. Die Weiterentwicklungen der STAR-Methode und das Verfahren MUSP weisen Möglichkeiten zur Parallelisierung auf, da die Bildung von Regeln unabhängig voneinander erfolgt. Das in dieser Arbeit eingesetzte aktive Datenbanksystem Oracle 7 ist für verschiedene Mehrprozessor-Architekturen verfügbar, so daß sich ein Einsatz eventuell auch für die Implementierung entsprechender paralleler Algorithmen anbietet. Ferner gilt es zu überprüfen, wie eine effiziente Gestaltung der Schnittstellen von der Betriebsdatenerfassung bzw. Auftragsverwaltung zur Datenbank einerseits, und von der Datenbank zum Informationssystem des Sachbearbeiters der Angebotsplanung andererseits erfolgen kann.

Literatur

Allen, B. P. (1994): Case-Based Reasoning: Business Applications. In: Communications of the ACM 37 (1994) 3, Seite 40-42.
Ammersbach, K. (1992): Decision Support for Retrieval From Fact Databases. In: Schader, M. (1992), Seite 153-159.
Angerer, G., Bätcher, K., Bars, P. (1993): Verwertung von Elektronikschrott - Stand der Technik, Forschungs- und Technologiebedarf. Abschlußbericht für das Bundesministerium für Forschung und Technologie des Fraunhofer-Insituts für Systemtechnik und Innovationsforschung (ISI). Berlin 1993.
Becker, J., Rosemann, M. (1993): Logistik und CIM - Die effiziente Material- und Informationsflußgestaltung im Industrieunternehmen. Berlin et al. 1993.
Brazdil, P. B. (1993): Machine Learning: ECML-93 (European Conference on Machine Learning Vienna, Austria, April 5-7, 1993). Berlin et al. 1993.
Carbonell, J. G. (1993): Machine Learning - Paradigms and Methods. Cambridge et al. 1993.
Chipman, S., Meyrowitz, A. L. (1993): Foundations of Knowledge Acquisition: Machine Learning. Boston et al. 1993.
Ehrlenspiel, K. (1985): Kostengünstig Konstruieren - Kostenwissen, Kosteneinflüsse, Kostensenkung. Berlin et al. 1985.
Feller, A. H. (1992): Kalkulation in der Angebotsphase mit dem selbsttätig abgeleiteten Erfahrungswissen in der Arbeitsplanung. Karlsruhe 1992.
Fensel, D. (1992): JoJo. Vortrag auf dem Fachgruppentreffen Maschinelles Lernen, 16. und 17. Juli 1992, Osnabrück.
Fensel, D., Klein, J. (1992): RELAX, H-RELAX, and I-RELAX. Three Algorithms for Rule Induction and Pruning. Forschungsbericht 235 des Instituts für angewandte Informatik und formale Beschreibungsverfahren der Universität Karlsruhe (TH).
Forsyth, R. (1989a): Inductive Learning for Expert Systems. In: Forsyth et al. (1989b), Seite 197-220.
Forsyth, R. (1989b): Expert Systems - Principles and Case Studies. London et al. 1989.
Frawley, W. J., Piatetsky-Shapiro, G., Matheus, C. J. (1992): Knowledge Discovery in Databases: An Overview. In: AI Magazine 13 (1992) 3, Seite 57-70..
Froese, J., Moazzami, M., Rautenstrauch, C., Welter, H. (1994): Effiziente Systementwicklung mit Oracle 7. Bonn et al. 1994.
Gennari, J. H., Langley, P., Fisher, D. (1993): Models of Incremental Concept Formation. In: Carbonell, J. G. (1993), Seite 11-61.
Grauel, A. (1995): Fuzzy-Logik - Einführung in die Grundlagen mit Anwendungen. Mannheim et al. 1995.
Haasis, H.-D., Hilty, L. M., Kürzl, H., Rautenstrauch, C. (1995): Betriebliche Umweltinformationssysteme (BUIS) - Projekte und Perspektiven. Marburg 1995.
Hecht, A., Hellendoorn, H., Leufke, A., Storjohann, K. (1994): Adaptions- und Akquisitionstechniken für Fuzzy-Systeme, Teil I. In: Informatik Spektrum (1994) 17, Seite 87-95.
Höfling, J. (1995): Blauer Engel - blauer Dunst? In: Business Computing (1995) 5, Seite 94-96.
Kandel, A. (1992): Fuzzy Expert Systems. Boca Raton 1992.
de Korvin, A., Bourgois, B., Kleyle, R. (1994): Extracting Fuzzy Rules under Uncertainty and Measuring Definability Using Rough Sets. In: Journal of Intelligent and Fuzzy Systems (1994) 2, Seite 75 - 87.
Kotz, A. M. (1989): Triggermechanismen in Datenbanksystemen. Berlin et al. 1989.
Kraus, M., Heimig, I., Scheer, A.-W. (1995): Informationsmodell für die integrierte Entsorgungssicherung. In: Haasis, H.-D., Hilty, L. M., Kürzl, H., Rautenstrauch, C. (1995), Seite 67-77.
Kurbel, K. (1990): Programmentwicklung. 5., vollständig überarbeitete und erweiterte Auflage. Wiesbaden 1990.
Kurbel, K. (1992): Entwicklung und Einsatz von Expertensystemen - Eine anwendungsorientierte Einführung in wissensbasierte Systeme. 2., verbesserte Auflage. Berlin et al. 1992.
Kurbel, K. (1993): Produktionsplanung und -steuerung: Methodische Grundlagen von PPS-Systemen und Erweiterungen. München et al. 1993.
Kurbel, K., Schneider, B. (1995): Konzeption eines betrieblichen Recycling-Informationssystems auf der Basis von Produktionsdaten. In: Haasis, H.-D., Hilty, L. M., Kürzl, H., Rautenstrauch, C. (1995), Seite 79-91.
Michalski, R. S. (1983): A Theory And Methodology Of Inductive Learning. In: Michalski, R. S., Carbonell, J. C., Mitchell, T. M. (1983), Seite 83-133.
Michalski, R. S. (1993): Learning = Inferencing + Memorizing; Basic Concepts of Inferential Theory of Learning and Their Use for Classifying Learning Processes. In: Chipman, S., Meyrowitz, A. L. (1993), Seite 1-42.
Michalski, R. S., Bergadano, F., Matwin, S., Zhang, J. (1993): Learning Flexible Concepts Using a Two-Tiered Representation. In: Chipman, S., Meyrowitz, A. L. (1993), Seite 145-202.
Michalski, R. S., Carbonell, J. C., Mitchell, T. M. (1983): Machine Learning - An Artificial Intelligence Approach. Berlin et al. 1983.
Nagl, M. (1992): Ada - Eine Einführung in die Programmiersprache der Softwaretechnik. Braunschweig, Wiesbaden 1992.
Nauck, D., Klawonn, F., Kruse, R. (1994): Neuronale Netze und Fuzzy-Systeme - Grundlagen des Konnektionismus, Neuronaler Fuzzy-Systeme und der Kopplung mit wissensbasierten Methoden. Braunschweig, Wiesbaden 1994.
Nietsch, T., Rautenstrauch, C., Rehfeldt, M., Rosemann, M., Turowski, K. (1994): Verbesserung von PPS-Systemen durch Fuzzy-Logik. In: CIM Management (1994) 6, Seite 22-26.
Oracle Corp. (1991): SQL*Plus User´s Guide and Reference. Oracle Corporation 1991.
Oracle Corp. (1992): PL/SQL User´s Guide and Reference. Oracle Corporation 1992.
Pickel, H. (1989): Kostenmodelle als Hilfsmittel zum kostengünstigen Konstruieren. München et al. 1989.
Quinlan, J. R. (1983): Learning Efficient Classification Procedures and Their Application to Chess End Games. In: Michalski, R. S., Carbonell, J. C., Mitchell, T. M. (1983), Seite 463-482.
Rommelfanger, H. (1994). Fuzzy Decision Support Systeme - Entscheiden bei Unschärfe. Berlin et al. 1994.
Schader, M. (1992): Analyzing and Modeling Data and Knowledge. Proceedings of the 15th Annual Conference of the "Gesellschaft für Klassifikation e.V.". Berlin et al. 1992.
Schneider, B. (1992): Automatische Wissensakquisition für Klassifikationssysteme. Diplomarbeit an der Universität Dortmund 1992.
Schneider, B. (1993): Neuronale Netze für betriebliche Anwendungen: Anwendungspotentiale und existierende Systeme. Arbeitsbericht Nr. 22 des Instituts für Wirtschaftsinformatik der Westfälischen-Wilhelms-Universität Münster, 1993.
Seidlmeier, H. (1991): Kostenrechnung und wissensbasierte Systeme - Theoretische Überlegungen und Entwicklung eines prototypischen Anwendungssystems. München et al 1991.
Seraphin, M. (1994): Neuronale Netze und Fuzzy-Logik. Verknüpfung der Verfahren, Anwendung, Vor- und Nachteile, Simulationsprogramm. München 1994.
Spengler, T. (1994): Industrielle Demontage- und Recyclingkonzepte - Betriebswirtschaftliche Planungsmodelle zur ökonomisch effizienten Umsetzung abfallrechtlicher Rücknahme- und Verwertungspflichten. Berlin 1994.
Torgo, L. (1993): Controlled Redundancy in Incremental Rule Learning. In: Brazdil, P. B. (1993), Seite 185-195.
Ultsch, A., Höffgen, K.-U. (1991): Automatische Wissensakquisition für Fuzzy-Expertensysteme aus selbstorganisierenden neuronalen Netzen. Forschungsbericht Nr. 404 des Fachbereichs Informatik der Universität Dortmund, 1991.
Vossen, G. (1994): Datenmodelle, Datenbanksprachen und Datenbank-Management-Systeme. Zweite, aktualisierte und erweiterte Auflage. Bonn et al. 1994.
Vossen, G., Groß-Hardt, M. (1993): Grundlagen der Transaktionsverarbeitung. Bonn et al. 1993.
Weber, R., Zimmermann, H.-J. (1991): Automatische Akquisition von unscharfem Expertenwissen. In: Künstliche Intelligenz (1991) 2, Seite 20-26.
Zadeh, L. A. (1965): Fuzzy Sets. In: Information and Control (1965) 8, Seite 338-353.
Zimmermann, H.-J. (1993): Fuzzy Set Theory - And Its Application. Second, Revised Edition. Boston et al. 1993.

Anhang

A Datenträger mit Dateien zur Implementierung von MUSP

B Kurzbeschreibung der Dateien auf dem Datenträger

Dateiname	Kurzbeschreibung
`CLEANALL.SQL`	Routine zum Leeren aller durch das Einfügen von Beispielen veränderten Tabellen
`DROP_ALL.SQL`	Batchdatei zum Löschen sämtlicher Tabellen, Pakete und Trigger
`GETTRACE.SQL`	Routine zum Auflisten der nach dem letzten Start von `CLEANALL.SQL` geschriebenen Protokollinformationen
`INS_EXi.SQL`	Routine zum Einfügen des i-ten Beispiel-Datensatzes
`INVALID.SQL`	Routine zum Auflisten derjenigen Datenbankobjekte, welche gegenwärtig ungültig sind und somit neu übersetzt werden müssen
`MAKE.SQL`	Batchdatei zum Generieren sämtlicher Tabellen, Pakete und Trigger
`PA_ATTR.SQL`	Erzeugung eines Pakets zur Handhabung des effizienten Zugriffs auf Attributinformationen
`PA_CLASS.SQL`	Erzeugung eines Pakets zur Handhabung des effizienten Zugriffs auf Klasseninformationen
`PA_FUZZY.SQL`	Erzeugung des Pakets für Fuzzy-Datenstrukturen und -Funktionen
`PA_MUSP.SQL`	Erzeugung des Pakets mit dem MUSP-Hauptalgorithmus und den Prozeduren für die widerspruchsgesteuerte Regelspezialisierung
`PA_RULES.SQL`	Erzeugung des Pakets mit Funktionen zur Regelanfrage u.ä.
`PA_TRACE.SQL`	Erzeugung des Pakets mit Prozeduren zur Protokollierung und Ausgabe von Fehlermeldungen
`PA_UTILS.SQL`	Erzeugung eines Pakets mit einigen hilfreichen Datenstrukturen
`TA_ATTR.SQL`	Erzeugung der Tabelle mit den Attributbeschreibungen
`TA_CLASS.SQL`	Erzeugung der Tabellen mit den Klassenbeschreibungen
`TA_EXAMP.SQL`	Erzeugung der (anwendungsabhängigen) Tabelle für die Aufnahme der Beispiel-Datensätze
`TA_EXINT.SQL`	Erzeugung der (anwendungsunabhängigen) Tabellen für die interne Darstellung der Beispiel-Datensätze
`TA_RULES.SQL`	Erzeugung der Tabellen für die Aufnahme von Regeln und den darin enthaltenen Bedingungen
`TA_TRACE.SQL`	Erzeugung der Tabelle für die Aufnahme von Protokollinformationen
`TR_CONS.SQL`	Erzeugung eines Triggers für die Konsistenzsicherung der Beispiel- Datensätze
`TR_LEARN.SQL`	Erzeugung des Triggers für die Übertragung der Beispiel-Datensätze vom anwendungsabhängigen Format in das interne, anwendungsunabhängige Format, sowie für das Anstoßen der MUSP-Hauptprozedur

[1] ) Vgl. Angerer, G., Bätcher, K., Bars, P. (1993), Seite 216.
[2] ) Vgl. Höfling, J. (1995).
[3] ) Vgl. Angerer, G., Bätcher, K., Bars, P. (1993), Seite 217.
[4] ) Vgl. Spengler, T. (1994), Seite 14.
[5] ) Vgl. Kurbel, K., Schneider, B. (1995).
[6] ) Vgl. Spengler, T. (1994), Seite 20 und Höfling, J. (1995).
[7] ) Vgl. Angerer, G., Bätcher, K., Bars, P. (1993), Seite 25.
[8] ) Vgl. Angerer, G., Bätcher, K., Bars, P. (1993), Seite 30-33.
[9] ) Vgl. Feller, A. H. (1992).
[10] ) Zu den ersten beiden Punkten vgl. Feller, A. H. (1992).
[11] ) Vgl. Kurbel, K. (1993), Kapitel 6.
[12] ) Vgl. Pickel, H. (1988), Seite 41-61; Feller, A. H. (1992), Seite 2-23.
[13] ) Vgl. Seidlmeier, H. (1991), Seite 20-25.
[14] ) Vgl. Ehrlenspiel, K. (1985), Seite 276-278.
[15] ) Vgl. Ehrlenspiel, K. (1985), Seite 284-285.
[16] ) Vgl. Ehrlenspiel, K. (1985), Seite 290-312.
[17] ) Vgl. Ehrlenspiel, K. (1985), Seite 312-320.
[18] ) Vgl. Ehrlenspiel, K. (1985), Seite 230/231.
[19] ) Vgl. Kurbel, K. (1993), Kapitel 6.
[20] ) Vgl. Angerer, G., Bätcher, K., Bars, P. (1993), Kapitel D und E.
[21] ) Vgl. Angerer, G., Bätcher, K., Bars, P. (1993), Seite 63.
[22] ) Vgl. Kraus, M., Heimig, I., Scheer, A.-W. (1995).
[23] ) Vgl. Becker, J., Rosemann, M. (1993), Seite 141.
[24] ) Vgl. Kurbel, K. (1992), Seite 68-70.
[25] ) Vgl. Nauck, D., Klawonn, F., Kruse, R. (1994), Seite 159.
[26] ) Vgl. Forsyth, R. (1989a).
[27] ) Vgl. Kurbel, K. (1992), Seite 70.
[28] ) Vgl. Frawley, W. J., Piatetsky-Shapiro, G., Matheus, C. J. (1992).
[29] ) Vgl. Michalski, R. S. (1993).
[30] ) Vgl. Gennari, J. H., Langley, P., Fisher, D. (1993).
[31] ) Vgl. Hecht, A., Hellendoorn, H., Leufke, A., Storjohann, K. (1994).
[32] ) Vgl. Nauck, D., Klawonn, F., Kruse, R. (1994), Seite 191-202.
[33] ) Vgl. Seraphin, M. (1994), Seite 163 - 174.
[34] ) Vgl. Schneider, B. (1993), Seite 8.
[35] ) Vgl. Rommelfanger, H. (1994), Seite 1-3.
[36] ) Vgl. Zadeh, L. A. (1965).
[37] ) Vgl. z. B. Rommelfanger, H. (1994).
[38] ) Vgl. z. B. Kandel, A. (1992).
[39] ) Vgl. Zimmermann, H.-J. (1993), Kapitel 5.
[40] ) Vgl. Zimmermann, H.-J. (1993), Seite 131-139 bzw. Nietsch, T., Rautenstrauch, C., Rehfeldt, M., Rosemann, M., Turowski, K. (1994).
[41] ) Vgl. Seidlmeier, H. (1991), Seite 95-99.
[42] ) Vgl. Vossen, G., Groß-Hardt, M. (1993), Kapitel 4.
[43] ) Vgl. Vossen, G., Groß-Hardt, M. (1993), Kapitel 5.
[44] ) Vgl. Vossen, G., Groß-Hardt, M. (1993), Kapitel 7.
[45] ) In Anlehnung an Froese, J., Moazzami, M., Rautenstrauch, C., Welter, H. (1994), Seite 2. Eine ähnliche Ansicht findet sich auch bei Kotz, A. M. (1989), Seite 40.
[46] ) Vgl. Vossen, G. (1994), Seite 522-524.
[47] ) Vgl. z.B. Nagl, M. (1990).
[48] ) Vgl. Oracle Corp. (1992), Kapitel 2, Seite 62.
[49] ) Vgl. Kotz, A. M. (1989), Seite 34-36.
[50] ) Vgl. Froese, J., Moazzami, M., Rautenstrauch, C., Welter, H. (1994), Seite 221-230; Oracle Corp. (1992), Kapitel 4, Seite 41; Kotz, A. M. (1989), Seite 42-44; Vossen, G. (1994), Seite 520-522.
[51] ) Vgl. Zimmermann, H.-J. (1993), Seite 30/31 bzw. Nauck, D., Klawonn, F., Kruse, R. (1994), Seite 241/242.
[52] ) Vgl. z. B. Zimmermann, H.-J. (1993), Seite 31/32; Grauel, A. (1995), Seite 205/206
[53] ) Vgl. Zimmermann, H.-J. (1993), Seite 30.
[54] ) Vgl. Michalski, R. S. (1983).
[55] ) Vgl. Michalski, R. S. (1983); Schneider, B. (1992), Seite 45/46.
[56] ) Vgl. Michalski, R. S. (1983).
[57] ) Vgl. Michalski, R. S., Bergadano, F., Matwin, S., Zhang, J. (1993).
[58] ) Vgl. Fensel, D., Klein, J. (1992).
[59] ) Vgl. Michalski, R. S. (1983).
[60] ) Vgl. Kurbel, K. (1990), Seite 35-40.
[61] ) Vgl. Grauel, A. (1995).
[62] ) Vgl. Vossen, G. (1994), Seite 162.
[63] ) Vgl. Allen, B. P. (1994).
[64] ) Vgl. Oracle Corp. (1992), Kapitel 7.
[65] ) Vgl. Oracle Corp. (1992), Kapitel 4, Seite 41-43; Froese, J., Moazzami, M., Rautenstrauch, C., Welter, H. (1994), Seite 221-230.
[66] ) Vgl. Froese, J., Moazzami, M., Rautenstrauch, C., Welter, H. (1994), Seite 216-218.
[67] ) Vgl. Kurbel, K. (1992), Seite 190; Rommelfanger, H. (1994), Seite 165.
[68] ) Vgl. Zimmermann, H.-J. (1993), Seite 47-51.
[69] ) Vgl. Torgo, L. (1993).
[70] ) Vgl. Torgo, L. (1993).
[71] ) Vgl. Fensel, D. (1992).
[72] ) Vgl. Oracle Corp. (1992), Kapitel 7.
[73] ) Vgl. Quinlan, J. R. (1983).
[74] ) Vgl. Weber, R., Zimmermann, H.-J. (1991).
[75] ) Vgl. Zimmermann, H.-J. (1993), Seite 131-139 bzw. Nietsch, T., Rautenstrauch, C., Rehfeldt, M., Rosemann, M., Turowski, K. (1994).
[76] ) Vgl. Zimmermann, H.-J. (1993), Seite 16.
[77] ) Vgl. Ultsch, A., Höffgen, K.-U. (1991), Seite 132.
[78] ) Vgl. Grauel, A. (1995), Seite 33.
[79] ) Vgl. de Korvin, A., Bourgois, B., Kleyle, R. (1994).
[80] ) Vgl. de Korvin, A., Bourgois, B., Kleyle, R. (1994).
[81] ) Vgl. de Korvin, A., Bourgois, B., Kleyle, R. (1994).
[82] ) Vgl. de Korvin, A., Bourgois, B., Kleyle, R. (1994).
[83] ) Vgl. Ammersbach, K. (1992).