Das Filtern entfernt in der Nähe Punkte aus einer Liste

https://stackoverflow.com/questions/416406

03-07-2019
|

Frage

I href="https://stackoverflow.com/questions/411837/finding-clusters-of-mass-in-a-matrix-bitmap#411855"> Halb beantwortet eine Frage über die Suche nach Clustern von Massen . Ich sage halb beantwortet, weil ich es in einem Zustand verlassen, wo ich alle Punkte in den Bitmap Massen sortiert hatte und überließ es den Leser die Liste zu entfernen Punkte aus demselben Cluster zu filtern.

Dann, wenn über diesen Schritt denke ich, dass die Lösung nicht gefunden mir herausspringen hätte, wie ich dachte, es würde. So, jetzt bitte ich euch um Hilfe. Wir haben eine Liste von Punkten mit Massen wie so (eine Python-Liste von Tupeln, aber Sie können es darstellen, wie Sie in jeder Sprache richtig halten):

[ (6, 2, 6.1580555555555554),
  (2, 1, 5.4861111111111107),
  (1, 1, 4.6736111111111107),
  (1, 4, 4.5938888888888885),
  (2, 0, 4.54),
  (1, 5, 4.4480555555555554),
  (4, 7, 4.4480555555555554),
  (5, 7, 4.4059637188208614),
  (4, 8, 4.3659637188208613),
  (1, 0, 4.3611111111111107),
  (5, 8, 4.3342191043083904),
  (5, 2, 4.119574829931973),
  ...
  (8, 8, 0.27611111111111108),
  (0, 8, 0.24138888888888888) ]

Jedes Tupel ist von der Form:

(x, y, mass)

Beachten Sie, dass die Liste hier sortiert ist. Wenn Ihre Lösung vorzieht, sie nicht zu haben sortiert es ist vollkommen in Ordnung.

Die Herausforderung, wenn Sie erinnern, ist zu finden Sie die wichtigsten Cluster der Masse. Die Anzahl der Cluster ist nicht bekannt. Aber Sie kennen die Dimensionen der Bitmap. Manchmal mehrere Punkte innerhalb eines Clusters haben mehr Masse als die Mitte der nächsten (in der Größe) Cluster. Also, was ich tun möchte, ist gehen von den höheren Massenpunkten und entfernen Punkte im gleichen Cluster (Punkte in der Nähe).

Als ich das versuchte ich schließlich durch Teile der Liste über zu gehen, die nach oben und immer wieder. Ich habe ein Gefühl, das ich, wenn ich nur dumm bin. Wie würdest du es machen? Pseudo-Code oder echter Code. Natürlich kann, wenn man nur ausziehen, wo ich mit Python-Code in dieser Antwort ließ es einfacher für mich damit zu experimentieren.

Der nächste Schritt ist, um herauszufinden, wie viele Cluster gibt es wirklich in der Bitmap sind. Ich bin immer noch mit der Definition dieses Problem zu kämpfen, damit ich mit einer Frage über sie zurückkehren könnten.

EDIT: Ich soll klarstellen, dass ich weiß, dass es auf diese Frage keine „richtige“ Antwort ist. Und der Name der Frage ist der Schlüssel. Phase eins der mein Clustering erfolgt. Im auf der Suche nach einem schnellen, in der Nähe gelegene accurate- "genug" Verfahren zum Filtern entfernt.

Lassen Sie mich wissen, wenn Sie sehen, wie ich kann die Frage klarer machen.

Lösung

Nur damit Sie wissen, fragen Sie nach einer Lösung zu einem schlecht gestellten Problem: keine endgültige Lösung existiert. Das ist in Ordnung ... es einfach macht es mehr Spaß. Ihr Problem ist schlecht gestellte vor allem, weil Sie nicht wissen, wie viele Cluster Sie wollen. Clustering ist einer der wichtigsten Bereiche des maschinellen Lernens und eine ganz wenige Ansätze, die im Laufe der Jahre entwickelt wurden.

Wie Arachnidus wies darauf hin, der k-means Algorithmus neigt dazu, ein guter zu sein und es ist ziemlich einfach zu implementieren. Die Ergebnisse hängen entscheidend von der anfänglichen Schätzung gemacht und von der Anzahl der gewünschten Cluster. Um das anfängliche Vermutung Problem zu überwinden, ist es üblich, den Algorithmus oft mit zufälligen Initialisierungen laufen und das beste Ergebnis holen. Sie müssen, was bedeutet „beste“ definieren. Eine Maßnahme wäre der mittlere quadratische Abstand von jedem Punkt seines Clusterzentrum. Wenn Sie automatisch erraten wollen, wie viele Cluster gibt, sollten Sie den Algorithmus mit einer ganzen Reihe von Zahlen von Clustern laufen. Für jede gute „beste“ Maßnahme werden mehr Cluster immer besser aussehen als weniger, so dass Sie einen Weg zu viele Cluster zu bestrafen, müssen mit. Die MDL Diskussion Wikipedia ist ein guter Ausgangspunkt.

