Upload
buikiet
View
213
Download
0
Embed Size (px)
Citation preview
Licence d’informatique 2002-2003
Informatique et Science du VivantCours 3
Méthodes de discrimination par arbredes espèces
Régine Vignes LebbeLaboratoire Informatique et Systématique
Identification en biologie• Classification préalable
• Représentation des connaissances
• Méthode de discrimination
• Identification d’un spécimen parla méthode de discrimination
?
Les clés d’identification En biologie
• Méthode la plus classique• La construction de clés est un travail quotidien dessystématiciens• Environ 1 million de monographies contenant pour la plupartdes clés La plus grande : >> 2000 nœuds ou questions
En médecine• Méthode récente pour enseigner une démarche diagnostiqueou thérapeutique• Il existe même une revue spécialisée publiant ces algorithmescliniques
1:1 Bractéoles = absentes ⇒ 21:2 Bractéoles = 2 ⇒ 31:3 Bractéoles = plus de 2 ⇒ Genre : Weddellina
2:1 Longueur de l'anthère des étamines = inférieure à 0.7 ⇒ Genre : Dalzellia2:2 Longueur de l'anthère des étamines = sup à 1.2 ⇒ Genre : Indotristicha
3:1 Longueur de l'anthère des étamines = inférieure à 0.4 ⇒ Genre : Malacotristicha3:2 Longueur de l'anthère des étamines = 0.4 à 0.7 ⇒ 43:3 Longueur de l'anthère des étamines = 0.8 à 1.2 ⇒ Genre : Tristicha3:4 Longueur de l'anthère des étamines = supérieure à 1.2 ⇒ Genre : Indotristicha
4:1 Hauteur de l'ovaire = inférieure à 1.0 ⇒ Genre : Dalzellia4:2 Hauteur de l'ovaire = 1.0 à 2.8 ⇒ Genre : Tristicha
Clé d’identification = graphe particulier Définition
Le graphe G = (S, A ∈ S2) est une clé d’identification si c’est un grapheenraciné connexe sans circuit.
G est connexe si il existe une chaîne reliant chaque paire de sommets.G est sans circuit si aucun chemin n’a son origine et son extrémité
confondues.G possède une racine, l’unique sommet ascendant de tous les autres.
Deux types de sommetsLes nœuds, sommets non terminaux. Les feuilles, sommets terminaux.
Étiquetage particulierLes nœuds sont étiquetés par un ou plusieurs descripteurs.Les branches sont étiquetées par des ensembles de valeursLes feuilles sont étiquetées par un ou plusieurs taxons.
Parcours de la clé = parcours d’un graphe
noeud
feuille
branche
Méthodes d’identification• Basées sur l’élimination des taxons non compatibles
- un taxon est ou non compatible- méthode convergente- Exemple : les clés d’identification
• Autres méthodes :- basées sur les probabilités Bayesian (probability)- par comparaison numérique (« matching ») et
identification au 1 ou k plus proches- Problème d’arrêt car méthode non convergente
• Distinction des méthodes aussi sur la nature des connaissancessous-jacentes
Phlebotomine wing structure
Generalized Procuste (GLS) Procustean K Nearest Neighbors
Originalcoordinates
Partial adjustmentcomplete adjustment
Why separate landmarks used for the adjustment et thedistance calculation?
Procustean K Nearest NeighborsLearning sample
Procusteanadjustment
Distance MatrixDiscrimination
KPPVIdentification system
= Sample + optimized parameters
Optimization ofparameters :
-Lm of adjustment-transformations-Lm of distance-K
Specimento identify
Identified specimen
LEARNING
IDENTIFICATION
Construction de graphes de discrimination
• Arbre de décision (IA, Apprentissage automatique)
• Arbre de segmentation ou de discrimination(Analyse des données et Statistique)
• Clé diagnostique ou de détermination (Biologie)
• Algorithme clinique (Médecine)
Données en entrée
• Base de règles (compilateur de système expert)
• Descriptions d’échantillons statistiques– CART (Breiman & coll., 1984) « Classification and regression tree »– ID3 (Quinlan, 1986), C4.5, C5.0 « decision tree »– RECPAM (Ciampi, 1985)– …
• Descriptions statistiques des taxons– CONFOR, KEY3M2, MAKEY . ..
Évaluation d’un nœud• Critère du χ2
– Évalue la non indépendance du tableau de contingence croisant lesnouvelles branches créées par le nœud et les classes à discriminer
• Critère basé sur la distance de Kolmogorov-Smirnov– Variable quantitative et discrimination de 2 classes– V maximisant : |F1(V) – F2(V)|
• Critère basé sur un gradient d’impureté– GINI, Entropie …– Mesure probabilité d’erreur aléatoire de classement
• Nombre de couples de taxons discriminés– Pouvoir discriminant
Heterogeneous descriptions:each description has adifferent list of descriptors.No standard terminologyThe comparison ofdescriptions need humaninterpretation
Comparable descriptions:all descriptions have thesame list of descriptors.Standard terminologyAn automatic comparisonof descriptions is possible
Knowledgerepresentation
Programs toaccess andanalyze theknowledgebase
Matrix of the KB
Dependencies between descriptors
taxa
descriptors All possible values(polymorphism)
De nombreuses clés possibles
a,bbca, ct5babat4bb, cab, ct3aaa, cct2aabct1
d4d3d2d1
Critères d’évaluation d’une cléMesures sur la topologie d’une clé
Nombre de nœudsLongueur moyenne des chemins maximauxLongueur du chemin maximal le plus longNombre total de chemins maximaux…
Facilité d’utilisation de la cléCaractères non ambigus utilisés préférentiellementFavoriser l'identification rapide des concepts les plus fréquentsTaxons proches discriminés en dernier Nombre total de descripteurs différents utilisés…
Construction d’un graphed’identification
• Programmes de construction de clés :M.J. Dallwitz (KEY), J.C. Gower, A.V. Hall, L.E. MorseR.J. Pankhurst (KEY3M2), R.W. Payne (Genkey),G.J.S. Ross, J. Lebbe et R. Vignes (Makey) …
• Etapes :Partitionnement récursif de l’espace de représentationAjout pas à pas d’un nœud au graphe courant.
• Choix :Méthode de construction et d’évaluation des noeuds
Heuristique qui sélectionne pas à pas le meilleur descripteur pour créer un nœud selon un critère choisi
pour optimiser certaines propriétés du graphe
di
dj
dk
Taxon A Taxon B
Taxon C
- Descendante- En profondeur- Heuristique- Optimiseglobalement uncritère sur le graphe
- Complexité :n2 x n x log2T
Partitionnement récursif del’espace de description
t1t4
t3t2
d1
d2
ae
b c d
hgf
d1= a ou b d1= c ou d
Pouvoir discriminantLe pouvoir discriminant d’un descripteur pour un ensemble deconcepts (ou de taxons) est une mesure de la capacité dediscriminer les concepts sur ce seul descripteur
PD(d) = ∑ comp(d(ti), d(tj))pour tous les couples de taxons ti, tj
- extension de la variance - s’adapte à la discrimination de toute partition sur les taxons
- de la même façon on peut calculer le PD original d’un descripteur par rapport aux autres (équivalent d’une covariance) - complexité : n x n = n2
Formalisation de l’identification• Contexte
Connaissances stratégiques• Étape d’identification• Quatre fonctions fondamentales :
– Comparaison de deux éléments de description(taxon/taxon, spécimen/taxon)
– Agrégation de résultats de la fonction de comparaison– Généralisation des résultats pour un groupe– Décision
Fonctions essentielles• Comparaison de descriptions (taxon/taxon, individu/taxon)
• Comparaison de deux attributs de concepts = comparaison de 2 distributions– Nombreux indices dans la littérature– Exemple :
• Cas de référentiels à états discrets, non structurés• Soit 2 taxons t1 et t2 et un descripteur d Comp (d(t1), d(t2)) = 1 ssi d(t1) ∩ d(t2) = 0
sinon Comp (d(t1), d(t2)) = 0
• Comparaison d’un attribut d’individu avec un attribut de concept– Mesure si l’individu est incompatible avec le concept– Exemple :
• Soit 1 taxon t1, un individu x et un descripteur d Comp (d(t1), x) = 1 ssi d(x) ⊂ d(t1)
sinon Comp (d(t1), x) = 0
MakeyMLT• Nouvelle représentation desconnaissances (CKRL)
• En entrée : ensemble de qualificatifsde typicité précisant la fréquencerelative de chaque valeur dans lesdescriptions initiales
• En sortie : le concept identifié estégalement muni d’une typicité
• Fonction d’agrégation (fonctionminimum) et option de renforcement
• Elagage du graphe
Fusion de branches• But : fusionner au mieux les
branches à chaque nœud pourobtenir si possible un arbredichotomique
• Possibilité de fusion de branchessans modification du PD
• Revient à la partition en cliquesdu graphe de discrimination destaxons
B
C
A
D
E
F
{A} {BCF} {DE}
Clé / I.A.O.
• Démarche imposée• Identification = parcours du
graphe de discrimination
• Accès libre• Identification = construction
dynamique d’un chemin du graphepotentiel de discrimination
Connaissances stratégiques
descrxp
mindescr
distinxp
Recherche en discrimination• Représentation et traitement des données incertaines,
imprécises ou manquantes• Représentation de la structure et utilisation de variables
calculées par des opérateurs• Construction de nœuds combinant plusieurs variables• Combiner des caractères de natures différentes• Utilisation de connaissances stratégiques• Critères globaux d’évaluation des nœuds• Construction incrémentale• Méthodes d’élagage …• Prise en compte de l’imprécision dans le parcours du
graphe
LecturesBarthélémy J-P & Guénoche, 1988. Les arbres et lesreprésentations des proximités. Masson.
Lecointre G. & Le Guyader H., 2001. Classificationphylogénétique du vivant. Belin.
Darlu P. & Tassy P. 1993 . Reconstruction phylogénétique.Masson.
Pankhurst R., 1998. A historical review of identification withcomputers. In Information Technology Plant Pathology andBiodiversity : 229-240.