Benutzer:Dborchmann/Formale Begriffsanalyse

Formale Begriffsanalyse (FBA) ist ein Teil der mathematischen Ordnungstheorie. Ihre ursprüngliche Motivation ist die konkrete Darstellung vollständiger Verbände und deren Eigenschaften mittels (einwertiger) formaler Kontexte. Diese Datentabellen repräsentieren binäre Relationen zwischen Gegenständen und Merkmalen. Prinzipiell können auch beliebige Tabellen einer relationalen Datenbank als mehrwertige Kontexte aufgefasst und mittels sogenannter Skalierung in einwertige Kontexte übersetzt werden.

Die Theorie in ihrer heutigen Form geht zurück auf die Darmstädter Forschungsgruppe um Rudolf Wille, Bernhard Ganter und Peter Burmeister, in welcher Anfang der 1980er Jahre die Formale Begriffsanalyse entstand. Die mathematischen Grundlagen wurden jedoch bereits von Garrett Birkhoff in den 1930er Jahren im Rahmen der allgemeinen Verbandstheorie geschaffen. Vor den Arbeiten der Darmstädter Gruppe gab es bereits Ansätze in verschiedenen französischen Gruppen. Philosophische Fundierungen der Formalen Begriffsanalyse berufen sich insbesondere auf Charles S. Peirce und Hartmut von Hentig.

Formale Begriffsanalyse findet in vielfältigen Bereichen praktische Anwendung, wie Data- und Textmining, Wissensmanagement, Semantic Web, Softwareentwicklung, Wirtschaft oder Biologie.

Mathematische Grundlagen

Das Hauptziel der Formalen Begriffsanalyse ist die Darstellung von vollständigen Verbänden mittels formaler Kontexte einerseits, aber auch die Untersuchung von Daten in Form formaler Kontexte mit Mitteln der Ordnungstheorie andererseits. Die dafür grundlegenden Definitionen sollen in diesem Abschnitt diskutiert werden.

Formale Kontexte und Formale Begriffe

Gegeben seien zwei Mengen $G,\,M$ und eine Relation $I\subseteq G\times M$. Das Tripel $\mathbb {K} =(G,M,I)$ wird dann als formaler Kontext bezeichet, $G$ als seine Gegenstandsmenge und $M$ als seine Merkmalsmenge; für einen Gegenstand $g\in G$ und ein Merkmal $m\in M$ bedeutet $(g,m)\in I$ „der Gegenstand $g$ hat das Merkmal $m$“. Oft wird auch $g{\mathrel {I}}m$ statt $(g,m)\in I$ geschrieben. Die Menge $I$ wird als Inzidenzrelation des formalen Kontextes bezeichnet.

Sind die Mengen $G$ und $M$ endlich, so lassen sich formale Kontexte gut in Form von „Kreuztabellen“ darstellen. Man beachte dabei, dass die Gegenstände und Merkmale in dieser Darstellung willkürlich geordnet werden können. Diese Ordnung ist dann aber nicht Teil des formalen Kontextes, sondern nur seiner Darstellung.

Ein formaler Kontext zu Eigenschaften der Zahlen 1-10.

Ist $A$ Menge von Gegenständen eines formalen Kontextes $\mathbb {K}$, so bezeichnet man mit

$A':=\{\,m\in M\mid \forall g\in A:g{\mathrel {I}}m\,\}$

die Menge der gemeinsamen Merkmale der Gegenstände in $A$. Entsprechend definitiert wird für eine Menge $B$ von Merkmalen von $\mathbb {K}$ die Menge

$B':=\{\,g\in G\mid \forall m\in B:g{\mathrel {I}}m\,\}$

aller Gegenstände, die die Merkmale aus $B$ besitzen. Die Menge $A'$ und $B'$ werden als die Ableitungen der entsprechenden Mengen $A$ und $B$ bezeichnet und die Funktionen, welche beide mit $(\cdot )'$ benannt sind, Ableitungsoperatoren von $\mathbb {K}$ genannt.

Die Ableitungsoperatoren erfüllen eine Reihe von sehr grundlegenden Eigenschaften. Sind $A,\,A_{1},\,A_{2}$ Mengen von Gegenständen und $B,\,B_{1},\,B_{2}$ Mengen von Merkmalen, so gilt

• $A_{1}\subseteq A_{2}\,\implies \,A_{2}'\subseteq A_{1}'$ und dual $B_{1}\subseteq B_{2}\,\implies \,B_{2}'\subseteq B_{1}'$,
• $A\subseteq A''$ und dual $B\subseteq B''$,
• $A'=A'''$ und $B'=B'''$,
• $A\subseteq B'\iff A'\supseteq B$.

Tatsächlich definieren damit die Ableitungsoperatoren eine antitone Galoisverbindung zwischen den Potenzmengenverbänden der Gegenstandsmenge und der Merkmalmenge. Umgekehrt lässt sich jede solche Galoisverbindung zwischen Potenzmengenverbänden als Paar von Ableitungsoperatoren eines formalen Kontextes darstellen.

Zu einem formalen Kontext $\mathbb {K}$ heißt nun ein Paar $(A,B)$ ein formaler Begriff von $\mathbb {K}$, falls

