Formale Begriffsanalyse

Die Formale Begriffsanalyse (kurz FBA) (englisch Formal Concept Analysis, kurz FCA) ist eine mathematische Theorie. Sie liefert eine Methodik, um Zusammenhänge in gegebenen Datenmengen zu erkennen. Typisch dafür sind hierarchische Beziehungen zwischen Begriffen. Die Formale Begriffsanalyse kann als angewandte Ordnungs- und Verbandstheorie verstanden werden.^[1]

Die formale Begriffsanalyse findet praktische Anwendung z. B. in Data- und Text Mining, Wissensmanagement, Semantic Web, Software Engineering, Wirtschaft und Bioinformatik.^[2]

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 gemeinsamer Merkmale zu Gruppen zusammengefasst. 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 entgegenkommt.

Umfang, Inhalt und Begriff

Jede durch gemeinsame Merkmale bestimmte Menge 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.^[3]

Bezug zur mathematischen Verbandstheorie

Diese Unterbegriff-Oberbegriff-Ordnung der formalen Begriffe erweist sich als eine Ordnungsstruktur. Sie ist in aller Regel netzartig verzweigt, 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 mehrere Oberbegriffe haben, z. B. vereinigt der Begriff Greifvogel die Merkmale sowohl von seinem Oberbegriff Vogel als auch die seines 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.

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^[4]

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.“^[5] Somit zielt auch Formale Begriffsanalyse von ihren Ursprüngen her auf Interdisziplinarität und demokratische Kontrolle von Forschung.^[6]

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

Klarheit von Begriffen wird im Sinn von Charles S. Peirce’ Pragmatischer Maxime dadurch angestrebt, dass beobachtbare, elementare Eigenschaften der subsumierten Gegenstände entfaltet werden.^[6] 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^[7]

Eine vergleichbare Motivation lag jedoch historisch früher den Projekten zur Entwicklung analytischer Plansprachen zu Grunde, vgl. auch Universalsprache.

Beispiel

Zur Erläuterung der Grundlagen der Formalen Begriffsanalyse dient folgendes bewusst klein gehaltene Beispiel. Es ist Teil einer umfangreicheren Wortfeldstudie, in der Gewässer anhand von Merkmalen in eine Systematik gebracht wurden.^[8] Für die hiesigen Zwecke wurde das dort behandelte Beispiel etwas reduziert.

Im Folgenden wird außer der Tabelle auch schon die daraus konstruierbare Grafik, das Liniendiagramm, gezeigt.

Beispiel für einen formalen Kontext: „Gewässer“

Gewässer		Merkmale
		temporär	fließend	natürlich	stehend	konstant	maritim
G e g e n s t ä n d e	Bach		X	X		X
	Fluss		X	X		X
	Haff			X	X	X	X
	Kanal		X			X
	Lache	X		X	X
	Pfuhl			X	X	X
	Pfütze	X		X	X
	Rinnsal		X	X		X
	Strom		X	X		X
	Maar			X	X	X
	Meer			X	X	X	X
	See			X	X	X
	Teich			X	X	X
	Tümpel			X	X	X
	Weiher				X	X

 

Liniendiagramm entsprechend der Tabelle Gewässer auf der linken Seite.

Ausgangsdaten in Tabellenform

Für eine Analyse müssen die zu untersuchenden Daten in Tabellenform vorliegen oder in eine solche Form überführt werden.

In der Tabelle Beispiel für einen formalen Kontext: „Gewässer“ sind verschiedene Gewässerarten als formale Gegenstände in Zeilen aufgelistet. Die dazugehörigen formalen Merkmale bestimmen die Spalten dieser Tabelle.

Weist ein Gegenstand ein bestimmtes Merkmal auf, dann steht am Kreuzungspunkt in der jeweiligen Zeile und Spalte eine Markierung, meist ein „X“. Weist er dieses Merkmal nicht auf oder ist unklar, ob er dieses Merkmal aufweist, dann fehlt diese Markierung.

Reale Welt und formale Strukturen

