Point d'ouverture "Index"

separator line

Point d'ouverture précédent white background Point d'ouverture suivant

separator line


Description

Le point d'ouverture Index permet la recherche d'un ensemble de cas suivant une situation. Il permet de définir différents index.


Conception

Un index est un objet qui encapsule une structure de données et une méthode de recherche d'un ensemble de cas sources suivant la situation du cas cible. On propose tout d'abord l'association d'un filtre d'indices à un index permettant ainsi à chaque index de prendre en compte un sous-ensemble d'indices suivant une représentation adaptée. On définit ensuite une hiérarchie extensible d'index mettant l'accent sur la possibilité de concevoir des index composites pour la réalisation de stratégies de recherche complexes. Enfin, on étudie les conditions de composition permettant de garantir la cohérence de la construction d'une telle stratégie.

Plus précisément, un index offre un ensemble d'opérations (indexation ou retrait d'un cas, reconstruction de sa structure interne) et permet notamment la recherche d'un ensemble de cas suivant une situation (méthode searchCases ). Un index offre également un accès direct à la liste des cas qu'il indexe, il est ainsi possible de consulter les propriétés de cette relation (nombre de cas indexés, test d'appartenance).

index et filtre d'indices

Figure 1 : index et filtre d'indices


On introduit la notion de filtre d'indices (classe IndiceFilter ) permettant de modifier l'ensemble des indices pris en compte à partir de la structure générale des situations (cf. Figure 1). Un filtre permet d'effectuer deux types d'opérations (qui peuvent être combinées) sur les indices :

  • sélection d'une sous-partie,
  • transformation de la représentation.

Par exemple, il est possible de concevoir un index n'utilisant que la sous-partie décrivant le design d'une voiture, au lieu de prendre l'ensemble des indices (design, prix et performance). Un index peut également nécessiter de regrouper les indices de manière différente (vecteur à plat par exemple) ou bien d'inclure des indices calculés à partir des indices initiaux. Un filtre permet la construction de cette représentation spécifique. Si cette transformation est coûteuse, elle devra être faite au niveau de la représentation initiale, ainsi la transformation sera réduite à une sélection. Un filtre est utilisé par l'index lors de la recherche ou de l'ajout de cas. Cette conception suit le patron Stratégie , ce qui permet une évolution indépendante des filtres et leur partage entre différents index.

Pour la construction de stratégies complexes de recherche, on propose une hiérarchie extensible d'index pouvant être composés (cf. Figure 2). Dans ce but, on utilise encore une fois le patron de conception Composite : la classe Index est la racine de la hiérarchie d'héritage comportant notamment les index simples (classe SimpleIndex ) et les index composés (classe CompoundIndex ). Grâce à cette modélisation, il est possible d'utiliser l'index adapté à un sous-espace des indices ou aux caractéristiques d'indices spécifiques (notamment les propriétés de leur domaine de valeurs), tout en les combinant pour former une organisation complète. Au sein de cette structure hiérarchique, l'indexation d'un nouveau cas ou la recherche des cas sources sont effectuées suivant un parcours récursif dans lequel chaque index composite contrôle l'exécution.

hiérarchie extensible d'index

Figure 2 : hiérarchie extensible d'index


Les index simples permettent la manipulation d'une seule structure de données, utilisée par une méthode de recherche de cas. Par exemple, dans CBR*Tools , nous offrons quatre index simples :

  • un index de prototypes (classe PrototypeIndex ) : cet index repose sur la définition d'une hiérarchie de prototypes où chaque prototype  définit une fonction de compatibilité. Un prototype est alors relié à un ensemble de cas compatibles. La recherche s'effectue par une opération de classification dans cette hiérarchie, et les identificateurs des prototypes compatibles ainsi que les cas reliés à ces prototypes sont retournés. La représentation des prototypes et le protocole de classification peuvent être spécialisés. Cet index permet de réaliser des arbres discriminants construits a priori ou avec un algorithme d'induction. La compatibilité d'un cas avec un prototype peut être booléenne ou basée sur le calcul d'une similarité,
  • un index à base d'une table de hachage (classe HashtableIndex ) : cet index permet de retrouver un ensemble de cas à partir d'une clef calculée en prenant en compte un sous-ensemble d'indices,
  • un index par plus proches voisins linéaire (K-Nearest Neighbours, classe LinearKnnIndex ) : cet index parcourt un ensemble de cas sources, calcule les similarités entre les situations des cas sources et celle du cas cible. Finalement, les k meilleures situations sont retenues suivant une relation d'ordre définie sur le domaine de valeurs des similarités. Cet index est le plus souple dans son utilisation : il permet de gérer tout domaine de valeurs (y compris avec des valeurs manquantes) du moment qu'une similarité a été définie. Par contre, la complexité de cette recherche est linéaire en fonction du nombre de cas à parcourir, dans la mesure où le calcul des similarités et le nombre d'indices sont négligeables devant le nombre de cas,
  • un index par plus proches voisins optimisé, utilisant des k-d trees (classe KdTreeKnnIndex ) : cet index utilise les relations d'ordre définies sur les domaines de valeurs des indices pour construire un arbre partageant l'espace de recherche en sous-espaces. Le résultat est identique à une recherche linéaire par plus proches voisins, mais certains sous-espaces sont d'office éliminés d'après les propriétés de construction (Wess et al., 1994) . La recherche est alors plus efficace  (complexité moyenne en O(log2 n), où n est le nombre de cas) mais nécessite la construction d'un arbre au préalable (complexité moyenne en O(k n log2 n)).

On peut identifier deux types d'index composés dont le comportement diffère lors de leur utilisation :

  • les index d'embranchement (sous-classes de AlternativeIndex ) qui permettent d'effectuer des recherches suivant un ensemble de sous-index et de traiter les résultats pour les réunir. Par exemple, on propose d'effectuer : l'union des résultats (classe UnionIndex ), l'intersection des résultats (classe IntersectionIndex ), ou la sélection du premier sous-index donnant des résultats de recherche satisfaisants (classe FirstAlternativeIndex ),
  • les index de connexion (sous-classes de ConnectionIndex ) qui permettent d'utiliser deux index en séquence : les résultats d'un premier index sont utilisés comme paramètres pour le second. Par exemple, l'index de répartition ( DispatchIndex ) permet d'activer des sous-index suivant les résultats du premier index. L'index de connexion vers un index dynamique ( ToDynamicKnnIndex ) permet d'opérer une recherche uniquement en prenant en compte les cas identifiés par le premier index.

exemple de composition d'index

Figure 3 : exemple de composition d'index


La Figure 3 donne l'exemple d'un diagramme d'objets représentant une stratégie de recherche basée sur la combinaison des techniques d'indexation de REMIND: prototypes puis arbres d'induction (ou plus généralement arbres discriminants) et plus proches voisins. On montre ainsi que cette modélisation permet d'effectuer ce type de combinaison tout en apportant une flexibilité accrue : des étapes peuvent en effet être ajoutées ou supprimées suivant les besoins. Dans cette structure, la recherche des cas sources les plus utiles au raisonnement, pour un cas cible donné, est effectuée par un parcours récursif en profondeur d'abord. Pour commencer, un ensemble de prototypes compatibles avec le cas cible est identifié (index prototypes). Chaque prototype représente un ensemble de cas en compréhension dont l'identificateur est relié sémantiquement à un arbre discriminant. L'index prototypes retourne les identificateurs des prototypes compatibles et l'index union continue le parcours récursif en ne considérant que les arbres discriminants ainsi sélectionnés. Chaque arbre permet d'identifier un sous-ensemble de cas (index arbre1 à arbreN). L'union de ces ensembles (index union) est alors passée en paramètre pour effectuer une recherche par plus proches voisins (index plusProchesVoisins). Finalement, les meilleurs cas suivant cette recherche sont retournés (index racine).

Un parcours similaire est effectué lors de l'indexation d'un nouveau cas. Le nouveau cas est tout d'abord classé dans les prototypes (index prototypes) puis ajouté dans les arbres discriminants associés aux prototypes (index arbre1 à arbreN). Si la structure interne des arbres discriminants n'est pas incrémentale, les index doivent être reconstruits pour que le cas soit pris en compte.
 

API

separator line

Valid XHTML 1.0!

Valid CSS!

Brigitte Trousse

Last modified: Thu Jul 26 13:06:23 MEST 2001