Bienvenue à tous ! Je suis très heureux de vous retrouver dans cet épisode, qui poursuit notre aperçu des techniques de base en apprentissage automatique.

Dans cette section, nous nous intéresserons à l'apprentissage non supervisé et, en particulier, à ce qu'on appelle le clustering.

Algorithmes supervisés vs non supervisés

Tout d'abord, rappelons que les algorithmes que nous avons abordés jusqu'à présent étaient supervisés, c'est-à-dire que les résultats obtenus étaient basés sur un ensemble de données déjà "étiquetées" (dans lequel chaque entrée est associée à la sortie correcte). Dans la plupart des cas, ces données étaient utilisées pour entraîner le modèle, tandis que dans d'autres cas, elles servaient au moment des prédictions. Voir les articles précédents sur la régression linéaire et la classification pour plus de détails.

Les algorithmes d'apprentissage non supervisé (comme ceux de clustering) ne se basent pas sur des observations existantes. Au contraire, leur particularité est de partir de données non étiquetées pour y détecter des similitudes, des corrélations, autrement dit, pour extraire de l'information sans pouvoir s'appuyer sur des observations réelles antérieures.

Qu'est-ce que le clustering ?

Le clustering, en apprentissage automatique, est une technique d'apprentissage non supervisé utilisée pour regrouper automatiquement un ensemble de données en sous-groupes (ou clusters) en fonction de leur similarité.

L'objectif est d'identifier des structures cachées dans les données, de sorte que celles appartenant au même cluster soient plus similaires entre elles qu'à celles des autres clusters.

Le premier exemple de cette technique remonte aux années 50, mais les évolutions ont été constantes et divers améliorations et approches du problème ont vu le jour au fil des années, jusqu'à aujourd'hui.

Applications du clustering

Le clustering automatique est utilisé dans de nombreux secteurs de la vie quotidienne, notamment dans la segmentation de la clientèle en marketing. Un algorithme est appliqué pour regrouper les clients en différents groupes en fonction de leurs caractéristiques, telles que l'âge, le temps passé sur un site web, le nombre d'achats, le type d'achats, etc.

