Prétopologie Classification Et Reconnaissance

LA CLASSIFICATION AUTOMATIQUE

La classification automatique, ou apprentissage non supervisé, a pour objectif d’organiser un ensemble d’individus E en classes, de façon à mieux l’interpréter et à mieux l’apprendre. Dans cette approche, on n’a aucune information a priori sur E, si ce n’est les attributs (caractéristiques) des individus ou les ressemblances entre ces individus, et, dans certains cas, le nombre de classes à détecter. Une méthode de classification automatique est basée en général sur l’idée de ressemblance suivante : deux éléments proches sont mis dans une même classe alors que deux éléments éloignés sont dans deux classes différentes. Ces hypothèses de classification automatique ont trouvé une première interprétation prétopologique avec EMPTOZ dans sa thèse de doctorat d’état [Emptoz-83]. Les mesures de ressemblance existantes entre les individus de l’ensemble E et le principe de proximité qui est à la base de la formation des classes sont remplacés par des adhérences prétopologiques. L’auteur propose des algorithmes prétopologiques pour l’apprentissage non supervisé qu’il présente en deux familles de méthodes dites respectivement : méthodes de groupement par propagation et méthodes de groupement par extraction d’une nouvelle prétopologie. Les méthodes de groupement par extraction d’une nouvelle prétopologie sont basées sur une recherche par adhérences successives d’extréma locaux relatifs à une fonction structurante modélisant la densité locale des points. Pour des raisons de généralité cette dernière famille de méthodes n’est pas présentée dans cette thèse. Dans la suite, nous présenterons les méthodes de groupement par propagation auxquelles nous adjoindrons l’algorithme de PIEGAY qui en forme une généralisation particulière. Nous trouvons une seconde utilisation des procédés prétopologiques en classification automatique avec la méthode DEMON dans [Nicoloyannis-88]. L’auteur a construit un algorithme auto-paramétré basé sur des voisinages de type r-voisin relatif. Cette méthode sera résumée plus loin. 

Les méthodes de groupement par propagation

 L’auteur présente plusieurs versions plus ou moins raffinées de son algorithme selon les cas à traiter (partition : classes disjointes, ou recouvrement : classes avec intersection non vide). On a besoin a priori de : – la définition d’une première adhérence qui traduit le fait que deux éléments proches sont susceptibles d’appartenir à la même classe, – la définition d’une fonction évaluant la densité locale en chaque individu, sur la base d’une deuxième adhérence (qui peut être identique à la première) Soit alors adE et ad deux structures prétopologiques définies sur E, Ψ une fonction d’ensemble définie sur P(E) et S une fonction structurante définie par : ∀ x ∈ E, S(x) = Ψ(ad({x})). L’algorithme effectue un seul balayage de tous les points de E qui ont été ordonnés dans une liste selon les valeurs croissantes ou décroissantes de S. L’ordre est choisi de telle sorte que l’on puisse commencer à partir d’un élément « modèle », par exemple de forte densité. Après cette étape de prétraitement un effet de chaîne, initialisé par le premier élément de la liste, est mis en route pour permettre à chaque élément x non encore classé de jouer le rôle de classifieur de la manière suivante : – dans le cas d’un recouvrement x attire dans sa classe tous les éléments de son adhérence adE ({x}); – et dans le cas d’une partition x n’attire dans sa classe que les éléments non encore classés de son adhérence.  

Le principe de l’algorithme