K-Means-Clustering ist im Grunde das einfachste Mischmodell . Manchmal ist es hilfreich, eine Mischung von Gauß-Funktionen durch Erwartungsmaximierungs gelernt zu aktualisieren (in dem Link beschrieben nur gegeben). Dies kann robuster sein als k-Mittel. Es dauert ein wenig mehr Mühe, es zu verstehen, aber wenn Sie tun, es ist nicht viel schwieriger als k-Mittel zu implementieren.

Es gibt viele andere Clustering-Techniken wie häuften Bündelung und spektralen Clustering. Agglomerative Clustering ist ziemlich einfach zu implementieren, aber die Wahl, wenn kann tückisch sein, den Aufbau der Cluster zu stoppen. Wenn Sie häuften Bündelung tun, werden Sie wahrscheinlich wollen, betrachten kd Bäume schneller nächste Nachbarn suchen. smacl Antwort beschreibt eine etwas andere Art und Weise zu tun, angehäufte Bündelung ein Voronoi-Diagramm verwendet wird.

Es gibt Modelle, die automatisch die Anzahl der Cluster für Sie wie diejenigen auswählen können, basierend auf Latent Dirichlet Allocation , aber sie sind viel schwieriger zu ein richtig zu verstehen implementieren.

Sie möchten vielleicht auch auf der sehen Mean-Shift Algorithmus, um zu sehen, ob es näher an, was Sie wirklich wollen.

Andere Tipps

Es klingt für mich wie Sie suchen die K-Means Algorithmus.

Wie ich im Kommentar zu Ihrer Frage erwähnte, ist die Antwort basierend darauf, ob oder nicht Masse kann Skalar in diesem Zusammenhang betrachtet werden. Wenn ja, Farbe basierte Lösungen werden wahrscheinlich nicht so Farbe zur Arbeit gehen wird oft nicht genommen als Skalar sein.

Zum Beispiel, wenn ich einen bestimmten Bereich mit 1 Punkt hoher Masse habe, ist, dass das gleiche wie die gleiche Fläche mit 10 Punkten von 1/10 mit der Masse? Wenn dies wahr ist, wird Masse in diesem Zusammenhang nicht Skalar, und ich würde bei einem Algorithmus zum räumlichen gouping ähnlichen nicht-skalierbaren Werten verwendet aussehen neigt, z.B. voronoi Diagramme .

In diesem Fall, wo zwei benachbarte voronoi Bereiche ein enges genug Masse Spiel und Abstand haben, können sie zusammen gruppiert werden. Sie können dies wiederholen alle Cluster zu finden.

Wenn auf der anderen Seite, Ihre Masse ist skalierbar, oder dass die Masse an einer unbekannten Position kann aus dem umliegenden Punkten interpoliert werden, würde ich dazu neigen,

Das klingt wie Farbe Quantisierung, in dem Sie die Anzahl der Farben in einem Bild zu reduzieren. Eine Möglichkeit wäre es, die Farben im Raum zu zeichnen, und kombinieren Cluster in der Mitte (oder ein gewichteter Mittelwert) eines Clusters.

Der genaue Name des Algorithmus, der diese Erinnerung versagt mir ausgelöst, aber ich werde die Antwort bearbeiten, wenn es erscheint, aber in der Zwischenzeit sollten Sie bei Farbquantisierung und sehen, ob einige der Algorithmen nützlich sind.

Beginnen Sie mit dem " Convex Hull " -Problem. Sie sind auch für einige „konvexe Hülle“ -ähnlichen Cluster suchen.

Beachten Sie, dass „Cluster“ vage ist. Sie haben eine durchschnittliche Masse im gesamten Feld. Ein paar Punkte sind überdurchschnittlich Masse, und einige unter dem Durchschnitt. Wie weit über dem Durchschnitt bedeutet, Sie haben einen Cluster gefunden? Wie weit auseinander tun Knoten sein müssen Teil eines Clusters oder ein separater Cluster zu sein?

Was ist der Unterschied zwischen zwei Berggipfeln und einem Grat?

Sie haben eine „Topographie“ berechnen - alle Punkte mit gleicher Dichte in Regionen verbinden. Dies erfordert, dass Sie einen Punkt holen und Ihr wollen arbeiten radial von einem Punkt aus, Ortung Positionen, wo die Dichten gleich sind. Sie können diese Punkte in Regionen verbinden.

Wenn Sie Ihren Ausgangspunkt mit Bedacht ausgewählt, sollten die Regionen Nest. Ihren Ausgangspunkt Picking ist einfach, weil man auf lokale Hochs.

starten

Da Sie sprechen schon von Masse, warum nicht eine Schwerkraft-basierte Lösung. Ein einfaches Partikel-System würde nicht super genau sein müssen, und Sie würden es nicht laufen zu lange müssen für bevor Sie eine viel bessere Schätzung über die Zahl der Cluster machen könnte.

Wenn Sie eine bessere Vorstellung über Clusternummern haben, k-means nächste Nachbarn möglich werden.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow