¿Cómo encontrar los lugares más dispersos?

Probablemente una pregunta muy simple. Tengo una lista de aproximadamente mil ubicaciones geográficas potenciales (lat lon), y de esas necesito seleccionar las 200 ubicaciones que están "más dispersas". Creo que serían los 200 puntos con la distancia promedio total más alta. Piensa en las tiendas de una ciudad.

¿Hay un método definido para hacerlo? Tal vez en un paquete R?

¡Gracias a todos por hacer de este el gran lugar para aprender!

/ Chris

Pregunta simple, solución difícil.

El mejor método que conozco es el recocido simulado (lo he usado para seleccionar unas pocas docenas de decenas de miles y se escala extremadamente bien para seleccionar 200 puntos: la escala es sublineal), pero esto requiere una codificación cuidadosa y una considerable experimentación, ya que así como una gran cantidad de computación. Debería comenzar por buscar métodos más simples y rápidos primero para ver si serán suficientes.

Una forma es primero agrupar las ubicaciones de las tiendas . Dentro de cada grupo seleccione la tienda más cercana al centro del grupo.

Un método de agrupamiento realmente rápido es K-means . Aquí hay una Rsolución que lo usa.

scatter <- function(points, nClusters) {
    #
    # Find clusters.  (Different methods will yield different results.)
    #
    clusters <- kmeans(points, nClusters)
    #
    # Select the point nearest the center of each cluster.
    #
    groups <- clusters$cluster
    centers <- clusters$centers
    eps <- sqrt(min(clusters$withinss)) / 1000
    distance <- function(x,y) sqrt(sum((x-y)^2))
    f <- function(k) distance(centers[groups[k],], points[k,])
    n <- dim(points)[1]
    radii <- apply(matrix(1:n), 1, f) + runif(n, max=eps)
    # (Distances are changed randomly to select a unique point in each cluster.)
    minima <- tapply(radii, groups, min)
    points[radii == minima[groups],]
}

Los argumentos para scatterson una lista de ubicaciones de tiendas (como una matriz de n por 2) y el número de tiendas para seleccionar (por ejemplo, 200). Devuelve una variedad de ubicaciones.

Como ejemplo de su aplicación, generemos n = 1000 tiendas ubicadas al azar y veamos cómo se ve la solución:

# Create random points for testing.
#
set.seed(17)
n <- 1000
nClusters <- 200
points <- matrix(rnorm(2*n, sd=10), nrow=n, ncol=2)
#
# Do the work.
#
system.time(centers <- scatter(points, nClusters))
#
# Map the stores (open circles) and selected ones (closed circles).
#
plot(centers, cex=1.5, pch=19, col="Gray", xlab="Easting (Km)", ylab="Northing")
points(points, col=hsv((1:nClusters)/(nClusters+1), v=0.8, s=0.8))

Este cálculo tomó 0.03 segundos:

Puedes ver que no es genial (pero tampoco es tan malo). Hacer mucho mejor requerirá métodos estocásticos, como recocido simulado, o algoritmos que probablemente se escalen exponencialmente con el tamaño del problema. (He implementado un algoritmo de este tipo: toma 12 segundos seleccionar los 10 puntos más espaciados entre 20. Aplicarlo a 200 grupos está fuera de discusión).

Una buena alternativa a K-means es un algoritmo de agrupamiento jerárquico; pruebe primero el método de "Ward" y considere experimentar con otros vínculos. Esto requerirá más cómputo, pero aún estamos hablando de unos pocos segundos para 1000 tiendas y 200 clústeres.

Existen otros métodos. Por ejemplo, podría cubrir la región con una cuadrícula hexagonal regular y, para las celdas que contienen una o más tiendas, seleccionar la tienda más cercana a su centro. Juegue un poco con el tamaño de celda hasta que se hayan seleccionado aproximadamente 200 tiendas. Esto producirá un espaciado muy regular de las tiendas, que puede querer o no. (Si se trata realmente de ubicaciones de tiendas, probablemente esta sería una mala solución, ya que tendría una tendencia a elegir tiendas en las áreas menos pobladas. En otras aplicaciones, esta podría ser una solución mucho mejor).