Une fois ces groupes identifiés, des campagnes de marketing ciblées peuvent être créées pour chaque groupe de clients (par exemple, il serait inapproprié d'envoyer des promotions pour des barbecues électriques à des clients végétaliens crudivores).

Types de clustering

Approfondissons pour découvrir les principales catégories d'algorithmes de clustering, leurs caractéristiques, domaines d'application, points forts et faiblesses.

Clustering basé sur les partitions

Le clustering basé sur les partitions divise un ensemble de données en groupes (ou clusters) prédéfinis. Dans cette technique, chaque donnée appartient à un et un seul cluster. L'objectif est de trouver une répartition qui minimise la distance entre les points à l'intérieur de chaque cluster et maximise la distance entre les points de clusters différents.

K-Means

K-Means, formalisé en 1956 par Ball et Hall, est l’un des algorithmes de clustering les plus populaires.

Il utilise une approche itérative qui, en partant de positions aléatoires, permet d’identifier les clusters de manière efficace.

Nous allons analyser un exemple concret de cet algorithme, tant parce qu’il est parmi les plus utilisés que parce que l’intuition sous-jacente est relativement simple à comprendre.

Partons de la configuration de données suivante (voir le diagramme), représentant des observations basées sur deux variables (nous passerons les détails non essentiels à la compréhension).

Commençons par choisir le nombre de clusters (quatre dans ce cas) que l’on souhaite définir et plaçons autant de centroïdes (un centroïde, c’est comme le centre de gravité d’un ensemble de points dans notre cas) de manière aléatoire (les petits carrés dans la figure). Nous créons donc un cluster pour chaque centroïde en nous basant sur la distance euclidienne des points (étape 2).

Déplaçons les centroïdes de manière à ce qu’ils se trouvent « au centre » de leur cluster actuel.

Recréons les partitions en nous basant sur la nouvelle position des centroïdes (on voit comment un point de couleur verte est passé du cluster vert au cluster bleu)(étape 3).

À l'étape 4, le déplacement des centroïdes n'a aucun effet sur les points des clusters, donc le calcul s'arrête. Nous avons partitionné l'ensemble en le nombre de groupes choisi.

Dans l'animation suivante, nous pouvons observer le comportement de K-Means pour un ensemble de 100 éléments et six clusters.

Applications

L'une des utilisations les plus courantes du K-Means est la segmentation des clients, dont nous avons parlé plus haut, mais ses caractéristiques de simplicité et de performance le rendent également très apprécié dans les moteurs de recommandation, la segmentation d'images et bien d'autres domaines.

Dans certains contextes, le K-Means s'est avéré très utile pour la détection de spams (un domaine généralement réservé aux classifieurs). En se basant sur des métriques comme la longueur du texte ou la fréquence de certains mots-clés (par exemple : prince, héritage, millions, etc.), un algorithme de clustering peut séparer les messages en deux ou plusieurs groupes sans avoir besoin d'exemples préalables.

Les clusters ainsi obtenus seront ensuite analysés et étiquetés comme spam ou non spam, en fonction, par exemple, de la fréquence de ces mots-clés. La particularité de cette approche réside dans sa capacité à identifier de nouvelles typologies de messages malveillants.

Avantages et inconvénients

Comme mentionné, c'est l'un des algorithmes les plus polyvalents grâce à sa simplicité, sa scalabilité (capacité à s'adapter suite a une augmentation de la charge ou de la taille) et sa rapidité de convergence.

Malheureusement, le choix initial des clusters peut influencer la qualité de la solution, allant jusqu'à la rendre sous-optimale. Aussi, les points très éloignés de la norme (outliers) peuvent poser un problème.

Clustering Hiérarchique

Le clustering hiérarchique crée une structure en arbre binaire (dendrogramme) pour regrouper les données de manière itérative à travers une série de fusions (agglomératif) ou de divisions (divisif). Contrairement au clustering basé sur la partition, il n'est pas nécessaire de spécifier le nombre de clusters.

Approche agglomératif

On considère chaque point individuel comme un cluster à part, puis de manière itérative :

1. On regroupe les points les plus proches pour former un cluster plus grand.

2. On répète l'étape 1 jusqu'à ce qu'il ne reste qu'un seul cluster qui englobe tous les autres.

Voyons cela ensemble avec une séquence de diagrammes. Dans le premier cadre, chaque point est considéré comme un cluster. Dans la figure suivante, le premier cluster de deux points (C1, comme montré aussi par le dendrogramme) est créé.

En continuant ainsi, à l'étape 4, nous aurons déjà trois clusters de deux points.

À ce stade (étape 5), C3 et un point assez proche viennent former le cluster C4. Dans la figure finale, nous pouvons observer la formation de deux autres clusters, C5 et C6 ; ce dernier englobe tous les autres et constitue la racine du dendrogramme.

Dans le dendrogramme, les nœuds sont des clusters et les branches (les lignes verticales) représentent la distance entre eux. Cette structure est très utile car elle nous permet non seulement de visualiser graphiquement les sous-ensembles, mais aussi de décider combien de clusters nous souhaitons réellement obtenir (en d'autres termes, où "couper" horizontalement l'arbre).

Approche divisif

La méthode divisive fonctionne de manière diamétralement opposée à la précédente. En partant d'un seul cluster contenant toutes les données, on procède en le divisant progressivement en plusieurs ensembles jusqu'à obtenir autant de clusters qu'il y a de points (comme illustré sur la figure).

Cette méthode peut être efficace pour des jeux de données de petite taille où une exploration approfondie des clusters est souhaitée. Toutefois, diviser un cluster de manière optimale à chaque étape nécessite de calculer toutes les dissimilarités possibles, ce qui peut être coûteux en termes de temps de calcul pour des grands jeux de données.

Applications

Le clustering hiérarchique a de multiples applications, notamment la segmentation de marché, la recherche clinique et le traitement d'image.

Avantages et inconvénients

Cet algorithme ne nécessite pas de spécifier à l'avance le nombre de clusters, contrairement à d'autres algorithmes comme K-Means et il crée une structure hiérarchique qui permet d'explorer les données à différents niveaux de granularité, offrant une vision complète des relations entre les points.

Les principaux défauts de cette approche sont le fait qu'elle soit coûteuse en calcul avec des ensembles de données volumineux et l'impossibilité de prédire un nouveau membre d'un cluster avec de nouvelles données.

Elle peut également être sensible au bruit et aux données anormales, qui peuvent altérer la structure hiérarchique et influencer les résultats.

Clustering basé sur la densité

Les algorithmes de clustering basés sur la densité sont utilisés pour regrouper des points de données en fonction de leur densité. En pratique, ces algorithmes recherchent des groupes de points dans des zones denses et les séparent des zones à faible densité (ou vides), qui peuvent être considérées comme du "bruit" ou des "outliers".

Cette technique est supérieure au partitionnement car elle permet d'identifier des clusters de n'importe quelle forme et d'identifier les outliers.

Par exemple, supposons que nous ayons un diagramme de points comme sur la figure ci-dessous. À l'œil, il est clair qu'il y a deux clusters l'un autour de l'autre, mais un algorithme de partitionnement ne serait pas capable de les séparer correctement (comme on eut voir en figure il n'est pas possible de tracer une droite qui les sépare). Pour cela, nous avons besoin d'un autre type d'approche.

DBSCAN

DBSCAN (scan basé sur la densité) a été introduit en 1996 par Ester et al. et est le plus populaire de ces algorithmes. Il a d’ailleurs reçu le prix Test of Time Award en 2014 lors de la conférence KDD (Special Interest Group on Knowledge Discovery and Data Mining).

En partant d'un ensemble de points comme dans le diagramme ci-dessus, on exécute les étapes suivantes :

Parmi tous les points, seuls ceux ayant un certain nombre m de voisins (à une distance maximale ɛ) sont sélectionnés et considérés comme des points centraux (étape 1).

On choisit un point au hasard parmi les observations cœur, et à partir de celui-ci, on trouve tous les voisins de manière récursive (un procédé similaire à celui d'une contagion) (étape 2).

Une fois que tous les voisins des observations cœur ont été trouvés, on considère cela comme un cluster (étape 3).

On cherche alors un point parmi les observations cœur qui n'appartient pas encore à un cluster et on recommence à partir de l'étape 2, jusqu'à ce qu'il n'existe plus d’observations cœur non encore associées à un cluster.

On peut observer que les deux clusters ont été correctement identifiés par l’algorithme, tandis que les points dans les zones de faible densité (les anomalies) en sont restés exclus.

Avantages et inconvénients

Le DBSCAN peut identifier des clusters de toutes tailles et formes, sans qu'il soit nécessaire de spécifier leur nombre au départ.

Il est également robuste aux anomalies, qui sont simplement ignorées, et en termes de performances, il reste efficace même avec de grands ensembles de données, grâce à une complexité temporelle de O(nlogn).

En revanche, le choix de la distance minimale ɛ pour l’identification des observations cœur et du nombre minimal de voisins m peut influencer négativement la performance (surtout en présence de clusters de densités différentes). Il est parfois nécessaire d’effectuer des essais pour définir correctement ces hyperparamètres.

Rappel : les hyperparamètres sont les réglages définis avant l’entraînement qui contrôlent comment le modèle apprend.

Exemple pratique (hands-on)

Vous êtes le propriétaire d'une librairie spécialisée dans les livres anciens (imprégnez-vous de ce rôle) et vous souhaitez sincèrement améliorer l'expérience de vos chers clients (une vingtaine au total).

Au cours des derniers mois, vous avez noté le nombre d'heures que vos visiteurs ont passé dans la boutique ainsi que le nombre de livres qu'ils ont achetés en une semaine.

Voici le tableau résultant, où nous pouvons voir le nombre moyen d'heures passées à la bibliothèque en une semaine et le nombre de livres achetés (n'oublions pas que vous êtes également passionné par le ML !).

La finalité est de regrouper les utilisateurs en quatre catégories et de leur fournir des bons d'achat avec des offres ciblées.

Le code

Ouvrons donc notre éditeur préféré, Google Colab, et commençons à entrer les données en notre possession.

# importons les bibliothèques nécessaires pour les opérations mathématiques
# et la visualisation des graphiques
import numpy as np
import matplotlib.pyplot as plt

# créons un tableau bidimensionnel : [heures passées, livres achetés]
X = np.array([
    [9,10], [9,9], [3,6], [2,1], [10,4], [3,8],
    [9,2], [2,9], [9,4], [8,9], [2,8], [8,2],
    [3,10], [1,7], [8,10], [4,3], [1,9], [7,8],
    [3,2], [8,7]])

# Visualisons le diagramme résultant 
plt.scatter(X[:, 0], X[:, 1], color="grey") 
plt.title("title") 
plt.xlabel("heures") 
plt.ylabel("livres") 
plt.show()

Avec un dataset aussi simple, il est déjà clair que nous avons un certain nombre de points qui forment des groupes bien distincts.

Essayons d'exécuter le K-Means avec quatre clusters et voyons si notre intuition est correcte.

Grâce à la bibliothèque scikit-learn nous serons capables, en quelques étapes simples, d'identifier les quatre clusters.

# importons la classe KMeans de scikit-learn 
from sklearn.cluster import KMeans 

# définissons le nombre de clusters à quatre 
kmeans = KMeans(n_clusters=4) 

# entraînons notre modèle (exécutons l'algorithme) 
kmeans.fit(X) 

# Générons donc un tableau avec les prédictions.
# Il contiendra un entier de 0 à 3 (correspondant à un cluster)
# pour chaque couple de notre table des observations. 
y_kmeans = kmeans.predict(X) 
print(y_kmeans)

> [3 3 0 2 1 0 1 0 1 3 0 1 0 0 3 2 0 3 2 3]

Voyons cela graphiquement :

# Visualisons le diagramme avec les clusters colorés.
plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, cmap='viridis', marker='o', s=50) 

# Incluons également les centroïdes.  
centroids = kmeans.cluster_centers_ 
labels = kmeans.labels_ 
plt.scatter(centroids[:, 0], centroids[:, 1], s = 100, c = 'red', label = 'Cluster 1')

Tous les points ont été attribués à un groupe dans lequel on peut également voir les centroïdes correspondants.

Vous êtes ainsi capables de regrouper les clients en quatre catégories :

• Bibliomanes (beaucoup d'heures et beaucoup de livres) : des clients qui aiment passer beaucoup de temps dans le magasin et acheter de nombreux livres, de véritables passionnés de lecture.

• Explorateurs (beaucoup d'heures et peu de livres) : des clients qui passent beaucoup de temps à flâner entre les rayons, peut-être à la recherche d'un livre rare, mais achètent peu de livres.

• Passants (peu d'heures et peu de livres) : des clients qui entrent rarement dans le magasin, peut-être pour un coup d'œil rapide ou un achat occasionnel.

• Chasseurs de trésors (peu d'heures et beaucoup de livres) : des clients qui savent ce qu'ils veulent et achètent de façon ciblée, passant peu de temps en magasin mais achetant de nombreux livres.

Évaluation du modèle

Même pour le clustering (comme nous l'avons déjà vu pour la régression et la classification), il est possible (et nécessaire) d'évaluer le modèle utilisé afin de mesurer la qualité du résultat et, si besoin, de l'améliorer.

Nous pouvons appliquer les métriques suivantes à notre modèle K-Means :

Somme des erreurs au carré (SSE)

Somme des distances entre les points et le centroïde de leur cluster (aussi appelée inertie du cluster ou distance intra-cluster).

Score de silhouette

Évalue à quel point un objet du cluster est similaire aux autres dans son cluster (cohésion) et dissimilaire des objets des autres clusters (séparation).

Sa valeur varie de -1 à 1, où des valeurs plus élevées signifient une cohésion et une séparation plus marquées.

Pour chaque point P :

• a = moyenne de la somme des distances entre P et tous les points de son cluster (distance intra-cluster).

• b = distance de P au cluster le plus proche (distance inter-cluster).

Score de silhouette du point P :

$$\frac{(b-a)} {max(a, b)}$$

En calculant ce score pour les différentes valeurs possibles de K, il peut être utilisé comme guide pour trouver le nombre idéal de K.

Par exemple, nous pouvons calculer le silhouette score de notre modèle de la manière suivante :

from sklearn.metrics import silhouette_score
print(silhouette_score(X, y_kmeans))

> 0.6447536975326736

À ces évaluations s'ajoute également le "bon sens", c'est-à-dire une inspection visuelle (lorsque possible) des clusters créés et une comparaison avec la réalité (en se basant sur notre expérience).

Place aux choses sérieuses !

Ce que nous devons apprendre à faire, nous l'apprenons en le faisant.
(Aristote)

Si les paroles d'un philosophe grec vous convainquent, kaggle.com est l'endroit idéal pour expérimenter vos nouvelles connaissances et apprendre en vous entraînant.

Kaggle.com vous permet de télécharger des ensembles de données de différentes tailles pour tester vos modèles sur des données qui simulent de vrais environnements de développement. Vous y trouverez également des problèmes à résoudre de niveaux de difficulté variés et pourrez participer à des défis avec d'autres utilisateurs.

Conclusion

Dans ce troisième article, nous avons exploré des concepts fondamentaux du Machine Learning, en approfondissant des techniques avancées telles que le clustering, l'analyse des métriques d'évaluation et l'optimisation des modèles.

Alors que nous nous rapprochons des prochains articles de notre série, nous nous concentrerons sur des sujets tout aussi cruciaux pour devenir des experts dans le domaine. La prochaine étape sera d'explorer les techniques d'apprentissage supervisé avec des modèles plus complexes comme les réseaux neuronaux.

Nous ne sommes qu'au début d'un voyage fascinant dans le monde du Machine Learning, et à mesure que nous explorerons les techniques et approches à venir, notre objectif reste le même : fournir les outils nécessaires pour appliquer le Machine Learning de manière efficace et pratique. Préparons-nous à découvrir le potentiel des réseaux neuronaux, de l'apprentissage profond (Deep Learning) et de l'intelligence artificielle dans des scénarios de plus en plus complexes.

Je suis impatient de poursuivre ce voyage ensemble. Restez avec nous, le meilleur est à venir, et d'ici là, bon apprentissage (automatique) !