Bagaimana menemukan lokasi yang paling tersebar?

Mungkin pertanyaan yang sangat sederhana. Saya memiliki daftar sekitar seribu lokasi geografis potensial (lat lon), dan dari mereka saya perlu memilih 200 lokasi yang "paling tersebar". Saya pikir itu akan menjadi 200 poin dengan total jarak rata-rata tertinggi. Pikirkan toko di kota.

Apakah ada metode yang pasti untuk melakukannya? Mungkin dalam paket-R?

Terima kasih kepada semua orang yang menjadikan ini tempat terbaik untuk mempelajarinya!

/ Chris

Pertanyaan sederhana, solusi sulit.

Metode terbaik yang saya tahu menggunakan simulated annealing (Saya telah menggunakan ini untuk memilih beberapa lusin poin dari puluhan ribu dan berskala sangat baik untuk memilih 200 poin: penskalaan adalah sublinear), tetapi ini membutuhkan pengkodean yang hati-hati dan eksperimen yang cukup, seperti serta sejumlah besar perhitungan. Anda harus mulai dengan melihat metode yang lebih sederhana dan lebih cepat terlebih dahulu untuk melihat apakah metode tersebut memadai.

Salah satu caranya adalah pertama mengelompokkan lokasi toko . Dalam setiap cluster pilih toko yang paling dekat dengan pusat cluster.

Metode pengelompokan yang sangat cepat adalah K-means . Berikut ini adalah Rsolusi yang menggunakannya.

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

Argumen untuk scatteradalah daftar lokasi toko (sebagai n oleh 2 matriks) dan jumlah toko untuk dipilih (misalnya, 200). Ini mengembalikan array lokasi.

Sebagai contoh aplikasinya, mari kita hasilkan n = 1000 toko yang terletak secara acak dan lihat seperti apa solusinya:

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

Perhitungan ini memakan waktu 0,03 detik:

Anda dapat melihat itu tidak bagus (tapi juga tidak terlalu buruk). Untuk melakukan jauh lebih baik akan memerlukan metode stokastik, seperti anil simulasi, atau algoritma yang cenderung skala secara eksponensial dengan ukuran masalah. (Saya telah mengimplementasikan algoritma semacam itu: butuh 12 detik untuk memilih 10 poin yang paling banyak spasi dari 20. Menerapkannya pada 200 cluster adalah hal yang mustahil.)

Alternatif yang baik untuk K-means adalah algoritma pengelompokan hierarkis; cobalah metode "Ward" terlebih dahulu dan pertimbangkan untuk bereksperimen dengan tautan lain. Ini akan membutuhkan lebih banyak perhitungan, tetapi kami masih berbicara tentang hanya beberapa detik untuk 1000 toko dan 200 cluster.

Ada metode lain. Misalnya, Anda bisa menutupi wilayah dengan kisi heksagonal biasa dan, untuk sel yang berisi satu atau lebih toko, pilih toko terdekat pusatnya. Mainkan sedikit dengan cellsize sampai sekitar 200 toko telah dipilih. Ini akan menghasilkan ruang toko yang sangat teratur, yang mungkin atau mungkin tidak Anda inginkan. (Jika ini benar-benar lokasi toko, ini mungkin akan menjadi solusi yang buruk, karena itu akan memiliki kecenderungan untuk memilih toko di daerah yang paling padat penduduknya. Dalam aplikasi lain ini mungkin solusi yang jauh lebih baik.)