2013-11-21 3 views
0

중심에서 가장 멀리 떨어진 점 (2D 유클리드 그래프)의 비교적 큰 부분을 선택하는 효율적인 방법을 찾고 있습니다. 이것은 볼록한 선체와 비슷하지만 더 많은 점을 포함합니다. 추가 기준 :그래프에서 바깥 쪽 점을 선택하는 알고리즘 ("rich"convex hull)

  • 선택/세트 ("K")의 포인트 수는 지정된 범위 내에 있어야합니다. 대부분 매우 좁은 것은 아니지만 대부분 다른 범위 (예 : 0.01 * N < K < 0.05 * N 및 0.1 * N < K < 0.2 * N)에서 작동합니다.

  • 알고리즘은 중심으로부터의 거리와 "로컬 밀도"의 균형을 유지할 수 있어야합니다. 그래프 영역의 위쪽 부분에 밀집된 영역이 있지만 하단 부분 근처에 드문 드문 영역이있는 경우 알고리즘은 상단 부분의 점보다 중심에 더 가깝더라도 하단 부분의 일부 점을 선택해야합니다 부위. (아래 예 참조)

  • 보너스 : 중심에서 단순한 거리가 아니라 특정 점 (또는 점과 중심 모두)까지의 거리를 고려하면 완벽 할 것입니다.

내 시도는 지금까지 (좌표 값에 기초하여 상자 포인트를 할당 CXR 박스로 나누어 그래프) "비둘기 천공"를 이용하여 우리가 세트 충분한 포인트가 될 때까지 "외부"박스 선택에 초점을 맞추고있다. 그러나, 나는 고정 된 박스 크기로 인해 과도하게 선택된 고밀도 영역의 선택과 센터를 대신하여 선택된 포인트를 참조로 사용하는 것에 성공하지 못했다.

나는 (가난하게) 그려진 것이 Example입니다. 빨간색 점이 점이고, 녹색 모양은 내가 원하는 것의 예입니다 (녹색 밖에 선택됨). 희소 영역의 경우, 경계 모양이 중심에 더 가까워 적절한 점을 찾습니다 (그러나 중심에 너무 가까울 경우 반드시 찾을 필요는 없습니다). 노란색 상자는 내 Pigeon Holing 기반 알고리즘의 예입니다. 더 좁은 지역을 조정하려고 할 때조차도 잘 관리되지 않습니다.

모든 아이디어를 환영합니다!

답변

1

나는 당신이 원하는 것을 줄 수있는 표준 알고리즘이 없다고 생각합니다. 당신은 창조적이되어야합니다. 몇 가지 아이디어가 당신의 포인트는 여기에 2 차원 유클리드 공간에 포함되어 있습니다 가정 :

  1. 반복적으로 여러 볼록를 계산하는 것은 선체. 예를 들어 볼록 선체를 계산하고 볼록 선체의 일부인 점을 유지 한 다음 원본 볼록 선체에서 점을 무시한 다른 볼록 선체를 계산합니다. 본질적으로 충분한 포인트를 얻을 때까지이 작업을 계속 수행하여 본질적으로 각 반복마다 주변 지점을 뽑아야합니다. 이 방법의 유일한 문제점은 데이터 세트의 오목면 (예 : 게시 한 샘플의 맨 아래에있는 오목면)에 적합하지 않다는 것입니다.

  2. 는 데이터에 가우스를 장착하고> 편차 멀리 평균으로부터 표준 N (N은 어디 해야 할 것 값 선택) 모든 것을 유지. 데이터가 가우시안이라면 꽤 잘 작동합니다. 이 아닌 경우 여러 가우스 (대신 )로 모델링 할 수 있으며 접합 확률이 특정 임계 값 미만인 점을 유지할 수 있습니다. 다중 가우시안을 사용하면 아마도 오목면을 적절하게 다룰 수 있습니다.
    참조 :
    http://en.wikipedia.org/wiki/Gaussian_function
    How to fit a gaussian to data in matlab/octave?

    \
  3. 사용 커널 밀도 추정 - 당신이 커널 밀도를 표면을 만드는 경우 슬라이스 어떤 높이에서 표면 (예를 들어,로를 회전 수 고원)을 사용하여 포인트 주변의 둘레 모양 ( 고원 모양)을 제공합니다. 트릭은 올바른 위치에서 슬라이스하는 것이지만, 결국 모양이 바뀌지 않고 끝낼 수 있기 때문에 모양을 선택할 수 있지만 올바른 선택을하면 쉽게 그린 모양을 얻을 수 있습니다. 이 방법은 슬라이스 지점을 현명하게 선택하는 경우 (예 : 수행하기 어려울 수 있음) 예제에서 녹색 모양을 제공하고 잘 작동합니다. 이 접근법의 가장 큰 단점은 매우 계산 비용이 많이 든다는 것입니다. 더 많은 정보 : http://en.wikipedia.org/wiki/Multivariate_kernel_density_estimation

  4. 사용 알파 모양는 지점 세트의 단단히 주위 외부 경계 일반적인 모양에게 랩을 얻을 수 있습니다. 그런 다음 셰이프 밖으로 어떤 점을 강제로 작은 모양을 침식하십시오. 저는 알파 셰이프에 대한 많은 경험이 없지만,이 접근법은 계산 상으로 많은 비용이들 것입니다. 더 많은 정보 : http://doc.cgal.org/latest/Alpha_shapes_2/index.html

+0

두 가지 모두 계산 상 매우 비쌉니다. 두 방법 모두의 복잡성에 대한 아이디어? – Gaminic

+0

네, 맞습니다 - KDE와 알파 형태의 접근 방식은 모두 매우 계산적으로 비쌉니다. 몇 가지 추가 아이디어를 추가했습니다. – mattnedrich

+0

감사합니다. 매우 흥미로운 아이디어. 나는 각각을 잘 살펴보고 경험적 방법으로 그들의 힘을 사용한다고 생각할 수 있는지 알아볼 것입니다. – Gaminic