De quelles solutions disposons nous lorsque notre dataset n’a pas labels, ou n’est pas étiqueté? L’apprentissage non supervisé est un groupe d’algorithmes et d’approches d’apprentissage automatique qui fonctionne dans ce cas de figure.
La définition que l’on trouve sur Wikipedia est la suivante : Dans le domaine informatique et de l’intelligence artificielle, l’apprentissage non supervisé est un problème d’apprentissage automatique. Il s’agit, pour un logiciel, de trouver des structures sous-jacentes à partir de données non étiquetées. Puisque les données ne sont pas étiquetées, il n’est pas possible d’affecter au résultat de l’algorithme utilisé un score d’adéquation. Cette absence d’étiquetage (ou d’annotation) est ce qui distingue les tâches d’apprentissage non-supervisé des tâches d’apprentissage supervisé.
K-MEANS
Le premier algorithme d’apprentissage non supervisé est l’algorithme de classification Κ-means. K-means utilise un raffinement itératif pour produire un résultat final. Les entrées de l’algorithme sont le nombre de clusters et le data set non étiqueté. L’ensemble de données est un ensemble de caractéristiques pour chaque point de données. Les algorithmes commencent par les estimations initiales pour les Κ centroïdes. Ces centroïdes peuvent être générés de manière aléatoire ou directement à partir du dataset. K-means procède par itérations selon deux étapes:
a) Affectation des données:
Chaque centroïde définit l’un des clusters. Dans cette étape, on assigne chaque point de données à son centroïde le plus proche, en fonction de la distance euclidienne au carré.
b) Étape de mise à jour des Centroïdes:
Dans cette étape, les centroïdes sont recalculés. Ceci se fait en prenant la moyenne de tous les points de données assignés au cluster de ce centroïde.
L’algorithme itère entre les étapes 1 et 2 jusqu’à ce qu’un critère d’arrêt soit satisfait. Le critère d’arrêt peut soit être qu’aucun point de données ne change de cluster, ou que la somme des distances est minimisée ou bien que l’on atteint le nombre maximal d’itérations. Ce nombre pouvant être défini avant le début de l’algorithme.
Cet algorithme converge forcement vers un résultat. Le résultat peut être un optimum local. C’est-à-dire pas nécessairement le meilleur résultat possible, ce qui signifie que l’évaluation de plusieurs exécutions de l’algorithme avec des centroïdes de départ randomisés peut donner un meilleur résultat.
Classification hiérarchique
La mise en cluster hiérarchique est similaire à la mise en cluster normale, sauf que dans ce cas nous souhaitons mettre en place une hiérarchie des clusters. Cela peut s’averer très important surtout quand vous désirez une flexibilité par rapport au nombre de clusters voulu. Par exemple, imaginez que vous regroupiez des éléments sur un marché en ligne tel qu’Etsy ou Amazon. Sur la page d’accueil, vous souhaiterez une navigation simple dans quelques grandes catégories d’articles. Toutefois, lorsque vous entrez dans des catégories de magasinage plus spécifiques, vous avez besoin de niveaux de granularité croissants. C’est-à-dire de groupes d’articles plus distincts.
En matière d’outputs de l’algorithme, en outre des assignations de clusters, vous obtenez également une arborescence qui vous renseigne sur les hiérarchies entre les clusters. Vous pouvez ensuite choisir le nombre de clusters que vous souhaitez dans cet arbre.
Voici les étapes pour la mise en cluster hiérarchique:
a) Commencez avec N clusters, un pour chaque point de données.
b) Fusionnez les deux groupes les plus proches l’un de l’autre. Maintenant, vous avez N-1 clusters.
c) Recalculez les distances entre les clusters. Il existe plusieurs façons de procéder (voir ce tutoriel pour plus de détails). L’un d’eux consiste à considérer la distance entre deux clusters comme la distance moyenne entre tous leurs membres respectifs.
d) Répétez les étapes 2 et 3 jusqu’à obtenir un cluster de N points de données. Vous obtenez un arbre, également appelé dendrogramme.
e) Choisissez un certain nombre de groupes et tracez une ligne horizontale dans le dendrogramme. En général, le nombre de groupes que vous obtenez est le nombre de points d’intersection de votre ligne horizontale avec les lignes verticales du dendrogramme.
Le clustering par décalage moyen
Le clustering par décalage moyen est un algorithme basé sur une fenêtre glissante qui tente de trouver des zones denses de points de données. C’est un algorithme basé sur un centroïde, ce qui signifie que l’objectif est de localiser les points centraux de chaque groupe / classe, ce qui fonctionne en mettant à jour les candidats pour que les points centraux soient la moyenne des points dans la fenêtre glissante. Ces fenêtres candidates sont ensuite filtrées dans une étape de post-traitement pour éliminer les quasi-doublons, formant ainsi le dernier ensemble de points centraux et leurs groupes correspondants. Consultez le graphique ci-dessous pour une illustration.
Regroupement à décalage moyen pour une seule fenêtre coulissante.
Explications
Pour expliquer le décalage moyen, nous allons considérer un ensemble de points dans un espace à deux dimensions, comme dans l’illustration ci-dessus. Nous commençons par une fenêtre glissante circulaire centrée sur un point C (sélectionné aléatoirement) et dont le rayon est le noyau. Le décalage moyen est un algorithme qui consiste à déplacer ce noyau de manière itérative vers une région de densité supérieure à chaque étape jusqu’à la convergence.
À chaque itération, on déplace la fenêtre glissante vers les régions de densité supérieure en déplaçant le point central vers la moyenne des points situés dans la fenêtre (d’où son nom). La densité à l’intérieur de la fenêtre glissante est proportionnelle au nombre de points qu’elle contient. Naturellement, en se déplaçant vers la moyenne des points de la fenêtre, il se déplacera progressivement vers des zones de densité de points plus élevée.
Nous continuons de décaler la fenêtre glissante en fonction de la moyenne jusqu’à ce qu’il n’y ait plus aucune direction dans laquelle un décalage peut accueillir plus de points à l’intérieur du noyau. Découvrez le graphique ci-dessus; nous continuons à déplacer le cercle jusqu’à ce que nous n’augmentions plus la densité (c’est-à-dire le nombre de points dans la fenêtre).
Ce processus des étapes 1 à 3 s’effectue avec de nombreuses fenêtres coulissantes jusqu’à ce que tous les points se trouvent dans une fenêtre. Lorsque plusieurs fenêtres glissantes se chevauchent, on conserve la fenêtre contenant le plus de points. Les points de données sont ensuite regroupés en fonction de la fenêtre glissante dans laquelle ils résident.
Apriori
L’algorithme Apriori s’utilise dans une base de données transactionnelle pour extraire des ensembles d’éléments fréquents, puis générer des règles d’association. Il est couramment utilisé dans l’analyse des paniers de marché, où l’on vérifie les combinaisons de produits qui apparaissent fréquemment dans la base de données. En général, nous écrivons la règle d’association pour «si une personne achète l’élément X, elle achète ensuite l’élément Y» comme suit: X -> Y.
Exemple: si une personne achète du lait et du sucre, elle achètera probablement de la poudre de café. Cela pourrait être écrit sous la forme d’une règle d’association comme suit: {lait, sucre} -> café en poudre. Les règles d’association sont générées après le franchissement du seuil de support et de confiance.
La mesure de support permet d’éliminer le nombre d’ensembles d’éléments à prendre en compte lors de la génération fréquente d’ensembles. Cette mesure de soutien est guidée par le principe Apriori. Le principe Apriori stipule que si un ensemble d’éléments est fréquent, tous ses sous-ensembles doivent également l’être.
Vous pouvez retrouver 5 algorithmes d’apprentissage supervisé en cliquant ici.
