Classification à l'aide de l'apprentissage automatique - Principes de la science des données

6.2 Classification à l'aide de l'apprentissage automatique

Objectifs d'apprentissage

À la fin de cette section, vous devriez être capable de :

6.2.1 Effectuer une régression logistique sur des ensembles de données et interpréter les résultats.
6.2.2 Effectuer un clustering en clusters par k-moyennes sur des ensembles de données.
6.2.3 Définir le concept de clustering en clusters basé sur la densité et utiliser DBScan sur des ensembles de données.
6.2.4 Interpréter la matrice de confusion dans le clustering en clusters ou la classification de données.

Les problèmes de classification se présentent sous de nombreuses formes. Par exemple, supposons que vous soyez chargé de créer un algorithme qui diagnostique une maladie cardiaque. Les caractéristiques d'entrée peuvent inclure le sexe biologique, l'âge, les données de pression artérielle et les taux de cholestérol. La sortie serait soit : oui (diagnostiquer une maladie cardiaque), soit non (ne pas diagnostiquer de maladie cardiaque). C'est-à-dire que votre algorithme doit classer les patients en « oui » ou « non » en fonction d'un tableau de caractéristiques, ou symptômes en terminologie médicale. La régression logistique est un outil de classification lorsqu'il n'y a que deux sorties possibles. C'est ce qu'on appelle souvent un problème de classification binaire (binomiale) (binary (binomial) classification). Si l'objectif est de classer les données dans plus de deux classes ou catégories, le problème est alors appelé classification multiclasse (multinomiale) (multiclass (multinomial) classification).

D'autres types de problèmes de classification consistent à trouver deux clusters ou plus dans les données. Une cluster (cluster) est une collection de points de données plus proches les uns des autres que des autres points de données, selon une certaine définition de la proximité. Par exemple, certaines caractéristiques de la musique, telles que le tempo, l'instrumentation, la durée totale et les types de motifs d'accords utilisés, peuvent être utilisées comme caractéristiques pour classer la musique en différents genres, comme le rock, la pop, la country et le hip-hop. Un algorithme d'apprentissage automatique supervisé tel qu'un arbre de décision (voir Arbres de décision) ou une forêt aléatoire (voir Autres techniques d'apprentissage automatique) peut être entraîné et utilisé pour classer la musique dans les différents genres prédéfinis. Alternativement, un modèle non supervisé tel que le clustering en clusters par k-moyennes pourrait être utilisé pour regrouper des morceaux aux sonorités similaires sans nécessairement adhérer à un concept de genre.

Cette section se concentrera sur les techniques de régression logistique et les algorithmes de clustering en clusters tels que les k-moyennes et DBScan. Nous utiliserons des mesures d'exactitude comprenant la matrice de confusion.

Régression logistique

Un modèle de régression logistique (logistic regression) $L (X)$ prend des vecteurs d'entrée $X$ (caractéristiques) et produit une sortie « oui » ou « non ». Tout comme la régression linéaire, le modèle de régression logistique ajuste d'abord une fonction continue basée sur des données étiquetées et connues. Cependant, au lieu d'ajuster une droite aux données, on utilise une fonction sigmoïde. Une fonction sigmoïde (sigmoid function) est un type spécifique de fonction qui associe tout nombre réel à une valeur comprise entre 0 et 1. Le terme sigmoïde vient du fait que le graphe a une forme caractéristique en « S » (comme illustré à la Figure 6.6), et sigma $(σ)$ est la lettre grecque qui correspond à notre lettre S. Nous utilisons souvent la notation $σ (x)$ pour désigner une fonction sigmoïde. La formule de base de la sigmoïde est :

σ (x) = \frac{1}{1 + e^{- x}}

Un graphique linéaire. L'axe des X s'étend de -1 à 1 et un axe des Y au centre du graphique s'étend de 0 à 1. Le graphique affiche une fonction sigmoïde qui forme une courbe en S commençant à (-1, 0), coupant l'axe central des Y à (0, 0,5) et se terminant à (1, 1).

Figure 6.6 Graphe d'une fonction sigmoïde typique

Un avantage de la sigmoïde par rapport à une fonction linéaire est que les valeurs de la sigmoïde restent proches de 0 lorsque $x$ est négatif et proches de 1 lorsque $x$ est positif. Cela la rend idéale pour classer des entrées arbitraires $x$ dans l'une des deux classes, « oui » (1) ou « non » (0). En fait, nous pouvons interpréter l'axe des y comme la probabilité qu'un événement se produise. La fonction sigmoïde peut être déplacée vers la droite ou la gauche et compressée ou étirée horizontalement selon les besoins pour s'adapter aux données. Dans la formule suivante, les paramètres $a$ et $b$ contrôlent respectivement la position et la forme de la fonction sigmoïde.

σ (a + b x) = \frac{1}{1 + e^{- (a + b x)}}

Aussi compliquée que cette formule puisse paraître au premier abord, elle est construite à partir d'éléments simples. La présence de $a + b x$ suggère qu'il pourrait y avoir une régression linéaire $y = a + b x$ cachée en arrière-plan. En effet, si nous résolvons pour trouver la fonction réciproque de $σ (x)$ , nous pouvons l'utiliser pour isoler $a + b x$ , ce qui nous permet ensuite d'utiliser des techniques de régression linéaire standard pour construire la régression logistique. Rappelons que la fonction logarithme népérien, ln $n$ , est la fonction réciproque de l'exponentielle, $e^{x}$ . Dans ce qui suit, soit $p$ égal à $σ (x)$ .

p = σ (x) = \frac{1}{1 + e^{- x}}

