logo aosis

Détection d’anomalies


La détection d’anomalies est un sujet classique en machine learning non supervisé. 

Dans cet article, je vais présenter une modélisation mathématique du problème et les grandes catégories d’algorithmes pour résoudre ce problème. 

Intuition mathématique 

Dans un problème de machine learning non supervisé, on a des observations, qui ont chacune des variables ou « features » en anglais. L’important, c’est qu’il n’y a pas de labellisation associée à chacune des observations. 

Intuitivement, l’objectif de la détection d’anomalies est de repérer quelles sont les observations qui sont différentes des autres. Il est cependant assez complexe de définir mathématiquement quel est l’objectif, car contrairement aux problèmes supervisés, on n’a pas accès à une vérité via un label. Il est important de comprendre que pour la partie entrainement du modèle, l’algorithme n’a pas accès à des données labellisées (sinon on serait dans un cas de classification). 

Une façon de modéliser le problème est de supposer que les observations suivent une loi à densité. Intuitivement, les observations vont être plus concentrées plus la densité est grande. Dans ce cas, on comprend qu’une anomalie est une observation qui apparait dans un endroit de l’espace où la densité est faible. Ou dit autrement, plus une observation va être loin des autres observations plus, elle va avoir tendance à être anormale, les algorithmes basés sur la distance utilisent ce principe. 

Ainsi, si on connait la fonction de densité avec laquelle ont été générées les observations, alors on peut résoudre le problème de détection d’anomalie, il suffit de dire que les observations pour lesquelles la densité est la plus faible sont des anomalies. Bien entendu, dans un cas pratique, on ne connait pas la densité des observations. Une technique de détection d’anomalies consiste à estimer la densité et ensuite les observations avec la plus faible densité estimée sont déclarées comme des anomalies. Une autre technique consiste à estimer les ensembles de niveaux de la densité, c’est-à-dire les régions de l’espace où les données sont suffisamment concentrées. Les observations, qui sont en dehors de ces ensembles de niveaux, sont déclarées comme des anomalies. 

Usuellement, un algorithme de détection d’anomalies va retourner une fonction d’évaluation, autrement dit une fonction qui va donner un score à chaque observation. Plus le score va être petit plus l’observation aura des chances d’être une anomalie. On voit que la fonction de densité remplie parfaitement ce rôle. 

Pour évaluer les performances des modèles, la plupart des approches classiques supposent qu’elles ont accès à un jeu de données labellisées pour comparer entre les algorithmes. Dans ce cas, les métriques classiques de classification peuvent être calculées telles que la précision, le rappel, le f1-score, l’aire sous la courbe ROC (AUC) et l’AUC partielle. 

Il existe cependant deux métriques peu utilisées basées uniquement sur des données non labellisées. Les courbes d’excès de masse (EM) et de masse-volume (MV) sont basées sur le principe qu’on veut mettre le maximum de données dans la plus petite région de l’espace possible. Pour une fonction d’évaluation, on intuite que les régions sont celle où le score est plus grand qu’un seuil. En faisant varier la taille de l’espace considéré, ou de façon équivalente le seuil de la fonction d’évaluation pour définir une région, on va obtenir une courbe qui va décrire les performances de l’algorithme. Finalement, on mesure l’aire sous la courbe et le meilleur algorithme est celui dont l’aire sous la courbe est la plus faible. Pour ces deux métriques, on intuite assez facilement que les courbes sont minimisées pour la fonction de densité (ou n’importe quelle fonction croissante de la densité). 

Les algorithmes 

Il existe des centaines d’algorithmes de détection d’anomalies qui sont chacun plus ou moins adaptés selon les données qu’on souhaite analyser. Nous allons donner un exemple typique pour chacune des grandes stratégies pour obtenir un détecteur d’anomalies. 

Technique statistique 

Les méthodes statistiques consistent à estimer directement la densité. 

Méthode paramétrique 

Une méthode paramétrique va supposer que les données sont distribuées selon une loi gaussienne (ou un mélange de loi gaussienne) et va apprendre les paramètres de la loi. Une fois les paramètres estimés, on obtient un estimateur de la densité que l’on peut utiliser pour trouver les anomalies. Cependant, si l’hypothèse de départ n’est pas correcte, notre estimateur a de mauvais résultats. 

Méthode non paramétrique 

Une méthode non paramétrique ne va pas faire d’hypothèse sur la loi des données et va directement estimer la densité. En une dimension, l’exemple le plus connu est l’histogramme qui va nous donner un estimateur de la densité. Pour ces techniques non paramétriques, on peut démontrer des vitesses de convergence sous de bonnes hypothèses. Toutefois, elles sont peu utilisées en pratique, car les hypothèses sont rarement au rendez-vous et qu’elles performent de moins en moins bien plus la dimension des données augmentent. 

Technique de classification 

Une possibilité est de revenir à un problème de classification. 

