CbO : Déroulement sur un exemple

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”)

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).

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) :

1. Traiter {1}, [ o, s]
2. Traiter {3}, [ o, p]
3. Traiter {5}, [ o, p]
4. Traiter {7}, [ o, p]
5. Traiter {2}, [ e, p]
6. Traiter {9}, [ c, o, s]
7. Traiter {8}, [ C, e]
8. Traiter {6}, [ c, e]
9. Traiter {10}, [ c, e]
10. 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 = D' = { 1, 9}
• D = [ o, s]
• {9} n'est pas lexicographiquement inférieur à {1} donc, on
  • rajoute ({1, 9}, [ o, s]) au treillis
  • poursuit le développement en faisant des appels récursifs avec, successivement, 3, 5, 7, 2, 6, 10, 4 comme élément complémentaire.
    • pour {3}
      • Z = {1, 9, 3}
      • Y = [ o, s] ∩ [o, p] = [ O ]
      • X = {1, 9, 3, 5, 7 } les nombre impaires
      • Traiter ( {1, 9, 3}, [ O , p], ( {1, 9, 3, 5, 7 },[ O ] ))
        • Ajouter ( {1, 9, 3, 5, 7 },[ O ] ) au treillis
        • Ne peut pas aller plus loin (intentions nulles)
    • pour {2}
      • Z = {1, 9, 2}
      • Y = [o, s ] ∩ [e, p] = ∅
    • pour {6}, {10}
      • Y = [o, s] ∩ [e, c] = ∅
    • pour {4}
      • X = { 1, 9, 4}
      • Y = [o, s] ∩ [e, s] = [ s ]
      • Z = { 1, 9, 4}
      • Traiter ({ 1, 9, 4}, [e, s], ({ 1, 9, 4},[ s ] )) :
        • Rajouter ({ 1, 9, 4},[ s ] ) au treillis
        • fin de la branche (4 est maximal)

• 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 :
  • Pour 9
    • Z = { 2, 9 ]
    • Y = [ e, p ] ∩ [ c, o, s] = ∅
  • Pour 6
    • Z = { 2, 6}
    • Y = [ e, p ] ∩ [ c, e ] = [ e ]
    • X = { 2, 6, 8, 10, 4}
    • Traiter ( { 2, 6}, [ c, e] , ({ 2, 6, 8, 10, 4},[ e ] ))
      • Rajouter le concept “paire” ({ 2, 6, 8, 10, 4},[ e ] ) au treillis
  • Pour 8, 10 : même concept “paire” repéré par présence de {6} dans la fermeture
  • Pour 4
    • Z = { 2, 4}
    • Y = [ e, p ] ∩ [ c, e, s ] = [ e ]
    • X = { 2, 6, 8, 10, 4 } : déjà fait

• 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.

• fermeture{ 8 } = { 6, 8, 10, 4 } : déjà traité

• fermeture{ 10 } = { 6, 8, 10, 4 } : déjà traité

• 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. ( {1, 9}, [ o, s])
2. ( {1, 9, 3, 5, 7 },[ O ] )
3. ( {1, 9, 4}, [ s ] )
4. ( {3, 5, 7}, [o, p] )
5. ( {3, 5, 7, 2}, [ p ])
6. ( {2 }, [ e, p])
7. ( {2, 6, 8, 10, 4},[ e ] )
8. ( {9 }, [ c, o, s] )
9. ( {9, 6, 8, 10, 4 }, [ c ] )
10. ( {9, 4 }, [ c, s ] )
11. ( {6, 8, 10, 4}, [ c, e ] )
12. ( {4 }, [ c, e, s] )

This is a file from the Wikimedia Commons.