Formale Begriffsanalyse

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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.

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.

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.[1]

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.

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[Bearbeiten]

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[2]

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.“[3] Somit zielt auch FBA von ihren Ursprüngen her auf Interdisziplinarität und demokratische Kontrolle von Forschung.[4]

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.[2] 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.[5]

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.[4] 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[6]

Mathematische Grundlagen[Bearbeiten]

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[Bearbeiten]

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[7] 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[7] 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) \le (C, D)\, \Leftrightarrow\, A \subseteq C

eine Halbordnung auf \mathfrak{B}(\mathbb{K}) definieren. Diese Ordnung macht dann die Struktur (\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 (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[Bearbeiten]

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) \le \mu(m)

Ist nun \underline{L} = (L, \le_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) \le \mu_{\underline{L}}(m)

gilt. Insbesondere ist \underline{L} isomorph zu \underline{\mathfrak{B}}(L, L, \le_L).

Implikationentheorie Formaler Kontexte[Bearbeiten]

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[8]. 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[Bearbeiten]

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[Bearbeiten]

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

Literatur[Bearbeiten]

  •  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 (LNCS/LNAI 4933, Online-Version).
  •  Bernhard Ganter: Diskrete Mathematik: Geordnete Mengen. Springer Spektrum, 2013, ISBN 978-3-642-37499-9, S. 1-192.

Weblinks[Bearbeiten]

Einzelnachweise und Anmerkungen[Bearbeiten]

  1. Ein Unterbegriff ergibt sich, wenn ein bestehender formaler Begriff durch zusätzliche Merkmale weiter spezifiziert ist. Daraus ergibt sich weiter, dass die Gegenstände, die im Unterbegriff enthalten sind, eine Teilmenge der Gegenstände ist, die im Oberbegriff enthalten ist. Das führt zu der mathematischen Formulierung, der Umfang des Unterbegriffs sei im Umfang des Oberbegriffs enthalten, denn der Begriffsumfang ist die Menge seiner Gegenstände. Ferner gilt, wenn der Unterbegriff durch zusätzliche Merkmale aus dem Oberbegriff gebildet wird, dann sind umgekehrt die Merkmale des Oberbegriffs eine Teilmenge der Merkmale des Unterbegriffs. Da der Inhalt eines formalen Begriffs die Menge seiner Merkmale bezeichnet, ist also der Inhalt des Oberbegriffs, im Inhalt des Unterbegriffs enthalten.
  2. a b Rudolf Wille: Restructuring lattice theory: An approach based on hierarchies of concepts. Nachdruck in: ICFCA '09: Proceedings of the 7th International Conference on Formal Concept Analysis, Berlin, Heidelberg, 2009, S. 314. Eigene Übersetzung Jwollbold; „geistiger Hochleistungssport“: „elaborate mental gymnastics“.
  3.  Hartmut von Hentig: Magier oder Magister? Über die Einheit der Wissenschaft im Verständigungsprozeß. Klett 1972 / Suhrkamp 1974. Zitiert nach Karl Erich Wolff: Ordnung, Wille und Begriff (MS Word; 2,0 MB), Ernst Schröder Zentrum für Begriffliche Wissensverarbeitung, Darmstadt 2003. Suhrkamp-Taschenbuch-Verlag, Frankfurt am Main 1974, ISBN 978-3518067079.
  4. a b Johannes Wollbold: Attribute Exploration of Gene Regulatory Processes. Doktorarbeit, Universität Jena 2011. Digitale Bibliothek Thüringen, S. 9, abgerufen am 14. November 2015 (PDF; 4,6 MB, englisch).
  5. Ganter, Wille: Formale Begriffsanalyse, 1996, S. 1.
  6. Rudolf Wille: Formal Concept Analysis as Mathematical Theory of Concepts and Concept Hierarchies. In: B. Ganter et al.: Formal Concept Analysis. Foundations and Applications, 2005, S. 1f. Eigene Übersetzung Jwollbold.
  7. a b  Bernhard Ganter, Rudolf Wille: Kap. 1 „Begriffsverbände von Kontexten“. In: Formale Begriffsanalyse. Mathematische Grundlagen. Springer, Heidelberg 1996, ISBN 978-3-642-61450-7.
  8.  W.W. Armstrong: Dependency structures of data base relationships. In: IFIP Congress. Genf 1974, S. 580-583.
  9.  Bernhard Ganter, Gerd Stumme, Rudolf Wille (Hrsg.): Formal Concept Analysis. Foundations and Applications. Springer Science & Business Media, 2005, ISBN 978-354027891-7 (Online-Vorschau, abgerufen am 14. November 2015).
  10. Konferenzbände wie zur
     Petko Valtchev, Robert Jäschke (Hrsg.): Formal Concept Analysis 9th International Conference, ICFCA 2011, Nicosia, Cyprus, May 2-6, 2011, Proceedings. Springer-Verlag, Berlin, Heidelberg 2011, ISBN 978-3-642-20513-2 (Inhaltsangabe, abgerufen am 14. November 2015). oder zu
    CLA: Concept Lattices and Their Applications. Conference Homepage mit Open Access-Artikeln aller Konferenzen seit 2004. CLA, abgerufen am 14. November 2015 (englisch).