Как найти наиболее распространенные локации?

Наверное, очень простой вопрос. У меня есть список из примерно тысячи потенциальных географических мест (широта), и из них мне нужно выбрать 200 мест, которые «наиболее распространены». Я думаю, что это будет 200 баллов с наибольшим общим средним расстоянием. Подумайте о магазинах в городе.

Есть определенный метод, чтобы сделать это? Может быть, в R-упаковке?

Спасибо всем, кто делает это отличным местом, чтобы узнать это!

/Крис

Простой вопрос, сложное решение.

Лучший метод, который я знаю, использует имитационный отжиг (я использовал его для выбора нескольких десятков точек из десятков тысяч, и он очень хорошо масштабируется до 200 точек: масштабирование сублинейно), но это требует тщательного кодирования и значительных экспериментов, так как а также огромное количество вычислений. Сначала вы должны посмотреть на более простые и быстрые методы, чтобы понять, хватит ли их.

Одним из способов является сначала кластеризация местоположений магазина . В каждом кластере выберите магазин, ближайший к центру кластера.

Действительно быстрый метод кластеризации - это K-means . Вот Rрешение, которое использует его.

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

Аргументами scatterявляются список местоположений магазинов (в виде матрицы n на 2) и количество магазинов, которые нужно выбрать (например, 200). Возвращает массив локаций.

В качестве примера его применения давайте сгенерируем n = 1000 случайно расположенных хранилищ и посмотрим, как выглядит решение:

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

Этот расчет занял 0,03 секунды:

Вы можете видеть, что это не здорово (но и не так уж плохо). Чтобы добиться большего успеха, потребуются либо стохастические методы, такие как моделируемый отжиг, либо алгоритмы, которые могут экспоненциально масштабироваться в зависимости от размера проблемы. (Я реализовал такой алгоритм: для выбора 10 наиболее широко разнесенных точек из 20 требуется 12 секунд. Применить его к 200 кластерам не может быть и речи.)

Хорошей альтернативой K-средних является алгоритм иерархической кластеризации; попробуйте сначала метод "Уорда" и подумайте над экспериментами с другими связями. Это потребует больше вычислений, но мы все еще говорим о нескольких секундах для 1000 магазинов и 200 кластеров.

Существуют и другие методы. Например, вы можете покрыть регион регулярной гексагональной сеткой и для ячеек, содержащих один или несколько магазинов, выбрать магазин, ближайший к его центру. Поиграйте немного с размером ячейки, пока не будет выбрано около 200 магазинов. Это приведет к очень регулярному интервалу магазинов, который вы можете или не хотите. (Если это действительно магазины, это, вероятно, было бы плохим решением, поскольку у него была бы тенденция выбирать магазины в наименее густонаселенных районах. В других приложениях это могло бы быть гораздо лучшим решением.)