Résumé "Classification Automatique" (c) 2003-01-11 Fabian M. Suchanek http://www.mpi-inf.mpg.de/~suchanek/personal/texts/summaries/ca.txt Ceci est le résumé du cours "Classification automatique", donné par Mme D'Aubigny en hiver 2002 à l'Université Pierre-Mendès-France Grenoble. (Since this text is supposed to be in French, I could not avoid using non-ASCII characters, sorry for that to all foreign readers) Le lecteur, en lisant le texte ci-dessous, accepte que l'auteur décline toute responsabilité concernant des informations fausses ou incomplètes. Si quelqu'un trouve une faute, je lui serais reconnaissant de bien vouloir me le dire. C'est le seul moyen de profiter moi-même de la publication de ce résumé. Mon e-mail est f.m.suchanek@zweb.de, mais il faut effacer la lettre 'z' dans l'adresse. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Introduction ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ cf aussi maths.txt (en francais) cf aussi gc.txt (en francais) Ensemble: Une collection non rangée d'éléments non identiques. X = {x[1], x[2], ..., x[n]} est l'ensemble de x[1], x[2], ..., x[n] X = {x | déclaration } est l'ensemble de tous les x pour lesquels la déclaration est vraie Dans toute la suite, les éléments d'un ensemble sont notés par les minuscules indexées du nom de l'ensemble. Cardinalité d'un ensemble: Le nombre d'éléments de cet ensemble. |M| = le nombre d'éléments de M Sous ensemble d'un ensemble M: Un ensemble T tel que tous les éléments appartenant à T appartiennent à M. On dit que T est inclu dans M. T < M R: L'ensemble des nombres réels. R+: L'ensemble des nombre réels positifs. N: L'ensemble des nombres naturels. Application, Fonction: Un classement f qui prend un élément appartenant à un ensemble A (ou à plusieurs ensembles) et qui redonne un élément appartenant à un ensemble B. On écrit: f: A -> B f(a)=b, où a appartient à A et b appartient à B Paramètre: Un élément qu'on donne à une apllication. Union: L'application "\/" qui prend deux ensembles M1 et M2 et redonne l'ensemble qui contient les élements qui appartiennent à M1 ou à M2 ou à tous les deux. L'union est associative et commutative. C(n,k): Le nombre de sous ensembles de k éléments d'un ensemble de n éléments. Il est: * C(n,k) = n! / k! / (n-k)! * C(n,k) = C(n,n-k) * C(n,k) = C(n-1,k) + C(n-1,k-1) * C(n,0) = 1 * C(n,1) = n * C(n,n-1) = n * C(n,n) = 1 * C(n,k>n) = 0 * C(0,k) = 0 On note k <-- sous ensemble C(n,k) = C n <-- grand ensemble n!: Le produit 1*2*3*...n n! est approximativement égal à (n/e)^n*sqrt(2*n*pi) SUM i=i1..i2 f(i): La somme f(i1) + f(i1+1) + ... f(i2). SUM f(x) cond(x): La somme f(x[1]) + f(x[2]) + ..., où X = {x | cond(x) } Suite, tuple: Une collection rangée d'éléments. v = (v[1], v[2], ... v[n]) Couple: Un tuple de deux éléments. Produit cartésien: L'application "x" qui prend deux ensembles A et B et rend l'ensemble de tous les tuples (a,b) tels que a appartient à A et b appartient à B. Au lieu de A x A, on écrit aussi A^2. Vecteur: Un tuple de nombres réels. Annotation: Pour une définition plus générale et les opérations principales, cf maths.txt Norme d'un vecteur v: La valeur ||v|| = sqrt(v[1]^2+...v[n]^2). Algorithme: Une suite finie d'instructions. Distance: Une application d qui prend deux éléments d'un ensemble X et redonne une valeur positive de sorte que * d(x,y) = 0 ssi x=y (Séparation) * d(x,y) = d(y,x) (Symétrie) * d(x,y) =< d(x,z)+d(z,y) (Inégalité triangulaire) pour tous éléments x,y,z de X. Partition d'un ensemble X: Un ensemble d'ensembles {X[1], ...X[n]} tel que X[1] \/ X[2] \/ ... X[n] = X Il n'existe aucun élément qui appartient à deux X[i] Relation, Relation binaire: Un sous ensemble du produit cartésien de deux ensembles. Soit R la relation, soient E et F les deux ensembles, alors on écrit: * (x,y) appartient à R * x R y * R(x,y) * x est en relation R avec y pour dire que le couple (x,y) appartient à R. On note ~R(x,y) le phénomène que (x,y) n'appartient pas à R. Relation définie sur E: Une relation R < E x E. Relation réflexive: Une relation R < E x E telle que R(x,x) pour tout x appartenant à E. Relation antiréflexive, relation irréflexive: Une relation R < E x E telle que ~R(x,x) pour tout x appartenant à E. Relation symétrique: Une relation R < E x E telle que R(x,y) ssi R(y,x) pour tout (x,y) appartenant à E^2. Relation transitive: Une relation R < E x E telle que si R(x,y) et R(y,z) alors R(x,z). Relation antisymétrique: Une relation R < E x E telle que si R(x,y) et R(y,x) alors x=z. Relation d'ordre: Une relation R < E x E qui est antisymétrique et transitive. Relation d'équivalence: Une relation R < E x E qui est réflexive, transitive et symétrique. Relation totale: Une relation R < E x E telle que pour tout x,y R(x,y) ou R(y,x). Classe d'équivalence de x0 par R: L'ensemble des supports de x0 par la relation d'équivalence R. On le note x0 avec un point en-dessus, ce(x0,R). Ssi ce(x,R) = ce(y,R) alors R(x,y) Classe: Un ensemble d'objets similaires. Singleton d'un ensemble E: Un ensemble qui contient un seul élément de E. Graphe: Un couple de * un ensemble de noeuds * une relation définie sur ces noeuds On dessine les noeuds comme cercles et on lie les noeuds en relation avec une flèche. Chemin dans un graphe: Une suite de noeuds liés. Arbre: Un élément et une suite d'arbres. La suite peut être vide. Chaque arbre de cette suite est appelé un "enfant", l'élément est appelé "noeud". On dessine un arbre en représentant tous les éléments de l'arbre et en liant les enfants à son parent. Arrête d'un arbre: Un couple de deux noeuds, dont l'un est l'enfant de l'autre. Chemin dans un arbre: Une suite de noeuds de cet arbre, dans laquelle chaque noeud est enfant de son prédécésseur ou de son successeur. Racine d'un arbre: Le noeud qui n'est enfant d'aucun autre noeud. Feuille d'un arbre: Un noeud sans enfants. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Classification automatique ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Clustering, Classification automatique: L'ensemble des méthodes exploratoires, dont l'objectif est de réveler des structures dans les données sous forme de classes. Ordre lexical: La relation d'ordre totale L < C x C telle que L(a1+a2*i , b1+b2*i) ssi (a1R telle que * diss(x,y) = diss(y,x) (Symétrie) * diss(x,x) = 0 Tableau d'une fonction f(x,y): Un tableau qui contient à la position i,j la valeur f(x,y). Classification d'un ensemble E: Un ensemble de sous ensembles de E, tel que tout élément de E apparaît dans au moins un des sous ensembles. Les sous ensembles sont appellés "parties". ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Classification hiérarchique ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Hiérarchie totale sur un ensemble E: Une classification H de E telle que * H contient tous les singletons de E * H contient E * pour tout h1, h2 appartenant à H: h1 /\ h2 = {} ou h1 < h2 ou h2 < h2 Une telle classification peut être visualisée en représentant tous les objets de l'ensemble et en dessinant un cercle autour des objets d'une classe. Arbre d'une hiérarchie sur E: Un arbre, dont les racines sont les singletons de E. Chaque noeud est enfant de la plus petite classe dans laquelle il est compris. Indendogramme d'une hiérarchie sur E: Une représentation graphique de l'hiérarchie, qui est similaire à l'arbre de l'hiérarchie. On représente chaque noeud sauf les feuilles par une ligne horizontale. Les deux enfants d'un noeud sont mis en dessous des fins de la ligne, chaqu'un lié à une fin. Les feuilles sont représentés par les singletons. Algorithme aggrégatif, Algorithme agglomératif: Un algorithme de classification hierarchique, qui, dans chaque étape, construit une classe en agrégeant deux classes de l'étape précédente. Il part de l'ensemble des singletons. Algorithme divisif: Un algorithme de classification hierarchique, qui, dans chaque étape, construit une classe en divisant une classe de l'étape précédente en deux. Il part de l'ensemble de l'ensemble. Un algorithme divisif a besoin de plus de calcul qu'un algorithme agrégatif, car * un algorithme agrégatif a le choix entre C(|L|,2) classes, si L est la classification courante * un algorithme divisif doit choisir la classe et la division, il a SUM i=1..|L| (2^(|l[i]|-1) - 1) choix Ordre de construction: Le préordre total '=<' défini sur une hiérarchie tel que C1 =< C2 ssi C1 a été construit avant C2 ou en même temps par un algorithme Hiérarchie stratifiée: Une hiérarchie munie d'un préordre total. Indice pour une hiérarchie H: Une fonction v:H->R+ telle que si C1 < C2, alors v(C1)R+ telle que d(x,y) =< max({d(x,z), d(z,y}) pour tout z appartenant à E Une ultramétrique n'est donc non seulement une distance, mais aussi une dissimilarité. Ses propriétés sont: * d(x,y) = 0 ssi x=y * d(x,y) = d(y,x) * d(x,y) =< max({d(x,z), d(z,y}) pour tout z appartenant à E h(u,w) d'une hiérarchie H: La plus petite classe de H qui contient u et w. Ultramétrique par une hiérarchie indicée H: L'ultramétrique définie par d(x,y) = v(h(x,y)). Hiérarchie définie par une ultramétrique: L'hiérarchie indicée H construite telle que v(h(x,y)) = d(x,y). Chemin de x à y dans un ensemble E: Une suite d'objets de E, dont le premier élément est x et le dernier y. Longueur normale d'un chemin c=(c[1],...c[n]): La valeur l(c) = SUM k=1..n-1 diss(c[k],c[k+1]). Longueur du saut maximal d'un chemin c=(c[1],...c[n]): La valeur lsm(c) = max({ diss(c[k],c[k+1]) | k=1..n-1 }). Distance normale sur un ensemble E: La fonction d:E^2->R+ telle que d(x,y) = min({ l(c) | c est un chemin de x à y }). Distance du saut maximal sur un ensemble E: La fonction dsm:E^2->R+ telle que dsm(x,y) = min({ lsm(c) | c est un chemin de x à y }). Ultramétrique du saut maximal: La distance dsm. Preuve: Soient x, y, z trois objets Soit xy le chemin de x à y tel que lsm(xy) minmale Soit xz le chemin de x à z tel que lsm(xz) minmale Soit yz le chemin de y à z tel que lsm(yz) minmale Soit xyz la concaténation de xy et yz Montrons que dsm(x,y) =< max({dsm(x,z), dsm(z,y}) par l'absurde Supposons dsm(x,y) > max({dsm(x,z), dsm(z,y}) <=> lsm(xy) > max({lsm(xz), lsm(yz}) Il est: lsm(xyz) = max({lsm(xz), lsm(yz}) Alors lsm(xy) > lsm(xyz) Alors xy n'est pas le plus court chemin -> contradiction Enveloppe supérieure d'un ensemble D de ultramétriques: La fonction d* telle que d*(x,y) = sup({d(x,y) | d appartient à D}). d* est une ultramétrique. Ultramétrique sous dominante d'une enveloppe supérieure: L'ultramétrique la plus grande de l'ensemble, qui est inféreure à l'enveloppe supérieure. L'ultramétrique du saut maximal est l'ultramétrique sous dominante. Preuve: Soit d une ultramétrique Soient x et y deux objets Soit c=(c[1]=x,c[2],...c[n]=y) le chemin entre x et y tel que l(c) minimale Montrons que d =< dsm Il est d(x,y) =< max({diss(c[k],c[k+1]) | k=1..n-1}) Comme dsm(x,y) = max({diss(c[k],c[k+1]) | k=1..n-1}), on déduit d =< dsm Arbre minimal couvrant d'un ensemble E: Un arbre dont les noeuds sont les éléments de E et qui est tel que: SUM {(x,y) arrête} diss(x,y) minimale. On munit les arrêtes (x,y) de l'arbre des valeurs diss(x,y). Algorithme de Prim: L'algorithme suivant, qui établit un arbre minimal couvrant d'un ensemble E: 1. Prends un élément quelconque o0 de E 2. Soit A := (o0,()) l'arbre 3. Pour k=1..|E|-1 4. Détermine l'élément o1 appartenant à A et l'élément o2 n'appartenant pas à A tels que diss(o1,o2) minimal 5. Ajoute o2 comme enfant à o1 6. FinPour Méthode de l'ultramétrique dominante: L'algorithme de classification hiérarchique suivant pour un ensemble E: 1. Calcule et écris le tableau de dissimilarité 2. Construis un arbre minimal couvrant A de E 3. Établis l'ultramétrique 3.1. Soit d(x,y) := lsm(c) où c est le chemin de x à y dans A d est une ultramétrique 3.2. Écris le tableau de l'ultramétrique 4. Établis l'hiérarchie 4.1. Soit H := { E } 4.2. TantQue A a encore des arrêtes 4.3. Trouve la plus grande arrête de A 4.4. Sa valeur est l'indice de la classe correspondante dans H 4.5. Rompe l'arrête 4.6. Ajoute les éléments des deux arbres résultants comme deux parties à H 4.7. FinTantQue 4.8. Dessine l'idendogramme de H Dissimilarité de classes: Une fonction D:C^2->R+, qui redonne une valeur réelle positive pour un couple de classes. Inversion: Le phénomène que la classe obtenue de l'agrégation de deux classes A et B se retrouve plus proche d'une classe C que l'étaient les classes A et B. Condition médiane: L'exigence qu'une dissimilarité de classes D doit satisfaire la contrainte suivante: Si D(C1,C2) < inf({D(C1,C), D(C2,C)}), alors inf({D(C1,C), D(C2,C)}) < D(C1 \/ C2, C) Si D satisfait cette condition, l'inversion est évitée. Tous les dissimilarités présentées ici satisfont la condition médiane. Méthode fondée sur un critère d'agrégation: Un algorithme aggrégatif, qui réunit à chaque étape 2 classes qui sont les moins dissemblables à partir de la partition obtenue à l'étape précédente. On part de la partition en singletons. Chaque classe construite est munie de l'indice donnée par la dissimilarité de classes: v(C) = D(C1,C2), où C = C1 \/ C2 Méthode directe: Une méthode fondée sur un critère d'agrégation, dont la dissimilarite de classes dépend uniquement sur la dissimilarité entre objets. L'algorithme est le suivant: 1. Soit E l'ensemble à classifier 2. Calcule et écris le tableau T de la dissimilarité diss 3. Soit H l'ensemble des singletons 4. TantQue T a plus de 1 colonne 5. Détermine la valeur minimale m de T, soit la position C1,C2 6. Ajoute (C1 \/ C2) à H avec v(C1 \/ C2) = m 7. Agrège les colonnes et lignes de C1 et C2 en mettant pour toute classe C la valeur D(C, C1 \/ C2) // Cela revient simplement au maximum ou au minimum des valeurs // anciennes, selon le choix de D 8. Soit T ce nouveau tableau 9. FinTantQue 10. Ajoute E à H avec v(E)=valeur de T 11. H est l'hiérarchie Méthode du lien simple, Méthode du saut minimal: La méthode directe, dont la dissimilarité de classes est D(C1,C2) = min({diss(x,y) | (x,y) appartient à C1 x C2}) Cette méthode a tendence à agréger les classes, qui ont une propriété quelconque en commun. Méthode du diamètre, Méthode du saut maximal: La méthode directe, dont la dissimilarité de classes est D(C1,C2) = max({diss(x,y) | (x,y) appartient à C1 x C2}) Cette méthode minimise la distance à l'intérieur d'une classe. Poids d'un objet o: Un réel P(o) tel que la somme des poids de tous les objets de l'ensemble est 1. Poids d'une classe C: La somme des poids des objets inclus, P(C) = SUM P(x) x appartenant à C Méthode du lien moyen: La méthode directe, dont la dissimilarité de classes est D(C1,C2) = 1/P(C1)/P(C2) * SUM P(x)*P(y)*diss(x,y), (x,y) appartient à C1 x C2 Point: Un objet donné par un vecteur. Nuage: Un ensemble de points. Centre de gravité d'une classe C: La valeur g(C) = SUM P(x)*x pour x appartenant à C Cette notion présuppose que les objets sont des points. Méthode de Ward: La méthode directe, dont la dissimilarité de classes est D(C1,C2) = sqrt(P(C1)*P(C2)/(P(C1)+P(C2))*||g(C1)-g(C2)||) Cette méthode présuppose des points. Méthode indirecte: Un algorithme agrégatif, qui réunit deux classes de sorte qu'un critère global soit optimisé. Inertie d'une classe C: La valeur I(C) = SUM P(x) * ||x-g(C)||^2 Elle mesure l'hétérogénité de la classe. Cette notion présuppose des points. Inertie interclasses d'une partition C: La valeur Iinter = SUM P(c)*||g(c)-g(E)|| c appartenant à C où E est l'ensemble partitionné. Cette notion présuppose des points. L'inertie interclasses mesure la séparation des classes. Inertie intraclasses d'une partition C: La valeur Iintra = SUM P(c)*I(c) c appartenant à C Cette notion présuppose des points. L'inertie intraclasses mesure l'hétérogénité globale des classes. Inertie totale d'une partition C: L'inertie de l'ensemble partitonné E: Itotale = I(E) Il est Itotale = Iintra + Iinter Pour la partition des singletons, l'inertie intraclasses est 0 et l'inertie intraclasses est Itotale. Si on agrège deux classes, l'inertie intraclasses augmente et l'intertie interclasses diminue. Si on arrive à la classe E, l'inertie interclasses est 0. Méthode d'inertie: La méthode indirecte, dont le critère global est l'inertie intraclasses. Elle agrège les deux classes qui provoquent la plus petite augmentation de l'inertie intraclasses. Pour cela, elle se donne une fonction delta(C1,C2), qui mesure la perte d'inertie due à l'agrégation des classes C1 et C2. On peut montrer que delta(C1,C2) n'est rien d'autre que la dissimilarité de Ward. Alors la méthode d'inertie est la méthode de Ward. Diamètre d'une classe C: La valeur diam(C) = sqrt( 1/P(C)*SUM P(x)*P(y)*||x-y||^2 ) pour x et y appartenant à c Méthode de la somme des diamètres: La méthode indirecte, dont le critère global est à minimiser f(C) = SUM diam(c[i])^2 c[i] appartenant à C Cette méthode donne la même hiérarchie que la méthode de Ward. Méthode du critère du lien moyen: La méthode indirecte, dont le critère global à minimiser est f(C) = ( SUM P(x)*P(y)*||x-y|| ) / (SUM P(x)*P(y)) pour x,y appartenant à une même classe Cette méthode est la méthode du lien moyen. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Classification non-hiérarchique ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Classification non-hiérarchique, Partitionnement de E: La classification sous forme d'une partition de E. Le partitionnement est mieux adapté aux grands ensembles, car il nécessite moins de calcul. Pour un ensemble E et un nombre de classes donné K, il y a 1/K! * SUM i=1..K (-1)^(K-i)*C(k,i)*i^|E| Algorithme de leader: L'algorithme de partitionnement suivant: 1. Soit E l'ensemble à classer 2. Soit m une dissimilarité maximale donnée 3. Soit k=1 4. Soit i1=1 5. Soit i2=1 6. TantQue i1 < |E| 7. TantQue diss(e[i1],e[i2])