Fallen Punkte zusammen oder nur Zufall



  • Hallo Leute,

    ich bin nur Biologe deswegen reduziert sich mein mathematisches Wissen auf ein notwendiges Minimum - leider.

    Folgendes Problem:
    Ich habe eine Anzahl von Punkten, so zwischen 20-50 an der Zahl. Diese Punkte befinden sich aber nicht iregndwo im Raum sondern befinden sich alle entlang einer Linie (Abbildung 1A).
    Weil ich hier keine "Anhängen-Funktion" gefunden habe ist das Bild unter folgender URL erreichbar: http://db.tt/r59krduj
    Jeder Punkt hat eine Position X,Y.
    Ist es Zufall oder kein Zufall, dass die Punkte sich zu "Inseln" bilden?

    Meine Ideen, die ich soweit hatte:

    1. Ich berechne die Abstände zueinander und plotte dies. Bei einer "Insel" müsste sich der Anteil kleiner Abstände erhöhen. (Abbildung 1B)

    2. Ich projeziere von X,Y auf eine Dimension und mache damit irgendwas "Fourier-Mäßiges", also die Rate von Ereignissen über die Entfernung. Sorry, das ist etwas schwammig ausgedrückt, aber ich bin da leider auch kein Experte... (Abbildung 1C)

    Schön und gut wenn ich das "sehen" kann, aber ich brauche was quantitatives. Irgendwas wo ich sagen kann "ja, die punkte fallen zu "Inseln" zusammen und das ist kein Zufall".

    Habt ihr einen Namen für die Methode? Oder sonst irgendwelche Ideen wie man da rangehen kann?

    Herzlichen Dank und viele Grüße,
    Simon





  • Nimm den dichtebasierten Cluster-Algorithmus DBSCAN.



  • Hi,

    danke für die Tipps. Ich habe mir den DBSCAN angesehen und fand ihn für die Fragestellung eigentlich ganz passend. Ich glaube das Vorgehen größtenteils verstanden zu haben.
    Ich dachte mir, ich will das Rad nicht neu erfinden und habe mal im Netz nach Bibliotheken gegoogled und bin auf folgende Website gestoßen:
    http://codingplayground.blogspot.de/2009/11/dbscan-clustering-algorithm.html
    Eine C++ (boost, STL)-Implementation des DB-Scan Algorithmus. Es gibt da aber 1-2 Punkte, die ich nicht ganz verstehe:

    1. Die Wahl der EPSILON-Sphäre. Woran orientiert sich diese? Ich habe mir mal ein paar Datenpunkte zusammengeklaubt, die drei Cluster ergeben SOLLEN. Das war aber nur dann der Fall, wenn ich EPSILON zwischen 0,9005 und 0,9099 oder sowas gewählt hatte. Das ist jetzt nur Beispielshalber aber es waren wirklich so "Minimalwerte", die überhaupt das Gewünschte Ergebnis brachten. Der Zufalls-Generator im Beispiel erzeugt Werte die alle so bei -1..0..1 liegen. Die Werte die ich hatte lagen aber bei 100..300. Daher die Frage: hängt der Algorithmus von den Werten an sich ab? Sollte er doch nicht, oder?

    2. Im Beispiel habe ich auch gesehen, dass für die Clusterbildung als Treshold nicht die Distanz per se herangezogen wird, sondern sowas wie eine "Ähnlichkeit" der Punte berechnet und mit EPSILON verglichen wird. Kann mir jemand erklären, was es mit dieser Ähnlichkeit auf sich hat? Ist das auch der Grund, wieso für das Clustering auch nur EPSILON-Werte zwischen 0..1 Ergebnisse produzieren?

    Herzlichen Dank!
    Viele Grüße,
    Simon



  • Hallo,

    ich habe jetzt den Code nur schnell überflogen.
    Zur Clusterbildung werden verschiedene Ähnlichkeitsmaße unterstzützt. Dort zu finden ist der euklidische Abstand und der Cosinus zwischen den Ortsvektoren der Punkte. Nur letzterer ist komplett implementiert (der Euklidische Abstand definiert die Funktion "getSimilarity" gar nicht.
    Daher schätze ich, dass Du, ohne es zu wollen, das Cosinusmaß verwendest (Das liegt natürlich zwischen -1 und 1 und da muss man schon ein gutes Epsilon hinfrickeln).

    Zu Deiner Frage wegen des Epsilons: Ja, das ist Koordinatenabhängig. Es gibt an, wie nah (oder wie fern nicht) Punkte sein müssen, damit sie überhaupt auf Clusterbildung untersucht werden. Das ist natürlich Datensatzabhängig. Was Du machen könntest, wäre die einschließende Kugel zu berechnen und eine Fraktion des Radiusses zu verwenden. Die konkrete Wahl des Epsilons und ob die Ähnlichkeit der Punkte größer oder kleiner als das Epsilon sein muss, hängt natürlich auch entscheidend davon ab, wie Du das Ähnlichkeitmaß definierst.



  • Du brauchts doch deine Punkte nur verschmieren, Addieren und nen Threshold für Clusterbildung definieren ...

    Ums erstmal ganz plump anzugehen.

    Nochmal ausführlicher:

    Dein Punkt X_n(x_n;x)X\_n(x\_n;x) ist ne Funktion, die Dirac-Delta Funktion. Die machste nun etwas glatter, zb mit ner Normalverteilung:
    X_n=12πϵexp((x_nx)22ϵ)X\_n = \frac{1}{\sqrt{2\pi \epsilon}}\exp{\left(-\frac{(x\_n-x)^2}{2\epsilon}\right)}
    Die addierst du nun alle auf
    ϕ(x)=_iX_i(xi;x)\phi(x) = \sum\_i X\_i(x_i;x)
    und sagst einfach bei ϕ(x)>θ\phi(x) > \theta liegt ein Cluster vor.
    Tada.



  • Okay, man kann sich mit diesem generellen Ansatz jetzt (nachdem man vielleicht einen etwas geeigneteren Tiefpass verwendet hat) natürlich für jeden Punkt ausrechnen, ob er in einem Cluster liegt. Aber wie findet man nun heraus, mit welchen Punkten er einen Cluster bildet? Da müsste man ja jetzt die Äquipotentiallinien zu Theta errechnen (=Clusterflächen) und anschließend alle Punkte auf Enthaltensein in den entstandenen Flächen testen?
    Vor allem können so ja auch Donut-Cluster oder alle möglichen Formen von Clustern entstehen.



  • Zu testen mit welchen Punkten er ein Cluster bildet ist aufwendiger. Aber das war nicht gefragt, es ging doch nur darum OB Cluster gebildet werden?
    Das mit den Potentialgebieten ginge natürlich.
    Ja alle möglichen Formen können da enstehen, aber wir sind in 1D 😉



  • Hi,

    danke für den Input.
    Okay, ich habe mich auch schon gefragt was es mit dem "Cosine" auf sich hat. Das wäre dann quasi eine "Normalisierung", was doch eigentlich nicht schlecht ist wenn ich nicht weiß, wo die Punkte im Raum liegen?

    ScottZhang: danke, ja das wäre auch eine Herangehensweise. Allerdings habe ich nicht den geringsten Peil wie ich deine Formel in einen Algorithmus umsetzen könnte - sorry mein mathematisches Verständnis ist leider beschränkt was mich gerade echt aufregt! die Punkte befinden sich in 2D in form von X/Y-Koordinaten, vielleicht habe ich mich da unpräzise ausgedrückt. Wenn sich später die Punkte noch einem Cluster zuordnen lassen wäre das natürlich klasse 🙂

    Danke und ciao,
    Simon



  • Jaha, 1D ist das natürlich einfach, die Einschränkung hatte ich total verdrängt.

    #1: Lineare Regression => Ausgleichsgerade (http://de.wikipedia.org/wiki/Lineare_Regression)
    #2: Punkte auf Ergebnisgerade projizieren, fortan nur noch Parameter t für die Punkte als Koordinate denken (http://de.wikipedia.org/wiki/Orthogonalprojektion)
    (Gedanklich ist das also ein Schnitt in der 2D-Potentialfunktion)
    #3: Tiefpass für Scotts Formel festlegen
    #4: Scott's Formel für alle Punkte auswerten (Das ordnet jedem Punkt das lokale Potential zu)
    #5: Punkte suchen, zwischen denen eine Überschneidung von < Grenzwert und > Grenzwert stattfindet.
    Links oder rechts davon liegt entsprechend ein Cluster (Beispielsweise hat Punk 0 ein Potential von 1.3, Punkt 2 hat ein Potential von 2.7 und Dein Grenzwert ist 2. Damit ist klar, dass Punkt 2 der erste Punkt in einem Cluster ist.

    Edit: Für deinen Fall ist der Cosinus ein schlechtes Maß. Der wäre nur gut, wenn die Punkte auf einem Kreis angeordnet sind. Dann ähnelt der Cosinus auch in etwa der Gleichverteilung aus dem Umfang um den Punkt herum, also gedanklich. Der Kosinus zwischen den Ortsvektoren zweier Punkte ist ja davon abhängig, wo man den Nullpunkt hinlegt....

    Edit #2: Wenn die Punkte schon so ziemlich nah auf einer Geraden liegen, kannst Du Dir die Regression sparen, ohne dass sich an der Genauigkeit viel tut. Hauptsache, du kannst sie irgendwie "in eine Reihenfolge" bringen.



  • Hi,

    das musste erst durch meine Hirnwindungen durch 😉
    Nein ich muss sagen, ich finde diese Herangehensweise mit dem "Punkteverschmieren" und "Wolkenbildung" ganz cool.
    Aber bei mir scheitert es da gnadenlos an der Implementation...
    Ich stelle mir das so vor, die X/Y Koordinaten als Punkt in eine Matrix zu übersetzen:

    00000
    00000
    00P00
    00000
    00000
    //P wird hier exemplarisch zu 9 
    //+ Tiefpassfilter
    33333
    37773
    37973
    37773
    33333
    

    Allerdings wird die Auflösung der Matrix etwas besser ausfallen als in dem Beispiel. Wie implementiert man denn jetzt, dass kreisförmig drum herum die Werte erhöht werden?

    Ciao,
    Simon



  • Mir ist gerade aufgefallen, dass es mit der Taktik auch nicht leicht ist, die Cluster zu finden. Und zwar mag das Potential aufeinander folgender Punkte zwar größer als eine Konstante sein, aber zwischen den Punkten könnte die Potentialfunktion trotzdem unter die Grenze fallen. So würde man sie fälschlicherweise zu einem Cluster zählen. Für den Fall einer von einem Rechteck unterschiedlichen Tiefpassfunktion wird es also auch irgendwie wieder aufwendig.

    Also sofern Du die Cluster brauchst und da schon lauffähigen Code hast, würde ich noch getSimilarity vom Euclidean-Maß implementieren und dieses mit dem fertig implementierten und funktionierenden Algo verwenden. 😃



  • Zu der Frage ob deine Daten 'zufällig' sind oder nicht, solltest du dir erstmal überlegen, was du mit 'zufällig' genau meinst und diese Hypthose dann gezielt testen.
    Falls du z.B. zeigen willst, dass die Daten nicht gleichverteilt entlang der Ausgleichsgerade liegen,
    dann projeziere eben auf die Ausgleichsgerade und teste auf Gleichverteilung mit irgendeinem Standardtest.
    (Kolmogorov-Smirnov, chi^2, ...)

    Falls du dann nen relativ kleinen p-Wert rausbekommst, kannst du argumentieren,
    dass die Daten mit hoher Wahrscheinlichkeit nicht aus einer Gleichverteilung kommen.
    (genaugenommen falsch, aber das ist die allgemein anerkannte Vorgehensweise 😉 )



  • Hi Leute,

    danke nochmals für eure Ratschläge.
    Decimad: ich war zu "faul" so eine Matrix zu implementieren, deswegen habe ich mit der CImg-Library einfach Kreise zu den entsprechenden Koordinaten gemalt (Opacity = 0.2) und dann nochmal Blur drüber laufen lassen. Das ergab dann schöne "Cluster-Nebel". Dort ist mir dann aber am praktischen Beispiel auch genau das Problem untergekommen, wie du es geschildert hast.

    Ich habe mal weiter im Netz geschaut und ein weiteres Beispiel gefunden und es auch schonmal ausprobiert, es funktioniert so weit ganz gut. Ich muss aber eingestehen, dass ich durch den Code noch nicht ganz durchgestiegen bin und ich auch die angelegten Datenstrukturen noch nicht ganz verstehe. Es clustert zwar, aber ich bin noch nicht dazu gekommen auf einzelne Cluster und ihre zugehörigen Punkte "zuzugreifen".
    http://biarri.blogspot.de/2011/08/spatial-clustering-in-c-post-2-of-5.html

    C14: ja, da gebe ich dir völlig recht! Und einen ähnlichen Ansatz habe ich auch schon implementiert und zwar habe ich zwischen jeden Punkt die Distanzen ausgerechnet und dann aus dieser Matrix die Minimaldistanzen extrahiert. Wenn es sich um keine Normalverteilung sondern um Cluster handelt, dann müssten sich die Distanzen gegenüber einer Normalverteilung in kleinere Bereiche verschieben. Habe die Daten zwar, habe das aber nach diesem Muster noch nicht analysiert, weil ich das dichtebasierte Clustern gerne verstehen würde. Blöde gegenfrage: wieso ist das genaugenommen falsch aber als richtig anerkannt?

    Viele Grüße,
    Simon



  • Die fertigen Cluster-Listen schmeißt er in seiner Implementierung wieder weg. Aber man kann sie anhand der m_nCluster-Member der einzelnen Punkte (Nodes) wieder rekonstruieren.

    KD-Tree ist "nur" ein Baum, dee die Geometrische Region abwechselnd entlang der Hauptachsen so unterteilt, dass die entstehenden Untermengen _ungefähr_ gleichviele Elemente enthalten. Damit kann man anschließend schnell Punkte in der Nähe suchen (Der Sinn wird sich Dir wahrscheinlich erschließen), außerdem spart man sich die n²-Matrix aus Deinem letzten Beispiel, wenn ich das denn richtig gedeutet hatte.



  • @PCMan
    Zu deiner Gegenfrage:

    Man kann über die Wahrscheinlichkeit, dass die Daten nicht aus einer Gleichverteilung stammen ohne Vorwissen nichts sagen.

    Was man bei so einem Test berechnen kann ist nur die bedingte Wahrscheinlichkeit P(Test sagt 'keine Gleichverteilung' | Daten stammen aus Gleichverteilung).

    Um daraus auf P(Daten stammen aus Gleichverteilung | Test sagt 'keine Gleichverteilung') zu schließen, musst du mit der Bayes-Formel umrechnen.
    Dazu brauchst du Vorwissen P(Daten stammen aus Gleichverteilung).

    Wenn man das Testergebnis als Wahrscheinlichkeit dafür interpretiert, dass die Daten aus einer Gleichverteilung stammen, dann geht man implizit davon aus, dass P(Daten stammen aus Gleichverteilung)=0.5,
    sprich dass man den Test im Durchschnitt gleich oft auf Daten anwendet, die tatsächlich aus einer Gleichverteilung stammen wie auf welche, die nicht aus einer Gleichverteilung stammen.
    Wie gerechtfertigt das ist, hängt wohl vom Einsatzgebiet ab.
    Hoffe das verwirrt nicht zu sehr, will nur sagen, dass man bei der Interpretation von Testergebnissen sehr vorsichtig sein muss.



  • Hi,

    eine Weile ist's her aber ich habe das Beispiel jetzt mal in eine einfache Klasse eingebettet. Bestünde am Code hier interesse, so würde ich ihn hier posten? Bisher clustert es auch ganz vernünftig...

    Noch eine Frage: das mit dem KD-Tree habe ich noch nicht so ganz verstanden, wie funktioniert das? Oder gibt es dazu irgendeine verständliche Beschreibung im Netz?

    Besten Dank,
    Simon


Log in to reply