\begin{array}{rcl} \frac{1}{p} & = & 1 + e^{- x} \\ \frac{1}{p} - 1 & = & e^{- x} \\ e^{- x} & = & \frac{1}{p} - 1 = \frac{1 - p}{p} \\ - x & = & ln (\frac{1 - p}{p}) \\ x & = & - ln (\frac{1 - p}{p}) = ln [{(\frac{1 - p}{p})}^{- 1}] = ln (\frac{p}{1 - p}) \end{array}

À la dernière ligne, nous avons utilisé la propriété des puissances des logarithmes, $ln A^{n} = n ln A$ , avec une puissance $n = - 1$ . La fonction que nous venons d'obtenir s'appelle la fonction logit.

logit (p) = ln (\frac{p}{1 - p})

La propriété clé de la fonction logit (logit function) est qu'elle est la fonction réciproque de $σ (x)$ . Rappelons d'après l'algèbre que si $g (x)$ est la fonction réciproque de $f (x)$ , alors nous avons $g (f (x)) = x$ pour tout $x$ . Dans notre cas, cela signifie que $logit (σ (x)) = x$ , pour tout $x$ . En appliquant maintenant la fonction logit à la fonction sigmoïde générale, nous pouvons écrire :

logit (σ (a + b x)) = a + b x

Ainsi, la fonction logit linéarise la sigmoïde. Examinons d'un peu plus près la fonction logit et ce qu'elle mesure.

Log-odds et régression logistique discrète

La régression logistique est un modèle de prédiction basé sur la notion de cote. La cote (odds) qu'un événement E se produise est le rapport entre la probabilité que E se produise et la probabilité que E ne se produise pas. Soit $p = P (E)$ .

Odds (E) = \frac{P (E)}{P (E')} = \frac{P (E)}{1 - P (E)} = \frac{p}{1 - p}

Ainsi, la fonction logit est simplement le logarithme de la cote d'un événement ayant une probabilité donnée $p$ . C'est pourquoi le logit est souvent appelé log-cotes. Alors que les probabilités $(p)$ vont de 0 à 1, les log-cotes vont de $- \infty$ (moins l'infini) à $\infty$ (l'infini).

Supposons que nous souhaitions prédire la probabilité qu'un événement $A$ se produise, sachant qu'un autre événement $B$ se produit ou ne se produit pas. Nous allons créer un modèle de régression logistique, $f (x) = \frac{1}{1 + e^{- (a + b x)}}$ , tel que :

$f (0)$ est la probabilité que $A$ se produise lorsque $B$ ne se produit pas, et
$f (1)$ est la probabilité que $A$ se produise lorsque $B$ se produit.

Nous obtenons $a$ et $b$ à l'aide de la fonction logit. Si $p_{1}$ est la probabilité que $A$ se produise sachant que $B$ ne se produit pas (c.-à-d., $p_{1} = P (A | B')$ ), en utilisant la notation de la probabilité conditionnelle (voir Distributions de probabilité continues normales), et si $p_{2}$ est la probabilité que $A$ se produise sachant que $B$ se produit (c.-à-d., $p_{2} = P (A | B)$ ), alors

$a = logit (p_{1})$ , et $b = logit (p_{2}) - logit (p_{1})$

Ce modèle est appelé une régression logistique discrète car la variable caractéristique vaut soit 1, soit 0 (selon que l'événement $B$ s'est produit ou non).

Exemple 6.4

Problème

Dans une université donnée, il a été constaté que les étudiants résidents de l'État ont plus de chances d'obtenir leur diplôme que les étudiants non-résidents de l'État. Environ 75 % des étudiants résidents finissent par obtenir leur diplôme, contre seulement environ 30 % des étudiants non-résidents. Construisez un modèle de régression logistique discrète à partir de ces données.

Solution

Soit $p_{1} = 0.3$ , qui est la probabilité d'obtenir son diplôme si la variable « résident » est fausse, ou 0. Soit $p_{2} = 0.75$ , qui est la probabilité d'obtenir son diplôme si la variable « résident » est vraie, ou 1.

\begin{array}{rcl} logit (p_{1}) & = & ln (\frac{0.3}{1 - 0.3}) = ln 0.4286 = - 0.847 \\ logit (p_{2}) & = & ln (\frac{0.75}{1 - 0. 75}) = ln 3.000 = 1.099 \end{array}

Donc $a = logit (p_{1}) = - 0.847$ , et $b = logit (p_{2}) - logit (p_{1}) = 1.099 - (- 0.847) = 1.946$ . Par conséquent, le modèle est :

f (x) = \frac{1}{1 + e^{- (- 0.847 + 1.946 x)}} = \frac{1}{1 + e^{0.847 - 1.946 x}}

Vous pouvez vérifier que $f (0) = 0.3$ et $f (1) = 0.75$ .

L'exemple précédent n'utilisait qu'une seule variable caractéristique, « résident », et l'utilité du modèle est donc très limitée. Nous verrons comment étendre le modèle pour inclure plusieurs entrées ou caractéristiques dans la section Techniques de régression multiple.

Vraisemblance maximale et régression logistique continue

La méthode de régression logistique peut également être utilisée pour prédire une réponse par oui/non sur la base d'une entrée continue. La construction du modèle nécessite de trouver des valeurs pour les paramètres de la fonction sigmoïde qui produisent les résultats les plus précis. Pour expliquer comment cela fonctionne, parlons d'abord de la vraisemblance. La vraisemblance (likelihood) d'un modèle $f (x)$ est calculée comme suit. Pour chaque point de données $x_{k}$ , si l'étiquette de $x_{k}$ est 1 (ou oui), alors calculez $f (x_{k})$ ; si l'étiquette est 0 (ou non), alors calculez ${1 - f (x}_{k})$ . Le produit de ces résultats individuels constitue le score de vraisemblance du modèle. Nous voulons trouver le modèle qui a la vraisemblance maximale.

Exemple 6.5

Problème

Considérez les modèles

