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

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 .$N$$R$

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.$(X_i, Y_i)$$N=5$$R=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.$R$$N$

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

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

Links:

• http://en.wikipedia.org/wiki/K-means_clustering
• http://stat.ethz.ch/R-manual/R-devel/library/stats/html/kmeans.html

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.

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.