Table des matières
Close by One
Algorithme développé et décrit par Kuznetsov dans "Comparing performance of algorithms for generating concept lattices"(2002) par Sergei O. Kuznetsov et Sergei A. Obiedkov:
Pseudocode
- Close by One
- L := \emptyset
- For each g \in G
- Process \left( \left\{ g \right\} ,g ,\left( \left\{ g \right\}^{' '} ,g \right) \right)
- L is the concept set.
- Process (A, g, (C, D))
- \left\{ C = A \prime\prime ; D = A \prime \right\}
- If \left\{h| h \in C\setminus A \quad\& \quad h \prec g\right\} = \emptyset
- L := L \cup \left\{\left(C,D\right)\right\}
- For each f \in\left\{h | h \in G \quad \& \quad g \prec h \right\}
- Z := C \cup \left\{f\right\}
- Y := D \cap \left\{f\right\}\prime
- X := Y\prime\left(=Z\cup \left\{h | h\in G\setminus Z\quad\&\quad Y \subseteq \left\{h\right\}\prime\right\}\right)
- Process \left(Z; f; \left(X; Y\right)\right)
Application à un petit exemple
Explication du traitement
| Close by One | Commentaires |
|---|---|
| L := \emptyset | Initialement, on n'a aucun concept. |
| For each g \in G | L'algorithme va utiliser successivement chaque objet comme “graine” puis explorer les possibilités d'agrandir l'extension qu'il engendre par le rajout d'un objet lexicographiquement supérieur. |
| Process ( \left\{ g \right\},g ,\left( \left\{ g \right\}^{' '} ,g \right) ) | \left( \left\{ g \right\}^{' '} ,g \right) est le concept dont l'intention correspond aux attributs de g, et \left\{ g \right\}^{' '} est l'extension fermée correspondante. |
| L is the concept set. | On a élaboré toutes les extensions. |
| Maintenant, voyons comment l'exploration et le développement incrémental sont réalisés | |
| Process (A, g, (C, D)) | |
| \left\{ C = A \prime\prime ; D = A \prime \right\} | En fait, ceci est pour rappel, il ne s'agit pas d'un nouveau calcul à l'entrée de la fonction. |
| If \left\{h| h \in C\setminus A \quad\& \quad h \prec g\right\} = \emptyset | Vérification qu'il s'agit d'un nouveau concept et non d'un concept déjà élaboré, ce qui se repèrerait par la présence dans l'extension C d'objet(s) de valeur lexicographique inférieur à l'objet courant, et qui n'étai(en)t pas déjà dans l'extension A (de l'intention précédente). Si c'est un concept déjà vu, on ne fait rien, on ne l'ajoute pas à L et on ne poursuit pas le développement de la branche. |
| L := L \cup \left\{\left(C,D\right)\right\} | On ajoute le nouveau concept. |
| For each f \in\left\{h | h \in G \quad \& \quad g \prec h \right\} | On cherche à agrandir l'extension(C) en rajoutant un objet du complémentaire de valeur lexicographique supérieur. |
| Z := C \cup \left\{f\right\} | On ajoute l'objet candidat à l'extension. |
| Y := D \cap \left\{f\right\}\prime | On calcule la nouvelle intention. |
| X := Y\prime\left(=Z\cup \left\{h | h\in G\setminus Z\quad\&\quad Y \subseteq \left\{h\right\}\prime\right\}\right) | On ferme l'extension par rapport à l'intention nouvelle. |
| Process \left(Z; f; \left(X; Y\right)\right) | On l'envoye au traitement : tester s'il s'agit d'un nouveau concept 1), puis si oui, - l'ajouter au treillis et -poursuivre les tentatives d'agrandissement, toujours par un objet de valeur lexicographique plus grande. |
Commentaires
- “L'algorithme CbO obtient chaque nouvelle fermeture à partir d'un concept qu'il a généré précedemment en calculant l'intersection de son intention avec l'intention d'un objet n'appartenant pas à son extension”.
- “Il y a deux stratégies pour l'utilisation d'une pile; CbO emploie la seconde :
- d'abord, choisir g et l'ensemble B à considérer prochainement, puis rechercher dans la pile un concept qui pourrait servir à générer la nouvelle intention;
- rechercher dans la pile un concept qui pourrait servir à générer la nouvelle intention, et ensuite choisir l'objet g et l'ensemble à considérer prochainement.
- Pour CbO, un ensemble dont la fermeture est calculée lors d'une étape ne peut pas être décrit par les formules (1) et (2)
2): il est égale à l'extension d'un concept engendré augmenté d'un objet. - Ici nous présentons la version récursive de CbO la plus simple. Il calcule des concepts selon l'ordre lexicographique défini sur les sous-ensembles de G (concepts ayant les extension lexicographiquement les plus faibles sont engendrés en premiers).
- A est lexicographiquement inférieur à B
- si A\subset B,
- ou \left[\left(B \cap A\right)\neq B\right] \rightarrow \left[A=B\right] (B n'est pas un sous-ensemble propre de A) et \min\left(\left(A\cup B\right)\setminus \left(B\cap A\right)\right)\in A
- L'ordre dans lequel les concepts sont engendrés par CbO semble préférable à celui de NextClosure si le graphe 3) est construit. The first generation of the concept is always canonical, which makes it possible to find a concept in the tree when it is generated for a second time and to draw appropriate diagram graph edges.
- Pour construire le graphe avec CbO, nous pouvons employer un arbre. Mais contrairement à l'arbre dans l'algorithme Bordat, cet arbre ne fait pas partie du graphe. Supposons que les fils d'un noeud sont ordonnés selon l'ordre lexicographique. Un chemin dans l'arbre est une séquence de ses noeuds depuis la racine telle que tout noeud est suivi par soit son fils (un de ses fils?) soit par son frère droit.4) La longueur d'un tel chemin est borné par |G|+1. Le graphe peut être construit de la manière suivante :
- chaque fois qu'un concept est engendré “non-canonically”, l'algorithme recherche dans l'arbre “the canonical generation of this concept” (ce qui coute un temps linéaire en le nombre d'objets) et l'arête correspondant est rajouté.
- pendant la recherche, nous faisons [faut trouver mieux] le chemin suivant dans l'arbre : le dernier noeud du chemin est le concept désiré; chaque noeud du chemin est soit le premier fils du noeud précédent (si le noeud précédent est un concept moins général que le concept désiré), soit son premier frère droit (sinon).
- La complexité de CbO est O\left( |G|^2 |M| L| \right)
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
