Les fondements du machine learning

Aborder le clustering hiérarchique

TESTEZ LINKEDIN LEARNING GRATUITEMENT ET SANS ENGAGEMENT

Tester maintenant Afficher tous les abonnements
Votre formateur présente la méthode de clustering hiérarchique ainsi que le diagramme correspondant, appelé dendrogramme.
08:19

Transcription

Dans l'ordre toujours académique et en ce qui concerne spécifiquement les techniques de clustering non supervisées, un autre grand classique c'est le hierarchical clustering qui veut dire le groupement hiérarchique. Cette technique construit une suite de clusters imbriqués d'après une hiérarchie de similarité. Visuellement ça ressemble à une sorte d'arbre dont on a des racines ou, si vous préférez, on peut voir le sens inverse de l'arbre, c'est-à-dire le tronc avec les branches, peu importe. La base c'est que chaque est composé d'un individu puis ensuite de paires de clusters. Les plus similaires sont fusionnées et de nouveaux clusters qui ensuite fusionneront avec d'autres clusters jusqu'à l'obtention d'un cluster racine au sommet. Ça c'est une approche possible. Ces imbrications de clusters en différents niveaux donnent lieu graphiquement à une arborescence hiérarchique, comme vous le voyez, et puis d'ailleurs on reprend souvent dans le domaine le nom des arbres, du moins du domaine de la biologie et on a une racine tout en haut, on a des nœuds et puis on a des feuilles avec des branches et ainsi de suite. Il faut savoir que, dans le domaine du clustering hiérarchique, il y a deux types d'implémentation courante de l'algorithme. Il y a une implémentation qu'on appelle la méthode descendante ou la méthode divise qui consiste à commencer par un grand cluster constitué de l'ensemble des données et ensuite, à chaque étape, on procède par scissions successives de clusters engendrés jusqu'à ce que chaque cluster ne soit constitué que d'un individu. Ensuite il y a la méthode ascendante ou agglomérative qui fait l'inverse de la logique précédente. Elle débute avec des clusters, chacun composé d'un individu, et ensuite, à chaque étape, les clusters sont associés par paires pour former d'autres clusters qui sont à leur tour joints deux à deux jusqu'à l'obtention d'un nouveau cluster et ainsi de suite. C'est cette dernière méthode ascendante qui est la plus populaire et répandue dans les logiciels. Après, dans les cours académiques théoriques, c'est l'inverse, c'est la méthode descendante qui est la plus enseignée, qui est la plus abordable on va dire, en terme de consommation de calculs à la main. Mais nous on va se concentrer, dans cette session, sur la deuxième méthode. Pour présenter cette méthode, ce que l'on va faire c'est utiliser un jeu de données. Le jeu de données qu'on utilisera est le suivant : on a des lignes de données qu'on a labellisées, pour simplifier l'expression de l'exemple oralement, par des lettres de l'alphabet. Et puis, comme vous pouvez le voir, c'est un exemple bidimensionnel. Maintenant la chose étant c'est que, pour construire les groupes de cette hiérarchie, il faut calculer une distance entre des points ou des groupes de points. La question c'est comment est-ce qu'on va calculer cette distance ? Premièrement il y a évidemment le fait de dire que je vais prendre une distance topologique euclidienne. Certes mais la chose étant c'est que, quand vous avez des groupes de points, comment calculez-vous la distance entre un groupe et un autre ? Il y a plusieurs méthodes, on peut en construire un grand nombre bien évidemment. Parmi les grands classiques il y a, en terme de critères d'agrégation, ce qu'on appelle le Single linkage ou lien minimum, c'est que la distance entre deux clusters sera définie comme la distance la plus courte entre deux points de chaque cluster. C'est assez intuitif humainement. Ensuite, toujours dans la même idée, on a un deuxième type de critère d'agrégation qui est très courant, c'est ce qu'on appelle le Complete linkage ou le lien maximum et là, la distance est exactement l'inverse de la distance précédente, on prend la distance la plus longue entre deux points de chaque cluster. Et enfin, dans les grands classiques, on a l'average linkage ou le lien moyen où l'idée c'est que la distance entre deux clusters est définie comme la distance moyenne entre chaque point d'un cluster à chaque point de l'autre cluster. Maintenant que l'on sait ça et qu'on a notre jeu de données initiales, on y va. Qu'est-ce que l'on va faire ? D'abord on construit une matrice, c'est-à-dire un tableau à double entrée qui donne la distance euclidienne entre tous les points, entre toutes les paires de points. On obtient le tableau que vous voyez actuellement sur votre écran, en calculant bien évidemment avec la distance topologique euclidienne. Si on regarde et qu'on calcule cette distance, on voit qu'il y a certains points qui ont une distance qui est très petite, 7,07 et, si on se base sur la distance du type lien minimum ou Single linkage, qu'est-ce que l'on va faire avec ça ? L'idée c'est de dire que, pour le coup, comme g et c sont très proches, on va les grouper. Donc on les groupe et on en crée une nouvelle entité. Pour le coup, ça va nous donner la matrice à double entrée que vous voyez maintenant à l'écran. Évidemment vous vous posez peut-être une question, avant que je vous explique les tenants et aboutissants de la manière de lire cette matrice, ce tableau à double entrée, c'est qu'est-ce que l'on a choisi comme coordonnées, comme valeurs de c et de g. La méthode de calcul, je l'ai explicitée, vous la voyez sur votre écran. Par exemple pour calculer maintenant la distance entre a et (c, g) si je choisis par exemple la distance maximale entre d(a, c) et d(a, g), ça veut dire le maximum entre 48.47 et 55.04, ça donne 55.04. Comme vous pouvez peut-être le deviner, j'ai utilisé la méthode du lien maximum, c'est-à-dire qu'on définit la distance entre des clusters comme la distance la plus longue entre deux points de chaque cluster. C'est un choix, évidemment, après les algorithmes peuvent procéder de façon assez simple dans le meilleur choix parmi un ensemble de choix existants. Voilà où on en est maintenant. Après, si on regarde à nouveau cette table à double entrée ou matrice, on se rend compte qu'il y a deux valeurs qui sont minimales. Comme toujours la matrice est symétrique, on retrouve cette valeur deux fois et on recommence la procédure. Comme on peut le voir, là c'est f qui a l'air d'être à une distance minimale avec e. La prochaine étape c'est de fusionner e et f et on reprocède au même genre de calculs qu'avant, c'est-à-dire qu'on calcule, avec la méthode du Complete linkage ou du lien maximum, toutes les distances. Et à nouveau on identifie les deux plus petites valeurs et on recommence l'approche et là, comme vous pouvez le voir, on a donc à nouveau un calcul de distance et on identifie la plus petite distance et on regroupe encore une fois et encore une fois on calcule les distances et on identifie la plus petite et on regroupe encore une fois et il y a un moment où on arrive au bout. Là, comme on peut le voir, on est arrivé au bout avec (a ,b) et puis (c, g), (e, f) et (d). Toutes ces étapes, on peut les retranscrire très facilement sous la forme d'un arbre hiérarchique. Ça va vous donner l'arbre que vous voyez maintenant sur l'écran. On voit qu'effectivement il y a un moment où c'est (a, b) qui ont été fusionnés mais aussi (c, g) (e, f) et (c, g) et (e, f) ont été fusionnés ensemble puis ensuite on a eu (c, g), (e, f) et d qui ont été fusionnés et voilà on s'est arrêté sur ces deux groupes finaux, c'est très simple finalement comme algorithme. Après toute la subtilité réside dans le choix de la méthode de calcul des distances inter-groupe et également le choix de la distance topologique. On a différentes distances topologiques comme la distance Euclidienne, la distance de Manhattan, la distance de Minkowski et ainsi de suite. L'avantage du clustering hiérarchique, c'est qu'il offre la possibilité de présenter visuellement les groupes hiérarchiquement et ainsi on lit facilement les ramifications qui en découlent.

Les fondements du machine learning

Acquérez les bases du vocabulaire lié au machine learning. Découvrez les outils fondamentaux avec les idées, applications et concepts mathématiques sous-jacents à chacun.

3h04 (33 vidéos)
Aucun commentaire n´est disponible actuellement
Spécial abonnés
Date de parution :21 déc. 2017

Votre formation est disponible en ligne avec option de téléchargement. Bonne nouvelle : vous ne devez pas choisir entre les deux. Dès que vous achetez une formation, vous disposez des deux options de consultation !

Le téléchargement vous permet de consulter la formation hors ligne et offre une interface plus conviviale. Si vous travaillez sur différents ordinateurs ou que vous ne voulez pas regarder la formation en une seule fois, connectez-vous sur cette page pour consulter en ligne les vidéos de la formation. Nous vous souhaitons un excellent apprentissage avec cette formation vidéo.

N'hésitez pas à nous contacter si vous avez des questions !