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

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

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

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

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

2 ответа

Решение

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

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. Шейп-файл штатов США из Бюро переписей.

Отредактируйте в ответ на комментарий @Anony-Mousse:

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

Кластеризация K-средних (4 кластера) удерживает область вокруг Лос-Анджелеса / Санта-Моники / Бербанка / Лонг-Бич в одном кластере (см. Ниже). Это просто сводится к различным алгоритмам, используемым kmeans(...) а также hclust(...),

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

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

Источник

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

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

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

Вот пример того, что я получил с помощью кластеризации ELKI: /questions/22107697/kak-sgruppirovat-blizlezhaschie-mestopolozheniya-shirotyi-i-dolgotyi-hranyaschiesya-v-sql/22107698#22107698

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

Источник
Другие вопросы по тегам