Aller au contenu

Détectez les anomalies

Dans l’enquête de salaires du service carrières, un diplômé déclare 650 k$ par an. Génie de la finance, ou 65 k$ saisi avec un zéro de trop ? Au chapitre 2, une seule valeur de ce genre suffisait à faire passer le « salaire typique » de 60 à 87 k$. Repérer ces valeurs avant d’apprendre est donc vital. Et parfois, les repérer est le but : une transaction bancaire frauduleuse, une panne de capteur, une intrusion dans un réseau.

Ce chapitre est un complément : la détection d’anomalies ne figurait pas dans les notes de ce cours, mais c’est un chapitre classique des cours de data mining, et elle prolonge directement l’étape 1 de la roue (la véracité des données). Notre fil rouge : l’enquête de salaires, puis les couples (GPA, salaire).

Une anomalie (anomaly, outlier) est une observation qui s’écarte tellement des autres qu’on soupçonne qu’elle a été produite par un autre mécanisme. Cette définition, volontairement floue, recouvre trois réalités très différentes :

  • une erreur : saisie en dollars au lieu de milliers de dollars, capteur débranché, GPA de 34 au lieu de 3,4 ;
  • un cas rare mais réel : le fondateur de start-up, la transaction frauduleuse, le patient atteint d’une maladie orpheline ;
  • une nouveauté (novelty) : un comportement jamais vu jusqu’ici, par exemple un nouveau type de fraude.

On distingue aussi les anomalies par leur forme. Une anomalie ponctuelle est atypique en elle-même (650 k$). Une anomalie contextuelle n’est atypique que dans son contexte : 45 k$ est un salaire banal en général, mais étonnant pour un ingénieur logiciel à New York. Une anomalie collective est un groupe d’observations normales une à une, mais anormales ensemble (cent petits retraits en une heure).

La difficulté principale est l’absence d’étiquettes : en général, personne n’a marqué à l’avance quelles lignes sont anormales. La détection d’anomalies est donc le plus souvent non supervisée, ce qui complique beaucoup l’évaluation (dernière section).

Commençons par une seule variable, le salaire déclaré. Voici dix réponses à l’enquête, en k$ : 48, 52, 55, 58, 60, 61, 63, 66, 70 et 650.

La règle la plus connue mesure l’écart à la moyenne en nombre d’écarts-types :

zi=xi−xˉsz_i = \frac{x_i - \bar{x}}{s}

où xˉ\bar{x} est la moyenne de l’échantillon et ss son écart-type. On déclare anormale une valeur telle que ∣zi∣>3\lvert z_i \rvert > 3 : pour une loi normale, moins de 0,3 % des valeurs dépassent ce seuil.

Appliquons-la. La moyenne vaut 118,3118{,}3 et l’écart-type 186,9186{,}9 : la valeur 650 obtient z=(650−118,3)/186,9≈2,84z = (650 - 118{,}3)/186{,}9 \approx 2{,}84. Elle n’est pas détectée.

Comment est-ce possible ? La valeur aberrante gonfle elle-même la moyenne (de 59 à 118) et surtout l’écart-type (de 6,9 à 187), et se cache ainsi derrière sa propre influence. C’est l’effet de masque (masking). Pire, il existe une borne : avec l’écart-type d’échantillon, aucune valeur ne peut dépasser

∣zi∣≤n−1n\lvert z_i \rvert \le \frac{n - 1}{\sqrt{n}}

où nn est le nombre de valeurs. Pour n=10n = 10, cette borne vaut 9/10≈2,859/\sqrt{10} \approx 2{,}85. Avec dix valeurs, la règle ∣z∣>3\lvert z \rvert > 3 ne peut jamais rien détecter, quelle que soit l’énormité de l’erreur.

510152025303540nombre n de valeurs0123456|z|n ≤ 10 :la règle ne peutrien détectern = 10 : 2,85n = 11 : 3,02|z| maximal possible : (n − 1)/√nseuil de la règle |z| > 3
Jusqu'à 10 valeurs, aucun |z| ne peut dépasser 3, quelle que soit l'erreur : la règle est aveugle par construction.

