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 formaler Kontexte, um Eigenschaften dieser Verbände als Eigenschaften der zugeordneten Kontexte zu studieren. Wegen der englischen Übersetzung Formal Concept Analysis findet man zuweilen im Deutschen auch die eigentlich falsche Bezeichnung Formale Konzeptanalyse.

Die Theorie in ihrer heutigen Form geht zurück auf die Darmstädter Forschungsgruppe um Rudolf Wille, Bernhard Ganter und Peter Burmeister, in der 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. Starken Einfluss auf die Entstehung der Formalen Begriffsanalyse hatten Schriften von Charles S. Peirce und Hartmut von Hentig.

FBA findet in vielfältigen Bereichen praktische Anwendung, wie Data- und Textmining, Wissensmanagement, Semantic Web, Software Engineering, Wirtschaft und Biologie.

Motivation und philosophischer Hintergrund

Im Artikel Restructuring Lattice Theory (1982), der die Formale Begriffsanalyse als Disziplin begründete, wird als Motivation das Unbehagen an der Verbandstheorie und der Reinen Mathematik allgemein genannt: Die oft durch „geistigen Hochleistungssport“ erreichte Produktion theoretischer Resultate sei beeindruckend, die Verknüpfungen zwischen benachbarten Gebieten und sogar Teilen einer Theorie würden jedoch schwächer.

„Die Restrukturierung der Verbandstheorie ist ein Versuch, Verbindungen zu unserer allgemeinen Kultur wieder zu verstärken, indem die Theorie so konkret wie möglich interpretiert und dadurch eine bessere Kommunikation zwischen Verbandstheoretikern und potentiellen Anwendern der Verbandstheorie gefördert wird.“

– Rudolf Wille:

Dieses Ziel geht direkt zurück auf Hartmut von Hentig, der 1972 eine Restrukturierung der Wissenschaften forderte, „um sie besser lernbar, gegenseitig verfügbar und allgemeiner (d.h. jenseits der Fachkompetenz) kritisierbar zu machen.“ Somit zielt auch FBA von ihren Ursprüngen her auf Interdisziplinarität und demokratische Kontrolle von Forschung.

Sie korrigiert den ursprünglichen Ansatz der Verbandstheorie mit der Entstehung der Formalen Logik im 19. Jahrhundert. Während ein Begriff als einstelliges Prädikat auf seinen Umfang reduziert wurde (ähnlich auch in der Modelltheorie), sollte nun durch Berücksichtigung auch des Inhalts die Begriffslehre wieder weniger abstrakt werden. Damit orientiert sich FBA an den Kategorien Extension und Intension der Linguistik und klassischen Begriffslogik. Ihr Begriffsverständnis entspricht auch dem der DIN-Normen 2330 Begriffe und Benennungen, DIN 2331 Begriffssysteme und ihre Darstellung sowie DIN 2342 Begriffe der Terminologielehre.

Klarheit von Begriffen wird im Sinn von Charles S. Peirce's Pragmatischer Maxime dadurch angestrebt, dass beobachtbare, elementare Eigenschaften der subsumierten Gegenstände entfaltet werden. In seiner Spätphilosophie ging Peirce davon aus, dass logisches Denken auf das Erfassen von Wirklichkeit zielt, durch den Dreischritt Begriff, Urteil und Schluss. Mathematik abstrahiert logisches Denken, entwickelt Formen möglicher Realität und kann daher rationale Kommunikation unterstützen. Rudolf Wille definiert vor diesem Hintergrund:

„Ziel und Bedeutung Formaler Begriffsanalyse als mathematische Theorie von Begriffen und Begriffshierarchien ist es, die rationale Kommunikation von Menschen zu unterstützen, indem sie mathematisch geeignete Begriffsstrukturen entwickelt, die logisch aktiviert werden können.“

– Rudolf Wille:

Mathematische Grundlagen

