Blog

Blog: Les techniques de détection d’anomalies

http://bit.ly/31ugCEY


Approche non supervisée

Dans cet article, on va introduire d’autres techniques pour la détection d’anomalies qui sont plus sophistiquées telles que le clustering DBSCAN, le réseau bayésien et l’auto-encoder.

Techniques basées sur le clustering

On peut utiliser le clustering comme une technique pour la détection d’anomalies. L’hypothèse clé est que les observations normales appartiennent à des clusters de grande taille et denses, alors que les anomalies n’appartiennent à aucun cluster ou appartiennent à des petits clusters isolés. Alors vu cette approche, il faut faire un post-traitement du résultat du clustering afin de déterminer les observations à considérer comme anomalies. Les anomalies détectées peuvent être des observations qui n’appartiennent à aucun cluster, des petits clusters ou des clusters de faibles densités.

Le DBSCAN est un algorithme de clustering basé sur la densité, son résultat final est un ensemble de clusters de différentes tailles et des points isolés n’appartenant à aucun cluster, cette caractéristique permet son utilisation pour la détection d’anomalies, où les points identifiés comme du bruit par l’algorithme seront considérés comme des anomalies.

L’algorithme est basé sur deux paramètres :

  • eps : rayon minimal de voisinage ;
  • MinPts : nombre de points minimum pour former un cluster.

Un point qui a au moins MinPts points dans son voisinage de rayon eps est marqué comme un core point. On a appelle X un border point, si le nombre de point dans son voisinage est inférieur à MinPts.

Illustration de l’utilisation des paramètres eps et MinPts

Il faut définir trois termes afin de comprendre le fonctionnement de l’algorithme :

  • Direct density reachable : Un point A est directly density reachabled’un autre point B si : 1) A est dans le cercle de rayon eps et de centre B, et 2) B est un core point ;
  • Density reachable : Un point A est density reachable de B s’il y a un groupe de core points menant de B à A ;
  • Density connected : A et B sont density connected lorsqu’il y un core point C dont les deux points A et B sont density reachable de C.

Les clusters renvoyés par l’algorithme sont des density-based clusters ce qui signifie que chaque cluster est un ensemble de points Density connected.

L’algorithme fonctionne de la manière suivante :

  • Pour chaque point x , calculer les distances aux autres points, puis trouver parmi ces points, ceux à une distance inférieure à eps (les voisins) ;
  • Chaque point avec un nombre de voisins supérieur à MinPts est marqué comme un « core point » ;
  • Pour chaque « core point » n’appartenant à aucun cluster, créer un nouveau cluster ;
  • Trouver tous les points « density connected » au « core point » et les mettre dans le même cluster ;
  • Itérer sur le reste des points.

Les points qui n’appartiennent à aucun cluster sont traités comme outliers. La figure ci-dessous nous montre les différents clusters qui ont des formes fortement non linéaires, et les outliers sous formes de points noirs.

Un exemple des résultats de clustering en utilisant dbscan[]

Exemple avec script et figure des résultats

On va utiliser cette fois le dbscan pour détecter les transactions frauduleuses. Comme vu précedemment, le dbscan prend deux paramètres principaux : l’eps et le MinPts. Le plus difficile à fixer est l‘eps, dont nous ne connaissons pas l’ordre de grandeur à l’avance. Il vaut donc mieux tracer le kNN plot qui consiste à calculer la distance dk pour chaque observation et faire le graphe des distances en ordre décroissant. Habituellement, nous choisissons comme eps la distance qui correspond au “knee” de la courbe. Dans ce cas, il est difficile de faire l’approximation visuellement et nous prenons donc une valeur qui correspond au percentile de 99% soit 275.

Après avoir déterminé la valeur du eps et fixé la valeur du deuxième paramètre MinPts(min_samples) à 10, nous entraînons notre modèle dbscan. Un grand cluster 0 contient 283185 observations et d’autres très petits clusters (1,2,3,4 et 5) ont une dizaine d’observations chacun. Le reste des points est considéré comme du bruit et affecté au cluster -1. Il semble naturelle dans notre cas, de considérer les observations appartenant au cluster 0 comme normales et toutes les autres comme des anomalies.

Nous remarquons que le modèle n’est pas assez performant : il l’est moins que le modèle local factor outlier, en comparant leurs precisions recall et f1-score. Une des pistes d’amélioration de la performance du modèle, consiste à optimiser les paramètres eps et min_samples (via un grid search par exemple).

En résumé, voici en quelques points les avantages et les inconvénients des techniques de détection d’anomalie par clustering :

  • Avantages :

-Pas besoin d’un apprentissage supervisé, et donc pas besoin de données labellisées ;

-Flexible et adaptable aux nouvelles données. Possibilité de rajouter des nouvelles formes de cluster non vues auparavant.

  • Inconvénients :

-Coûteux en temps de calcul et en mémoire ;

-Si les points normaux ne créent aucun cluster (observations très hétérogènes par exemple), la technique échouera ;

-En grandes dimensions, cela perd sa significativité : les distances seront très similaires.

Techniques probabilistes : réseau bayésien

Le réseau bayésien est un modèle graphique probabiliste représentant des variables aléatoires sous la forme d’un graphe orienté acyclique. Il repose essentiellement sur le calcul des probabilités conditionnelles. Le réseau bayésien est le plus performant pour la détection d’anomalies dans le cas où les données sont de grandes dimensions et de types mixtes (discrètes et continues).

Dans un modèle graphique probabiliste, chaque nœud dans le graphe représente une variable et les liens (arêtes) connectent des paires de nœuds pour représenter la possible relation causale. Le réseau bayésien appartient à la famille des modèles graphiques connus sous le nom de diagramme acyclique dirigé (DAG), ce qui signifie que les arêtes ont une direction et il n’y a pas de cycle dans le graphe.

Etant donnée la structure S et les paramètres P, la distribution de probabilité conjointe pour X est donnée par le produit entre les probabilités antérieures individuelles de tous les nœuds parents en X et les probabilités conditionnelles de tous les nœuds enfants en X :

Pour calculer la probabilité d’occurrence d’une observation X, nous utilisons la distribution de probabilité conjointe. Plus cette probabilité d’occurrence est faible, plus l’observation va être considérée comme aberrante. Prenons un exemple :

Un exemple de structure d’un réseau bayésien avec les tables de probabilités conditionnelles[1]

Les réseaux bayésiens sont bien adaptés à la détection d’anomalie, car ils peuvent gérer des données dimensionnelles élevées difficiles à interpréter par l’humain. Bien que certaines anomalies soient clairement visibles en traçant des variables individuelles, les anomalies sont souvent beaucoup plus subtiles et sont basées sur l’interaction de nombreuses variables.

Les réseaux bayésiens ont également les propriétés suivantes, utiles pour la détection d’anomalies :

  • Prise en compte des variables catégoriques et continues ;
  • Capacité à traiter les données en grandes dimensions (difficile à interpréter par les humains) ;
  • Il n’est pas coûteux en temps de calcul et en mémoire, et donc est très utile pour traiter les larges jeux de données.

Exemple avec script et figure des résultats

Nous allons faire cet exemple en R, pour pouvoir utiliser le package Bnlearn qui nous permet avec ses différents algorithmes et fonctions implémentés de bien traiter la problématique de détection d’anomalies. La fonction hc() du package représente l’algorithme hill-climbing pour l’apprentissage de la structure du DAG. Pour arriver à la structure optimale que nous voyons sur la figure ci-dessous, nous réalisons l’apprentissage de la structure du réseau. Pour les score based algorithms, il y a deux étapes:

  • Définir un score qui évalue comment les indépendances et les dépendances entre les variables “match” les observations. En d’autre termes, comment la structure du réseau fit les données, ce qu’on appelle en général la vraisemblance. On peut utiliser le maximum de vraisemblance comme critère.
  • Chercher la structure qui maximise le plus ce score.

L’algorithme fait aléatoirement construire la structure à chaque fois et conserve celle qui maximise le score. Cette famille est appelée “score based algorithm”. Le logarithme du maximum de vraisemblance est calculé à l’aide de l’expression suivante :

n étant le nombre de variables dans le jeu de données qui sera le nombre de noeuds du graphe ; qi le nombre de combinaisons possible des parents Pai du noeud xi ; ri le nombre de modalités de la variable xi ; Nijk la fréquence d’apparition de la modalité k sous la configuration j des parents Pai du noeud xi ; et Nij est la fréquence d’apparition de la configuration j des parents Pai du noeud xi.

Il y a d’autres familles d’algorithmes, pour chercher la structure optimale, qui sont basées sur les tests d’indépendance entre les variables, comme le test 2 ou le mutual information test. Cette famille est appelée “constraint based algorithm”.

la structure DAG du réseau bayésien

Une fois l’apprentissage de structure fait, nous passons à l’apprentissage des paramètres, qui correspond à l’apprentissage des tables de probabilités conditionnelles au niveau de chaque noeud de la structure. Ensuite, nous calculons la probabilité conjointe de chaque observation qui indique sa probabilité d’appartenance aux données. Plus cette probabilité est faible, plus l’observation est aberrante, et plus le score de loglikhood tend vers — infini.

La figure ci-dessous montre les scores pour les 284 000 observations que nous avons dans le jeu de données. Nous voyons qu’il y a quelques points qui ont un score très petit par rapport à l’ensemble. Nous allons prendre les N observations possédant les scores les plus petits. Pour avoir plus de précision dans les prédictions, Il faut choisir le nombre d’outliers N à considérer qui correspond au pourcentage réel d’anomalies dans les données.

Le loglikhood de toutes les observations du jeu de données

Si nous considérons que les observations avec un score inférieur de -300 sont des anomalies, nous obtenons 920 transactions frauduleuses.

Les performances du modèle bayésien sont bien meilleures que les deux autres. Nous obtenons une précision de 17%, i.e. que 17% des anomalies renvoyées par le modèles sont donc des vraies anomalies. Le rappel de 32% indique que nous arrivons à détecter un tiers des transactions frauduleuses.

Conclusion

Dans cet article, l’accent a été mis sur trois familles d’approches non supervisées qui permettent de traiter les problématiques de détections d’anomalies.
L’exemple de la fraude pour les cartes bancaire montre que les performances des approches sont différentes. Le réseau bayésien a ainsi montré une bien meilleure performance que le local factor outlier, qui a montré une bonne capacité de détection d’anomalies. D’autres techniques existantes n’ont pas été étudiées dans cet article comme l’auto-encoder et l’algorithme isolation-forest et pourront faire l’objet d’un prochain article.

Bibliographie

[1] https://scikit-learn.org/stable/auto_examples/neighbors/plot_lof_outlier_detection.html

[2] http://www.sthda.com/english/wiki/wiki.php?id_contents=7940

[3] Sakshi Babbar and Sanjay Chawla. On Bayesian Network and Outlier Detection. Sydney NSW 2006 : https://www.cse.iitb.ac.in/~comad/2010/ResearchTrack/paper%2017.pdf

Rédigée par Mohamed Sfina et Youssef Guezguez

Source: Artificial Intelligence on Medium

Leave a Reply

Your email address will not be published. Required fields are marked *

Back To Top
a

Display your work in a bold & confident manner. Sometimes it’s easy for your creativity to stand out from the crowd.

Social