Python에서 계층 적 클러스터링의 볼록한 껍질

Question

계층 적 클러스터링을 사용하여 2 차원으로 병합 된 많은 양의 데이터를 시각화하려고합니다. 내가 원하는 것은 클러스터를 구성 포인트의 볼록 선체로 렌더링하여 계층 구조의 여러 높이에서 데이터를 볼 수있는 시각화를 만드는 것입니다. 이 문제의 가장 어려운 부분은 계층 구조를 위로 이동하면서 쌍 클러스터의 볼록 선체를 효율적으로 병합 할 수있는 알고리즘이 필요하다는 것입니다. O (n log n) 시간에 점의 볼록 선체를 계산하기위한 알고리즘을 많이 보았습니다. 그러나이 경우 문제의 하부 구조를 활용하는 것이 훨씬 효율적일 것으로 보이지만, 어떻게 확실하지.

편집 :

자세한 내용은, 상기 데이터 구조는 클러스터의 최초 포인트에서 시작하고 포인트/클러스터가 다음의 클러스터를 형성하도록 결합하는 말했다 배열이다. 따라서 트리/포인터 구조와 비슷하지만 하나의 큰 배열에 포함되어 있습니다. 중요한 부분은 두 구성 클러스터가 수퍼 클러스터 중 무엇인지 확인하는 것이 효율적이지만 클러스터에 속한 모든 포인트 세트를 얻는 것은 효율적이지 않다는 것입니다. 따라서 합리적인 알고리즘은 아래에서 위로 작업해야합니다.

우리는 계층 구조의 중간에 있다고 가정하고 미리 계산 된 계층 구조에서 클러스터 A와 B가 병합되어 클러스터 C를 생성한다고 가정 해 봅시다. 우리는 위에서 아래로 갈 것입니다. 클러스터 A와 B에있는 점의 볼록 선체입니다. 따라서이를 결합하여 클러스터 C의 볼록 선체를 생성하면됩니다. 클러스터 A의 convex hull은 실제로 단일 점, 쌍 또는 전체 다각형 일 수 있습니다. 그래서 클러스터 C의 convex hull을 형성하기 위해 이들을 병합해야하는 몇 가지 경우가 있습니다. 그러나 아마도 싱글 톤과 페어를 다각형과 같은 방식으로 처리 할 수있는 영리한 솔루션이있을 것입니다.

가장 확실한 해결책은 클러스터 A와 B의 볼록 선체에서 결합 된 점 집합을 사용하여 볼록 선체를 계산하는 것입니다. 그러나이를 100k 점의 계층 구조에서 수행해야합니다. 이 A와 B

편집 2의 볼록 선체를 결합하는보다 효율적인 방법 :

  /----5 
    1---/ /\ 
/\ /B 8 
    2 A 3 C 6 /
    \/ \/
    4--------7 

그래, 그래서 내가 무슨 뜻인지의 그림을 ASCII로 시도했다. 클러스터 A의 볼록한 선체는 1-2-3-4이며, B의 볼록한 선체는 5-6-7-8이고 C의 볼록한 선체는 1-2-4-7-8-5입니다. 아마도 클러스터 A와 B는 선체 내부에 추가 점을 포함하고 있지만 분명히 C의 선체 일부가 될 수는 없으므로 문제는 클러스터 A와 B의 선체를 "연결하여" 포인트의 좌표에 따라 C의 선체. 이것은 전체 프로세스의 귀납적 인 단계입니다. (결과적으로 C는 클러스터 D와 결합 될 것이고, 알고리즘은 최상위 클러스터로 끝날 때까지 볼록한 선체로 모든 점의 볼록한 선체를 가질 것이다).

Answer 1

내가 알고있는 볼록 선체 병합 알고리즘은 Toussaint (용지 섹션 5)의 rotating calipers과 Preparata와 Hong의 bridging algorithm입니다 (이 문서의 섹션 3 참조). 이들 알고리즘 모두 시간 = h를 ₁ 및 H ₂ 제 1 및 제 2 볼록 선체 정점의 수가 각각 H 선체있다 ₁ + H ₂, 시간 선형 걸릴 .

Answer 2

새로운 점을 추가 할 때 볼록 선체를 "업데이트"할 수있는 다양한 방법이 있습니다. 또한 볼록 선체와 Delauney 삼각 측량을위한 몇 가지 방법은 이미 내부에서 잘 작동합니다.이 방법은이 작업을 능숙하게 수행해야합니다. s-hull 알고리즘을 살펴보십시오.

그러나 계층 적 클러스터링에 대해 이야기하고 있기 때문에 복잡성과 관련하여 볼록한 선체는 아마도 가장 우려 할 사항이 아닙니다.

계층 적 클러스터링은 일반적으로 알고리즘이 보통 O(n^3)이기 때문에 큰 데이터 세트로 확장되지 않습니다. 실제로는 실제로 사용되는 알고리즘 중 가장 느린 클러스터링 알고리즘 중 하나입니다.따라서 많은 볼록 선체를 추가로 계산하면 이 아닌이 클러스터링이 더 비쌉니다. 당신은 단지 O(n log n) 볼록 선체 알고리즘의 빠르고 증분적인 구현이 필요할 것입니다.