• $A$ eine Menge von Gegenständen von $\mathbb {K}$ ist,
• $B$ eine Menge von Merkmalen von $\mathbb {K}$ ist,
• $A'=B$ und
• $B'=A$ gilt.

Die Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} wird dann Umfang und die Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B} Inhalt des Begriffes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (A,B)} genannt. Die Menge aller Begriffe wird mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{B}(\mathbb{K})} bezeichnet. Stellt man formale Kontexte als Kreuztabellen dar und wählt dabei eine geeignete Ordnung auf den Gegenständen und Merkmalen, so lassen sich formale Begriffe als maximale Rechtecke in dieser Kreuztabelle verstehen.

Sind nun Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (A, B), (C, D) \in \mathfrak{B}(\mathbb{K})} , so lässt sich mit

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (A, B) \le (C, D)\, \Leftrightarrow\, A \subseteq C}

eine Ordung auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{B}(\mathbb{K})} definieren. Diese Ordnung macht dann die Struktur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\mathfrak{B}(\mathbb{K}), \le)} zu einem vollständigen Verband. Tatsächlich ist umgekehrt nach dem Hauptsatz der Formalen Begriffsanalyse jeder vollständige Verband ordnungsisomorph zu einem Begriffsverband.

Begriffsverband zum obigen Zahlenkontext.

Begriffsverbände können als Ordnungsdiagramme dargestellt werden. Die Beschriftung von Begriffsverbänden erlaubt dabei eine vereinfachte Beschriftung. Betrachtet man für einen Gegenstand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g \in G} die Menge aller Begriffe, die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g} in ihrem Umfang haben, so hat diese Menge einen Hauptfilter im Begriffsverband. Daher wird nur unterhalb des kleinsten Begriffs, der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g} im Umfang enthält, der Gegenstand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g} notiert. Dual dazu wird oberhalb des größten Begriffs, der ein gegebenes Merkmal Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m \in M} im Inhalt besitzt, das Merkmal Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} notiert. Ein Begriff im Ordnungsdiagramm hat also genau dann einen Gegenstand in seinem Umfang, wenn er oberhalb des Begriffes liegt, der mit dem Gegenstand beschriftet ist. Entsprechend hat ein Begriff im Ordnungsdiagramm ein Merkmal in seinem Inhalt, wenn er unterhalb des Begriffes liegt, der mit dem Merkmal beschriftet ist.

Hauptsatz der Formalen Begriffsanalyse

Es sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{K} = (G, M, I)} ein formaler Kontext und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \underline{\mathfrak{B}}(\mathbb{K})} sein Begriffsverband. Man kann für Gegenstände Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g \in G} und Merkmale Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m \in M} dann die Begriffe

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \gamma(g) = (\{\,g\,\}'', \{\,g\,\}'),}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mu(m) = (\{\,m\,\}', \{\,m\,\}'')}

betrachten. Es wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \gamma(g)} der Gegenstandsbegriff von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mu(m)} der Merkmalsbegriff von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} genannt. Weiterhin gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g\mathrel{I}m \iff \gamma(g) \le \mu(m)}

Ist nun Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \underline{L} = (L, \le_L)} ein vollständiger Verband, so ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \underline{L}} genau dann isomorph zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \underline{\mathfrak{B}}(\mathbb{K})} , wenn es Abbildungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \gamma_{\underline{L}}\colon G \to L, \mu_{\underline{L}}\colon M \to L} gibt derart, dass

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g\mathrel{I}m \iff \gamma_{\underline{L}}(g) \le \mu_{\underline{L}}(m)}

gilt. Insbesondere ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \underline{L}} isomorph zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \underline{\mathfrak{B}}(L, L, \le_L)} .

Beispiele

(aus dem Buch, zitieren!)

• Partitionenverband
• Tamari-Verband

Eigenschaften Vollständiger Verbände als Eigenschaften zugehöriger Kontexte

(alles nur kurz erwähnen, eventuell auf andere Seiten verweisen (auch wenn es die noch nicht gibt)).

• Vollständige Kongruenzen
• Pfeilrelationen
• Verbandsoperationen als Kontextoperationen (Tensorprodukte, subdirekte Produkte, ...)
• Verbandssymmetrien als Kontextsymmetrien

Implikationentheorie Formaler Kontexte

Implikationen und die Kanonische Basis

Definition Implikation

Definition Pseudoinhalt

Definition Kanonische Basis

Auch noch erwähnen
* Association Rules
* Regeln
* Partielle Implikationen
* funktionale und ordinale Abhängigkeiten in mehrwertigen Kontexten

Merkmalexploration

→ Hauptartikel: Merkmalexploration

Verbindung zu anderen Formalismen

• Beschreibungslogiken (Rudolph, Sertkaya, Distel), oder auch allgemein Theorien zur Wissenrepräsentation
• Theorie relationaler Datenbanken
• Philosophie?
• Systembiologie

Varianten

• Relational Concept Analysis
• Fuzzy stuff

Software

• ConExp
• Lattice Miner
• Galicia
• conexp-clj (shameless plug ;)

Weblinks

• Formal Concept Analysis Seite von Uta Priss, mit Links zu weiteren Programmen
• The Dresden Formal Concept Analysis Page von Bernhard Ganter