Búsqueda de un número conocido de círculo centros de maximizar el número de puntos dentro de una distancia fija

Question

Tengo un conjunto de 2-D de datos donde quiero encontrar a los centros de un número determinado de centros de círculos ($N$) que maximiza el número total de puntos dentro de una distancia especificada ($R$).

por ejemplo, he de 10.000 puntos de datos $(X_i, Y_i)$ y quiero encontrar a los centros de $N=5$ círculos que capturar tantos puntos como sea posible dentro de un radio de $R=10$. El 5 centros y radio de 10 está dado de antemano, no se deriva de los datos.

La presencia de un punto de datos dentro de un círculo es un binario/o la proposición. Si $R=10$, no hay ninguna diferencia en el valor a un punto de las 11 unidades de distancia frente a 100 unidades de distancia, ya que se trata de > 10. Del mismo modo para los que están dentro del círculo, no hay ningún valor extra al estar cerca del centro de la frente, cerca de la orilla. Un punto de datos se encuentra en uno de los círculos o fuera.

Es un algoritmo que puede ser usado para resolver este problema? Estos parece estar relacionado con técnicas de clustering, pero en lugar de minimizar la distancia media, la "distancia" de la función es 0 si el punto está dentro de $R$ de cualquiera de las $N$ puntos, y 1 en caso contrario.

Mi preferencia sería encontrar una manera de hacer esto en R, pero cualquier enfoque sería apreciada.

Answer 1

Esta es una variación de k-means problema. La radio de los centros no importa, siempre y cuando se supone que son iguales.

Enlaces:

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

Se pondrá a los centros de los círculos en los lugares de mayor probabilidad de los puntos.

Clásico Procedimiento K-medios:

1. clúster de conjunto de contar hasta 5
2. poner cada punto en un clúster de azar
3. para cada cluster, calcular la posición media
4. para cada punto, se calcula la distancia a cada nueva posición media
5. la calidad de miembro asociado con el clúster más cercano
6. repita hasta que esté hecho (iteraciones, cambio de posición, o de otro error métrico)

Opciones:

• Usted puede utilizar algunas de relajación después de 3, donde se traduce la posición media lentamente hacia la nueva posición.
• este es un sistema discreto para que no convergen a la perfección. A veces lo hace y se puede terminar en los puntos de parada cambio de miembros, pero a veces sólo se mueva un poco.
• Si usted está haciendo su propio código (como la mayoría de la gente debería), entonces usted puede utilizar el POR k-means anteriormente como punto de partida, y hacer alguna variación en EM informado por ciento de los puntos en exclusiva y totalmente abarcado por los círculos.

Por qué K-means ataca el problema:

• Es el equivalente de la instalación de un Modelo de Mezcla de Gaussianas donde las covarianzas de los componentes son iguales. Los centros de los componentes de la mezcla va a estar situado en los puestos de más alta expectativa de puntos. Las curvas de constante probabilidad van a ser los círculos. Este es el algoritmo EM por lo que tiene la convergencia asintótica. Las membresías son duros, no de software.
• Yo creo que si el supuesto fundamental de la igualdad de la varianza de los componentes del modelo de mezcla es razonablemente "cerrar", lo que significa que, a continuación, este método va a encajar. Si usted acaba de distribuir al azar puntos, es menos probable que se ajustan bien.

Debe haber algún análogo de un "Cero Inflado de Poisson" donde hay un componente que no es gaussiana que se recoge la distribución uniforme.

Si usted quería para "sintonizar" modelo y estaban seguros de que había suficientes puntos de la muestra, a continuación, usted puede inicializar con el k-means, y, a continuación, hacer un aumentada k-means ajustador que elimina los puntos fuera de los radios de los círculos de la competencia. Sería ligeramente perturbar los círculos que usted tiene, pero podría haber mejorado ligeramente el rendimiento de la vista de los datos.

Answer 2

Alguien tiene probablemente una mejor formal de algoritmo, pero aquí es una aproximación de fuerza bruta (un hack?). Yo uso uno de la hexagonal binning algoritmos para calcular un histograma 2D. Como hexbin en R.

Yo uso un hexágono tamaño que había aproximadamente circunscribir su círculo de radio R y, a continuación, ordenar en los primeros N cubos. Si tienes N distintos lejos de las bandejas, gran. Ahora es una forma de moverse sobre el círculo de forma local en un 2*R escala (en las direcciones x e y) desde el centro de la parte superior de la densidad de hexágonos. Computación densidades pueden casi optimizar la posición local. Esto explica el hecho de que los hexágonos no eran una ventana móvil con respecto al fijo origen.

Si todos los contenedores están cerca de usted tendría que tener alguna forma más inteligente de movimiento de los círculos en los alrededores.

Tenga en cuenta que no puedo pensar en varios casos de esquina donde un ingenuo estrategia espectacularmente fallar. Sin embargo, sólo un punto de partida.

Mientras tanto, espero que alguien tiene un mejor algoritmo.