Will man den Unterschied zwischen realen Gegenständen und Merkmalen einerseits und ihren Abstraktionen (den Daten in der Tabelle) andererseits betonen, spricht man bei den Abstraktionen von formalen Gegenständen und formalen Merkmalen. Analog spricht man bei der Gesamtheit der ganzen Tabelle von einem formalen Kontext. Später werden formale Begriffe noch genauer eingeführt.

Häufig entsprechen die formalen Gegenstände realen Gegenständen der Welt und die formalen Merkmale deren realen qualitativen oder quantitativen Eigenschaften. Ein formaler Gegenstand kann aber auch ein Abstraktum darstellen – wie die Gewässerarten in obigem Beispiel. Ebenso kann ein formales Merkmal ein Abstraktum darstellen.

Liniendiagramm

Das obige Liniendiagramm enthält Kreise und verbindende Linien. Kreise stellen formale Begriffe dar. An den Linien lässt sich die Unterbegriff-Oberbegriff-Hierarchie ablesen.

Bei der hier verwendeten reduzierten Beschriftung wird jeder Gegenstands- und jeder Merkmalname genau einmal in das Diagramm eingetragen, wobei Gegenstände unterhalb und Merkmale oberhalb von Begriffskreisen stehen. Dies geschieht so, dass ein Merkmal genau dann von einem Gegenstand aus über einen aufsteigenden Linienzug erreichbar ist, wenn der Gegenstand das Merkmal hat.

In dem gezeigten Diagramm hat z. B. der Gegenstand Weiher die Merkmale stehend und konstant, nicht aber die Merkmale temporär, natürlich, fließend und maritim. Entsprechend haben Lache und Pfütze genau die Merkmale temporär, stehend und natürlich.

Zu jedem Begriff kann man seinen Umfang und seinen Inhalt am Liniendiagramm ablesen. Der Umfang eines Begriffs besteht aus den Gegenständen, von denen ein aufsteigender Linienzug zum Kreis des Begriffes führt. Der Begriff, der im Diagramm unmittelbar links neben Weiher steht, hat den Inhalt stehend und natürlich und den Umfang Lache, Pfütze, Pfuhl, Maar, See, Teich, Tümpel, Haff und Meer.

Erweiterungen

Zur Formalen Begriffsanalyse gab es weitere Forschungen in unterschiedliche Richtungen. Exemplarisch folgen einige Forschungsansätze und Hinweise auf weiterführende Veröffentlichungen.

Triadische FBA

Die Triadische Begriffsanalyse ersetzt die binäre Beziehung zwischen Gegenständen und Merkmalen durch eine ternäre Beziehung zwischen Gegenständen, Merkmalen und Bedingungen. Eine Inzidenz ${\displaystyle (g,m,b)}$ drückt dann aus, dass der Gegenstand ${\displaystyle g}$ das Merkmal ${\displaystyle m}$ unter der Bedingung ${\displaystyle b}$ hat. Obwohl triadische Begriffe in Analogie zu den obigen formalen Begriffen definiert werden können, ist die Theorie der von ihnen gebildeten Tri-Verbände viel weniger weit entwickelt als die der Begriffsverbände und scheint schwierig zu sein.^[9]

George Voutsadakis hat den n-stelligen Fall (Polyadische FBA) untersucht.^[10]

Fuzzy-Begriffe

Fuzzy-Begriffe ergeben sich aus einer Kombination von Formaler Begriffsanalyse mit der Fuzzy-Set-Theorie. Dazu hat es zahlreiche Untersuchungen gegeben. Eine der ersten war die Dissertation von Silke Pollandt.^[11] Umfangreich entwickelt wurde die Theorie in der Gruppe um den tschechischen Mathematiker Radim Belohlávek, von der auch eine eigene Tagungsreihe Concept Lattices and Their Applications eingerichtet wurde. Deren Ergebnisse sind frei zugänglich.^[12] Einen Einstieg ins Thema bieten die Aufsätze What is a fuzzy concept lattice?^[13] und Formal Concept Analysis and Fuzzy Logic.^[14]

