Arbres de décision et Support Vector Machines

By Paul Claret

10 minutes read - 06/12/24

Decision Tree : Classification et Régression

Introduction

Grâce à sa simplicité et sa capacité à être interprété facilement, il est souvent utilisé dans les tâches de classification et de régression. Un arbre de décision est une méthode qui prend des décisions en posant une série de questions simples sur les caractéristiques des données. Chaque question correspond à une branche de l’arbre, et chaque réponse conduit à un autre niveau de l’arbre jusqu’à une prédiction finale.

Par exemple, si vous souhaitez classifier des fruits en fonction de leurs caractéristiques (taille, couleur, texture), l’arbre de décision posera des questions comme : « La taille est-elle supérieure à 5 cm ? », et il suivra les branches de l’arbre jusqu’à arriver à une conclusion finale (par exemple, “c’est une pomme”).

Dans quel cas l’utiliser ?

L’algorithme des arbres de décision est souvent utilisé dans plusieurs situations :

• Classification simple : Très efficace pour la classification binaire ou multiclasse.
• Régression : Peut prédire des valeurs continues.
• Interprétabilité élevée : Les arbres sont facilement compréhensibles et peuvent être visualisés pour une meilleure compréhension des décisions.
• Peu de prétraitement des données nécessaire : Fonctionne bien même sans normalisation des caractéristiques.

Fonctionnement de l’algorithme Decision Tree

Principe

Un arbre de décision est une structure hiérarchique où chaque nœud interne représente une question sur une caractéristique, chaque branche représente une réponse à cette question, et chaque feuille représente la prédiction finale (une classe pour la classification ou une valeur pour la régression).

Par exemple, pour un problème de classification des fruits, un arbre peut poser des questions comme :

1. « La couleur est-elle rouge ? »
2. « La taille est-elle supérieure à 5 cm ? »
3. Etc.

Chaque réponse guide l’algorithme à travers les différentes branches de l’arbre jusqu’à une prédiction finale. Voici un exemple.

1. Construction de l’arbre

La construction d’un arbre de décision suit une méthode appelée “division récursive”. Cela signifie que l’arbre divise continuellement les données en groupes plus petits selon les caractéristiques les plus pertinentes.

Pour déterminer comment diviser les données, l’algorithme utilise des métriques comme :

• L’Entropie (pour la classification)
  L’entropie mesure la désorganisation des classes. Un faible niveau d’entropie indique des groupes homogènes.

• L’Indice de Gini (pour la classification)
  Il mesure la probabilité de classer incorrectement un élément dans un groupe.

• La Variance (pour la régression)
  Elle est utilisée pour minimiser la dispersion des valeurs prédictives dans les feuilles.

2. Sélection de la meilleure division (split)

À chaque nœud, l’algorithme doit choisir la meilleure caractéristique pour diviser les données. Pour ce faire, il utilise des critères d’impureté :

1. Entropie (Information Gain) :
   L’algorithme mesure l’entropie des groupes pour choisir la meilleure caractéristique qui réduit l’impureté des groupes.

2. Indice de Gini :
   Une autre métrique souvent utilisée pour mesurer l’impureté des groupes et choisir la meilleure division.

Exemple visuel

Prennons l’arbre de décision suivant. Il commence par classer les objects selon premier critère qui broie la majorité du travail en séparant le graph en 2. Il continue ensuite jusqu’à ce que les objets soient correctement classés.

Les étapes de l’implémentation de Decision Tree

1. Préparation des Données

Avant de construire votre arbre de décision, il est nécessaire de préparer vos données :

1. Nettoyage des Données

   • Éliminez les valeurs manquantes.
   • Traitez les valeurs aberrantes, car elles peuvent fausser l’arbre de décision.

2. Codage des Données Catégorielles
   Les arbres de décision gèrent directement les valeurs catégorielles. Par exemple :

   • “Rouge” peut être représenté directement sans transformation particulière.
   • Si nécessaire, effectuez un encodage en one-hot pour certaines caractéristiques.

2. Construction de l’arbre

Lors de la construction, l’algorithme suit plusieurs étapes :

1. Choix des Splits optimaux

   • Pour chaque caractéristique, évaluez l’entropie et l’indice de Gini pour choisir le meilleur split.
   • Comparez les différentes divisions et sélectionnez celle qui réduit le plus l’impureté.

2. Création des feuilles

   • Continuez à diviser les branches jusqu’à ce que :
     • Toutes les feuilles contiennent des points appartenant à une seule classe.
     • Une profondeur maximale de l’arbre est atteinte pour éviter le surapprentissage (overfitting).

3. Taille et Complexité de l’Arbre

Un arbre trop profond peut entraîner le problème de surapprentissage où l’algorithme mémorise trop les détails de l’entraînement. Pour éviter cela :

