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 ${\displaystyle X\;\mapsto \;X''}$ ein Hüllenoperator auf der (endlichen) Merkmalsmenge M. Eine Teilmenge ${\displaystyle P\;\subseteq \;M}$ heißt Pseudohülle genau dann wenn sie die folgenden Bedingungen erfüllt:

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

Implikationen und Stammbasis

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

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

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

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

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

1. Jede Implikation aus ${\displaystyle {\mathcal {L}}}$ gilt im formalen Kontext (Korrektheit).
2. Jede Implikation, die im Kontext gilt, folgt aus ${\displaystyle {\mathcal {L}}}$ (Vollständigkeit).
3. Keine Implikation ${\displaystyle A\rightarrow B\in {\mathcal {L}}}$ folgt aus den übrigen Implikationen, also aus ${\displaystyle {\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 ${\displaystyle (G,\;M,\;I)}$ ist die Menge der Implikationen ${\displaystyle \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 ${\displaystyle 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, die entsprechende Gegenstandsmenge ist leer): 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.

Die Stammbasis^[2] zum nebenstehenden Beispiel ist

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

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

${\displaystyle G^{+}\longleftrightarrow \;T^{+}P^{+}}$

Nur diese beiden Implikationen erhält man als Stammbasis, wenn man die Negation der Merkmale bestanden / nicht bestanden durch die Implikation ${\displaystyle G^{+}\wedge \;G^{-}\longrightarrow \;\bot }$ sowie die Vollständigkeit der Information durch die Klausel ${\displaystyle \top \multimap \;G^{+}\vee G^{-}}$ dem Algorithmus als Startwissen übergibt, analog für die anderen Merkmale P und T.

Verfügt man also über Hintergrundwissen, kann die Merkmalexploration abgekürzt und die Stammbasis verkleinert werden. So kann etwa eine Menge ${\displaystyle {\mathcal {L}}}$ von kumulierten Klauseln ${\displaystyle \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 besteht dann aus einer Menge von Implikationen ${\displaystyle {\mathcal {B}}}$ jeweils mit Prämissen P, die unter dem Hintergrundwissen abgeschlossen sind, also alle Merkmale enthalten, die durch das Hintergrundwissen gefordert sind. Für Implikationen als Hintergrundwissen bedeutet das eine wiederholte Anwendung des wie folgt definierten ${\displaystyle {\mathcal {L}}}$-Operators auf P:

${\displaystyle X^{\mathcal {L}}:=X\cup \bigcup \{B\subseteq M\mid A\subseteq X,A\rightarrow B\in {\mathcal {L}}\}}$

Die gültigen Implikationen des zugrunde liegenden Kontexts können dann aus ${\displaystyle {\mathcal {L}}\cup {\mathcal {B}}}$ gefolgert werden.^[3] Diese Stammbasis bezüglich eines durch das Hintergrundwissen definierten „relativen Testkontexts“ ist allerdings nicht in jedem Fall eindeutig bestimmt.^[4]

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^[5]. Eine Anwendung in der Systembiologie zielt mittels Integration von Wissen und experimentellen Daten auf Prozessregeln für genregulatorische und andere Netzwerke.^[6] 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 eigenen Java-Programm ist möglich.
• Conexp-ng: Erweiterbare Java-Neuimplementierung von Concept Explorer.
• Conexp-clj: Neuimplementierung im Java-basierten Lisp-Dialekt Clojure. Insbesondere für Kommandozeilen-Aufruf und skriptbasierte Programmierung geeignet, mit erweiterten Möglichkeiten wie Luxenburger-Basen, Kontext-Automorphismen (Symmetrien der Merkmale), Fuzzy-FCA oder einer Schnittstelle zum Computeralgebra-System Sage.
• ConImp: Für Linux und DOS/Windows, kommandozeilenbasiert, beschränkt auf formale Kontexte mit 256 Gegenständen, jedoch mit erweiterten Optionen wie Eingabe von Hintergrund- und unvollständigem Wissen. Hintergrundwissen verändert dort – im Unterschied zum oben beschriebenen und in conexp-clj implementierten Ansatz – den Algorithmus nicht, sondern es werden vorgeschlagene Implikationen durch Folgern aus einer Menge von Hintergrund-Implikationen entschieden, nicht durch den Experten.

Literatur

• Bernhard Ganter, Rudolf Wille: Formale Begriffsanalyse; Springer, 1996, ISBN 3-540-60868-0
• Bernhard Ganter, Sergei Obiedkov: Conceptual Exploration; Springer, 2016, ISBN 978-3-662-49290-1

Weblinks

• Dresdener Seite zur Formalen Begriffsanalyse (englisch)
• Dort Vorlesungsfolien (PDF; 2,1 MB) 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. ↑ Bernhard Ganter: Finger Exercises in Formal Concept Analysis (PDF; 2,1 MB); Vorlesungsfolien, Dresden 2006, S. 85–87.
3. ↑ Gerd Stumme, Attribute Exploration with Background Knowledge and Exceptions. In: H.H. Bock u. a., Data Analysis and Information Systems. Springer 1996, S. 457–469. Preprint (PDF; 219 kB)
4. ↑ Bernhard Ganter: Contextual Attribute Logic of Many-Valued Attributes. In Bernhard Ganter, Gerd Stumme, Rudolf Wille (Hrsg.): Formal Concept Analysis. Foundations and Applications; Springer, 2005, ISBN 3-540-27891-5, S. 107. Online-Version
5. ↑ Franz Baader and Barıs Sertkaya: Usability Issues in Description Logic Knowledge Base Completion. In S. Ferre and S. Rudolph (Hrsg.): Formal Concept Analysis: 7th International Conference, ICFCA 2009, LNAI 5548; Springer, Heidelberg 2009, p. 1–21.
6. ↑ Johannes Wollbold: Attribute Exploration of Gene Regulatory Processes (PDF; 4,4 MB). Doktorarbeit, Universität Jena 2011.