오목 선체
케이-가장 가까운 이웃 접근 방식을 사용하여 클러스터 경계 만들기
몇 달 전,나는 매체에 영국의 교통 사고 핫스팟 매핑에 기사를 여기에 썼다. 나는 주로 지리적 데이터에 대한 클러스터링 알고리즘의 사용을 설명하는 것에 대해 우려했다. 이 기사에서 나는보고 된 교통 사고에 대해 영국 정부가 발표 한 지리 정보를 사용했습니다. 내 목적은 교통 사고가 가장 자주보고되는 영역을 찾기 위해 밀도 기반 클러스터링 프로세스를 실행하는 것이 었습니다. 최종 결과는 이러한 사고 핫스팟을 나타내는 지리적 울타리 세트를 생성 한 것입니다.
지정된 군집의 모든 점을 수집하면 지도에서 군집의 모양을 알 수 있지만 중요한 정보인 군집의 외부 모양이 부족합니다. 이 경우,우리는 지오 펜스로지도에 표현 될 수있는 닫힌 다각형에 대해 이야기하고 있습니다. 지오 펜스 내부의 모든 지점은 클러스터에 속한다고 가정 할 수 있습니다.이 모양을 흥미로운 정보로 만듭니다.판별 자 함수로 사용할 수 있습니다. 다각형 내부에 속하는 새로 샘플링 된 모든 점은 해당 클러스터에 속한다고 가정 할 수 있습니다. 이 기사에서 암시 한 것처럼 이러한 다각형을 사용하여 운전 위험을 주장 할 수 있습니다.이 다각형을 사용하여 자신의 샘플링 된 위치를 분류 할 수 있습니다.
이제 문제는 특정 클러스터를 구성하는 점 구름에서 의미있는 다각형을 만드는 방법입니다. 첫 번째 기사에서 내 접근 방식은 다소 노나이었다. 이 솔루션은 클러스터의 각 점을 중심으로 원을 배치 한 다음 모든 원을 함께 병합하여 구름 모양의 다각형을 형성했습니다. 결과는 아주 좋은,도 현실적인 없습니다. 또한 최종 다각형을 만들기 위한 기본 모양으로 원을 사용하면 보다 간소화된 모양보다 더 많은 포인트를 가지므로 스토리지 비용이 증가하고 포함 검색 알고리즘의 실행 속도가 느려집니다.
한편,이 접근법은 모든 원을 함께 병합하기 위해 매끈한cascaded_union함수를 사용하기 때문에(적어도 개발자의 관점에서)계산 상 간단하다는 장점이 있습니다. 또 다른 장점은 다각형의 모양이 클러스터의 모든 점을 사용하여 암시적으로 정의된다는 것입니다.
보다 정교한 접근 방식을 위해서는 점 구름 모양을 정의하는 것처럼 보이는 클러스터 경계 점을 어떻게 든 식별해야합니다. 흥미롭게도,일부 디비스캔 구현에서는 클러스터링 프로세스의 부산물로서 경계점을 실제로 복구할 수 있습니다. 불행히도,이 정보는(분명히)사이킷 배우 구현에서 사용할 수 없으므로 우리는 할 수 있어야합니다.
마음에 떠오르는 첫 번째 접근 방식은 점 집합의 볼록한 선체를 계산하는 것이 었습니다. 이것은 잘 이해 된 알고리즘이지만 다음과 같이 오목한 모양을 처리하지 않는 문제로 고통 받고 있습니다:
이 모양은 기본 점의 본질을 올바르게 포착하지 않습니다. 판별자로 사용되었다면,일부 지점은 그렇지 않을 때 클러스터 내부에 있는 것으로 잘못 분류될 수 있습니다. 우리는 다른 접근 방식이 필요합니다.
오목 선체 대안
다행히도,이 상태에 대한 대안이 있습니다:우리는 오목 선체를 계산할 수 있습니다. 다음은 이전 이미지와 동일한 점 집합에 적용할 때 오목한 선체의 모습입니다:
또는 어쩌면 이것:
보시다시피 볼록 선체와는 달리 점 집합의 오목한 선체가 무엇인지에 대한 단일 정의는 없습니다. 제가 여기서 제시하고 있는 알고리즘으로,선체가 얼마나 오목하게 되는지를 선택하는 것은 하나의 매개 변수를 통해 이루어집니다:케이-선체 계산 중에 고려되는 가장 가까운 이웃의 수. 이것이 어떻게 작동하는지 보자.
알고리즘
내가 여기서 제시하고있는 알고리즘은 10 년 전에 포르투갈 민호 대학의 아드리아노 모레이라와 마리벨 야스미나 산토스에 의해 설명되었습니다. 에서 추상:
이 논문은 주어진 포인트에 의해 점유 된 영역을 나타내는 비 볼록 선체에 볼록을 생성하는 평면에서 포인트 세트의 봉투를 계산하는 알고리즘을 설명합니다. 제안 된 알고리즘을 기반으로 케이-가장 가까운 이웃 접근 방식,여기서 값 케이,유일한 알고리즘 매개 변수,최종 솔루션의”부드러움”을 제어하는 데 사용됩니다.
이 알고리즘을 지리 정보에 적용 할 것이므로 각도와 거리를 계산할 때 일부 변경해야했습니다. 그러나 이러한 방법은 알고리즘의 요점을 변경하지 않습니다,그 광범위하게 다음 단계에 의해 설명 될 수있다:
- 와이(위도)좌표가 가장 낮은 점을 찾아 현재 좌표로 만듭니다.
- 현재 지점에 가장 가까운 지점을 찾습니다.
- 케이-가장 가까운 지점에서,이전 각도에서 가장 큰 오른쪽 턴에 해당하는 하나를 선택합니다. 여기서 우리는 베어링의 개념을 사용하고 270 도(서쪽으로 인해)의 각도로 시작할 것입니다.
- 성장 선 문자열에 새 점을 추가하여 그 자체가 교차하지 않는지 확인하십시오. 5213>
- 새 점을 현재 점으로 만들고 목록에서 제거합니다.
- 케이 반복 후 첫 번째 점을 목록에 다시 추가합니다.
- 번호 2 로 루프.
이 알고리즘은 매우 간단한 것 같다,하지만 우리가 지리적 좌표를 다루고 특히 때문에,에 참석해야 할 세부 사항의 숫자가있다. 거리와 각도는 다른 방식으로 측정됩니다.
내가 게시하고있는 코드
는 이전 기사 코드의 적응 된 버전입니다. 여전히 동일한 클러스터링 코드와 동일한 구름 모양의 클러스터 생성기를 찾을 수 있습니다. 이제 업데이트된 버전에는ConcaveHull클래스를 찾을 수 있는geomath.hulls라는 패키지가 포함되어 있습니다. 오목한 선체를 만들려면 다음과 같이 하십시오:
위의 코드에서points는 차원 배열입니다(엔,2),행에는 관찰 된 점이 있고 열에는 지리적 좌표(경도,위도)가 포함됩니다. 결과 배열은 정확히 동일한 구조를 갖지만 클러스터의 다각형 모양에 속하는 점만 포함합니다. 종류의 필터.
우리는 배열을 처리 할 것이기 때문에 그 싸움에 숫자를 가져 오는 것은 자연스러운 일입니다. 모든 계산은 가능할 때마다 정식으로 벡터화되었으며 배열에서 항목을 추가 및 제거 할 때 성능을 향상시키기위한 노력이 이루어졌습니다(스포일러:전혀 움직이지 않음). 누락 된 개선 사항 중 하나는 코드 병렬화입니다. 그러나 그것은 기다릴 수 있습니다.
번역 중에 일부 최적화가 이루어졌지만 논문에 노출 된대로 알고리즘을 중심으로 코드를 구성했습니다. 이 알고리즘은 명확하게 종이에 의해 식별되는 서브 루틴의 수를 중심으로 구축,그래서 지금 길에서 사람들을 얻을 수 있습니다. 당신의 독서 편의를 위해,나는 종이에 사용 된 것과 같은 이름을 사용할 것입니다.
정리 목록-점 목록 정리는 클래스 생성자에서 수행됩니다:
보시다시피,점 목록은 성능상의 이유로 숫자 배열로 구현됩니다. 목록의 청소는 라인 10 에서 수행되며,여기서 고유 한 포인트 만 유지됩니다. 데이터 집합 배열은 행의 관측치와 두 열의 지리적 좌표로 구성됩니다. 또한 13 행에 부울 배열을 만들어 주 데이터 세트 배열에 인덱싱하여 항목을 제거하고 가끔씩 다시 추가하는 자질구레 한 작업을 완화하는 데 사용됩니다. 이 기술을”마스크”라고 부르는 것을 보았습니다.이 기술은 매우 강력합니다. 소수에 관해서는,나는 그들을 나중에 토론 할 것이다.
미니 포인트 찾기—작은 기능이 필요합니다.:
이 함수는 데이터 집합 배열을 인수로 호출하고 위도가 가장 낮은 점의 인덱스를 반환합니다. 행은 첫 번째 열의 경도와 두 번째 열의 위도로 인코딩됩니다.
제거점
추가점—이 배열은indices배열의 사용으로 인해 뇌가 없습니다. 이 배열은 기본 데이터 세트 배열에 활성 인덱스를 저장하는 데 사용되므로 데이터 세트에서 항목을 제거하는 것은 간단합니다.
이 논문에서 설명한 알고리즘은 선체를 구성하는 배열에 점을 추가 할 것을 요구하지만 실제로는 다음과 같이 구현됩니다:
나중에test_hull변수는 줄 문자열이 교차하지 않는 것으로 간주 될 때hull에 다시 할당됩니다. 그러나 나는 여기서 게임보다 앞서 가고 있습니다. 데이터 집합 배열에서 점을 제거하는 방법은 다음과 같이 간단합니다:
self.indices = False
그것을 다시 추가하는 것은 동일한 인덱스에서 그 배열 값을 다시 사실로 뒤집는 문제 일뿐입니다. 하지만이 모든 편의 인덱스에 우리의 탭을 유지 하는 데의 가격으로 온다. 이 나중에 더.
가까운 점-우리가 평면 좌표를 다루지 않기 때문에 여기서 흥미로운 점이 생기기 시작합니다.:
두 번째 및 세 번째 매개 변수는 데이터 집합 형식의 배열입니다:첫 번째 열의 경도 및 두 번째 열의 위도. 보시다시피,이 함수는 두 번째 인수의 점과 세 번째 인수의 점 사이의 거리(미터)배열을 반환합니다. 일단 우리가 이것들을 가지고 있으면,우리는 케이-가장 가까운 이웃들을 쉬운 방법으로 얻을 수 있습니다. 그러나 그것에 대한 전문화 된 기능이 있으며 몇 가지 설명이 필요합니다:
이 함수는 기본 인덱스를 사용하여 배열을 만드는 것으로 시작합니다. 데이터 집합 배열에서 제거되지 않은 점의 인덱스입니다. 예를 들어,10 점 클러스터에서 첫 번째 점을 제거하여 시작한 경우 기본 인덱스 배열이 될 것입니다. 다음으로 거리를 계산하고 결과 배열 인덱스를 정렬합니다. 첫 번째 케이 추출 된 다음 기본 인덱스를 검색하는 마스크로 사용됩니다. 그것은 일종의 뒤틀린 것이지만 작동합니다. 보시다시피 함수는 좌표 배열을 반환하지 않고 인덱스 배열을 데이터 세트 배열로 반환합니다.
정렬 각도-우리가 단순한 각도를 계산하는 것이 아니라 베어링을 계산하기 때문에 더 많은 문제가 있습니다. 이들은 각도가 시계 방향으로 증가하는 북쪽으로 인해 0 도로 측정됩니다. 다음은 베어링을 계산하는 코드의 핵심입니다:
이 함수는 인덱스가 첫 번째 인수에 있는 지점에서 세 번째 인수에 있는 지점으로 측정된 베어링 배열을 반환합니다. 정렬은 간단합니다:
이 시점에서 후보 배열은 인덱스를 포함합니다 케이-가장 가까운 점 베어링의 내림차순으로 정렬됩니다.
교차점-내 자신의 선 교차점 기능을 굴리는 대신 도움을 받기 위해 매끈한 것으로 바뀌 었습니다. 사실,다각형을 구축하는 동안,우리는 본질적으로 이전 것들과 교차하지 않는 세그먼트를 추가,라인 문자열을 처리하고 있습니다. 이에 대한 테스트는 간단하다:우리는 건설 선체 배열을 선택,매끈한 라인 문자열 객체로 변환,그것은 간단한 경우 테스트(비 자기 교차)여부.
간단히 말해서,매끈한 줄 문자열은 자기 교차하면 복잡해 지므로is_simple술어는 거짓이됩니다. 쉬운.
포인틴 폴리곤-이 구현하기 가장 까다로운 것으로 밝혀졌다. 최종 선체 다각형 유효성 검사를 수행하는 코드를 확인하여 설명 할 수 있습니다(클러스터의 모든 점이 다각형에 포함되어 있는지 확인합니다):
교차점과 포함을 테스트하는 매끈한 기능은 최종 선체 다각형이 클러스터의 모든 점과 겹치는지 확인하기에 충분했지만 그렇지 않았습니다. 왜? 매끈한 좌표 불가지론이다,그래서 직교 평면에 좌표와 정확히 같은 방식으로 위도와 경도로 표현 지리적 좌표를 처리합니다. 그러나 당신이 구에 살 때 세상은 다르게 행동하며 각도(또는 베어링)는 측지를 따라 일정하지 않습니다. 바그다드와 오사카를 연결하는 측지선을 참조하는 예는 이것을 완벽하게 보여줍니다. 어떤 상황에서는 알고리즘이 베어링 기준에 따라 점을 포함 할 수 있지만 나중에 매끈한 평면 알고리즘을 사용하여 다각형 외부에서 약간 벗어난 것으로 간주됩니다. 즉,작은 거리 보정이 무엇을하고 있습니다.
이 문제를 파악하는 데 시간이 걸렸습니다. 내 디버깅 도움말은 무료 소프트웨어의 훌륭한 조각이었습니다. 이 응용 프로그램은 당신이 당신의 데이터를 읽을 수 있도록 설계되었습니다. 진짜 생명의 은인!
마지막으로 폴리곤이 클러스터의 모든 점을 덮지 못하면 유일한 옵션은 케이를 늘리고 다시 시도하는 것입니다. 여기에 내 자신의 직감을 조금 추가했습니다.
프라임 케이
이 기사는 케이의 값이 1 씩 증가하고 알고리즘이 처음부터 다시 실행된다고 제안합니다. 이 옵션을 사용한 초기 테스트는 그다지 만족스럽지 않았습니다:문제가있는 클러스터에서는 실행 시간이 느려질 것입니다. 이것은 케이의 느린 증가에 기인했다,그래서 나는 또 다른 증가 일정을 사용하기로 결정:소수의 테이블. 이 알고리즘은 이미 케이=3 로 시작,그래서 소수의 목록에 진화 할 수있는 쉬운 확장했다. 이것은 재귀 호출에서 일어나는 것을 볼 수 있습니다:
나는 소수에 대한 것을 가지고 있습니다…
폭파
이 알고리즘에 의해 생성 된 오목한 선체 다각형은 선체 내부의 점만 구별하기 때문에 추가 처리가 필요하지만 가깝지는 않습니다. 이 솔루션은 이러한 마른 클러스터에 약간의 패딩을 추가하는 것입니다. 여기서 나는 전에 사용 된 것과 동일한 기술을 사용하고 있으며,여기에 그것이 어떻게 생겼는지입니다:
여기서는 매끈한buffer기능을 사용하여 트릭을 수행했습니다.
이 함수는 매끈한 다각형을 받아 자체의 팽창 된 버전을 반환합니다. 두 번째 매개 변수는 추가된 안쪽 여백의 반경(미터)입니다.
코드 실행
실행할 파일은 주 디렉터리에서ShowHotSpots.py입니다. 처음 실행되면 코드는 2013 년부터 2016 년까지 영국 교통 사고 데이터를 읽고 클러스터링합니다. 그런 다음 결과는 후속 실행을 위해 캐시됩니다.첫 번째 맵은 구름 모양의 클러스터를 사용하여 생성되고 두 번째 맵은 여기에서 설명한 오목한 클러스터링 알고리즘을 사용합니다. 폴리곤 생성 코드가 실행되는 동안 몇 가지 오류가 보고되는 것을 볼 수 있습니다. 알고리즘이 오목한 선체를 만들지 못하는 이유를 이해하기 위해 코드는 클러스터를data/out/failed/디렉토리에 씁니다. 이러한 파일을 레이어로 가져올 수 있습니다.
본질적으로이 알고리즘은 자체 교차하지 않고 모양을”돌아 다니기에”충분한 점을 찾지 못할 때 실패합니다. 즉,이러한 클러스터를 폐기하거나 다른 처리(볼록한 선체 또는 병합 된 거품)를 적용 할 준비가되어 있어야합니다.
오목
랩입니다. 이 기사에서는 지리적 클러스터를 오목한 모양으로 생성 한 후 처리 방법을 제시했습니다. 이 방법은 다른 대안에 비해 클러스터에 더 잘 맞는 외부 폴리곤을 제공 할 수 있습니다.
읽고 코드를 땜질 즐길 주셔서 감사합니다!이 두 가지 유형의 군집은 삼각 부등식에 의한 군집입니다. 2015 년 10 월 15 일(토)~2015 년 10 월 15 일(일) 2010. 컴퓨터 과학 강의 노트,권 6086. 컴퓨터 학습과 컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습,컴퓨터 학습. 12,페이지. 2825-2830,2011
