Free Press

Une tâche impliquant l’apprentissage automatique peut ne pas être linéaire, mais elle comporte un certain nombre d’étapes bien connues :

• Définition du problème.
• Préparation des données.
• Apprendre un modèle sous-jacent.
• Améliorer le modèle sous-jacent par des évaluations quantitatives et qualitatives.
• Présenter le modèle.

Une bonne façon de venir à bout d’un nouveau problème est de travailler à identifier et à définir le problème de la meilleure façon possible et d’apprendre un modèle qui capture des informations significatives à partir des données. Bien que les problèmes de reconnaissance des formes et d’apprentissage automatique puissent être de différents types, ils peuvent être largement classés en trois catégories :

• Apprentissage supervisé :
  On présente au système des exemples d’entrées et leurs sorties souhaitées, données par un « enseignant », et l’objectif est d’apprendre une règle générale qui fait correspondre les entrées aux sorties.
• Apprentissage non supervisé :
  Aucune étiquette n’est donnée à l’algorithme d’apprentissage, le laissant seul pour trouver une structure dans son entrée. L’apprentissage non supervisé peut être un but en soi (découvrir des modèles cachés dans les données) ou un moyen vers une fin (apprentissage de caractéristiques).
• Apprentissage par renforcement:
  Un système interagit avec un environnement dynamique dans lequel il doit réaliser un certain objectif (comme conduire un véhicule ou jouer à un jeu contre un adversaire). Le système reçoit un retour d’information en termes de récompenses et de punitions alors qu’il navigue dans son espace problématique.

Entre l’apprentissage supervisé et l’apprentissage non supervisé se trouve l’apprentissage semi-supervisé, où l’enseignant donne un signal d’apprentissage incomplet : un ensemble d’apprentissage où il manque certaines (souvent beaucoup) des sorties cibles. Nous nous concentrerons sur l’apprentissage non supervisé et le regroupement de données dans ce billet de blog.

Apprentissage non supervisé

Dans certains problèmes de reconnaissance des formes, les données d’apprentissage consistent en un ensemble de vecteurs d’entrée x sans aucune valeur cible correspondante. L’objectif dans ces problèmes d’apprentissage non supervisé peut être de découvrir des groupes d’exemples similaires au sein des données, on parle alors de clustering, ou de déterminer comment les données sont distribuées dans l’espace, on parle alors d’estimation de densité. Pour avancer en termes plus simples, pour un espace à n échantillons x1 à xn, les véritables étiquettes de classe ne sont pas fournies pour chaque échantillon, d’où le nom d’apprentissage sans professeur.

Les problèmes de l’apprentissage non supervisé :

• L’apprentissage non supervisé est plus difficile par rapport aux tâches d’apprentissage supervisé…
• Comment savoir si les résultats sont significatifs puisqu’aucune étiquette de réponse n’est disponible ?
• Laisser l’expert regarder les résultats (évaluation externe)
• Définir une fonction objective sur le clustering (évaluation interne)

Pourquoi l’apprentissage non supervisé est nécessaire malgré ces problèmes ?

• L’annotation de grands ensembles de données est très coûteuse et donc nous ne pouvons étiqueter que quelques exemples manuellement. Exemple : Reconnaissance de la parole
• Il peut y avoir des cas où nous ne savons pas en combien/quelles classes sont divisées les données. Exemple : L’exploration de données
• Nous pouvons vouloir utiliser le clustering pour avoir un aperçu de la structure des données avant de concevoir un classificateur.

L’apprentissage non supervisé peut encore être classé en deux catégories :

• Apprentissage non supervisé paramétrique
  Dans ce cas, nous supposons une distribution paramétrique des données. Elle suppose que les données de l’échantillon proviennent d’une population qui suit une distribution de probabilité basée sur un ensemble fixe de paramètres. Théoriquement, dans une famille de distributions normales, tous les membres ont la même forme et sont paramétrés par la moyenne et l’écart-type. Cela signifie que si vous connaissez la moyenne et l’écart-type, et que la distribution est normale, vous connaissez la probabilité de toute observation future. L’apprentissage paramétrique non supervisé implique la construction de modèles de mélange gaussien et l’utilisation de l’algorithme Expectation-Maximisation pour prédire la classe de l’échantillon en question. Ce cas est beaucoup plus difficile que l’apprentissage supervisé standard car il n’y a pas d’étiquettes de réponse disponibles et donc il n’y a pas de mesure correcte de la précision disponible pour vérifier le résultat.