Dans les calculs pratiques les adhérences utilisées par l’auteur sont de types ε-voisins ou k-plus-proches-voisins. En particulier, lorsque l’adhérence ad est celle des p-plus-prochesvoisins et adE l’adhérence des n-plus-proches-voisins, l’algorithme est baptisé algorithme des (n-p) plus proches voisins. Une version plus élaborée de l’algorithme construit une adhérence plus intelligente que l’adhérence ad traduisant la proximité entre les éléments pour les agréger aux classes. Cette nouvelle adhérence s’adapte aux structures locales de l’espace de représentation. Dans l’algorithme des (n-p) plus proches voisins, par exemple, cette adaptativité se traduit par la dépendance du paramètre p de la structure avoisinant l’élément x à classer. p, qui devient alors p(x), peut être égal à : )( )( )( xS cS pxp ×= où S est la fonction structurante et c est le classifieur de x. I- PRETRAITEMENT • Pöur chaque x de E – Déterminer ad({x}) – Calculer S(x) • Ordonner les éléments de E dans un tableau T selon les valeurs décroissantes (ou croissantes) de S II GROUPEMENT α) Initialisation i Å 0 Soit e le 1er élément de T T Å T-{e}. Aller en β) β) Création d’une i Å i+1 nouvelle classe e crée la classe Ci et y entraîne les éléments de son adhérence non classés Aller en δ) χ) Groupement les éléments de adE({e}), non encore classés sont affectés à la classe Ck. δ) Contrôle les éléments de adE({e}) déjà classifiés ailleurs qu’en Ck sont neutralisés donc retirés du tableau T. Si T=∅ aller en ε) Sinon, soit e le premier élément de T – Si e est déjà classifié dans une classe Ck aller en χ) – Sinon aller en β) ε) Edition Editer les classes obtenues Figure III.1 : L’algorithme de groupement par propagation dans le cas d’une partition [Emptoz-83] Chapitre III . 57 Validation de l’algorithme Sur la figure III.2 nous avons représenté l’exemple initial qui démontre que cette méthode de classification, très sommaire, était capable de donner des résultats presque satisfaisants. Les trois groupes de points de l’exemple suivent respectivement des lois de distribution uniforme, normale et de poisson. Ces méthodes ont été en outre utilisées avec succès dans des domaines applicatifs très variés, par exemple : – pour résoudre des problèmes de neurophysiologie dans la classification des nuits de sommeil en fonction de l’activité onirique, – pour la classification des signaux traduisant la pression dans un injecteur de moteur diesel.

La méthode de groupement de PIEGAY 

Cette méthode qui est une généralisation de la méthode de groupement par propagation, présentée précédemment, repose sur les trois points suivants : – quantification de l’attachement de chaque individu classé à sa classe par un coût d’agrégation, le calcul de ce coût dépendant directement de la description a priori des classes recherchées ; – propagation, par application d’une adhérence prétopologique, des classes parmi leurs individus voisins pour lesquels elles sont susceptibles de proposer un coût d’agrégation inférieur à leur coût « courant »; il y a ainsi remise en question possible de l’appartenance d’un individu à une classe ; – utilisation d’un intérieur prétopologique pour déclasser les individus « déconnectés » de leur classe à la suite de la remise en cause de l’appartenance d’un individu à une classe. Le principe de la méthode : Chaque individu de E est muni d’un ensemble d’attributs caractéristiques, d’un voisinage, et d’une fonction structurante. L’algorithme repose sur des régions noyaux qui sont des parties, connexes, de densité locale maximale ; elles peuvent être déterminées manuellement ou automatiquement. Tout individu x (classé ou non classé) voisin d’une classe C peut y être agrégé, cette agrégation est « assortie » d’un coût d’agrégation de x à C. Ce coût d’agrégation est une valeur d’attachement de l’individu à sa classe, il est évalué sur le chemin que la classe a parcouru depuis sa région noyau jusqu’à cet individu. Il sera d’autant plus petit que l’individu x sera susceptible d’appartenir réellement à C. Un individu classé changera donc de classe si une nouvelle classe lui propose un coût d’agrégation plus faible. Cette remise en question de l’étiquetage des individus, pose des problèmes de connexité des classes; afin d’y remédier, l’auteur propose de procéder de la manière suivante : lorsqu’un individu x change d’état, cela entraîne également un changement des individus sur lesquels x a eu une influence (au sens du classement). Si x est réaffecté à une autre classe, alors les individus de la branche associée à x, c’est à dire l’ensemble des individus y tels que C est passée par l’individu x pour absorber y, doivent être déclassés, pour ne pas obtenir des classes finales disconnexes ; d’où la nécessité d’utiliser deux outils pour effectuer la segmentation d’un ensemble E (cf. Figure III.3): – une adhérence prétopologique formalisant la propagation des classes, – un intérieur prétopologique formalisant la destruction des « branches » qui ont été coupées.