Eric Buist ([email protected]) Département d ... · Exemple de degrés qualitatifs • 35 ans est considéré identique à 40 ans • 66 ans différent de 50 ans d'un degré

Le raisonnement à base de cas

Eric Buist([email protected])

Département d’informatique et de recherche opérationnelle

Eric Buist Raisonnement à base de casFévrier 2004

2/38

Processus de raisonnementà base de cas

Base de cas

Problème

Casretrouvés

Recherche

Solution proposée

Solution confirmée

Révision

Rétention

Réutilisation

Introduction Base de cas Recherche Révision Applications


3/38

Plan

• La base de cas• La recherche des cas• La révision de la solution• Applications



4/38

Qu’est-ce qu’un cas?• Ensemble d’informations contextuelles

enseignant une leçon– Problème– Solution– Impact

• Exemples– Recette de cuisine (planification)– Diagramme UML (conception)– Problème technique (classification)



5/38

Caractéristiques• Nécessité d’exprimer un cas pour qu’il soit

utilisable par l’ordinateur• Utilisation de caractéristiques pour décrire

les cas• Caractéristique = descripteur = paire

(attribut, valeur)• Le problème, la solution et son impact

sont extraits à partir des caractéristiques



6/38

Primaire ou dérivée• Caractéristique primaire

– Se calcule facilement– Contenue dans les cas et dans le problème

• Caractéristique dérivée– N’est pas présente dans la requête ou dans certains

cas– Doit être calculée ou inférée– Donnée par des règles de complétion



7/38

Index• Caractéristique utilisée pour rechercher

des cas• Index central

– Pour chaque valeur de chaque caractéristique indexée, liste de cas

– Analogue avec l’index d’un livre– Recherche plus rapide si l’index est bien

construit– Problèmes de consistance



8/38

Format des cas• Plusieurs modes de représentation possibles

(cadres, réseau sémantique, logique d’ordre 0 ou 1, règles, …)

• Idéalement, mode hybride de type objet– Cadre avec attributs complexes autorisés– Classes pour décrire la structure de la base de cas– Cas = instance d’une classe

• Plusieurs formats possibles– Formats propriétaires– Base de données relationnelle– CASUEL– XML– …



9/38

Base de cas initiale• Doit couvrir tout le domaine d'application, ou du

moins une grande partie• Le système ne peut pas fonctionner sans base

de cas initiale• Peut être construite de plusieurs façons

– À l'aide d'un expert– Depuis un autre système– Depuis une base de données

• Souvent nécessaire de transformer les données existantes



10/38

Élargissement de la base de cas

• L'adaptation crée de nouveaux cas, qu'elle soit faite par le système ou l'être humain

• Nécessité de définir des politiques de contrôle de la base de cas– Quels cas doit-on ajouter?– Quand doit-on regrouper ou supprimer des

cas?



11/38

Recherche des cas• L'utilisateur formule une requête R pour le

système à base de cas• Le système retrouve des cas C1, …Ck similaires

à R. L’utilisateur examine les cas et sélectionne le ou les meilleurs

• La requête est un objet dont les attributs ne sont tous nécessairement définis

• Deux classes de méthodes de recherche– Plus proches voisins– Méthodes inductives



12/38

Plus proches voisins• Préfiltrage de la base de cas, soit S l'ensemble des cas restants• Pour chaque cas C de S

– Déterminer les attributs communs dans R et C, soit A l'ensemble de ces attributs

– Pour chaque attribut a dans A,• Calculer µa(Ra, Ca), la fonction de similarité locale

– Calculer le degré global de similarité

• Retourner les k (souvent k=1) cas les plus similaires à R• Autres mesures de similarité possibles (e.g. [Ruet et Geneste 2002,

Kontkanen et al. 2000])

∑∑

∈

∈=

Aaa

Aaaaaa

CRw

