Merkmalexploration

Die Merkmalexploration ist ein interaktiver Algorithmus der Formalen Begriffsanalyse zum Finden von Implikationen zwischen Merkmalen von Daten. Der Algorithmus berechnet eine vollständige und minimale Stammbasis, aus der alle im untersuchten Gebiet geltenden Implikationen gefolgert werden können.

Idee

Ziel der Merkmalexploration ist es, alle möglichen Merkmalkombinationen in einem speziellen Sachbereich zu beschreiben, d.h. die Merkmallogik zu finden. Dieser Sachbereich ist durch einen formalen Kontext gegeben, der grundlegenden Datenstruktur der Formalen Begriffsanalyse. In dieser Kreuztabelle sind Beziehungen zwischen Gegenständen und Merkmalen verzeichnet. Mit Hilfe von Implikationen - in einer Erweiterung auch Klauseln - werden Abhängigkeiten und Zusammenhänge seitens der Merkmale erklärt.

Die Hauptaufgabe ist es eine Stammbasis zu bestimmen. Dabei geht man von einer Sammlung von Beispielen aus, die in einem Teilkontext gegeben sind. Der Algorithmus schlägt in einer eindeutig bestimmten Reihenfolge einem Experten (oder einem unterstützenden Programm) im Teilkontext geltende Implikationen vor. Akzeptiert der Experte diese, werden sie in die Stammbasis aufgenommen. Im anderen Fall muss der Experte ein Gegenbeispiel liefern, d.h. eine neue Zeile des Kontexts. So können selbst unendliche Mengen von Objekten (bei endlicher Merkmalmenge) untersucht werden.

Es ist auch möglich, für einen gegebenen Datensatz automatisch die Stammbasis zu berechnen; dann werden alle vorgeschlagenen Implikationen akzeptiert.

Mathematische Grundlagen

Pseudohüllen

Sei $X \;\mapsto \;X''$ ein Hüllenoperator auf der (endlichen) Merkmalsmenge M. Eine Teilmenge $P \;\subseteq \; M$ heißt Pseudohülle genau dann wenn sie die folgenden Bedingungen erfüllt:

1. $P \;\neq \;P''$,
2. P enthält die Hülle Q'' jeder Pseudohülle Q, die echte Teilmenge von P ist.

Implikationen und Stammbasis

Eine Implikation auf einer Menge M ist ein Paar von Teilmengen von M. Notation: $A \;\rightarrow \; B$.

Eine Teilmenge $T \; \subseteq \; M$ respektiert eine Implikation $A \;\rightarrow \; B$, wenn $A \;\not\subseteq \; T$ oder $B \;\subseteq \; T$ gilt.

$A \;\rightarrow \;B$ gilt in einem formalen Kontext $(G,\;M,\;I)$, wenn jeder Gegenstandsinhalt g' (also jede Zeile des Kontexts) die Implikation respektiert.

Eine Implikation $A \; \rightarrow \; B$ folgt aus einer Menge $\mathcal{L}$ von Implikationen per Definition genau dann, wenn $A \; \rightarrow \; B$ in jedem formalen Kontext gilt, in dem auch jede Implikation aus $\mathcal{L}$ gültig ist.

Betrachtet man die Menge aller Implikationen, die auf einem Kontext gelten, stellt sich die Frage ob es eine Teilmenge $\mathcal{L}$ gibt, die alle diese Implikationen repräsentiert. Eine solche Basis muss folgende Bedingungen erfüllen:

1. Jede Implikation aus $\mathcal{L}$ gilt im formalen Kontext (Korrektheit).
2. Jede Implikation, die im Kontext gilt, folgt aus $\mathcal{L}$ (Vollständigkeit).
3. Keine Implikation $A \rightarrow B \in \mathcal{L}$ folgt aus den übrigen Implikationen, also aus $\mathcal{L} \setminus \{A \rightarrow B\}$ (Irredundanz).

Duquenne und Guigues haben gezeigt, dass für endliche Merkmalmengen eine solche Basis existiert.^[1] Sie ist sogar eindeutig bestimmbar und von minimaler Kardinalität unter allen möglichen Implikationenbasen. Hierfür gibt es verschiedene Bezeichnungen: Stammbasis, kanonische Basis oder auch D-G-Basis.

Die Stammbasis eines formalen Kontextes $(G,\;M,\;I)$ ist die Menge der Implikationen $\left\{ P \mapsto P'' \mid P \text{ ist Pseudoinhalt von } (G,M,I)\right\}$.

Beispiel

Formaler Kontext (unvollständig) zur Lage zweier Quadrate in der Ebene.

Begriffsverband nach Abschluss der Merkmalexploration.

• Der Ausgangspunkt ist ein meist unvollständiger oder auch leerer Teilkontext.
• Der Algorithmus schlägt im Teilkontext geltende Implikationen $P\; \longrightarrow \; P''$ vor. Der Experte kann sie akzeptieren oder ein Gegenbeispiel angeben:

