基于点连接的聚类
Clustering based on connectivity of points
我有 100 万条经纬度 [5 位精度] 和路线的记录。我想对这些数据点进行聚类。
我不想使用标准的 k-means 聚类,因为我不确定有多少聚类[尝试了 Elbow 方法但不相信]。
这是我的逻辑-
1) 我想将经纬度的宽度从 5 位数减少到 3 位数。
2) 现在,在 +/- 0.001 范围内的经纬度将聚集在一个簇中。计算簇的质心。
但在这样做的过程中,我无法找到好的算法和 R 脚本来执行我的思想代码。
谁能帮我解决上面的问题。
谢谢,
可以根据connected components进行聚类。
所有在 +/-0.001 距离内的点都可以连接,所以我们将有一个包含子图的图,每个子图可以是单个点或一系列连接点(连接组件)
然后可以找到连接的组件并可以计算它们的质心。
此任务需要两个包:
1.deldir
形成点的三角剖分并指定哪些点彼此相邻并计算它们之间的距离。
2 igraph
查找连通分量。
library(deldir)
library(igraph)
coords <- data.frame(lat = runif(1000000),long=runif(1000000))
#round to 3 digits
coords.r <- round(coords,3)
#remove duplicates
coords.u <- unique(coords.r)
# create triangulation of points. depends on the data may take a while an consume more memory
triangulation <- deldir(coords.u$long,coords.u$lat)
#compute distance between adjacent points
distances <- abs(triangulation$delsgs$x1 - triangulation$delsgs$x2) +
abs(triangulation$delsgs$y1 - triangulation$delsgs$y2)
#remove edges that are greater than .001
edge.list <- as.matrix(triangulation$delsgs[distances < .0011,5:6])
if (length(edge.list) == 0) { #there is no edge that its lenght is less than .0011
coords.clustered <- coords.u
} else { # find connected components
#reformat list of edges so that if the list is
# 9 5
# 5 7
#so reformatted to
# 3 1
# 1 2
sorted <- sort(c(edge.list), index.return = TRUE)
run.length <- rle(sorted$x)
indices <- rep(1:length(run.length$lengths),times=run.length$lengths)
edge.list.reformatted <- edge.list
edge.list.reformatted[sorted$ix] <- indices
#create graph from list of edges
graph.struct <- graph_from_edgelist(edge.list.reformatted, directed = FALSE)
# cluster based on connected components
clust <- components(graph.struct)
#computation of centroids
coords.connected <- coords.u[run.length$values, ]
centroids <- data.frame(lat = tapply(coords.connected$lat,factor(clust$membership),mean) ,
long = tapply(coords.connected$long,factor(clust$membership),mean))
#combine clustered points with unclustered points
coords.clustered <- rbind(coords.u[-run.length$values,], centroids)
# round the data and remove possible duplicates
coords.clustered <- round(coords.clustered, 3)
coords.clustered <- unique(coords.clustered)
}
我有 100 万条经纬度 [5 位精度] 和路线的记录。我想对这些数据点进行聚类。
我不想使用标准的 k-means 聚类,因为我不确定有多少聚类[尝试了 Elbow 方法但不相信]。
这是我的逻辑-
1) 我想将经纬度的宽度从 5 位数减少到 3 位数。
2) 现在,在 +/- 0.001 范围内的经纬度将聚集在一个簇中。计算簇的质心。
但在这样做的过程中,我无法找到好的算法和 R 脚本来执行我的思想代码。
谁能帮我解决上面的问题。
谢谢,
可以根据connected components进行聚类。
所有在 +/-0.001 距离内的点都可以连接,所以我们将有一个包含子图的图,每个子图可以是单个点或一系列连接点(连接组件) 然后可以找到连接的组件并可以计算它们的质心。 此任务需要两个包:
1.deldir
形成点的三角剖分并指定哪些点彼此相邻并计算它们之间的距离。
2 igraph
查找连通分量。
library(deldir)
library(igraph)
coords <- data.frame(lat = runif(1000000),long=runif(1000000))
#round to 3 digits
coords.r <- round(coords,3)
#remove duplicates
coords.u <- unique(coords.r)
# create triangulation of points. depends on the data may take a while an consume more memory
triangulation <- deldir(coords.u$long,coords.u$lat)
#compute distance between adjacent points
distances <- abs(triangulation$delsgs$x1 - triangulation$delsgs$x2) +
abs(triangulation$delsgs$y1 - triangulation$delsgs$y2)
#remove edges that are greater than .001
edge.list <- as.matrix(triangulation$delsgs[distances < .0011,5:6])
if (length(edge.list) == 0) { #there is no edge that its lenght is less than .0011
coords.clustered <- coords.u
} else { # find connected components
#reformat list of edges so that if the list is
# 9 5
# 5 7
#so reformatted to
# 3 1
# 1 2
sorted <- sort(c(edge.list), index.return = TRUE)
run.length <- rle(sorted$x)
indices <- rep(1:length(run.length$lengths),times=run.length$lengths)
edge.list.reformatted <- edge.list
edge.list.reformatted[sorted$ix] <- indices
#create graph from list of edges
graph.struct <- graph_from_edgelist(edge.list.reformatted, directed = FALSE)
# cluster based on connected components
clust <- components(graph.struct)
#computation of centroids
coords.connected <- coords.u[run.length$values, ]
centroids <- data.frame(lat = tapply(coords.connected$lat,factor(clust$membership),mean) ,
long = tapply(coords.connected$long,factor(clust$membership),mean))
#combine clustered points with unclustered points
coords.clustered <- rbind(coords.u[-run.length$values,], centroids)
# round the data and remove possible duplicates
coords.clustered <- round(coords.clustered, 3)
coords.clustered <- unique(coords.clustered)
}