Facteur d'Anomalie Locale (LOF)
- Introduite par
- Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J.
- Année
- 2000
- Type
- Density-based anomaly detection (unsupervised)
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
Le Facteur d'Abnormality Locale (LOF) est un algorithme de détection d'anomalies non supervisé, basé sur la densité, introduit par Breunig, Kriegel, Ng et Sander en 2000.
Il attribue à chaque point de données un score d'abnormality continu qui quantifie à quel point ce point est isolé par rapport à son voisinage local, permettant la détection d'anomalies que les méthodes globales manquent parce qu'elles se fondent dans des grappes denses ailleurs dans l'espace.
L’intuition derrière la méthode
Imaginez un plan de ville où la plupart des gens vivent dans des quartiers urbains denses. Une maison isolée à la campagne est manifestement isolée. Mais le LOF va plus loin : il peut aussi signaler une maison située dans une banlieue modérément dense alors que tous ses voisins immédiats sont regroupés dans un cluster encore plus dense. Au lieu de demander « ce point est-il loin de tout ? », le LOF demande « le voisinage de ce point est-il beaucoup plus clairsemé que les voisinages de ses propres voisins ? » Un point dont les voisins sont tous plus étroitement regroupés que le point lui-même obtient un score LOF élevé — signalant qu'il s'agit d'un outlier local même si globalement il ne se trouve pas dans une région vide.
Histoire
Le LOF a été introduit par Markus Breunig, Hans-Peter Kriegel, Raymond Ng et Jörg Sander lors de la conférence ACM SIGMOD 2000. Il a abordé une limitation reconnue des méthodes d'outlier existantes — à savoir qu'elles reposaient sur des seuils de distance globaux et confondaient donc les anomalies locales avec des points normaux dans des régions moins denses. L'article a introduit le concept de densité d'accessibilité locale et le score LOF, qui est rapidement devenu une référence fondamentale en détection d'anomalies. Il a depuis été étendu par de nombreuses variantes, y compris LoOP (local outlier probabilities), LOCI et COF, et est inclus dans les principales bibliothèques d'apprentissage automatique. L'article ACM SIGMOD 2000 a accumulé des milliers de citations et est considéré comme l'un des travaux fondateurs de l'exploration de données basée sur la densité.
Quand l’utiliser
Le LOF est approprié lorsque des anomalies sont attendues dans des grappes de densité variable et lorsqu'un seuil de distance global manquerait des outliers cachés dans des régions clairsemées ou signalerait incorrectement des points dans des grappes légitimement clairsemées mais cohérentes. Il fonctionne sur tout espace de caractéristiques continu avec une métrique de distance significative et ne nécessite pas d'exemples d'anomalies étiquetées (entièrement non supervisé). Il convient aux applications telles que la détection de fraude, la détection d'intrusion réseau, le contrôle qualité de fabrication et le dépistage d'anomalies médicales. Les principales hypothèses sont que les inliers forment des voisinages locaux raisonnablement cohérents et que des distances par paires significatives peuvent être calculées. Le LOF est plus performant lorsque n est au moins de l'ordre de quelques dizaines à quelques centaines ; pour des données de très haute dimension (la malédiction de la dimensionnalité), les distances deviennent moins discriminantes et une réduction de dimensionnalité ou une sélection de caractéristiques est d'abord conseillée.
Limites et points d’attention
- La complexité temporelle quadratique dans l'implémentation naïve le rend lent sur de grands ensembles de données sans indexation approximative des plus proches voisins.
- Sensible au choix de k : un k trop petit produit des scores bruyants ; un k trop grand estompe la structure locale.
- Les performances se dégradent dans les espaces de très haute dimension en raison de la malédiction de la dimensionnalité.
- Ne s'adapte pas naturellement aux données en flux ou en ligne sans recalcul.
- Ne fournit pas de modèle pouvant être directement appliqué pour évaluer de nouveaux points sans accès à l'ensemble d'entraînement.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Détecte les outliers locaux dans des ensembles de données avec des grappes de densité variable, là où les méthodes globales échouent.
- Produit un score continu et interprétable plutôt qu'une étiquette binaire stricte, permettant un choix de seuil flexible.
- Entièrement non supervisé : aucune donnée d'anomalie étiquetée n'est requise.
- Applicable à tout espace de caractéristiques avec une métrique de distance calculable, y compris les distances non euclidiennes.
- Robuste à l'échelle des caractéristiques individuelles lorsque les distances sont calculées sur des données standardisées.
Applications
- Détection de fraude dans les transactions financières où l'activité frauduleuse crée des motifs localement clairsemés.
- Détection d'intrusion réseau en signalant les enregistrements de trafic dont le voisinage local est beaucoup plus clairsemé que son environnement.
- Contrôle qualité de fabrication pour identifier les articles défectueux dans les données de production riches en capteurs.
- Dépistage d'anomalies médicales — détection de profils de patients inhabituels par rapport à des cohortes de patients similaires.
- Détection d'anomalies spatiales dans les données géographiques et environnementales à densité hétérogène.
Comment ça marche
Comment ça marche
Pour chaque point p, l'algorithme calcule d'abord la k-distance : la distance jusqu'au k-ième plus proche voisin de p. Cela définit la portée du voisinage local de p. Tous les points situés à cette distance forment le k-voisinage N_k(p). Le choix de k contrôle l'échelle à laquelle la localité est évaluée — un petit k capture une structure locale fine, un k plus grand la lisse.
Formule
k\text{-dist}(p) = \text{distance to the } k\text{-th nearest neighbor of } pLa distance d'accessibilité (reachability distance) de p à un voisin o est définie comme le maximum de la k-distance de o et de la distance euclidienne (ou autre métrique) réelle entre p et o. Ce lissage prévient l'instabilité lorsque deux points sont extrêmement proches : il remplace les petites distances par l'empreinte plus large du propre voisinage de o, rendant les estimations de densité plus robustes.
Formule
\text{reach-dist}_k(p, o) = \max\{k\text{-dist}(o),\, d(p, o)\}La densité d'accessibilité locale de p (lrd) est l'inverse de la distance d'accessibilité moyenne de p à tous ses k voisins. Un point entouré de voisins très proches a une petite distance d'accessibilité moyenne, et donc une lrd élevée. Un point dans une région clairsemée a une grande distance d'accessibilité moyenne et une faible lrd.
Formule
\text{lrd}_k(p) = \left(\frac{\sum_{o \in N_k(p)} \text{reach-dist}_k(p,o)}{|N_k(p)|}\right)^{-1}Le score LOF de p est le rapport moyen des valeurs lrd de ses voisins à la propre lrd de p. Si les voisins de p ont tous une lrd substantiellement plus élevée que p lui-même — ce qui signifie qu'ils vivent dans des sous-régions plus denses — le rapport dépasse 1, indiquant que p est un outlier local. Un score proche de 1 indique que p a à peu près la même densité que son environnement. Des scores bien supérieurs à 1 signalent des points de plus en plus anormaux. Cette comparaison sensible à la localité est ce qui distingue le LOF des méthodes basées uniquement sur la distance.
Formule
\text{LOF}_k(p) = \frac{\sum_{o \in N_k(p)} \frac{\text{lrd}_k(o)}{\text{lrd}_k(p)}}{|N_k(p)|}Pièges courants
- Oublier de standardiser ou de normaliser les caractéristiques avant de calculer les distances, ce qui fait que les caractéristiques à forte variance dominent.
- Utiliser une seule valeur de k sans analyse de sensibilité ; la meilleure pratique est d'évaluer plusieurs valeurs de k.
- Traiter le score LOF comme une probabilité — c'est une mesure relative sans interprétation probabiliste fixe.
- Ignorer la malédiction de la dimensionnalité dans les données de haute dimension et s'attendre à ce que le LOF fonctionne sans réduction de dimensionnalité préalable.
- Définir un seuil LOF arbitraire (par exemple, score > 1,5) sans inspecter la distribution des scores pour l'ensemble de données spécifique.
Questions fréquentes
Comment choisir la bonne valeur de k ?
Il n'y a pas de k universellement optimal. La pratique courante consiste à évaluer une gamme de valeurs — généralement de 5 à 50 — et à examiner comment la distribution des scores et les outliers signalés changent. Une analyse de sensibilité sur les valeurs de k donne confiance dans la robustesse des anomalies détectées au choix. La connaissance du domaine concernant la taille minimale attendue des grappes peut également guider la borne inférieure.
Que signifie un score LOF de 1 par rapport à 3 ?
Un score proche de 1 signifie que le point a à peu près la même densité locale que ses voisins et est considéré comme un inlier. Un score significativement supérieur à 1 — souvent interprété comme supérieur à 1,5 ou 2 selon l'ensemble de données — indique que le voisinage du point est beaucoup plus clairsemé que les voisinages de ses voisins. Il n'y a pas de seuil universel ; le seuil doit être choisi en inspectant la distribution des scores LOF pour l'ensemble de données spécifique.
Le LOF peut-il évaluer de nouveaux points, non vus, sans réentraînement ?
Le LOF est une méthode transductive : il nécessite que l'ensemble d'entraînement soit présent pour calculer les voisinages et les densités de tout nouveau point. Pour évaluer de nouvelles observations, l'ensemble d'entraînement doit être conservé et chaque nouveau point doit être inséré pour recalculer son k-voisinage par rapport aux points d'entraînement stockés. Certaines implémentations offrent cette fonctionnalité, mais elle diffère fondamentalement des modèles paramétriques qui apprennent une fonction de score compacte.
Comment le LOF se compare-t-il à Isolation Forest pour la détection d'anomalies ?
Le LOF utilise l'estimation de densité basée sur les voisinages locaux et est plus efficace lorsque les anomalies se regroupent dans des régions localement clairsemées d'un espace hétérogène. Isolation Forest utilise le partitionnement aléatoire et a tendance à être plus rapide et plus évolutif pour les grands ensembles de données. Pour les ensembles de données de haute dimension ou très grands, Isolation Forest est souvent préféré ; pour les données de dimension modérée avec une variation de densité, le LOF offre fréquemment une discrimination plus fine.
Méthodes associées
Sources
Breunig, M. M., Kriegel, H.-P., Ng, R. T., & Sander, J. (2000). LOF: Identifying density-based local outliers. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 93–104.
Ouvrir la référence DOICopié.Aggarwal, C. C. (2017). Outlier Analysis (2nd ed., Ch. 4). Springer.
ISBN : 978-3-319-47577-6Copié.Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 14). Springer.
ISBN : 978-0-387-84857-0Copié.