f (x) = \frac{1}{1 + e^{1.6 - 1.1 x}}, g (x) = \frac{1}{1 + e^{2.1 - 0.8 x}}

Supposons qu'il y ait quatre points de données, $A = 1$ , $B = 2$ , $C = 3$ , $D = 4$ , et que $A$ et $B$ aient tous deux l'étiquette 0, tandis que $C$ et $D$ ont l'étiquette 1. Trouvez les scores de vraisemblance de chaque modèle et déterminez quel modèle s'ajuste le mieux aux données fournies.

Solution

Pour le modèle $f$ , les vraisemblances prédites sont $f (1) = 0.378$ , $f (2) = 0.646$ , $f (3) = 0.846$ et $f (4) = 0.943$ . Puisque $x = 1$ et 2 ont l'étiquette 0, tandis que $x = 3$ et 4 ont l'étiquette 1, nous calculons :

(1 - 0.378) (1 - 0.646) (0.846) (0.943) = 0.176

Pour le modèle $g$ , les vraisemblances prédites sont $g (1) = 0.214$ , $g (2) = 0.378$ , $g (3) = 0.574$ et $g (4) = 0.75$ .

(1 - 0.214) (1 - 0.378) (0.574) (0.75) = 0.211

Ainsi, le modèle $g$ est le meilleur des deux modèles sur ces données.

Comment trouve-t-on le modèle qui a la vraisemblance maximale ? La méthode exacte pour trouver les coefficients $a$ et $b$ pour le modèle $σ (a + b x)$ dépasse la portée de ce texte. Heureusement, il existe des logiciels qui peuvent faire ce travail à votre place.

Par exemple, la même université a mené une étude sur l'effet de la moyenne pondérée cumulative (GPA) de première année sur l'obtention d'un diplôme universitaire. Un petit échantillon des données est présenté dans le Tableau 6.5. Quel est le modèle qui s'ajuste le mieux à ces données ?

GPA	Diplôme universitaire obtenu ?
1.5	N
2.4	O
3.4	O
2.1	N
2.5	O
0.8	N
2.9	N
4.0	O
2.3	O
2.1	N
3.6	O
0.5	N

Tableau 6.5 Données sur la GPA par rapport à l'obtention du diplôme universitaire

La Figure 6.7 montre les données sous forme graphique.

Un graphique linéaire avec un axe des X allant de 0 à 4 et un axe des Y allant de 0 à 1. Il y a cinq points de données à 0 sur l'axe des Y (0, 0,5), (0, 0,8), (0, 1,5), (0, 2,1), (0, 2,9) et six points de données à 1 sur l'axe des Y à (2,3, 1), (2,4, 1), (2,5, 1), (3,4, 1), (3,6, 1), (4,0, 1).

Figure 6.7 Graphe de la GPA (axe des x) et de l'obtention du diplôme (axe des y). Les valeurs utilisées sont 0 pour la non-obtention et 1 pour l'obtention. Le graphe suggère que des GPA plus élevées ont tendance à prédire l'obtention d'un diplôme.

Le modèle logistique (trouvé à l'aide d'un logiciel informatique) qui maximise la vraisemblance est :

\frac{1}{1 + e^{2.826 - 1.197 x}}

Le modèle de régression logistique qui s'ajuste le mieux aux données est illustré à la Figure 6.8 avec les points de données colorés en vert pour une obtention de diplôme prédite et en rouge pour une non-obtention prédite.

Un graphique linéaire avec un axe des X allant de 0 à 4 et un axe des Y allant de 0 à 1. Il y a cinq points de données rouges (0, 0,5), (0, 0,8), (0, 1,5), (0, 2,1) et (2,3, 1) et six points de données verts (0, 2,9), (2,4, 1), (2,5, 1), (3,4, 1), (3,6, 1), (4,0, 1). Les points de données sont colorés en vert pour une obtention de diplôme prédite et en rouge pour une non-obtention prédite.

Figure 6.8 Modèle de régression logistique ajusté aux données du Tableau 6.5

Régression logistique en Python

Un exemple de code Python pour la régression logistique, utilisant les données du Tableau 6.5, apparaît ci-dessous. Nous utilisons la fonction LogisticRegression trouvée dans la bibliothèque Python sklearn.linear_model.

Code Python

      # Import libraries
      from sklearn.linear_model import LogisticRegression
      
      # Define input and output data
      data = [[1.5, 0], [2.4, 1], [3.4, 1 ], [2.1, 0 ], [2.5, 1 ], 
       [0.8, 0 ], [2.9, 0 ], [4.0, 1], [2.3, 1], [2.1, 0], [3.6, 1 ], [0.5, 0]]
      
      # Separate features (X) and labels (y)
      X = [[row[0]] for row in data]  # Feature
      y = [row[1] for row in data]    # Label
      
      # Build the logistic model
      Lmodel = LogisticRegression()
      Lmodel.fit(X,y)
      
      # Display the coefficients of the logistic regression
      (a,b) = (Lmodel.intercept_[0], Lmodel.coef_[0,0])
      print("Coefficients: ", (round(a,3),round(b,3)))
      
      # Display the accuracy of the model
      s = Lmodel.score(X,y)
      print("Accuracy: ", round(s, 3))

La sortie résultante ressemblera à ceci :

Coefficients: (-2.826, 1.197)
Accuracy: 0.833

Le code produit les coefficients qui peuvent être introduits pour $a$ et $b$ dans le modèle :

σ (- 2.826 + 1.197 x) = \frac{1}{1 + e^{- (- 2.826 + 1.197 x)}} = \frac{1}{1 + e^{2.826 - 1.197 x}}

Regroupement par k-moyennes

