Verschiedene Ergebnisse von LOF Implementierung in ELKI und RapidMiner

Question

Ich habe meine eigene Implementierung von LOF geschrieben und ich versuche, Ergebnisse mit den Implementierungen in ELKI und RapidMiner zu vergleichen, aber alle 3 geben andere Ergebnisse! Ich versuche herauszufinden, warum.

Mein Referenzdatensatz ist eindimensional, 102 echte Werte mit vielen Duplikaten. Ich werde es versuchen und es unten posten.

Zuerst die RapidMiner-Implementierung. Die LOF-Werte unterscheiden sich stark von ELKI und von meinen Ergebnissen; viele kommen mit einem LOF der Unendlichkeit zurück. Wurde diese Implementierung als richtig validiert?

Meine Ergebnisse sind ähnlich wie ELKI, aber ich bekomme nicht genau die gleichen LOF-Werte. Aus einem kurzen Blick auf die Kommentare im ELKI-Quellcode, denke ich, kann dies an den Unterschieden in der Art und Weise liegen, wie die k-Nachbarschaft berechnet wird.

Im LOF-Papier gibt der MinPts-Parameter (an anderer Stelle k genannt) die minimale Anzahl an. von Punkten, die in der k-Nachbarschaft enthalten sein sollen. In der ELKI-Implementierung, glaube ich, definieren sie die k-Nachbarschaft als genau k Punkte und nicht als alle Punkte innerhalb der k-Distanz oder k-distinkten Distanz. Kann jemand genau bestätigen, wie ELKI die k-Nachbarschaft konstruiert? Es gibt auch eine private Variable, die es erlaubt, den Punkt selbst in seine eigene Nachbarschaft aufzunehmen, aber es sieht so aus, als ob der Punkt nicht darin enthalten wäre.

Kennt jemand einen öffentlichen Referenzdatensatz, der die LOF-Scores für Validierungszwecke angehängt hat?

--- mehr Details folgen ---

Referenz: ELKI Quellcode ist hier:

http://elki.dbs.ifi.lmu.de/browser/elki/trunk/src/de/lmu/ifi/dbs/elki/algorithm/outlier/lof/LOF.java

Rapidminer Quellcode ist hier:

http://code.google.com/p/rapidminer-anomalydetection/source/browse/trunk/src/de/dfki/madm/anomalydetection/evaluator/nearest_neighbor_based/LOFEvaluator.java

Hier ist mein Testdatensatz:

4,32323 5,12595 5,12595 5,12595 5,12595 5,7457 5,7457 5,7457 5,7457 5,7457 5,7457 5,97766 5,97766 6,07352 6,07352 6,12015 6,12015 6,12015 6,44797 6,44797 6,48131 6,48131 6,48131 6,48131 6,48131 6,48131 6,6333 6,6333 6,6333 6,70872 6,70872 6,70872 6,70872 6,70872 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,10361 7,10361 7,10361 7,10361 7,10361 7,10361 7,10361 7,10361 7,15651 7,1 5651 7,15651 7,15651 7,15651 7,15651 7,15651 7,15651 8,22598 8,22598 8,22598 8,22598 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538

Zum Beispiel bekomme ich folgende LOF Punktzahl für die erste Reihe (4,32323):

• Rapid: unendlich (mit MinPts unterer/oberer Grenze eingestellt 10.100)
• ELKI: 2.6774 (mit k = 10 und distfunction/reachdistfunction auf Standard gesetzt) ​​
• Meine Implementierung: 1,9531

Einige weitere Details darüber, was meine Implementierung tut:

1. MinPts ist 10, so dass ich Ich finde die 10 verschiedenen Nachbarn des Punktes. So ist die Nachbarschaft von 4,33232 tatsächlich 48 Punkte, von 5,12595 bis zu 6,77579.
2. Das hat mir einen k-deutlichen Abstand von 2,45256
3. gibt ich die Berechnung den Erreichbarkeits Abstandes des ersten Nächsten wie 1,58277
4. ich die LRD der Probe als 1/(99,9103/48)
Berechnung
5. Summe LRD (o)/LRD (p) für alle 48 Nachbarn ist 93,748939
6. Division durch 48 eine LOF von 1,9531

Answer 1

wirklich überrascht, dass ich bin nicht sie unterscheiden zu bekommen. Sie könnten auch in Wekas ​​Implementierung von LOF hinzufügen, und Sie werden wahrscheinlich noch eine andere Antwort bekommen.

