Les méthodes de classification

Dans cet article, vous trouverez des détails sur les principaux algorithmes de classification supervisée (données étiquetées) et non-supervisée (données non-étiquetées). Beaucoup de ces algorithmes fonctionnent en réalité sur les mêmes exemples, mais avec des approches et parfois des niveaux de performance différents.

A. Quelques modèles de classification non-supervisée

• Classification hiérarchique (Single Linkage, Ward) : Les algorithmes de classification hiérarchique ont pour objectif de trouver des classes telles que les observations d’une classe soient plus proches entre elles qu’avec les observations d’autres classes. Pour ce faire, on détermine une mesure de dissimilarité, permettant de comparer deux groupes d’observations A et B. Pour la méthode de classification hiérarchique avec single linkage, cette mesure est :  

  

  où d est une mesure de distance entre deux observations, telle que la norme 2 :

  

  Pour le critère de Ward, la mesure de distance utilisée est plutôt :

  

  Le résultat intermédiaire d’un algorithme de classification hiérarchique est un dendrogramme, qui permet de visualiser les interactions entre les classes. Les méthodes de classification hiérarchique permettent même de séparer des classes de façon non-linéaire.

• K-Moyennes : L’algorithme des K-Moyennes (ou K-Means) a pour objectif de délimiter des classes telles que la variance au sein de chaque classe soit minimale. L’utilisation de ce modèle impose que l’utilisateur choisisse une valeur pour le nombre de classes final K. A l’initialisation de l’algorithme, le modèle choisit aléatoirement K points, qui joueront le rôle des barycentres des K classes. A chaque itération de l’algorithme, le modèle fait une prédiction de classe sur une observation, en l'associant à la classe du barycentre de laquelle elle est la plus proche. Ensuite, l’algorithme recalcule les barycentres des K classes. L’algorithme s’arrête lorsque les affectations sont stables. Cependant, le modèle des K-Moyennes ne fonctionne bien que pour des classes de forme sphérique (ou au moins convexes), et beaucoup moins bien pour des classes non-linéairement séparables, à cause du fait qu’il repose sur une notion de distance, souvent euclidienne.

• DBSCAN (Density-Based Spatial Clustering of Applications with Noise) : Cet algorithme a l’avantage de ne pas prendre en compte le bruit, c’est-à-dire les points d’observations isolés par rapport aux autres. Il ne nécessite pas que l’utilisateur connaisse le nombre de classes à l’avance, mais a besoin de valeurs pour deux hyperparamètres : la distance à partir de laquelle deux points ne peuvent plus être considérés comme voisins, et le nombre minimum de points pour qu’un groupe d’observations soit considéré comme une classe. A chaque itération de l’algorithme, le modèle sélectionne un point, le classe en « point cœur » s’il a un nombre important de voisins, en « point bordure » s’il est voisin d’un point cœur mais n’en est pas un, et en « point bruit » s’il est isolé. Ensuite, l’algorithme crée une classe autour d’un point cœur non-visité et y ajoute tous ses points bordure. C’est un algorithme plus complexe que les K-Moyennes par exemple, donc plus lent à exécuter. De plus, il est moins efficace pour des jeux de données à densité variable. En revanche, il permet de résoudre aussi les cas de classes non-linéairement séparables.

• Mean Shift : A l’initialisation de cet algorithme, chaque point de données est considéré comme un barycentre de classe. Ensuite, chaque barycentre est déplacé vers la moyenne des points voisins dans une certaine distance. Les barycentres trop proches sont fusionnés, et l’algorithme s’arrête lorsque les barycentres ne se déplacent plus. Cet algorithme nécessite qu’on détermine l'hyperparamètre h, représentant la distance en-dessous de laquelle deux points sont considérés comme voisins. Il existe cependant une fonction python estimate_bandwidth() qui permet d’obtenir une bonne proposition pour la valeur de h. Ce modèle est performant même dans le cas de classes non-linéairement séparables, mais il peut être plus lent à exécuter qu’un modèle plus simple, comme les K-Moyennes.