Les algorithmes de clustering en clusters fonctionnent comme des détectives numériques, découvrant des motifs et des structures dans les données. L'objectif est de trouver et d'étiqueter des groupes de points de données proches les uns des autres. Cette section développe des méthodes de clustering de données (clustering) qui intègrent l'apprentissage automatique.

L'algorithme de clustering par k-moyennes (k-means clustering algorithm) peut classifier ou regrouper des points de données similaires en clusters ou catégories sans connaissance préalable de ce que ces catégories pourraient être (c'est-à-dire l'apprentissage non supervisé). Cependant, l'utilisateur doit fournir une estimation de la valeur de $k$ , le nombre de clusters attendu. (Remarque : vous pouvez contourner ce problème en exécutant l'algorithme par itération sur de nombreuses valeurs de $k$ et en évaluant quelle valeur de k a produit les meilleurs résultats. Le compromis réside dans le temps nécessaire pour exécuter l'algorithme en utilisant plusieurs valeurs de $k$ et interpréter les résultats. La méthode dite du coude est souvent utilisée pour trouver la meilleure valeur de $k$ , mais expliquer cette méthode dépasse la portée de ce texte.) L'utilisateur doit également fournir des estimations initiales quant à l'emplacement des centroïdes. Nous verrons par l'exemple comment ces choix peuvent affecter l'algorithme.

Fondamentaux du clustering par k-moyennes

L'idée de base derrière les k-moyennes est assez intuitive : chaque cluster doit être centrée autour de son centroïde de manière à minimiser la distance entre les données de la cluster et son centroïde. L'astuce consiste à trouver ces centroïdes ! Brièvement, un centroïde (centroid) d'un ensemble de points de données est défini comme la moyenne arithmétique des données, considérées comme des vecteurs.

Centroid = \frac{1}{N} \sum_{i = 1}^{N} X_{i}

Les étapes de base de l'algorithme de clustering par k-moyennes sont les suivantes :

