근접한 세트로 객체를 어떻게 그룹화합니까?

Question

수천 개의 주소가 포함 된 세트가 있습니다. 각 주소의 경도와 위도를 얻을 수 있다면 세트를 근접하게 그룹으로 분할하려면 어떻게해야합니까?

또한 다른 규칙에 따라 '클러스터링'을 다시 시도하고 싶을 수도 있습니다.

• n 그룹
• 그룹당 m 주소
• 그룹의 모든 주소 사이의 최대 거리

Answer 1

당신은 시도 할 수 있습니다 K- 평균 클러스터링 연산.

Answer 2

벡터 양자화를 원합니다 :

http://en.wikipedia.org/wiki/vector_quantization

"큰 포인트 (벡터)를 가장 가까운 포인트 수를 가진 그룹으로 나누어 작동합니다. 각 그룹은 K- 평균 및 다른 클러스터링 알고리즘과 같이 중심 지점으로 표시됩니다."

여기서 벡터는 각 주소의 지리적 좌표이며, 제약 조건 (근접성, 그룹 크기, 그룹 수 ...)에 따라 다른 매개 변수로 알고리즘을 공급할 수 있습니다.

K-Means로 시작할 수 있지만 내 경험에서 Voronoi 기반 알고리즘이 더 유연합니다. 좋은 소개 여기.

Answer 3

클러스터를 원하는 데이터의 척도에 약간 의존합니다. Brute Force 접근법은 모든 점 조합 사이의 거리를 거리 배열로 계산하는 것입니다. 결과 배열은 n^2이고 a에서 b까지의 거리는 b와 동일하기 때문에 A 절반 만 필요하므로 결과 세트는 n^2/2입니다.

비교적 가까운 LAT LON 좌표의 경우 때로는 LAT LONG을 X, Y 그리드로 사용하고 직교 거리를 계산할 수 있습니다. 현실 세계가 평평하지 않기 때문에 직교 거리는 오류가 발생합니다. 주소가 전국에 위치한 경우 사용해야 할보다 정확한 계산을 보려면 Mathforum.com 에서이 링크.

전체 거리 매트릭스를 처리 할 스케일이없는 경우 효율성을 높이기 위해 알고리즘 프로그래밍을 수행해야합니다.

Answer 4

"N 그룹"및 "그룹당 M 주소"제약 조건은 상호 배타적입니다. 하나는 다른 하나를 암시합니다.

Answer 5

1. 모든 주소 사이에 거리의 매트릭스를 구축하십시오.
2. 임의의 주소로 시작하여 해당 주소까지의 거리를 올라가서 매트릭스를 정렬하십시오.
3. 매트릭스에서 주소를 제거하면 기준 (그룹 또는 최대 거리의 크기)에 도달 할 때까지 시작 주소에 가장 가까운 주소를 새 그룹에 넣습니다.
4. 그룹이 가득 차면 다른 임의 주소를 선택하고 해당 주소와의 거리별로 매트릭스를 리조트합니다.
5. 모든 주소가 행렬에서 나올 때까지 이렇게 계속하십시오.

주소가 골고루 분포 된 경우 각 그룹은 시작 주소 주위에 일종의 원형 모양을 갖습니다. 문제는 시작 주소가 기존 그룹 근처에있을 때 발생합니다. 이런 일이 발생하면 새 그룹은 기존 그룹을 랩핑하고 정지 기준이 그룹 크기 일 경우에도 완전히 동그라미를 만들 수도 있습니다. 최대 용기 제약 조건을 사용하면 이런 일이 발생하지 않을 것입니다 (다른 제약 조건이 없다고 가정).

나는 이것이 좋은 방법인지 확실하지 않지만 그것은 내가 시도한 것입니다. 많은 최적화가 필요할 것이라고 확신합니다. 특히 가장자리의 주소.