Formale Begriffsanalyse

Die Formale Begriffsanalyse (FBA), englisch Formal Concept Analysis (FCA), ist eine mathematische Theorie, mit der Daten auf Zusammenhänge und Struktur analysiert werden können. Die Daten werden dabei auf eine Weise gegliedert, die dem menschlichen Denken in Begriffen und deren Ordnung entgegenkommen soll. Die FBA gründet sich auf die mathematische Ordnungstheorie.

Einführung

Die Formale Begriffsanalyse untersucht Zusammenhänge in Datensammlungen und macht Strukturen in den Daten deutlich. Dabei werden Gegenstände (z.B. beschrieben durch Datensätze) aufgrund ihrer Merkmale zu Gruppen zusammengefasst, die in diesen Merkmalen (Dateninhalten) übereinstimmen. Innerhalb solcher Gruppen wird dann aufgrund weiterer Merkmale weiter unterteilt. Daraus ergibt sich eine hierarchische Struktur, die in Form eines netzartigen Ordnungsdiagramms veranschaulicht werden kann. Ziel ist eine mathematisch fundierte Methodik, die dem begrifflichen Denken des Menschen entgegen kommt.

Umfang, Inhalt und Begriff

Jede durch gemeinsame Merkmale bestimmte Gruppe von Gegenständen wird als ein Begriffsumfang gedeutet, die zugehörige Menge aller gemeinsamen Merkmale als Begriffsinhalt. Beide Teile zusammen, also jeweils ein Umfang und der zugehörige Inhalt, bilden einen formalen Begriff, wobei der Zusatz „formal“ darauf hinweist, dass es sich um eine mathematische Konstruktion handelt. Ein formaler Begriff ist also immer sowohl durch seinen Umfang als auch durch seinen Inhalt eindeutig bestimmt.

Ober- und Unterbegriff

Ein formaler Begriff ist ein Unterbegriff eines zweiten formalen Begriffs, wenn sein Umfang ganz im Umfang des zweiten enthalten ist. Dann ist der Inhalt des Oberbegriffs (also des Begriffs mit dem größeren Umfang) im Inhalt des Unterbegriffs enthalten.

Bezug zur mathematischen Verbandstheorie

Diese Unterbegriff-Oberbegriff-Ordnung der formalen Begriffe erweist sich in aller Regel als eine netzartig verzweigte Ordnungsstruktur, sie ist also gewöhnlich nicht baumartig oder gar linear. Es kann aber bewiesen werden, dass diese Ordnungen besondere und gut untersuchte Eigenschaften haben: Es handelt sich dabei stets um sogenannte vollständige Verbände (engl.: complete lattices).

Ein Begriff kann so nicht nur einen Oberbegriff haben. Vielmehr sind mehrere Oberbegriffe für einen Begriff die Regel, auch solche, die miteinander nicht in einer Oberbegriff-Beziehung stehen. Z.B. vereinigt der Begriff Greifvogel die Merkmale sowohl von seinem Oberbegriff Vogel als auch die eines zweiten Oberbegriffs Beutegreifer.

Entstehung

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. Einfluss auf die Entstehung der Formalen Begriffsanalyse hatten Schriften von Charles S. Peirce und Hartmut von Hentig.

Anwendungsgebiete

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: Restructuring lattice theory: An approach based on hierarchies of concepts

Dieses Ziel bezieht sich 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.

Während ein Begriff in der Formalen Logik als einstelliges Prädikat auf seinen Umfang reduziert wird, macht die FBA durch Berücksichtigung auch des Begriffsinhalts die Begriffslehre wieder weniger abstrakt. Damit orientiert sich die FBA an den Kategorien Extension und Intension der Linguistik und klassischen Begriffslogik.

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: Formal Concept Analysis as Mathematical Theory of Concepts and Concept Hierarchies

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.

Anwendungserfahrungen mit der Formalen Begriffsanalyse

Die Formale Begriffsanalyse lässt sich als qualitative Methode zur Datenanalyse einsetzen. Seit den frühen Anfängen von FBA Anfang der 1980er hat die Forschungsgruppe FBA an der TU-Darmstadt Erfahrungen aus mehr als 200 Projekten gesammelt, in denen die FBA angewandt wurde (Stand 2005). Darunter aus den Bereichen: Medizin und Zellbiologie, Genetik, Ökologie, Softwaretechnik, Ontologie (Informatik), Informations- und Bibliothekswissenschaften, Büroorganisation, Recht, Sprachwissenschaft, Politikwissenschaften

Viele weitere Anwendungsbeispiele sind z.B. beschrieben in: Formal Concept Analysis. Foundations and Applications, den Konferenzbänden zu regelmäßig stattfindenden Konferenzen, wie: International Conference on Formal Concept Analysis (ICFCA), Concept Lattices and their Applications (CLA) oder International Conference on Conceptual Structures (ICCS)

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)