Подходы к кластеризации долготы пространственной геодезической широты в R с геодезическими или большими расстояниями

Я хотел бы применить некоторые основные методы кластеризации к некоторым координатам широты и долготы. Что-то вдоль линий кластеризации (или некоторого неконтролируемого обучения) координаты в группы определяются либо их большим кругом, либо их geodesic расстояние. ПРИМЕЧАНИЕ: это может быть очень плохой подход, поэтому, пожалуйста, сообщите.

В идеале я хотел бы заняться этим в R.

Я сделал несколько поисков, но, возможно, я пропустил прочный подход? Я столкнулся с пакетами: flexclust и pam - однако я не нашел четкого примера (-ов) относительно следующего:

Определение моей собственной функции расстояния.
Сделайте либо flexclut (через kcca или cclust), либо pam учтите случайные перезагрузки?
Обледенение на торте = знает ли кто-либо подходы/пакеты, которые позволят указать минимальное количество элементов в каждом кластере?

Ответ 1

Что касается вашего первого вопроса: поскольку данные длинны/латы, один подход заключается в использовании earth.dist(...) в пакете fossil (вычисляет большой круг):

library(fossil)
d = earth.dist(df)    # distance object

Другой подход использует distHaversine(...) в пакете geosphere:

geo.dist = function(df) {
  require(geosphere)
  d <- function(i,z){         # z[1:2] contain long, lat
    dist <- rep(0,nrow(z))
    dist[i:nrow(z)] <- distHaversine(z[i:nrow(z),1:2],z[i,1:2])
    return(dist)
  }
  dm <- do.call(cbind,lapply(1:nrow(df),d,df))
  return(as.dist(dm))
}

Преимущество в том, что вы можете использовать любой из других алгоритмов расстояния в geosphere, или вы можете определить свою собственную функцию расстояния и использовать ее вместо distHaversine(...). Затем примените любую из базовых методов кластеризации R (например, kmeans, hclust):

km <- kmeans(geo.dist(df),centers=3)  # k-means, 3 clusters
hc <- hclust(geo.dist(df))            # hierarchical clustering, dendrogram
clust <- cutree(hc, k=3)              # cut the dendrogram to generate 3 clusters

Наконец, реальный пример:

setwd("<directory with all files...>")
cities <- read.csv("GeoLiteCity-Location.csv",header=T,skip=1)
set.seed(123)
CA     <- cities[cities$country=="US" & cities$region=="CA",]
CA     <- CA[sample(1:nrow(CA),100),]   # 100 random cities in California
df     <- data.frame(long=CA$long, lat=CA$lat, city=CA$city)

d      <- geo.dist(df)   # distance matrix
hc     <- hclust(d)      # hierarchical clustering
plot(hc)                 # dendrogram suggests 4 clusters
df$clust <- cutree(hc,k=4)

library(ggplot2)
library(rgdal)
map.US  <- readOGR(dsn=".", layer="tl_2013_us_state")
map.CA  <- map.US[map.US$NAME=="California",]
map.df  <- fortify(map.CA)
ggplot(map.df)+
  geom_path(aes(x=long, y=lat, group=group))+
  geom_point(data=df, aes(x=long, y=lat, color=factor(clust)), size=4)+
  scale_color_discrete("Cluster")+
  coord_fixed()

Данные города от GeoLite. Форм файл US States из Бюро переписи населения.

Изменить в ответ на комментарий @Anony-Mousse:

Может показаться странным, что "LA" разделяется между двумя кластерами, однако расширение карты показывает, что для этого случайного выбора городов существует разрыв между кластером 3 и кластером 4. Кластер 4 - это в основном Санта-Моника и Бербанк; кластер 3 - Пасадена, Южный Лос-Анджелес, Лонг-Бич и все, что к югу от него.

K-означает, что кластеризация (4 кластера) удерживает область вокруг LA/Santa Monica/Burbank/Long Beach в одном кластере (см. ниже). Это просто сводится к различным алгоритмам, используемым kmeans(...) и hclust(...).

km <- kmeans(d, centers=4)
df$clust <- km$cluster

Стоит отметить, что эти методы требуют, чтобы все точки попадали в какой-то кластер. Если вы просто спросите, какие точки близко друг к другу, и разрешите, чтобы некоторые города не попали в какой-либо кластер, вы получите очень разные результаты.

Ответ 2

Я иногда группировал пространственные данные с помощью ELKI.

Это не R (мне не нравится R и я обнаружил, что во многих ситуациях он очень медленный. На самом деле все, кроме простых матричных умножений и простых вызовов в C- или Fortran-код, медленное.)

Во всяком случае, ELKI поддерживает геодезические расстояния и даже ускорение индекса для этих расстояний (как с помощью M-дерева, так и с R * -tree, загруженные R * -товары работают лучше для меня и дают огромные ускорения); и с этими функциями расстояния могут использоваться многие алгоритмы кластеризации, такие как DBSCAN и OPTICS.

Вот пример того, что я получил с кластеризацией ELKI: fooobar.com/info/492351/...

Я не сохранил код. Не уверен, что я использовал Python для вывода KML, или я внедрил модуль вывода ELKI.