• Modèles de mélanges gaussiens (GMM) : Cet algorithme permet d’obtenir comme résultat la probabilité que chaque observation appartienne à chaque classe, contrairement à beaucoup d’algorithmes, qui se contentent de renvoyer la classe la plus probable pour chaque observation. Le nombre de classes final K doit être entré en paramètre par l’utilisateur (ce qui n’est pas toujours possible). Cet algorithme suppose que les données sont générées par plusieurs fonctions gaussiennes superposées, représentant chacune une classe. A l’initialisation, les caractéristiques de chaque gaussienne sont choisies aléatoirement. A chaque itération, l’algorithme choisit une observation et calcule la probabilité qu’elle appartienne à chacune des K gaussiennes. Ensuite, la gaussienne la plus probable voit ses paramètres modifiés pour maximiser la probabilité que l’observation lui appartienne. L’algorithme continue jusqu’à ce que les changements deviennent négligeables. Cet algorithme peut marcher sur des classes non-linéairement séparables, mais peut être inefficace lorsque les classes sont de formes trop complexes. L’hypothèse qui associe à chaque classe une gaussienne devient alors trop grossière.

B. Quelques modèles de classification supervisée

• Classifieur naïf de Bayes : Un classifieur de Bayes est un classifieur qui cherche à maximiser la probabilité a posteriori 

  

  où Ck est la classe k, et x est une observation. Mathématiquement, pour mettre en place le classifieur naïf de Bayes, on suppose que les différentes caractéristiques (ou colonnes) des observations sont indépendantes. On découpe ensuite le problème, pour réfléchir à la loi de probabilité conditionnelle de chaque caractéristique séparément, avant d’appliquer une formule mathématique pour trouver le classifieur. Ce classifieur est rapide à exécuter, car il ne calcule que les probabilités conditionnelles des caractéristiques, et non pas des observations entières. Il est aussi capable de délimiter des classes de façon non-linéaire. Cependant, il repose sur une hypothèse d’indépendance qui peut être trop grossière. Ce classifieur est moins performant que d’autres, et a surtout une importance historique.

• Régression logistique : Cet algorithme est aussi un classifieur de Bayes, mais qui consiste cette fois-ci à supposer une relation sigmoïde (un type de relation mathématique non-linéaire) entre les caractéristiques des observations et leur probabilité conditionnelle. De même, ce modèle est simple à calculer, donc rapide à exécuter. De plus, il ne repose pas sur une hypothèse d’indépendance, contrairement au classifieur naïf de Bayes. En revanche, il fait une autre hypothèse, plus complexe, de relation linéaire entre les caractéristiques des observations et le logarithme des probabilités. Ce modèle reste un modèle simple par rapport aux autres modèles de machine learning. Cette méthode est utilisable dans le cas d’une séparation des classes non-linéaire, grâce à l’astuce du noyau.

• Algorithme des k plus proches voisins (k-NN) : C’est un algorithme très simple : il consiste à attribuer à chaque observation la classe majoritaire parmi ses k plus proches voisins. Il est très intuitif, mais peut mener à du sur-apprentissage si k est trop faible. Il a aussi l’inconvénient de s’appuyer sur une hypothèse de distribution de probabilité constante sur l’ensemble des observations, assez simplificatrice. Il n’est utilisable que si les classes sont bien définies, mais la séparation entre les classes peut être non-linéaire.

• Machines à vecteurs supports (SVM) : Ces algorithmes ont pour objectif de chercher un hyperplan séparant les observations de chaque classe, en maximisant la distance minimale entre les observations et cet hyperplan. Les machines à vecteurs supports sont particulièrement utiles lorsque le nombre de données est limité, car elles prennent surtout en compte les observations à la limite des classes, et n’ont pas besoin d’une grande densité de données. Pour les cas où la séparation des classes est non-linéaire, les SVM peuvent être adaptées grâce à l’astuce du noyau.