• Apprentissage non supervisé non paramétrique
  Dans la version non paramétrée de l’apprentissage non supervisé, les données sont regroupées en clusters, où chaque cluster(espérons-le) dit quelque chose sur les catégories et les classes présentes dans les données. Cette méthode est couramment utilisée pour modéliser et analyser des données avec des échantillons de petite taille. Contrairement aux modèles paramétriques, les modèles non paramétriques ne nécessitent pas que le modélisateur fasse des hypothèses sur la distribution de la population, et sont donc parfois appelés méthode sans distribution.

Qu’est-ce que le clustering ?

Le clustering peut être considéré comme le plus important problème d’apprentissage non supervisé ; ainsi, comme tout autre problème de ce type, il traite de la recherche d’une structure dans une collection de données non étiquetées. Une définition libre du clustering pourrait être « le processus d’organisation des objets en groupes dont les membres sont similaires d’une certaine manière ». Un cluster est donc une collection d’objets qui sont « similaires » entre eux et qui sont « dissemblables » aux objets appartenant à d’autres clusters.

Clustering basé sur la distance.

Donné un ensemble de points, avec une notion de distance entre les points, regrouper les points en un certain nombre de clusters, tels que

• les distances internes (à l’intérieur du cluster) doivent être faibles c’est-à-dire.e membres des clusters sont proches/similaires les uns des autres.
• les distances externes (intra-clusters) doivent être grandes c’est-à-dire que les membres de différents clusters sont dissemblables.

Les objectifs du clustering

Le but du clustering est de déterminer le regroupement interne dans un ensemble de données non étiquetées. Mais comment décider ce qui constitue un bon clustering ? On peut montrer qu’il n’existe pas de « meilleur » critère absolu qui serait indépendant de l’objectif final du clustering. Par conséquent, c’est l’utilisateur qui doit fournir ce critère, de manière à ce que le résultat du clustering réponde à ses besoins.

Dans l’image ci-dessus, comment savoir quelle est la meilleure solution de clustering ?

Pour trouver une solution de clustering particulière , nous devons définir les mesures de similarité pour les clusters.

Mesures de proximité

Pour le clustering, nous devons définir une mesure de proximité pour deux points de données. La proximité signifie ici à quel point les échantillons sont similaires/dissimilaires les uns par rapport aux autres.

• Mesure de similarité S(xi,xk) : grande si xi,xk sont similaires
• Mesure de dissimilarité(ou distance) D(xi,xk) : petite si xi,xk sont similaires

Il existe différentes mesures de similarité qui peuvent être utilisées.

• Vecteurs : Distance cosinus

• Ensembles : Distance Jaccard

• Points : Distance euclidienne
  q=2

Une « bonne » mesure de proximité est TRES dépendante de l’application. Les clusters doivent être invariants sous les transformations « naturelles » du problème. De plus, lors du clustering, il n’est pas conseillé de normaliser les données qui sont tirées de plusieurs distributions.

Algorithmes de clustering

Les algorithmes de clustering peuvent être classés comme indiqué ci-dessous :

• Clustering exclusif
• Clustering chevauchant
• Clustering hiérarchique
• Clustering probabiliste

Dans le premier cas, les données sont regroupées de manière exclusive, de sorte que si un certain point de données appartient à un cluster défini, alors il ne pourrait pas être inclus dans un autre cluster. Un exemple simple de cela est montré dans la figure ci-dessous, où la séparation des points est réalisée par une ligne droite sur un plan bi-dimensionnel.

Au contraire, le deuxième type, le clustering par recouvrement, utilise des ensembles flous pour regrouper les données, de sorte que chaque point peut appartenir à deux ou plusieurs clusters avec différents degrés d’appartenance. Dans ce cas, les données seront associées à une valeur d’appartenance appropriée.

Un algorithme de clustering hiérarchique est basé sur l’union entre les deux clusters les plus proches. La condition de départ est réalisée en fixant chaque point de données comme un cluster. Après quelques itérations, il atteint les clusters finaux voulus.

Enfin, le dernier type de clustering utilise une approche complètement probabiliste.

Dans ce blog, nous allons parler de quatre des algorithmes de clustering les plus utilisés :

• K-means
• K-means flou
• Clustering hiérarchique
• Mélange de gaussiens

Chacun de ces algorithmes appartient à l’un des types de clustering énumérés ci-dessus. Alors que, K-means est un algorithme de clustering exclusif, Fuzzy K-means est un algorithme de clustering chevauchant, le clustering hiérarchique est évident et enfin Mixture de Gaussiens est un algorithme de clustering probabiliste. Nous allons discuter de chaque méthode de clustering dans les paragraphes suivants.