La solution consiste à remplacer moyenne et écart-type par des statistiques qu’une valeur extrême ne peut pas faire bouger : la médiane et l’écart absolu médian (MAD, median absolute deviation), la médiane des écarts à la médiane. Le z-score robuste s’écrit

zirob=0,6745×xi−meˊdianeMADz_i^{\text{rob}} = 0{,}6745 \times \frac{x_i - \text{médiane}}{\text{MAD}}

Le facteur 0,6745 rend le MAD comparable à un écart-type pour des données normales. On signale généralement les valeurs telles que ∣zrob∣>3,5\lvert z^{\text{rob}} \rvert > 3{,}5.

Sur nos salaires, la médiane vaut 60,5 et le MAD 5,5. La valeur 650 obtient zrob≈72z^{\text{rob}} \approx 72 : elle est détectée sans la moindre ambiguïté, et toutes les autres restent entre −1,5-1{,}5 et 1,21{,}2.

650z classique : moyenne 118,3 ± 3 écarts-types (186,9) : 650 reste dedans (z ≈ 2,84)−400−2000200400600salaire déclaré (k$)650zone normale : ± 28,5z robuste : médiane 60,5, MAD 5,5 : 650 est à z ≈ 72
Le salaire de 650 gonfle la moyenne et surtout l'écart-type, au point de se cacher dans sa propre zone normale (effet de masque). La médiane et le MAD, eux, ne bougent presque pas.

Autre règle robuste, celle qu’utilisent les boîtes à moustaches : on calcule le premier quartile Q1Q_1, le troisième quartile Q3Q_3 et l’écart interquartile IQR=Q3−Q1IQR = Q_3 - Q_1, puis on signale toute valeur hors de l’intervalle