1. Pruning (Élagage) :
   Une méthode qui réduit la taille de l’arbre en supprimant les branches peu significatives après sa construction.

2. Max Depth et Min Samples Split

   • Des hyperparamètres qui limitent respectivement la profondeur de l’arbre et le nombre de points nécessaires pour créer une division.

Implémentation basique en Python

La bibliothèque Scikit-learn offre une implémentation facile des arbres de décision. Voici un exemple de base :

                    
from sklearn.tree import DecisionTreeClassifier
import numpy as np
                        
# Exemple des caractéristiques et des labels
X = np.array([[1, 2], [2, 1], [3, 3], [4, 2]])
y = np.array(['pomme', 'orange', 'banane', 'pomme'])
                        
# Construction et entraînement du modèle de l'arbre de décision
clf = DecisionTreeClassifier(max_depth=3)
clf.fit(X, y)
                        
# Prédiction d'une nouvelle observation
new_data = np.array([[2, 2]])
prediction = clf.predict(new_data)
                        
print("Classe prédite :", prediction)
                    
                

Avantages et limites de l’algorithme Decision Tree

Avantages

1. Interprétabilité Facile
   Les arbres sont facilement compréhensibles pour les humains.

2. Aucun besoin de prétraitement complexe des données
   Les valeurs catégorielles sont directement supportées.

3. Flexibilité
   Peut être utilisé pour des tâches de classification et régression.

Inconvénients

1. Surapprentissage (Overfitting)
   Un arbre trop complexe peut mémoriser des détails non essentiels et échouer sur des nouvelles données.

2. Instabilité
   Un petit changement dans les données d’entraînement peut entraîner un arbre complètement différent.

3. Profondeur excessive
   La taille des arbres peut devenir énorme et difficile à interpréter.

SVM (Support Vector Machine) – Classification et Régression

Introduction

Les Support Vector Machines (SVM) sont des algorithmes de machine learning puissants et polyvalents qui peuvent être utilisés pour des tâches de classification et de régression. Les SVM sont particulièrement appréciés pour leur capacité à maintenir des performances élevées, même lorsque les données sont complexes et en haute dimension.

Contrairement à KNN ou aux arbres de décision, qui sont souvent plus simples à interpréter, les SVM reposent sur des concepts mathématiques plus sophistiqués comme les marges maximales et les noyaux (kernels). Cela leur confère une grande flexibilité et des performances solides, mais en contrepartie, ils nécessitent des choix stratégiques concernant leurs hyperparamètres.

Pourquoi utiliser SVM ?

Les SVM sont souvent utilisés pour des tâches où les relations entre les données ne sont pas triviales et nécessitent des solutions robustes. Voici les principaux cas d’usage de SVM :

1. Séparation des classes en haute dimension
   Les SVM sont extrêmement efficaces lorsque l’ensemble des données possède un grand nombre de caractéristiques (features). Ils peuvent gérer des espaces multidimensionnels sans perte significative de performance.

2. Marges maximales
   L’un des concepts clés des SVM est la recherche de l’hyperplan qui maximise la distance entre les classes. Cela permet une meilleure généralisation, réduisant ainsi le risque de surapprentissage.

3. Flexibilité grâce aux noyaux (Kernels)
   Les noyaux permettent aux SVM de travailler dans des espaces non linéaires. Il existe plusieurs types de noyaux, chacun adapté à un besoin spécifique :

• Noyau linéaire (linear) : Pour des classes parfaitement séparables.
• Noyau polynomial (poly) : Utile lorsque les relations ne sont pas strictement linéaires.
• Noyau RBF (Radial Basis Function) : Souvent utilisé lorsque les classes ne sont pas linéairement séparables.

Fonctionnement des SVM

Concept des marges maximales

L’idée principale des SVM repose sur le concept de marge maximale. En d’autres termes, SVM cherche l’hyperplan qui maximise la distance entre les points des deux classes. Cette séparation est cruciale pour une bonne généralisation du modèle.

• En classification, l’objectif est de trouver l’hyperplan qui divise correctement les différentes classes.
• En régression, on utilise les Support Vector Regression (SVR) pour prédire des valeurs continues tout en maintenant une marge d’erreur minimale.

Le noyau (Kernel)

Lorsque les relations ne sont pas linéaires, SVM utilise des noyaux pour transformer les données en un espace de dimensions plus élevées, où les classes deviennent linéairement séparables.

• Noyau linéaire : Idéal lorsque les classes peuvent être séparées sans difficulté.
• Noyau polynomial : Utilisé pour des relations plus complexes.
• Noyau RBF : Un choix très populaire qui fonctionne bien pour des relations non linéaires.