Hier ist ein weiterer Unterschied für Sie zu Ihren Gleichungen hinzufügen: Soweit ich weiß, verschmilzt die rapidminer Implementierung Punkte, die die gleichen Koordinaten haben. Aber vielleicht haben sie vergessen, diese Gewichte bei der Berechnung der nächsten Nachbarn zu berücksichtigen! Im klassischen Datenbankkontext würden Sie doppelte Koordinaten in einer einzigen Beobachtung nicht zusammenführen. Sie sind immer noch gültige Datenbankdatensätze und sollten als vollständige Datensätze gezählt werden.

Ich weiß nicht, ob einige von ihnen einige automatische Datenvorverarbeitung wie z. B. Neuskalierung des Datensatzes durchführen.

Die ELKI-Implementierung wurde verifiziert gegen eine Reihe von Lehrbuchbeispielen, die wir für den Unterricht verwenden.

Es gibt jedoch Eckfälle im Algorithmus, die nicht zu 100% festgelegt sind, so dass selbst bei "wörtlichen" Implementierungen des Algorithmus Raum für Unterschiede besteht. Sie haben bereits in drei davon laufen: A) Aggregat, B) Tropfen, C) betrachten Aus Data-Mining-Sicht, C richtig ist, verschiedene

:

1. Wie, um doppelte Punkte zu behandeln und A (bei korrekter Implementierung) ist eine Optimierung, die Ihnen unnötige Distanzberechnungen ersparen kann. B ist die übliche mathematische Ansicht, macht aber für einen Datenbankkontext wenig Sinn. Wenn ich zwei "John Doe" habe, sind sie die gleiche Person?

2. Definition von k nächsten Nachbarn und k-Abstand.

   Die übliche Definition von k-Abstand ist: der kleinste Abstand, so dass mindestens k Beobachtungen enthalten sind. Wenn der Abfragepunkt ausgeschlossen wird, ergibt dies den Inver- val bis zu 5,7457 vom Startpunkt aus: Es gibt 10 weitere Beobachtungen in einem Radius von 5,7457 - 4,332323.

   Die k nächsten Nachbarn sind normalerweise definiert als jeder Punkt innerhalb dieser Entfernung, der mehr als k sein kann.Aber dann müssen alle zusätzlichen Objekte den gleichen Abstand wie die kth haben! Es scheint, als ob Rapid genau k verwendet, die mit der LOF Veröffentlichung richten sich nicht (Definition 4 in der LOF Veröffentlichung sehen!)

   Es ist wirklich die k nächsten Nachbarn (einschließlich Krawatten, aber anders als das nicht mehr als k Objekte), nicht die k-ths kleinste deutlich Entfernung. Wo hast du das "distinct" her?

   Definitionen 3 und 4 in der LOF-Veröffentlichung sind ziemlich klar auf dem kNN-Set LOF verwendet.

   Ihre Nachbarschaft von 48 Objekten ist somit nicht korrekt.

3. Was tun, wenn es mehr als MinPts Punkte duplizieren (eine wörtliche Umsetzung wird eine Division durch Null ergeben, aber aus offensichtlichen Gründen sollte der Punkt eine LOF von 1,0 gegeben werden)

   Dies ist vielleicht, was ist passiert mit Rapidminer.

Und dann gibt es die Erreichbarkeit Entfernung: dies ist wirklich schwierig, weil es nicht eine mathematische Distanz ist. Es ist asymmetrisch.

Die Erreichbarkeit des ersten Beobachtungs von die zweite ist die k-Abstand des zweiten passiert zu sein, die von einem kurzen Blick reach-dist(x[0], x[1]) = max(5.97766 - 5.12595, 5.12595 - 4.32323) = 0.80272 (nicht überprüfen tat)

Siehe my extensive tutorial slides on outlier detection für eine Schritt-für- Schritt Demonstration der Berechnung von LOF. Soweit ich das beurteilen kann, ist dies buchstäblich LOF. Es berührt nicht alle Eckfälle, aber es motiviert das Design des LOF-Algorithmus und ist ziemlich erschöpfend.

Answer 2

Wenn Sie die Anomalieerkennungserweiterung für RapidMiner [1] (nicht die integrierte LOF) verwenden, erhalten Sie die korrekten Ergebnisse. Der eingebaute LOF ist defekt. Dies sind die gleichen Ergebnisse wie ELKI. Diese Implementierung ist viel schneller als ELKI, weil sie mehr Threads enthält und auch viel weniger Speicher verbraucht. Es kann auch Duplikate behandeln (sogar mehr als k + 1), wo ELKI Ausnahmen auslöst. (Basierend auf dem k-verschieden)

Best, Hans

[1] http://marketplace.rapid-i.com/UpdateServer/faces/product_details.xhtml?productId=rmx_anomalydetection