관련성없는 위도 경도 쌍을 버려야하는 알고리즘

Question

여러 위치에 대해 최고의 위도 경도 쌍을 계산하려고합니다. 위치가있는 데이터베이스가 있고 각 위치마다 여러 좌표가있을 수 있습니다. 이 좌표의 대부분은 서로 5m 이내에 위치하므로 위치와 관련이있는 것으로 보입니다. 그래서 평균을 구하여 새로운 (최종) 위도 경도 쌍을 도출 할 수 있습니다.

때때로 나는 수백 미터 떨어져있는 지점 (때로는 하나 이상)을 가지고 있습니다.

소수점 (최대 10 점) 위도 경도 점이 주어지면 다른 점과 너무 멀리 떨어져있는 점을 찾아서 버리고 싶습니다.

어떤 접근/알고리즘을 사용해야합니까?

참고 Java로 작업합니다.

Answer 1

간단한 방법 :

1. 계산 어떤 임의의 점에 대한 모든 지점의 거리.
2. 모든 점의 평균 거리를 찾으십시오.
3. abs (dist - median)> 값을 갖는 모든 점을 무시합니다.

클러스터 된 중심점이 멀리 떨어져있는 중심점 접근 방식보다 약간 낫습니다.

Answer 2

간단한 방법이 될 가능성이 높습니다 :

1. 포인트
2. 계산 중심에 세트의 각 지점으로부터의 거리의 주어진 집합에 대한 중심 (평균 길이/위도) 지점을 찾을 수 있습니다. 특정 상수 값 이상의 거리를 가진 모든 점을 무시하십시오. (이 점들을 노이즈라고 부름)
3. 나머지 비 잡음 점으로부터 중심을 다시 계산하여 위치라고 부릅니다.

이것은 자바로 구현하기가 아주 쉬워야하며, O(N), N이 세트의 수인 것이 틀림 없습니다.

귀하의 문제는 특정 사례 인 K-means clustering입니다. 어떤 실제 데이터가 어떤 샘플에 해당하는지 알기 때문에 일반적인 경우에는 해당 지식이 없습니다. 더 많은 연구를 원한다면 그 문제와 다양한 접근법을 살펴보십시오.

Answer 3

는 당신이 요구할 필요가 몇 가지 질문이 있습니다 포인트가 100 미터 떨어져있는 두 지점이있는 경우 "감각을하지"로 취급한다

1. .
2. 포인트가 두 개로 분리되어있는 경우 어떤 포인트를 "이해가 안된다"고 간주해야합니까?
3. 가장 가까운 이웃으로 계산되는 오류의 한계 이내에 여전히 전체 한계를 초과하는 연속적인 행의 점이 있다면 어떻게해야합니까?

클러스터링 알고리즘을 살펴 보겠지만 명확한 기준이 없으면 대답하지 못했습니다.

우리는 내가 언급 한 문제를 건너한다면, 나는 그것이 계산 무거운 것을 말할 것입니다,하지만 당신은별로 정렬

설정 주어진 모든 점 사이의 거리를 계산

1. 로 갈 수있다 거리 합계
2. 합계가 가장 큰 값을 필터링 함
3. 거리 합계가 errorMargin * N-1보다 큰 점이 없을 때까지 반복합니다. 여기서 N은 현재 점의 수입니다.

국경을 고려해야합니다. 예를 들어 1)에서 언급 한 문제로 인해 임의의 단일 지점이 남을 수 있습니다. 그렇다고 확신 할 수는 없으므로주의 깊게 분석해야합니다. 도메인.

Answer 4

Java8을 사용하는 경우 다음 코드는 훌륭한 해결책을 제공합니다.

Collector<Location, ?, Location> centreCollector = new CentreCollector(); 
Location centre = locations.stream().collect(centreCollector); 
centre = locations.stream().filter(centre::furtherThan(NOISE_DISTANCE)).collect(centreCollector); 

작성할 사항이 2 가지 있습니다. 콜렉터를 구현하고 Location 객체가 스트리밍 될 때 평균을내는 클래스 CentreCollector. this 사이의 거리와 주어진 위치 사이의 거리를 주어진 거리와 비교하는 술어를 리턴하는 메소드 인 furtherThan입니다.

약간 더 우아한 방법은 중심까지의 거리의 표준 편차를 계산 한 다음 평균 거리와 일정한 표준 편차 이상인 위치를 무시하는 것입니다. 이것은 모든 또는 대부분의 표본이 중심으로부터의 NOISE_DISTANCE보다 더 많은 위치의 집합을 고려하는 이점을 가질 것이다. 이 경우 CentreCollector는 위치 및 통계 정보를 보유하는보다 복잡한 객체를 반환해야하며 위치 대신 해당 클래스의 구성원으로 furtherThan을 보유해야합니다. 표준 편차를 사용하기위한 동일한 코드를 게시하기를 원하면이 의견에 대해 알려주십시오.