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