1. ce → pa, cv, cs: akzeptiert
2. cs → pa: akzeptiert
3. pa, cv, cs → ce: akzeptiert
4. ov, cv → pa, cs, ce: Gegenbeispiel - neuer Gegenstand mit Merkmalen ov und cv
5. ov, pa, cs → cv, ce: Gegenbeispiel - neuer Gegenstand mit Merkmalen ov, pa und cs
6. ov, pa, cv → cs, ce: akzeptiert
7. di, cv → alle Merkmale (widersprüchliche Prämisse): akzeptiert
8. di, pa, cs → alle Merkmale: akzeptiert
9. di, ov → alle Merkmale: akzeptiert

• Die vom Experten akzeptierten Implikationen bilden die Stammbasis.
• Die Begriffsinhalte des erweiterten Kontexts und damit der Begriffsverband sind durch diese eindeutig bestimmt.

Exploration mit Hintergrundwissen

Formaler Kontext zum Bestehen einer Führerscheinprüfung.

Verfügt man über Hintergrundwissen, so kann die Merkmalexploration abgekürzt und die Stammbasis verkleinert werden. So können etwa kumulierte Klauseln $\bigwedge A \rightarrow \bigvee \bigwedge_{i\in I} B_i,\; A,\; B_i \; \in \; M$ verwendet werden, die ausdrucksstärker als Implikationen sind.

Die Stammbasis zum nebenstehenden Beispiel ist

1. $P^-\longrightarrow \; G^-$
2. $T^-\longrightarrow \; G^-$
3. $G^- P^+ \longrightarrow \; T^-$
4. $G^- T^- \longrightarrow \;P^-$
5. $T^+ G^+ \longrightarrow \;G^+$
6. $G^+ \longrightarrow \;T^+ P^+$
7. $G^- T^- P^+ P^- \longrightarrow \; \bot-$
8. $G^- T^- T^+ P^- \longrightarrow \;\bot-$

Dies ist allerdings eine etwas komplizierte Form, die einfache Äquivalenz auszudrücken:

$G^+ \longleftrightarrow \; T^+ P^+$

Diese beiden Implikationen erhält man als Stammbasis, wenn man die Negation der Merkmale bestanden / nicht bestanden etwa durch die Implikation $G^+ \wedge \; G^-\longrightarrow \; \bot$ sowie die Vollständigkeit der Information durch die Klausel $\top \multimap \;G^+ \vee G^-$ dem Algorithmus als Startwissen übergibt.

Anwendungsgebiete

Mit Hilfe der Merkmalexploration lassen sich Datensätze auf Vollständigkeit überprüfen, Funktionale Abhängigkeiten sowie Assoziationsregeln finden und in kompakter Form darstellen, oder in Beschreibungslogiken ausgedrückte Wissensbasen vervollständigen^[2]. Eine neue Anwendung in der Systembiologie zielt mittels Integration von Wissen und experimentellen Daten auf Prozessregeln für genregulatorische und andere Netzwerke.^[3] In der Mathematik dient die Merkmalexploration dem Strukturieren von Beweisen.

Software

• Concept Explorer: Einfach zu bedienendes, grafisches Java-Programm mit den wichtigsten Funktionen, einschließlich Erzeugen eines Begriffsverbands. Die Eingabe von Hintergrund-Implikationen beim Aufruf aus einem eigenem Java-Programm ist möglich.
• ConImp: Für Linux und DOS/Windows, kommandozeilenbasiert, beschränkt auf formale Kontexte mit 256 Gegenständen, jedoch mit erweiterten Optionen wie Eingabe von Hintergrundwissen.

Literatur

• Bernhard Ganter, Rudolf Wille: Formale Begriffsanalyse; Springer, 1996, ISBN 3-540-60868-0
• Bernhard Ganter: Begriffe und Implikationen. In Gerd Stumme, Rudolf Wille: Begriffliche Wissensverarbeitung: Methoden und Anwendungen. Springer, 2000, ISBN 9783540663911. Online-Version
• Bernhard Ganter: Contextual Attribute Logic of Many-Valued Attributes. In Bernhard Ganter, Gerd Stumme, Rudolf Wille (Hg.): Formal Concept Analysis. Foundations and Applications; Springer, 2005, ISBN 3-540-27891-5, S. 101-113. Online-Version

Weblinks

• Dresdener Seite zur Formalen Begriffsanalyse (englisch)
• Dort Vorlesungsfolien als ausführliche Einführung zu FCA und Merkmalexploration.

Einzelnachweise

1. ↑ Bernhard Ganter, Rudolf Wille: Formale Begriffsanalyse; Springer, 1996, ISBN 3-540-60868-0, Theorem 8, S. 85
2. ↑ Franz Baader and Barıs Sertkaya: Usability Issues in Description Logic Knowledge Base Completion. In S. Ferre and S. Rudolph (Eds.): Formal Concept Analysis: 7th International Conference, ICFCA 2009, LNAI 5548; Springer, Heidelberg 2009, p. 1–21.
3. ↑ Wollbold J, Guthke R, Ganter B: Constructing a Knowledge Base for Gene Regulatory Dynamics by Formal Concept Analysis Methods. In Horimoto K et al. (Hg.): Algebraic Biology: Third International Conference, AB 2008, Castle of Hagenberg, Austria, July 31-August 2, Lecture Notes in Computer Science. Volume 5147. Springer, Heidelberg 2008, S. 230-244. arxiv.org