Estimer les emplacements des centres de $k$ clusters.
Calculer les distances entre chaque point de données et le centre de chaque cluster. Les points de données sont attribués à la cluster dont le centre est le plus proche d'eux.
Trouver le centroïde de chaque cluster.
Répéter les étapes 2 et 3 jusqu'à ce que les centroïdes se stabilisent, c'est-à-dire que les nouveaux centroïdes soient identiques (ou approximativement identiques, dans les limites d'une certaine tolérance donnée) aux centroïdes de l'itération précédente.

Si le clustering en clusters a été bien fait, alors les clusters doivent être clairement séparées. Le score de silhouette (silhouette score) est une mesure du degré de séparation des clusters et est défini comme suit :

Soit $a (i)$ la distance moyenne entre le point $i$ et tous les autres points de données de la même cluster que le point $i$ .

Pour chaque cluster $J$ ne contenant pas le point $i$ , soit $b_{J} (i)$ la distance moyenne entre le point $i$ et tous les points de données de la cluster $J$ . Ensuite, soit $b (i)$ le minimum de toutes les valeurs de $b_{J} (i)$ .

Le score de silhouette est alors obtenu par la formule

S = \frac{1}{N} \sum_{i = 1}^{N} \frac{b (i) - a (i)}{max {a (i), b (i)}}

Les valeurs de $S$ sont comprises entre $-$ 1 et 1, des valeurs proches de 1 indiquant des clusters bien séparées, des valeurs proches de 0 indiquant que les clusters sont ambiguës, et des valeurs proches de $-$ 1 indiquant un clustering médiocre avec des points assignés aux clusters de façon arbitraire. Heureusement, les progiciels statistiques capables d'effectuer un clustering par k-moyennes pourront calculer le score de silhouette pour vous.

Exemple 6.6

Problème

Une prolifération de champignons a touché une petite zone de jardin. Le champignon a pris naissance sous terre, mais il a produit des champignons facilement repérables. D'après une photo de la zone, on suppose qu'il y a trois clusters de champignons (voir la Figure 6.9). Utilisez les k-moyennes pour classifier les champignons en trois groupes.

Un nuage de points avec un axe X étiqueté « Est » qui va de 20 à 160 et un axe Y étiqueté « Nord » qui va de 20 à 90. Il y a 19 points de données qui représentent les emplacements de champignons dans un jardin et représentent trois clusters apparentes avec quelques valeurs aberrantes.

Figure 6.9 Les emplacements de champignons dans un jardin. Il y a trois clusters apparentes.

Solution

Les données d'emplacement se composent de 19 points indiquant la position en pieds vers l'est et vers le nord par rapport à un point fixe.

(101.7, 51.1), (109.2, 66.7), (33.2, 54.1), (39.6, 53.6), (66.8, 70.5), (119.9, 42.4),

(26.9, 33.1), (55.5, 71.7), (75, 82.4), (108.6, 71.4), (62.1, 83.5), (119.8, 69.1),

(25.9, 30.2), (37.5, 46.4), (24, 49.1), (75.5, 77.8), (101.5, 51), (110.5, 72),

(39.5, 55.8)

Tout d'abord, choisissez trois centroïdes potentiels. Pour simplifier les choses, nous allons simplement prendre les trois premiers points de données (101.7, 51.1), (109.2, 66.7) et (33.2, 54.1), que nous colorerons respectivement en rouge, vert et bleu. Colorez maintenant tous les points de données en rouge, vert et bleu selon le point le plus proche parmi ces trois. Le clustering initial n'est pas parfait, comme vous pouvez le voir sur la Figure 6.10.

Figure 6.10 Graphique avec de grands points indiquant les choix initiaux de centroïdes. Les points de données sont colorés selon le centroïde dont ils sont le plus proches.

Ensuite, nous trouvons les centroïdes de chacun des groupes colorés. En pratique, tout cela est fait automatiquement par un logiciel, mais nous allons calculer l'un des centroïdes explicitement ici. Calculons le centroïde vert.

Points verts actuels : (75, 82.4), (75.5, 77.8), (108.6, 71.4), (109.2, 66.7), (110.5, 72), (119.8, 69.1).

Valeur en x du centroïde vert : $\bar{x} = \frac{1}{6} (75 + 75.5 + 108.6 + 109.2 + 110.5 + 119.8) = 99.8$

Valeur en y du centroïde vert : $\bar{y} = \frac{1}{6} (82.4 + 77.8 + 71.4 + 66.7 + 72 + 69.1) = 73.2$

Ainsi, le centroïde vert est situé à (99.8, 73.2).

Tracez maintenant tous les centroïdes. Vous pouvez imaginer que les centroïdes potentiels précédents se sont déplacés vers des positions plus proches des véritables centroïdes des groupes visibles. Le point rouge se déplace vers (107.7, 48.2) ; le point vert se déplace vers (99.8, 73.2) ; et le point bleu se déplace vers (41.1, 54.8). Notez que (en dehors des choix initiaux) les centroïdes ne sont généralement pas des points du jeu de données. Recolorez les points du jeu de données par rapport à ces nouveaux centroïdes, comme le montre la Figure 6.11.

Figure 6.11 Graphique avec de nouveaux centroïdes. Après la deuxième itération de l'algorithme des k-moyennes, les centroïdes se sont rapprochés des centres des clusters principales. Cependant, aucun point n'a changé d'emplacement, de sorte que l'algorithme se stabilise à cette étape.

Exécutez l'algorithme un certain nombre de fois jusqu'à ce que la coloration se stabilise. Dans ce cas, l'itération suivante est stable. Les clusters se trouvent-elles là où vous pensiez qu'elles allaient aboutir ? Cet exemple met en évidence le fait que les k-moyennes peuvent être très sensibles au choix initial des centroïdes.

Exécuter à nouveau l'algorithme avec des centroïdes initiaux différents peut produire des clusters différentes, comme le montre la Figure 6.12.

Figure 6.12 Graphique avec différents centroïdes initiaux. En utilisant des centroïdes initiaux de (110, 70), (60, 80) et (40, 40), l'algorithme des k-moyennes produit un clustering différent. Les positions finales des centroïdes sont (110.2, 60.5), (67.0, 77.2) et (32.4, 46.0).

Les algorithmes de clustering en clusters tels que les k-moyennes permettent également de faire des prédictions sur de nouvelles données. Par exemple, supposons qu'un nouveau champignon pousse à l'emplacement (90, 50). Pour classifier ce point comme rouge, vert ou bleu, il suffit de déterminer quel centroïde est le plus proche de ce point.

Rappelons que la distance entre deux points $(x_{1}, y_{1})$ et $(x_{2}, y_{2})$ est obtenue à l'aide de la formule

d = \sqrt{{(x_{2} - x_{1})}^{2} + {(y_{2} - y_{1})}^{2}}

Distance au centroïde rouge : $\sqrt{{(90 - 110.2)}^{2} + {(50 - 60.5)}^{2}} = 22.77$

Distance au centroïde vert : $\sqrt{{(90 - 67)}^{2} + {(50 - 77.2)}^{2}} = 35.62$

Distance au bleu : $\sqrt{{(90 - 32.4)}^{2} + {(50 - 46)}^{2}} = 57.74$

Par conséquent, le nouveau champignon doit être inclus dans le groupe rouge.

Parmi les algorithmes de clustering en clusters, les k-moyennes sont plutôt simples, faciles à mettre en œuvre et très rapides. Cependant, ils souffrent de nombreux inconvénients, notamment la sensibilité au choix initial des centroïdes. De plus, les k-moyennes ne détectent pas les clusters qui ne sont pas de simples « taches ». Dans la section suivante, nous aborderons un autre algorithme de clustering qui fonctionne généralement mieux sur un éventail plus large de données.

Regroupement par k-moyennes en Python

Notre exemple précédent utilisait un échantillon de seulement 19 points de données sélectionnés parmi les 115 points de données figurant dans le fichier FungusLocations.csv. Voici le code Python permettant de produire un clustering par k-moyennes à partir d'un ensemble de données :

Code Python

      # Import libraries
      import pandas as pd  ## for dataset management
      import matplotlib.pyplot as plt ## for data visualization
      from sklearn.cluster import KMeans
      from sklearn.metrics import silhouette_score
      
      # Read data
      data = pd.read_csv('FungusLocations.csv').dropna()
      
      # Build K-means model with 3 clusters
      km = KMeans(n_clusters=3, n_init='auto')
      km.fit(data)
      
      # Calculate silhouette score
      silhouette_avg = silhouette_score(data, km.labels_)
      print("Silhouette Score:", round(silhouette_avg,2))
      
      # Visualize the result of k-Means clustering using matplotlib
      plt.scatter(data['East'], data['North'], c=km.labels_, cmap='viridis')
      plt.xlabel('East')
      plt.ylabel('North')
      plt.title('k-Means Clustering Result')
      plt.show()

La sortie obtenue ressemblera à ceci :

Silhouette Score: 0.77

Un nuage de points étiqueté « k-Means Clustering Result » avec un axe X étiqueté « Est » qui va de 20 à 160 et un axe Y étiqueté « Nord » qui va de 20 à 90. Il y a 19 points de données qui représentent les emplacements de champignons dans un jardin. Les points sont représentés en trois clusters colorées en jaune, violet et vert.

Avec un score de silhouette d'environ 0,77, la séparation des points de données en trois clusters semble appropriée.

Pour aller plus loin

Centroïdes par rapport à d'autres moyennes

Au lieu d'utiliser des centroïdes (qui sont calculés à l'aide de moyennes arithmétiques), d'autres moyennes peuvent être employées, notamment les médianes, les moyennes tronquées, les moyennes géométriques ou harmoniques, et bien d'autres. Ces algorithmes peuvent porter des noms différents tels que k-médianes, k-médoydes, etc. De plus amples informations peuvent être trouvées sur Neptune et les articles Tidymodels..

