Como encontrar os locais mais espalhados?

Provavelmente uma pergunta muito simples. Eu tenho uma lista de cerca de mil locais geográficos em potencial (lat lon) e desses preciso selecionar os 200 locais que estão "mais espalhados". Eu acho que seriam os 200 pontos com maior distância média total. Pense em lojas em uma cidade.

Existe um método definido para fazer isso? Talvez em um pacote R?

Obrigado a todos que fazem deste o ótimo lugar para aprender!

/ Chris

Pergunta simples, solução difícil.

O melhor método que conheço usa o recozimento simulado (usei isso para selecionar algumas dezenas de milhares de pontos e é extremamente bom para selecionar 200 pontos: o dimensionamento é sublinear), mas isso requer codificação cuidadosa e experimentação considerável, como bem como uma enorme quantidade de computação. Você deve começar analisando métodos mais simples e rápidos primeiro para verificar se eles serão suficientes.

Uma maneira é primeiro agrupar os locais das lojas . Dentro de cada cluster, selecione a loja mais próxima do centro do cluster.

Um método de cluster muito rápido é o K-means . Aqui está uma Rsolução que a 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],]
}

Os argumentos para scattersão uma lista dos locais das lojas (como uma matriz n por 2) e o número de lojas a serem selecionadas (por exemplo, 200). Retorna uma matriz de locais.

Como exemplo de sua aplicação, vamos gerar n = 1000 lojas localizadas aleatoriamente e ver como é a solução:

# 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 levou 0,03 segundos:

Você pode ver que não é ótimo (mas também não é tão ruim). Para fazer muito melhor, serão necessários métodos estocásticos, como recozimento simulado, ou algoritmos que provavelmente escalarão exponencialmente com o tamanho do problema. (Eu implementei esse algoritmo: leva 12 segundos para selecionar os 10 pontos mais amplamente espaçados de 20. A aplicação a 200 clusters está fora de questão.)

Uma boa alternativa ao K-means é um algoritmo hierárquico de agrupamento; tente o método "Ward" primeiro e considere experimentar outros vínculos. Isso exigirá mais computação, mas ainda estamos falando de apenas alguns segundos para 1000 lojas e 200 clusters.

Existem outros métodos. Por exemplo, você pode cobrir a região com uma grade hexagonal regular e, para células que contêm uma ou mais lojas, selecionar a loja mais próxima do seu centro. Brinque um pouco com o tamanho da célula até que aproximadamente 200 lojas tenham sido selecionadas. Isso produzirá um espaçamento muito regular das lojas, que você pode ou não querer. (Se esses são realmente locais de lojas, isso provavelmente seria uma solução ruim, porque tenderia a escolher lojas nas áreas menos populosas. Em outros aplicativos, pode ser uma solução muito melhor.)