In der Informationswissenschaft ist formelle Konzeptanalyse eine Weise mit hohen Grundsätzen, eine Konzepthierarchie oder formelle Ontologie von einer Sammlung von Gegenständen und ihren Eigenschaften abzuleiten. Jedes Konzept in der Hierarchie vertritt den Satz von Gegenständen, die dieselben Werte für einen bestimmten Satz von Eigenschaften teilen; und jedes Subkonzept in der Hierarchie enthält eine Teilmenge der Gegenstände in den Konzepten darüber. Der Begriff wurde von Rudolf Wille 1984 eingeführt, und baut auf angewandtes Gitter und Ordnungstheorie, die von Birkhoff und anderen in den 1930er Jahren entwickelt wurde.

Formelle Konzeptanalyse findet praktische Anwendung in Feldern einschließlich Datenbergwerks, Textbergwerks, des Maschinenlernens, des Kenntnisse-Managements, des semantischen Webs, der Softwareentwicklung und der Biologie.

Übersicht und Geschichte

Die ursprüngliche Motivation der formellen Konzeptanalyse war die konkrete Darstellung von ganzen Gittern und ihren Eigenschaften mittels formeller Zusammenhänge, Datentische, die binäre Beziehungen zwischen Gegenständen und Attributen vertreten. In dieser Theorie wird ein formelles Konzept einem Paar definiert, das aus einer Reihe von Gegenständen (das "Ausmaß") und eine Reihe von Attributen (die "Absicht") solch besteht, dass das Ausmaß aus allen Gegenständen besteht, die die gegebenen Attribute teilen, und die Absicht aus allen durch die gegebenen Gegenstände geteilten Attributen besteht. Auf diese Weise formalisiert formelle Konzeptanalyse die Begriffe der Erweiterung und Verstärkung.

Paaren von formellen Konzepten kann durch die Teilmenge-Beziehung zwischen ihren Sätzen von Gegenständen, oder gleichwertig durch die Obermenge-Beziehung zwischen ihren Sätzen von Attributen teilweise befohlen werden. Diese Einrichtung läuft auf ein abgestuftes System sub - und Superkonzepte, eine Konzepthierarchie hinaus, die als ein Diagramm von Hasse gezeigt werden kann. Die Familie dieser Konzepte folgt den mathematischen Axiomen, die ein Gitter definieren, und wird mehr formell ein Konzeptgitter genannt. In Französisch wird das einen treillis de Galois (Gitter von Galois) wegen der Beziehung zwischen den Sätzen von Konzepten genannt, und Attribute ist eine Verbindung von Galois.

Die Theorie in seiner gegenwärtigen Form geht zur Forschungsgruppe von Darmstadt zurück, die von Rudolf Wille, Bernhard Ganter und Peter Burmeister geführt ist, wo formelle Konzeptanalyse am Anfang der 1980er Jahre entstanden ist. Die mathematische Basis wurde bereits jedoch von Garrett Birkhoff in den 1930er Jahren als ein Teil der allgemeinen Gitter-Theorie geschaffen. Vor der Arbeit der Gruppe von Darmstadt gab es bereits Annäherungen in verschiedenen französischen Gruppen. Philosophische Fundamente der formellen Konzeptanalyse verweisen insbesondere Charles S. Peirce und dem Pädagogen Hartmut von Hentig.

Beispiel

Denken Sie O = {1,2,3,4,5,6,7,8,9,10}, und = {Zusammensetzung, sogar, seltsam, erst, quadratisch}. Das kleinste Konzept einschließlich der Nummer 3 ist dasjenige mit Gegenständen {3,5,7}, und Attribute {seltsam, erst}, für 3 hat beide jener Attribute, und {3,5,7} ist der Satz von Gegenständen, die diesen Satz von Attributen haben. Das größte Konzept, das das Attribut einschließt, quadratisch zu sein, ist dasjenige mit Gegenständen {1,4,9}, und Attribute {Quadrat}, für 1, 4 und 9 sind alle Quadratzahlen, und alle drei von ihnen haben diesen Satz von Attributen.

Es kann sogleich gesehen werden, dass beide dieser Beispiel-Konzepte die formellen Definitionen unter befriedigen

Der volle Satz von Konzepten für diese Gegenstände und Attribute wird in der Illustration gezeigt. Es schließt ein Konzept für jedes der ursprünglichen Attribute ein: die zerlegbaren Zahlen, Quadratzahlen, geraden Zahlen, ungeraden Zahlen und Primzahlen. Zusätzlich schließt es Konzepte für die gleichen zerlegbaren Zahlen, zerlegbare Quadratzahlen (d. h. alle Quadratzahlen außer 1), sogar zerlegbare Quadrate, sonderbare Quadrate, sonderbare zerlegbare Quadrate, sogar Blüte und sonderbare Blüte ein.

Zusammenhänge und Konzepte

