Finden einer bekannten Anzahl von Kreismittelpunkten, die die Anzahl von Punkten innerhalb eines festen Abstands maximieren

10

Ich habe einen Satz von 2D-Daten, in denen ich die Zentren einer bestimmten Anzahl von Kreismittelpunkten ( ) finden möchte , die die Gesamtzahl der Punkte innerhalb eines bestimmten Abstands ( ) maximieren .NR

Ich habe zB 10.000 Datenpunkte und möchte die Zentren von Kreisen finden, die so viele Punkte wie möglich in einem Radius von erfassen . Die 5 Zentren und der Radius von 10 werden vorher angegeben und nicht aus den Daten abgeleitet.(Xi,Yi)N=5R=10

Das Vorhandensein eines Datenpunkts innerhalb eines Kreises ist ein binärer Entweder-Oder-Satz. Wenn , gibt es keinen Wertunterschied zu einem Punkt, der 11 Einheiten entfernt ist, gegenüber 100 Einheiten, da beide> 10 sind. Ebenso gibt es keinen zusätzlichen Wert, wenn Sie sich innerhalb des Kreises befinden, nahe der Mitte oder nahe der Kante . Ein Datenpunkt befindet sich entweder in einem der Kreise oder außerhalb.R=10

Gibt es einen guten Algorithmus, mit dem dieses Problem gelöst werden kann? Diese scheinen mit Clustering-Techniken in Zusammenhang zu stehen, aber anstatt die durchschnittliche Entfernung zu minimieren, ist die "Entfernungs" -Funktion 0, wenn der Punkt innerhalb von eines der Punkte liegt, und ansonsten 1.RN

Ich würde es vorziehen, einen Weg zu finden, dies in R zu tun, aber jeder Ansatz wäre willkommen.

Colonel.triq
quelle
Ist eine Kreisüberlappung zulässig?
neugierige Katze
1
Dies ist im Wesentlichen eine Nachbarschaftsoperation (oder eine Fokusoperation) für ein Raster-Dataset. Es wäre gut, die GIS-Site zu überprüfen, um festzustellen, ob sie beantwortet wurde, und R-Pakete zu untersuchen, um eine Rasteranalyse durchzuführen.
Andy W
1
Kreisüberlappung ist zulässig, aber die von beiden Kreisen abgedeckten Datenpunkte werden nicht doppelt gezählt. Vielen Dank für den Hinweis auf die Nachbarschafts- / Fokusoperation für Raster-Datasets. Ich werde nach etwas in dieser Richtung suchen.
Colonel.triq
@Andy W Obwohl fokale Operationen natürlich an einer Lösung beteiligt wären, liegt diese Frage außerhalb des Fachwissens der GIS-Community, IMHO, da es sich wirklich um ein (ziemlich schwieriges) Optimierungsproblem handelt. Es ist kein einfaches Finden des Maximums eines Fokusmittelwerts. Ich würde empfehlen, es eine Weile hier zu lassen und dann, wenn sich keine zufriedenstellende Lösung ergibt, auf eine programmierorientierte Site zu migrieren.
whuber
.... oder auf math.overflow migrieren? Sie könnten auch einige Einsichten darüber haben.
neugierige Katze

Antworten:

1

Dies ist ein Variations-K-Mittel-Problem. Der Radius der Zentren spielt keine Rolle, solange sie als gleich angenommen werden.

Links:

Die Zentren der Kreise werden an Stellen mit der höchsten Wahrscheinlichkeit der Punkte platziert.

Klassisches K-Mittel-Verfahren:

  1. Setzen Sie die Clusteranzahl auf 5
  2. Setzen Sie jeden Punkt in einen zufälligen Cluster
  3. Berechnen Sie für jeden Cluster die mittlere Position
  4. Berechnen Sie für jeden Punkt den Abstand zu jeder neuen mittleren Position
  5. Verknüpfen Sie die Mitgliedschaft mit dem nächstgelegenen Cluster
  6. Wiederholen, bis dies erledigt ist (Iterationen, Positionsänderung oder andere Fehlermetrik)

Optionen:

  • Sie können nach 3 eine gewisse Unterentspannung verwenden, bei der Sie die mittlere Position langsam in Richtung der neuen Position verschieben.
  • Dies ist ein diskretes System, daher konvergiert es nicht perfekt. Manchmal ist es so und Sie können enden, wenn Punkte die Mitgliedschaft nicht mehr ändern, aber manchmal wackeln sie nur ein bisschen.
  • Wenn Sie Ihren eigenen Code erstellen (wie es die meisten Leute tun sollten), können Sie die oben genannten POR-k-Mittel als Ausgangspunkt verwenden und eine Variation der EM vornehmen, die durch Prozent der Punkte ausschließlich und vollständig von den Kreisen erfasst wird.

Warum K-means das Problem angreift:

  • Dies entspricht der Anpassung eines Gaußschen Mischungsmodells, bei dem die Kovarianzen der Komponenten gleich sind. Die Zentren der Mischungskomponenten werden an den Positionen mit der höchsten Erwartung von Punkten liegen. Die Kurven konstanter Wahrscheinlichkeit werden Kreise sein. Dies ist ein EM-Algorithmus, der eine asymptotische Konvergenz aufweist. Die Mitgliedschaften sind hart, nicht weich.
  • Ich denke, wenn die Grundannahme des Mischungsmodells für Komponenten gleicher Varianz einigermaßen "nahe" ist, was auch immer das bedeutet, dann wird diese Methode passen. Wenn Sie Punkte nur zufällig verteilen, ist es weniger wahrscheinlich, dass sie gut passen.