K-Means Clustering

K-means est l’un des algorithmes d’apprentissage non supervisé les plus simples qui résout le problème de clustering bien connu. La procédure suit une méthode simple et facile pour classer un ensemble de données donné à travers un certain nombre de clusters (supposons k clusters) fixés a priori. L’idée principale est de définir k centres, un pour chaque cluster. Ces centres doivent être placés de manière intelligente car un emplacement différent entraîne des résultats différents. Ainsi, le meilleur choix est de les placer aussi loin que possible les uns des autres. L’étape suivante consiste à prendre chaque point appartenant à un ensemble de données donné et à l’associer au centroïde le plus proche. Lorsqu’aucun point n’est en attente, la première étape est terminée et un premier groupage est effectué. A ce stade, nous devons recalculer k nouveaux centroïdes comme barycentres des clusters résultant de l’étape précédente. Après avoir obtenu ces k nouveaux centroïdes, une nouvelle liaison doit être effectuée entre les mêmes points de l’ensemble de données et le nouveau centroïde le plus proche. Une boucle a été générée. Le résultat de cette boucle est que les k centroïdes changent de position pas à pas jusqu’à ce qu’il n’y ait plus de changement. En d’autres termes les centroïdes ne se déplacent plus.

Enfin, cet algorithme vise à minimiser une fonction objectif, dans ce cas une fonction d’erreur au carré. La fonction objectif

où

est une mesure de distance choisie entre un point de données xi et le centre de cluster cj, est un indicateur de la distance des n points de données par rapport à leurs centres de grappes respectifs.

L’algorithme se compose des étapes suivantes :

• Détente X = {x1,x2,x3,……..,xn} l’ensemble des points de données et V = {v1,v2,…….,vc} l’ensemble des centres.
• Sélectionne aléatoirement ‘c’ centres de grappes.
• Calcule la distance entre chaque point de données et les centres de grappes.
• Attribuer le point de données au centre de cluster dont la distance au centre de cluster est minimale de tous les centres de cluster.
• Recalculer le nouveau centre de cluster en utilisant :

où, ‘ci’ représente le nombre de points de données dans ie cluster.

• Recalculer la distance entre chaque point de données et les centres de cluster nouvellement obtenus.
• Si aucun point de données n’a été réaffecté, alors arrêter, sinon répéter à partir de l’étape 3).

Bien que l’on puisse prouver que la procédure se terminera toujours, l’algorithme k-means ne trouve pas nécessairement la configuration la plus optimale, correspondant au minimum global de la fonction objectif. L’algorithme est aussi significativement sensible aux centres de clusters initiaux sélectionnés aléatoirement. L’algorithme k-means peut être exécuté plusieurs fois pour réduire cet effet.

K-means est un algorithme simple qui a été adapté à de nombreux domaines de problèmes. Comme nous allons le voir, il est un bon candidat pour une extension afin de travailler avec des vecteurs de caractéristiques flous.

La procédure k-means peut être vue comme un algorithme avide de partitionner les n échantillons en k clusters de manière à minimiser la somme des distances au carré aux centres des clusters. Elle présente cependant quelques faiblesses :

• La façon d’initialiser les moyennes n’était pas spécifiée. Une façon populaire de commencer est de choisir aléatoirement k des échantillons.
• Il peut arriver que l’ensemble des échantillons les plus proches de mi soit vide, de sorte que mi ne peut pas être mis à jour. C’est un problème qui doit être traité lors de l’implémentation, mais qui est généralement ignoré.
• Les résultats dépendent de la valeur de k et il n’y a pas de manière optimale de décrire un meilleur « k ».

Ce dernier problème est particulièrement gênant, car nous n’avons souvent aucun moyen de savoir combien de clusters existent. Dans l’exemple présenté ci-dessus, le même algorithme appliqué aux mêmes données produit le clustering 3-means suivant. Est-il meilleur ou pire que le clustering à 2 moyens ?

Malheureusement, il n’existe pas de solution théorique générale pour trouver le nombre optimal de clusters pour tout ensemble de données donné. Une approche simple est de comparer les résultats de plusieurs exécutions avec différentes classes k et de choisir la meilleure selon un critère donné, mais nous devons être prudents car l’augmentation de k entraîne des valeurs de fonction d’erreur plus petites par définition, mais augmente également le risque de sur-ajustement.

Fuzzy K-Means Clustering