Ein (formeller) Zusammenhang besteht aus einer Reihe von Gegenständen O, eine Reihe unärer Attribute A, und dessen Anzeige Gegenstände der Attribute haben. Formell kann es als ein zweiteiliger Graph I  O × A betrachtet werden.

Ein (formelles) Konzept für einen Zusammenhang wird definiert, um ein Paar (O, A) solch dass zu sein

1. O  O
2. EIN  EIN
3. jeder Gegenstand in O hat jedes Attribut in Einem
4. für jeden Gegenstand in O, der nicht in O ist, gibt es ein Attribut in, dass der Gegenstand nicht hat
5. für jedes Attribut in, der nicht in A ist, gibt es einen Gegenstand in O, der dieses Attribut nicht hat

O wird das Ausmaß des Konzepts, die Absicht genannt.

Ein Zusammenhang kann als ein Tisch, mit den Gegenständen entsprechend den Reihen des Tisches, der Attribute entsprechend den Säulen des Tisches und eines Werts von Boolean (im Beispiel vertreten grafisch als ein checkmark) in der Zelle beschrieben werden (x, y), wann auch immer Gegenstand x Wert y hat:

Ein Konzept, in dieser Darstellung, bildet eine maximale Subreihe (nicht notwendigerweise aneinander grenzend) solch, dass alle Zellen innerhalb der Subreihe überprüft werden. Zum Beispiel ist das Konzept, das mit einer verschiedenen Hintergrundfarbe im Beispiel-Tisch hervorgehoben ist, dasjenige, das die sonderbaren Primzahlen beschreibt, und bildet 3 × 2 Subreihe, in der alle Zellen überprüft werden.

Konzeptgitter eines Zusammenhangs

Die Konzepte (O, A) definiert können oben durch die Einschließung teilweise bestellt werden: Wenn (O, A) und (O, A) Konzepte sind, definieren wir eine teilweise Ordnung , indem wir dass (O, A)  (O, A) wann auch immer O  O sagen. Gleichwertig, (O, A)  (O, A) wann auch immer Ein  A.

Jedes Paar von Konzepten in dieser teilweisen Ordnung hat einen einzigartigen tiefer gebundenen größten (treffen sich). Das größte, das tiefer (O, A) und (O, A) gebunden ist, ist das Konzept mit Gegenständen O  O; es hat als seine Attribute die Vereinigung von A, A, und irgendwelche zusätzlichen Attribute, die durch alle Gegenstände in O  O gehalten sind.

Symmetrisch hat jedes Paar von Konzepten in dieser teilweisen Ordnung einen einzigartigen gebundenen am wenigsten oberen (schließen sich an). Das am wenigsten obere, das (O, A) und (O, A) gebunden ist, ist das Konzept mit Attributen Ein  A; es hat als seine Gegenstände die Vereinigung von O, O, und irgendwelche zusätzlichen Gegenstände, die alle Attribute in Einem  A haben.

Diese treffen sich und schließen sich an Operationen befriedigen die Axiome, die ein Gitter definieren. Tatsächlich, durch das Betrachten als unendlich trifft sich und schließt sich an, analog zur Dualzahl trifft sich und schließt sich definiert oben an, man sieht, dass das ein ganzes Gitter ist. Es kann als die Dedekind-MacNeille Vollziehung eines teilweise bestellten Satzes der Höhe zwei angesehen werden, in dem die Elemente der teilweisen Ordnung die Gegenstände und Attribute von A sind, und in dem zwei Elemente x und y x  y genau befriedigen, wenn x ein Gegenstand ist, der Attribut y hat.

Jedes begrenzte Gitter kann als das Konzeptgitter für einen Zusammenhang erzeugt werden. Da gelassener L, ein begrenztes Gitter sein, und einen Zusammenhang zu bilden, in dem die Gegenstände und die Attribute beide Elementen von L entsprechen. In diesem Zusammenhang, lassen Sie Gegenstand x haben Attribut y genau, wenn x und y als x  y im Gitter bestellt werden. Dann ist das Konzeptgitter dieses Zusammenhangs zu L selbst isomorph. Dieser Aufbau kann als das Formen der Dedekind-MacNeille Vollziehung von L interpretiert werden, der, wie man bekannt, ein isomorphes Gitter von jedem begrenzten Gitter erzeugt.

Konzeptalgebra eines Zusammenhangs

Das Modellieren der Ablehnung in einem formellen Zusammenhang ist etwas problematisch, weil die Ergänzung (O\O, A\A) eines Konzepts (O, A) im Allgemeinen nicht ein Konzept ist. Jedoch, da das Konzeptgitter ganzes ist, kann die Verbindungslinie (O, A) aller Konzepte denken (O, A), die O  G\O befriedigen; oder Doppel-das Entsprechen (O, A) aller Konzepte, die Einen  G\A befriedigen. Diese zwei Operationen sind als schwache Ablehnung und schwache Opposition beziehungsweise bekannt.