Das Hauptziel der Formalen Begriffsanalyse ist die Darstellung von vollständigen Verbänden mittels formaler Kontexte. Darüber hinaus erlaubt sie aber auch umgekehrt die Untersuchung von Daten in Form formaler Kontexte mit Mitteln der Ordnungstheorie. 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 bezeichnet, $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\subseteq G$ eine Menge von Gegenständen eines formalen Kontextes $\mathbb {K} =(G,M,I)$, 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 definiert wird für eine Menge $B\subseteq M$ von Merkmalen von $\mathbb {K} =(G,M,I)$ die Menge

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

aller Gegenstände, die alle 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, so lassen sich formale Begriffe - bei geeigneter Ordnung der Gegenstände und Merkmale - als maximale, vollständig gefüllte 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 Halbordnung 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 (Liniendiagramme) dargestellt werden und entfalten so die Daten in ihrer Struktur und ihren Zusammenhängen. Die Gegenstände haben dabei alle (durch Kanten verbundene) darüber stehenden Merkmale; in nebenstehendem Beispiel ist 4 gerade, zusammengesetzt und quadratisch.

Mathematisch genauer kann zunächst die vereinfachte Beschriftung von Begriffsverbänden begründet werden. 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})$.

Implikationentheorie Formaler Kontexte

Für einen formalen Kontext $\mathbb {K} =(G,M,I)$ kann seine Implikationentheorie untersucht werden. Dabei ist eine Implikation von $\mathbb {K}$ einfach ein Paar $(A,B)$ mit $A,B\subseteq M$, was meist mit $A\to B$ geschrieben wird. Man sagt, dass $A\to B$ in $\mathbb {K}$ gilt, wenn jeder Gegenstand, der alle Merkmale aus $A$ besitzt, auch alle Merkmale aus $B$ besitzt, wenn also $A'\subseteq B'$ gilt. Diese Bedingung ist äquivalent dazu, dass $B\subseteq A''$ gilt.

Ist ${\mathcal {L}}$ eine Menge von Implikationen von $\mathbb {K}$ und ist $A\subseteq M$, so bezeichnet man mit ${\mathcal {L}}(A)$ die kleinste Menge, die $A$ enthält und abgeschlossen ist unter ${\mathcal {L}}$. Dabei heißt eine Menge $X\subseteq M$ abgeschlossen unter ${\mathcal {L}}$, falls für alle Implikationen $(A\to B)\in {\mathcal {L}}$ stets $A\not \subseteq X$ oder $B\subseteq X$ gilt, wenn also $A\subseteq X$ stets $B\subseteq X$ impliziert. Man sieht dann, dass die Abbildung $A\to {\mathcal {L}}(A)$ ein Hüllenoperator auf der Potenzmenge von $M$ ist.

Ist $A\to B$ eine Implikation von $\mathbb {K}$, so folgt $A\to B$ aus ${\mathcal {L}}$, falls $B\subseteq {\mathcal {L}}(A)$ gilt. Dies ist äquivalent dazu, dass in jedem formalen Kontext, in dem alle Implikationen aus ${\mathcal {L}}$ gelten, auch stets die Implikation $A\to B$ gilt.

Eine Basis für $\mathbb {K}$ ist dann eine Menge ${\mathcal {L}}$ von gültigen Implikationen von $\mathbb {K}$, so dass jede (semantisch) gültige Implikation aus $\mathbb {K}$ bereits aus ${\mathcal {L}}$ folgt, durch Anwendung geeigneter syntaktischer Inferenzregeln wie der Armstrong-Regeln. Die in diesem neuen Sinn abgeschlossene Menge aller Implikationen von $\mathbb {K}$ ist eine Theorie, da sie außerdem laut Konstruktion zum Beispiel bezüglich des zugrunde liegenden Kontexts erfüllbar ist.

Die Basis heißt irredundant, falls sie $\subseteq$-minimal mit dieser Eigenschaft ist. Ein Beispiel für eine irredundante Basis ist die kanonische Basis (siehe auch Merkmalexploration), die darüber hinaus die Eigenschaft hat, auch minimal bezüglich der Größe der Basis zu sein.