Regroupement basé sur la densité (DBScan)

Supposons que vous deviez classifier les données de la Figure 6.13 en deux clusters.

Un balayage de clustering basé sur la densité avec un axe X qui va de -15 à 15 et un axe Y qui va de -15 à 15. Les points bleus forment une cluster circulaire externe plus grande et une cluster interne plus petite au centre du cercle.

Figure 6.13 Ensemble de données avec un anneau interne et externe

Comment pourriez-vous procéder ? Il semble y avoir une distinction nette entre les points situés sur l'anneau intérieur et les points situés sur l'anneau extérieur. Alors que le clustering par k-moyennes n'obtiendrait pas de bons résultats sur cet ensemble de données, un algorithme de clustering basé sur la densité (density-based clustering algorithm) tel que DBScan pourrait donner de meilleurs résultats.

Fondamentaux de DBScan

L'algorithme DBScan (DBScan algorithm) (DBScan est un acronyme anglais qui signifie density-based spatial clustering of applications with noise) fonctionne en localisant les points de données centraux (cœurs) qui font partie de régions denses du jeu de données et en s'étendant à partir de ces cœurs en ajoutant des points voisins selon certains critères de proximité.

Tout d'abord, nous définissons deux paramètres : $K$ et $r$ . Un point dans le jeu de données est appelé point cœur s'il a au moins $K$ voisins, en se comptant lui-même, à une distance inférieure ou égale à $r$ de lui-même.

Les étapes de DBScan sont les suivantes :

Choisir un point de départ qui est un point cœur et l'assigner à une cluster. (Remarque : s'il n'y a aucun point cœur dans le jeu de données, les paramètres $K$ et $r$ devront être ajustés.)
Ajouter tous les points cœurs qui sont proches (à une distance inférieure à $r$ ) du premier point dans la première cluster. Continuer d'ajouter à la cluster de cette façon jusqu'à ce qu'il n'y ait plus de points cœurs suffisamment proches de la première cluster.
S'il reste des points cœurs non assignés à une cluster, en choisir un pour démarrer une nouvelle cluster et répéter l'étape 2 jusqu'à ce que tous les points cœurs soient assignés à des clusters.
Pour chaque point non cœur, vérifier s'il est proche de points cœurs. Si c'est le cas, l'ajouter à la cluster du point cœur le plus proche. Si un point non cœur n'est pas assez proche de points cœurs, il ne sera ajouté à aucune cluster. Un tel point est considéré comme une valeur aberrante ou du bruit.

Comme les valeurs de $K$ et $r$ sont primordiales pour les performances de DBScan, l'algorithme est généralement exécuté plusieurs fois sur le même ensemble de données en utilisant une plage de valeurs de $K$ et de valeurs de $r$ . S'il y a un grand nombre de valeurs aberrantes et/ou très peu de clusters, le modèle peut souffrir de sous-apprentissage. À l'inverse, un très petit nombre de valeurs aberrantes (ou zéro valeur aberrante) et/ou de nombreuses clusters présentes dans le modèle peuvent être le signe d'un surapprentissage.

Examinons un petit exemple utilisant DBScan avec $K = 3$ et $r = 2.1$ pour classifier le jeu de données suivant en clusters. (Les points sont étiquetés par des lettres pour plus de commodité.)

A: (3.5, 5.8) B: (4.5, 3.5) C: (5.0, 5.0) D: (6.0, 6.0) E: (6.0, 3.0) F: (6.9, 4.7)

G: (9.0, 4.0) H: (11.0, 5.0) J: (12.0, 4.0) K: (12.4, 5.4) L: (13.2, 2.5)

Remarque : en pratique, DBScan ne serait jamais effectué à la main, mais les étapes présentées ci-dessous illustrent le fonctionnement de l'algorithme. La Figure 6.14 affiche les données.

Un nuage de points avec un axe X qui s'étend de 0 à 16 et un axe Y qui s'étend de 0 à 8. Il y a 11 points de données étiquetés de A à L dispersés aléatoirement.

Figure 6.14 Ensemble de données initial avec 11 points non étiquetés.

Les points cœurs sont ceux qui ont au moins $K$ voisins (ou $K - 1$ , sans compter le point lui-même) à une distance inférieure ou égale à $r$ . La façon la plus simple de déterminer les points cœurs serait de tracer des cercles de rayon 2,1 centrés sur chaque point, comme le montre la Figure 6.15, puis de compter le nombre de points à l'intérieur de chaque cercle.

Un nuage de points avec un axe X allant de 0 à 16 et un axe Y allant de 0 à 8. Il y a 11 points de données étiquetés de A à L dispersés au hasard. Il y a 11 cercles bleus, chacun centré autour d'un point de données. Les cercles se chevauchent et se croisent, illustrant quels points sont cœurs ou non cœurs.

Figure 6.15 Cercles de rayon centrés sur chaque point. En traçant des cercles de rayon

r

autour de chaque point de données, il est plus facile de voir quels points sont cœurs et lesquels ne le sont pas.

D'après la Figure 6.15, le point A n'a que deux voisins, A et C, de sorte que A n'est pas un point cœur. D'autre part, le point B a trois voisins, B, C et E, de sorte que B est un point cœur. La liste complète des points cœurs est B, C, D, E, F, H, J et K. On peut donc choisir B pour commencer la première cluster. Ensuite, en partant de B, les points C et E sont ajoutés. Ensuite, D, E et F sont ajoutés à la première cluster en expansion. Ni A ni G ne sont ajoutés à ce stade car ils ne sont pas des points cœurs. Ayant trouvé tous les points cœurs de la première cluster, laissons H commencer une deuxième cluster. Les seuls points cœurs restants sont suffisamment proches de H pour que la deuxième cluster soit formée de H, J et K.