Das kann in Bezug auf die abgeleiteten Funktionen ausgedrückt werden. Die Ableitung eines Satzes O  O Gegenstände ist der Satz O'  aller Attribute, die für alle Gegenstände in O halten. Die Ableitung eines Satzes Ein  Attribute ist der Satz'  O aller Gegenstände, die alle Attribute in A haben. Ein Paar (O, A) ist ein Konzept wenn und nur wenn O' = A und' = O.

Mit dieser Funktion kann schwache Ablehnung als geschrieben werden

: (O, A) = ((G\A)

und schwache Opposition kann als geschrieben werden

: (O, A) = ((M\B)', (M\B)

Das Konzeptgitter, das mit den zwei zusätzlichen Operationen Δ und  ausgestattet ist, ist als die Konzeptalgebra eines Zusammenhangs bekannt. Konzeptalgebra sind eine Generalisation von Macht-Sätzen.

Die schwache Ablehnung auf einem Konzeptgitter L ist eine schwache Fertigstellung, d. h. eine Ordnung umkehrende Karte Δ: L  L, der die Axiome x  x und (xy)  (xy) = x befriedigt. Schwache Zusammensetzung ist eine schwache Doppelfertigstellung. Ein (begrenztes) Gitter wie eine Konzeptalgebra, die mit einer schwachen Fertigstellung und einer schwachen Doppelfertigstellung ausgestattet wird, wird schwach dicomplemented Gitter genannt. Schwach verallgemeinern Dicomplemented-Gitter verteilende orthocomplemented Gitter, d. h. Algebra von Boolean.

Die Besserung des Zusammenhangs aus dem Diagramm von Hasse

Das Diagramm von Hasse des Konzeptgitters (auch genannt, in der formellen Konzeptanalyse, einem Liniendiagramm), verschlüsselt genug Information, um den ursprünglichen Zusammenhang wieder zu erlangen, von dem es gebildet wurde. Jeder Gegenstand des Zusammenhangs entspricht einem Gitter-Element, dem Element mit dem minimalen Gegenstand-Satz, der diesen Gegenstand, und mit einem Attribut-Satz enthält, der aus allen Attributen des Gegenstands besteht. Symmetrisch entspricht jedes Attribut des Zusammenhangs einem Gitter-Element, demjenigen mit dem minimalen Attribut-Satz, der dieses Attribut, und mit einem Gegenstand-Satz enthält, der aus allen Gegenständen mit diesem Attribut besteht. Wir können die Knoten des Diagramms von Hasse mit den Gegenständen und Attributen etikettieren, denen sie entsprechen; mit diesem Beschriften, wenden Sie ein, dass x Attribut y hat, wenn, und nur wenn dort ein monotonischer Pfad von x bis y im Diagramm besteht.

Effizienter Aufbau

überblicken Sie die vielen Algorithmen, die entwickelt worden sind, um Konzeptgitter zu bauen. Diese Algorithmen ändern sich in vielen Details, aber basieren im Allgemeinen auf der Idee, dass jeder Rand des Diagramms von Hasse des Konzeptgitters ein Konzept C mit dem Konzept verbindet, das durch die Verbindungslinie von C mit einem einzelnen Gegenstand gebildet ist. So kann man das Konzeptgitter ein Konzept auf einmal aufbauen, indem man die Nachbarn im Diagramm von Hasse bekannter Konzepte findet, vom Konzept mit einem leeren Satz von Gegenständen anfangend. Die Zeitdauer, die ausgegeben ist, um das komplette Konzeptgitter auf diese Weise zu überqueren, ist Polynom in der Zahl von Eingangsgegenständen und Attributen pro erzeugtes Konzept.

Werkzeuge

Viele FCA Softwareanwendungen sind heute verfügbar. Der Hauptzweck dieser Werkzeuge ändert sich von der formellen Zusammenhang-Entwicklung bis formelles Konzeptbergwerk und das Erzeugen des Konzeptgitters eines gegebenen formellen Zusammenhangs und der entsprechenden Vereinigungsregeln. Die meisten dieser Werkzeuge sind akademisch und noch unter der aktiven Entwicklung. Man kann eine nicht erschöpfende Liste von FCA Werkzeugen in der FCA Softwarewebsite finden. Die meisten dieser Werkzeuge sind Anwendungen der offenen Quelle wie ConExp, ToscanaJ, Gitter-Bergarbeiter, Coron, FcaBedrock usw.

Siehe auch

• Biclustering
• Traube-Analyse
• Konzept, das abbaut
• Das Begriffssammeln

Referenzen

• . Übersetzt von C. Franzke.

. . . .

Außenverbindungen

• Eine formelle Konzeptanalyse-Einstiegsseite
• Demo
• 8. Internationale Konferenz für die Formelle Konzeptanalyse. ICFCA 2010 - Agadir, Marokko, am 15-18 März 2010