Es gilt, dass eine Menge ${\mathcal {L}}$ von Implikationen genau dann eine Basis eines Kontextes $\mathbb {K}$ ist, wenn die Menge der unter ${\mathcal {L}}$ abgeschlossenen Mengen genau die der Inhalte von $\mathbb {K}$ ist.

Merkmalexploration

→ Hauptartikel: Merkmalexploration

Es ist möglich, die Implikationentheorie eines bestimmten Themengebietes mit Hilfe eines formalen Kontextes darzustellen. Dies bedeutet insbesondere, dass man dies mit Hilfe einer ausreichenden Menge von Beispielen tun kann, die dann die Gegenstände des formalen Kontextes werden. Theoretisch kann solch eine Menge von Beispielen von einem menschlichen Experten oder auch einer Maschine angegeben werden.

Dabei entsteht allerdings das Problem, dass weder von vornherein garantiert ist, dass eine ausreichende Menge von Beispielen angegeben ist, noch, ob nicht einige generierte Beispiele redundant sind, da bereits gegebene Beispiele ausreichen. Unter den Gesichtspunkten, dass die Generierung guter Beispiele schwierig ist, die Befragung von Experten oder gar neue Experimente teuer sind, und Literatursuche oder Algorithmen aufwendig werden können, ist dies ein ernstzunehmendes Problem.

Abhilfe kann hier der Algorithmus der Merkmalexploration schaffen. Ausgehend von einer bereits bekannten Menge von Implikationen und einer bereits bekannten Menge von Beispielen aus dem Themengebiet schlägt der Algorithmus Implikationen vor, die dann von einem Experten (menschlich oder nicht) akzeptiert oder zurückgewiesen werden können. Dabei soll eine Implikation genau dann akzeptiert werden, wenn diese im besagten Themengebiet gültig ist. Wird eine Implikation zurückgewiesen, so muss der Experte ein Gegenbeispiel erzeugen, das dann von einem Experten (menschlich oder nicht) akzeptiert oder zurückgewiesen werden kann. Dabei soll eine Implikation genau dann akzeptiert werden, wenn diese im besagten Themengebiet gültig ist. Durch ein akzeptiertes Gegenbeispiel, wird die Implikation widerlegt und somit eine kleinstmögliche Menge von akzeptierten Implikationen generiert, die am Ende das Themengebiet vollständig beschreibt. Darüber hinaus wird auch die Menge von Beispielen vervollständigt.

Anwendungen

Die Formale Begriffsanalyse lässt sich als qualitative Methode zur Datenanalyse einsetzen, etwa in Data- und Textmining, Wissensmanagement, Semantic Web, Softwareentwicklung, Wirtschaft oder Biologie. Eine direkte Anwendung ist es, die ursprünglichen Daten anders zu strukturieren und zu visualisieren.

Literatur

• Bernhard Ganter, Rudolf Wille: Formale Begriffsanalyse. Springer, 1996, ISBN 3-540-60868-0. 
• Bernhard Ganter, Gerd Stumme, Rudolf Wille (Hrsg.): Formal Concept Analysis. Foundations and Applications. Springer, 2005, ISBN 3-540-27891-5 (Online-Vorschau). 
• R. Missaoui, Jürg Schmid: Formal Concept Analysis. Springer, 2006, ISBN 3-540-32203-5. 
• Raoul Medina, Sergei Obiedkov (Hrsg.): Formal Concept Analysis. 6th International Conference, ICFCA 2008, Montreal, Canada, February 25-28, 2008. Springer, Heidelberg 2008, ISBN 978-3-540-78136-3 (Online-Version – LNCS/LNAI 4933). 
• Bernhard Ganter: Diskrete Mathematik: Geordnete Mengen. Springer Spektrum, 2013, ISBN 978-3-642-37499-9, S. 1–192. 

Weblinks

• Formal Concept Analysis Seite von Uta Priss, mit Links zu weiteren Programmen
• The Dresden Formal Concept Analysis Page von Bernhard Ganter
• Literatur und Weblinks nicht nur zu FBA (social bookmarking)