• Auto-encodeurs (réseaux de neurones) : Les auto-encodeurs sont des réseaux de neurones artificiels. Les neurones artificiels, ou perceptrons, sont des algorithmes qui associent des poids à chaque caractéristique des observations, afin de faire une prédiction. Les neurones artificiels sont appelés ainsi car ils sont aussi capables d’effectuer les opérations logiques AND et OR, comme les neurones humains. Un auto-encodeur est un réseau de neurones artificiels en deux parties : une partie ayant pour objectif d’encoder les données de manière à réduire leur poids en mémoire, et une partie qui décode les données. Les auto-encodeurs cherchent à trouver la manière d’encoder les données pour réduire l’écart entre la valeur décodée ensuite et la valeur réelle. Une fois que ce processus d’encodage est mis-au-point, la classification s’opère sur les données encodées, à l’aide d’un algorithme tel que la régression logistique ou la SVM par exemple. Le modèle constitué de l’encodeur et de l’algorithme de classification associé ensuite sont entraînés ensemble sur la base de données. Les auto-encodeurs sont des modèles très complexes, qui fonctionnent même dans le cas de classes non-linéairement séparables. De plus, ils permettent, grâce à l’encodage des données, de réduire la dimension des observations, ce qui peut réduire le risque de sur-apprentissage. Cependant, à cause de leur complexité, ils peuvent être lents à l’exécution et ont besoin d’un grand nombre de données pour entraîner le modèle.

• Arbres de décision et Random Forest : Un arbre de décision est un algorithme de prédiction qui représente une série de règles de décision. A la racine de l’arbre se trouve l’ensemble des observations, et les feuilles de l’arbre sont les prédictions différentes possibles pour une observation. Un algorithme en arbre de décision peut présenter du sur-apprentissage, à cause de sa structure rigide et artificielle. L’algorithme Random Forest produit plusieurs arbres de décision, qui sont chacun calculés à partir d’un échantillon aléatoire des données. Pour chaque observation de la base de test, tous les arbres font une prédiction et l’algorithme renvoie la classe majoritairement prédite. Ce modèle permet de réduire le sur-apprentissage que pourrait présenter un arbre de décision seul. Cependant, son exécution est très coûteuse en temps et en mémoire, à cause de la complexité des calculs. Les arbres de décision sont utilisables même dans le cas non-linéaire.

• Perceptrons et réseaux de neurones artificiels : Le perceptron est aussi appelé « neurone artificiel ». C’est un des premiers algorithmes de machine learning. Il a pour objectif de faire de la classification sur des images ou des sons par exemple. Pour chaque observation de la base d’apprentissage, l’algorithme calcule une prédiction à partir d’un vecteur de poids associé aux caractéristiques des observations. Si la classe prédite est différente de la classe réelle, les poids sont modifiés. L’algorithme converge (c’est-à-dire a un nombre fini d’étapes) si les classes sont linéairement séparables. Le perceptron est intéressant car il est capable d’effectuer les opérations logiques AND et OR, tel un neurone humain. Cependant, il n’est pas capable d’effectuer l’opération du « ou exclusif ». C’est pourquoi on s’est ensuite intéressés aux réseaux de neurones artificiels. Ces réseaux de neurones artificiels introduisent des non-linéarités, grâce aux fonctions de seuil des neurones, ce qui permet de résoudre aussi des problèmes non-linéaires. Cependant, le modèle du réseau de neurones artificiels dépend de nombreux paramètres à fixer lors de l’initialisation du modèle, qui ont une forte influence sur les résultats du modèle, et qui sont généralement fixés aléatoirement. Le nombre de neurones dans la couche de sortie par exemple, est égal au nombre de classes que va chercher le modèle.

• Deep learning : Le deep learning désigne l’étude des réseaux de neurones convolutifs. Ces réseaux sont constitués de neurones formant plusieurs couches. Ces neurones analysent les observations (qui peuvent être des images par exemple), les découpent en plusieurs signaux et calculent un produit de convolution, réinjecté ensuite dans la couche de neurones suivante. Ces réseaux de neurones convolutifs permettent d’obtenir des taux d’erreurs deux fois moins élevés que les réseaux de neurones classiques, mais nécessitent l’emploi de GPU pour calculer les opérations de convolution. Ils sont efficaces lorsque les données sont en très grand nombre. Le deep learning est une discipline à part entière.

 Retrouvez d'autres contenus, et toutes nos formations sur : https://www.expertpython.fr/