Par exemple, en utilisant un noyau RBF, il est possible de projeter des points dans un espace à plus haute dimension, où l’algorithme SVM trouve facilement un hyperplan séparant les différentes classes.

Les étapes de l’implémentation de SVM

1. Préparation des Données

Comme pour tous les algorithmes de machine learning, une bonne préparation des données est essentielle pour des résultats optimaux.

1. Nettoyage des Données :
   Assurez-vous que vos données ne contiennent pas de valeurs manquantes ou des valeurs aberrantes qui pourraient fausser l’entraînement.

2. Normalisation / Standardisation :
   Les SVM sont sensibles aux échelles des caractéristiques, il est donc souvent nécessaire de les normaliser.

• Normalisation MinMax :

  Xnorm=X−XminXmax−XminX_{norm} = Xnorm​=Xmax​−Xmin​X−Xmin​​

• Cela garantit que toutes les caractéristiques sont sur la même échelle et évite que certaines dominent l’entraînement.

2. Choix du noyau et des hyperparamètres

Les hyperparamètres jouent un rôle crucial dans la performance des SVM :

• Le paramètre CCC : Il contrôle la régularisation. Une valeur élevée peut entraîner du surapprentissage, tandis qu’une valeur faible peut causer du underfitting.
• Le noyau choisi (linear, poly, rbf) doit être sélectionné en fonction de la complexité des relations dans vos données.

3. Entraînement du modèle et prédiction

Une fois les hyperparamètres sélectionnés, vous pouvez utiliser une bibliothèque comme Scikit-learn pour entraîner votre modèle SVM.

Implémentation simple en Python avec Scikit-learn

Voici un exemple de code basique pour implémenter SVM en Python :

                    
from sklearn.svm import SVC 
from sklearn.preprocessing import StandardScaler 
import numpy as np  
                        
# Exemple de données 
X = np.array([[1, 2], [2, 3], [3, 1], [6, 5]]) 
y = np.array([0, 1, 0, 1])  
                        
# Normalisation des données 
scaler = StandardScaler() 
X_normalized = scaler.fit_transform(X)  
                        
# Création et entraînement du modèle SVM 
svm = SVC(kernel='rbf', C=1.0) 
svm.fit(X_normalized, y)  
                        
# Prédiction sur une nouvelle donnée 
nouvelle_donnée = np.array([[2, 2]]) 
nouvelle_donnée_normalisée = scaler.transform(nouvelle_donnée) 
prediction = svm.predict(nouvelle_donnée_normalisée)  
print("Classe prédite :", prediction)
                    
                

Avantages et inconvénients des SVM

Avantages

• Robustesse en haute dimension : Convient parfaitement pour des ensembles de données complexes.
• Marges maximales : Aide à éviter le surapprentissage grâce à une meilleure généralisation.
• Flexibilité avec les noyaux : Capable de s’adapter à des relations linéaires et non linéaires.

Inconvénients

• Coût computationnel élevé : En particulier lorsque l’ensemble des données est grand.
• Sensibilité aux valeurs aberrantes : Les valeurs aberrantes peuvent affecter la qualité des hyperplans.
• Choix des hyperparamètres délicat : La performance dépend des paramètres C et du noyau sélectionné.

Conclusion

Les arbres de décision sont des outils puissants pour de nombreux problèmes de machine learning. Ils permettent une compréhension intuitive des décisions grâce à leur structure visuelle simple. Toutefois, il est nécessaire de prendre des précautions comme l’élagage (pruning) ou la réduction de la profondeur maximale pour éviter le surapprentissage.

Les arbres de décision peuvent être utilisés seuls ou combinés à d’autres algorithmes plus robustes, comme les Random Forests, pour améliorer leurs performances et généraliser les prédictions.

Les Support Vector Machines (SVM) sont des outils essentiels en machine learning pour des tâches de classification et de régression, particulièrement adaptés aux ensembles de données avec des relations complexes et des dimensions élevées. Leur approche basée sur les marges maximales et les noyaux offre une puissance et une flexibilité remarquables.

Cependant, les SVM nécessitent des décisions stratégiques concernant les hyperparamètres et les noyaux, et peuvent être sensibles aux valeurs aberrantes. La clé du succès avec SVM réside dans une bonne préparation des données, le choix judicieux des hyperparamètres et l’expérimentation avec différents types de noyaux.

Les SVM peuvent également être combinés avec des techniques plus avancées comme Grid Search pour l’optimisation des hyperparamètres et des méthodes d’ensemble pour renforcer leur robustesse et leurs performances.

Vous voulez apprendre l'IA en autonomie ?

Si vous êtes nouveau sur mon site, je vous invite à aller voir ma page sur Roadmap IA qui regroupe tous mes articles dans l'ordre pour vous facilitez l'apprentissage.