|
|
|
|
|
|
Classification (non supervisée)
Aussi appelée "Segmentation".
-----
Les données de l'illustration ci-dessous sont clairement constituées de trois "clusters", mot anglais qui n'a pas d'équivalent exact en français (celui qui s'en rapproche le plus pourrait être "amas", comme dans les "amas d'étoiles" des astronomes).
Cette information est importante, car elle suggère que la population totale est en fait un mélange de trois populations ayant chacune des caractéristiques distinctes.
Le but ultime de la classification non supervisée (ou "classification automatique", ou "clustering", ou "regroupement") est d'identifier ces trois populations (image inférieure de l'illustration ci-dessus), et donc d'affecter à chaque observation une "étiquette de classe" qui matérialise l'appartenance de l'observation à une des trois classes. De plus, on souhaite pouvoir également affecter à toute nouvelle observation une étiquette de classe.
Cette situation n'est pas sans rappeler celle rencontrée en classification supervisée : les observations disponibles ont alors déjà une étiquette de classe, et l'objectif est d'affecter (en général, de façon probabiliste), une nouvelle observation à une classe. Mais le problème est ici plus difficile puisque les observations disponibles ne sont pas initialement identifiées comme appartenant à telle ou telle population : il faudra déduire cette information de la répartition spatiale des observations.
L'expression "non supervisée" fait donc référence au fait qu'aucun "superviseur" n'est là pour nous dire à quelle population appartient telle ou telle observation.
L'absence d'étiquette de classe est un lourd handicap qui n'est que très partiellement surmontable. Seule l'analyse de la répartition des observations peut permettre de "deviner" où sont les véritables classes. Les deux difficultés essentielles que rencontre la classification non supervisée sont les suivantes :
Devant un problème défini de façon aussi imparfaite, il était naturel de voir apparaître un grand nombre de techniques, souvent à fort parfum heuristique. On peut aujourd'hui les regrouper en deux grandes familles : la classification par partitionnement, et la classification hiérarchique.
L'idée générale est de découper l'espace des observations en un certain nombre de régions disjointes, définies par des frontières, et de décréter que toutes les observations situées dans une même région de l'espace appartiennent à une même classe.
Chaque classe est représentée par un "prototype", observation virtuelle sensée être la plus représentative de la population de la classe. Le prototype d'une classe sera le plus souvent le barycentre des observations de la classe.
Ces prototypes sont positionnés de façon itérative dans les zones à forte densité, et les observations sont affectées aux classes sur la base d'un critère de proximité aux différents prototypes.
-----
Il existe de nombreuses techniques de classification par partitionnement, la plus connue étant K-means (ou "K-moyennes") et ses variantes. Notez qu'un type très particulier de Réseaux de Neurones, les Cartes de Kohonen (ou "SOM") peut être perçu comme une technique de partitionnement puisque cherchant à donner, dans la mesure du possible, une représentation plane des classes qui respecte leurs positionnements relatifs dans l'espace des données.
L'idée selon laquelle chacune des classes réelles, sous-jacentes, occupe une région limitée de l'espace peut paraître irréaliste. En particulier, l'Analyse Discriminante nous a habitués à penser en termes de classes ayant des distributions multinormales, et donc se chevauchant nécessairement. Il est donc naturel de considérer la possibilité que les classes empiètent les unes sur les autres.
Cette approche reprend l'idée selon laquelle les classes ont des distributions multinormales. Pour un nombre supposé de classes K donné, on considèrera donc que l'ensemble des données est en fait un échantillon tiré de K distributions multinormales, chacune affectée d'une probabilité a priori. On cherche alors les centres et matrices de covariances de ces distributions, ainsi que les probabilités a priori, de façon à maximiser la vraisemblance des données, ce qui se fait par l'algorithme classique dit "EM" (Expectation Maximization).
Dans les mélanges de modèles, les classes se chevauchent mais chaque observation appartient à une classe et une seule (bien que la détermination de cette classe ne puisse être faite que de façon probabiliste). En classification floue, à l'inverse, on reconnait qu'une observation peut effectivement appartenir simultanément à plusieurs classes à des degrés divers dont somme est égale à 1. Cette attitude reflète le fait que dans de nombreuses situations réelles, les définitions des classes (supervisées ou non) ne rendent pas obligatoire l'appartenance à une classe et une seule (pensez aux classes "Chaud" et "Très chaud").
La classification floue affecte alors à chaque observation des degrés d'appartenance aux diverses classes d'une façon cohérente avec la répartition géométrique des données. Pour chaque observation, la somme des degrés d'appartenance à chacune des classes est égale à 1.
La "classification hiérarchique" est une famille de techniques qui génèrent des suites de partitions emboîtées les unes dans les autres, et allant depuis la partition triviale à une seule classe (contenant toutes les observations) jusqu'à la partition triviale où chaque observation est une classe. Entre ces deux extrêmes figurent de nombreuses partitions plus réalistes entre lesquelles l'analyste devra choisir.
Les classes rencontrées dans les applications ont souvent des distributions unimodales : à partir d'un noyau central, la densité des observations décroît de façon monotone dans toutes les directions de l'espace. Beaucoup de techniques de classification non supervisée s'appuient sur cette image et portent une attention particulière aux ensembles d'observations ayant entre elles de faibles distances (régions de forte densité). Elles le font de diverses façons :
* En utilisant les distances entre observations pour construire les classes (p. ex. méthodes hiérarchiques).
* En reconnaissant que les zones peuplées mais de faible inertie autour de leurs barycentres sont des zones de forte densité (K-means).
* En faisant de l'estimation de densité de façon paramétrique (modèles de mélanges) ou non paramétriques (méthodes basées sur l'estimation de densité par K-Premiers Voisins).
Un algorithme de classification non supervisée produira toujours des classes. Mais ces classes reflètent-elles la structure des données ? Chaque classe abrite-t-elle un cluster dense et ses environs immédiats, comme le souhaite l'analyste ?
Il y a deux raisons pour lesquelles une typologie peut être non satisfaisante :
Il est donc indispensable de pouvoir quantifier la qualité d'une partition, c'est à dire d'apprécier le fait que la partition correspond à des clusters présents dans les données.
-----
Il existe de nombreux critères de qualité d'une partition, ce qui signifie qu'aucun n'est universellement satisfaisant. Parmi les plus utilisés, mentionnons :
Le contenu théorique des techniques de classification non supervisée est souvent simple, ce qui laisse à penser, à tort, que la classification non supervisée est une activité dénuée de difficultés. Il n'en est rien.
La grande majorité des techniques de classification, reposant sur des notions métriques (distance, densité), exigent que les variables soient quantitatives. Cependant, il est rare que les données ne soient décrites de façon native que par des variables quantitatives. Il faut donc procéder à une phase initiale de codage des variables nominales sous forme quantitative.
Ceci se fait :
* Soit en codant les modalités des variables nominales sous forme disjonctive complète.
* Soit en soumettant les variables quantitatives à une Analyse des Correspondances Multiples, et en remplaçant dans la table des données les variables nominales par les facteurs issus de l'ACM.
-----
Notons qu'il est cependant possible de définir un degré numérique de "dissimilarité" entre observations décrites par des variables nominales. Si cette approche est retenue, la phase de codage numérique des variables nominales devient alors superflue.
L'illustration ci-dessus est trompeuse, car elle suggère la présence de clusters clairement identifiables. Le plus souvent, il n'existe pas de raison forte de croire en l'existence de tels clusters naturels et pourtant, même sur des données uniformément distribuées, et donc sans structure, les algorithmes produiront des classes. Mais le résultat d'une classification non supervisée (une "typologie") n'a de sens que si les classes identifiées correspondent effectivement à des clusters présents dans les données.
Affirmer qu'un ensemble de données contient des clusters bien définis est difficile. Deux idées directrices permettent d'aborder cette question :
* La stabilité des classes.
* L'influence du nombre de classes.
Plus précisément :
Plusieurs typologies sont construites en laissant à chaque fois de côté un sous-ensemble des données choisi aléatoirement. Si les clusters sont bien définis, cette faible réduction du nombre d'observations utilisées pour construire les typologies aura peu d'influence sur le résultat final, et les diverses typologies obtenues seront très similaires.
Par contre, si les données sont plus ou moins uniformément distribuées, les ensembles de classes finales seront très différents (pensez à des points uniformément distribués le long d'une droite : en enlevant quelques points choisis aléatoirement, on obtient à chaque fois des "classes" très différentes).
Si l'analyse est conduite avec le "bon" nombre de classes (voir ci-dessous), il est possible d'obtenir une typologie particulièrement convaincante. Par contre, si les données ne sont que faiblement structurées, toutes les typologies obtenues seront également "mauvaises", quel que soit le nombre de classes.
Beaucoup de techniques (en particulier les techniques par partitionnement) tendent à former des classes convexes. Cette restriction n'a aucune raison de correspondre à la réalité et quels que soient les efforts de l'analyste, la classification obtenue ne correspondra alors jamais à la structure réelle des données, même si les clusters réels sont nettement séparés.
Dans l'illustration ci-dessus, la ligne pointillée représente la frontière que l'on aimerait identifier entre les deux clusters naturels. Mais une partition en deux classes convexes donnera un résultat comme celui de l'image inférieure de cette illustration, qui ne correspond pas à la structure réelle des données.
-----
Il existe des techniques permettant une plus grande flexibilité dans la forme des classes obtenues (CURE, ROCK, BIRCH etc...), mais elles sont plus complexes à utiliser que les techniques les plus populaires.
Toutes les méthodes de classification non supervisées permettent à l'analyste de choisir le nombre de classes de la partition finale (niveau de la coupure de l'arbre en classification hiérarchique, nombre de prototypes en K-means etc...).
Cette possibilité est une arme à double tranchant. Si la population contient effectivement des clusters bien identifiables, mais si le choix du nombre de classes finales ne correspond pas au nombre de clusters, alors la partition :
* Soit regroupera à tort des clusters séparés (pas assez de classes, illustration ci-dessous),
* Soit découpera en plusieurs classes des clusters homogènes (trop de classes, image inférieure de l'illustration ci-dessous).
Dans le premier cas, la typologies sera dit "trop grossière", ou ayant une "granularité trop forte". Dans le deuxième cas, la typologie sera dite "trop fine", ou ayant une "granularité trop petite".
-----
La recherche du nombre approprié de classes est toujours une phase indispensable dans la construction d'une classification de données, mais elle est longue et souvent ambiguë.
Il n'y a pas de formule permettant de calculer ce nombre à partir des données. La recherche se fait par essais et erreurs. Une même technique est utilisée à plusieurs reprises avec un nombre croissant de classes, et pour chaque nouvelle partition obtenue, on calcule la valeur d'un critère de qualité (voir ci-dessus). Le nombre de classes retenu est celui qui conduit à la meilleure valeur de ce critère.
--
On peut également utiliser des aides graphiques. Si une quantité
évolue de façon monotone avec le nombre de classes, et tend vers une
asymptote horizontale lorsque le nombre de classes augmente, on cherche
dans la courbe représentant l'évolution de cette quantité une "cassure"
après laquelle son évolution devient négligeable. Le nombre de classes retenu
est alors celui correspondant à la cassure.
Un exemple de telle aide
graphique est le graphe
des distances en classification hiérarchique.
Lorsque le choix d'une partition a été retenu, il convient de caractériser les classes constituant cette partition. Au-delà des interprétations élémentaires (liste des observations dans chaque classe, coordonnées des barycentre, analyses univariées...), il existe des méthodes d'interprétation plus riches en enseignements, mais plus difficiles à mettre en œuvre. Mentionnons :
Mentionnons enfin qu'il est possible de procéder à une classification non supervisée non pas sur des observations mais sur des variables. La dissimilarité entre deux variables (similaire à la distance entre observations) est en général définie à partir de leur coefficient de corrélation, des variables fortement corrélées étant alors considérées comme "proches".
Une telle classification peut être est utile lorsque les variables sont nombreuses et présentent un fort risque de collinéarité. Après classification, toutes les variables d'une classe seront alors remplacées par une unique variable synthétique représentant au mieux l'ensemble des variables de la classe.
________________________________
Voir aussi:
|
|
|
|
Téléchargez ce Glossaire |
|