CRCRwCRs

),(

),(),(),(

µ



13/38

Préfiltrage des cas• Utilisation d'un index central pour retrouver les

cas• Utilisation de contraintes

– Contrainte = fonction booléenne θi(C)– On ne compare que les cas satisfaisant toutes les

contraintes– Possibilité d'éliminer tous les cas. Si cela se produit

• Division du problème• Relaxation



14/38

Attributs correspondants

• Si R et C de même classe, A contient tous les attributs définis dans R

• Sinon, il faut utiliser des heuristiques dépendant du domaine– Attributs de même nom et définis dans R– Attributs de la super-classe commune– …



15/38

Similarité locale ou dimensionnelle

• Idéalement, la fonction µa(Ra, Ca) est sur l'intervalle [0,1]. 0 = différence totale, 1 = similarité parfaite

• Souvent, on utilise une distance de similarité d(Ra, Ca). Possibilité de transformer une distance en mesure de similarité– Cas normalisé, 0 ≤ da(Ra,Ca) ≤ M

– Cas non normaliséM

CRdCRµ aaaaaa

),(1),( −=

),(11),(

aaaaaa CRd

CRµ+

=



16/38

Quelques distances dimensionnelles

• Différence absolue– Pour comparer des valeurs numériques telles que les prix, les

tailles, les distances, …– Faire attention aux unités

• Norme Euclidienne ou autre norme– Pour comparer les vecteurs (ex. Positions)

• Variation du nombre de degrés qualitatifs• Distance sémantique• Pour les attributs de type objet, appliquer l’algorithme de

mesure de similarité globale récursivement



17/38

Exemple de degrés qualitatifs• 35 ans est considéré

identique à 40 ans• 66 ans différent de 50

ans d'un degré qualitatif• Problème si on compare

65 ans avec 64 ans– Possibilité de corriger les

âges sur les bords– Ou utiliser des intervales

qui se chevauchent[65,…[Retraité

[35,65[Adulte

[18,35[Jeune adulte

[12,18[Adolescent

[0,12[Enfant



18/38

Exemple de distance sémantiqueAnimal

Mammifère Oiseau

Chien

Chat

Canari

Rouge-gorge

• Le chien est davantage similaire au chat qu'au canari

• Comme distances, possibilité d'utiliser– Nombre de relations à traverser– Nombre d'abstractions à effectuer



19/38

Pondération des attributs• La pondération donne le degré d'importance des

attributs• Les degrés d’importance sont souvent sur [0,1]• La pondération peut être définie pour

– Un ensemble de cas– Un seul cas– L'utilisateur peut aussi spécifier l'importance des

caractéristiques dans sa requête



20/38

Exemple de calcul dedegré de similarité

-

1/(1+2)=0.33

1-1/11=0.909

µa(Ra,Ca)

-

2

1

Da(Ra,Ca)

Baignade

14

Avril

Ca

BaignadeType

16Durée

MaiMois

RaAttribut

Caractéristiques toutes de même poids:

S(Ra,Ca)=(0.909 + 0.33)/2=0.62Données tirées de [Lenz 1993]



21/38

Méthodes inductives

• Méthodes apparentées aux arbres de décision dans les algorithmes d'apprentissage

• Deux grands types de méthodes– Réseaux de caractéristiques partagées– Réseaux de discrimination



22/38

Réseaux de caractéristiques partagées

• Chaque nœud de l'arbre représente un objet• Les feuilles représentent des cas• Un nœud interne contient toutes les

caractéristiques communes aux enfants

Racine

Couleur foncée,pas d'ailes Couleur foncée,

ailesCouleur vive,ailes

Couleur variée,pas d'ailes

Souris Éléphant Corbeau Canari Rouge-gorgeChien

Chat



23/38

Avantages et inconvénients des réseaux de caractéristiques

• Avantages– Possibilité de retrouver un cas plus

rapidement que dans une base plate– Faciles à construire

• Inconvénients– Le cas le plus similaire à R peut ne pas être

retrouvé– N'est pas optimal si des cas sont ajoutés de

façon incrémentale



24/38

Réseaux de discrimination

• Chaque nœud interne de l'arbre est une question• Tous les avantages des réseaux de caractéristiques

partagées• La comparaison se fait sur un descripteur à la fois, pas

besoin d’appliquer les plus proches voisins comme avec les réseaux de caractéristiques partagées

A-t-il des ailes?

Quel est son poids?Quelle est sa couleur?

Oui Non

Canari Rouge-gorge Corbeau Souris ChienChat

Jaune Rouge Noir <1kg

[1,10[ kg

>10kg



25/38

Inconvénient majeur des réseaux de discrimination

• Que faire si la question posée par un nœud ne peut être traitée?

• Plusieurs solutions possibles– Arrêter l'algorithme (la pire)– Retourner toutes les feuilles à partir du nœud

sans réponse et appliquer les plus proches voisins

– Utiliser un réseau de discrimination redondant



26/38

Évaluation et justification de la solution

• Évaluation de la solution– Par un expert utilisateur du système– De façon automatique par simulation

• Justification de la solution– Quels cas ont été recherchés et retournés?– Quelles adaptations ont été employées?– Quel est le processus de dérivation de la

solution?



27/38

Adaptation• Solution proposée souvent inadéquate, car elle

ne tient pas compte de tout le contexte• Adaptation = transformation de la solution pour

satisfaire les exigences du nouveau contexte• Deux types d'adaptation

– Transformation– Dérivation



28/38

Transformation• Guidée par un modèle casuel

– Exemple: remplacer un effet par un autre si une cause commune est présente dans le problème et le cas retrouvé

• Guidée par le bon sens– Ajouter un élément à la solution– Retirer un élément secondaire– Remplacer un élément…

• Il existe plusieurs types de substitutions



29/38

Substitution• Réinstanciation

– Transposition du problème passé dans le contexte présent

– Création d'une nouvelle instance de la classe du meilleur cas proposé

• Ajustement de paramètres– Modification de valeurs numériques

• Substitution à base de cas– Réutilisation du moteur de recherche à base de cas– Extraction de la composante à adapter d'un cas

précédent



30/38

Substitution (suite)• Recherche locale

– À partir d'un concept inadéquat, retrouver un concept sémantiquement près

– Exemple des oranges pour le dessert

• Interrogation de la mémoire– Recherche directe d'un

concept en utilisant ses attributs

• Recherche spécialisée– Interrogation de la mémoire

avec indices sur comment chercher

Oranges

Pommes

Fruits

Dessert

Crème glacée



31/38

Dérivation• Au lieu d'adapter la solution au problème,

adaptation du processus menant du problème vers la solution

• Processus de dérivation = plan menant d'un état initial (le problème) vers un état final (la solution) par un ensemble d'étapes

• État initial, état final et étapes = ensemble de caractéristiques, de composantes qu'il est possible d'adapter

• Possibilité de considérer toutes les adaptations comme dérivationnelles [Fuchs et al. 1999]



32/38

Domaines d'application• Analytique

– Classification– Diagnostic– Aide à la décision

• Synthétique– Conception– Planification– Configuration[Althoff et Bartsch-Spörl 1996]



33/38

Implantations• Plusieurs implantations de systèmes [Kolodner

1993]– CHEF (recettes de cuisine)– JULIA (planification de repas)– CASEY (diagnostic de maladies cardiaques)– …

• Outils généraux disponibles [Watson 1997]– CBR3– CASPIAN– The CBR-Product Experience Base CBR-PEB– …



34/38

Exemple CBR-PEB



35/38

Consortium INRECA [Bergman 2001]

• Ensemble d’entreprises et de groupes de recherche travaillant sur le raisonnement à base de cas

• Plusieurs contributions– Nouvelle vision des éléments nécessaires pour construire un

système à base de cas– Généralisation des mesures de similarité– Intégration des arbres de décision avec le raisonnement à base

de cas• Méthodologie INRECA pour développer des système à

base de cas– Processus généraux– Recettes spécifiques à des domaines– Expériences de développement



36/38

Conclusion• Le raisonnement à base de cas apprend à partir

d'exemples concrets• Un moteur de raisonnement à base de cas établit la

description d'un problème, trouve la solution au problème le plus similaire dans sa base de cas, révise cette solution et la propose à l'utilisateur

• Plusieurs problèmes à surmonter pour implanter le raisonnement à base de cas– Format de représentation des cas– Caractéristiques servant d'index– Degré d'importance de chaque caractéristique– Mesures de similarité à appliquer– Politiques de maintenance de la base de cas


37/38

Références• Althoff, Klaus-Dieter et Bartsch-Spörl, B. (1996). « Decision Support for Case-Based

Applications », Wirtschaftsinformatik 1/96, special issue on case-based decisionsupport (édité par D. Ehrenberg), p. 6 – 14.

• Bergman, Ralph, « Highlights of the european INRECA projects », Case-BasedReasoning Research and Development, 4th International Conference on Case-BasedReasoning ICCBR-2001, Springer, p. 1 – 15.

• Fuchs, Béatrice et al., « Towards a unified theory of adaptation in case-basedreasoning », Case-Based Reasoning Research and Development, Third International Conference on Case-Based Reasoning ICCBR-99, Springer, p. 104 – 117.

• Kolodner, Janet L., Case-Based Reasoning, Morgan Kaufmann Publishers, SanMateo, 1993.

• Kolodner, Janet L. et Leake, David B., « A tutorial introduction to case-based reasoning », Case-Based Reasoning Experiences, Lessons, & Future Directions,American Association for Artificial Intelligence, Menlo Park, 1996, p. 31 – 66.

• Kontkanen, Petri et al., « An unsupervised Bayesian Distance Measure », Advancesin Case-Based Reasoning, 5th European Workshop on Case-Based ReasoningEWCBR 2000, Springer, p. 148 – 160.

• Ruet, Magali et Geneste, Laurent, « Search and adaptation in a fuzzy object orientedcase base », Advances in Case-Based Reasoning, 6th European ConferenceECCBR 2002, Springer, p. 350 – 364.

• Watson, Ian, Applying Case-Based Reasoning Techniques for Enterprise Systems, Morgan Kaufmann Publishers, Inc., San Francisco, 1997.


38/38

Références Internet• AI-CBR, http://www.ai-cbr.org• Lenz, Mario, « Decision support in a travel

agency », 1993, ftp://ftpagr.informatik.uni-kl.de/pub/CASUEL/Casebases/travel-domain.tar.gz, extrait du système CABATA

• International Conference on Case-BasedReasoning, http://www.iccbr.org

• European Conference on Case-BasedReasoning 2004, http://www.idt.mdh.se/eccbr

• The CBR-Product Experience Base CBR-PEB, http://demolab.iese.fhg.de:8080/

Documents

Eric Buist ([email protected]) Département d ... · Exemple de degrés qualitatifs • 35 ans est considéré identique à 40 ans • 66 ans différent de 50 ans d'un degré