Key points are not available for this paper at this time.
Die Definition von Ausreißern durch ihre Distanz zu benachbarten Beispielen ist ein beliebter Ansatz, um ungewöhnliche Beispiele in einem Datensatz zu finden. In letzter Zeit wurde viel Arbeit geleistet, um schnelle Algorithmen für diese Aufgabe zu entwickeln. Wir zeigen, dass ein einfacher verschachtelter Schleifenalgorithmus, der im schlimmsten Fall quadratisch ist, eine nahezu lineare Laufzeit erzielen kann, wenn die Daten in zufälliger Reihenfolge vorliegen und eine einfache Beschneidungsregel angewendet wird. Wir testen unseren Algorithmus an realen hochdimensionalen Datensätzen mit Millionen von Beispielen und zeigen, dass die nahezu lineare Skalierung über mehrere Größenordnungen hinweg gilt. Unsere Analyse des Durchschnittsfalls legt nahe, dass ein Großteil der Effizienz darauf zurückzuführen ist, dass die Zeit zur Verarbeitung von Nicht-Ausreißern, die die Mehrheit der Beispiele ausmachen, nicht von der Größe des Datensatzes abhängt.
Bay et al. (Sun,) haben diese Frage untersucht.