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 $A$ wird dann Umfang und die Menge $B$ Inhalt des Begriffes $(A,B)$ genannt. Die Menge aller Begriffe wird mit ${\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 $(A,B),(C,D)\in {\mathfrak {B}}(\mathbb {K} )$, so lässt sich mit

$(A,B)\leq (C,D)\,\Leftrightarrow \,A\subseteq C$

eine Ordung auf ${\mathfrak {B}}(\mathbb {K} )$ definieren. Diese Ordnung macht dann die Struktur $({\mathfrak {B}}(\mathbb {K} ),\leq )$ 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 $g\in G$ die Menge aller Begriffe, die $g$ in ihrem Umfang haben, so hat diese Menge einen Hauptfilter im Begriffsverband. Daher wird nur unterhalb des kleinsten Begriffs, der $g$ im Umfang enthält, der Gegenstand $g$ notiert. Dual dazu wird oberhalb des größten Begriffs, der ein gegebenes Merkmal $m\in M$ im Inhalt besitzt, das Merkmal $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 $\mathbb {K} =(G,M,I)$ ein formaler Kontext und ${\underline {\mathfrak {B}}}(\mathbb {K} )$ sein Begriffsverband. Man kann für Gegenstände $g\in G$ und Merkmale $m\in M$ dann die Begriffe

$\gamma (g)=(\{\,g\,\}'',\{\,g\,\}'),$

$\mu (m)=(\{\,m\,\}',\{\,m\,\}'')$

betrachten. Es wird $\gamma (g)$ der Gegenstandsbegriff von $g$ und $\mu (m)$ der Merkmalsbegriff von $m$ genannt. Weiterhin gilt

$g{\mathrel {I}}m\iff \gamma (g)\leq \mu (m)$

Ist nun ${\underline {L}}=(L,\leq _{L})$ ein vollständiger Verband, so ist ${\underline {L}}$ genau dann isomorph zu ${\underline {\mathfrak {B}}}(\mathbb {K} )$, wenn es Abbildungen $\gamma _{\underline {L}}\colon G\to L,\mu _{\underline {L}}\colon M\to L$ gibt derart, dass

$g{\mathrel {I}}m\iff \gamma _{\underline {L}}(g)\leq \mu _{\underline {L}}(m)$

gilt. Insbesondere ist ${\underline {L}}$ isomorph zu ${\underline {\mathfrak {B}}}(L,L,\leq _{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