Dans le clustering flou, chaque point a une probabilité d’appartenir à chaque cluster, plutôt que d’appartenir complètement à un seul cluster comme c’est le cas dans le k-means traditionnel. Le k-means flou essaie spécifiquement de traiter le problème où les points sont quelque peu entre les centres ou autrement ambigus en remplaçant la distance par la probabilité, qui bien sûr pourrait être une fonction de la distance, comme avoir une probabilité relative à l’inverse de la distance. Le k-means flou utilise un centroïde pondéré basé sur ces probabilités. Les processus d’initialisation, d’itération et de fin sont les mêmes que ceux utilisés dans les k-means. Les clusters qui en résultent sont mieux analysés en tant que distributions probabilistes plutôt qu’en tant qu’assignation stricte d’étiquettes. On doit réaliser que le k-means est un cas particulier de k-means flou lorsque la fonction de probabilité utilisée est simplement 1 si le point de données est le plus proche d’un centroïde et 0 sinon.

L’algorithme de k-means flou est le suivant :

• Supposons un nombre fixe de clusters K.
• Initialisation : Initialiser aléatoirement les k-means μk associés aux clusters et calculer la probabilité que chaque point de données Xi soit membre d’un cluster K donné,
  P(PointXiHasLabelK|Xi,K).
• Itération : Recalculer le centroïde du cluster comme centroïde pondéré étant donné les probabilités d’appartenance de tous les points de données Xi :

• Terminaison : Itérer jusqu’à convergence ou jusqu’à ce qu’un nombre d’itérations spécifié par l’utilisateur ait été atteint (l’itération peut être piégée à certains maxima ou minima locaux)

Pour mieux comprendre, nous pouvons considérer cet exemple simple mono-dimensionnel. Étant donné un certain ensemble de données, supposons de le représenter comme distribué sur un axe. La figure ci-dessous le montre :

En regardant l’image, nous pouvons identifier deux clusters à proximité des deux concentrations de données. Nous les appellerons « A » et « B ». Dans la première approche présentée dans ce tutoriel – l’algorithme k-means – nous avons associé chaque point de données à un centroïde spécifique ; par conséquent, cette fonction d’appartenance ressemblait à ceci :

Dans l’approche Fuzzy k-means, au contraire, le même point de données donné n’appartient pas exclusivement à un cluster bien défini, mais il peut être placé de manière intermédiaire. Dans ce cas, la fonction d’appartenance suit une ligne plus lisse pour indiquer que chaque point de données peut appartenir à plusieurs clusters avec un degré d’appartenance différent.

Dans la figure ci-dessus, le point de données représenté par un point marqué en rouge appartient davantage au cluster B plutôt qu’au cluster A. La valeur 0,2 de ‘m’ indique le degré d’appartenance à A pour ce point de données.

Algorithmes de clustering hiérarchique

Sous réserve d’un ensemble de N éléments à clusteriser, et d’une matrice de distance (ou de similarité) N*N, le processus de base du clustering hiérarchique est le suivant :

• Commencez par affecter chaque élément à un cluster, de sorte que si vous avez N éléments, vous avez maintenant N clusters, chacun contenant un seul élément. Laissez les distances (similarités) entre les clusters identiques aux distances (similarités) entre les éléments qu’ils contiennent.
• Recherchez la paire de clusters la plus proche (la plus similaire) et fusionnez-les en un seul cluster, de sorte que vous avez maintenant un cluster de moins.
• Calculez les distances (similarités) entre le nouveau cluster et chacun des anciens clusters.
• Répétez les étapes 2 et 3 jusqu’à ce que tous les éléments soient regroupés en un seul cluster de taille N.

Clustering as a Mixture of Gaussians

Il existe une autre façon de traiter les problèmes de clustering : une approche basée sur le modèle, qui consiste à utiliser certains modèles pour les clusters et à tenter d’optimiser l’ajustement entre les données et le modèle.

En pratique, chaque cluster peut être représenté mathématiquement par une distribution paramétrique, comme une gaussienne. L’ensemble des données est donc modélisé par un mélange de ces distributions.
Un modèle de mélange à forte vraisemblance tend à présenter les traits suivants :

• les distributions des composantes ont des « pics » élevés (les données d’un cluster sont serrées);
• le modèle de mélange « couvre » bien les données (les modèles dominants dans les données sont capturés par les distributions des composantes).

Principaux avantages du clustering basé sur un modèle :

