Les deux principes majeurs de CbO sont :
Utiliser chaque instance (objet) comme “graine” pour engendrer une suite de sous-ensembles le contenant, en ajoutant un par un des objets qui ne sont pas encore dans l'extension (fermeture par rapport à l'intention), tant que l'intention reste non-nulle. Ceci se fait par le développement récursif en profondeur d'abord.
Rajouter des objets “lexicographiquement supérieurs” seulement, pour pouvoir repérer une extension qui aurait déjà été engendré puisqu'elle contient un objet lexicographiquement inférieur à l'objet courant.
Donc, on commence par fermer l'extension par rapport à l'intention d'un objet (le plus petit). Si cela n'ajoute pas d'éléments déjà traités, on a un nouveau concept, qu'on rajoute au treillis. S'il reste des objets lexicographiquement plus fort dans le complémentaire de l'extension, on prend le premier et tente de l'ajouter à l'extension : intersection des intentions, puis fermeture de l'extension, et là on vérifie de nouveau qu'on a un nouveau concept par l'absence d'objet lexico. inférieur. En cas de succès (nouveau concept) on poursuit l'élargissement de l'extension dans cette branche, et ainsi de suite. Quand une branche est terminée, on passe à la suivante en prenant le prochain objet lexicographiquement plus fort dans le complémentaire de l'extension, jusqu'à épuisement.
Pour voir comment ça marche, nous allons le dérouler sur un petit exemple bien connu : les entiers de 1 à 10, et cinq propriétés :
“c” composé (ou produit)
“e” paire (“even”)
“o” impaire (“odd”)
“p” premier (“prime”)
“s” carré (“square”)
Objet | “c”
(composite) | “e”
(paire) | “o”
(impaire) | “p”
(premier) | “s”
(carré) |
1 | | | 1 | | 1 |
2 | | 1 | 0 | | |
3 | | | 1 | 1 | |
4 | 1 | 1 | | | 1 |
5 | | | 1 | 1 | |
6 | 1 | 1 | | | |
7 | | | 1 | 1 | |
8 | 1 | 1 | | | |
9 | 1 | | 1 | | 1 |
10 | 1 | 1 | | | |
Pour avoir un ordre “lexicographique”, le tableau d'entrées est ensuite trié (comme si le bloc des attributs était un nombre binaire dans le sens usuel).
Objet | “c”
(composite) | “e”
(paire) | “o”
(impaire) | “p”
(premier) | “s”
(carré) |
1 | | | 1 | | 1 |
3 | | | 1 | 1 | |
5 | | | 1 | 1 | |
7 | | | 1 | 1 | |
2 | | 1 | | 1 | |
9 | 1 | | 1 | | 1 |
6 | 1 | 1 | | | |
8 | 1 | 1 | | | |
10 | 1 | 1 | | | |
4 | 1 | 1 | | | 1 |
On déroulera successivement les appels suivants, qui lanceront des parties de la construction de l'arborescence des sous-ensembles avec un nombre croissant d'éléments à partir de chacun de ces noyaux (graines) :
Traiter {1}, [ o, s]
Traiter {3}, [ o, p]
Traiter {5}, [ o, p]
Traiter {7}, [ o, p]
Traiter {2}, [ e, p]
Traiter {9}, [ c, o, s]
Traiter {8}, [ C, e]
Traiter {6}, [ c, e]
Traiter {10}, [ c, e]
Traiter {4}, [ c, e, s]
Chaque fois qu'on retrouvera des éléments lexicographiquement inférieur lorsqu'on ferme, on saura que le concept a déjà été engendré à partir de cette graine lexicographiquement inférieur et on arretera le développement de cette branche.
C = fermeture{3} = {3, 5, 7 }
D = [ o, p ]
aucun des éléments {5, 7} n'est lexicographiquement inférieur à 3, donc on
rajoute le concept ({3,5,7}, [o, p] ) au treillis
poursuit le développement en faisant des appels récursifs avec, successivement, 2, 9, 6, 10, 4 comme élément complémentaire.
pour {2}
Z = {3, 5, 7, 2}
Y = [ o, p] ∩ [e, p] = [ p ]
X = Z = {3, 5, 7, 2}
Traiter ({3, 5, 7, 2}, [e, p], ({3, 5, 7, 2},[ p ]) )
rajouter le concept ({3, 5, 7, 2},[ p ]) au treillis
essayer d'aller plus loin avec 9, 6, 10, 4 : pas possible
Branche morte : déjà engendrée par la fermeture de {3}, se qui se repère par la présence de {3} dans la fermeture.
Branche morte : déjà engendrée par la fermeture de {3}, se qui se repère par la présence de {3} dans la fermeture.
C = { 2 }
D = [ e, p]
Rajouter ({2 }, [ e, p]) au treillis
Essayer d'étendre avec 9, 6, 8, 10, 4 :
D = [ c, o, s]
C = { 9 }
Rajouter le concept ({ 9 }, [ c, o, s] ) au treillis
Essayer d'étendre avec 6, 8, 10, 4 :
Pour 6
Z = { 9, 6 }
Y = [ c, o, s ] ∩ [ c, e] = [ c ]
X = { 9, 6, 8, 10, 4 }
Traiter ({ 9, 6 }, [ c, e], ( { 9, 6, 8, 10, 4 }, [ c ] ))
8, 10 et 4 sont lexicographiquement supérieur à 9 : rajouter le concept “composé” ( { 9, 6, 8, 10, 4 }, [ c ] ) au treillis.
Pour 8
Z = { 9, 8}
Y = [ c, o, s ] ∩ [ c, e] = [ c ]
X = { 9, 6, 8, 10, 4 } contient un élément lexicographiquement inférieur à 8
Pour 10
Z = { 9, 10}
Y = [ c, o, s ] ∩ [ c, e] = [ c ]
X = { 9, 6, 8, 10, 4 } contient un élément lexicographiquement inférieur à 10
Pour 4
Z = { 9, 4}
Y = [ c, o, s ] ∩ [ c, e, s] = [ c, s ]
X = { 9, 4 }
Traiter ({ 9, 4}, [ c, e, s] ({ 9, 4 }, [ c, s ] ) )
Rajouter le concept ({ 9, 4 }, [ c, s ] ) au treillis
Fin de la branche : 4 est lexicographiquement maximal
D = [c, e]
C = D' = {6, 8, 10, 4 }
Nouveau concept:
Rajouter ({6, 8, 10, 4}, [ c, e ] ) au treillis
Chercher à prolonger avec rien, il ne reste plus d'objet lexicographiquement supérieurs dans le complémentaire.
D = [ c, e, s]
C = D' = { 4 }
Rajouter le concept ({ 4 }, [ c, e, s]) au treillis.
Arrêter : 4 est l'objet maximal, il ne reste plus de candidats pour intégrer l'extension.
( {1, 9}, [ o, s])
( {1, 9, 3, 5, 7 },[ O ] )
( {1, 9, 4}, [ s ] )
( {3, 5, 7}, [o, p] )
( {3, 5, 7, 2}, [ p ])
( {2 }, [ e, p])
( {2, 6, 8, 10, 4},[ e ] )
( {9 }, [ c, o, s] )
( {9, 6, 8, 10, 4 }, [ c ] )
( {9, 4 }, [ c, s ] )
( {6, 8, 10, 4}, [ c, e ] )
( {4 }, [ c, e, s] )
This is a file from the Wikimedia Commons.