C89

From SAS
Jump to: navigation, search

'Formal Concept Analysis' (en abrégé 'FBA' ) (anglais 'Formal Concept Analysis' , en abrégé 'FCA' ) est une théorie mathématique. Il fournit une méthodologie pour identifier les relations dans des ensembles de données donnés. Les relations hiérarchiques entre term sont typiques de cela. L'analyse conceptuelle formelle peut être comprise comme appliquée ordre et théorie de l'association. [1]

L'analyse de concept formelle trouve une application pratique, par exemple B. dans Data- et Text Mining, Knowledge Management, Semantic Web, Software Engineering, Business and [ [Bioinformatique]]. [2]

Introduction

L '«analyse de concept formelle» examine les relations dans les collectes de données et rend les structures des données claires. Les `` objets (décrits par exemple par des enregistrements de données) sont regroupés en fonction de caractéristiques communes. Au sein de ces groupes, d'autres subdivisions sont ensuite faites en fonction d'autres caractéristiques. Il en résulte une structure hiérarchique, qui peut être illustrée sous la forme d'un réseau diagramme de commande. L'objectif est une méthodologie mathématiquement solide qui intègre la pensée conceptuelle humaine.

portée, contenu et concept

Chaque ensemble d'objets déterminé par des caractéristiques communes est interprété comme une `` portée des termes , l'ensemble associé de toutes les caractéristiques communes comme un `` contenu des termes . Les deux parties ensemble, c'est-à-dire une portée et le contenu associé, forment un «terme formel», l'addition «formelle» indiquant qu'il s'agit d'une construction mathématique. Un terme formel est donc toujours clairement défini à la fois par sa portée et par son contenu.

terme générique et subordonné

Un terme formel est un terme subordonné d'un second terme formel si sa portée est entièrement dans la portée du second. Ensuite, le contenu du terme générique s (c'est-à-dire le terme avec la plus grande portée) est contenu dans le contenu du sous-terme est spécifié. Il s'ensuit que les objets qui appartiennent au sous-concept appartiennent également au terme générique. Inversement, toutes les caractéristiques du terme générique sont également des caractéristiques du sous-terme. </ref>

référence à la théorie de l'association mathématique

Cet ordre de termes sous-génériques des termes formels se révèle être une structure d'ordre. En règle générale, il est semblable à un réseau, généralement pas semblable à un arbre ou même linéaire. Cependant, il peut être prouvé que ces ordres ont des propriétés spéciales et bien examinées: ce sont toujours des soi-disant associations complètes (anglais: réseaux complets).

Un terme peut avoir plusieurs termes génériques, par exemple B. le terme «oiseau de proie» combine les caractéristiques de son terme générique «oiseau» et celles de son deuxième terme générique «rapace proie».

Origine

La théorie dans sa forme actuelle remonte au groupe de recherche de Darmstadt autour de Rudolf Wille, Bernhard Ganter et Peter Burmeister, dans lequel l'analyse formelle du concept a émergé au début des années 1980. . Les fondements mathématiques ont déjà été créés par Garrett Birkhoff dans les années 1930 dans le cadre de la théorie des associations. Avant les travaux du groupe Darmstadt, il y avait déjà des approches dans différents groupes français. Les écrits de Charles S. Peirce et Hartmut von Hentig ont influencé le développement de l'analyse conceptuelle formelle.

Motivation et contexte philosophique

Dans l'article Restructuring Lattice Theory (1982), qui a fondé l'analyse conceptuelle formelle comme une discipline, le malaise de la théorie de l'association et des mathématiques pures est mentionné comme une motivation: la production de résultats théoriques, qui est souvent obtenue grâce au "sport intellectuel de haute performance", est impressionnante, cependant, les liens entre les régions voisines et même des parties d'une théorie s'affaibliraient.

Template:Citation

Cet objectif fait référence à Hartmut von Hentig, qui a appelé à une restructuration des sciences en 1972, "afin de les rendre plus faciles à apprendre, mutuellement disponibles et plus générales (c'est-à-dire au-delà de la compétence professionnelle) pour permettre la critique." [3] Cela signifie que les formels visent également Analyse conceptuelle de ses origines sur l'interdisciplinarité et le contrôle démocratique de la recherche. [4]Ainsi, l'analyse conceptuelle formelle, depuis ses origines, vise l'interdisciplinarité et le contrôle démocratique de la recherche. [4]Ainsi, l'analyse conceptuelle formelle, depuis ses origines, vise l'interdisciplinarité et le contrôle démocratique de la recherche. [4]pdf | title = Exploration des attributs des processus de régulation des gènes | titelerg = Thèse de doctorat, Université d'Iéna 2011 | hrsg = Bibliothèque numérique de Thuringe | pages = 9 | accès = 2015-11-14 | format = PDF; 4,6 Mo | language = de}} </ref>pdf | title = Exploration des attributs des processus de régulation des gènes | titelerg = Thèse de doctorat, Université d'Iéna 2011 | hrsg = Bibliothèque numérique de Thuringe | pages = 9 | accès = 2015-11-14 | format = PDF; 4,6 Mo | language = de}} </ref>

