우리는 2D 평면에서 거대한 점 집합을받습니다. 각 점에 대해 집합 내의 가장 가까운 점을 찾아야합니다.엄청난 수의 점에 대한 가장 가까운 쌍
foo <- data.frame(x=c(1,2,4,4,10),y=c(1,2,4,4,10))
출력은 다음과 같이해야합니다 :
ClosesPair(foo)
2
1
4
3
3 # (could be 4 also)
어떤 생각 예를 들어 다음과 같이 초기 설정은 가정?
전통적인 접근 방식은 데이터 을 사전 처리하여 데이터 구조에 넣습니다. 보통 "가장 가까운 지점"쿼리가 매우 빠른 K-d tree, 입니다.
nnclust 패키지에 구현이 있습니다.
library(nnclust)
foo <- cbind(x=c(1,2,4,4,10),y=c(1,2,4,4,10))
i <- nnfind(foo)$neighbour
plot(foo)
arrows(foo[,1], foo[,2], foo[i,1], foo[i,2])
다음은 예입니다. 모두 하나의 함수로 싸여있다. 최적화를 위해 약간 분할 할 수 있습니다.
ClosesPair <- function(foo) {
dist <- function(i, j) {
sqrt((foo[i,1]-foo[j,1])**2 + (foo[i,2]-foo[j,2])**2)
}
foo <- as.matrix(foo)
ClosestPoint <- function(i) {
indices <- 1:nrow(foo)
indices <- indices[-i]
distances <- sapply(indices, dist, i=i, USE.NAMES=TRUE)
closest <- indices[which.min(distances)]
}
sapply(1:nrow(foo), ClosestPoint)
}
ClosesPair(foo)
# [1] 2 1 4 3 3
원인의 경우 매우 잘 처리하지 못합니다.
고마워,하지만 거대한 세트의 포인트에서 작동 할까? 예를 들어 1M 포인트를 의미합니까? – Ali
그래,하지만 효율적으로? 확실하지 않다. 모든 거리를 다시 계산해야하는 각 지점에 대해 O (n^2)로 실행되므로 최적의 솔루션을 원한다면이 문제를 해결할 방법이 없습니다. 일반적으로 더 중요한 문제인 공간별로, O (n) 만 사용합니다. 속도를 높여야하는 경우 병렬 처리를 살펴볼 수 있습니다.이 처리는 쉽게 다시 작성하거나 휴리스틱 검색 알고리즘으로 처리 할 수 있습니다.이 알고리즘은 데이터에 크게 의존합니다. – MrGumble
당신은'dist' 함수가 이미 벡터화되어 있다는 사실을 이용하지 않습니다 ...'sapply (indices, dist, i = i, USE.NAMES = TRUE)'를'dist (i, indices)'로 대체하면 거대한 개선을 볼 수 있습니다. 보다 효율적으로 인덱스를 사용하여 작업을 빠르게 할 수도 있습니다. 예를 들어,'indices <- 1 : nrow (foo)'는 루프 내에서 계산해서는 안됩니다. 그리고'sapply'를'vapply'로 대체하십시오. – flodel
spatstat을 사용하십시오. 그것은 이런 종류의 일을하는 내장 함수를 가지고 있습니다.
비슷한 질문 : http://stackoverflow.com/questions/16474179/how-to-calculate-euclidean-distance-and-save-only-summaries-for-large-data-fra/16474415#16474415 – flodel