Based on Figure 6.15, point A has only two neighbors, A and C, so A is not a core point. On the other hand, point B has three neighbors, B, C, and E, so B is core. The full list of core points is B, C, D, E, F, H, J, and K. So B may be chosen to start the first cluster. Then, building from B, points C and E are added next. Next, D, E, and F are added to the growing first cluster. Neither A nor G are added at this stage since they are not core points. Having found all core points that are in the first cluster, let H start a second cluster. The only core points left are close enough to H that the second cluster is H, J, and K.

Un nuage de points avec un axe X qui s'étend de 0 à 16 et un axe Y qui s'étend de 0 à 8. Il y a 11 points de données étiquetés de A à L. Les points de données A-F sont bleus, G est noir et H-L sont rouges, représentant un DBScan de deux clusters. La cluster 1 est en bleu et la cluster 2 est en rouge.

Figure 6.16 Graphique montrant les résultats du clustering DBScan. La cluster 1 est en bleu et la cluster 2 est en rouge.

DBScan en Python

La bibliothèque Python sklearn.cluster dispose d'un module nommé DBSCAN. Voici comment il fonctionne sur le jeu de données DBScanExample.csv.

Code Python

      # Import libraries
      import pandas as pd ## for dataset management
      from sklearn.cluster import DBSCAN
      
      # Read data
      data = pd.read_csv('DBScanExample.csv').dropna()
      
       # Run DBScan
      db = DBSCAN(eps=1.3, min_samples=5).fit(data)
      labels = db.labels_
      
      # Find the number of clusters and points of noise
      n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
      n_noise = list(labels).count(-1)
      print("Number of clusters: ", n_clusters)
      print("Points of noise:", n_noise)

La sortie obtenue ressemblera à ceci :

Number of clusters: 2
Points of noise: 8

Code Python

      # Visualize clusters
      import matplotlib.pyplot as plt ## for data visualization
      
      plt.scatter(data['X'], data['Y'], c=db.labels_)

La sortie obtenue ressemblera à ceci :

Un balayage de clustering basé sur la densité avec un axe X qui va de -10 à 10 et un axe Y qui va de -10 à 10. Les points jaunes forment une cluster circulaire externe plus grande et les points verts forment une cluster interne plus petite au centre du cercle. Huit points violets apparaissent comme des valeurs aberrantes à l'intérieur et à l'extérieur du cercle.

La matrice de confusion

Lors de l'entraînement et du test de tout algorithme effectuant une classification, comme les modèles de régression logistique, le clustering par k-moyennes ou DBScan, il est important de mesurer l'exactitude et d'identifier les erreurs. La matrice de confusion (confusion matrix) est un moyen de quantifier et de visualiser l'efficacité d'un modèle de classification. Ce concept sera illustré par l'exemple suivant.

Supposons que vous ayez entraîné un modèle qui classifie des images de plantes dans l'une des trois catégories suivantes : fleurs, arbres et herbes. Lorsque vous testez le modèle sur 100 images supplémentaires de plantes, vous découvrez qu'il a correctement identifié les fleurs, les arbres et les herbes la majorité du temps, mais qu'il y a également eu un certain nombre d'erreurs. Le Tableau 6.6 présente les résultats dans une matrice de confusion :

	Identifié comme une fleur	Identifié comme un arbre	Identifié comme une herbe
Est une fleur	23	3	9
Est un arbre	2	32	0
Est une herbe	12	1	18

Tableau 6.6 Une matrice de confusion pour les fleurs, les arbres et les herbes

Ainsi, nous pouvons voir que 23 fleurs, 32 arbres et 18 herbes ont été correctement identifiés, ce qui donne au modèle une exactitude de $\frac{23 + 32 + 18}{100} = 0.73$ , soit 73 %. Remarque : les termes TP, TN, FP et FN introduits dans Qu'est-ce que l'apprentissage automatique ? et définis à nouveau dans l'exemple suivant ne s'appliquent pas lors de la classification de données en trois catégories ou plus ; cependant, la matrice de confusion donne des informations plus détaillées sur les erreurs. Lorsque les nombres hors de la diagonale principale sont relativement bas, le modèle a obtenu de bons résultats. À l'inverse, des nombres plus élevés hors de la diagonale principale indiquent des taux d'erreur d'identification, ou de confusion, plus élevés. Dans cet exemple, lorsqu'on lui présentait une image de fleur, le modèle réussissait assez bien à l'identifier comme une fleur, mais confondait les fleurs avec des herbes plus souvent qu'avec des arbres. Le modèle a très bien réussi à identifier les arbres comme des arbres, ne les confondant jamais avec des herbes et ne les confondant que deux fois avec des fleurs. En revanche, le modèle n'a pas été aussi efficace pour identifier les herbes. Près de 40 % des images d'herbes ont été confondues avec des fleurs ! Avec ces informations en main, vous pourriez revenir à votre modèle et ajuster les paramètres de manière à traiter ces problèmes spécifiques. Il peut y avoir un moyen de modifier le modèle qui aide particulièrement à identifier les herbes. Ou vous pouvez décider de prendre des mesures supplémentaires chaque fois qu'une image est identifiée comme une fleur, par exemple en soumettant l'image à une analyse supplémentaire pour vous assurer qu'il s'agit bien d'une fleur et non pas d'une herbe mal étiquetée.

