Les fondements du machine learning

Découvrir la méthode k-means

TESTEZ LINKEDIN LEARNING GRATUITEMENT ET SANS ENGAGEMENT

Tester maintenant Afficher tous les abonnements
Initiez-vous à la méthode de partitionnement de données k-means (k-moyennes) et découvrez quelques algorithmes alternatifs.
08:05

Transcription

Relativement aux algorithmes non-supervisés de type clustering il est très fréquent, dans le domaine académique et dans la pratique, de commencer par étudier un classique qui s'appelle l'algorithme nommé K-means, c'est-à-dire des K-moyennes. Cette technique de clustering est incontestablement une des plus populaires parmi les techniques de Machine learning en général. Il faut savoir d'ailleurs qu'elle fait partie aussi des top 10 de l'IEE et donc de la "Section de l'International Conference" en data mining. Alors maintenant l'idée c'est quoi ? C'est que pour une population de données définie par des attributs, c'est-à-dire des propriétés comme longueur, poids, salaire et autres, cet algorithme, qui est un algorithme itératif comme je vais vous le montrer un peu plus tard, partitionne les données en K-groupes donc en K-clusters en minimisant la distance entre les individus et le centre du cluster auquel ils appartiennent et en maximisant la distance inter-centres. Il faut entendre par ici, ce qu'on entend par centre, la notion de centre comme la moyenne arithmétique des variables, du moins basiquement, après il y a d'autres techniques de mesures plus robustes comme la valeur modale ou la médiane. De façon figurée, ça ressemble à la chose suivante : si on imagine qu'on a un ensemble de données qui sont décrites par deux attributs, c'est-à-dire deux coordonnées numériques, mais sachez qu'il y a également des algorithmes qui font du K-means avec des variables qualitatives, on peut représenter les points sur un plan et ensuite l'idée c'est de trouver, de façon un peu empirique, peut-être meilleure que l'être humain, une façon de regrouper ces points. Maintenant qu'on a un peu cette idée, je vais vous illustrer ça par un exemple. Considérez le tableau de données suivant, on a des lignes de données donc des enregistrements avec des poids et des longueurs. J'ai labellisé chacune des lignes. Attention c'est pas un algorithme supervisé, c'est pas parce que j'utilise le terme labellisé, c'est juste pour vous faciliter l'explication. Maintenant qu'est-ce qu'on va faire ? Alors une approche simpliste de l'algorithme des K-means, c'est de prendre deux points au hasard sachant que j'aimerais, par exemple, AK = A2 et par exemple, aléatoirement, imaginez que ça me donne donc le cluster 1a et pour le cluster 2 ça me donne d donc la coordonnée de a c'est (12,10) et celle de d c'est (50,100), ce qui correspondait aux deux attributs précédents. Maintenant, une fois qu'on a choisi ces deux centres, on va calculer la distance entre chacun des points que l'on a dans le tableau d'origine avec les deux centres que l'on vient de choisir et on calcule cette distance, par exemple en utilisant la distance topologique euclidienne. Évidemment si vous observez le tableau que vous voyez maintenant sur votre écran, l'objet a est à une distance nulle de lui-même, l'objet d est aussi à une distance nulle de lui-même et respectivement ils appartiennent chacun à leur propre cluster pour le coup. Mais si on prend par euclidienne de 55 de a, il est à une distance euclidienne de 42,72 de d. Pour le le coup il appartiendra à d et donc c'est-à-dire au cluster 2. Et ensuite il a ça d'itératif, l'algorithme des K-means, qu'on va recalculer la moyenne de chacun des deux clusters pour chacun des attributs, ce qui va nous donner deux nouveaux centres, le centre C1 donc le centroïde 1, pour le coup, sachant qu'il inclut a, b et c et qu'on prend la moyenne arithmétique de chacun des attributs pour calculer la nouvelle coordonnée, ça nous donnera un centre 19 et 30. Pour le cluster 2, comme il a d, e, f, g maintenant qui lui sont associés, en faisant de même, on aura 41; 25; 75. Et ensuite on recommence la manipulation, on recalcule la distance euclidienne entre chacun des points et les nouveaux centres et on voit par exemple que le point C a changé de groupe, maintenant il appartient au cluster 2. On recommence la procédure avec les nouveaux centres et, comme vous pouvez le voir, le C1 a maintenant a,b. Le C2 a c, d, e, f, g. Ils ont respectivement des nouvelles coordonnées. À nouveau il faut calculer la distance euclidienne de chaque individu par rapport au centre et réaffecter chacun au cluster qui lui est le plus proche et, comme on peut le voir, plus rien ne bouge et à partir de là on peut arrêter l'itération et, si on représente cela graphiquement, on voit bien qu'on a des points bleus qui correspondent au premier cluster, les points rouges qui correspondent au deuxième cluster avec les points jaunes qui représentent les centres respectifs des clusters. Et on a donc une ellipse autour ou un cercle, peu importe comment on représente ça de façon ludique, qui montre à quel groupe ils appartiennent. Maintenant ce qu'il faut savoir c'est qu'il n'y a pas que lorsqu'il n'y a plus d'enregistrement qui change de groupe qu'on arrête, il y a d'autres critères mathématiques qui peuvent arrêter l'itération. Tout le problème de cette méthode c'est de choisir le bon nombre de clusters et, comme je vous ai dit plus tôt et je souhaiterais revenir sur ce sujet, l'idée des K-means, vous le voyez sur la figure maintenant, c'est de minimiser la distance intra-cluster et de maximiser la distance inter-cluster. Mathématiquement ça s'écrit avec la relation mathématique que vous voyez à l'écran, c'est-à-dire que l'inertie totale c'est l'inertie inter-classe plus l'inertie intra-classe. Alors maintenant l'idée c'est quoi ? C'est de choisir le bon K et de faire varier l'inertie intra-classe, qu'on appelle aussi WSS pour wivine some of screar. En fonction de K, on va prendre le dernier K donc la dernière valeur de K qui a induit une réduction considérable de cette mesure WSS. Géométriquement parlant, à ce point K qu'on va considérer comme optimal, on observe une sorte de coude se former si on représente le WSS en fonction de K. Comme vous pouvez le voir sur l'illustration que vous avez maintenant à l'écran, on a verticalement WSS, horizontalement les K puis on voit qu'il y a un coude qui se forme pour une certaine valeur de K qui, dans le cas présent, est K = 2. Par exemple, au-delà de K = 3, le gain en information n'est plus significatif et on obtiendra un cluster ayant seulement un individu, ce qui n'est pas très pertinent pour une analyse de groupe et on risque d'avoir un sur-apprentissage. Voilà une manière de choisir K. Maintenant, évidemment, il a de nombreuses applications cet algorithme des K-means, après, au niveau de ses avantages, c'est qu'il est plutôt rapide à générer des clusters et même sur des grosses bases de données et également, vu qu'il y a des versions non paramétrées des K-means, il peut être non sensible aux valeurs aberrantes. Cependant il a un inconvénient majeur c'est que la solution finale dépend fortement du choix initial des points ou des centres des clusters. Or ces derniers sont choisis aléatoirement. Il souffre également de multicolinéarité et gère mal les clusters non-sphériques, ou non elliptiques si vous préférez. Pour pallier les problèmes du choix initial des points centraux de clusters, il existe d'autres variantes des K-Means dont les K-medoids, les K-médianes, les K-modes, les Cartes auto-organisées, les nuages dynamiques et ainsi de suite. Au moins là vous avez une petite introduction de l'idée du concept de cet algorithme.

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 !