Es sollte ein Analogon zu einem "Zero Inflated Poisson" geben, bei dem es eine nicht-gaußsche Komponente gibt, die die gleichmäßige Verteilung aufnimmt.

Wenn Sie Ihr Modell "abstimmen" wollten und sicher waren, dass genügend Abtastpunkte vorhanden sind, können Sie mit den k-Mitteln initialisieren und dann einen erweiterten k-Mittel-Einsteller erstellen, der Punkte außerhalb der Radien der Kreise aus dem Wettbewerb entfernt. Es würde die Kreise, die Sie haben, leicht stören, aber es könnte die Leistung angesichts der Daten leicht verbessern.

EngrStudent
quelle
Könnten Sie bitte etwas genauer erläutern, wie K-means dieses Problem löst?
whuber
Danke für den Vorschlag. Mir ist immer noch nicht klar, dass der K-Mittel-Ansatz das Problem löst? Betrachten Sie das Beispiel von drei Clustern normaler (0,1) generierter Daten, bei denen die Zentren um etwa 5 Einheiten versetzt sind. Die K-Mittel-Zentren würden die maximale Dichte ergeben. Schneiden Sie nun einige Punkte mit "Löchern" aus, sodass Daten entfernt werden, die näher als 0,5 an den Zentren liegen. K-means zeigt immer noch ungefähr die gleichen Zentren an, aber wenn Sie versuchen, eine maximale Abdeckung für N = 3, R = 0,5 zu erreichen, ist dies eindeutig nicht die richtige Antwort (da die Donut-Löcher keine Daten enthalten). Verstehe ich etwas falsch?
Colonel.triq
Ich werde Ihre Frage genauer untersuchen, um eine bessere Antwort zu erhalten, wenn ich Zeit habe. Ich erlaube gerne negative Gewichte. Sie können manchmal sowohl Datendonuts als auch radiale rationale Polynome verarbeiten.
EngrStudent
0

Jemand hat wahrscheinlich einen besseren formalen Algorithmus, aber hier ist ein Brute-Force-Ansatz (ein Hack?). Ich würde einen der hexagonalen Binning-Algorithmen verwenden, um ein 2D-Histogramm zu berechnen. Wie hexbinin R.

Ich würde eine Sechseckgröße verwenden, die Ihren Kreis mit dem Radius R grob umschreibt und dann nach den oberen N Behältern sortiert. Wenn Sie Nverschiedene weit entfernte Mülleimer haben, großartig. Eine Möglichkeit besteht nun darin, sich lokal auf einer 2 * R-Skala (in x- und y-Richtung) vom Zentrum der Sechsecke mit der höchsten Dichte um den Kreis zu bewegen. Durch die Berechnung der Dichte kann die Position lokal grob optimiert werden. Dies erklärt die Tatsache, dass die Sechsecke in Bezug auf einen festen Ursprung kein bewegliches Fenster waren.

Wenn alle oberen Behälter in der Nähe sind, müssten Sie Ihre Kreise in dieser Umgebung intelligenter bewegen.

Beachten Sie, dass ich mir mehrere Eckfälle vorstellen kann, in denen eine solch naive Strategie spektakulär scheitern wird. Doch nur ein Ausgangspunkt.

In der Zwischenzeit hoffe ich, dass jemand einen besseren Algorithmus hat.

neugierig_katze
quelle
1
So etwas könnte das Problem zumindest annähernd für einen Kreis lösen . (Dies kann leicht mithilfe von Fokuszählungen mit einem GIS durchgeführt werden.) Das Mehrkreisproblem wird jedoch nicht gelöst.
whuber
@whuber: Wie wäre es, nach einem Kreis zu lösen, dann alle Punkte, die innerhalb dieses Kreises liegen, zu löschen und dann den ursprünglichen Algorithmus zu wiederholen? Können Sie Situationen sehen, in denen dies fehlschlagen würde?
neugierige Katze
Ja, leicht. (Ihr ist ein "gieriger Algorithmus".) Betrachten Sie den Fall in einer Dimension mit Punkten bei . Ihr Algorithmus setzt der erste Kreis abdeckt und die zweite Abdeckung : acht Punkte in toto . Eine bessere Lösung umfasst mit einem Kreis und mit einem anderen: neun Punkte. 0 , 1 , 2 , 20 , 21 , 28 , 29 , 30 , 31 , 32 , 39 , 40 28 , 29 , 30 , 31 , 32 0 , 1 , 2 20 , 21 , 28 , 29 , 30, 30 , 31 , 32 ,R=10,N=20,1,2,20,21,28,29,30,31,32,39,4028,29,30,31,320,1,220,21,28,29,3030,31,32,39,40
whuber
@ Whuber: Stimmt. Du hast recht. Obwohl abhängig von der Struktur der Eingabepunkte in einigen (vielen?) Fällen die gierigen und nicht gierigen Lösungen identisch sein können oder nahe an? Ich weiß es nicht.
neugierige Katze
@whuber: Das Problem scheint meist an Grenzen. Was passiert , wenn ( ein wenig wie ich in meiner Antwort erwähnt) bewegt man sich das Fenster +Rund -Rdann setzt alle durchführbaren Lösungen auf einen Stapel und wählt unter ihnen. zB in Ihrem 1DBeispiel beim Auftreffen 28,29,30,31,32es das Fenster bis gleiten würde 18-28und 38-48suchen für alle machbar Lösungen. Dann kann man innerhalb dieser nach Kombinationen mit maximaler Punktausbeute suchen. Nicht sicher, ob das helfen würde? Ich versuche zu sehen, ob mein naiver Algorithmus gerettet werden kann. :)
neugierig_cat