Alors qu'un terme dans Logique formelle est réduit à sa portée comme un seul chiffre Prédicat, l'analyse conceptuelle formelle rend la théorie conceptuelle moins abstraite à nouveau en considérant le contenu conceptuel. <Nom de référence = "restructuration" /> L'analyse conceptuelle formelle est basée sur les catégories Extension et Intension de Linguistique et la classique logique conceptuelle.

La clarté des termes est recherchée dans le sens de la maxime pragmatique de Charles S. Peirce en dévoilant les propriétés élémentaires observables des objets subsumés. "AttrExGeneRegProc" /> Dans sa dernière philosophie, Peirce a supposé que la pensée logique vise à saisir la réalité à travers le concept en trois étapes, jugement et conclusion . Les mathématiques résument la pensée logique, développent des formes possible réalité et peuvent donc soutenir communication rationnelle. Dans ce contexte, Rudolf Wille définit: Template:Citation

Historiquement, cependant, les projets de développement de langages analytiques planifiés reposaient sur une motivation comparable, cf. aussi langage universel.

Exemple

L'exemple délibérément petit qui suit sert à expliquer les bases de l'analyse de concept formelle. Il fait partie d'une étude de champ de mots plus approfondie dans laquelle les eaux ont été introduites dans un système utilisant des caractéristiques. [5] Exemple quelque peu réduit.

En plus du tableau, le graphique qui peut être construit à partir de celui-ci, le `` diagramme linéaire , est illustré ci-dessous.

+ Exemple de contexte formel: "eaux" - Des eaux fonctionnalités - temporaire couramment Naturellement debout constant maritime - G
e
g
e
n
s
t
ä
n
d
e
'Bach' X X X - 'Rivière' X X X - 'Haff' X X X X - ' Canal' X X - ' piscine' X X X - ' Pfuhl' X X X - 'Flaque' X X X - 'Trickle' X X X - ' ruisseau' X X X - 'Maar' X X X - 'Mer' X X X X - 'Voir' X X X - 'Étang' ' X X X - 'Tümpel' X X X - ' étang' X X -
 <! - Pour que le graphique soit à mi-hauteur de la table ->

mini | Diagramme linéaire selon le tableau Waters à gauche. Template:Paragraphe

données de sortie sous forme de tableau

Pour une analyse, les données à examiner doivent être sous forme de tableau ou être converties en un tel formulaire.

Dans le tableau Exemple de contexte formel: "Eaux" , différents types d'eau sont répertoriés dans les rangées comme objets formels . Les «caractéristiques formelles» associées déterminent les colonnes de ce tableau.

Si un objet a une certaine caractéristique, il y a un marquage, généralement un "X", dans la ligne et la colonne respectives au point de croisement. S'il n'a pas cette caractéristique ou s'il n'est pas clair s'il a cette caractéristique, alors ce marquage est manquant.

Monde réel et structures formelles

Si l'on veut souligner la différence entre les objets et caractéristiques réels d'une part et leurs abstractions (les données du tableau) d'autre part, on parle des abstractions des `` objets formels et des `` caractéristiques formelles . De même, on parle d'un «contexte formel» pour l'ensemble du tableau. Plus tard, des «termes formels» seront introduits plus en détail.

Souvent, les «objets formels» correspondent à des objets réels du monde et les «caractéristiques formelles» correspondent à leurs propriétés qualitatives ou quantitatives réelles. Cependant, un objet formel peut également représenter un résumé - comme les types d'eau dans l'exemple ci-dessus. Une caractéristique formelle peut également représenter un résumé.

graphique linéaire

Le graphique linéaire ci-dessus contient des cercles et des lignes de connexion. Les cercles représentent des termes formels, la hiérarchie peut être lue à partir des lignes.

Avec l'étiquetage réduit utilisé ici, chaque nom d'élément et d'entité est entré exactement une fois dans le diagramme, avec les éléments ci-dessous et les caractéristiques au-dessus des cercles de concept. Cela se fait de telle manière qu'une fonctionnalité peut être atteinte à partir d'un élément via une ligne ascendante si et seulement si l'élément possède la fonctionnalité.

Dans le diagramme illustré, par ex. B. l'objet étang les caractéristiques debout et constant , mais pas les caractéristiques temporaire, naturel, coulant et maritime . En conséquence, «piscine» et «flaque» ont exactement les caractéristiques «temporaire, debout» et «naturel».

La portée et le contenu de chaque terme peuvent être lus à partir du diagramme linéaire. La portée d'un concept se compose des objets, dont une ligne ascendante de lignes mène au cercle du concept. Le terme qui se trouve immédiatement à gauche de Weiher dans le diagramme a le contenu debout et naturel et la portée piscine, flaque, flaque d'eau, maar, lac, étang, étang, lagune et mer .

Bases mathématiques

Les associations de termes sont bien adaptées pour organiser et présenter des données de manière à ce qu'elles puissent être facilement comprises même sans formation mathématique préalable. Les bases mathématiques doivent être brièvement décrites ici.

Contextes formels et termes formels

Il existe deux ensembles <math> G, \, M </math> et un relation <math> I \ subseteq G \ times M </math>. Le triple <math> \ mathbb {K} = (G, M, I) </math> est alors utilisé comme contexte formel [6], <math> G </math> comme son ensemble d'éléments et <math> M </math> comme son ensemble de fonctionnalités ; pour un objet <math> g \ in G </math> et une caractéristique <math> m \ in M ​​</math> signifie <math> (g, m) \ in I </math>"L'élément <math> g </math> a la caractéristique <math> m </math>". Souvent, <math> g \ mathrel {I} m </math> est également écrit en I </math> au lieu de <math> (g, m) \. L'ensemble <math> I </math> est appelé la "relation d'incidence" du contexte formel.

Si les ensembles <math> G </math> et <math> M </math> sont finis, les contextes formels peuvent être bien représentés sous la forme de "tableaux croisés". Il convient de noter que les objets et les caractéristiques de cette représentation peuvent être commandés arbitrairement. Cet ordre ne fait alors pas partie du contexte formel, mais seulement de sa représentation.

<! - mini | 200px | Un contexte formel pour les propriétés des nombres 1-10. -> Template:Anchor Si <math> A \ subseteq G </math> est un ensemble d'objets d'un contexte formel <math> \ mathbb {K} = (G, M, I) </math>, cela s'appelle Avec

<math> A ': = \ {\, m \ in M ​​\ mid \ forall g \ in A: g \ mathrel {I} m \, \} </math>

l'ensemble des caractéristiques communes des éléments dans <math> A </math>. L'ensemble est défini en conséquence pour un ensemble de <math> B \ subseteq M </math> de caractéristiques de <math> \ mathbb {K} = (G, M, I) </math>

<math> B ': = \ {\, g \ in G \ mid \ forall m \ in B: g \ mathrel {I} m \, \} </math>

tous les objets qui ont toutes les caractéristiques de <math> B </math>. Les ensembles <math> A '</math> et <math> B' </math> sont appelés les dérivés des ensembles correspondants <math> A </math> et <math> B </math> et les fonctions, toutes deux nommées avec <math> (\ cdot) '</math>, appelées' 'opérateurs de dérivation' 'par <math> \ mathbb {K} </math>.

Les opérateurs de dérivation ont un certain nombre de propriétés très basiques. Si <math> A, \, A_1, \, A_2 </math> sont des ensembles d'objets et <math> B, \, B_1, \, B_2 </math> sont des ensembles de caractéristiques, ce qui suit s'applique

  • <math> A_1 \ subseteq A_2 \, \ implique \, A_2 '\ subseteq A_1' </math> et double <math> B_1 \ subseteq B_2 \, \ implique \, B_2 '\ subseteq B_1' </math>,
  • <math> A \ subseteq A </math> et double <math> B \ subseteq B </math>,
  • <math> A '= A' </math> et <math> B '= B' </math>,
  • <math> A \ subseteq B '\ iff A' \ supseteq B </math>.

En fait, les opérateurs de dérivation définissent ainsi une connexion Galois antitone entre les associations power set de l'ensemble d'objets et de l'ensemble de fonctionnalités. Inversement, une telle connexion galoisienne entre les ensembles de puissance peut être représentée comme une paire d'opérateurs dérivés d'un contexte formel.

Pour un contexte formel <math> \ mathbb {K} </math> une paire <math> (A, B) </math> est maintenant appelée un terme formel [6] par < math> \ mathbb {K} </math>, si

  • <math> Un </math> est un ensemble d'éléments de <math> \ mathbb {K} </math>,
  • <math> B </math> est un ensemble de fonctionnalités de <math> \ mathbb {K} </math>,
  • <math> A '= B </math> et
  • <math> B '= A </math> s'applique.

L'ensemble <math> A </math> est alors appelé scope et l'ensemble <math> B </math> content du terme <math> (A, B) </math>. L'ensemble de tous les termes est indiqué par <math> \ mathfrak {B} (\ mathbb {K}) </math>. Si les contextes formels sont représentés sous forme de tableaux croisés, les termes formels - avec un ordre approprié d'objets et de caractéristiques - peuvent être compris comme des `` rectangles maximum complètement remplis dans ce tableau croisé.

Si <math> (A, B), (C, D) \ in \ mathfrak {B} (\ mathbb {K}) </math>, vous pouvez utiliser

<math> (A, B) \ le (C, D) \, \ Leftrightarrow \, A \ subseteq C </math>

définir un semi-ordre sur <math> \ mathfrak {B} (\ mathbb {K}) </math>. Cet ordre fait alors de la structure <math> (\ mathfrak {B} (\ mathbb {K}), \ le) </math> une association complète. En fait, à l'inverse, selon le principe de l'analyse formelle de concept, chaque association complète est d'ordre isomorphe à une association de concept.

<! - mini | Association de termes pour le contexte numérique ci-dessus. -> Les associations de termes peuvent être représentées comme diagramme de commande e (diagrammes linéaires) et ainsi déplier les données dans leur structure et leur contexte. Les objets ont toutes les caractéristiques au-dessus d'eux (reliés par des bords); Dans l'exemple ci-contre, 4 est droit, composé et carré.

L'étiquetage simplifié des associations de termes peut être justifié mathématiquement plus précisément. Si l'on considère pour un objet <math> g \ in G </math> l'ensemble de tous les termes que <math> g </math> a dans leur portée, alors cet ensemble a un filtre principal dans le terme association. Par conséquent, seul ci-dessous le plus petit terme, qui contient <math> g </math> dans la portée, le sujet <math> g </math> est noté. Le double «au-dessus» du terme le plus grand qui a un contenu <math> m \ in M ​​</math> donné est noté dans la caractéristique <math> m </math>. Un terme dans le diagramme de commande a un objet dans sa portée si et seulement s'il se trouve au-dessus du terme,qui est étiqueté avec l'article. Par conséquent, un terme dans le diagramme de commande a une caractéristique dans son contenu s'il se trouve en dessous du terme étiqueté avec la caractéristique.

clause principale de l'analyse conceptuelle formelle

Soit <math> \ mathbb {K} = (G, M, I) </math> un contexte formel et <math> \ underline {\ mathfrak {B}} (\ mathbb {K}) </math> Association à terme. Vous pouvez ensuite utiliser les termes <math> g \ in G </math> et les caractéristiques <math> m \ in M ​​</math>

