Comment trouver les emplacements les plus dispersés?

Probablement une question très simple. J'ai une liste d'environ mille emplacements géographiques potentiels (lat lon), et de ceux dont j'ai besoin pour sélectionner les 200 emplacements qui sont "les plus dispersés". Je pense que ce serait les 200 points avec la distance moyenne totale la plus élevée. Pensez aux magasins dans une ville.

Existe-t-il une méthode définie pour le faire? Peut-être dans un R-package?

Merci à tous ceux qui en font le lieu idéal pour l'apprendre!

/ Chris

Question simple, solution difficile.

La meilleure méthode que je connaisse utilise un recuit simulé (je l'ai utilisé pour sélectionner quelques dizaines de points sur des dizaines de milliers et il évolue extrêmement bien pour sélectionner 200 points: la mise à l'échelle est sublinéaire), mais cela nécessite un codage soigneux et une expérimentation considérable, comme ainsi qu'une énorme quantité de calcul. Vous devriez commencer par regarder d'abord des méthodes plus simples et plus rapides pour voir si elles suffiront.

Une façon consiste d'abord à regrouper les emplacements de magasin . Dans chaque cluster, sélectionnez le magasin le plus proche du centre de cluster.

Une méthode de clustering très rapide est K-means . Voici une Rsolution qui l'utilise.

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],]
}

Les arguments de scattersont une liste d'emplacements de magasins (sous forme d'une matrice n par 2) et le nombre de magasins à sélectionner (par exemple, 200). Il renvoie un tableau d'emplacements.

Comme exemple de son application, générons n = 1000 magasins situés au hasard et voyons à quoi ressemble la solution:

# 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))

Ce calcul a pris 0,03 seconde:

Vous pouvez voir que ce n'est pas génial (mais ce n'est pas trop mal non plus). Pour faire beaucoup mieux, il faudra soit des méthodes stochastiques, comme le recuit simulé, soit des algorithmes susceptibles d'évoluer de façon exponentielle avec la taille du problème. (J'ai implémenté un tel algorithme: il faut 12 secondes pour sélectionner les 10 points les plus espacés sur 20. Il n'est pas question de l'appliquer à 200 clusters.)

Une bonne alternative à K-means est un algorithme de clustering hiérarchique; essayez d'abord la méthode de «Ward» et envisagez d'expérimenter d'autres liens. Cela prendra plus de calcul, mais nous parlons encore de quelques secondes pour 1000 magasins et 200 clusters.

D'autres méthodes existent. Par exemple, vous pouvez couvrir la région avec une grille hexagonale régulière et, pour les cellules contenant un ou plusieurs magasins, sélectionner le magasin le plus proche de son centre. Jouez un peu avec la taille de la cellule jusqu'à ce que 200 magasins environ soient sélectionnés. Cela produira un espacement très régulier des magasins, que vous souhaiterez ou non. (Si ce sont vraiment des emplacements de magasins, ce serait probablement une mauvaise solution, car cela aurait tendance à choisir des magasins dans les zones les moins peuplées. Dans d'autres applications, cela pourrait être une bien meilleure solution.)