[ Q1−1,5×IQR ;  Q3+1,5×IQR ]\big[\,Q_1 - 1{,}5 \times IQR \,;\; Q_3 + 1{,}5 \times IQR\,\big]
4050607080salaire déclaré (k$)Q₁ − 1,5 IQR= 41,5Q₃ + 1,5 IQR= 79,5Q₁ = 55,75 Q₃ = 65,25650650signalé
La boîte va de Q1 à Q3 ; les bornes sont à 1,5 IQR de chaque côté. Toutes les valeurs y tiennent sauf 650 (l'axe est coupé pour la montrer).
import pandas as pd
salaires = pd.Series([48, 52, 55, 58, 60, 61, 63, 66, 70, 650]) # en k$
# z-score classique : victime de l'effet de masque
z = (salaires - salaires.mean()) / salaires.std()
print(salaires[z.abs() > 3]) # aucune valeur signalée
# z-score robuste (médiane et MAD)
med = salaires.median()
mad = (salaires - med).abs().median()
z_rob = 0.6745 * (salaires - med) / mad
print(salaires[z_rob.abs() > 3.5]) # 650
# Règle de l'écart interquartile
q1, q3 = salaires.quantile([0.25, 0.75])
iqr = q3 - q1
print(salaires[(salaires < q1 - 1.5 * iqr) | (salaires > q3 + 1.5 * iqr)]) # 650

Ces règles univariées sont précieuses pour l’étape 1 de la roue, variable par variable. Mais elles ne voient pas les anomalies contextuelles : un GPA de 3,9 est normal, un salaire de 40 k$ aussi, mais un diplômé à 3,9 de GPA et 40 k$ de salaire, dans une filière où tout le monde gagne 90 k$, est atypique. Il faut alors des méthodes multivariées.

Isolation Forest : isoler les cas faciles à séparer

Section intitulée « Isolation Forest : isoler les cas faciles à séparer »

L’idée d’Isolation Forest est d’une simplicité désarmante : une anomalie est facile à isoler. Choisissez une variable au hasard, puis un seuil au hasard entre son minimum et son maximum, et coupez les données en deux. Recommencez dans chaque moitié, jusqu’à ce que chaque point soit seul. Un point perdu loin des autres se retrouve seul après très peu de coupes ; un point au cœur d’un nuage dense en demande beaucoup.

2,53,03,5GPA5060708090salaire (k$)12point isolé : 2 coupes2,53,03,5GPApoint au cœur du nuage : 10 coupes
Des coupes aléatoires, variable par variable, jusqu'à ce que le point soit seul. Le point isolé l'est en 2 coupes ; le point du cœur du nuage en demande 10. C'est cette profondeur, moyennée sur la forêt, qui sert de score.

On construit ainsi une forêt de plusieurs centaines d’arbres de découpe aléatoire, chacun sur un petit sous-échantillon (256 points par défaut), et l’on mesure pour chaque point sa profondeur moyenne d’isolement E[h(x)]\mathbb{E}[h(x)]. Le score d’anomalie est

s(x)=2−E[h(x)]/c(ψ)s(x) = 2^{-\mathbb{E}[h(x)] / c(\psi)}
  • h(x)h(x) est le nombre de coupes nécessaires pour isoler xx dans un arbre ;
  • ψ\psi est la taille du sous-échantillon de chaque arbre ;
  • c(ψ)c(\psi) est la profondeur moyenne attendue pour un point quelconque, qui sert à normaliser (c(256)≈10,2c(256) \approx 10{,}2).

Un score proche de 1 signale une anomalie (isolée bien plus vite que la moyenne), un score autour de 0,5 ou en dessous un point ordinaire. Par exemple, avec ψ=256\psi = 256, un point isolé en 2 coupes en moyenne obtient s≈0,87s \approx 0{,}87, un point isolé en 10 coupes s≈0,51s \approx 0{,}51.

0,02,55,07,510,012,515,017,520,0profondeur moyenne d’isolement E[h(x)]0,00,20,40,60,81,0score s(x)c(256) ≈ 10,2 :profondeur moyenneisolé en 2 coupes :s ≈ 0,87 (anomalie)isolé en 10 coupes :s ≈ 0,51 (ordinaire)
Le score vaut 0,5 pour un point isolé à la profondeur moyenne c(256) ≈ 10,2, et se rapproche de 1 quand l'isolement est rapide.

La méthode a de beaux atouts : elle ne calcule aucune distance, passe très bien à l’échelle, et n’a pas besoin de standardiser les variables (les coupes se font variable par variable). Elle voit surtout les anomalies globales, éloignées de l’ensemble des données.

LOF : comparer une densité à celle de ses voisins

Section intitulée « LOF : comparer une densité à celle de ses voisins »

Le facteur local d’anomalie (local outlier factor, LOF) répond au cas contextuel. Pour chaque point, on estime une densité locale à partir de la distance à ses kk plus proches voisins : plus les voisins sont proches, plus la densité est forte. Le LOF d’un point est le rapport entre la densité moyenne de ses voisins et sa propre densité.

  • LOF proche de 1 : le point est aussi dense que son voisinage, il est normal.
  • LOF nettement supérieur à 1 : le point est beaucoup moins dense que ses voisins, il est anormal localement.

Pourquoi « local » ? Imaginez deux groupes de diplômés dans le plan (GPA, salaire) : un groupe très serré d’ingénieurs logiciels autour de 90 k$, et un groupe plus dispersé de diplômés en lettres autour de 45 k$. Un ingénieur à 70 k$ est à distance modeste de son groupe, mais ce groupe est si serré que, relativement, il est très isolé. Une règle fondée sur la distance globale ne le verrait pas, car les littéraires sont souvent plus loin de leurs voisins que lui. Le LOF le repère, car il compare chaque point à son propre voisinage.

2,252,502,753,003,253,503,754,00GPA2030405060708090salaire (k$)ingénieur à 70 k$ : LOF ≈ 3,2,classé 1ᵉʳ sur 201taille des points : LOFingénieurs logiciels (serrés)lettres (dispersés)
Les données de l'exercice 3 : l'ingénieur à 70 k$ n'est pas plus loin de ses voisins que bien des littéraires, mais son groupe est si serré qu'il y est très isolé. Le LOF, qui compare chaque point à la densité de son voisinage, le classe premier.
import numpy as np
from sklearn.ensemble import IsolationForest
from sklearn.neighbors import LocalOutlierFactor
from sklearn.preprocessing import StandardScaler
# X : une ligne par diplômé, colonnes GPA et salaire (en k$)
X = np.column_stack([gpa, salaire])
# Isolation Forest : pas besoin de standardiser
iso = IsolationForest(n_estimators=300, contamination="auto", random_state=0).fit(X)
score_iso = -iso.score_samples(X) # plus c'est grand, plus c'est anormal
# LOF : fondé sur des distances, il faut standardiser
Xs = StandardScaler().fit_transform(X)
lof = LocalOutlierFactor(n_neighbors=20)
etiquettes = lof.fit_predict(Xs) # -1 pour les anomalies, 1 sinon
score_lof = -lof.negative_outlier_factor_ # le LOF lui-même (proche de 1 : normal)
# Les 10 cas les plus suspects selon chaque méthode, à montrer à un expert
print(np.argsort(score_iso)[::-1][:10])
print(np.argsort(score_lof)[::-1][:10])
MéthodeType d’anomalie viséStandardisationPoints fortsLimites
z-scoreponctuelle, univariéesans objetsimpleeffet de masque, suppose une loi normale
Médiane et MAD, IQRponctuelle, univariéesans objetrobustesune variable à la fois
Isolation Forestglobale, multivariéeinutilerapide, grands volumesvoit mal les anomalies locales
LOFlocale, multivariéeindispensabledensités variablescoûteux, sensible à kk

Les méthodes de partitionnement comme DBSCAN, qui étiquettent comme « bruit » les points hors des zones denses, peuvent aussi servir de détecteurs. Elles sont présentées dans le cours d’Analyse et fouille de données, avec k-means et le partitionnement hiérarchique.

Voici le point délicat. Sans étiquettes, impossible de construire une matrice de confusion comme au chapitre 6. Comment savoir si le détecteur fonctionne ? Quelques pratiques :

  1. Faire valider par un expert. On trie les observations par score décroissant et l’on montre les 20 ou 50 premières à quelqu’un qui connaît le domaine. La proportion de vraies anomalies parmi elles, la précision dans les kk premiers (precision at k), est souvent la seule mesure disponible, et c’est la plus utile : c’est elle qui dit si l’équipe qui vérifie les alertes perd son temps.
  2. Utiliser les quelques étiquettes existantes. Si l’on connaît une poignée de fraudes avérées, on vérifie qu’elles obtiennent des scores élevés (en regardant leur rang, ou l’aire sous la courbe précision-rappel, avec la prévalence comme référence du hasard).
  3. Injecter des anomalies connues. On ajoute quelques erreurs synthétiques (un salaire multiplié par 10) et l’on vérifie qu’elles remontent en tête.
  4. Comparer les méthodes entre elles. Des cas signalés à la fois par Isolation Forest et par LOF sont de bons candidats ; des désaccords massifs invitent à creuser.
  • Une anomalie peut être une erreur, un cas rare réel ou une nouveauté ; elle peut être ponctuelle, contextuelle ou collective. On la signale, on ne la supprime pas automatiquement.
  • Le z-score souffre de l’effet de masque et ne peut pas dépasser (n−1)/n(n - 1)/\sqrt{n} : avec 10 valeurs, la règle ∣z∣>3\lvert z \rvert > 3 ne détecte rien.
  • Les règles robustes (médiane et MAD, écart interquartile avec les bornes Q1−1,5 IQRQ_1 - 1{,}5\,IQR et Q3+1,5 IQRQ_3 + 1{,}5\,IQR) résistent aux valeurs extrêmes.
  • Isolation Forest repère les points qui s’isolent en peu de coupes aléatoires (score proche de 1) ; il est rapide et n’exige pas de standardisation.
  • LOF compare la densité d’un point à celle de ses voisins ; il détecte les anomalies locales mais demande de standardiser et de choisir kk.
  • Sans étiquettes, on évalue par validation experte des cas les mieux classés (précision dans les kk premiers), par quelques cas connus ou par des anomalies injectées.

Exercice · Appliquer la règle de l'écart interquartile

facile

Voici dix GPA déclarés : 3,1 ; 3,3 ; 3,4 ; 3,5 ; 3,6 ; 3,6 ; 3,7 ; 3,8 ; 3,9 ; 0,4. Avec la méthode d’interpolation de NumPy, on trouve Q1=3,325Q_1 = 3{,}325 et Q3=3,675Q_3 = 3{,}675. Appliquez la règle de l’écart interquartile. La valeur signalée est-elle forcément une erreur ?

Voir la solution

IQR=3,675−3,325=0,35IQR = 3{,}675 - 3{,}325 = 0{,}35, donc 1,5×IQR=0,5251{,}5 \times IQR = 0{,}525. Les bornes sont 3,325−0,525=2,83{,}325 - 0{,}525 = 2{,}8 et 3,675+0,525=4,23{,}675 + 0{,}525 = 4{,}2. Seule la valeur 0,4 est hors de l’intervalle.

Ce n’est pas forcément une erreur : un GPA de 0,4 est possible (un étudiant qui a presque tout échoué), même s’il serait étonnant chez un diplômé. L’hypothèse la plus probable est une faute de frappe pour 3,4, mais seule une vérification à la source (le relevé de notes) permet de trancher. Remarquez qu’ici le z-score classique vaut environ −2,77-2{,}77 : il ne signalerait rien.

En code

import numpy as np
gpa = np.array([3.1, 3.3, 3.4, 3.5, 3.6, 3.6, 3.7, 3.8, 3.9, 0.4])
q1, q3 = np.percentile(gpa, [25, 75]) # interpolation linéaire par défaut
iqr = q3 - q1
bas, haut = q1 - 1.5 * iqr, q3 + 1.5 * iqr
print(round(q1, 3), round(q3, 3), round(bas, 3), round(haut, 3)) # 3.325 3.675 2.8 4.2
print(gpa[(gpa < bas) | (gpa > haut)]) # [0.4]
# Le z-score classique ne signale rien
z = (gpa - gpa.mean()) / gpa.std(ddof=1)
print(round(z[-1], 2)) # -2.77

Exercice · La borne du z-score

moyen
  1. Calculez la valeur maximale possible de ∣z∣\lvert z \rvert (avec l’écart-type d’échantillon) pour n=5n = 5, 1010, 2020 et 100100 valeurs.
  2. À partir de quelle taille d’échantillon la règle ∣z∣>3\lvert z \rvert > 3 peut-elle, au moins en théorie, signaler quelque chose ?
  3. Pourquoi, même au-delà de cette taille, la règle reste-t-elle fragile ?
Voir la solution
  1. La borne vaut (n−1)/n(n - 1)/\sqrt{n} : environ 1,791{,}79 pour n=5n = 5, 2,852{,}85 pour n=10n = 10, 4,254{,}25 pour n=20n = 20 et 9,99{,}9 pour n=100n = 100.
  2. Il faut (n−1)/n>3(n - 1)/\sqrt{n} > 3. Pour n=10n = 10, on a 2,852{,}85 ; pour n=11n = 11, 10/11≈3,0210/\sqrt{11} \approx 3{,}02. La règle ne peut donc rien signaler en dessous de 11 valeurs.
  3. La borne n’est atteinte que dans le cas extrême d’une seule valeur isolée face à des valeurs toutes identiques. En pratique, la valeur aberrante gonfle toujours l’écart-type (effet de masque), et s’il y a plusieurs valeurs aberrantes, elles se masquent mutuellement. De plus, le seuil 3 suppose des données à peu près normales, ce que les salaires (asymétriques) ne sont pas. D’où l’intérêt des versions robustes.

En code

import numpy as np
borne = lambda n: (n - 1) / np.sqrt(n) # |z| maximal possible
print([round(float(borne(n)), 2) for n in (5, 10, 20, 100)]) # [1.79, 2.85, 4.25, 9.9]
print(next(n for n in range(2, 100) if borne(n) > 3)) # 11
# La borne est atteinte : une valeur isolée face à n - 1 valeurs identiques
x = np.array([0.0] * 9 + [1000.0])
print(round(abs((x[-1] - x.mean()) / x.std(ddof=1)), 2)) # 2.85, jamais plus de 3
# Effet de masque : deux salaires aberrants parmi 20 (borne 4,25)
x = np.r_[np.arange(50, 68), 650, 700]
print(np.round((x - x.mean()) / x.std(ddof=1), 2)[-2:]) # [2.79 3.05]

Exercice · Choisir une méthode

difficile

Pour chaque situation, proposez une méthode de détection et une façon d’évaluer le résultat.

  1. Vérifier, avant toute modélisation, les 600 salaires déclarés d’une enquête.
  2. Repérer, parmi 2 millions de transactions bancaires décrites par 15 variables numériques, les plus suspectes, sachant qu’une équipe peut en vérifier 200 par jour.
  3. Repérer, dans le plan (GPA, salaire), les diplômés atypiques au sein de leur filière, sachant que les filières ont des niveaux et des dispersions de salaire très différents.
Voir la solution
  1. Une variable, un volume modeste : une règle robuste (médiane et MAD, ou écart interquartile). On examine à la main chaque valeur signalée, en revenant si possible au questionnaire d’origine. Une boîte à moustaches par filière aide aussi à repérer les valeurs contextuelles.
  2. Gros volume, plusieurs variables, pas de notion de voisinage évidente : Isolation Forest, rapide et sans standardisation. On classe les transactions par score et l’on transmet chaque jour les 200 premières. L’évaluation naturelle est la précision dans les 200 premiers (combien de fraudes réelles l’équipe confirme), complétée par le rang des fraudes déjà connues.
  3. Densités très différentes d’une filière à l’autre : c’est le cas d’école du LOF, après standardisation, avec un kk assez grand pour couvrir le voisinage d’un diplômé dans sa filière (ou, plus simplement, un z-score robuste calculé filière par filière). On fait valider les cas signalés par le service carrières, qui connaît les métiers et les salaires de chaque filière.

En code

import numpy as np, pandas as pd
from sklearn.neighbors import LocalOutlierFactor
from sklearn.preprocessing import StandardScaler
rng = np.random.default_rng(0)
df = pd.concat([
pd.DataFrame({"filiere": "info", "gpa": rng.normal(3.5, 0.2, 100), "salaire": rng.normal(90, 2, 100)}),
pd.DataFrame({"filiere": "lettres", "gpa": rng.normal(3.2, 0.3, 100), "salaire": rng.normal(45, 8, 100)}),
pd.DataFrame({"filiere": ["info"], "gpa": [3.6], "salaire": [70.0]}), # le cas atypique
], ignore_index=True)
def z_robuste(s):
return 0.6745 * (s - s.median()) / (s - s.median()).abs().median()
# z robuste global : le cas atypique (dernière ligne) passe inaperçu
print(round(z_robuste(df["salaire"]).iloc[-1], 2)) # 0.0
# z robuste filière par filière : il est signalé
print(round(df.groupby("filiere")["salaire"].transform(z_robuste).iloc[-1], 1)) # -10.7
# LOF sur (GPA, salaire) standardisés : rang du cas atypique parmi 201 diplômés
lof = LocalOutlierFactor(n_neighbors=20).fit(StandardScaler().fit_transform(df[["gpa", "salaire"]]))
score = -lof.negative_outlier_factor_
print(round(score[-1], 1), int((score > score[-1]).sum()) + 1) # LOF 3.2, classé 1er