<math> \ gamma (g) = (\ {\, g \, \} , \ {\, g \, \} '), </math>
<math> \ mu (m) = (\ {\, m \, \} ', \ {\, m \, \}' ') </math>

considérer. Il devient <math> \ gamma (g) </math> le concept d'objet de <math> g </math> et <math> \ mu (m) </math> le concept de caractéristiques de <math> m </math> . S'applique toujours

<math> g \ mathrel {I} m \ iff \ gamma (g) \ le \ mu (m) </math>

Si <math> \ underline {L} = (L, \ le_L) </math> est une union complète, alors <math> \ underline {L} </math> est isomorphe à <math> \ underline {\ mathfrak {B}} (\ mathbb {K}) </math>, s'il y a des chiffres <math> \ gamma _ {\ underline {L}} \ colon G \ to L, \ mu _ {\ underline {L}} \ colon M \ to L </math> donne tel que

<math> g \ mathrel {I} m \ iff \ gamma _ {\ underline {L}} (g) \ le \ mu _ {\ underline {L}} (m) </math>

s'applique. En particulier, <math> \ underline {L} </math> est isomorphe à <math> \ underline {\ mathfrak {B}} (L, L, \ le_L) </math>.

La clause principale est également connue sous le nom de `` clause principale de Rudolf Wille sur les associations de termes . Il indique, entre autres, que chaque association complète d'une association de termes est isomorphe. Cite error: Closing </ref> missing for <ref> tag. L'ensemble de toutes les implications de <math> \ mathbb {K} </math> fermé dans ce nouveau sens est un Theory,car, selon la construction, il s'agit aussi, par exemple, du contexte sous-jacent réalisable.

La base est appelée "irredundant" si elle est <math> \ subseteq </math> -minimal avec cette propriété. Un exemple de base non redondante est la «base canonique» (voir aussi Exploration d'entités), qui a également la propriété d'être minimale en termes de taille de la base.

Il considère qu'un ensemble <math> \ mathcal {L} </math> d'implications est la base d'un contexte <math> \ mathbb {K} </math> si et seulement si l'ensemble de ceux sous <math> \ mathcal {L} </math> les quantités terminées correspondent exactement au contenu de <math> \ mathbb {K} </math>.

Exploration des fonctionnalités

Template:Article principal

Il est possible de présenter la théorie de l'implication d'un certain sujet à l'aide d'un contexte formel. Cela signifie notamment que cela peut se faire à l'aide d'un nombre suffisant d'exemples, qui deviennent alors les objets du contexte formel. En théorie, un tel ensemble d'exemples peut être donné par un expert humain ou une machine.

Le problème se pose cependant qu'il n'est ni garanti d'emblée qu'un nombre suffisant d'exemples est donné, ni que certains exemples générés sont redondants, car des exemples déjà donnés sont suffisants. Il s'agit d'un problème grave du point de vue de la difficulté à générer de bons exemples, à interroger des experts ou même de nouvelles expériences, et la recherche de littérature ou d'algorithmes peut s'avérer complexe.

L'algorithme d'exploration des fonctionnalités peut aider ici. Sur la base d'un ensemble connu d'implications et d'un ensemble connu d'exemples du domaine, l'algorithme suggère des implications qui peuvent ensuite être acceptées ou rejetées par un expert (humain ou non). Une implication doit être acceptée si et seulement si elle est valable dans le domaine. Si une implication est rejetée, l'expert doit créer un contre-exemple, qui peut ensuite être accepté ou rejeté par un expert (humain ou non). Une implication doit être acceptée si et seulement si elle est valable dans le domaine. Par un contre-exemple accepté,l'implication est réfutée et le plus petit ensemble possible d'implications acceptées est généré, ce qui en fin de compte décrit complètement le sujet. De plus, l'ensemble d'exemples est également complété.

Expérience d'application avec l'analyse de concept formelle

L'analyse conceptuelle formelle peut être utilisée comme méthode qualitative pour l'analyse des données. Depuis les débuts de l'analyse de concept formelle au début des années 1980, le groupe de recherche sur l'analyse de concept formelle de TU Darmstadt a acquis l'expérience de plus de 200 projets dans lesquels une analyse de concept formelle a été utilisée (statut 2005). [7]Y compris dans les domaines: Médecine et Biologie cellulaire, [8] [9] Génétique, [10] [11] [[Écologie] ], [12] génie logiciel, [13] Ontology (IT)]] < ref> Template:Literature </ref>, Information - et Library Studies en, < ref> Template:Literature </ref> [14] [15] organisation du bureau, [16] loi, [17] [18] Linguistique, [19] Science politique en. [20]New York | Date = 2000 | ISBN = 978-3-540-66391-1 | Pages = 325-340}} </ref>New York | Date = 2000 | ISBN = 978-3-540-66391-1 | Pages = 325-340}} </ref>

De nombreux autres exemples d'application sont par exemple B. décrit dans: Analyse formelle du concept. Fondations et applications , [7] les volumes de conférence pour les Conférences régulières, tels que: Conférence internationale sur l'analyse formelle des concepts (ICFCA), [21] Concept Lattices and their Applications (CLA) [22] ou Conférence internationale sur les structures conceptuelles (ICCS). [23]htm | title = Conférences internationales sur les structures conceptuelles - Conférences et ateliers | hrsg = Université d'État du Nouveau-Mexique | access = 2016-02-14 | language = de}} </ref>htm | title = Conférences internationales sur les structures conceptuelles - Conférences et ateliers | hrsg = Université d'État du Nouveau-Mexique | access = 2016-02-14 | language = de}} </ref>

Littérature

  Eds = Bernhard Ganter, Gerd Stumme, Rudolf Wille
  | Titre = Analyse formelle du concept. Fondations et applications
  | Éditeur = Springer
  | Date = 2005
  | ISBN = 3-540-27891-5
  | En ligne = preview}}

liens web

preuves individuelles et commentaires

<références />

Catégorie: Algèbre Catégorie: Logique mathématique Catégorie: Théorie des ordres Catégorie: Ontologie Catégorie: Intelligence artificielle Catégorie: Business Intelligence
Cite error: <ref> tags exist, but no <references/> tag was found