Méthode échantillonnage 

La méthode d’échantillonnage consiste à générer des données sous la loi uniforme, c’est-à-dire que tous les endroits de l’espace ont la même probabilité d’être tirées aléatoirement. Ensuite, on utilise n’importe quel algorithme de classification pour apprendre notre modèle en considérant les données de notre jeu de base comme les observations avec label positif et les données venant de notre jeu de données générées comme ayant un label négatif. 

Avec cette technique, on peut également directement calculer les métriques d’évaluation courbes d’excès de masse (EM) et de masse-volume (MV) pour comparer la performance des algorithmes. 

Méthode à une classe 

Une stratégie est d’utiliser un algorithme de classification à une classe. Un exemple de tel algorithme est le one-class SVM. Le SVM est une méthode à noyau qui consiste à transformer des données non linéairement séparables dans un espace de grande dimension, où une séparation linéaire est possible. Cela se fait en utilisant une fonction noyau qui calcule la similarité entre chaque paire de données d’entrée, permettant ainsi de les projeter dans un espace de dimension supérieure. L’objectif du one-class SVM est de séparer linéairement les données dans l’espace de à grande dimension avec d’un côté de l’hyperplan de séparation le maximum de données et en maximisant la marge par rapport à l’origine. 

Méthode d’arbres de décision 

Isolation Forest est un algorithme d’apprentissage automatique utilisé pour la détection d’anomalies dans les ensembles de données. L’idée de base derrière Isolation Forest est de créer des arbres de décision aléatoires qui divisent les données en partitions successives jusqu’à ce que chaque point de données soit dans sa propre partition. Les points de données qui peuvent être séparés avec moins de partitions sont considérés comme étant plus anormaux que les points de données qui nécessitent plus de partitions pour être séparés. 

L’avantage de l’Isolation Forest est qu’il peut détecter rapidement les points de données anormaux sans avoir besoin de comparer chaque point de données aux autres points de données dans l’ensemble de données. Il est également capable de détecter des anomalies dans des ensembles de données avec des attributs numériques et catégoriels, ainsi que des ensembles de données avec des attributs manquants.  

Technique des plus proches voisins 

L’idée est que les points de données qui ont une densité locale significativement plus faible que leurs voisins sont plus susceptibles d’être des anomalies. 

LOF (Local Outlier Factor) est une méthode de détection d’anomalies qui mesure la déviation de la densité locale d’un point de données par rapport à celle de ses voisins. 

LOF utilise le concept de factorisation de la densité pour mesurer la densité locale d’un point de données en le comparant à la densité de ses k-plus proches voisins. La densité locale d’un point de données est calculée en utilisant la distance entre le point et ses k-plus proches voisins. Ensuite, le LOF est calculé en comparant la densité locale du point de données à celle de ses voisins. Les points de données qui ont un LOF élevé ont une densité locale plus faible que leurs voisins, ce qui les rend plus susceptibles d’être des anomalies. 

Technique de clustering 

L’idée générale de l’utilisation d’une technique est la suivante : les données normales appartiennent à un cluster dense et de taille significative et ont des voisins similaires, tandis que les anomalies n’appartiennent à aucun cluster ou appartiennent à des clusters petits ou épars. 

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)) est un algorithme de clustering qui peut être utilisé pour identifier des groupes dans des données en trouvant les régions de densité élevée. Il fonctionne en regroupant des points de données en fonction de leur proximité spatiale et de leur densité. L’algorithme DBSCAN utilise deux paramètres importants : le rayon de recherche epsilon (ε) et le nombre minimum de points dans une région dense. Il commence par choisir un point aléatoire et recherche les autres points dans son voisinage défini par ε. Si le nombre de points dans ce voisinage est supérieur ou égal au minimum fixé, alors un nouveau groupe est créé. Sinon, le point est considéré comme du bruit ou il appartient à un groupe existant si son voisinage est proche de celui-ci. 

Technique en grande dimension 

Pour les données en grande dimension, une technique consiste à utiliser une méthode de réduction de la dimension pour exemple l’analyse en composante principale et de dire que les observations qui se retrouve les plus loin des autres dans l’espace projeté sont anormales. 

Conclusion 

Le problème de détection d’anomalies est un problème de machine learning non supervisé complexe et dont il est difficile d’avoir une formulation mathématique formelle. Il est intimement lié à la densité sous-jacente des observations qui apparait comme la fonction optimale pour résoudre ce problème. Cependant, les estimateurs directs de la densité ont souvent de mauvais résultats. Dans cet article, nous avons présenté quelques algorithmes pour faire de la détection d’anomalies pour illustrer les principes à utiliser pour résoudre ce problème. Il n’y a pas de meilleurs algorithmes dans l’absolu et il faudra choisir le plus adapté en fonction des données que l’on rencontre. 

Article écrit par Sylvain – Data Scientist

Pour suivre nos aventures sur LinkedIn :