Temporale Begriffsanalyse

Um auch zeitlich veränderliche Vorgänge begrifflich beschreiben zu können, hat Karl Erich Wolff eine temporale Erweiterung der Begriffsanalyse formuliert.^[15]

Begriffsalgebren

Die Modellierung der Negation von formalen Begriffen ist etwas problematisch, weil das Komplement ${\displaystyle (G\setminus A,M\setminus B)}$ eines formalen Begriffs nicht notwendigerweise ein formaler Begriff ist. Da der Begriffsverband jedoch vollständig ist, kann man das Supremum ${\displaystyle (A,B)^{\Delta }}$ aller Begriffe ${\displaystyle (C,D)}$ betrachten, welche ${\displaystyle C\subseteq G\setminus A}$ erfüllen; oder alternativ das Infimum ${\displaystyle (A,B)^{\nabla }}$ aller Begriffe, welche ${\displaystyle D\subseteq M\setminus B}$ erfüllen. Diese beiden Operationen werden als schwache Negation bzw. schwache Opposition bezeichnet. Sie können mit Hilfe der Ableitungsoperatoren ausgedrückt werden.

Die schwache Negation kann geschrieben werden als ${\displaystyle (A,B)^{\Delta }=((G\setminus A)^{\prime \prime },(G\setminus A)^{\prime })}$ und die schwache Opposition als ${\displaystyle (A,B)^{\nabla }=((M\setminus B)^{\prime },(M\setminus B)^{\prime \prime })}$. Der mit den beiden zusätzlichen Operationen ${\displaystyle \Delta }$ und ${\displaystyle \nabla }$ ausgestattete Begriffsverband wird als Begriffsalgebra eines Kontexts bezeichnet. Begriffsalgebren verallgemeinern Potenzmengen.

Die schwache Negation auf einem Begriffsverband ${\displaystyle L}$ ist eine schwache Komplementation, d. h. eine ordnungsumkehrende Abbildung ${\displaystyle \Delta \colon L\to L}$, die die Axiome ${\displaystyle x^{\Delta \Delta }\leq x}$ und ${\displaystyle (x\wedge y)\vee (x\wedge y^{\Delta })=x}$ erfüllt.

Die schwache Opposition ist eine duale schwache Komplementation. Ein (beschränkter) Verband, der mit einer schwachen Komplementierung und einer dualen schwachen Komplementierung ausgestattet ist, wird als schwach dikomplementierter Verband bezeichnet. Begriffsalgebren sind davon Beispiele. Schwach dikomplementierte Verbände verallgemeinern distributive orthokomplementierte Verbände, d. h. Boolesche Algebren.^[16][17]

Mathematische Grundlagen

Begriffsverbände sind gut geeignet, Daten so zu ordnen und darzustellen, dass sie auch ohne mathematische Vorbildung gut verstanden werden können. Die mathematischen Grundlagen sollen hier kurz dargelegt werden.

Formale Kontexte und Formale Begriffe

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

