Jak znaleźć najbardziej rozpowszechnione lokalizacje?

Prawdopodobnie bardzo proste pytanie. Mam listę około tysiąca potencjalnych lokalizacji geograficznych (lat lon) i spośród nich muszę wybrać 200 lokalizacji, które są „najbardziej rozproszone”. Myślę, że byłoby to 200 punktów z najwyższym całkowitym średnim dystansem. Pomyśl o sklepach w mieście.

Czy istnieje określona metoda, aby to zrobić? Może w pakiecie R?

Dziękujemy wszystkim, którzy sprawiają, że jest to świetne miejsce do nauki!

/ Chris

Proste pytanie, trudne rozwiązanie.

Najlepsza metoda, jaką znam, wykorzystuje symulowane wyżarzanie (użyłem tego, aby wybrać kilkadziesiąt punktów z dziesiątek tysięcy i bardzo dobrze skaluje się, wybierając 200 punktów: skalowanie jest podliniowe), ale wymaga to starannego kodowania i znacznych eksperymentów, ponieważ a także ogromną ilość obliczeń. Powinieneś zacząć od spojrzenia na prostsze, szybsze metody, aby zobaczyć, czy one wystarczą.

Jednym ze sposobów jest najpierw klastrowanie lokalizacji sklepów . W ramach każdego klastra wybierz sklep najbliższy centrum klastra.

Metoda jest bardzo szybko grupowania k-średnich . Oto Rrozwiązanie, które z niego korzysta.

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

Argumentami do scatterjest lista lokalizacji sklepów (jako macierz n na 2) i liczba sklepów do wyboru (np. 200). Zwraca tablicę lokalizacji.

Jako przykład jego zastosowania, wygenerujmy n = 1000 losowo zlokalizowanych sklepów i zobaczmy, jak wygląda rozwiązanie:

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

Obliczenia trwały 0,03 sekundy:

Widać, że to nie jest świetne (ale też nie jest tak źle). Osiągnięcie znacznie lepszych wyników będzie wymagało metod stochastycznych, takich jak symulowane wyżarzanie, lub algorytmów, które prawdopodobnie skalują się wykładniczo wraz z rozmiarem problemu. (Zaimplementowałem taki algorytm: wybranie 10 najbardziej rozstawionych punktów na 20 zajmuje 12 sekund. Zastosowanie go do 200 klastrów nie wchodzi w rachubę.)

Dobrą alternatywą dla K-średnich jest hierarchiczny algorytm grupowania; najpierw wypróbuj metodę „Totem” i rozważ eksperymentowanie z innymi powiązaniami. To zajmie więcej obliczeń, ale wciąż mówimy o zaledwie kilku sekundach dla 1000 sklepów i 200 klastrów.

Istnieją inne metody. Na przykład możesz objąć region zwykłą sześciokątną siatką, a dla komórek zawierających jeden lub więcej sklepów wybierz sklep najbliższy jego centrum. Graj trochę z rozmiarem komórek, aż zostanie wybranych około 200 sklepów. Spowoduje to bardzo regularne rozmieszczanie sklepów, które możesz chcieć lub nie. (Jeśli są to naprawdę lokalizacje sklepów, byłoby to prawdopodobnie złe rozwiązanie, ponieważ miałoby tendencję do wybierania sklepów w najmniej zaludnionych obszarach. W innych aplikacjach może to być znacznie lepsze rozwiązanie).