Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Data Mining TutorialOutlier Detection

Erich Schubert, Arthur Zimek

Ludwig-Maximilians-Universität München

2015-06-10 — KDD Übung

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Distanzbasierte Ausreißer

Distanzbasierte Ausreißer:“Ausreißer sind weiter weg von den anderen Daten”

I Distanz zum nächsten Nachbarn

⇒ übersieht Ausreißer-Paare

10 1

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Distanzbasierte Ausreißer

Distanzbasierte Ausreißer:“Ausreißer sind weiter weg von den anderen Daten”

I Distanz zum nächsten Nachbarn⇒ übersieht Ausreißer-Paare

1 1

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Distanzbasierte Ausreißer

Distanzbasierte Ausreißer:“Ausreißer sind weiter weg von den anderen Daten”

I Distanz zum k nächsten Nachbarn

⇒ Micro-Cluster (|C| < k + 1) werden Ausreißer

k = 2

10 1

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Distanzbasierte Ausreißer

Distanzbasierte Ausreißer:“Ausreißer sind weiter weg von den anderen Daten”

I Distanz zum k nächsten Nachbarn

⇒ Micro-Cluster (|C| < k + 1) werden Ausreißer

k = 2

1 1

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Distanzbasierte Ausreißer

Distanzbasierte Ausreißer:“Ausreißer sind weiter weg von den anderen Daten”

I Distanz zum k nächsten Nachbarn⇒ Micro-Cluster (|C| < k + 1) werden Ausreißer

k = 3

10 1

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Distanzbasierte Ausreißer

Distanzbasierte Ausreißer:“Ausreißer sind weiter weg von den anderen Daten”

I Summe der Distanzen zu den k nächsten NachbarnEtwas robuster bzgl. k und Micro-Clustern

k = 2

2 (1) 2 (1)

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Distanzbasierte Ausreißer

Distanzbasierte Ausreißer:“Ausreißer sind weiter weg von den anderen Daten”

I Summe der Distanzen zu den k nächsten Nachbarn

Etwas robuster bzgl. k und Micro-Clustern

k = 3

12 (4) 3 (1)

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Distanzbasierte Ausreißer

Distanzbasierte Ausreißer:“Ausreißer sind weiter weg von den anderen Daten”

I Summe der Distanzen zu den k nächsten Nachbarn⇒ Kann aber nicht gut mit unterschiedlichen Dichtenumgehen!

k = 4

8.5 10

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

Idee: Ein Ausreißer ist weniger dicht als seine Nachbarn

Dichteschätzung basierend auf den Ideen derClusteringalgorithmen OPTICS und DBSCAN:“Wann wäre ein Objekt p im minPts-Kern von o?”

reach-distk(p← o) = max{k-distance(o),dist(o, p)}

Lokale ErreichbarkeitsdichteVorsicht: Division durch 0 (aber nicht bei Ausreißern!)

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

Idee: Ein Ausreißer ist weniger dicht als seine NachbarnDichteschätzung basierend auf den Ideen derClusteringalgorithmen OPTICS und DBSCAN:“Wann wäre ein Objekt p im minPts-Kern von o?”

reach-distk(p← o) = max{k-distance(o),dist(o, p)}

Lokale ErreichbarkeitsdichteVorsicht: Division durch 0 (aber nicht bei Ausreißern!)

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

Idee: Ein Ausreißer ist weniger dicht als seine NachbarnDichteschätzung basierend auf den Ideen derClusteringalgorithmen OPTICS und DBSCAN:“Wann wäre ein Objekt p im minPts-Kern von o?”

reach-distk(p, o) = max{k-distance(o),dist(o, p)}

reach-distk(p← o) = max{k-distance(o),dist(o, p)}

Lokale ErreichbarkeitsdichteVorsicht: Division durch 0 (aber nicht bei Ausreißern!)

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

Idee: Ein Ausreißer ist weniger dicht als seine NachbarnDichteschätzung basierend auf den Ideen derClusteringalgorithmen OPTICS und DBSCAN:“Wann wäre ein Objekt p im minPts-Kern von o?”

reach-distk(p, o) = max{k-distance(o)︸ ︷︷ ︸kNN outlier!

,dist(o, p)}

reach-distk(p← o) = max{k-distance(o),dist(o, p)}

Lokale ErreichbarkeitsdichteVorsicht: Division durch 0 (aber nicht bei Ausreißern!)

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

Idee: Ein Ausreißer ist weniger dicht als seine NachbarnDichteschätzung basierend auf den Ideen derClusteringalgorithmen OPTICS und DBSCAN:“Wann wäre ein Objekt p im minPts-Kern von o?”

reach-distk(p← o) = max{k-distance(o),dist(o, p)}

Vorsicht: diese “Distanz” ist nicht symmetrisch!Sie hängt von der Kerngröße des anderen Objekts o ab.Ich bevorzuge die Notation “p erreichbar von o”:

reach-distk(p← o)

um das zu betonen.

Lokale ErreichbarkeitsdichteVorsicht: Division durch 0 (aber nicht bei Ausreißern!)

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

Idee: Ein Ausreißer ist weniger dicht als seine NachbarnDichteschätzung basierend auf den Ideen derClusteringalgorithmen OPTICS und DBSCAN:“Wann wäre ein Objekt p im minPts-Kern von o?”

reach-distk(p← o) = max{k-distance(o),dist(o, p)}

Lokale Erreichbarkeitsdichte

lrdk(p) = 1/(∑

o∈N reach-distk(p← o)|N |

)

Vorsicht: Division durch 0 (aber nicht bei Ausreißern!)

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

Idee: Ein Ausreißer ist weniger dicht als seine NachbarnDichteschätzung basierend auf den Ideen derClusteringalgorithmen OPTICS und DBSCAN:“Wann wäre ein Objekt p im minPts-Kern von o?”

reach-distk(p← o) = max{k-distance(o),dist(o, p)}

Lokale Erreichbarkeitsdichte

lrdk(p) = 1/( 1|N |

∑o∈N

reach-distk(p← o)

)

Vorsicht: Division durch 0 (aber nicht bei Ausreißern!)

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

Idee: Ein Ausreißer ist weniger dicht als seine NachbarnDichteschätzung basierend auf den Ideen derClusteringalgorithmen OPTICS und DBSCAN:“Wann wäre ein Objekt p im minPts-Kern von o?”

reach-distk(p← o) = max{k-distance(o),dist(o, p)}

Lokale Erreichbarkeitsdichte

lrdk(p) = 1/(︸︷︷ ︸

Kehrwert

1|N |

∑o∈N︸ ︷︷ ︸

mittlere

reach-distk(p← o)

)︸ ︷︷ ︸

Erreichbarkeit von den Nachbarn

Vorsicht: Division durch 0 (aber nicht bei Ausreißern!)

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

LOF(p) =

∑o∈N

lrdk(o)lrdk(p)

|N |

LOF(p) =1|N |

∑o∈N︸ ︷︷ ︸

Mittlere

lrdk(o)lrdk(p)︸ ︷︷ ︸

relative Dichte (der Nachbarn!)

I p gleich dicht⇔ relative Dichte = 1I p ähnlich dicht⇔ relative Dichte ≈ 1I p weniger dicht⇔ relative Dichte > 1I LOF(p)� 1 für Ausreißer!

Hinweis: Dichte im Sinne von OPTICS/DBSCAN!Die Erreichbarkeitsdistanz (lrd) wird oft übersehen!

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

LOF(p) =1|N |

∑o∈N

lrdk(o)lrdk(p)

LOF(p) =1|N |

∑o∈N︸ ︷︷ ︸

Mittlere

lrdk(o)lrdk(p)︸ ︷︷ ︸

relative Dichte (der Nachbarn!)

I p gleich dicht⇔ relative Dichte = 1I p ähnlich dicht⇔ relative Dichte ≈ 1I p weniger dicht⇔ relative Dichte > 1I LOF(p)� 1 für Ausreißer!

Hinweis: Dichte im Sinne von OPTICS/DBSCAN!Die Erreichbarkeitsdistanz (lrd) wird oft übersehen!

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

LOF(p) =1|N |

∑o∈N︸ ︷︷ ︸

Mittlere

lrdk(o)lrdk(p)︸ ︷︷ ︸

relative Dichte (der Nachbarn!)

I p gleich dicht⇔ relative Dichte = 1I p ähnlich dicht⇔ relative Dichte ≈ 1I p weniger dicht⇔ relative Dichte > 1I LOF(p)� 1 für Ausreißer!

Hinweis: Dichte im Sinne von OPTICS/DBSCAN!Die Erreichbarkeitsdistanz (lrd) wird oft übersehen!

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

LOF(p) =1|N |

∑o∈N︸ ︷︷ ︸

Mittlere

lrdk(o)lrdk(p)︸ ︷︷ ︸

relative Dichte (der Nachbarn!)

I p gleich dicht⇔ relative Dichte = 1

I p ähnlich dicht⇔ relative Dichte ≈ 1I p weniger dicht⇔ relative Dichte > 1I LOF(p)� 1 für Ausreißer!

Hinweis: Dichte im Sinne von OPTICS/DBSCAN!Die Erreichbarkeitsdistanz (lrd) wird oft übersehen!

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

LOF(p) =1|N |

∑o∈N︸ ︷︷ ︸

Mittlere

lrdk(o)lrdk(p)︸ ︷︷ ︸

relative Dichte (der Nachbarn!)

I p gleich dicht⇔ relative Dichte = 1I p ähnlich dicht⇔ relative Dichte ≈ 1

I p weniger dicht⇔ relative Dichte > 1I LOF(p)� 1 für Ausreißer!

Hinweis: Dichte im Sinne von OPTICS/DBSCAN!Die Erreichbarkeitsdistanz (lrd) wird oft übersehen!

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

LOF(p) =1|N |

∑o∈N︸ ︷︷ ︸

Mittlere

lrdk(o)lrdk(p)︸ ︷︷ ︸

relative Dichte (der Nachbarn!)

I p gleich dicht⇔ relative Dichte = 1I p ähnlich dicht⇔ relative Dichte ≈ 1I p weniger dicht⇔ relative Dichte > 1

I LOF(p)� 1 für Ausreißer!

Hinweis: Dichte im Sinne von OPTICS/DBSCAN!Die Erreichbarkeitsdistanz (lrd) wird oft übersehen!

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

LOF(p) =1|N |

∑o∈N︸ ︷︷ ︸

Mittlere

lrdk(o)lrdk(p)︸ ︷︷ ︸

relative Dichte (der Nachbarn!)

I p gleich dicht⇔ relative Dichte = 1I p ähnlich dicht⇔ relative Dichte ≈ 1I p weniger dicht⇔ relative Dichte > 1I LOF(p)� 1 für Ausreißer!

Hinweis: Dichte im Sinne von OPTICS/DBSCAN!Die Erreichbarkeitsdistanz (lrd) wird oft übersehen!

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

Local Outlier Factor

LOF(p) =1|N |

∑o∈N︸ ︷︷ ︸

Mittlere

lrdk(o)lrdk(p)︸ ︷︷ ︸

relative Dichte (der Nachbarn!)

I p gleich dicht⇔ relative Dichte = 1I p ähnlich dicht⇔ relative Dichte ≈ 1I p weniger dicht⇔ relative Dichte > 1I LOF(p)� 1 für Ausreißer!

Hinweis: Dichte im Sinne von OPTICS/DBSCAN!Die Erreichbarkeitsdistanz (lrd) wird oft übersehen!

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A

B C 1 B C D E 6

B

A D 1 A C D E 5

C

A D 1 A B D E 5

D

B C 1 A B C E 4

E

D F 4 B C D F G 5

F

G H 2 G H I J 3

G

F H 1 F H I J 2

H

G I J 1 F G I J 2

I

G H J 2 F G H J 3

J

G H I K 2 G H I K 2

K

H J 3 G H I J L 4

L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

E

K

O

2NN 2d. 4NN 4d.A

B C 1 B C D E 6

B

A D 1 A C D E 5

C

A D 1 A B D E 5

D

B C 1 A B C E 4

E

D F 4 B C D F G 5

F

G H 2 G H I J 3

G

F H 1 F H I J 2

H

G I J 1 F G I J 2

I

G H J 2 F G H J 3

J

G H I K 2 G H I K 2

K

H J 3 G H I J L 4

L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1

B C D E 6

B A D 1

A C D E 5

C A D 1

A B D E 5

D B C 1

A B C E 4

E

D F 4 B C D F G 5

F

G H 2 G H I J 3

G

F H 1 F H I J 2

H

G I J 1 F G I J 2

I

G H J 2 F G H J 3

J

G H I K 2 G H I K 2

K

H J 3 G H I J L 4

L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E

D F 4 B C D F G 5

F

G H 2 G H I J 3

G

F H 1 F H I J 2

H

G I J 1 F G I J 2

I

G H J 2 F G H J 3

J

G H I K 2 G H I K 2

K

H J 3 G H I J L 4

L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4

B C D F G 5

F

G H 2 G H I J 3

G

F H 1 F H I J 2

H

G I J 1 F G I J 2

I

G H J 2 F G H J 3

J

G H I K 2 G H I K 2

K

H J 3 G H I J L 4

L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F

G H 2 G H I J 3

G

F H 1 F H I J 2

H

G I J 1 F G I J 2

I

G H J 2 F G H J 3

J

G H I K 2 G H I K 2

K

H J 3 G H I J L 4

L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2

G H I J 3

G

F H 1 F H I J 2

H

G I J 1 F G I J 2

I

G H J 2 F G H J 3

J

G H I K 2 G H I K 2

K

H J 3 G H I J L 4

L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G

F H 1 F H I J 2

H

G I J 1 F G I J 2

I

G H J 2 F G H J 3

J

G H I K 2 G H I K 2

K

H J 3 G H I J L 4

L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1

F H I J 2

H G I J 1

F G I J 2

I

G H J 2 F G H J 3

J

G H I K 2 G H I K 2

K

H J 3 G H I J L 4

L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I

G H J 2 F G H J 3

J

G H I K 2 G H I K 2

K

H J 3 G H I J L 4

L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I G H J 2

F G H J 3

J

G H I K 2 G H I K 2

K

H J 3 G H I J L 4

L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I G H J 2 F G H J 3J

G H I K 2 G H I K 2

K

H J 3 G H I J L 4

L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I G H J 2 F G H J 3J G H I K 2 G H I K 2K

H J 3 G H I J L 4

L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I G H J 2 F G H J 3J G H I K 2 G H I K 2K H J 3

G H I J L 4

L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I G H J 2 F G H J 3J G H I K 2 G H I K 2K H J 3 G H I J L 4L

K M O 4 K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I G H J 2 F G H J 3J G H I K 2 G H I K 2K H J 3 G H I J L 4L K M O 4

K M N O P R 5

M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I G H J 2 F G H J 3J G H I K 2 G H I K 2K H J 3 G H I J L 4L K M O 4 K M N O P R 5M

N O P R 2 N O P R 2

N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I G H J 2 F G H J 3J G H I K 2 G H I K 2K H J 3 G H I J L 4L K M O 4 K M N O P R 5M N O P R 2 N O P R 2N

O Q 1 M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I G H J 2 F G H J 3J G H I K 2 G H I K 2K H J 3 G H I J L 4L K M O 4 K M N O P R 5M N O P R 2 N O P R 2N O Q 1

M O P Q R 2

O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I G H J 2 F G H J 3J G H I K 2 G H I K 2K H J 3 G H I J L 4L K M O 4 K M N O P R 5M N O P R 2 N O P R 2N O Q 1 M O P Q R 2O

M N P R 1 M N P R 1

P

O S 1 M N O R S 2

Q

N R 1 N O R S T 2

R

O Q S T 1 O Q S T 1

S

P R 1 O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I G H J 2 F G H J 3J G H I K 2 G H I K 2K H J 3 G H I J L 4L K M O 4 K M N O P R 5M N O P R 2 N O P R 2N O Q 1 M O P Q R 2O

M N P R 1 M N P R 1

P O S 1

M N O R S 2

Q N R 1

N O R S T 2

R

O Q S T 1 O Q S T 1

S P R 1

O P Q R T 2

T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I G H J 2 F G H J 3J G H I K 2 G H I K 2K H J 3 G H I J L 4L K M O 4 K M N O P R 5M N O P R 2 N O P R 2N O Q 1 M O P Q R 2O

M N P R 1 M N P R 1

P O S 1 M N O R S 2Q N R 1 N O R S T 2R

O Q S T 1 O Q S T 1

S P R 1 O P Q R T 2T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I G H J 2 F G H J 3J G H I K 2 G H I K 2K H J 3 G H I J L 4L K M O 4 K M N O P R 5M N O P R 2 N O P R 2N O Q 1 M O P Q R 2O M N P R 1 M N P R 1P O S 1 M N O R S 2Q N R 1 N O R S T 2R O Q S T 1 O Q S T 1S P R 1 O P Q R T 2T

O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

1 2 3 4 5 6 7 8 9 101112

123456789

101112

A B

C D

E

F

G H

I

J K

L

M

N O P

Q R S

T

2NN 2d. 4NN 4d.A B C 1 B C D E 6B A D 1 A C D E 5C A D 1 A B D E 5D B C 1 A B C E 4E D F 4 B C D F G 5F G H 2 G H I J 3G F H 1 F H I J 2H G I J 1 F G I J 2I G H J 2 F G H J 3J G H I K 2 G H I K 2K H J 3 G H I J L 4L K M O 4 K M N O P R 5M N O P R 2 N O P R 2N O Q 1 M O P Q R 2O M N P R 1 M N P R 1P O S 1 M N O R S 2Q N R 1 N O R S T 2R O Q S T 1 O Q S T 1S P R 1 O P Q R T 2T O Q R S 2 O Q R S 2

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 -

4/(6 + 5 + 4 + 5)

C A D 1 A B D E 5 -

4/(6 + 5 + 4 + 5)

D B C 1 A B C E 4

2/(1 + 1) 4/(6 + 5 + 5 + 5)

E D F 4 B C D F G 5

2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)

F G H 2 G H I J 3

2/(1 + 2) 4/(2 + 2 + 3 + 3)

G F H 1 F H I J 2 -

4/(3 + 2 + 3 + 2)

H G I J 1 F G I J 2

3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)

I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2

4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4

2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)

L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 -

4/(6 + 5 + 4 + 5)

C A D 1 A B D E 5 -

4/(6 + 5 + 4 + 5)

D B C 1 A B C E 4

2/(1 + 1) 4/(6 + 5 + 5 + 5)

E D F 4 B C D F G 5 2/(4 + 4)

5/(5 + 5 + 4 + 4 + 5)

F G H 2 G H I J 3

2/(1 + 2) 4/(2 + 2 + 3 + 3)

G F H 1 F H I J 2 -

4/(3 + 2 + 3 + 2)

H G I J 1 F G I J 2

3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)

I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2

4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4

2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)

L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 -

4/(6 + 5 + 4 + 5)

C A D 1 A B D E 5 -

4/(6 + 5 + 4 + 5)

D B C 1 A B C E 4

2/(1 + 1) 4/(6 + 5 + 5 + 5)

E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3

2/(1 + 2) 4/(2 + 2 + 3 + 3)

G F H 1 F H I J 2 -

4/(3 + 2 + 3 + 2)

H G I J 1 F G I J 2

3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)

I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2

4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4

2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)

L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 -

4/(6 + 5 + 4 + 5)

C A D 1 A B D E 5 -

4/(6 + 5 + 4 + 5)

D B C 1 A B C E 4 2/(1 + 1)

4/(6 + 5 + 5 + 5)

E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3

2/(1 + 2) 4/(2 + 2 + 3 + 3)

G F H 1 F H I J 2 -

4/(3 + 2 + 3 + 2)

H G I J 1 F G I J 2

3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)

I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2

4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4

2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)

L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 -

4/(6 + 5 + 4 + 5)

C A D 1 A B D E 5 -

4/(6 + 5 + 4 + 5)

D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3

2/(1 + 2) 4/(2 + 2 + 3 + 3)

G F H 1 F H I J 2 -

4/(3 + 2 + 3 + 2)

H G I J 1 F G I J 2

3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)

I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2

4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4

2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)

L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 -

4/(6 + 5 + 4 + 5)

C A D 1 A B D E 5 -

4/(6 + 5 + 4 + 5)

D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2)

4/(2 + 2 + 3 + 3)

G F H 1 F H I J 2 -

4/(3 + 2 + 3 + 2)

H G I J 1 F G I J 2

3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)

I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2

4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4

2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)

L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 -

4/(6 + 5 + 4 + 5)

C A D 1 A B D E 5 -

4/(6 + 5 + 4 + 5)

D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 -

4/(3 + 2 + 3 + 2)

H G I J 1 F G I J 2

3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)

I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2

4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4

2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)

L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 -

4/(6 + 5 + 4 + 5)

D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 -

4/(3 + 2 + 3 + 2)

H G I J 1 F G I J 2

3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)

I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2

4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4

2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)

L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 -

4/(3 + 2 + 3 + 2)

H G I J 1 F G I J 2

3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)

I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2

4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4

2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)

L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2

3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)

I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2

4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4

2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)

L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2

3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)

I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2

4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4 2/(2 + 3)

5/(4 + 3 + 4 + 2 + 5)

L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2

3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)

I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2

4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2)

4/(3 + 2 + 3 + 2)

I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2

4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2

4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2 4/(2 + 1 + 2 + 3)

4/(2 + 2 + 3 + 4)

K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 -

4/(3 + 2 + 2 + 2)

J G H I K 2 G H I K 2 4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 - 4/(3 + 2 + 2 + 2)J G H I K 2 G H I K 2 4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 -

6/(4 + 3 + 5 + 4 + 5 + 5)

M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 - 4/(3 + 2 + 2 + 2)J G H I K 2 G H I K 2 4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 - 6/(4 + 3 + 5 + 4 + 5 + 5)M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1

4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 - 4/(3 + 2 + 2 + 2)J G H I K 2 G H I K 2 4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 - 6/(4 + 3 + 5 + 4 + 5 + 5)M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1 4/(2 + 1 + 1 + 1)

4/(2 + 2 + 2 + 1)

P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 - 4/(3 + 2 + 2 + 2)J G H I K 2 G H I K 2 4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 - 6/(4 + 3 + 5 + 4 + 5 + 5)M N O P R 2 N O P R 2

4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1 4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 - 4/(3 + 2 + 2 + 2)J G H I K 2 G H I K 2 4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 - 6/(4 + 3 + 5 + 4 + 5 + 5)M N O P R 2 N O P R 2 4/(2 + 2 + 1 + 2)

4/(2 + 1 + 2 + 2)

N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1 4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 - 4/(3 + 2 + 2 + 2)J G H I K 2 G H I K 2 4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 - 6/(4 + 3 + 5 + 4 + 5 + 5)M N O P R 2 N O P R 2 4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)N O Q 1 M O P Q R 2

2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1 4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 - 4/(3 + 2 + 2 + 2)J G H I K 2 G H I K 2 4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 - 6/(4 + 3 + 5 + 4 + 5 + 5)M N O P R 2 N O P R 2 4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)N O Q 1 M O P Q R 2 2/(1 + 1)

5/(2 + 1 + 2 + 2 + 2)

O M N P R 1 M N P R 1 4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 - 4/(3 + 2 + 2 + 2)J G H I K 2 G H I K 2 4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 - 6/(4 + 3 + 5 + 4 + 5 + 5)M N O P R 2 N O P R 2 4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)N O Q 1 M O P Q R 2 2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)O M N P R 1 M N P R 1 4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)P O S 1 M N O R S 2

2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 - 4/(3 + 2 + 2 + 2)J G H I K 2 G H I K 2 4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 - 6/(4 + 3 + 5 + 4 + 5 + 5)M N O P R 2 N O P R 2 4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)N O Q 1 M O P Q R 2 2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)O M N P R 1 M N P R 1 4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)P O S 1 M N O R S 2 2/(1 + 1)

5/(2 + 2 + 1 + 2 + 2)

Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 - 4/(3 + 2 + 2 + 2)J G H I K 2 G H I K 2 4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 - 6/(4 + 3 + 5 + 4 + 5 + 5)M N O P R 2 N O P R 2 4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)N O Q 1 M O P Q R 2 2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)O M N P R 1 M N P R 1 4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)P O S 1 M N O R S 2 2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1

4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 - 4/(3 + 2 + 2 + 2)J G H I K 2 G H I K 2 4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 - 6/(4 + 3 + 5 + 4 + 5 + 5)M N O P R 2 N O P R 2 4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)N O Q 1 M O P Q R 2 2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)O M N P R 1 M N P R 1 4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)P O S 1 M N O R S 2 2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1 4/(1 + 1 + 1 + 2)

4/(1 + 2 + 2 + 2)

S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

2NN 2d. 4NN 4d. lrd2 lrd4A B C 1 B C D E 6 - -B A D 1 A C D E 5 - 4/(6 + 5 + 4 + 5)C A D 1 A B D E 5 - 4/(6 + 5 + 4 + 5)D B C 1 A B C E 4 2/(1 + 1) 4/(6 + 5 + 5 + 5)E D F 4 B C D F G 5 2/(4 + 4) 5/(5 + 5 + 4 + 4 + 5)F G H 2 G H I J 3 2/(1 + 2) 4/(2 + 2 + 3 + 3)G F H 1 F H I J 2 - 4/(3 + 2 + 3 + 2)H G I J 1 F G I J 2 3/(1 + 2 + 2) 4/(3 + 2 + 3 + 2)I G H J 2 F G H J 3 - 4/(3 + 2 + 2 + 2)J G H I K 2 G H I K 2 4/(2 + 1 + 2 + 3) 4/(2 + 2 + 3 + 4)K H J 3 G H I J L 4 2/(2 + 3) 5/(4 + 3 + 4 + 2 + 5)L K M O 4 K M N O P R 5 - 6/(4 + 3 + 5 + 4 + 5 + 5)M N O P R 2 N O P R 2 4/(2 + 2 + 1 + 2) 4/(2 + 1 + 2 + 2)N O Q 1 M O P Q R 2 2/(1 + 1) 5/(2 + 1 + 2 + 2 + 2)O M N P R 1 M N P R 1 4/(2 + 1 + 1 + 1) 4/(2 + 2 + 2 + 1)P O S 1 M N O R S 2 2/(1 + 1) 5/(2 + 2 + 1 + 2 + 2)Q N R 1 N O R S T 2 - -R O Q S T 1 O Q S T 1 4/(1 + 1 + 1 + 2) 4/(1 + 2 + 2 + 2)S P R 1 O P Q R T 2 - -T O Q R S 2 O Q R S 2 - -

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

Finale LOF-Werte für k = 2:

LOF2(E) :=22 + 2

32

/28

≈ 3.333

LOF2(O) :=47 + 2

2 + 22 + 4

54

/45

≈ 1.054

LOF2(K) :=35 + 4

82

/25

≈ 1.375

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

Finale LOF-Werte für k = 4:

LOF4(E) :=4

20 + 420 + 4

21 + 410 + 4

105

/523

≈ 1.279

LOF4(O) :=47 + 5

9 + 59 + 4

74

/47

≈ 0.986

LOF4(K) :=4

10 + 410 + 4

9 + 411 + 6

265

/518

≈ 1.324

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF und kNN

Finale LOF-Werte für k = 4:

LOF4(E) :=4

20 + 420 + 4

21 + 410 + 4

105

/523

≈ 1.279

LOF4(O) :=47 + 5

9 + 59 + 4

74

/47

≈ 0.986

LOF4(K) :=4

10 + 410 + 4

9 + 411 + 6

265

/518

≈ 1.324

|N (o)| des betrachteten Objektes|N (p)| der NachbarnSumme der Erreichbarkeit von o / p

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF and kNN

Sowohl LOF als auch kNN haben bei k = 4 = | {A,B,C,D} |das Problem, dass k + 1 größer ist als der kleinste Cluster.

Aber: für 4NN wird der Punkt A der größte Ausreißer.

Bei LOF, wird lediglich E weniger deutlich, da sich dieDichten der Nachbarn B, C und D reduzieren.Aber es hat immernoch einen der größten Werte,und A, B, C, D bleiben “Inlier”!

⇒ LOF bleibt auch bei ungünstigem k zuverlässiger.

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF and kNN

Sowohl LOF als auch kNN haben bei k = 4 = | {A,B,C,D} |das Problem, dass k + 1 größer ist als der kleinste Cluster.

Aber: für 4NN wird der Punkt A der größte Ausreißer.

Bei LOF, wird lediglich E weniger deutlich, da sich dieDichten der Nachbarn B, C und D reduzieren.Aber es hat immernoch einen der größten Werte,und A, B, C, D bleiben “Inlier”!

⇒ LOF bleibt auch bei ungünstigem k zuverlässiger.

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF and kNN

Sowohl LOF als auch kNN haben bei k = 4 = | {A,B,C,D} |das Problem, dass k + 1 größer ist als der kleinste Cluster.

Aber: für 4NN wird der Punkt A der größte Ausreißer.

Bei LOF, wird lediglich E weniger deutlich, da sich dieDichten der Nachbarn B, C und D reduzieren.Aber es hat immernoch einen der größten Werte,und A, B, C, D bleiben “Inlier”!

⇒ LOF bleibt auch bei ungünstigem k zuverlässiger.

Data MiningTutorial

E. Schubert,A. Zimek

Outlierdetection

Aufgabe 8-1

LOF and kNN

Sowohl LOF als auch kNN haben bei k = 4 = | {A,B,C,D} |das Problem, dass k + 1 größer ist als der kleinste Cluster.

Aber: für 4NN wird der Punkt A der größte Ausreißer.

Bei LOF, wird lediglich E weniger deutlich, da sich dieDichten der Nachbarn B, C und D reduzieren.Aber es hat immernoch einen der größten Werte,und A, B, C, D bleiben “Inlier”!

⇒ LOF bleibt auch bei ungünstigem k zuverlässiger.