Sind die Mengen ${\displaystyle G}$ und ${\displaystyle 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.

Ist ${\displaystyle A\subseteq G}$ eine Menge von Gegenständen eines formalen Kontextes ${\displaystyle \mathbb {K} =(G,M,I)}$, so bezeichnet man mit

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

die Menge der gemeinsamen Merkmale der Gegenstände in ${\displaystyle A}$. Entsprechend definiert wird für eine Menge ${\displaystyle B\subseteq M}$ von Merkmalen von ${\displaystyle \mathbb {K} =(G,M,I)}$ die Menge

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

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

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

• ${\displaystyle A_{1}\subseteq A_{2}\,\implies \,A_{2}'\subseteq A_{1}'}$ und dual ${\displaystyle B_{1}\subseteq B_{2}\,\implies \,B_{2}'\subseteq B_{1}'}$,
• ${\displaystyle A\subseteq A''}$ und dual ${\displaystyle B\subseteq B''}$,
• ${\displaystyle A'=A'''}$ und ${\displaystyle B'=B'''}$,
• ${\displaystyle 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 ${\displaystyle \mathbb {K} }$ heißt nun ein Paar ${\displaystyle (A,B)}$ ein formaler Begriff^[18] von ${\displaystyle \mathbb {K} }$, falls

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

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

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

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

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

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

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

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

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

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

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

gilt. Insbesondere ist ${\displaystyle {\underline {L}}}$ isomorph zu ${\displaystyle {\underline {\mathfrak {B}}}(L,L,\leq _{L})}$.

Der Hauptsatz ist auch als Rudolf Willes Hauptsatz über Begriffsverbände bekannt. Er besagt unter anderem, dass jeder vollständige Verband einem Begriffsverband isomorph ist.^[19]

Implikationentheorie Formaler Kontexte

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

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

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

Eine Basis für ${\displaystyle \mathbb {K} }$ ist dann eine Menge ${\displaystyle {\mathcal {L}}}$ von gültigen Implikationen von ${\displaystyle \mathbb {K} }$, so dass jede (semantisch) gültige Implikation aus ${\displaystyle \mathbb {K} }$ bereits aus ${\displaystyle {\mathcal {L}}}$ folgt, durch Anwendung geeigneter syntaktischer Inferenzregeln wie der Armstrong-Regeln^[20]. Die in diesem neuen Sinn abgeschlossene Menge aller Implikationen von ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle {\mathcal {L}}}$ von Implikationen genau dann eine Basis eines Kontextes ${\displaystyle \mathbb {K} }$ ist, wenn die Menge der unter ${\displaystyle {\mathcal {L}}}$ abgeschlossenen Mengen genau die der Inhalte von ${\displaystyle \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 Formale Begriffsanalyse Anfang der 1980er hat die Forschungsgruppe Formale Begriffsanalyse an der TU Darmstadt Erfahrungen aus mehr als 200 Projekten gesammelt, in denen die Formale Begriffsanalyse angewandt wurde (Stand 2005).^[21] Darunter aus den Bereichen: Medizin und Zellbiologie,^[22][23] Genetik,^[24][25] Ökologie,^[26] Softwaretechnik,^[27] Ontologie (Informatik)^[28], Informations- und Bibliothekswissenschaften,^[29][30][31] Büroorganisation,^[32] Recht,^[33][34] Sprachwissenschaft,^[35] Politikwissenschaften.^[36]

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

Literatur

• Brian A. Davey, Hilary A. Priestley: Introduction to Lattices and Order. 2. Auflage. Cambridge University Press, New York 2002, ISBN 0-521-78451-4 (MR1902334). 
• Bernhard Ganter: Diskrete Mathematik: Geordnete Mengen (= Springer-Lehrbuch). Springer Spektrum, Berlin, Heidelberg 2013, ISBN 978-3-642-37499-9, doi:10.1007/978-3-642-37500-2. 
• 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 (Vorschau). 
• George Grätzer: General Lattice Theory. New appendices by the author with B. A. Davey, R. Freese, B. Ganter, M. Greferath, P. Jipsen, H. A. Priestley, H. Rose, E. T. Schmidt, S. E. Schmidt, F. Wehrung and R. Wille. 2. Auflage. Birkhäuser Verlag, Basel, Boston, Berlin 1998, ISBN 3-7643-5239-6 (MR1670580). 
• 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). 

Weblinks

• Uta Priss: Formal Concept Analysis Homepage. 2007, abgerufen am 2. Mai 2019 (englisch).  mit Links zu weiteren Programmen
• Bernhard Ganter: The Dresden Formal Concept Analysis Page. TU Dresden, 2. März 1999, abgerufen am 2. Mai 2019 (englisch). 
• BibSonomy. Lesezeichen und Publikationen teilen - in blau! bibsonomy.org, abgerufen am 2. Mai 2019.  Literatur und Weblinks nicht nur zu Formale Begriffsanalyse (social bookmarking)

Einzelnachweise und Anmerkungen

1. Rudolf Wille: Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts. In: I.Rival (Hrsg.): Ordered Sets: Proceedings of the NATO Advanced Study Institute Held at Banff, Canada. 1982 (englisch). 
2. Siehe Abschnitt #Anwendungserfahrungen mit der Formalen Begriffsanalyse für Beispiele
3. Ein Unterbegriff ergibt sich, wenn ein formaler Begriff durch zusätzliche Merkmale weiter spezifiziert ist. Daraus ergibt sich, dass die Gegenstände, die zum Unterbegriff gehören auch zum Oberbegriff gehören. Umgekehrt sind alle Merkmale des Oberbegriffs auch Merkmale des Unterbegriffs.
4. 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. „geistiger Hochleistungssport“: „elaborate mental gymnastics“.
5. Hartmut von Hentig: Magier oder Magister? Über die Einheit der Wissenschaft im Verständigungsprozeß. 1. Auflage. Suhrkamp-Taschenbuch-Verlag, Frankfurt am Main 1974, ISBN 3-518-06707-9.  Zitiert nach Karl Erich Wolff: Ordnung, Wille und Begriff. Ernst Schröder Zentrum für Begriffliche Wissensverarbeitung, Darmstadt 2003 (fbmn.h-da.de [DOC; 2,0 MB]).  fbmn.h-da.de (Memento vom 12. September 2015 im Internet Archive)
6. Johannes Wollbold: Attribute Exploration of Gene Regulatory Processes. (PDF; 4,6 MB) Doktorarbeit, Universität Jena 2011. Digitale Bibliothek Thüringen, S. 9, abgerufen am 14. November 2015 (englisch). 
7. 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.
8. Peter Rolf Lutzeier: Wort und Feld: wortsemantische Fragestellungen mit besonderer Berücksichtigung des Wortfeldbegriffes. Dissertation (= Linguistische Arbeiten. Band 103). Niemeyer, Tübingen 1981, OCLC 8205166, doi:10.1515/9783111678726.fm. 
9. Rudolf Wille: The basic theorem of triadic concept analysis. Springer Nature, 1995, S. 149–158, doi:10.1007/BF01108624. 
10. George Voutsadakis: Polyadic Concept Analysis. Order 19(3). Springer, 22. August 2002, S. 295–304 (englisch, voutsadakis.com [PDF; abgerufen am 28. Oktober 2021]). 
11. Silke Pollandt: Fuzzy-Begriffe. Formale Begriffsanalyse unscharfer Daten. Springer, Berlin Heidelberg 1997, ISBN 3-540-61335-8. 
12. Radim Belohlavek, Jan Outrata: CLA: Concept Lattices and Their Applications. Palacký University, Olomouc, Czech Republic, 2018, abgerufen am 28. Oktober 2021 (englisch). 
13. Radim Belohlávek, Vilém Vychodil: What is a fuzzy concept lattice? In: Proc. CLA. 2005, S. 34–45 (englisch, upol.cz [PDF; abgerufen am 22. Oktober 2021]). 
14. "Formal Concept Analysis and Fuzzy Logic". Archived from the original (PDF) on 2017-12-09. Retrieved 2017-12-08.
15. Karl Erich Wolff: Process Representation in Temporal Concept Analysis. In: G.W. Mineau, Dept. of Computer Science. University Laval (Hrsg.): Conceptual Structures: Extracting and Representing Semantics. Quebec, Canada 2001, S. 211–212 (englisch). 
16. Rudolf Wille: Boolean Concept Logic. In: Bernhard Ganter, Guy W. Mineau (Hrsg.): ICCS 2000 Conceptual Structures: Logical, Linguistic and Computational Issues (= LNAI 1867). Band 1867. Springer-Verlag, Berlin, Heidelberg 2000, ISBN 3-540-67859-X, S. 317–331, doi:10.1007/10722280 (englisch). 
17. Léonard Kwuida: Dicomplemented Lattices. A contextual generalization of Boolean algebras. Shaker Verlag, Düren 2004, ISBN 3-8322-3350-4. 
18. Bernhard Ganter, Rudolf Wille: Kap. 1 „Begriffsverbände von Kontexten“. In: Formale Begriffsanalyse. Mathematische Grundlagen. Springer, Heidelberg 1996, ISBN 3-540-60868-0, urn:nbn:de:1111-20111002812. 
19. Bernhard Ganter: Diskrete Mathematik: Geordnete Mengen. 2013, S. 66, S. 167–168.
20. W.W. Armstrong: Dependency structures of data base relationships. In: IFIP Congress. Genf 1974, S. 580–583 (englisch). 
21. Bernhard Ganter, Gerd Stumme, Rudolf Wille (Hrsg.): Formal Concept Analysis. Foundations and Applications. Springer Science & Business Media, Berlin Heidelberg 2005, ISBN 3-540-27891-5, doi:10.1007/978-3-540-31881-1 (books.google.de [abgerufen am 14. November 2015]). 
22. Susanne Motameny, Beatrix Versmold, Rita Schmutzler: Formal Concept Analysis for the Identification of Combinatorial Biomarkers in Breast Cancer. In: Raoul Medina, Sergei Obiedkov (Hrsg.): ICFCA 2008 (= LNAI). Band 4933. Springer, Berlin Heidelberg 2008, ISBN 978-3-540-78136-3, S. 229–240. 
23. Dominik Endres, Ruth Adam, Martin A. Giese, Uta Noppeney: Understanding the Semantic Structure of Human fMRI Brain Recordings with Formal Concept Analysis. In: Florent Domenach, Dmitry I. Ignatov, Jonas Poelmans (Hrsg.): ICFCA 2012 (= LNCS). Band 7278. Springer, 2012, ISBN 978-3-642-29891-2, ISSN 0302-9743, S. 96–111, doi:10.1007/978-3-642-29892-9. 
24. Denis Ponomaryov, Nadezhda Omelianchuk, Victoria Mironova, Eugene Zalevsky, Nikolay Podkolodny, Eric Mjolsness, Nikolay Kolchanov: From Published Expression and Phenotype Data to Structured Knowledge: The Arabidopsis Gene Net Supplementary Database and Its Applications. In: Karl Erich Wolff, Dmitry E. Palchunov, Nikolay G. Zagoruiko, Urs Andelfinger (Hrsg.): KONT 2007, KPP 2007 (= LNCS). Band 6581. Springer, 2011, ISBN 978-3-642-22139-2, ISSN 0302-9743, S. 101–120, doi:10.1007/978-3-642-22140-8. 
25. Mehdi Kaytoue, Sergei Kuznetsov, Amedeo Napoli, Sébastien Duplessis: Mining gene expression data with pattern structures in formal concept analysis. In: Information Sciences. Band 181, Nr. 10. Elsevier, 2011, S. 1989–2001, doi:10.1016/j.ins.2010.07.007 (hse.ru [PDF; abgerufen am 13. Februar 2016]). 
26. Aurélie Bertaux, Florence Le Ber, Agnès Braud, Michèle Trémolières: Identifying Ecological Traits: A Concrete FCA-Based Approach. In: Sébastien Ferré, Sebastian Rudolph (Hrsg.): ICFCA 2009 (= LNAI). Band 5548. Springer-Verlag, Berlin Heidelberg 2009, ISBN 978-3-642-01814-5, S. 224–236, doi:10.1007/978-3-642-01815-2. 
27. Gregor Snelting, Frank Tip: Reengineering class hierarchies using concept analysis. In: Proceeding. SIGSOFT ’98/FSE-6. Band 23, Nr. 6. ACM, New York 1998, ISBN 1-58113-108-9, S. 99–110, doi:10.1145/291252.288273 (dl.acm.org [abgerufen am 4. Februar 2016]). 
28. Gerd Stumme, Alexander Maedche: FCA-Merge: Bottom-up merging of ontologies. In: Uni Leipzig (Hrsg.): IJCAI. Leipzig 2001, S. 225–230 (se-pubs.dbs.uni-leipzig.de [PDF; abgerufen am 13. Februar 2016]). 
29. Uta Priss: Formal Concept Analysis in Information Science. In: American Documentation Institute (Hrsg.): Annual Review of Information Science and Technology. Band 40, Nr. 1. Information Today Inc., 2006, ISSN 0066-4200, S. 521–543, doi:10.1002/aris.1440400120 (upriss.org.uk [PDF; abgerufen am 4. Februar 2016]). 
30. Jens Illig, Andreas Hotho, Robert Jäschke, Gerd Stumme: A Comparison of Content-Based Tag Recommendations in Folksonomy Systems. In: Karl Erich Wolff, Dmitry E. Palchunov, Nikolay G. Zagoruiko, Urs Andelfinger (Hrsg.): KONT 2007, KPP 2007 (= LNCS). Band 6581. Springer, 2011, ISBN 978-3-642-22139-2, ISSN 0302-9743, S. 136–149, doi:10.1007/978-3-642-22140-8. 
31. Claudio Carpineto, Giovanni Romano (Hrsg.): Concept Data Analysis: Theory and Applications. John Wiley & Sons, 2004, ISBN 0-470-85055-8 (eu.wiley.com [abgerufen am 4. Februar 2016]). 
32. Richard Cole, Gerd Stumme: CEM – A Conceptual Email Manager. In: Bernhard Ganter, Guy W. Mineau (Hrsg.): Conceptual Structures: Logical, Linguistic, and Computational Issues (= LNAI). Band 1867. Springer-Verlag, Berlin Heidelberg 2000, ISBN 3-540-67859-X, S. 438–452, doi:10.1007/10722280. 
33. Dieter Eschenfelder, Wolfgang Kollewe, Martin Skorsky, Rudolf Wille: Ein Erkundungssystem zum Baurecht: Methoden der Entwicklung eines TOSCANA-Systems. In: Gerd Stumme, Rudolf Wille (Hrsg.): Begriffliche Wissensverarbeitung – Methoden und Anwendungen. Springer, Berlin Heidelberg 2000, ISBN 3-540-66391-6, S. 254–272, doi:10.1007/978-3-642-57217-3_12. 
34. Nada Mimouni, Adeline Nazarenko; Sylvie Salotti: A Conceptual Approach for Relational IR: Application to Legal Collections. In: Jaume Baixeries, Christian Sacarea, Manuel Ojeda-Aciego (Hrsg.): ICFCA 2015 (= LNAI). Band 9113. Springer, 2015, ISBN 978-3-319-19544-5, ISSN 0302-9743, S. 303–318, doi:10.1007/978-3-319-19545-2_19. 
35. Uta Priss: Linguistic Applications of Formal Concept Analysis. In: Bernhard Ganter, Gerd Stumme, Rudolf Wille (Hrsg.): Formal Concept Analysis – Foundations and Applications (= LNCS). Band 3626. Springer, 2005, ISBN 3-540-27891-5, ISSN 0302-9743, S. 149–160, doi:10.1007/978-3-540-31881-1. 
36. Beate Kohler-Koch, Frank Vogt: Normen- und Regelgeleitete internationale Kooperationen. "Zitiert nach: Peter Becker et al. The ToscanaJ Suite for Implementing Conceptual Information Systems". In: Gerhard Stumme, Rudolf Wille (Hrsg.): Begriffliche Wissenverarbeitung – Methoden und Anwendungen. Springer, Berlin, Heidelberg, New York 2000, ISBN 3-540-66391-6, S. 325–340. 
37. International Conference on Formal Concept Analysis. dblp, abgerufen am 14. Februar 2016 (englisch). 
38. CLA: Concept Lattices and Their Applications. Conference Homepage mit Open-Access-Artikeln aller Konferenzen seit 2004. CLA, abgerufen am 14. November 2015 (englisch). 
39. International Conferences On Conceptual Structures – Conferences and Workshops. New Mexico State University, abgerufen am 14. Februar 2016 (englisch).