• Des techniques d’inférence statistique bien étudiées sont disponibles ;
• flexibilité dans le choix de la distribution des composants ;
• obtenir une estimation de la densité pour chaque cluster ;
• une classification « douce » est disponible.

Mélange de gaussiennes
La méthode de clustering de ce type la plus utilisée est basée sur l’apprentissage d’un mélange de gaussiennes :

Un modèle de mélange est un mélange de k distributions composantes qui font collectivement une distribution de mélange f(x) :

L’αk représente la contribution de la kième composante dans la construction de f(x). En pratique, les distributions paramétriques (par exemple les gaussiennes), sont souvent utilisées car beaucoup de travail a été fait pour comprendre leur comportement. Si vous remplacez chaque fk(x) par une gaussienne, vous obtenez ce que l’on appelle un modèle de mélange gaussien (GMM).

L’algorithme EM

L’espérance-maximisation suppose que vos données sont composées de multiples distributions normales multivariées (notez qu’il s’agit d’une hypothèse très forte, en particulier lorsque vous fixez le nombre de clusters !) Autrement dit, EM est un algorithme pour maximiser une fonction de vraisemblance lorsque certaines des variables de votre modèle ne sont pas observées (c’est-à-dire lorsque vous avez des variables latentes).
Vous pourriez équitablement demander, si nous essayons simplement de maximiser une fonction, pourquoi ne pas utiliser la machinerie existante pour maximiser une fonction. Eh bien, si vous essayez de maximiser cette fonction en prenant des dérivés et en les mettant à zéro, vous découvrez que dans de nombreux cas, les conditions de premier ordre n’ont pas de solution. Il y a un problème de la poule et de l’œuf en ce sens que pour résoudre vos paramètres de modèle, vous devez connaître la distribution de vos données non observées ; mais la distribution de vos données non observées est une fonction de vos paramètres de modèle.

L’Expectation-Maximisation tente de contourner ce problème en devinant itérativement une distribution pour les données non observées, puis en estimant les paramètres du modèle en maximisant quelque chose qui est une borne inférieure sur la fonction de vraisemblance réelle, et en répétant jusqu’à convergence :

L’algorithme d’Expectation-Maximisation

• Débuter avec une supposition pour les valeurs de vos paramètres de modèle
• E-étape : Pour chaque point de données qui a des valeurs manquantes, utilisez votre équation de modèle pour résoudre la distribution des données manquantes compte tenu de votre estimation actuelle des paramètres du modèle et compte tenu des données observées (notez que vous résolvez une distribution pour chaque valeur manquante, et non pour la valeur attendue). Maintenant que nous avons une distribution pour chaque valeur manquante, nous pouvons calculer l’espérance de la fonction de vraisemblance par rapport aux variables non observées. Si notre estimation du paramètre du modèle était correcte, cette vraisemblance attendue sera la vraisemblance réelle de nos données observées ; si les paramètres n’étaient pas corrects, il s’agira simplement d’une borne inférieure.
• Étape M : Maintenant que nous avons une fonction de vraisemblance attendue sans variables non observées, maximisez la fonction comme vous le feriez dans le cas entièrement observé, pour obtenir une nouvelle estimation des paramètres de votre modèle.
• Répétez jusqu’à convergence.

Problèmes associés au regroupement

Le regroupement pose un certain nombre de problèmes. Parmi eux :

• traiter un grand nombre de dimensions et un grand nombre de données peut être problématique en raison de la complexité du temps ;
• l’efficacité de la méthode dépend de la définition de la « distance » (pour le clustering basé sur la distance). Si une mesure de distance évidente n’existe pas, nous devons la « définir », ce qui n’est pas toujours facile, surtout dans les espaces multidimensionnels;
• le résultat de l’algorithme de clustering (qui, dans de nombreux cas, peut être lui-même arbitraire) peut être interprété de différentes manières.

Applications possibles

Les algorithmes de clustering peuvent être appliqués dans de nombreux domaines, par exemple :

• Marketing : trouver des groupes de clients ayant un comportement similaire étant donné une grande base de données de clients contenant leurs propriétés et leurs achats passés ;
• Biologie : classification des plantes et des animaux étant donné leurs caractéristiques ;
• Assurances : identification de groupes de titulaires de polices d’assurance automobile ayant un coût moyen de sinistre élevé ; identification des fraudes ;
• Études sur les tremblements de terre : regroupement des épicentres de tremblements de terre observés pour identifier les zones dangereuses ;
• World Wide Web : classification des documents ; regroupement des données de weblogs pour découvrir des groupes de modèles d’accès similaires.