Local Outlier Factor

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

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

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

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