Ausreißer ausmerzen



  • Ich suche einen effizienten Algorithmus zum finden von (sehr offensichtlichen) Ausreißern.

    Bsp

    5
    5.2
    5.4
    10 // <-
    5.8
    6

    Ich würde eine lineare regression machen (über X Punkte) und dann den Abstand der mittleren Punkte zur Gerade berechnen, aber vielleicht ist das ja nicht der beste Ansatz.



  • bei den von dir gezeigten Daten?
    Mittelwert + Standardabweichung, und dann ab bestimmtem Schwellwert als Ausreisser markieren.



  • dfsfsdf schrieb:

    bei den von dir gezeigten Daten?
    Mittelwert + Standardabweichung, und dann ab bestimmtem Schwellwert als Ausreisser markieren.

    das müsste ich zwar Abschnittsweise machen, aber das dürfte deutlich schneller sein als Matrixmultiplikation


  • Mod

    dfsfsdf schrieb:

    bei den von dir gezeigten Daten?
    Mittelwert + Standardabweichung, und dann ab bestimmtem Schwellwert als Ausreisser markieren.

    Das hat aber ein erhebliches Problem: Der Ausreißer verändert den Durchschnitt! Es gibt wesentlich robustere Verfahren:
    http://en.wikipedia.org/wiki/Outlier

    5crip schrieb:

    aber das dürfte deutlich schneller sein als Matrixmultiplikation

    Hast du denn keinen Computer, der dir das in ein paar Mikrosekunden berechnet?



  • SeppJ schrieb:

    5crip schrieb:

    aber das dürfte deutlich schneller sein als Matrixmultiplikation

    Hast du denn keinen Computer, der dir das in ein paar Mikrosekunden berechnet?

    Das ganze wird in CoffeeScript implementiert und der ganze Analyseprozess (von dem ich euch ncihts erzählt habe :P) ist schon teuer genug.



  • SeppJ schrieb:

    Hast du denn keinen Computer, der dir das in ein paar Mikrosekunden berechnet?

    Nicht mal ich benutze einen Computer. Ist hier in Nordkorea nicht erwünscht.


  • Mod

    5cript schrieb:

    SeppJ schrieb:

    5crip schrieb:

    aber das dürfte deutlich schneller sein als Matrixmultiplikation

    Hast du denn keinen Computer, der dir das in ein paar Mikrosekunden berechnet?

    Das ganze wird in CoffeeScript implementiert und der ganze Analyseprozess (von dem ich euch ncihts erzählt habe :P) ist schon teuer genug.

    Dann ist es ja besonders wichtig, dass man statt 1 Stunde für Analyse + 1 Mikrosekunde für Ausreißersuche nicht 1 Stunde für Analyse + 10 Mikrosekunden für Ausreißersuche benötigt. Oder ist CoffeeScript so lahm?



  • SeppJ schrieb:

    Dann ist es ja besonders wichtig, dass man statt 1 Stunde für Analyse + 1 Mikrosekunde für Ausreißersuche nicht 1 Stunde für Analyse + 10 Mikrosekunden für Ausreißersuche benötigt. Oder ist CoffeeScript so lahm?

    Ja die Ausreißersuche ist nicht der schlimmste Teil bei weitem.
    Aber JavaScript ist auch keine Rakete. (bzw Coffee->JS).
    Vorherige Tests waren schon im Sekunden- -> Minuten- bereich (wegen der Bildzugriffe inklusive Bildtransformationen).



  • Koennen die Ausreißer nur in eine Richtung auftreten, wie in deinem Minibeispiel?



  • Was für Messwerte sind das denn? Sollen die auf einer Gerade liegen? Wenn ja, dann sollte diese Information in einen entsprechenden Filter einfliessen.



  • itsamee schrieb:

    Koennen die Ausreißer nur in eine Richtung auftreten, wie in deinem Minibeispiel?

    jaein. lokal betrachtet ja, global nicht.

    Beispiel: (Alle X müssen korrigiert werden)

    ####                     XX
        #####
             ####
                 ##  ####                             ##   ##
                         ####  ####          #########       ####
                                   ##########
    
                   XX
    
                                                        XXX
    

    EDIT: Der verlauf der Rauten verläuft nicht entlang eines Polynoms oder einer bekannten Funktion.

    EDIT 2: Das ist noch ein relativ "nettes / günstiges" Beispiel



  • Hm, also wenn ich dein Bild so sehe, würde ich spontan eine LOWESS regression drauf anwenden. Dadurch werden normalerweilse sämtliche Punkte etwas verschoben (weiß nicht, ob das schlimm ist in deinem Fall), aber ich denke mal, dass es davon auch lokale Varianten gibt, so dass nicht sämtliche Punkte normalisiert werden. Frage ist natürlich, ob es dafür irgendwelche CoffeeScript Bibliotheken gibt, kenne die Sprache nicht.



  • Irgendwie verstehe ich das nicht ganz. Sind das keine diskreten Daten oder warum kannst du nicht einfach

    |f(n) - f(n+1)| > eps
    

    vergleichen?
    (Bzw. wie in deinem Bild mit mehreren x dann |f(n) - f(n+m)|)


  • Mod

    Da bietet sich schon irgendwie einer der fortgeschrittenen Tests an, die ich verlinkt habe. Oder, da es sich ja anscheinend um ein zusammenhängendes Gebilde handelt, etwas wie RANSAC (was auch ein Test auf Ausreißer ist, aber ein bisschen spezieller für zusammenhängende Mengen). Wenn du aber ernsthaft Zeitprobleme bei den einfachen Methoden hast, dann kommt so etwas gar nicht in Frage. Du solltest darüber nachdenken, die Rechnung extern in einer anderen Sprache zu programmieren und dann von deinem Script aus bloß aufzurufen.



  • Im Prinzip brauchst du lokal einen Tiefpass, also im einfachsten Fall einen gleitenden Mittelwert. Und den Tiefpasswert ziehst du eben vom Funktionswert ab.
    Oder eigentlich einen Hochpass. Dort wo der viel durchlässt hast hohe Frequenzen die oft mit Störungen einhergehen.

    Wenn du mehr Infos zum Signal gibst, kann man dir eher helfen. Gerade in der Bildverarbeitung gäbe es spezielle Methoden die hilfreich sein könnten. Im Audiobereich gibts auch diverses.



  • Ich update hier nochmal, weil ich glaube ich habe ein Weg gefunden auch ohne das auszukommen.

    Die Aufgabe liegt darin Graphen wie sowas hier (das ist schon ein relativ harter Fall):
    http://upload.wikimedia.org/wikipedia/commons/d/de/Fitted_line.svg
    zu analysieren und aus dem Bild auf die Werte zu kommen.
    Bei echten Daten sind neben der Regression auch oft noch die Werte als Punkte dargestellt im Koordinatensytem oder gar andere Graphen oder Schmutz.

    Der Analysealgorithmus benötigt einen markierten Bereich im Bild (die Kurve anpinseln) und die Pixeldaten. Daraus erstellt dieser dann, mittels Median, Punkte die "ungefähr" auf der Gerade liegen. Messpunkte die sich außerdem im Bild befinden verursachen offensichtliche Sprungstellen (wenn man sie mit anpinselt).

    Mein jetzt aktueller Ansatz ist diese Sprungstellen zu finden und auf Grund der Sprungrichtung und Verteilung der Punkte zwischen den Sprungstellen auf die tatsächliche Kurve zurückzuschließen. Das ist einfacher als die Ausreißer zu finden. (EDIT: pen und paper tests zeigen gute Ergebnisse)

    Das habe ich alles so einfach wie möglich gehalten weil mathematische Kanonen einfach nur alles verlangsamen.
    Ganz zu Beginn habe ich den sämtlichen markierten Bereich in eine Matrix gefasst und diese manipuliert und mit gerechnet und Verfahren angwandt die mit jeder Iteration bessere Ergebnisse liefern. Das Ergebnis war gut in der Theorie aber Praktisch viel zu langsam.



  • @5cript: Ich habe mir die Methoden aus dem Wikipedia-Artikel nicht angeguckt, aber ich würde da einfach mit einem Schwellwert arbeiten. Nimm 2 Werte vor dem jeweils untersuchten Wert und konstruiere Dir damit eine Gerade, die durch diese beiden Punkte geht. Dann guck, welchen Funktionswert die Gerade am Ort des zu testenden Wertes hat und wenn die mehr als um einen bestimmten Schwellwert von einander abweichen, dann nimmst Du den Wert halt raus. Das funktioniert, wenn die Krümmung Deiner Funktion nicht zu hoch ist.

    ...im Zweifelsfall kannst Du das auch beidseitig machen. Und wenn die Krümmung nennenswert ist, dann musst Du eben eine Näherung höherer Ordnung nutzen.



  • 5cript schrieb:

    Die Aufgabe liegt darin Graphen wie sowas hier (das ist schon ein relativ harter Fall):
    http://upload.wikimedia.org/wikipedia/commons/d/de/Fitted_line.svg
    zu analysieren und aus dem Bild auf die Werte zu kommen.

    Wenn Du bei solchen Daten Ausreißer rausfiltern sollst, dann ist das eigentliche Problem glaube ich eher an einer anderen Stelle. Die Daten da erscheinen mir derart mies zu sein, dass man eher daran arbeiten sollte, die Erzeugung der Messdaten zu verbessern.

    Ich meine, dort gehören mehr als 50% der Messpunkte in die Kategorie "Ausreißer". Ich weiß nicht, ob "Ausreißer" irgendwo als Begriff definiert ist, aber ich würde da nicht mehr von Ausreißern sprechen.



  • Gregor schrieb:

    5cript schrieb:

    Die Aufgabe liegt darin Graphen wie sowas hier (das ist schon ein relativ harter Fall):
    http://upload.wikimedia.org/wikipedia/commons/d/de/Fitted_line.svg
    zu analysieren und aus dem Bild auf die Werte zu kommen.

    Wenn Du bei solchen Daten Ausreißer rausfiltern sollst, dann ist das eigentliche Problem glaube ich eher an einer anderen Stelle. Die Daten da erscheinen mir derart mies zu sein, dass man eher daran arbeiten sollte, die Erzeugung der Messdaten zu verbessern.

    Der Witz ist das die Daten aus wissenschaftliche Papieren stammen. Die nur die Graphen haben, aber keine Werte (die ich haben will).
    Wie die aussehen (optisch im Bild) ist sehr variabel.
    Steigung der Kurve kann von flach bis drastisch gehen.

    EDIT: um den richtigen Graph zu erwischen (und wenig Fehlerquellen) haben (wir) ich die Markierung eingeführt. Das erspart mir viel nachdenken, wenn ein Mensch dahinter sitzt und die Richtung vorgibt, was jetzt tatsächlich der Graph ist.

    EDIT 2: Gauß Quadratur, Newton Schema, Spline Interpolation, führen bei so extremen offensichtlichen Ausreißern nur zu extremen Verfälschungen der wirklichen Punkte auf dem Graph

    EDIT 3: Ich weiß was gleich kommt: Du arbeitest an der falschen Stelle! Die Analyse muss verbessert werden! => Leichter gesagt als getan. Flexibilität <=> Performanz <=> Korrektheit - das ist nicht so leicht zu balancieren.



  • tausch in deiner regression den quadratischen loss durch den huber-loss oder den loss der ε-SVM aus. Die sind noch konvex, aber wesentlich stabiler. Wenn DAS nicht mehr hilft, dann bleiben dir wohl nur noch Verfahren die auf nicht konvexen Lossfunktionen basieren.


Anmelden zum Antworten