Local Outlier Factor
Ricco Rakotomalala
Université Lumière Lyon 2
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
1
Plan
1. Problématique
2. Local Outlier Factor
3. Un exemple
4. Conclusion
5. Références
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
2
Quelques définitions - Problématique
DÉTECTION DES ANOMALIES
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
3
Anomalie ?
2 formes d’anomalies à identifier dans les données
Détection des points atypiques (outlier detection) : un ou des points s’écartent
significativement des autres dans une base de données. Ils sont épars et localisés
dans une zone peu dense des données (s’ils forment un groupe compact, on ne
peut pas vraiment parler d’anomalies)
Détection des nouveautés (novelty detection) : on situe un individu
supplémentaire par rapport à un échantillon de référence (considéré « propre »),
on cherche à savoir s’il peut y être associé ou s’il s’en écarte significativement
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
4
Approche simple – Distance de Mahalanobis
Pour chaque point, calculer la distance par rapport au barycentre (μ)
– qui sert de référence – en tenant compte de la forme du nuage de
points (via la covariance Σ).
2
𝑑 𝜇,Σ
𝑥𝑖 = 𝑥𝑖 − 𝜇 ′Σ−1 𝑥𝑖 − 𝜇
μ
•
Le point rouge n’est pas atypique sur les
deux axes pris individuellement, mais l’est
par rapport à la forme du nuage de points
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
5
-2-10123-2-1012Problème distance de Mahalanobis
Les calculs de μ et Σ peuvent être affectés par les points
atypiques (Remarque : des solutions robustes existent…
ex. « Minimum Covariance Determinant estimator »,
Rousseuw, 1984)
Les données peuvent être non-gaussiens, ou
clustérisées, le barycentre global ne veut plus rien dire.
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
6
-2-10123-2-1012-2-10123-2-1012Identification locale des points atypiques
•
•
Dans une zone à forte densité, un
point qui s’écarte des autres (de
ses voisins immédiats) devrait
plus interroger que lorsqu’il se
situe dans une zone moins dense.
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
7
-2-10123-2-1012Calcul de densité locale basée sur les k-plus proches voisins
LOCAL OUTLIER FACTOR
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
8
Principe du Local Outlier Factor (LOF)
Publicité
Comparer la densité locale d’un point avec celles de ses k (paramètre)
plus proches voisins : si elle est inférieure, suspicion de point atypique
Exemple (k = 2)
𝑙𝑟𝑑 6 ≪ 𝑙𝑟𝑑 4
𝑙𝑟𝑑 6 ≪ 𝑙𝑟𝑑 2
lrd(4)=5.61
lrd(2)=5.43
lrd(6)=2.45
Le point n°6 est potentiellement atypique
𝑙𝑜𝑓 6 = 2.2459 … ≫ 1
lrd (local reachability density) : mesure de densité locale d’un point (
Valeur de référence
fortement entouré, densité élevée ; faiblement entouré, densité faible)
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
9
0.30.40.50.60.70.80.20.30.40.5V1V2123456Quelques définitions et calculs
Distance euclidienne entre paires de points :
𝑝
𝑑2 𝑖, 𝑖′ =
𝑗=1
𝑥𝑖,𝑗 − 𝑥𝑖′,𝑗
2
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
1 2 3 4 5 6
1 0.000 0.210 0.161 0.158 0.130 0.533
2 0.210 0.000 0.198 0.170 0.332 0.439
3 0.161 0.198 0.000 0.270 0.276 0.620
4 0.158 0.170 0.270 0.000 0.225 0.374
5 0.130 0.332 0.276 0.225 0.000 0.573
6 0.533 0.439 0.620 0.374 0.573 0.000
k-distance(A) : distance d’un objet A avec
son kème voisin. Ex. 2-distance(6) = 0.439
Nk(A) : taille du voisinage d’ordre k de A. Attention, à
cause des ex-aequo, Nk(A) ≥ k
Distance atteignable (reachability distance) entre 2
objets : rdk(A,B) = max{k-distance(B), d(A,B)}
c.-à-d. Les points inclus dans le « rayon d’influence »
d’ordre k de B sont considérés équivalents
Ex. 2-distance(4) = 0.170 → rd2(1,4) = max{0.170, 0.158) = 0.170
Ex. rd2(6,4) = max{0.170,0.374} = 0.374
rdk(. , .) n’est pas symétrique !
10
0.30.40.50.60.70.80.20.30.40.5V1V2123456Quelques définitions et calculs (suite)
La densité locale (lrd : local reachability density) d’un
point est l’inverse de la moyenne de son rdk(., .) avec
ses k-plus proches voisins
𝑙𝑟𝑑𝑘(𝐴) =
1
σ𝐵∈𝑁𝑘(𝐴) 𝑟𝑑𝑘(𝐴, 𝐵)
𝑁𝑘(𝐴)
|Nk(A)| cardinal du k-voisinage de A ( = k si pas d’ex-aequo)
k-d(4)=0.170
0.374
0.439
k-d(2)=0.198
rd2(6,4) = max {0.170, 0.374} = 0.374
rd2(6,2) = max {0.198, 0.439} = 0.439
𝑙𝑟𝑑2 6 =
1
0.374 + 0.439
2
= 2.457756
lrd2(1) = 5.071 ; lrd2(2) = 5.432 ;
lrd2(3) = 5.560 ; lrd2(4) = 5.608 ;
lrd2(5) = 5.224 ; lrd2(6) = 2.458
On distingue les zones à forte densité !
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
11
0.30.40.50.60.70.80.20.30.40.5V1V2123456lrd2(.)
5.224
5.071
Publicité
5.608
5.560
2.458
5.432
Le facteur local d’anomalie (lof : local outlier factor)
d’un point est obtenu en opposant sa densité locale
avec celles de ses k-plus proches voisins
𝑙𝑜𝑓𝑘(𝐴) =
σ𝐵∈𝑁𝑘(𝐴)
𝑙𝑟𝑑𝑘(𝐵)
𝑙𝑟𝑑𝑘(𝐴)
𝑁𝑘(𝐴)
Exemple.
𝑙𝑜𝑓2 6 =
5.608
2.458
+
2
5.432
2.458
= 2.246
lof2(.)
1.022
Règle de décision :
1.068
LOF 1, densité similaire à ses voisins
LOF < 1, densité plus élevée que ses voisins (inlier)
0.936
0.945
LOF > 1, densité moindre que ses voisins (outlier)
2.246
1.028
Le mieux toujours est de trier les données pour
identifier les observations suspectes (LOF très élevé) !
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
12
0.30.40.50.60.70.80.20.30.40.5V1V21234560.30.40.50.60.70.80.20.30.40.5V1V2123456LOF – Avantages et inconvénients
Non dépendant au calcul toujours hasardeux d’un barycentre
Approche locale, applicable même si les données sont organisées en clusters
Tient compte de la densité des points
Généralisable à d’autres mesures de distance (autre que euclidienne…)
Peut travailler directement à partir d’une matrice de distance
Interprétation du LOF difficile
Valeur seuil de 1 discutable, mieux vaut identifier les décrochements
Complexité des calculs, il faut une approche efficace de recherche des voisins
Comment fixer la valeur du paramètre k ?
•
•
k faible, plus précis mais instabilité des résultats
k fort, plus lissé mais risque de masquer les informations locales…
+
-
?
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
13
Identification des véhicules atypiques
UN EXEMPLE
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
14
Un ensemble de véhicules
Comment identifier des
véhicules atypiques – dont les
caractéristiques se
démarquent significativement
des autres – dans cette base ?
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
15
ModelePrixCylindreePuissancePoidsConsoDaihatsu Cuore11600846326505.7Suzuki Swift 1.0 GLS12490993397905.8Fiat Panda Mambo L10450899297306.1VW Polo 1.4 60171401390449556.5Opel Corsa 1.2i Eco148251195338956.8Subaru Vivio 4WD13730658327406.8Toyota Corolla1949013315510107.1Ferrari 456 GT2850005474325169021.3Mercedes S 6001839005987300225018.7Maserati Ghibli GT925002789209148514.5Opel Astra 1.6i 16V2500015977410807.4Peugeot 306 XS 1082235017617411009Renault Safrane 2.2. V366002165101150011.7Seat Ibiza 2.0 GTI2250019838510759.5VW Golt 2.0 GTI3158019848511559.5Citroen ZX Volcane2875019988911408.8Fiat Tempra 1.6 Liberty2260015806510809.3Fort Escort 1.4i PT2030013905411108.6Honda Civic Joker 1.41990013966611407.7Volvo 850 2.5398002435106137010.8Ford Fiesta 1.2 Zetec197401242559406.6Hyundai Sonata 3000389902972107140011.7Lancia K 3.0 LS508002958150155011.9Mazda Hachtback V362002497122133010.8Mitsubishi Galant3199019986613007.6Opel Omega 2.5i V6477002496125167011.3Peugeot 806 2.036950199889156010.8Nissan Primera 2.02695019979212409.2Seat Alhambra 2.036400198485163511.6Toyota Previa salon50900243897180012.8Volvo 960 Kombi aut493002473125157012.7Calculs sous R (1)
Les 3 premières on comprend,
la Mitshubishi je doute, les
Publicité
autres (lof>1) pas bon.
#chargement du fichier
library(xlsx)
cars <- read.xlsx("cars_outliers.xlsx",header=TRUE,sheetIndex=1)
rownames(cars) <- cars$Modele
cars <- cars[-1]
print(str(cars))
#standardisation des données - important
Z1 <- scale(cars,center=TRUE,scale=TRUE)
print(Z1)
#identification des outliers
library(Rlof)
atyp <- Rlof::lof(Z1,k=3)
names(atyp) <- rownames(cars)
lof <- sort(atyp,decreasing=TRUE)
print(lof)
#décroissance du lof
plot(lof,type="b",pch=16,cex=0.5)
abline(a=1,b=0,col='gray')
text(3,lof[1],names(lof)[1],cex=0.75,col='red')
text(4.5,lof[2],names(lof)[2],cex=0.75,col='red')
text(5.5,lof[3],names(lof)[3],cex=0.75,col='red')
text(6.5,lof[4],names(lof)[4],cex=0.75,col='red')
Ferrari 456 GT Mercedes S 600 Maserati Ghibli GT
4.0367621 3.8476903 2.2698694
Mitsubishi Galant Fiat Tempra 1.6 Liberty Opel Astra 1.6i 16V
1.7300548
1.1390725 1.1264925
Fiat Panda Mambo L Fort Escort 1.4i PT VW Polo 1.4 60
1.1188335 1.0924104 1.0848137
Honda Civic Joker 1.4 Toyota Previa salon VW Golt 2.0 GTI
1.0749252 1.0735969 1.0650363
Nissan Primera 2.0 Citroen ZX Volcane
Peugeot 306 XS 108
1.0486296 1.0377882 1.0294415
Renault Safrane 2.2. V Ford Fiesta 1.2 Zetec
Opel Omega 2.5i V6
1.0182159 1.0176061 1.0126277
Lancia K 3.0 LS Hyundai Sonata 3000 Mazda Hachtback V
1.0051918 1.0022382 1.0022382
Volvo 960 Kombi aut
Peugeot 806 2.0 Volvo 850 2.5
1.0018507 0.9979525 0.9820399
Daihatsu Cuore
Suzuki Swift 1.0 GLS Subaru Vivio 4WD
0.9710589 0.9613885 0.9613885
Seat Alhambra 2.0 Opel Corsa 1.2i Eco Toyota Corolla
0.9582223 0.9300970 0.9102498
Seat Ibiza 2.0 GTI
0.8616536
La valeur seuil 1 n’est pas
adaptée, clairement.
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
Le « coude » interpelle, forcément…
16
0510152025301.01.52.02.53.03.54.0IndexlofFerrari 456 GTMercedes S 600Maserati Ghibli GTMitsubishi GalantCalculs sous R (2)
L’analyse est confirmée
#analyse en composantes principales
acp <- princomp(cars,cor=TRUE,scores=TRUE)
#4 points atypiques : lof > 1.5
iza <- (atyp>1.5)
print(iza)
#projection dans le plan factoriel
plot(acp$scores[,1],acp$scores[,2],
xlim=c(-3,8),ylim=c(-3,8), xlab='Comp.1’,
ylab='Comp.2',asp=1)
text(acp$scores[iza,1],acp$scores[iza,2],
rownames(cars)[iza],col='red',cex=0.75)
Reste un mystère à éclaircir (faux positif ?)
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
17
-4-202468-202468Comp.1Comp.2Ferrari 456 GTMercedes S 600Maserati Ghibli GTMitsubishi GalantMitsubishi Galant VW Polo 1.4 60 Volvo 960 Kombi aut
Publicité
Opel Omega 2.5i V6
1.5256643
1.1131063 1.0861770 1.0723752
Peugeot 306 XS 108 Renault Safrane 2.2. V Fiat Panda Mambo L Opel Astra 1.6i 16V
1.0636407 1.0557054 1.0494570 1.0479916
Honda Civic Joker 1.4 Fiat Tempra 1.6 Liberty Citroen ZX Volcane Hyundai Sonata 3000
1.0465680 1.0382405 1.0207959 1.0153769
Mazda Hachtback V Fort Escort 1.4i PT Lancia K 3.0 LS Toyota Previa salon
1.0153769 1.0053759 1.0029175 0.9971779
Opel Corsa 1.2i Eco Suzuki Swift 1.0 GLS VW Golt 2.0 GTI Nissan Primera 2.0
0.9906934 0.9902857 0.9894906 0.9894906
Daihatsu Cuore
Peugeot 806 2.0 Seat Alhambra 2.0 Subaru Vivio 4WD
0.9863229 0.9857968 0.9857968 0.9658605
Seat Ibiza 2.0 GTI Volvo 850 2.5 Ford Fiesta 1.2 Zetec
Toyota Corolla
0.9588196 0.9470005 0.9456732 0.9244434
Calculs sous R (3)
Mitsubishi
suspecte encore…
#refaire l'analyse sans les 3 atypiques
#(Mercedes, Ferrari, Maserati)
carsbis <- cars[atyp < 2.0,]
#centrage-réduction
Z2 <- scale(carsbis,center=TRUE,scale=TRUE)
#identification
atyp2 <- Rlof::lof(Z2,k=3)
names(atyp2) <- rownames(carsbis)
lof2 <- sort(atyp2,decreasing=TRUE)
print(lof2)
#graphique
plot(lof2,type="b",pch=16,cex=0.5)
abline(a=1,b=0,col='gray')
Artefact : (k=3) le fait apparaître comme isolé au milieu d’une zone
à forte densité (ses 3 plus proches voisins ont des voisins proches).
Quand on augmente k (k ≥ 5), ce phénomène disparaît.
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
18
05101520251.01.11.21.31.41.5Indexlof2-2024-3-2-10123Comp.1Comp.2Mitsubishi GalantCONCLUSION
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
19
Local Outlier Factor - Conclusion
•
La détection des anomalies a de nombreuses applications (identification des
observations qui appartiennent à une autre population, des situations exceptionnelles,
des comportements déviants [détection des intrusions par ex.], …)
•
LOF est une approche non-supervisée locale basée sur le différentiel de densité entre
les points d’un voisinage donné (nombre de voisins k est un paramètre)
•
« Anomaly détection » peut–être « outlier détection » (sur la base étudiée) ou
« novelty détection » (sur individus supplémentaires). LOF est applicable aussi en
« novelty détection ».
•
Le choix du paramètre (k) reste un problème ouvert…
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
20
RÉFÉRENCES
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
21
Références
• Wikipédia (en anglais) : « Outlier », « Anomaly detection », « Local outlier factor ».
• Documentation Scikit-learn 0.22, « Novelty and Outlier Detection », section 2.7.
• Breunig, Kriegel, Ng and Sander, « LOF: identifying density-based local outliers », Proc. of ACM
SIGMOD – Int. Conf. on Management of Data, pp. 93-104, 2000.
Ricco Rakotomalala
Tutoriels Tanagra - http://tutoriels-data-mining.blogspot.fr/
22