Lorsqu'il n'y a que deux classes (classification binaire), la matrice de confusion n'aurait bien sûr que quatre entrées. Des termes spéciaux s'appliquent à ce cas lorsque les deux classes sont « Positif » et « Négatif ». Pensez au diagnostic d'une maladie. Soit le patient a la maladie, soit il ne l'a pas. Un médecin peut effectuer un test, et l'espoir est que le test déterminera avec certitude si le patient a cette maladie. Malheureusement, aucun test n'est précis à 100 %. Les deux cas dans lesquels le test échoue sont appelés faux positif et faux négatif. Un faux positif (également appelé erreur de type I) se produit lorsque l'état réel est négatif, mais que le modèle ou le test prédit un résultat positif. Un faux négatif (également appelé erreur de type II) est exactement le contraire : l'état est positif, mais le modèle ou le test prédit un résultat négatif. Les deux erreurs peuvent être dangereuses dans des domaines tels que la médecine. Une certaine terminologie pour les quatre possibilités est présentée dans le Tableau 6.7.

	Prédit Positif	Prédit Négatif
Positif réel	Vrai positif (TP) – succès	Faux négatif (FN) – échec
Négatif réel	Faux positif (FP) – fausse alerte	Vrai négatif (TN) – correctement rejeté

Tableau 6.7 Terminologie résumant les quatre possibilités d'une matrice de confusion

Les ajustements apportés à un modèle pour réduire un type d'erreur augmentent généralement le taux de l'autre type d'erreur. C'est-à-dire que si vous souhaitez que votre modèle ait un taux très faible de faux négatifs, il peut acquérir un biais positif (devenir plus sensible), prédisant davantage de positifs, qu'il s'agisse de vrais ou de faux positifs. En revanche, si le taux de faux positifs doit être réduit, le modèle peut acquérir un biais négatif (devenir moins sensible) et produire davantage de prédictions négatives dans l'ensemble, à la fois de vrais et de faux négatifs.

Visualisation des matrices de confusion

Les matrices de confusion sont souvent ombrées ou colorées de manière à montrer le contraste entre les valeurs élevées et les valeurs faibles, ce qui est utile pour localiser tout comportement anormal dans le modèle, souvent appelée une carte thermique (heatmap). La Figure 6.17 fournit une carte thermique pour l'exemple fleurs/arbres/herbes.

Une carte thermique à 9 cellules. De gauche à droite, les colonnes sont étiquetées « fleur », « arbre », « herbe ». De haut en bas, les lignes sont étiquetées « fleur », « arbre », « herbe ». La ligne supérieure indique 23, 3, 9. La ligne centrale indique 2, 32, 0. La ligne inférieure indique 12, 1, 18. Les cellules ont différentes nuances de gris, 0 étant la plus claire et 32 la plus sombre.

Figure 6.17 Carte thermique pour l'exemple fleur/arbre/herbe

Les nuances plus sombres indiquent des valeurs plus élevées. La diagonale principale se détache avec des cellules plus sombres. C'est ce à quoi on peut s'attendre si notre classificateur fait son travail. Cependant, des nuances plus sombres dans les cellules situées en dehors de la diagonale principale indiquent des taux d'erreur de classification plus élevés. Les nombres 12 en bas à gauche et 9 en haut à droite sont marquants. Le modèle a manifestement plus de mal avec les fleurs et les herbes qu'avec les arbres.

Génération d'une matrice de confusion en Python

Le jeu de données CollegeCompletionData.csv contient 62 points de données (parmi lesquels seulement 12 points de données ont été utilisés dans le Tableau 6.6). Le code suivant produit une régression logistique basée sur l'ensemble des 62 points. Ensuite, la matrice de confusion est générée. Enfin, un affichage visuel de la matrice de confusion sous forme de carte thermique est généré à l'aide d'une autre bibliothèque de visualisation appelée seaborn. Si vous n'avez pas besoin de la carte thermique, tapez simplement print(cf) directement après avoir obtenu la matrice de confusion pour afficher une version textuelle de la matrice.

Code Python

      # Import libraries
      import pandas as pd  ## for dataset management
      import matplotlib.pyplot as plt ## for data visualization
      import seaborn as sns ## for heatmap visualization
      from sklearn.linear_model import LogisticRegression
      from sklearn.metrics import confusion_matrix
      
      # Read data
      data = pd.read_csv('CollegeCompletionData.csv').dropna()
      x = data[['GPA']]
      y = data['Completion']
      
      # Build the logistic model
      model = LogisticRegression()
      model.fit(x,y)
      
      # Generate model predictions
      y_pred = model.predict(x)
      
      # Generate the confusion matrix
      cf = confusion_matrix(y, y_pred)
      
      # Plot the heatmap using seaborn and matplotlib
      sns.heatmap(cf, annot=True, fmt='d', cmap='Blues', cbar=True)
      plt.xlabel('Predicted')
      plt.ylabel('True')
      plt.yticks(rotation=0)
      plt.title('Confusion Matrix')
      plt.show()

La sortie obtenue ressemblera à ceci :

Une matrice de confusion visualisant la performance d'un modèle de classification binaire. La matrice comporte deux lignes et deux colonnes, représentant respectivement les classes réelles et prédites. Les cellules diagonales (en haut à gauche et en bas à droite) montrent le nombre d'instances correctement classées (vrais positifs et vrais négatifs), tandis que les cellules hors diagonale montrent le nombre d'instances mal classées (faux positifs et faux négatifs). Dans le sens des aiguilles d'une montre à partir du coin supérieur gauche, les cases indiquent : 20, 10, 24, 8. Une échelle de couleurs sur la droite indique la fréquence de chaque valeur. Elle s'étend sur le côté droit de la matrice, commençant en bleu clair à 5.0 et devenant plus foncée en haut à 25. La couleur des cases correspond à cette échelle.

D'après l'analyse précédente, nous trouvons 20 vrais positifs et 24 vrais négatifs, ce qui représente une exactitude de $44 / 62 = 71 %$ . Il y a eu 10 faux négatifs et 8 faux positifs.