Oracle-based Lattice Construction

L'extraction de concepts par treillis de Galois sur les relations binaires peut être vu comme une spécialisation d'une procédure d'élaboration des intents et extents plus générale.

Les Données en Entrée

Relation Binaire

Lorsqu'on traite un contexte binaire, chaque objet est décrit par la liste de ses attributs, soit sous forme de liste, soit sous forme d'un vecteur binaire ou logique indiquant pour chaque attribut présence ou absence. Les opérations de fermeture sont intersection pour les intentions et union pour les extensions.

Relation Multi-Valuée

Lorsqu'on traite un contexte multi-valué, chaque objet est décrit par la modalité de chaque attribut qui lui correspond. Une description est donc un vecteur de modalités, ou une liste de couples attribut-modalité. Souvent, le traitement est réalisé par “scaling” où chaque attribut est transformé en autant de attribut-modalité qu'il a de modalité, et la modalité que possède un objet est signifiée par un '1' dans la colonne attribut-modalité correspondant. Le contexte est ensuite traité comme un contexte binaire.

Relation Histogramme

Lorsqu'on traite un context multi-valué flou, un objet est décrit par une liste de couples (modalité,affinité) pour chaque attribut (ou trait). Ceci peut être structuré comme un contexte multi-valué après scaling, mais avec plusieurs poids répartis sur les attribut-modalité d'un attribut au lieu d'un seul '1' et des '0' sur les autres modalités. Cependant, la structure des données en entrée sera différente car il faut indiquer les poids sur chaque modalité au lieu de prendre '1' (ou 100%) implicitement pour la modalité indiquée dans le cas d'une relation multi-valuée “normale.” Il faut donc définir un format de fichier adéquat. Qui plus est, on peut imaginer que tous les attributs n'auront pas le même nombre de modalités, au quel cas il faudrait aussi passer l'information “nombre de modalités.” Hormis un format XML, on pourrait utiliser soit un un format de ce type (avec une ligne par attribut dans un bloc par objet) :

object_name_1
aff_1_1 aff_1_2 aff_1_3 aff_1_4          // les poids des affinités pour les quatre modalités du premier attribut
aff_2_1 aff_2_2 aff_2_3  ....aff_2_10    // les poids des affinités pour les 10 modalités du second attribut
...
aff_k_1                                  // présence ou absence du k-ième attribut
                                         // ligne vide entre deux objets pour lisibilité (sinon, on compte les attributs)
object_name_2                            // début objet suivant

soit grouper par une (ou des) symbole (“démarquer”)

object_name_1 {aff_1_1 aff_1_2 aff_1_3 aff_1_4} { aff_2_1 aff_2_2 aff_2_3  ....aff_2_10} ...{aff_k_1 }

object_name_1 aff_1_1 aff_1_2 aff_1_3 aff_1_4 | aff_2_1 aff_2_2 aff_2_3  ....aff_2_10 | ... | {aff_k_1 }

L'opérateur de fermeture à utiliser en premier pour les histogrammes est min-max, qui établit l'enveloppe dans laquelle un histogramme doit rentrer pour que son objet appartienne à l'extension (étendu). Dans une algorithme incrémental comme CbO, on commence avec un premier objet, on ferme son intention (qui ne change rien, min et max pour chaque modalité seront sa valeur pour la modalité), puis ferme l'extension de cette intention : on trouve d'éventuels autres objets qui sont identiques. Ensuite, on étend l'extension avec l'objet le plus proche qui n'est pas encore dans l'extension : on élargit l'intention , puis intègre à l'extension les objets nouvellement qualifiés. Mais on peut vouloir ne pas trop élargir les intentions pour ne s'intéresser qu'aux concepts pas trop généraux, d'où l'idée de contraindre l'élargissement des intentions avec des seuils.

Une intention (pour un attribut histogramme) aurait la forme

max 10 20 30 20 40
min 0 10 10 0 20

Le seuil peut être appliqué modalité par modalité, mais il peut aussi être appliqué à la somme des largeurs sur les modalités d'un attribut ou au maximum de celles-ci (ou les deux, pas forcément avec deux mêmes valeurs du seuil).

1)

Mes Questions

  • s'agit-il de traiter une seule nouvelle connexion de Galois (min-max) ou de réaliser un développement plus générique, permettant de rajouter d'autres relations par la suite? A priori ça ne change pas fondamentalement l'architecture du traitement, mais il faudrait prévoir (ou pas) un mécanisme de sélection.
    • FLB : au-delà de la connexion min-max, vous pouvez prévoir un format général, en vous appuyant sur le modèle de 'pattern structure' de Ganter et Kuznetsov (papier à demander à Aurélie, si vous ne l'avez déjà).
  • quel format (ou quels formats) de données de contextes à pouvoir traiter (format d'entrée des données) ?
    • FLB : pour les formats, à discuter, xml, ou voir le(s) format(s) de Coron (site http://coron.loria.fr)
    • AB : généralement csv, rcf, sortie en dot (mais c'est moche)
  • y a-t-il un format “standard” pour des données de type histogramme?
    • AB : Jusqu'ici une lettre pour identifier le trait et les pourcentages des modalités.
  • la démarcation entre histogrammes a-t-elle une importance?
    • FLB : je ne comprends pas la question
    • AB : tant qu'on ne seuille pas les différences entre min et max, en nous basant sur la variance au niveau du trait, non. On peut alors considerer l'intension comme un tableau d'affinités successives sans démarcation. Nous allons nous orienter cependant vers un seuillage.
  • peut-il y avoir des attributs d'autres types (binaires) à traiter par les opérations classiques (intersection des attributs binaires) dans le même lot? ça pourrait marcher, l'extension contiendrait les objets dont les histogrammes rentrent dans les tranches s'ils ont les attributs binaires aussi. Est-ce que je me trompe? Est-ce un traitement qui aurait un sens, qui serait utile?
    • FLB : pour le moment on se limite à un type, quitte à intégrer des attributs de type binaire dans un formalisme plus spécifique.
    • AB : Si les affinités 0 ou 1 c'est une coincidence dont on a pas besoin de tenir compte pour

etre du binaire.

  • seuillage du support d'un concept : faut-il le prévoir en option?
    • FLB : oui, il faut prévoir de tester la distance min-max par rapport à un seuil donné afin d'éliminer ces concepts trop 'larges'.
    • AB : On peut, ou alors si y a une sortie de type csv, on fera le tri de ce qu'on veut garder dans un tableur.
  • construction du treillis (graphe de Hasse) : intégrée à l'extraction de concepts ou par un traitement distinct a posteriori?
    • FLB : à voir en fonction de l'algo choisi. pour notre problème le graphe n'est pas forcément nécessaire.
    • AB : Le diagramme nous importe peu. Et ralenti les traitements. Sauf si la construction permet de le construire au fur et à mesure.
1) En algèbre linéaire, on juge la similarité de deux vecteurs en calculant leur projection : pourrait-on faire un calcul analogue entre un histogramme et l'intention à priori?
 
java/nary.txt · Dernière modification: 2010/02/18 13:32 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki